Čo je užitočné vedieť o ordináloch

[Martin Sleziak]

Transfinitnú indukciu by sme v princípe mohli brať tak, že je to indukcia na dobre usporiadaných množinách. V podstate každý dôkaz transfinitnou indukciou by sme asi vedeli prepísať takto - možno ale za cenu toho, že by sme niektoré úvahy opakovali v každom dôkaze. Ordinály nám okrem toho občas zjednodušia označenie. A ak by nás tieto dôvody nepresvedčili o tom, že sa oplatí ordinály vedieť používať, stále je tu fakt že v literatúre sa nájde veľa dôkazov, ktoré ordinály používajú. Aby sme ich boli schopní prečítať a porozumieť im, oplatí sa vedieť o ordináloch aspoň niečo.

Ako som spomenul, k ordinálom môžeme pristupovať "naivne". (T.j. vlastne poriadne nedefinujeme, čo je ordinálne číslo. Ale pre každú dobre usporiadanú množinu máme nejaký ordinálny typ a zadefinujeme, kedy sa dva ordinály rovnajú.) A dajú sa vybudovať aj v rámci axiomatickej teórie množín - tzv. von Neumannova definícia ordinálov. Bez ohľadu na to, akým spôsobom ordinály definujeme, asi sa nám môže hodiť vedieť, že majú vlastnosti, ktoré tu spomeniem. (Resp. ak sa snažíme nejakú definíciu ordinálov vymyslieť, tak by nebolo zlé aby tieto vlastnosti spĺňala.)

Niektoré z uvedených vlastností sú také, že vyplývajú z ostatných.

Užitočné vlastnosti ordinálov

1. Pre každú dobre usporiadanú množinu existuje práve jeden ordinál, ktorý je jej ordinálny typ. Rovnosť ordinálov zodpovedá izomorfizmu dobre usporiadaných množín.
2. Pre ordinály máme $\alpha\le\beta$ práve vtedy, keď množina zodpovedajúca $\alpha$ je izomorfná s počiatočným úsekom množiny zodpovedajúcej $\beta$.
3. Každý ordinál je presne ordinálny typ množiny ordinálov od neho menších; $\alpha=\operatorname{ot}(\{\beta\in\mathrm{On}; \beta<\alpha\},\le)$
4. Každý ordinál má nasledovníka.
5. Pre každý ordinál platí jedna z troch možností: $\alpha=0$; $\alpha$ je nasledovník nejakého ordinálu; $\alpha=\sup\{\beta\in\mathrm{On}; \beta<\alpha\}$. (Ordinály tretieho typu voláme limitné.)
6. Každá množina ordinálov má suprémum.
7. Každá množina ordinálov je dobre usporiadaná. Špeciálne, ľubovoľná neprázdna množina ordinálov má najmenší prvok.
8. Ak dôsledok predošlej vlastnosti dostaneme, že existuje najmenší ordinál danej kardinality. (Toto sa dokonca často používa priamo ako definícia kardinálov.)
9. Neexistuje množina všetkých ordinálov. (Ordinály tvoria vlastnú triedu.)

[Martin Sleziak]

Von Neumannova konštrukcia ordinálov

Vlastne sme už videli, že z toho ako je definovaná nerovnosť medzi ordinálmi nám priamo vyjde, že $\alpha$ je ordinálny typ množiny $\{\beta\in\mathrm{On}; \beta<\alpha\}$ (na ktorej ako nerovnosť berieme obvyklé usporiadanie ordinálov).

Pri von Neumannovej definícii ordinálov dostaneme dokonca rovnosť
$$\alpha=\{\beta\in\mathrm{On}; \beta<\alpha\}.$$
Skoro pri čomkoľvek, na čo chcete použiť ordinály, by vám v dôkaze úplne stačili veci ktoré sme spomenuli vyššie. Veci, ktoré som tu vypísal, spomínam najmä preto, že občas môžete v literatúre naraziť na texty, kde sa táto definícia považuje za štandardnú a nižšie uvedené vlastnosti sa bežne používajú. Čiže vedieť o nich môže byť užitočné pri čítaní dôkazu, ktorého autor používa takúto definíciu a aj jej dôsledky.

Opäť, niektoré veci v tomto zozname sú také, že by sme ich vedeli ľahko odvodiť z niektorých ostatných.

1. Ľubovoľný ordinál $\alpha$ sa rovná množine ordinálov od neho menších.
2. Pre dva ordinály $\alpha$, $\beta$ máme
   $$\begin{gather*} \alpha\lt\beta \Leftrightarrow \alpha\in\beta\\ \alpha\le\beta \Leftrightarrow \alpha\subseteq\beta \end{gather*}$$
3. Ak $\alpha$ je ordinál, tak relácia $\in$ je ostré dobré usporiadanie na $\alpha$.
4. Nasledovník ordinálu $\alpha$ je $S(\alpha)=\alpha+1=\alpha\cup\{\alpha\}$.
5. Ak máme neprázdnu množinu ordinálov $\{\alpha_i; i\in I\}$, tak jej suprémum je $$\sup\limits_{i\in I} \alpha_i=\bigcup\limits_{i\in I} \alpha_i$$ a jej minimum je $$\min\limits_{i\in I} \alpha_i=\bigcap\limits_{i\in I} \alpha_i.$$

[Martin Sleziak]

Skúsim pridať aj konkrétny príklad - toto je dôkaz z knihy Halbeisen: Combinatorial Set Theory.

Pracuje sa tu s podmnožinami prirodzených čísel - tie tu chápeme ako konečné ordinály, čiže množinu prirodzených čísel priamo označujeme $\omega$.
Máme nejaký spočítateľný systém $\{X_n; n\in\omega\}$ nekonečných podmnožín množiny $\omega$. Navyše predpokladáme, že prienik ľubovoľného konečného podsystému je opäť nekonečná množina. (Tejto vlastnosti sa hovorí strong finite intersection property = sfip.)
Cieľom je ukázať, že ak mám spočítateľne s nekonečných podmnožín prirodzených čísel, tak existuje nekonečný pseudoprienik tohoto systému.

Pseudoprienik systému $\{X_n; n\in\omega\}$ je taká množina, že pre každé $n$ je množina $Y$ "takmer podmnožina" množiny $X_n$, čiže rozdiel $Y\setminus X_n$ je konečný. Toto sa označuje aj ako $Y\subseteq^* X_n$.
$$A\subseteq^* B \overset{def}\Leftrightarrow |A\setminus B|<\infty$$
Pseudoprienik evidentne nie je určený jednoznačne. (Ak $Y$ zmeníme o konečne veľa prvkov, neovplyvní to, či to je alebo nie je pseudoprienik.) Chceme však ukázať, že existuje nekonečná množina $Y$, ktorá je pseudoprienikom. (To je presne to, čo sa myslí tvrdením $\omega_1\le\mathfrak p$, len som ho tu prerozprával tak, aby sa dôkaz dal čítať a nebolo treba vedieť definíciu $\mathfrak p$.)

Uvedený dôkaz som zobral odtiaľto: How to prove that $\omega_1 \leq \mathfrak p$. (Čiže je to naozaj dôkaz, na ktorý sa niekto pýtal a bol mu nejasný.)

Podobne ako tu, v množinovo-teoretických knihách či článkoch (a občas aj v niektorých príbuzných oblastiach) je pomerne bežné, že prirodzené čísla chápeme priamo ako konečné ordinály. A bežne sa využívajú vlastnosti, ktoré platia pre ordinály. Tu je úplny citát dôkazu.

Theorem 8.1. $\omega_1\le\mathfrak p$.

Proof. Let $\mathscr E=\{X_n\in[\omega]^\omega : n\in\omega\}$ be a countable family which has the sfip. We construct a pseudo-intersection of $\mathscr E$ as follows: Let $a_0:=\bigcap X_0$ and for positive $n$ let
$$a_n=\bigcap \left(\bigcap \{X_i; i\in n\}\setminus \{a_i; i\in n\}\right).$$
Further, let $Y=\{a_n : n\in\omega\}$; then for every $n\in\omega$, $Y\setminus \{a_i; i\in n\} \subseteq X_n$ which shows that $Y\subseteq^* X_n$, hence, $Y$ is a pseudointersection of $\mathscr E$.

Tento dôkaz môže byť na prvý pohľad nezrozumiteľný. Je však čitateľnejší, ak si uvedomíme, že s prirodzenými číslami sa tu pracuje ako s ordinálmi.

• Zápis "$a_0:=\bigcap X_0$" znamená, že sme vybrali minimum z množiny $X_0$. Chceme ďalej indukciou definovať $a_n$
• Keďže chápeme prirodzené čísla ako ordinály, tak $i\in n$ je len iný zápis pre $i<n$. Čiže $\{a_i; i\in n\}$ je množina doteraz definovaných prvkov. (V indukčnom kroku chceme nájsť prvok $a_n$.)
• Celý výraz $\bigcap \{X_i; i\in n\}\setminus \{a_i; i\in n\}$ hovorí iba to, že sme z prieniku množín $X_0,\ldots,X_{n-1}$ (ktorý je nekonečný) dali preč doteraz vybraté prvky.
• Potom sme prvok $a_n$ definovali ako $\min\left(\bigcap \{X_i; i\in n\}\setminus \{a_i; i\in n\}\right)$.
• Zostáva ukázať, že ak za $Y$ vezmeme množinu takto definovaných $a_n$, tak skutočne dostaneme nekonečný pseudoprienik.

Uvedený príklad je pomerne extrémny - keby sme písali $\min$ namiesto $\bigcap$ a $<$ namiesto $\in$ na správnych miestach, asi by bol čitateľnejší pre človeka, ktorý nie je na tieto veci zvyknutý.
Na druhej strane ale vôbec nie je až také zriedkavé, že ak sa niekde pracuje s ordinálmi, tak sa sa bežne namiesto nerovnosti použije $\in$ alebo namiesto supréma či infima $\bigcup$ resp. $\bigcap$. Čiže ak človek bude čítať nejaké veci z teórie množín či všeobecnej topológie, nemal by byť prekvapený ak na takéto veci narazí.
Hoci v tomto konkrétnom dôkaze to tak nebolo, tak niekedy takéto označenie môže pomôcť veci zapísať výrazne stručnejšie. (Napríklad ak chceme sformulovať princíp definície transfinitnou indukciou, tak je určite jednoduchšie napísať $F|_\alpha$ ako zakaždým písať $F|_{\{\beta\in\mathrm{On}; \beta<\alpha\}}$.)

Spomeniem ešte, že uvedená veta súvisí s takouto oblasťou teórie množín: kardinálne charakteristiky kontinua (cardinal characteristic of the continuum) resp. malé nespočítateľné kardinály (small uncountable cardinals).