„Jólrendezett halmaz” változatai közötti eltérés

A tételt [[Hausdorff–Birkhoff-tétel]] felhasználásával fogjuk bizonyítani. Legyen <math>H</math> tetszőleges halmaz. A bizonyításhoz tekintsük az összes lehetséges <math>(A, \leq)</math> jólrendezett halmazt, ahol <math>A \subseteq H</math>. Két ilyen jólrendezett halmaz akkor és csak akkor egyenlő, ha nem csak az alaphalmazok elemei egyeznek meg, de a rajtuk megadott <math>\leq</math> reláció is. Definiáljuk most a <math>\leq_1</math> részbenrendezést az így képezett jólrendezett halmazok halmazán a következőképpen: <math>(A, \leq) \leq_1 (B, \leq)</math> akkor és csak akkor, ha <math>A</math> szelete <math>B</math>-nek. A Hausdorff–Birkhoff-tétel szerint az így definiált részbenrendezett halmazban van maximális rendezett részhalmaz, legyen ez <math>(A_1, \leq), (A_2, \leq), \ldots</math>. Legyen ezeknek az egyesítése <math>(M, \leq)</math>, ahol <math>\leq</math> az <math>M</math> 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 <math>(M, \leq)</math> jólrendezett halmaz és <math>M = H</math>. Vegyük észre, hogy <math>(M, \leq)</math> 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 <math>M \ne H</math>, akkor <math>(M, \leq)</math> bővíthető egy <math>M</math>-en kívüli <math>H</math>-beli elemmel, és az így kapott jólrendezett halmaznak <math>M</math> szelete lenne, ami szintén ellentmond a Hausdorff–Birkhoff-tétel szerint rendezett részhalmaz maximális voltának.

 

Legyen ''H'' tetszőleges halmaz. A bizonyítás lényege az, hogy ''H'' elemeihez [[Rendszám (halmazelmélet)|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.

 

Legyen tehát ''F'' egy kiválasztási függvény ''H'' hatványhalmazán: <math>F:\mathcal{P}(H)\rightarrow H ;\ F(A) \in A</math> minden <math>A \subseteq H ;\ A \ne \emptyset</math> esetén.

* <math>G(\alpha) \ne G(\beta) \,</math> , ha <math>\alpha \ne \beta</math> és egyikük sem <math>t</math>. Hiszen ha például α < β, akkor ''G''(β) értékét olyan halmazból választjuk, amiben ''G''(α) már nincs benne.

* <math>\alpha < \beta</math> és <math>G(\alpha)= t \ \Rightarrow \ G(\beta)=t</math>. 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.

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.