Logika i teoria mnogości/Wykład 11: Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Rogoda (dyskusja | edycje)
Nie podano opisu zmian
 
 
(Nie pokazano 103 wersji utworzonych przez 7 użytkowników)
Linia 1: Linia 1:
{tw}{Twierdzenie}[section]
{lem}[tw]{Lemmat}
{mtw}[tw]{Meta twierdzenie}
{fa}[tw]{Fakt}
{wn}[tw]{Wniosek}
{df}[tw]{Definicja}
{AZbioruPustego}{Aksjomat Zbioru Pustego}
{APary}{Aksjomat Pary}
{ASumy}{Aksjomat Sumy}
{ANieskonczonosci}{Aksjomat Nieskończoności}
{AWyrozniania}{Aksjomat Wyróżniania}
{AZbioruPotegowego}{Aksjomat Zbioru Potęgowego}
{AZastepowania}{Aksjomat Zastępowania}
{ARegularnosci}{Aksjomat Regularności}
{AWyboru}{Aksjomat Wyboru}
{}{0pt} {}{0pt}
{}{0in} {}{-0.5in}
{}{6.3in} {}{9in}
{cwicz}[section]
{obra}[section]
{hint}
==Wstęp==
==Wstęp==


Linia 32: Linia 8:
intuicją.
intuicją.


W tym wykładzie przedstawiamy szereg twierdzeń które są równoważne,
W tym wykładzie przedstawiamy szereg twierdzeń, które są równoważne
lub wynikają z aksjomatu wyboru. Zanim przejdziemy do wypowiedzi
lub wynikają z aksjomatu wyboru. Zanim przejdziemy do wypowiedzi
tych faktów wprowadzimy jeszcze jeden koncept.
tych faktów, wprowadzimy jeszcze jeden koncept.


==Zbiory dobrze uporządkowane==
==Zbiory dobrze uporządkowane==
Linia 42: Linia 18:
Jednak w obecności aksjomatu wyboru zbiory dobrze uporządkowane
Jednak w obecności aksjomatu wyboru zbiory dobrze uporządkowane
nabierają zupełnie nowego znaczenia.
nabierają zupełnie nowego znaczenia.
{{definicja|2.1.||


Częściowy porządek <math>(A,\sqsubseteq)</math> jest dobrym porządkiem, jeśli
Częściowy porządek <math>(A,\sqsubseteq)</math> jest dobrym porządkiem, jeśli
Linia 49: Linia 27:
* każdy niepusty podzbiór <math>A</math> zawiera element najmniejszy względem <math>\sqsubseteq</math>.
* każdy niepusty podzbiór <math>A</math> zawiera element najmniejszy względem <math>\sqsubseteq</math>.


Mówimy wtedy, że zbiór <math>A</math> jest ''dobrze uporządkowany'' przez
Mówimy wtedy, że zbiór <math>A</math> jest dobrze uporządkowany przez
<math>\sqsubseteq</math>.
<math>\sqsubseteq</math>.
}}
Istnienie zbiorów dobrze uporządkowanych nie jest nowością. Zdefiniowany w [[Logika i teoria mnogości/Wykład 7: Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje|Wykładzie 7]] zbiór liczb naturalnych jest dobrze uporządkowany na mocy dowiedzionych tam twierdzeń. Łatwo zauważyć,
że również każda liczba naturalna <math>n</math> wraz z relacją inkluzji jest zbiorem dobrze uporządkowanym. Ogólnie, następujący fakt jest prawdziwy


Istnienie zbiorów dobrze uporządkowanych nie jest nowością.
{{fakt|2.2.||
Zdefiniowany w Wykład 7 zbiór liczb naturalnych jest dobrze
uporządkowany na mocy dowiedzionych tam twierdzeń. Łatwo zauważyć,
że również każda liczba naturalna <math>n</math> wraz z relacją inkluzji jest
zbiorem dobrze uporządkowanym. Ogólnie, następujący fakt jest
prawdziwy
 
{{fakt|[Uzupelnij]||


Dla dowolnego dobrego porządku <math>(A,\sqsubseteq)</math> i dla dowolnego
Dla dowolnego dobrego porządku <math>(A,\sqsubseteq)</math> i dla dowolnego
Linia 66: Linia 40:
}}
}}


{{dowod|[Uzupelnij]||
{{dowod|||


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


<center><math>a\sqsubseteq b \iff a (\sqsubseteq\cap B\times B) b.
<center><math>a\sqsubseteq b \iff a (\sqsubseteq\cap B\times B) b</math></center>
</math></center>


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


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


==Aksjomat wyboru i twierdzenia mu równoważne==
==Aksjomat wyboru i twierdzenia mu równoważne==


część wykładu zaczniemy od przytoczenia aksjomatu wyboru w
część wykładu zaczniemy od przytoczenia aksjomatu wyboru w
postaci w jakiej został wprowadzony w Wykład 4.
postaci, w jakiej został wprowadzony w [[Logika i teoria mnogości/Wykład 4: Teoria mnogości ZFC. Operacje na zbiorach|Wykładzie 4]].


Następująca formuła jest prawdziwa
'''Aksjomat Wyboru'''. Następująca formuła jest prawdziwa:


<center><math>\forall x\; \left( \emptyset\notin x\land \forall y\forall z\; (z\in
<math>\forall x\; \left( \emptyset\notin x\land \forall y\forall z\; (z\in x\land y\in x)\implies (z=y \lor z\cap y = \emptyset)\right)\implies \exists w \forall v\;(v\in x \implies \exists u\;v\cap w=\{u\})</math>.
x\land y\in x)\implies (z=y \lor z\cap y = \emptyset)\right)\implies
\exists w \forall v\; (v\in x \implies \exists u\;v\cap w=\{u\})
</math></center>


Aksjomat ten mówi, że jeśli <math>x</math> jest rodziną niepustych, parami
[[File:logika-3.1.svg|350x250px|thumb|right|Rysunek 1]]
rozłącznych zbiorów to istnieje zbiór mający z każdym elementem <math>x</math>
dokładnie jeden element wspólny. Zbiór <math>w</math>, którego istnienie
gwarantuje aksjomat wyboru "wybiera" z każdego elementu rodziny
dokładnie jeden element.


{obra}{1}{Obrazek {section}.{obra}}Zbiory jako pionowe, nieregularne obszary, zbiór
Aksjomat ten mówi, że jeśli <math>x</math> jest rodziną niepustych, parami rozłącznych zbiorów, to istnieje zbiór mający z każdym elementem <math>x</math> dokładnie jeden element wspólny. Zbiór <math>w</math>, którego istnienie gwarantuje aksjomat wyboru, "wybiera" z każdego elementu rodziny dokładnie jeden element (rysynek 1). Zbiory jako pionowe, nieregularne obszary, zbiór
wybierający jako poziomy zbiór przecinający każdy z nich na
wybierający jako poziomy zbiór przecinający każdy z nich na dokładnie jednym elemencie.
dokładnie jednym elemencie


W dalszej części wykładu prezentujemy parę twierdzeń równoważnych
W dalszej części wykładu prezentujemy kilka twierdzeń równoważnych
aksjomatowi wyboru. To znaczy, że na gruncie aksjomatyki ZF, bez
aksjomatowi wyboru. To znaczy, że na gruncie aksjomatyki ZF, bez
aksjomatu wyboru, założenie prawdziwości któregokolwiek z tych
aksjomatu wyboru, założenie prawdziwości któregokolwiek z tych
Linia 121: Linia 76:


Aby wykazać równoważność między aksjomatem wyboru a poniższymi
Aby wykazać równoważność między aksjomatem wyboru a poniższymi
twierdzeniami pokażemy, że każde twierdzenie implikuje następne i że
twierdzeniami, pokażemy, że każde twierdzenie implikuje następne i że
ostatnie implikuje aksjomat wyboru. Jest to najprostszy sposób na
ostatnie implikuje aksjomat wyboru. Jest to najprostszy sposób na
wykazanie równoważności.
wykazanie równoważności.
Linia 131: Linia 86:
rodziny zbiorów wybieraliśmy elementy przez utworzenie zbioru. Aby
rodziny zbiorów wybieraliśmy elementy przez utworzenie zbioru. Aby
możliwe było wybranie ''dokładnie'' jednego elementu z każdego
możliwe było wybranie ''dokładnie'' jednego elementu z każdego
zbioru niezbędne było założenie o rozłączności tych zbiorów.
zbioru, niezbędne było założenie o rozłączności tych zbiorów.
Poniższe twierdzenie mówi o istnieniu funkcji wybierającej elementy
Poniższe twierdzenie mówi o istnieniu funkcji wybierającej elementy
ze zbiorów.
ze zbiorów.


{{twierdzenie|[Uzupelnij]||
<span id="twierdzenie_3_1">{{twierdzenie|3.1.||


Dla dowolnej rodziny niepustych zbiorów istnieje funkcja, która
Dla dowolnej rodziny niepustych zbiorów istnieje funkcja, która
każdem zbiorowi w tej rodzinie przyporządkowuje któryś z jego
każdemu zbiorowi w tej rodzinie przyporządkowuje któryś z jego
elementów. Formalnie
elementów. Formalnie


<center><math>\forall x\; \emptyset\notin x \implies \exists f\; f:x\rightarrow\bigcup x
<center><math>\forall x\; \emptyset\notin x \implies \exists f\; f:x\rightarrow\bigcup x \land\left( \forall y\; y\in x \implies f(y)\in y\right)</math></center>
\land\left( \forall y\; y\in x \implies f(y)\in y\right)
</math></center>


}}
}}</span>


Poniżej przedstawiamy dowód, na gruncie ZF, że aksjomat
Poniżej przedstawiamy dowód, na gruncie ZF, że aksjomat
wyboru implikuje powyższe twierdzenie.
wyboru implikuje powyższe twierdzenie.


{{dowod|[Uzupelnij]||
{{dowod|||
[Aksjomat wyboru implikuje Twierdzenie&nbsp;[[##tw:choicefunction|Uzupelnic tw:choicefunction|]]]
 
Ustalmy dowolny, nie zawierający zbioru pustego, zbiór <math>x</math>.
Aksjomat wyboru implikuje Twierdzenie 3.1 (patrz [[#twierdzenie_3_1|Twierdzenie 3.1.]]) Ustalmy dowolny, niezawierający zbioru pustego, zbiór <math>x</math>. Skonstruujemy zbiór <math>x_1</math>, do którego stosować będziemy aksjomat wyboru. Zbiór
Skonstruujemy zbiór <math>x_1</math> do którego stosować będziemy aksjomat
wyboru. Zbiór


<center><math>x_1 = \{\{y\}\times y\,:\, y\in x\}</math></center>
<center><math>x_1 = \{\{y\}\times y\,:\, y\in x\}</math></center>


jest rodziną zbiorów parami rozłącznych -- elementy pochodzące z
jest rodziną zbiorów parami rozłącznych - elementy pochodzące z różnych zbiorów <math>x</math> różnią się w <math>x_1</math> na pierwszej współrzędnej. Do zbioru <math>x_1</math> stosujemy aksjomat wyboru i otrzymujemy zbiór <math>w\subset x\times \bigcup x</math>. Ponieważ z każdego zbioru <math>x_1</math> wybraliśmy dokładnie jeden element, to <math>w</math> jest funkcją z <math>x</math> do <math>\bigcup x</math>. Definicja <math>x_1</math> gwarantuje również, że <math>w(y)\in y</math> dla każdego <math>y\in x</math>. Wnioskujemy, że <math>w</math> może być wzięte jako <math>f</math> i że aksjomat wyboru implikuje Twierdzenie 3.1 (patrz [[#twierdzenie_3_1|Twierdzenie 3.1.]]).
różnych zbiorów <math>x</math> różnią się w <math>x_1</math> na pierwszej współrzędnej. Do
zbioru <math>x_1</math> stosujemy aksjomat wyboru i otrzymujemy zbiór
<math>w\subset x\times \bigcup x</math>. Ponieważ z każdego zbioru <math>x_1</math>
wybraliśmy dokładnie jeden element, to <math>w</math> jest funkcją z <math>x</math> do
<math>\bigcup x</math>. Definicja <math>x_1</math> gwarantuje również, że <math>w(y)\in y</math> dla
każdego <math>y\in x</math>. Wnioskujemy, że <math>w</math> może być wzięte jako <math>f</math> i że
aksjomat wyboru implikuje Twierdzenie&nbsp;[[##tw:choicefunction|Uzupelnic tw:choicefunction|]].
}}
}}


Kolejny fakt, równoważny aksjomatowi wyboru, przedstawiamy
Kolejny fakt, równoważny aksjomatowi wyboru, przedstawiamy
w formie ćwiczenia:
w formie ćwiczenia:
{cwicz}{1}{Ćwiczenie {section}.{cwicz}} 
 
Wykaż, że stwierdzenie "Dla każdej surjekcji <math>f:x\rightarrow y</math> istnieje
<span id="cwiczenie_3_1">
iniekcja <math>g:y\rightarrow x</math> taka, że <math>f\circ g</math> jest funkcją
{{cwiczenie|3.1||
identycznościową na <math>y</math>." jest równoważne aksjomatowi wyboru na
 
gruncie ZF. {hint}{0}
Wykaż, że stwierdzenie "dla każdej surjekcji <math>f:x\rightarrow y</math> istnieje iniekcja <math>g:y\rightarrow x</math> taka, że <math>f\circ g</math> jest funkcją identycznościową na <math>y</math>" jest równoważne aksjomatowi wyboru na gruncie ZF.
; Solution.
}}
: Pokażmy najpierw, że z aksjomatu wyboru
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
wynika powyższe stwierdzenie. Ustalmy dowolną surjekcję <math>f:x\rightarrow y</math>
Pokażmy najpierw, że z aksjomatu wyboru wynika powyższe stwierdzenie. Ustalmy dowolną surjekcję <math>f:x\rightarrow y</math>
i zdefiniujmy zbiór <math>z</math> w następujący sposób:
i zdefiniujmy zbiór <math>z</math> w następujący sposób:


<center><math>z = \{w\subset x\,:\, \exists v\; v\in y \land w =
<center><math>z = \{w\subset x\,:\, \exists v\; v\in y \land w =
\vec{f}^{-1}(\{v\})\}.
\vec{f}^{-1}(\{v\})\}</math></center>
</math></center>


Jest to zbiór składający się z przeciwobrazów singletonów z <math>y</math>.
Jest to zbiór składający się z przeciwobrazów singletonów z <math>y</math>. Ponieważ <math>f</math> jest surjekcją <math>\emptyset\notin z</math>, a ponieważ <math>f</math> jest funkcją każde dwa różne elementy <math>z</math> przecinają się pusto. W związku z tym do zbioru <math>z</math> możemy zastosować aksjomat wyboru i otrzymać zbiór <math>u</math> mający dokładnie jeden element wspólny z każdym elementem <math>z</math>, wtedy
Ponieważ <math>f</math> jest surjekcją <math>\emptyset\notin z</math>, a ponieważ <math>f</math> jest
funkcją każde dwa różne elementy <math>z</math> przecinają się pusto. W związku
z tym do zbioru <math>z</math> możemy zastosować aksjomat wyboru i otrzymać
zbiór <math>u</math> mający dokładnie jeden element wspólny z każdym elementem
<math>z</math>, wtedy


<center><math>g = \{(v,w)\in y\times x\,:\, v\in y \;\land\; w\in x\;\land\;
<center><math>g = \{(v,w)\in y\times x\,:\, v\in y \;\land\; w\in x\;\land\;
Linia 195: Linia 133:
</math></center>
</math></center>


jest funkcją przekształcającą <math>y</math> w <math>x</math> i taką, że <math>f\circ g </math> jest
jest funkcją przekształcającą <math>y</math> w <math>x</math> i taką, że <math>f\circ g</math> jest identycznością na <math>y</math>. Fakt, że <math>g</math> jest funkcją jest oczywisty z
identycznością na <math>y</math>. Fakt, że <math>g</math> jest funkcją jest oczywisty z
definicji i z własności <math>u</math>. Aby dowieść własności złożenia ustalmy <math>v\in y</math>, wtedy <math>g(v)=w</math> implikuje <math>w\in\vec{f}^{-1}(\{v\})</math>, czyli <math>f(w) = v</math>, co dowodzi implikacji.
definicji i z własności <math>u</math>. Aby dowieść własności złożenia ustalmy
 
<math>v\in y</math>, wtedy <math>g(v)=w</math> implikuje <math>w\in\vec{f}^{-1}(\{v\})</math>, czyli
Aby wykazać, że stwierdzenie implikuje aksjomat wyboru ustalmy dowolny zbiór <math>x</math> taki, że <math>\emptyset\notin x</math>, oraz, że każde dwa różne elementy zbioru <math>x</math> są rozłączne. Zdefiniujmy funkcję <math>f:\bigcup x \rightarrow x</math> tak, że
<math>f(w) = v</math>, co dowodzi implikacji.
 
<center><math>f(w) = z \iff w\in z</math></center>


Aby wykazać, że stwierdzenie implikuje aksjomat wyboru ustalmy
Relacja <math>f</math> jest funkcją, ponieważ każdy element <math>\bigcup x</math> należy do dokładnie jednego zbioru w <math>x</math> i jest surjekcją, ponieważ <math>\emptyset \notin x</math>. Na mocy powyższego stwierdzenia istnieje funkcja <math>g:x\rightarrow \bigcup x</math> taka, że <math>f\circ g</math> jest identycznością na <math>x</math>. Ustalmy <math>z\in x</math>, wtedy <math>f(g(z)) = z</math> wtedy i tylko wtedy, kiedy <math>g(z)\in z</math>, a ponieważ <math>g</math> jest funkcją, to zbiór <math>\vec{g}(x)</math> jest zbiorem, który z każdym elementem <math>x</math> ma dokładnie jeden element wspólny. Czyli ze stwierdzenia powyżej wynika aksjomat wyboru.
dowolny zbiór <math>x</math> taki, że <math>\emptyset\notin x</math>, oraz, że każde dwa
</div></div>
różne elementy zbioru <math>x</math> są rozłączne. Zdefiniujmy funkcję
<math>f:\bigcup x \rightarrow x</math> tak, że


<center><math>f(w) = z \iff w\in z.
</span>
</math></center>


Relacja <math>f</math> jest funkcją, ponieważ każdy element <math>\bigcup x</math> należy
do dokładnie jednego zbioru w <math>x</math> i jest surjekcją, ponieważ
<math>\emptyset \notin x</math>. Na mocy powyższego stwierdzenia istnieje
funkcja <math>g:x\rightarrow \bigcup x</math> taka, że <math>f\circ g</math> jest identycznością
na <math>x</math>. Ustalmy <math>z\in x</math>, wtedy <math>f(g(z)) = z</math> wtedy i tylko wtedy,
kiedy <math>g(z)\in z</math>, a ponieważ <math>g</math> jest funkcją, to zbiór
<math>\vec{g}(x)</math> jest zbiorem, który z każdym elementem <math>x</math> ma dokładnie
jeden element wspólny. Czyli ze stwierdzenia powyżej wynika aksjomat
wyboru.
{Koniec ćwiczenia {section}.{cwicz}} 
===Twierdzenia dotyczące porządków===
===Twierdzenia dotyczące porządków===


Kolejne dwa twierdzenia dotyczą częściowych porządków. Pierwsze z
[[grafika:Hausdorff.jpg|thumb|right||Felix Hausdorff (1868-1942)<br>[[Biografia Hausdorff|Zobacz biografię]]]]Kolejne dwa twierdzenia dotyczą częściowych porządków. Pierwsze z
nich gwarantuje istnienie maksymalnych łańcuchów
nich gwarantuje istnienie maksymalnych łańcuchów.
 
<span id="twierdzenie_3_2">{{twierdzenie|3.2. [Zasada maksimum Felixa Hausdorff'a]||


{{twierdzenie|[Uzupelnij]||
[Zasada maksimum Felix Hausdorff 'a]
W każdym zbiorze częściowo uporządkowanym istnieje maksymalny, pod
W każdym zbiorze częściowo uporządkowanym istnieje maksymalny, pod
względem inkluzji, łańcuch.
względem inkluzji, łańcuch.
}}
}}</span>


Zgodnie z przyjętą strategią postępowania wykażemy, że
Zgodnie z przyjętą strategią postępowania wykażemy, że
Twierdzenie&nbsp;[[##tw:choicefunction|Uzupelnic tw:choicefunction|]] implikuje zasadę maksimum
Twierdzenie 3.1 (patrz [[#twierdzenie_3_1|twierdzenie 3.1.]]) implikuje zasadę maksimum [[Biografia Hausdorff|Felixa Hausdorffa]].
Felix Hausdorff'a


{{dowod|[Uzupelnij]||
{{dowod|||
[Twierdzenie&nbsp;[[##tw:choicefunction|Uzupelnic tw:choicefunction|]] implikuje zasadę maksimum Felix Hausdorff'a]
Twierdzenie 3.1 (patrz [[#twierdzenie_3_1|twierdzenie 3.1.]]) implikuje zasadę maksimum Felixa Hausdorffa.
Dowód tej implikacji opiera się na Twierdzeniu Bourbakiego-Witta z
Dowód tej implikacji opiera się na Twierdzeniu Bourbakiego-Witta z Wykładu 10 (patrz [[Logika i teoria mnogości/Wykład 10.2| Twierdzenie Bourbakiego-Witta]]). Ustalmy dowolny zbiór częściowo uporządkowany <math>(A,\sqsubseteq)</math>. Jeśli <math>A=\emptyset</math>, to zbiór ten posiada dokładnie jeden łańcuch i fakt jest dowiedziony. Jeśli <math>A\neq\emptyset</math>,
Wykład 10. Ustalmy dowolny zbiór częściowo uporządkowany
<math>(A,\sqsubseteq)</math>. Jeśli <math>A=\emptyset</math> to zbiór ten posiada dokładnie
jeden łańcuch i fakt jest dowiedziony. Jeśli <math>A\neq\emptyset</math>,
oznaczmy przez <math>(B,\subset)</math> zbiór częściowo uporządkowany
oznaczmy przez <math>(B,\subset)</math> zbiór częściowo uporządkowany
składający się z łańcuchów w <math>(A,\sqsubseteq)</math> uporządkowanych przez
składający się z łańcuchów w <math>(A,\sqsubseteq)</math> uporządkowanych przez inkluzję
inkluzję


<center><math>B = \{C\subset A\,:\, C \text{ jest uporządkowany liniowo przez
}\}
</math></center>


Zbiór częściowo uporządkowany <math>(B,\subset)</math> jest łańcuchowo
<center><math>B = \{C\subset A\,:\, C</math> jest uporządkowany liniowo przez <math>\sqsubseteq\}</math></center>
zupełny. Aby to pokazać ustalmy dowolny, uporządkowany liniowo przez
 
inkluzję, zbiór <math>D\subset B</math>. Jeśli <math>\bigcup D</math> należy do <math>B</math> to
Zbiór częściowo uporządkowany <math>(B,\subset)</math> jest łańcuchowo zupełny. Aby to pokazać, ustalmy dowolny, uporządkowany liniowo przez inkluzję zbiór <math>D\subset B</math>. Jeśli <math>\bigcup D</math> należy do <math>B</math>, to jest to niewątpliwie supremum zbioru <math>D</math>. Aby wykazać, że <math>\bigcup D</math> jest elementem <math>B</math>, należy wykazać, że jest on uporządkowany liniowo przez <math>\sqsubseteq</math>. Weźmy dwa elementy <math>\bigcup D</math> - <math>x</math> i <math>y</math>. Istnieje <math>C_x\in D</math> i <math>C_y\in D</math> takie, że <math>x\in C_x</math>, a <math>y\in C_y</math>. Ponieważ <math>D</math> jest łańcuchem, to, bez straty ogólności, możemy założyć, że <math>C_x\subset C_y</math>. Wtedy, zarówno <math>x</math> jak i <math>y</math>, należą do <math>C_y</math> i
jest to niewątpliwie supremum zbioru <math>D</math>. Aby wykazać że <math>\bigcup D</math>
ponieważ <math>C_y\in B</math>, wnioskujemy, że <math>x</math> i <math>y</math> są porównywalne. Wykazaliśmy, że dowolne dwa elementy <math>\bigcup D</math> są porównywalne, czyli że <math>\bigcup D</math> jest uporządkowany liniowo przez <math>\sqsubseteq</math>.
jest elementem <math>B</math> należy wykazać, że jest on uporządkowany liniowo
przez <math>\sqsubseteq</math>. Weźmy dwa elementy <math>\bigcup D</math> -- <math>x</math> i <math>y</math>. Istnieje
<math>C_x\in D</math> i <math>C_y\in D</math> takie, że <math>x\in C_x</math> a <math>y\in C_y</math>. Ponieważ
<math>D</math> jest łańcuchem to, bez straty ogólności, możemy założyć, że
<math>C_x\subset C_y</math>. Wtedy zarówno <math>x</math>, jak i <math>y</math> należą do <math>C_y</math> i
ponieważ <math>C_y\in B</math> wnioskujemy, że <math>x</math> i <math>y</math> są porównywalne.
Wykazaliśmy, że dowolne dwa elementy <math>\bigcup D</math> są porównywalne,
czyli, że <math>\bigcup D</math> jest uporządkowany liniowo przez <math>\sqsubseteq</math>.


Na mocy Twierdzenia&nbsp;[[##tw:choicefunction|Uzupelnic tw:choicefunction|]] definiujemy funkcję
Na mocy Twierdzenia 3.1 (patrz [[#twierdzenie_3_1|Twierdzenie 3.1.]]) definiujemy funkcję wyboru <math>f</math> dla zbioru <math>\mathcal{P}(A)\setminus\{\emptyset\}</math> zwracającą, dla każdego niepustego podzbioru <math>A</math>, jego element. Twierdzenie Bourbakiego-Witta będziemy stosować do funkcji <math>g</math> przeprowadzającej <math>B</math>  w <math>B</math> i zdefiniowanej następująco:
wyboru <math>f</math> dla zbioru <math>\mathcal{P}(A)\setminus\{\emptyset\}</math> --
<br>
zwracającą, dla każdego niepustego podzbioru <math>A</math>, jego element.
Twierdzenie Bourbakiego-Witta będziemy stosować do funkcji <math>g</math>
przeprowadzającej <math>B</math>  w <math>B</math> i zdefiniowanej następująco:


<center><math>g(C)=\begincases
<center><math>g(C)=\left\{
C\cup \{f(C')\}&\text{jeśli </math>C'<math>, zbiór elementów porównywalnych z
\begin{array}{ll}
każdym elementem </math>C<math>, jest niepusty}\\
C\cup \{f(C')\},& \quad \text{jeśli } C', \text{zbiór elementów porównywalnych z każdym elementem } C, \text{jest niepusty}\\
C&\text{w przeciwnym przypadku}.
C ,& \quad \text{w przeciwnym przypadku}. \end{array} \right.</math>.</center>
\endcases
</math></center>


Funkcja <math>g</math> dostaje, jako argument łańcuch w <math>(A,\sqsubseteq)</math>
<br>
oznaczony przez <math>C</math> i przy pomocy funkcji <math>f</math> rozszerza&nbsp;(jeśli jest
Funkcja <math>g</math> dostaje jako argument łańcuch w <math>(A,\sqsubseteq)</math> oznaczony przez <math>C</math> i przy pomocy funkcji <math>f</math> rozszerza&nbsp;(jeśli jest to możliwe) <math>C</math> o jeden element porównywalny ze wszystkimi elementami <math>C</math>, otrzymując w ten sposób nowy, większy łańcuch.
to możliwe) <math>C</math> o jeden element porównywalny ze wszystkimi
elementami <math>C</math> otrzymując w ten sposób nowy, większy łańcuch.


Zbiór <math>(B,\subset)</math> i funkcja <math>g</math> spełniają założenia
Zbiór <math>(B,\subset)</math> i funkcja <math>g</math> spełniają założenia Twierdzenia Bourbakiego-Witta i, na jego mocy, istnieje punkt stały <math>g</math>, czyli zbiór <math>D</math> taki, że <math>g(D) = D</math>. To gwarantuje, że zbiór <math>D'</math> elementów porównywalnych z każdym elementem <math>D</math> jest pusty, czyli że <math>D</math> jest maksymalnym pod względem inkluzji łańcuchem w <math>A</math>.
Twierdzenia Bourbakiego-Witta i, na jego mocy, istnieje punkt stały
<math>g</math>, czyli zbiór <math>D</math> taki, że <math>g(D) = D</math>. To gwarantuje, że zbiór
<math>D'</math> elementów porównywalnych z każdym elementem <math>D</math> jest pusty,
czyli, że <math>D</math> jest maksymalnym pod względem inkluzji łańcuchem w
<math>A</math>.
}}
}}


Równoważną wersję zasady Felix Hausdorff'a pozostawiamy jako
Równoważną wersję zasady [[Biografia Hausdorff|Felixa Hausdorffa]] pozostawiamy jako ćwiczenie.
ćwiczenie.
 
{cwicz}{1}{Ćwiczenie {section}.{cwicz}} 
{{cwiczenie|3.2||
 
Wykaż, na gruncie ZF, że następujące stwierdzenie jest równoważne
Wykaż, na gruncie ZF, że następujące stwierdzenie jest równoważne
zasadzie Felix Hausdorff'a: "W każdym zbiorze częściowo uporządkowanym
zasadzie Felixa Hausdorffa: "W każdym zbiorze częściowo uporządkowanym każdy łańcuch jest zawarty w maksymalnym, pod względem inkluzji, łańcuchu".
każdy łańcuch jest zawarty w maksymalnym, pod względem inkluzji,
}}
łańcuchu." {hint}{0}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
; Solution.
Aby udowodnić zasadę maksimum [[Biografia Hausdorff|Felixa Hausdorffa]] używając powyższego stwierdzenia, wystarczy, dla dowolnego zbioru częściowo uporządkowanego znaleźć jeden łańcuch i z faktu że jest on zawarty w łańcuchu maksymalnym wynika, że łańcuch maksymalny istnieje. Dla dowolnego zbioru częściowo uporządkowanego możemy znaleźć jego podzbiór  <math>(\emptyset,\emptyset)</math>, który jest łańcuchem i w związku z tym jest zawarty w jakimś łańcuchu maksymalnym, co należało wykazać.
: Aby udowodnić zasadę maksimum Felix Hausdorff'a
 
używając powyższego stwierdzenia, wystarczy, dla dowolnego zbioru
Aby wykazać powyższe stwierdzenie używając zasady [[Biografia Hausdorff|Felixa Hausdorffa]], ustalmy dowolny zbiór częściowo uporządkowany <math>(A,\sqsubseteq)</math> i dowolny łańcuch <math>C\subset A</math>. Rozważmy zbiór <math>B\subset A</math> taki, że
częściowo uporządkowanego znaleźć jeden łańcuch i z faktu że jest on
zawarty w łańcuchu maksymalnym wynika, że łańcuch maksymalny
istnieje. Dla dowolnego zbioru częściowo uporządkowanego możemy
znaleźć jego podzbiór  <math>(\emptyset,\emptyset)</math> który jest
łańcuchem i w związku z tym jest zawarty w jakimś łańcuchu
maksymalnym, co należało wykazać.


Aby wykazać powyższe stwierdzenie używając zasady Felix Hausdorff'a
<center><math>B = \{a\in A\ : a \text{ jest porównywalne z każdym elementem }C\}</math></center>
ustalmy dowolny zbiór częściowo uporządkowany <math>(A,\sqsubseteq)</math> i
dowolny łańcuch <math>C\subset A</math>.  Rozważmy zbiór <math>B\subset A</math> taki,
że


<center><math>B = \{a\in A\,:\, \text{</math>a<math> jest porównywalne z każdym elementem
Ponieważ <math>C</math> jest łańcuchem, mamy <math>C\subset B</math>. Zastosujmy zasadę Hausdorff'a do zbioru <math>B</math> uporządkowane przez <math>\sqsubseteq</math> zawężone do <math>B</math>. Gwarantuje ona istnienie łańcucha maksymalnego <math>D</math> w <math>B</math>. Ponieważ każdy z elementów zbioru <math>C</math> był porównywalny z każdym elementem zbioru <math>B</math>&nbsp;(i w szczególności z każdym elementem zbioru <math>D</math>), to <math>D\cup C</math> jest łańcuchem i maksymalność <math>D</math> gwarantuje <math>C\subset D</math>. Pozostaje wykazać, że <math>D</math> jest maksymalnym łańcuchem w <math>A</math>. Gdyby tak nie było to istniało by <math>a\in A\setminus D</math> porównywalne z każdym elementem <math>D</math>. Wtedy <math>a</math> byłoby porównywalne z każdym elementem <math>C</math> i w związku z tym <math>a\in B</math> i <math>a\in B\setminus D</math>, co przeczy maksymalności <math>D</math> w <math>B</math>. W związku z tym <math>D</math> jest maksymalnym łańcuchem w <math>A</math> i zawiera <math>C</math> - stwierdzenie zostało dowiedzione.
</math>C<math>}\}.
</div></div>
</math></center>
 
 
Kolejne z równoważnych aksjomatowi wyboru twierdzeń nosi nazwę Lematu [[Biografia Zorn|Maxa Augusta Zorna]]. Nazwa ta ma korzenie historyczne i dlatego pozostawiamy ją w tym brzmieniu.


Ponieważ <math>C</math> jest łańcuchem, mamy <math>C\subset B</math>. Zastosujmy zasadę
[[grafika:Zorn.jpg|thumb|right||Max August Zorn (1906-1993)<br>[[Biografia Zorn|Zobacz biografię]]]]{{twierdzenie|3.3. [Lemat Maxa Augusta Zorna]||
Hausdorff'a do zbioru <math>B</math> uporządkowane przez <math>\sqsubseteq</math> zawężone do <math>B</math>.
Gwarantuje ona istnienie łańcucha maksymalnego <math>D</math> w <math>B</math>. Ponieważ
każdy z elementów zbioru <math>C</math> był porównywalny z każdym elementem
zbioru <math>B</math>&nbsp;(i w szczególności z każdym elementem zbioru <math>D</math>) to
<math>D\cup C</math> jest łańcuchem i maksymalność <math>D</math> gwarantuje <math>C\subset
D</math>. Pozostaje wykazać, że <math>D</math> jest maksymalnym łańcuchem w <math>A</math>.
gdyby tak nie było to istniało by <math>a\in A\setminus D</math> porównywalne z
każdym elementem <math>D</math>. Wtedy <math>a</math> byłoby porównywalne z każdym
elementem <math>C</math> i w związku z tym <math>a\in B</math> i <math>a\in B\setminus D</math>, co
przeczy maksymalności <math>D</math> w <math>B</math>.  W związku z tym <math>D</math> jest
maksymalnym łańcuchem w <math>A</math> i zawiera <math>C</math> -- stwierdzenie zostało
dowiedzione.
{Koniec ćwiczenia {section}.{cwicz}} 
Kolejne z równoważnych aksjomatowi wyboru twierdzeń nosi
nazwę Lematu Max August Zorn'a. Nazwa ta ma korzenie historyczne i dlatego
pozostawiamy ją w tym brzmieniu.


{{twierdzenie|[Uzupelnij]||
Jeśli w pewnym zbiorze częściowo uporządkowanym, każdy łańcuch jest
[Lemat Max August Zorn'a]
ograniczony od góry, to istnieje w nim element maksymalny.
Jeśli w pewnym zbiorze częściowo uporządkowanym każdy łańcuch jest
ograniczony od góry to istnieje w nim element maksymalny.
}}
}}


Dowodzimy kolejną implikację
Dowodzimy kolejną implikację


{{dowod|[Uzupelnij]||
{{dowod|||
[Zasada maksimum Felix Hausdorff'a implikuje Lemat Max August Zorn'a]
 
Dowód tej implikacji jest bardzo prosty. Wybierzmy dowolny zbiór
Zasada maksimum Felixa Hausdorffa implikuje Lemat Maxa Augusta Zorna. Dowód tej implikacji jest bardzo prosty. Wybierzmy dowolny zbiór częściowo uporządkowany spełniający założenia Lematu Maxa Augusta Zorna, czyli taki, że każdy łańcuch jest w nim ograniczony od góry. Na mocy zasady maksimum Felixa Hausdorffa istnieje w tym zbiorze łańcuch maksymalny pod względem inkluzji. Łańcuch ten posiada ograniczenie górne, które musi być elementem  łańcucha i równocześnie elementem maksymalnym zbioru. Jeśliby tak nie było, to dodając element istotnie większy od tego ograniczenia do łańcucha danego przez zasadę maksimum Hausdorffa, uzyskalibyśmy łańcuch istotnie większy pod względem inkluzji.
częściowo uporządkowany spełniający założenia lematu Max August Zorn'a, czyli
taki, że każdy łańcuch jest w nim ograniczony od góry. Na mocy
zasady maksimum Felix Hausdorff'a istnieje w tym zbiorze łańcuch
maksymalny pod względem inkluzji. Łańcuch ten posiada ograniczenie
górne, które musi być elementem  łańcucha i równocześnie elementem
maksymalnym zbioru. Jeśliby tak nie było, to dodając element
istotnie większy od tego ograniczenia do łańcucha danego przez
zasadę maksimum Hausdorff'a uzyskalibyśmy łańcuch istotnie większy
pod względem inkluzji
}}
}}


Kolejne ćwiczenie mówi o istnieniu maksymalnego
Kolejne ćwiczenie mówi o istnieniu maksymalnego antyłańcucha.
antyłańcucha.
 
{cwicz}{1}{Ćwiczenie {section}.{cwicz}} 
{{cwiczenie|3.3||
Udowodnij, używając lematu Max August Zorn'a, że w każdym zbiorze częściowo
Udowodnij, używając lematu Maxa Augusta Zorna, że w każdym zbiorze częściowo uporządkowanym istnieje antyłańcuch maksymalny pod względem inkluzji.  
uporządkowanym istnieje antyłańcuch maksymalny pod względem
}}
inkluzji. {hint}{0}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
; Solution.
Ustalmy dowolny niepusty (twierdzenie jest trywialne dla zbiorów pustych) zbiór częściowo uporządkowany <math>(A,\sqsubseteq)</math>. Zdefiniujmy zbiór
: Ustalmy dowolny niepusty&nbsp;(twierdzenie jest
trywialne dla zbiorów pustych) zbiór częściowo uporządkowany
<math>(A,\sqsubseteq)</math>. Zdefiniujmy zbiór


<center><math>B = \{C\subset A\,:\, \text{</math>C<math> jest antyłańcuchem w </math>A<math>}\}
<center><math>B = \{C\subset A\ :\ C\text{ jest antyłańcuchem w }A\}
</math></center>
</math></center>


i uporządkujmy go relacją inkluzji. Aby móc zastosować do
i uporządkujmy go relacją inkluzji. Aby móc zastosować do <math>(B,\subset)</math> lemat [[Biografia Zorn|Maxa Augusta Zorna]], wykażemy, że każdy łańcuch ma majorantę. Ustalmy w tym celu dowolny łańcuch <math>B'</math> w <math>(B,\subset)</math>. Najprostszym kandydatem na majorantę <math>B'</math> względem inkluzji jest <math>\bigcup B'</math> - wykażemy, że <math>\bigcup B'</math> jest antyłańcuchem w <math>(A,\sqsubseteq)</math>. Niewątpliwie <math>\bigcup B'\subset A</math>. Ustalmy dwa dowolne elementy <math>x</math> i <math>y</math> w <math>\bigcup B'</math>, wtedy istnieje <math>C_x\in B'</math> i <math>C_y \in B'</math> takie, że <math>x\in C_x</math> i <math>y\in C_y</math>. Ponieważ <math>B'</math> jest łańcuchem w sensie inkluzji, to <math>C_x</math> i <math>C_y</math> są porównywalne i możemy, bez straty ogólności założyć, że <math>C_x\subset C_y</math> i w związku z tym <math>x\in C_y</math>. Ponieważ <math>C_y\in B'\subset B</math>, to <math>C_y</math> jest antyłańcuchem, czyli elementy <math>x</math> i <math>y</math> są nieporównywalne w <math>A,\sqsubseteq)</math>. Wykazaliśmy, że dowolne dwa elementy <math>\bigcup B'</math> są nieporównywalne, czyli, że <math>\bigcup B'</math> jest antyłańcuchem i należy do <math>B</math>. Wnioskujemy, że każdy łańcuch w  <math>(B,\subset)</math> ma majorantę.
<math>(B,\subset)</math> lemat Max August Zorn'a wykażemy, że każdy łańcuch ma
 
majorantę. Ustalmy w tym celu dowolny łańcuch <math>B'</math> w
Na podstawie lematu [[Biografia Zorn|Maxa Augusta Zorna]] wnioskujemy, że <math>(B,\subset)</math> posiada element maksymalny - jest to, poszukiwany przez nas, maksymalny w sensie inkluzji antyłańcuch.
<math>(B,\subset)</math>. Najprostszym kandydatem na majorantę <math>B'</math>
</div></div>
względem inkluzji jest <math>\bigcup B'</math> -- wykażemy, że <math>\bigcup B'</math>
jest antyłańcuchem w <math>(A,\sqsubseteq)</math>. Niewątpliwie <math>\bigcup
B'\subset A</math>. Ustalmy dwa dowolne elementy <math>x</math> i <math>y</math> w <math>\bigcup
B'</math>, wtedy istnieje <math>C_x\in B'</math> i <math>C_y \in B'</math> takie, że <math>x\in C_x</math>
i <math>y\in C_y</math>. Ponieważ <math>B'</math> jest łańcuchem w sensie inkluzji, to
<math>C_x</math> i <math>C_y</math> są porównywalne i możemy, bez straty ogólności
założyć, że <math>C_x\subset C_y</math> i w związku z tym <math>x\in C_y</math>.
Ponieważ <math>C_y\in B'\subset B</math> to <math>C_y</math> jest antyłańcuchem, czyli
elementy <math>x</math> i <math>y</math> są nieporównywalne w <math>(A,\sqsubseteq)</math>.
Wykazaliśmy, że dowolne dwa elementy <math>\bigcup B'</math> są
nieporównywalne, czyli, że <math>\bigcup B'</math> jest antyłańcuchem i należy
do <math>B</math>. Wnioskujemy, że każdy łańcuch w  <math>(B,\subset)</math> ma
majorantę.


Na podstawie lematu Max August Zorn'a wnioskujemy, że <math>(B,\subset)</math>
posiada element maksymalny -- jest to, poszukiwany przez nas,
maksymalny w sensie inkluzji antyłańcuch.
{Koniec ćwiczenia {section}.{cwicz}} 
Poniższe ćwiczenie dotyczy rozszerzeń porządków.
Poniższe ćwiczenie dotyczy rozszerzeń porządków.
{cwicz}{1}{Ćwiczenie {section}.{cwicz}} 
Wykaż, używając lematu Max August Zorn'a, że każdy częściowy porządek da się
rozszerzyć do porządku liniowego. To znaczy, że dla każdego zbioru
częściowo uporządkowanego <math>(A,\sqsubseteq)</math> istnieje liniowy porządek
<math>\preccurlyeq</math> na <math>A</math> taki, że


<center><math>x \sqsubseteq y \implies x\preccurlyeq y.
{{cwiczenie|3.4||
</math></center>
 
Wykaż, używając lematu Maxa Augusta Zorna, że każdy częściowy porządek da się rozszerzyć do porządku liniowego. To znaczy, że dla każdego zbioru częściowo uporządkowanego <math>(A,\sqsubseteq)</math> istnieje liniowy porządek <math>\preccurlyeq</math> na <math>A</math> taki, że
 
<center><math>x \sqsubseteq y \implies x\preccurlyeq y</math></center>


dla dowolnych <math>x</math> i <math>y</math> w <math>A</math>. {hint}{0}
dla dowolnych <math>x</math> i <math>y</math> w <math>A</math>.  
; Solution.
}}
: Ustalmy dowolny porządek
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
częściowy <math>(A,\sqsubseteq)</math> na niepustym zbiorze <math>A</math>&nbsp;(porządek pusty
Ustalmy dowolny porządek częściowy <math>(A,\sqsubseteq)</math> na niepustym zbiorze <math>A</math>&nbsp;(porządek pusty na zbiorze pustym jest liniowy). Niech zbiór <math>B</math> będzie zbiorem porządków rozszerzających <math>\sqsubseteq</math> na <math>A</math>
na zbiorze pustym jest liniowy). Niech zbiór <math>B</math> będzie zbiorem
porządków rozszerzających <math>\sqsubseteq</math> na <math>A</math>


<center><math>B = \{r\subset A\times A\,:\, \text{ </math>r<math> jest porządkiem
<center><math>B = \{r\subset A\times A\ : r</math> jest porządkiem częściowym na <math>A</math> rozszerzającym <math>\sqsubseteq\}</math></center>
częściowym na </math>A<math> rozszerzającym }\}.
</math></center>


uporządkowanym przez inkluzję. Formalnie, każdy element zbioru <math>B</math>
uporządkowanym przez inkluzję. Formalnie, każdy element zbioru <math>B</math> jest nadzbiorem relacji <math>\sqsubseteq</math>.
jest nadzbiorem relacji <math>\sqsubseteq</math>.


Wykażemy teraz, że w zbiorze <math>B</math>, uporządkowanym przez inkluzję,
Wykażemy teraz, że w zbiorze <math>B</math>, uporządkowanym przez inkluzję, każdy łańcuch ma majorantę. Niech <math>D</math> będzie niepustym łańcuchem, wtedy, standardowo, kandydatem na majorantę łańcucha <math>D</math> jest zbiór <math>\bigcup D</math>. Relacja <math>\bigcup D</math> jest niewątpliwie nadzbiorem <math>\sqsubseteq</math>, bo istnieje element <math>D</math> który jest takim nadzbiorem. Relacja ta jest przechodnia, bo jeśli <math>(a,b)\in\bigcup D</math> i <math>(b,c)\in\bigcup D</math>, to <math>(a,b)\in C \in D</math> i <math>(b,c)\in C'\in D</math> dla pewnych <math>C</math> i <math>C'</math>. Ponieważ <math>D</math> było łańcuchem, bez straty ogólności możemy założyć, że <math>C\subset C'</math> i w związku z tym obie pary są elementami <math>C'</math> i przechodniość <math>C'</math> gwarantuje, że <math>(a,c)\in C'\subset \bigcup D</math>. Antysymetrii dowodzimy w identyczny sposób, co pozwala nam stwierdzić, że <math>\bigcup D\in B</math>  i, że każdy łańcuch w <math>B</math> ma majorantę.
każdy łańcuch ma majorantę. Niech <math>D</math> będzie niepustym łańcuchem,
wtedy, standardowo, kandydatem na majorantę łańcucha <math>D</math> jest zbiór
<math>\bigcup D</math>. Relacja <math>\bigcup D</math> jest niewątpliwie nadzbiorem <math>\sqsubseteq</math>,
bo istnieje element <math>D</math> który jest takim nadzbiorem. Relacja ta jest
przechodnia, bo jeśli <math>(a,b)\in\bigcup D</math> i <math>(b,c)\in\bigcup D</math>, to
<math>(a,b)\in C \in D</math> i <math>(b,c)\in C'\in D</math> dla pewnych <math>C</math> i <math>C'</math>.
Ponieważ <math>D</math> było łańcuchem, bez straty ogólności możemy założyć, że
<math>C\subset C'</math> i w związku z tym obie pary są elementami <math>C'</math> i
przechodniość <math>C'</math> gwarantuje, że <math>(a,c)\in C'\subset \bigcup D</math>.
Antysymetrii dowodzimy w identyczny sposób, co pozwala nam
stwierdzić, że <math>\bigcup D\in B</math>  i, że każdy łańcuch w <math>B</math> ma
majorantę.


Niech relacja  <math>\,\rho\,</math> będzie, gwarantowanym przez lemat Max August Zorn'a,
Niech relacja  <math>\,\rho\ </math>, będzie, gwarantowanym przez lemat Maxa Augusta Zorna, elementem maksymalnym w <math>(B,\subset)</math>. Jeśli <math>\,\rho\ </math>, jest porządkiem liniowym, to jest to poszukiwane rozszerzenie liniowe <math>\sqsubseteq</math> i dowód jest zakończony. Pokażemy, że przypadek kiedy <math>\,\rho\ </math>, nie jest porządkiem liniowym prowadzi do sprzeczności. Załóżmy, że <math>\,\rho\ </math>, nie jest porządkiem liniowym, czyli, że istnieją dwa elementy <math>a</math> i <math>b</math> nieporównywalne w <math>\,\rho\ </math>,. Zdefiniujmy
elementem maksymalnym w <math>(B,\subset)</math>. Jeśli <math>\,\rho\,</math> jest
porządkiem liniowym, to jest to poszukiwane rozszerzenie liniowe
<math>\sqsubseteq</math> i dowód jest zakończony. Pokażemy, że przypadek kiedy <math>\,\rho\,</math>
nie jest porządkiem liniowym prowadzi do sprzeczności. Załóżmy, że
<math>\,\rho\,</math> nie jest porządkiem liniowym, czyli, że istnieją dwa elementy
<math>a</math> i <math>b</math> nieporównywalne w <math>\,\rho\,</math>. Zdefiniujmy


<center><math>\uparrow a= \{c\in A\,:\, a\,\rho\, c\}
<center><math>\uparrow a= \{c\in A\,:\, a\,\rho\, c\}
Linia 440: Linia 260:
oraz
oraz


<center><math>\downarrow b= \{c\in A\,:\, c\,\rho\, b\}.
<center><math>\downarrow b= \{c\in A\,:\, c\,\rho\, b\}</math></center>
</math></center>


Zauważmy że przecięcie zbiorów <math>\uparrow a</math> i <math>\downarrow b</math> jest
Zauważmy że przecięcie zbiorów <math>\uparrow a</math> i <math>\downarrow b</math> jest puste (w przeciwnym przypadku otrzymalibyśmy z przechodniości <math>a\,\rho\, b</math>), co więcej żaden element <math>\downarrow b</math> nie może być nad (w <math>\,\rho\ </math>,) żadnym elementem <math>\uparrow a</math> (z tego samego powodu).
puste&nbsp;(w przeciwnym przypadku otrzymalibyśmy z przechodniości <math>a\,\rho\,
b</math>), co więcej żaden element <math>\downarrow b</math> nie może być nad&nbsp;(w
<math>\,\rho\,</math>) żadnym elementem <math>\uparrow a</math>&nbsp;(z tego samego powodu).
Zdefiniujmy nową relację
Zdefiniujmy nową relację


<center><math>x\,\rho'\, y \iff x\,\rho\, y \lor (x\in \downarrow b \land y\in\uparrow a).
<center><math>x\,\rho'\, y \iff x\,\rho\, y \lor (x\in \downarrow b \land y\in\uparrow a)</math></center>
</math></center>
 
Relacja <math>\,\rho'\ </math>, jest oczywiście zwrotna (ponieważ zawiera <math>\,\rho\ </math>,). Aby dowieść antysymetrii załóżmy, że <math>x\,\rho'\, y</math> i <math>y\,\rho'\, x</math>. Jeśli w obu przypadkach pierwsza część alternatywy jest prawdą, to, na mocy antysymetrii <math>\,\rho\ </math>, mamy <math>x=y</math>. W obu przypadkach prawdą nie może być druga część alternatywy, bo wtedy <math>x\in\uparrow a \cap \downarrow b</math> co wykluczyliśmy. Pozostaje możliwość, że <math>x\,\rho\, y</math> i <math>y\in\downarrow b \land x\in\uparrow a</math> - którą jednak też
wykluczyliśmy wcześniej. W dowodzie przechodniości, zakładając <math>x\,\rho'\, y</math> i <math>y\,\rho'\, z</math>, wszystkie przypadki trywializują się podobnie jak w antysymetrii, za wyjątkiem przypadku kiedy <math>x\,\rho\, y</math> i <math>y\in\downarrow b \land z\in\uparrow a</math>&nbsp;(i przypadku dualnego, kiedy <math>x\in\downarrow b \land y\in\uparrow a</math> i <math>y\,\rho\, z</math>). Ale wtedy z przechodniości <math>\,\rho\ </math>, wnioskujemy, że <math>x\in\downarrow b</math>&nbsp;(lub, że <math>z\in\uparrow a</math>) i że <math>x\,\rho'\, z</math>. Pokazaliśmy, że <math>\,\rho'\ </math>, jest częściowym porządkiem na <math>A</math>. Niewątpliwie <math>\,\rho'\ </math>, rozszerza <math>\sqsubseteq</math>&nbsp;(ponieważ jest nadzbiorem <math>\rho</math> rozszerzającej <math>\sqsubseteq</math>). Równocześnie <math>b\,\rho'\, a</math> dla elementów, które były nieporównywalne w <math>\,\rho\ </math>,. Sprzeczność z maksymalnością <math>\,\rho\ </math>, pozwala zakończyć dowód niewprost.
</div></div>
 


Relacja <math>\,\rho'\,</math> jest oczywiście zwrotna&nbsp;(ponieważ zawiera <math>\,\rho\,</math>).
W Wykładzie 5 (patrz [[Logika i teoria mnogości/Wykład 5: Para uporządkowana, iloczyn kartezjański, relacje, domykanie relacji, relacja równoważności, rozkłady zbiorów|Wykład 5]]) pokazaliśmy, że dla dowolnej relacji istnieje najmniejsza relacja równoważności zawierająca tą relację. W poniższym ćwiczeniu pokażemy, że dla niektórych relacji istnieje maksymalna, pod względem inkluzji, relacja równoważności zawarta w
Aby dowieść antysymetrii załóżmy, że <math>x\,\rho'\, y</math> i <math>y\,\rho'\, x</math>. Jeśli
w obu przypadkach pierwsza część alternatywy jest prawdą, to, na
mocy antysymetrii <math>\,\rho\,</math> mamy <math>x=y</math>. W obu przypadkach prawdą nie
może być druga część alternatywy, bo wtedy <math>x\in\uparrow a \cap
\downarrow b</math> co wykluczyliśmy. Pozostaje możliwość, że <math>x\,\rho\, y</math> i
<math>y\in\downarrow b \land x\in\uparrow a</math> -- którą jednak też
wykluczyliśmy wcześniej. W dowodzie przechodniości, zakładając
<math>x\,\rho'\, y</math> i <math>y\,\rho'\, z</math>, wszystkie przypadki trywializują się
podobnie jak w antysymetrii, za wyjątkiem przypadku kiedy <math>x\,\rho\, y</math>
i <math>y\in\downarrow b \land z\in\uparrow a</math>&nbsp;(i przypadku dualnego, kiedy
<math>x\in\downarrow b \land y\in\uparrow a</math> i <math>y\,\rho\, z</math>). Ale wtedy z
przechodniości <math>\,\rho\,</math> wnioskujemy, że <math>x\in\downarrow b</math>&nbsp;(lub, że
<math>z\in\uparrow a</math>) i że <math>x\,\rho'\, z</math>. Pokazaliśmy, że <math>\,\rho'\,</math> jest
częściowym porządkiem na <math>A</math>. Niewątpliwie <math>\,\rho'\,</math> rozszerza
<math>\sqsubseteq</math>&nbsp;(ponieważ jest nadzbiorem <math>\rho</math> rozszerzającej <math>\sqsubseteq</math>).
Równocześnie <math>b\,\rho'\, a</math> dla elementów, które były nieporównywalne w
<math>\,\rho\,</math>. Sprzeczność z maksymalnością <math>\,\rho\,</math> pozwala zakończyć dowód
niewprost.
{Koniec ćwiczenia {section}.{cwicz}} 
W Wykład 5 pokazaliśmy, że dla dowolnej relacji
istnieje najmniejsza relacja równoważności zawierająca tą relację. W
poniższym ćwiczeniu pokażemy, że dla niektórych relacji istnieje
maksymalna, pod względem inkluzji, relacja równoważności zawarta w
nich
nich
{cwicz}{1}{Ćwiczenie {section}.{cwicz}} 
Użyj lematu Max August Zorn'a, aby wykazać, że dla każdej relacji <math>\rho
\subset A\times A</math>, jeśli <math>1_{A}\subset\rho</math> to istnieje,
maksymalna pod względem inkluzji relacja równoważności zawarta w
<math>\rho</math>. {hint}{0} 
; Solution.
: Ustalmy niepusty zbiór <math>A</math>&nbsp;(twierdzenie jest
trywialne dla zbioru pustego). Podobnie jak w poprzednich
przypadkach lemat Max August Zorn'a stosować będziemy do zbioru
uporządkowanego przez inkluzję. Zbiorem tym jest


<center><math>B = \{\,\delta\,\subset A\times A\,:\, \,\delta\,\subset\,\rho\, \land
{{cwiczenie|3.5||
\textrm{ jest relacją równoważności na </math>A<math>}\}.
 
</math></center>
Użyj lematu Maxa Augusta Zorna, aby wykazać, że dla każdej relacji <math>\rho \subset A\times A</math>, jeśli <math>1_{A}\subset\rho</math>, to istnieje maksymalna pod względem inkluzji relacja równoważności zawarta w <math>\rho</math>.
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
Ustalmy niepusty zbiór <math>A</math> (twierdzenie jest trywialne dla zbioru pustego). Podobnie jak w poprzednich przypadkach lemat [[Biografia Zorn|Maxa Augusta Zorn'a]] stosować będziemy do zbioru uporządkowanego przez inkluzję. Zbiorem tym jest
 
<center><math>B = \{\delta\ \subset A\times A\ : \delta\ \subset\ \rho\ \land \delta \text{ jest relacją równoważności na }A\}</math></center>


Zbiór <math>B</math> niewątpliwie nie jest pusty, ponieważ <math>1_{A}\in B</math>. Jeśli
Zbiór <math>B</math> niewątpliwie nie jest pusty, ponieważ <math>1_{A}\in B</math>. Jeśli
zbiór <math>B</math> uporządkowany przez inkluzję spełnia założenia lematu
zbiór <math>B</math> uporządkowany przez inkluzję spełnia założenia lematu
Max August Zorn'a, to jego element maksymalny jest niewątpliwe maksymalną w
Maxa Augusta Zorn'a, to jego element maksymalny jest niewątpliwe maksymalną w
sensie inkluzji relacją równoważności zawartą w <math>\,\rho\,</math>. Pozostaje
sensie inkluzji relacją równoważności zawartą w <math>\,\rho\ </math>,. Pozostaje
wykazać, że każdy łańcuch w <math>(B,\subset)</math> posiada
wykazać, że każdy łańcuch w <math>(B,\subset)</math> posiada
ograniczenie górne.
ograniczenie górne.


Ustalmy dowolny niepusty łańcuch <math>D\subset B</math>. Musimy wykazać, że
Ustalmy dowolny niepusty łańcuch <math>D\subset B</math>. Musimy wykazać, że <math>\bigcup D</math> jest relacją równoważności i, że <math>\bigcup D\subset \,\rho\ </math>,. Ponieważ każdy element <math>D</math> jest elementem <math>B</math> i w związku z tym podzbiorem <math>\,\rho\ </math>,, to również ich unia jest podzbiorem <math>\,\rho\ </math>,. Wykażemy teraz, że <math>\bigcup D</math> jest relacją równoważności. Relacja ta jest niewątpliwie zwrotna, ponieważ istnieje element <math>D</math> i jest on zwrotny. Jest przechodnia, bo dla <math>(a,b)\in\bigcup D</math> i <math>(b,c)\in\bigcup D</math> mamy <math>(a,b)\in C\in D</math> i <math>(b,c)\in C'\in D</math> dla pewnych <math>C,C'</math>. Zbiory <math>C</math> i <math>C'</math> są porównywalne w sensie inkluzji więc, bez straty ogólności zakładamy, że <math>C\subset C'</math> i w związku z tym obie pary należą do <math>C'</math>. Ponieważ relacja <math>C'</math>, jako element <math>B</math>, jest przechodnia, to <math>(a,c)\in C'\subset \bigcup D</math> co dowodzi przechodniości. Dla dowodu symetrii ustalmy dowolne <math>(a,b)\in\bigcup D</math> wtedy dla pewnego <math>C\in D</math> mamy <math>(a,b)\in C</math> i, ponieważ <math>C</math> jest symetryczna, <math>(b,a)\in C\subset \bigcup D</math> czego należało dowieść. Wykazaliśmy że w zbiorze częściowo uporządkowanym <math>(B,\subset)</math> każdy łańcuch ma majorantę, więc istniejący, na podstawie lematu Maxa Augusta Zorna, element maksymalny jest poszukiwaną przez nas relacją równoważności.
<math>\bigcup D</math> jest relacją równoważności i, że <math>\bigcup D\subset
</div></div>
\,\rho\,</math>. Ponieważ każdy element <math>D</math> jest elementem <math>B</math> i w związku z
tym podzbiorem <math>\,\rho\,</math>, to również ich unia jest podzbiorem <math>\,\rho\,</math>.
Wykażemy teraz, że <math>\bigcup D</math> jest relacją równoważności. Relacja
ta jest niewątpliwie zwrotna, ponieważ istnieje element <math>D</math> i jest
on zwrotny. Jest przechodnia, bo dla <math>(a,b)\in\bigcup D</math> i
<math>(b,c)\in\bigcup D</math> mamy <math>(a,b)\in C\in D</math> i <math>(b,c)\in C'\in D</math> dla
pewnych <math>C,C'</math>. Zbiory <math>C</math> i <math>C'</math> są porównywalne w sensie inkluzji
więc, bez straty ogólności zakładamy, że <math>C\subset C'</math> i w związku
z tym obie pary należą do <math>C'</math>. Ponieważ relacja <math>C'</math>, jako element
<math>B</math>, jest przechodnia, to <math>(a,c)\in C'\subset \bigcup D</math> co
dowodzi przechodniości. Dla dowodu symetrii ustalmy dowolne
<math>(a,b)\in\bigcup D</math> wtedy dla pewnego <math>C\in D</math> mamy <math>(a,b)\in C</math> i,
ponieważ <math>C</math> jest symetryczna, <math>(b,a)\in C\subset \bigcup D</math> czego
należało dowieść. Wykazaliśmy że w zbiorze częściowo uporządkowanym
<math>(B,\subset)</math> każdy łańcuch ma majorantę, więc istniejący,
na podstawie lematu Max August Zorn'a, element maksymalny jest poszukiwaną
przez nas relacją równoważności.
{Koniec ćwiczenia {section}.{cwicz}} 
Kolejny warunek równoważny dotyczy zbiorów dobrze
uporządkowanych.
===Twierdzenie Ernst Zermelo===


Kolejny warunek równoważny dotyczy zbiorów dobrze uporządkowanych.
===Twierdzenie Ernsta Zermelo===
[[grafika:Zermelo.JPG|thumb|right||Ernst Friedrich Ferdinand Zermelo (1871-1953)<br>[[Biografia Zermelo|Zobacz biografię]]]]
Twierdzenie Zermelo jest jedną z równoważnych postaci aksjomatu
Twierdzenie Zermelo jest jedną z równoważnych postaci aksjomatu
wyboru w którą wyjątkowo trudno uwierzyć.
wyboru, w którą wyjątkowo trudno uwierzyć.
 
<span id="twierdzenie_3_4">
{{twierdzenie|3.4. [Zermelo]||


{{twierdzenie|[Uzupelnij]||
[Zermello]
Dla każdego zbioru istnieje relacja, która jest dobrym porządkiem na
Dla każdego zbioru istnieje relacja, która jest dobrym porządkiem na
tym zbiorze.
tym zbiorze.
}}
}}
</span>
Kolejny dowód to


Kolejny dowód to
{{dowod|||


{{dowod|[Uzupelnij]||
Lemat Maxa Augusta Zorna implikuje Twierdzenie Ernsta Zermelo. Ustalmy dowolny zbiór niepusty <math>A</math> (dla zbioru pustego porządek pusty porządkuje go dobrze). Rozważmy zbiór <math>B</math> składający się z podzbiorów <math>A</math>, które mogą być dobrze uporządkowane, wraz z dobrymi porządkami
[Lemat Max August Zorn'a implikuje Twierdzenie Ernst Zermelo]
Ustalmy dowolny zbiór niepusty <math>A</math>&nbsp;(dla zbioru pustego porządek
pusty porządkuje go dobrze). Rozważmy zbiór <math>B</math> składający się z
podzbiorów <math>A</math> które mogą być dobrze uporządkowane, wraz z dobrymi
porządkami


<center><math>B = \{(C,\sqsubseteq)\,:\, C\subset A \land \text{ jest
<center><math>B = \{(C,\sqsubseteq)\,:\, C\subset A \land \sqsubseteq \text{ jest dobrym porządkiem na} C\}
dobrym porządkiem na C}\}.
</math></center>
</math></center>


i zdefiniujmy relację na elementach <math>B</math> w następujący sposób
i zdefiniujmy relację na elementach <math>B</math> w następujący sposób


<center><math>c\forall d\; c\in C \land d\in C \land c\sqsubseteq d\implies c\sqsubseteq' d,
<center>
(C,\sqsubseteq) \preccurlyeq (C',\sqsubseteq') \iff C\subset C' \land
<math>
\left\{
(C,\sqsubseteq) \preccurlyeq (C',\sqsubseteq')  
\beginaligned
\iff C\subset C' \land  
\forall c \forall d\; &(c\in C\land d\in C) \implies (c\sqsubseteq d \iff c\sqsubseteq' d) \textrm{ oraz }\\
\begin{cases}
\forall c \forall d\; &(c\in C\land d\in C'\setminus C) \implies c\sqsubseteq' d.
\forall c \forall d\ (c\in C\land d\in C) \implies (c\sqsubseteq d \iff c\sqsubseteq' d) & \text{ oraz }\\
\endaligned \right.
\forall c \forall d\ (c\in C\land d\in C'\setminus C) \implies c\sqsubseteq' d
</math></center>
\end{cases}
</math>
</center>


czyli dwa elementy <math>B</math> są porównywalne wtedy i tylko wtedy, jeśli
czyli dwa elementy <math>B</math> są porównywalne wtedy i tylko wtedy, jeśli zbiory, na których, są określone są porównywalne w sensie inkluzji i porządek zdefiniowany na większym zbiorze jest rozszerzeniem porządku zdefiniowanego na mniejszym przez dodanie elementów większych od wszystkich zastanych. Aby zastosować Lemat Maxa Augusta Zorna do zbioru częściowo uporządkowanego <math>(B,\preccurlyeq)</math> musimy wykazać, że każdy łańcuch w tym zbiorze ma ograniczenie górne.
zbiory na których są określone są porównywalne w sensie inkluzji i
porządek zdefiniowany na większym zbiorze jest rozszerzeniem
porządku zdefiniowanego na mniejszym przez dodanie elementów
większych od wszystkich zastanych. Aby zastosować Lemat Max August Zorn'a do
zbioru częściowo uporządkowanego <math>(B,\preccurlyeq)</math> musimy wykazać,
że każdy łańcuch w tym zbiorze ma ograniczenie górne.


Niech <math>D\subset B </math> będzie łańcuchem w sensie <math>\preccurlyeq</math>. Zdefiniujmy
Niech <math>D\subset B</math> będzie łańcuchem w sensie <math>\preccurlyeq</math>. Zdefiniujmy <math>C_0</math> jako unię wszystkich pierwszych współrzędnych elementów <math>D</math> i <math>\sqsubseteq_0</math> jako unię drugich współrzędnych elementów <math>D</math>. Niewątpliwie <math>C_0\subset A</math>. Ponieważ <math>D</math> jest łańcuchem w sensie <math>\preccurlyeq</math>, to
<math>C_0</math> jako unię wszystkich pierwszych współrzędnych elementów <math>D</math> i
relacja <math>\sqsubseteq_0</math> jest porządkiem liniowym na <math>C_0</math>. Aby wykazać, że <math>\sqsubseteq_0</math> jest dobrym porządkiem na <math>C_0</math>, ustalmy dowolny <math>E\subset
<math>\sqsubseteq_0</math> jako unię drugich współrzędnych elementów <math>D</math>. Niewątpliwie
C_0</math>. Niewątpliwie istnieje element <math>(C,\sqsubseteq)\in D</math> taki, że <math>E\cap C\neq\emptyset</math>. Ponieważ  <math>(C,\sqsubseteq)\in B</math>, to <math>C</math> jest dobrze uporządkowany przez <math>\sqsubseteq</math> i w związku z tym <math>E\cap C</math> posiada element najmniejszy w <math>C,\sqsubseteq)</math> - oznaczmy go przez <math>x</math>. Element <math>x</math> będzie również najmniejszym elementem <math>E</math> w <math>C_0</math>. Aby to wykazać, ustalmy <math>y\in E</math>. Jeśli <math>y\in C</math>, to niewątpliwie <math>x\sqsubseteq y</math>
<math>C_0\subset A</math>. Ponieważ <math>D</math> jest łańcuchem w sensie <math>\preccurlyeq</math> to
i w związku z tym <math>x\sqsubseteq_0 y</math>. Jeśli <math>y\notin C</math>, to <math>y \in C'\setminus C</math> dla jakiegoś <math>(C',\sqsubseteq')\in D</math>. Ponieważ <math>D</math> jest łańcuchem wnioskujemy, że <math>C\subset C'</math> i na mocy definicji <math>\preccurlyeq</math>, że <math>x\sqsubseteq' y</math>, czyli <math>x\sqsubseteq_0 y</math>, co należało wykazać.
relacja <math>\sqsubseteq_0</math> jest porządkiem liniowym na <math>C_0</math>. Aby wykazać, że
<math>\sqsubseteq_0</math> jest dobrym porządkiem na <math>C_0</math> ustalmy dowolny <math>E\subset
C_0</math>. Niewątpliwie istnieje element <math>(C,\sqsubseteq)\in D</math> taki, że
<math>E\cap C\neq\emptyset</math>. Ponieważ  <math>(C,\sqsubseteq)\in B</math> to <math>C</math> jest
dobrze uporządkowany przez <math>\sqsubseteq</math> i w związku z tym <math>E\cap C</math> posiada
element najmniejszy w <math>(C,\sqsubseteq)</math> -- oznaczmy go przez <math>x</math>.
Element <math>x</math>, będzie również najmniejszym elementem <math>E</math> w <math>C_0</math>. Aby
to wykazać ustalmy <math>y\in E</math>. Jeśli <math>y\in C</math> to niewątpliwie <math>x\sqsubseteq y</math>
i w związku z tym <math>x\sqsubseteq_0 y</math>. Jeśli <math>y\notin C</math> to <math>y \in
C'\setminus C</math> dla jakiegoś <math>(C',\sqsubseteq')\in D</math>. Ponieważ <math>D</math>
jest łańcuchem wnioskujemy, że <math>C\subset C'</math> i na mocy definicji
<math>\preccurlyeq</math>, że <math>x\sqsubseteq' y</math>, czyli <math>x\sqsubseteq_0 y</math> co należało wykazać.


Stosując Lemat Max August Zorn'a wnioskujemy, że w zbiorze częściowo
Stosując Lemat Maxa Augusta Zorna wnioskujemy, że w zbiorze częściowo
uporządkowanym <math>(B,\preccurlyeq)</math> istnieje element maksymalny
uporządkowanym <math>(B,\preccurlyeq)</math> istnieje element maksymalny <math>(D,\sqsubseteq)</math>. Jeśli <math>D = A</math>, to <math>\sqsubseteq</math> jest wymaganym dobrym porządkiem na <math>A</math>. Aby wykazać, że tak musi być, załóżmy niewprost, że <math>D\varsubsetneq A</math>, czyli że istnieje <math>d\in A\setminus D</math>. Wtedy zbiór <math>D\cup\{d\}</math> wraz z dobrym porządkiem <math>\sqsubseteq'</math> zdefiniowanym jako
<math>(D,\sqsubseteq)</math>. Jeśli <math>D = A</math> to <math>\sqsubseteq</math> jest wymaganym dobrym
porządkiem na <math>A</math>. Aby wykazać że tak musi być załóżmy niewprost, że
<math>D\varsubsetneq A</math>, czyli, że istnieje <math>d\in A\setminus D</math>. Wtedy
zbiór <math>D\cup\{d\}</math> wraz z dobrym porządkiem <math>\sqsubseteq'</math> zdefiniowanym
jako


<center><math>a\sqsubseteq' b \iff b=d \lor (a\in D\land b\in D \land a\sqsubseteq b)
<center><math>a\sqsubseteq' b \iff b=d \lor (a\in D\land b\in D \land a\sqsubseteq b)
</math></center>
</math></center>


jest większy w sensie relacji <math>\preccurlyeq</math> , co przeczy maksymalności <math>D</math>.
jest większy w sensie relacji <math>\preccurlyeq</math>, co przeczy maksymalności <math>D</math>. Uzyskana w dowodzie niewprost sprzeczność kończy rozumowanie.
Uzyskana w dowodzie niewprost sprzeczność kończy rozumowanie.
}}
}}


Twierdzenie Ernst Zermelo jest sprzeczne z intuicją wielu
Twierdzenie [[Biografia Zermelo|Ernsta Zermelo]] jest sprzeczne z intuicją wielu matematyków. Gwarantuje ono między innymi istnienie dobrego porządku na liczbach rzeczywistych, czyli  takiego liniowego uporządkowania liczb rzeczywistych, w którym każdy zbiór posiada element najmniejszy. Porządek taki jest trudnym do wyobrażenia konceptem matematycznym.
matematyków. Gwarantuje ono między innymi istnienie dobrego porządku
na liczbach rzeczywistych -- takiego, liniowego, uporządkowania
liczb rzeczywistych w którym każdy zbiór posiada element
najmniejszy. Porządek taki jest trudnym do wyobrażenia konceptem
matematycznym.


Aby zamknąć ciąg rozumowań wystarczy wykazać, że Twierdzenie
Aby zamknąć ciąg rozumowań, wystarczy wykazać, że Twierdzenie Zermelo implikuje aksjomat wyboru.
Zermello implikuje aksjomat wyboru.


{{dowod|[Uzupelnij]||
{{dowod|||
[Twierdzenie Zermello implikuje akjomat wyboru]
Twierdzenie Zermelo implikuje aksjomat wyboru. Niech <math>x</math> będzie dowolnym zbiorem spełniającym założenia aksjomatu wyboru, to znaczy takim, że <math>\emptyset\notin x</math> i że wszystkie elementy <math>x</math> są parami rozłączne. Niech <math>\sqsubseteq</math> będzie istniejącym, na podstawie Twierdzenia Zermelo, dobrym uporządkowaniem zbioru <math>\bigcup x</math>. Zbiór wybierający po jednym elemencie z każdego elementu <math>x</math> otrzymujemy, stosując zasadę wycinania do <math>\bigcup x</math>
Niech <math>x</math> będzie dowolnym zbiorem spełniającym założenia aksjomatu
wyboru, to znaczy takim, że <math>\emptyset\notin x</math> i że wszystkie
elementy <math>x</math> są parami rozłączne. Niech <math>\sqsubseteq</math> będzie istniejącym, na
podstawie Twierdzenia Zermello, dobrym uporządkowaniem zbioru
<math>\bigcup x</math>. Zbiór wybierający po jednym elemencie z każdego
elementu <math>x</math> otrzymujemy stosując zasadę wycinania do <math>\bigcup x</math>


<center><math>w = \{y\in\bigcup x\,:\, \exists z\; y\in z\in x \land \text{</math>y<math>
<center><math>w = \{y\in\bigcup x\,:\, \exists z\; y\in z\in x \land y</math> jest najmniejszym elementem <math>z</math> względem relacji <math>\sqsubseteq\}</math></center>
jest najmniejszym elementem </math>z<math> względem relacji }\}.
</math></center>


Zbiór <math>w</math> posiada po dokładnie jednym elemencie wspólnym z każdym
Zbiór <math>w</math> posiada po dokładnie jednym elemencie wspólnym z każdym zbiorem <math>z\in x</math> - jest to element najmniejszy w <math>z</math> względem dobrego uporządkowania <math>\bigcup x</math>.
zbiorem <math>z\in x</math> -- jest to element najmniejszy w <math>z</math> względem
dobrego uporządkowania <math>\bigcup x</math>.
}}
}}


Nasze rozumowanie wykazało, że wszystkie powyższe fakty są
Nasze rozumowanie wykazało, że wszystkie powyższe fakty są
równoważne na gruncie ZF. Jak wspomnieliśmy na początku aksjomat
równoważne na gruncie ZF. Jak wspomnieliśmy na początku, aksjomat
wyboru jest kontrowersyjnym aksjomatem. Niektóre z równoważnych mu
wyboru jest kontrowersyjnym aksjomatem. Niektóre z równoważnych mu
stwierdzeń są intuicyjnie oczywiste inne przeczą intuicji.
stwierdzeń są intuicyjnie oczywiste, inne przeczą intuicji.
Podsumujemy rozdział żartem autorstwa Jerrego Bona:
Podsumujemy rozdział żartem autorstwa Jerrego Bona:


The Axiom of Choice is obviously true; the Well Ordering Principle
The Axiom of Choice is obviously true; the Well Ordering Principle
is obviously false; and who can tell about Max August Zorn's
is obviously false; and who can tell about Max August Zorn's
Lemma?{Aksjomat wyboru jest oczywiście prawdziwy;
Lemma? (Aksjomat wyboru jest oczywiście prawdziwy;
twierdzenie Ernst Zermelo jest oczywiście fałszem; lemat Zorn'a kto
twierdzenie Ernsta Zermelo jest oczywiście fałszem; lemat Zorn'a kto
wie?}
wie?)


==Twierdzenia wymagające aksjomatu wyboru==
==Twierdzenia wymagające aksjomatu wyboru==
Linia 644: Linia 380:
nadaje się do udowodnienia, że jakiś fakt jest słabszy od aksjomatu
nadaje się do udowodnienia, że jakiś fakt jest słabszy od aksjomatu
wyboru. Możemy pokazać, że jeśli aksjomat wyboru jest prawdą, to
wyboru. Możemy pokazać, że jeśli aksjomat wyboru jest prawdą, to
dane twierdzenie jest  prawdziwe, ale nie możemy pokazać że jeśli
dane twierdzenie jest  prawdziwe, ale nie możemy pokazać, że jeśli
założymy dane twierdzenie, to aksjomat wyboru nie musi być prawdą.
założymy dane twierdzenie, to aksjomat wyboru nie musi być prawdą.
Nie jesteśmy w stanie zdecydować czy aksjomat wyboru jest niezbędny
Nie jesteśmy w stanie zdecydować, czy aksjomat wyboru jest niezbędny
do udowodnienia danego twierdzenia -- tego typu dowody wykraczają
do udowodnienia danego twierdzenia - tego typu dowody wykraczają
poza zakres tego kursu i nie będą prezentowane.
poza zakres tego kursu i nie będą prezentowane.


Pierwszy z faktów, które będziemy dowodzić brzmi następująco:
Pierwszy z faktów, które będziemy dowodzić brzmi następująco:
 
<span id="twierdzenie_4_1">
{{twierdzenie|[Uzupelnij]||
{{twierdzenie|4.1.||


Dla dowolnego zbioru nieskończonego istnieje iniekcja ze zbioru
Dla dowolnego zbioru nieskończonego istnieje iniekcja ze zbioru
liczb naturalnych w ten zbiór.
liczb naturalnych w ten zbiór.
}}
}}
</span>


{{dowod|[Uzupelnij]||
{{dowod|1||
[Co możemy dowieść bez aksjomatu wyboru]
Ustalmy dowolny zbiór nieskończony <math>A</math>. Na mocy definicji z
Wykład 9 wiemy, że nie istnieje bijekcja między <math>A</math> a żadną
liczbą naturalną. Pokażmy najpierw, że dla każdej liczby naturalnej
<math>n</math> istnieje iniekcja z <math>n</math> do <math>A</math>. Dowód przeprowadzamy przez
indukcję na <math>n</math>.


* Jeśli <math>n=0</math> to niewątpliwie istnieje iniekcja ze zbioru pustego
Co możemy dowieść bez aksjomatu wyboru. Ustalmy dowolny zbiór nieskończony <math>A</math>. Na mocy definicji z [[Logika i teoria mnogości/Wykład 9: Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy kontinuum|Wykładu 9]] wiemy, że nie istnieje bijekcja między <math>A</math> a żadną liczbą naturalną. Pokażmy najpierw, że dla każdej liczby naturalnej <math>n</math> istnieje iniekcja z <math>n</math> do <math>A</math>. Dowód przeprowadzamy przez indukcję na <math>n</math>.
w <math>A</math> -- jest to funkcja pusta.


* Załóżmy, że istnieje iniekcja <math>f:n\rightarrow A</math>. Ponieważ nie istnieje
* Jeśli <math>n=0</math>, to niewątpliwie istnieje iniekcja ze zbioru pustego w <math>A</math> - jest to funkcja pusta.
bijekcja pomiędzy <math>n</math> a <math>A</math> wnioskujemy, że <math>\vec{f}(n)\varsubsetneq A</math>,
czyli, że istnieje <math>a\in A\setminus \vec{f}(n)</math>. Zdefiniujmy  <math>f':n'\rightarrow A</math> jako


<center><math>f'(m)=\begincases
* Załóżmy, że istnieje iniekcja <math>f:n\rightarrow A</math>. Ponieważ nie istnieje bijekcja pomiędzy <math>n</math> a <math>A</math>, wnioskujemy, że <math>\vec{f}(n)\varsubsetneq A</math>, czyli że istnieje <math>a\in A\setminus \vec{f}(n)</math>. Zdefiniujmy  <math>f':n'\rightarrow A</math> jako
f(m)&\text{jeśli </math>m n<math>}\\
 
a&\text{jeśli </math>m<nowiki>=</nowiki>n<math>}.
<center><math>
\endcases
f'(m)=
</math></center>
\left\{
\begin{array}{ll}
f(m),& \quad \text{jeśli } m \in n,\\
a ,& \quad \text{jeśli } m=n. \end{array} \right.</math></center>


Funkcja <math>f'</math> jest iniekcją, co kończy dowód indukcyjny.
Funkcja <math>f'</math> jest iniekcją, co kończy dowód indukcyjny.


Wykazaliśmy jedynie, że dla każdej liczby naturalnej istnieje
Wykazaliśmy jedynie, że dla każdej liczby naturalnej istnieje iniekcja z niej w <math>A</math>. Nie udało nam się wykazać istnienia jednej funkcji dla całego zbioru <math>\mathbb{N}</math>.
iniekcja z niej w <math>A</math>. Nie udało nam się wykazać istnienia jednej
funkcji dla całego zbioru <math>\mathbb{N}</math>.
}}
}}


Drugi dowód.
{{dowod|2||


{{dowod|[Uzupelnij]||
Dowód przy użyciu aksjomatu wyboru. Aby udowodnić istnienie iniekcji z <math>\mathbb{N}</math> w <math>A</math>, skorzystamy z
[Dowód przy użyciu aksjomatu wyboru]
Twierdzenia&nbsp;[[#twierdzeni_3.1.|twierdzenie 3.1.]] równoważnego aksjomatowi wyboru. Zastosujmy je do zbioru <math>\mathcal{P}(A)\setminus \{\emptyset\}</math>, dostając funkcję <math>e:\mathcal{P}(A)\setminus \{\emptyset\}\rightarrow A</math> taką, że <math>e(B)\in
Aby udowodnić istnienie iniekcji z <math>\mathbb{N}</math> w <math>A</math> skorzystamy z
B</math> dla każdego <math>B</math>, jeśli tylko <math>\emptyset \neq B \subset A</math>. Aby udowodnić istnienie żądanej funkcji, zastosujemy twierdzenie o definiowaniu przez indukcję. Dzięki temu twierdzeniu dostaniemy funkcję <math>h: \mathbb{N}\times\{\emptyset\}\rightarrow \mathcal{P}(A)</math> taką, że
Twierdzenia&nbsp;[[##tw:choicefunction|Uzupelnic tw:choicefunction|]] równoważnego aksjomatowi wyboru.
Zastosujmy je do zbioru <math>\mathcal{P}(A)\setminus \{\emptyset\}</math> dostając
funkcję <math>e:\mathcal{P}(A)\setminus \{\emptyset\}\rightarrow A</math> taką, że <math>e(B)\in
B</math> dla każdego <math>B</math> jeśli tylko <math>\emptyset \neq B \subset A</math>. Aby
udowodnić istnienie żądanej funkcji zastosujemy twierdzenie o
definiowaniu przez indukcję. Dzięki temu twierdzeniu dostaniemy
funkcję <math>h: \mathbb{N}\times\{\emptyset\}\rightarrow \mathcal{P}(A)</math> taką, że


<center><math>h(0, \emptyset) = \{e(A)\}
<center><math>h(0, \emptyset) = \{e(A)\}
Linia 704: Linia 426:
oraz
oraz


<center><math>h(n',\emptyset) = h(n,\emptyset)\cup \{e(A\setminus h(n))\}.
<center><math>h(n',\emptyset) = h(n,\emptyset)\cup \{e(A\setminus h(n))\}</math></center>
</math></center>


Jest to funkcja, która każdej liczbie naturalnej przyporządkowuje
Jest to funkcja, która każdej liczbie naturalnej przyporządkowuje zbiór o jeden element większy niż przyporządkowany poprzedniej liczbie naturalnej. Aby otrzymać żądaną iniekcję wystarczy zdefiniować:
zbiór o jeden element większy niż przyporządkowany poprzedniej
liczbie naturalnej. Aby otrzymać żądaną iniekcję wystarczy
zdefiniować:


<center><math>f(n) = x \iff h(n',\emptyset)\setminus h(n,\emptyset) = \{x\}
<center><math>f(n) = x \iff h(n',\emptyset)\setminus h(n,\emptyset) = \{x\}</math></center>
</math></center>


Funkcja <math>f</math> jest dobrze zdefiniowana ponieważ dla każdego <math>n</math> zbiór
Funkcja <math>f</math> jest dobrze zdefiniowana, ponieważ dla każdego <math>n</math> zbiór <math>h(n',\emptyset)\setminus h(n',\emptyset)</math> jest jednoelementowy (co gwarantuje definicja funkcji <math>e</math>). A jest iniekcją, ponieważ <math>h(m,\emptyset)\subset  h(n,\emptyset)</math>, jeśli tylko <math>m\leq n</math>.
<math>h(n',\emptyset)\setminus h(n',\emptyset)</math> jest jednoelementowy&nbsp;(co
gwarantuje definicja funkcji <math>e</math>). A jest iniekcją, ponieważ
<math>h(m,\emptyset)\subset  h(n,\emptyset)</math> jeśli tylko <math>m\leq n</math>.
}}
}}


Kolejną konsekwencję podajemy w formie ćwiczenia.
Kolejną konsekwencję podajemy w formie ćwiczenia.
{cwicz}{1}{Ćwiczenie {section}.{cwicz}} 
 
Rozważmy przedział <math>[-1,3]</math> w zbiorze liczb rzeczywistych. Niech
{{cwiczenie|4.1||
funkcja <math>f:\mathcal{P}([-1,3])\rightarrow \mathbb{R}</math> będzie "miłą miarą zbiorów"
 
Rozważmy przedział <math>[-1,3]</math> w zbiorze liczb rzeczywistych. Niech funkcja <math>f:\mathcal{P}([-1,3])\rightarrow \mathbb{R}</math> będzie "miłą miarą zbiorów",
jeśli:
jeśli:


* dla każdego zbioru jego miara jest większa lub równa <math>0</math> i  <math>f([0,1])=1</math>.
* dla każdego zbioru jego miara jest większa lub równa <math>0</math> i  <math>f([0,1])=1</math>,


* jeśli zbiór <math>A</math> ma miarę <math>f(A)</math> to <math>f(\{x+r\,:\, x\in A\})=f(A)</math> dla
* jeśli zbiór <math>A</math> ma miarę <math>f(A)</math> to <math>f(\{x+r\,:\, x\in A\})=f(A)</math> dla dowolnego <math>r</math> - to znaczy, że przesunięcie zbioru o wektor nie zmienia jego miary,
dowolnego <math>r</math> -- to znaczy, że przesunięcie zbioru o wektor nie zmienia jego miary


* jeśli <math>A_0, A_1,\dotsc</math> są zbiorami parami rozłącznymi, to suma tych
* jeśli <math>A_0, A_1,\dotsc</math> są zbiorami parami rozłącznymi, to suma tych zbiorów ma miarę równą sumie miar
zbiorów ma miarę równą sumie miar


<center><math>f(\bigcup_i A_i) =\sum_i f(A_i)
<center><math>f(\bigcup_i A_i) =\sum_i f(A_i)</math>,</center>
</math></center>


to znaczy że sumowanie zbiorów rozłącznych zachowuje miarę.
to znaczy, że sumowanie zbiorów rozłącznych zachowuje miarę.


Wykaż, że nie istnieje miła miara zbiorów. {hint}{0}  {hint}{1}
Wykaż, że nie istnieje miła miara zbiorów.
; Hint .
}}
: Połóż dwie
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
liczby w relacji ze sobą jeśli ich różnica jest wymierna. {hint}{1}
Połóż dwie liczby w relacji ze sobą jeśli ich różnica jest wymierna.
; Hint .
</div></div>
: Wybierz po jednym reprezentancie z każdej klasy równoważności i
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
przesuń go o wektor.  
Wybierz po jednym reprezentancie z każdej klasy równoważności i przesuń go o wektor.
; Solution.
</div></div>
: Załóżmy, niewprost, że istnieje miła miara
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
<math>f</math>. Zdefiniujmy relację równoważności <math>\,\rho\,</math> na zbiorze <math>[0,1]</math> w
Załóżmy, niewprost, że istnieje miła miara <math>f</math>. Zdefiniujmy relację równoważności <math>\,\rho\ </math>, na zbiorze <math>[0,1]</math> w następujący sposób
następujący sposób


<center><math>x\,\rho\, y \iff x-y\in\mathbb{Q}
<center><math>x\,\rho\, y \iff x-y\in\mathbb{Q}</math></center>
</math></center>


Niewątpliwie relacja <math>\,\rho\,</math> jest relacją równoważności:
Niewątpliwie relacja <math>\,\rho\ </math>, jest relacją równoważności:


:* <math>x\,\rho\, x</math> ponieważ <math>x-x=0\in\mathbb{Q}</math>,
:* <math>x\,\rho\, x</math> ponieważ <math>x-x=0\in\mathbb{Q}</math>,


:* <math>x\,\rho\, y\implies y\,\rho\, x</math> ponieważ, jeśli <math>x-y\in\mathbb{Q}</math> to również <math>y-x = -(x-y)\in\mathbb{Q}</math>
:* <math>x\,\rho\, y\implies y\,\rho\, x</math> ponieważ, jeśli <math>x-y\in\mathbb{Q}</math> to również <math>y-x = -(x-y)\in\mathbb{Q}</math>,


:* <math>x\,\rho\, y \land y\,\rho\, z\implies x\,\rho\, z</math>  ponieważ jeśli <math>x-y\in \mathbb{Q}</math> i <math>y-z\in \mathbb{Q}</math>, to również <math>x-z = (x-y)+(y-z)\in\mathbb{Q}</math>.
:* <math>x\,\rho\, y \land y\,\rho\, z\implies x\,\rho\, z</math>  ponieważ jeśli <math>x-y\in \mathbb{Q}</math> i <math>y-z\in \mathbb{Q}</math>, to również <math>x-z = (x-y)+(y-z)\in\mathbb{Q}</math>.
Linia 765: Linia 475:
W związku z tym zbiór <math>[0,1]</math> podzielony jest na klasy równoważności
W związku z tym zbiór <math>[0,1]</math> podzielony jest na klasy równoważności
i, na mocy aksjomatu wyboru, możemy wybrać zbiór <math>C</math> posiadający po
i, na mocy aksjomatu wyboru, możemy wybrać zbiór <math>C</math> posiadający po
jednym elemencie z każdej klasy równoważności. Rozważmy ''przeliczalną'' rodzinę zbiorów <math>\{C_r\}</math> gdzie <math>r</math> jest liczbą
jednym elemencie z każdej klasy równoważności. Rozważmy ''przeliczalną'' rodzinę zbiorów <math>\{C_r\}</math>, gdzie <math>r</math> jest liczbą
wymierną z przedziału <math>[-1,1]</math>, a zbiór <math>C_r</math> jest translacją zbioru
wymierną z przedziału <math>[-1,1]</math>, a zbiór <math>C_r</math> jest translacją zbioru
<math>C</math> o liczbę <math>r</math>
<math>C</math> o liczbę <math>r</math>


<center><math>C_r=\{c+r\,:\, c\in C\}.
<center><math>C_r=\{c+r\,:\, c\in C\}</math></center>
</math></center>


Ponieważ każdy element zbioru <math>[0,1]</math> jest odległy o liczbę wymierną
Ponieważ każdy element zbioru <math>[0,1]</math> jest odległy o liczbę wymierną
Linia 777: Linia 486:
to
to


<center><math>[0,1] \subset \bigcup_r C_r \subset [-1,2]
<center><math>[0,1] \subset \bigcup_r C_r \subset [-1,2]</math>,</center>
</math></center>


czyli miara zbioru <math>\bigcup_r C_r</math> musi być pomiędzy <math>f([0,1])=1</math>, a
czyli miara zbioru <math>\bigcup_r C_r</math> musi być pomiędzy <math>f([0,1])=1</math>, a
Linia 784: Linia 492:
f(C_r)</math> dla  każdego <math>r</math>. Oraz
f(C_r)</math> dla  każdego <math>r</math>. Oraz


<center><math>f(\bigcup_r C_r) = \sum_r f(C_r) = \sum_r f(C)
<center><math>f(\bigcup_r C_r) = \sum_r f(C_r) = \sum_r f(C)</math>,</center>
</math></center>
 
skąd wnioskujemy, że <math>f(\bigcup_r C_r)</math> musi być równe zero (w przeciwnym przypadku suma po prawej stronie równości byłaby
nieskończona) i w związku z tym również <math>\sum_r f(C_r) = 0</math>, czyli zbiór <math>C</math> ma miarę <math>0</math>, co jest żądaną sprzecznością. Skonstruowany przez nas zbiór <math>C</math> nazywa się, od nazwiska pomysłodawcy, zbiorem Vitaliego.
</div></div>


skąd wnioskujemy, że <math>f(\bigcup_r C_r)</math> musi być równe zero&nbsp;(w
przeciwnym przypadku suma po prawej stronie równości byłaby
nieskończona) i w związku z tym również <math>\sum_r f(C_r) = 0</math>, czyli
zbiór <math>C</math> ma miarę <math>0</math> co jest żądaną sprzecznością. Skonstruowany
przez nas zbiór <math>C</math> nazywa się, od nazwiska pomysłodawcy, zbiorem
Vitaliego.
{Koniec ćwiczenia {section}.{cwicz}} 
==Podsumowanie==
==Podsumowanie==


W powyższym wykładzie przedstawiliśmy twierdzenia równoważne
W powyższym wykładzie przedstawiliśmy twierdzenia równoważne
aksjomatowi wyboru i udowodniliśmy parę jego konsekwencji. Aksjomat
aksjomatowi wyboru i udowodniliśmy kilka jego konsekwencji. Aksjomat
wyboru jest kontrowersyjnym aksjomatem. Przyjęcie go pociąga za sobą
wyboru jest kontrowersyjnym aksjomatem. Przyjęcie go, pociąga za sobą
nieintuicyjne konsekwencje. Zakładając aksjomat wyboru możemy
nieintuicyjne konsekwencje. Zakładając aksjomat wyboru, możemy
wykazać, że zbiór liczb rzeczywistych daje się uporządkować w taki
wykazać, że zbiór liczb rzeczywistych daje się uporządkować w taki
sposób, że każdy jego podzbiór ma element najmniejszy. Kolejną
sposób, że każdy jego podzbiór ma element najmniejszy. Kolejną
nieintuicyjną konsekwencją jest wykazany przez Stefan Banach 'a i Alfred Tarski'
nieintuicyjną konsekwencją jest wykazany przez [[Biografia_Banach|Stefana Banacha]] i [[Biografia_Tarski|Alfreda Tarskiego]] paradoksalny rozkład trójwymiarowej kuli na sześć części, z których, za pomocą obrotów i translacji, możemy skleić dwie kule identyczne z pierwszą.
ego paradoksalny rozkład trójwymiarowej kuli na sześć części, z
których, za pomocą obrotów i translacji, możemy skleić dwie kule
identyczne z pierwszą.


Z drugiej strony wiele intuicyjnych faktów wymaga aksjomatu wyboru,
[[grafika:Russell.jpeg|thumb|right||Bertrand Arthur William Russell (1872-1970)<br>[[Biografia Russell|Zobacz biografię]]]]
lub jednej z jego słabszych wersji. Twierdzenie, że jeśli zbiór jest
Z drugiej strony, wiele intuicyjnych faktów wymaga aksjomatu wyboru lub jednej z jego słabszych wersji. Twierdzenie, że jeśli zbiór jest nieskończony, to istnieje iniekcja liczb naturalnych w ten zbiór, jest intuicyjnym faktem. [[Biografia_Russell|Bertrand Russell]] powiedział o aksjomacie wyboru:
nieskończony, to istnieje iniekcja liczb naturalnych w ten zbiór
jest intuicyjnym faktem. Bertrandt Russell powiedział o aksjomacie wyboru


The Axiom of Choice is necessary to select a set from an infinite
The Axiom of Choice is necessary to select a set from an infinite
number of socks, but not an infinite number of
number of socks, but not an infinite number of shoes (Aksjomat wyboru jest niezbędny, aby wybrać zbiór z nieskończonej ilości skarpet, ale nie z nieskończonej ilości butów).
shoes{Aksjomat wyboru jest niezbędny aby wybrać zbiór z
nieskończonej ilości skarpet ale nie z nieskończonej ilości butów}


Znaczenie tego cytatu powinno być jasne. Jesteśmy w stanie wybrać po
Znaczenie tego cytatu powinno być jasne. Jesteśmy w stanie wybrać po

Aktualna wersja na dzień 11:29, 12 wrz 2023

Wstęp

Poniższy wykład poświęcony jest konsekwencjom aksjomatu wyboru. Aksjomat wyboru jest niewątpliwie najbardziej kontrowersyjnym z aksjomatów ZFC. Wielu znanych matematyków poddawało go w wątpliwość. W chwili obecnej znakomita większość uważa, że aksjomat wyboru jest prawdziwy, nawet jeśli niektóre z jego konsekwencji są sprzeczne z intuicją.

W tym wykładzie przedstawiamy szereg twierdzeń, które są równoważne lub wynikają z aksjomatu wyboru. Zanim przejdziemy do wypowiedzi tych faktów, wprowadzimy jeszcze jeden koncept.

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,) jest dobrym porządkiem, jeśli

  • jest porządkiem liniowym,
  • każdy niepusty podzbiór A zawiera element najmniejszy względem .

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

Istnienie zbiorów dobrze uporządkowanych nie jest nowością. Zdefiniowany w Wykładzie 7 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,) i dla dowolnego zbioru BA zbiór ten jest dobrze uporządkowany przez relację B×B.

Dowód

Relacja B×B to relacja zawężona do elementów zbioru B. Mamy dla każdego a,bB

aba(B×B)b

Oczywistym wnioskiem jest, że zbiór B jest uporządkowany liniowo przez B×B. Pozostaje wykazać, że każdy podzbiór zbioru B ma element najmniejszy. Ustalmy dowolne CB, ponieważ BA zbiór C jest również podzbiorem A i z definicji zbioru dobrze uporządkowanego wynika, że C posiada element najmniejszy względem . Ponieważ CB, to ten sam element jest elementem najmniejszym w C względem B×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. W dalszej części wykładu ograniczamy się do własności tych porządków bezpośrednio powiązanych z aksjomatem wyboru.

Aksjomat wyboru i twierdzenia mu równoważne

Tę część wykładu zaczniemy od przytoczenia aksjomatu wyboru w postaci, w jakiej został wprowadzony w Wykładzie 4.

Aksjomat Wyboru. Następująca formuła jest prawdziwa:

x(xyz(zxyx)(z=yzy=))wv(vxuvw={u}).

Rysunek 1

Aksjomat ten mówi, że jeśli x jest rodziną niepustych, parami rozłącznych zbiorów, to istnieje zbiór mający z każdym elementem x dokładnie jeden element wspólny. Zbiór w, którego istnienie gwarantuje aksjomat wyboru, "wybiera" z każdego elementu rodziny dokładnie jeden element (rysynek 1). Zbiory jako pionowe, nieregularne obszary, zbiór wybierający jako poziomy zbiór przecinający każdy z nich na dokładnie jednym elemencie.

W dalszej części wykładu prezentujemy kilka twierdzeń równoważnych aksjomatowi wyboru. To znaczy, że na gruncie aksjomatyki ZF, bez aksjomatu wyboru, założenie prawdziwości któregokolwiek z tych twierdzeń implikuje prawdziwość aksjomatu wyboru i vice versa. Bardzo istotną częścią dowodów jest wykazanie, że twierdzenia te są dokładnie równoważne aksjomatowi wyboru na gruncie ZF. Na gruncie aksjomatyki ZFC twierdzenia te dają się udowodnić przy użyciu aksjomatu wyboru.

Aby wykazać równoważność między aksjomatem wyboru a poniższymi twierdzeniami, pokażemy, że każde twierdzenie implikuje następne i że ostatnie implikuje aksjomat wyboru. Jest to najprostszy sposób na wykazanie równoważności.

Twierdzenia dotyczące zbiorów

Pierwsze, równoważne aksjomatowi wyboru, twierdzenie mówi o istnieniu funkcji wybierającej. W aksjomacie wyboru, z rodziny zbiorów wybieraliśmy elementy przez utworzenie zbioru. Aby możliwe było wybranie dokładnie jednego elementu z każdego zbioru, niezbędne było założenie o rozłączności tych zbiorów. Poniższe twierdzenie mówi o istnieniu funkcji wybierającej elementy ze zbiorów.

Twierdzenie 3.1.

Dla dowolnej rodziny niepustych zbiorów istnieje funkcja, która każdemu zbiorowi w tej rodzinie przyporządkowuje któryś z jego elementów. Formalnie

xxff:xx(yyxf(y)y)

Poniżej przedstawiamy dowód, na gruncie ZF, że aksjomat wyboru implikuje powyższe twierdzenie.

Dowód

Aksjomat wyboru implikuje Twierdzenie 3.1 (patrz Twierdzenie 3.1.) Ustalmy dowolny, niezawierający zbioru pustego, zbiór x. Skonstruujemy zbiór x1, do którego stosować będziemy aksjomat wyboru. Zbiór

x1={{y}×y:yx}

jest rodziną zbiorów parami rozłącznych - elementy pochodzące z różnych zbiorów x różnią się w x1 na pierwszej współrzędnej. Do zbioru x1 stosujemy aksjomat wyboru i otrzymujemy zbiór wx×x. Ponieważ z każdego zbioru x1 wybraliśmy dokładnie jeden element, to w jest funkcją z x do x. Definicja x1 gwarantuje również, że w(y)y dla każdego yx. Wnioskujemy, że w może być wzięte jako f i że aksjomat wyboru implikuje Twierdzenie 3.1 (patrz Twierdzenie 3.1.).

Kolejny fakt, równoważny aksjomatowi wyboru, przedstawiamy w formie ćwiczenia:

Ćwiczenie 3.1

Wykaż, że stwierdzenie "dla każdej surjekcji f:xy istnieje iniekcja g:yx taka, że fg jest funkcją identycznościową na y" jest równoważne aksjomatowi wyboru na gruncie ZF.

Rozwiązanie

Twierdzenia dotyczące porządków

Felix Hausdorff (1868-1942)
Zobacz biografię

Kolejne dwa twierdzenia dotyczą częściowych porządków. Pierwsze z

nich gwarantuje istnienie maksymalnych łańcuchów.

Twierdzenie 3.2. [Zasada maksimum Felixa Hausdorff'a]

W każdym zbiorze częściowo uporządkowanym istnieje maksymalny, pod względem inkluzji, łańcuch.

Zgodnie z przyjętą strategią postępowania wykażemy, że Twierdzenie 3.1 (patrz twierdzenie 3.1.) implikuje zasadę maksimum Felixa Hausdorffa.

Dowód

Twierdzenie 3.1 (patrz twierdzenie 3.1.) implikuje zasadę maksimum Felixa Hausdorffa. Dowód tej implikacji opiera się na Twierdzeniu Bourbakiego-Witta z Wykładu 10 (patrz Twierdzenie Bourbakiego-Witta). Ustalmy dowolny zbiór częściowo uporządkowany (A,). Jeśli A=, to zbiór ten posiada dokładnie jeden łańcuch i fakt jest dowiedziony. Jeśli A, oznaczmy przez (B,) zbiór częściowo uporządkowany składający się z łańcuchów w (A,) uporządkowanych przez inkluzję


B={CA:C jest uporządkowany liniowo przez }

Zbiór częściowo uporządkowany (B,) jest łańcuchowo zupełny. Aby to pokazać, ustalmy dowolny, uporządkowany liniowo przez inkluzję zbiór DB. Jeśli D należy do B, to jest to niewątpliwie supremum zbioru D. Aby wykazać, że D jest elementem B, należy wykazać, że jest on uporządkowany liniowo przez . Weźmy dwa elementy D - x i y. Istnieje CxD i CyD takie, że xCx, a yCy. Ponieważ D jest łańcuchem, to, bez straty ogólności, możemy założyć, że CxCy. Wtedy, zarówno x jak i y, należą do Cy i ponieważ CyB, wnioskujemy, że x i y są porównywalne. Wykazaliśmy, że dowolne dwa elementy D są porównywalne, czyli że D jest uporządkowany liniowo przez .

Na mocy Twierdzenia 3.1 (patrz Twierdzenie 3.1.) definiujemy funkcję wyboru f dla zbioru 𝒫(A){} zwracającą, dla każdego niepustego podzbioru A, jego element. Twierdzenie Bourbakiego-Witta będziemy stosować do funkcji g przeprowadzającej B w B i zdefiniowanej następująco:

g(C)={C{f(C)},jeśli C,zbiór elementów porównywalnych z każdym elementem C,jest niepustyC,w przeciwnym przypadku..


Funkcja g dostaje jako argument łańcuch w (A,) oznaczony przez C i przy pomocy funkcji f rozszerza (jeśli jest to możliwe) C o jeden element porównywalny ze wszystkimi elementami C, otrzymując w ten sposób nowy, większy łańcuch.

Zbiór (B,) i funkcja g spełniają założenia Twierdzenia Bourbakiego-Witta i, na jego mocy, istnieje punkt stały g, czyli zbiór D taki, że g(D)=D. To gwarantuje, że zbiór D elementów porównywalnych z każdym elementem D jest pusty, czyli że D jest maksymalnym pod względem inkluzji łańcuchem w A.

Równoważną wersję zasady Felixa Hausdorffa pozostawiamy jako ćwiczenie.

Ćwiczenie 3.2

Wykaż, na gruncie ZF, że następujące stwierdzenie jest równoważne zasadzie Felixa Hausdorffa: "W każdym zbiorze częściowo uporządkowanym każdy łańcuch jest zawarty w maksymalnym, pod względem inkluzji, łańcuchu".

Rozwiązanie


Kolejne z równoważnych aksjomatowi wyboru twierdzeń nosi nazwę Lematu Maxa Augusta Zorna. Nazwa ta ma korzenie historyczne i dlatego pozostawiamy ją w tym brzmieniu.

Max August Zorn (1906-1993)
Zobacz biografię

Twierdzenie 3.3. [Lemat Maxa Augusta Zorna]

Jeśli w pewnym zbiorze częściowo uporządkowanym, każdy łańcuch jest ograniczony od góry, to istnieje w nim element maksymalny.

Dowodzimy kolejną implikację

Dowód

Zasada maksimum Felixa Hausdorffa implikuje Lemat Maxa Augusta Zorna. Dowód tej implikacji jest bardzo prosty. Wybierzmy dowolny zbiór częściowo uporządkowany spełniający założenia Lematu Maxa Augusta Zorna, czyli taki, że każdy łańcuch jest w nim ograniczony od góry. Na mocy zasady maksimum Felixa Hausdorffa istnieje w tym zbiorze łańcuch maksymalny pod względem inkluzji. Łańcuch ten posiada ograniczenie górne, które musi być elementem łańcucha i równocześnie elementem maksymalnym zbioru. Jeśliby tak nie było, to dodając element istotnie większy od tego ograniczenia do łańcucha danego przez zasadę maksimum Hausdorffa, uzyskalibyśmy łańcuch istotnie większy pod względem inkluzji.

Kolejne ćwiczenie mówi o istnieniu maksymalnego antyłańcucha.

Ćwiczenie 3.3

Udowodnij, używając lematu Maxa Augusta Zorna, że w każdym zbiorze częściowo uporządkowanym istnieje antyłańcuch maksymalny pod względem inkluzji.

Rozwiązanie

Poniższe ćwiczenie dotyczy rozszerzeń porządków.

Ćwiczenie 3.4

Wykaż, używając lematu Maxa Augusta Zorna, że każdy częściowy porządek da się rozszerzyć do porządku liniowego. To znaczy, że dla każdego zbioru częściowo uporządkowanego (A,) istnieje liniowy porządek na A taki, że

xyxy

dla dowolnych x i y w A.

Rozwiązanie


W Wykładzie 5 (patrz Wykład 5) pokazaliśmy, że dla dowolnej relacji istnieje najmniejsza relacja równoważności zawierająca tą relację. W poniższym ćwiczeniu pokażemy, że dla niektórych relacji istnieje maksymalna, pod względem inkluzji, relacja równoważności zawarta w nich

Ćwiczenie 3.5

Użyj lematu Maxa Augusta Zorna, aby wykazać, że dla każdej relacji ρA×A, jeśli 1Aρ, to istnieje maksymalna pod względem inkluzji relacja równoważności zawarta w ρ.

Rozwiązanie


Kolejny warunek równoważny dotyczy zbiorów dobrze uporządkowanych.

Twierdzenie Ernsta Zermelo

Ernst Friedrich Ferdinand Zermelo (1871-1953)
Zobacz biografię

Twierdzenie Zermelo jest jedną z równoważnych postaci aksjomatu wyboru, w którą wyjątkowo trudno uwierzyć.

Twierdzenie 3.4. [Zermelo]

Dla każdego zbioru istnieje relacja, która jest dobrym porządkiem na tym zbiorze.

Kolejny dowód to

Dowód

Lemat Maxa Augusta Zorna implikuje Twierdzenie Ernsta Zermelo. Ustalmy dowolny zbiór niepusty A (dla zbioru pustego porządek pusty porządkuje go dobrze). Rozważmy zbiór B składający się z podzbiorów A, które mogą być dobrze uporządkowane, wraz z dobrymi porządkami

B={(C,):CA jest dobrym porządkiem naC}

i zdefiniujmy relację na elementach B w następujący sposób

(C,)(C,)CC{cd (cCdC)(cdcd) oraz cd (cCdCC)cd

czyli dwa elementy B są porównywalne wtedy i tylko wtedy, jeśli zbiory, na których, są określone są porównywalne w sensie inkluzji i porządek zdefiniowany na większym zbiorze jest rozszerzeniem porządku zdefiniowanego na mniejszym przez dodanie elementów większych od wszystkich zastanych. Aby zastosować Lemat Maxa Augusta Zorna do zbioru częściowo uporządkowanego (B,) musimy wykazać, że każdy łańcuch w tym zbiorze ma ograniczenie górne.

Niech DB będzie łańcuchem w sensie . Zdefiniujmy C0 jako unię wszystkich pierwszych współrzędnych elementów D i 0 jako unię drugich współrzędnych elementów D. Niewątpliwie C0A. Ponieważ D jest łańcuchem w sensie , to relacja 0 jest porządkiem liniowym na C0. Aby wykazać, że 0 jest dobrym porządkiem na C0, ustalmy dowolny EC0. Niewątpliwie istnieje element (C,)D taki, że EC. Ponieważ (C,)B, to C jest dobrze uporządkowany przez i w związku z tym EC posiada element najmniejszy w C,) - oznaczmy go przez x. Element x będzie również najmniejszym elementem E w C0. Aby to wykazać, ustalmy yE. Jeśli yC, to niewątpliwie xy i w związku z tym x0y. Jeśli yC, to yCC dla jakiegoś (C,)D. Ponieważ D jest łańcuchem wnioskujemy, że CC i na mocy definicji , że xy, czyli x0y, co należało wykazać.

Stosując Lemat Maxa Augusta Zorna wnioskujemy, że w zbiorze częściowo uporządkowanym (B,) istnieje element maksymalny (D,). Jeśli D=A, to jest wymaganym dobrym porządkiem na A. Aby wykazać, że tak musi być, załóżmy niewprost, że DA, czyli że istnieje dAD. Wtedy zbiór D{d} wraz z dobrym porządkiem zdefiniowanym jako

abb=d(aDbDab)

jest większy w sensie relacji , co przeczy maksymalności D. Uzyskana w dowodzie niewprost sprzeczność kończy rozumowanie.

Twierdzenie Ernsta Zermelo jest sprzeczne z intuicją wielu matematyków. Gwarantuje ono między innymi istnienie dobrego porządku na liczbach rzeczywistych, czyli takiego liniowego uporządkowania liczb rzeczywistych, w którym każdy zbiór posiada element najmniejszy. Porządek taki jest trudnym do wyobrażenia konceptem matematycznym.

Aby zamknąć ciąg rozumowań, wystarczy wykazać, że Twierdzenie Zermelo implikuje aksjomat wyboru.

Dowód

Twierdzenie Zermelo implikuje aksjomat wyboru. Niech x będzie dowolnym zbiorem spełniającym założenia aksjomatu wyboru, to znaczy takim, że x i że wszystkie elementy x są parami rozłączne. Niech będzie istniejącym, na podstawie Twierdzenia Zermelo, dobrym uporządkowaniem zbioru x. Zbiór wybierający po jednym elemencie z każdego elementu x otrzymujemy, stosując zasadę wycinania do x

w={yx:zyzxy jest najmniejszym elementem z względem relacji }

Zbiór w posiada po dokładnie jednym elemencie wspólnym z każdym zbiorem zx - jest to element najmniejszy w z względem dobrego uporządkowania x.

Nasze rozumowanie wykazało, że wszystkie powyższe fakty są równoważne na gruncie ZF. Jak wspomnieliśmy na początku, aksjomat wyboru jest kontrowersyjnym aksjomatem. Niektóre z równoważnych mu stwierdzeń są intuicyjnie oczywiste, inne przeczą intuicji. Podsumujemy rozdział żartem autorstwa Jerrego Bona:

The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Max August Zorn's Lemma? (Aksjomat wyboru jest oczywiście prawdziwy; twierdzenie Ernsta Zermelo jest oczywiście fałszem; lemat Zorn'a kto wie?)

Twierdzenia wymagające aksjomatu wyboru

Wiele twierdzeń wymaga aksjomatu wyboru, choć założenie ich prawdziwości w ZF nie implikuje prawdziwości tego aksjomatu. W tej części wykładu przedstawimy kilka tego typu twierdzeń. Zwróćmy uwagę, że żadna z dostępnych w tej chwili technik dowodowych nie nadaje się do udowodnienia, że jakiś fakt jest słabszy od aksjomatu wyboru. Możemy pokazać, że jeśli aksjomat wyboru jest prawdą, to dane twierdzenie jest prawdziwe, ale nie możemy pokazać, że jeśli założymy dane twierdzenie, to aksjomat wyboru nie musi być prawdą. Nie jesteśmy w stanie zdecydować, czy aksjomat wyboru jest niezbędny do udowodnienia danego twierdzenia - tego typu dowody wykraczają poza zakres tego kursu i nie będą prezentowane.

Pierwszy z faktów, które będziemy dowodzić brzmi następująco:

Twierdzenie 4.1.

Dla dowolnego zbioru nieskończonego istnieje iniekcja ze zbioru liczb naturalnych w ten zbiór.

Dowód 1

Co możemy dowieść bez aksjomatu wyboru. Ustalmy dowolny zbiór nieskończony A. Na mocy definicji z Wykładu 9 wiemy, że nie istnieje bijekcja między A a żadną liczbą naturalną. Pokażmy najpierw, że dla każdej liczby naturalnej n istnieje iniekcja z n do A. Dowód przeprowadzamy przez indukcję na n.

  • Jeśli n=0, to niewątpliwie istnieje iniekcja ze zbioru pustego w A - jest to funkcja pusta.
  • Załóżmy, że istnieje iniekcja f:nA. Ponieważ nie istnieje bijekcja pomiędzy n a A, wnioskujemy, że f(n)A, czyli że istnieje aAf(n). Zdefiniujmy f:nA jako
f(m)={f(m),jeśli mn,a,jeśli m=n.

Funkcja f jest iniekcją, co kończy dowód indukcyjny.

Wykazaliśmy jedynie, że dla każdej liczby naturalnej istnieje iniekcja z niej w A. Nie udało nam się wykazać istnienia jednej funkcji dla całego zbioru .

Dowód 2

Dowód przy użyciu aksjomatu wyboru. Aby udowodnić istnienie iniekcji z w A, skorzystamy z Twierdzenia twierdzenie 3.1. równoważnego aksjomatowi wyboru. Zastosujmy je do zbioru 𝒫(A){}, dostając funkcję e:𝒫(A){}A taką, że e(B)B dla każdego B, jeśli tylko BA. Aby udowodnić istnienie żądanej funkcji, zastosujemy twierdzenie o definiowaniu przez indukcję. Dzięki temu twierdzeniu dostaniemy funkcję h:×{}𝒫(A) taką, że

h(0,)={e(A)}

oraz

h(n,)=h(n,){e(Ah(n))}

Jest to funkcja, która każdej liczbie naturalnej przyporządkowuje zbiór o jeden element większy niż przyporządkowany poprzedniej liczbie naturalnej. Aby otrzymać żądaną iniekcję wystarczy zdefiniować:

f(n)=xh(n,)h(n,)={x}

Funkcja f jest dobrze zdefiniowana, ponieważ dla każdego n zbiór h(n,)h(n,) jest jednoelementowy (co gwarantuje definicja funkcji e). A jest iniekcją, ponieważ h(m,)h(n,), jeśli tylko mn.

Kolejną konsekwencję podajemy w formie ćwiczenia.

Ćwiczenie 4.1

Rozważmy przedział [1,3] w zbiorze liczb rzeczywistych. Niech funkcja f:𝒫([1,3]) będzie "miłą miarą zbiorów", jeśli:

  • dla każdego zbioru jego miara jest większa lub równa 0 i f([0,1])=1,
  • jeśli zbiór A ma miarę f(A) to f({x+r:xA})=f(A) dla dowolnego r - to znaczy, że przesunięcie zbioru o wektor nie zmienia jego miary,
  • jeśli A0,A1, są zbiorami parami rozłącznymi, to suma tych zbiorów ma miarę równą sumie miar
f(iAi)=if(Ai),

to znaczy, że sumowanie zbiorów rozłącznych zachowuje miarę.

Wykaż, że nie istnieje miła miara zbiorów.

Podpowiedź
Podpowiedź
Rozwiązanie

Podsumowanie

W powyższym wykładzie przedstawiliśmy twierdzenia równoważne aksjomatowi wyboru i udowodniliśmy kilka jego konsekwencji. Aksjomat wyboru jest kontrowersyjnym aksjomatem. Przyjęcie go, pociąga za sobą nieintuicyjne konsekwencje. Zakładając aksjomat wyboru, możemy wykazać, że zbiór liczb rzeczywistych daje się uporządkować w taki sposób, że każdy jego podzbiór ma element najmniejszy. Kolejną nieintuicyjną konsekwencją jest wykazany przez Stefana Banacha i Alfreda Tarskiego paradoksalny rozkład trójwymiarowej kuli na sześć części, z których, za pomocą obrotów i translacji, możemy skleić dwie kule identyczne z pierwszą.

Bertrand Arthur William Russell (1872-1970)
Zobacz biografię

Z drugiej strony, wiele intuicyjnych faktów wymaga aksjomatu wyboru lub jednej z jego słabszych wersji. Twierdzenie, że jeśli zbiór jest nieskończony, to istnieje iniekcja liczb naturalnych w ten zbiór, jest intuicyjnym faktem. Bertrand Russell powiedział o aksjomacie wyboru:

The Axiom of Choice is necessary to select a set from an infinite number of socks, but not an infinite number of shoes (Aksjomat wyboru jest niezbędny, aby wybrać zbiór z nieskończonej ilości skarpet, ale nie z nieskończonej ilości butów).

Znaczenie tego cytatu powinno być jasne. Jesteśmy w stanie wybrać po jednym bucie z nieskończonego zbioru par mówiąc "wybierzmy buty lewe". Nie jesteśmy w stanie przeprowadzić tego rozumowania, jeśli byty występujące w zbiorach są identyczne.