BMETE91AM60

Nyomtatóbarát változatNyomtatóbarát változat
Tantárgy azonosító adatok
A tárgy címe: 
Halmazelmélet és matematikai logika
A tárgy angol címe: 
Set Theory and Mathematical Logic
A tárgy rövid címe: 
HalmazelméletÉsMatematikaiLogika
4
0
0
v
Kredit: 
4
A tantárgy felelős tanszéke: 
Algebra Tanszék
A tantárgy felelős oktatója: 
Dr. Sági Gábor
A tantárgy felelős oktatójának beosztása: 
egyetemi docens
Akkreditációs adatok
Akkreditációs bizottság döntési időpontja: 
2022.05.16.
Tematika
A tantárgy szerepe a képzés céljának megvalósításában: 
TTK Matematika BSc szak Elméleti specializációjának kötelezően választható tárgya
A tantárgy részletes tematikája magyarul és angolul: 

Logika: A nulladrendű és az elsőrendű logika nyelve. Kitekintés a magasabb rendű nyelvekre. A nulladrendű és az elsőrendű nyelvek szemantikája. Normálformák. Galois-⁠kapcsolat modellosztályok és formulahalmazok között. Logikai következmény fogalma és kapcsolata az implikációval. Dedukciós tétel, a következmény jellemzése az ellentmondásosság fogalmával. A bizonyításelméletről, levezetési és cáfolati rendszerek. Hilbert típusú kalkulus kijelentéslogikára, nulladrendű teljességi tétel. Az elsőrendű logika néhány teljes, illetve cáfolat-teljes kalkulusa (rezolúció, analitikus fák, stb.). Kompaktsági tétel. Löwenheim-Skolem tételek. Izomorfizmus és elemi ekvivalencia. Eldönthető és eldönthetetlen elméletek. A levezethetőség fogalmának aritmetizálása vázlatosan. Church és Gödel tételei.

Halmazelmélet: Halmazok ekvivalenciája. A kiválasztási axióma és egyszerű következményei: megszámlálható sok megszámlálható halmaz uniója is megszámlálható. A Bernstein-féle antiszimmetria tétel. Tetszőleges halmaz és hatványhalmaza nem ekvivalensek. A számosságok naiv definíciójának ellentmondásossága. A ZFC axiómarendszer. Új operációk és relációk bevezetése. Rendezett pár, reláció, függvény fogalma. Rendezett halmaz, jólrendezés. Rendszámok és alaptulajdonságaik. A rendszámok valódi osztályt alkotnak. Rendszámok rákövetkezői, rendszámokból álló halmazok szuprémumai, és az ezekre vonatkozó tételek. Limeszrendszámok létezése. Transzfinit indukció és transzfinit rekurzió. A kiválasztási axióma két ekvivalense (Zorn--lemma, és jólrendezési tétel: minden halmazhoz van vele ekvivalens rendszám. A számosságoperáció és néhány alaptulajdonsága: minden végtelen számosság limeszrendszám. Példák. Műveletek számosságokon, és ezek néhány tulajdonsága. Általános disztributivitási szabály. Kofinalitás operáció, tételek végtelen számosságokra. A számosságaritmetika alaptétele. Az alef-operáció. Példák: néhány klasszikus matematikai objektum számossága. A kontinuum-probléma. Néhány nevezetes, ZFC-től független állítás. Rang, kumulatív hierarchia és alaptulajdonságaik. A regularitási axióma ekvivalens azzal, hogy minden halmaznak van rangja.

Kitekintés:
-- Ultraszorzatok, axiomatizálhatóság, nemsztenderd valós számok.
-- Kategoricitás, és teljesség kapcsolata. Megszámlálhatóan kategorikus elméletek és jellemzésük modelljeik automorfizmus-?csoportjával. Véletlen gráfok, 0-1-törvények.
-- Algebrai módszerek a logikában.
-- Transzfinit módszerek a halmazelméleten kívül (algebrailag zárt test transzfinit konstrukciója, a síknak van olyan részhalmaza, mely minden egyenest pontosan 2 pontban metsz, stb.).
-- Hamel-bázisok, és létezésük néhány érdekes következménye.
-- A partíciókalkulus alapjai (a végtelen Ramsey-elmélet néhány egyszerűbb tétele).




Logic: The language of zero-⁠order and first-⁠order logic. An overview of higher-⁠order languages. Semantics of zero-⁠order and first-⁠order languages. Normal forms. Galois connection between model classes and sets of formulas. Logical consequence and its relation to implication. Deduction theorem, characterization of consequence by the notion of inconsistency. On proof theory: derivation and refutation systems. Hilbert type calculus for propositional logic, zero-⁠order completeness theorem. Some (refutation-⁠)complete calculi of first-⁠order logic (resolution, analytic trees, etc.). Compactness theorem. Löwenheim-⁠Skolem theorems. Isomorphism and elementary equivalence. Decidable and undecidable theories. Outline of the arithmetization of derivability. The theorems of Church and Gödel.

Set theory: The equivalence of sets. The axiom of choice and some basic consequences; countable unions of countable sets are countable. Bernstein's antisymmetry theorem. A set and its power set are never equivalent. The naive definition of cardinality leads to a contradiction. The ZFC axioms. Introducing new operations and relations. Ordered pairs, relations, functions. Partial orders, total orders, well-orders. Ordinals and their basic properties. Ordinals form a proper class. Each ordinal has a successor ordinal, each set of ordinals has a supremum. The existence of limit ordinals. Transfinite induction and transfinite recursion. The axiom of choice and two equivalent characterizations: Zorn's lemma and Zermelo's well-ordering theorem (every set has a well-ordering). The definition of the cardinality operation and some of it's basic properties. Every infinite cardinal is a limit ordinal. Examples. Cardinal arithmetic: addition, multiplication and exponentiation of cardinals and some of their basic properties. The general distributive law. The cofinality operation. Theorems about infinite cardinalities. The fundamental theorem of cardinal arithmetic. The aleph-operateion. Examples: the cardinalities of some well-known mathematical objects. The continuum-problem. Some well-known statements which are independent from ZFC. The cumulative hierarchy of sets; the rank operation and its basic properties. The axiom of regularity is equivalent to the statement that every set has a rank.

Outlook:
-- Ultraproducts, axiomatizability, nonstandard real numbers.
-- Connections between categoricity and completeness. Countably categorical theories and their characterization by the automorphism group of theirs models. Random graphs, 0-1-laws.
-- Algebraic methods in logic.
-- Transfinite methods outside of set theory: the transfinite construction of algebraically closed fields; the plane has a subset which intersects each line in exactly 2 points, etc.
-- The existence of a Hamel-basis and some interesting consequences.
-- Fundementals of partition calculus; some introductory results in
infinite Ramsey-theory.

Követelmények vizsgaidőszakban: 
írásbeli és szóbeli vizsga
Pótlási lehetőségek: 
A TVSZ szerint
Konzultációs lehetőségek: 
Az oktatóval egyeztetve
Jegyzet, tankönyv, felhasználható irodalom: 
Joseph R. Shoenfield, Mathematical Logic, CRC Press, 2018
Andras Hajnal, Peter Hamburger, Set Theory, Cambridge University Press, 1999
Hajnal András, Hamburger Péter, Halmazelmélet, Budapest, Tankönyvkiadó, 1983
Totik Vilmos, Halmazelméleti feladatok és tételek, Szeged, Polygon, 1997
A tárgy elvégzéséhez átlagosan szükséges tanulmányi munka mennyisége órákban (a teljes szemeszterre számítva)
Kontakt óra: 
56
Félévközi felkészülés órákra: 
14
Felkészülés zárthelyire: 
0
Zárthelyik megírása: 
0
Házi feladat elkészítése: 
0
Kijelölt írásos tananyag elsajátítása (beszámoló): 
0
Egyéb elfoglaltság: 
0
Vizsgafelkészülés: 
50
Összesen: 
120
Ellenőrző adat: 
120
A tárgy tematikáját kidolgozta
Név: 
Dr. Sági Gábor
Beosztás: 
egyetemi docens
Munkahely (tanszék, kutatóintézet, stb.): 
Algebra Tanszék
A tanszékvezető neve: 
Dr. Nagy Gábor Péter