Zbiory dobrze uporządkowane

Definicja dobrego porządku nie zależy od aksjomatu wyboru. W aksjomatyce ZF istnieje wiele zbiorów dobrze uporządkowanych. Jednak w obecności aksjomatu wyboru zbiory dobrze uporządkowane nabierają zupełnie nowego znaczenia.

Definicja 2.1.

Częściowy porządek $(A,\sqsubseteq)$ jest dobrym porządkiem, jeśli

jest porządkiem liniowym,

każdy niepusty podzbiór $A$ zawiera element najmniejszy względem $\sqsubseteq$ .

Mówimy wtedy, że zbiór $A$ jest dobrze uporządkowany przez $\sqsubseteq$ .

Istnienie zbiorów dobrze uporządkowanych nie jest nowością. Zdefiniowany w wykładzie 7 "Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje" zbiór liczb naturalnych jest dobrze uporządkowany na mocy dowiedzionych tam twierdzeń. Łatwo zauważyć, że również każda liczba naturalna $n$ wraz z relacją inkluzji jest zbiorem dobrze uporządkowanym. Ogólnie, następujący fakt jest prawdziwy

Fakt 2.2.

Dla dowolnego dobrego porządku $(A,\sqsubseteq)$ i dla dowolnego zbioru $B\subset A$ zbiór ten jest dobrze uporządkowany przez relację $\sqsubseteq\cap B\times B$ .

Dowód

Relacja $\sqsubseteq\cap B\times B$ to relacja $\sqsubseteq$ zawężona do elementów zbioru $B$ . Mamy dla każdego $a,b\in B$

$a\sqsubseteq b \iff a (\sqsubseteq\cap B\times B) b.$

Oczywistym wnioskiem jest, że zbiór $B$ jest uporządkowany liniowo przez $\sqsubseteq\cap B\times B$ . Pozostaje wykazać, że każdy podzbiór zbioru $B$ ma element najmniejszy. Ustalmy dowolne $C\subset B$ , ponieważ $B\subset A$ zbiór $C$ jest również podzbiorem $A$ i z definicji zbioru dobrze uporządkowanego wynika, że $C$ posiada element najmniejszy względem $\sqsubseteq$ . Ponieważ $C\subset B$ , to ten sam element jest elementem najmniejszym w $C$ względem $\sqsubseteq\cap B\times B$ , co kończy dowód faktu.

Dokładnej analizie własności zbiorów dobrze uporządkowanych jest poświęcony wykład 12 "Twierdzenie o indukcji. Liczby porządkowe. Zbiory liczb porządkowych. Twierdzenie o definiowaniu przez indukcje pozaskończoną". W dalszej części wykładu ograniczamy się do własności tych porządków bezpośrednio powiązanych z aksjomatem wyboru.