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
m (Zastępowanie tekstu - "<div class="thumb t(.*)"><div style="width:(.*);"> <flash>file=(.*)\.swf\|width=(.*)\|height=(.*)<\/flash> <div\.thumbcaption>(.*)<\/div> <\/div><\/div>" na "$4x$5px|thumb|$1|$6")
 
(Nie pokazano 16 wersji utworzonych przez 5 użytkowników)
Linia 30: Linia 30:
 
<math>\sqsubseteq</math>.
 
<math>\sqsubseteq</math>.
 
}}
 
}}
Istnienie zbiorów dobrze uporządkowanych nie jest nowością. Zdefiniowany w [http://osilek.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogo%C5%9Bci/Wyk%C5%82ad_7:_Konstrukcja_von_Neumanna_liczb_naturalnych%2C_twierdzenie_o_indukcji%2C_zasady_minimum%2C_maksimum%2C_definiowanie_przez_indukcje Wykładzie 7] zbiór liczb naturalnych jest dobrze uporządkowany na mocy dowiedzionych tam twierdzeń. Łatwo zauważyć,
+
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
 
ż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
  
Linia 51: Linia 51:
 
}}
 
}}
  
Dokładnej analizie własności zbiorów dobrze uporządkowanych jest poświęcony [http://osilek.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogo%C5%9Bci/Wyk%C5%82ad_12:_Twierdzenie_o_indukcji._Liczby_porz%C4%85dkowe._Zbiory_liczb_porz%C4%85dkowych._Twierdzenie_o_definiowaniu_przez_indukcje_pozasko%C5%84czon%C4%85&action=edit 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.
+
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.
  
 
==Aksjomat wyboru i twierdzenia mu równoważne==
 
==Aksjomat wyboru i twierdzenia mu równoważne==
  
 
Tę część wykładu zaczniemy od przytoczenia aksjomatu wyboru w
 
Tę część wykładu zaczniemy od przytoczenia aksjomatu wyboru w
postaci, w jakiej został wprowadzony w [http://osilek.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogo%C5%9Bci/Wyk%C5%82ad_4:_Teoria_mnogo%C5%9Bci_ZFC._Operacje_na_zbiorach Wykładzie 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]].
  
 
'''Aksjomat Wyboru'''. Następująca formuła jest prawdziwa:  
 
'''Aksjomat Wyboru'''. Następująca formuła jest prawdziwa:  
Linia 62: Linia 62:
 
<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>
 
<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>
  
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.
+
[[File:logika-3.1.svg|350x250px|thumb|right|Rysunek 1]]
'''Obrazek 3.1''' 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 dokładnie jednym elemencie.
 
wybierający jako poziomy zbiór przecinający każdy z nich na dokładnie jednym elemencie.
  
Linia 120: Linia 121:
  
 
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.
 
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.
 
+
}}
 
<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">
 
<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">
 
Pokażmy najpierw, że z aksjomatu wyboru 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>
Linia 145: Linia 146:
 
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.
 
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.
 
</div></div>
 
</div></div>
}}
+
 
 
</span>
 
</span>
  
Linia 160: Linia 161:
  
 
Zgodnie z przyjętą strategią postępowania wykażemy, że
 
Zgodnie z przyjętą strategią postępowania wykażemy, że
Twierdzenie 3.1 (patrz [[#twierdzenie_3_1|twierdzenie 3.1.]]) implikuje zasadę maksimum [http://osilek.mimuw.edu.pl/index.php?title=Biografia_Hausdorff%2C_Felix Felixa Hausdorffa].
+
Twierdzenie 3.1 (patrz [[#twierdzenie_3_1|twierdzenie 3.1.]]) implikuje zasadę maksimum [[Biografia Hausdorff|Felixa Hausdorffa]].
  
 
{{dowod|||
 
{{dowod|||
Linia 180: Linia 181:
 
<center><math> g(C)=\left\{
 
<center><math> g(C)=\left\{
 
\begin{array}{ll}
 
\begin{array}{ll}
C\cup \{f(C')\},& \quad \textrm{jeśli } C', \textrm{zbiór elementów porównywalnych z każdym elementem } C, \textrm{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 ,& \quad \textrm{w przeciwnym przypadku}. \end{array} \right.</math></center>
+
C ,& \quad \text{w przeciwnym przypadku}. \end{array} \right.</math></center>
  
 
<br>
 
<br>
Linia 189: Linia 190:
 
}}
 
}}
  
Równoważną wersję zasady [http://osilek.mimuw.edu.pl/index.php?title=Biografia_Hausdorff%2C_Felix Felixa Hausdorffa] pozostawiamy jako ćwiczenie.
+
Równoważną wersję zasady [[Biografia Hausdorff|Felixa Hausdorffa]] pozostawiamy jako ćwiczenie.
  
 
{{cwiczenie|3.2||
 
{{cwiczenie|3.2||
Linia 195: Linia 196:
 
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 Felixa Hausdorffa: "W każdym zbiorze częściowo uporządkowanym każdy łańcuch jest zawarty w maksymalnym, pod względem inkluzji, łańcuchu".
 
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".
 
+
}}
 
<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">  
 
<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">  
Aby udowodnić zasadę maksimum '''<u>Felixa Hausdorffa</u>''' 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 [[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 wykazać powyższe stwierdzenie używając zasady '''<u>Felixa Hausdorffa</u>''', 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
+
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
  
<center><math>B = \{a\in A\ : a</math> jest porównywalne z każdym elementem <math>C}\}.
+
<center><math>B = \{a\in A\ : a \text{ jest porównywalne z każdym elementem }C\}.
 
</math></center>
 
</math></center>
  
 
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.
 
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.
 
</div></div>
 
</div></div>
}}
+
 
  
 
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.
 
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.
Linia 227: Linia 228:
 
{{cwiczenie|3.3||
 
{{cwiczenie|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.   
 
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.   
 +
}}
 
<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">
 
<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 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 (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\ :\ C</math> jest antyłańcuchem w <math>A}\}
+
<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 <math>(B,\subset)</math> lemat '''<u>Maxa Augusta Zorn'a</u>''', 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ę.
+
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ę.
  
Na podstawie lematu '''<u>Maxa Augusta Zorn'a</u>''' wnioskujemy, że <math>(B,\subset)</math> posiada element maksymalny - jest to, poszukiwany przez nas, maksymalny w sensie inkluzji antyłańcuch.
+
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.
 
</div></div>
 
</div></div>
}}
+
 
 
Poniższe ćwiczenie dotyczy rozszerzeń porządków.
 
Poniższe ćwiczenie dotyczy rozszerzeń porządków.
  
Linia 248: Linia 250:
  
 
dla dowolnych <math>x</math> i <math>y</math> w <math>A</math>.  
 
dla dowolnych <math>x</math> i <math>y</math> w <math>A</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">
 
<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 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>
 
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>
Linia 278: Linia 280:
 
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.
 
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>
 
</div></div>
}}
+
 
  
 
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
 
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
Linia 286: Linia 288:
  
 
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>.
 
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">
 
<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 [http://osilek.mimuw.edu.pl/index.php?title=Biografia_Zorn%2C_Max_August Maxa Augusta Zorn'a] stosować będziemy do zbioru uporządkowanego przez inkluzję. Zbiorem tym jest
+
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 </math> jest relacją równoważności na <math>A}\}.
+
<center><math>B = \{\delta\ \subset A\times A\ : \delta\ \subset\ \rho\ \land \delta \text{ jest relacją równoważności na }A\}.
 
</math></center>
 
</math></center>
  
Linia 301: Linia 304:
 
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.
 
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.
 
</div></div>
 
</div></div>
}}
+
 
  
 
Kolejny warunek równoważny dotyczy zbiorów dobrze uporządkowanych.
 
Kolejny warunek równoważny dotyczy zbiorów dobrze uporządkowanych.
Linia 311: Linia 314:
 
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|3.4. [Zermelo]||
  
Linia 316: Linia 320:
 
tym zbiorze.
 
tym zbiorze.
 
}}
 
}}
 
+
</span>
 
Kolejny dowód to
 
Kolejny dowód to
  
Linia 323: Linia 327:
 
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 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
  
<center><math>B = \{(C,\sqsubseteq)\,:\, C\subset A \land \sqsubseteq </math> jest dobrym porządkiem na <math>C}\}
+
<center><math>B = \{(C,\sqsubseteq)\,:\, C\subset A \land \sqsubseteq \text{ jest dobrym porządkiem na} C\}
 
</math></center>
 
</math></center>
  
Linia 330: Linia 334:
 
<center>
 
<center>
 
<math>  
 
<math>  
\begin{array}{ll}
 
\displaystyle
 
 
(C,\sqsubseteq) \preccurlyeq (C',\sqsubseteq')  
 
(C,\sqsubseteq) \preccurlyeq (C',\sqsubseteq')  
\iff & C\subset C' \land  
+
\iff C\subset C' \land  
\left\{\begin{array}{l}\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 \end{array} \right
+
\forall c \forall d\ (c\in C\land d\in C) \implies (c\sqsubseteq d \iff c\sqsubseteq' d) & \text{ oraz }\\
\end{array}</math>
+
\forall c \forall d\ (c\in C\land d\in C'\setminus C) \implies c\sqsubseteq' d
 +
\end{cases}
 +
</math>
 
</center>
 
</center>
  
Linia 355: Linia 359:
 
}}
 
}}
  
Twierdzenie [http://osilek.mimuw.edu.pl/index.php?title=Biografia_Zermelo%2C_Ernst_Friedrich_Ferdinand 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.
+
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.
  
 
Aby zamknąć ciąg rozumowań, wystarczy wykazać, że Twierdzenie Zermelo implikuje aksjomat wyboru.
 
Aby zamknąć ciąg rozumowań, wystarczy wykazać, że Twierdzenie Zermelo implikuje aksjomat wyboru.
Linia 405: Linia 409:
 
{{dowod|1||
 
{{dowod|1||
  
Co możemy dowieść bez aksjomatu wyboru. Ustalmy dowolny zbiór nieskończony <math>A</math>. Na mocy definicji z '''<u>Wykładu 9</u>''' 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>.
+
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>.
  
 
* Jeśli <math>n=0</math>, to niewątpliwie istnieje iniekcja ze zbioru pustego w <math>A</math> - jest to funkcja pusta.
 
* Jeśli <math>n=0</math>, to niewątpliwie istnieje iniekcja ze zbioru pustego w <math>A</math> - jest to funkcja pusta.
Linia 415: Linia 419:
 
\left\{
 
\left\{
 
\begin{array}{ll}
 
\begin{array}{ll}
f(m),& \quad \textrm{jeśli } m \in n,\\
+
f(m),& \quad \text{jeśli } m \in n,\\
a ,& \quad \textrm{jeśli } m=n. \end{array} \right.
+
a ,& \quad \text{jeśli } m=n. \end{array} \right.
 
</math></center>
 
</math></center>
  
Linia 465: Linia 469:
  
 
Wykaż, że nie istnieje miła miara zbiorów.
 
Wykaż, że nie istnieje miła miara zbiorów.
 
+
}}
 
<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">
 
<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">
 
Połóż dwie liczby w relacji ze sobą jeśli ich różnica jest wymierna.
 
Połóż dwie liczby w relacji ze sobą jeśli ich różnica jest wymierna.
Linia 513: Linia 517:
 
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.
 
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>
 
</div></div>
}}
 
  
 
==Podsumowanie==
 
==Podsumowanie==
Linia 523: Linia 526:
 
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 [http://osilek.mimuw.edu.pl/index.php?title=Biografia_Banacha Stefana Banacha] i [http://osilek.mimuw.edu.pl/index.php?title=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ą.
+
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ą.
  
[[grafika:Russell.jpeg|thumb|right||Bertrand Arthur William Russell (1872-1970)<br>[[Biografia Russell|Zobacz biografię]]]]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. [http://osilek.mimuw.edu.pl/index.php?title=Biografia_Russell Bertrand 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 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)
+
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
 
Znaczenie tego cytatu powinno być jasne. Jesteśmy w stanie wybrać po

Aktualna wersja na dzień 11:08, 3 paź 2021

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

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

Mówimy wtedy, że zbiór 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 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 i dla dowolnego zbioru zbiór ten jest dobrze uporządkowany przez relację .

Dowód

Relacja to relacja zawężona do elementów zbioru . Mamy dla każdego

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

End of proof.gif

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:

Rysunek 1

Aksjomat ten mówi, że jeśli jest rodziną niepustych, parami rozłącznych zbiorów, to istnieje zbiór mający z każdym elementem dokładnie jeden element wspólny. Zbiór , 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

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 . Skonstruujemy zbiór , do którego stosować będziemy aksjomat wyboru. Zbiór

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

End of proof.gif

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

Ćwiczenie 3.1

Wykaż, że stwierdzenie "dla każdej surjekcji istnieje iniekcja taka, że jest funkcją identycznościową na " 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 . Jeśli , to zbiór ten posiada dokładnie jeden łańcuch i fakt jest dowiedziony. Jeśli , oznaczmy przez zbiór częściowo uporządkowany składający się z łańcuchów w uporządkowanych przez inkluzję


jest uporządkowany liniowo przez

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

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


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

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

End of proof.gif

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.

End of proof.gif

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 istnieje liniowy porządek na taki, że

dla dowolnych i w .

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 , jeśli , 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 (dla zbioru pustego porządek pusty porządkuje go dobrze). Rozważmy zbiór składający się z podzbiorów , które mogą być dobrze uporządkowane, wraz z dobrymi porządkami

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

czyli dwa elementy 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 musimy wykazać, że każdy łańcuch w tym zbiorze ma ograniczenie górne.

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

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

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

End of proof.gif

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

jest najmniejszym elementem względem relacji

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

End of proof.gif

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 . Na mocy definicji z Wykładu 9 wiemy, że nie istnieje bijekcja między a żadną liczbą naturalną. Pokażmy najpierw, że dla każdej liczby naturalnej istnieje iniekcja z do . Dowód przeprowadzamy przez indukcję na .

  • Jeśli , to niewątpliwie istnieje iniekcja ze zbioru pustego w - jest to funkcja pusta.
  • Załóżmy, że istnieje iniekcja . Ponieważ nie istnieje bijekcja pomiędzy a , wnioskujemy, że , czyli że istnieje . Zdefiniujmy jako

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

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

End of proof.gif

Dowód 2

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

oraz

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ć:

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

End of proof.gif

Kolejną konsekwencję podajemy w formie ćwiczenia.

Ćwiczenie 4.1

Rozważmy przedział w zbiorze liczb rzeczywistych. Niech funkcja będzie "miłą miarą zbiorów", jeśli:

  • dla każdego zbioru jego miara jest większa lub równa i ,
  • jeśli zbiór ma miarę to dla dowolnego - to znaczy, że przesunięcie zbioru o wektor nie zmienia jego miary,
  • jeśli są zbiorami parami rozłącznymi, to suma tych zbiorów ma miarę równą sumie miar

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.