Jólrendezett halmaz

Jólrendezett halmaznak nevezünk egy halmazt, ha adott rajta egy jólrendezés, ami olyan teljes rendezést jelent, melyre igaz, hogy alaphalmaza minden nemüres részhalmazának van a rendezés szerint legkisebb eleme.

Definíció

Az (A, ≤) rendezett halmazt jólrendezett halmaznak nevezzük, ha $(A, \leq)$ minden nemüres részhalmazának van legkisebb eleme.

Két jólrendezett halmazt izomorfnak nevezünk, ha van köztük rendezéstartó bijekció, azaz $(A, \leq_1)$ izomorf $(B, \leq_2)$ -vel, ha van olyan $F:A\rightarrow B$ bijekció, melyre a <₁ b pontosan akkor, ha F(a) <₂ F(b) minden $a, b \in A$ -ra.

Az izomorfia tehát a halmazok és a rajtuk definiált jólrendezések közös tulajdonsága, egy adott halmaznak is lehetnek egymással nem izomorf jólrendezései (sőt, pontosan a véges halmazok azok, amiknek minden (jól)rendezése izomorf egymással). A jólrendezett halmazok közötti izomorfizmus ekvivalenciareláció.
Izomorf jólrendezett halmazok közös tulajdonságát, "a jólrendezésük típusát" rendszámnak nevezzük.

Tulajdonságok

Egy jólrendezett halmaz nem tartalmazhat végtelen csökkenő sorozatot.

Az egész számok halmaza a szokásos rendezéssel nem alkot jólrendezett halmazt, de könnyen definiálható olyan rendezés, amely mellett a kapott struktúra jólrendezett. Legyen a rendezés a következő: x <_z y pontosan akkor, ha |x| < |y| vagy |x| = |y| és x < y. (Itt < a szokásos rendezést jelöli.)

Egy jólrendezett halmazban minden elemnek van rákövetkezője, azaz olyan elem, ami a nála nagyobbak közül a legkisebb. (Kivéve ha a halmaznak van legnagyobb eleme, akkor annak értelemszerűen nincs rákövetkezője.) Érdemes megemlíteni, hogy nem feltétlenül van minden elemnek megelőzője. Tekintsük azt a halmazt, ami két példányban tartalmazza a természtes számokat olymódon, hogy egy példányon belül a rendezés a szokásos, de a második példány minden eleme nagyobb az első példány elemeinél. (ω + ω: 0₁, 1₁, 2₁, …, 0₂, 1₂, 2₂, …). Ez a halmaz jólrendezett, de 0₂-nek nincs megelőzője. (0₁-nek sincs, de az a legkisebb elem a hamazban.)

A jólrendezett halmazok azért kényelmesek, mert alkalmazható bennük a transzfinit indukció (a teljes indukció általánosítása), melynek segítségével a halmaz elemeire olykor könnyen bizonyíthatunk állításokat.

Példák

Példák jólrendezett halmazra:

• Bármely véges teljesen rendezett halmaz.
• A természetes számok a szokásos rendezéssel. $(\mathbb{N}, < )$

Példák nem jólrendezett halmazra:

• Az egész számok a szokásos rendezéssel, hiszen a negatív számokból álló részhalmaznak nincs legkisebb eleme. $(\mathbb{Z}, < )$
• A pozitív valós számok a szokásos rendezéssel, hiszen például a (0,1) nyílt intervallumnak nincs legkisebb eleme. $(\mathbb{R}, < )$

Topológia

Minden jólrendezett halmaz topologikus térré tehető. Ezekben a topológiákban kétféle elem van:

• Izolált pontok: a minimum és azok az elemek, amiknek van megelőzője
• Határpontok: az összes többi. Csak végtelen halmazban jelenhetnek meg. Azok a végtelen halmazok, amik nem tartalmaznak ilyen pontot, éppen az ω rendszámú halmazopk. Ilyen például a természetes számok halmaza.

A részhalmazok lehetnek:

• maximumot tartalmazó halmazok. Mivel minimumuk is van, ezért ezek kétszeresen jólrendezett halmazok.
• önmagukban nem korlátos, de az egészben korlátos részhalmazok. Nincs maximumuk; szuprémumuk a részhalmazon kívülre, de a tartalmazó halmazon belülre esik. Ha a részhalmaz nem üres, akkor ez határpontja a részhalmaznak, és a tartalmazó halmaznak is. Ha a részhalmaz üres, akkor ez az egész halmaz minimuma.
• az egészben sem korlátos részhalmazok

Egy részhalmaz ko-véges, ha nem korlátos az egészben, vagy maximuma az egész halmaznak is maximuma.

A jólrendezett halmazban, mint topologikus térben akkor és csak akkor minden pontnak van megszámlálható környezetbázisa, ha rendszáma kisebb ω₁-nél. Ez tovább ekvivalens azzal, hogy a halmaz megszámlálható, vagy rendszáma a legkisebb nem megszámlálható rendszám.

Jólrendezési tétel

Tétel

Minden halmaz jólrendezhető, azaz tetszőleges halmazon megadható olyan rendezés, amellyel a struktúra jólrendezett.

Megjegyzés

A jólrendezési tétel ekvivalens a kiválasztási axiómával. A bizonyítása tehát csak azt jelenti, hogy föltesszük a Kiválasztási axiómát vagy egy azzal ekvivalens állítást, és abból levezetjük a jólrendezési tételt. Az itt bemutatott bizonyítások közül az első a Zorn-lemma egy következményét használja, a második közvetlenül a Kiválasztási axiómát.

A tétel és az eredeti bizonyítás Ernst Zermelotól származik. Ebben a bizonyításban mondta ki először Zermelo a kiválasztási axiómát.

Definíció

Legyenek $A$ és $B$ egy tetszőleges $(R, \leq)$ részbenrendezett halmaz részhalmazai. Azt mondjuk, hogy $A$ szelete $B$-nek, ha $A=B$ vagy valamely $b\in B$-re $A = \{x< b: x\in B\}$.

Bizonyítás

A tételt Hausdorff–Birkhoff-tétel felhasználásával fogjuk bizonyítani. Legyen $H$ tetszőleges halmaz. A bizonyításhoz tekintsük az összes lehetséges $(A, \leq)$ jólrendezett halmazt, ahol $A \subseteq H$. Két ilyen jólrendezett halmaz akkor és csak akkor egyenlő, ha nem csak az alaphalmazok elemei egyeznek meg, de a rajtuk megadott $\leq$ reláció is. Definiáljuk most a $\leq_1$ részbenrendezést az így képezett jólrendezett halmazok halmazán a következőképpen: $(A, \leq) \leq_1 (B, \leq)$ akkor és csak akkor, ha $A$ szelete $B$-nek. A Hausdorff–Birkhoff-tétel szerint az így definiált részbenrendezett halmazban van maximális rendezett részhalmaz, legyen ez $(A_1, \leq), (A_2, \leq), \ldots$. Legyen ezeknek az egyesítése $(M, \leq)$, ahol $\leq$ az $M$ indukált rendezése, azaz az a rendezés, amelynél a maximális rendezett részhalmazban szereplő jólrendezett halmazokban érvényes relációk továbbra is érvényben maradnak. Azt kell belátnunk, hogy $(M, \leq)$ jólrendezett halmaz és $M = H$. Vegyük észre, hogy $(M, \leq)$ meg kell egyezzen az őt alkotó jólrendezett halmazok valamelyikével, ugyanis ellenkező esetben a maximális rendezett részhalmazunk bővíthető lenne ezzel a jólrendezett halmazzal, ami ellentmondás. Másrészről ha $M \ne H$, akkor $(M, \leq)$ bővíthető egy $M$-en kívüli $H$-beli elemmel, és az így kapott jólrendezett halmaznak $M$ szelete lenne, ami szintén ellentmond a Hausdorff–Birkhoff-tétel szerint rendezett részhalmaz maximális voltának.

Bizonyítás-vázlat a kiválasztási axióma felhasználásával

Legyen H tetszőleges halmaz. A bizonyítás lényege az, hogy H elemeihez rendszámokat rendelünk egyértelmű módon, azaz megadunk egy bijekciót a halmaz és a rendszámok egy szelete között. Mivel a rendszámok szeletei jólrendezett halmazok, a megfeleltetetés jólrendezést generál H-n. A kiválasztási axióma azt biztosítja, hogy tudunk tetszőlegesen sokszor új elemet választani H-ból, amit a soron következő rendszámhoz rendelünk hozzá.

Legyen tehát F egy kiválasztási függvény H hatványhalmazán: $F:\mathcal{P}(H)\rightarrow H ;\ F(A) \in A$ minden $A \subseteq H ;\ A \ne \emptyset$ esetén. Kiválasztási függvény létezését a Kiválasztási axióma garantálja. Azonban a kiválasztási függvény az üres halmazhoz nem rendel semmit, F ottani értékét ezért külön kell definiálnunk: $F(\emptyset):=t$, ahol t egy tetszőleges H-n kívüli elem.
Ezután transzfinit rekurzióval legyártjuk a G jólrendező függvényt. Minden rendszámhoz hozzárendelünk egy-egy elemet H-ból, mégpedig a következőképp: legyen α egy rendszám. Ha az α-nál kisebb rendszámokra már meghatároztuk G értékét, nézhetjük H-nak azon elemeit amiket már fölvett a G függvény az α-nál kisebb rendszámokon. Ezek egy részhalmazt alkotnak. Az F függvény ezen részhalmazon fölvett értéke lesz G(α). Tehát a

$G(\alpha)=F(H \setminus \{G(\beta) \mid \beta < \alpha \})$

rekurzió megoldása lesz G, a traszfinit rekurzió tétele szerint G létezik és egyértelmű. Ez a G még nem függvény, hanem ún. operáció, mert az értelmezési tartománya -a rendszámok osztálya- nem halmaz. Viszont belátható, hogy G injektív, amég föl nem veszi a t értéket, onnantól kezdve viszont mindig t-t vesz föl:

• $G(\alpha) \ne G(\beta) \,$ , ha $\alpha \ne \beta$ és egyikük sem $t$. Hiszen ha például α < β, akkor G(β) értékét olyan halmazból választjuk, amiben G(α) már nincs benne.
• $\alpha < \beta$ és $G(\alpha)= t \ \Rightarrow \ G(\beta)=t$. G(α)=t ugyanis azt jelenti, hogy H-nak már minden elemét fölvette G α-nál kisebb rendszámokra, és így β esetén még inkább ez a helyzet.
• G fölveszi a t értéket. Mert ha nem venné föl, akkor G bijekció lenne H és a rendszámok osztálya között, márpedig H halmaz, a rendszámok osztálya nem halmaz. (Egész pontosan a pótlás axiómájára lehet hivatkozni.)

Legyen φ a legkisebb rendszám, amire G a t értéket veszi föl. A rendszámok tulajdonságai miatt ilyen rendszám létezik. Ekkor G megszorítása a φ-nél kisebb rendszámokra függvény, és bijekció ezen rendszámok és H között.

Ez a bizonyítás nem tartalmazza a transzfinit rekurzió pontos leírását.

Ekvivalens állítások

A jólrendezési tétel ekvivalens a következő állításokkal:

• kiválasztási axióma
• Zorn-lemma
• Teichmüller–Tukey-lemma
• Hausdorff–Birkhoff-tétel
• Tyihonov-tétel

Következmény

A jólrendezési tétel következménye, hogy létezik kiválasztási függvény, azaz a kiválasztási axióma teljesül, mert ekkor definiálhatjuk úgy a kiválasztási függvényt, hogy az rendelje hozzá minden részhalmazhoz az adott részhalmaz legkisebb elemét.

Hivatkozások

• Rédei, László: Algebra I. kötet, Akadémiai Kiadó, Budapest, 1954
• Szendrei, Ágnes: Diszkrét matematika Logika, algebra, kombinatorika, Polygon Kiadó, Szeged, 1994