Vizsgatematika

1. Itéletkalkulusbeli formulák. Tautológia, kielégíthető, elutasítható formula és formulahalmaz. Logikai kifejezések, szabadalgebra, diszjunktív és konjunktív normálformák.
2. Ultrafilter, főfilter, centrált rendszer. Véges halmazon minden ultrafilter főfilter. Valódi ultrafilter létezése. Frechèt filter, majdnem diszjunkt rendszer.
3. Itéletkalkulus kompatsági tétele.
4. Bizonyítások általában. Hilbert típusú bizonyítás (axióma, levezetési szabály) és tulajdonságai. Teljesség és helyesség. Itéletkalkulusban dedukció lemma.
5. Itéletkalkulushoz létezik teljes Hilbert típusú bizonyítás.
6. Elsőrendű logika: típus (jelkészlet), kifejezés, prímformula, formula. Struktúra, kiértékelés, formula igazsága egy struktúrában. Formulák ekvivalenciája.
7. Részstruktúra, elemi rész. Tarski-Vaught kritérium. Növő elemi lánc uniója. Példák, ellenpéldák.
8. Struktúrák szorzata. Ultraszorzat, ultrahatvány. Łoś lemma (mindkét változat).
9. Elsőrendű logika kompaktsági tétele ultraszorzattal. Alkalmazások.
10. Axiomatizálható és végesen axiomatizálható struktúraosztályok (Kiesler tételei). Példák, ellenpéldák.
11. Leszálló Löwenheim-Skolem tétel. Skolem-függvények. Skolem paradoxon.
12. Felszálló Löwenheim-Skolem tétel, következmények. Bizonyítás ultraszorzattal valamint növő elemi lánccal.
13. Diagram és elemi digram. Beágyazás részstruktúraként és elemi részként. Elemien ekvivalens struktúrák közös kiterjesztései.
14. Robinson konzisztencia tétele, interpolációs tétel.
15. Elsőrendű logikában a Hilbert-féle levezetés fogalma. Levezetési szabályok, kvantort manipuláló axiómák, egyenlőség axiómák. Dedukció lemma.
16. Elsőrendű logika Hilbert-féle teljessége: Henkin elmélet, tanusító konstansok, a bizonyítás befejezése.
17. Rekurzív, parciálisan rekurzív függvény, rek.rel definíciója. Példák (konstansok, gyök x egész része, paritás, <). Definíció esetszétválasztással. Rekurzív és rekurzíve felsorolható halmazok. Korlátos kvantorok.
18. A Gödel-féle β függvény. Sorozatok kódolása. 2ⁿ rekurzív. Rekurzív definíciók. Primitív rekurzió tétele.
19. Parc rek függvények kódolása.
20. Univerzális parc.rek függvény. Index, φ_i definíciója. Kleene normálforma tétel.
21. s-m-n tétel. Fixpont tétel.
22. Problémák, eldönthető és eldönthetetlen problémák. A megállási probléma megoldhatatlansága. Rice tétel.
23. Aritmetizálás: formulák kódolása természetes számokkal. Kifejezés, formula, levezethetőség rekurzivitása. Rekurzív és eldönthető elméletek. Példák nem rekurzív de eldönthető, stb. elméletekre.
24. Félgyűrűk, elemi tulajdonságok. Rek függvény reprezentálhatósága. Minden rek.függvény reprezentálható Q-ban.
25. Rekurzív és eldönthető elméletek definíciója. Church tétele. Gödel első nem-teljességi tétele.
26. A Lev, Helyettesítve, Con formulák definíciója. Fixpont tétel. A ν formula konstrukciója és bizonyíthatatlansága.
27. A Lev* formula definíciója; levezethetősége. Explicit példa független formulára (Rösser).
28. Gödel második nem-teljességi tétele, Con és Con* formulák, levezethetőségük, Löb tétele.

Előadás

Hogyan csináljunk minusz jelet ponttal fölötte?

\def\mindot{\mathop{\buildrel\textstyle.\over{\setbox0{\hbox{$-$}\ht0=0.6ex\box0}}}

A pontverseny végeredménye, jegyek