Jólrendezett halmaz

A Wikipédiából, a szabad lexikonból.

Jólrendezett halmaznak nevezünk egy halmazt, ha adott rajta egy teljes rendezés, ami jólrendezés, vagyis a halmaz minden nemüres részhalmazának van a rendezés szerint legkisebb eleme.

Tartalomjegyzék 1 Definíció 2 Tulajdonságok 3 Példák 4 Jólrendezési tétel 4.1 Tétel 4.2 Definíció 4.3 Bizonyítás 4.4 Ekvivalens állítások 4.5 Következmény 5 Hivatkozások

[szerkesztés] Definíció

Az rendezett halmazt jólrendezett halmaznak nevezzük, ha minden nemüres részhalmazának van legkisebb eleme.

[szerkesztés] Tulajdonságok

Egy jólrendezett halmaz nem tartalmazhat végtelen csökkenő sorozatot.

Az egész számok halmaza a szokásos rendezéssel nem alkot jólrendezett halmazt, de könnyen definiálható olyan rendezés, amely mellett a kapott struktúra jólrendezett. Legyen a rendezés a következő: x <_z y pontosan akkor, ha |x| < |y| vagy |x| = |y| és x < y. (Itt < a szokásos rendezést jelöli.)

Egy jólrendezett halmazban minden elemnek van rákövetkezője, azaz olyan elem, ami a nála nagyobbak közül a legkisebb. (Kivéve ha a halmaznak van legnagyobb eleme, akkor annak értelemszerűen nincs rákövetkezője.) Érdemes megemlíteni, hogy nem feltétlenül van minden elemnek megelőzője. Tekintsük azt a halmazt, ami két példányban tartalmazza a természtes számokat olymódon, hogy egy példányon belül a rendezés a szokásos, de a második példány minden eleme nagyobb az első példány elemeinél. (ω + ω: 0₁, 1₁, 2₁, ..., 0₂, 1₂, 2₂, ...). Ez a halmaz jólrendezett, de 0₂-nek nincs megelőzője. (0₁-nek sincs, de az a legkisebb elem a hamazban.)

A jólrendezett halmazok azért kényelmesek, mert alkalmazható bennük a transzfinit indukció (a teljes indukció általánosítása), melynek segítségével a halmaz elemeire olykor könnyen bizonyíthatunk állításokat.

[szerkesztés] Példák

Példák jólrendezett halmazra:

• Bármely véges teljesen rendezett halmaz.
• A természetes számok a szokásos rendezéssel.

Példák nem jólrendezett halmazra:

• Az egész számok a szokásos rendezéssel, hiszen a negatív számokból álló részhalmaznak nincs legkisebb eleme.
• A pozitív valós számok a szokásos rendezéssel, hiszen például a (0,1) nyílt intervallumnak nincs legkisebb eleme.

[szerkesztés] Jólrendezési tétel

[szerkesztés] Tétel

Minden halmaz jólrendezhető, azaz tetszőleges halmazon megadható olyan rendezés, amellyel a struktúra jólrendezett.

[szerkesztés] Definíció

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

[szerkesztés] Bizonyítás

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 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 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 . Legyen ezeknek az egyesítése , ahol 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 jólrendezett halmaz és M = H. 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 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.

[szerkesztés] 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

[szerkesztés] 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.

[szerkesztés] Hivatkozá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