Extremální objekty

Lineární báze

Začneme příkladem, který je čtenáři dobře známý. Je-li $V$ vektorový prostor, řekneme, že podmnožina $B \subset V$ je jeho *báze*, pokud je zároveň

• *generující*, tj. každý vektor z $V$ lze získat jako lineární kombinaci vektorů z $B$;
• *lineárně nezávislá*, tj. žádná netriviální kombinace vektorů z $B$ není nulová.

Tyto dva požadavky jsou protichůdné v následujícím smyslu: první vlastnost požaduje, aby v $B$ bylo dost vektorů na to, aby se z nich všechny ostatní daly kombinovat; druhá naopak požaduje, aby vektorů v $B$ nebylo příliš mnoho, totiž aby nebyly lineárně závislé.

Tomuto pozorování můžeme dát přesný smysl pomocí pojmu minimality a maximality. Je-li $(X,<)$ nějaká uspořádaná množina, řekneme, že prvek $a \in X$ je *minimální*, pokud žádný jiný prvek z $X$ není menší, tj. pokud $\neg (\exists x \in X) (x < a)$; podobně prvek $b \in X$ je *maximální*, pokud žádný jiný prvek z $X$ není větší, tj. pokud $\neg (\exists x \in X) (b < x)$.

Nejmenší prvek uspořádané množiny $(X, <)$, pokud existuje, je zároveň minimální (navíc je to jediný takový), ale nikoli nutně naopak. Například minimálními prvky množiny ${\mathbb N} \setminus \{1\} = \{2, 3, 4, 5, 6, \dots \}$ uspořádané relací dělitelnosti jsou právě prvočísla (tedy minimálních prvků je dokonce nekonečně mnoho), ale žádný z nich není nejmenší (tj. není *minimem*). Analogická poznámka platí pro největší a maximální prvky. Každé dva minimální (jakož i každé dva maximální) prvky jsou navzájem neporovnatelné.

Extremální vlastnosti lineární báze můžeme nyní vyjádřit takto. Je-li $V$ vektorový prostor, označme jako $\mathcal G$ systém všech generujících podmnožin, a jako $\mathcal N$ systém všech lineárně nezávislých podmnožin. Pro podmnožinu $B \subset V$ jsou potom následující podmínky ekvivalentní:

• $B$ je báze prostoru $V$
• $B$ je minimálním prvkem uspořádání $({\mathcal G}, \subset)$
• $B$ je maximálním prvkem uspořádání $({\mathcal N}, \subset)$

Uvědomme si nejprve, co obnáší být minimálním prvkem v $({\mathcal G}, \subset)$. Je to taková podmnožina prostoru $V$, která jej generuje, ale žádná menší jej negeneruje; odebráním jediného vektoru přestane být generující. Podobně maximálním prvkem v $({\mathcal N}, \subset)$ je taková podmnožina prostoru $V$, která je lineárně nezávislá, ale přidáním libovolného vektoru nezávislost ztratí.

Důkaz není těžký. Předpokládejme nejprve, že $B$ je báze. Pokud není minimálním prvkem v $({\mathcal G}, \subset)$, znamená to, že v $\mathcal G$ existuje ostře menší prvek, tedy nějaká vlastní podmnožina $A \subset B$, která ovšem stále generuje $V$. V tom případě zvolme libovolný vektor $u \in B \setminus A$. Ten se dá vyjádřit jako lineární kombinace vektorů z $A \subset B$, neboť $A$ je generující. To ale znamená, že $B$ je lineárně závislá, což je spor.

Je-li naopak $B$ minimálním prvkem v $({\mathcal G}, \subset)$, je z definice generující; zbývá ukázat že je nezávislá. Pokud ne, znamená to, že nějaký vektor $u \in B$ se dá vyjádřit jako lineární kombinace ostatních. Potom ale $B$ není minimální, neboť $B \setminus \{u\} \subset B$ stále generuje $V$, což je spor.

Ekvivalence s maximalitou v $({\mathcal N}, \subset)$ se ukáže zcela analogicky.

Úplné teorie

Druhý příklad pochází z logiky. Je-li $\mathcal L$ jazyk predikátové logiky prvního řádu, řekneme, že bezesporná teorie $T$ v jazyce $\mathcal L$ je *úplná*, pokud pro každou uzavřenou formuli $\varphi$ jazyka $\mathcal L$ je buďto $T \vdash \varphi$ nebo $T \vdash \neg \varphi$, tj. teorie $T$ buďto dokazuje nebo vyvrací každou sentenci daného jazyka.

Typické teorie z matematické praxe úplné nejsou. Například teorie grup není úplná, protože ani nedokazuje ani nevyvrací uzavřenou formuli $(\forall x)(\forall y)(x + y = y + x)$. Ani aritmetika, ani teorie množin není úplná; naproti tomu teorie neomezených hustých lineárních uspořádání úplná je (nic z toho nebudeme dokazovat).

Všimněme si, že požadavky na úplnost a bezespornost jsou podobně protichůdné, jako požadavky v definici lineární baze. Teorie $T$ má obsahovat dost axiomů na to, aby z nich bylo možné dokázat či vyvrátit každé další tvrzení (v daném jazyce); zároveň nesmí být příliš silná, totiž nesmí dokazovat cokoli.

Je-li $T$ bezesporná teorie, označme jako $\mathrm{Thm}(T) = \{\varphi ; T \vdash \varphi \}$ množinu všech formulí dokazatelných v teorii $T$. Potom jsou následující tvrzení ekvivalentní:

• $T$ je úplná teorie
• $\mathrm{Thm}(T)$ je maximální bezesporná

Jinými slovy, k důsledkům úplné teorie již nelze přidat žádnou další formuli a zároveň zachovat bezespornost.

Důkaz je podobný jako výše. Předpokládejme nejprve, že $T$ je úplná. Pokud $\mathrm{Thm}(T)$ není maximální, znamená to, že pro nějakou jinou bezespornou teorii $S$ (v témže jazyce) je $\mathrm{Thm}(T) \subset S$. Buď tedy $\varphi$ nějaká formule z $S \setminus \mathrm{Thm}(T)$; to jest, $\varphi$ je dokazatelná v $S$, ale není dokazatelná v $T$. Přitom $T$ je úplná teorie, takže pokud není $T \vdash \varphi$, musí být $T \vdash \neg\varphi$. Potom je ale také $S \vdash \neg\varphi$, takže $S$ je sporná. Je-li naopak $\mathrm{Thm}(T)$ maximální bezesporná, je také $T \subset \mathrm{Thm}(T)$ bezesporná; zbývá ukázat, že je úplná. Buď tedy $\varphi$ libovolná uzavřená formule jazyka teorie $T$. Pokud není $T \vdash \varphi$, znamená to, že teorie $T \cup \{\neg\varphi\}$ je stále bezesporná. Přitom $\mathrm{Thm}(T) \subseteq \mathrm{Thm}(T \cup \{\neg\varphi\})$, takže z maximality je $\mathrm{Thm}(T) = \mathrm{Thm}(T \cup \{\neg\varphi\})$. To ale znamená, že je $T \vdash \neg\varphi$.

Lineární uspořádání

Třetí příklad pochází z uspořádaných množin. Dva různé prvky $x, y$ částečně uspořádané množiny $(X,<)$ jsou porovnatelné*, pokud je buďto $x < y$ nebo $y < x$. *Lineární uspořádání je potom takové, ve kterém jsou každé dva různé prvky porovnatelné. Lineární uspořádání se též nazývá úplné*, jako extrémní případ *částečného uspořádání.

(Pro úplnost dodejme, že mluvíme o ostrém uspořádání. S patřičnými úpravami bychom mohli vše reformulovat i pro odpovídající neostré uspořádání.)

Po předchozích příkladech nás nepřekvapí následující tvrzení. Buď $({\mathcal U}, \subset)$ systém všech uspořádání množiny $X$. Potom pro uspořádání $<$ jsou následující podmínky ekvivalentní:

• $(X, <)$ je lineární uspořádání
• Relace $<$ je maximálním prvkem v $({\mathcal U}, \subset)$

Maximální prvek v $({\mathcal U}, \subset)$ je taková relace uspořádání, ke které nelze přidat žádnou další porovnatelnou dvojici, aniž by přestala být ostrým uspořádáním.

Důkaz je opět analogií předchozích. Předpokládejme nejprve, že $(X,<)$ je lineární. Pokud není maximální, pak jej lze rozšířit do nějakého uspořádání $(X, \prec)$, ve kterém je navíc porovnatelná nějaká dvojice $x \prec y$, zatímco $x < y$ neplatí. V tom případě ale musí být $y < x$, neboť $<$ je lineární. Pak ale máme $x \prec y \prec x$, jelikož $\prec$ rozšiřuje $<$. Z transitivity je potom $x \prec x$, což není možné. Buď naopak $<$ maximálním prvkem v $({\mathcal U}, \subset)$. Pokud je nějaká dvojice $x,y \in X$ neporovnatelná, dá se uspořádání $<$ rozšířit do nějakého uspořádání $\prec$, ve kterém bude $x \prec y$. (Stačí pro každé dva různé prvky $p,q \in X$ položit $p \prec q$ právě tehdy, když je buďto $p < q$, nebo $p \leq x$ a $y \leq q$. Relace $\prec$ očividně rozšiřuje $<$ a splňuje $x \prec y$; snadno se ověří, že je ostrým uspořádáním.) To ale znamená, že $<$ není maximální, což je spor.

Kompaktní Hausdorffova topologie

Poslední příklad je určen čtenářům obeznámeným se základy obecné topologie.

Připomeňme, že topologický prostor je *Hausdorffův*, pokud každé dva různé body lze oddělit disjunktními okolími; tj. pro $x,y \in X, x \ne y$ existují navzájem disjunktní otevřené množiny $U,V \subset X$ tak, že $x \in U, y \in V$. Topologický prostor je *kompaktní*, pokud každé jeho pokrytí otevřenými množinami má konečné podpokrytí.

Budeme potřebovat následující pozorování. Buďte $(X, \sigma)$ a $(Y, \tau)$ topologické prostory. Jsou-li oba kompaktní a Hausdroffovy, pak každá spojitá bijekce mezi nimi je homeomorfismus. Je-li totiž $f: X \to Y$ spojitá bijekce, zbývá jen ukázat, že je uzavřená, tedy že obrazem uzavřené množiny v $X$ je uzavřená množina v $Y$. Buď tedy $A \subset X$ uzavřená. Potom je zároveň kompaktní (jakožto uzavřená množina v kompaktu), a její spojitý obraz $f[A] \subset Y$ je rovněž kompaktní. Přitom kompaktní podmnožina v Hausdorffově prostoru je uzavřená: je-li $B \subset Y$ kompaktní a $y \in Y \setminus B$, pak pro každý bod $b \in B$ máme disjunktní otevřené množiny $U_b, V_b \subset Y$ takové, že $b \in U_b, y \in V_b$. Možiny $U_b$ potom pokrývají kompakt $B$, tedy jej pokrývají konečně; jinými slovy, $B \subset U_{b_1} \cup \dots \cup U_{b_n}$ pro nějakých konečně mnoho bodů $b_1, \dots, b_n \in B$. Pro odpovídající množiny $V_b$ pak máme otevřené okolí $V_{b_1} \cap \dots \cap V_{b_n}$ bodu $y$, které jej odděluje od $B$. Tedy $B$ je uzavřená.

Jako důsledek pak máme: kompaktní Hausdorffova topologie na prostoru $X$ je zároveň

• maximální mezi všemi kompaktními topologiemi na $X$ a
• minimální mezi všemi Hausdorffovými topologiemi na $X$.

To znamená, že kdybychom danou topologii jakkoli zesílili (přidáním jakékoli nové otevřené množiny), přestala by být kompaktní. Naopak žádná slabší topologie již není Hausdorffova. Laskavý čtenář si opět všimne analogie s lineárními bazemi.

Důkaz je s použitím předchozího tvrzení již snadný. Buď $\tau$ kompaktní Hausdorffova topologie na $X$. Je-li $\sigma \subset \tau$ libovolná slabší topologie, pak identické zobrazení $id: (X, \tau) \to (X, \sigma)$ je spojitá bijekce, ale není homeomorfismem; $\sigma \subset \tau$ je sice stále kompaktní (je to slabší topologie), ale nemůže být Hausdorffova, jinak bychom měli spor s předchozím tvrzením. Podobně, je-li $\sigma \supset \tau$ libovolná silnější topologie, je stále Hausdorffova, ale nemůže být kompaktní, protože $id: (X, \sigma) \to (X, \tau)$ je spojitá bijekce, ale nikoli homeomorfismus.

Princip maximality

Viděli jsme objekty, jejichž vlastnosti jsou projevem (či ekvivalentem) nějaké formy maximality či minimality. Ptejme se nyní, odkud plyne samotná existence takových extremálních objektů. Například: má každý vektorový prostor bázi? Má každá bezesporná teorie úplné bezesporné rozšíření? Dá se každé uspořádání rozšířit do lineárního?

V některých jednotlivých případech lze tyto otázky zodpovědět triviálně. Například obvyklé uspořádání přirozených čísel lineárně rozšiřuje uspořádání podle dělitelnosti. Vektorový prostor ${\mathbb R^3}$ samozřejmě má bázi, ba mnoho různých bazí, rutinně s nimi pracujeme. Síla otázky je v tom, zda pro každý prostor, každé uspořádání, atd. V této obecnosti je otázka rázem netriviální.

Je dokonce natolik jemná, že odpověď na ni závisí na předpokladech o množinových základech matematiky. Tyto předpoklady jsou zformulovány v axiomatice nějaké *teorie množin*, z nichž zdaleka nejrozšířenější je ZFC. Tu zde nebudeme rozvíjet, zformulujeme jen příslušné *principy maximality*. (Základy axiomatické teorie množin pokrývá výběrová přednáška Algebra a logika.)

Buď $X$ libovolná množina. Řekneme, že systém ${\mathcal A} \subset P(X)$ je *konečného charakteru*, pokud pro každou $A \subset X$ je $A \in \mathcal A$ právě tehdy, když platí $B \in \mathcal A$ pro všechny konečné $B \subset A$. To jest, množina $A \subset X$ padne do systému $\mathcal A$ právě tehdy, když do $\mathcal A$ padnou všechny její konečné podmnožiny.

Tukeyův princip maximality. Je-li ${\mathcal A} \subset P(X)$ systém konečného charakteru, pak pro každou množinu $A \in \mathcal A$ existuje $Y \supset A$, která je maximální v $({\mathcal A}, \subset)$.

Každé z následujích tvrzení je důsledkem Tukeyova principu:

• Každou lineárně nezávislou množinu lze rozšířit do báze.
• Každá bezesporná teorie má bezesporné zúplnění.
• Každé uspořádání má lineární rozšíření.

Stačí ukázat, že příslušné systémy jsou konečného charakteru. To ale plyne téměř okamžitě z definic. Je-li daná podmnožina vektorového prostoru lineárně *závislá*, znamená to, že už nějaká její konečná pomnožina je závislá, neboť lineární kombinace jsou z definice konečné. Je-li daná teorie *sporná*, je sporná už nějaká její konečná část, neboť důkaz je z definice konečná posloupnost. Je-li dané uspořádání *nelineární*, je nelineární už nějaká jeho konečná (toitiž dvouprvková) podmnožina. Podle Tukeyova principu tedy v těchto systémech existuje nad každým prvkem nějaký maximální. Přitom báze je právě maximální nezávislá množina, úplná teorie je právě maximální bezesporná, a lineární uspořádání je právě maximální uspořádání, jak jsme ukázali výše.

Předvedeme ještě dvě ekvivalentní formulace principu maximality.

Podmnožina $C$ uspořádané množiny $(X,<)$ je *řetězec*, pokud je $(C, <)$ lineárně uspořádaná. Například množina přirozených čísel není lineárně uspořádaná relací dělitelnosti, ale mocniny dvojky tvoří v tomto uspořádání řetězec.

Hausdorffův princip maximality. Každé uspořádání obsahuje maximální řetězec.

Maximální řetězec je taková lineárně uspořádaná podmnožina $C \subset (X,<)$, kterou nelze rozšířit do žádné větší lineárně uspořádané $D \supset C$. Ekvivalentně, řetězec $C \subset X$ je maximální právě když pro každý prvek $x \in X$ porovnatelný se všemi $y \in C$ je $x \in C$. Speciálně nejmenší a největší prvek uspořádání $(X,<)$, pokud existují, musí ležet v každém maximálním řetězci.

Zornovo lemma. Buď $(X,<)$ uspořádaná množina, ve které každý řetězec má horní mez. Potom pro každé $x \in X$ existuje maximální prvek $y \geq x$.

Ukážeme nyní, že všechny tři principy jsou navzájem ekvivalentní.

(Tukey $\to$ Hausdorff) Buď $(X,<)$ dané uspořádání. Systém všech řetězců v $X$ je konečného charakteru: je-li $A \subset X$ řetězec, je i každé $B \subset A$ řetězec, a naopak pokud $A$ není řetězec, jsou nějaké $x,y \in A$ neporovnatelné, takže konečná $\{x,y\} \subset A$ není řetězec. Podle Tukeyova principu má pak systém řetězců maximální prvek.

(Hausdorff $\to$ Zorn) Buď $(X,<)$ uspořádaná množina a $x \in X$ daný prvek. Pokud každý řetězec v $X$ má horní mez, má horní množina $(x, \to) = \{y \in X ; y \geq x \}$ tutéž vlastnost. Podle Hausdorffova principu existuje v $(x, \to)$ maximální řetězec $C$; ten obsahuje $x$, jinak není maximální. Je-li potom $y$ horní mez $C$, je $y \geq x$ maximální v $(X, <)$: kdyby $z > y$ pro nějaké $z$, bylo by $C \cup \{z\}$ prodloužení maximálního řetězce $C$.

(Zorn $\to$ Tukey) Je-li ${\mathcal A} \subset P(X)$ systém konečného charakteru, pak pro každý řetězec ${\mathcal C} \subset {\mathcal A}$ je také $\bigcup {\mathcal C} \in {\mathcal A}$. Tedy každý řetězec v $\mathcal A$ má horní mez. Nad zvoleným $A \in \mathcal A$ tedy podle Zornova lemmatu existuje maximální $Y \in \mathcal A$.

Axiom výběru

Předvedli jsme tři navzájem ekvivalentní principy maximality, ze kterých plyne (mimo jiné) existence extremálních objektů, které jsme popsali výše. Zbývá otázka, odkud plynou samy tyto principy. Všechny jsou ekvivalentní jistému axiomu teorie množin, který nyní vyslovíme.

Buď $X$ libovolná neprázdná množina. Řekneme, že zobrazení $f: P(X) \to X$ je výběrová funkce neboli selektor pro $X$, pokud pro každou neprázdnou $A \subseteq X$ je $f(A) \in A$.

Axiom výběru. Na každé množině existuje selektor.

Tento axiom se od ostatních axiomů teorie množin liší v tom, že postuluje existenci množin, aniž by říkal, co mají být jejich prvky. (Narozdíl třeba od axiomu dvojice, který pro každé dvě množiny $x, y$ postuluje existenci množiny, jejímiž jedinými dvěma prvky jsou právě $x$ a $y$.) V tomto smyslu axiom výběru není *konstruktivní*. Laskavý čtenář může zkusit popsat nějaký selektor na $\mathbb R$.

Následující tvrzení jsou navzájem ekvivalentní:

• Axiom výběru
• Každý vektorový prostor má bazi
• Hausdorffův princip maximality
• Tukeyův princip maximality
• Zornovo lemma

Tyto ekvivalence ponecháme bez důkazu (ale v přednášce BI-ALO je dokážeme). O existenci lineárních bazí víme z předchozího, že je důsledkem principu maximality; trochu překvapivě je existence lineární báze pro každý prostor dokonce ekvivalentní s axiomem výběru.

Literatura

• Balcar, Štěpánek: Teorie množin, Academia, 2005
• Herrlich: Axiom of Choice, Springer-Verlag, 2006

---

Tento článek byl vznikl v rámci řešení projektu Institucionální podpora Českého vysokého učení technického v Praze (CZ.02.2.69/0.0/0.0/16_015/0002382).

---