3) A matek alapjai

Naiv halmazelmelet

Ha $T$ valamilyen tulajdonsag, akkor van az a halmaz amely tartalmaz mindent melyre igaz $T$.
Mas szavakkal, ha $T$ egy tulajdonsag, akkor $\{x:T(x)\}$ azon $x$-ek halmaza melyekre teljesul $T$.

Ezzel a felepitessel sok dolog mukodik, de vannak nagyon alapveto problemak vele, mint peldaul a Russel paradoxon.

Russel paradoxon

Legyen $A=\{x:x\notin x\}$. Ekkor $A\in A⟺A\notin A$.
Szavakban: Legyen $A$ azon halmazok halmaza melyek nem tartalmazzak magukat. Ekkor $A$ csak akkor eleme onmaganak, ha nem eleme onmaganak. Mert ha $A\in A$ akkor $A$ egy olyan halmaz ami tartalmazza magat, tehat $A\notin A$. Viszont, ha $A\notin A$, akkor $A$ egy olyan halmaz ami nem tartalmazza magat, tehat $A\in A$.

Axiomatikus halmazelmet alapjai

0. Egyenlosegi axioma - Ha ket halmaznak ugyanazok az elemei, akkor egyenloek:
1. Letezesi axioma - Letezik halmaz. (Letezik a nullhazlmaz.)
2. Reszhalmaz axioma - Ha $A$ egy halmaz es $T(x)$ egy tulajdonsag, akkor $\{x\in A:T(x)\}$ is egy halmaz.
3. Par axioma - Tetszoleges $x$ es $y$-hoz letezik olya halmaz, mely csak oket tartalmazza, ergo letezik a $\{x,y\}$ halmaz.
4. Unio axioma - Ha $A_i$ halmazok, akkor $\cup A_i$ is halmaz.
5. Hatvany axioma - Ha $A$ halmaz, akkor $\mathcal{P}(A)$ is halmaz.
6. Vegtelen axioma - Van vegtelen halmaz. (Def.: Az $A$ halmaz vegtelen, ha van vegtelen reszhalmaza.)

Kivalasztasi axioma

Def.: Az $f:I\to \cup A_i$ fuggvenyt kivalasztasi fuggvenynek nevezunk, ha $f(i)\in A_i\forall i\in I$.
Axioma: A kivalasztasi axioma azt mondja, hogy ha $A_{i}i\in I$ nemures halmazok, akkor letezik kivalasztasi fuggveny.
Megj.: A kivalasztasi axioma szavakban azt mondja, hogy tetszoleges halmazokbol tudunk egyszerre valasztani egy-egy elemet minden halmazbol.

Szamossagok

Def.: $|A|=|B|$, ha letezik $A\to B$ bijekcio.
Def.: $|A|<|B|$, ha letezik $B\to A$ injekcio, de nem letezik $A\to B$ injekcio.

Muveletek szamossagokon

$|A|=a$, $|B|=b$
Ha $A\cap B=\varnothing$, akkor $|A\cup B|=a+b$.
$|A\times B|=a\cdot b$.

Cantor tetele

Tetel: Minden $A$ halmazra $|A|<\mathcal{P}(A)$. Azaz, minden halmaznak a szamossagi kisebb mint a hatvany halmazae.

Ismert halmazok szamossaga

Def.: Azt mondjuk, hogy ha egy halmaz szamossaga egyenlo $|\mathbb{N}|$-vel, akkor megszamolhato.
Def.: Azt mondjuk, hogy ha egy halmaz szamossaga egyenlo $|\mathbb{R}|$-vel, akkor megszamlalhatatlan.
Tetel: (Cantor) $|\mathbb{N}|<|\mathbb{R}|$.
Tetel: $|\mathbb{Q}|=|\mathbb{N}|$.
Tetel: $|{\mathbb{Q}}^{\ast }|=|\mathbb{R}|$.
Tetel: Folytonos $\mathbb{R}\to \mathbb{R}$ fuggvenyek szamossaga $|\mathbb{R}|$.
Tetel: Monoton $\mathbb{R}\to \mathbb{R}$ fuggvenyek szamossaga $|\mathbb{R}|$.
Tetel: $[0,1]\sim [0,1]\times [0,1]\sim \mathbb{R}$.

A valos szamok felepitese

Def.: (Dedekind szelet) Legyen $A\subset \mathbb{Q}$ es $A\ne \varnothing$ es $A\ne \mathbb{Q}$ racionalis szamok nemures valodi reszhalmaza. Azt mondjuk, hogy az $A$ halmaz dedekind szelet, ha lefele zart es nincs legnagyobb eleme, azaz

• ha $x\in \mathbb{Q}$, $y\in A$ es $x<y$, akkor $x\in A$,
• ha $x\in A$, akkor $\exists y\in A$ ugy, hogy $y>x$.

Ezekkel a szeletekkel tudjuk reprezentalni a valos szamokat, pl a $A=\{a\in \mathbb{Q}:a^2<2,\text{ vagy }a<0\}$ reprezentalja a $\sqrt{2}$ szamot.

Rendezes, jojlrendezes

Def.: A $<$ muveletet rendezesnek hivjuk az $A$ halmazon, ha

• irreflexiv, azaz $\nexists a\in A$, melyre $a<a$,
• tranzitiv, azaz $a,b,c\in A$ es $a<b$ es $b<c$, akkor $a<c$,
• trichotomia: $a,b\in A$ akkor a kovetkezo harom kozul pontosan egy teljesul: $a<b$, $a>b$, $a=b$.

Def.: Az $(A,<)$ parost rendezett halmaznak hivunk.
Def.: Az $(A,<)$ rendezett halmzt jol rendezettnek hivunk, ha minden nemures reszhalmazanak van legkisebb eleme.
Tetel: Minden halmaz jolrendezheto.
Megj.: Ez ekvivalens a kivalasztasi axiomaval.

Igazszagfuggvenyek

Def.: Egy $f:\{i,h{\}}^n\to \{i,h\}$ fuggvenyt igazsag fuggvenynek nevezunk, ahol $i$ igazat jelol es $h$ hamisat.
Jelolesek:

• $\wedge$ - logikai es
• $\vee$ - logikai vagy
• $\to$ - ha … akkor …
• $\oplus$ - xor
• $\leftrightarrow$ - xnor
• $|$ - nand

Kijelenteslogika

Tetel: Nevezetes azonossagok, tulajdonsagok

• $\neg (\neg A)=A$
• $\neg A\wedge A=h$
• $\neg A\vee A=i$

kommutativ:

• $A\vee B=B\vee A$
• $A\wedge B=B\wedge A$
  reflexiv:
• $A\vee A=A$
  asszociativ:
• $(A\vee B)\vee C=A\vee (B\vee C)$
• $(A\wedge B)\wedge C=A\wedge (B\wedge C)$
  elnyeles:
• $(A\vee B)\wedge A=A$
• $(A\wedge B)\vee A=A$
  disztributivitas:
• $A\wedge (B\vee C)=(A\wedge B)\vee (A\wedge C)$
• $A\vee (B\wedge C)=(A\vee B)\wedge (A\vee C)$
  de Morgan azonossagok:
• $\neg (A\vee B)=\neg A\wedge \neg B$
• $\neg (A\wedge B)=\neg A\vee \neg B$

Igazsagtablazatok

Def.: Egy $f:\{i,h{\}}^n\to \{i,h\}$ $n$ valtozos igazsagfuggvenyt lehet reprezentalni egy tablazattal, melynek $2^n$ sora van van es $n+1$ oszlopa. Az elso $n$ oszlopban szerepel az osszes $2^n$ lehetseges $\{i,h{\}}^n$ ertek, mig az utolso oszlapban szerepel a fuggveny erteke arra az igaz-hamis ertekadasnak.

Pelda: xor igazsagtablazata

$x_1$	$x_2$	$x_1\oplus x_2$
i	i	h
i	h	i
h	i	i
h	h	h

Teljes diszjunktiv normalforma

Def.: A

$$(y_{1_1}\wedge \cdots \wedge y_{1_k})\vee (y_{2_1}\wedge \cdots \wedge y_{2_{k^{\prime }}})\vee \cdots \vee (y_{n_1}\wedge \cdots \wedge y_{n_{1_{k^{\prime \prime }}}})$$

alakot teljes diszjunktiv normalformanak hivunk, ahol $y_i=x_l$ vagy $y_i=\overline{x_l}$.
Tetel: Minden nem konstans hamis igazsag fuggveny eloall teljes diszjunktiv normal formaban.

Teljes rendszerek

Def.: Muveletek egy halmaza teljes rendszer, ha tetszoleges igazsag fuggvenyt elo tudunk allitani ezen muveletek valamilyen kombinaciojakent.
Peldaul: $\{\neg ,\wedge ,\vee \}$ teljes rendszer, mivel a de Morgan azonossagokkal elo tudjuk allitani $\wedge$-et $\neg$ es $\vee$ hasznalataval, es forditva, ezert $\{\neg ,\wedge \}$ es $\{\neg ,\vee \}$ es teljes rendszerek.

Tetel: (Post-Jablonszkij) Igazsagfuggvenyeknek egy $\mathcal{F}$ rendszere pontosan akkor teljes, ha nem reszrendszere $K_i,K_h,U,\mathcal{L},\mathcal{M}$ egyike sem.
Tetel: Minden teljes rendszerbol kivalaszthato legfeljebb $5$ eleme teljes reszrendszer.

Kovetkeztetesek

Def.: Egy formula tautologia, ha minden igazsagertekeles eseten igaz.
Tetel: A kovetkezo formulak mind tautologiat adnak:

• $A\to (B\to A)$
• $(A\to (B\to C))\to ((A\to B)\to (A\to C))$
• $(\neg A\to B)\to ((\neg A\to \neg B)\to A)$

Def.: A fenti tautologiakat a nulladrendu logika axiomasemajanak nevezzuk.
Def.: Azt mondjuk, hogy egy $\alpha$ formula levezetheto a $\Sigma$ formulahalmazbol, ha letezik formulaknak ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n=\alpha$ veges sorozata, ahol minden ${\alpha }_i$ vagy axioma, vagy eleme $\Sigma$-nak, vagy letezik ket korabbi ${\alpha }_j,{\alpha }_k$ melyekkel ${\alpha }_k={\alpha }_j\to {\alpha }_i$. Jelolesben $\Sigma ⊢\alpha$.
Megj.: Az utolsot ugy hivjuk hogy modus ponens es azt jelenti, hogy ha van egy olyan allitasunk, hogy $A$-bol kovetkezik $B$ es tudjuk hogy $A$ igaz akkor $B$-nek is igaznak kell lennie.

Tetel: (indirekt bizonyitas) $\{\neg \alpha \to \neg \beta ,\beta \}⊢\alpha$.
Ha $\alpha$ tagadasabol kovetkezik $\beta$ tagadasa, mikozben $\beta$ igaz, akkor $\alpha$ igaz.

Tetel: $\{\phi ,\neg \phi \}⊢\psi$ tetszoleges $\psi$-re.

Elsorendu nyelvek

Def.: $\mathcal{L}$ elsorendu nyelv, ha

• valtozojelek - $v_0,v_1,v_2,\dots$
• konstansjelek - $c_0,c_1,c_2,\dots$
• fuggvenyjelek - $f_0,f_1,f_2,\dots$
• relaciojelek - $R_0,R_1,R_2,\dots$
• logikai jelek - $\neg ,\wedge ,\vee ,\to$
• kvantorok - $\forall ,\exists$
• segedjelek - "$($" es "$)$" es "$,$"
  mindegyikhez tartozik egy pozitiv egesz szam, hogy hany valtozos.
  Szokasosan $R_0$ egy $2$ valtozos relaciojel, ami az egyenloseg.

Def.: A kovetkezoket hivjuk kifejezeseknek:

• minden valtozojel kifejezes
• minden konstansjel kifejezes
• ha $f$ egy $n$ valtozos fuggveny jel, es $t_1,\dots ,t_n$ kifejezesek, akkor $f(t_1,\dots ,t_n)$ kifejezes

Def.: A kovetkezoket hivunk formulaknak:

• (kifejezesek relacioja formula) ha $R$ egy $n$ valtozos relaciojel, es $t_1,\dots ,t_n$ kifejezesek, akkor $R(t_1,\dots ,t_n)$ formula
• (formulak vagyolasa formula) ha $\phi$ es $\psi$ formulak, akkor $\phi \vee \psi$ is formula
• (formula tagadasa formula) ha $\phi$ formula, akkor $\neg \phi$ formula
• ha $v_i$ valtozojel es $\phi$ es formula, akkor $\exists v_i\phi$ formula