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

[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. (ω + ω: 01, 11, 21, ..., 02, 12, 22, ...). Ez a halmaz jólrendezett, de 02-nek nincs megelőzője. (01-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