No Title

Halmazelmélet és matematikai logika

TEMATIKA 2000/01 tél

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. bírósági vallomások.

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.

3.2 $\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.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. ${\mathcal Pred}_{\mathcal L}$ teljes. Teljességi tétel elso és második alakja és ezek következményei. Kompaktsági tétel.

Modellelmélet elemei

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

A Löwenheim-Skolem-Tarski tétel. 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.

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}\, {\mathfrak Q}$ , a racionális számok rendezésének elmélete végesen axiomatizálható. ${\mathcal Th}\, {\mathfrak Q}$ eldöntheto. ${\mathcal Th}\, {\mathfrak Q}$ kontinuumszámosságú nem izomorf modelljei. ${\mathcal Th}\, {\mathfrak 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))$ .

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ó. 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. Zorn lemma. Kiválasztási axióma az elemi analízisben.

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 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 kumulatív hierarchia. A halmazelmélet ZFC axiómarendszere.