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

Bizonyítás

A Hausdorff–Birkhoff-tétel felhasználásával

Legyen ${\displaystyle H}$ tetszőleges halmaz. A bizonyításhoz tekintsük az összes lehetséges ${\displaystyle (A,\leq )}$ jólrendezett halmazt, ahol ${\displaystyle 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 ${\displaystyle \leq }$ reláció is.

Definiáljuk most a ${\displaystyle \leq _{1}}$ részbenrendezést az így képezett jólrendezett halmazok halmazán a következőképpen: ${\displaystyle (A,\leq )\leq _{1}(B,\leq )}$ akkor és csak akkor, ha ${\displaystyle A}$ szelete ${\displaystyle B}$-nek. A Hausdorff–Birkhoff-tétel szerint az így definiált részbenrendezett halmazban van maximális rendezett részhalmaz, legyen ez ${\displaystyle (A_{1},\leq ),(A_{2},\leq ),\ldots }$. Legyen ezeknek az egyesítése ${\displaystyle (M,\leq )}$, ahol ${\displaystyle \leq }$ az ${\displaystyle 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 ${\displaystyle (M,\leq )}$ jólrendezett halmaz és ${\displaystyle M=H}$.

Vegyük észre, hogy ${\displaystyle (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 ${\displaystyle M\neq H}$, akkor ${\displaystyle (M,\leq )}$ bővíthető egy ${\displaystyle M}$-en kívüli ${\displaystyle H}$-beli elemmel, és az így kapott jólrendezett halmaznak ${\displaystyle 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: ${\displaystyle F:{\mathcal {P}}(H)\rightarrow H;\ F(A)\in A}$ minden ${\displaystyle 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: ${\displaystyle 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

${\displaystyle 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:

• ${\displaystyle G(\alpha )\neq G(\beta )\,}$ , ha ${\displaystyle \alpha \neq \beta }$ és egyikük sem ${\displaystyle t}$. Hiszen ha például α < β, akkor G(β) értékét olyan halmazból választjuk, amiben G(α) már nincs benne.
• ${\displaystyle \alpha <\beta }$ és ${\displaystyle 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