1. Porównywanie mocy
Mówimy, że moc zbioru jest mniejsza lub równa mocy zbioru
, ozn.
, jeśli istnieje funkcja różnowartościowa z
w
.
2. Kraty zupełne
Częściowy porządek nazywamy kratą zupełną, jeśli dla każdego niepustego podzbioru
istnieje najmniejsze ograniczenie górne i najmniejsze ograniczenie dolne.
Theorem 1. Następujące warunki są równoważne dla danego częściowego porządku :
jest kratą zupełną,
- dla każdego niepustego podzbioru
istnieje najmniejsze ograniczenie górne,
- dla każdego niepustego podzbioru
istnieje najmniejsze ograniczenie dolne.
Zauważmy, że kraty zupełne muszą mieć element największy i najmniejszy, co wynika z zastosowania definicji kraty do całego zbioru .
Przykłady krat zupełnych.
Definition 1. Niech ,
Odwzorowanie
nazywamy monotonicznym, jeśli dla każdych
,
zachodzi
.
Przykłady odwzorowań monotonicznych.
Theorem 2. (Knaster-Tarski) Niech będzie kratą zupełną i niech
będzie odwzorowaniem monotonicznym. Wtedy istnieje najmniejszy punkt stały
, to znaczy element
taki, że
oraz jeśli
, to
.
Proof. Niech . Wtedy
jest zbiorem niepustym, gdyż element największy w
należy do
. Weźmy
, najmniejsze ograniczenie dolne zbioru
. Wtedy
. Istotnie, w przeciwnym razie
lub
. W pierwszym przpyadku dla każdego
zachodzi
, a zatem
. Wynikałoby z tego, że
jest ograniczeniem dolnym zbioru
większym od
, sprzeczność. W drugim przypadku
, a zatem
z monotoniczności
. Wynikałoby z tego, że
, co jednak byłoby sprzeczne z przypuszczeniem, że
jest mniejsze od wszystkich elementów
.
Pozostaje zauważyć, że jeśli jest punktem stałym
, to
. Zatem
, czyli
istotnie jest najmniejszym punktem stałym.
3. Lemat Banacha
Theorem 3. (lemat Banacha) Jeśli i
to istnieją rozłączne zbiory
oraz rozłączne zbiory
takie, że
Proof. Dowód tego twierdzenia jest oparty o twierdzenie Knastera-Tarskiego o punkcie stałym. Definiujemy odwozorowanie zadane wzorem,
Jeśli , to
. Po przejściu do dopełnień dostajemy
i dalej
. Zatem po ponownym przejściu do dopełnień dostajemy
, co dowodzi, że
, czyli
jest odwzorowaniem monotonicznym. Niech
będzie (najmniejszym) punktem stałym
,
i niech
,
. Wtedy
, to znaczy
Z powyższej równości wynika, że .
4. Twierdzenie Cantora-Bernsteina
Theorem 4. Jeśli oraz
to
.
Proof. Niech i
będą funkcjami różnowartościowymi. Z lematu Banacha wynika istnienie zbiorów
takich, że
,
,
,
. Bijekcję
definiujemy wzorem