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
 
(Nie pokazano 5 wersji utworzonych przez 3 użytkowników)
Linia 585: Linia 585:
 
takich, że <math>\displaystyle s \subset r</math> mamy:
 
takich, że <math>\displaystyle s \subset r</math> mamy:
  
<center><math>\displaystyle \aligned \vec{s}(X) \subset    \vec{r}(X) \\
+
<center><math>\displaystyle \begin{align} \vec{s}(X) \subset    \vec{r}(X) \\
 
Z \setminus \vec{s}(X) \supset Z\setminus    \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).
 
g(s)= \min_Z(Z \setminus \vec{s}(X)) \leq  \min_Z(Z\setminus    \vec{r}(X))= g(r).
\endaligned</math></center>
+
\end{align}</math></center>
  
 
Z twierdzenia o definiowaniu przez indukcję wynika, że istnieje funkcja <math>\displaystyle h:X\rightarrow
 
Z twierdzenia o definiowaniu przez indukcję wynika, że istnieje funkcja <math>\displaystyle h:X\rightarrow
Linia 599: Linia 599:
 
których <math>\displaystyle x\leq_X y</math> mamy:
 
których <math>\displaystyle x\leq_X y</math> mamy:
  
<center><math>\displaystyle \aligned O(x) \subset O(y) \\
+
<center><math>\displaystyle \begin{align} O(x) \subset O(y) \\
 
h \cap (O(x) \times Z) \subset h \cap (O(y) \times Z)
 
h \cap (O(x) \times Z) \subset h \cap (O(y) \times Z)
\endaligned</math></center>
+
\end{align}</math></center>
  
 
i z monotoniczności funkcji <math>\displaystyle g</math> otrzymujemy:
 
i z monotoniczności funkcji <math>\displaystyle g</math> otrzymujemy:
Linia 634: Linia 634:
  
 
<center><math>\displaystyle \vec{h}(X)=    \vec{h}(\bigcup_{x\in X} \overline{O(x)})=        \bigcup_{x\in X}
 
<center><math>\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}).
+
\vec{h}(\overline{O(x)})= \bigcup_{x\in X}(h{x}).
 
</math></center>
 
</math></center>
  
Linia 689: Linia 689:
 
uporządkowanych jeden z nich jest podobny do odcinka początkowego drugiego.
 
uporządkowanych jeden z nich jest podobny do odcinka początkowego drugiego.
  
Powiemy, że dobre porządki <math>\displaystyle A</math> i <math>\displaystyle B</math> są ''tego samego typu'' jeśli <math>\displaystyle A</math> jest
+
Powiemy, że dobre porządki <math>\displaystyle A</math> i <math>\displaystyle B</math> są ''tego samego typu'', jeśli <math>\displaystyle A</math> jest
 
podobny do <math>\displaystyle B</math>.
 
podobny do <math>\displaystyle B</math>.
  
 
Łatwo wykazać, że każdy dobry porządek jest tego samego typu co on sam, jeśli <math>\displaystyle A</math>
 
Łatwo wykazać, że każdy dobry porządek jest tego samego typu co on sam, jeśli <math>\displaystyle A</math>
jest tego samego typu co <math>\displaystyle B</math> to <math>\displaystyle B</math> jest tego samego typu co <math>\displaystyle A</math>, oraz że jeśli <math>\displaystyle A</math>
+
jest tego samego typu co <math>\displaystyle B</math>, to <math>\displaystyle B</math> jest tego samego typu co <math>\displaystyle A</math> oraz że, jeśli <math>\displaystyle A</math>
jest tego samego typu co <math>\displaystyle B</math> i <math>\displaystyle B</math> jest tego samego typu co  <math>\displaystyle C</math> to <math>\displaystyle A</math> jest tego
+
jest tego samego typu co <math>\displaystyle B</math> i <math>\displaystyle B</math> jest tego samego typu co  <math>\displaystyle C</math>, to <math>\displaystyle A</math> jest tego
 
samego typu co <math>\displaystyle C</math>. Te trzy własności dokładnie odpowiadają wymaganiom jakie stawiamy
 
samego typu co <math>\displaystyle C</math>. 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, aby była relacją równoważności. Może się wydawać kuszące zdefiniowanie
Linia 703: Linia 703:
 
które są tego samego typu co on. W podejściach do teorii mnogości, które dopuszczają
 
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
 
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
+
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
+
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
 
te, będące czymś w rodzaju reprezentantów "klas" podobieństwa, nazwiemy liczbami
porządkowymi. Poniższa definicja liczb porządkowych pochodzi od [http://osilek.mimuw.edu.pl/index.php?title=Biografia_Neumann Johna von Neumanna]. Jest to
+
porządkowymi. Poniższa definicja liczb porządkowych pochodzi od [[Biografia Neumann, John|Johna von Neumanna]]. Jest to
 
formalizacja idei aby liczba porządkowa była zbiorem liczb porządkowych od niej
 
formalizacja idei aby liczba porządkowa była zbiorem liczb porządkowych od niej
 
mniejszych.
 
mniejszych.
Linia 712: Linia 712:
 
{{definicja|4.1.||
 
{{definicja|4.1.||
  
Zbiór <math>\displaystyle X</math> nazwiemy liczbą porządkową jeśli  ma następujące własności
+
Zbiór <math>\displaystyle X</math> nazwiemy liczbą porządkową, jeśli  ma następujące własności:
# <math>\displaystyle \forall_{x,y\in X} \;x \in y \vee y\in x \vee x=y</math>
+
# <math>\displaystyle \forall_{x,y\in X} \;x \in y \vee y\in x \vee x=y</math>.
# <math>\displaystyle \forall_{x\in X} \;x\subset X</math>
+
# <math>\displaystyle \forall_{x\in X} \;x\subset X</math>.
 
}}
 
}}
 
Najprostszym przykładem liczby porządkowej jest zbiór pusty. W poniższym ćwiczeniu
 
Najprostszym przykładem liczby porządkowej jest zbiór pusty. W poniższym ćwiczeniu
pokazujemy jak można konstruować kolejne liczby porządkowe.
+
pokazujemy, jak można konstruować kolejne liczby porządkowe.
  
 
{{cwiczenie|4.2||
 
{{cwiczenie|4.2||
  
Udowodnij, że jeśli <math>\displaystyle X</math> jest liczbą porządkową to <math>\displaystyle X \cup \{X\}</math> jest liczbą porządkową.
+
Udowodnij, że jeśli <math>\displaystyle X</math> jest liczbą porządkową, to <math>\displaystyle X \cup \{X\}</math> jest liczbą porządkową.
  
 
}}
 
}}
Linia 729: Linia 729:
 
Pokażemy, że zbiór  <math>\displaystyle X \cup \{X\}</math> spełnia własności liczb porządkowych.
 
Pokażemy, że zbiór  <math>\displaystyle X \cup \{X\}</math> spełnia własności liczb porządkowych.
  
# Weźmy dowolne <math>\displaystyle x,y\in X \cup \{X\}</math> takie, że <math>\displaystyle y\neq x</math>. Jeśli <math>\displaystyle x,y \in X</math> to ponieważ <math>\displaystyle X</math> jest liczbą porządkową otrzymujemy <math>\displaystyle x\in y</math> lub <math>\displaystyle y\in x</math>. W pozostałym przypadku jeden z tych elementów jest równy <math>\displaystyle X</math>. Ze względu na symetrię sytuacji przypuśćmy, że <math>\displaystyle x=X</math>. Wtedy ponieważ <math>\displaystyle y \in X \cup \{X\}</math> i <math>\displaystyle y\neq x=X</math> to <math>\displaystyle y\in X</math>, a więc <math>\displaystyle y\in x</math>. Pokazaliśmy więc że dla każdych dwóch różnych elementów zbioru <math>\displaystyle X \cup \{X\}</math> jeden z nich jest elementem drugiego.
+
# Weźmy dowolne <math>\displaystyle x,y\in X \cup \{X\}</math> takie, że <math>\displaystyle y\neq x</math>. Jeśli <math>\displaystyle x,y \in X</math>, to ponieważ <math>\displaystyle X</math> jest liczbą porządkową, otrzymujemy <math>\displaystyle x\in y</math> lub <math>\displaystyle y\in x</math>. W pozostałym przypadku jeden z tych elementów jest równy <math>\displaystyle X</math>. Ze względu na symetrię sytuacji przypuśćmy, że <math>\displaystyle x=X</math>. Wtedy ponieważ <math>\displaystyle y \in X \cup \{X\}</math> i <math>\displaystyle y\neq x=X</math>, to <math>\displaystyle y\in X</math>, a więc <math>\displaystyle y\in x</math>. Pokazaliśmy więc, że dla każdych dwóch różnych elementów zbioru <math>\displaystyle X \cup \{X\}</math> jeden z nich jest elementem drugiego.
# Weźmy dowolny <math>\displaystyle x\in X</math>. Rozważymy dwa przypadki
+
# Weźmy dowolny <math>\displaystyle x\in X</math>. Rozważymy dwa przypadki:
  
# <math>\displaystyle x\in X</math>. Wtedy ponieważ <math>\displaystyle X</math> jest liczbą porządkową to <math>\displaystyle x\subset X</math>, a więc tym bardziej <math>\displaystyle x\subset X\cup \{X\}</math>.
+
# <math>\displaystyle x\in X</math>. Wtedy ponieważ <math>\displaystyle X</math> jest liczbą porządkową, to <math>\displaystyle x\subset X</math>, a więc tym bardziej <math>\displaystyle x\subset X\cup \{X\}</math>.
# <math>\displaystyle x\in \{X\}</math>. Wtedy <math>\displaystyle x=X</math> a więć również <math>\displaystyle x\subset X</math>.
+
# <math>\displaystyle x\in \{X\}</math>. Wtedy <math>\displaystyle x=X</math>, a więc również <math>\displaystyle x\subset X</math>.
  
 
Wobec tego każdy <math>\displaystyle x</math> ze zbioru <math>\displaystyle X \cup \{X\}</math> jest jego podzbiorem.
 
Wobec tego każdy <math>\displaystyle x</math> ze zbioru <math>\displaystyle X \cup \{X\}</math> jest jego podzbiorem.
  
Zbiór <math>\displaystyle X \cup \{X\}</math> spełnia własności w definicji liczb porządkowych a więc jest liczbą porządkową.
+
Zbiór <math>\displaystyle X \cup \{X\}</math> spełnia własności w definicji liczb porządkowych, a więc jest liczbą porządkową.
 
</div></div>
 
</div></div>
  
 
Z twierdzenia udowodnionego w poprzednim ćwiczeniu możemy wywnioskować, że każda
 
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 <math>\displaystyle \mathbb{N}</math>
 
liczba naturalna jest liczbą porządkową. Nie koniec na tym, zauważmy, że cały <math>\displaystyle \mathbb{N}</math>
też jest liczbą porządkową (<u>'''patrz również twierdzenie wykład o liczbach inkluzje liczb</u>'''), a więc również <math>\displaystyle \mathbb{N} \cup \{\mathbb{N}\}</math> oraz <math>\displaystyle \mathbb{N} \cup \{\mathbb{N}\} \cup
+
też jest liczbą porządkową (patrz [[Logika i teoria mnogości/Wykład 7: Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje#twierdzenie_4_1|Wykład 7, Twierdzenie 4.1]]), a więc także <math>\displaystyle \mathbb{N} \cup \{\mathbb{N}\}</math> oraz <math>\displaystyle \mathbb{N} \cup \{\mathbb{N}\} \cup
\{\mathbb{N} \cup \{\mathbb{N}\}\}</math> itd.
+
\{\mathbb{N} \cup \{\mathbb{N}\}\}</math>, itd.
  
 
<span id="twierdzenie_4_3">{{twierdzenie|4.3.||
 
<span id="twierdzenie_4_3">{{twierdzenie|4.3.||
Linia 752: Linia 752:
 
{{dowod|||
 
{{dowod|||
  
Niech <math>\displaystyle X</math> będzie liczbą porządkową, i niech <math>\displaystyle x\in X</math>. Z drugiej własności liczb
+
Niech <math>\displaystyle X</math> będzie liczbą porządkową i niech <math>\displaystyle x\in X</math>. Z drugiej własności liczb
porządkowych otrzymujemy <math>\displaystyle x\subset X</math>. Pokażemy że <math>\displaystyle x</math> spełnia warunki bycia liczbą
+
porządkowych otrzymujemy <math>\displaystyle x\subset X</math>. Pokażemy, że <math>\displaystyle x</math> spełnia warunki bycia liczbą
porządkową
+
porządkową:
  
# Weźmy dowolne różne elementy <math>\displaystyle a,b \in x</math>. Wtedy ponieważ <math>\displaystyle x\subset X</math> to <math>\displaystyle a,b \in X</math>. Skoro <math>\displaystyle X</math> jest liczbą porządkową to <math>\displaystyle a\in b</math> lub <math>\displaystyle b\in a</math>. Zbiór <math>\displaystyle x</math> spełnia więc pierwszy warunek bycia liczbą porządkową.
+
# Weźmy dowolne różne elementy <math>\displaystyle a,b \in x</math>. Wtedy ponieważ <math>\displaystyle x\subset X</math>, to <math>\displaystyle a,b \in X</math>. Skoro <math>\displaystyle X</math> jest liczbą porządkową, to <math>\displaystyle a\in b</math> lub <math>\displaystyle b\in a</math>. Zbiór <math>\displaystyle x</math> spełnia więc pierwszy warunek bycia liczbą porządkową.
# Weźmy dowolny element <math>\displaystyle a \in x</math>. Ponieważ <math>\displaystyle x\subset X</math> to <math>\displaystyle a\in X</math> i z drugiej własności liczb porządkowych otrzymujemy <math>\displaystyle a\subset X</math>. Przypuśćmy, że <math>\displaystyle a \nsubseteq x</math>, wtedy istnieje <math>\displaystyle b\in a</math> taki, że <math>\displaystyle b\notin x</math>. Ponieważ jednak <math>\displaystyle a\subset X</math> to <math>\displaystyle b\in X</math> to z drugiej własności liczb porządkowych otrzymujemy <math>\displaystyle b=x</math> lub <math>\displaystyle x \in b</math>. W pierwszym przypadku otrzymujemy <math>\displaystyle x\in a \in x</math> a w drugim <math>\displaystyle x \in x</math>.
+
# Weźmy dowolny element <math>\displaystyle a \in x</math>. Ponieważ <math>\displaystyle x\subset X</math>, to <math>\displaystyle a\in X</math> i z drugiej własności liczb porządkowych otrzymujemy <math>\displaystyle a\subset X</math>. Przypuśćmy, że <math>\displaystyle a \nsubseteq x</math>, wtedy istnieje <math>\displaystyle b\in a</math> taki, że <math>\displaystyle b\notin x</math>. Ponieważ jednak <math>\displaystyle a\subset X</math>, to <math>\displaystyle b\in X</math>; zatem z drugiej własności liczb porządkowych otrzymujemy <math>\displaystyle b=x</math> lub <math>\displaystyle x \in b</math>. W pierwszym przypadku otrzymujemy <math>\displaystyle x\in a \in x</math> a w drugim <math>\displaystyle x \in x</math>.
  
 
Obydwa te przypadki prowadzą do sprzeczności z aksjomatem regularności. Wobec tego,
 
Obydwa te przypadki prowadzą do sprzeczności z aksjomatem regularności. Wobec tego,
konieczne jest aby <math>\displaystyle a\subset x</math>.
+
konieczne jest, aby <math>\displaystyle a\subset x</math>.
  
 
}}
 
}}
  
Z powyższego twierdzenia natychmiast wynika następujący fakt z którego będziemy
+
Z powyższego twierdzenia natychmiast wynika następujący fakt, z którego będziemy
 
często korzystać.
 
często korzystać.
  
 
{{fakt|4.1.||
 
{{fakt|4.1.||
  
Dla dowolnej liczby porządkowej <math>\displaystyle X</math> oraz elementów <math>\displaystyle x,y\in X</math> jeśli <math>\displaystyle x\in y</math> to <math>\displaystyle x \subset y</math>.
+
Dla dowolnej liczby porządkowej <math>\displaystyle X</math> oraz elementów <math>\displaystyle x,y\in X</math>, jeśli <math>\displaystyle x\in y</math>, to <math>\displaystyle x \subset y</math>.
 
}}
 
}}
  
Linia 783: Linia 783:
  
 
Rozważmy zbiór <math>\displaystyle X</math> będący liczbą porządkową. Skoro dla każdych dwóch różnych
 
Rozważmy zbiór <math>\displaystyle X</math> będący liczbą porządkową. Skoro dla każdych dwóch różnych
elementów <math>\displaystyle x,y\in X</math> mamy <math>\displaystyle x\in y</math> lub <math>\displaystyle y\in x</math> to z poprzedniego twierdzenia
+
elementów <math>\displaystyle x,y\in X</math> mamy <math>\displaystyle x\in y</math> lub <math>\displaystyle y\in x</math>, to z poprzedniego twierdzenia
 
otrzymujemy <math>\displaystyle x\subset y</math> lub <math>\displaystyle y \subset x</math>. A więc <math>\displaystyle X</math> jest uporządkowany liniowo
 
otrzymujemy <math>\displaystyle x\subset y</math> lub <math>\displaystyle y \subset x</math>. A więc <math>\displaystyle X</math> jest uporządkowany liniowo
 
przez relację inkluzji.
 
przez relację inkluzji.
  
 
Pokażemy teraz, że w każdym podzbiorze <math>\displaystyle A\subset X</math> istnieje element najmniejszy
 
Pokażemy teraz, że w każdym podzbiorze <math>\displaystyle A\subset X</math> istnieje element najmniejszy
ze względu na inkluzję. Weźmy dowolny taki zbiór <math>\displaystyle A</math>. Z aksjomatu regularności z <u>'''Wykładu 4</u>''' wynika, że istnieje element <math>\displaystyle a\in A</math> taki, że <math>\displaystyle a \cap A =\emptyset</math>.
+
ze względu na inkluzję. Weźmy dowolny taki zbiór <math>\displaystyle A</math>. Z aksjomatu regularności (patrz [[Logika i teoria mnogości/Wykład 4: Teoria mnogości ZFC. Operacje na zbiorach#Aksjomat_Regularności|Wykład 4, Aksjomat Regularności]]) wynika, że istnieje element <math>\displaystyle a\in A</math> taki, że <math>\displaystyle a \cap A =\emptyset</math>.
Pokażemy, że <math>\displaystyle a</math>  należy do każdego elementu <math>\displaystyle b\in A</math> który jest różny od <math>\displaystyle a</math>. Weźmy
+
Pokażemy, że <math>\displaystyle a</math>  należy do każdego elementu <math>\displaystyle b\in A</math>, który jest różny od <math>\displaystyle a</math>. Weźmy
dowolny taki element <math>\displaystyle b</math>, wiemy, że jest różny od <math>\displaystyle a</math>, a więc z pierwszej własności
+
dowolny taki element <math>\displaystyle b</math>. Wiemy, że jest różny od <math>\displaystyle a</math>, a więc z pierwszej własności
liczb porządkowych otrzymujemy <math>\displaystyle a\in b</math> lub <math>\displaystyle b\in a</math>. Przypuśćmy, że <math>\displaystyle b\in a</math>, wtedy
+
liczb porządkowych otrzymujemy <math>\displaystyle a\in b</math> lub <math>\displaystyle b\in a</math>. Przypuśćmy, że <math>\displaystyle b\in a</math>, wtedy,
ponieważ <math>\displaystyle b\in A</math> to również <math>\displaystyle b\in a\cap A</math> co prowadzi do sprzeczności ponieważ ten
+
ponieważ <math>\displaystyle b\in A</math>, to również <math>\displaystyle b\in a\cap A</math>, co prowadzi do sprzeczności, ponieważ ten
zbiór jest niepusty. Wobec tego konieczne jest aby <math>\displaystyle a\in b</math>. Z drugiej własności
+
zbiór jest niepusty. Wobec tego konieczne jest, aby <math>\displaystyle a\in b</math>. Z drugiej własności
 
liczb porządkowych otrzymujemy, że <math>\displaystyle a\subset b</math>. Wobec czego pokazaliśmy, że dla
 
liczb porządkowych otrzymujemy, że <math>\displaystyle a\subset b</math>. Wobec czego pokazaliśmy, że dla
dowolnego <math>\displaystyle b\in A</math> mamy <math>\displaystyle a \subset b</math>, co znaczy że <math>\displaystyle a</math> jest najmniejszym w sensie
+
dowolnego <math>\displaystyle b\in A</math> mamy <math>\displaystyle a \subset b</math>, co znaczy że, <math>\displaystyle a</math> jest najmniejszym w sensie
 
inkluzji elementem <math>\displaystyle A</math>.
 
inkluzji elementem <math>\displaystyle A</math>.
 
}}
 
}}
Linia 806: Linia 806:
 
{{dowod|||
 
{{dowod|||
  
Jeśli przedział początkowy jest zbiorem pustym to jest liczbą początkową.
+
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ą <math>\displaystyle X</math>. Niech
 
Zajmiemy się więc tylko niepustymi. Weźmy dowolną liczbę porządkową <math>\displaystyle X</math>. Niech
 
<math>\displaystyle A</math> będzie jej niepustym przedziałem początkowym. Pokażemy, że <math>\displaystyle A</math> jest liczbą
 
<math>\displaystyle A</math> będzie jej niepustym przedziałem początkowym. Pokażemy, że <math>\displaystyle A</math> jest liczbą
Linia 812: Linia 812:
  
 
# Własność pierwsza wynika natychmiast z faktu, że <math>\displaystyle A \subset X</math>.
 
# Własność pierwsza wynika natychmiast z faktu, że <math>\displaystyle A \subset X</math>.
# Weźmy dowolną liczbę <math>\displaystyle x\in A</math>. Skoro <math>\displaystyle X</math> jest liczbą porządkową to <math>\displaystyle x\subset
+
# Weźmy dowolną liczbę <math>\displaystyle x\in A</math>. Skoro <math>\displaystyle X</math> jest liczbą porządkową, to <math>\displaystyle x\subset
 
X</math>. Weźmy dowolny element <math>\displaystyle z\in x</math>, wynika stąd, że <math>\displaystyle z\subset x</math>, a więc skoro <math>\displaystyle A</math>
 
X</math>. Weźmy dowolny element <math>\displaystyle z\in x</math>, wynika stąd, że <math>\displaystyle z\subset x</math>, a więc skoro <math>\displaystyle A</math>
 
jest przedziałem początkowym to <math>\displaystyle z \in A</math>.
 
jest przedziałem początkowym to <math>\displaystyle z \in A</math>.
Linia 821: Linia 821:
  
 
Niech <math>\displaystyle X</math> będzie liczbą porządkową. Udowodnij, że dla dowolnych elementów <math>\displaystyle x,y
 
Niech <math>\displaystyle X</math> będzie liczbą porządkową. Udowodnij, że dla dowolnych elementów <math>\displaystyle x,y
\in X</math> jeśli <math>\displaystyle x\subsetneq y</math> to <math>\displaystyle x\in y</math>.   
+
\in X</math>, jeśli <math>\displaystyle x\subsetneq y</math>, to <math>\displaystyle x\in y</math>.   
 
}}</span>
 
}}</span>
  
Linia 831: Linia 831:
 
<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">   
  
Dla dowodu nie wprost przypuśćmy, że <math>\displaystyle x\subseteq y</math> oraz <math>\displaystyle x\notin y</math>. Ponieważ zbiór <math>\displaystyle X</math> jest liczbą porządkową to dla każdych dwóch różnych elementów <math>\displaystyle X</math>, jeden jest elementem drugiego. Ponieważ <math>\displaystyle x\neq y</math> i <math>\displaystyle x\notin y</math> to konieczne jest aby <math>\displaystyle y\in x</math> ale z faktu że <math>\displaystyle x\subset y</math> otrzymujemy <math>\displaystyle y\in y</math> co prowadzi do sprzeczności z aksjomatem regularności. Wobec tego <math>\displaystyle x</math> musi być elementem <math>\displaystyle y</math>.
+
Dla dowodu nie wprost przypuśćmy, że <math>\displaystyle x\subseteq y</math> oraz <math>\displaystyle x\notin y</math>. Ponieważ zbiór <math>\displaystyle X</math> jest liczbą porządkową, to dla każdych dwóch różnych elementów <math>\displaystyle X</math> jeden jest elementem drugiego. Ponieważ <math>\displaystyle x\neq y</math> i <math>\displaystyle x\notin y</math>, to konieczne jest, aby <math>\displaystyle y\in x</math>, ale z faktu, że <math>\displaystyle x\subset y</math>, otrzymujemy <math>\displaystyle y\in y</math>, co prowadzi do sprzeczności z aksjomatem regularności. Wobec tego <math>\displaystyle x</math> musi być elementem <math>\displaystyle y</math>.
 
</div></div>
 
</div></div>
  
Linia 849: Linia 849:
 
<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</math> będzie niepustą liczbą porządkową. Z aksjomatu regularności wynika, że w <math>\displaystyle X</math> istnieje element <math>\displaystyle x</math> dla którego <math>\displaystyle x \cap X=\emptyset</math>. Ponieważ jednak <math>\displaystyle X</math> jest liczbą porządkową to <math>\displaystyle x\subset X</math> wobec czego <math>\displaystyle x</math> musi być zbiorem pustym.
+
Niech <math>\displaystyle X</math> będzie niepustą liczbą porządkową. Z aksjomatu regularności wynika, że w <math>\displaystyle X</math> istnieje element <math>\displaystyle x</math>, dla którego <math>\displaystyle x \cap X=\emptyset</math>. Ponieważ jednak <math>\displaystyle X</math> jest liczbą porządkową, to <math>\displaystyle x\subset X</math>, wobec czego <math>\displaystyle x</math> musi być zbiorem pustym.
 
</div></div>
 
</div></div>
  
 
<span id="twierdzenie_4_8">{{twierdzenie|4.8.||
 
<span id="twierdzenie_4_8">{{twierdzenie|4.8.||
  
Dla każdych dwóch liczb porządkowych, jedna jest podzbiorem drugiej.
+
Dla każdych dwóch liczb porządkowych jedna jest podzbiorem drugiej.
 
}}</span>
 
}}</span>
  
 
{{dowod|||
 
{{dowod|||
  
Dowiedliśmy już że liczby porządkowe są dobrze uporządkowane przez inkluzję. Wobec tego z twierdzenia 3.6 (patrz [[#twierdzenie_3_6|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ą.
+
Dowiedliśmy już, że liczby porządkowe są dobrze uporządkowane przez inkluzję. Wobec tego z Twierdzenia 3.6 (patrz [[#twierdzenie_3_6|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 <math>\displaystyle X,Y</math> i przypuśćmy, że funkcja <math>\displaystyle f:X \rightarrow Y</math> jest
 
Weźmy liczby porządkowe <math>\displaystyle X,Y</math> i przypuśćmy, że funkcja <math>\displaystyle f:X \rightarrow Y</math> jest
podobieństwem pomiedzy porządkami <math>\displaystyle (X,\subset)</math> i <math>\displaystyle (Y,\subset)</math>. Pokażemy, że <math>\displaystyle f</math>
+
podobieństwem pomiędzy porządkami <math>\displaystyle (X,\subset)</math> i <math>\displaystyle (Y,\subset)</math>. Pokażemy, że <math>\displaystyle f</math>
 
jest identycznością.
 
jest identycznością.
  
Niech <math>\displaystyle A\subset X</math> będzie zbiorem <math>\displaystyle x\in X</math> dla których <math>\displaystyle f(x)\neq x</math>. Jeśli <math>\displaystyle A=
+
Niech <math>\displaystyle A\subset X</math> będzie zbiorem <math>\displaystyle x\in X</math>, dla których <math>\displaystyle f(x)\neq x</math>. Jeśli <math>\displaystyle A=
\emptyset</math> to funkcja <math>\displaystyle f</math> jest identycznością. Dla dowodu niewprost załóżmy więc, że
+
\emptyset</math>, to funkcja <math>\displaystyle f</math> jest identycznością. Dla dowodu niewprost załóżmy więc, że
<math>\displaystyle A\neq \emptyset</math>. Ponieważ <math>\displaystyle X</math> jest dobrze uporządkowany to w zbiorze <math>\displaystyle A</math> istnieje
+
<math>\displaystyle A\neq \emptyset</math>. Ponieważ <math>\displaystyle X</math> jest dobrze uporządkowany, to w zbiorze <math>\displaystyle A</math> istnieje
 
element najmniejszy, oznaczmy go przez <math>\displaystyle a</math>.
 
element najmniejszy, oznaczmy go przez <math>\displaystyle a</math>.
  
 
Pokażemy, że <math>\displaystyle f(a) \supset a</math>. Weźmy dowolny element <math>\displaystyle b\in a</math>, wtedy <math>\displaystyle b\subset a</math>  i
 
Pokażemy, że <math>\displaystyle f(a) \supset a</math>. Weźmy dowolny element <math>\displaystyle b\in a</math>, wtedy <math>\displaystyle b\subset a</math>  i
z monotoniczności <math>\displaystyle f</math> otrzymujemy <math>\displaystyle f(b) \subset f(a)</math> ponieważ jednak <math>\displaystyle b\notin A</math> to
+
z monotoniczności <math>\displaystyle f</math> otrzymujemy <math>\displaystyle f(b) \subset f(a)</math>, ponieważ jednak <math>\displaystyle b\notin A</math>, to
<math>\displaystyle f(b)=b</math> a więc <math>\displaystyle b\in f(a)</math>. Wobec dowolności wyboru <math>\displaystyle b</math> dostajemy <math>\displaystyle a\subset f(a)</math>.
+
<math>\displaystyle f(b)=b</math>, a więc <math>\displaystyle b\in f(a)</math>. Wobec dowolności wyboru <math>\displaystyle b</math> dostajemy <math>\displaystyle a\subset f(a)</math>.
  
Skoro <math>\displaystyle a\neq f(a)</math> to istnieje element <math>\displaystyle z\in f(a)</math> który nie należy do <math>\displaystyle a</math>. Ponieważ
+
Skoro <math>\displaystyle a\neq f(a)</math>, to istnieje element <math>\displaystyle z\in f(a)</math>, który nie należy do <math>\displaystyle a</math>. Ponieważ
<math>\displaystyle f(a)\in Y</math> to również <math>\displaystyle z\in Y</math>. Funkcja <math>\displaystyle f</math> jest bijekcją więc musi istnieć <math>\displaystyle b\in X</math>
+
<math>\displaystyle f(a)\in Y</math>, to również <math>\displaystyle z\in Y</math>. Funkcja <math>\displaystyle f</math> jest bijekcją, więc musi istnieć <math>\displaystyle b\in X</math>,
 
dla którego <math>\displaystyle f(b)=z</math>. Łatwo zauważyć, że <math>\displaystyle  b\neq a</math>, gdyż <math>\displaystyle f(b)=z\ \in f(a)</math>. Element
 
dla którego <math>\displaystyle f(b)=z</math>. Łatwo zauważyć, że <math>\displaystyle  b\neq a</math>, gdyż <math>\displaystyle f(b)=z\ \in f(a)</math>. Element
<math>\displaystyle b</math> nie może być elementem <math>\displaystyle a</math> gdyż wtedy <math>\displaystyle f(b)=b</math> i <math>\displaystyle z=b \in a</math>. Wobec tego <math>\displaystyle a</math> musi
+
<math>\displaystyle b</math> nie może być elementem <math>\displaystyle a</math>, gdyż wtedy <math>\displaystyle f(b)=b</math> i <math>\displaystyle z=b \in a</math>. Wobec tego <math>\displaystyle a</math> musi
 
być elementem <math>\displaystyle b</math>, ale wtedy <math>\displaystyle a \subset b</math> i z monotoniczności <math>\displaystyle f</math> dostajemy <math>\displaystyle f(a)
 
być elementem <math>\displaystyle b</math>, ale wtedy <math>\displaystyle a \subset b</math> i z monotoniczności <math>\displaystyle f</math> dostajemy <math>\displaystyle f(a)
 
\subset f(b)</math>, co jest sprzeczne z faktem <math>\displaystyle f(b) \in f(a)</math> (bo wtedy <math>\displaystyle f(b)\in f(b)</math>).
 
\subset f(b)</math>, co jest sprzeczne z faktem <math>\displaystyle f(b) \in f(a)</math> (bo wtedy <math>\displaystyle f(b)\in f(b)</math>).
Linia 888: Linia 888:
 
Powyższe twierdzenie mówi, że każde dwie liczby porządkowe są porównywalne przez
 
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
 
inkluzję. Przez analogię do liczb naturalnych używamy jednak dla liczb porządkowych
oznaczenia <math>\displaystyle x \leq y</math> zamiast <math>\displaystyle x\subset y</math>.
+
oznaczenia <math>\displaystyle x \leq y</math>, zamiast <math>\displaystyle x\subset y</math>.
  
 
Z powyższego twierdzenia wynika, że każdy zbiór liczb porządkowych jest uporządkowany
 
Z powyższego twierdzenia wynika, że każdy zbiór liczb porządkowych jest uporządkowany
Linia 901: Linia 901:
 
<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</math> będzie zbiorem liczb porządkowych, i niech <math>\displaystyle A</math> będzie niepustym podzbiorem <math>\displaystyle X</math>. Weźmy dowolny element <math>\displaystyle a\in A</math>. Oraz zbiór <math>\displaystyle A'=\{x\in A: x \in a\}</math>.
+
Niech <math>\displaystyle X</math> będzie zbiorem liczb porządkowych, i niech <math>\displaystyle A</math> będzie niepustym podzbiorem <math>\displaystyle X</math>. Weźmy dowolny element <math>\displaystyle a\in A</math> oraz zbiór <math>\displaystyle A'=\{x\in A: x \in a\}</math>.
Rozważymy dwa przypadki
+
Rozważymy dwa przypadki:
  
# Jeśli zbiór <math>\displaystyle A'</math> jest pusty to dla dowolnego elementu <math>\displaystyle b\in A</math> mamy <math>\displaystyle b\notin a</math> a więc <math>\displaystyle b \supset a</math> (ponieważ <math>\displaystyle X</math> jest uporządkowany liniowo przez inkluzję, a <math>\displaystyle b\subsetneq a</math> prowadziłoby do <math>\displaystyle b\in a</math>). Wtedy element <math>\displaystyle a</math> jest elementem najmniejszym <math>\displaystyle A</math>.
+
# Jeśli zbiór <math>\displaystyle A'</math> jest pusty, to dla dowolnego elementu <math>\displaystyle b\in A</math> mamy <math>\displaystyle b\notin a</math>, a więc <math>\displaystyle b \supset a</math> (ponieważ <math>\displaystyle X</math> jest uporządkowany liniowo przez inkluzję, a <math>\displaystyle b\subsetneq a</math> prowadziłoby do <math>\displaystyle b\in a</math>). Wtedy element <math>\displaystyle a</math> jest elementem najmniejszym <math>\displaystyle A</math>.
# Jeśli zbiór <math>\displaystyle A'</math> jesteś niepusty to ponieważ jest podzbiorem liczby porządkowej <math>\displaystyle a</math> to istnieje w nim element najmniejszy, oznaczmy go przez <math>\displaystyle c</math>. Wtedy dla dowolnego elementu <math>\displaystyle b\in A</math>. Jeśli <math>\displaystyle b\in A'</math> to <math>\displaystyle c\subset b</math>. W przeciwnym przypadku <math>\displaystyle b \notin a</math>. Wtedy <math>\displaystyle b \supset a</math>, i skoro <math>\displaystyle c\in a \subset b</math> to <math>\displaystyle c \subset b</math>. Wynika stąd, że <math>\displaystyle c</math> jest najmniejszym elementem rodziny <math>\displaystyle A</math>.
+
# Jeśli zbiór <math>\displaystyle A'</math> jesteś niepusty, to ponieważ jest podzbiorem liczby porządkowej <math>\displaystyle a</math>, to istnieje w nim element najmniejszy, oznaczmy go przez <math>\displaystyle c</math>. Wtedy dla dowolnego elementu <math>\displaystyle b\in A</math>. Jeśli <math>\displaystyle b\in A'</math>, to <math>\displaystyle c\subset b</math>. W przeciwnym przypadku <math>\displaystyle b \notin a</math>. Wtedy <math>\displaystyle b \supset a</math> i skoro <math>\displaystyle c\in a \subset b</math>, to <math>\displaystyle c \subset b</math>. Wynika stąd, że <math>\displaystyle c</math> jest najmniejszym elementem rodziny <math>\displaystyle A</math>.
  
 
</div></div>
 
</div></div>
Linia 920: Linia 920:
 
dobrze uporządkowany, przez inkluzję.
 
dobrze uporządkowany, przez inkluzję.
  
# Niech <math>\displaystyle x,y</math> będą różnymi elementami <math>\displaystyle X</math>. Wtedy <math>\displaystyle x\subsetneq y</math> lub <math>\displaystyle y\subsetneq x</math>. Z ćwiczenia 4.6 (patrz [[#cwiczenie_4_6|ćwiczenie 4.6]]) wynika, że w pierwszym przypadku mamy <math>\displaystyle x \in y</math> a w drugim <math>\displaystyle y\in x</math>. Więc zbiór <math>\displaystyle X</math> spełnia pierwszy z warunków bycia liczbą porządkową.
+
# Niech <math>\displaystyle x,y</math> będą różnymi elementami <math>\displaystyle X</math>. Wtedy <math>\displaystyle x\subsetneq y</math> lub <math>\displaystyle y\subsetneq x</math>. Z Ćwiczenia 4.6 (patrz [[#cwiczenie_4_6|Ćwiczenie 4.6]]) wynika, że w pierwszym przypadku mamy <math>\displaystyle x \in y</math>, a w drugim <math>\displaystyle y\in x</math>. Więc zbiór <math>\displaystyle X</math> spełnia pierwszy z warunków bycia liczbą porządkową.
# Weźmy dowolny element <math>\displaystyle x</math> ze zbioru <math>\displaystyle X</math>. Z faktu 4.2 (patrz [[#fakt_4_2|fakt 4.2.]]) wiemy, że każdy element <math>\displaystyle y</math> należący do zbioru <math>\displaystyle x</math> jest liczbą porządkową. Ponieważ do <math>\displaystyle X</math> należą wszystkie liczby porządkowe to <math>\displaystyle x\subset X</math>. A więc <math>\displaystyle X</math> spełnia drugi warunek bycia liczbą porządkową.
+
# Weźmy dowolny element <math>\displaystyle x</math> ze zbioru <math>\displaystyle X</math>. Z Faktu 4.2 (patrz [[#fakt_4_2|Fakt 4.2.]]) wiemy, że każdy element <math>\displaystyle y</math> należący do zbioru <math>\displaystyle x</math> jest liczbą porządkową. Ponieważ do <math>\displaystyle X</math> należą wszystkie liczby porządkowe, to <math>\displaystyle x\subset X</math>. A więc <math>\displaystyle X</math> spełnia drugi warunek bycia liczbą porządkową.
  
 
Wobec powyższych faktów zbiór <math>\displaystyle X</math> jest liczbą porządkową, a więc musi być własnym
 
Wobec powyższych faktów zbiór <math>\displaystyle X</math> jest liczbą porządkową, a więc musi być własnym
Linia 938: Linia 938:
 
{{dowod|||
 
{{dowod|||
  
Dla dowodu nie wprost załóżmy, że istnieje dobry porządek <math>\displaystyle (X,\leq)</math> który nie jest podobny do żadnej liczby porządkowej. Z twierdzenia 3.6 (patrz [[#twierdzenie_3_6|twiedzenie 3.6.]]) wynika, że każda liczba porządkowa jest podobna do jakiegoś przedziału początkowego <math>\displaystyle X</math>. Używając aksjomatu zastępowania z <u>'''Wykladu 4</u>''' pokażemy, że istnieje wtedy zbiór liczb porządkowych.
+
Dla dowodu nie wprost załóżmy, że istnieje dobry porządek <math>\displaystyle (X,\leq)</math>, który nie jest podobny do żadnej liczby porządkowej. Z Twierdzenia 3.6 (patrz [[#twierdzenie_3_6|Twiedzenie 3.6.]]) wynika, że każda liczba porządkowa jest podobna do jakiegoś przedziału początkowego <math>\displaystyle X</math>. Używając aksjomatu zastępowania z (patrz [[Logika i teoria mnogości/Wykład 4: Teoria mnogości ZFC. Operacje na zbiorach#Schemat_Aksjomatu_Zastępowania|Wykład 4, Aksjomat Zastępowania]]) pokażemy, że istnieje wtedy zbiór liczb porządkowych.
  
Niech <math>\displaystyle \phi(o,p)</math> będzie formułą o zmiennych wolnych <math>\displaystyle o,p</math> która będzie spełniona
+
Niech <math>\displaystyle \phi(o,p)</math> będzie formułą o zmiennych wolnych <math>\displaystyle o,p</math>, która będzie spełniona
 
wtedy i tylko wtedy, gdy <math>\displaystyle o</math> jest dobrym porządkiem, <math>\displaystyle p</math> jest liczbą porządkową i <math>\displaystyle o</math>
 
wtedy i tylko wtedy, gdy <math>\displaystyle o</math> jest dobrym porządkiem, <math>\displaystyle p</math> jest liczbą porządkową i <math>\displaystyle o</math>
 
jest podobne do <math>\displaystyle p</math>. Nie jest trudno napisać taką formułę, ale nie jest ona krótka,
 
jest podobne do <math>\displaystyle p</math>. Nie jest trudno napisać taką formułę, ale nie jest ona krótka,
 
dlatego ten fragment dowodu pozostawiamy czytelnikowi. Ponieważ dwie liczby
 
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 <math>\displaystyle o</math>
+
porządkowe są podobne wtedy i tylko wtedy, gdy są równe, to do każdy dobry porządek <math>\displaystyle o</math>
 
jest podobny do co najwyżej jednej liczby porządkowej. Wobec tego dla dowolnego <math>\displaystyle o</math>
 
jest podobny do co najwyżej jednej liczby porządkowej. Wobec tego dla dowolnego <math>\displaystyle o</math>
 
można dobrać co nawyżej jedno <math>\displaystyle p</math> takie, aby formuła <math>\displaystyle \phi(o,p)</math> była prawdziwa. To
 
można dobrać co nawyżej jedno <math>\displaystyle p</math> takie, aby formuła <math>\displaystyle \phi(o,p)</math> była prawdziwa. To
 
znaczy że dla formuły <math>\displaystyle \phi(o,p)</math> przesłanka aksjomatu zastępowania jest spełniona.
 
znaczy że dla formuły <math>\displaystyle \phi(o,p)</math> przesłanka aksjomatu zastępowania jest spełniona.
Wobec tego prawdą jest również
+
Wobec tego prawdą jest również:
  
 
<center><math>\displaystyle \forall_x \exists_y \forall_p (p\in y \Leftrightarrow (\exists_o o\in x \wedge \phi(o,p))
 
<center><math>\displaystyle \forall_x \exists_y \forall_p (p\in y \Leftrightarrow (\exists_o o\in x \wedge \phi(o,p))
Linia 955: Linia 955:
 
Biorąc za <math>\displaystyle x</math> zbiór odcinków początkowych <math>\displaystyle X</math>, dostaniemy, że istnieje zbiór <math>\displaystyle y</math>
 
Biorąc za <math>\displaystyle x</math> zbiór odcinków początkowych <math>\displaystyle X</math>, dostaniemy, że istnieje zbiór <math>\displaystyle y</math>
 
taki, że <math>\displaystyle p</math> należy do <math>\displaystyle y</math> wtedy i tylko wtedy, gdy istnieje <math>\displaystyle o</math> będący odcinkiem
 
taki, że <math>\displaystyle p</math> należy do <math>\displaystyle y</math> wtedy i tylko wtedy, gdy istnieje <math>\displaystyle o</math> będący odcinkiem
początkowym <math>\displaystyle X</math> dla którego prawdziwa jest formuła <math>\displaystyle \phi(o,p)</math>. Oznacza to dokładnie
+
początkowym <math>\displaystyle X</math>, dla którego prawdziwa jest formuła <math>\displaystyle \phi(o,p)</math>. Oznacza to dokładnie,
 
że istnieje zbiór wszystkich liczb porządkowych podobnych do przedziałów początkowych
 
że istnieje zbiór wszystkich liczb porządkowych podobnych do przedziałów początkowych
 
<math>\displaystyle X</math>. Skoro założyliśmy, że każda liczba porządkowa jest podobna do pewnego przedziału
 
<math>\displaystyle X</math>. Skoro założyliśmy, że każda liczba porządkowa jest podobna do pewnego przedziału
 
początkowego <math>\displaystyle X</math>, to istnieje zbiór liczb porządkowych. Otrzymaliśmy więc sprzeczność
 
początkowego <math>\displaystyle X</math>, to istnieje zbiór liczb porządkowych. Otrzymaliśmy więc sprzeczność
z twierdzeniem 4.10 (patrz [[#twierdzenie_4_10|twierdzenie 4.10.]]).
+
z Twierdzeniem 4.10 (patrz [[#twierdzenie_4_10|Twierdzenie 4.10.]]).
 
}}
 
}}
  
Linia 965: Linia 965:
 
naszym podejściu <math>\displaystyle \omega</math> jest po prostu zbiorem <math>\displaystyle \mathbb{N}</math>, który jest dobrze
 
naszym podejściu <math>\displaystyle \omega</math> jest po prostu zbiorem <math>\displaystyle \mathbb{N}</math>, który jest dobrze
 
uporządkowany przez inkluzję. Przyjęło się jednak używać oznaczenia <math>\displaystyle \omega</math> dla
 
uporządkowany przez inkluzję. Przyjęło się jednak używać oznaczenia <math>\displaystyle \omega</math> dla
podkreślenia, że mówimy o dobrym uporządkowaniu. Będziemy mówić że zbiór częściowo
+
podkreślenia, że mówimy o dobrym uporządkowaniu. Będziemy mówić, że zbiór częściowo
uporządkowany jest ''typu'' <math>\displaystyle \omega</math> jeśli jest podobny do
+
uporządkowany jest ''typu'' <math>\displaystyle \omega</math>, jeśli jest podobny do
 
<math>\displaystyle (\mathbb{N},\subset_\mathbb{N})</math>. Podobnie dla dowolnej innej liczby porządkowej <math>\displaystyle x</math> powiemy, że
 
<math>\displaystyle (\mathbb{N},\subset_\mathbb{N})</math>. Podobnie dla dowolnej innej liczby porządkowej <math>\displaystyle x</math> powiemy, że
zbiór częściowo uporządkowany jest typu <math>\displaystyle x</math> jeśli jest podobny do <math>\displaystyle (x,\subset_x)</math>
+
zbiór częściowo uporządkowany jest typu <math>\displaystyle x</math>, jeśli jest podobny do <math>\displaystyle (x,\subset_x)</math>
  
 
{{cwiczenie|4.12||
 
{{cwiczenie|4.12||
Linia 975: Linia 975:
 
(B,\leq_B)</math> następujące zbiory są dobrymi porządkami:
 
(B,\leq_B)</math> następujące zbiory są dobrymi porządkami:
  
# <math>\displaystyle (A,\leq_A) \oplus (B,\leq_B) =(A\cup B, \leq_A \cup \leq_B \cup A \times B)</math> czyli na zbiorach <math>\displaystyle A,B</math> porządki są takie jak w zbiorach wyjściowych, a do tego każdy element zbioru <math>\displaystyle A</math> jest mniejszy od każdego elementu zbioru <math>\displaystyle B</math>.
+
# <math>\displaystyle (A,\leq_A) \oplus (B,\leq_B) =(A\cup B, \leq_A \cup \leq_B \cup A \times B)</math>, czyli na zbiorach <math>\displaystyle A,B</math> porządki są takie, jak w zbiorach wyjściowych, a do tego każdy element zbioru <math>\displaystyle A</math> jest mniejszy od każdego elementu zbioru <math>\displaystyle B</math>.
 
# <math>\displaystyle (A,\leq_A) \otimes (B,\leq_B)= (A \times B, \leq_{A \times B})</math>, gdzie <math>\displaystyle \leq_{A \times B}</math> jest porządkiem leksykograficznym, czyli
 
# <math>\displaystyle (A,\leq_A) \otimes (B,\leq_B)= (A \times B, \leq_{A \times B})</math>, gdzie <math>\displaystyle \leq_{A \times B}</math> jest porządkiem leksykograficznym, czyli
  
<center><math>\displaystyle (a_1,b_1) \leq_{A \times B} (a_2,b_2) \Leftrightarrow (a_1<_A a_2) \vee (a_1=a_2\wedge b_1\leq_A b_2)
+
<center><math>\displaystyle (a_1,b_1) \leq_{A \times B} (a_2,b_2) \Leftrightarrow (a_1<_A a_2) \vee (a_1=a_2\wedge b_1\leq_A b_2).
 
</math></center>
 
</math></center>
  
Linia 984: Linia 984:
  
 
<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. Weźmy dowolny niepusty podzbiór <math>\displaystyle X\subset A \cup B</math>. Pokażemy, że istnieje w nim element najmniejszy. Rozważmy dwa przypadki.
+
: 1. Weźmy dowolny niepusty podzbiór <math>\displaystyle X\subset A \cup B</math>. Pokażemy, że istnieje w nim element najmniejszy. Rozważmy dwa przypadki:
  
: a) Jeśli <math>\displaystyle X\cap A \neq \emptyset</math> to w tym zbiorze istnieje element najmniejszy, oznaczmy go przez <math>\displaystyle x_0</math>. Element ten jest również najmniejszym elementem w zbiorze <math>\displaystyle X</math>, gdyż jest mniejszy od wszystkich elementów <math>\displaystyle X\cap A</math> oraz należy do <math>\displaystyle A</math> a więc z definicji porządku na <math>\displaystyle A\cup B</math> jest mniejszy od wszystkich elementów z <math>\displaystyle B</math>, w szczególności od elementów z <math>\displaystyle X\cap B</math>.
+
: a) Jeśli <math>\displaystyle X\cap A \neq \emptyset</math>, to w tym zbiorze istnieje element najmniejszy, oznaczmy go przez <math>\displaystyle x_0</math>. Element ten jest również najmniejszym elementem w zbiorze <math>\displaystyle X</math>, gdyż jest mniejszy od wszystkich elementów <math>\displaystyle X\cap A</math> oraz należy do <math>\displaystyle A</math>, a więc z definicji porządku na <math>\displaystyle A\cup B</math> jest mniejszy od wszystkich elementów z <math>\displaystyle B</math>, w szczególności od elementów z <math>\displaystyle X\cap B</math>.
  
: b) Jeśli <math>\displaystyle X\cap A = \emptyset</math> to <math>\displaystyle X\subset B</math> i wobec tego istnieje w <math>\displaystyle X</math> element który jest najmniejszy w <math>\displaystyle X</math> względem porządku <math>\displaystyle \leq_B</math>. Element ten jest najmniejszy w całym zbiorze <math>\displaystyle X</math> ponieważ porządek na całym zbiorze <math>\displaystyle A\cup B</math> jest rozszerzeniem porządku na <math>\displaystyle B</math> tak, że wszystkie elementy zbioru <math>\displaystyle A</math> są mniejsze od każdego elementu zbioru <math>\displaystyle B</math>.
+
: b) Jeśli <math>\displaystyle X\cap A = \emptyset</math>, to <math>\displaystyle X\subset B</math> i wobec tego istnieje w <math>\displaystyle X</math> element, który jest najmniejszy w <math>\displaystyle X</math>, względem porządku <math>\displaystyle \leq_B</math>. Element ten jest najmniejszy w całym zbiorze <math>\displaystyle X</math>, ponieważ porządek na całym zbiorze <math>\displaystyle A\cup B</math> jest rozszerzeniem porządku na <math>\displaystyle B</math> tak, że wszystkie elementy zbioru <math>\displaystyle A</math> są mniejsze od każdego elementu zbioru <math>\displaystyle B</math>.
  
: 2. Weźmy dowolny niepusty podzbiór <math>\displaystyle X\subset A \times B</math>. Pokażemy, że istnieje w nim element najmniejszy. Rozważmy zbiór <math>\displaystyle X_L</math> (jest to zbiór składający się z lewych współrzędnych par ze zbioru <math>\displaystyle X</math>).  Zbiór ten jest podzbiorem <math>\displaystyle A</math> i ponieważ <math>\displaystyle X</math> jest niepusty to <math>\displaystyle X_L</math> również. Skoro <math>\displaystyle A</math> jest dobrze uporządkowany relacją <math>\displaystyle \leq_A</math> to w <math>\displaystyle X_L</math> istnieje element najmniejszy względem <math>\displaystyle \leq_A</math> oznaczmy go przez <math>\displaystyle a_0</math>. Rozważmy teraz zbiór <math>\displaystyle B_0=\{b\in B: (a_0,b)\in X\}</math>. Ponieważ <math>\displaystyle a_0\in X_L</math> to zbiór <math>\displaystyle B_0</math> musi być niepusty. <math>\displaystyle B_0</math> jest podzbiorem <math>\displaystyle B</math> wobec czego musi istnieć w tym zbiorze element najmniejszy, oznaczmy go przez <math>\displaystyle b_0</math>. Pokażemy, że <math>\displaystyle (a_0,b_0)</math> jest najmniejszym elementem zbioru <math>\displaystyle X</math>. Weźmy dowolny element <math>\displaystyle (a_1,b_1)</math> zbioru  <math>\displaystyle X</math>. Ponieważ <math>\displaystyle a_0</math> jest najmniejszy w <math>\displaystyle X_L</math> to mamy <math>\displaystyle a_0 \leq_A a_1</math>. Jeśli <math>\displaystyle a_0 < a_1</math> to z definicji porządku <math>\displaystyle \leq_{A \times B}</math> otrzymujemy <math>\displaystyle (a_0,b_0) \leq_{A \times B} (a_1,b_1)</math>. W przeciwnym przypadku mamy <math>\displaystyle a_0=a_1</math>, wtedy <math>\displaystyle b_1 \in B_0</math> i ponieważ <math>\displaystyle b_0</math> jest najmniejszy w tym zbiorze to otrzymujemy <math>\displaystyle b_0 \leq_b b_1</math>. Wobec tego zgodnie z definicją <math>\displaystyle \leq_{A \times B}</math> mamy <math>\displaystyle (a_0,b_0) \leq_{A \times B} (a_1,b_1)</math>. Wynika stąd, że element <math>\displaystyle (a_0,b_0)</math> jest najmniejszy w <math>\displaystyle X</math>. Wobec dowolności wybory <math>\displaystyle X</math> otrzymujemy, że zbiór <math>\displaystyle A\times B</math> jest dobrze uporządkowany relacją <math>\displaystyle \leq_{A \times B}</math>.
+
: 2. Weźmy dowolny niepusty podzbiór <math>\displaystyle X\subset A \times B</math>. Pokażemy, że istnieje w nim element najmniejszy. Rozważmy zbiór <math>\displaystyle X_L</math> (jest to zbiór składający się z lewych współrzędnych par ze zbioru <math>\displaystyle X</math>).  Zbiór ten jest podzbiorem <math>\displaystyle A</math> i ponieważ <math>\displaystyle X</math> jest niepusty, to <math>\displaystyle X_L</math> również. Skoro <math>\displaystyle A</math> jest dobrze uporządkowany relacją <math>\displaystyle \leq_A</math>, to w <math>\displaystyle X_L</math> istnieje element najmniejszy względem <math>\displaystyle \leq_A</math> oznaczmy go przez <math>\displaystyle a_0</math>. Rozważmy teraz zbiór <math>\displaystyle B_0=\{b\in B: (a_0,b)\in X\}</math>. Ponieważ <math>\displaystyle a_0\in X_L</math>, to zbiór <math>\displaystyle B_0</math> musi być niepusty. <math>\displaystyle B_0</math> jest podzbiorem <math>\displaystyle B</math>, wobec czego musi istnieć w tym zbiorze element najmniejszy, oznaczmy go przez <math>\displaystyle b_0</math>. Pokażemy, że <math>\displaystyle (a_0,b_0)</math> jest najmniejszym elementem zbioru <math>\displaystyle X</math>. Weźmy dowolny element <math>\displaystyle (a_1,b_1)</math> zbioru  <math>\displaystyle X</math>. Ponieważ <math>\displaystyle a_0</math> jest najmniejszy w <math>\displaystyle X_L</math>, to mamy <math>\displaystyle a_0 \leq_A a_1</math>. Jeśli <math>\displaystyle a_0 < a_1</math>, to z definicji porządku <math>\displaystyle \leq_{A \times B}</math> otrzymujemy <math>\displaystyle (a_0,b_0) \leq_{A \times B} (a_1,b_1)</math>. W przeciwnym przypadku mamy <math>\displaystyle a_0=a_1</math>, wtedy <math>\displaystyle b_1 \in B_0</math> i ponieważ <math>\displaystyle b_0</math> jest najmniejszy w tym zbiorze, to otrzymujemy <math>\displaystyle b_0 \leq_b b_1</math>. Wobec tego zgodnie z definicją <math>\displaystyle \leq_{A \times B}</math> mamy <math>\displaystyle (a_0,b_0) \leq_{A \times B} (a_1,b_1)</math>. Wynika stąd, że element <math>\displaystyle (a_0,b_0)</math> jest najmniejszy w <math>\displaystyle X</math>. Wobec dowolności wybory <math>\displaystyle X</math> otrzymujemy, że zbiór <math>\displaystyle A\times B</math> jest dobrze uporządkowany relacją <math>\displaystyle \leq_{A \times B}</math>.
  
 
</div></div>
 
</div></div>
  
Powyższe konstrukcje łatwo zaadaptować do operowania na zbiorach które nie są
+
Powyższe konstrukcje łatwo zaadaptować do operowania na zbiorach, które nie są
rozłączne. W miejsce <math>\displaystyle A</math> wystarczy wziąć zbiór <math>\displaystyle \{0\} \times A</math> a w miejsce <math>\displaystyle B</math> zbiór
+
rozłączne. W miejsce <math>\displaystyle A</math> wystarczy wziąć zbiór <math>\displaystyle \{0\} \times A</math>, a w miejsce <math>\displaystyle B</math> zbiór
 
<math>\displaystyle \{1\} \times B</math>. Wtedy będziemy mieli zagwarantowaną rozłączność. Porządek na tak
 
<math>\displaystyle \{1\} \times B</math>. Wtedy będziemy mieli zagwarantowaną rozłączność. Porządek na tak
 
zmienionych zbiorach łatwo przenieść z wyjściowych zbiorów poprzez naturalną bijekcję
 
zmienionych zbiorach łatwo przenieść z wyjściowych zbiorów poprzez naturalną bijekcję
pomiędzy nimi (czyli <math>\displaystyle [(0,a_1) \leq_{\{0\} \times A }(0,a_2)] \Leftrightarrow a_1\leq_A a2</math>). W
+
pomiędzy nimi (czyli <math>\displaystyle [(0,a_1) \leq_{\{0\} \times A }(0,a_2)] \Leftrightarrow a_1\leq_A a_2</math>). W
dalszej części będziemy sie posługiwać tak zmodyfikowanymi konstrukcjami nie dbając o
+
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.
 
rozłączność zbiorów. Zdefiniujemy  teraz arytmetykę na liczbach porządkowych.
  
 
{{definicja|4.13.||
 
{{definicja|4.13.||
  
Niech <math>\displaystyle a,b</math> będą liczbami porządkowymi. Wtedy
+
Niech <math>\displaystyle a,b</math> będą liczbami porządkowymi. Wtedy:
 
# Liczbę porządkową podobną do  <math>\displaystyle (a,\subset) \oplus (b,\subset)</math> będziemy oznaczać przez <math>\displaystyle a+b</math>.
 
# Liczbę porządkową podobną do  <math>\displaystyle (a,\subset) \oplus (b,\subset)</math> będziemy oznaczać przez <math>\displaystyle a+b</math>.
 
# Liczbę porządkową podobną do  <math>\displaystyle (a,\subset) \otimes (b,\subset)</math> będziemy oznaczać przez <math>\displaystyle a \cdot b</math>.
 
# Liczbę porządkową podobną do  <math>\displaystyle (a,\subset) \otimes (b,\subset)</math> będziemy oznaczać przez <math>\displaystyle a \cdot b</math>.
Linia 1010: Linia 1010:
 
{{cwiczenie|4.14||
 
{{cwiczenie|4.14||
  
Sprawdź czy prawdziwe są następujące własności liczb porządkowych
+
Sprawdź, czy prawdziwe są następujące własności liczb porządkowych:
# <math>\displaystyle 1+\omega= \omega</math>
+
# <math>\displaystyle 1+\omega= \omega</math>.
# <math>\displaystyle \omega +1 \neq \omega</math>
+
# <math>\displaystyle \omega +1 \neq \omega</math>.
# <math>\displaystyle \omega + \omega = 2 \cdot \omega</math>
+
# <math>\displaystyle \omega + \omega = 2 \cdot \omega</math>.
# <math>\displaystyle a < b \Rightarrow a+c < b+c</math>
+
# <math>\displaystyle a < b \Rightarrow a+c < b+c</math>.
# <math>\displaystyle b+a= c+a \Rightarrow b=c</math>
+
# <math>\displaystyle b+a= c+a \Rightarrow b=c</math>.
# <math>\displaystyle a+b= a+c \Rightarrow b=c</math>
+
# <math>\displaystyle a+b= a+c \Rightarrow b=c</math>.
# <math>\displaystyle a \cdot b= a \cdot c \Rightarrow b=c</math>
+
# <math>\displaystyle a \cdot b= a \cdot c \Rightarrow b=c</math>.
# <math>\displaystyle x \cdot y = y \cdot x</math>
+
# <math>\displaystyle x \cdot y = y \cdot x</math>.
  
 
}}
 
}}
Linia 1025: Linia 1025:
 
: 1. Równość jest prawdziwa. Zgodnie z definicją dodawania <math>\displaystyle 1+\omega</math> to liczba porządkowa odpowiadająca zbiorowi liczb naturalnych z dodanym jednym elementem jako
 
: 1. Równość jest prawdziwa. Zgodnie z definicją dodawania <math>\displaystyle 1+\omega</math> to liczba porządkowa odpowiadająca zbiorowi liczb naturalnych z dodanym jednym elementem jako
 
najmniejszym, oznaczymy go przez <math>\displaystyle \bot</math>. Łatwo zauważyć, że funkcja
 
najmniejszym, oznaczymy go przez <math>\displaystyle \bot</math>. Łatwo zauważyć, że funkcja
<math>\displaystyle f:\mathbb{N}\cup\{\bot\} \rightarrow \mathbb{N}</math> określona w następujący sposób
+
<math>\displaystyle f:\mathbb{N} \cup \{\bot \} \rightarrow \mathbb{N}</math> określona w następujący sposób:
  
<math>f(\bot) = 0 \\ F(n)& = n+1, \quad dla \quad \displaystyle n\in \mathbb{N}</math>
+
<math>\begin{align}
 +
f(\bot) &= 0 \\  
 +
F(n) &= n+1, \quad dla \quad \displaystyle n\in \mathbb{N}
 +
\end{align}
 +
</math>
  
 
: jest monotoniczną bijekcją. Wobec tego częściowe porządki są podobne, a więc odpowiadają jednej liczbie porządkowej <math>\displaystyle \omega</math>.
 
: jest monotoniczną bijekcją. Wobec tego częściowe porządki są podobne, a więc odpowiadają jednej liczbie porządkowej <math>\displaystyle \omega</math>.
Linia 1033: Linia 1037:
 
: 2. Równość nie jest prawdziwa. Łatwo zauważyć, że w porządku <math>\displaystyle \omega+1</math> istnieje element największy, a w <math>\displaystyle \omega</math> nie.
 
: 2. Równość nie jest prawdziwa. Łatwo zauważyć, że w porządku <math>\displaystyle \omega+1</math> istnieje element największy, a w <math>\displaystyle \omega</math> nie.
  
: 3. Równość jest prawdziwa. Zgodnie z rozszerzeniem konstrukcji z ćwiczenia na zbiory które nie muszą być rozłączne, porządki <math>\displaystyle (\omega,\leq) \oplus (\omega,\leq)</math> oraz <math>\displaystyle (\{0,1\},\leq) \times (\omega,\leq)</math> są dokładnie identyczne, a więc odpowiadają tej samej liczbie porządkowej.
+
: 3. Równość jest prawdziwa. Zgodnie z rozszerzeniem konstrukcji z ćwiczenia na zbiory, które nie muszą być rozłączne, porządki <math>\displaystyle (\omega,\leq) \oplus (\omega,\leq)</math> oraz <math>\displaystyle (\{0,1\},\leq) \times (\omega,\leq)</math> są dokładnie identyczne, a więc odpowiadają tej samej liczbie porządkowej.
  
: 4. Implikacja nie jest prawdziwa. Na przykład mamy <math>\displaystyle 0<1</math> ale nieprawda, że <math>\displaystyle 0+\omega < 1+\omega</math>, gdyż te liczby są równe.
+
: 4. Implikacja nie jest prawdziwa. Na przykład mamy <math>\displaystyle 0<1</math>, ale nieprawda, że <math>\displaystyle 0+\omega < 1+\omega</math>, gdyż te liczby są równe.
  
: 5. Implikacja nie jest prawdziwa. Sytuacja jest analogiczna do poprzedniego punktu. Mamy <math>\displaystyle 0+\omega=1+\omega</math>, ale nie prawda, że <math>\displaystyle 0=1</math>.
+
: 5. Implikacja nie jest prawdziwa. Sytuacja jest analogiczna do poprzedniego punktu. Mamy <math>\displaystyle 0+\omega=1+\omega</math>, ale nieprawda, że <math>\displaystyle 0=1</math>.
  
: 6. Implikacja jest prawdziwa. Przypuśćmy, że <math>\displaystyle a,b,c</math> są liczbami porządkowymi, takimi że <math>\displaystyle a+b= a+c</math>. Niech <math>\displaystyle (A,\leq_A),(B,\leq_B),(C,\leq_C)</math> będą rozłącznymi porządkami podobnymi odpowiednio do <math>\displaystyle (a,\subset),(b,\subset),(c,\subset)</math>. Równość <math>\displaystyle a+b=a+c</math> implikuje, że porządki <math>\displaystyle (A,\leq_A)\oplus (B,\leq_B)</math> i <math>\displaystyle (A,\leq_A)\oplus(C,\leq_C)</math> są podobne. Niech <math>\displaystyle f</math> będzie monotoniczną bijekcją z <math>\displaystyle A\cup B</math> w <math>\displaystyle A\cup C</math>. Ponieważ żaden dobry porządek nie jest podobny do swojego istotnego przedziału początkowego to <math>\displaystyle \vec{f}(A)=A</math>, wobec tego <math>\displaystyle \vec{f}(B)=C</math>. Skutkiem tego <math>\displaystyle f\cap B\times C</math> jest podobieństwem pomiędzy porządkami <math>\displaystyle (B,\leq_B), (C,\leq_C)</math>. W efekcie odpowiadające im liczby porządkowe są równe, czyli <math>\displaystyle b=c</math>.
+
: 6. Implikacja jest prawdziwa. Przypuśćmy, że <math>\displaystyle a,b,c</math> są liczbami porządkowymi, takimi że <math>\displaystyle a+b= a+c</math>. Niech <math>\displaystyle (A,\leq_A),(B,\leq_B),(C,\leq_C)</math> będą rozłącznymi porządkami podobnymi odpowiednio do <math>\displaystyle (a,\subset),(b,\subset),(c,\subset)</math>. Równość <math>\displaystyle a+b=a+c</math> implikuje, że porządki <math>\displaystyle (A,\leq_A)\oplus (B,\leq_B)</math> i <math>\displaystyle (A,\leq_A)\oplus(C,\leq_C)</math> są podobne. Niech <math>\displaystyle f</math> będzie monotoniczną bijekcją z <math>\displaystyle A\cup B</math> w <math>\displaystyle A\cup C</math>. Ponieważ żaden dobry porządek nie jest podobny do swojego istotnego przedziału początkowego, to <math>\displaystyle \vec{f}(A)=A</math>, wobec tego <math>\displaystyle \vec{f}(B)=C</math>. Skutkiem tego <math>\displaystyle f\cap B\times C</math> jest podobieństwem pomiędzy porządkami <math>\displaystyle (B,\leq_B), (C,\leq_C)</math>. W efekcie odpowiadające im liczby porządkowe są równe, czyli <math>\displaystyle b=c</math>.
  
: 7. Implikacja nie jest prawdziwa. Pokażemy, że <math>\displaystyle \omega \cdot 2= \omega \cdot 1</math> podczas gdy <math>\displaystyle 1\neq 2</math>. Ponieważ <math>\displaystyle \omega \cdot 1 =\omega</math> to pokażemy, że również <math>\displaystyle \omega \cdot 2=\omega</math>. Zdefiniujmy funkcję <math>\displaystyle f:\omega \times 2 \rightarrow \omega</math> następująco
+
: 7. Implikacja nie jest prawdziwa. Pokażemy, że <math>\displaystyle \omega \cdot 2= \omega \cdot 1</math>, podczas gdy <math>\displaystyle 1\neq 2</math>. Ponieważ <math>\displaystyle \omega \cdot 1 =\omega</math>, to pokażemy, że również <math>\displaystyle \omega \cdot 2=\omega</math>. Zdefiniujmy funkcję <math>\displaystyle f:\omega \times 2 \rightarrow \omega</math> następująco:
  
 
<center><math>\displaystyle f(n,x)= 2 \cdot n+x.
 
<center><math>\displaystyle f(n,x)= 2 \cdot n+x.
 
</math></center>
 
</math></center>
  
: Ponieważ <math>\displaystyle x\in \{0,1\}</math> to <math>\displaystyle f</math> jest bijekcją. Udowodnimy, że <math>\displaystyle f</math> jest monotoniczna. Weźmy dowolne różne pary <math>\displaystyle (n,a),(m,b) \in \omega \times 2</math> takie, że <math>\displaystyle (n,a)\leq_{\omega \times 2}(m,b)</math>. Rozważymy dwa przypadki.
+
: Ponieważ <math>\displaystyle x\in \{0,1\}</math>, to <math>\displaystyle f</math> jest bijekcją. Udowodnimy, że <math>\displaystyle f</math> jest monotoniczna. Weźmy dowolne różne pary <math>\displaystyle (n,a),(m,b) \in \omega \times 2</math> takie, że <math>\displaystyle (n,a)\leq_{\omega \times 2}(m,b)</math>. Rozważymy dwa przypadki:
  
: a) Jeśli <math>\displaystyle n<m</math> to
+
: a) Jeśli <math>\displaystyle n<m</math>, to:
<center><math>\displaystyle f(n, x)= 2\cdot n+x \leq 2\cdot n+1 < 2\cdot (n+1) \leq 2 \cdot m \leq  2 \cdot m +b=f(m,b)
+
<center><math>\displaystyle f(n, x)= 2\cdot n+x \leq 2\cdot n+1 < 2\cdot (n+1) \leq 2 \cdot m \leq  2 \cdot m +b=f(m,b).
 
</math></center>
 
</math></center>
  
: b) W przeciwnym przypadku mamy <math>\displaystyle n=m</math> oraz <math>\displaystyle a<b</math>. Wobec tego <math>\displaystyle a</math> musi być równe 0 a <math>\displaystyle b</math> równe 1. Wtedy
+
: b) W przeciwnym przypadku mamy <math>\displaystyle n=m</math> oraz <math>\displaystyle a<b</math>. Wobec tego <math>\displaystyle a</math> musi być równe 0, a <math>\displaystyle b</math> równe 1. Wtedy
  
 
<center><math>\displaystyle f(n,x)=2\cdot n = 2\cdot m \leq 2\cdot m+1 =f(m,b).
 
<center><math>\displaystyle f(n,x)=2\cdot n = 2\cdot m \leq 2\cdot m+1 =f(m,b).
Linia 1068: Linia 1072:
 
<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">   
  
Na początek zauważmy, że każda skończona liczba porządkowa ma powyższą własność. Niech <math>\displaystyle n</math> będzie skończoną liczbą porządkową. Wiemy, że <math>\displaystyle n</math> jest dobrze uporządkowany przez inkluzję. Wystarczy wykazać, że jest dobrze uporządkowany przez odwróconą inkluzje, a więc że każdy niepusty podzbiór <math>\displaystyle n</math> ma element największy. Ta własność wynika jednak z udowodnionej w <u>'''Wykładzie 7</u>''' zasady maksimum. Rozważmy teraz nieskończoną liczbę porządkową <math>\displaystyle x</math>. Skoro <math>\displaystyle x</math> jest nieskończona to <math>\displaystyle \omega</math> musi być podobna do przedziału początkowego <math>\displaystyle x</math>. Ponieważ w <math>\displaystyle \omega</math> nie ma elementu największego to zbiór <math>\displaystyle x</math> nie może być dobrze uporządkowany przez odwrotną inkluzję.
+
Na początek zauważmy, że każda skończona liczba porządkowa ma powyższą własność. Niech <math>\displaystyle n</math> będzie skończoną liczbą porządkową. Wiemy, że <math>\displaystyle n</math> jest dobrze uporządkowany przez inkluzję. Wystarczy wykazać, że jest dobrze uporządkowany przez odwróconą inkluzję, a więc że każdy niepusty podzbiór <math>\displaystyle n</math> ma element największy. Ta własność wynika jednak z udowodnionej w Wykładzie 7 Zasady Maksimum (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_3|Wykład 7, Zasada Maksimum]] ). Rozważmy teraz nieskończoną liczbę porządkową <math>\displaystyle x</math>. Skoro <math>\displaystyle x</math> jest nieskończona to <math>\displaystyle \omega</math> musi być podobna do przedziału początkowego <math>\displaystyle x</math>. Ponieważ w <math>\displaystyle \omega</math> nie ma elementu największego, to zbiór <math>\displaystyle x</math> nie może być dobrze uporządkowany przez odwrotną inkluzję.
 
</div></div>
 
</div></div>

Aktualna wersja na dzień 13:58, 28 wrz 2020

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 twierdzenie o indukcji (patrz Wykład 7, Twierdzenie 3.1), z którego wynika, że zasada indukcji 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 indukcję 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. ,
  2. .

Innymi słowy, jest zbiorem funkcji częściowych określonych na przedziałach początkowych , spełniających równość 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 niewprost, ż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łniona jest równość 3.1.

Pozostało pokazać, że jest jedyną taką funkcją. Przypuśćmy, że istnieje funkcja różna od , która spełnia równość 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 nienależą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:

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:

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 róż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

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 (patrz Wykład 11, Twierdzenie 3.4) 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:

  1. .
  2. .

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 Wykład 7, Twierdzenie 4.1), a więc także 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 ; zatem 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 (patrz Wykład 4, Aksjomat Regularności) 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 pomiędzy 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 (patrz Wykład 4, Aksjomat Zastępowania) 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:

  1. .
  2. .
  3. .
  4. .
  5. .
  6. .
  7. .
  8. .
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