Alapadatok
Év, oldalszám:2005, 23 oldal
Nyelv:magyar
Letöltések száma:125
Feltöltve:2007. augusztus 31.
Méret:180 KB
Intézmény:
-
Megjegyzés:
Csatolmány:-
Letöltés PDF-ben:Kérlek jelentkezz be!
Értékelések
Nincs még értékelés. Legyél Te az első!
Legnépszerűbb doksik ebben a kategóriában
Tartalmi kivonat
Sereny Gyorgy LET ELEMEI HALMAZELM E Vazlat 1. A targyalasi univerzum 1.1 A nyelv a. Szimbolumok (i) Szabad valtozok: v2; v4 ; : : : , Kotott valtozok: v1 ; v3; : : : ; (ii) Relacio szimbolum: 2 Identitas szimbolum: = (iii) Logikai szimbolumok Els}odleges: :; ^; 8 Szarmaztatott: ); ; () ; 9 (iv) Segedszimbolumok: (; ); [; ]f; g; : A szabad valtozok feletti metavaltozok: a; b; c; d es indexelt valtozataik A kotott valtozok feletti metavaltozok: x; y; z; w es indexelt valtozataik. b. Sz}uk ertelemben vett formulak (i) Ha a; b szabad valtozok, akkor a 2 b sz}uk ertelemben vett formula (ii) Ha es sz}uk ertelemben vett formulak, akkor : es ^ is azok (iii) Ha sz}uk ertelemben vett formula, akkor (8x)(x) is az, ha x nem kotott valtozoja {nek, ahol itt es a tovabbiakban is tetsz}oleges eseten (x) az a formula, melyet ugy kapunk, hogy valamely szabad valtozojanak minden el}ofordulasat kicsereljuk x{re De ncio (i)
) $ :( ^ : ) (iv) () $ ( ) ) ^ ( Megjegyzes ) ) (ii) $ : ) (v) (9x) $ :(8x)(x) (iii) F $ : c1 = c1 1) A fenti es a tovabbikban bevezetend}o szimbolumok szandekolt jelentese termeszetesen a szokasos. 2) Ha mast nem mondunk, ; ; sz}uk ertelemben vett formulakat jelolnek. 3) =) es ) ugyanazt jelentik. A tagadast gyakran athuzassal jeloljuk, peldaul a 62 b $ :(a 2 b). Neha elhagyjuk az ^{t, pl a 2 b 2 c $ a 2 b ^ b 2 c vagy ) ) $ ( ) ) ^ ( ) ) es persze a felesleges zarojeleket is. 4) A meta `ha : : : akkor , azaz a `mivel : : : tehat jelolese a kovetkez}o: , mg a meta{ellentmondase: . 5) Ahogy mar eddig is tettuk, a `de ncio szerint legyen kifejezes rovidtesere a szokasos $ jelolest hasznaljuk. ; De ncio A szabad valtozokat halmaz(szimbolumok)nak es a fx : (x)g kifejezeseket osztaly(szimbolumok)nak nevezzuk. Az osztalyok es halmazok feletti metavaltozok a nagybetuk : A; B; C; : : : (esetleg indexekkel) es
nehany esetben specialis szimbolumok, pl. < De ncio 2f g (i) a x : (x) $ (a) ahol persze (a) az a formula, melyet {ben azon szabad valtozo minden el}ofordulasanak a{ra valo cserelesevel kapunk, melynek minden el}ofordulasanak x{re valo cserelesevel (x){et kaptuk es x nem szerepel {ben. 1 8 2 () x 2 B 9 ^x2B (ii) A = B $ ( x)(x A ha A es B kozul legalabb az egyik osztaly. (iii) A B $ ( x)(x = A ha A osztaly. 2 ) ) 1.2 Bizonytas a. Logikai axiomak (i) Propozicionalis axiomak (ii) Kvantoraxiomak: (1) (8x)( ) (x)) ) ( ) (8x) (x)), ahol az a szabad valtozo, melynek x{re valo cserejevel (x){et kaptuk nem fordul el}o {ben. (2) (8x)(x) ) (a), ahol (a) az a formula, melyet {b}ol azon szabad valtozo minden el}ofordulasanak a{ra valo cserelesevel kapunk, melynek minden el}ofordulasat x{re cserelve kaptuk (x){et. (iii) Identitas axiomak a = a; a = b ) ((a) ) (b)), ahol (a) es (b) az a formula, melyet {b}ol valamely szabad
valtozo minden el}ofordulasanak a{ra ill. b{re valo cserejevel kapunk b. Levezetesi szabalyok (i) Modus ponens: es ( ) ) (ii) Generalizalas: (8x)(x) ; Megjegyzes ; A bizonytasi rendszer tehat a predikatumkalkulus szokasos bizonytasi rendszerenek a sz}uk ertelmeben vett formulakra szortkozott valtozata, annak minden eredmenye gy kozvetlenul alkalmazhato. Megtehettuk volna eppen azt is (csak kevesbe lett volna elegans), hogy megtartjuk az L = h2i els}orend}u nyelv teljes bizonytasi rendszeret. Ekkor teljesen nyilvanvalo, hogy minden predikatumkalkulusbeli eredmeny atvihet}o a sz}uk ertelemben vett formulakra, hiszen ezek L osszes formulainak egy reszhalmazat alkotjak. 1.3 Alapfogalmak De ncio V $ x:x=x 0$ x:x=x A lltas f f g 6 g univerzalis osztaly ures osztaly (i) (8x)(x 2 V ) (ii) (8x)(x 62 0) De ncio (A) $ ( x)(x = A) r(A) $ (A) M P 9 :M halmaz (Menge (Cantor)) valodi osztaly (proper class) 2
Hasznos jelolesek (i) fA(x1 ; : : : ; xn) : (x1 ; : : : ; xn)g $ fx : (9x1 )(9x2 ) : : : (9xn )(x = A(x1 ; : : : ; xn ) ^ (x1 ; : : : ; xn )g, ahol A(x1 ; : : : ; xn) es (x1 ; : : : ; xn ) ugyanazoknak a szabad valtozoknak a kicserelesevel adodik A ill. {bol (ii) (a) (8x1 ; : : : ; xn) $ (8x1 ) : : : (8xn) (b) (9x1 ; : : : ; xn) $ (9x1 ) : : : (9xn) (iii) (a) (8x 2 A) $ (8x)(x 2 A ) ) (b) (9x 2 A) $ (9x)(x 2 A ^ ) (c) fx 2 A : (x)g $ fx : x 2 A ^ (x)g. Tobbvaltozora analog (iv) (9 ! x) (x) $ (9x)(x) ^ (8x)(8y)((x) ^ (y) ) x = y) 2. Az els}o ot axioma Az extenzionalitasi axioma (Ax1): 8x x 2 a () x 2 b ) a ( Kovetkezmeny A=B (8x)(x 2 A () )( ) = 8 2 A=B A lltas () ) 2 ^ A B ^ b x B) () 2 De ncio A B $ ( x)(x A x B ) A B$A(B$A B A=B Jeloles A B $ B A, A B $ B A Kovetkezmeny = resz(osztaly/halmaz) valodi resz(osztaly/halmaz) 6 B A (i) (a) A = A (b) A = B ) B = A (c) A = B ^ B = C ) A = C (ii) A =
B ) ((A) () (B )) A lltas (i) a = fx : x 2 ag (ii) P r(fx : x 62 xg) (russel paradoxon) Kovetkezmeny (i) Minden halmaz osztaly (ii) Nem minden osztaly halmaz De ncio a; b $ x : x = a x = b a $ a; a (a; b) $ a ; a; b f f g g f f par szingleton rendezett par g g ff g f gg 3 A paraxioma (Ax2): M fa; bg ( A lltas (a; b) = (c; d) De ncio [ a=c b=d () ^ A = x : ( y)(x y y A A = x : ( y)(y A x y f 9 2 f 8 2 Feladat a A= 2 ) A a ) ^ 2 ) [ unio metszet g 2 g A Az unioaxioma (Ax3): M [a ( Megjegyzes ) Eddig es a tovabbiakban is, amennyiben valamely uj osztaly tipust csak halmazokra de nialunk, mint peldaul a part { szemben az unioval { , ez azt jelenti, hogy csak halmazokra, de minden halmazra de nialtuk ezt a jelolest, azaz peldaul f Ru g nem de nialt, de { az unioaxioma miatt { f[ ag igen, nevezetesen persze? f[ ag $ fx : x = [ a x = [ ag = fx : x = [ ag = fx : (8y ) y 2 x () (9z )(y 2 z
^ z 2 a) g. Ugyanakkor termeszetesen [ Ru jol de nialt : [ Ru = fx : (9y)(x 2 y ^ y 2 Ru)g = = fx : (9y)(x 2 y ^ y 62 y)g . De ncio A B$ x:x A x B A B$ x:x A x B A B$ x:x A x B A lltas [ f 2 2 g f 2 ^ 2 g n f 2 ^ 62 unio metszet kulonbseg g (i) a [ b = [fa; bg (ii) a b = fa; bg Kovetkezmeny (a [ b) M [ par{ es unioaxioma ] De ncio (a) $ x : x a P f hatvanyhalmaz g A hatvanyhalmazaxioma (Ax4): MP ( A lltas (i) [ P (a) = a (ii) a P ([ a) (i) a =? P ([ a) (ii) a P ([ a) Kerdes ? 4 a ( )) De ncio A B $ (x; y) : x A y B A2 $ A A A?1 $ (y; x) : (x; y) A el(A) $ A V 2 n(A) $ ( x; y; z)((x; y); (x; z) A y = z) nc(A) $ el(A) n(A) o(A) $ x : ( y)((x; y) A) g(A) $ y : ( x)((x; y) A) F nc A $ nc (F ) o(F ) = A A B $ (x; y) A : x B A B $ g(A B ) A B $ (x; y) : ( z)((x; z) B (z; y) A) F : A B $ F nc A o(F ) B , ab $ f : f : a b Jeloles xRy $ (x; y) R A lltas f 2 ^ 2 g f 2 R g U 8 2 F
R ^U D f 9 2 g R f 9 2 g F F j ^D f R ) 2 2 g j f 9 ! F 2 ^D ^ 2 g f Descartes szorzat inverz relacio egyertek}u fuggveny ertelmezesi tartomany (domain) ertekkeszlet (range) megszortas kep osszetett (kompozicio) ! g 2 A B = y : ( x B )( (x; y) A ) f 9 2 2 g A helyettestesi axiomasema (Ax5): F nc F ) M F a ( ) ( ) Kovetkezmeny (zermelo szeparacio axiomasemaja) (a A) [ F $ f(x; y) : x 2 A ^ x = yg =) F nc(F ) ^ F a = a A ] Kovetkezmeny (ures halmaz axioma) M(0) [ ((8x)(x 62 A) ) A = 0) ^ (A $ fx : x 62 ag =) a A = 0) ] Kovetkezmeny (halmaz resze halmaz) A a =) M(A) M Kovetkezmeny (i) M(a b) (ii) M(ab) (iii) P r(V ) [ (i) a b P (P (a [ b)) (ii) a b P (a b) (iii) fx : x 62 xg V ] A lltas (i) M(Do (a)) (ii) M(Rg (a)) [ (i) F $ f((x; y); x) : (x; y) 2 ag =) F F nc a ^ F a = Do (a) ; (ii) analog. ] Kerdes (i) M(ff : f F nc ag) ? (ii) M(ff : f F nc A ^ Rg f bg) ? 5
[ (i) a 6= 0 ) P r (ff : f F nc ag) mert F $ ?y; f(x; y) : x 2 ag : y 2 V =) ) Rg(F ) ff : f F nc ag ^ (a 6= 0 ) F ?1 F nc Rg(F ) ^ Rg F ?1 = V ) ^ P r (V ) . (ii) M(Do (f )) (9a)(ff : f F nc A ^ Rg f bg = a b) ] De ncio ? F (a) $ x : ( y)(x y (a; y) F ) ( ! y) (a; y) F ertek A lltas ? ; f 9 2 ^ 2 ^ (i) (9 ! y) (a; y) 2 F =) (F (a) = b (ii) M (F (a)) (iii) F nc (F ) =) M (F j a) [ (iii) F j a a F a ] 9 () 2 g (a; b) 2 F ) Kerdes Fenti (iii){ban kell a F nc (F ) feltetel ? [ Igen: ? f0g V f0g = V ] Jeloles S x2A F (x) $ [f Feladat S D o( T F (x) : x A 2 x2A F (x)) = g S x2A F (x) $ fF (x) : x 2 Ag T x2A Do (F (x)) ( {re es Rg{re analog ) 3. Rendszamok 3.1 Rendezes Jeloles a>b$b<a a b $ a<b a=b a b De ncio ef (A; <) $ ( x A)(x < x) rr (A; <) $ ( x A)(x < x) ym (A; <) $ ( x A)( y A)(x < y y < x) rs (A; <) $ ( x; y; z A)(x < y y < z x < z) o (A; <) $ rr (A; <) rs (A;
<) o (A; <) $ o (A; <) ( x; y A)(x y y x) a ax< A $ a A ( x A)(a < x) a in< A $ a A ( x A)(x < a) a st< A $ a A ( x A)(x a) a st< A $ a A ( x A)(a x) a b< A $ ( x A)(x a) a b< A $ ( x A)(a x) a up< A $ a st< x : x b< A a nf< A $ a st< x : x b< A R 8 I 8 S 6 2 8 P I L P 2 2 8 T 8 2 ) 2 ^ ) ^T ^ 8 2 M 2 ^: 9 2 M 2 ^ : 9 2 L 2 ^ 8 2 F 2 ^ 8 2 U 8 2 L 8 2 S F I L f f U L g g 6 $ a>b a=b re exv irre exv szimmetrikus tranzitv (reszben) rendezett (partially ordered) linearisan rendezett (linearly ordered) (lanc) maximalis minimalis legnagyobb (utolso, last) legkisebb (els}o, rst) fels}o korlat (upper bound) also korlat (lower bound) supremum in mum A lltas (i) (a) P o (A; <) ^ a; b 2 A =) (a < b ) b 6 a) (b) Lo (A; <) ^ a; b 2 A =) (a 6< b ) b a) (ii) (a) a Lst< A =) a Max< A (b) a F st< A =) a
Min< A (c) Lo (A; <) =) (a Max< A ) a Lst< A) ^ (a Min< A ) a F st< A) (iii) (a) a S up< A ^ a 2 A =) a Lst< A (b) a I nf < A ^ a 2 A =) a F st< A (iv) (a) a Lst< A ^ b Lst< A =) a = b (b) a F st< A ^ b F st< A =) a = b Megjegyzes (i)(b), (ii)(c){ben a Lo (A; <) feltetel kell: < $ f(c; a); (c; b)g; A $ fa; b; cg. A lltas Ha $ (x; y) : x y , akkor f (i) P o (A; ) (ii) (a) Kovetkezmeny A=0= 6 g [ A up A A nf A (b) S I ( A) ) M [ Halmaz resze halmaz ] Megjegyzes Feltetel kell: 0 = V De ncio (i) up A $ A A lltas S (ii) I nf A $ A [ (i) A B =) S up A S up B (ii) A B =) I nf A I nf B 3.2 Elemi rendszamelmelet De ncio o (A; <) $ o (A; <) ( x)(x A x = 0 r (A) $ ( x)(x A x A) $ (a; b) : a b rd(a) $ r (a) o (a; ) n $ x : rd(x) W T 2 L 8 2 f 2 O O ^ T f Jeloles ) ^ 6 ) (9y)(y F st< x)) jolrendezett (well ordered) tranzitv g ^ W O
8 rendszam (ordinal) 2 g Gorog bet}u mindig rendszamot jelol, tehat peldaul: ( ) $ Ord( ) ^ ( ), (8 )( ) $ (8x)(Ord(x) ) (x)), (9 )( ) $ (9x)(Ord(x) ^ (x)): De ncio <On $ < $ A lltas 2 jO n azaz < () 2 . (i) Ord(0) (ii) T r(On) (rendszam elemei rendszamok) 7 (iii) Ord(a) ^ Ord(b) ) Ord(a b) (iv) ^ 6= ) 2 (v) [ (ii) (b 2 =) b ) =) x; y 2 [y ] ; ; Wo(b; 2 ) ; ? x2y2b2 =) x 2 y 2 =) [b 2 ; b ] [b 2 ^ T rs ( ; 2 ) =) (x 2 y 2 b =) x 2 b)] T r (b). ; (iv) ^ 6= =) n 6= 0: $ F st2 ( n ) =) = f : < g. Ugyanis egyreszt, 2 ^ 6< =) ^ < =) 2 =) F , masreszt, ξ γ < =) 2 2 =) 2 ^ 62 n =) 2 . Igy valoban = f : < g = 2 : α β (v) El}oszor is: 6= =) = . Ugyanis, $ ^ 6= ^ 6= =) =) 2 ^ 2 =) 2 =) F. Ezert 6 =) 6= =) [ ^ es (iv) ] =) = =) . ] Kovetkezmeny (i) Lo (On; 2) (ii) = f : < g (iii) < () 2 () (iv) () (v) 6= 0 () > 0 [ (i) 1) 2 =) (9 2
)( 2 ) =) F . 2) T r( ) 3) A lltas (iv) es (v) ] De ncio +1$ Pelda 1$ 0+1=0 3$ 2+1=2 A lltas [ f (i) (ii) (iii) (iv) rakovetkez}o g 0 = f0g ; 2 $ 1 + 1 = 1 [ f1g = f0g [ f1g = f0; 1g; [ f2g = f0; 1g [ f2g = f0; 1; 2g; : : : [ f g + 1 2 On < +1 < + 1 () + 1 () (azaz :(9 )( < < + 1) ) + 1 < + 1 () < Lo( + 1; 2 ). 2) W o( + 1; 2 ): t fel h ; a) h 6= 0 ^ F st ( h) =) F st h , hiszen h < =) < ^ 2 h =) < ; ; 2 h ^ < =) 2 h =) =) . [ (i) 1) + 1 On < < F β α + 1 ^ h 6= 0. α+1 b) h = 0 ^ h 6= 0 ^ h +1 =) h = f g =) F st< h. 3) T r( +1): x 2 +1 =) =) x 2 x = =) x + 1. (ii) 2 [ f g (iii) < + 1 =) 2 = =) < + 1 =) < + 1 8 (iv) ? 1) < =) 2 + 1 ) =) + 1 < + 1 =) 2) =) > = + 1 < + 1 =) : ( ; A lltas W 2 = ) 2 2 ) 2 =) + 1 =) +1 < +1 =) + 1 > + 1 + 1 = + 1 =) + 1 + 1 + 1 + 1) =) : ( ) =) < ] ; o( n; ) O 2 [ (a) Fenti
Kovetkezmeny (i) alapjan: Lo(On; 2 ). (b) h On ^ h 6= 0 ) (9)( 2 h) ) ) (9)( 2 ( + 1) h)) ) (9 )( h 6= 0) ) (9 )(9 )( F st<( h) es, ahogy mar az el}oz}o biz. (i) 2)a){ban lattuk: F st< ( h) ) F st< h ] Kovetkezmeny (i) P r(On) (burali{forti paradoxon) (ii) a On ^ T r(a) =) a 2 On (iii) A On ^ T r(A) =) A 2 On A = On [ (i) M(On) ) (9a)(On = a); On = a ) T r(a) ^ W o(a; 2) ) a 2 On On = a ) ) a 2 On ^ On = a ) a 2 a ) F (ii) Nyilvan a b ^ W o(b; <) =) W o(a; <) (iii) T r(A) =) (8 2 A)(8 2 )( 2 A) =) (8 62 A)(8 2 A)( > ) =) ) (8 62 A )(8 )( 2 A ) 2 ) =) (8 62 A)(A ) =) [(9 62 A) ) (9 )(A )]) =) [(9 62 A) ) MA)] =) [A On ^ A = 6 On ) M(A)] es (ii). ] ; A lltas (i) (8x 2 A)T r (x) =) T r ([ A) ^ T r ( A) (ii) A On =) [ A On ^ (A 6= 0 ) A On) [ (i) x 2 [A =) (9y 2 A)(x 2 y) =) (9y 2 A)(x y) =) x [A . x 2 A =) (8y 2 A)(x 2 y) =) (8y 2 A)(x y) =) x A , (ii) x 2 [A =) (9 2 A)(x 2 ) =) x 2 On x 2 A ^ A = 6 0 =) (8 2
A)(x 2 ) ^ (9 2 A) =) x 2 On ] Kovetkezmeny Rendszamok minden nemures reszosztalyanak van els}o eleme: A On ^ A 6= 0 =) I nf A 2 A [ T. fel A On ^ A =6 0 1) I nf A 2 On : a) M(I nf A) (7. old Kovetkezmeny) b) T r (I nf A) : el}oz}o A ll c) W o (I nf A; 2 ) el}oz}o A ll. miatt mert nyilvan A B ^ W o(B; <) =) W o(A; <) 2) $ I nfA ^ 62 A =) 62 A ^ (8 )( 2 A ) ) =) (8 )( 2 A ) > ) ) =) (8 )( 2 A ) + 1) =) F hiszen $ I nf A . ] Kovetkezmeny A O n= ) S up A Kovetkezmeny 2 O n S up A = n O (i) (a) a On =) S up a 2 On (ii) (a) a On ^ a 6= 0 =) I nf a 2 On (b) S up 2 On (b) 6= 0 =) I nf 9 2 O n 3.3 Rendszamok osztalyozasa De ncio KI $ : = 0 ( )( = + 1) KII $ n KI f O 9 g n KI nemzerus elemeit rakovetkez}o{, mg KII elemeit limesrendszamoknak nevezzuk. Megjegyzes Nyilvan osszesen 3 egymast kizaro eset van: 1. = 0 2. (9 )( = + 1), azaz rakovetkez}o. 3. 6= 0 ^ : (9 )( = + 1), azaz limes. A lltas [
[ 2 [ =) (9 2 )( 2 ) =) (9 )( 2 2 ) =) 2 ] Megjegyzes Az alltas alapjan osszesen 2 egymast kizaro eset van: 1. [ 2 2. [ = A lltas Az alabbi alltasok ekvivalensek: (i) rakovetkez}o (ii) [ 2 (iii) = [ + 1 (ii) : = + 1 =) 2 ^ (8 2 )( < = ) =) = S up ; (ii) ; (iii) : 2 [ + 1 () 2 S up + 1 () < S up () S up 2 () S up < () 2 (iii) ; (i) : trivialis ] [ (i) =[ + 1 () A lltas Tetsz}oleges 6= 0 eseten az alabbi alltasok ekvivalensek: (i) limes (ii) [ = (iii) (8 < )( + 1 < ) (ii) : el}oz}o alltasok alapjan (i) =) [ 62 =) (ii). ; (ii) ; (iii) : 2 = [ ) (9 2 )( 2 ) ) (9 )( < < ) ) + 1 < (iii) ; (i) : < ) + 1 < ) + 1 6= es ) +1 +1 > [ (i) Kovetkezmeny ( 2 KI ^ 2 KI ) ( 2 KII ^ 2 KII ) = ) 10 < = ) [ < [ ) + 1 6= ] Kerdes ? KI = n , azaz letezik{e limesrendszam ? 6 O De ncio ! $ : + 1 KI A lltas f != f A lltas : 2 KI ^ g (8 < )( 2 KI ) g
(i) T r (!) (ii) 2 ! =) + 1 2 ! (iii) ! = [ ! [ (iii) : Egyreszt az el}oz}o old. els}o A lltas alapjan : [ ! ! Masreszt ! [ ! , hisz 2 ! =) + 1 2 ! =) (9 2 !)( 2 =) 2 [ !) . ] Megjegyzes El}oz}o A lltas (iii) es 9.old utolso el}otti Kovetkezmeny miatt : ! 2 On ! = On A vegtelensegi axioma (Ax6): M! ( ) Kovetkezmeny (i) ! limesrendszam De ncio O (ii) On n ! 6= 0 n ! elemeit transz nit szamok nak nevezzuk. n Pelda S up ! = ! = up (! + 1) S 3.4 Transz nit indukcio es rekurzio INDUKCIO Tetel (transzfinit indukcio elve) (8 ) ( A ) 2 A) =) On A Bizonytas. 1) H $ On n A ^ H 6= 0 =) (9 2 H )( = I nf H ) . 2) 2 ) < ) 62 H ) 2 A A. 3) A 2 A 2 H = On n A H=0 On A . (A legkisebb nem A{belinel kisebb osszes rendszam A{beli, tehat a feltetel miatt }o is az: ; ;; ; .) QED 11 Kovetkezmeny (i) esetszetvalasztasos (transzfinit) indukcio : ? 0 2 A ^ (8 ) ( 2 A ) + 1 2 A) ^ (8 2 KII ) (8 < ) ( 2 A) ) 2 A
=) On A (ii) rendszamra szortkozo (transzfinit) indukcio : (8 < ) ( A ) 2 A) =) A (iii) rendszamra szortkozo esetszetvalasztasos (transzfinit) indukcio : ? 0 2 A ^ (8 < )( 2 A ) +1 2 A) ^ (8 < ) 2 KII ^ ((8 < )( 2 A) ) 2 A =) A [ (i) = + 1 =) ? A ) 2 ^ A ) 2 A ) = + 1 2 A (ii) H $ n A ^ H = 6 0 =) F (pontosan ugy, mint a tetel bizonytasaban). ] ALKALMAZA S De ncio F << A $ F nc A % F o (A; <) ^L ^ P o ( g (F ); <) R ^ ? (8a; b 2 A)(a < b ) F (a) < F (b) szigoruan monoton nov}o Megjegyzes A rendezesi relaciokra vonatkozo indexeket gyakran, mikor implicite egyertelm}uek, az attekinthet}obb jeloles kedveert elhagyjuk, mint pl. ha A rendszam, akkor nyilvan (ha mast nem mondunk) < = 2, tehat pl. ha F F nc ^ Rg (F ) On, akkor csak ennyit runk: F % . A lltas F % F % < A =) Lo (Rg (F ); <) < A lltas < A =) < A lltas R g (F ) O n F nc(F ?1)
^ F ^ F ?1 % =) (8 % < Rg (F ) < 2 )( F ( )) [ {ra szortkozo transz nit indukcio: A $ f 2 : F ( )g ^ 2 ^ A ^ 62 A ) ) 6 F ( ) ) F ( ) < ) F ( ) 2 ) F ( ) 2 A ^ F ( ) < ) F ( ) F (F ( )) ^ ^ F (F ( )) < F ( ) ) F ] Lemma f nc g nc ( = ( < )(f ( ) = g( )) F ) ^ F ^ ^ 8 < )(f ( ) = G(f )) ( j ^ 8 < )(g( ) = G(g )) = j ) 8 [ Transz nit indukcio: A $ f : f () = g()g ^ < ^ A ) (8 2 )(f () = g()) ) ) f j = g j ) G(f j ) = G(g j ) ) f ( ) = G(f j ) = G(g j ) = g( ) ) 2 A ] 12 REKURZIO Tetel (transzfinit rekurzio) S ? F = f : ( ) f nc ( < )(f ( ) = G(f )) = = F nc n ( )(F ( ) = G(F )) H nc n ( )(H ( ) = G(H )) ) F 9 O ^ F 8 ^ 8 j j ^ F O ^ ) 8 j ) H =F Bizony tas. ? M $ f : (9 ) f F nc ^ (8 < )(f ( ) = G(f j )) . Ekkor a feltetel: F = [M S 1) Do (F ) = f 2M Do (f ) ^ (8f 2 M ) (Do (f ) 2 On) D o (F ) O n ^ T r (D o(F )) (lasd 9.old masodik A lltast) o
lepesben afenti 2) F nc (F ) mert relaciok unioja leven relacio es egyertek}u is, hisz ? az utols Lemmat hasznalva: ( ; a ) ; ( ; b ) 2 F = [ M =) (9f; g 2 M )( ; a ) 2 f ^ ( ; b) 2 g =) ? =) (9f; g 2 M ) 2 Do(f ) Do(g) ^ f ( ) = a ^ g( ) = b =) a = f ( ) = g( ) = b . 3) (8 2 Do(F ))(F ( ) = G(F j )) : S a) 2 Do(F ) = f 2M Do (f ) =) (9f 2 M )( 2 Do(f )) . b) f ( ) = G(f j ) . c) f F (8 2 Do(f ))(f ( ) = F ( )) f ( ) = F ( ) ^ f j = F j . d) F ( ) = f ( ) = G(f j ) = G(F j ) . 4) Do(F ) 62 On : D o(F ) 2 O n ^ $ Do(F ) =) M( ) ^ M(F ) =) M( F ) =) M(F ) =) =) M(F [ f( ; G(F j )g) es ? g $ F [ f( ; G(F j )g =) (8 < ) g( ) = F ( ) = G(?F j ) = G(g j ) ^ ^ g ( ) = G(F j ) = G(F ) = G(g j ) =) (8 2 D o(g ) = + 1) g( ) = G(g j ) =) S =) g 2 M =) + 1 = Do(g) f 2M Do (f ) = Do(F ) = =) F . 5) Do(F ) = On : 1) , 4) es 9. old utolso el}otti Kovetkezmeny 6) H F nc On ^ (8 )(H ( ) = G(H j )) =) H = F : Transz nit indukcio: (8 )(H ( ) = G(H j )) ^ A $ f :
H ( ) = F ( )g ^ A =) (8 < )(H ( ) = F ( )) ) =) H j = F j =) H ( ) = G(H j ) = G(F j ) = F ( ) =) 2 A H F nc On ^ (8 )(H ( ) = G(H j )) =) (8 )(H ( ) = F ( )) =) H = F . ; ; ; ; ; QED Kovetkezmeny (i) rendsz amra szortkozo (transzfinit) rekurzio : ? (9 !f ) f F nc ^ (8 < )(f ( ) = G(f j )) (ii) esetszetvalasztasos (transzfinit) rekurzio : A tetelben G va?laszthato olymodon, hogy ? S F (0) = a ^ (8 ) F ( + 1) = H (F ( )) ^ (8 2 KII ) F ( ) = < F ( ) (iii) rendszamra szortkozo esetszetvalasztasos (transzfinit) rekurzio : A tetelben G valaszthato olymodon, hogy ? S (9!f ) f F nc ^ f (0) = a ^ (8 < ) f ( +1)= H (f ( )) ^ (8 < )( 2 KII ) f ( )= < f ( ) 13 [ (i) Letezes : Tetel f = F j { val ,Segyertelm}useg : egyertelm}usegi Lemma (el}oz}o old.) S (ii) G = f(x; y) : x = 0 ^ y = a g f(x; y) : Do (x) 6= [Do (x) ^ y = H (x([Do (x))) g S f(x; y) : x 6= 0 ^ Do (x) = [Do (x) ^ y = [Rg (x))g ] ALKALMAZA S
(Rendszamaritmetika) De ncio (i) (rendszamok osszege) +0= + ( +S1) = ( + ) + 1 + = <( + ) ha limes (ii) (rendszamok szorzata) 0 = 0 ( + 1) = + S ha limes = <( ) A lltas n [ (i) : Transz nit indukcio: A $ f : + 2 Ong : (a) + 0 = 2 On 02A (b) + 2 On =) + ( + 1) = ( + ) + 1 2 On 2 A =) + 1 2 A (c) ? $ (8 < )( 2 A) ^ C $ f + : < g ^ F $ f( ; + ) : < g . ? =) F nc (F ) ^ Do F = ^ Rg F = C =) M (C ) =) M (S up C ) ^ ^ =) C On =) M (S up C ) ^ C On =) + = S up C 2 On (8 < )( 2 A) =) 2 A . ] (i) + A lltas 2 ! 2 O n (ii) ; ; ; ; ^ 2 O 2 != ) + 2 ! ^ 2 ; ! [ !{ra szortkozo transz nit indukcio : (a) 2 ! =) + 0 = 2 ! (b) + 2 ! =) + ( + 1) = ( + ) + 1 2 ! . Szorzat az osszegre vonatkozo alltast hasznalva analog ] Feladat Bizonytsuk be, hogy (i) + 0 = 0 + = (ii) 0 = 0 = 0 (iii) 1=1 = Kerdes + 1 =? 1 + [ Nem : 1+ ! = S 2! (1+ ) = S 2! = [ ! = ! < ! +1 mert persze 2 ! =) 1+ = +1 ]
14 3.5 A termeszetes szamok De ncio ! elemeit veges (rend)szamok nak vagy termeszetes szamok nak nevezzuk. Jeloles i ; j ; k ; l ; m ; n veges szamokat jelol. Tetel (peano axiomak) (i) ( n)(n + 1 = 0) (ii) ( n)( m)(n + 1 = m + 1 = n = m) (iii) ( n)(n + 0 = n) (iv) ( n)( m)(n + (m + 1) = (n + m) + 1) (v) ( n)(n 0 = 0) (vi) ( n)( m)(n (m + 1) = n m + n) (vii) 0 A ( n)(n A n + 1 A) = ! A 8 6 8 8 ) 8 8 8 8 8 2 8 ^ 8 2 ) 2 ) (veges indukcio) Bizonytas. (i) : n 2 n + 1 (ii) : n < m =) n + 1 < m + 1 (iii), (iv) : + def. (v), (vi) : (vii) !{ra szortkozo esetszetvalasztasos transz nit indukcio Megjegyzes def. QED Az indukcio atfogalmazhato a szokasos (formulakra vonatkozo) alakba, ha az A = fx : (x)g osztalyra alkalmazzuk : (0) ^ (8n)((n) ) (n + 1)) =) (8n)(n) , ahol {ben a x ; 0 ; n ; n + 1 valtozok nem szerepelnek es {nek ugyanazon szabad valtozojat csereljuk x ; 0 ; n ; n + 1{re . A tetel tehat
azt mondja ki, hogy s(n) $ n + 1 {el ! = h ! ; 0 ; s ; + ; i tenyleg modellje a Peano axiomaknak. Tetel (veges rekurzio) ? (9 !f )[f F nc ! ^ f (0) = m ^ (8n) f (n + 1) = H (f (n)) ] Bizonytas. !{ra szortkozo esetszetvalasztasos transz nit rekurzio Tetel (induktv halmazok izomorfak) QED Legyen C tetsz}oleges olyan, hogy (1) (i) a 2 C (ii) (8x 2 C )(S (x) 2 C ) es (2) (i) (8x 2 C )(S (x) 6= a) (ii) (8x 2 C )(8y 2 C )(S (x)= S (y) =) x = y) (iii) a 2 A ^ (8x 2 C )(x 2 A ) S (x) 2 A) =) C A (indukci o ) ? Ekkor (9 !f )[f F nc ! ^ Rg (f ) = C ^ U n (f ?1) ^ f (0) = a ^ (8n) f (n + 1) = S (f (n)) ] 15 Bizonytas. ? El}oz}o tetel alapjan (9 !f ) F nc ! ^ f (0) = a ^ (8n)(f (n + 1) = S (f (n) . Belatando, hogy Rg (f ) = C ^ U n (f ?1) . 1) C Rg (f ) : Indukcio C {n . A $ Rg (f ) (a) f (0) = a a2A (b) x 2 A =) (9n)(f (n) = x) =) (9n)(f (n + 1) = S (x)) =) S (x) 2 A (c) (a) es (b){vel (2)(iii) alapjan : a 2 A ^ (8x 2 A)(S (x) 2 A) C A = Rg (f
) . 2) Rg (f ) C : Indukcio ! { n . A $ fn : f (n) 2 C g (a) f (0) = a 2 C 02A (b) n 2 A =) f (n) 2 C =) f (n + 1) = S (f (n)) 2 C =) n + 1 2 A (c) (a)+(b) ! A. Vegul (c) {vel : Rg (f ) = f ! f A C Rg (f ) C . 3) U n (f ?1) : Indukcio ! { n . A $ fn : (8m)(f (m) = f (n) =) m = n)g a) 0 2 A : f (0) = f (m) ^ m 6= 0 =) (9k)(a = f (0) = f (m) = f (k + 1) = S (f (k)) =) =) (9k)(a = S (f (k)) =) (9x 2 C )(a = S (x)) =) F b) n 2 A =) n + 1 2 A : a){val n +1 6= 0 f (n +1) = f (m) =) m 6= 0 =) (9k)(k +1 = m) =) (9k)(f (n +1) = = f (k + 1)) n 2 A ^ f (n + 1) = f (m) =) S (f (n)) = f (n + 1) = f (k + 1) = = S (f (k)) =) f (n) = f (k) =) n = k =) n + 1 = k + 1 = m =) n + 1 = m n 2 A =) n + 1 2 A : (c) (a)+(b) ! A. ; ; ; ; ; ; ;; ; ; QED Kovetkezmeny (! egyertelmu}) C { re a = 0 es S = (x; y) : y = x x { el fennallnak a Tetel feltetelei [ Tetelbeli f { el indukcio A $ fn : f (n) = ng { re. ] f [ f gg Kerdes ; C = !. Legyen L = h 0 ; s i ; els}orend}u
nyelv, ! = h ! ; 0 ; s i ; L 0 L{nek egy uj c konstanssal valo b}ovtese, = T h ! [ fs(n) 0 6= c : n 2 !g ( s (0) 0 = 0 ; 0s(n+1) 0 = s s(n) 0 ) . Kompaktsagi tetellel van {nak C 0 = hC ; a ; S ; d i modellje (d = cC ) . Nomarmost, f F nc! ^ Rg (f ) = C ^ f (0) = a ^ (8n 2 !)(f (s(n)) = S (f (n)) (9n 2 !)(d = = f (n) = f (s(n) 0) = S (n) f (0) = S (n) a 6= d) , mert C 0 modellje {nak. Ebb}ol az ellentmondasbol kovetkez}oen ilyen f fuggveny nincs, tehat C 0 {nek L{re vonatkozo reduktumat C {vel jelolve : (1) C nem izomorf ! { val. Masreszt C j= T h ! es ! { n igazak az (i),(ii), (vii) Peano axiomak, gy C {re fennallnak ezek megfelel}oi, azaz az el}oz}o tetel feltetelei, tehat: (2) C izomorf ! { val. A kerdes tehat : (1) es (2) kozul melyik igaz ? ; 16 [ (2) hamis, mert bar az igaz, hogy C { re fennallnak az (i) es (ii) Peano axiomak, azaz a tetel (1)(i), (ii) es (2)(i)(ii) feltetelei, a (vii) Peano axioma es vele a tetel (2)(iii)
feltetele, az indukcio, altalaban mar nem, csak bizonyos specialis A = fx : (x)g osztalyokra igaz, azokra, amelyek eseten a (x) { ben (a halmaz{ es osztalyszimbolumokon, az ={en ens az 2{on tovabba a logikai konstansokon kvul) csak az a es az S (n) $ S S : : : S ^ szerepel x n { ekre, hiszen csak ezen formulak azok, melyekben csak L = h 0 ; s i { beli nem logikai konstansok C { beli interpretacioi szerepelnek, azaz, amelyek maguk L { beli formulak C { beli interpretacioi, mint peldaul a (8x 2 C )(S (x) 6= a) . Masreszt az indukcio nem vonatkozik peldaul az A = fx : (x)g osztalyra, ha (x) a kovetkez}o | L { ben nem, a halmazelmeletben viszont megfogalmazhato | formula, mely azt fejezi ki, hogy egy osztaly elemei megkaphatoak egy elemeb}ol S segtsegevel veges sok lepesben (amelyre, bar a 2 A ^ (8x 2 C )(x 2 A ) S (x) 2 A) de persze C 6 A , hisz C A nyilvan kizarna azt a konstrukciot, amelynek alapjan megmutattuk azt, hogy C nem
izomorf ! { val) : (x) = (9n)(s(n) = x) , ahol s { et a { bol?es S { b}ol veges rekurzi oval de nialjuk, hiszen eszerint (9 !f )(f F nc ! ^ f (0) = a ^ (8n) f (n + 1) = S (f (n)) ] Feladat Adjuk meg a Z ; Q ; R es C { nek, azaz az egesz, a racionalis, a valos es a komplex szamok halmazanak ! { bol valo felepteset vazlatosan ! 4. A kivalasztasi axioma A kivalasztasi axioma (Ax7): 9f f F nc a ^ 8x 2 a x 6 ( De ncio ) ? ( ) ( )( Az f F nc (a) ^ (8x 2 a)(x 6= 0 =) f (x) az a kivalasztasi fuggvenyei nek nevezzuk. 2 F F 9 8 ^ U 2 6 ^ D ) ^ ) 2 ^ R 9 ^ ( ) x) feltetelt kielegt}o f Jeloles f h a $ f nc (a) ( x a)(x = 0 f (x) x) . De ncio a f b $ nc(f ) n(f ?1) o(f ) = a g(f ) = b a b $ ( f )(a f b) a =f b $ a f b f <<a a = b $ ( f )(a =f b) A lltas C )f x 2x =0= % ekvivalencia ekvivalens izomor zmus izomorf (i)(a) a f b =) b f ?1 a (b) a =f b =) b f ?1 a (ii) (ekvivalencia es
izomorfia ekvivalenciarelaciok) E1 $? f(x; y) : x yg ^ E2 $ f(x; y) : x = yg =) =) E = E1 E = E2 =) Ref (V; E ) ^ S ym(V; E ) ^ T rs(V; E ) 17 fuggvenyeket Tetel (zermelo jolrendezesi tetel) Minden halmaz ekvivalens egy rendszammal (azaz minden halmaz jolrendezhet}o): (9 )( a) . Specialisan, minden jolrendezett halmaz izomorf egy rendszammal: a) . W o(a; <) =) (9 )( = Bizonytas. 1) Legyen f P (a) egy kivalasztasi fuggvenye, alisan ? speci W o(a; <) =) (8x 2 P (a) x 6= 0 ) f (x)F st< (x) . ? G $ f(x; y) : y = f (a n Rg(x)g van F , hogy F F nc On ^ (8 ) F ( ) = G(F j ) = = f (a n Rg(F j )) = f (a n F ) . 2) a n F ? 6= 0 =) F ( ) = f (a n F ) 2 a n F a =) F ( ) 2 a ^ ^ (8 < ) F ( ) 6= F ( ) A On ^ (8 2 A)(a n F 6= 0) =) F A a ^ ? 1 ^ U n((F j A) ). 3) (8 )(a n F 6= 0) =) F On a ^ U n(F ?1) =) M(F On) ^ F nc(F ?1) =) =) M(Rg (F ?1)) =) M(On) =) F (9 )(a n F = 0) . 4) $ I nf f : a n F = 0g ^ g $ F j =) a n F
= 0 ^ (8 < )(a n F 6= 0) =) =) a F = Rg(F j ) = Rg(g) ^ U n (g?1) =) Rg(g) = a ^ U n (g?1) g F nc ^ Rg(g) = a ^ U n(g?1) g a : 5) W o(a; <) ^ (8x 2 P (a))[x 6= 0 ) f (x)F st<(x)] ^ 1 ; 2 2 ^ 1 < 2 =) =) 1 2 =) F 1 F 2 =) a n F 1 a n F 2 =) f (a n F 1) f (a n F 2) =) a. =) F ( 1) F ( 2 ) =) F ( 1) < F ( 2) =) g( 1) < g( 2) =g ; ; ; ; ; ; ; Megjegyzes QED Mivel izomorf rendszamok azonosak: = =) = , tovabba rendszamok egyetlen izomor aja az identitas : =f =) (8 2 )(f ( ) = ) , gy az is igaz, hogy a) . W o(a; <) =) (9 ! )(9 ! g )( =g Feladat Mutassuk meg, hogy (i) izomorf rendszamok azonosak (ii) rendszamok egyetlen izomor aja az identitas ! [ Az 12. old utolso A lltast hasznaljuk f ^ < =) 2 =) 2 Do(f ) =) f ( ) 2 Rg(f ) = =) f ( ) 2 ) (i) = =) < =) F es felhasznalva, hogy f % ^ Rg (f ) = =) f ?1 % analog modon adodik, hogy < =) F . (ii) =f ^ 2 ^ f ( ) 6= =) f ( ) < < f ( ) :
f ( ) < =) f ( ) < =) F . < f ( ) =) f ?1( ) < f ?1 ( ) =) F . ? (ii){b}ol egyebkent persze mar kovetkezik (i) . ] Feladat Mutassuk meg, hogy a =) (9 )(a = 18 ) = a =) . ; ) =) (9 )(a = ) ] [ 2 =f a =) f ( ) 2 =) 2 Igy a Feladat =) W o(a; 2 ) =) (9 )( =a Mutassuk meg, hogy (9r)(W o (a; r)) Tetel (zorn lemma) Ha egy rendezett halmazban minden lancnak van fels}o korlatja, akkor a halmaznak van maximalis eleme: ? P o (a; <) ^ (8x 2 P (a)) Lo (x; <) ) (9y 2 a) y U b< x =) (9x)(x Max< a) : Bizonytas. 1) Legyen f P (a) egy kivalasztasi fuggvenye. G $ f (fy 2 a : (8z 2 Rg(x))(y > z)g) van F , hogy F F nc On ^ (8 )(F ( ) = G(F j ) = f (fy 2 a : (8z 2? F )(y > z)g) . 2) u $ fy 2 a :(8z 2 F )(y > z)g 6= 0 =) F ( )= f (u ) 2 a ^ (8 2 ) F ( ) >F ( ) A On ^ (8 2 A)(u 6= 0) =) F A a ^ F % A . 3) (8 )(u 6= 0) =) F On a ^ F % On =) M(F On) ^ F nc(F ?1) =) M(On) =) =) F (9 )(u = 0) . 4) $
I nf f : u = 0g =) F a ^ F % =) F a ^ Lo (F ; <) (9y 2 a)(y U b<F ) a feltetel miatt. Legyen c 2 a ^ c U b<F 5) c U b<F ^ (9x 2 a)(x > c) =) (9x)(x 2 u ) =) u 6= 0 =) F :(9x 2 a)(x > c) c Max<a . ; ; ; ; ; ; ; ; ; ; QED Tetel Az alabbi alltasok ekvivalensek: (i) Kivalasztasi axioma (ii) Zermelo jolrendezesi tetel (iii) Zorn lemma Bizonytas. 1) Az el}oz}o ket tetel szerint (i) (ii) es (i) (iii) . ? 2) (ii) ? (i) : W o ( a; <) =) (9f ) f = f(x;y) : x a ^ x 6= 0 ^ y F st< xg =) =) (9f ) f F nc(a) ^ (8x 2 a)(x 6= 0 ) f (x) 2 x) . 3) (iii) ? (i) : a) C $ ff : 9x 2 P (a) f C h x g =) ? =) M(C ) ^ P o (C; ) ^ (8z 2 P (C )) Lo (z; ) ) (9w 2 C ) w U b z Ugyanis: a1) C P (a [ a) M(C ) ? a2) (8x) P o (x; ) a3) Lo(z; ) ^ w $ [ z =) w U b z es S z C ^ Lo(z; ) ^ w $ [ z =) F nc (w ) ^ D o (w ) = f 2z Do (f ) a ^ ^ x 6= 0 ^ (x; y ) 2 w ) (9f 2 z )(x 6= 0 ^ (x; y ) 2 f ) ) y 2 x =) w 2 C .
; ; [ ; ; [ ; 19 b) (iii){al a) miatt (9h 2 C ) [: (9g 2 C )(g h)] . ? c) z 2 a ^ z 6= 0 ^ z 62 Do(h) ) (9y)(y 2 z) es g $ h [ f(z; y)g ) g 2 C ^ g h ) F . Igy : (9z)(z 2 a ^ z 6= 0 ^ z 62 Do(h)) a n f0g Do(h) a ( 0 62 a 0 2 Do(h) ) h C h a ) ^ ( 0 2 a n Do(h) ) h [ f(0; 0)g C h a ) : ; ; ; QED Megjegyzes ZF jeloli azt az elmeletet, melyet ugy kapunk, hogy halmazelmeleti axiomak kozul elhagyjuk a kivalasztasi axiomat. (i) (megszamlalhato sok megszamlalhato unioja megszamlalhato" nem tetele zf{nek) ZF 6` a ! ^ (8b 2 a)(b !) =) [ a ! (ii) (atviteli elv nem tetele zf{nek) ZF 6` h R ^ f : h? ! R ^ a 2 h ) ) [ (8x 2 ! h) C onv(x) ^ Lim(x)= a ) C onv(f x) ^ Lim(f x)= f (a) =) C onta(f ) ] ahol persze ? Lim $ f(x; y) : x 2 ! R ^ y 2 R ^ (8" 2 R) "> 0 =) (9m 2 !)(8n 2 !)(n>m ) jx(n) ? yj <") g (limes) C onv(a) $ a 2Do(Lim) (konvergens) C onta(f ) $ h R ^ f : h ! R? ^ a 2 h ^ ^(8" 2
R)["> 0 =) (9 2 R) > 0 ^ (8x 2 h)(jx ? aj < ) jf (x) ? f (a)j <") ] (folytonos) 5. Szamossag De ncio a $ nf : a a$ x :x V Jeloles j j I f C fj j 2 g szamossag g Ha mast nem mondunk mast, ezentul ; ; ; es indexelt valtozataik szamossagokat jelolnek. Megjegyzes A jolrendezesi tetel miatt a de ncio ertelmes. Tetel a b () a=b j j j j Bizonytas. =) : a b =) jaj a b jbj =) jaj b ^ jbj a =) jbj jaj jbj =) jaj = jbj (= : jaj = jbj =) a jaj = jbj b =) a b QED 20 A lltas a b= a b ) j j j j [ A masodik lepesben a 18.old utolso Feladattal: a b ) (9f )(f a f b = jbj ^ b f jbj) ) =) (9f )(9 )(jaj a f a jbj) =) (9f )(9 )(jaj jbj) =) jaj jbj ] A lltas a =a [ jaj a =) jjajj = jaj ] jj jj j j Kovetkezmeny a= : = j jg [ = jaj =) = jaj = jjajj = j j ] C f Tetel (cantor{schroder{berstein) a c b ^ Bizonytas. b d a= a b ) a c b b d a= a = c
= a = b. ) j j ^ ) j j b b=d j j j j ^ j j a= a j j j j b b a= ) j j j j ^ j j j j ) j j QED Tetel (cantor) < ( )j Bizonytas. 1) a 6 P (a) : (9f )(a f P (a)) ^ C $ fx 2 a : x 62? f (x)g =) C a ^ M (C ) =) (9c)(C = c 2 P (a)) =) =) (9c)(c 0 $ f ?1(c) 2 a) =) (9c) c 0 2 c () c 0 62 f (c 0) = c () c 0 62 c =) F . 2) j j jP ( )j : 2 =) =) 2 P ( ) P ( ) j j jP ( )j . j j jP Ezekkel : 6 P ( )^j j jP ( )j ; ; j = jP ( )j ^ j j 6 Kovetkezmeny j jP ; ( ) ; j j j < jP ( )j . QED a < (a) [ a f b ^ G $ f(x; f x) : x 2 P (a)g =) (9g)?g = G ^ P (a) g P (a) jaj = jbj =) jP (a)j = jP (b)j P (a) P (jaj) jaj = jjajj < jP (jaj)j = jP (a)j jaj < jP (a)j ] Kovetkezmeny (van szamossaghalmaz minden elemenel nagyobb szamossag) a a = ( )( a)( > ) [ 2 a =) S up a =) S up a =) = jj jS up aj < jP (S up a)j ] j j jP j ;; C ; ) 9 8 ; 2 21 ;; Kovetkezmeny (minden
szamossagnal van nagyobb szamossag) (8)(9)( > ) [ 2 C a =) fg C a ; (9)(8 2 fg)( > ) =) (9)( > ) ] Kovetkezmeny (cantor paradoxon) r ( a) [ a = C a =) (9 2 a)(8 2 a)( > ) =) (9 2 a)(8 2 a)( 6= ) =) (9)( 6= ) =) F : (a = C a) (8x): (x = C a) : (9x) (x = C a) P r(C a) ] P C ; ; ; ; ; A lltas (szamossaghalmaz szupremuma szamossag) a a = up a a [ a C a ^ $ jS up aj ^ < S up a =) 2 S up a = [ a =) (9 2 a)( 2 ) =) ) (9)( < S up a) =) (9)( < S up a) =) (9)( < = jj jS up aj = ) =) F = S up a S up a 2 C a ] C ) S ; 2 C ; De ncio + $ nf : > Megjegyzes I f ; szamossag rakovetkez}oje g Fenti masodik Kovetkezmeny miatt a de ncio ertelmes. A kovetkez}o de ncio jogosultsagat az el}oz}o A lltas mutatja De ncio (alephek) 0 $! + +1 $ $ up : < ha limes De ncio @ @ @ rakovetkez}o szamossag limes szamossag @ S f@ g = jP (@0 )j
(8 )(@ +1 = jP (@ )j) kontinuum hipotezis altalanostott kontinuum hipotezis De ncio n(a) $ ( n)(n a) n(a) $ n(a) Feladat veges vegtelen @1 F 9 I :F Mutassuk meg, hogy a vegtelen szamossagok limes rendszamok ! [ I n( ) ^ f F nc ^ f (0) = ^ (8 < )? < ! ) f ( + 1) = ^ ! < ) f ( ) = =) f + 1 ] Megjegyzes Tudjuk, hogy A ltalaban is igaz : a b =! = n(a) = j j[j j I ) a b=a b=a a b=a b=a b. b. j [ j j j j j[j j ) j [ j j j j j[j j 22 =) 6. A regularitasi axioma Kerdes Van{e olyan halmaz, mely eleme sajat maganak ? A regularitasi axioma (Ax8): Megjegyzes a 6= 0 =) (9x 2 a)(x a = 0) A regularitasi axioma szerint minden nemures halmaznak van 2 {minimalis eleme : Ax8 () a 6= 0 =) (9x 2 a)(8y 2 a)(y 62 x) Kovetkezmeny (i) (nincs vegtelen leszallo 2 { lanc) ? : (9f ) f F nc ! ^ (8n)(f (n + 1) 2 f (n)) (ii) (nincs veges 2 { ciklus) ? : (9f )(9m) f F nc (m + 1) ^ (8n < m)(f (n + 1) 2 f
(n)) ^ f (0) 2 f (m) (iii) (8x)(x 62 x) [ (i), (ii) : Indirekte : Rg f { nek nem volna 2 { minimalis eleme. (iii) : (ii) specialisan m = 0{val, vagy kozvetlenul indirekte : b 2 b ^ a $ fbg =) [a 6= 0 ^ ^ b 2 (b a) ^ (8x 2 a)(x = b)] =) (8x 2 a)(x a =6 0) : ] Megjegyzes A Kovetkezmeny szerint tehat nincs olyan halmaz, melynek volnanak olyan elemei, hogy (i) a0 3 a1 3 a2 3 : : : 3 an 3 : : : (ii) a0 3 a1 3 a2 3 : : : 3 an 3 a0 (iii) a 3 a Megjegyzes (a kumulatv hierarchia : minden halmaz jolfundalt) A regularitasi axiomabol kovetkezik, hogy S S R F nc On ^ R(0)=0 ^ (8 )(R( +1)= P (R( )) ^ (8 2 KII )(R( )= < R ) =) V = Rg(R) De ncio A halmazelmelet ZFC ( Zermelo { Fraenkel + Choice ) axiomarendszere : Extenzionalitasi axioma (Ax1 ): (8x)(x 2 a () x 2 b) =) a = b M(fa; bg) Paraxioma (Ax2 ): Unioaxioma (Ax3 ): M([ a) M(P (a)) Hatvanyhalmazaxioma (Ax4 ): F nc(F ) ) M(F a) Helyettestesi axiomasema (Ax5 ): M(!?) Vegtelensegi axioma (Ax6 ):
(9f ) f F nc (a) ^ (8x 2 a)(x 6= 0 ) f (x) 2 x) Kivalasztasi axioma (Ax7 ): a 6= 0 =) (9x 2 a)(x a = 0) Regularitasi axioma (Ax8 ): 23
) $ :( ^ : ) (iv) () $ ( ) ) ^ ( Megjegyzes ) ) (ii) $ : ) (v) (9x) $ :(8x)(x) (iii) F $ : c1 = c1 1) A fenti es a tovabbikban bevezetend}o szimbolumok szandekolt jelentese termeszetesen a szokasos. 2) Ha mast nem mondunk, ; ; sz}uk ertelemben vett formulakat jelolnek. 3) =) es ) ugyanazt jelentik. A tagadast gyakran athuzassal jeloljuk, peldaul a 62 b $ :(a 2 b). Neha elhagyjuk az ^{t, pl a 2 b 2 c $ a 2 b ^ b 2 c vagy ) ) $ ( ) ) ^ ( ) ) es persze a felesleges zarojeleket is. 4) A meta `ha : : : akkor , azaz a `mivel : : : tehat jelolese a kovetkez}o: , mg a meta{ellentmondase: . 5) Ahogy mar eddig is tettuk, a `de ncio szerint legyen kifejezes rovidtesere a szokasos $ jelolest hasznaljuk. ; De ncio A szabad valtozokat halmaz(szimbolumok)nak es a fx : (x)g kifejezeseket osztaly(szimbolumok)nak nevezzuk. Az osztalyok es halmazok feletti metavaltozok a nagybetuk : A; B; C; : : : (esetleg indexekkel) es
nehany esetben specialis szimbolumok, pl. < De ncio 2f g (i) a x : (x) $ (a) ahol persze (a) az a formula, melyet {ben azon szabad valtozo minden el}ofordulasanak a{ra valo cserelesevel kapunk, melynek minden el}ofordulasanak x{re valo cserelesevel (x){et kaptuk es x nem szerepel {ben. 1 8 2 () x 2 B 9 ^x2B (ii) A = B $ ( x)(x A ha A es B kozul legalabb az egyik osztaly. (iii) A B $ ( x)(x = A ha A osztaly. 2 ) ) 1.2 Bizonytas a. Logikai axiomak (i) Propozicionalis axiomak (ii) Kvantoraxiomak: (1) (8x)( ) (x)) ) ( ) (8x) (x)), ahol az a szabad valtozo, melynek x{re valo cserejevel (x){et kaptuk nem fordul el}o {ben. (2) (8x)(x) ) (a), ahol (a) az a formula, melyet {b}ol azon szabad valtozo minden el}ofordulasanak a{ra valo cserelesevel kapunk, melynek minden el}ofordulasat x{re cserelve kaptuk (x){et. (iii) Identitas axiomak a = a; a = b ) ((a) ) (b)), ahol (a) es (b) az a formula, melyet {b}ol valamely szabad
valtozo minden el}ofordulasanak a{ra ill. b{re valo cserejevel kapunk b. Levezetesi szabalyok (i) Modus ponens: es ( ) ) (ii) Generalizalas: (8x)(x) ; Megjegyzes ; A bizonytasi rendszer tehat a predikatumkalkulus szokasos bizonytasi rendszerenek a sz}uk ertelmeben vett formulakra szortkozott valtozata, annak minden eredmenye gy kozvetlenul alkalmazhato. Megtehettuk volna eppen azt is (csak kevesbe lett volna elegans), hogy megtartjuk az L = h2i els}orend}u nyelv teljes bizonytasi rendszeret. Ekkor teljesen nyilvanvalo, hogy minden predikatumkalkulusbeli eredmeny atvihet}o a sz}uk ertelemben vett formulakra, hiszen ezek L osszes formulainak egy reszhalmazat alkotjak. 1.3 Alapfogalmak De ncio V $ x:x=x 0$ x:x=x A lltas f f g 6 g univerzalis osztaly ures osztaly (i) (8x)(x 2 V ) (ii) (8x)(x 62 0) De ncio (A) $ ( x)(x = A) r(A) $ (A) M P 9 :M halmaz (Menge (Cantor)) valodi osztaly (proper class) 2
Hasznos jelolesek (i) fA(x1 ; : : : ; xn) : (x1 ; : : : ; xn)g $ fx : (9x1 )(9x2 ) : : : (9xn )(x = A(x1 ; : : : ; xn ) ^ (x1 ; : : : ; xn )g, ahol A(x1 ; : : : ; xn) es (x1 ; : : : ; xn ) ugyanazoknak a szabad valtozoknak a kicserelesevel adodik A ill. {bol (ii) (a) (8x1 ; : : : ; xn) $ (8x1 ) : : : (8xn) (b) (9x1 ; : : : ; xn) $ (9x1 ) : : : (9xn) (iii) (a) (8x 2 A) $ (8x)(x 2 A ) ) (b) (9x 2 A) $ (9x)(x 2 A ^ ) (c) fx 2 A : (x)g $ fx : x 2 A ^ (x)g. Tobbvaltozora analog (iv) (9 ! x) (x) $ (9x)(x) ^ (8x)(8y)((x) ^ (y) ) x = y) 2. Az els}o ot axioma Az extenzionalitasi axioma (Ax1): 8x x 2 a () x 2 b ) a ( Kovetkezmeny A=B (8x)(x 2 A () )( ) = 8 2 A=B A lltas () ) 2 ^ A B ^ b x B) () 2 De ncio A B $ ( x)(x A x B ) A B$A(B$A B A=B Jeloles A B $ B A, A B $ B A Kovetkezmeny = resz(osztaly/halmaz) valodi resz(osztaly/halmaz) 6 B A (i) (a) A = A (b) A = B ) B = A (c) A = B ^ B = C ) A = C (ii) A =
B ) ((A) () (B )) A lltas (i) a = fx : x 2 ag (ii) P r(fx : x 62 xg) (russel paradoxon) Kovetkezmeny (i) Minden halmaz osztaly (ii) Nem minden osztaly halmaz De ncio a; b $ x : x = a x = b a $ a; a (a; b) $ a ; a; b f f g g f f par szingleton rendezett par g g ff g f gg 3 A paraxioma (Ax2): M fa; bg ( A lltas (a; b) = (c; d) De ncio [ a=c b=d () ^ A = x : ( y)(x y y A A = x : ( y)(y A x y f 9 2 f 8 2 Feladat a A= 2 ) A a ) ^ 2 ) [ unio metszet g 2 g A Az unioaxioma (Ax3): M [a ( Megjegyzes ) Eddig es a tovabbiakban is, amennyiben valamely uj osztaly tipust csak halmazokra de nialunk, mint peldaul a part { szemben az unioval { , ez azt jelenti, hogy csak halmazokra, de minden halmazra de nialtuk ezt a jelolest, azaz peldaul f Ru g nem de nialt, de { az unioaxioma miatt { f[ ag igen, nevezetesen persze? f[ ag $ fx : x = [ a x = [ ag = fx : x = [ ag = fx : (8y ) y 2 x () (9z )(y 2 z
^ z 2 a) g. Ugyanakkor termeszetesen [ Ru jol de nialt : [ Ru = fx : (9y)(x 2 y ^ y 2 Ru)g = = fx : (9y)(x 2 y ^ y 62 y)g . De ncio A B$ x:x A x B A B$ x:x A x B A B$ x:x A x B A lltas [ f 2 2 g f 2 ^ 2 g n f 2 ^ 62 unio metszet kulonbseg g (i) a [ b = [fa; bg (ii) a b = fa; bg Kovetkezmeny (a [ b) M [ par{ es unioaxioma ] De ncio (a) $ x : x a P f hatvanyhalmaz g A hatvanyhalmazaxioma (Ax4): MP ( A lltas (i) [ P (a) = a (ii) a P ([ a) (i) a =? P ([ a) (ii) a P ([ a) Kerdes ? 4 a ( )) De ncio A B $ (x; y) : x A y B A2 $ A A A?1 $ (y; x) : (x; y) A el(A) $ A V 2 n(A) $ ( x; y; z)((x; y); (x; z) A y = z) nc(A) $ el(A) n(A) o(A) $ x : ( y)((x; y) A) g(A) $ y : ( x)((x; y) A) F nc A $ nc (F ) o(F ) = A A B $ (x; y) A : x B A B $ g(A B ) A B $ (x; y) : ( z)((x; z) B (z; y) A) F : A B $ F nc A o(F ) B , ab $ f : f : a b Jeloles xRy $ (x; y) R A lltas f 2 ^ 2 g f 2 R g U 8 2 F
R ^U D f 9 2 g R f 9 2 g F F j ^D f R ) 2 2 g j f 9 ! F 2 ^D ^ 2 g f Descartes szorzat inverz relacio egyertek}u fuggveny ertelmezesi tartomany (domain) ertekkeszlet (range) megszortas kep osszetett (kompozicio) ! g 2 A B = y : ( x B )( (x; y) A ) f 9 2 2 g A helyettestesi axiomasema (Ax5): F nc F ) M F a ( ) ( ) Kovetkezmeny (zermelo szeparacio axiomasemaja) (a A) [ F $ f(x; y) : x 2 A ^ x = yg =) F nc(F ) ^ F a = a A ] Kovetkezmeny (ures halmaz axioma) M(0) [ ((8x)(x 62 A) ) A = 0) ^ (A $ fx : x 62 ag =) a A = 0) ] Kovetkezmeny (halmaz resze halmaz) A a =) M(A) M Kovetkezmeny (i) M(a b) (ii) M(ab) (iii) P r(V ) [ (i) a b P (P (a [ b)) (ii) a b P (a b) (iii) fx : x 62 xg V ] A lltas (i) M(Do (a)) (ii) M(Rg (a)) [ (i) F $ f((x; y); x) : (x; y) 2 ag =) F F nc a ^ F a = Do (a) ; (ii) analog. ] Kerdes (i) M(ff : f F nc ag) ? (ii) M(ff : f F nc A ^ Rg f bg) ? 5
[ (i) a 6= 0 ) P r (ff : f F nc ag) mert F $ ?y; f(x; y) : x 2 ag : y 2 V =) ) Rg(F ) ff : f F nc ag ^ (a 6= 0 ) F ?1 F nc Rg(F ) ^ Rg F ?1 = V ) ^ P r (V ) . (ii) M(Do (f )) (9a)(ff : f F nc A ^ Rg f bg = a b) ] De ncio ? F (a) $ x : ( y)(x y (a; y) F ) ( ! y) (a; y) F ertek A lltas ? ; f 9 2 ^ 2 ^ (i) (9 ! y) (a; y) 2 F =) (F (a) = b (ii) M (F (a)) (iii) F nc (F ) =) M (F j a) [ (iii) F j a a F a ] 9 () 2 g (a; b) 2 F ) Kerdes Fenti (iii){ban kell a F nc (F ) feltetel ? [ Igen: ? f0g V f0g = V ] Jeloles S x2A F (x) $ [f Feladat S D o( T F (x) : x A 2 x2A F (x)) = g S x2A F (x) $ fF (x) : x 2 Ag T x2A Do (F (x)) ( {re es Rg{re analog ) 3. Rendszamok 3.1 Rendezes Jeloles a>b$b<a a b $ a<b a=b a b De ncio ef (A; <) $ ( x A)(x < x) rr (A; <) $ ( x A)(x < x) ym (A; <) $ ( x A)( y A)(x < y y < x) rs (A; <) $ ( x; y; z A)(x < y y < z x < z) o (A; <) $ rr (A; <) rs (A;
<) o (A; <) $ o (A; <) ( x; y A)(x y y x) a ax< A $ a A ( x A)(a < x) a in< A $ a A ( x A)(x < a) a st< A $ a A ( x A)(x a) a st< A $ a A ( x A)(a x) a b< A $ ( x A)(x a) a b< A $ ( x A)(a x) a up< A $ a st< x : x b< A a nf< A $ a st< x : x b< A R 8 I 8 S 6 2 8 P I L P 2 2 8 T 8 2 ) 2 ^ ) ^T ^ 8 2 M 2 ^: 9 2 M 2 ^ : 9 2 L 2 ^ 8 2 F 2 ^ 8 2 U 8 2 L 8 2 S F I L f f U L g g 6 $ a>b a=b re exv irre exv szimmetrikus tranzitv (reszben) rendezett (partially ordered) linearisan rendezett (linearly ordered) (lanc) maximalis minimalis legnagyobb (utolso, last) legkisebb (els}o, rst) fels}o korlat (upper bound) also korlat (lower bound) supremum in mum A lltas (i) (a) P o (A; <) ^ a; b 2 A =) (a < b ) b 6 a) (b) Lo (A; <) ^ a; b 2 A =) (a 6< b ) b a) (ii) (a) a Lst< A =) a Max< A (b) a F st< A =) a
Min< A (c) Lo (A; <) =) (a Max< A ) a Lst< A) ^ (a Min< A ) a F st< A) (iii) (a) a S up< A ^ a 2 A =) a Lst< A (b) a I nf < A ^ a 2 A =) a F st< A (iv) (a) a Lst< A ^ b Lst< A =) a = b (b) a F st< A ^ b F st< A =) a = b Megjegyzes (i)(b), (ii)(c){ben a Lo (A; <) feltetel kell: < $ f(c; a); (c; b)g; A $ fa; b; cg. A lltas Ha $ (x; y) : x y , akkor f (i) P o (A; ) (ii) (a) Kovetkezmeny A=0= 6 g [ A up A A nf A (b) S I ( A) ) M [ Halmaz resze halmaz ] Megjegyzes Feltetel kell: 0 = V De ncio (i) up A $ A A lltas S (ii) I nf A $ A [ (i) A B =) S up A S up B (ii) A B =) I nf A I nf B 3.2 Elemi rendszamelmelet De ncio o (A; <) $ o (A; <) ( x)(x A x = 0 r (A) $ ( x)(x A x A) $ (a; b) : a b rd(a) $ r (a) o (a; ) n $ x : rd(x) W T 2 L 8 2 f 2 O O ^ T f Jeloles ) ^ 6 ) (9y)(y F st< x)) jolrendezett (well ordered) tranzitv g ^ W O
8 rendszam (ordinal) 2 g Gorog bet}u mindig rendszamot jelol, tehat peldaul: ( ) $ Ord( ) ^ ( ), (8 )( ) $ (8x)(Ord(x) ) (x)), (9 )( ) $ (9x)(Ord(x) ^ (x)): De ncio <On $ < $ A lltas 2 jO n azaz < () 2 . (i) Ord(0) (ii) T r(On) (rendszam elemei rendszamok) 7 (iii) Ord(a) ^ Ord(b) ) Ord(a b) (iv) ^ 6= ) 2 (v) [ (ii) (b 2 =) b ) =) x; y 2 [y ] ; ; Wo(b; 2 ) ; ? x2y2b2 =) x 2 y 2 =) [b 2 ; b ] [b 2 ^ T rs ( ; 2 ) =) (x 2 y 2 b =) x 2 b)] T r (b). ; (iv) ^ 6= =) n 6= 0: $ F st2 ( n ) =) = f : < g. Ugyanis egyreszt, 2 ^ 6< =) ^ < =) 2 =) F , masreszt, ξ γ < =) 2 2 =) 2 ^ 62 n =) 2 . Igy valoban = f : < g = 2 : α β (v) El}oszor is: 6= =) = . Ugyanis, $ ^ 6= ^ 6= =) =) 2 ^ 2 =) 2 =) F. Ezert 6 =) 6= =) [ ^ es (iv) ] =) = =) . ] Kovetkezmeny (i) Lo (On; 2) (ii) = f : < g (iii) < () 2 () (iv) () (v) 6= 0 () > 0 [ (i) 1) 2 =) (9 2
)( 2 ) =) F . 2) T r( ) 3) A lltas (iv) es (v) ] De ncio +1$ Pelda 1$ 0+1=0 3$ 2+1=2 A lltas [ f (i) (ii) (iii) (iv) rakovetkez}o g 0 = f0g ; 2 $ 1 + 1 = 1 [ f1g = f0g [ f1g = f0; 1g; [ f2g = f0; 1g [ f2g = f0; 1; 2g; : : : [ f g + 1 2 On < +1 < + 1 () + 1 () (azaz :(9 )( < < + 1) ) + 1 < + 1 () < Lo( + 1; 2 ). 2) W o( + 1; 2 ): t fel h ; a) h 6= 0 ^ F st ( h) =) F st h , hiszen h < =) < ^ 2 h =) < ; ; 2 h ^ < =) 2 h =) =) . [ (i) 1) + 1 On < < F β α + 1 ^ h 6= 0. α+1 b) h = 0 ^ h 6= 0 ^ h +1 =) h = f g =) F st< h. 3) T r( +1): x 2 +1 =) =) x 2 x = =) x + 1. (ii) 2 [ f g (iii) < + 1 =) 2 = =) < + 1 =) < + 1 8 (iv) ? 1) < =) 2 + 1 ) =) + 1 < + 1 =) 2) =) > = + 1 < + 1 =) : ( ; A lltas W 2 = ) 2 2 ) 2 =) + 1 =) +1 < +1 =) + 1 > + 1 + 1 = + 1 =) + 1 + 1 + 1 + 1) =) : ( ) =) < ] ; o( n; ) O 2 [ (a) Fenti
Kovetkezmeny (i) alapjan: Lo(On; 2 ). (b) h On ^ h 6= 0 ) (9)( 2 h) ) ) (9)( 2 ( + 1) h)) ) (9 )( h 6= 0) ) (9 )(9 )( F st<( h) es, ahogy mar az el}oz}o biz. (i) 2)a){ban lattuk: F st< ( h) ) F st< h ] Kovetkezmeny (i) P r(On) (burali{forti paradoxon) (ii) a On ^ T r(a) =) a 2 On (iii) A On ^ T r(A) =) A 2 On A = On [ (i) M(On) ) (9a)(On = a); On = a ) T r(a) ^ W o(a; 2) ) a 2 On On = a ) ) a 2 On ^ On = a ) a 2 a ) F (ii) Nyilvan a b ^ W o(b; <) =) W o(a; <) (iii) T r(A) =) (8 2 A)(8 2 )( 2 A) =) (8 62 A)(8 2 A)( > ) =) ) (8 62 A )(8 )( 2 A ) 2 ) =) (8 62 A)(A ) =) [(9 62 A) ) (9 )(A )]) =) [(9 62 A) ) MA)] =) [A On ^ A = 6 On ) M(A)] es (ii). ] ; A lltas (i) (8x 2 A)T r (x) =) T r ([ A) ^ T r ( A) (ii) A On =) [ A On ^ (A 6= 0 ) A On) [ (i) x 2 [A =) (9y 2 A)(x 2 y) =) (9y 2 A)(x y) =) x [A . x 2 A =) (8y 2 A)(x 2 y) =) (8y 2 A)(x y) =) x A , (ii) x 2 [A =) (9 2 A)(x 2 ) =) x 2 On x 2 A ^ A = 6 0 =) (8 2
A)(x 2 ) ^ (9 2 A) =) x 2 On ] Kovetkezmeny Rendszamok minden nemures reszosztalyanak van els}o eleme: A On ^ A 6= 0 =) I nf A 2 A [ T. fel A On ^ A =6 0 1) I nf A 2 On : a) M(I nf A) (7. old Kovetkezmeny) b) T r (I nf A) : el}oz}o A ll c) W o (I nf A; 2 ) el}oz}o A ll. miatt mert nyilvan A B ^ W o(B; <) =) W o(A; <) 2) $ I nfA ^ 62 A =) 62 A ^ (8 )( 2 A ) ) =) (8 )( 2 A ) > ) ) =) (8 )( 2 A ) + 1) =) F hiszen $ I nf A . ] Kovetkezmeny A O n= ) S up A Kovetkezmeny 2 O n S up A = n O (i) (a) a On =) S up a 2 On (ii) (a) a On ^ a 6= 0 =) I nf a 2 On (b) S up 2 On (b) 6= 0 =) I nf 9 2 O n 3.3 Rendszamok osztalyozasa De ncio KI $ : = 0 ( )( = + 1) KII $ n KI f O 9 g n KI nemzerus elemeit rakovetkez}o{, mg KII elemeit limesrendszamoknak nevezzuk. Megjegyzes Nyilvan osszesen 3 egymast kizaro eset van: 1. = 0 2. (9 )( = + 1), azaz rakovetkez}o. 3. 6= 0 ^ : (9 )( = + 1), azaz limes. A lltas [
[ 2 [ =) (9 2 )( 2 ) =) (9 )( 2 2 ) =) 2 ] Megjegyzes Az alltas alapjan osszesen 2 egymast kizaro eset van: 1. [ 2 2. [ = A lltas Az alabbi alltasok ekvivalensek: (i) rakovetkez}o (ii) [ 2 (iii) = [ + 1 (ii) : = + 1 =) 2 ^ (8 2 )( < = ) =) = S up ; (ii) ; (iii) : 2 [ + 1 () 2 S up + 1 () < S up () S up 2 () S up < () 2 (iii) ; (i) : trivialis ] [ (i) =[ + 1 () A lltas Tetsz}oleges 6= 0 eseten az alabbi alltasok ekvivalensek: (i) limes (ii) [ = (iii) (8 < )( + 1 < ) (ii) : el}oz}o alltasok alapjan (i) =) [ 62 =) (ii). ; (ii) ; (iii) : 2 = [ ) (9 2 )( 2 ) ) (9 )( < < ) ) + 1 < (iii) ; (i) : < ) + 1 < ) + 1 6= es ) +1 +1 > [ (i) Kovetkezmeny ( 2 KI ^ 2 KI ) ( 2 KII ^ 2 KII ) = ) 10 < = ) [ < [ ) + 1 6= ] Kerdes ? KI = n , azaz letezik{e limesrendszam ? 6 O De ncio ! $ : + 1 KI A lltas f != f A lltas : 2 KI ^ g (8 < )( 2 KI ) g
(i) T r (!) (ii) 2 ! =) + 1 2 ! (iii) ! = [ ! [ (iii) : Egyreszt az el}oz}o old. els}o A lltas alapjan : [ ! ! Masreszt ! [ ! , hisz 2 ! =) + 1 2 ! =) (9 2 !)( 2 =) 2 [ !) . ] Megjegyzes El}oz}o A lltas (iii) es 9.old utolso el}otti Kovetkezmeny miatt : ! 2 On ! = On A vegtelensegi axioma (Ax6): M! ( ) Kovetkezmeny (i) ! limesrendszam De ncio O (ii) On n ! 6= 0 n ! elemeit transz nit szamok nak nevezzuk. n Pelda S up ! = ! = up (! + 1) S 3.4 Transz nit indukcio es rekurzio INDUKCIO Tetel (transzfinit indukcio elve) (8 ) ( A ) 2 A) =) On A Bizonytas. 1) H $ On n A ^ H 6= 0 =) (9 2 H )( = I nf H ) . 2) 2 ) < ) 62 H ) 2 A A. 3) A 2 A 2 H = On n A H=0 On A . (A legkisebb nem A{belinel kisebb osszes rendszam A{beli, tehat a feltetel miatt }o is az: ; ;; ; .) QED 11 Kovetkezmeny (i) esetszetvalasztasos (transzfinit) indukcio : ? 0 2 A ^ (8 ) ( 2 A ) + 1 2 A) ^ (8 2 KII ) (8 < ) ( 2 A) ) 2 A
=) On A (ii) rendszamra szortkozo (transzfinit) indukcio : (8 < ) ( A ) 2 A) =) A (iii) rendszamra szortkozo esetszetvalasztasos (transzfinit) indukcio : ? 0 2 A ^ (8 < )( 2 A ) +1 2 A) ^ (8 < ) 2 KII ^ ((8 < )( 2 A) ) 2 A =) A [ (i) = + 1 =) ? A ) 2 ^ A ) 2 A ) = + 1 2 A (ii) H $ n A ^ H = 6 0 =) F (pontosan ugy, mint a tetel bizonytasaban). ] ALKALMAZA S De ncio F << A $ F nc A % F o (A; <) ^L ^ P o ( g (F ); <) R ^ ? (8a; b 2 A)(a < b ) F (a) < F (b) szigoruan monoton nov}o Megjegyzes A rendezesi relaciokra vonatkozo indexeket gyakran, mikor implicite egyertelm}uek, az attekinthet}obb jeloles kedveert elhagyjuk, mint pl. ha A rendszam, akkor nyilvan (ha mast nem mondunk) < = 2, tehat pl. ha F F nc ^ Rg (F ) On, akkor csak ennyit runk: F % . A lltas F % F % < A =) Lo (Rg (F ); <) < A lltas < A =) < A lltas R g (F ) O n F nc(F ?1)
^ F ^ F ?1 % =) (8 % < Rg (F ) < 2 )( F ( )) [ {ra szortkozo transz nit indukcio: A $ f 2 : F ( )g ^ 2 ^ A ^ 62 A ) ) 6 F ( ) ) F ( ) < ) F ( ) 2 ) F ( ) 2 A ^ F ( ) < ) F ( ) F (F ( )) ^ ^ F (F ( )) < F ( ) ) F ] Lemma f nc g nc ( = ( < )(f ( ) = g( )) F ) ^ F ^ ^ 8 < )(f ( ) = G(f )) ( j ^ 8 < )(g( ) = G(g )) = j ) 8 [ Transz nit indukcio: A $ f : f () = g()g ^ < ^ A ) (8 2 )(f () = g()) ) ) f j = g j ) G(f j ) = G(g j ) ) f ( ) = G(f j ) = G(g j ) = g( ) ) 2 A ] 12 REKURZIO Tetel (transzfinit rekurzio) S ? F = f : ( ) f nc ( < )(f ( ) = G(f )) = = F nc n ( )(F ( ) = G(F )) H nc n ( )(H ( ) = G(H )) ) F 9 O ^ F 8 ^ 8 j j ^ F O ^ ) 8 j ) H =F Bizony tas. ? M $ f : (9 ) f F nc ^ (8 < )(f ( ) = G(f j )) . Ekkor a feltetel: F = [M S 1) Do (F ) = f 2M Do (f ) ^ (8f 2 M ) (Do (f ) 2 On) D o (F ) O n ^ T r (D o(F )) (lasd 9.old masodik A lltast) o
lepesben afenti 2) F nc (F ) mert relaciok unioja leven relacio es egyertek}u is, hisz ? az utols Lemmat hasznalva: ( ; a ) ; ( ; b ) 2 F = [ M =) (9f; g 2 M )( ; a ) 2 f ^ ( ; b) 2 g =) ? =) (9f; g 2 M ) 2 Do(f ) Do(g) ^ f ( ) = a ^ g( ) = b =) a = f ( ) = g( ) = b . 3) (8 2 Do(F ))(F ( ) = G(F j )) : S a) 2 Do(F ) = f 2M Do (f ) =) (9f 2 M )( 2 Do(f )) . b) f ( ) = G(f j ) . c) f F (8 2 Do(f ))(f ( ) = F ( )) f ( ) = F ( ) ^ f j = F j . d) F ( ) = f ( ) = G(f j ) = G(F j ) . 4) Do(F ) 62 On : D o(F ) 2 O n ^ $ Do(F ) =) M( ) ^ M(F ) =) M( F ) =) M(F ) =) =) M(F [ f( ; G(F j )g) es ? g $ F [ f( ; G(F j )g =) (8 < ) g( ) = F ( ) = G(?F j ) = G(g j ) ^ ^ g ( ) = G(F j ) = G(F ) = G(g j ) =) (8 2 D o(g ) = + 1) g( ) = G(g j ) =) S =) g 2 M =) + 1 = Do(g) f 2M Do (f ) = Do(F ) = =) F . 5) Do(F ) = On : 1) , 4) es 9. old utolso el}otti Kovetkezmeny 6) H F nc On ^ (8 )(H ( ) = G(H j )) =) H = F : Transz nit indukcio: (8 )(H ( ) = G(H j )) ^ A $ f :
H ( ) = F ( )g ^ A =) (8 < )(H ( ) = F ( )) ) =) H j = F j =) H ( ) = G(H j ) = G(F j ) = F ( ) =) 2 A H F nc On ^ (8 )(H ( ) = G(H j )) =) (8 )(H ( ) = F ( )) =) H = F . ; ; ; ; ; QED Kovetkezmeny (i) rendsz amra szortkozo (transzfinit) rekurzio : ? (9 !f ) f F nc ^ (8 < )(f ( ) = G(f j )) (ii) esetszetvalasztasos (transzfinit) rekurzio : A tetelben G va?laszthato olymodon, hogy ? S F (0) = a ^ (8 ) F ( + 1) = H (F ( )) ^ (8 2 KII ) F ( ) = < F ( ) (iii) rendszamra szortkozo esetszetvalasztasos (transzfinit) rekurzio : A tetelben G valaszthato olymodon, hogy ? S (9!f ) f F nc ^ f (0) = a ^ (8 < ) f ( +1)= H (f ( )) ^ (8 < )( 2 KII ) f ( )= < f ( ) 13 [ (i) Letezes : Tetel f = F j { val ,Segyertelm}useg : egyertelm}usegi Lemma (el}oz}o old.) S (ii) G = f(x; y) : x = 0 ^ y = a g f(x; y) : Do (x) 6= [Do (x) ^ y = H (x([Do (x))) g S f(x; y) : x 6= 0 ^ Do (x) = [Do (x) ^ y = [Rg (x))g ] ALKALMAZA S
(Rendszamaritmetika) De ncio (i) (rendszamok osszege) +0= + ( +S1) = ( + ) + 1 + = <( + ) ha limes (ii) (rendszamok szorzata) 0 = 0 ( + 1) = + S ha limes = <( ) A lltas n [ (i) : Transz nit indukcio: A $ f : + 2 Ong : (a) + 0 = 2 On 02A (b) + 2 On =) + ( + 1) = ( + ) + 1 2 On 2 A =) + 1 2 A (c) ? $ (8 < )( 2 A) ^ C $ f + : < g ^ F $ f( ; + ) : < g . ? =) F nc (F ) ^ Do F = ^ Rg F = C =) M (C ) =) M (S up C ) ^ ^ =) C On =) M (S up C ) ^ C On =) + = S up C 2 On (8 < )( 2 A) =) 2 A . ] (i) + A lltas 2 ! 2 O n (ii) ; ; ; ; ^ 2 O 2 != ) + 2 ! ^ 2 ; ! [ !{ra szortkozo transz nit indukcio : (a) 2 ! =) + 0 = 2 ! (b) + 2 ! =) + ( + 1) = ( + ) + 1 2 ! . Szorzat az osszegre vonatkozo alltast hasznalva analog ] Feladat Bizonytsuk be, hogy (i) + 0 = 0 + = (ii) 0 = 0 = 0 (iii) 1=1 = Kerdes + 1 =? 1 + [ Nem : 1+ ! = S 2! (1+ ) = S 2! = [ ! = ! < ! +1 mert persze 2 ! =) 1+ = +1 ]
14 3.5 A termeszetes szamok De ncio ! elemeit veges (rend)szamok nak vagy termeszetes szamok nak nevezzuk. Jeloles i ; j ; k ; l ; m ; n veges szamokat jelol. Tetel (peano axiomak) (i) ( n)(n + 1 = 0) (ii) ( n)( m)(n + 1 = m + 1 = n = m) (iii) ( n)(n + 0 = n) (iv) ( n)( m)(n + (m + 1) = (n + m) + 1) (v) ( n)(n 0 = 0) (vi) ( n)( m)(n (m + 1) = n m + n) (vii) 0 A ( n)(n A n + 1 A) = ! A 8 6 8 8 ) 8 8 8 8 8 2 8 ^ 8 2 ) 2 ) (veges indukcio) Bizonytas. (i) : n 2 n + 1 (ii) : n < m =) n + 1 < m + 1 (iii), (iv) : + def. (v), (vi) : (vii) !{ra szortkozo esetszetvalasztasos transz nit indukcio Megjegyzes def. QED Az indukcio atfogalmazhato a szokasos (formulakra vonatkozo) alakba, ha az A = fx : (x)g osztalyra alkalmazzuk : (0) ^ (8n)((n) ) (n + 1)) =) (8n)(n) , ahol {ben a x ; 0 ; n ; n + 1 valtozok nem szerepelnek es {nek ugyanazon szabad valtozojat csereljuk x ; 0 ; n ; n + 1{re . A tetel tehat
azt mondja ki, hogy s(n) $ n + 1 {el ! = h ! ; 0 ; s ; + ; i tenyleg modellje a Peano axiomaknak. Tetel (veges rekurzio) ? (9 !f )[f F nc ! ^ f (0) = m ^ (8n) f (n + 1) = H (f (n)) ] Bizonytas. !{ra szortkozo esetszetvalasztasos transz nit rekurzio Tetel (induktv halmazok izomorfak) QED Legyen C tetsz}oleges olyan, hogy (1) (i) a 2 C (ii) (8x 2 C )(S (x) 2 C ) es (2) (i) (8x 2 C )(S (x) 6= a) (ii) (8x 2 C )(8y 2 C )(S (x)= S (y) =) x = y) (iii) a 2 A ^ (8x 2 C )(x 2 A ) S (x) 2 A) =) C A (indukci o ) ? Ekkor (9 !f )[f F nc ! ^ Rg (f ) = C ^ U n (f ?1) ^ f (0) = a ^ (8n) f (n + 1) = S (f (n)) ] 15 Bizonytas. ? El}oz}o tetel alapjan (9 !f ) F nc ! ^ f (0) = a ^ (8n)(f (n + 1) = S (f (n) . Belatando, hogy Rg (f ) = C ^ U n (f ?1) . 1) C Rg (f ) : Indukcio C {n . A $ Rg (f ) (a) f (0) = a a2A (b) x 2 A =) (9n)(f (n) = x) =) (9n)(f (n + 1) = S (x)) =) S (x) 2 A (c) (a) es (b){vel (2)(iii) alapjan : a 2 A ^ (8x 2 A)(S (x) 2 A) C A = Rg (f
) . 2) Rg (f ) C : Indukcio ! { n . A $ fn : f (n) 2 C g (a) f (0) = a 2 C 02A (b) n 2 A =) f (n) 2 C =) f (n + 1) = S (f (n)) 2 C =) n + 1 2 A (c) (a)+(b) ! A. Vegul (c) {vel : Rg (f ) = f ! f A C Rg (f ) C . 3) U n (f ?1) : Indukcio ! { n . A $ fn : (8m)(f (m) = f (n) =) m = n)g a) 0 2 A : f (0) = f (m) ^ m 6= 0 =) (9k)(a = f (0) = f (m) = f (k + 1) = S (f (k)) =) =) (9k)(a = S (f (k)) =) (9x 2 C )(a = S (x)) =) F b) n 2 A =) n + 1 2 A : a){val n +1 6= 0 f (n +1) = f (m) =) m 6= 0 =) (9k)(k +1 = m) =) (9k)(f (n +1) = = f (k + 1)) n 2 A ^ f (n + 1) = f (m) =) S (f (n)) = f (n + 1) = f (k + 1) = = S (f (k)) =) f (n) = f (k) =) n = k =) n + 1 = k + 1 = m =) n + 1 = m n 2 A =) n + 1 2 A : (c) (a)+(b) ! A. ; ; ; ; ; ; ;; ; ; QED Kovetkezmeny (! egyertelmu}) C { re a = 0 es S = (x; y) : y = x x { el fennallnak a Tetel feltetelei [ Tetelbeli f { el indukcio A $ fn : f (n) = ng { re. ] f [ f gg Kerdes ; C = !. Legyen L = h 0 ; s i ; els}orend}u
nyelv, ! = h ! ; 0 ; s i ; L 0 L{nek egy uj c konstanssal valo b}ovtese, = T h ! [ fs(n) 0 6= c : n 2 !g ( s (0) 0 = 0 ; 0s(n+1) 0 = s s(n) 0 ) . Kompaktsagi tetellel van {nak C 0 = hC ; a ; S ; d i modellje (d = cC ) . Nomarmost, f F nc! ^ Rg (f ) = C ^ f (0) = a ^ (8n 2 !)(f (s(n)) = S (f (n)) (9n 2 !)(d = = f (n) = f (s(n) 0) = S (n) f (0) = S (n) a 6= d) , mert C 0 modellje {nak. Ebb}ol az ellentmondasbol kovetkez}oen ilyen f fuggveny nincs, tehat C 0 {nek L{re vonatkozo reduktumat C {vel jelolve : (1) C nem izomorf ! { val. Masreszt C j= T h ! es ! { n igazak az (i),(ii), (vii) Peano axiomak, gy C {re fennallnak ezek megfelel}oi, azaz az el}oz}o tetel feltetelei, tehat: (2) C izomorf ! { val. A kerdes tehat : (1) es (2) kozul melyik igaz ? ; 16 [ (2) hamis, mert bar az igaz, hogy C { re fennallnak az (i) es (ii) Peano axiomak, azaz a tetel (1)(i), (ii) es (2)(i)(ii) feltetelei, a (vii) Peano axioma es vele a tetel (2)(iii)
feltetele, az indukcio, altalaban mar nem, csak bizonyos specialis A = fx : (x)g osztalyokra igaz, azokra, amelyek eseten a (x) { ben (a halmaz{ es osztalyszimbolumokon, az ={en ens az 2{on tovabba a logikai konstansokon kvul) csak az a es az S (n) $ S S : : : S ^ szerepel x n { ekre, hiszen csak ezen formulak azok, melyekben csak L = h 0 ; s i { beli nem logikai konstansok C { beli interpretacioi szerepelnek, azaz, amelyek maguk L { beli formulak C { beli interpretacioi, mint peldaul a (8x 2 C )(S (x) 6= a) . Masreszt az indukcio nem vonatkozik peldaul az A = fx : (x)g osztalyra, ha (x) a kovetkez}o | L { ben nem, a halmazelmeletben viszont megfogalmazhato | formula, mely azt fejezi ki, hogy egy osztaly elemei megkaphatoak egy elemeb}ol S segtsegevel veges sok lepesben (amelyre, bar a 2 A ^ (8x 2 C )(x 2 A ) S (x) 2 A) de persze C 6 A , hisz C A nyilvan kizarna azt a konstrukciot, amelynek alapjan megmutattuk azt, hogy C nem
izomorf ! { val) : (x) = (9n)(s(n) = x) , ahol s { et a { bol?es S { b}ol veges rekurzi oval de nialjuk, hiszen eszerint (9 !f )(f F nc ! ^ f (0) = a ^ (8n) f (n + 1) = S (f (n)) ] Feladat Adjuk meg a Z ; Q ; R es C { nek, azaz az egesz, a racionalis, a valos es a komplex szamok halmazanak ! { bol valo felepteset vazlatosan ! 4. A kivalasztasi axioma A kivalasztasi axioma (Ax7): 9f f F nc a ^ 8x 2 a x 6 ( De ncio ) ? ( ) ( )( Az f F nc (a) ^ (8x 2 a)(x 6= 0 =) f (x) az a kivalasztasi fuggvenyei nek nevezzuk. 2 F F 9 8 ^ U 2 6 ^ D ) ^ ) 2 ^ R 9 ^ ( ) x) feltetelt kielegt}o f Jeloles f h a $ f nc (a) ( x a)(x = 0 f (x) x) . De ncio a f b $ nc(f ) n(f ?1) o(f ) = a g(f ) = b a b $ ( f )(a f b) a =f b $ a f b f <<a a = b $ ( f )(a =f b) A lltas C )f x 2x =0= % ekvivalencia ekvivalens izomor zmus izomorf (i)(a) a f b =) b f ?1 a (b) a =f b =) b f ?1 a (ii) (ekvivalencia es
izomorfia ekvivalenciarelaciok) E1 $? f(x; y) : x yg ^ E2 $ f(x; y) : x = yg =) =) E = E1 E = E2 =) Ref (V; E ) ^ S ym(V; E ) ^ T rs(V; E ) 17 fuggvenyeket Tetel (zermelo jolrendezesi tetel) Minden halmaz ekvivalens egy rendszammal (azaz minden halmaz jolrendezhet}o): (9 )( a) . Specialisan, minden jolrendezett halmaz izomorf egy rendszammal: a) . W o(a; <) =) (9 )( = Bizonytas. 1) Legyen f P (a) egy kivalasztasi fuggvenye, alisan ? speci W o(a; <) =) (8x 2 P (a) x 6= 0 ) f (x)F st< (x) . ? G $ f(x; y) : y = f (a n Rg(x)g van F , hogy F F nc On ^ (8 ) F ( ) = G(F j ) = = f (a n Rg(F j )) = f (a n F ) . 2) a n F ? 6= 0 =) F ( ) = f (a n F ) 2 a n F a =) F ( ) 2 a ^ ^ (8 < ) F ( ) 6= F ( ) A On ^ (8 2 A)(a n F 6= 0) =) F A a ^ ? 1 ^ U n((F j A) ). 3) (8 )(a n F 6= 0) =) F On a ^ U n(F ?1) =) M(F On) ^ F nc(F ?1) =) =) M(Rg (F ?1)) =) M(On) =) F (9 )(a n F = 0) . 4) $ I nf f : a n F = 0g ^ g $ F j =) a n F
= 0 ^ (8 < )(a n F 6= 0) =) =) a F = Rg(F j ) = Rg(g) ^ U n (g?1) =) Rg(g) = a ^ U n (g?1) g F nc ^ Rg(g) = a ^ U n(g?1) g a : 5) W o(a; <) ^ (8x 2 P (a))[x 6= 0 ) f (x)F st<(x)] ^ 1 ; 2 2 ^ 1 < 2 =) =) 1 2 =) F 1 F 2 =) a n F 1 a n F 2 =) f (a n F 1) f (a n F 2) =) a. =) F ( 1) F ( 2 ) =) F ( 1) < F ( 2) =) g( 1) < g( 2) =g ; ; ; ; ; ; ; Megjegyzes QED Mivel izomorf rendszamok azonosak: = =) = , tovabba rendszamok egyetlen izomor aja az identitas : =f =) (8 2 )(f ( ) = ) , gy az is igaz, hogy a) . W o(a; <) =) (9 ! )(9 ! g )( =g Feladat Mutassuk meg, hogy (i) izomorf rendszamok azonosak (ii) rendszamok egyetlen izomor aja az identitas ! [ Az 12. old utolso A lltast hasznaljuk f ^ < =) 2 =) 2 Do(f ) =) f ( ) 2 Rg(f ) = =) f ( ) 2 ) (i) = =) < =) F es felhasznalva, hogy f % ^ Rg (f ) = =) f ?1 % analog modon adodik, hogy < =) F . (ii) =f ^ 2 ^ f ( ) 6= =) f ( ) < < f ( ) :
f ( ) < =) f ( ) < =) F . < f ( ) =) f ?1( ) < f ?1 ( ) =) F . ? (ii){b}ol egyebkent persze mar kovetkezik (i) . ] Feladat Mutassuk meg, hogy a =) (9 )(a = 18 ) = a =) . ; ) =) (9 )(a = ) ] [ 2 =f a =) f ( ) 2 =) 2 Igy a Feladat =) W o(a; 2 ) =) (9 )( =a Mutassuk meg, hogy (9r)(W o (a; r)) Tetel (zorn lemma) Ha egy rendezett halmazban minden lancnak van fels}o korlatja, akkor a halmaznak van maximalis eleme: ? P o (a; <) ^ (8x 2 P (a)) Lo (x; <) ) (9y 2 a) y U b< x =) (9x)(x Max< a) : Bizonytas. 1) Legyen f P (a) egy kivalasztasi fuggvenye. G $ f (fy 2 a : (8z 2 Rg(x))(y > z)g) van F , hogy F F nc On ^ (8 )(F ( ) = G(F j ) = f (fy 2 a : (8z 2? F )(y > z)g) . 2) u $ fy 2 a :(8z 2 F )(y > z)g 6= 0 =) F ( )= f (u ) 2 a ^ (8 2 ) F ( ) >F ( ) A On ^ (8 2 A)(u 6= 0) =) F A a ^ F % A . 3) (8 )(u 6= 0) =) F On a ^ F % On =) M(F On) ^ F nc(F ?1) =) M(On) =) =) F (9 )(u = 0) . 4) $
I nf f : u = 0g =) F a ^ F % =) F a ^ Lo (F ; <) (9y 2 a)(y U b<F ) a feltetel miatt. Legyen c 2 a ^ c U b<F 5) c U b<F ^ (9x 2 a)(x > c) =) (9x)(x 2 u ) =) u 6= 0 =) F :(9x 2 a)(x > c) c Max<a . ; ; ; ; ; ; ; ; ; ; QED Tetel Az alabbi alltasok ekvivalensek: (i) Kivalasztasi axioma (ii) Zermelo jolrendezesi tetel (iii) Zorn lemma Bizonytas. 1) Az el}oz}o ket tetel szerint (i) (ii) es (i) (iii) . ? 2) (ii) ? (i) : W o ( a; <) =) (9f ) f = f(x;y) : x a ^ x 6= 0 ^ y F st< xg =) =) (9f ) f F nc(a) ^ (8x 2 a)(x 6= 0 ) f (x) 2 x) . 3) (iii) ? (i) : a) C $ ff : 9x 2 P (a) f C h x g =) ? =) M(C ) ^ P o (C; ) ^ (8z 2 P (C )) Lo (z; ) ) (9w 2 C ) w U b z Ugyanis: a1) C P (a [ a) M(C ) ? a2) (8x) P o (x; ) a3) Lo(z; ) ^ w $ [ z =) w U b z es S z C ^ Lo(z; ) ^ w $ [ z =) F nc (w ) ^ D o (w ) = f 2z Do (f ) a ^ ^ x 6= 0 ^ (x; y ) 2 w ) (9f 2 z )(x 6= 0 ^ (x; y ) 2 f ) ) y 2 x =) w 2 C .
; ; [ ; ; [ ; 19 b) (iii){al a) miatt (9h 2 C ) [: (9g 2 C )(g h)] . ? c) z 2 a ^ z 6= 0 ^ z 62 Do(h) ) (9y)(y 2 z) es g $ h [ f(z; y)g ) g 2 C ^ g h ) F . Igy : (9z)(z 2 a ^ z 6= 0 ^ z 62 Do(h)) a n f0g Do(h) a ( 0 62 a 0 2 Do(h) ) h C h a ) ^ ( 0 2 a n Do(h) ) h [ f(0; 0)g C h a ) : ; ; ; QED Megjegyzes ZF jeloli azt az elmeletet, melyet ugy kapunk, hogy halmazelmeleti axiomak kozul elhagyjuk a kivalasztasi axiomat. (i) (megszamlalhato sok megszamlalhato unioja megszamlalhato" nem tetele zf{nek) ZF 6` a ! ^ (8b 2 a)(b !) =) [ a ! (ii) (atviteli elv nem tetele zf{nek) ZF 6` h R ^ f : h? ! R ^ a 2 h ) ) [ (8x 2 ! h) C onv(x) ^ Lim(x)= a ) C onv(f x) ^ Lim(f x)= f (a) =) C onta(f ) ] ahol persze ? Lim $ f(x; y) : x 2 ! R ^ y 2 R ^ (8" 2 R) "> 0 =) (9m 2 !)(8n 2 !)(n>m ) jx(n) ? yj <") g (limes) C onv(a) $ a 2Do(Lim) (konvergens) C onta(f ) $ h R ^ f : h ! R? ^ a 2 h ^ ^(8" 2
R)["> 0 =) (9 2 R) > 0 ^ (8x 2 h)(jx ? aj < ) jf (x) ? f (a)j <") ] (folytonos) 5. Szamossag De ncio a $ nf : a a$ x :x V Jeloles j j I f C fj j 2 g szamossag g Ha mast nem mondunk mast, ezentul ; ; ; es indexelt valtozataik szamossagokat jelolnek. Megjegyzes A jolrendezesi tetel miatt a de ncio ertelmes. Tetel a b () a=b j j j j Bizonytas. =) : a b =) jaj a b jbj =) jaj b ^ jbj a =) jbj jaj jbj =) jaj = jbj (= : jaj = jbj =) a jaj = jbj b =) a b QED 20 A lltas a b= a b ) j j j j [ A masodik lepesben a 18.old utolso Feladattal: a b ) (9f )(f a f b = jbj ^ b f jbj) ) =) (9f )(9 )(jaj a f a jbj) =) (9f )(9 )(jaj jbj) =) jaj jbj ] A lltas a =a [ jaj a =) jjajj = jaj ] jj jj j j Kovetkezmeny a= : = j jg [ = jaj =) = jaj = jjajj = j j ] C f Tetel (cantor{schroder{berstein) a c b ^ Bizonytas. b d a= a b ) a c b b d a= a = c
= a = b. ) j j ^ ) j j b b=d j j j j ^ j j a= a j j j j b b a= ) j j j j ^ j j j j ) j j QED Tetel (cantor) < ( )j Bizonytas. 1) a 6 P (a) : (9f )(a f P (a)) ^ C $ fx 2 a : x 62? f (x)g =) C a ^ M (C ) =) (9c)(C = c 2 P (a)) =) =) (9c)(c 0 $ f ?1(c) 2 a) =) (9c) c 0 2 c () c 0 62 f (c 0) = c () c 0 62 c =) F . 2) j j jP ( )j : 2 =) =) 2 P ( ) P ( ) j j jP ( )j . j j jP Ezekkel : 6 P ( )^j j jP ( )j ; ; j = jP ( )j ^ j j 6 Kovetkezmeny j jP ; ( ) ; j j j < jP ( )j . QED a < (a) [ a f b ^ G $ f(x; f x) : x 2 P (a)g =) (9g)?g = G ^ P (a) g P (a) jaj = jbj =) jP (a)j = jP (b)j P (a) P (jaj) jaj = jjajj < jP (jaj)j = jP (a)j jaj < jP (a)j ] Kovetkezmeny (van szamossaghalmaz minden elemenel nagyobb szamossag) a a = ( )( a)( > ) [ 2 a =) S up a =) S up a =) = jj jS up aj < jP (S up a)j ] j j jP j ;; C ; ) 9 8 ; 2 21 ;; Kovetkezmeny (minden
szamossagnal van nagyobb szamossag) (8)(9)( > ) [ 2 C a =) fg C a ; (9)(8 2 fg)( > ) =) (9)( > ) ] Kovetkezmeny (cantor paradoxon) r ( a) [ a = C a =) (9 2 a)(8 2 a)( > ) =) (9 2 a)(8 2 a)( 6= ) =) (9)( 6= ) =) F : (a = C a) (8x): (x = C a) : (9x) (x = C a) P r(C a) ] P C ; ; ; ; ; A lltas (szamossaghalmaz szupremuma szamossag) a a = up a a [ a C a ^ $ jS up aj ^ < S up a =) 2 S up a = [ a =) (9 2 a)( 2 ) =) ) (9)( < S up a) =) (9)( < S up a) =) (9)( < = jj jS up aj = ) =) F = S up a S up a 2 C a ] C ) S ; 2 C ; De ncio + $ nf : > Megjegyzes I f ; szamossag rakovetkez}oje g Fenti masodik Kovetkezmeny miatt a de ncio ertelmes. A kovetkez}o de ncio jogosultsagat az el}oz}o A lltas mutatja De ncio (alephek) 0 $! + +1 $ $ up : < ha limes De ncio @ @ @ rakovetkez}o szamossag limes szamossag @ S f@ g = jP (@0 )j
(8 )(@ +1 = jP (@ )j) kontinuum hipotezis altalanostott kontinuum hipotezis De ncio n(a) $ ( n)(n a) n(a) $ n(a) Feladat veges vegtelen @1 F 9 I :F Mutassuk meg, hogy a vegtelen szamossagok limes rendszamok ! [ I n( ) ^ f F nc ^ f (0) = ^ (8 < )? < ! ) f ( + 1) = ^ ! < ) f ( ) = =) f + 1 ] Megjegyzes Tudjuk, hogy A ltalaban is igaz : a b =! = n(a) = j j[j j I ) a b=a b=a a b=a b=a b. b. j [ j j j j j[j j ) j [ j j j j j[j j 22 =) 6. A regularitasi axioma Kerdes Van{e olyan halmaz, mely eleme sajat maganak ? A regularitasi axioma (Ax8): Megjegyzes a 6= 0 =) (9x 2 a)(x a = 0) A regularitasi axioma szerint minden nemures halmaznak van 2 {minimalis eleme : Ax8 () a 6= 0 =) (9x 2 a)(8y 2 a)(y 62 x) Kovetkezmeny (i) (nincs vegtelen leszallo 2 { lanc) ? : (9f ) f F nc ! ^ (8n)(f (n + 1) 2 f (n)) (ii) (nincs veges 2 { ciklus) ? : (9f )(9m) f F nc (m + 1) ^ (8n < m)(f (n + 1) 2 f
(n)) ^ f (0) 2 f (m) (iii) (8x)(x 62 x) [ (i), (ii) : Indirekte : Rg f { nek nem volna 2 { minimalis eleme. (iii) : (ii) specialisan m = 0{val, vagy kozvetlenul indirekte : b 2 b ^ a $ fbg =) [a 6= 0 ^ ^ b 2 (b a) ^ (8x 2 a)(x = b)] =) (8x 2 a)(x a =6 0) : ] Megjegyzes A Kovetkezmeny szerint tehat nincs olyan halmaz, melynek volnanak olyan elemei, hogy (i) a0 3 a1 3 a2 3 : : : 3 an 3 : : : (ii) a0 3 a1 3 a2 3 : : : 3 an 3 a0 (iii) a 3 a Megjegyzes (a kumulatv hierarchia : minden halmaz jolfundalt) A regularitasi axiomabol kovetkezik, hogy S S R F nc On ^ R(0)=0 ^ (8 )(R( +1)= P (R( )) ^ (8 2 KII )(R( )= < R ) =) V = Rg(R) De ncio A halmazelmelet ZFC ( Zermelo { Fraenkel + Choice ) axiomarendszere : Extenzionalitasi axioma (Ax1 ): (8x)(x 2 a () x 2 b) =) a = b M(fa; bg) Paraxioma (Ax2 ): Unioaxioma (Ax3 ): M([ a) M(P (a)) Hatvanyhalmazaxioma (Ax4 ): F nc(F ) ) M(F a) Helyettestesi axiomasema (Ax5 ): M(!?) Vegtelensegi axioma (Ax6 ):
(9f ) f F nc (a) ^ (8x 2 a)(x 6= 0 ) f (x) 2 x) Kivalasztasi axioma (Ax7 ): a 6= 0 =) (9x 2 a)(x a = 0) Regularitasi axioma (Ax8 ): 23
