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ą: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 19: Linia 19:
 
Przykładem zbioru dobrze uporządkowanego jest zbiór <math>\displaystyle \mathbb{N}</math> uporządkowany, przez
 
Przykładem zbioru dobrze uporządkowanego jest zbiór <math>\displaystyle \mathbb{N}</math> uporządkowany, przez
 
<math>\displaystyle \subset</math>. <br>
 
<math>\displaystyle \subset</math>. <br>
'''<u>Zasada minimum (Wykład 7)</u>''' mówi, że w każdym podzbiorze <math>\displaystyle \mathbb{N}</math> istnieje element najmniejszy, a więc, że ten porządek jest dobry.
+
Zasada minimum (patrz
 +
[[Logika i teoria mnogości/Wykład 7: Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje#twierdzenie_5_2|Wykład 7, Twierdzenie 5.2]])
 +
mówi, że w każdym podzbiorze <math>\displaystyle \mathbb{N}</math> istnieje element najmniejszy, a więc, że ten porządek jest dobry.
 
}}
 
}}
  
Linia 36: Linia 38:
 
<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">   
  
Niech <math>\displaystyle (X,\leq)</math> będzie dobrym porządkiem. Jeśli <math>\displaystyle X</math> jest pusty lub jednoelementowy to jest dobrze uporządkowany. W przeciwnym przypadku weźmy dowolne dwa różne elementy <math>\displaystyle x,y \in X</math>. Wtedy <math>\displaystyle \{x,y\} \subset X</math> i istnieje element minimalny w <math>\displaystyle \{x,y\}</math>, a więc <math>\displaystyle x \leq y</math> lub <math>\displaystyle y\leq x</math>. Wobec tego dowolne dwa elementy <math>\displaystyle X</math> są porównywalne.
+
Niech <math>\displaystyle (X,\leq)</math> będzie dobrym porządkiem. Jeśli <math>\displaystyle X</math> jest pusty lub jednoelementowy, to jest dobrze uporządkowany. W przeciwnym przypadku weźmy dowolne dwa różne elementy <math>\displaystyle x,y \in X</math>. Wtedy <math>\displaystyle \{x,y\} \subset X</math> i istnieje element minimalny w <math>\displaystyle \{x,y\}</math>, a więc <math>\displaystyle x \leq y</math> lub <math>\displaystyle y\leq x</math>. Wobec tego dowolne dwa elementy <math>\displaystyle X</math> są porównywalne.
 
</div></div>
 
</div></div>
  
Linia 44: Linia 46:
  
 
W zbiorze uporządkowanym <math>\displaystyle (X,\leq)</math> element <math>\displaystyle y</math> nazywamy ''następnikiem''
 
W zbiorze uporządkowanym <math>\displaystyle (X,\leq)</math> element <math>\displaystyle y</math> nazywamy ''następnikiem''
elementu <math>\displaystyle x</math> jeśli <math>\displaystyle x \leq y</math>, <math>\displaystyle x\neq y</math> oraz każdy element silnie większy od <math>\displaystyle x</math>
+
elementu <math>\displaystyle x</math>, jeśli <math>\displaystyle x \leq y</math>, <math>\displaystyle x\neq y</math> oraz każdy element silnie większy od <math>\displaystyle x</math>
 
jest nie mniejszy od <math>\displaystyle y</math> (czyli <math>\displaystyle (x \leq z \wedge x \neq z) \Rightarrow y\leq z</math>).
 
jest nie mniejszy od <math>\displaystyle y</math> (czyli <math>\displaystyle (x \leq z \wedge x \neq z) \Rightarrow y\leq z</math>).
 
}}
 
}}
 
{{cwiczenie|2.4||
 
{{cwiczenie|2.4||
  
Podaj przykład zbioru uporządkowanego w którym żaden element nie ma następnika.
+
Podaj przykład zbioru uporządkowanego, w którym żaden element nie ma następnika.
  
 
}}
 
}}
Linia 56: Linia 58:
  
 
Zbiór liczb wymiernych uporządkowany naturalną relacją mniejszości ma tę
 
Zbiór liczb wymiernych uporządkowany naturalną relacją mniejszości ma tę
własność. Przypuśćmy, że istnieje liczba <math>\displaystyle x\in \mathbb{Q}</math> która ma następnik, oznaczymy go
+
własność. Przypuśćmy, że istnieje liczba <math>\displaystyle x\in \mathbb{Q}</math>, która ma następnik, oznaczymy go
przez <math>\displaystyle y</math>. Wtedy <math>\displaystyle x<y</math> wobec tego
+
przez <math>\displaystyle y</math>. Wtedy <math>\displaystyle x<y</math> wobec tego:
  
 
<center><math>\displaystyle x<\frac{x+y}{2} < y.
 
<center><math>\displaystyle x<\frac{x+y}{2} < y.
Linia 73: Linia 75:
 
{{dowod|||
 
{{dowod|||
  
Niech <math>\displaystyle (X,\leq)</math> będzie zbiorem dobrze uporządkowanym. Niech <math>\displaystyle x</math> będzie dowolnym elementem zbioru <math>\displaystyle X</math> który nie jest elementem największym. Zdefiniujmy zbiór <math>\displaystyle A</math> następująco
+
Niech <math>\displaystyle (X,\leq)</math> będzie zbiorem dobrze uporządkowanym. Niech <math>\displaystyle x</math> będzie dowolnym elementem zbioru <math>\displaystyle X</math>, który nie jest elementem największym. Zdefiniujmy zbiór <math>\displaystyle A</math> następująco:
  
 
<center><math>\displaystyle A= \{y\in X: x<y\}.
 
<center><math>\displaystyle A= \{y\in X: x<y\}.
 
</math></center>
 
</math></center>
  
Zbiór <math>\displaystyle A</math> jest niepusty gdyż <math>\displaystyle x</math> nie jest elementem największym. Ponieważ <math>\displaystyle X</math> jest
+
Zbiór <math>\displaystyle A</math> jest niepusty, gdyż <math>\displaystyle x</math> nie jest elementem największym. Ponieważ <math>\displaystyle X</math> jest
dobrze uporządkowany to w zbiorze <math>\displaystyle A</math> istnieje element najmniejszy, nazwijmy go <math>\displaystyle y</math>.
+
dobrze uporządkowany, to w zbiorze <math>\displaystyle A</math> istnieje element najmniejszy, nazwijmy go <math>\displaystyle y</math>.
Pokażemy, że jest następnikiem <math>\displaystyle x</math>. Ponieważ <math>\displaystyle y\in A</math> to <math>\displaystyle x<y</math>. Weźmy dowolny element
+
Pokażemy, że jest następnikiem <math>\displaystyle x</math>. Ponieważ <math>\displaystyle y\in A</math>, to <math>\displaystyle x<y</math>. Weźmy dowolny element
<math>\displaystyle z\in X</math> który jest silnie większy od <math>\displaystyle x</math>. Wtedy <math>\displaystyle z</math> musi należeć do <math>\displaystyle A</math>, a więc
+
<math>\displaystyle z\in X</math>, który jest silnie większy od <math>\displaystyle x</math>. Wtedy <math>\displaystyle z</math> musi należeć do <math>\displaystyle A</math>, a więc
ponieważ <math>\displaystyle y</math> jest najmniejszy w <math>\displaystyle A</math> to <math>\displaystyle y\leq z</math>. Wobec tego <math>\displaystyle y</math> jest następnikiem
+
ponieważ <math>\displaystyle y</math> jest najmniejszy w <math>\displaystyle A</math>, to <math>\displaystyle y\leq z</math>. Wobec tego <math>\displaystyle y</math> jest następnikiem
 
elementu <math>\displaystyle x</math>.
 
elementu <math>\displaystyle x</math>.
 
}}
 
}}
Linia 88: Linia 90:
 
{{definicja|2.6.||
 
{{definicja|2.6.||
  
Element zbioru dobrze uporządkowanego nazywamy ''elementem granicznym'' jeśli nie jest następnikiem, żadnego elementu.
+
Element zbioru dobrze uporządkowanego nazywamy ''elementem granicznym'', jeśli nie jest następnikiem, żadnego elementu.
 
}}
 
}}
 
{{cwiczenie|2.7||
 
{{cwiczenie|2.7||
Linia 101: Linia 103:
 
Przykładem takiego zbioru może być zbiór liczb całkowitych uporządkowany przez naturalną relację mniejszości. Wtedy dla dowolnego elementu <math>\displaystyle x\in \mathbb{Z}</math>, jego następnikiem jest <math>\displaystyle x+1</math>, a zbiór ten nie jest dobrze uporządkowany, gdyż na przykład cały zbiór <math>\displaystyle \mathbb{Z}</math> nie ma elementu najmniejszego.
 
Przykładem takiego zbioru może być zbiór liczb całkowitych uporządkowany przez naturalną relację mniejszości. Wtedy dla dowolnego elementu <math>\displaystyle x\in \mathbb{Z}</math>, jego następnikiem jest <math>\displaystyle x+1</math>, a zbiór ten nie jest dobrze uporządkowany, gdyż na przykład cały zbiór <math>\displaystyle \mathbb{Z}</math> nie ma elementu najmniejszego.
  
Można też skonstruować taki zbiór spełniający wymagania ćwiczenia, który ma element minimalny. Rozważmy zbiory <math>\displaystyle A= \mathbb{N}\times \{0\}</math> oraz <math>\displaystyle B= \mathbb{Z} \times \{1\}</math>. Zauważmy, że zbiory te są rozłączne. Zbiór <math>\displaystyle A</math> uporządkujemy relacją <math>\displaystyle \leq_A</math> zdefiniowaną następująco
+
Można też skonstruować taki zbiór spełniający wymagania ćwiczenia, który ma element minimalny. Rozważmy zbiory <math>\displaystyle A= \mathbb{N}\times \{0\}</math> oraz <math>\displaystyle B= \mathbb{Z} \times \{1\}</math>. Zauważmy, że zbiory te są rozłączne. Zbiór <math>\displaystyle A</math> uporządkujemy relacją <math>\displaystyle \leq_A</math> zdefiniowaną następująco:
 
+
<center><math>\displaystyle (x,0) \leq_A (y,0) \Leftrightarrow  x \leq_{\mathbb{N}} y,
<center><math>\displaystyle (x,0) \leq_A (y,0) \Leftrightarrow  x \leq_{\mathbb{N}} y
 
 
</math></center>
 
</math></center>
  
gdzie <math>\displaystyle \leq_\mathbb{N}</math> jest naturalną relacją mniejszości na liczbach naturalnych. Analogicznie dla zbioru <math>\displaystyle B</math> zdefiniujemy relację <math>\displaystyle \leq_B</math>
+
gdzie <math>\displaystyle \leq_\mathbb{N}</math> jest naturalną relacją mniejszości na liczbach naturalnych. Analogicznie dla zbioru <math>\displaystyle B</math> zdefiniujemy relację <math>\displaystyle \leq_B</math>:
  
<center><math>\displaystyle (x,1) \leq_B (y,1) \Leftrightarrow  x \leq_{\mathbb{Z}} y
+
<center><math>\displaystyle (x,1) \leq_B (y,1) \Leftrightarrow  x \leq_{\mathbb{Z}} y,
 
</math></center>
 
</math></center>
  
gdzie <math>\displaystyle \leq_\mathbb{Z}</math> jest naturalną relacją mniejszości na liczbach całkowitych. Rozważmy teraz zbiór <math>\displaystyle C=A\cup B</math> który uporządkujemy relacją <math>\displaystyle \leq_A \cup \leq_B \cup A \times B</math>. Innymi słowy w zbiorze <math>\displaystyle C</math> porządek pomiędzy elementami zbioru <math>\displaystyle A</math> jest zgodny z <math>\displaystyle \leq_A</math>, porządek pomiędzy elementami zbioru <math>\displaystyle B</math> jest zgodny z <math>\displaystyle \leq_B</math> oraz każdy element zbioru <math>\displaystyle A</math> jest mniejszy od każdego elementu zbioru <math>\displaystyle B</math>. W zbiorze <math>\displaystyle C</math> każdy element ma następnik, gdyż każdy element zbioru <math>\displaystyle A</math> ma następnik w <math>\displaystyle A</math> i każdy element zbioru <math>\displaystyle B</math> ma następnik w <math>\displaystyle B</math>. Zbiór <math>\displaystyle C</math> nie jest dobrze uporządkowany, gdyż <math>\displaystyle B\subset C</math> nie ma elementu najmniejszego.
+
gdzie <math>\displaystyle \leq_\mathbb{Z}</math> jest naturalną relacją mniejszości na liczbach całkowitych. Rozważmy teraz zbiór <math>\displaystyle C=A\cup B</math> który uporządkujemy relacją <math>\displaystyle \leq_A \cup \leq_B \cup A \times B</math>. Innymi słowy, w zbiorze <math>\displaystyle C</math> porządek pomiędzy elementami zbioru <math>\displaystyle A</math> jest zgodny z <math>\displaystyle \leq_A</math>, porządek pomiędzy elementami zbioru <math>\displaystyle B</math> jest zgodny z <math>\displaystyle \leq_B</math> oraz każdy element zbioru <math>\displaystyle A</math> jest mniejszy od każdego elementu zbioru <math>\displaystyle B</math>. W zbiorze <math>\displaystyle C</math> każdy element ma następnik, gdyż każdy element zbioru <math>\displaystyle A</math> ma następnik w <math>\displaystyle A</math> i każdy element zbioru <math>\displaystyle B</math> ma następnik w <math>\displaystyle B</math>. Zbiór <math>\displaystyle C</math> nie jest dobrze uporządkowany, gdyż <math>\displaystyle B\subset C</math> nie ma elementu najmniejszego.
 
</div></div>
 
</div></div>
  
Linia 123: Linia 124:
 
</math></center>
 
</math></center>
 
}}
 
}}
Czyli <math>\displaystyle A</math> jest przedziałem początkowym jeśli wraz z każdym swoim elementem zawiera także wszystkie elementy zbioru <math>\displaystyle X</math> które są od niego mniejsze. Będziemy używać następujących oznaczeń, dla <math>\displaystyle x_0\in X</math>
+
Czyli <math>\displaystyle A</math> jest przedziałem początkowym, jeśli wraz z każdym swoim elementem zawiera także wszystkie elementy zbioru <math>\displaystyle X</math>, które są od niego mniejsze. Będziemy używać następujących oznaczeń, dla <math>\displaystyle x_0\in X</math> niech:
 
 
 
<center><math>\displaystyle O(x_0)=\{x\in X: x < x_0\}
 
<center><math>\displaystyle O(x_0)=\{x\in X: x < x_0\}
 
</math></center>
 
</math></center>
  
oraz
+
oraz:
  
 
<center><math>\displaystyle \overline{O(x_0)}=\{x\in X: x \leq x_0\}.
 
<center><math>\displaystyle \overline{O(x_0)}=\{x\in X: x \leq x_0\}.
Linia 138: Linia 138:
  
 
Jeśli <math>\displaystyle (X,\leq)</math> będzie zbiorem dobrze uporządkowanym. Wtedy każdy jego przedział
 
Jeśli <math>\displaystyle (X,\leq)</math> będzie zbiorem dobrze uporządkowanym. Wtedy każdy jego przedział
początkowy, różny od <math>\displaystyle X</math>, jest postaci <math>\displaystyle \{x\in X: x < x_0\}</math> dla pewnego elementu
+
początkowy, różny od <math>\displaystyle X</math>, jest postaci <math>\displaystyle \{x\in X: x < x_0\}</math>, dla pewnego elementu
 
<math>\displaystyle x_0\in X</math> (czyli każdy przedział początkowy jest postaci <math>\displaystyle O(x_0)</math>).
 
<math>\displaystyle x_0\in X</math> (czyli każdy przedział początkowy jest postaci <math>\displaystyle O(x_0)</math>).
 
}}</span>
 
}}</span>
Linia 145: Linia 145:
  
 
Niech <math>\displaystyle A</math> będzie przedziałem początkowym <math>\displaystyle X</math> różnym od <math>\displaystyle X</math>. Wtedy zbiór
 
Niech <math>\displaystyle A</math> będzie przedziałem początkowym <math>\displaystyle X</math> różnym od <math>\displaystyle X</math>. Wtedy zbiór
<math>\displaystyle X\setminus A</math> jest niepusty i jest podzbiorem <math>\displaystyle X</math> więc posiada element najmniejszy,
+
<math>\displaystyle X\setminus A</math> jest niepusty i jest podzbiorem <math>\displaystyle X</math>, więc posiada element najmniejszy,
 
oznaczmy go przez <math>\displaystyle x_0</math>. Pokażemy, że <math>\displaystyle A=O(x_0)</math>. Przypuśćmy, że istnieje
 
oznaczmy go przez <math>\displaystyle x_0</math>. Pokażemy, że <math>\displaystyle A=O(x_0)</math>. Przypuśćmy, że istnieje
 
element <math>\displaystyle y\in X</math> taki, że <math>\displaystyle y\in A</math> oraz  <math>\displaystyle x_0\leq y</math>. Wtedy ponieważ <math>\displaystyle A</math> jest
 
element <math>\displaystyle y\in X</math> taki, że <math>\displaystyle y\in A</math> oraz  <math>\displaystyle x_0\leq y</math>. Wtedy ponieważ <math>\displaystyle A</math> jest
przedziałem początkowym to <math>\displaystyle x_0</math> również musiałby być elementem <math>\displaystyle A</math> co jest sprzeczne
+
przedziałem początkowym, to <math>\displaystyle x_0</math> również musiałby być elementem <math>\displaystyle A</math>, co jest sprzeczne
z tym że <math>\displaystyle x_0\in X\setminus A</math>. Wobec tego wszystkie elementy <math>\displaystyle A</math> są silnie mniejsze
+
z tym, że <math>\displaystyle x_0\in X\setminus A</math>. Wobec tego wszystkie elementy <math>\displaystyle A</math> są silnie mniejsze
 
od <math>\displaystyle x_0</math>. Przypuśćmy teraz, że istnieje element <math>\displaystyle y\in X</math>, który jest silnie mniejszy
 
od <math>\displaystyle x_0</math>. Przypuśćmy teraz, że istnieje element <math>\displaystyle y\in X</math>, który jest silnie mniejszy
 
od <math>\displaystyle x_0</math> i nie należy do <math>\displaystyle A</math>. Wtedy <math>\displaystyle y\in X \setminus A</math> i ponieważ jest silnie
 
od <math>\displaystyle x_0</math> i nie należy do <math>\displaystyle A</math>. Wtedy <math>\displaystyle y\in X \setminus A</math> i ponieważ jest silnie
mniejszy od <math>\displaystyle x_0</math> to dostajemy sprzeczność z faktem że <math>\displaystyle x_0</math> jest najmniejszy w tym
+
mniejszy od <math>\displaystyle x_0</math>, to dostajemy sprzeczność z faktem, że <math>\displaystyle x_0</math> jest najmniejszy w tym
 
zbiorze. Wobec tego zbiór <math>\displaystyle A</math> składa się dokładnie z elementów silnie mniejszych od
 
zbiorze. Wobec tego zbiór <math>\displaystyle A</math> składa się dokładnie z elementów silnie mniejszych od
<math>\displaystyle x_0</math>, co oznacza że <math>\displaystyle A=O(x_0)</math>.
+
<math>\displaystyle x_0</math>, co oznacza, że <math>\displaystyle A=O(x_0)</math>.
 
}}
 
}}
  
Linia 160: Linia 160:
  
 
Podaj przykład zbioru dobrze uporządkowanego <math>\displaystyle X</math>, w którym istnieje przedział
 
Podaj przykład zbioru dobrze uporządkowanego <math>\displaystyle X</math>, w którym istnieje przedział
początkowy różny od <math>\displaystyle X</math> który nie jest postaci <math>\displaystyle \{x\in X: x \leq x_0\}</math> (uwaga!
+
początkowy różny od <math>\displaystyle X</math>, który nie jest postaci <math>\displaystyle \{x\in X: x \leq x_0\}</math> (uwaga!
 
nierówność jest słaba).
 
nierówność jest słaba).
 
}}
 
}}
Linia 169: Linia 169:
 
<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">   
  
Rozważmy zbiór liczb naturalnych <math>\displaystyle \mathbb{N}</math> oraz jeden element który nie należy do <math>\displaystyle \mathbb{N}</math>. Oznaczymy go przez <math>\displaystyle \top</math> (w roli <math>\displaystyle \top</math> może występować na przykład <math>\displaystyle \mathbb{N}</math> ponieważ wiemy, że żaden zbiór nie jest swoim własnych elementem). Zbiór <math>\displaystyle \mathbb{N} \cup \{\top\}</math> oznaczymy przez <math>\displaystyle \mathbb{N}'</math> i uporządkujemy relacją <math>\displaystyle \leq_\mathbb{N} \cup \mathbb{N} \times\{\top\}</math>, gdzie <math>\displaystyle \leq_\mathbb{N}</math> jest naturalnym porządkiem pomiędzy liczbami z <math>\displaystyle \mathbb{N}</math>. Relację będziemy oznaczać przez <math>\displaystyle \leq</math> . Tak zdefiniowana relacja zachowuje porządek <math>\displaystyle \leq_\mathbb{N}</math> pomiędzy liczbami naturalnymi, oraz określa element <math>\displaystyle \top</math> jako element największy w <math>\displaystyle \mathbb{N}'</math>. Łatwo sprawdzić, że zbiór ten jest dobrze uporządkowany. Pokażemy, że zbiór <math>\displaystyle \mathbb{N}</math> jest odcinkiem początkowym w <math>\displaystyle \mathbb{N}'</math> który nie jest postaci <math>\displaystyle \{x\in X: x \leq x_0\}</math>. Zbiór <math>\displaystyle \mathbb{N}</math> jest odcinkiem początkowym gdyż <math>\displaystyle \top </math> jest elementem największym w <math>\displaystyle \mathbb{N}'</math>. Istnieje elementu <math>\displaystyle x_0 \in \mathbb{N}'</math> takiego, że <math>\displaystyle \mathbb{N}=\{x\in X: x \leq x_0\}</math> oznaczałoby, że istnieje największa liczba naturalna, gdyż <math>\displaystyle x_0</math> musiałby należeć do <math>\displaystyle \mathbb{N}</math>. Wobec tego taki element nie istnieje.
+
Rozważmy zbiór liczb naturalnych <math>\displaystyle \mathbb{N}</math> oraz jeden element, który nie należy do <math>\displaystyle \mathbb{N}</math>. Oznaczymy go przez <math>\displaystyle \top</math> (w roli <math>\displaystyle \top</math> może występować na przykład <math>\displaystyle \mathbb{N}</math>, ponieważ wiemy, że żaden zbiór nie jest swoim własnych elementem). Zbiór <math>\displaystyle \mathbb{N} \cup \{\top\}</math> oznaczymy przez <math>\displaystyle \mathbb{N}'</math> i uporządkujemy relacją <math>\displaystyle \leq_\mathbb{N} \cup \mathbb{N} \times\{\top\}</math>, gdzie <math>\displaystyle \leq_\mathbb{N}</math> jest naturalnym porządkiem pomiędzy liczbami z <math>\displaystyle \mathbb{N}</math>. Relację będziemy oznaczać przez <math>\displaystyle \leq</math> . Tak zdefiniowana relacja zachowuje porządek <math>\displaystyle \leq_\mathbb{N}</math> pomiędzy liczbami naturalnymi oraz określa element <math>\displaystyle \top</math> jako element największy w <math>\displaystyle \mathbb{N}'</math>. Łatwo sprawdzić, że zbiór ten jest dobrze uporządkowany. Pokażemy, że zbiór <math>\displaystyle \mathbb{N}</math> jest odcinkiem początkowym w <math>\displaystyle \mathbb{N}'</math>, który nie jest postaci <math>\displaystyle \{x\in X: x \leq x_0\}</math>. Zbiór <math>\displaystyle \mathbb{N}</math> jest odcinkiem początkowym, gdyż <math>\displaystyle \top </math> jest elementem największym w <math>\displaystyle \mathbb{N}'</math>. Istnieje elementu <math>\displaystyle x_0 \in \mathbb{N}'</math> takiego, że <math>\displaystyle \mathbb{N}=\{x\in X: x \leq x_0\}</math> oznaczałoby, istnieje największa liczba naturalna, gdyż <math>\displaystyle x_0</math> musiałby należeć do <math>\displaystyle \mathbb{N}</math>. Wobec tego taki element nie istnieje.
 
</div></div>
 
</div></div>
  
 
{{cwiczenie|2.11||
 
{{cwiczenie|2.11||
  
Udowodnij, że dla każdego dobrego porządku <math>\displaystyle (X,\leq)</math> istnieje funkcja, która niepustym podzbiorom <math>\displaystyle X</math> przypisuje ich element najmniejszy. Funkcje nazywamy <math>\displaystyle \min: \mathcal{P}(X) \setminus \left\{\emptyset\right\} \rightarrow X</math>.
+
Udowodnij, że dla każdego dobrego porządku <math>\displaystyle (X,\leq)</math> istnieje funkcja, która niepustym podzbiorom <math>\displaystyle X</math> przypisuje ich element najmniejszy. Funkcje nazywamy <math>\displaystyle \min: \mathcal{P}(X) \setminus \left\{\emptyset\right\} \rightarrow X</math>.
  
 
}}
 
}}
Linia 180: Linia 180:
 
<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">   
  
Zdefiniujemy zbiór <math>\displaystyle \min</math>  następująco
+
Zdefiniujemy zbiór <math>\displaystyle \min</math>  następująco:
  
 
<center><math>\displaystyle \min = \{z\in \mathcal{P}(\mathcal{P}(\mathcal{P}(X)\cup X)): \exists_{A\in \mathcal{P}(X)}\exists_{a\in X} [ z=(A,a)
 
<center><math>\displaystyle \min = \{z\in \mathcal{P}(\mathcal{P}(\mathcal{P}(X)\cup X)): \exists_{A\in \mathcal{P}(X)}\exists_{a\in X} [ z=(A,a)
Linia 186: Linia 186:
 
</math></center>
 
</math></center>
  
Istnienie zbioru <math>\displaystyle \min</math> wynika z aksjomatu wyróżniania. Jest to funkcja częściowa ponieważ istnieje co najwyżej jeden element najmniejszy w każdym podzbiorze <math>\displaystyle A</math>. <math>\displaystyle \min</math> jest funkcją totalną ponieważ <math>\displaystyle A</math> jest dobrze uporządkowany, a więc w każdym podzbiorze istnieje element najmniejszy.
+
Istnienie zbioru <math>\displaystyle \min</math> wynika z aksjomatu wyróżniania. Jest to funkcja częściowa, ponieważ istnieje co najwyżej jeden element najmniejszy w każdym podzbiorze <math>\displaystyle A</math>. <math>\displaystyle \min</math> jest funkcją totalną, ponieważ <math>\displaystyle A</math> jest dobrze uporządkowany, a więc w każdym podzbiorze istnieje element najmniejszy.
 
</div></div>
 
</div></div>
  
Linia 199: Linia 199:
  
 
{{dowod|||
 
{{dowod|||
Zdefiniujmy funkcję <math>\displaystyle f:X \rightarrow \mathcal{R}</math> tak aby <math>\displaystyle f(x)=O(x)</math>. Pokażemy, że ta
+
Zdefiniujmy funkcję <math>\displaystyle f:X \rightarrow \mathcal{R}</math>, tak aby <math>\displaystyle f(x)=O(x)</math>. Pokażemy, że ta
funkcja ustala podobieństwo. Pokażemy po kolei, że jest suriekcją , iniekcją oraz, że
+
funkcja ustala podobieństwo. Pokażemy po kolei, że jest suriekcją , iniekcją oraz że
jest monotoniczna.
+
jest monotoniczna:
# Suriektywność funkcji <math>\displaystyle f</math> wynika z twierdzenia 2.9 (patrz [[#twierdzenie_2_9|twierdzenie 2.9]]).
+
# Suriektywność funkcji <math>\displaystyle f</math> wynika z Twierdzenia 2.9 (patrz [[#twierdzenie_2_9|Twierdzenie 2.9]]).
# Weźmy dowolne <math>\displaystyle x,y \in X</math> takie, że <math>\displaystyle x <y</math>. Wtedy z definicji <math>\displaystyle  x \in O(y)</math>, oraz <math>\displaystyle x\notin O(x)</math>, w więc <math>\displaystyle f(x)\neq f(y)</math>.
+
# Weźmy dowolne <math>\displaystyle x,y \in X</math> takie, że <math>\displaystyle x <y</math>. Wtedy z definicji <math>\displaystyle  x \in O(y)</math> oraz <math>\displaystyle x\notin O(x)</math>, a więc <math>\displaystyle f(x)\neq f(y)</math>.
 
# Weźmy dowolne <math>\displaystyle x,y \in X</math> takie, że <math>\displaystyle x <y</math>. Weźmy dowolny <math>\displaystyle z\in f(x)</math>.
 
# Weźmy dowolne <math>\displaystyle x,y \in X</math> takie, że <math>\displaystyle x <y</math>. Weźmy dowolny <math>\displaystyle z\in f(x)</math>.
Oznacza to, że <math>\displaystyle z\in O(x)</math> a więc <math>\displaystyle z<x</math>. Wtedy również <math>\displaystyle z<y</math> a więc <math>\displaystyle z\in O(y)=f(y)</math>.
+
Oznacza to, że <math>\displaystyle z\in O(x)</math>, a więc <math>\displaystyle z<x</math>. Wtedy również <math>\displaystyle z<y</math>, a więc <math>\displaystyle z\in O(y)=f(y)</math>.
Wobec dowolności wyboru <math>\displaystyle z</math> otrzymujemy <math>\displaystyle f(x) \subset f(z)</math> a więc funkcja <math>\displaystyle f</math> jest monotoniczna.
+
Wobec dowolności wyboru <math>\displaystyle z</math> otrzymujemy <math>\displaystyle f(x) \subset f(z)</math>, a więc funkcja <math>\displaystyle f</math> jest monotoniczna.
  
 
}}
 
}}
Linia 215: Linia 215:
 
{{cwiczenie|2.13||
 
{{cwiczenie|2.13||
  
Jeśli porządki <math>\displaystyle (X,\leq_X)</math> oraz <math>\displaystyle (Y,\leq_Y)</math> są podobne, to <math>\displaystyle (X,\leq_X)</math> jest dobry wtedy i tylko wtedy gdy <math>\displaystyle (Y,\leq_Y)</math> jest dobry.
+
Jeśli porządki <math>\displaystyle (X,\leq_X)</math> oraz <math>\displaystyle (Y,\leq_Y)</math> są podobne, to <math>\displaystyle (X,\leq_X)</math> jest dobry wtedy i tylko wtedy, gdy <math>\displaystyle (Y,\leq_Y)</math> jest dobry.
 
}}
 
}}
  
 
<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">   
  
Ze względu na symetrię wykażemy implikację tylko w jedną stronę. Niech <math>\displaystyle f:X\rightarrow Y</math> będzie monotoniczną bijekcją. Przypuśćmy, że <math>\displaystyle (X,\leq_X)</math>  jest dobry. Weźmy dowolny niepusty podzbiór <math>\displaystyle A\subset Y</math>. Pokażemy, że jego najmniejszy element to <math>\displaystyle a= f(\min(\vec{f}^{-1}(A)))</math>. Z własności przeciwobrazu otrzymujemy, że <math>\displaystyle a\in A</math>. Weźmy dowolny element <math>\displaystyle b\in A</math>. Ponieważ <math>\displaystyle f</math> jest bijekcją to istnieje element <math>\displaystyle c\in X</math> taki, że <math>\displaystyle f(c)=b</math>. Oznacza to również, że <math>\displaystyle c\in \vec{f}^{-1}(A)</math> a wtedy
+
Ze względu na symetrię wykażemy implikację tylko w jedną stronę. Niech <math>\displaystyle f:X\rightarrow Y</math> będzie monotoniczną bijekcją. Przypuśćmy, że <math>\displaystyle (X,\leq_X)</math>  jest dobry. Weźmy dowolny niepusty podzbiór <math>\displaystyle A\subset Y</math>. Pokażemy, że jego najmniejszy element to <math>\displaystyle a= f(\min(\vec{f}^{-1}(A)))</math>. Z własności przeciwobrazu otrzymujemy, że <math>\displaystyle a\in A</math>. Weźmy dowolny element <math>\displaystyle b\in A</math>. Ponieważ <math>\displaystyle f</math> jest bijekcją, to istnieje element <math>\displaystyle c\in X</math> taki, że <math>\displaystyle f(c)=b</math>. Oznacza to również, że <math>\displaystyle c\in \vec{f}^{-1}(A)</math>, a wtedy
  
<center><math>\displaystyle \min(\vec{f}^{-1}(A)) \leq_X c
+
<center><math>\displaystyle \min(\vec{f}^{-1}(A)) \leq_X c,
 
</math></center>
 
</math></center>
  
wobec tego z monotoniczności <math>\displaystyle f</math> otrzymujemy
+
wobec tego z monotoniczności <math>\displaystyle f</math> otrzymujemy:
  
<center><math>\displaystyle a=f(  \min(\vec{f}^{-1}(A))) \leq_Y  f(c)=b
+
<center><math>\displaystyle a=f(  \min(\vec{f}^{-1}(A))) \leq_Y  f(c)=b,
 
</math></center>
 
</math></center>
  
Linia 235: Linia 235:
 
{{cwiczenie|2.14||
 
{{cwiczenie|2.14||
  
Dla zbiorów  uporządkowanych <math>\displaystyle (X,\leq_X)</math>, <math>\displaystyle (Y,\leq_Y)</math> porządek leksykograficzny <math>\displaystyle \prec \subset X\times Y</math> definiujemy tak, że
+
Dla zbiorów  uporządkowanych <math>\displaystyle (X,\leq_X)</math>, <math>\displaystyle (Y,\leq_Y)</math> porządek leksykograficzny <math>\displaystyle \prec \subset X\times Y</math> definiujemy tak, że:
  
<center><math>\displaystyle (a,b) \prec (c,d) \Leftrightarrow (a\leq_X c) \vee (a=c \wedge b\leq_Y c)
+
<center><math>\displaystyle (a,b) \prec (c,d) \Leftrightarrow (a\leq_X c) \vee (a=c \wedge b\leq_Y c),
 
</math></center>
 
</math></center>
  
Dla zbiorów <math>\displaystyle \{0,1\},\mathbb{N}, \mathbb{Z}, \mathbb{R}</math> uporządkowanych w naturalny sposób, sprawdź
+
Dla zbiorów <math>\displaystyle \{0,1\},\mathbb{N}, \mathbb{Z}, \mathbb{R}</math> uporządkowanych w naturalny sposób, sprawdź,
czy następujące ich produkty są dobrze uporządkowane.
+
czy następujące ich produkty są dobrze uporządkowane:
# <math>\displaystyle \{0,1\} \times \mathbb{N}</math>
+
# <math>\displaystyle \{0,1\} \times \mathbb{N}</math>,
# <math>\displaystyle \mathbb{N} \times \mathbb{N}</math>
+
# <math>\displaystyle \mathbb{N} \times \mathbb{N}</math>,
# <math>\displaystyle \mathbb{Z} \times \mathbb{N}</math>
+
# <math>\displaystyle \mathbb{Z} \times \mathbb{N}</math>,
# <math>\displaystyle \mathbb{N} \times \mathbb{Z}</math>
+
# <math>\displaystyle \mathbb{N} \times \mathbb{Z}</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">   
1. Tak, porządek leksykograficzny na zbiorze <math>\displaystyle \{0,1\} \times \mathbb{N}</math> jest dobrym porządkiem. Rozważmy dowolny niepusty podzbiór <math>\displaystyle A \subset (\{0,1\} \times \mathbb{N})</math>, pokażemy że istnieje w nim element najmniejszy. Zbiór <math>\displaystyle A</math> możemy podzielić na dwa podzbiory <math>\displaystyle A_0,A_1</math> tak, że <math>\displaystyle A_0= A \cap (\{0\}\times \mathbb{N})</math> otaz <math>\displaystyle A_1= A \cap (\{1\} \times \mathbb{N})</math>. Wtedy zbiory <math>\displaystyle A_0,A_1</math> są rozłączne oraz <math>\displaystyle A_0 \cup A_1= A</math>. Ponadto każdy element ze zbioru <math>\displaystyle A_0</math> jest mniejszy od każdego elementu, ze zbioru <math>\displaystyle A_1</math>.
+
1. Tak, porządek leksykograficzny na zbiorze <math>\displaystyle \{0,1\} \times \mathbb{N}</math> jest dobrym porządkiem. Rozważmy dowolny niepusty podzbiór <math>\displaystyle A \subset (\{0,1\} \times \mathbb{N})</math>, pokażemy, że istnieje w nim element najmniejszy. Zbiór <math>\displaystyle A</math> możemy podzielić na dwa podzbiory <math>\displaystyle A_0,A_1</math> tak, że <math>\displaystyle A_0= A \cap (\{0\}\times \mathbb{N})</math> oraz <math>\displaystyle A_1= A \cap (\{1\} \times \mathbb{N})</math>. Wtedy zbiory <math>\displaystyle A_0,A_1</math> są rozłączne oraz <math>\displaystyle A_0 \cup A_1= A</math>. Ponadto każdy element ze zbioru <math>\displaystyle A_0</math> jest mniejszy od każdego elementu ze zbioru <math>\displaystyle A_1</math>.
  
Przypuśćmy, że zbiór <math>\displaystyle A_0</math> jest niepusty. Ponieważ <math>\displaystyle (\{0\}\times \mathbb{N},\prec)</math> jest podobny do <math>\displaystyle (\mathbb{N},\leq)</math> to <math>\displaystyle (\{0\}\times \mathbb{N},\prec)</math> jest dobrym porządkiem, a więc skoro <math>\displaystyle A_0 \subset (\{0\}\times \mathbb{N},\prec)</math> to istnieje w <math>\displaystyle A_0</math> element najmniejszy <math>\displaystyle a_0</math>. Ponieważ <math>\displaystyle a_0</math> jest mniejszy od każdego elementu <math>\displaystyle A_1</math> to jest elementem najmniejszym w <math>\displaystyle A</math>.
+
Przypuśćmy, że zbiór <math>\displaystyle A_0</math> jest niepusty. Ponieważ <math>\displaystyle (\{0\}\times \mathbb{N},\prec)</math> jest podobny do <math>\displaystyle (\mathbb{N},\leq)</math>, to <math>\displaystyle (\{0\}\times \mathbb{N},\prec)</math> jest dobrym porządkiem, a więc skoro <math>\displaystyle A_0 \subset (\{0\}\times \mathbb{N},\prec)</math>, to istnieje w <math>\displaystyle A_0</math> element najmniejszy <math>\displaystyle a_0</math>. Ponieważ <math>\displaystyle a_0</math> jest mniejszy od każdego elementu <math>\displaystyle A_1</math>, to jest elementem najmniejszym w <math>\displaystyle A</math>.
  
Jeśli zbiór <math>\displaystyle A_0</math> jest pusty, to analogiczne rozumowanie dla zbioru <math>\displaystyle A_1</math> pokaże, że w <math>\displaystyle A_1</math> jest element najmniejszy. Ponieważ w takim przypadku <math>\displaystyle A_1=A</math> to ten element jest najmniejszy w <math>\displaystyle A</math>.
+
Jeśli zbiór <math>\displaystyle A_0</math> jest pusty, to analogiczne rozumowanie dla zbioru <math>\displaystyle A_1</math> pokaże, że w <math>\displaystyle A_1</math> jest element najmniejszy. Ponieważ w takim przypadku <math>\displaystyle A_1=A</math>, to ten element jest najmniejszy w <math>\displaystyle A</math>.
  
2. Tak, porządek leksykograficzny na zbiorze <math>\displaystyle \mathbb{N} \times \mathbb{N}</math> jest dobrym porządkiem. Pokażemy, że jego każdy niepusty podzbiór ma element najmniejszy. Niech <math>\displaystyle A\subset \mathbb{N} \times \mathbb{N}</math> będzie niepusty. Niech <math>\displaystyle B= A_L</math>, czyli <math>\displaystyle B</math> jest zbiorem liczb naturalnych które występują na pierwszej współrzędnej jakiejś pary ze zbioru <math>\displaystyle A</math>. Ponieważ <math>\displaystyle B\subset \mathbb{N}</math> to w <math>\displaystyle B</math> istnieje element najmniejszy w sensie naturalnego porządku w <math>\displaystyle \mathbb{N}</math>, oznaczmy go przez <math>\displaystyle b</math>. Rozważmy teraz zbiór <math>\displaystyle A_b=A \cap (\{b\} \times \mathbb{N})</math>, zbiór ten jest niepusty, ze względu na wybór elementu <math>\displaystyle b</math>. Porządek <math>\displaystyle (A_{\{b\} \times \mathbb{N}},\prec)</math> jest podobny do <math>\displaystyle (\mathbb{N},\leq)</math> wobec tego istnieje w nim element najmniejszy, oznaczmy go przez <math>\displaystyle a</math>. Pokażemy że <math>\displaystyle a</math> jest najmniejszy w <math>\displaystyle a</math>. Weźmy dowolny element <math>\displaystyle x\in A</math>. Jeśli pierwsza współrzędna <math>\displaystyle x</math> jest różna od <math>\displaystyle b</math> to z konstrukcji <math>\displaystyle b</math> wynika, że jest większa od <math>\displaystyle b</math> wobec tego z definicji porządku <math>\displaystyle \prec</math> otrzymujemy <math>\displaystyle a\prec x</math>. Jeśli pierwsza współrzędna <math>\displaystyle x</math> jest równa <math>\displaystyle b</math> to <math>\displaystyle x\in A_b</math> i z konstrukcji <math>\displaystyle a</math> wynika, że <math>\displaystyle a\prec x</math>.
+
2. Tak, porządek leksykograficzny na zbiorze <math>\displaystyle \mathbb{N} \times \mathbb{N}</math> jest dobrym porządkiem. Pokażemy, że jego każdy niepusty podzbiór ma element najmniejszy. Niech <math>\displaystyle A\subset \mathbb{N} \times \mathbb{N}</math> będzie niepusty. Niech <math>\displaystyle B= A_L</math>, czyli <math>\displaystyle B</math> jest zbiorem liczb naturalnych które występują na pierwszej współrzędnej jakiejś pary ze zbioru <math>\displaystyle A</math>. Ponieważ <math>\displaystyle B\subset \mathbb{N}</math> to w <math>\displaystyle B</math> istnieje element najmniejszy w sensie naturalnego porządku w <math>\displaystyle \mathbb{N}</math>, oznaczmy go przez <math>\displaystyle b</math>. Rozważmy teraz zbiór <math>\displaystyle A_b=A \cap (\{b\} \times \mathbb{N})</math>. Zbiór ten jest niepusty, ze względu na wybór elementu <math>\displaystyle b</math>. Porządek <math>\displaystyle (A_{\{b\} \times \mathbb{N}},\prec)</math> jest podobny do <math>\displaystyle (\mathbb{N},\leq)</math>, wobec tego istnieje w nim element najmniejszy, oznaczmy go przez <math>\displaystyle a</math>. Pokażemy, że <math>\displaystyle a</math> jest najmniejszy w <math>\displaystyle a</math>. Weźmy dowolny element <math>\displaystyle x\in A</math>. Jeśli pierwsza współrzędna <math>\displaystyle x</math> jest różna od <math>\displaystyle b</math>, to z konstrukcji <math>\displaystyle b</math> wynika, że jest większa od <math>\displaystyle b</math> wobec tego z definicji porządku <math>\displaystyle \prec</math> otrzymujemy <math>\displaystyle a\prec x</math>. Jeśli pierwsza współrzędna <math>\displaystyle x</math> jest równa <math>\displaystyle b</math>, to <math>\displaystyle x\in A_b</math> i z konstrukcji <math>\displaystyle a</math> wynika, że <math>\displaystyle a\prec x</math>.
  
 
3. Nie jest dobry. Zbiór <math>\displaystyle \mathbb{Z} \times \{0\}</math> nie ma elementu najmniejszego. Gdyby miał, to musiałby być postaci <math>\displaystyle (x,0)</math>, a wtedy <math>\displaystyle x</math> byłby najmniejszym elementem <math>\displaystyle \mathbb{Z}</math>, a taki nie istnieje.
 
3. Nie jest dobry. Zbiór <math>\displaystyle \mathbb{Z} \times \{0\}</math> nie ma elementu najmniejszego. Gdyby miał, to musiałby być postaci <math>\displaystyle (x,0)</math>, a wtedy <math>\displaystyle x</math> byłby najmniejszym elementem <math>\displaystyle \mathbb{Z}</math>, a taki nie istnieje.
Linia 266: Linia 266:
 
{{cwiczenie|2.15||
 
{{cwiczenie|2.15||
  
Rozważmy dwa porządki <math>\displaystyle \ll,\prec</math> na zbiorze <math>\displaystyle \mathbb{N} \times \mathbb{N}</math> zdefiniowane w następujący sposób
+
Rozważmy dwa porządki <math>\displaystyle \ll,\prec</math> na zbiorze <math>\displaystyle \mathbb{N} \times \mathbb{N}</math> zdefiniowane w następujący sposób:
  
 
<center><math>\displaystyle (a,b)\prec(c,d) \Leftrightarrow (a< c) \vee (a=c \wedge b\leq d)
 
<center><math>\displaystyle (a,b)\prec(c,d) \Leftrightarrow (a< c) \vee (a=c \wedge b\leq d)
Linia 279: Linia 279:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </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">Wskazówka </span><div class="mw-collapsible-content" style="display:none">   
  
Tylko jeden z nich jest dobry  
+
Tylko jeden z nich jest dobry.
 
</div></div>
 
</div></div>
  
Linia 286: Linia 286:
 
W poprzednim ćwiczeniu pokazaliśmy, że porządek <math>\displaystyle \prec</math> jest dobry. Pokażemy teraz, że <math>\displaystyle \ll</math> nie jest. Będzie to oznaczało, że nie są podobne, gdyż własność bycia dobrym porządkiem jest przenoszona przez podobieństwo.
 
W poprzednim ćwiczeniu pokazaliśmy, że porządek <math>\displaystyle \prec</math> jest dobry. Pokażemy teraz, że <math>\displaystyle \ll</math> nie jest. Będzie to oznaczało, że nie są podobne, gdyż własność bycia dobrym porządkiem jest przenoszona przez podobieństwo.
  
Rozważmy zbiór <math>\displaystyle \{1\} \times \mathbb{N}</math>. Przypuśćmy, że istnieje w nim element minimalny <math>\displaystyle (1,a)</math>. Z definicji porządku <math>\displaystyle \ll</math> wynika, że <math>\displaystyle (1,a+1)\ll (1,a)</math>. Ponieważ <math>\displaystyle (1,a+1)\in \{1\} \times \mathbb{N}</math> to <math>\displaystyle (1,a)</math> nie może być elementem minimalnym w tym zbiorze. Wobec tego porządek <math>\displaystyle \ll</math> nie jest dobry.
+
Rozważmy zbiór <math>\displaystyle \{1\} \times \mathbb{N}</math>. Przypuśćmy, że istnieje w nim element minimalny <math>\displaystyle (1,a)</math>. Z definicji porządku <math>\displaystyle \ll</math> wynika, że <math>\displaystyle (1,a+1)\ll (1,a)</math>. Ponieważ <math>\displaystyle (1,a+1)\in \{1\} \times \mathbb{N}</math>, to <math>\displaystyle (1,a)</math> nie może być elementem minimalnym w tym zbiorze. Wobec tego porządek <math>\displaystyle \ll</math> nie jest dobry.
 
</div></div>
 
</div></div>
  
 
{{cwiczenie|2.16||
 
{{cwiczenie|2.16||
  
Czy porządek leksykograficzny na zbiorze <math>\displaystyle \{0,1\}^*</math> jest dobrym porządkiem. (Zbiór <math>\displaystyle \{0,1\}^*</math> to zbiór wszystkich skończonych ciągów złożonych z 0 i 1. Porządek leksykograficzny na takim zbiorze definiujemy jako <math>\displaystyle x\prec y</math> jeśli <math>\displaystyle x</math> jest prefiksem <math>\displaystyle y</math>  lub jeśli na pierwszej współrzędnej na której się różnią w <math>\displaystyle x</math> występuje 0, a w <math>\displaystyle y</math> występuje 1.)   
+
Czy porządek leksykograficzny na zbiorze <math>\displaystyle \{0,1\}^*</math> jest dobrym porządkiem. (Zbiór <math>\displaystyle \{0,1\}^*</math> to zbiór wszystkich skończonych ciągów złożonych z 0 i 1. Porządek leksykograficzny na takim zbiorze definiujemy jako <math>\displaystyle x\prec y</math>, jeśli <math>\displaystyle x</math> jest prefiksem <math>\displaystyle y</math>  lub jeśli na pierwszej współrzędnej, na której się różnią w <math>\displaystyle x</math> występuje 0, a w <math>\displaystyle y</math> występuje 1.)   
 
}}
 
}}
  
Linia 302: Linia 302:
 
<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">   
  
Porządek ten nie jest dobry. Niech <math>\displaystyle A</math> będzie zbiorem wszystkich ciągów postaci <math>\displaystyle 0^n 1</math>, gdzie <math>\displaystyle 0^n</math> oznacza ciąg zer długości <math>\displaystyle n</math>. Przypuśćmy, że w zbiorze <math>\displaystyle A</math> istnieje element najmniejszy, musi być postaci <math>\displaystyle 0^{n_0} 1</math> dla pewnego <math>\displaystyle n_0 \in \mathbb{N}</math>. Wtedy jednak ciąg <math>\displaystyle 0^{n_0+1} 1</math> jest od niego mniejszy, gdyż na pierwszej różniącej ich współrzędnej (<math>\displaystyle n_0+1</math>) pierwszy z nich ma 1, a drugi 0. Wobec tego w <math>\displaystyle A</math> nie istnieje element najmniejszy i porządek ten nie jest dobry.
+
Porządek ten nie jest dobry. Niech <math>\displaystyle A</math> będzie zbiorem wszystkich ciągów postaci <math>\displaystyle 0^n 1</math>, gdzie <math>\displaystyle 0^n</math> oznacza ciąg zer długości <math>\displaystyle n</math>. Przypuśćmy, że w zbiorze <math>\displaystyle A</math> istnieje element najmniejszy, musi być postaci <math>\displaystyle 0^{n_0} 1</math>, dla pewnego <math>\displaystyle n_0 \in \mathbb{N}</math>. Wtedy jednak ciąg <math>\displaystyle 0^{n_0+1} 1</math> jest od niego mniejszy, gdyż na pierwszej różniącej ich współrzędnej (<math>\displaystyle n_0+1</math>) pierwszy z nich ma 1, a drugi 0. Wobec tego w <math>\displaystyle A</math> nie istnieje element najmniejszy i porządek ten nie jest dobry.
 
</div></div>
 
</div></div>
  

Wersja z 09:31, 21 wrz 2006

Wprowadzenie

W poniższym wykładzie przyjrzymy się dokładnie zbiorom dobrze uporządkowanym. Jedną z ważniejszych własności tych zbiorów jest to, że prawdziwa jest w nich uogólniona zasada indukcji zwana "indukcją pozaskończoną". Jest to szczególnie istotne w kontekście twierdzenia Zermelo które mówi, że każdy zbiór da się dobrze uporządkować. Możemy dzięki temu przeprowadzać dowody indukcyjne oraz definiować nowe funkcje za pomocą indukcji pozaskończonej na zbiorach większych niż przeliczalne.

Dobre uporządkowanie

Przypomnijmy, że zbiorem dobrze uporządkowanym nazywamy zbiór częściowo uporządkowany, w którym każdy niepusty podzbiór ma element najmniejszy. Wynika stąd, że również w całym zbiorze musi istnieć element najmniejszy, o ile tylko zbiór jest niepusty.

Przykład 2.1.

Przykładem zbioru dobrze uporządkowanego jest zbiór uporządkowany, przez .
Zasada minimum (patrz Wykład 7, Twierdzenie 5.2)

mówi, że w każdym podzbiorze  istnieje element najmniejszy, a więc, że ten porządek jest dobry.

Ćwiczenie 2.2

Udowodnij, że każdy dobry porządek jest porządkiem liniowym.

Wskazówka
Rozwiązanie

Zbiory dobrze uporządkowane mają bardzo specyficzną strukturę. Jedną z własności jest istnienie następników dla prawie wszystkich elementów.

Definicja 2.3.

W zbiorze uporządkowanym element nazywamy następnikiem elementu , jeśli , oraz każdy element silnie większy od jest nie mniejszy od (czyli ).

Ćwiczenie 2.4

Podaj przykład zbioru uporządkowanego, w którym żaden element nie ma następnika.

Rozwiązanie

Twierdzenie 2.5.

W zbiorze dobrze uporządkowanym każdy element, który nie jest elementem największym, ma następnik.

Dowód

Niech będzie zbiorem dobrze uporządkowanym. Niech będzie dowolnym elementem zbioru , który nie jest elementem największym. Zdefiniujmy zbiór następująco:

Zbiór jest niepusty, gdyż nie jest elementem największym. Ponieważ jest dobrze uporządkowany, to w zbiorze istnieje element najmniejszy, nazwijmy go . Pokażemy, że jest następnikiem . Ponieważ , to . Weźmy dowolny element , który jest silnie większy od . Wtedy musi należeć do , a więc ponieważ jest najmniejszy w , to . Wobec tego jest następnikiem elementu .

End of proof.gif

Definicja 2.6.

Element zbioru dobrze uporządkowanego nazywamy elementem granicznym, jeśli nie jest następnikiem, żadnego elementu.

Ćwiczenie 2.7

Podaj przykład zbioru uporządkowanego liniowo, w którym każdy element ma następnik, a zbiór nie jest dobrze uporządkowany. Czy zbiór tak uporządkowany może mieć element najmniejszy?

Rozwiązanie

Pokażemy teraz, że każdy zbiór dobrze uporządkowany jest podobny do pewnej rodziny zbiorów uporządkowanych przez inkluzję.

Definicja 2.8.

Niech będzie zbiorem uporządkowanym. Zbiór nazywamy przedziałem początkowym jeśli

Czyli jest przedziałem początkowym, jeśli wraz z każdym swoim elementem zawiera także wszystkie elementy zbioru , które są od niego mniejsze. Będziemy używać następujących oznaczeń, dla niech:

oraz:

Zbiór będziemy nazywać domkniętym przedziałem początkowym.

Twierdzenie 2.9.

Jeśli będzie zbiorem dobrze uporządkowanym. Wtedy każdy jego przedział początkowy, różny od , jest postaci , dla pewnego elementu (czyli każdy przedział początkowy jest postaci ).

Dowód

Niech będzie przedziałem początkowym różnym od . Wtedy zbiór jest niepusty i jest podzbiorem , więc posiada element najmniejszy, oznaczmy go przez . Pokażemy, że . Przypuśćmy, że istnieje element taki, że oraz . Wtedy ponieważ jest przedziałem początkowym, to również musiałby być elementem , co jest sprzeczne z tym, że . Wobec tego wszystkie elementy są silnie mniejsze od . Przypuśćmy teraz, że istnieje element , który jest silnie mniejszy od i nie należy do . Wtedy i ponieważ jest silnie mniejszy od , to dostajemy sprzeczność z faktem, że jest najmniejszy w tym zbiorze. Wobec tego zbiór składa się dokładnie z elementów silnie mniejszych od , co oznacza, że .

End of proof.gif

Ćwiczenie 2.10

Podaj przykład zbioru dobrze uporządkowanego , w którym istnieje przedział początkowy różny od , który nie jest postaci (uwaga! nierówność jest słaba).

Wskazówka
Rozwiązanie

Ćwiczenie 2.11

Udowodnij, że dla każdego dobrego porządku istnieje funkcja, która niepustym podzbiorom przypisuje ich element najmniejszy. Funkcje tę nazywamy .

Rozwiązanie

W poniższym twierdzeniu przedstawiamy konstrukcję rodziny zbiorów uporządkowanej przez podobnej do danego zbioru dobrze uporządkowanego.

Twierdzenie 2.12

Niech będzie zbiorem dobrze uporządkowanym, a będzie zbiorem jego istotnych przedziałów początkowych. Wtedy jest podobny do .

Dowód

Zdefiniujmy funkcję , tak aby . Pokażemy, że ta funkcja ustala podobieństwo. Pokażemy po kolei, że jest suriekcją , iniekcją oraz że jest monotoniczna:

  1. Suriektywność funkcji wynika z Twierdzenia 2.9 (patrz Twierdzenie 2.9).
  2. Weźmy dowolne takie, że . Wtedy z definicji oraz , a więc .
  3. Weźmy dowolne takie, że . Weźmy dowolny .

Oznacza to, że , a więc . Wtedy również , a więc . Wobec dowolności wyboru otrzymujemy , a więc funkcja jest monotoniczna.

End of proof.gif

Zauważmy, że własność bycia dobrym porządkiem jest przenoszona przez podobieństwo porządków.

Ćwiczenie 2.13

Jeśli porządki oraz są podobne, to jest dobry wtedy i tylko wtedy, gdy jest dobry.

Rozwiązanie

Ćwiczenie 2.14

Dla zbiorów uporządkowanych , porządek leksykograficzny definiujemy tak, że:

Dla zbiorów uporządkowanych w naturalny sposób, sprawdź, czy następujące ich produkty są dobrze uporządkowane:

  1. ,
  2. ,
  3. ,
  4. .
Rozwiązanie

Ćwiczenie 2.15

Rozważmy dwa porządki na zbiorze zdefiniowane w następujący sposób:

Czy porządki te są podobne?

Wskazówka
Rozwiązanie

Ćwiczenie 2.16

Czy porządek leksykograficzny na zbiorze jest dobrym porządkiem. (Zbiór to zbiór wszystkich skończonych ciągów złożonych z 0 i 1. Porządek leksykograficzny na takim zbiorze definiujemy jako , jeśli jest prefiksem lub jeśli na pierwszej współrzędnej, na której się różnią w występuje 0, a w występuje 1.)

Wskazówka
Rozwiązanie

Zasada indukcji

Zdefiniujemy teraz zasadę indukcji, która będzie obowiązywała w zbiorach dobrze uporządkowanych.

Definicja 3.1.

Niech będzie liniowym porządkiem. W obowiązuje zasada indukcji jeśli dla dowolnego zbioru takiego, że

  1. ,
  2. ,
  3. dla dowolnego jeśli to .

zachodzi .

W wykładzie o liczbach naturalnych udowodniliśmy Wykład 7. twierdzenie o indukcji, z którego wynika, że zasada indukcji jest obowiązuje w . W poniższym twierdzeniu dowodzimy analogiczne twierdzenie dla wszystkich zbiorów dobrze uporządkowanych.

Twierdzenie 3.2.

W każdym zbiorze dobrze uporządkowanym obowiązuje zasada indukcji.

Dowód

Niech będzie dobrym porządkiem. Niech będzie dowolnym zbiorem takim, że

  1. ,
  2. element najmniejszy należy do ,
  3. dla dowolnego jeśli to .

Pokażemy, że . Niech . Dla dowodu niewprost przypuśćmy że . W takim przypadku w zbiorze istnieje element najmniejszy . Skoro jest najmniejszy w to każdy element dla którego musi należeć do (nie może należeć do więc należy do ). Wtedy wiemy, że , a więc z trzeciej własności zbioru otrzymujemy , a więc dostaliśmy sprzeczność (bo a te zbiory są rozłączne).

End of proof.gif

Okazuje się, że dobre porządki są nawet bardziej związane z zasadą indukcji. Wyrazem tego jest poniższe twierdzenie.

Twierdzenie 3.3.

Każdy porządek liniowy w którym istnieje element najmniejszy i obowiązuje zasada indukcji jest dobry.

Dowód

Niech będzie liniowym porządkiem, w którym istnieje element najmniejszy oraz obowiązuje zasada indukcji. Niech będzie podzbiorem w którym nie ma elementu najmniejszego. Zdefiniujmy zbiór jako zbiór tych elementów , które są mniejsze od wszystkich elementów z , czyli

Zbiór jest niepusty, gdyż ( nie może należeć do gdyż byłby najmniejszy). Pokażemy, że dla dowolnego jeśli to . Przypuśćmy, że tak nie jest. Wtedy dla pewnego mamy oraz . Wynika stąd, że istnieje element taki, że ponieważ jednak żaden element mniejszy od nie należy do to , a więc . Z tego samego powodu i z faktu że porządek jest liniowy otrzymujemy że element jest najmniejszy w , co jest sprzeczne z założeniem, że w nie ma elementu najmniejszego. Wobec tego konieczne jest aby .

Pokazaliśmy, że zbiór spełnia założenia zasady indukcji. Ponieważ zasada ta obowiązuje w to otrzymujemy . Wynika stąd, że zbiór musi być pusty. Wobec tego każdy niepusty podzbiór ma element najmniejszy, a więc jest dobrym porządkiem.

End of proof.gif

Twierdzenie o definiowaniu przez indukcje udowodnione dla liczb naturalnych również ma swój odpowiednik dla dobrych porządków. Mówi ono, że jeśli wyspecyfikujemy sposób konstrukcji wartości funkcji na argumentach na podstawie wartości oraz wartości tej funkcji dla wszystkich takich, że , to wyznaczymy jednoznacznie funkcję odpowiadającą tej specyfikacji. Twierdzenie to, nazywane jest twierdzeniem o definiowaniu przez indukcję pozaskończoną, gdyż najważniejsze zastosowania ma właśnie dla zbiorów nieskończonych.

Twierdzenie 3.4. [o definiowaniu przez indukcję pozaskończoną]

Niech będzie dobrym porządkiem. Przez oznaczamy zbiór wszystkich funkcji częściowych ze zbioru do . Pokażemy, że dla każdej funkcji istnieje dokładnie jedna funkcja dla której

Dowód

Dowód przebiega analogicznie jak dla liczb naturalnych. Rozważmy następujący zbiór

gdzie i oznaczają odpowiednio

  1. .

Innymi słowy jest zbiorem funkcji częściowych określonych na przedziałach początkowych , spełniających warunek 3.1.

Pokażemy, że dla każdych dwóch funkcji częściowych jedna z nich jest rozszerzeniem drugiej. Przypuśćmy, że tak nie jest. Weźmy funkcje określone odpowiednio na zbiorach , które różnią się na pewnym argumencie na którym obie są określone. Bez straty ogólności możemy założyć, że . Rozważmy zbiór . Zbiór jest podzbiorem . Skoro funkcje się różnią na jakimś argumencie to jest niepusty, a więc zawiera element najmniejszy, oznaczmy go przez . Skoro jest najmniejszy to dla dla wszystkich funkcje muszą być równe. Czyli

wobec tego dla dowolnego mamy

I skoro obie funkcje są określone na i należą do to dla dowolnego z warunku (2) otrzymamy . Otrzymaliśmy więc sprzeczność z faktem, że . Wobec tego jest pusty i jest rozszerzeniem .

Pokażemy teraz, że dla każdego istnieje w funkcja określona na . Niech będzie zbiorem tych elementów dla których nie istnieje w funkcja określona na . Załóżmy dla dowodu nie wprost, że ten zbiór jest niepusty. Jako podzbiór zbioru dobrze uporządkowanego posiada element najmniejszy, oznaczmy go przez . Niech będzie zbiorem funkcji częściowych z określonych na domkniętych przedziałach początkowych silnie mniejszych od , ponieważ jest najmniejszy w to na każdym takim przedziale jest określona jakaś funkcja należąca do . Określimy funkcję jako

Zauważmy jest funkcją częściową, gdyż dla każdych dwóch funkcji z jedna z nich jest rozszerzeniem drugiej. Z powyższej definicji wynika, że . Wobec tego spełnia pierwszy warunek przynależności do zbioru . Pokażemy, że spełnia również drugi. Weźmy dowolny oraz . Rozważymy dwa przypadki.

1. Jeśli to

i ponieważ to

2. W pozostałym przypadku . Wtedy a więc musi należeć do którejś z funkcji z , nazwijmy tą funkcję . Ponieważ to

Skoro to a więc . Ponieważ jednak jest określona na całym zbiorze to

Stąd otrzymujemy

Wobec tego funkcja spełnia także drugi warunek przynależności do , a więc . Ponieważ to otrzymaliśmy sprzeczność z . Wobec tego zbiór musi być pusty. Czyli dla każdego istnieje w funkcja określona na .

Pokażemy, że szukaną funkcją jest . Ponieważ elementy zbioru są funkcjami częściowymi i zbiór jest uporządkowanymi przez inkluzję to jest funkcją częściową. Ponieważ dla każdego istnieje w funkcja to jest określona na wszystkich elementach . Stąd otrzymujemy . Ze sposobu konstrukcji wynika również, że spełniony jest warunek 3.1.

Pozostało pokazać, że jest jedyną taką funkcją. Przypuśćmy, że istnieje funkcja różna od która spełnia warunek 3.1. Niech . Ponieważ jest niepustym podzbiorem to posiada element najmniejszy . Ponieważ jest najmniejszy w to

Ustalmy dowolne . Wtedy

Ponieważ obie funkcje spełniają 3.1 to lewa strona powyższej równości jest równa a prawa . Wynika stąd, że co wobec dowolności wyboru jest sprzeczne z przynależnością do zbioru . Wynika stąd, że zbiór musi być pusty, a więc funkcje i muszą być równe.

End of proof.gif

Ćwiczenie 3.5

Udowodnij, że każdy zbiór nieskończony można podzielić na dwa równoliczne rozłączne podzbiory.

Wskazówka
Rozwiązanie

Pokażemy teraz ważne twierdzenie,które mówi że dla dowolnych dwóch zbiorów dobrze uporządkowanych jeden z nich jest podobny do przedziału początkowego drugiego.

Twierdzenie 3.6.

Niech , będą dobrymi porządkami. Wtedy przynajmniej jedno z poniższych zdań jest prawdziwe

  1. istnieje przedział początkowy taki, że jest podobny do
  2. istnieje przedział początkowy taki, że jest podobny do

Dowód

Niech będzie elementem nie należącym do (w roli może wystąpić , ze względu na przejrzystość dowodu decydujemy się na oznaczenie ). Rozważmy zbiór , który uporządkujemy relacją , czyli jest większy od wszystkich elementów . Zauważmy, że jest dobrym porządkiem.

Zdefiniujmy funkcję następująco, dla dowolnej funkcji częściowej niech

Pokażemy, że funkcja jest monotoniczna (funkcje częściowe porządkujemy za pomocą inkluzji). Dla dowolnych dwóch funkcji częściowych takich, że mamy

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \vec{s}(X) \subset \vec{r}(X) \\ Z \setminus \vec{s}(X) \supset Z\setminus \vec{r}(X)\\ g(s)= \min_Z(Z \setminus \vec{s}(X)) \leq \min_Z(Z\setminus \vec{r}(X))= g(r). \endaligned}

Z twierdzenia o definiowaniu przez indukcję wynika, że istnieje funkcja dla której

Łatwo pokazać, że funkcja jest monotoniczna. Dla dowolnych dla których mamy

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned O(x) \subset O(y) \\ h \cap (O(x) \times Z) \subset h \cap (O(y) \times Z) \endaligned}

i z monotoniczności funkcji otrzymujemy

Pokażemy że dla każdego prawdą jest, że . Ustalmy dowolny element . Z monotoniczności dostajemy prawie natychmiast . Dla pokazania inkluzji w drugą stronę weźmy dowolny element . Wtedy . Przypuśćmy dla dowodu nie wprost, że wtedy oraz co jest sprzeczne z definicją funkcji w punkcie , bo element miał być najmniejszy w tym zbiorze. Pokazaliśmy więc inkluzje w obie strony. Wobec dowolności wyboru dowiedliśmy żądaną własność.

Pokażemy, że dla różnych elementów jeśli wartości są równe sobie to są równe . Weźmy dowolne rożne elementy dla których . Bez straty ogólności możemy założyć, że . Wtedy

Ponieważ to , a więc skoro to musi należeć do , czyli .

Rozważymy teraz dwa przypadki.

1. Jeśli to jest iniekcją. Zauważmy, że

. Ponieważ to

Parser nie mógł rozpoznać (nieznana funkcja „\kPPoczD”): {\displaystyle \displaystyle \vec{h}(X)= \vec{h}(\bigcup_{x\in X} \overline{O(x)})= \bigcup_{x\in X} \vec{h}(\overline{O(x)})= \bigcup_{x\in X} \kPPoczD(h{x}). }

A więc jako suma przedziałów początkowych jest przedziałem początkowym. Wobec tego jest monotoniczną iniekcją której obrazem jest istotny przedział początkowy , a więc również przedział początkowy . Wobec tego jest podobny do przedziału początkowego .

2. Jeśli to niech będzie takim elementem, że

. Rozważymy zbiór . Z monotoniczności wynika, że jest odcinkiem początkowym . Ponieważ to . Wobec tego funkcja zawężona do zbioru jest monotoniczną bijekcją w zbiór . Wynika stąd, że jest podobny do . Ponieważ jest przedziałem początkowym to jest podobny do pewnego przedziału początkowego .

End of proof.gif

Z powyższego twierdzenia wynika bardzo ważny następujący wniosek

Twierdzenie 3.7.

Każde dwa zbiory są porównywalne na moc. Czyli dla dowolnych zbiorów , prawdą jest, że

Dowód

Z twierdzenia 3.6 (patrz twierdzenie 3.6.) wynika, że dowolne zbiory dobrze uporządkowane można porównywać na moc. Z twierdzenia Ernsta Zermelo wynika, że dowolne zbiory można dobrze uporządkować. Wobec tego dowolne zbioru można porównywać na moc.

End of proof.gif

Twierdzenie 3.8.

Żaden zbiór dobrze uporządkowany nie jest podobny do swojego istotnego przedziału początkowego.

Dowód

Niech będzie dobrym porządkiem. Przypuśćmy, że istnieje przedział początkowy który uporządkowany relacją jest podobny do . Niech będzie funkcją podobieństwa niech . Skoro to jest zbiorem niepustym, a więc ma element najmniejszy, oznaczmy go przez . Wtedy , a więc ponieważ jest najmniejszy w zbiorze to . Rozważmy dwa przypadki

  1. wtedy nie jest iniekcją, a więc dostaliśmy sprzeczność.
  2. a więc nie jest monotoniczna i dostaliśmy sprzeczność.
End of proof.gif

Liczby porządkowe

W poprzednim rozdziale pokazaliśmy, że dla dowolnych dwóch zbiorów dobrze uporządkowanych jeden z nich jest podobny do odcinka początkowego drugiego.

Powiemy, że dobre porządki i tego samego typu jeśli jest podobny do .

Łatwo wykazać, że każdy dobry porządek jest tego samego typu co on sam, jeśli jest tego samego typu co to jest tego samego typu co , oraz że jeśli jest tego samego typu co i jest tego samego typu co to jest tego samego typu co . Te trzy własności dokładnie odpowiadają wymaganiom jakie stawiamy relacji, aby była relacją równoważności. Może się wydawać kuszące zdefiniowanie relacji podobieństwa. Niestety takie próby skazane są na niepowodzenie, gdyż taka relacja musiałaby być określona na zbiorze wszystkich dobrych porządków, a taki zbiór (podobnie jak zbiór wszystkich zbiorów) nie istnieje. Co więcej dla ustalonego niepustego zbioru dobrze uporządkowanego nie istnieje nawet zbiór dobrych porządków, które są tego samego typu co on. W podejściach do teorii mnogości, które dopuszczają pojęcie klasy, mówi się o typach porządkowych jako o klasach. W przypadku rozważanej teorii ZFC, nie możemy definiować klas które nie są zbiorami. Zamiast tego wyróżnimy pewne porządki które będą reprezentować wszystkie porządki podobne do nich. Porządki te, będące czymś w rodzaju reprezentantów "klas" podobieństwa, nazwiemy liczbami porządkowymi. Poniższa definicja liczb porządkowych pochodzi od Johna von Neumanna. Jest to formalizacja idei aby liczba porządkowa była zbiorem liczb porządkowych od niej mniejszych.

Definicja 4.1.

Zbiór nazwiemy liczbą porządkową jeśli ma następujące własności

Najprostszym przykładem liczby porządkowej jest zbiór pusty. W poniższym ćwiczeniu pokazujemy jak można konstruować kolejne liczby porządkowe.

Ćwiczenie 4.2

Udowodnij, że jeśli jest liczbą porządkową to jest liczbą porządkową.

Rozwiązanie

Z twierdzenia udowodnionego w poprzednim ćwiczeniu możemy wywnioskować, że każda liczba naturalna jest liczbą porządkową. Nie koniec na tym, zauważmy, że cały też jest liczbą porządkową (patrz również twierdzenie wykład o liczbach inkluzje liczb), a więc również oraz itd.

Twierdzenie 4.3.

Każdy element liczby porządkowej jest liczbą porządkową.

Dowód

Niech będzie liczbą porządkową, i niech . Z drugiej własności liczb porządkowych otrzymujemy . Pokażemy że spełnia warunki bycia liczbą porządkową

  1. Weźmy dowolne różne elementy . Wtedy ponieważ to . Skoro jest liczbą porządkową to lub . Zbiór spełnia więc pierwszy warunek bycia liczbą porządkową.
  2. Weźmy dowolny element . Ponieważ to i z drugiej własności liczb porządkowych otrzymujemy . Przypuśćmy, że , wtedy istnieje taki, że . Ponieważ jednak to to z drugiej własności liczb porządkowych otrzymujemy lub . W pierwszym przypadku otrzymujemy a w drugim .

Obydwa te przypadki prowadzą do sprzeczności z aksjomatem regularności. Wobec tego, konieczne jest aby .

End of proof.gif

Z powyższego twierdzenia natychmiast wynika następujący fakt z którego będziemy często korzystać.

Fakt 4.1.

Dla dowolnej liczby porządkowej oraz elementów jeśli to .

Jeśli liczby porządkowe mają reprezentować "klasy" podobnych dobrych porządków, to same powinny być dobrymi porządkami. Dowodzimy tego w następnym twierdzeniu.

Twierdzenie 4.4.

Każdy zbiór będący liczbą porządkową jest dobrze uporządkowany relacją inkluzji.

Dowód

Rozważmy zbiór będący liczbą porządkową. Skoro dla każdych dwóch różnych elementów mamy lub to z poprzedniego twierdzenia otrzymujemy lub . A więc jest uporządkowany liniowo przez relację inkluzji.

Pokażemy teraz, że w każdym podzbiorze istnieje element najmniejszy ze względu na inkluzję. Weźmy dowolny taki zbiór . Z aksjomatu regularności z Wykładu 4 wynika, że istnieje element taki, że . Pokażemy, że należy do każdego elementu który jest różny od . Weźmy dowolny taki element , wiemy, że jest różny od , a więc z pierwszej własności liczb porządkowych otrzymujemy lub . Przypuśćmy, że , wtedy ponieważ to również co prowadzi do sprzeczności ponieważ ten zbiór jest niepusty. Wobec tego konieczne jest aby . Z drugiej własności liczb porządkowych otrzymujemy, że . Wobec czego pokazaliśmy, że dla dowolnego mamy , co znaczy że jest najmniejszym w sensie inkluzji elementem .

End of proof.gif

Twierdzenie 4.5.

Każdy przedział początkowy liczby porządkowej jest liczbą porządkową.

Dowód

Jeśli przedział początkowy jest zbiorem pustym to jest liczbą początkową. Zajmiemy się więc tylko niepustymi. Weźmy dowolną liczbę porządkową . Niech będzie jej niepustym przedziałem początkowym. Pokażemy, że jest liczbą porządkową.

  1. Własność pierwsza wynika natychmiast z faktu, że .
  2. Weźmy dowolną liczbę . Skoro jest liczbą porządkową to . Weźmy dowolny element , wynika stąd, że , a więc skoro

jest przedziałem początkowym to .

End of proof.gif

Ćwiczenie 4.6

Niech będzie liczbą porządkową. Udowodnij, że dla dowolnych elementów jeśli to .

Wskazówka
Rozwiązanie

Z powyższego ćwiczenia wynika następujący fakt.

Fakt 4.2.

Każdy element liczby porządkowej jest liczbą porządkową.

Ćwiczenie 4.7

Udowodnij, że jest elementem każdej niepustej liczby porządkowej.

Rozwiązanie

Twierdzenie 4.8.

Dla każdych dwóch liczb porządkowych, jedna jest podzbiorem drugiej.

Dowód

Dowiedliśmy już że liczby porządkowe są dobrze uporządkowane przez inkluzję. Wobec tego z twierdzenia 3.6 (patrz twierdzenie 3.6.) wynika, że dla każdych dwóch liczb porządkowych jedna z nich jest podobna do przedziału początkowego drugiej. Ponieważ przedziały początkowe liczb porządkowych są liczbami porządkowymi to wystarczy wykazać, że każde podobieństwo liczb porządkowych uporządkowanych inkluzją jest identycznością.

Weźmy liczby porządkowe i przypuśćmy, że funkcja jest podobieństwem pomiedzy porządkami i . Pokażemy, że jest identycznością.

Niech będzie zbiorem dla których . Jeśli to funkcja jest identycznością. Dla dowodu niewprost załóżmy więc, że . Ponieważ jest dobrze uporządkowany to w zbiorze istnieje element najmniejszy, oznaczmy go przez .

Pokażemy, że . Weźmy dowolny element , wtedy i z monotoniczności otrzymujemy ponieważ jednak to a więc . Wobec dowolności wyboru dostajemy .

Skoro to istnieje element który nie należy do . Ponieważ to również . Funkcja jest bijekcją więc musi istnieć dla którego . Łatwo zauważyć, że , gdyż . Element nie może być elementem gdyż wtedy i . Wobec tego musi być elementem , ale wtedy i z monotoniczności dostajemy , co jest sprzeczne z faktem (bo wtedy ).

Pokazaliśmy, że założenie o niepustości zbioru prowadzi do sprzeczności. Zbiór ten musi więc być pusty co oznacza, że funkcja jest identycznością. Wobec tego, każde dwie podobne liczby porządkowe są sobie równe.

End of proof.gif

Powyższe twierdzenie mówi, że każde dwie liczby porządkowe są porównywalne przez inkluzję. Przez analogię do liczb naturalnych używamy jednak dla liczb porządkowych oznaczenia zamiast .

Z powyższego twierdzenia wynika, że każdy zbiór liczb porządkowych jest uporządkowany liniowo przez inkluzję.

Ćwiczenie 4.9

Udowodnij, że każdy zbiór liczb porządkowych jest dobrze uporządkowany inkluzją.

Rozwiązanie

Twierdzenie 4.10. [Antynomia Burali-Forti]

Nie istnieje zbiór liczb porządkowych.

Dowód

Dla dowodu nie wprost przypuśćmy, że taki zbiór istnieje, nazwijmy go . Pokażemy, że jest liczbą porządkową. W poprzednich ćwiczeniach pokazaliśmy, że jest dobrze uporządkowany, przez inkluzję.

  1. Niech będą różnymi elementami . Wtedy lub . Z ćwiczenia 4.6 (patrz ćwiczenie 4.6) wynika, że w pierwszym przypadku mamy a w drugim . Więc zbiór spełnia pierwszy z warunków bycia liczbą porządkową.
  2. Weźmy dowolny element ze zbioru . Z faktu 4.2 (patrz fakt 4.2.) wiemy, że każdy element należący do zbioru jest liczbą porządkową. Ponieważ do należą wszystkie liczby porządkowe to . A więc spełnia drugi warunek bycia liczbą porządkową.

Wobec powyższych faktów zbiór jest liczbą porządkową, a więc musi być własnym elementem. Otrzymaliśmy więc sprzeczność.

End of proof.gif

W ostatnim twierdzeniu w tym rozdziale pokażemy, że każdy dobry porządek jest podobny do pewnej liczby porządkowej, a więc każda "klasa" podobnych dobrych porządków ma swojego reprezentanta, który jest liczbą porządkową.

Twierdzenie 4.11.

Każdy zbiór dobrze uporządkowany jest podobny do pewnej liczby porządkowej.

Dowód

Dla dowodu nie wprost załóżmy, że istnieje dobry porządek który nie jest podobny do żadnej liczby porządkowej. Z twierdzenia 3.6 (patrz twiedzenie 3.6.) wynika, że każda liczba porządkowa jest podobna do jakiegoś przedziału początkowego . Używając aksjomatu zastępowania z Wykladu 4 pokażemy, że istnieje wtedy zbiór liczb porządkowych.

Niech będzie formułą o zmiennych wolnych która będzie spełniona wtedy i tylko wtedy, gdy jest dobrym porządkiem, jest liczbą porządkową i jest podobne do . Nie jest trudno napisać taką formułę, ale nie jest ona krótka, dlatego ten fragment dowodu pozostawiamy czytelnikowi. Ponieważ dwie liczby porządkowe są podobne wtedy i tylko wtedy gdy są równe to do każdy dobry porządek jest podobny do co najwyżej jednej liczby porządkowej. Wobec tego dla dowolnego można dobrać co nawyżej jedno takie, aby formuła była prawdziwa. To znaczy że dla formuły przesłanka aksjomatu zastępowania jest spełniona. Wobec tego prawdą jest również

Biorąc za zbiór odcinków początkowych , dostaniemy, że istnieje zbiór taki, że należy do wtedy i tylko wtedy, gdy istnieje będący odcinkiem początkowym dla którego prawdziwa jest formuła . Oznacza to dokładnie że istnieje zbiór wszystkich liczb porządkowych podobnych do przedziałów początkowych . Skoro założyliśmy, że każda liczba porządkowa jest podobna do pewnego przedziału początkowego , to istnieje zbiór liczb porządkowych. Otrzymaliśmy więc sprzeczność z twierdzeniem 4.10 (patrz twierdzenie 4.10.).

End of proof.gif

Najmniejszą nieskończoną liczbę porządkową będziemy oznaczać przez . W naszym podejściu jest po prostu zbiorem , który jest dobrze uporządkowany przez inkluzję. Przyjęło się jednak używać oznaczenia dla podkreślenia, że mówimy o dobrym uporządkowaniu. Będziemy mówić że zbiór częściowo uporządkowany jest typu jeśli jest podobny do . Podobnie dla dowolnej innej liczby porządkowej powiemy, że zbiór częściowo uporządkowany jest typu jeśli jest podobny do

Ćwiczenie 4.12

Udowodnij, że dla dowolnych rozłącznych dobrych porządków następujące zbiory są dobrymi porządkami:

  1. czyli na zbiorach porządki są takie jak w zbiorach wyjściowych, a do tego każdy element zbioru jest mniejszy od każdego elementu zbioru .
  2. , gdzie jest porządkiem leksykograficznym, czyli
Rozwiązanie

Powyższe konstrukcje łatwo zaadaptować do operowania na zbiorach które nie są rozłączne. W miejsce wystarczy wziąć zbiór a w miejsce zbiór . Wtedy będziemy mieli zagwarantowaną rozłączność. Porządek na tak zmienionych zbiorach łatwo przenieść z wyjściowych zbiorów poprzez naturalną bijekcję pomiędzy nimi (czyli ). W dalszej części będziemy sie posługiwać tak zmodyfikowanymi konstrukcjami nie dbając o rozłączność zbiorów. Zdefiniujemy teraz arytmetykę na liczbach porządkowych.

Definicja 4.13.

Niech będą liczbami porządkowymi. Wtedy

  1. Liczbę porządkową podobną do będziemy oznaczać przez .
  2. Liczbę porządkową podobną do będziemy oznaczać przez .

Ćwiczenie 4.14

Sprawdź czy prawdziwe są następujące własności liczb porządkowych

Rozwiązanie

Ćwiczenie 4.15

Udowodnij, że liczba porządkowa jest skończona wtedy i tylko wtedy, gdy relacja (czyli ) jest dobrym porządkiem na .

Rozwiązanie