B A B A B A B A A B A B B

MATEMATICKÁ LOGIKA A TEORIE MNOŽIN Univerzita Palackého v Olomouci

1. Obecná logika Logika jako p
edmt se zabývá analýzou myšlení, p
esnji analýzou úsudkových metod, p
itom ale abstrahujeme od nápln konkrétních tvrzení, sledujeme pouze správnost deduktivních postup. P
es snahu o formalizaci však v logice existují tzv. logické paradoxy, nap
. paradox lhá
e. – nkdo
íká: „Jsem lhá
!“ - Bu mluví pravdu a je lhá
nebo lže a lhá
není Russel
v paradox 2 skupiny množin A ... Normální množiny B ... Nenormální množiny A={x , x
x } - nemohou být sami svými prvky B={x , x x}  AA A
A  A
A AA Výraz, který má pevn urený smysl nazýváme logickou konstantou, ten který ho dostane až po dosazení urité konstanty z oboru promnnosti nazýváme logickou promnnou. Nejvtší význam mají tzv. p
edmtové konstanty neboli vlastní jména. Jsou to pojmy, které mají 3 následující atributy: Jméno to, co vyslovíme Smysl to, co vnímáme, když jméno vyslovíme Denotát vlastní realizace Sledujme vztah dvou p
edmtových konstant:

Nesprávnost úsudku v obecném jazyce asto plyne z nesprávné hierarchie p
edmtových konstant. Píklad: Petr je mj p
ítel. Závr: Potkal jsem Petra, tedy jsem potkal p
ítele. Správn Potkal jsem p
ítele, tedy jsem potkal Petra. Špatn Matematická logika Dlíme na dv skupiny: 1) Výroková 2) Predikátová

1

Výroková logika Dlíme na dvouhodnotovou, vícehodnotovou a na fuzzy logiku. Dvouhodnotová: Pouze dv pravdivostní hodnoty: pravda 1, nepravda 0. Vícehodnotová: Více pravdivostních hodnot Fuzzy logika: ph  0 , 1 ph – pravdivostní hodnota Dvouhodnotová výroková logika: Výroková logika si všímá vztahu mezi pravdivostní hodnotou výroku a výrokových formulí Definice: Výrokem zde rozumíme libovolné tvrzení o nmž má smysl
íci, zda je pravdivé nebo nepravdivé, p
iemž nastává práv jedna z obou možností. Výroky, které nelze dále rozdlit na dva i více dílích výrok nazýváme atomické, opak nazýváme výrokem složeným. Výrokovou promnnou zde budeme rozumt libovolnou promnnou nabývající pouze možných hodnot 0,1. Výrokové promnné budeme znait A, B, C, D, ... Jednotlivé výroky je možno skládat do složených výrok a výrokových formulí pomocí tzv. extenzionálních spojek. Používáme jen unární a binární spojky Unární 1 A 1

2

3

4

1

0

0

1

0 1 0 1 3 ... negace A ... ¬A Binární A B

0

1

2

3

4

5

6

7

8

9

10 11 12 13 14 15 16

1

1

1

1

1

1

1

1

1

1

0

0

0

0

0

0

0

0

1

0

1

1

1

1

0

0

0

0

1

1

1

1

0

0

0

0

0

1

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

0

0 0 1 0 1 2 ... A B 5 ... A B 7 ... A B 8 ... A B 9 ...¬ A B  A B Scheffer 15 ... ¬ A B Nicode

0

1

0

1

0

1

0

1

0

1

0

1

0

Krom nám známých spojek negace, konjunkce, ekvivalence, implikace a disjunkce mají vtší uplatnní ješt spojky Schefferova a Nicodova (v elektrotechnice), protože jako jediné tvo
í jednoprvkové báze spojek výrokové logiky. Zvláštní postavení ve výrokové logice mají tzv. formule výrokové logiky pro než platí následující definice. 2

Definice: Každá výroková promnná i konstanta je souasn formulí výrokové logiky. Definice: Jsou-li A ,B formule výrokové logiky ¬A , ¬B , A  B , A B , A B , A B jsou také formule výrokové logiky. Definice: Vše co dostaneme koneným potem krok 1 a 2 dává opt formuli výrokové logiky K urování pravdivostních hodnot výrokových formulí slouží 2 metody: – Tabulková – Aritmetická Aritmetická metoda P
i aritmetické metod intuitivn vytvo
íme vztah pro stanovení pravdivostní hodnoty t
í základních formulí a potom z nich odvozujeme další vztahy: ph ¬A=1 ph  A 1) ph  A B= ph A ph  B 2) ph  A B= ph A ph B ph A ph  B 3) ph  A B=1 ph A ph A ph B 4) ph  A B=1 ph A ph B2 ph A ph B 5) D
kaz: ph  A  B= ph¬ A B= ph¬A ph  B ph ¬A ph B=1 ph  A ph  B 4) 1 ph A ph  B=1 ph A ph B  ph  B ph  A ph  B=1 ph A ph  A ph  B 5) ph  A  B= ph A B  B A=1 ph A ph A ph B1 ph B ph A ph  B= =1 ph  B ph  A ph B ph A ph A ph  B ph 2  A ph B ph A ph B  ph A ph 2  B ph 2  A ph2  B=1 ph  B ph  A2 ph A ph B Formule výrokové logiky jsou vždy pravdivé nazýváme tautologie. Formule výrokové logiky jsou vždy nepravdivé nazýváme kontradikce. Tautologií existuje nekonen mnoho, nkteré z nich však povyšujeme na tzv. zákony výrokové logiky. 1) Zákon vyloueného t
etího A ¬ A 2) Zákon sporu ¬ A ¬ A 3) Zákon dvojí negace ¬¬A= A 4) Zákon komutativity  A B  B A 5) Zákon komutativity  A B  B A 6) Zákon asociativity  A  B C A B C 

3

7) Zákon asociativity  A  B C A B C  8) Zákon vzájemné distributivity  A  B C A B  A C  9) Zákon vnjší distributivity  A  B C A B  A C  10) Zákon De-Morganova pravidlo ¬ A B ¬ A ¬B 11) Zákon De-Morganova pravidlo ¬ A B ¬ A ¬B 12) Náhrada implikace  A B¬A B 13) Negace implikace ¬ A B A ¬B 14) Kontrapozice  A B¬B ¬ A 15) Tranzitivita implikace  A B  B C  A C  16) Náhrada ekvivalence  A B A B  B  A Poznámka: Užitené jsou ješt i následující tautologie: 1)  A A A 2)  A A A 3)  A 1 A 4)  A 0 0 5)  A 11 6)  A 0  A Definice: Nech A , B jsou libovolné formule výrokové logiky. 1) A  B je tautologií, pak formuli B nazveme logickým dsledkem formule A . 2) A B  je tautologií, potom formule A i B nazveme navzájem logicky ekvivalentní formule.

Základní vty o tautologiích Vta 1: Nech A , B jsou libovolné formule výrokové logiky a nech A je tautologie a souasn A  B je tautologie, potom i formule B je tautologie. D
kaz: P
ipusme, že B není tautologie, potom bude urit existovat zastoupení vnit
ních promnných, pro než platí ph B=0 . Potom ale  ph A =1 ph B=0  phA  B =0 což je spor s p
edpokladem.

4

Vta 2: Nech A je formule výrokové logiky, která má uvnit
vnit
ní promnné A1 , A2 , ... , An . Nech B vznikne z A tak, že promnné A1 , A2 , ... , An nahradíme libovolnými formulemi A 1 , A 2 , ... , A n . Potom platí, je-li A tautologie, musí být i B tautologie. D
kaz: Je-li A tautologie, její pravdivostní hodnota závisí pouze na vnit
ních spojkách a nezávisí na jednotlivých promnných A1 , A2 , ... , An . Když za tyto dosadíme libovolné útvary, pvodní spojky se nezmní, nová formule je opt tautologií. Píklad: A : A  B  B C   A C  A ...¬B C  B ... D  B C ...¬D B :¬B C  D B  D B  ¬D     ¬B C  ¬D  A

B

C

B

A

C

Vta 3: Nech A 1 je formule výrokové logiky, která v sob t
eba na více místech obsahuje podformuli A . Nech B 1 vznikne z A 1 tak, že na všech místech výskytu nahradíme podformuli A jinou podformulí B . Potom platí: 1) A  B A 1 B 1  je tautologie A  B A 1 B 1 =D , A  B=C , A 1 B 1 =C 1 2) A  B je tautologií A 1 B 1 je tautologiích D
kaz: 1) a    ph A = phB   ph A 1 = ph B 1  phD =1 phC =1

}

ph C 1 =1

D =tautologie

b   ph A  phB   ph C =0  phD =1 2) Plyne ze závru vty 1, tj. je-li C tautologie a je-li D tautologie, musí být i C 1 tautologie. Píklad na vtu 3 bod 2: A 1 : C  A B  D C  A B A

A

}

B 1 :C ¬ A B   D C ¬A B   B

B

=A 1 B 1 je tautologie

A 1 a B 1 jsou logicky ekvivalentní, protože zámna byla logicky ekvivalentní Poznámka: Druhá ást vty 3 je podstatou logicky ekvivalentních úprav výrokových formulí.

5

2. Princip duality Logické spojky konjunkce a disjunkce mají mnoho spole
ných vlastností, nap. idempotenci, komutativitu, asociativitu a vzájemnou distributivitu a jsou prost ednictvím De-Morganových pravidel vzájemn zamnitelné. Nazýváme je proto spojkami navzájem duálními. Tato skute
nost nám umožuje vyslovit dv vty, které shrnujeme pod název princip duality, které nám umožují z daných tautologií vytváet další tautologie. V
ta 1: Nech A resp B jsou formule výrokové logiky, které v sob obsahují pouze spojky negace konjunkce a disjunkce. Nech A ' resp B ' vzniknou z pvodních formulí tak, že spojky nahradíme za spojky duální. Pak platí: 1) Jestliže A je tautologie
¬A ' je tautologie 2) Jestliže A
B  je tautologie
B '
A '  je tautologie 3) Jestliže A  B je tautologie
A '  B '  je tautologie Dkaz: 1) Vytvoíme-li formuli A ' zmníme spojky na duální. Pi její negaci se spojky vrátí vlastn nazpt, ale z promnných se stanou jejich negace. To nám však nevadí, protože byla-li pvodní formule A tautologií, její pravdivostní hodnota je na promnných nezávisela. 2) Podle 1). Jestliže A
B  je tautologií
¬A
B ' je tautologie ¬A
B ' ¬¬A B ' ¬¬A ' B ' A ' ¬B ' ¬B ' A ' B '
A '  3) A  B je tautologie  ( A
B  je tautologie B
A  je tautologie)

( B '
A '  je tautologie A '
B '  je tautologie) A '  B '  je tautologie Definice: Nech A je formule výrokové logiky, která v sob obsahuje spojky negace, konjunkce a disjunkce a nech formule A  vynikne z pvodní formule tak, že spojky nahradíme za spojky duální a promnné za jejich negace. Potom formule A a A  nazveme navzájem logicky duálními formulemi. V
ta 2: Nech A resp. B jsou formule výrokové logiky obsahující v sob pouze spojky negace, konjunkce a disjunkce a nech A  resp. B  jsou k nim formule logicky duální. Potom platí: 1) Jestliže A je tautologie
¬A  je tautologie 2) Jestliže A
B  je tautologie
B 
A   je tautologie 3) A  B je tautologie
A  B  je tautologie Dkaz: 1) Tvoíme-li A  zamníme spojky za duální a promnné za jejich negace. Pi negaci A  se všechno vrátí nazpátek ¬A   A 2) Víme, že ¬A   A 
 A   ¬A  , ¬B  B 
B  ¬B   A
B ¬B 
¬A  B
A  B



A



3) Analogicky k výše uvedenému pomocí
a .

6

Úplné systémy a báze spojek výrokové logiky V této kapitole si všimneme systému spojek, které sta
í k popisu celé výrokové logiky, tj. že pomocí nich lze nahradit každou další spojku. V
ta*: Nech A je libovolná formule výrokové logiky. Potom vždy existuje formule F , která obsahuje pouze spojky negace, konjunkce a disjunkce, která je s A logicky ekvivalentní. Dkaz: Nech A obsahuje vnitní promnné A1 , A2 , ... , An 1) A je kontradikcí F = A1¬ A1  potom A  F 2) A není kontradikcí A1 A2 An A Vyjdeme z tabulky pravdivostních hodnot n

2 ádk

{

Nejprve každému ádku piadíme ur
itou konjunkci, tj. k i-tému ádku konjunkci i A j pro ph  A j =1 C i=U i1 U i2 ...U in  kde U j = v i-tém ádku ¬A j pro ph  A j =0 Platí ph C i =1 práv pouze pro zastoupení ph z i-tého ádku. Nyní tyto konjunkce zaadíme do výsledné disjunkce D , ale ne ze všech ádk, , pouze z tch, , kde byla ph A =1 . Nyní se lze pesvd
it, že formule D je onou hledanou formulí F , tj. že je s pvodní formulí logicky ekvivalentní. Ukážeme, že to platí v obecném k-tém ádku. I.  ph A =1
C k D  phC k =1
ph 0=1 II.  ph A =0
C k D  ph C j =0
ph D =0

{

jk


formule A a D =F jsou logicky ekvivalentní Definice: Úplným systémem spojek výrokové logiky budeme rozumt každou libovolnou množinu tchto spojek, která sta
í k popisu celé výrokové logiky, tj. pomocí nichž lze zapsat každou spojku výrokové logiky. Poznámka: Z vty* plyne, že takové spojky {¬ ,  , } tvoí úplný systém výrokové logiky. Definice: Každý minimální úplný systém spojek výrokové logiky nazveme bází spojek výrokové logiky. Poznámka: Z De-Morganových pravidel plyne, že výše uvedený systém {¬ ,  , } není sou
asn bází a platí, že existují dvouprvkové báze {¬ , }, {¬ , },{¬ ,
} . Vzniká otázka, zda existují njaké jednoprvkové báze a odpov na ní je kladná, tvoí je spojky Schefferova {  } a Nicodova {  } .

7

Shefferova spojka  AB¬ AB 1) ¬ A¬ AA AA 2)  AB ¬¬ A B¬ AB AB AB 3)  AB ¬¬ A B¬¬ A¬B¬A¬B AA BB Nicodova spojka  A  B ¬ AB 1) ¬ A¬ A A A A 2)  AB ¬¬ AB¬¬A¬B ¬ A ¬B A A  B  B 3)  AB ¬¬ AB ¬ A B A B A B Úplné a neúplné konjunktivní a disjunktivní formy Definice: Nech A1 , A2 , ... , A n jsou libovolné výrokové promnné. Potom: 1) Formuli F nazveme normální disjunktivní formou (NDF) nad množinou promnných A1 , A2 , ... , An , je-li tato formule ve tvaru disjunkce a každý její disjunktivní
len je ve tvaru konjunkce nkterých promnných z množiny A1 , A2 , ... , A n nebo jejich negací.   2) Formuli F nazveme normální konjunktivní formou (NKF) nad množinou promnných A1 , A2 , ... , A n , je-li tato ve tvaru konjunkce a každý její konjunktivní
len ve tvaru disjunkce nkterých promnných z množiny A1 , A2 , ... , A n nebo jejich negací.   Poznámka: NDF a NKF vytváíme k dané formulí A vtšinou ekvivalentními úpravami vzhledem k platnosti následující vty. V
ta: Ke každé formulí A výrokové logiky vždy existuje normální disjunktivní forma logicky s ní ekvivalentní a normální konjunktivní forma logicky s ní ekvivalentní. Dkaz: Je z
ásti uveden v dkazu vty*, z
ásti uveden v dkazu následující vty Definice: Nech A je libovolná výroková promnná, potom samu tuto promnnou nebo její negaci nazveme literálem promnné A . Definice: 1) Normální disjunktivní formu nad množinou promnných A1 ,... , An nazveme úplnou normální disjunktivní formou (ÚNDF), jestliže každý její disjunktivní
len (každá konjunkce) obsahuje práv jeden literál od každé z promnných A1 ,... , An . 2) Normální konjunktivní formu nad množinou promnných A1 ,... , An nazveme úplnou normální konjunktivní formou (ÚNKF), jestliže každý její konjunktivní
len (každá disjunkce) obsahuje práv jeden literál od každé z promnných A1 ,... , An .

8

V
ta: Ke každé formuli výrokové logiky A , která není kontradikcí, existuje úplná normální disjunktivní forma nad množinou jejich promnných, která je s ní logicky ekvivalentní. Je-li vnitních promnných n , potom je formule A tautologií práv tehdy, jestliže jí píslušná ÚNDF obsahuje práv 2 n disjunktivních
len (závorek). Dkaz: Dkaz je obsažen v bod b) vty*, kde formule D byla konstruovaná práv ve tvaru ÚNDF. Kdyby by byla formule A tautologií, bude mít 1 ve všech ádcích a konjunkce ze všech ádk budou zapojeny do výsledné disjunkce, bude jich tedy 2 n . Naopak, kdyby to byla kontradikce, nenajdeme ádek, v nmž by ph  A=1 , tudíž ÚNDF nelze sestrojit. V
ta: Ke každé formuli výrokové logiky A , která není tautologií, existuje úplná normální konjunktivní forma nad množinou jejich promnných. Je-li tchto promnných n , je formule A kontradikcí práv tehdy, jestliže jí píslušná ÚNKF obsahuje práv 2 n konjunktivních
len. Dkaz: Máme formuli A s vnitními promnnými A1 , A2 , ... , An A1 A2 An 2 n ádk

{

Vyjdeme z tabulky pravdivostních hodnot. Nyní ke každému ádku pipojíme ur
itou disjunkci, tj. k i-tému ádku pipojíme disjunkci  j A ... pro pípad , kdy ph  A j =0  i i D i=V i kde V j = j v i-tém ádku 1 V 2 ...V n ¬ A j... pro pípad , kdy ph  A j =1 ph D i =0 práv pouze pro zastoupení hodnot v i-tém ádku. Nyní tyto disjunkce zaadíme do výsledné konjunkce C , ale ne ze všech ádk, pouze z tch, kde ph A =0 . Formule C je hledanou úplnou normální konjunktivní formou a sta
í ukázat, že je ekvivalentní s pvodní formulí A . Zvolíme obecný k-tý ádek 1)  ph A =0
D k C  ph D k =0
ph C =0 2)  ph A =1
D k C  phD j =1
phC =1

{

j k

Kdyby formule A byla tautologií, nenajdeme ádek, v nmž by ph A =0 a tudíž ÚNKF nelze konstruovat. Naopak, je-li A kontradikcí, budou 0 ve všech ádcích,tj. disjunkce ze všech ádk zahrneme do výsledné konjunkce. Bude jich tedy 2 n . Poznámka: Pesn v duchu obou tchto dkaz (vty* a pedešlé) se ÚNDF a ÚNKF konstruují. Pi ÚNDF udláme tabulku pravdivostních hodnot, najdeme ádky, v nichž celková formule má pravdivostní hodnotu 1. Z tchto ádk udláme konjunkce a to tak, že kde byla jedni
ka, zstane promnná stejná, kde byla nula, dáme její negaci a konjunkce zaadíme do výsledné disjunkce. Pi ÚNKF je to pesn naopak.

9

Základy predikátové logiky V predikátové logice již výrok není nedlitelným celkem, ale dlíme jej na dv
ásti, na tzv. subjekt a predikát. Píklad: „Dané
íslo je dlitelné sedmi.“ Subjekt: Dané
íslo Predikát: je dlitelné sedmi. Predikát je vlastnost, která je tímto výrokem subjektu piazována. Výrokovou formou v predikátové logice budeme rozumt libovolné sdlení, obsahující libovolné promnné(i nevýrokové) s píslušným oborem promnnosti, z kterého se stane výrok až po dosazení konstant za všechny promnné, z jejich oboru promnnosti. Píklad: x je dlitelné y , x , y  Dvourozmrná výroková forma (má dv promnné). Podle po
tu promnných rozlišujeme výrokové formy na jednorozmrné a více rozmrné. V predikátové logice je možno z výrokové formy u
init výrok i jiným zpsobem, než dosazením a to pomocí tzv. kvantifikátor. V této souvislosti platí následující definice. Definice: Nech V  x  je jednorozmrná výroková forma, kde x {a1 , a 2 , ... , a n } . Potom: 1) Všeobecným výrokem k dané výrokové form budeme rozumt výrok, který je pravdivý práv tehdy, když po dosazení kterékoliv konstanty z oboru promnnosti dá výroková forma pravdivý výrok. Zapisujeme takto V  x V a 1 V a 2...V a n  . x

2) Existen
ním výrokem k dané výrokové form, budeme rozumt výrok, který je pravdivý práv tehdy, když po dosazení alespo jedné konstanty z oboru promnnosti dá výroková forma pravdivý výrok. Zapisujeme takto V  xV a 1 V a 2 ...V a n  . x

Pravidla používání kvantifikátor: Jedná se o dv pravidla, jedno se týká zámny poadí kvantifikátor a druhé používání negace ve formách s kvantifikátory. Uvažujme dvourozmrnou výrokovou formu V  x , y  1) V  x , y  5)  V  x , y  x y x y  2) V  x , y  6)  V  x , y  y

3)

 V  x , y  x y

4)

 V  x , y  y x

y

x

x

7)  V  x , y  

x

y

8)  V  x , y  y x

10

x {a1 , a 2 , ... , a n } y{b1 ,b 2 , ... ,b n }

V  x , y  V  x , b 1V  x , b2 ...V  x , bn V a 1 ,b 1V a 1 ,b 2 ...V a 1 , b n x

y

x

V a 2 , b 1 V a 2 , b2 ...V a 2 , bn ...V  a n , b1 V a n ,b 2 ...V a n ,b n   V  x , y y

x

Podobn by se to dalo odvodit i pro 3) a 4), jen s tím rozdílem, že všude budou disjunkce, kdežto vyjádíme-li 5) budou uvnit velkých závorek disjunkce a mezi tmi závorkami konjunkce, což se žádným roznásobením nebo zmnou poadí nedá pevést na výraz 6). Tzn. , že 5) a 6) a podobn i 7) a 8) nebudou navzájem ekvivalentní. 1. Pravidlo poadí kvantifikátor: Poadí kvantifikátor téhož typu lze libovoln zamovat, kdežto poadí kvantifikátor rzných typ zamovat nelze. V  x  x{a 1 , a 2 ,... , a n } ¬ V  x  ¬V a1 V  A2 ...V a n ¬V  a1 ¬V a 2...¬V a n  ¬V  x  x

x

¬ V  x¬V a 1V  a 2...V a n ¬V a 1 ¬V a 2 ...¬V a n  ¬V  x x

x

Negací všeobecného výroku je existen
ní výrok vztažený k negaci výrokové formy. Negací existen
ního výroku je všeobecný výrok vztažený k negaci výrokové formy. 2. Pravidlo negování výrok s kvantifikátory: Negujeme-li výrokovou formu s kvantifikátory, pemníme tyto na opa
né a vztáhneme je k negaci výrokové formy. Píklad:

 x y 
  y=x z x

y

z

x , y , z 

1) 2)

A
B ph A
B =? B
A  ph ?

ph=1

  y= xz 
 x= y

3)

¬B
¬A  ph ?

  y xz 
 x  y ph=1

¬A
B  ph ?

 ¬A
B
  A ¬B   x y   yx z  ph=0

4)

x x

x y

y y

z

ph=1

z

x y

11

x y

z

TEORIE MNOŽIN 3. Vývoj teorie množin, Zermelo-Fraenkel
v axiomatický systém Teorie množin prošla od svého vzniku rozsáhlým vývojem. První ucelenou teorií byla Cantorova intuitivní teorie, která v sob
ale obsahovala v
tší množství paradox. Ze snahy se t
mto paradoxm vyhnout vychází moderní teorie množin z axiomatického pojetí, kde na poátku je vysloveno urité množství poáteních axiom a teprve potom na nich budována bezesporná teorie. Vyvinuly se dva sm
ry ze dvou rzných axiomatických systém. Gödel-Bernaysv axiomatický systém a Zermelo-Fraenkelv axiomatický systém. Gödel-Bernaysv vychází z pojm tída a náležení ke tíd
, piemž rozlišujeme tídy na tzv. vlastní a nevlastní, vlastní jsou ty, které už nemohou být prvky jiných tíd, kdežto nevlastní jsou naopak prvky jiných tíd a splývají s prvkem množina. Celý axiomatický systém je zde mén
poetný, ale celá teorie je komplikovan
jší, takže se tomuto systému nebudeme v
novat. Zermelo-Fraenkelv axiomatický systém vychází z pojm množina a náležení množin
. Je zde více axiom (dohromady 11), celá teorie však je jednodušší. Poznámka: Existují také hybridní pojetí, která vychází ze Zermelo-Fraenkelova axiomatického systému, ale zavádí se zde i pojem tíd. Proto abychom dosp
li k tíd
všech množin, tzv. univerzu. Tída všech tíd zde už ale neexistuje. Jazyk teorie množin Výrazové prostedky teorie množin jsou velmi sevené. Vycházíme zde pouze ze znalostí výrokové a predikátové logiky a pitom se snažíme o co nejv
tší formalizaci. 1) x ,Y , z , A , B ,
,  ... znaení pro množinové konstanty i prom
nné 2)  ,  3) = ,  4) ¬ ,  ,  ,  , , ,  5) [] , {}, 6) Další symboly  ,  , , , 1 , 2 , ... Poznámka: V teorii množin má dležité postavení tzv. formule teorie množin (FTM). Definice: 1) a A , x Z , a=b , X Y tyto formule nazveme atomickými formulemi 2) Jestliže  , jsou FTM ¬ , ¬ , , ,   ,   jsou op
t FTM  x ,  x jsou FTM 3) Jestliže  x je FTM volné prom
nné x 

x x 4) Vše co dostaneme koneným potem krok 1 až 3 je op
t FTM

12

Zermelo-Fraenkel
v axiomatický systém I. Axiom existence Existuje alespo jedna množina.  x= x (vždy spln
no) x

II. Axiom rovnosti (extenzionality) Dv
množiny A , B jsou si rovny práv
tehdy, mají-li tytéž prvky.

A= B x A x B

A

B

x

Poznámka: Z tohoto axiomu plynou dv
implikace A=B  x A  xB

x

x= y  x  A  y  A

A

III.Axiom sumy (sjednocení) K libovolné množin
S (zvané systém množin) existuje množina M (zvaná sjednocení systému), která obsahuje práv
ty prvky,které patí alespo do jedné z množin systému S .

 x M  AS  x A

S M x

A

Poznámka: M =S , M =  Ai Ai S

Poznámka: Z II. plyne, že sjednocení systému je ureno jednoznan
, což lze dokázat sporem.

x M  A S x A

II. A  xM x N  M =N M =S , N =S , pak platí x x

x N  AS  x A

x

}

A

IV. Axiom dvojice (existence dvouprvkové množiny) Pro každé dv
množiny a ,b existuje množina A , která práv
tyto dv
množiny obsahuje jako své prvky.

 x A x=a x=b

a

b A x

Poznámka: Pro pípad, kdy a=b , je zaruena existence jednoprvkové množiny A={a , a}={a } Poznámka: Axiomy III. a IV. nám zaruují i existenci libovolné típrvkové, typrvkové ... až n-prvkové III. množiny, nebo S ={A , B} , A={x , y },  B={z }  S ={x , y , z } V. Axiom separace (Zermelovo separaní schéma) Nech  x je libovolná formule teorie množin volné prom
nné x . Potom z každé množiny A lze vybrat množinu C t
ch prvk, pro které je spln
no  x .

 xC x A  x

A C x

13

Poznámka: Axiom V. v sob
obsahuje nekonené množství axiom podle volby formule  x . Souasn
nám tento axiom umožní zavést standardní množinové operace, jako je množinový prnik, množinové sjednocení, množinový rozdíl a prokázat existenci prázdné množiny. Vta: 1) Ke každým dv
ma množinám A , B existuje práv
jedna množina A B , obsahující práv
ty prvky, které patí alespo do jedné z obou množin. 2) Ke každým dv
ma množinám A , B existuje práv
jedna množina A B , obsahující práv
ty prvky, které patí do obou množin souasn
. 3) Ke každým dv
ma množinám A , B existuje práv
jedna množina A  B , obsahující práv
ty prvky, které patí do A a nepatí do B . 4) Existuje práv
jedna množina  , zvaná prázdná množina, která neobsahuje žádný prvek. D
kaz: 1) plyne triviáln
z III. 2)  x C x  A   x  B

A

3)

 x

 x C x  A   x B

A

4)

B C x

B C x

 x

 xC x A   x x

A C x

 x

Poznámka: Pro výše uvedené množinové operace platí následující vlastnosti. 1)  A=A 2)  A= 3) A B=B A 4) A B=B A 5) A BC = AB C 6) A BC = AB C 7) A BC = AB  AC 8) A BC = AB  AC 9) A  BC = A B  A C 10) A  BC = A B  A C 11) A  B  C = A B  AC Poznámka: Mimo tyto zavedené operace je teba zavést i operace množinové inkluze. Definice: 1) ekneme, že množina A je ástí množiny B ( A B ), jestliže každý prvek množiny A je souasn
prvkem množiny B . 2) ekneme, že množina A je vlastní ástí množiny B ( A B ), jestliže AB  AB . tj. platí 1) AB x A  xB

x

2) AB x A  x B

 y  B  y  A

x

y

14

Poznámka: Množinová inkluze spluje následující vlastností: 1)  A 2) ¬ A A (není pravda, že A A ) 3) AB  AB= A 4) AB  AB=B 5) ABBC  AC 6) ABBC  AC 7) ABBC  AC Definice: Dv
množiny A , B nazveme vzájemn
disjunktními množinami, jestliže A B= . VI. Axiom potence (existence potenní množiny) Ke každé množin
A existuje množina P A zvaná potenní množina, která obsahuje práv
všechny podmnožiny množiny A jako své prvky.

 X P A

X  A

A P A X

Poznámka: Potenní množina je urena jednoznan
(plyne z II.). Poznámka: Jestliže množina A je n-prvková, potom její potenní množina má 2 n prvk. D
kaz A ....n-prvková množina n  ...práv
jedna ... 0





n Jednoprvkové množiny ... n= 1 n Dvouprvkové množiny ... n= 2 .................................... n =1 Celá množina ... n

Souet je 2 n



n

ab = n

i =0



n ai b ni i

n



11 = n 1i 1 ni=2 n i=0 i n

VII. Axiom výbru Ke každému systému S neprázdných, po dvou disjunktních množin existuje množina V taková, že s každou množinou systému S má jednoprvkový prnik (z každé množiny systému daných vlastností lze vybrat po jednom prvku).

A S  A

 AS B S A B  A B=

 S

A

A

B

 AS   V  A={x }

. V A x

15

Poznámka: Disjunktnost po dvou je pro množinu V a její existenci podstatná.(viz. píklad) Píklad: S={{x} ,{ y }, {x , y}} V ={x , y} nespluje požadovanou vlastnost. Poznámka: Množina V v axiomu výb
ru není urená jednoznan
, dokonce mže existovat nekonen
mnoho takovýchto množin. Napíklad: S={{x} ,{ y }, {a , b}} V 1={x , y , a} V 2 ={x , y , b} V 3={x , y , a , z , c , d }

Poznámka: Axiom výb
ru je ekvivalentní tzv. Zermelov
v
t
o výb
rové funkci. VIII. Fraenkelovo substituní schéma Nech  x , y je libovolná formule teorie množin volných prom
nných x a y taková, že ke každému x existuje nejvýše jedno y tak, že platí  x , y . Potom ke každé množin
A (prvk x ) existuje množina B (prvk y ) tak, že pro n
platí formule  x , y .

 x , y  x , z

 y=z

  y  B  x  A x , y

x

y

z

A B y

x

Poznámka: Fraenkelovo substituní schéma v sob
obsahuje nekonené množství axiom podle volby formule  x , y .

16

4. Relace a jejich vlastnosti Definice: Nech
a ,b jsou libovolné množiny. Potom jejich uspoádanou dvojicí [a , b] budeme rozumt systém množin {{a }, {a , b}} Poznámka: Pozice a ,b budeme nazývat souadnicemi uspoádané dvojice. Poznámka: Pro regulérnost a smysl výše uvedené definice je teba dokázat, že dv rzné uspoádané dvojice jsou si rovny, jestliže jsou si rovny jejich odpovídající si souadnice. D
kaz: Chceme dokázat
[a ,b ]=[c , d ]

a=c 
b=d  .
[a ,b ]=[c , d ]
{{a }, {a , b}}={{c }, {c , d }}
{a}={c }
{a , b}={c , d } 

{a }={c , d }
{a , b}={c}
a=cb=d 
a=b=c=d  Definice: Nech
A , B jsou libovolné množiny. Potom jejich kartézským souinem budeme rozumt množinu všech uspoádaných dvojic [a , b] takových, že a A , bB . A× B={[a ,b ]; a  A ,b B } Poznámka: Kartézský souin není obecn asociativní, asociativita neplatí dokonce ani v pípad týchž jednoprvkových množin. Píklad: A= B=C ={x} A×
B×C ={[ x , [ x , x] ]}
A×B×C ={[ [ x , x] , x ]} Jsou rzné, protože x[ x , x ]={{x }, {x , x}}={{x }, {x }}={{x}} Poznámka: Komutativita kartézského souinu platí pouze v pípad stejných množin, nebo v pípad, že jedna z nich je prázdná množina. Vta: Nech
A , B jsou libovolné množiny. Pak platí: 1)
A×B=
A= B= 2)
A×B=B×A
A=B=A=B D
kaz: 1) je triviální

dokážeme sporem
AB

x  A
y  B 
[x , y ] A×B (spor s pedpokladem) x y [ x , y] 2) je triviální

dokážeme sporem
ABA B
A B

x Ax B

y A y  B x


[x , y ] A×B[ x , y ] B× A

[ x , y]

17

y

Poznámka: Další vlastnosti kartézského souinu: 1) A×
B C =
A×B
A×C  2) A×
BC =
A×B
A×C  3) A×
B  C =
A×B
A×C 
AC B D
A×B
C×D Definice: Nech
A , B jsou množiny, potom binární relací (korespondencí) mezi prvky množiny A a B budeme rozumt libovolnou podmnožinu A× B . Poznámka: Relace budeme znait eckými písmeny z konce:  ,  ,... . Definice: Nech
A× B , potom: 1) Defininí obor D={x  A , 
[ x , y ]} y B

2) Obor hodnot W ={ y B , 
[ x , y ]} x A

3) Pole relace C = D×W  Poznámka: Speciální postavení v teorii množin mají 2 relace: I ={[ x , y ] A×B , x= y } identita E={[ x , y ] A×B , x y } relace náležení Definice: Nech
A× B , potom inverzní relací 1 budeme rozumt 1 ={[ y , x ]B× A; [ x , y ]} Definice: Nech
A× B , B×C , potom složenou relací °={[ x , z ] A×C , 
[ x , y ][ y , z ]} y B

Vlastnosti relací: 1)
 1=1 1 2)
1=11 3)
°1 =1 °1 4) °
  =
°
°  5) °
 =
°
°  6)

11 Vlastnosti relací na množin: Definice: Nech
A je libovolná množina a A× A . Potom: 1)  je reflexivní na A : 
[ x , x ] x A

2)

 je symetrická na A : 
[ x , y ] [ y , x ]

3)

 je asymetrická na A : 
[ x , y ] [ y , x ] 

x , y A

x , y A

18

4)

 je tranzitivní na A : 

[ x , y ][ y , z ] [ x , z ]

5)

 je atranzitivní na A : 

[ x , y ][ y , z ] [ x , z ] 

6)

 je trichotomická na A : 

x y 
[ x , y ][ y , x]

7)

 je antisymetrická na A : 

[ x , y ][ y , x ]
x= y 

8)

 je ireflexivní na A : 
[ x , x] 

x,y, z

x,y, z

x , y A

x ,y A

x A

Poznámka: Ireflexivita, atranzitivita a asymetrie nejsou prostými negacemi tch pvodních relací. Relace ekvivalence na množin: Definice: Nech
A je libovolná množina a A× A , potom relaci  nazveme relací ekvivalence na množin A , jestliže je reflexivní, symetrická a tranzitivní. Platí: x~ x 1  
[ x , x ] x A

2  
[ x , y ] [ y , x ] x , y A

3  

[ x , y ][ y , z ] [ x , z ] x,y, z

}


x~ y 
y~x 
x~ y y~ z
x~z 

Rozklad množiny Definice: Nech
A je libovolná množina, potom libovolný systém S neprázdných po dvou disjunktních podmnožin této množiny nazveme rozkladem množiny A , jestliže navíc platí S =A . Vta: Nech
M je libovolná množina a nech
 je relace ekvivalence na M a nech
dále  je xM

definována množina A x ={ y M , x~ y} . Potom systém S všech takových množin A x S={A x , pro x M } tvoí rozklad množiny M a nazveme ho rozkladem indukovaným relací ekvivalence  . D
kaz: 1) A x  1 2) x ~ y
A x A y = .... 1 ~ je ~ peškrtnuté!

A x =M 3) xM

1) reflexivita 
x Ax  Ax  x M

1

1

2) Sporem: pedpokládejme

x ~ y
A x A y 

x ~ y  zM
z  A x z A y 

1



x~ y

z~ xz~ y z M

3)

tranzitivita



1


x ~ y 
x~ y  .


x A x  A x =M

xM

x M

Vta: Nech
M je libovolná množina a S je její libovolný rozklad. Nech
na M je definována relace ={[ x , y ]M ×M ; 
A S x A y  A} , potom relace  je relací ekvivalence na M . A

19

D
kaz: Chceme dokázat, že: 1)  je reflexivní 2)  je symetrická 3)  je tranzitivní 1) Pro x= y 
AS x  A y  A[ x , x ] A

2)

[ x , y ]
AS x A y A
AS  y  A x A[ y , x ]

3)


[ x , y ][ y , z ]

AS x A y A

BS  y Bz B
A= B

A

A

A

B


AS x  Az  A[ x , z ] A

Píklad: Mjme N pirozených ísel ={[a , b] N ×N ; ab
mod m , m , m1} relace ekvivalence na N S={0 , 1 , 2 , ... , m1} tvoí rozklad N (indukovaný  ). Píklad: A={a , b , c } . Popište všechny možné rozklady A a její píslušné relace ekvivalence. S 1={{a} ,{b}, {c}} 1={[a , a ] ,[b , b ], [c , c]}= I S 2={{a , b} ,{c }} 2=I {[a , b ] ,[ b , a ]} S 3={{a , c} ,{b}} 3=I {[a , c ] ,[c , a ]} S 4 ={{a },{b , c }} 4=I {[b , c] ,[c , b ]} S 5={{a , b , c}} 5=A× A Relace uspoádání na množin M Definice: Nech
M je libovolná množina. Potom relaci M ×M nazveme relací ásteného uspoádání (ásteným uspoádáním M ), jestliže je tato asymetrická a tranzitivní. Relaci M ×M nazveme relací úplného (lineárního) uspoádání množiny M , jestliže je tato asymetrická, tranzitivní a trichotomická. Poznámka: Místo [ x , y ] budeme zapisovat x y (pedchází). Vlastnosti: 1 1) x y y  x asymetrie 2)
x y y z  x z tranzitivita ástené uspoádání 3)
x y 
x y y x  trichotomie

úplné uspoádání

Poznámka: Nkdy se uvádí i vlastnost ireflexivity, tato však už pímo plyne z asymetrie. Kdybychom pipustili
xx  , tak by z asymetrie vyplynulo x 1  x , což je spor. Ireflexivitu tedy nemusíme uvádt. Poznámka: Námi uvedená relace uspoádání odpovídá ostré nerovnosti mezi ísly. V algebe se uvádí relace odpovídající neostré nerovnosti
x y  , která je potom ale reflexivní, antisymetrická, tranzitivní a trichotomická. 20

Píklad: Píkladem ásteného uspoádání systému S libovolných množin je relace inkluze ={[ A , B ]S ×S , AB} . Definice: Nech
M je alespo ásten uspoádaná množina njakou relací  , potom ekneme: 1) Prvek a M nazveme prvkem minimálním v množin M , jestliže pro žádné x M není splnno, že xa ( x pedchází a ). 2) Prvek bM nazveme prvkem maximálním v množiny M , jestliže pro žádné x M není splnno bx ( b následuje x ). 3) Prvek c M nazveme nejmenším (prvním) prvkem z množiny M , jestliže  xc xM

platí cx . 4) Prvek d  M nazveme nejvtším (posledním) prvkem z množiny M , jestliže 
xd x d  xM

Poznámka: Prvek nejmenší je souasn prvkem minimálním. Prvek nejvtší je souasn prvkem maximálním, naopak to neplatí. Zatímco minimálních a maximálních prvk mže být více, nejmenší respektive nejvtší prvek mže být nejvýše jeden. Píklad: Množina A která vznikne z N {1} ={[a , b] A×A ; aba /b } Potom relace  je relace ásten uspoádané množiny A . Minimálních prvk je zde nekonen mnoho(jsou to všechno prvoísla), nejmenší prvek zde neexistuje, maximální a nejvtší prvky nejsou. Píklad: N ,={[a , b] A×A , aba / b} existuje nejmenší prvek, který je souasn minimální (1) a maximální a nejvtší prvky zde nejsou. Funkce Definice: Nech
X , Y jsou libovolné množiny. Potom relaci f  X ×Y nazveme funkcí (zobrazením) množiny X do množiny Y , jestliže platí: 1) 2)

  [ x , y] f

x X y Y

 

[ x , y ] f [ x , y ' ] f 
y= y ' 

x X y , y ' Y

neboli pro každé x X existuje práv jedno y Y tak, že [ x , y ] f . Poznámka: Místo [ x , y ] f budeme psát y= f
x  f  X ×Y f : X Y x nazveme argument funkce, y nazveme hodnotou funkce.

21

Poznámka: Nech
A X Potom symbolem f
A budeme rozumt f
A={ yY ,  y= f
x} . xA

f
A - množina všech obraz prvk z A . Definice: Nech
A X a f : X Y , potom symbolem f / A : AY : f / A= f 
A×Y  a tuto funkci nazveme restriktivní funkcí (restrikcí) funkce f na množin A . Definice: Funkci f : X Y nazveme surjektivní funkcí (surjekcí) nebo zobrazením na množinu, jestliže platí f
X =Y . Definice: Funkci f : X Y nazveme injektivní funkcí (injekcí) nebo prostým zobrazením do množiny, jestliže platí 

xx ' 
f
x  f
x '  . x , x' X

Definice: Funkci f : X Y nazveme bijektivní funkcí (bijekcí) nebo prostým zobrazením na množinu, jestliže je injektivní a surjektivní souasn. Vta: Nech
funkce f : X Y je injekce. Potom inverzní relace f 1 je bijekce f 1 : f
X  X . Vta: Nech
funkce f : X Y je bijekce. Potom inverzní relace f 1 je bijekce f 1 : Y  X . Vta: Nech
funkce f : X Y je surjekce a g : Y Z je surjekce. Potom složená relace f ° g : X  Z je surjekce. Vta: Nech
funkce f : X Y je injekce a g : Y Z je injekce. Potom složená relace je injekce.

f °g : X Z

Vta: Nech
funkce f : X Y je bijekce a g : Y Z je bijekce g : Y Z . Potom složená relace f ° g : X  Z je bijekce. Poznámka: Nech
A , B jsou libovolné množiny, potom symbolem B A={ f : B A} . Vta: Zermelova o výbrové funkci K libovolnému systému S neprázdných množin existuje funkce f zvaná výbrová funkce zobrazující S do sjednocení f : S  S taková, že platí 
f
A= x A . A S

22

D
kaz: Opírá se o dva axiomy: VIII a VII. S ....uvnit A .... uvnit x    S ... A ... x    x =[ A , x ] A ={A}×A S Axiom VIII nám existenci systému S  zaruuje, protože   
A S  
AS  A={A}×A S S A

A


A , A  Systém S již obsahuje po dvou disjunktní množiny, protože   
AB {A}{B}
{A}×  A{B}×  B= A B = 

A , B S

A





B

Protože se vždy budou lišit v první souadnici. Na systém S  již lze aplikovat VII, což je axiom výbru, takže lze zapsat   

AS  
V A={x } 

S V





A



x

Neboli z každé množiny A systému S  lze vybrat po jednom prvku x  . x =[ A , x ], x  A Prvky x  už budou vytváet naši hledanou funkci f .   f =V  S

23

5. Ekvivalentnost množin, jejich mohutnost a jejich kardinální
ísla V teorii množin je snaha o porovnání jednotlivých množin, tj. porovnání jejich mohutnosti. P
iemž množiny stejn poetné budou pro nás stejn mohutné a práv v tchto p
ípadech bude existovat bijekce jedné množiny druhou. U nekonených množinách o potu prvk nelze hovo
it. V tomto p
ípad práv existence bijekce bude m
ítkem mohutnosti a p
itom budeme hovo
it o navzájem ekvivalentních množinách a budeme jim p
i
azovat totéž kardinální íslo. Definice: Nech A , B jsou libovolné množiny, potom
ekneme, že A je ekvivalentní s B (zapisujeme A~ B ), jestliže existuje njaká bijekce f zobrazující A na B . Vta: Platí vlastnosti pro A , B , C : 1) A~ A 2)
A~B 
B~ A 3)
A~B
B~C 
A~C  Dkaz: 1) Vždy existuje bijekce f : A A , staí zvolit identitu f
x =x pro každé x A 2)
A~B 
 bijkece f : A B  bijekce f 1 : B  A
B~A 3)

A~B
B~C 
 bijekce f : A B bijekce g : BC 
 : f g : A C  
A~C  Poznámka: Vzhledem k symetrii ekvivalentnosti množin lze hovo
it o navzájem ekvivalentních množinách. V ekvivalentnosti množin platí následující vztahy: 1)
A×{x }~ A 2)
A×B~
B×A 3)
A×
B×C ~

A×B×C  4)
A×
B C~

A×B
A×C  5)
A B=C D=A~CB~D

A B~
C D 6)

A~C 
B~D

A×B~
C×D 7)
A~C B~D
B A~ DC  8)
B C =

B C  A~
B A×C A  9)
A B×C ~
AB ×AC  10) A
B ~
A× BC C

Ekvivalentnost množin je reflexivní, symetrická a tranzitivní, je tedy relací ekvivalence na libovolném systému uvažovaných množin. Zpsobuje tedy rozklad tohoto systému na t
ídy vzájemn ekvivalentních množin a my z každé té t
ídy mžeme vybrat jednoho reprezentanta a toho nazveme kardinálním íslem. nula prvkové ~ ... oznaíme 0 (prázdná množina je sama sob kardinálním íslem) 1-prvkové {}={0} ... oznaíme 1 2-prvkové { , {}}={0 , 1} ... oznaíme 2 3-prvková { , {}, { , {}}}={0 , 1 , 2} ... oznaíme 3 Z výše uvedené konstrukce je z
ejmé, že existence konených kardinálních ísel je již zaruena, kdežto obecn i pro nekonené je jí pot
eba zajistit axiomaticky

24

IX. Axiom existence kardinálního
ísla Ke každé množin A existuje množina card
A která je ekvivalentní s pvodní množinou a pro každé dv ekvivalentní množiny bude platit, že jejich kardinální ísla se budou rovnat.  
 A~A 

A~B
 A=B  A  A

A

B

Poznámka: Místo card
A budeme psát  A ... kardinální íslo množiny A . Vta: 1) 2)

 A= A
 A= B
A~B

Dkaz: IX. 1)
 A~ A
 A= A 2)
A~ A=B~B
A~B Vta: Ke každému libovolnému systému S existuje množina K obsahující práv všechna kardinální ísla množin systému S . Dkaz: P
es axiom VIII.   
a  K 
AS a= A  S K a

A



A , a  Poznámka: Budeme dodržovat: a= A , b= B , c=C Aritmetika kardinálních
ísel Zavádíme souet, souin a mocninu. Definice: Nech a ,b jsou libovolná kardinální ísla z množiny K . 1) Soutem ab budeme rozumt kardinální íslo množiny

a×{0 }
b×{1} 2) Souinem ab budeme rozumt kardinální íslo jejich kartézského souinu. ab=a×b 3) Mocninou a b budeme rozumt kardinální íslo množiny všech zobrazení { f : b a } . Neboli platí: 1) ab=

a×{0}
b×{1} 2) ab=a×b 3) a b=b a Poznámka: Definice soutu komplikujeme kartézskými souiny, protože kardinální ísla nejsou obecn disjunktní. Z konstrukce je z
ejmé, že každé menší je souasn prvkem i podmnožinou každého vtšího. Kdežto množiny a×{0}, b×{1} už jsou vzájemn disjunktní, protože se liší na druhé pozici, ale p
itom jsou ekvivalentní pvodním množinám. 25

Smysl této definice bude z
ejmý z následující vty. Vta: Nech A , B jsou libovolné množiny, potom: 1)
A B=
 A B= A B 2)  A×B= AB 3) B A= AB Dkaz: Ozname a= A , b= B 1) A~a~
a×{0} B~b~
b×{1} {
A B~

a×{0}
b×{1}} { A B=
a×{0}
b×{1}=ab= AB} A B=
a×{0}
b×{1}= 2)

A~a 
B~b 

A×B~
a×b  A×B=a×b=ab= AB 3)
a~ Ab~B B A ~ b a  B A=ba=a b= AB






Další vlastnosti kardinálních ísel vzhledem k soutu, souinu a mocnin: Pro a , b , cK platí: 1) ab=ba 2) ab=ba 3) a
bc=
abc 4) a
bc=
abc 5) a
bc=abac 6) a
bc=a ba c 7)
abc =a cbc 8)
a b c =abc Dkaz: 1) a= A , b= B , c=C , A B= , B C = , A C =

A×
B C =

A×B
A×C
 A×
B C =
A×B
A×C 
a
bc =a ba c  2)
B C A ~B A×C A 
B C A=B A×C A  f : B C  A={q : B  A}×{h : C  A}=a bac Poznámka: Vlastnosti soutu, souinu a mocniny konených kardinálních ísel jsou v souladu s vlastnostmi p
irozených ísel a nemohou nás p
ekvapit, kdežto vlastnosti nekonených kardinálních ísel nás p
ekvapit mohou. Píklad: Víme, že = 0 ,  0= . ~ ~0 ~  bijekce f :   f
0= 1 f
1= 2 f
1= 3 f
2= 4 f
2= 5 .... ~0  bijekce g :  0 g
0=0 g
1=1 g
1=2 g
2=3 g
2=4 .... Ozname a== = 0 . a=aa . Z = 0 a  0 = plyne =  0

26

Poznámka: Vzhledem k tomu, že kardinální ísla p
edstavují u konených množin poet jejich prvk a obecn oznaují mohutnost p
íslušné množiny, musíme je mezi sebou njak porovnávat. Nerovnosti mezi kardinálními
ísly Definice: Nech a ,bK , potom
ekneme, že 1) ab , jestliže existuje injekce f : a b , tj.

 
a~b  . 

b b


ab jestliže
abab Jinak
eeno 1)
ab 
a~b  2)



b b

2)


ab
abab

Vta: Nech A , B jsou libovolné množiny a= A , b= B . Potom bude platit
ab  injekce h : A B . Dkaz: 1) 
ab injekce f : a  b 1
a~A bijekce : a  A injekce h= ° f ° : A B
b~B  bijekce : b  B 2)  analogicky

}

Poznámka: Pro nerovnosti mezi kardinálními ísly platí následující vztahy: 1)
ab
ac 
bc  2)
ab
acbc 3)
ab
a cbc  4)
ab
c ac b  5)

ab
bc 
ac Poznámka: P
i ostré nerovnosti už by p
íslušné implikace, hlavn pro nekonená kardinální ísla nemusely platit. Cantor-Bernsteinova vta a její dsledky Vta Bernsteinova Nech A , B jsou libovolné množiny. Existuje-li njaká injekce f : A B a souasn existuje-li njaká injekce g : B  A , potom musí existovat njaká bijekce : A  B a platí A~ B .

27

Dkaz:  Existuje injekce f : A B   f : A  B je bijekce  A~B . B B 



Existuje injekce g : B  A  A  A g : B  A 









je bijekce  B~ A .


h= f ° g / B : A A je bijekce A~ A tj. pro konené množiny 

A A  A  



A  A  A
A~ A
A= A= AA~B
A~ B Pro nekonené množiny dkaz pokrauje pomocnou vtou. Pomocná Vta: Nech A ,C , A1 jsou libovolné množiny takové, že AC A1 a p
itom platí A~ A1 . Potom platí A~C . Dkaz: A~ A1  bijekce : A A1 tj. platí
A= A1 .


C =C 1  A1 C A C A A1C A


A1= A2C 1 A1C A AC A1 C 1 A2C 2.... A~ A1~ A2~A3~... C~C 1~C 2~C 3~...
A C ~
A1 C 1 ~
A2 C 2 ~... tj. existuje bijekce f :
Ai C i 
Ai 1 C i1 i{0 , 1 , 2 , ...} C=C 0 , A= A0  bijekce  : AC 
x= i
x= x pro x
C i Ai1  A~C f
x pro x 
Ai C i 

{

}

Závr do p
edchozí vty V roli A .... A  A~B V roli A ... A1  V roli A ... C Dsledek 1: Pro libovolná kardinální ísla a ,b plyne následující implikace
abba 
a=b . Dkaz: Je p
ímým závrem C-B vty. Dsledek 2: Pro libovolná kardinální ísla a ,b platí: 1 1)
ab
b a 2)
abbc 
ac  Dkaz: 1)
abba 
ababbaab
a=bab - spor 2)
abbc 
ababbcbc 
ac a je t
eba ukázat, že ac a to sporem. P
ipusme, že
a=c  a aplikujme na
abbc  . Potom
abba  což je spor s bodem 1).

28

Závr: Ostrá nerovnost mezi kardinálními ísly je asymetrická, tranzitivní a trichotomická. Proto lze
íci, že relace  definovaná na systému kardinálních ísel K : ={[a , b] K ×K , ab} tento systém kardinálních ísel úpln uspo
ádává. Cantorova vta a její dsledky Vta: Nech A je libovolná množina, nech P
A její potenní množina. Potom platí P
A=2A . Dkaz: Nyní ke každé

BA definujeme jednoznan její charakteristickou funkci  B : A{0 , 1} ,   B
x = 0 pro x B . x A 1 pro x B A A
P
A~{ B , BP
A}={ f : A{0 , 1}}P
A={ f : A{0 ,1}}= {0,1}={0 , 1} =2A .

{

Vta Cantorova: Pro libovolné kardinální íslo a platí a2a . Dkaz: Vždy platí evidentn, že a2a nebo vždy existuje injekce f : a P
A , f
x={x } pro  xa Nyní je t
eba ukázat, že a2a a to sporem. P
ipusme existenci bijekce : a  P
A . Definujeme Y ={xa ; x
x} a tj. Y P
a Y ={xa ; x 
x} P
ipustíme-li,že je bijekce  je surjekce Y musí být obrazem njakého prvku y a , tedy
y =Y . Protože
y A
y Y ! y Y  . yY  y
y =Y spor y Y  y 
y =Y

}

Závr: Množina Y nemže mít svj vzor v zobrazení  není surjekce a tudíž není ani bijekce. Tedy a2a . Dsledek Cantorovy vty: Ke každému systému S libovolných množin vždy existuje kardinální íslo c , které je vtší než kardinální íslo kterékoliv z množin systému S . Dkaz: S , A , a= A , M = S , m=M  . 
m"a AS  c=2 m=P
S =P
M  m m2

}

Dsledek: Neexistuje množina K , která by obsahovala úpln všechna kardinální ísla.

29

6. Množiny kone
né a nekone
né, spo
etné a nespo
etné Na libovolném systému S libovolných množin je vždycky automaticky p
ítomna relace inkluze, která je ásteným uspo
ádáním tohoto systému. Proto vždycky vzhledem k této relaci je možno hovo
it o maximálním prvku. Definice: (Tarskiho) Kone
né a nekone
né množiny Množinu M nazveme konenou množinou, jestliže každý neprázdný systém jejich podmnožin obsahuje maximální prvek. V opaném p
ípad hovo
íme o množin nekonené. Poznámka: Pro dkaz nekonenosti množiny tedy staí najít jeden systém jejich podmnožin, který nemá maximální prvek. Vlastnosti kone
ných množin: Vta 1: Každá podmnožina B konené množiny A je opt konenou množinou. Dkaz: Každý systém podmnožiny množiny B je souasn systém podmnožin množiny A . Ta je konená, musí tedy obsahovat maximální prvek. Vta 2: Nech A je konená množina, nech B vznikne z A p
idáním jednoprvkové množiny B=A
{x }, x je libovolné. Potom množina B je konená množina. Dkaz: 1) x A B=A a tedy i B je konená 2) x  A . Zvolme libovolný systém S B podmnožin množiny B . Chceme ukázat, že obsahuje maximální prvek. Nyní k systému S B zkonstruujeme 

S B={M S B ;  M =C
{x } } C A

 A  A

S ={C A ; C
{x }=M  S B } ( S je systém podmnožin množiny A , A je konená)  S A obsahuje maximální prvek, oznaíme ho C max .  M max =C max
{x } musí být maximální prvek v systému S B  maximální prvek v systému S B

Vta 3: Nech množina A je konená množina a nech existuje njaká surjekce f : A B . Potom i množina B je konená množina. Dkaz: 1) Dkaz intuitivní: U libovolného zobrazení je množina obraz vždy mén i rovno poetná množin vzor. P
i surjektivním zobrazení množiny obraz splyne s celou množinou B . Proto tedy se tato vlastnost vztahuje na tuto množinu. 2) Dkaz formální: Zvolme libovolný systém podmnožin množiny B S B a ukážeme, že obsahuje maximální prvek: S A={x A , f  x =Y S B } . 30

S A je systém podmnožin množiny A . Množina A je konená  S A obsahuje maximální prvek x max . Surjektivita zajišuje, že ke každému Y S B takové x existuje. Potom y max = f  x max musí být maximální prvek v systému S B .

Existence konených množin je zajištna výchozími axiomy, kdežto existenci nekonené množiny je pot
eba axiomaticky zaruit: X. Axiom existence nekone
né množiny Existuje alespo jedna nekonená množina  H   A H  ABB H H

A

B

Poznámka: Existence nekonené množiny nám umožuje definovat množinu  0 (tj. množinu celých nezáporných ísel). Definice: Vezmeme libovolnou nekonenou množinu H . Její potenní množina P  H a K P  H je množina všech kardinálních ísel prvku potenní množiny 0={a K P  H ;   a=A } .

 AH

kone
ná

Poznámka: Z výše uvedené definice množiny  0 je z
ejmé, že množina  0 obsahuje úpln všechna konená kardinální ísla. To plyne z toho, že k libovolné nekonené množin H vždy existuje njaká prázdná podmnožina njaké 1-prvkové, 2-prvkové podmnožiny... a tedy všechna jejich kardinální ísla padnou do množiny  0 . Vta: Množina  0 je nekonená množina. Dkaz: Nejdeme alespo jeden systém jejích podmnožin, který nemá maximální prvek: S={{0}, {0,1} ,{0,1 ,2}, {0,1 ,2 ,3},...} . Poznámka: Protože 0 je nekonená množina, její kardinální íslo bude také nekonené a oznaujeme ho 0 (álef nula).  0= 0 . Definice: Množinu M nazveme nekonenou spoetnou množinou, jestliže je tato ekvivalentní s množinou  0 . (Všechny takovéto množiny mají kardinální íslo 0 ) Definice: Množinu M nazveme spoetnou množinou, jestliže je tato konená množina nebo nekonená spoetná množina. Poznámka: Existence bijekce mezi množinou  0 a další libovolnou nekonenou spoetnou množinou vlastn zpsobuje, že prvky této množiny lze oindexovat (ísly 0,1,2,...) a tudíž tuto množinu lze se
adit do nekonené spoetné posloupnosti. 31

Definice: (Dedekindova) Nekone
né a kone
né množiny Množinu M nazveme nekonenou množinou, jestliže je tato ekvivalentní s njakou svou vlastní pravou podmnožinou. V opaném p
ípad hovo
íme o množin konené. Dedekindova vta: Množina M je nekonená dle Dedekinda  jestliže v sob obsahuje njakou nekonenou spoetnou podmnožinu (nekonenou spoetnou posloupnost)   A0 M  A0 ~0 . A0

Dkaz: 1)  p
edpokládejme, že množina M je nekonená dle Dedekinda   BM B~M  B je také nekonená. B

B je nekonená dle Dedekinda   B1 BB 1~B  B1 je také nekonená B1

B1 je nekonená dle Dedekinda  B 2B1 B2~ B1  B 2 je také nekonená B1

Opakováním p
edchozích krok dostaneme posloupnost M BB1 B2 ...  M B , BB 1 , B1 B2 , ... posloupnost neprázdných rozdíl    x 0 M B ,   x 1  BB 1 , x   x 2 B 1B2 , ... M x 0 M

x1 M

2

 existuje posloupnost A0 ={x0 , x 1 , x 2 ,... , x n , ...}M  A0~ 0   A0M  A0~0 tj. A0 ={x0 , x 1 , x 2 ,...}M

2)

A0

a nyní hledáme množinu BM abychom byli schopni dokázat, že B~M B=M {x 0 } Nyní hledáme bijekci  : M B Existuje bijekce f : A0 {x 1 , x 2 ,...} f  x 0 =x 1 f  x 1 =x 2   x = i  x = x pro x M  A0 f  x pro x A0

{

Vta: Množina M je nekonená dle Dedekinda práv tehdy, když je nekonená dle Tarskiho. Dkaz: 1)

 M je nekonená dle Dedekinda

Dedekindova vta



  A0M A0~0 tj. A0

A0 ={x 0 , x 1 , ... , x n }M . Pro platnost definice Tarskiho staí najít jeden systém podmnožin množiny M , který nemá maximální prvek: S m ={{x 0 }, {x 0 , x 1} ,{x 0 , x1 , x 2} ,...} nebude mít maximální prvek. 2)  M je nekonená dle Tarskiho  systém S podmnožin množiny M , který nemá 



maximální prvek tj. S={I 0 , I 1 , I 2 ,...}  posloupnost I 1 I 0 , I 2 I 1 , I 3I 2 ,...    x 0 I 1I 0 ,   x 1I 2I 1 ,    x 2  I 3 I 2 , ... x 0 M

x 1 M

  A0={x 0 , x1 , x 2 , ... ,} A0 M

x 2 M

Dedekindova vta



M je nekonená dle Dedekinda. 32

Vta: Dsledek Dedekindovy vty 0 je nejmenší nekonené (transfinitní) kardinální íslo. Dkaz: Zvolme libovolnou nekonenou množinu M , m= M 

Dedekindova vta



  A0~ 0 

A0  M

A0=0A0m  0m , kde m je libovolné nekonené kardinální íslo.

33

7. Vlastnosti a p
íklady spoetných a nespoetných množin Vta 1: Každá podmnožina B spo
etné množiny A je opt spo
etná množina. Dkaz: Množina A lze vždy seadit do kone
né
i nekone
né spo
etné posloupnosti. Z ní lze vybrat podmnožinu B , kterou lze opt peindexovat a seadit do spo
etné posloupnosti. Vta 2: Sjednocení systému S spo
etn mnoha spo
etných množin je opt spo
etná množina. Dkaz: Dokážeme pro extrémní pípad nekone
n spo
etn mnoha nekone
ných spo
etných množin: S={A0 , A1 , A2 ,... , An ,...}
S ~0  , 
Ai~ 0 i

A0 ={a
00 , a
01  , a
20 , a
30 , ...}
1
1
1 A1={a
1 0 , a1 , a 2 , a 3 , ...} A2 ={a
02 , a
12 , a
22  , a
32 ,...} .......................................... Ozna
íme-li si M =S Abychom dokázali, že M je nekone
ná spo
etná množina, sta
í najít zpsob, jak tyto prvky
1
0 
1
2 seadit do spo
etné posloupnosti: M ={a
00  , a
0 1 , a0 , a 2 , a 1 , a 0 , ...}
M ~ 0  tedy nekone
ná spo
etná množina.

Vta 3: Kartézský sou
in kone
n mnoha spo
etných množin je opt spo
etná množina. Dkaz: Provedeme pro extrémní pípad nekone
ných spo
etných množin (a to matematickou indukcí) Ai ~0 pro každé i . 1)
A1× A2~ 0 dokážeme 2) Pedpokládejme, že platí pro n množin



A1× A2 ×A3 ×A4 ×... An ~ 0 3) Dokážeme, že platí pro n1:
B×An1 ~0 Protože dkaz 3) z 2) je opt pro dv množiny B×An1 , sta
í dokázat 1). add 1) a) pes pedchozí vtu A1× A2= 
A1×{ y } 
A1× A2~0  y A2

~ A1~0

nebo b) kartézský sou
in A1 × A2 celý vyjádíme a množinu uspoádaných dvojic opt seadíme po vedlejších diagonálách do spo
etné posloupnosti.
1
1 A1={a
1 0 , a1 , a 2 ,...} A2 ={a
02 , a
12 , a
22  , ...}
2
1
2
1
2 A1× A2={ [a
1 0 , a 0 ] ,[a 1 , a 0 ] ,[a 2 , a0 ] ,...
2
1
2 [a
01 , a
21 ] ,[a
1 1 , a 1 ] ,[a 2 , a1 ] ,... ......................................................

Poznámka: Píklady nekone
ných spo
etných množin:  0 , , množina
ísel sudých, lichých,  . 34

Dkaz:

{

}

a = c= , kde a , b b ={[a , b ] ×}, ~~0  množina ~0 (nekone
ná spo
etná). Nyní se naskýtá otázka, zda vbec existují njaké nespo
etné množiny. Kladnou odpov na ni zaru
uje existence poten
ní množiny a Cantorova vta. Vta 1: Poten
ní množina množiny 0 je nespo
etná množina. Dkaz:

 0 = 0 , P
0  =2 . Z Cantorovy vty  0 2  poten
ní množina má vtší kardinální
íslo P
 0   0 a tudíž je nespo
etná. 0

0

Vta 2: Množina všech zobrazení f z množiny 0 do dvouprvkové množiny {0,1}, f : 0 {0,1} je nespo
etná množina. Dkaz: f : 0 {0,1} =  0

 0

= {0,1}

{0,1 }

=2  0 0

Vta 3: Množina U všech nekone
ných spo
etných posloupností z nul a jedni
ek je nespo
etná množina. Dkaz: 1) plyne bezprostedn z pedchozí vty: Každému zobrazení odpovídá vzájemn jednozna
n práv jedna posloupnost. 2) Sporem
i  0 Pedpokládejme, že U ={x 0 , x 1 , x 2 ,...} , xi ={a
0i , a
i1  , ...} , kde a j = 1
0 
0
0
0 x 0={a 0 , a 1 , a 2 , a3 , ...}
1
1
1 x 1={a
1 0 , a1 , a 2 , a3 , ...} 
2
2 x 2={a
02 , a
2 1 , a 2 , a 3 ,...} ........................................ Nyní ukážeme, že ur
it najdeme posloupnost nul a jedni
ek, která v našem schématu není. y={b0 , b1 , b 2 , ... , b n , ...} , bi= 0 1
0  b0 =1a 0 b1=1a
1 1 b 2=1a
2 2  Tím jsme vyvrátili, že množina U je seaditelná a tedy množina U je nespo
etnou množinou.

{

{

Vta: Spojitý interval 0,1 reálné osy je nespo
etná množina.

35

Dkaz: Budeme provádt sporem. Pedpokládejme, že J 0 = 0,1={y 0 , y 1 , y 2 ,... , y n , ...} . Ukážeme, že najdeme prvek, který do této posloupnosti není zaazen. 1 1 2 2 J 0 rozdlíme na tetiny. Dostaneme 0, , , , ,1 . 3 3 3 3 1 y 0  J 1 délka J 1= .Vybereme tetinu,kam nepadne y 1 ,ozna
íme J 2 a zase ji roztetíme. 3 1 y 1 J 2 délka J 2= . 9 1 y 2  J 3 délka J 3= . 27 Tímto postupem dostaneme posloupnost vložených interval J 0J 1J 2... Délka J n  0 pro n  .   J i={ y} . y padne do všech interval, je rzný od y i . i=1 y je nekone
ným prnikem dlených interval.

   

Pomocná vta: Nech A je nespo
etná množina a nech B je její spo
etná podmnožina ( BA ). Potom rozdíl A  B je opt nespo
etná a navíc platí, že
A B ~ A . Dkaz 1) A  B je nespo
etná Sporem, pedpokládáme, že A  B je spo
etná množina, B je spo
etná,
A B  B=
A B B= A

A B B je spo
etná, ale A je nespo
etná, což je spor. 2)
A B ~ A , ešíme pes Dedekindovu vtu


A B  je nespo
etná 
A  B je nekone
ná 



B0
A  B


B 0~0


B B0 ~
B 0
CBB B0 C  0~
A B

A

Poznámka: Vzhledem k tomu, že spojitý interval 0,1 je nespo
etná množina platí, že i celá reálná osa musí být nespo
etná množina. Mohutnost reálné osy zna
íme gotické c a nazveme mohutností kontinua.  = (Nedailo se mi ho najít, tak jsem ho nahradil tímto znakem) Poznámka: Nyní ukážeme, že platí následující
tyi vztahy pro intervaly reálné osy a odtud nám vyplyne závr, že libovolný uzavený
i otevený spojitý interval reálné osy má tutéž mohutnost, tj. mohutnost kontinua.   1) ~  , 2 2 2)
a , b~
0,1 kde a ,b 3) a , b~ 0,1 kde a ,b 4)  0,1~
0,1






36

Dkaz: 1)




arctan x :   

  , 2 2



xa ba xa f
x :  a , b  0,1 kde f
x = 3) ba 0,1{0,1}  0,1 4) Pes pomocnou vtu je nespo
etná množina a platí
0,1 = . 2)

f
x :
a , b
0,1 kde f
x =

AB

A

B

Poznámka: Nyní zbývá ukázat, jaký je vztah mezi  a mohutností 0 . Vta: 2 = . 0

Dkaz: U je množina všech spo
etných posloupností z nul a jedni
ek. U =2  0 ,1  0,1  = U =V W . W ... obsahuje posloupnost s jedni
kami od ur
itého místa po
ínaje W je nekone
n spo
etná. V ... obsahuje posloupnosti s nekone
n mnoha nulami.  z pomocné vty U = V =2  c i x= , c i 0 posloupnost koeficientu c i obsahující nekone
n Z teorie
ísel: x  0,1  i 1 i =0 2 mnoho nul.   0,1  ~V ~U a platí =  0,1  = V = U =2 . 0

0

{

0

Poznámka: Pro nekone
ná kardinální
ísla 0 a  platí následující vztahy. 1) 0 = 0  0=n! 0 = 0! 0 = n0 , kde n"2 , n0 2) ==n = 0 ==n= 3) 2 =n =

0 = 4) 2 =n = 0 = 0

0

0

0

0

Dkaz: 2) Ur
it platí ##n # 0 ## n# . Sta
í dokázat, že na za
átku i na konci máme totéž
íslo.  =
2  =2 =2 = 3) Ur
it platí 2 #n #

0 # . Sta
í dokázat, že na za
átku i na konci máme totéž
íslo  =
2  =2 4) Ur
it platí 2 #n # 0 # . Sta
í dokázat, že na za
átku i na konci máme totéž
íslo
2  =2  =2  0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

37

Poznámka: Poznali jsme nekone
ná kardinální
ísla 0 a  . Ptáme se, zda existují další nekone
ná kardinální
ísla. Odpov je kladná. Pes existenci poten
ní množiny a Cantorovu vtu plyne, že existuje nekone
n mnoho nekone
ných kardinálních
ísel. 0  1  2 . 2

0

2



2

1

Skok se odehrává pes poten
ní množinu pedešlé množiny. Naskýtá se ješt další otázka, zda existují njaká jiná nekone
ná kardinální
ísla mezi skoky pes poten
ní množinu. Pedpokládá se záporná odpov, jejíž formulace je známá jako zobecnná hypotéza kontinua, ale tato doposud nebyla ani potvrzena ani vyvrácena.

38

8. Peanuv model aritmetiky množiny
0 (celých nezáporných
ísel) Vta: H nekone
ná množina, P  H  , K P  H  .
0={a K P  H  ,   a=A} A kone
ná H

~ = ... ozna
íme 0 {}={0} ... ozna
íme 1 { , {}}={0,1} ... ozna
íme 2 .......................... n 1=n{n } n 1 íkáme následník prvku n , ozna
ujeme n=n 1 (následník funkce) Vta (Peanovi vlastnosti): 1) 0
0 2) n
0 n
0 (padne prvek, padne i následník) 3) n
0  n 0 4) n , m
0 n= m  n=m 5) Princip matematické indukce nech U 
0 a nech platí a) 0U b) nU n 1U pak U =
0 . Množina U se nazývá induktivní množina. Dkaz: 1) 
 je kone
ná 
0 0
0 kone
ná

2)

n
0

3)

n
0

4)

n
0 m
0 =



 n= A    n= A{x} A{x }H   n
0



 n= A    n= A{x}A{x }   A{x}  n 0



 n= A    n= A{x}



 m=B   m=B{ y}

A kone
ná H Akone
ná H A kone
ná H B kone
ná H

x H  A x H  A x H  A

y= H  B

  n= m  A{x }~ B{y }  bijekce f  A{x } B{ y} Tch bijekcí mže existovat celá ada a my z nich vybereme práv tu, pro kterou platí f  x = y  f  A= B  A~B A= Bm=n . 5) Sporem. Pedpoklad platnosti U 
0 a) 0U b) nU n 1U a sou
asn neplatí závr U 
0 neboli U
0
0U    p
0U    p= X  pU  p

X kone
ná H

S={Y  X ,YU } a X je kone
ná množina S obsahuje maximální prvek,ozna
íme ho Y max a platí že n=Y max a platí nU Pes b) platí nU n 1U  Y max { y }=n 1n 1U  y X Y max

Y max{y }S což je spor s pedpokladem, že Y max byl maximální prvek S Z toho tedy plyne, že systém S by neml maximální prvek, což je ve sporu s tím, že množina X je kone
ná žádná taková kone
ná množina X nemže existovat a tedy nemže existovat ani její kardinální
íslo p , kde p 
0U . Odtud tedy plyne, že
0U = a tedy U splyne s
0 . U =
0 . Vta: Následníková funkce :
0 
kde
=
0  {0} je bijekce. 39

Dkaz: je ur
it injekce nebo to plyne z kontrapozice Peanovi 4), tj. m n   m n . Sta
í tedy ukázat, že je surjekce, tj. že platí 
0 =
=
0  {0 } tj. sta
í ukázat, že
0= 
0 {0} . To dokážeme pes induktivní množinu U , kde U = 
0 {0} a když dokážeme a) 0U Plyne pímo z definice U b) nU n 1U definiceU nU n
0 n 
0 n uU což je n 1U . Z platnosti a) a b) plyne, že U =
0 neboli
0 = 
0 {0} . Vta: Na celé množin
0 platí n n . Dkaz: 
ná H , potom n= A{x } , kde x  H A . Pedpokládejme, že n= A , A kone Mžeme íci, že je vždy n n nebo vždy existuje injekce f : A A{x } , sta
í zvolit identitu kde f  x =x pro  x A . Nyní dokážeme, že n n na celé
0 . Pes U ={n
0 , n  n} . Sta
í tedy dokázat a) 0U 0 1 0U b) nU n 1U P4 nU n n n 1 n 1n 1U  U =
0 neboli n v  n platí na celé množin. Poznámka: Z této vty je zejmé, že každý prvek množiny
0 má svého bezprostedního následníka a také každý prvek mimo nulu má svého bezprostedního pedchdce, tj. množina
0 je úpln uspoádaná relací  , kde ={[m , n ]
0×
0 , mn} Sou
et, sou
in a mocnina na množin
0 Množina
0 je uzavená vzhledem k sou
tu, sou
inu a mocnin, tj. platí: 1) a ,b
0  a b
0  2) a ,b
0  ab
0  3) a ,b
0  ab 
0 Dkaz: 1) Pes induktivní množinu U ={b
0 ;  a b 
0 } a
0

sta
í dokázat a)

0U  a 0=a 
0  0 U a
0

b)

bU b 1U P2 bU   a b
0    a b 1
0 a
0

a 
0

   a b 1
0  b 1U a 
0

40

2) Pes induktivní množinu U ={b
0 ;  ab 
0 } a
0

sta
í dokázat a)

0U  a0=0
0  0U a
0

b)

bU b 1U 1 bU   ab
0   ab a
0   a b 1
0  a
0

a
0

a
0

b 1U  U =
0 3) Pes induktivní množinu b U ={b
0 ;  a 
0 } a
0

sta
í dokázat a)

0U 0  a =1
0  0U a
0

b) bU b 1U 2 bU   a b 
0  a ba
0   a b 1
0  b 1U  a
0

a 
0

a 
0

U =
0 Pomocná vta: Nech A , B jsou kone
né množiny a nech A B . Potom pro jejich kardinální
ísla platí  A B . Dkaz: Vždy platí, že  A B , protože vždy existuje injekce f : A B , sta
í identita f  x =x pro  x A . Je teba dokázat, že  A  B ,což dokážeme sporem.  A~ B AB . Pipusme  A= BAB  A, B jsou nekone
né spor

Vta: Pro libovolná kardinální
ísla a ,b , c 
0 dále platí: 1) ab a cb c  2) ab acbc pro c 0 3) ab a c bc  pro c 0 Dkaz: 1) Mjme ab , a= A , b=B . Potom lze pedpokládat A B , AC= , BC = . ab ... A B  AC BC   AC BC  a cb c  2) c  ab ...  AB   A×C  B×C   A×B B×C acbc  3) c  ab ...  AB  C A  C B C AC B a c b c 

    



Vta (O existenci rozdílového prvku): Pro libovolná kardinální
ísla a ,b
0 platí. ab  b=a c ( c - rozdílový prvek). c
0

41

Dkaz: a= A , b= B ab ... A B   B= AC C A=  b=a c C= B A 

c=C

kone
ná



 b=a c   b= Ba= Ac=C AC = B~AC 

c
0

B , A ,C  kone
né

 bijekce f : AC  B f / A : A B je injekce  A B ab . restrikce

Metody matematické indukce Vta (Oby
ejná metoda matematické indukce): Nech n je libovolná formule teorie množin volné promnné n definované na
0 . Nech dále platí: I.) platí 0 II.) platnost  n  n 1 pro  n
0 Potom  n platí na celé množin
0 . Dkaz: U ={n
0 , platí n} Je teba dokázat, že 1) 0U z I.) plyne platnost 1) 2) nU n 1U z II.) plyne platnost 2) U =
0  neboli  n platí na celé množin
0 . Vta (Zobecnná metoda matematické indukce): Nech m je libovolní prvek množiny
0 , N m ={n
0 , nm} a n je libovolná formule teorie množin volné promnné n definovaná na N m . Nech dále platí m I) II)  n   n 1 pro  n
m Potom  n platí na celé množin
m . Dkaz: U ={0,1,2 , ... , m1}{n
m , pro které  n platí} 1) 0U Z definice U 0U . 2) nU n 1U . a) n{0,1 ,... , m2} z definice U plyne platnost 2) b) n=m1 z I) plyne platnost 2) c) nm z II) plyne platnost 2) U =
0 neboli n platí na celé
m . Poznámka: Krom metod matematické indukce se používá i rekurentní zpsob, jak definovat njaký výraz na množin
0 a to tak, že ho definujeme pro nulu a potom stanovíme rekurentní pedpis, jak z definice výrazu pro n dostat definice výrazu pro n 1 .

42

Píklad: Definice faktoriálu 1) 0 !=1 2) n 1 != n 1n ! Píklad: Skládání funkcí 1) f 0 ...identita 2) f n 1 = f  n ° f Vta (Definice matematickou indukcí): Nech A je libovolná neprázdná množina a nech a je její libovolný prvek a  A . Nech :
0 ×A A . Potom existuje práv jedna posloupnost prvk {x n }n=0 z množiny A , jestliže platí: 1) x 0=a 2) x n 1= [n , x n ] Neboli posloupnost prvk z množiny A je za tchto okolností ur
ena jednozna
n. Dkaz: Provedeme matematickou indukcí. 1) Dokážeme, že je ur
eno x 0 Ur
enost x 0 plyne z jednozna
nosti volby a . 2) Pedpokládáme ur
enost x n 3) Dokážeme ur
enost x n 1 Ur
enost x n 1 plyne: ( z ur
enosti x n ur
enost [n , x n ] ur
enost [ n , x n ] ur
enost x n 1 ) jednozna
ná ur
enost x n pro n
0 . Píklad: A={a , b} 1) x 0=a 2) x n 1= [ n , x n ] , [ n , a ]=b pro  n
0 [ n , b]=a pro  n
0 x 0=a x 1= [0, x 0 ]=[0, a ]=b x 2= [ 1, x 1 ]=[ 1,b ]=a x 3= [2, x 2 ]= [2, a ]=b ..........................................

43

9. Podobnost množin, dob
e uspo
ádané množiny a jejich vlastnosti Definice: Nech
A ,
A , B ,
B (kde
je relace alespo ásteného uspoádání) a nech
f : A B . Potom toto zobrazení nazveme podobným(izotonním), jestliže je toto injektivní a zachovávající uspoádání, tj. když platí

  x
A x'  f  x
B f  x '  . '

x, x A

Definice: Nech
A , B jsou úpln uspoádané množiny píslušnými relacemi. Potom ekneme, že množina A je podobná množin B (znaíme A B ), jestliže existuje podobná bijekce f : A B . Poznámka: Nyní ukážeme, že podobnost množin je reflexivní, symetrická a tranzitivní a lze tedy hovoit o vzájemn podobných množinách. Tj. platí: 1) A A 2) A B  B A 3)  A B BC  AC  Dkaz: 1) Vždy existuje bijekce f : A A 2) Jestliže  A B  podobná bijekce f : A B  bijekce f ' : B  A , ale je teba dokázat, že je podobná a to sporem. Pipus
me, že by bylo 1 1  y
B y ' f 1  y
A f 1  y '   y
B y'   f  f 1  y
B f  f 1  y '  x A

3)

'

x A

 AB  BC   podobná bijekce f : A B  podobná bijekce g : B C

 bijekce = f ° g : A C a je teba ukázat, že je podobná    x
A x '  f  x 
B f  x '    y
B y '  g  y 
B g  y '  '

'

x , x A

'

y ,y B '

  x
A x  g  f  x 
C g  f  x    x
A x'   x 
C   x '  '

x, x A

'

x ,x A

  x  je podobná bijekce. Poznámka: Podobnost množin je tedy reflexivní, symetrická a tranzitivní na libovolném systému úpln uspoádaných množin a zpsobuje rozklad tohoto systému na tídy vzájemn podobných množin, kde lze potom hovoit o množinách téhož ordinálního typu. Chceme-li tmto množinám piazovat tzv. ordinální ísla, potebujeme tzv. dobe uspoádané množiny. Definice: Uspoádanou množinu A nazveme dobe uspoádanou množinou, jestliže každá její neprázdná podmnožina obsahuje první prvek(vzhledem k relaci uspoádání). Poznámka: Zjevn platí, že dobe uspoádaná množina je souasn úpln uspoádaná, takže všechny prvky jsou mezi sebou srovnatelné. P
íklad:  0 je dobe uspoádanou množinou (DUM) {0,1,2 ,3 ,...}

44

Naopak  není dobe uspoádanou množinou, {... , 2 , 1 , 0 , 1 , 2 ,...} . Sama nemá první prvek, ale lze ji násilím dobe uspoádat, jednoduše jí odsekneme zleva. Definice: Nech
A je dobe uspoádaná množina, a je libovolný prvek množiny A . Potom množinu Aa definovanou pedpisem Aa ={x A , x
a} nazveme úsekem množiny A píslušným prvku a . Poznámka: Zjevn platí a  Aa . Definice: Nech
A je dobe uspoádaná množina a nech
I A . Potom tuto podmnožinu nazveme primitivním intervalem množiny A , jestliže spolu s každým svým prvkem x obsahuje souasn i všechna y z množiny A , která pedchází x . Poznámka: Zjevn každý úsek dobe uspoádané množiny je souasn jejím primitivním intervalem, naopak to však neplatí, což ukazuje následující vta. Vta: Nech
A je dobe uspoádaná množina a nech
I je její primitivní interval. Potom platí: I =A I = Aa pro nkteré a A . (Bu splyne s celou množinou A nebo s nkterým jejím úsekem) Dkaz: Nech
A je dobe uspoádanou množinou, I je vlastní íslo A .  I A tj. I A A I   A I  A A je DUM A I obsahuje první prvek, ozname ho a .    xI xA I x
a x  Aa  I = Aa . x A

Vlastnosti dob
e uspo
ádaných množin Vta: Každá podmnožina B dobe uspoádané množiny A je opt dobe uspoádanou množinou. Dkaz: Každá podmnožina množiny B je souasn podmnožinou množiny A . Je-li neprázdná, musí obsahovat první prvek. Vta: Nech
A je dobe uspoádaná množina a nech
B je množina všech jejich úsek. Potom i množina B je dobe uspoádaná relací inkluze a navíc platí B A . Dkaz: A={a0 , a 1 , a 2 , ...} a nech
platí a 0
a1
a 2
... Aa ={x A , x
a0 }= Aa ={x A , x
a1 }={a 0 } Aa ={x A , x
a2 }={a 0 , a1 } f a i =Aa  i 0  podobná bijekce f : A B  B A B je dobe uspoádaná množina. 0

1

2

i

45

Vta: Nech
A je dobe uspoádaná množina a nech
f je podobné zobrazení f : A A . Potom nikdy nemže nastat f  x 
x pro x  A . Dkaz: Provedeme ho sporem. Pedpokládejme, že  B={x  A , f  x 
A x} A=DUM  B musí obsahovat první prvek b . f b  f  a
a a
b Pak bB  f b 
b . Z podobnosti f  f  a
a A

a

 a B a
b b je první prvek což je spor  B by nemla první prvek  B= . Tedy f  x x pro  x A . Vta: Nech
A , B jsou dobe uspoádané množiny. Existuje-li podobná bijekce f : A B je tato pouze jediná. Dkaz: Intuitivn:

Formáln: Provedeme ho pomocí sporu.

{

f : A B  podobné zobrazení h= f ° g 1 : A A ' 1 g : A B  podobné zobrazení h =g ° f : A A  h  x x  x A g 1  f  xx  x  A g  g 1  f  xg  x  x  A f  x g  x   x  A  h'  x x  x A f 1  g  xx  x  A f  f 1  g  x  f  x  x A g  x f  x   x  A  f  x=g  x  x A

Pedpokládejme,že  2 podobné bijekce

Vta: (Základní vta o dob
e uspo
ádaných množinách) Nech
A , B jsou dobe uspoádané množiny, potom platí práv jedná z možností: 1) A B 2) A Bb pro nkteré bB 3) B Aa pro nkteré a A (tj. bu jsou tyto množiny vzájemn podobné nebo nkterá z nich je podobná nkterému úseku množiny druhé) Dkaz: X ={x A ,   A x B y } y B

Y ={ y B ,   A x B y } x A

}

 X Y

X =A Y =B 1) X =A Y =B b 2) V souladu s tvrzením vty X =Aa Y = B 3) X =Aa Y = Bb Není v souladu s tvrzením vty – musíme tvrzení vylouit 4) a  X = Aa  a Aa , což je spor s definicí úseku kde a Aa . 46

Princip transfinitní indukce Vta: Nech
A je dobe uspoádaná množina a nech
a 0 je její první prvek. Nech
  x je libovolná formule teorie množin volné promnné x definovaná na A a nech
platí: 1)  a 0 2)

  x pro   x
y  platnost  x pro  taková y A x A

Potom   x platí na celém A . Dkaz: Budeme ho provádt sporem. Pedpokládejme, že platí 1) a 2). Pedpokládejme množinu B={y A ,¬ y } A=DUM  B 2 obsahuje první prvek y 0  ¬  y 0  ¬  x pro  x A , x
y 0   x
y 0 x  B , což je spor s pedpokladem, že y 0 je první prvek  B by neml první prvek  B= . Vta: (Druhá metoda matematické indukce) Nech
n je libovolná formule teorie množin volné n definovaná na  0=DUM a nech
platí: 1) platí 0 2) platnost m pro

  m
n platnost  n pro  n0 .

m 0

Potom  n platí na celém 0 . P
íklad: Pes druhou metodu matematické indukce dokažte, že každé íslo z množiny  je možno vyjádit ve tvaru souinu dvou i více prvoísel, pakliže jedniku také zaadíme mezi prvoísla. ešení: 1) Dokážeme pro 1 1=11 , tedy platí 2) Pedpokládáme platnost pro m
n 3) Dokážeme platnost pro n Zvolme libovolné n1 , n 0 n je prvoíslo  n=1n n není prvoíslo  n=m1m2 , m1 , m2
n Nech
m1= p1p2...pr , m2 =q1q2...q s , kde p 1 , p 2 , ... , pr , q 1 , q 2 , ... , q s jsou prvoísla, pak n= p 1p 2...prq 1q 2...q s .

{

47

10. Ordinální
ísla Podobnost dob
e uspo
ádaných množin na libovolném systému takovýchto množin je reflexivní, symetrická a tranzitivní a tudíž zpsobuje rozklad tohoto systému na t
ídy vzájemn podobných dob
e uspo
ádaných množin a z každé této t
ídy je potom možno opt vybrat reprezentanta, kterého nazveme ordinální íslo. Existence ordinálního ísla je obecn opt t
eba zaruit axiomaticky. XI. Axiom existence ordinálního
ísla Ke každé dob
e uspo
ádané množin A existuje množina ord
A (zvaná ordinální íslo), dob
e uspo
ádaná relací inkluze tak, že je podobná s pvodní množinou A a souasn pro dv vzájemn podobné dob
e uspo
ádané množiny platí, že jejich ordinální ísla se rovnají.  
Aord
A  

A B
ord
A=ord
B . A=DUM ord
A= DUM relací inkluze A=DUM B= DUM Poznámka: Ordinální ísla budeme znait =ord
A , =ord
B , ... Nerovnosti mezi ordinálními
ísly Definice: Nech  a jsou libovolná ordinální ísla. Potom
ekneme, že 


 b  (tj. že

b

 je podobné nkterému úseku množiny ). Poznámka: Nyní si ukážeme, že libovolná množina M ordinálních ísel je úpln uspo
ádaná relací , kde ={[ , ] M ×M , } a souasn i dob
e uspo
ádaná touto relací a tudíž sama mže mít svoje ordinální íslo. Vta: Libovolná množina M ordinálních ísel je výše uvedenou relací úpln uspo
ádanou množinou. Dkaz: Je t
eba dokázat, že relace je 1) asymetrická Sporem. P
edpokládejme, že
  

 b  
a  . Spor se základní a 

b

vtou o dob
e uspo
ádaných množinách. 2) tranzitivní Pro všechna  , , taková, že
 

 
 b  
 c  b

c


 podobná bijekce f :  b  podobná bijekce g :  c   
 : f ° g / :  je podobná bijekce 
 c 


 c  c c

c  c  c

b



3) trichotomická základní v
ta o DUM
  

 b

a 
   b

a 

48

Poznámka: Pro dkaz dobrého uspo
ádání ukážeme platnost pomocné vty. Pomocná vta: Nech  je libovolné ordinální íslo, nech B je množina všech jeho úsek a nech W
 je množina všech ordinálních ísel tchto úsek. Potom platí, že W
=DUM a navíc platí, že W
 . Dkaz: =DUM  ={a 0 , a 1 , a 2 ,...} a 0 a =0=ord
 a = a 1  a ={a 0 }1=ord
a =ord
{a 0 } a 2  a ={a 0 , a 1}2=ord
a =ord
{a 0 , a1 } ............................................................................. 0

0

1

1

2

2

Poznámka: Zjevn bude dále platit, že množina W
 v sob obsahuje všechna ordinální ísla, která jsou menší než  . Vta: Libovolná množina M ordinálních ísel je výše uvedenou relací dob
e uspo
ádanou množinou. Dkaz: Zvolme libovolnou podmnožinu M  množiny M a ukážeme, že obsahuje první prvek vzhledem k výše uvedené relaci .   1.  je pvní prvek v M M M , zvolme libovolné M 2.  není první prvek v M  2) K tomu  uvažujme p
íslušnou množinu W
 , která evidentn obsahuje všechna  i menší než to 
M W
W
=DUM  prnik obsahuje první prvek   musí být souasn i první prvek v tom M  .

{

Dsledek: Neexistuje množina M , která by obsahovala úpln všechna ordinální ísla. Dkaz: Sporem. P
edpokládejme, že M obsahuje všechna ordinální ísla.
M =DUM  
=ord
M  M W
  M W
  

 Podobná bijekce f : M W
M  f
=i W
 ,i  a souasn musí platit    f
   . f
 . Kdyby  M  f
 =i    spor s pedchozí v
tou oDUM

Odsud tedy plyne, že ordinální íslo množiny M už do této množiny M nemže pat
it, tj. množina M neobsahuje všechna ordinální ísla.

49

Konstrukce ordinálních
ísel Axiom XI. nám zajišuje existenci ordinálního ísla, nic však ne
íká o tom, jak ordinální ísla obecn vypadají. Pro praktické použití je však rozumné p
ijmout njakou konstrukci ordinálních ísel. My nyní p
ijmeme tu konstrukci, která se opírá o definici ordinálního ísla v Cantorov intuitivní teorii. Definice: Libovolnou, dob
e uspo
ádanou množinu nazveme ordinálním íslem, jestliže každý její prvek splývá s jemu p
íslušným úsekem. Odtud plyne jednoznaná konstrukce: 1) Nula prvkové 0= , protože   ord
= ... oznaíme 0 2) Jednoprvkové 1={a 0 } 1 B  a0 1 ={x  1 , x a 0}=  a 0 =  1 ={}={0} ... oznaíme 1 3) Dvouprvkové 2 B 2 ={x 2 , x a 0 }= a 0= 2 ={ ,{}}={0 , 1} ... oznaíme 2 a0 2 ={x 2 , x a 1 }={a0 }{} a0

a0

a1

}

Z této konstrukce vyplývá, že konená ordinální ísla splývají s d
íve uvedenou konstrukcí konených kardinálních ísel a obecn tedy bude platit, že n1= n {n } . Poznámka: Z výše uvedené konstrukce ordinálních ísel plyne, že pro libovolná ordinální ísla jsou následující ty
i vztahy ekvivalentní: 1)  2)  3)  4) = b pro nkteré b Aritmetika ordinálních
ísel Budeme definovat souet a souin ordinálních ísel, bylo by možno uvažovat i p
irozenou mocninu na základ kartézského souinu více množin, ale kvli komplikovanému uspo
ádání se tato mocnina nezavádí. Pomocná vta: Nech A , B=DUM , A B= a dále nech C= AB je uspo
ádaná tak, že nap
ed za
adíme prvky z množiny A p
íslušné relaci a potom za n prvky množiny B p
íslušné relaci. Potom množina C je takto dob
e uspo
ádanou množinou.

50

Dkaz: Zvolme libovolné

{

1. M A= DUM  M obsahuje první prvek ozn. a  M C =A B 2. M B=DUM  M obsahuje první prvek ozn. b 3. M A B
M =M 1M 2 , kde M 1M 2 =M 1 Aa také M 2 B  M 1 obsahuje první prvek a , který souasn musí být i první prvek v M . Definice: Nech A , B=DUM , A B= a nech =ord
A , =ord
B . Potom soutem  =ord
AB , p
iemž p
edpokládáme, že sjednocení je uspo
ádané dle výše uvedené vty. Poznámka: Definice není závislá na volb p
íslušných množin a ani požadovaná disjunktnost tchto množin není na závadu, protože bychom vždycky našly jiné podobné množiny, AC , BD takové, že C D= a souasn =ord
C  , =ord
D . Poznámka: Souet ordinálních ísel je obecn asociativní, ale není obecn komutativní, komutativita platí pouze v p
ípad konených ordinálních ísel. Píklad: Dokažte, že 2=2 když 2=ord
A kde A={x , y }, =ord
0  , 0 ={0,1 ,2 ,...} p
es vztah podobnosti 1 A0 0  0 A . A0={x , y ,0 ,1,2 , ...}  podobná bijekce f : A 0  0  0={0 ,1 , 2 ,3 , ... }  0 A={0,1 ,2 ,... , x , y } zde se nikdy na prvky x , y nedostaneme  0={0 ,1 , 2 ,3 , ... }  neexistuje podobná bijekce g : 0 A 0

}

Poznámka: Z výše uvedeného textu plyne platnost následujících vztah pro libovolná ordinální ísla  , , : 1)   pro 0 2)
 


  3)
 
    4)
 
   Pomocná vta: Nech A , B jsou dob
e uspo
ádané množiny a nech A× B je jejich kartézský souin, který je tzv. lexikograficky uspo
ádán, tj. platí  
[ x , y ] [ x ' , y ' ]

x x '  y = y ' 
y B y '  . [ x , y] A×B [ x ' , y' ]A×B

Potom kartézský souin je touto relací dob
e uspo
ádanou množinou. Dkaz: Zvolme libovolnou M  A×B a ukážeme, že obsahuje první prvek. M y ={ y B , 
[ x , y ] M }B=DUM  M y obsahuje první prvek, ozname ho y 0 . x A M x ={x A ,[ x , y 0 ] M }A= DUM  M x obsahuje první prvek, ozname ho x 0 . [ x 0 , y 0 ] musí být první prvek v množin M . 51

Píklad na lexikografické uspoádání kartézského sou
inu: A={x , y} , B={a , b , c} A× B={[x , a ], [ y , a] ,[ x ,b ], [ y , b] ,[ x , c ], [ y , c]} . Definice: Nech A , B jsou dob
e uspo
ádané množiny. Nech A× B jejich kartézský souin, který je lexikograficky uspo
ádán a nech =ord
A , =ord
B . Potom souinem  =ord
A×B . Poznámka: Platnost definice evidentn nezávisí na volb p
íslušných množin. Násobení ordinálních ísel je obecn asociativní, není však obecn komutativní, komutativita platí obecn pouze v p
ípad konených ordinálních ísel. Píklad: 2 = 2 kde 2=ord
A , A={x , y }, =ord
 0  , 0={0,1 ,2 ,...} 1 A×0 0  0 × A A×0={[ x ,0] ,[ y ,0] ,[ x ,1], [ y ,1], [x ,2] ,[ y ,2] ,...}  0={ 0 , 1 , 2 , 3 , 4 , 5 , ...}  podobná bijekce f : A× 0  0 0×A={[0, x] ,[1, x ], [2 , x ] ,[3 , x ] , ... ,[0 , y ], [1 , y ] ,[2, y ], ...}  neexistuje bijekce g : 0 ×A 0 . Z toho vyplývají následující vztahy pro násobení ordinálních ísel: 1)  0=0  2)  1=1   =...  3) krát

4) 5) 6) 7)

  , 0 , 1 , 0
 



 
  
 
  , 0

Poznámka: Z výše uvedeného je zjevné, že každé ordinální íslo  a to i nekonené má svého bezprost
edního následovníka 1 , nemusí však mít svého bezprost
edního p
edchdce. Ta která ho mají nazýváme nelimitní ordinální ísla a ta která ho nemají nazýváme limitní ordinální ísla. Limitní: 0,  ,  2 ,  n , ... Nelimitní: 1 , n0 , 1 ,  23 , ... Vztah mezi ordinálními a kardinálními
ísly Z výše uvedené konstrukce ordinálních ísel je z
ejmé, že konená ordinální ísla splývají s konenými kardinálními ísly, bereme-li v úvahu jejich p
irozené uspo
ádání. U nekonených ordinálních ísel existuje nekonen mnoho tch, která jsou mezi sebou rzná (nejsou si podobná) a p
itom jsou mezi sebou ekvivalentní. Nejmenší z tchto položíme do rovnosti s p
íslušným kardinálním íslem =!0 . P
itom však nám vadí, že ordinální ísla p
i
azujeme pouze dob
e uspo
ádaným množinám. V tom nám ale pomáhá Zermelova vta o dobrém uspo
ádání. 52

Vta Zermelova o dobrém uspoádání: Každou libovolnou množinu (i kontinuální povahy) lze dob
e uspo
ádat. Princip dkazu: Opírá se o Zermelovu vtu o výbrové funkci. Dkaz: Nech S je libovolný systém neprázdných množin  f : S   S , f
A=x A pro  A S . Máme libovolnou množinu M , S=P
M {} . M S  
f
M = x 0 x 0 M

M 1=M {x 0 }, M 1 S  
f
M 1 =x 1 x 1M 1

M 2=M 1{x 1 }, M 2 S  
f
M 2= x 2 x 2 M 2

.....................................................................

53