Välbeställt set

En välordnad mängd är en linjärt ordnad mängd M så att någon av dess icke-tomma delmängder har ett minimalt element. Det är med andra ord en välgrundad uppsättning med linjär ordning.

Exempel

Den tomma uppsättningen är välordnad.
Det enklaste exemplet på en oändlig välordnad mängd är mängden naturliga tal med naturlig ordning.
Heltalsuppsättningen är inte helt ordnad, eftersom det till exempel inte finns det minsta bland negativa tal . Det kan dock göras ganska ordnat genom att definiera en icke-standard "mindre än eller lika med" relation [1] , som vi betecknar och definierar enligt följande: $\precurlyeq$

a\preccurlyeq b,

om antingen eller eller och

a=b,

|a|<|b|,

|a|=|b|

a<0<b.

Då blir heltalsordningen: I synnerhet kommer det att vara det minsta negativa talet.

0\preccurlyeq -1\preccurlyeq 1\preccurlyeq -2\preccurlyeq 2\dots

-ett

Det enklaste exemplet på en oräknelig välordnad mängd är samlingen av alla räknebara ordningstal ordnade efter relationen . Om man antar kontinuumhypotesen är dess kraft lika med kontinuumets kraft. $\i$

Egenskaper

Enligt Zermelos teorem , om man accepterar valets axiom , kan vilken uppsättning som helst vara välordnad. Dessutom är påståendet att det finns en fullständig ordning för varje uppsättning ekvivalent med valets axiom. I synnerhet, i närvaro av det valda axiomet, kan uppsättningen av reella tal ordnas helt.
Om X och Y är två välordnade uppsättningar, så är de antingen isomorfa till varandra, eller så är exakt en av dem isomorf till den andras initiala segment.

Se även

Transfinit induktion

Litteratur

N.K. Vereshchagin, A. Shen. Del 1. Början av mängdlära // Föreläsningar om matematisk logik och teori om algoritmer. — 2:a uppl., rättad. - M. : MTSNMO , 2002. - 128 sid.

Anteckningar

↑ Donald Knuth . Konsten att programmera, volym I. Grundläggande algoritmer. - M .: Mir , 1976. - S. 571 (15b). — 736 sid.