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óSzerkesztés

Legyenek   és   egy tetszőleges   részbenrendezett halmaz részhalmazai. Azt mondjuk, hogy   szelete  -nek, ha   vagy valamely  -re  .

BizonyításSzerkesztés

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

Legyen   tetszőleges halmaz. A bizonyításhoz tekintsük az összes lehetséges   jólrendezett halmazt, ahol  . Két ilyen jólrendezett halmaz akkor és csak akkor egyenlő, ha nem csak az alaphalmazok elemei egyeznek meg, de a rajtuk megadott   reláció is.

Definiáljuk most a   részbenrendezést az így képezett jólrendezett halmazok halmazán a következőképpen:   akkor és csak akkor, ha   szelete  -nek. A Hausdorff–Birkhoff-tétel szerint az így definiált részbenrendezett halmazban van maximális rendezett részhalmaz, legyen ez  . Legyen ezeknek az egyesítése  , ahol   az   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   jólrendezett halmaz és  .

Vegyük észre, hogy   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  , akkor   bővíthető egy  -en kívüli  -beli elemmel, és az így kapott jólrendezett halmaznak   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)Szerkesztés

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:   minden   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:  , 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

 

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. 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:

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

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

KövetkezménySzerkesztés

  • 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ásokSzerkesztés

  • 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