Jólrendezési tétel

A jólrendezési tétel a halmazelmélet egy tétele, amely kimondja, hogy minden halmaz jólrendezhető, azaz tetszőleges halmazon megadható olyan rendezés, amellyel a struktúra jólrendezett.

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 Zermelótó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 Hausdorff–Birkhoff-tétel felhasználásával

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\neq 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.

A kiválasztási axióma felhasználásával (vázlat)

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 megfelelteté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\neq \emptyset$ esetén. Ilyen 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 transzfinit 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. Belátható viszont, 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 )\neq G(\beta )\,$ , ha $\alpha \neq \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.
• A valós számok fölött is van jólrendezés, habár ilyet még senki nem tudott megadni.

Forrá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