Jólrendezett halmaz

Az (A, ≤) rendezett halmazt jólrendezett halmaznak nevezzük, ha ${\displaystyle (A,\leq )}$  minden nemüres részhalmazának van legkisebb eleme.

Két jólrendezett halmazt izomorfnak nevezünk, ha van köztük rendezéstartó bijekció, azaz ${\displaystyle (A,\leq _{1})}$  izomorf ${\displaystyle (B,\leq _{2})}$ -vel, ha van olyan ${\displaystyle F:A\rightarrow B}$  bijekció, melyre a <₁ b pontosan akkor, ha F(a) <₂ F(b) minden ${\displaystyle a,b\in A}$ -ra.

Az izomorfia tehát a halmazok és a rajtuk definiált jólrendezések közös tulajdonsága, egy adott halmaznak is lehetnek egymással nem izomorf jólrendezései (sőt, pontosan a véges halmazok azok, amiknek minden (jól)rendezése izomorf egymással). A jólrendezett halmazok közötti izomorfizmus ekvivalenciareláció.
Izomorf jólrendezett halmazok közös tulajdonságát, "a jólrendezésük típusát" rendszámnak nevezzük.

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észetes számokat oly mó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 halmazban.)

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.

Példák jólrendezett halmazra:

• Bármely véges teljesen rendezett halmaz.
• A természetes számok a szokásos rendezéssel. ${\displaystyle (\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. ${\displaystyle (\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. ${\displaystyle (\mathbb {R} ,<)}$ 

Minden jólrendezett halmaz topologikus térré tehető. Ezekben a topológiákban kétféle elem van:

• Izolált pontok: a minimum és azok az elemek, amelyeknek van megelőzője
• Határpontok: az összes többi. Csak végtelen halmazban jelenhetnek meg. Azok a végtelen halmazok, amelyek nem tartalmaznak ilyen pontot, éppen az ω rendszámú halmazok. Ilyen például a természetes számok halmaza.

A részhalmazok lehetnek:

• Maximumot tartalmazó halmazok. Mivel minimumuk is van, ezért ezek kétszeresen jólrendezett halmazok.
• Önmagukban nem korlátos, de az egészben korlátos részhalmazok. Nincs maximumuk; szuprémumuk a részhalmazon kívülre, de a tartalmazó halmazon belülre esik. Ha a részhalmaz nem üres, akkor ez határpontja a részhalmaznak, és a tartalmazó halmaznak is. Ha a részhalmaz üres, akkor ez az egész halmaz minimuma.
• Egészben sem korlátos részhalmazok

Egy részhalmaz ko-véges, ha nem korlátos az egészben, vagy maximuma az egész halmaznak is maximuma.

A jólrendezett halmazban mint topologikus térben akkor és csak akkor van minden pontnak megszámlálható környezetbázisa, ha rendszáma kisebb ω₁-nél. Ez tovább ekvivalens azzal, hogy a halmaz megszámlálható, vagy rendszáma a legkisebb nem megszámlálható rendszám.

• 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