Dobře objednaná sada

Dobře uspořádaná množina je lineárně uspořádaná množina M taková, že každá její neprázdná podmnožina má minimální prvek. Jinými slovy jde o fundovanou množinu s lineárním řádem.

Příklady

Prázdná sada je dobře uspořádaná.
Nejjednodušším příkladem nekonečné dobře uspořádané množiny je množina přirozených čísel s přirozeným uspořádáním.
Množina celých čísel není úplně uspořádaná, protože například mezi zápornými čísly neexistuje nejmenší . Lze to však udělat docela uspořádané definováním nestandardního vztahu „menší nebo rovno“ [1] , který označujeme a definujeme následovně: $\preccurlyeq$

a\preccurlyeq b,

jestli buď nebo nebo a

a=b,

|a|<|b|,

|a|=|b|

a<0<b.

Potom bude pořadí celých čísel: Zejména bude nejmenší záporné číslo.

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

-jeden

Nejjednodušším příkladem nepočitatelné dobře uspořádané množiny je sbírka všech spočítatelných řadových čísel uspořádaných podle vztahu . Za předpokladu hypotézy kontinua je jeho síla rovna síle kontinua. $\v$

Vlastnosti

Podle Zermelova teorému , jestliže jeden přijme axiom výběru , pak nějaká množina může být dobře uspořádaná. Navíc tvrzení, že pro jakoukoli množinu existuje úplné pořadí, je ekvivalentní axiomu výběru. Zejména v přítomnosti axiomu výběru může být množina reálných čísel kompletně uspořádána.
Jestliže X a Y jsou dvě dobře uspořádané množiny, pak jsou buď navzájem izomorfní , nebo právě jedna z nich je izomorfní s počátečním segmentem druhé.

Viz také

Transfinitní indukce

Literatura

N. K. Vereščagin, A. Šen. Část 1. Počátky teorie množin // Přednášky o matematické logice a teorii algoritmů. — 2. vyd., opraveno. - M. : MTSNMO , 2002. - 128 s.

Poznámky

↑ Donald Knuth . Umění programování, svazek I. Základní algoritmy. - M .: Mir , 1976. - S. 571 (15b). — 736 s.