VAROV ´AN´I

(1)

VAROV ´AN´I

Tento studijn´ı materiál je urˇcen posluchaˇc˚um úvodn´ıch kurz˚u teorie mnoˇzin, jako doplnˇek k poznámkám z pˇrednáˇsek. Aˇckoli obˇcas pˇresahuje rámec prob´ırané látky, neklade si za c´ıl podat celistvý výklad dané problematiky. Jsem si vˇedom toho, ˇze ˇradu m´ıst by bylo uˇziteˇcné doplnit vhodnými pˇr´ıklady ˇci dokonce obrázky; na to mi zat´ım nezbyly s´ıly ani ˇcas.

Jelikoˇz jde o pracovn´ı verzi v ranném stádiu vývoje, vyskytuje se zde nejsp´ıˇs nemalé mnoˇzstv´ı chyb, jakoˇz i zákeˇrných pˇreklep˚u. ˇCtenáˇre proto pros´ım aby text uˇz´ıval s rozmyslem a chyby a nedostatky, jeˇz pˇr´ıpadnˇe nalezne, mi zaslal elektronickou poˇstou na adresupajas@ufal.mff.cuni.cz.

Petr Pajas

(2)

Obsah

1 Uvod do teorie mnoˇ´ zin 3

1.1 Zermelo-Fraenkelova axiomatick´a teorie mnoˇzin . . . 3

1.1.1 Tˇr´ıdy . . . 4

1.2 Z´akladn´ı pojmy a znaˇcen´ı . . . 5

1.3 Vlastnosti operac´ı . . . 7

1.4 Ekvivalence, pokryt´ı, rozklady. . . 9

1.5 Uspoˇr´ad´an´ı . . . 10

1.6 Mohutnost mnoˇziny . . . 11

1.7 Tˇr´ıdy podmnoˇzin dan´e mohutnosti . . . 13

1.8 Pˇrirozen´a ˇc´ısla a dalˇs´ı obory. . . 14

1.9 Koneˇcn´e mnoˇziny . . . 16

1.10 Spoˇcetn´e mnoˇziny . . . 20

1.11 Ordin´aln´ı ˇc´ısla . . . 22

1.11.3 Transfinitn´ı indukce a rekurze . . . 24

1.12 Axiom v´ybˇeru. . . 26

1.13 Kardin´aln´ı ˇc´ısla . . . 27 1.13.3 Souˇcet souboru kardin´aln´ıch ˇc´ısel a kardinalita sjednocen´ı 30

(3)

Kapitola 1

Uvod do teorie mnoˇ ´ zin

1.1 Zermelo-Fraenkelova axiomatick´ a teorie mnoˇ zin

Zermelo-Fraenkelovu teorii mnoˇzin formulujeme jako teorii v logice 1. ˇrádu s rovnost´ı v jazyce s jediným mimologickým symbolem∈a následuj´ıc´ımi axiomy:

(A1) Axiom existence. Existuje aspoˇn jedna mnoˇzina (tento axiom nemá v naˇs´ı axiomatizaci valný význam, nebot’ jde o sentenci platnou pˇr´ımo v logice s rovnost´ı; uvád´ıme jej pouze z tradiˇcn´ıch d˚uvod˚u).

(∃x)x=x

(A2) Axiom extenzionality. Mnoˇziny, jeˇz maj´ı stejné prvky se rovnaj´ı. (Opaˇcná implikace vyplývá z axiom˚u rovnosti v logice).

(∀x)(∀y)((∀u)(u∈x↔u∈y)→x=y)

(A3) Schéma axiom˚u vydˇelen´ı. Z kaˇzdé mnoˇziny lze vydˇelit mnoˇzinu vˇsech prvk˚u vyhovuj´ıch dané formuli (schéma je pˇredpis, stanovuj´ıc´ı naráz mnoho axiom˚u stejného typu):

Je-liφ(u) formule neobsahuj´ıc´ı volnˇe promˇennouz, potom formule (∀x)(∃z)(∀u)(u∈ z↔(u∈x∧φ(u))) je axiom vydˇelen´ı.

(A4) Axiom dvojice. Kaˇzd´e dvˇe mnoˇziny urˇcuj´ı dvouprvkovou mnoˇzinu.

(∀x)(∀y)(∃z)(∀u)(u∈z↔u=x∨u=y) (A5) Axiom sjednocen´ı. Sjednocen´ı vˇsech prvk˚u mnoˇziny je mnoˇzina.

(∀x)(∃z)(∀u)(u∈z→(∃y)(y∈x∧u∈y)

(A6) Axiom potence. Ke kaˇzd´e mnoˇzinˇe existuje mnoˇzina vˇsech jej´ıch podmnoˇzin (oznaˇcuje seP(x)).

(∀x)(∃z)(∀u)(u∈z↔(∀v)(v∈u→v∈x))

(4)

(A7) Sch´ema axiom˚u nahrazen´ı: Obraz mnoˇziny pˇri definovan´em zobrazen´ı je mnoˇzinou:

Je-liφ(u, v) formule, jeˇz neobsahuje volnˇe promˇenn´ez, w, potom formule (∀u)(∀v)(∀w)(φ(u, v)∧φ(u, w) → v = w) → (∀x)(∃z)(∀v)(v ∈ z ↔ (∃u)(u∈x∧φ(u, v))) je axiom nahrazen´ı.

(A8) Axiom nekoneˇcna. Existuje nekoneˇcná (induktivn´ı) mnoˇzina (konkrétnˇeji existuje mnoˇzina, obsahuj´ıc´ı prázdnou mnoˇzinu a s kaˇzdým svým prvkem utaké mnoˇzinuu∪ {u}).

(∃z)((∃u)(u∈z∧(∀v)(¬v∈u))∧

(∀u)(u∈z→(∀w)((∀t)(t∈w↔(t∈u∨t=u))→w∈z)) Do Zermelo-Fraenkelovy teorie mnoˇzin bývá obvykle zahrnován téˇzaxiom fundovanosti, jenˇz z univerza mnoˇziny ,,vykazuje” mnoˇziny urˇcitých vlastnost´ı (napˇr´ıklad vˇsechny mnoˇziny, pro nˇeˇz plat´ı x ∈ x) tak, ˇze stanov´ı, ˇze kaˇzdá neprázdná mnoˇzina mus´ı obsahovat prvek, jenˇz s n´ı má jiˇz prázdný pr˚unik).

V d˚usledku tento axiom omezuje univerzum mnoˇzin na kumulativn´ı hierarchii, jiˇz z´ıskáme transfinitn´ı iterac´ı operac´ı potence (v izolovaných kroc´ıch) a sjednocen´ı (v limitn´ıch kroc´ıch). Axiom fundovanosti nemá uplatnˇen´ı v bˇeˇzné ma- tematické praxi a z naˇsich dalˇs´ıch úvah jej vypust´ıme. Uvedenou teorii budeme znaˇcit ZF .

V mnoˇzinové matematice má dnes své pevné m´ısto takéaxiom výbˇeruumoˇzˇnuj´ıc´ı odpovˇedˇet na ˇradu matematických problém˚u a v r˚uzných podobách se uplatˇnuje v ˇradˇe matematických discipl´ın. Formulovat jej budeme pozdˇeji.

1.1.1 Tˇ r´ıdy

Schéma axiom˚u vydˇelen´ı nám umoˇzˇnuje z dané mnoˇziny vyˇclenit podmnoˇzinu tˇech prvk˚u, jeˇz splˇnuj´ı urˇcitou mnoˇzinovou vlastnost (vyjádˇrenou formul´ı jazyka teorie mnoˇzin). ˇCasto je vˇsak výhodné hovoˇrit o souboru v˚ubec vˇsech mnoˇzin splˇnuj´ıc´ıch danou vlastnost (bez omezen´ı do nˇejaké pˇredem dané mnoˇziny).

Zavád´ıme tak pojemtˇr´ıdového termu, tedy výrazu tvaru{x; φ(x)}, který ˇcteme tˇr´ıda vˇsech mnoˇzinxsplˇnuj´ıc´ıch formuliφ(x). Formuleφ(x) pˇritom sm´ı obsahovat dalˇs´ı mnoˇziny jako parametry. Tˇr´ıdy oznaˇcujeme zpravidla velkými p´ısmeny.

Malá p´ısmena vˇzdy oznaˇcuj´ı mnoˇziny. S tˇr´ıdami lze pracovat velmi podobnˇe jako s mnoˇzinami. Prvkem tˇr´ıdyX ={x; φ(x)}je kaˇzdá mnoˇzinax, splˇnuj´ıc´ı formuli φ(x). V takovém pˇr´ıpadˇe p´ıˇseme x∈ X. Podobnˇe p´ıˇseme X =Y právˇe kdyˇz tˇr´ıdy X, Y maj´ı za prvky tytéˇz mnoˇziny. Vˇsimnˇeme si, ˇze mnoˇzinaxobsahuje tytéˇz mnoˇziny jako tˇr´ıda definovaná tˇr´ıdovým termemX ={y; y∈x}. Mnoˇzinu xm˚uˇzeme proto s uvedenou tˇr´ıdou ztotoˇznit. Kaˇzdá mnoˇzina se tak souˇcasnˇe stává tˇr´ıdou. Tˇr´ıdám, které neodpov´ıdaj´ı ˇzádné mnoˇzinˇe, ˇr´ıkámevlastn´ı tˇr´ıdy.

Cistˇˇ e formálnˇe, pojem tˇr´ıdy chápeme jako toliko výrazový prostˇredek, který umoˇzˇnuje pracovat s vlastnostmi mnoˇzin jako s objekty. Kaˇzdý zápis obsahuj´ıc´ı tˇr´ıdové termy ˇci promˇenné m˚uˇzeme pˇreloˇzit do jazyka teorie mnoˇzin tak, ˇze kaˇzdý tˇr´ıdový term ˇci promˇennou nahrad´ıme pˇr´ısluˇsnou∈-formul´ı, která danou tˇr´ıdu definuje.

(5)

Universáln´ı tˇr´ıdou nazýváme tˇr´ıduVobsahuj´ıc´ı v˚ubec vˇsechny mnoˇziny, tj.

definujemeV={x; x=x}.Vje vlastn´ı tˇr´ıda: kdyby totiˇzV=vbyla mnoˇzina, byla by podle axiomu vydˇelen´ı téˇz y = {x ∈ v; x 6∈ x} mnoˇzina. Pˇritom z definicey vyplývá, ˇzey∈y↔y6∈y, coˇz nen´ı moˇzné.

1.2 Z´ akladn´ı pojmy a znaˇ cen´ı

Pˇri zapisován´ı mnoˇzinových ˇci tˇr´ıdových formul´ı budeme pouˇz´ıvat r˚uzných zkra- tek. Tam, kde nem˚uˇze doj´ıt k nedorozumˇen´ı, nebudeme d˚uslednˇe uˇz´ıvat závorek, jak naˇrizuje obvyklá induktivn´ı definice formule v logice. Jazyk teorie mnoˇzin (resp. jazyk tˇr´ıd) nav´ıc postupnˇe rozˇs´ıˇr´ıme o dalˇs´ı výrazové prostˇredky zaveden´ım nových funkˇcn´ıch a predikátových symbol˚u definic´ı. Kaˇzdou formuli takto obohaceného jazyka lze na základˇe definuj´ıc´ı formule nahradit s n´ı ekvivalentn´ı formul´ı základn´ıho jazyka (resp. jazyka tˇr´ıd).

Znakem ∅ oznaˇcujeme prázdnou mnoˇzinu. Poznamenejme, ˇze jej´ı existence vyplývá z axiomu existence a axiomu vydˇelen´ı pro formuli¬(x=x). Symbolem SXbudeme oznaˇcovatsjednocen´ıtˇr´ıdyX, tedy tˇr´ıdu{x; (∃y)(y∈X∧x∈y)}.

Z axiomu sjednocen´ı pak vypl´yv´a, ˇze pro libovolnou mnoˇzinuxjeSxmnoˇzina.

D´ale definujeme

\X={y; y∈[

X∧(∀z∈X)(y∈z)}, X−Y ={z; (z∈X)∧ ¬(z∈Y)}

pr˚unik tˇr´ıdy X a tˇr´ıdový rozd´ıl tˇr´ıdX aY. Jsou-li xa y mnoˇziny, jsou podle axiom˚u sjednocen´ı a vydˇelen´ıTxax−ymnoˇziny. (Poznamenejme, ˇze dle námi uvedené definice je T

∅ = ∅, nˇekter´a literatura zav´ad´ıT

tak, ˇze T

∅ = V.) Cten´ˇ aˇri jsou dále jistˇe známé symbolyX∪Y a X∩Y, oznaˇcuj´ıc´ısjednocen´ıa pr˚unik tˇr´ıd X a Y, tedy tˇr´ıdy X ∪Y ={z; (z ∈ X)∨(z ∈Y)} a X ∩Y = {z; (z ∈ X)∧(z ∈ Y)}. Pro mnoˇziny x,y máme ovˇsem x∪y = S

{x, y}, x∩y=T

{x, y}, kde{x, y}oznaˇcuje(neuspoˇr´adanou) mnoˇzinovou dvojici (jej´ıˇz existenci zaruˇcuje axiom dvojice).

Tˇr´ıdyX, Y jsou disjunktn´ı, jestliˇze X∩Y =∅.

Definic´ı zaved’me hned také nové predikáty6=,6∈,⊂,⊆,⊃,⊇:

x6=y↔ ¬(x^df =y) x /∈y↔ ¬(x^df ∈y)

x⊆y↔^df (∀z)(z∈x→z∈y) x⊂y↔^df (x⊆y∧x6=y) x⊇y↔^df y⊆x

x⊃y↔^df y⊂x

Uspoˇrádaná dvojice mnoˇzinxa y je definována jako hx, yi={{x},{x, y}}.

(6)

Uspoˇr´adan´en-tice definujeme induktivnˇe:

hxi₁=x, hx₁, . . . , x_n+1i_n+1=hhx₁, . . . , x_ni_n, x_n+1i M´ıstoh. . .in p´ıˇseme vˇetˇsinou opˇet jenh. . .i.

Dále zavád´ıme následuj´ıc´ı operace:

−X={x; x6∈X} (doplnˇek),

X×Y ={hx, yi; x∈X∧y∈Y}(kart´ezsk´y souˇcin),

Xⁿ={hx1, . . . , x_ni; x₁∈X∧. . .∧x_n∈X}(kart´ezsk´a mocnina), dom(X) ={x; (∃y)(hx, yi ∈X)} (definiˇcn´ı obor),

rng(X) ={y; (∃x)(hx, yi ∈X)}(obor hodnot), X⁻¹={hy, xi; hx, yi ∈X}(inverze),

X⁰⁰Y ={z; (∃y)(hy, zi ∈X} (obraz), m´ıstoX⁰⁰Y p´ıˇseme t´eˇzX[Y].

X Y ={hx, yi; hx, yi ∈X∧x∈Y}(parcializace) P(X) ={u; u⊆X}(potence)

Z axiomu potence vypl´yv´a, ˇze potence mnoˇziny je mnoˇzina.

n-árn´ı relac´ına tˇr´ıdˇeX nazýváme libovolnou tˇr´ıduR ⊆Xⁿ. M´ısto 2-árn´ı relace ˇr´ıkámebinárn´ı relace nebo ˇcastˇeji jenrelace.

Zobrazen´ıje relaceF (naV) splˇnuj´ıc´ı n´asleduj´ıc´ı podm´ınku jednoznaˇcnosti:

(∀x)(∀y)(∀z)((hx, yi ∈F∧ hx, zi ∈F)→y=z)

Je-liF zobrazen´ı a hx, yi ∈F, znaˇc´ıme y symbolem F(x). M´ısto zobrazen´ı ˇr´ıkáme takéfunkce. Je-liamnoˇzinaX libovolná tˇr´ıda, definujeme dále

aX ={f; f je funkce ∧dom(f) =a∧rng(f)⊆X} (mnoˇzinová mocnina) M´ıstof ∈âX p´ıˇseme téˇzf :a→X, ˇr´ıkáme, ˇzef je zobrazen´ıadoX. Obdobnˇe definujemeF :A→X (Aje zde libovolná tˇr´ıda), ˇcteme:F je zobrazen´ıAdoX.

Jestliˇze nav´ıcX = rng(F), ˇr´ıkáme, ˇzeFje zobrazen´ıAnaX. FunkceF :A→X je prostá, jestliˇze pro kaˇzdé dva r˚uzné prvky x, y ∈ A plat´ı F(x) 6= F(y).

Zobrazen´ıF : A → X je vzájemnˇe jednoznaˇcné neboli bijekce, je-li souˇcasnˇe prosté a na.

Znaˇc´ıme d´aleId={hx, xi; x∈V}(identick´e zobrazen´ı) a klademeId_X = IdX pro libovolnou tˇr´ıduX.

Sloˇzen´ım relac´ıR, S nazveme relaci

R◦S={hu, vi; (∃w)(hu, wi ∈R∧ hw, vi ∈S}.

Pro libovolnou tˇr´ıduX pak plat´ı (R◦S)⁰⁰X =S⁰⁰(R⁰⁰X). Speci´alnˇe, jsou-liF,G zobrazen´ı, plat´ı (∀x∈dom(F))((F◦G)(x) =G(F(x)).

Zobrazen´ıX : I → V, kde I je mnoˇzina, m˚uˇzeme chápat také jako sou- bor mnoˇzin (indexovaný prvky mnoˇziny I). M´ısto X(i) pro i ∈ I pak p´ıˇseme vˇetˇsinou jenXi a m´ıstoX p´ıˇseme

hX_i; i∈Ii, ˇci krátcehX_ii_i∈I, nebo jenhX_ii_I (1.1) O mnoˇzináchXimluv´ıme téˇz jako o prvc´ıch souboru (1.1).Kartézský souˇcin souboru mnoˇzin(1.1) je mnoˇzinaQ

Xivˇsech zobrazen´ıf takov´ych, ˇze dom(f) =

(7)

I a f(i)∈ Xi pro vˇsechna i∈I. Sjednocen´ı souboru mnoˇzin (1.1) je mnoˇzina S

i∈IXi=S

rng(X),pr˚unik souboru mnoˇzin(1.1) je mnoˇzinaT

i∈IXi=T

rng(X).

M´ısto symbol˚uQ

i∈IXi,S

i∈IXi,T

i∈IXip´ıˇseme ˇcasto pro zkr´acen´ı jenQ

IXi, S

IXi,T

IXi.

1.3 Vlastnosti operac´ı

Komutativita∪a∩

X∩Y =Y ∩X, X∪Y =Y ∪X Asociativita∪a∩

(X∩Y)∩Z=X∩(Y ∩Z), (X∪Y)∪Z=X∪(Y ∪Z) Idempotence∪ a∩

X∩X =X X∪X =X Distributivita∪ a∩

X∩(Y ∪Z) = (X∩Y)∪(X∩Z), X∪(Y ∩Z) = (X∪Y)∩(X∪Z) Z´akony absorpce

X∪(X∩Y) =X, X∩(X∪Y) =X DeMorganova pravidla

−(X∩Y) = (−X)∪(−Y), −(X∪Y) = (−X)∩(−Y) Pravidlo dvoj´ıho komplementu

−(−X) =X

Z´akony o∅ aV

X∩ ∅=∅ X∪ ∅=X

X∩V=X X∪V=V

X∩ −X =∅ X∪ −X=V

∅ 6=V

Pravidla pro operace∩,∪,−, která jsme dosud uvedli jsou vlastnˇe axiomy Bo- oleových algeber. Aplikujeme-li je na podmnoˇziny nˇejaké mnoˇziny x, pˇriˇcemˇz vˇsude tˇr´ıdu V nahrad´ıme mnoˇzinou x (takˇze napˇr. −y = {z ∈ x; z /∈ y}), vid´ıme, ˇze mnoˇzinaP(x) tvoˇr´ı spolu s operacemi∩,∪,−Booleovu algebru.

(8)

Pravidla o rozd´ılu tˇr´ıd

X−Y =X∩(−Y) X− ∅=X ∅ −X=∅

X−X =∅ X−V=∅

(X−Y)−Z=X−(Y ∪Z) X−(Y −Z) = (X−Y)∪(X∩Z) (X−Y)−Z⊆X−(Y −Z) Vlastnosti inkluze

X ⊆Y ∧Y ⊆X ↔X =Y

X ⊆Y ↔X∩Y =X X ⊆Y ↔X∪Y =Y

X ⊆V ∅ ⊆X

Distributivn´ı z´akony pro×: Bud’operace∪nebo∩. Pak:

X×(YZ) = (X×Y)(X×Z), (XY)×Z = (X×Z)(Y ×Z) Vlastnosti obrazu:

X⁰⁰(Y ∪Z) =X⁰⁰Y ∪X⁰⁰Z X⁰⁰(Y ∩Z)⊆X⁰⁰Y ∩X⁰⁰Z X⁰⁰Y −X⁰⁰Z ⊆X⁰⁰(Y −Z)

Je-liF funkce, plat´ı

F⁻¹[Y ∩Z] =F⁻¹[Y]∩F⁻¹[Z], F⁻¹[Y −Z] =F⁻¹[Y]−F⁻¹[Z].

Pro relaceR, S, T plat´ı:

(R⁻¹)⁻¹=R,(R◦S)⁻¹=S⁻¹◦R⁻¹, R◦(S◦T) = (R◦S)◦T VlastnostiP a S:

[P(X) =X, X ⊆ P([ X) Omezen´ı operac´ı:

X×Y ⊆ P(P(X∪Y)) ^aX ⊆ P(a×X)⊆ P(P(P(a∪X))) dom(X)⊆[ [

X rng(X)⊆[ [

X

D˚usledek: jsou-li x, y, a mnoˇziny, jsou x∪y, x×y, ^ax, dom(x) i rng(x) mnoˇziny podle axiom˚u potence, sjednocen´ı a vydˇelen´ı.

(9)

1.4 Ekvivalence, pokryt´ı, rozklady

RelaceRjereflexivn´ına tˇr´ıdˇeA, jestliˇze pro kaˇzdéx∈Ajehx, xi ∈R. ˇRekneme dále, ˇzeR jesymetrickáresp.tranzitivn´ı, jestliˇzehx, yi ∈R→ hy, xi ∈R. resp.

(hx, yi ∈R∧ hy, zi ∈R)→ hx, zi ∈Rpro kaˇzd´ex, y, z.

RelaceE jeekvivalence na tˇr´ıdˇe A, je-li reflexivn´ı naA, symetrická a tranzitivn´ı. ˇR´ıkáme, ˇzeEjeekvivalence, je-li ekvivalenc´ı na svém definiˇcn´ım oboru.

Je-lixprvek definiˇcn´ıho oboru ekvivalenceE, jeE⁰⁰{x}tˇr´ıda ekvivalence prvku xa znaˇc´ı se symbolem [x]E. Je-liE⊆a² ekvivalence na mnoˇzinˇea, naz´yv´ame mnoˇzinu

a/E ={[x]E; x∈a}

faktorizac´ı ˇci faktorem mnoˇzinyapodle ekvivalence E.

Je-li u 6= ∅ mnoˇzina, jej´ıˇz kaˇzd´y prvek je ekvivalence na mnoˇzinˇe a, pak rovnˇeˇzTuje ekvivalence naa. D´ale plat´ı, ˇzeId_X je⊆-nejmenˇs´ı ekvivalence na tˇr´ıdˇeX.

Rekneme, ˇˇ ze tˇr´ıdaC je pokryt´ıtˇr´ıdyX, neboli ˇzepokrývá tˇr´ıduX, jestliˇze C ⊆ P(X)− {∅} a SC = X. Rozklad neboli disjunktn´ı pokryt´ı tˇr´ıdy X je pokryt´ı tˇr´ıdyX, které se skládá z navzájem disjunktn´ıch mnoˇzin.

Zˇrejmˇe, je-liEekvivalence na mnoˇzinˇea, jea/Erozklad mnoˇzinya. Naopak, je-liCrozklad mnoˇzinya, je mnoˇzinaE={hx, yi ∈a×a; (∃u∈C)({x, y} ⊆u)}

ekvivalence naaaa/E =D.

Bud’ Atˇr´ıda,F :Aⁿ →Azobrazen´ı aE ekvivalence naA. ˇRekneme, ˇzeE jekongruence v˚uˇci F na A, jestliˇze plat´ı

(∀x1, . . . , x_n)(∀x⁰₁, . . . , x⁰_n)(hx1, x⁰₁i ∈E∧. . .∧ hxn, x⁰_ni ∈E

→ hF(x1, . . . , xn), F(x⁰₁, . . . , x⁰_n)i ∈E) Speciálnˇe, je-li F : A → A nˇejaká funkce, je ekvivalence E na A kongruence v˚uˇciF, právˇe kdyˇzhx, yi ∈E→ hF(x), F(y)i ∈E pro kaˇzdéx, y∈A.

Poukaˇzme hned na jeden velmi hojný a uˇziteˇcný matematický obrat. Je-liA mnoˇzina, na n´ıˇz je dána nˇejaká mnoˇzina operac´ıσ(pˇredstavit si m˚uˇzeme tˇreba mnoˇzinu okruh ˇc´ısel Z s operacemi {+,−,·}) pak na faktor A/E mnoˇziny A podle ekvivalenceE, jeˇz je kongruenc´ı v˚uˇci kaˇzdé operaci zσ, m˚uˇzemekanonicky pˇrenést vˇsechny operace z σ tak, ˇze pro kaˇzdoun-árn´ı operaci o∈σ poloˇz´ıme o⁰ = {h[x₁]_E, . . . ,[x_n]_E,[y]_Ei; o(x₁, . . . , x_n) = y}. Z definice kongruence nyn´ı zˇrejmˇe plyne, ˇzeo⁰je korektnˇe definovaná operace na faktoruA/E. Jej´ı hodnota na libovolných rozkladových tˇr´ıdách podle E je jednoznaˇcnˇe urˇcena hodnotou operaceona libovolných reprezentantech daných rozkladových tˇr´ıd.

Pˇ r´ıklady

1. Strukturu Q racionáln´ıch ˇc´ısel s operacemi sˇc´ıtán´ı, odˇc´ıtán´ı, násoben´ı a inverzn´ıho prvku, lze z´ıskat výˇse popsanou metodou faktorizace struktury hZ×N,⊕, ,,⁻¹i, kde

• ha, bi ⊕ hc, di=had+bc, bdi,

(10)

• ha, bi hc, di=had−bc, bdi,

• ha, bi ⊗ hc, di=hac, bdi,

• ha, bi⁻¹=hb, ai, proa≥0

• ha, bi⁻¹=h−b,|a|i, proa <0

podle kongruence ∼definované vztahem:ha, bi ∼ hc, di ↔ ad=bc. Ob- vyklé uspoˇrádán´ı lze naQzavést vztahem [ha, bi]_∼<^Q[hc, di]_∼↔ad < bc, kde na pravé stranˇe<znaˇc´ı obvyklé uspoˇrádán´ı celých ˇc´ısel.

2. Faktorizac´ı okruhuhZ,0,1,+,·ipodle kongruence ,,modulop”,a≡_pb↔ p|a−b, kde p >1 je prvoˇc´ıslo, z´ıskáme koneˇcné, alegebraicky uzavˇrené tˇeleso charakterup, oznaˇcovanéZp.

1.5 Uspoˇ r´ ad´ an´ı

RelaceRje na tˇr´ıdˇeAslabˇe antisymetrickáresp.trichotomická, plat´ı-li (∀x, y∈ A)(hx, yi ∈ R∧ hy, xi ∈ R → x = y) resp. (∀x, y ∈ A)(hx, yi ∈ R ∨x = y∨hy, xi ∈R).Rjeuspoˇrádán´ınaA, je-liRnaAreflexivn´ı, slabˇe antisymetrická a tranzitivn´ı. RelaceR jeostré uspoˇrádán´ı naA, je-li R naA antisymetrická, tj. plat´ı-li (∀x, y ∈ A)(hx, yi ∈ R → hy, xi ∈/ R) a tranzitivn´ı. Z uvedených vlastnost´ı ihned plyne, ˇze ostré uspoˇrádán´ı je téˇzantireflexivn´ı, tj. ˇze plat´ı (∀x∈ A)(hx, xi∈/R).

Je-liR uspoˇrádán´ı (resp. ostré uspoˇrádán´ı), a R je nav´ıc trichotomická na A, nazývá seR lineárn´ı uspoˇrádán´ı(resp.ostré lineárn´ı uspoˇrádán´ınaA.

Rekneme-li, ˇˇ ze (A, R) je uspoˇrádán´ı, znamená to, ˇze R je uspoˇrádán´ı na A a A 6= ∅. M´ısto hx, yi ∈ R v takovém pˇr´ıpadˇe p´ıˇseme x ≤R y. Je-li (A, R) uspoˇrádán´ı, je ˜R = R−Id ostré uspoˇrádán´ı na A. M´ısto hx, yi ∈ R˜ p´ıˇseme x <_Ry. Plat´ı tedyx <_Ry↔x≤Ry∧x6=y.

Relaci uspoˇrádán´ı na nˇejaké tˇr´ıdˇe znaˇc´ıme nejˇcastˇeji symboly ≤,,v, apod. Pˇr´ısluˇsnou ostrou verzi pak znaˇc´ıme symboly<,≺,@, /.

Bud’ (A,≤) uspoˇrádán´ı a X ⊆ A. ˇRekneme, ˇze X je doln´ı (resp. horn´ı) tˇr´ıda v uspoˇrádán´ı (A,≤), jestliˇze plat´ı (∀x ∈ X)(∀y ∈ A)(y ≤x → y ∈ X) (resp. (∀x∈ X)(∀y ∈ A)(x≤ y → y ∈ X)). Bud’ dále X 6= ∅. Prvek y ∈ A je minoranta (resp. majoranta) tˇr´ıdy X v uspoˇrádán´ı (A,≤), plat´ı-li (∀x ∈ X)(y≤x) (resp. (∀x∈X)(x≤y)). ˇRekneme dále, ˇze y∈Ajenejmenˇs´ı(resp.

nejvˇetˇs´ı)prvek tˇr´ıdyX v uspoˇrádán´ı (A,≤), je-liyminoranta (resp. majoranta) X v uspoˇrádán´ı (A,≤) a y ∈ X. P´ıˇseme pak y = nejm_≤(X) nebo obˇs´ırnˇeji y= nejm_(A,≤)(X) (resp.y= nejv_≤(X) nebo obˇs´ırnˇejiy= nejv_(A,≤)(X)). Prvek y ∈ A je minimáln´ı (resp.maximáln´ı) prvek tˇr´ıdy X, plat´ı-liy ∈ X∧(∀x ∈ X)¬(x < y) (resp.y ∈X∧(∀x∈X)¬(y < x)). Prveky∈Ajeinfimum (resp.

supremum) tˇr´ıdy X v (A,≤), jestliˇze y je nejvˇetˇs´ı minoranta (resp. nejmenˇs´ı majoranta) tˇr´ıdy X v (A,≤). P´ıˇseme pak y = inf_≤(X) nebo obˇs´ırnˇeji y = inf_(A,≤)(X) (resp. y= sup_≤(X) nebo obˇs´ırnˇeji y= sup_(A,≤)(X)).

(11)

Nejmenˇs´ı prvek a infimum jsou, pokud existuj´ı, urˇceny jednoznaˇcnˇe. V line-

´

arn´ım uspoˇrádán´ı pojmy minimáln´ıho a nejmenˇs´ıho prvku splývaj´ı. Obdobnˇe je tomu s nejvˇetˇs´ım prvkem, supremem a maximáln´ım prvkem.

Uspoˇrádán´ı (A,≤) je tzv. dobré uspoˇrádán´ı (ˇr´ıkáme téˇz, ˇze relace ≤ je dobrým uspoˇrádán´ım naA), má-li kaˇzdá neprázdná podmnoˇzinau⊆Av uspoˇrádán´ı (A,≤) nejmenˇs´ı prvek.

Kaˇzdé dobré uspoˇrádán´ı je lineárn´ı, nebot’ jsou-lix, y∈A, mus´ı m´ıt mnoˇzina {x, y} ⊆Anejmenˇs´ı prvek, tud´ıˇz bud’x≤y neboy≤x.

Mnoˇzinové uspoˇrádán´ı (a,≤) je úplný svaz, jestliˇze kaˇzdá neprázdná pod- mnoˇzina mnoˇzinyamá v (a,≤) jak infimum tak supremum.

Bud’ Alibovolná tˇr´ıda. Symbolem (A,⊆) oznaˇcujeme uspoˇrádán´ı (A, R) na A, kde R = {hx, yi ∈ A×A; x⊆ y}. Bud’ a mnoˇzina a ∅ 6= u⊆ P(a). Pak sup_(P(a),⊆)(u) =Sua inf_(P_(a),⊆)(u) =Tu, (P(a),⊆) je tedy úplný svaz. Je-li x∈a, je {x}minimáln´ı prvek tˇr´ıdyP(a)− {∅} v uspoˇrádán´ı (P(a),⊆).

Jiným pˇr´ıkladem úplného svazu je tˇreba uzavˇrený interval [0,1] reálných ˇc´ısel spolu s obvyklým uspoˇrádán´ım.

Necht’ (A,≤),(B,v) jsou uspoˇrádán´ı. ˇRekneme, ˇze zobrazen´ıF : A → B je vnoˇren´ı uspoˇrádán´ı (A,≤) do (B,v), je-li to zobrazen´ı prosté a pro kaˇzdé x, y∈Aplat´ı

x≤y↔F(x)vF(y).

Rekneme d´ˇ ale, ˇze zobrazen´ıF :A→B jeizomorfismus (A,≤) a (B,v), je-li to vnoˇren´ı (A,≤) do (B,v) a zobrazuje-li nav´ıc mnoˇzinuAnaB.Automorfismus uspoˇr´ad´an´ı (A,≤) je izomorfismus (A,≤) a (A,≤).

V ˇETA 1.5.1 (o pevném bodu). Bud’(a,≤)úplný svaz af neklesaj´ıc´ı funkce na (a,≤)(tj. f :a→a ax≤y →f(x)≤f(y) prox, y∈a). Pak existuje u∈a tak, ˇzef(u) =u.¹

D˚ukaz. Uvaˇzujme mnoˇzinut={v ∈a; v≤f(v)} ⊆aa oznaˇcmeujej´ı supremum. Ukáˇzeme, ˇze u je pevný bod f. Pro kaˇzdé v ∈ t tedy plat´ı v ≤ u a d´ıky definici t a monotónnosti zobrazen´ı f tedy v ≤ f(v) ≤ f(u) a tud´ıˇz i u = sup_(a,≤)(t) ≤ f(u) z definice suprema. Z monotónnosti proto plyne f(u) ≤ f(f(u)). Pak ovˇsem f(u) ∈ t (dle definice t), tud´ıˇz f(u) ≤ u (neb u je majorantat); souˇcasnˇe z definice t mámeu≤f(u). Rovnost plyne ze slabé

antisymetrie uspoˇr´ad´an´ı. 2

1.6 Mohutnost mnoˇ ziny

Pro srovnáván´ı velikosti mnoˇzin zavád´ıme dvˇe d˚uleˇzité relace: ˇrekneme, ˇze mnoˇzina xje subvalentn´ı mnoˇzinˇe y (p´ıˇseme x 4 y, pˇr´ıpadnˇe y < x), jestliˇze existuje prosté zobrazen´ı mnoˇziny x doy. ˇR´ıkáme pak téˇz, ˇze x má mohutnost menˇs´ı nebo rovnu mohutnosti y. ˇRekneme, ˇze mnoˇzinyxay jsou ekvipotentn´ı, neboli ˇzemaj´ı stejnou mohutnost (p´ıˇsemex≈y), existuje-li prosté zobrazen´ıxnay.

1R´ık´ˇ ame, ˇzeuje pevn´y bod funkcef.

(12)

Plat´ı-lix4y, nikoli vˇsakx≈y, ˇr´ık´ame, ˇze mnoˇzinaxm´amenˇs´ı mohutnost neˇz mnoˇzina y a p´ıˇsemex≺y.

Evidentnˇe plat´ı n´asleduj´ıc´ı vztahy x≈x

x≈y→y≈x

(x≈y∧y ≈z)→x≈z x⊆y→x4y

x4x

(x4y∧y 4z)→x4z

Z uvedených vlastnost´ı vid´ıme, ˇze relaceR_≈={hx, yi; x≈y}je ekvivalence na tˇr´ıdˇeV. Nav´ıc, je-lix6=∅, je tˇr´ıda [x]R≈ ekvivalence R≈ vlastn´ı tˇr´ıda (staˇc´ı napˇr´ıklad uváˇzit, ˇze vlastn´ı tˇr´ıda{{y} ×x; y∈V}je ˇcást´ı [x]R≈).

Relace4je reflexivn´ı a tranzitivn´ı.

V ˇETA 1.6.1 (Cantor, Bernstein).

(x4y∧y4x)→x≈y

Neboli: Je-li mohutnost mnoˇziny x menˇs´ı nebo rovna mohutnosti mnoˇziny y a naopak, maj´ıxay stejnou mohutnost.

D˚ukaz. Podle pˇredpokladu existuj´ı prosté funkce f :x→y a g :y →x. Staˇc´ı dokázat, ˇze existujeu⊆xtakové, ˇze plat´ı

x−u=g[y−f[u]], tedy u=x−g[y−f[u]],

nebot’ pak m˚uˇzeme definovat prost´e zobrazen´ıhmnoˇzinyxna mnoˇzinuypˇredpisem

h(z) =

(f(z) proz∈u g⁻¹(z) proz∈x−u

(nakreslete si obrázek). Hledanéunalezneme jako pevný bod funkceH :P(x)→ P(x),H(u) =x−g[y−f[u]]. Jelikoˇz (P(x),⊆) je úplný svaz, staˇc´ı podle vˇety o pevném bodu, ukáˇzeme-li, ˇze H je ⊆-neklesaj´ıc´ı. Necht’ u ⊆ v ⊆ x. Pak zˇrejmˇef[u]⊆f[v],y−f[u]⊇y−f[v], tedyg[y−f[u]]⊇g[y−f[v]] a koneˇcnˇe H(u) =x−g[y−f[u]]⊆x−g[y−f[v]] =H(v). 2 V ˇETA 1.6.2 (Cantor). x≺ P(x)

D˚ukaz. Zˇrejmˇex4P(x) (staˇc´ı napˇr., poloˇz´ıme-lif(z) ={z}proz∈x). Zbývá dokázat ¬(x≈ P(x)). Sporem: necht’f je prostá funkce zobrazuj´ıc´ıxnaP(x).

Pak existuje a ∈ x tak, ˇze f(a) = {z ∈ x; z /∈ f(z)} a mˇelo by platit bud’

a∈f(a), neboa /∈f(a). Kaˇzd´y z tˇechto pˇredpoklad˚u vˇsak vede ihned ke sporu.

2

(13)

Prázdnou mnoˇzinu∅budeme znaˇcit téˇz symbolem 0, jednoprvkovou mnoˇzinu {0}symbolem 1 a dvouprvkovou mnoˇzinu{0,1}symbolem 2 (posléze analogicky zavedeme vˇsechna pˇrirozená ˇc´ısla).

Disjunktn´ı sjednocen´ıtˇr´ıdX, Y znaˇc´ımeX]Y a definujeme vztahem X]Y = ({∅} ×X)∪({1} ×Y).

Plat´ı zˇrejmˇex∪y4x]ya je-lixalespoˇn dvouprvkov´a, je nav´ıcx]x4x×x.

Prox≈x⁰,y≈y⁰ a zplat´ı d´ale n´asleduj´ıc´ı vztahy:

x]y≈x⁰]y⁰ x×y≈x⁰×y⁰

x]y≈y]x x×y≈y×x

x](y]z)≈(x]y)]z x×(y×z)≈(x×y)×z x×(y]z)≈(x×y)](x×z)

yx≈^y⁰x⁰ P(x)≈ P(x⁰)

Pˇripomeˇnme, ˇze^∅x={∅} a^y∅=∅proy6=∅. Pro mnoˇzinyx, y, u, v d´ale plat´ı:

∅ 6=x4y →^xu4^yu ^y(^xu)≈^(y×x)u u4v→^xu4^xv ^(x]y)u≈^xu×^yu

Dokaˇzme napˇr´ıklad prvn´ı formuli druhého sloupce. Funkceh:^y(^xu)→^(y×x)u bud’ definována vztahemh(f)(ha, bi) =f(a)(b) (kdef :y→^xuah(f) :y×x→ u. Zˇrejmˇe pakhje prosté zobrazen´ı^y(^xu) na^(y×x)u.

TVRZEN´I 1.6.3.

1. P(a)≈^a2.

2. Je-li a×a≈aaaprázdná, nebo alespoˇn dvouprvková, pakâ2≈âa.

D˚ukaz. Zobrazen´ıh:P(a)→^a2 bud’ definov´ano pˇredpisem h(x)(z) =

(1 proz∈x

∅ proz∈a−x

Snadno se nahlédne, ˇzehje prosté zobrazen´ıP(a) naâ2. Pro prázdnou mnoˇzinu plat´ı druhá ˇcást tvrzen´ı evidentnˇe. Je-liaalespoˇn dvouprvková, je zˇrejmˇeâa<

a2. Dále âa ⊆ P(a×a), tedy âa4 P(a×a) a tud´ıˇz, je-li a×a ≈a, je âa 4

P(a)≈^a2. 2

1.7 Tˇ r´ıdy podmnoˇ zin dan´ e mohutnosti

Bud’ X tˇr´ıda a a mnoˇzina. Tˇr´ıdu vˇsech podmnoˇzin tˇr´ıdy X maj´ıc´ıch stejnou mohutnost jakoa, znaˇc´ıme symbolem [X]^a. Form´alnˇe:

[X]^a={y; y⊆X∧y≈a}.

Zˇrejmˇe je [X]^∅ = {∅} a [∅]â = ∅, pokud je a 6= ∅. Je-li x mnoˇzina, je [x]â ⊆ P(x) mnoˇzina. Je-lix≺a, je [x]â =∅.

(14)

1.8 Pˇ rirozen´ a ˇ c´ısla a dalˇ s´ı obory

V dneˇsn´ı dobˇe hraje teorie mnoˇzin roli základn´ı matematické teorie, v jej´ımˇz rámci jsou podrobovány studiu prakticky veˇskeré matematické objekty. Tyto objekty ˇci pojmy vˇsak ˇcasto nevzeˇsly ze svˇeta teorie mnoˇzin, ale ze svˇeta, jenˇz nás obklopuje. Chceme-li je tedy v teorii mnoˇzin studovat, mus´ıme je v n´ı být nejprve schopni dostateˇcnˇe vˇernˇe zachytit, reprezentovat. Pod´ıvejme se nejprve, jakým zp˚usobem lze pomoc´ı mnoˇzin zachytit pˇrirozená ˇc´ısla.

Základn´ı myˇslenka pocház´ı od von Neumanna: kaˇzdému pˇrirozenému ˇc´ıslu pˇriˇrad´ıme vhodnou mnoˇzinu, jeˇz bude m´ıt právˇe tolik prvk˚u, jaké ˇc´ıslo pˇredstavuje a tˇemi budou mnoˇziny pˇriˇrazené právˇe vˇsem ˇc´ısl˚um menˇs´ım. ˇC´ıslo nula nemá ˇzádné pˇredch˚udce, bude tedy reprezentováno prázdnou mnoˇzinou∅. ˇC´ıslo 1 má právˇe jednoho pˇredch˚udce a t´ım je ˇc´ıslo 0, reprezentované mnoˇzinou ∅; ˇc´ıslu jedna tedy pˇriˇrad´ıme jednoprvkovou mnoˇzinu {∅}. T´ımto zp˚usobem m˚uˇzeme pokraˇcovat dále a ˇc´ısl˚um 2,3,4, . . . atd. po ˇradˇe pˇriˇradit mnoˇziny {∅,{∅}}, {∅,{∅},{∅,{∅}}},{∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}}}. Je-li ˇc´ıslonreprezentováno mnoˇzinou ¯n, je ˇc´ıslon+ 1 reprezentováno mnoˇzinoun+ 1 = ¯n∪ {¯n}.

Je zˇrejmé, ˇze takto m˚uˇzeme do teorie mnoˇzin pˇrenést kaˇzdé konkrétn´ı pˇrirozené ˇc´ıslo. Problém nastane, budeme-li cht´ıt v teorii mnoˇzin z´ıskat mnoˇzinu právˇe vˇsech takto z´ıskaných mnoˇzin. Z vˇety o kompaktnosti v logice totiˇz vyplývá, ˇze (ani pˇridán´ım libovolného mnoˇzstv´ı axiom˚u) nem˚uˇzeme zabránit tomu, aby kaˇzdá mnoˇzina obsahuj´ıc´ı reprezentanty vˇsech konkrétn´ıch pˇrirozených ˇc´ısel ob- sahovala také nˇejaký nestandardn´ı prvek, tedy mnoˇzinu, jeˇz sama nen´ı tvaru

¯

npro ˇzádné konkrétn´ı (metamatematické) pˇrirozené ˇc´ıslon. S t´ımto faktem je tˇreba se sm´ıˇrit. Podstatné bude, podaˇr´ı-li se nám v teorii mnoˇzin naj´ıt mnoˇzinu obsahuj´ıc´ı vˇsechna konkrétn´ı pˇrirozená ˇc´ısla (rozum´ı se jejich mnoˇzinové reprezentanty) a jej´ıˇz vˇsechny prvky maj´ı veˇskeré základn´ı vlastnosti pˇrirozených ˇc´ısel, ˇreknˇeme splˇnuj´ı axiomyPeanovy aritmetiky vˇcetnˇe schématu indukce pro vhodnˇe definované operace sˇc´ıtán´ı a násoben´ı. Takovou mnoˇzinu pak budeme nazývat mnoˇzinou pˇrirozených ˇc´ısel (v teorii mnoˇzin je zvykem znaˇcit ji ˇreckým p´ısmenem omega,ω, pˇr´ıpadnˇe symbolemN) a jej´ım prvk˚um budeme prostˇe ˇr´ıkat pˇrirozená ˇc´ısla (ztotoˇzˇnuj´ıce kaˇzdé konkrétn´ı pˇrirozené ˇc´ıslo n s jeho reprezen- tantem ¯n).

Idea, jeˇz nám umoˇzn´ı mnoˇzinuω naj´ıt, je následuj´ıc´ı: je zˇrejmé, ˇze ideáln´ı mnoˇzinaω, jej´ımiˇz prvky by byly pouze konkrétn´ı pˇrirozená ˇc´ısla, mus´ı obsahovat nulu (∅) a s kaˇzdým ˇc´ıslemx, které se v n´ı nacház´ı, mus´ı obsahovat také jeho následn´ıka, tj. mnoˇzinu x∪ {x}. To nás vede k následuj´ıc´ı definici: ˇRekneme, ˇze mnoˇzinaz jeinduktivn´ı, jestliˇze ∅ ∈z∧(∀x)(x∈z →x∪ {x} ∈ z). Kaˇzdá induktivn´ı mnoˇzina tak obsahuje vˇsechna konkrétn´ı pˇrirozená ˇc´ısla a ideáln´ı mnoˇzina sestávaj´ıc´ı právˇe z tˇechto ˇc´ısel by nutnˇe sama byla induktivn´ı. Nejlepˇs´ı aproximaci takové ideáln´ı mnoˇziny tud´ıˇz z´ıskáme, kdyˇz nalezneme nejmenˇs´ı induktivn´ı mnoˇzinu. Tou by ovˇsem musel být pr˚unik vˇsech induktivn´ıch mnoˇzin, T{x; xje induktivn´ı}. Axiom nekoneˇcna zaruˇcuje, ˇze existuje alespoˇn jedna induktivn´ı mnoˇzina. Odtud vyplývá, ˇze tˇr´ıda vˇsech induktivn´ıch mnoˇzin je neprázdná a tud´ıˇz je jej´ı pr˚unik mnoˇzina. Jak jiˇz bylo ˇreˇceno, budeme ji znaˇcit

(15)

ω, tj.

ω=\

{x; xje induktivn´ı}.

Snadno se nahl´edne, ˇzeω je sama induktivn´ı. Plat´ı tedy n´asleduj´ıc´ı princip:

V ˇETA 1.8.1 (Princip matematick´e indukce).

1. Necht’ φ(x) je formule jazyka teorie mnoˇzin. Pak plat´ı

(φ(∅)∧(∀x∈ω)(φ(x)→φ(x∪ {x})))→(∀x∈ω)φ(x) 2. Necht’ X ⊆ω,∅ ∈X a pro kaˇzd´e x∈X je x∪ {x} ∈X. PakX=ω.

Naω zav´ad´ıme relaci≤vztahem

x≤y↔(x=y∨x∈y).

Ukáˇzeme, ˇze ≤je lineárn´ı (dokonce dobré) uspoˇrádán´ı. Nav´ıc uv´ıd´ıme, ˇze odpov´ıdaj´ıc´ı ostré uspoˇrádán´ı je pˇr´ımo relace ∈a ˇze pro pˇrirozená ˇc´ıslax, yplat´ı x≤y právˇe kdyˇzx⊆y.

LEMMA 1.8.2. Pro kaˇzd´ex∈ω plat´ı:

1. x6=∅ → ∅ ∈x,

2. (∀y∈ω)(x∈y→x∪ {x} ≤y), 3. (∀y∈ω)(x≤y→x⊆y), 4. x6=x

D˚ukaz. 1. Indukc´ı: je-li x = ∅, nen´ı co dokazovat. Je-li ∅ ∈ x, je zjevnˇe ∅ ∈ x∪ {x}.

2. Zvolme x libovolnˇe, ale pevnˇe. Formuli dokazujeme indukc´ı dle y. Je-li y =∅, nen´ı co dokazovat. Necht’ formule plat´ı pro y, dok´aˇzeme ji proy∪ {y}.

Necht’ x ∈ y ∪ {y}. Pak bud’ x ∈ y a tedy dle indukˇcn´ıho pˇredpokladu x∪ {x} ∈y ⊆ y∪ {y}, nebo x = y a pak x∪ {x} = y∪ {y}. V obou pˇr´ıpadech x∪ {x} ≤y∪ {y}.

3. Prox=y je to trivi´aln´ı, dokazujeme to indukc´ı dleyprox∈y: proy=∅ nen´ı co dokazovat. Plat´ı-li to proy a je-li x∈y∪ {y}, je bud’ x∈y a pak dle indukˇcn´ıho pˇredpokladux⊆y, nebox=y. V obou pˇr´ıpadechx⊆y⊆y∪ {y}.

4. Indukc´ı: prox=∅ to plat´ı. Necht’x /∈x. Kdybyx∪ {x} ∈x∪ {x}, pak bud’ x∪ {x} ∈ x odkud dle 3. x∪ {x} ⊆ x, nebox∪ {x} ∈ x = x. V obou

pˇr´ıpadechx∈x, spor. 2

TVRZENÍ 1.8.3. (ω,≤) je dobré (a tedy lineárn´ı) uspoˇrádán´ı; je diskrétn´ı, nemá nejvˇetˇs´ı prvek, jeho nejmenˇs´ım prvkem je ˇc´ıslo 0 a(ω,∈) je odpov´ıdaj´ıc´ı ostré uspoˇrádán´ı.

Nav´ıc pro x, y∈ω je x≤y pr´avˇe kdyˇz x⊆y.

(16)

D˚ukaz. ≤je reflexivn´ı z definice. Dle3. lemmatu1.8.2,x≤y implikujex⊆y.

Je-li x≤y≤z a x 6= y, pak x ∈ y ⊆ z, ˇcili x ∈ z a tedy x ≤ z. Tud´ıˇz je

≤ tranzitivn´ı. Slab´a anti-symetrie plyne z tranzitivity a bodu 4. pˇredchoz´ıho lemmatu. Kdyby totiˇz x < y < x, pak by speci´alnˇe x∈ y ⊆ x, tud´ıˇz x ∈ x, spor.

Ze (ω,ˇ ≤) je dobré, neboli ˇze kaˇzdá neprázdná podmnoˇzina u ⊆ ω má ≤- nejmenˇs´ı prvek, ukáˇzeme sporem: Necht’unemá≤-nejmenˇs´ı prvek. Oznaˇcmev mnoˇzinu vˇsech minorant mnoˇzinyu, tj.v ={x∈ω; (∀y ∈u)(x≤y)}. Zˇrejmˇe u∩v=∅(prvek pr˚uniku by byl nejmenˇs´ı vu). Ze stejného d˚uvodu∅ ∈v. Necht’

x∈v. Pak pro kaˇzd´ey ∈uplat´ıx∈y (kdyby x=y, byl by x∈u∩v). Dle bodu2. pˇredchoz´ıho lemmatux∪ {x} ≤y, ˇcilix∪ {x} ∈v. Z principu indukce tedyv=ω a tedyu=∅, spor.

(ω,≤) je tedy lineárn´ı. Kdyˇzx⊆y, je x≤y, neb jinaky < xa tedy y∈y, spor. (ω,≤) nemá nejvˇetˇs´ı prvek, nebot’x < x∪ {x}. Je diskrétn´ı, nebot’ kdyby x < y < x∪ {x}, pakx6=y, a tedyy∈x, ˇcilix < y < x, spor. 2

Operace sˇc´ıtán´ı, násoben´ı a umocˇnován´ı naω zavedeme aˇz pozdˇeji.

Zaveden´ı dalˇs´ıch poˇcetn´ıch obor˚u se v tomto textu podrobnˇe vˇenovat nebudeme. Uved’me pouze, ˇze celá ˇc´ısla Z lze definovat napˇr. jako prvky 2× ω− {h1,0i}, kde dvojice tvaru h0, ni interpretujeme jako nezáporná celá ˇc´ısla a ztotoˇzˇnujeme je s prvky ω, zat´ımco prvky tvaru h1, ni, kde n 6= 0, interpretujeme jako ˇc´ısla záporná. Operace na Z se zavedou jako vhodná rozˇs´ıˇren´ı operac´ı naω. Konstrukce mnoˇzinyracionáln´ıch ˇc´ısel spolu s uspoˇrádán´ım a ob- vyklými tˇelesovými operacemi je naznaˇcena v pˇr´ıkladu1. na konci odstavce1.4.

Reálná ˇc´ısla se v teorii mnoˇzin obvykle konstruuj´ı na základˇe ˇc´ısel racionáln´ıch, napˇr´ıklad pomoc´ı Dedekindových ˇrez˚u.

Neˇzli na mnoˇzinˇe pˇrirozených ˇc´ısel zavedeme obvyklé operace, pod´ıvejme se jak lze v teorii mnoˇzin zachytit pojemkoneˇcnostia prozkoumejme bl´ıˇze koneˇcné mnoˇziny.

1.9 Koneˇ cn´ e mnoˇ ziny

Máme jiˇz k dispozici pˇrirozená ˇc´ısla a um´ıme porovnávat mohutnosti mnoˇzin.

Mohli bychom tedy ˇr´ıci, ˇze koneˇcné mnoˇziny jsou právˇe ty, jeˇz maj´ı stejnou mohutnost, jako nˇejaké pˇrirozené ˇc´ıslo. To se vˇsak jako definice ukazuje z mnoha d˚uvod˚u nepˇr´ıliˇs výhodné. Jedn´ım z nich je, ˇze se taková definice kromˇe dané mnoˇziny odkazuje na dalˇs´ı objekt, konkrétnˇe mnoˇzinu pˇrirozených ˇc´ısel. Zvol´ıme proto jinou definici, s n´ıˇz pˇriˇsel Tarski a jeˇz umoˇzˇnuje stanovit koneˇcnost mnoˇziny pouze na základˇe struktury j´ı samé.

Rekneme, ˇˇ ze mnoˇzinaxjekoneˇcná(znaˇc´ıme Fin(x)), jestliˇze kaˇzdý neprázdný systém jej´ıch podmnoˇzin y ⊆ P(x), y 6= ∅, obsahuje vzhledem k inkluzi mi- nimáln´ı prvek, tj. existujeu∈y tak, ˇze pro ˇzádnév∈ynen´ıv⊂u.Intuitivnˇe:

mnoˇzina je koneˇcná, jestliˇze z neprázdné mnoˇziny jej´ıch podmnoˇzin m˚uˇzeme vˇzdy vybrat nˇekterou s mimimáln´ım poˇctem prvk˚u.

(17)

Vˇsimnˇeme si, ˇze ˇzádná induktivn´ı mnoˇzina x nen´ı koneˇcná, nebot’ ω ⊆ x a tud´ıˇz (neprázdný) systém y = {x−n; n ∈ ω} ⊆ P(x) nemá minimáln´ı prvek (pron ∈ ω je totiˇz n ∈x−n a tud´ıˇz x−n ⊃ x−(n∪ {n})∈ y, coˇz znamená, ˇze ˇzádnéx−nnen´ı minimáln´ı vy).Intuitivnˇe: odeb´ırán´ım koneˇcných podmnoˇzin nekoneˇcné mnoˇziny z´ıskáme systém jej´ıch podmnoˇzin, z nichˇz ˇzádná nemá minimáln´ı poˇcet prvk˚u.

Necht’ ∅ 6=y ⊆ P(x) ay⁰ ={x−u; u∈y}. Paku∈y je minimáln´ı prvek (y,⊆) právˇe kdyˇzx−uje maximáln´ı prvek (y⁰,⊆). Kdybychom tedy v definici Fin nahradili slovo minimáln´ı slovem maximáln´ı, z´ıskali bychom ekvivalentn´ı definici. Speciálnˇe, kaˇzdý neprázdný systém podmnoˇzin koneˇcné mnoˇziny má vzhledem k inkluzi maximáln´ı prvek.

Tˇr´ıdu vˇsech koneˇcn´ych mnoˇzin znaˇc´ıme Fin.

V ˇETA 1.9.1. Plat´ı:

1. (a⊂b∧Fin(b))→a≺b 2. (Fin(a)∧b⊆a)→Fin(b) 3. (Fin(a)∧a≈b)→Fin(b) 4. (Fin(a)∧b4a)→Fin(b) 5. (Fin(a)∧Fin(b))→Fin(a∪b) 6. Fin(a)→(∀b)Fin(a∪ {b}) 7. ω⊆Fin

8. Princip indukce pro koneˇcn´e mnoˇziny

(∅ ∈A∧(∀a∈A)(∀b)(a∪ {b} ∈A))→Fin⊆A 9. Fin(a)→Fin(P(a))

10. Fin(a)∧Fin(b)→Fin(a×b) 11. Fin(a)∧Fin(b)→Fin(^ab))

12. (a6=∅ ∧Fin(a)∧(∀z∈a)Fin(z))→Fin(S a) 13. Fin(a)→(∀z)(a4z∨z4a)

14. Fin(a)↔(∃n∈ω)(a≈n) 15. (∀n, m∈ω)(n≈m→n=m)

D˚ukaz. 1. Pˇredpokládejme, ˇzeb je koneˇcná a pˇresto existuje nˇejaká jej´ı vlastn´ı podmnoˇzinaa⊂b, taková, ˇze¬(a≺b). Jelikoˇza4b, je nutnˇea≈b. Uvaˇzujme mnoˇzinuy vˇsech takových vlastn´ıch podmnoˇzin mnoˇzinyb, tj.y={a⊂b; a≈ b}. Dle pˇredpokladu je∅ 6=y⊆ P(b) aymá tedy d´ıky koneˇcnostib(v˚uˇci inkluzi) minimáln´ı prvek a0 ∈ y. Je-li f : b → a0 vzájemnˇe jednoznaˇcné zobrazen´ı, je

(18)

f[a0] ⊂a0 (nebot’ a0 ⊂b) a pˇritomf a0 je vzájemnˇe jednoznaˇcné zobrazen´ı a0 na f[a0]. Odtud vyplývá, ˇze f[a0]≈a0 ≈b, ˇcili f[a0]∈ y, coˇz je ve sporu s minimalitoua0.

2. plyne ihned z definice.

3. Necht’ f : b → a je vzájemnˇe jednoznaˇcné zobrazen´ı a y ⊆ P(b). Pak y⁰ ={f[x]; x∈ y} ⊆ P(a) a snadno se ovˇeˇr´ı, ˇze je-lif[z] minimáln´ı prvek y⁰ (vzhledem k inkluzi), jez minimáln´ı prveky (vzhledem k inkluzi).

4. je d˚usledkem2. a3.

5. Necht’∅ 6=y⊆ P(a∪b). Oznaˇcmey₁={x∩a; x∈y} ⊆ P(a). Zˇrejmˇe je y₁neprázdná (nebot’ je takováy) a má tud´ıˇz d´ıky Fin(a) minimáln´ı prvek, a to tvarux1∩apro nˇejakéx1∈y. Poloˇzmey2 ={x∩b; x∈y∧x⊆x1}. Zˇrejmˇe

∅ 6=y2 ⊆ P(b) a má tedy d´ıky Fin(b) nˇejaký minimáln´ı prvek z⁰ tvaru x2∩b pro nˇejakéx2⊆x1,x2∈y. Dokáˇzeme, ˇzex2 je minimáln´ı prveky. Bud’x∈y, x⊆x2. Pak x⊆x1, a tedyx∩b∈y2, z ˇcehoˇz plyne, ˇze x∩b=x2∩b, jelikoˇz x2∩bje minimáln´ı vy2. Podobnˇe dostanemex∩a=x1∩a=x2∩a. Protoˇze x, x2⊆a∪b, jex=x2.

6. Snadno se ovˇeˇr´ı, ˇze pro kaˇzd´ey je Fin({y}). Zbytek plyne5.

7. se dok´aˇze matematickou indukc´ı podle6.

8. Necht’ Asplˇnuje pˇredpoklad uveden´e implikace. Dok´aˇzeme, ˇze Fin ⊆A.

Sporem. Necht’ a ∈ Fin, ale a /∈ A. Uvaˇzujme y = {b ⊆ a; b /∈ A}. Jelikoˇz a ∈ y, je y neprázdná a má tedy minimáln´ı prvek b. Zˇrejmˇe je b 6= ∅ nebot’

∅ ∈ A. Existuje tedy nˇejaké x ∈ b. Pak ale b− {x} ∈ A nebot’ v opaˇcném pˇr´ıpadˇe dostáváme spor s minimalitoub. Z vlastnost´ı tˇr´ıdy A ovˇsem plyne, ˇze (b− {x})∪ {x}=b∈A, coˇz je spor.

9. dokáˇzeme podle principu indukce pro koneˇcné mnoˇziny. Zˇrejmˇe Fin(P(∅)), nebot’P(∅) ={∅}. Zbývá dokázat, ˇze je-li Fin(a) a Fin(P(a)), pak pro libovolné b je Fin(P(a∪ {b})). To plyne z 5 a toho, ˇze P(a∪ {b}) = P(a)∪c, kde c={x∪ {b}; x∈ P(a)} ≈ P(a), a tedy Fin(c) dle3.

10. plyne z9. a toho, ˇze a×b⊆ P(P(a∪b)).

11. plyne z9. a toho, ˇze ^ab⊆ P(a×b).

12. Tvrzen´ı dokáˇzeme indukc´ı pro koneˇcné mnoˇziny. Proa=∅tvrzen´ı zˇrejmˇe plat´ı. Plat´ı-li dále tvrzen´ı pro nˇejakou koneˇcnou mnoˇzinua, jej´ıˇz vˇsechny prvky jsou koneˇcné, plat´ı i proa∪ {b} kdeb je koneˇcná, nebot’S

(a∪ {b}) =b∪S a, pˇriˇcemˇz na pravé stranˇe je sjednocen´ı dvou koneˇcných mnoˇzin, tedy koneˇcná mnoˇzina dle5.

13. Indukc´ı pro koneˇcné mnoˇziny: zˇrejmˇe∅4z pro kaˇzdéz. Plat´ı-liz 4a, je z 4a∪ {x} pro libovolné x. Plat´ı-li naopak z ≺ a, bud’ f : a → z prosté zobrazen´ı. Jelikoˇza6≈z, nen´ıf na, a tedy existuje prveky∈z−rng(f). Poloˇzme f⁰=f∪ {hx, yi}. Z´ıskali jsme prosté zobrazen´ıf⁰:a∪ {x} →z, ˇcilia4z, ˇc´ımˇz je dokázán potˇrebný indukˇcn´ı krok.

14. Na jednu stranu z7v´ıme, ˇze kaˇzdé pˇrirozené ˇc´ıslonje koneˇcná mnoˇzina a tud´ıˇz je-lia≈n, je rovnˇeˇzakoneˇcná mnoˇzina. Obrácenou implikaci dokáˇzeme opˇet indukc´ı pro koneˇcné mnoˇziny. Je-li a =∅ pravá strana ekvivalence plat´ı triviálnˇe (staˇc´ı poloˇzitn= 0). Ukáˇzeme, ˇze je-lia≈na xlibovolná mnoˇzina, plat´ı (∃m ∈ ω)(m ≈ a∪ {x}). Pokud x ∈ a, je a∪ {x} = a a staˇc´ı poloˇzit m=n. V opaˇcném pˇr´ıpadˇe (x /∈a), poloˇzmem=n+ 1. Je-li nyn´ıf vzájemnˇe

(19)

jednoznaˇcné zobrazen´ıf : a→ n, je f⁰ =f ∪ {hx, ni} vzájemnˇe jednoznaˇcné zobrazen´ıa∪ {x}nam.

15. Matematickou indukc´ı dle n. Pro n = 0 je tvrzen´ı triviáln´ı. Necht’ n splˇnuje formuli (∀m)(n ≈m→ n =m). Dokáˇzeme, ˇze ji splˇnuje téˇzn+ 1 = n∪ {n}. Necht’ n+ 1 ≈m. Pak zˇrejmˇe m 6= 0 (nebot’ n+ 16= ∅). Indukc´ı se snadno ukáˇze, ˇze je-li 06=m ∈ω, je m tvaruk∪ {k} pro nˇejaké k ∈ω. Bud’

nyn´ıf : n+ 1→ k+ 1 vzájemnˇe jednoznaˇcné zobrazen´ı. Pˇr´ıpadnou zámˇenou funkˇcn´ı hodnotyfv bodechnaf⁻¹(k) z´ıskáme vzájemnˇe jednoznaˇcné zobrazen´ı f⁰ :n+ 1→k+ 1 takové, ˇze f(n) = k. Odtud vyplývá, ˇzef⁰ nje vzájemnˇe jednoznaˇcné zobrazen´ınnak, ˇcilin≈ka podle indukˇcn´ıho pˇredpokladun=k.

Odtud plyne, ˇze n+ 1 =k+ 1 =m. T´ım je d˚ukaz hotov. 2 POZN ÁMKA 1.9.2. Bod1. pˇredchoz´ı vˇety formuluje zaj´ımavou vlastnost koneˇcných mnoˇzin, totiˇz ˇze jejich vlastn´ı ˇcást je vˇzdy menˇs´ı neˇz celek. Toto tvrzen´ı pouˇzil kdysi k definici koneˇcnosti mnoˇziny Dedekind. Pˇresto je známo, ˇze bez pˇridán´ı dalˇs´ıho axiomu (napˇr. axiomu výbˇeru) nelze dokázat opaˇcnou implikaci, tj. ˇze mnoˇzina, jej´ıˇz kaˇzdá vlastn´ı ˇcást má mohutnost menˇs´ı neˇz celek, je koneˇcná.

Problém spoˇc´ıvá v tom, ˇze pomoc´ı axiom˚u Zermelo-Fraenkelovy teorie nejsme obecnˇe schopni k dané nekoneˇcné mnoˇzinˇe nalézt zobrazen´ı, jeˇz by ji vzájemnˇe jednoznaˇcnˇe zobrazilo na jej´ı vlastn´ı ˇcást (pˇrestoˇze pro vˇsechny ,,bˇeˇzné” ne- koneˇcné mnoˇziny, jako je tˇreba ω, taková zobrazen´ı nalézt um´ıme).

Z pˇredchoz´ı vˇety v´ıme, ˇze kaˇzdé pˇrirozené ˇc´ıslo je koneˇcné, ˇze sjednocen´ı, kartézský souˇcin i mnoˇzinová mocnina dvou koneˇcných mnoˇzin jsou koneˇcné mnoˇziny a ˇze kaˇzdá koneˇcná mnoˇzina má mohutnost právˇe jednoho pˇrirozeného ˇc´ısla. Na mnoˇzinˇeωm˚uˇzeme tedy operacesˇc´ıtán´ı,násoben´ıaumocˇnován´ızavést následuj´ıc´ımi vztahy (pron, m∈ω):

n+m=k∈ω ↔ k≈n]m, n·m=k∈ω ↔ k≈n×m,

n^m=k∈ω ↔ k≈^mn.

V kaˇzdém z nich je ˇc´ıslo k, udávaj´ıc´ı výsledek uvedené operace, urˇceno jedno- znaˇcnˇe. Poznamenejme, ˇze takto definovaná operace sˇc´ıtán´ı je v souladu s námi jiˇz dˇr´ıve pˇrijatým znaˇcen´ımn+ 1 =n∪ {n}.

Nen´ı tˇeˇzké dokázat, ˇze pro pˇrirozená ˇc´ısla v teorii mnoˇzin s výˇse uvedenými operacemi a uspoˇrádán´ım daným relac´ı náleˇzen´ı (tj.n < mprávˇe kdyˇzn∈m), plat´ı vˇsechny axiomy Peanovy aritmetiky. Na druhou stranu jsou známá tvrzen´ı o pˇrirozených ˇc´ıslech, jeˇz jsou dokazatelná v teorii mnoˇzin, ale v Peanovˇe aritmetice je nelze dokázat ani vyvrátit. Nahrad´ıme-li vˇsak v teorii mnoˇzin axiom nekoneˇcna jeho negac´ı, situace se zmˇen´ı. V takové ,,teorii koneˇcných mnoˇzin”

jsou o pˇrirozených ˇc´ıslech dokazatelná právˇe tatáˇz tvrzen´ı jazyka aritmetiky, jako v Peanovˇe aritmetice. To poukazuje na zaj´ımavý fakt, totiˇz ˇze zkoumán´ım ne- koneˇcných mnoˇzin lze z´ıskat nové poznatky o mnoˇzinách koneˇcných (pˇrirozených ˇc´ıslech), jeˇz by nám jinak z˚ustaly skryty.

(20)

1.10 Spoˇ cetn´ e mnoˇ ziny

Rekneme, ˇˇ ze mnoˇzina je (nekoneˇcnˇe) spoˇcetná, má-li stejnou mohutnost jako mnoˇzina pˇrirozených ˇc´ısel. ˇRekneme, ˇze mnoˇzina jenejvýˇse spoˇcetná, je-li bud’to koneˇcná nebo spoˇcetná. Mnoˇzina jenespoˇcetná, je-li nekoneˇcná, ale nen´ı spoˇcetná.

Z Cantorovy vˇety v´ıme, ˇze nespoˇcetn´a je napˇr. mnoˇzinaP(ω).

Snadno se nahlédne, ˇze sjednocen´ı dvou nejvýˇse spoˇcetných mnoˇzin je opˇet nejvýˇse spoˇcetná mnoˇzina. Indukc´ı lze toto tvrzen´ı rozˇs´ıˇrit na libovolný koneˇcný poˇcet nejvýˇse spoˇcetných mnoˇzin. Otázku, zda sjednocen´ı spoˇcetnˇe mnoha nejvýˇse spoˇcetných mnoˇzin je stále spoˇcetné, nelze rozhodnout bez nˇejaké formy axiomu výbˇeru, o nˇemˇz se zm´ın´ıme pozdˇeji.

Pˇ r´ıklady

1. ω×ω≈ω

Vzájemnˇe jednoznaˇcné zobrazen´ı meziω×ωaωzprostˇredkovává napˇr´ıklad funkce (x+y)(x+y+1)

2 +x. Jeˇstˇe jednoduˇsˇs´ı d˚ukaz umoˇzˇnuje vˇeta Cantor- Bernsteinova. Staˇc´ı nal´ezt prost´a zobrazen´ıf :ω×ω→ωag:ω→ω×ω.

Ta lze definovat napˇr´ıklad takto: f(hn, mi) = 2ⁿ3^ma g(n) =hn, ni.

2. Z,Qjsou spoˇcetn´e.Rje nespoˇcetn´a aR≈ P(ω)≈^ω2.

Prvn´ı dva vztahy vyplývaj´ı snadno z naznaˇcených konstrukc´ı a pˇredeˇslého tvrzen´ı. NespoˇcetnostRlze nahlédnout nˇekolika zp˚usoby. Jednou moˇznost´ı je hned dokázat, ˇzeR≈ P(ω) a pouˇz´ıt Cantorovu vˇetu. Druhou moˇznost nab´ız´ı následuj´ıc´ı úvaha: Kdybyω≈R, ˇslo byvˇsechnareálná ˇc´ısla oˇc´ıslovat pˇrirozenými ˇc´ısly a seˇradit do posloupnosti{rn}_n∈ωtak, aby ˇzádné reálné ˇ

c´ıslo nezbylo. Definujme nyn´ıˇc´ıslos, dané desetinným rozvojem 0, s0s1s2. . ., kdesn jsou jednotlivé ˇc´ıslice zvolené takto:sn = 2 pokudn+ 1-n´ı ˇc´ıslice za desetinou ˇcárkou v rozvoji ˇc´ısla rn je vˇetˇs´ı neˇz 5 a sn = 7, je-li tato ˇ

c´ıslice menˇs´ı neˇz 5. Uvedený rozvoj urˇcuje jednoznaˇcnˇe nˇejaké reálné ˇc´ıslo s. Pˇritom se toto ˇc´ıslo liˇs´ı od kaˇzdéhorn(nan+ 1-n´ım desetinném m´ıstˇe).

Je tedy s 6= rn pro vˇsechna n ∈ ω, coˇz je ve sporu s pˇredpokladem, ˇze posloupnost{rn}n∈ω obsahuje vˇsechna re´aln´a ˇc´ısla.

Vztah R ≈ P(ω) m˚uˇzeme od˚uvodnit tˇreba takto: Kaˇzdé reálné ˇc´ıslo r je supremem mnoˇziny racionáln´ıch ˇc´ısel menˇs´ıch neˇz r. Z toho vyplývá, ˇ

ze zobrazen´ı pˇriˇrazuj´ıc´ı ˇc´ıslurprávˇe tuto podmnoˇzinuQje prosté, a tedy R4P(Q). Obrácenou subvalenci lze nahlédnout napˇr´ıklad takto: z tvrzen´ı 1.6.3v´ıme, ˇze P(ω)≈^ω2. Staˇc´ı tedy ukázat, ˇze reálných ˇc´ısel je alespoˇn tolik, jako nekoneˇcných posloupnost´ı nul a jedniˇcek. Pro f :ω → {0,1}

poloˇzme r = P∞ n=0

2f(n)

3ⁿ . Snadno se ovˇeˇr´ı, ˇze dvˇe r˚uzná zobrazen´ı urˇc´ı t´ımto zp˚usobem dvˇe r˚uzná reálná ˇc´ısla. Máme tak prosté zobrazen´ı^ω2 doR. Mimochodem, z´ıskané obrazy tvoˇr´ı zaj´ımavou podmnoˇzinu reálných ˇ

c´ısel zvanou Cantorovo diskontinuum. Lze ji z´ıskat tak´e tak, ˇze z jed- notkov´eho intervalu ,,vylom´ıme” jeho prostˇredn´ı tˇretinu, pak prostˇredn´ı

(21)

tˇretiny obou zbylých kus˚u, a tak stále dále, aˇz do nekoneˇcna. To, co zbude, je nespoˇcetná mnoˇzina, jej´ıˇz prvky lze jednoduˇse vyjádˇrit jako výˇse uvedené sumy. V˚uˇci uspoˇrádán´ı reálných ˇc´ısel tvoˇr´ı Cantorovo diskontinuum úplný svaz. Cantorovo diskontinuum má ˇradu dalˇs´ıch zaj´ımavých a d˚uleˇzitých vlastnost´ı, o nich vˇsak aˇz jindy.

3. Reálné ˇc´ıslo, jeˇz je koˇrenem nˇejaké rovnice

a_nxⁿ+a_n−1xⁿ⁻¹+. . .+a₁x+a₀= 0,

s celoˇc´ıselnými koeficienty, se nazývá algebraické. Reálné ˇc´ıslo, které nen´ı koˇrenem ˇzádné takové rovnice, se nazývá transcendentn´ı. Otázka, zda existuje nˇejaké transcendentn´ı ˇc´ıslo z˚ustávala dlouho otevˇrená. Dodnes je známo jen nˇekolik konkrétn´ıch pˇr´ıklad˚u transcendentn´ıch ˇc´ısel, mezi nˇeˇz patˇr´ı ˇc´ıslaπae. Dokázat o nˇejakém konkrétn´ım ˇc´ısle, ˇze je transcendentn´ı, je nicménˇe dosti obt´ıˇzné.

Následuj´ıc´ı jednoduchá úvaha dokazuje existenci transcendentn´ıch ˇc´ısel, aniˇz by ukázala jediný konkrétn´ı pˇr´ıklad takového ˇc´ısla. Jedná se o pˇr´ıklad takzvanéhoexistenˇcn´ıho ˇcinekonstruktivn´ıho d˚ukazu, tj. d˚ukazu, v nˇemˇz je existence objekt˚u urˇcitého typu dokázána, aniˇz by byl nalezen jediný konkrétn´ı exempláˇr.

Kaˇzdá z uvedených rovnic je urˇcena posloupnost´ı celoˇc´ıselných koefici- ent˚uha0, . . . , ani. Zvolme libovolné prosté zobrazen´ıf :Z→ωa poloˇzme g(ha0, a₁, . . . , a_ni) = p^f(a₀ ⁰⁾·p^f(a₁ ¹⁾. . .·p^f(an ⁿ⁾, kde p_k je k-té prvoˇc´ıslo (prvoˇc´ısla tvoˇr´ı spoˇcetnou podmnoˇzinuω). Zobrazen´ıgpˇriˇrazuje posloup- nostiha₀, . . . , a_nipˇrirozené ˇc´ıslo a je zˇrejmé, ˇze dvˇema r˚uzným posloup- nostem ha₀, . . . , a_ni, hb₀, . . . , b_mi, kde a_n 6= 0 a b_m 6= 0 a a_k 6= b_k pro nˇejakék≤m, n, jsou zobrazen´ımg pˇriˇrazena r˚uzná ˇc´ısla. Jelikoˇz uvedené posloupnosti urˇcuj´ı právˇe vˇsechny rovnice s celoˇc´ıselnými koeficienty. je takových rovnic spoˇcetnˇe mnoho. Pˇritom kaˇzdá z nich, jak v´ıme z algebry, má pouze koneˇcnˇe mnoho reálných koˇren˚u (reálný polynomn-tého stupnˇe má nejvýˇse n reálných koˇren˚u). Odtud jiˇz snadno plyne, ˇze algebraické rovnice s celoˇc´ıselnými koeficienty mohou m´ıt dohromady nejv´ıce spoˇcetnˇe mnoho koˇren˚u, a tedy existuje nejvýˇse spoˇcetnˇe mnoho algebraických ˇc´ısel.

Re´aln´ych ˇc´ısel je vˇsak nespoˇcetnˇe mnoho, tud´ıˇz mus´ı existovat dokonce ne- spoˇcetnˇe mnoho ˇc´ısel, jeˇz jsou transcendentn´ı.

4. Necht’C(R) znaˇc´ı mnoˇzinu vˇsech spojitých reálných funkc´ı. Je známo, ˇze kaˇzdá taková funkce f : R→Rje jednoznaˇcnˇe urˇcena svými hodnotami na Q. Odtud plyne, ˇze C(R) 4 ^QR. Pˇritom kaˇzdá konstantn´ı funkce je spojitá, tedy R4C(R). JelikoˇzQ≈ω,R≈^ω2, aω≈ω×ω, dostáváme

ω2≈R4C(R)4^QR≈^ω(^ω2)≈^ω×ω2≈^ω2.

Spojitých reálných funkc´ı je tedy stejnˇe jako reálných ˇc´ısel. To je pomˇernˇe pˇrekvapivé, nebot’ vˇsech reálných funkc´ı je^RR≈ P(R), coˇz je (podle Can- torovy vˇety) daleko v´ıc.

(22)

5. Úkol: Zkuste jako d˚usledek pˇredchoz´ıho tvrzen´ı zkonstruovat reálnou funkci, jej´ıˇz graf protne graf kaˇzdé spojité reálné funkce.

1.11 Ordin´ aln´ı ˇ c´ısla

V tomto odd´ılu se budeme vˇenovat ordináln´ım ˇc´ısl˚um, která rozˇsiˇruj´ı obor pˇrirozených ˇc´ısel smˇerem k nekoneˇcným mnoˇzinám. V´ıme jiˇz, ˇze mnoˇzina ω pˇrirozených ˇc´ısel je dobˇre ostˇre uspoˇrádána relac´ı∈, jeˇz naωdefinuje kanonické ostré uspoˇrádán´ı. V´ıme dále, ˇze kaˇzdé pˇrirozené ˇc´ıslo obsahuje (jako své prvky) právˇe vˇsechna ˇc´ısla menˇs´ı. Je-li tedy n ∈m, je n⊆ m a m =S

{n; n ∈m}.

Totéˇz vˇsak plat´ı pro samu mnoˇzinu ω a také pro mnoˇziny ω+ 1 = ω∪ {ω}, ω+ 2 = (ω+ 1)∪ {ω+ 1}, atd., jeˇz m˚uˇzeme pokládat za pˇrirozené prodlouˇzen´ı nekoneˇcné ˇrady 0,1,2, . . ..

Rekneme, ˇˇ ze tˇr´ıdaAjetranzitivn´ı, jestliˇze SA⊆A. To znamená, ˇzeAob- sahuje také vˇsechny prvky svých prvk˚u. Tranzitivn´ım mnoˇzinám na kterých je relace ∈ dobré ostré uspoˇrádán´ı, ˇr´ıkáme ordináln´ı ˇc´ısla, neboli ordinály.

Speciáln´ımi pˇr´ıpady ordináln´ıch ˇc´ısel jsou tedy pˇrirozená ˇc´ısla a dále mnoˇziny ω, ω+ 1,ω+ 2 uvedené výˇse.

V následuj´ıc´ım ukáˇzeme, ˇze relace náleˇzen´ı urˇcuje na oboru ordináln´ıch ˇc´ısel dobré ostré uspoˇrádán´ı. Na tomto oboru dále zavedeme operace sˇc´ıtán´ı, násoben´ı a umocˇnován´ı. Ty budou m´ıt na podoboru pˇrirozených ˇc´ısel vˇsechny své obvyklé vlastnosti.

Na ordináln´ı ˇc´ısla obvykle nahl´ıˇz´ıme jako na typy vˇsech dobrých uspoˇrádán´ı.

Oprávnˇenost tohoto názoru opˇreme o tvrzen´ı, v nˇemˇz ukáˇzeme, ˇze kaˇzdé dobré ostré uspoˇrádán´ı (A,≤) lze izomorfnˇe zobrazit na (α,∈), kdeαje nˇejaký ordinál.

Ordináln´ıˇc´ısla bývá zvykem oznaˇcovat malými ˇreckými p´ısmeny. Tˇr´ıdu vˇsech ordináln´ıch ˇc´ısel znaˇc´ımeOn

TVRZEN´I 1.11.1.

1. Pro kaˇzd´eα∈On plat´ıα /∈α.

2. Kaˇzdý prvek ordináln´ıho ˇc´ısla je ordináln´ı ˇc´ıslo.

3. Jsou-liα, βordináln´ı ˇc´ısla, pakα⊆β právˇe tehdy, kdyˇzα∈β neboα=β. 4. Je-li αordináln´ı ˇc´ıslo je (α,⊆)dobré uspoˇrádán´ı.

5. (On,∈)je dobré ostré uspoˇrádán´ı a(On,⊆je odpov´ıdaj´ıc´ı dobré neostré uspoˇrádán´ı.

6. On je vlastn´ı tˇr´ıda.

D˚ukaz. Ad1. Kdybyα∈α, nebylo by uspoˇrádán´ı (α,∈) ostré.

Ad 2. Bud’ α ordináln´ı ˇc´ıslo a x∈ α. Jelikoˇz α je tranzitivn´ı mnoˇzina, je x⊆ α, a x je tedy také dobˇre uspoˇrádáno relac´ı∈. Nyn´ı, je-li z ∈ y ∈ x, je y ∈ α, a tedy téˇz z ∈ α. Jelikoˇz∈ je na αostré uspoˇrádán´ı a tud´ıˇz speciálnˇe tranzitivn´ı relace, jez∈x.

(23)

Ad 3. Je-li α ∈ β, je α ⊆ S

β ⊆β. Naopak, necht’ α ⊆ β a α6= β. Pak β−α6=∅a existuje nejmenˇs´ı prvek γmnoˇzinyβ−α6=∅. Uk´aˇzeme, ˇzeα=γ.

Je-liδ ∈ γ, je δ ∈β a nav´ıcδ ∈α, jelikoˇzγ je nejmenˇs´ı prvek β−α. Tud´ıˇz γ⊆α. Je-li nyn´ıδ∈α, je téˇzδ∈βa nutnˇe plat´ı jeden ze vztah˚uγ∈δ,γ=δˇci δ∈γ, nebot’∈je ostré lineárn´ı uspoˇrádán´ı naβ. Je zˇrejmé, ˇze ˇzádný z prvn´ıch dvou vztah˚u nastat nem˚uˇze, jelikoˇzδ∈α, zat´ımcoγ /∈α, tud´ıˇzδ∈γ a γ⊆α, ˇc´ımˇz je dokázána i druhá potˇrebná inkluze.

Tvrzen´ı (4) je okamˇzit´ym d˚usledkem pˇredchoz´ıch dvou.

Ad5. ˇZe (On,∈) je ostré uspoˇrádán´ı plyne ihned z tranzitivity ordinál˚u a bodu (1). Dále dokáˇzeme linearitu ∈ naOn. Necht’α, β ∈On, α6= β. Nen´ı- li α ∈ β, neplat´ı podle bodu (3) ani α ⊆ β a existuje tud´ıˇz nejmenˇs´ı prvek γ∈α−β. Pak γ⊆β, nebot’ je-li δ ∈γ, je δ∈α∩β. Jelikoˇzγ /∈β, je podle bodu (3) nutnˇeγ=β, a tedy β∈α. Nyn´ı jiˇz snadno ovˇeˇr´ıme, ˇze uspoˇrádán´ı∈ je dobré naOn. Bud’x⊆On neprázdná a α∈x. Ukáˇzeme, ˇze má minimáln´ı prvek. Ten je d´ıky linearitˇe nejmenˇs´ı. Je-liα∩x=∅, jeαzˇrejmˇe∈-minimáln´ı v x. Je-li naopakα∩x6=∅, pak existuje∈-nejmenˇs´ı prvekγmnoˇzinyα∩x, jenˇz je d´ıky tranzitivitˇeα∈-minimáln´ı vx.

Tvrzen´ı (5) nyn´ı plyne bezprostˇrednˇe z dok´azan´eho a z (3).

Ad6. Tˇr´ıdaOnje dle (2) tranzitivn´ı, a dle (5) dobˇre ostˇre uspoˇrádaná relac´ı náleˇzen´ı. KdybyOnbyla mnoˇzina, byla by ordináln´ım ˇc´ıslem, a tedy by platilo

On∈On. To je ve sporu s (1). 2

Na tˇr´ıdˇe ordin´aln´ıch ˇc´ısel definujeme relaci≤pˇredpisem α≤β↔^df α∈β∨α=β.

Z pˇredchoz´ıho tvrzen´ı plyne, ˇze relace≤je dobré uspoˇrádán´ı na tˇr´ıdˇe ordináln´ıch ˇc´ısel. Odpov´ıdaj´ıc´ı ostrá relace α < β je pouze jiným zápisem vztahu α ∈ β.

Z dokázaného tvrzen´ı nav´ıc plyne, ˇze pro libovolná ordináln´ı ˇc´ısla α, β plat´ı α≤β právˇe tehdy, kdyˇzα⊆β. Následuj´ıc´ı tvrzen´ı je natolik zˇrejmé, ˇze je nen´ı tˇreba dokazovat.

TVRZEN´I 1.11.2.

1. Kaˇzdá neprázdná tˇr´ıda ordináln´ıch ˇc´ısel má nejmenˇs´ı prvek. Podrobnˇeji, je-li ∅ 6= X ⊆On, je T

X ∈ On nejmenˇs´ı prvek tˇr´ıdy X v uspoˇr´ad´an´ı (On,≤).

2. Kaˇzdá neprázdná mnoˇzina ordináln´ıch ˇc´ısel má supremum. Podrobnˇeji, je-li ∅ 6=⊆On, je S

x= sup_(On,≤)(x)∈On.

Prvn´ım ordináln´ım ˇc´ıslem v uspoˇrádán´ı≤je prázdná mnoˇzina∅, tedy pˇrirozené ˇc´ıslo 0. Dále následuj´ı pˇrirozená ˇc´ısla (prvky ω) 1,2, . . . v obvyklém poˇrad´ı.

Následn´ıkem ordináln´ıho ˇc´ısla α je ordináln´ı ˇc´ıslo α+ 1 = α∪ {α}, jeˇz je nejmenˇs´ım ordináln´ım ˇc´ıslem vˇetˇs´ım neˇz α. ˇR´ıkáme, ˇze ordináln´ı ˇc´ıslo je limitn´ı, nen´ı-li následn´ıkem ˇzádného ordináln´ıho ˇc´ısla. ˇC´ısl˚um, která nejsou limitn´ı ˇr´ıkáme téˇzizolovaná. Limitn´ı ordináln´ı ˇc´ıslo je sjednocen´ım (a tedy supremem) vˇsech ˇc´ısel, která je pˇredcházej´ı, tedy α = S

α. V tomto smyslu je i 0

(24)

limitn´ı ordinál, vˇsechna ostatn´ı pˇrirozená ˇc´ısla jsou izolovaná. Nejmenˇs´ı limitn´ı ordinál vˇetˇs´ı neˇz 0 jeω, a je to supremum mnoˇziny pˇrirozených ˇc´ısel.

1.11.3 Transfinitn´ı indukce a rekurze

Nyn´ı se dostáváme ke dvˇema matematickým princip˚um, formuluj´ıc´ım d˚uleˇzitou vlastnost ordináln´ıch resp. pˇrirozených ˇc´ısel. Jde o principytransfinitn´ı indukce atransfinitn´ı rekurze. Dˇr´ıve uvedený principmatematické indukce je d˚usledkem obecnˇejˇs´ıho principu transfinitn´ı indukce.

Princip transfinitn´ı indukce. Je-li A tˇr´ıda ordináln´ıch ˇc´ısel taková, ˇze pro kaˇzdý ordinál αplat´ı

α⊆A→α∈A, (1.2)

pakA=On.

Princip transfinitn´ı rekurze. Necht’Gje (tˇr´ıdové) zobrazen´ı naVaD∈On neboD=On. Potom existuje právˇe jedno zobrazen´ıF, takové, ˇzedom(F) =D, pˇriˇrazuj´ıc´ı kaˇzdému ordinálu α∈D mnoˇzinu

F(α) =G(F α). (1.3)

D˚ukaz principu transfinitn´ı indukce. Sporem: Bud’A⊆Ontˇr´ıda splˇnuj´ıc´ı (1.2), takov´a ˇzeA6=On. Pak ovˇsem existuje nejmenˇs´ı prvekαtˇr´ıdyOn−A. Zˇrejmˇe

α⊆Aa podle (1.2)α∈A. Spor! 2

D˚ukaz principu transfinitn´ı rekurze. Uvaˇzujme tˇr´ıdu Y vˇsech funkc´ıf, jejichˇz definiˇcn´ım oborem je nˇejak´e ordin´aln´ı ˇc´ıslo α⊆D a pro nˇeˇz plat´ı

α∈dom(f)→f(α) =G(f α). (1.4) O tˇr´ıdˇeY dok´aˇzeme n´asleduj´ıc´ı dvˇe tvrzen´ı:

1. (Y,⊆) je lineárn´ı uspoˇrádán´ı

2. Pro kaˇzd´eα∈D existujef ∈Y tak, ˇzeα∈dom(f).

Z nich jiˇz snadno vypl´yv´a, ˇzeF=S

Y je zobrazen´ı s poˇzadovan´ymi vlastnostmi.

Ad (1). Bud’te f, g ∈ Y a oznaˇcme δ_f = dom(f) a δ_g = dom(g). Podle definiceY jsouδ_f, δ_g ordin´aln´ı ˇc´ısla, tud´ıˇz plat´ı aspoˇn jeden ze vztah˚uδ_f ≤δ_g, δ_g≤δ_f. Pˇredpokl´adejme napˇr´ıklad, ˇzeδ_f ≤δ_ga oznaˇcmez={α∈δ_f; f(α)6=

g(α)}. Je-liz=∅, je zˇrejmˇef ⊆g. V opaˇcném pˇr´ıpadˇe existuje nejmenˇs´ı prvek γ mnoˇzinyz ⊆D. To ovˇsem znamená, ˇze f(α) =g(α) pro kaˇzdé α∈γ, tedy f γ=gγ. Pak takéf(γ) =G(f γ) = G(g γ) = g(γ) podle (1.4). To je vˇsak spor sγ∈z.

Ad (2). OznaˇcmeY⁰ =S{dom(f); f ∈Y}. Pˇredpokl´adejme, ˇzeD−Y⁰ 6=∅, vyvod´ıme spor. Bud’ γ nejmenˇs´ı prvek tˇr´ıdy D−Y⁰. Zˇrejmˇe γ ⊆ Y⁰. Snadno se nahl´edne, ˇzef =S

{g∈Y; dom(g)∈γ} je funkce, dom(f) =γ a f splˇnuje (1.4). Speci´alnˇe f ∈ Y. Poloˇz´ıme-li nyn´ıf⁰ = f ∪ {hγ, G(f γ)i}, je zˇrejmˇe f⁰∈Y,γ∈dom(f⁰) =γ+ 1 a tud´ıˇzγ∈Y⁰. Spor! 2

(25)

Princip transfinitn´ı indukce lze ekvivalentnˇe formulovat takto: Je-liA tˇr´ıda ordináln´ıch ˇc´ısel taková, ˇze pro kaˇzdý ordinálαplat´ı

1. 0∈A,

2. α∈A→α∪ {α} ∈A,

3. (∀β < α)(β∈A)→α∈A, je-liαlimitn´ı, pakA=On.

Chceme-li ukázat, ˇze vlastnost vyjádˇrená formul´ıφ(x) plat´ı pro kaˇzdé or- dináln´ı ˇc´ıslo, staˇc´ı ovˇeˇrit uvedené tˇri podm´ınky (resp. podm´ınku (1.2)) pro tˇr´ıdu A={α; α∈On∧φ(α)}.

Casto nen´ı potˇˇ reba indukci provádˇet pro vˇsechna ordináln´ı ˇc´ısla, ale staˇc´ı nám, omez´ıme-li se na ˇc´ısla menˇs´ı neˇz nˇejaký daný limitn´ı ordinál. Je-li λ or- dináln´ı ˇc´ıslo aA⊆λmnoˇzina taková, ˇze pro kaˇzdé ordináln´ı ˇc´ısloα < λplat´ı (1.2), pakA=λ.

Princip transfinitn´ı rekurze zaruˇcuje existenci zobrazen´ıF, jehoˇz hodnota pro ordináln´ı ˇc´ısloαzávis´ı na úsekuF α, tedy na hodnotách (pr˚ubˇehu) funkce F pro vˇsechna ordináln´ı ˇc´ısla menˇs´ı, neˇzα. FunkciGv (1.3) se ˇr´ıkákonstruuj´ıc´ı funkce.

Jako snadnou aplikaci principu transfinitn´ı rekurze dokaˇzme následuj´ıc´ı tvrzen´ı, které ukazuje, ˇze tˇr´ıdaOn pˇredstavuje úplnou ˇskálu vˇsech typ˚u dobrých uspoˇrádán´ı:

TVRZEN´I 1.11.4 (o ordin´aln´ıch typech).

1. Bud’ (A,v) dobré uspoˇrádán´ı. Je-liA mnoˇzina, existuje právˇe jedno or- dináln´ı ˇc´ıslo α tak, ˇze uspoˇrádán´ı (A,v) a (α,≤) jsou izomorfn´ı. Je-li A vlastn´ı tˇr´ıda a uspoˇrádán´ı ≤ je nav´ıc úzké, tj. pro kaˇzdé x ∈ A je {y∈A; y≤x}mnoˇzina, je(A,v)izomorfn´ı s(On,≤). V obou pˇr´ıpadech je uvedený izomorfismus urˇcen jednoznaˇcnˇe.

2. ˇZádná dvˇe r˚uzná ordináln´ı ˇc´ısla nejsou izomorfn´ı vzhledem k ≤.

D˚ukaz. Pˇredpokládejme, ˇzeAje neprázdná, a (A,v) je dobré uspoˇrádán´ı. Hle- daný izomorfismus se konstruuje transfinitn´ı rekurz´ı, pˇriˇcemˇz konstruuj´ıc´ı funkci Glze definovat napˇr´ıklad takto:

G(x) =

(nejm_(A,v)(A−rng(x)) proA−rng(x)6=∅

nejm_(A,v)(A) jinak.

Podle principu transfinitn´ı rekurze nyn´ı existuje pr´avˇe jedna funkceF :On→V splˇnuj´ıc´ı podm´ınku (1.3) a snadno se jiˇz nahl´edne, ˇze zobrazen´ı

H =F {α∈dom(F); α= 0∨F(α)6= nejm_(A,v)(A)}

má poˇzadované vlastnosti. Druhá ˇcást tvrzen´ı je bezprostˇredn´ım d˚usledkem té

prvn´ı. 2