Jólrendezési tétel

A Wikipédiából, a szabad enciklopédiából

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 Zermelotól származik. Ebben a bizonyításban mondta ki először Zermelo a kiválasztási axiómát.

Definíció[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 \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[szerkesztés | forrásszöveg szerkesztése]

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

Következmény[szerkesztés | forrásszöveg szerkesztése]

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.

Források[szerkesztés | forrásszöveg szerkesztése]

  • 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