No Title

Halmazelmélet és matematikai logika

TEMATIKA

Szimbólumok, formulák, mondatok, propozicionális formulaalgebra, formulaindukció és -rekurzió, származtatott konnektívumok, elmélet.

1.1 Az igazságértékek Boole-algebrája, nevezetes 2-azonosságok, ${\mathbb Z}_2$ -azonosságok.

1.2Lehetséges modell, propozicionális értékelés, modellbeli (modellhez tartozó, modell által definiált, modellen(ben) való) igazság, formula és elmélet modellje, szemantikai következmény, tautológia (logikai igazság, érvényes formula), kielégíthetoség.

1.3Példák elméletekre: a. az átellenes oldalainak azonosan piros, kék ill. zöld színure festésével kapott kocka egyszeri feldobásának eredménye b. egy halmaz (részleges) rendezései c. gráf szinezés d. gráf Hamilton körei.

3.1 Logikai axiómak: implikáció- és konjunkcióaxiómák, bizonyítás, modus ponens, levezethetoség, szintaktikai következmény, elmélet tétele, a Ded operátor, logikai tétel, elmélet axiómái, elmélet bovítése (kiterjesztése).

3.2 Metatétel és metabizonyítás. $\vdash \varphi \Longrightarrow \varphi$ bizonyítása és következményei, az ellentmondás és a harmadik kizárásának törvénye, a meta- és a formalizált ÉS viszonyának elso alakja, ellentmondásból minden levezetheto, kettos tagadás egyik iránya.

3.3 Bizonyításelmélet elemei, a ` $\vdash$ ' tranzitivitása, az $\land$ és az ÉS, Ded lezárási operátor, dedukciós tétel, hamisból minden következik, indirekt bizonyítás. Néhány alapveto logikai tétel: kontrapozíció, kettos tagadás, de Morgan és általánosítása, ekvivalensek helyettesítése, stb. Példák az 1.3 pontbeli elméletek tételeire.

4.1 Inkonzisztencia, konzisztencia és maximális konzisztencia. Ekvivalens feltételek inkonzisztenciára, szintaktikai kompaktsági tétel, iff feltétel bovítés inkonzisztenciájára, maximálisan konzisztens elmélet jellemzoi.

4.2 Teljesség, teljes konzisztens elmélet jellemzése, maximális konzisztencia és teljesség, teljesség és Ded maximális konzisztenciája. Függetlenség, teljesség és függetlenség. Konzisztencia és teljesség mint egymás duálisai. Véges teljes bovítés.

Az axiómák érvényessége. A ${\mathcal Prop}_X$ logika. ${\mathcal Prop}_X$ helyes és konzisztens. Lindenbaum tétel. ${\mathcal Prop}_X$ teljes. Teljességi tétel elso és második alakja és ezek következményei. Kompaktsági tétel.

Modell elmélete maximális konzisztens. Elmélet modelljei elméleteinek kapcsolata. Függetlenség jellemzése modellekkel. Teljes elmélet jellemzése modelljeinek elméleteivel. Elmélet tételei és modelljének elmélete. Modell elméletének axiómái. Teljes konzisztens elmélet jellemzése modelljeivel.

Prédikátum kalkulus

1.1 Elsorendu nyelv, nem logikai szimbólumok, argumentumszám. Bovítés és reduktum. Nyelv számossága. A változójelek sorozata.

1.2 Termek, termalgebra, termindukció és -rekurzió. Atomi formulák, formulák, formulaindukció és -rekurzió. Logikai szimbólumok. Prédikátum formulaalgebra. Származtatott konnektívumok.

2.1 Modell, modell nyelve, univerzuma. Nyelv elemeinek interpretációi. Reduktum.

2.2 Értékelés, term értéke, formula kielégítése, igazsága, kielégíthetosége. Formula modellje, érvényessége. Elmélet modellje, szemantikai következménye. Véges értékelés.

2.3 Példák: a. matematikai elméletek mint formális elméletek modelljei b. intuitív logikai igazságok, mint formális tautológiák.

2.4 Elemi tények: formula igazsága, csak a szabad változók valódi változók, helyettesítési lemma, származtatott konnektívumok interpretációja, mondatok igazsága, összetett mondatok igazsága, term- és formulaértékelés reduktumon, konstansokkal képzett mondatok igazsága.

3.1 Logikai axiómak: propozicionális kalkulus axiómái, kvantoraxiómák, identitásaxiómák. Bizonyítás, modus ponens, generalizálás, levezethetoség, szintaktikai következmény, elmélet tétele, a Ded operátor, logikai tétel, elmélet axiómái, elmélet bovítése (kiterjesztése). Propozicionális kalkulusra szorítkozott levezethetoség, propozicionális logikai tétel, a Ded_p operátor.

3.2 $\vdash_p \varphi \Longrightarrow \varphi$ bizonyítása és következményei, az ellentmondás és a harmadik kizárásának törvénye, a meta- és a formalizált ÉS viszonyának elso alakja, ellentmondásból minden levezetheto, kettos tagadás egyik iránya.

3.4 Kötött változók cseréje, Leibniz elv (és amikor nem igaz), nem szabad változóra való kvantifikáció, term létezése, helyettesítés, term létezik, esetszétválasztás. Példák a 2.3 a. pontbeli elméletek tételeire. Peano aritmetika és tételei.

Az axiómák érvényessége. A ${\mathcal Pred}_{\mathcal L}$ logika. ${\mathcal Pred}_{\mathcal L}$ helyes és konzisztens. Lindenbaum tétel. ${\mathcal Pred}_{\mathcal L}$ teljes. Teljességi tétel elso és második alakja és ezek következményei. A teljességi tétel bizonyításának vázlata. Kompaktsági tétel.

Modellelmélet elemei

Izomorfizmus és elemi ekvivalencai. Példák. Izomorfizmus és elemi ekvivalencai kapcsolata. Elemei ekvivalencia és teljesség.

Elsorendu tulajdonság, elemi osztály. Véges axiomatizálhatóság. A véges és végtelen modellek osztályai. A pontosan n elemu modellek osztálya. Azon Abel csoportok osztálya, melyeknek minden eleme végesrendu. Azon Abel csoportok osztálya, melyeknek van nem triviális végesrendu elemük. Körmentes gráfok osztálya.

A Löwenheim-Skolem-Tarski tétel. Adott végtelen számosságú modellek osztálya. Standard és nem standard modellek. Az aritmetika megszámlálható nem standard modelljének létezése. A valós számok elméletének nem standard modellje. A végtelen és az infinitezimális szám fogalma. Konvergens sorozat és nem standard interpretációja.

Kategoricitás fogalma. Kategórikus elméletek létezése és a Löwenheim-Skolem-Tarski tétel. $\alpha$ -kategoricitás. A $\L$ os-Vaught teszt. A lineáris végpontnélküli suru rendezések elmélete $\omega$ -kategórikus. ${\mathcal Th}\, {\mathbb Q}$ , a racionális számok rendezésének elmélete végesen axiomatizálható. ${\mathcal Th}\, {\mathbb Q}$ eldöntheto. ${\mathcal Th}\, {\mathbb Q}$ kontinuumszámosságú nem izomorf modelljei. ${\mathcal Th}\, {\mathbb Q}$ nem teljes eldöntheto részelméletei.

Halmazelmélet

1.1 A tárgyalási univerzum: nyelv , szimbólumok, szabad és kötött változók, reláció szimbólum, identitás szimbólum, logikai szimbólumok, segédszimbólumok.

1.2 Szuk értelemben vett formulák, halmaz(szimbólum)ok, osztály(szimbólum)ok. Metaváltozók. Osztályrelációk.

1.4 Az univerzális és az üres osztály, a halmaz és a valódi osztály fogalma

2.1 Az extenzionalitási axióma, osztályazonosság, (valódi) részosztály és részhalmaz, azonosság elemi tulajdonságai. Halmaz, mint osztály, minden halmaz osztály, Russell paradoxon: nem minden osztály halmaz.

2.2 Pár, szingleton, rendezett pár. A páraxióma. Rendezett párok egyenlosége.

2.3 Unió, metszet. Az unióaxióma. Két osztály metszete, uniója és különbsége.

2.5 Descartes szorzat, inverz, reláció, egyértékuség, függvény, értelmezési tartomány, értékkészlet, (halmazra való) megszorítás, (függvény szerinti) kép, összetett függvény (kompozició), ^ab. A helyettesítési axiómaséma. Zermelo szeparáció axiómasémája. Üres halmaz axióma. Halmaz része halmaz. ${\mathcal M}(a \times b)$ , ${\mathcal M}({}^ab)$ , ${\mathcal Pr}(V)$ , ${\mathcal M}({\mathcal D}o\,(a))$ , ${\mathcal M}({\mathcal R}g\,(a))$ , ${\mathcal M}(\{f : f\,{\mathcal F}nc\,\,A \land {\mathcal R}g\,f \subseteq b \})$ . Függvény értéke, ${\mathcal M}\,(F(a))$ , ${\mathcal Fnc}\,(F) \Longrightarrow {\mathcal M}\,(F\,\vert\,a)$ .

3.1 Reflexivitás, irreflexivitás, szimmetria, tranzitivitás, részben és lineárisan való rendezettség. Maximális és minimális elem, legnagyobb (utolsó) és legkisebb (elso) elem, felso és alsó korlát, suprémum és infimum. Extremális elemek viszonya. Részhalmazreláció mint részben rendezés. $A \neq 0 \Longrightarrow {\mathcal M}(\cap A)$ .

3.2 Jólrendezettség, tranzitív halmaz, rendszám, eleme reláció, ${\mathcal On}$ . 0 rendszám, rendszám elemei rendszámok, rendszámok közös része rendszám. ${\mathcal Lo}\,\,({\mathcal On},\in^*)$ . $<_{\mathcal On}\, = \, \in^* \,=\, \subset^*$ . Rákövetkezo, 1,2,3, ..., rákövetkezo rendszám, rákövetkezo = közvetlen rákövet-
kezo, rákövetkezo és megelo monoton. ${\mathcal Wo}({\mathcal On},\in^*)$ . Burali-Forti paradoxon.
$A \subseteq {\mathcal On} \, \land \, {\mathcal Tr}(A) \Longrightarrow A \in {\mathcal On}\, \lor \, A = {\mathcal On}$ , $(\forall x \in A){\mathcal Tr}\,(x) \Longrightarrow {\mathcal Tr}\,(\cup\,A)\,\land\,{\mathcal Tr}\,(\cap\,A)$ , $A \subseteq {\mathcal On} \Longrightarrow \cup\,A \subseteq {\mathcal On}\,\land\,(A \neq 0 \Rightarrow \cap\,A \subseteq {\mathcal On})$ . Rendszámok minden nemüres részosztályának van elso eleme. $A \subseteq {\mathcal On} \Longrightarrow {\mathcal Sup}\,A \in {\mathcal On} \,\lor\, {\mathcal Sup}\,A = {\mathcal On}$

3.3 K_I, K_II. Rendszámok osztályozása, rákövetkezo és limesrendszám. Rendszámok jellemzése a rákövetkezés ill. a suprémum alapján. $\omega$ definíciója és tulajdonságai. A végtelenségi axióma. $\omega$ limesrendszám, transzfinit számok.

3.4 Transzfinit indukció elve, esetszétválasztásos és adott rendszámra szorítkozó transzfinit indukció. Szigorúan monoton növo függvény és tulajdonságai. Transzfinit rekurzió elve, esetszétválasztásos és adott rendszámra szorítkozó transzfinit rekurzió. Rendszámaritmetika.

3.5 A természetes számok. Peano axiómák. Véges rekurzió. Induktív halmazok izomorfak, $\omega$ egyértelmu, $\omega$ egyértelmuségének és az aritmetika nem standard modellje létezésének paradoxona. Az egész, a racionális, a valós és a komplex számok halmazának $\omega$ -ból való felépítése.

A kiválasztási axióma, kiválasztási függvény. Ekvivalencia, izomorfia, ekvivalencia és izomorfia ekvivalenciarelációk. Zermelo jólrendezési tétel, minden jólrendezett halmaz izomorf egy rendszámmal. Izomorf rendszámok azonosak, rendszámok egyetlen izomorfiája az identitás. Zorn lemma. A kiválasztási axióma, a Zermelo jólrendezési tétel és a Zorn lemma ekvivalenciája.

Számosság, ${\mathcal Ca}$ . Ekvivalencia és számosság. Részhalmaz számossága. Számosság számossága. Cantor-Schröder-Berstein tétel. Cantor tétele és a hatványhalmaz számossága. Számossághalmaz minden eleménél nagyobb számosság létezése és minden számosságnál nagyobb számosság létezése, A Cantor paradoxon. Számossághalmaz szuprémuma számosság, számosság rákövetkezoje, alephek, rákövetkezo és limes számosság. A kontinuum és az általánosított kontinuum hipotézis. A véges és végtelen halmaz fogalma, a végtelen számosságok limes rendszámok.

A regularitási axióma: minden nemüres halmaznak van $\in^*$ -minimális eleme. Nincs végtelen leszálló $\in^*$ -lánc, nincs véges $\in^*$ -ciklus, egyetlen halmaz sem eleme önmagának. A halmazelmélet ZFC axiómarendszere.