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
5 Hivatkozások

[szerkesztés] Definíció

Az $(A, \leq)$ rendezett halmazt jólrendezett halmaznak nevezzük, ha $(A, \leq)$ 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. $(\mathbb{N}, < )$

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. $(\mathbb{Z}, < )$
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. $(\mathbb{R}, < )$

[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, \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\}$ .

[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 $(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.

[szerkesztés] Ekvivalens állítások

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

[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