Logika i teoria mnogości/Wykład 10: Zbiory uporządkowane. Zbiory liniowo uporządkowane. Pojęcia gęstości i ciągłości: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 433: Linia 433:
 
{{definicja|2.1.||
 
{{definicja|2.1.||
  
Porządki liniowe <math>\displaystyle (X,\leq )</math> i <math>\displaystyle (Y,\leq )</math> nazywamy podobnymi
+
Porządki liniowe <math>\displaystyle (X,\leq )</math> i <math>\displaystyle (Y,\leq )</math> nazywamy podobnymi,
gdy istnieje bijekcja <math>\displaystyle f:X \to Y</math> rosnąca czyli taka że jeżeli <math>\displaystyle x \leq y</math> to <math>\displaystyle f(x)
+
gdy istnieje bijekcja <math>\displaystyle f:X \to Y</math> rosnąca, czyli taka, że jeżeli <math>\displaystyle x \leq y</math>, to <math>\displaystyle f(x)
 
\leq f(y)</math>.   
 
\leq f(y)</math>.   
 
}}
 
}}
 
{{cwiczenie|2.2||
 
{{cwiczenie|2.2||
  
Dla podobieństwa <math>\displaystyle f</math> jeżeli <math>\displaystyle f(x) \leq f(y)</math> to <math>\displaystyle x \leq y</math>
+
Dla podobieństwa <math>\displaystyle f</math>, jeżeli <math>\displaystyle f(x) \leq f(y)</math>, to <math>\displaystyle x \leq y</math>
  
 
}}
 
}}
Linia 445: Linia 445:
 
<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 f(x) \leq f(y)</math> oraz <math>\displaystyle x \nleq y</math>. Ponieważ zbiór <math>\displaystyle X</math> jest uporządkowany liniowo to w takiej sytuacji konieczne jest aby <math>\displaystyle y\leq x</math>. Skoro <math>\displaystyle f</math> jest rosnąca to <math>\displaystyle f(y)\leq f(x)</math>. Wobec tego mamy <math>\displaystyle f(y)=f(x)</math> i skoro <math>\displaystyle f</math> jest iniekcją to <math>\displaystyle x=y</math> co jest sprzeczne z <math>\displaystyle x \nleq y</math>.
+
Dla dowodu nie wprost przypuśćmy, że <math>\displaystyle f(x) \leq f(y)</math> oraz <math>\displaystyle x \nleq y</math>. Ponieważ zbiór <math>\displaystyle X</math> jest uporządkowany liniowo, to w takiej sytuacji konieczne jest, aby <math>\displaystyle y\leq x</math>. Skoro <math>\displaystyle f</math> jest rosnąca, to <math>\displaystyle f(y)\leq f(x)</math>. Wobec tego mamy <math>\displaystyle f(y)=f(x)</math> i skoro <math>\displaystyle f</math> jest injekcją to <math>\displaystyle x=y</math>, co jest sprzeczne z <math>\displaystyle x \nleq y</math>.
 
</div></div>
 
</div></div>
  
 
{{definicja|2.3.||
 
{{definicja|2.3.||
  
Porządek  <math>\displaystyle (X,\leq )</math> nazywamy gęstym gdy
+
Porządek  <math>\displaystyle (X,\leq )</math> nazywamy gęstym, gdy
 
<math>\displaystyle \forall_{x,y\in X} \;\; x<y \hspace*{0.1mm} \Rightarrow  \exists_{z\in X} \;\; x<z<y</math>
 
<math>\displaystyle \forall_{x,y\in X} \;\; x<y \hspace*{0.1mm} \Rightarrow  \exists_{z\in X} \;\; x<z<y</math>
 
}}
 
}}
Linia 461: Linia 461:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
  
Niech <math>\displaystyle (X,\leq )</math> i <math>\displaystyle (Y,\leq )</math> będą podobnymi porządkami a <math>\displaystyle f:X \to Y</math> będzie rosnącą bijekcją. Pokażemy, że jeśli <math>\displaystyle (X,\leq )</math> jest gęsty to również <math>\displaystyle (Y,\leq)</math> jest gęsty.
+
Niech <math>\displaystyle (X,\leq )</math> i <math>\displaystyle (Y,\leq )</math> będą podobnymi porządkami, a <math>\displaystyle f:X \to Y</math> będzie rosnącą bijekcją. Pokażemy, że jeśli <math>\displaystyle (X,\leq )</math> jest gęsty, to również <math>\displaystyle (Y,\leq)</math> jest gęsty.
  
Weźmy dowolne elementy <math>\displaystyle y_1,y_2\in Y</math> takie, że <math>\displaystyle y_1 < y_2</math>. Skoro <math>\displaystyle f</math> jest bijekcją to istnieją elementy <math>\displaystyle x_1,x_2\in X</math> dla których <math>\displaystyle f(x_1)=y_1</math> oraz <math>\displaystyle f(x_2)=y2</math>. Z poprzedniego ćwiczenia wynika, że <math>\displaystyle x_1 < x_2</math>. Ponieważ <math>\displaystyle (X,\leq)</math> jest gęsty to istnieje element <math>\displaystyle x_3\in X</math> taki, że <math>\displaystyle x_1 < x_3 <x_2</math>, wtedy z monotoniczności i iniektywności <math>\displaystyle f</math> otrzymujemy
+
Weźmy dowolne elementy <math>\displaystyle y_1,y_2\in Y</math> takie, że <math>\displaystyle y_1 < y_2</math>. Skoro <math>\displaystyle f</math> jest bijekcją, to istnieją elementy <math>\displaystyle x_1,x_2\in X</math>, dla których <math>\displaystyle f(x_1)=y_1</math> oraz <math>\displaystyle f(x_2)=y2</math>. Z poprzedniego ćwiczenia wynika, że <math>\displaystyle x_1 < x_2</math>. Ponieważ <math>\displaystyle (X,\leq)</math> jest gęsty, to istnieje element <math>\displaystyle x_3\in X</math> taki, że <math>\displaystyle x_1 < x_3 <x_2</math>, wtedy z monotoniczności i injektywności <math>\displaystyle f</math> otrzymujemy:
  
 
<center><math>\displaystyle y_1 = f(x_1) < f(x_3) < f(x_2)= y_2.
 
<center><math>\displaystyle y_1 = f(x_1) < f(x_3) < f(x_2)= y_2.
 
</math></center>
 
</math></center>
  
Oznacza to, że istnieje element <math>\displaystyle y_3\in Y</math> który leży pomiędzy <math>\displaystyle y_1</math> a <math>\displaystyle y_2</math>. Udowodniliśmy więc, że porządek <math>\displaystyle (Y\leq)</math> jest gęsty.
+
Oznacza to, że istnieje element <math>\displaystyle y_3\in Y</math>, który leży pomiędzy <math>\displaystyle y_1</math> a <math>\displaystyle y_2</math>. Udowodniliśmy więc, że porządek <math>\displaystyle (Y\leq)</math> jest gęsty.
  
 
</div></div>
 
</div></div>
Linia 474: Linia 474:
 
{{cwiczenie|2.5||
 
{{cwiczenie|2.5||
  
W zbiorze <math>\displaystyle \mathbb{N}^\mathbb{N}</math> rozważymy dwie relacje porządkujące zdefiniowane następująco
+
W zbiorze <math>\displaystyle \mathbb{N}^\mathbb{N}</math> rozważymy dwie relacje porządkujące zdefiniowane następująco:
  
 
<center><math>\displaystyle \aligned f \sqsubseteq_1 g  \Leftrightarrow  \forall_{n \in \mathbb{N}} f(n) \leq g(n),\\
 
<center><math>\displaystyle \aligned f \sqsubseteq_1 g  \Leftrightarrow  \forall_{n \in \mathbb{N}} f(n) \leq g(n),\\
Linia 488: Linia 488:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
  
Pokażemy, że porządek <math>\displaystyle \sqsubseteq_1</math> nie jest gęsty, podczas gdy porządek <math>\displaystyle \sqsubseteq_2</math> jest. Wobec faktu, że gęstość jest przenoszona przez podobieństwo będzie to oznaczało, że nie są podobne.
+
Pokażemy, że porządek <math>\displaystyle \sqsubseteq_1</math> nie jest gęsty, podczas gdy porządek <math>\displaystyle \sqsubseteq_2</math> jest. Wobec faktu, że gęstość jest przenoszona przez podobieństwo, będzie to oznaczało, że nie są podobne.
  
Niech <math>\displaystyle f_0</math> będzie funkcją stale równą 0, a <math>\displaystyle f_1</math> niech będzie zdefiniowana następująco
+
Niech <math>\displaystyle f_0</math> będzie funkcją stale równą 0, a <math>\displaystyle f_1</math> niech będzie zdefiniowana następująco:
  
 
<center><math>\displaystyle f_1(x)= \left\{\begin{array} {ll}
 
<center><math>\displaystyle f_1(x)= \left\{\begin{array} {ll}
0, & x >0  \\
+
0, & x >0, \\
1, & x=0 \\\end{array} \right.
+
1, & x=0. \\\end{array} \right.
 
</math></center>
 
</math></center>
  
Z definicji funkcji wynika, że <math>\displaystyle f_0 \sqsubseteq_1 f_1</math>. Przypuśćmy teraz, że istnieje funkcja <math>\displaystyle g</math> taka, że <math>\displaystyle f_0 \sqsubseteq_1 g \sqsubseteq_1 f_1</math>. Wtedy, z definicji <math>\displaystyle \sqsubseteq_1</math>, dla każdego <math>\displaystyle n\in \mathbb{N} \setminus\{0\}</math> mamy
+
Z definicji funkcji wynika, że <math>\displaystyle f_0 \sqsubseteq_1 f_1</math>. Przypuśćmy teraz, że istnieje funkcja <math>\displaystyle g</math> taka, że <math>\displaystyle f_0 \sqsubseteq_1 g \sqsubseteq_1 f_1</math>. Wtedy, z definicji <math>\displaystyle \sqsubseteq_1</math>, dla każdego <math>\displaystyle n\in \mathbb{N} \setminus\{0\}</math> mamy:
  
 
<center><math>\displaystyle 0=f_0(x) \leq g(x) \leq f_1(x)=0,
 
<center><math>\displaystyle 0=f_0(x) \leq g(x) \leq f_1(x)=0,
 
</math></center>
 
</math></center>
  
a więc <math>\displaystyle g(x)=0</math> dla <math>\displaystyle x\neq 0</math>. Dla <math>\displaystyle x=0</math> otrzymujemy
+
a więc <math>\displaystyle g(x)=0</math> dla <math>\displaystyle x\neq 0</math>. Dla <math>\displaystyle x=0</math> otrzymujemy:
  
 
<center><math>\displaystyle 0 = f_0(0) \leq g(0) \leq f_1(0)=1.
 
<center><math>\displaystyle 0 = f_0(0) \leq g(0) \leq f_1(0)=1.
 
</math></center>
 
</math></center>
  
Ponieważ <math>\displaystyle g(0)\in \mathbb{N}</math> to są tylko dwie możliwości, <math>\displaystyle g(0)=0</math> i wtedy <math>\displaystyle g=f_0</math>, lub <math>\displaystyle g(0)=1</math> i wtedy <math>\displaystyle g=f_1</math>. Wynika stąd, że nie istnieje funkcja która znajduje się pomiędzy <math>\displaystyle f_0</math> a <math>\displaystyle f_1</math> w sensie <math>\displaystyle \sqsubseteq_1</math>, więc ten porządek nie jest gęsty.
+
Ponieważ <math>\displaystyle g(0)\in \mathbb{N}</math>, to są tylko dwie możliwości, <math>\displaystyle g(0)=0</math> i wtedy <math>\displaystyle g=f_0</math> lub <math>\displaystyle g(0)=1</math> i wtedy <math>\displaystyle g=f_1</math>. Wynika stąd, że nie istnieje funkcja, która znajduje się pomiędzy <math>\displaystyle f_0</math> a <math>\displaystyle f_1</math> w sensie <math>\displaystyle \sqsubseteq_1</math>, więc ten porządek nie jest gęsty.
  
Pokażemy teraz, że <math>\displaystyle \sqsubseteq_2</math> jest gęsty. Weźmy dowolne funkcje <math>\displaystyle f_1,f_2\in \mathbb{N}^\mathbb{N}</math> takie, że <math>\displaystyle f_1\sqsubseteq_2 f_2</math>. Z definicji <math>\displaystyle \sqsubseteq_2</math> otrzymujemy, że istnieje <math>\displaystyle n_0\in \mathbb{N}</math> takie, że dla każdego <math>\displaystyle n<n_0</math> mamy <math>\displaystyle f_1(n)=f_2(n)</math> oraz <math>\displaystyle f(n_0) < g(n_0)</math>. Zdefiniujmy funkcję <math>\displaystyle g</math> następująco
+
Pokażemy teraz, że <math>\displaystyle \sqsubseteq_2</math> jest gęsty. Weźmy dowolne funkcje <math>\displaystyle f_1,f_2\in \mathbb{N}^\mathbb{N}</math> takie, że <math>\displaystyle f_1\sqsubseteq_2 f_2</math>. Z definicji <math>\displaystyle \sqsubseteq_2</math> otrzymujemy, że istnieje <math>\displaystyle n_0\in \mathbb{N}</math> takie, że dla każdego <math>\displaystyle n<n_0</math> mamy <math>\displaystyle f_1(n)=f_2(n)</math> oraz <math>\displaystyle f(n_0) < g(n_0)</math>. Zdefiniujmy funkcję <math>\displaystyle g</math> następująco:
  
 
<center><math>\displaystyle g(x)=\left\{\begin{array} {ll}
 
<center><math>\displaystyle g(x)=\left\{\begin{array} {ll}
f_1(x), & x \neq n_0+1  \\
+
f_1(x), & x \neq n_0+1, \\
f_1(x)+1, & x=n_0+1 \\\end{array} \right.
+
f_1(x)+1, & x=n_0+1. \\\end{array} \right.
 
</math></center>
 
</math></center>
  
Z definicji od razu wynika, że <math>\displaystyle f_1 \sqsubseteq_2 g</math>. Z drugiej strony mamy też <math>\displaystyle g\sqsubseteq_2 f_2</math>, bo dla <math>\displaystyle n<n_0</math> mamy <math>\displaystyle g(x)=f_1(x) = f_2(x)</math> oraz <math>\displaystyle g(x)=f_1(x) < f_2(x)</math>.  Wskazaliśmy więc funkcję <math>\displaystyle g</math> która znajduje się pomiędzy funkcjami <math>\displaystyle f_1, f_2</math> w porządku <math>\displaystyle \sqsubseteq</math>. Funkcja ta różni się od <math>\displaystyle f_1</math> na współrzędnej <math>\displaystyle n_0+1</math> i od <math>\displaystyle f_2</math> na współrzędnej <math>\displaystyle n_0</math>. Wobec dowolności wyboru <math>\displaystyle f_1,f_2</math> porządek <math>\displaystyle \sqsubseteq_2</math> jest gęsty.
+
Z definicji od razu wynika, że <math>\displaystyle f_1 \sqsubseteq_2 g</math>. Z drugiej strony mamy też <math>\displaystyle g\sqsubseteq_2 f_2</math>, bo dla <math>\displaystyle n<n_0</math> mamy <math>\displaystyle g(x)=f_1(x) = f_2(x)</math> oraz <math>\displaystyle g(x)=f_1(x) < f_2(x)</math>.  Wskazaliśmy więc funkcję <math>\displaystyle g</math>, która znajduje się pomiędzy funkcjami <math>\displaystyle f_1, f_2</math> w porządku <math>\displaystyle \sqsubseteq</math>. Funkcja ta różni się od <math>\displaystyle f_1</math> na współrzędnej <math>\displaystyle n_0+1</math> i od <math>\displaystyle f_2</math> na współrzędnej <math>\displaystyle n_0</math>. Wobec dowolności wyboru <math>\displaystyle f_1,f_2</math> porządek <math>\displaystyle \sqsubseteq_2</math> jest gęsty.
 
</div></div>
 
</div></div>
  
Linia 523: Linia 523:
 
Niech <math>\displaystyle (X,\leq )</math> będzie porządkiem liniowym. Przekrojem
 
Niech <math>\displaystyle (X,\leq )</math> będzie porządkiem liniowym. Przekrojem
 
Dedekinda w <math>\displaystyle (X,\leq )</math> nazywamy parę
 
Dedekinda w <math>\displaystyle (X,\leq )</math> nazywamy parę
zbiorów <math>\displaystyle X_1 , X_2 \subset X</math> taką że:
+
zbiorów <math>\displaystyle X_1 , X_2 \subset X</math>, taką że:
 
# <math>\displaystyle X_1 \cup X_2 = X</math>.
 
# <math>\displaystyle X_1 \cup X_2 = X</math>.
 
# <math>\displaystyle X_1 \cap X_2 = \emptyset</math>.
 
# <math>\displaystyle X_1 \cap X_2 = \emptyset</math>.
Linia 531: Linia 531:
 
{{definicja|2.7.||
 
{{definicja|2.7.||
  
Przekrój <math>\displaystyle X_1 , X_2</math> daje skok jeżeli <math>\displaystyle X_1</math> ma
+
Przekrój <math>\displaystyle X_1 , X_2</math> daje skok, jeżeli <math>\displaystyle X_1</math> ma
 
element największy i <math>\displaystyle X_2</math> ma element najmniejszy.
 
element największy i <math>\displaystyle X_2</math> ma element najmniejszy.
 
}}
 
}}
 
{{cwiczenie|2.8||
 
{{cwiczenie|2.8||
  
Liniowy porządek  <math>\displaystyle (X,\leq )</math> jest gęsty wtedy i tylko wtedy gdy żaden przekrój nie daje
+
Liniowy porządek  <math>\displaystyle (X,\leq )</math> jest gęsty wtedy i tylko wtedy, gdy żaden przekrój nie daje
 
skoku.
 
skoku.
  
Linia 543: Linia 543:
 
<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">   
  
Przypuśćmy, że w porządku <math>\displaystyle (X,\leq)</math> istnieje przekrój <math>\displaystyle X_1,X_2</math> który daje skok. Istnieją wtedy różne elementy <math>\displaystyle x_1, x_2</math> takie, że <math>\displaystyle x_1 = \bigvee X_1</math> oraz <math>\displaystyle x_2 =\bigwedge X_2</math>. Weźmy dowolny element <math>\displaystyle z</math> taki, że <math>\displaystyle x_1 \leq z \leq x_2</math>. <math>\displaystyle z</math> należy do <math>\displaystyle X</math> więc musi należeć do któregoś ze zbiorów przekroju. Jeśli <math>\displaystyle z\in X_1</math> to <math>\displaystyle z\leq x_1</math> i wtedy <math>\displaystyle z=x_1</math>. Jeśli <math>\displaystyle z\in X_2</math> to <math>\displaystyle x_2 \leq z</math> i wtedy <math>\displaystyle z=x_2</math>. Wynika stąd, że nie istnieje element leżący pomiędzy <math>\displaystyle x_1</math> a <math>\displaystyle x_2</math> w porządku <math>\displaystyle \leq</math>, a więc porządek ten nie jest gesty.
+
Przypuśćmy, że w porządku <math>\displaystyle (X,\leq)</math> istnieje przekrój <math>\displaystyle X_1,X_2</math>, który daje skok. Istnieją wtedy różne elementy <math>\displaystyle x_1, x_2</math> takie, że <math>\displaystyle x_1 = \bigvee X_1</math> oraz <math>\displaystyle x_2 =\bigwedge X_2</math>. Weźmy dowolny element <math>\displaystyle z</math> taki, że <math>\displaystyle x_1 \leq z \leq x_2</math>. Element <math>\displaystyle z</math> należy do <math>\displaystyle X</math>, więc musi należeć do któregoś ze zbiorów przekroju. Jeśli <math>\displaystyle z\in X_1</math>, to <math>\displaystyle z\leq x_1</math> i wtedy <math>\displaystyle z=x_1</math>. Jeśli <math>\displaystyle z\in X_2</math>, to <math>\displaystyle x_2 \leq z</math> i wtedy <math>\displaystyle z=x_2</math>. Wynika stąd, że nie istnieje element leżący pomiędzy <math>\displaystyle x_1</math> a <math>\displaystyle x_2</math> w porządku <math>\displaystyle \leq</math>, a więc porządek ten nie jest gęsty.
  
Przypuśćmy, że  żaden przekrój w porządku <math>\displaystyle (X,\leq)</math> nie daje skoku. Pokażemy, że ten porządek jest gęsty. Weźmy dowolne elementy <math>\displaystyle x_1,x_2 \in X</math> takie, że <math>\displaystyle x_1 < x_2</math>. Niech <math>\displaystyle X_1= \{z\in X: z \leq x_1\}</math> oraz <math>\displaystyle X_2= X \setminus X_1</math>. Z konstrukcji wynika, że zbiory <math>\displaystyle X_1,X_2</math> są przekrojem zbioru <math>\displaystyle X</math>, <math>\displaystyle x_2\in X_2</math>, oraz w zbiorze <math>\displaystyle X_1</math> istnieje element największy (jest nim <math>\displaystyle x_1</math>). Ponieważ przekrój ten nie może dawać skoku to w zbiorze <math>\displaystyle X_2</math> nie może istnieć element najmniejszy. Oznacza to, że w <math>\displaystyle X_2</math> musi istnieć element <math>\displaystyle z</math> taki, że <math>\displaystyle z < x_2</math> ( w przeciwnym przypadku <math>\displaystyle x_2</math> byłby najmniejszy, gdyż <math>\displaystyle X</math> jest uporządkowany liniowo). Ponieważ <math>\displaystyle z\in X_2</math> to również <math>\displaystyle z\neq x_1</math>. Wskazaliśmy więc element <math>\displaystyle z\in X</math> dla którego <math>\displaystyle x_1 < z <x_2</math>. Wobec dowolności wyboru <math>\displaystyle x_1,x_2</math> dowiedliśmy, że porządek <math>\displaystyle (X,\leq)</math> jest gęsty.
+
Przypuśćmy, że  żaden przekrój w porządku <math>\displaystyle (X,\leq)</math> nie daje skoku. Pokażemy, że ten porządek jest gęsty. Weźmy dowolne elementy <math>\displaystyle x_1,x_2 \in X</math> takie, że <math>\displaystyle x_1 < x_2</math>. Niech <math>\displaystyle X_1= \{z\in X: z \leq x_1\}</math> oraz <math>\displaystyle X_2= X \setminus X_1</math>. Z konstrukcji wynika, że zbiory <math>\displaystyle X_1,X_2</math> są przekrojem zbioru <math>\displaystyle X</math>, <math>\displaystyle x_2\in X_2</math> oraz w zbiorze <math>\displaystyle X_1</math> istnieje element największy (jest nim <math>\displaystyle x_1</math>). Ponieważ przekrój ten nie może dawać skoku, to w zbiorze <math>\displaystyle X_2</math> nie może istnieć element najmniejszy. Oznacza to, że w <math>\displaystyle X_2</math> musi istnieć element <math>\displaystyle z</math> taki, że <math>\displaystyle z < x_2</math> ( w przeciwnym przypadku <math>\displaystyle x_2</math> byłby najmniejszy, gdyż <math>\displaystyle X</math> jest uporządkowany liniowo). Ponieważ <math>\displaystyle z\in X_2</math>, to również <math>\displaystyle z\neq x_1</math>. Wskazaliśmy więc element <math>\displaystyle z\in X</math>, dla którego <math>\displaystyle x_1 < z <x_2</math>. Wobec dowolności wyboru <math>\displaystyle x_1,x_2</math> dowiedliśmy, że porządek <math>\displaystyle (X,\leq)</math> jest gęsty.
 
</div></div>
 
</div></div>
  
 
{{cwiczenie|2.9||
 
{{cwiczenie|2.9||
  
W zbiorze <math>\displaystyle \{0,1\}^\mathbb{N}</math> rozważymy relację porządkującą zdefiniowaną następująco
+
W zbiorze <math>\displaystyle \{0,1\}^\mathbb{N}</math> rozważymy relację porządkującą zdefiniowaną następująco:
  
 
<center><math>\displaystyle \aligned f \sqsubseteq g \Leftrightarrow [f=g \vee \exists_{n_0 \in \mathbb{N}} (f(n_0) < g(n_0)\wedge  \forall_{n<n_0} f(n) =g(n))].
 
<center><math>\displaystyle \aligned f \sqsubseteq g \Leftrightarrow [f=g \vee \exists_{n_0 \in \mathbb{N}} (f(n_0) < g(n_0)\wedge  \forall_{n<n_0} f(n) =g(n))].
Linia 561: Linia 561:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
  
Porządek ten nie jest gęsty. Zdefiniujmy funkcje <math>\displaystyle f_1,f_2</math> następująco
+
Porządek ten nie jest gęsty. Zdefiniujmy funkcje <math>\displaystyle f_1,f_2</math> następująco:
  
 
<center><math>\displaystyle f_1(x)= \left\{\begin{array} {ll}
 
<center><math>\displaystyle f_1(x)= \left\{\begin{array} {ll}
 
0, & x=0; \\
 
0, & x=0; \\
1, & x\neq0. \\\end{array} \right.
+
1, & x\neq0, \\\end{array} \right.
 
</math></center>
 
</math></center>
  
 
<center><math>\displaystyle f_2(x)= \left\{\begin{array} {ll}
 
<center><math>\displaystyle f_2(x)= \left\{\begin{array} {ll}
 
1, & x=0; \\
 
1, & x=0; \\
0, & x\neq0, \\\end{array} \right.
+
0, & x\neq0. \\\end{array} \right.
 
</math></center>
 
</math></center>
  
Wtedy <math>\displaystyle f_1 \sqsubseteq f_2</math> gdyż dla <math>\displaystyle n_0=0</math> mamy <math>\displaystyle f_1(0)=0  < 1 =f_2(0)</math>. Przypuśćmy teraz, że funkcja <math>\displaystyle g\in 2^\mathbb{N}</math> jest taka, że <math>\displaystyle f_1 \sqsubseteq g \sqsubseteq f_2</math>. Rozważmy dwa przypadki. Jeśli <math>\displaystyle g(0)=1</math> to <math>\displaystyle g=f_2</math> gdyż wtedy nie może istnieć <math>\displaystyle n>0</math> dla którego <math>\displaystyle g(n)< f_2(n)</math> (bo <math>\displaystyle f_2(n)=0</math>). Jeśli natomiast <math>\displaystyle g(0)=1</math> to <math>\displaystyle g=f_1</math> gdyż nie może istnieć <math>\displaystyle n>0</math> dla którego <math>\displaystyle f_1(n)< g(n)</math> (bo <math>\displaystyle f_1(n)=1</math>). Wynika stąd, że nie istnieje element <math>\displaystyle g\in 2^\mathbb{N}</math> różny od <math>\displaystyle f_1,f_2</math> taki, że <math>\displaystyle f_1 \sqsubseteq g \sqsubseteq f_2</math>, a więc porządek ten nie jest gęsty.
+
Wtedy <math>\displaystyle f_1 \sqsubseteq f_2</math>, gdyż dla <math>\displaystyle n_0=0</math> mamy <math>\displaystyle f_1(0)=0  < 1 =f_2(0)</math>. Przypuśćmy teraz, że funkcja <math>\displaystyle g\in 2^\mathbb{N}</math> jest taka, że <math>\displaystyle f_1 \sqsubseteq g \sqsubseteq f_2</math>. Rozważmy dwa przypadki. Jeśli <math>\displaystyle g(0)=1</math>, to <math>\displaystyle g=f_2</math>, gdyż wtedy nie może istnieć <math>\displaystyle n>0</math>, dla którego <math>\displaystyle g(n)< f_2(n)</math> (bo <math>\displaystyle f_2(n)=0</math>). Jeśli natomiast <math>\displaystyle g(0)=1</math>, to <math>\displaystyle g=f_1</math>, gdyż nie może istnieć <math>\displaystyle n>0</math>, dla którego <math>\displaystyle f_1(n)< g(n)</math> (bo <math>\displaystyle f_1(n)=1</math>). Wynika stąd, że nie istnieje element <math>\displaystyle g\in 2^\mathbb{N}</math> różny od <math>\displaystyle f_1,f_2</math> taki, że <math>\displaystyle f_1 \sqsubseteq g \sqsubseteq f_2</math>, a więc porządek ten nie jest gęsty.
 
</div></div>
 
</div></div>
  
 
{{definicja|2.10.||
 
{{definicja|2.10.||
  
Przekrój <math>\displaystyle X_1 , X_2</math> daje lukę  jeżeli <math>\displaystyle X_1</math> nie ma
+
Przekrój <math>\displaystyle X_1 , X_2</math> daje lukę, jeżeli <math>\displaystyle X_1</math> nie ma
 
elementu największego i <math>\displaystyle X_2</math> nie ma elementu najmniejszego.
 
elementu największego i <math>\displaystyle X_2</math> nie ma elementu najmniejszego.
 
}}
 
}}
 
{{definicja|2.11.||
 
{{definicja|2.11.||
  
Porządek liniowy <math>\displaystyle (X,\leq )</math> nazywamy ciągłym wtedy i tylko wtedy
+
Porządek liniowy <math>\displaystyle (X,\leq )</math> nazywamy ciągłym wtedy i tylko wtedy,
 
gdy  żaden przekrój nie daje luki.   
 
gdy  żaden przekrój nie daje luki.   
 
}}
 
}}
Linia 594: Linia 594:
  
 
Niech <math>\displaystyle A \neq \emptyset</math> będzie zbiorem ograniczonym od góry. Łatwo zauważyć, że
 
Niech <math>\displaystyle A \neq \emptyset</math> będzie zbiorem ograniczonym od góry. Łatwo zauważyć, że
jeżeli jakieś ograniczenie zbioru <math>\displaystyle A</math> należy do <math>\displaystyle A</math> to jest jego supremum. Załóżmy
+
jeżeli jakieś ograniczenie zbioru <math>\displaystyle A</math> należy do <math>\displaystyle A</math>, to jest jego supremum. Załóżmy
 
zatem, że żadne ograniczenie do <math>\displaystyle A</math> nie należy. Utwórzmy parę zbiorów:
 
zatem, że żadne ograniczenie do <math>\displaystyle A</math> nie należy. Utwórzmy parę zbiorów:
 
<math>\displaystyle X_1 = \left\{y\in X: \exists_{x\in A} \;\; y \leq x\right\}</math> oraz
 
<math>\displaystyle X_1 = \left\{y\in X: \exists_{x\in A} \;\; y \leq x\right\}</math> oraz
Linia 602: Linia 602:
 
Do <math>\displaystyle X_2 </math> należą wszystkie ograniczenia górne zbioru <math>\displaystyle A</math> więc musi on być niepusty.
 
Do <math>\displaystyle X_2 </math> należą wszystkie ograniczenia górne zbioru <math>\displaystyle A</math> więc musi on być niepusty.
 
Z konstrukcji wynika <math>\displaystyle X_1 \cup X_2 = X</math>.
 
Z konstrukcji wynika <math>\displaystyle X_1 \cup X_2 = X</math>.
Korzystając z ciągłości otrzymujemy, że <math>\displaystyle X_1</math> ma element największy lub <math>\displaystyle X_2</math> ma element
+
Korzystając z ciągłości, otrzymujemy, że <math>\displaystyle X_1</math> ma element największy lub <math>\displaystyle X_2</math> ma element
najmniejszy. Gdy <math>\displaystyle X_1</math> posiada element największy <math>\displaystyle b</math> to jest on supremum <math>\displaystyle A</math>. Istotnie,
+
najmniejszy. Gdy <math>\displaystyle X_1</math> posiada element największy <math>\displaystyle b</math>, to jest on supremum <math>\displaystyle A</math>. Istotnie,
element <math>\displaystyle b</math> góruje nad <math>\displaystyle X_1</math> więc tym bardziej nad <math>\displaystyle A</math>. Gdy element <math>\displaystyle b'</math> góruje nad <math>\displaystyle A</math>
+
element <math>\displaystyle b</math> góruje nad <math>\displaystyle X_1</math>, więc tym bardziej nad <math>\displaystyle A</math>. Gdy element <math>\displaystyle b'</math> góruje nad <math>\displaystyle A</math>,
to góruje też nad <math>\displaystyle X_1</math>, zatem jeżeli należy do <math>\displaystyle X_1</math> musi być równy <math>\displaystyle b</math>, gdy zaś
+
to góruje też nad <math>\displaystyle X_1</math>, zatem jeżeli należy do <math>\displaystyle X_1</math>, musi być równy <math>\displaystyle b</math>, gdy zaś
należy do <math>\displaystyle X_2</math> to <math>\displaystyle b' > b</math>. W drugim przypadku gdy w <math>\displaystyle X_1</math> nie ma elementu
+
należy do <math>\displaystyle X_2</math>, to <math>\displaystyle b' > b</math>. W drugim przypadku, gdy w <math>\displaystyle X_1</math> nie ma elementu
 
największego,  supremum <math>\displaystyle A</math> jest najmniejszy element  <math>\displaystyle b</math> z <math>\displaystyle X_2</math> . Istotnie, <math>\displaystyle b</math> góruje
 
największego,  supremum <math>\displaystyle A</math> jest najmniejszy element  <math>\displaystyle b</math> z <math>\displaystyle X_2</math> . Istotnie, <math>\displaystyle b</math> góruje
nad <math>\displaystyle A</math>. Jeżeli jakiś <math>\displaystyle b'</math> góruje nad <math>\displaystyle A</math> to również nad <math>\displaystyle X_1</math>. <math>\displaystyle b'</math> nie może
+
nad <math>\displaystyle A</math>. Jeżeli jakiś <math>\displaystyle b'</math> góruje nad <math>\displaystyle A</math>, to również nad <math>\displaystyle X_1</math>. <math>\displaystyle b'</math> nie może
należeć do <math>\displaystyle X_1</math> bo w <math>\displaystyle X_1</math> nie ma największego. Należy więc do <math>\displaystyle X_2</math>, zatem <math>\displaystyle b \leq
+
należeć do <math>\displaystyle X_1</math>, bo w <math>\displaystyle X_1</math> nie ma największego. Należy więc do <math>\displaystyle X_2</math>, zatem <math>\displaystyle b \leq
b '</math>. Proszę o zwrócenie uwagi na fakt, że możliwe jest aby zarówno <math>\displaystyle X_1</math> miał
+
b '</math>. Proszę o zwrócenie uwagi na fakt, że możliwe jest, aby zarówno <math>\displaystyle X_1</math> miał
element największy jak i <math>\displaystyle X_2</math> miał element najmniejszy. Wtedy supremum jest ten pochodzący z
+
element największy, jak i <math>\displaystyle X_2</math> miał element najmniejszy. Wtedy supremum jest ten pochodzący z
 
<math>\displaystyle X_1</math>.
 
<math>\displaystyle X_1</math>.
 
}}
 
}}
Linia 617: Linia 617:
 
<span id="twierdzenie_2_13">{{twierdzenie|2.13.||
 
<span id="twierdzenie_2_13">{{twierdzenie|2.13.||
  
W porządek liniowym <math>\displaystyle (X,\leq )</math> jeżeli każdy niepusty zbiór ograniczony od góry ma supremum to porządek jest ciągły.  
+
W porządku liniowym <math>\displaystyle (X,\leq )</math>, jeżeli każdy niepusty zbiór ograniczony od góry ma supremum, to porządek jest ciągły.  
 
}}</span>
 
}}</span>
  
Linia 623: Linia 623:
  
 
Weźmy przekrój Dedekinda <math>\displaystyle X_1 , X_2 \subset X</math>. <math>\displaystyle X_1</math> jest ograniczony od góry przez
 
Weźmy przekrój Dedekinda <math>\displaystyle X_1 , X_2 \subset X</math>. <math>\displaystyle X_1</math> jest ograniczony od góry przez
elementy z <math>\displaystyle X_2</math>. <math>\displaystyle X_1</math> ma więc supremum <math>\displaystyle a</math>. Jeżeli <math>\displaystyle a\in X_1</math> to <math>\displaystyle X_1</math> ma element
+
elementy z <math>\displaystyle X_2</math>. <math>\displaystyle X_1</math>, ma więc supremum <math>\displaystyle a</math>. Jeżeli <math>\displaystyle a\in X_1</math>, to <math>\displaystyle X_1</math> ma element
 
największy. W przeciwnym przypadku <math>\displaystyle a \in X_2</math>.
 
największy. W przeciwnym przypadku <math>\displaystyle a \in X_2</math>.
Gdyby <math>\displaystyle a > x_2</math> dla pewnego <math>\displaystyle x_2 \in X_2</math> to zbiór <math>\displaystyle X_1</math> miałby mniejsze
+
Gdyby <math>\displaystyle a > x_2</math> dla pewnego <math>\displaystyle x_2 \in X_2</math>, to zbiór <math>\displaystyle X_1</math> miałby mniejsze
 
ograniczenie górne niż <math>\displaystyle a</math>. To jest niemożliwe, musi więc być <math>\displaystyle a \leq  x_2</math> dla
 
ograniczenie górne niż <math>\displaystyle a</math>. To jest niemożliwe, musi więc być <math>\displaystyle a \leq  x_2</math> dla
 
każdego <math>\displaystyle x_2 \in X_2</math>. Zatem <math>\displaystyle a</math> jest najmniejszy w <math>\displaystyle X_2</math>.
 
każdego <math>\displaystyle x_2 \in X_2</math>. Zatem <math>\displaystyle a</math> jest najmniejszy w <math>\displaystyle X_2</math>.
Linia 633: Linia 633:
  
 
W porządku liniowym <math>\displaystyle (X,\leq )</math> każdy niepusty zbiór ograniczony od dołu ma
 
W porządku liniowym <math>\displaystyle (X,\leq )</math> każdy niepusty zbiór ograniczony od dołu ma
infimum wtedy i tylko wtedy gdy porządek jest ciągły.
+
infimum wtedy i tylko wtedy, gdy porządek jest ciągły.
 
}}
 
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
Odwróć porządek w <math>\displaystyle X</math> i zastosuj twierdzenia 2.12 i 2.13 (patrz [[#twierdzenie_2_12|twierdzenie 2.12.]] i [[#twierdzenie_2_13|twierdzenie 2.13.]]) )  
+
Odwróć porządek w <math>\displaystyle X</math> i zastosuj Twierdzenia 2.12 i 2.13 (patrz [[#twierdzenie_2_12|Twierdzenie 2.12.]] i [[#twierdzenie_2_13|Twierdzenie 2.13.]]) )  
 
</div></div>
 
</div></div>
  
Linia 651: Linia 651:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
  
Niech <math>\displaystyle (X,\leq_X)</math> oraz <math>\displaystyle (Y,\leq_Y)</math> będą podobnymi porządkami, takimi, że <math>\displaystyle (X,\leq_X)</math> jest porządkiem ciągłym. Pokażemy, że <math>\displaystyle (Y,\leq_Y)</math> jest ciągły. Niech <math>\displaystyle f:X\rightarrow Y</math> będzie rosnącą bijekcją. Weźmy dowolny przekrój <math>\displaystyle Y_1,Y_2</math> zbioru <math>\displaystyle Y</math>. Rozważmy zbiory <math>\displaystyle \vec{f}^{-1}(Y_1), \vec{f}^{-1}(Y_2)</math>, oznaczmy je przez <math>\displaystyle X_1,X_2</math>. Pokażemy że tworzą one przekrój zbioru <math>\displaystyle X</math>. Z własności przeciwobrazu otrzymujemy natychmiast <math>\displaystyle X_1\cup X_2= X</math> oraz <math>\displaystyle X_1 \cap X_2 = \emptyset</math>. Z suriektywności funkcji <math>\displaystyle f</math> oraz z faktu, że zbiory <math>\displaystyle Y_1,Y_2</math> są niepuste otrzymujemy, że zbiory <math>\displaystyle X_1, X_2</math> też są niepuste. Weźmy teraz dowolny element <math>\displaystyle x_1\in X_1</math> oraz <math>\displaystyle x_2\in X_2</math>. Pokażemy, że <math>\displaystyle x_1 \leq_X x_2</math>. Przypuśćmy, że tak nie jest. Wtedy <math>\displaystyle x_1 >_X x_2</math> i ponieważ funkcja <math>\displaystyle f</math> jest iniektywna i rosnąca to otrzymamy <math>\displaystyle f(x_1) >_Y f(x_2)</math>. Otrzymaliśmy sprzeczność, gdyż <math>\displaystyle f(x_1) \in Y_1</math> i <math>\displaystyle f(x_2) \in Y_2</math> a zbiory <math>\displaystyle Y_1,Y_2</math> są przekrojem <math>\displaystyle Y</math>. Wobec tego konieczne jest aby <math>\displaystyle x_1 \leq x_2</math>. Dowiedliśmy więc, że zbiory <math>\displaystyle X_1,X_2</math> są przekrojem <math>\displaystyle X</math>.
+
Niech <math>\displaystyle (X,\leq_X)</math> oraz <math>\displaystyle (Y,\leq_Y)</math> będą podobnymi porządkami, takimi że <math>\displaystyle (X,\leq_X)</math> jest porządkiem ciągłym. Pokażemy, że <math>\displaystyle (Y,\leq_Y)</math> jest ciągły. Niech <math>\displaystyle f:X\rightarrow Y</math> będzie rosnącą bijekcją. Weźmy dowolny przekrój <math>\displaystyle Y_1,Y_2</math> zbioru <math>\displaystyle Y</math>. Rozważmy zbiory <math>\displaystyle \vec{f}^{-1}(Y_1), \vec{f}^{-1}(Y_2)</math>, oznaczmy je przez <math>\displaystyle X_1,X_2</math>. Pokażemy że tworzą one przekrój zbioru <math>\displaystyle X</math>. Z własności przeciwobrazu otrzymujemy natychmiast <math>\displaystyle X_1\cup X_2= X</math> oraz <math>\displaystyle X_1 \cap X_2 = \emptyset</math>. Z suriektywności funkcji <math>\displaystyle f</math> oraz z faktu, że zbiory <math>\displaystyle Y_1,Y_2</math> są niepuste otrzymujemy, że zbiory <math>\displaystyle X_1, X_2</math> też są niepuste. Weźmy teraz dowolny element <math>\displaystyle x_1\in X_1</math> oraz <math>\displaystyle x_2\in X_2</math>. Pokażemy, że <math>\displaystyle x_1 \leq_X x_2</math>. Przypuśćmy, że tak nie jest. Wtedy <math>\displaystyle x_1 >_X x_2</math> i ponieważ funkcja <math>\displaystyle f</math> jest injektywna i rosnąca, to otrzymamy <math>\displaystyle f(x_1) >_Y f(x_2)</math>. Otrzymaliśmy sprzeczność, gdyż <math>\displaystyle f(x_1) \in Y_1</math> i <math>\displaystyle f(x_2) \in Y_2</math>, a zbiory <math>\displaystyle Y_1,Y_2</math> są przekrojem <math>\displaystyle Y</math>. Wobec tego konieczne jest, aby <math>\displaystyle x_1 \leq x_2</math>. Dowiedliśmy więc, że zbiory <math>\displaystyle X_1,X_2</math> są przekrojem <math>\displaystyle X</math>.
  
Ponieważ <math>\displaystyle X</math> jest ciągły to w <math>\displaystyle X_1</math> jest element największy lub w <math>\displaystyle X_2</math> element najmniejszy. Zajmiemy się najpierw pierwszym przypadkiem. Niech <math>\displaystyle x_1</math> będzie elementem największym w <math>\displaystyle X_1</math> pokażemy, że <math>\displaystyle f(x_1)</math> jest największy w <math>\displaystyle Y_1</math>. Weźmy dowolny element  <math>\displaystyle y\in Y_1</math>, wtedy ponieważ <math>\displaystyle f</math> jest bijekcją to istnieje <math>\displaystyle z\in X</math> taki, że <math>\displaystyle f(z)=y</math>. Ponieważ <math>\displaystyle y\in Y_1</math> to <math>\displaystyle z\in X_1</math>. Skoro <math>\displaystyle x_1</math> jest największy w <math>\displaystyle X_1</math> to w szczególności <math>\displaystyle z \leq_X x_1</math> i z faktu, że funkcja <math>\displaystyle f</math> jest rosnąca otrzymujemy <math>\displaystyle f(z)\leq_y f(x_1)</math>. Wobec tego <math>\displaystyle f(x_1)</math> jest największym elementem <math>\displaystyle Y_1</math>. Drugi przypadek jest analogiczny. Wynika stąd że w <math>\displaystyle Y_1</math> jest element największy albo w <math>\displaystyle Y_2</math> jest element najmniejszy. Oznacza to, że przekrój <math>\displaystyle Y_1,Y_2</math> nie daje luki. Wobec dowolności wyboru przekroju <math>\displaystyle Y_1,Y_2</math>, udowodniliśmy, że żaden przekrój nie daje luki, a więc że <math>\displaystyle (Y,\leq_Y)</math> jest ciągły.
+
Ponieważ <math>\displaystyle X</math> jest ciągły, to w <math>\displaystyle X_1</math> jest element największy lub w <math>\displaystyle X_2</math> element najmniejszy. Zajmiemy się najpierw pierwszym przypadkiem. Niech <math>\displaystyle x_1</math> będzie elementem największym w <math>\displaystyle X_1</math>, pokażemy, że <math>\displaystyle f(x_1)</math> jest największy w <math>\displaystyle Y_1</math>. Weźmy dowolny element  <math>\displaystyle y\in Y_1</math>, wtedy ponieważ <math>\displaystyle f</math> jest bijekcją to istnieje <math>\displaystyle z\in X</math> taki, że <math>\displaystyle f(z)=y</math>. Ponieważ <math>\displaystyle y\in Y_1</math>, to <math>\displaystyle z\in X_1</math>. Skoro <math>\displaystyle x_1</math> jest największy w <math>\displaystyle X_1</math>, to w szczególności <math>\displaystyle z \leq_X x_1</math> i z faktu, że funkcja <math>\displaystyle f</math> jest rosnąca otrzymujemy <math>\displaystyle f(z)\leq_y f(x_1)</math>. Wobec tego <math>\displaystyle f(x_1)</math> jest największym elementem <math>\displaystyle Y_1</math>. Drugi przypadek jest analogiczny. Wynika stąd, że w <math>\displaystyle Y_1</math> jest element największy albo w <math>\displaystyle Y_2</math> jest element najmniejszy. Oznacza to, że przekrój <math>\displaystyle Y_1,Y_2</math> nie daje luki. Wobec dowolności wyboru przekroju <math>\displaystyle Y_1,Y_2</math> udowodniliśmy, że żaden przekrój nie daje luki, a więc że <math>\displaystyle (Y,\leq_Y)</math> jest ciągły.
 
</div></div>
 
</div></div>
  
Linia 661: Linia 661:
 
}}
 
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
Użyj warunku z twierdzenia 2.13 (patrz [[#twierdzenie_2_13|twierdzenie 2.13.]]) lub zasady minimum.
+
Użyj warunku z Twierdzenia 2.13 (patrz [[#twierdzenie_2_13|Twierdzenie 2.13.]]) lub zasady minimum (patrz [[Logika i teoria mnogości/Wykład 7: Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje#twierdzenie_5_2|zasada minimum]]).
 
</div></div>
 
</div></div>
 
<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">   
  
Weźmy dowolny przekrój liczb naturalnych <math>\displaystyle N_1,N_2</math>. Zbiór <math>\displaystyle N_2</math> jest niepusty więc w myśl zasady minimum ma element najmniejszy. Wobec tego przekrój ten nie daje luki. Wobec dowolności wyboru przekroju otrzymujemy, że żaden przekrój nie daje luki, a więc porządek jest ciągły.
+
Weźmy dowolny przekrój liczb naturalnych <math>\displaystyle N_1,N_2</math>. Zbiór <math>\displaystyle N_2</math> jest niepusty, więc w myśl zasady minimum ma element najmniejszy. Wobec tego przekrój ten nie daje luki. Wobec dowolności wyboru przekroju otrzymujemy, że żaden przekrój nie daje luki, a więc porządek jest ciągły.
  
 
</div></div>
 
</div></div>
Linia 677: Linia 677:
 
<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">   
  
Weźmy dowolne liczby rzeczywiste <math>\displaystyle A,B \in \mathbb R</math> dla których <math>\displaystyle A<B</math>. Niech <math>\displaystyle a, b\in \mathbb{Q}^\mathbb{N}</math> będą ciągami Cauchy'ego wyznaczającymi odpowiednio liczby <math>\displaystyle A</math> i <math>\displaystyle B</math>. Z definicji mniejszości <math>\displaystyle A<B</math> oznacza dokładnie, że
+
Weźmy dowolne liczby rzeczywiste <math>\displaystyle A,B \in \mathbb R</math>, dla których <math>\displaystyle A<B</math>. Niech <math>\displaystyle a, b\in \mathbb{Q}^\mathbb{N}</math> będą ciągami Cauchy'ego wyznaczającymi odpowiednio liczby <math>\displaystyle A</math> i <math>\displaystyle B</math>. Z definicji mniejszości <math>\displaystyle A<B</math> oznacza dokładnie, że:
  
 
<center><math>\displaystyle \exists_{\varepsilon: \varepsilon \in \mathbb{Q} \wedge \varepsilon >0} \exists_{n_0\in \mathbb{N}} \forall_{k: k\in \mathbb{N} \wedge k \geq n_0} a_k+\varepsilon < b_k.
 
<center><math>\displaystyle \exists_{\varepsilon: \varepsilon \in \mathbb{Q} \wedge \varepsilon >0} \exists_{n_0\in \mathbb{N}} \forall_{k: k\in \mathbb{N} \wedge k \geq n_0} a_k+\varepsilon < b_k.
 
</math></center>
 
</math></center>
  
Niech <math>\displaystyle \varepsilon_0</math> oraz <math>\displaystyle n_0</math> będą liczbami, o których istnieniu  mówi powyższa formuła. Ponieważ <math>\displaystyle a,b</math> są ciągami Cauchy'ego to dla <math>\displaystyle \varepsilon_1= \frac{\varepsilon_0}{4}</math> można dobrać <math>\displaystyle m_0</math> takie, że dla dowolnych liczb <math>\displaystyle k,l \geq m_0</math> będziemy mieli <math>\displaystyle |a_k -a_l| < \varepsilon_1</math> oraz <math>\displaystyle |b_k -b_l| < \varepsilon_1</math>. Niech teraz <math>\displaystyle N_0</math> będzie większą z liczb <math>\displaystyle n_0</math> i <math>\displaystyle m_0</math>. Pokażemy, że liczba <math>\displaystyle a_{N_0}+2 \varepsilon_1</math> jest szukaną liczbą <math>\displaystyle q</math>.
+
Niech <math>\displaystyle \varepsilon_0</math> oraz <math>\displaystyle n_0</math> będą liczbami, o których istnieniu  mówi powyższa formuła. Ponieważ <math>\displaystyle a,b</math> są ciągami Cauchy'ego, to dla <math>\displaystyle \varepsilon_1= \frac{\varepsilon_0}{4}</math> można dobrać <math>\displaystyle m_0</math> takie, że dla dowolnych liczb <math>\displaystyle k,l \geq m_0</math> będziemy mieli <math>\displaystyle |a_k -a_l| < \varepsilon_1</math> oraz <math>\displaystyle |b_k -b_l| < \varepsilon_1</math>. Niech teraz <math>\displaystyle N_0</math> będzie większą z liczb <math>\displaystyle n_0</math> i <math>\displaystyle m_0</math>. Pokażemy, że liczba <math>\displaystyle a_{N_0}+2 \varepsilon_1</math> jest szukaną liczbą <math>\displaystyle q</math>.
  
Zaczniemy od pokazania, że <math>\displaystyle a_{N_0}+2 \varepsilon_1 < B</math>. Wiemy, że
+
Zaczniemy od pokazania, że <math>\displaystyle a_{N_0}+2 \varepsilon_1 < B</math>. Wiemy, że:
  
 
<center><math>\displaystyle  
 
<center><math>\displaystyle  
Linia 690: Linia 690:
 
</math></center>
 
</math></center>
  
oraz dla każdego <math>\displaystyle k \geq N_0</math> mamy
+
oraz dla każdego <math>\displaystyle k \geq N_0</math> mamy:
  
 
<center><math>\displaystyle |b_{N_0} - b_k|<\frac{\varepsilon_0}{4}.
 
<center><math>\displaystyle |b_{N_0} - b_k|<\frac{\varepsilon_0}{4}.
 
</math></center>
 
</math></center>
  
Z powyższej nierówności otrzymujemy
+
Z powyższej nierówności otrzymujemy:
  
<center><math>\displaystyle b_{N_0} - \frac{\varepsilon_0}{4}< b_k.
+
<center><math>\displaystyle b_{N_0} - \frac{\varepsilon_0}{4}< b_k,
 
</math></center>
 
</math></center>
  
wobec czego z ostatniej równości i z 2.1 otrzymujemy
+
wobec czego z ostatniej równości i z 2.1 otrzymujemy:
  
<center><math>\displaystyle a_{N_0}+\frac{3 \varepsilon_0}{4} < b_k
+
<center><math>\displaystyle a_{N_0}+\frac{3 \varepsilon_0}{4} < b_k,
 
</math></center>
 
</math></center>
  
 
skąd wynika, że <math>\displaystyle a_{N_0}+2 \varepsilon_1<B</math>.
 
skąd wynika, że <math>\displaystyle a_{N_0}+2 \varepsilon_1<B</math>.
  
Pokażemy teraz, że <math>\displaystyle a_{N_0}+2 \varepsilon_1 > A</math>. Wiemy, że dla każdego <math>\displaystyle k\geq N_0</math> mamy
+
Pokażemy teraz, że <math>\displaystyle a_{N_0}+2 \varepsilon_1 > A</math>. Wiemy, że dla każdego <math>\displaystyle k\geq N_0</math> mamy:
  
 
<center><math>\displaystyle |a_{N_0} - a_k|<\frac{\varepsilon_0}{4}.
 
<center><math>\displaystyle |a_{N_0} - a_k|<\frac{\varepsilon_0}{4}.
 
</math></center>
 
</math></center>
  
Oznacza to, że
+
Oznacza to, że:
  
 
<center><math>\displaystyle a_k< a_{N_0} + \frac{\varepsilon_0}{4},
 
<center><math>\displaystyle a_k< a_{N_0} + \frac{\varepsilon_0}{4},
 
</math></center>
 
</math></center>
  
skąd otrzymujemy
+
skąd otrzymujemy:
  
 
<center><math>\displaystyle a_k +\frac{\varepsilon_0}{4} < a_{N_0} +\frac{\varepsilon_0} {2}.
 
<center><math>\displaystyle a_k +\frac{\varepsilon_0}{4} < a_{N_0} +\frac{\varepsilon_0} {2}.
 
</math></center>
 
</math></center>
  
Ponieważ powyższa równość jest prawdziwa dla każdego <math>\displaystyle k \geq N_0</math> to otrzymujemy <math>\displaystyle A<a_{N_0} +\frac{\varepsilon_0} {2} =a_{N_0} +2\varepsilon_1</math>.
+
Ponieważ powyższa równość jest prawdziwa dla każdego <math>\displaystyle k \geq N_0</math>, to otrzymujemy <math>\displaystyle A<a_{N_0} +\frac{\varepsilon_0} {2} =a_{N_0} +2\varepsilon_1</math>.
 
</div></div>
 
</div></div>
  
Linia 730: Linia 730:
 
}}</span>
 
}}</span>
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
Do tego celu przeanalizuj przekrój Dedekinda <math>\displaystyle (X_1 , X_2)</math> gdzie <math>\displaystyle X_1 =
+
Do tego celu przeanalizuj przekrój Dedekinda <math>\displaystyle (X_1 , X_2)</math>, gdzie <math>\displaystyle X_1 =
\left\{x\in \mathbb{Q}: x\leq\rho\right\}</math> gdzie <math>\displaystyle \rho</math> jest ustaloną liczbą niewymierną, oraz <math>\displaystyle X_2 = \mathbb{Q} \setminus X_1</math>.
+
\left\{x\in \mathbb{Q}: x\leq\rho\right\}</math> gdzie <math>\displaystyle \rho</math> jest ustaloną liczbą niewymierną oraz <math>\displaystyle X_2 = \mathbb{Q} \setminus X_1</math>.
 
</div></div>
 
</div></div>
 
<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 \rho</math> będzie ustaloną liczbą niewymierną. Istnienie takich liczb wynika z twierdzenia Cantora.
 
Niech <math>\displaystyle \rho</math> będzie ustaloną liczbą niewymierną. Istnienie takich liczb wynika z twierdzenia Cantora.
Zdefiniujmy zbiór <math>\displaystyle X_1</math> następująco
+
Zdefiniujmy zbiór <math>\displaystyle X_1</math> następująco:
  
 
<center><math>\displaystyle X_1 =\{x\in \mathbb{Q}: x \leq \rho\}
 
<center><math>\displaystyle X_1 =\{x\in \mathbb{Q}: x \leq \rho\}
Linia 743: Linia 743:
 
oraz zbiór <math>\displaystyle X_2=\mathbb{Q} \setminus X_1</math>. Z konstrukcji łatwo wynika, że zbiory <math>\displaystyle X_1,X_2</math> tworzą przekrój zbioru <math>\displaystyle (\mathbb{Q},\leq)</math>. Pokażemy, że taki przekrój daje lukę.
 
oraz zbiór <math>\displaystyle X_2=\mathbb{Q} \setminus X_1</math>. Z konstrukcji łatwo wynika, że zbiory <math>\displaystyle X_1,X_2</math> tworzą przekrój zbioru <math>\displaystyle (\mathbb{Q},\leq)</math>. Pokażemy, że taki przekrój daje lukę.
  
Przypuśćmy, że w zbiorze <math>\displaystyle X_1</math> istnieje element największy oznaczmy, go przez <math>\displaystyle x_0</math>. Rozpatrzymy zbiór <math>\displaystyle Y_1=\{x \in \mathbb R: x \leq \rho\}</math>. W zbiorze <math>\displaystyle Y_1</math> elementem największym jest <math>\displaystyle \rho</math>. Ponieważ <math>\displaystyle X_1 \subset Y_1</math> to <math>\displaystyle x_0 \leq \rho</math>. Ponieważ <math>\displaystyle \rho</math> jest niewymierne to równość jest wykluczona, czyli <math>\displaystyle x_0 < \rho</math>. Wtedy jednak z ćwiczenia 2.17 (patrz [[#cwiczenie_2_17|ćwiczenie 2.17.]]) otrzymujemy, że istnieje <math>\displaystyle z\in \mathbb{Q}</math> takie, że <math>\displaystyle x_0 < z <\rho</math>. Taki element <math>\displaystyle z</math> musi należeć do <math>\displaystyle X_1</math> co przeczy temu, że <math>\displaystyle x_0</math> jest największy w <math>\displaystyle X_1</math>. Wobec tego w zbiorze <math>\displaystyle X_1</math> nie ma elementu największego.
+
Przypuśćmy, że w zbiorze <math>\displaystyle X_1</math> istnieje element największy, oznaczmy go przez <math>\displaystyle x_0</math>. Rozpatrzymy zbiór <math>\displaystyle Y_1=\{x \in \mathbb R: x \leq \rho\}</math>. W zbiorze <math>\displaystyle Y_1</math> elementem największym jest <math>\displaystyle \rho</math>. Ponieważ <math>\displaystyle X_1 \subset Y_1</math>, to <math>\displaystyle x_0 \leq \rho</math>. Ponieważ <math>\displaystyle \rho</math> jest niewymierne, to równość jest wykluczona, czyli <math>\displaystyle x_0 < \rho</math>. Wtedy jednak z ćwiczenia 2.17 (patrz [[#cwiczenie_2_17|ćwiczenie 2.17.]]) otrzymujemy, że istnieje <math>\displaystyle z\in \mathbb{Q}</math> takie, że <math>\displaystyle x_0 < z <\rho</math>. Taki element <math>\displaystyle z</math> musi należeć do <math>\displaystyle X_1</math>, co przeczy temu, że <math>\displaystyle x_0</math> jest największy w <math>\displaystyle X_1</math>. Wobec tego w zbiorze <math>\displaystyle X_1</math> nie ma elementu największego.
  
 
Analogiczny dowód faktu, że w <math>\displaystyle X_2</math> nie ma elementu najmniejszego pomijajmy (należy rozważyć zbiór <math>\displaystyle Y_2= \{x \in \mathbb R: \rho \leq x\}</math>).
 
Analogiczny dowód faktu, że w <math>\displaystyle X_2</math> nie ma elementu najmniejszego pomijajmy (należy rozważyć zbiór <math>\displaystyle Y_2= \{x \in \mathbb R: \rho \leq x\}</math>).
Linia 758: Linia 758:
 
{{dowod|||
 
{{dowod|||
  
Przed przystąpieniem do dowodu przejrzyj dowód twierdzenia Cantora 2.9 z wykładu 9 o
+
Przed przystąpieniem do dowodu przejrzyj dowód twierdzenia Cantora 2.9 z wykładu 9 o
nieprzeliczalności <math>\displaystyle \mathbb{R}</math>.
+
nieprzeliczalności <math>\displaystyle \mathbb{R}</math> (patrz [[Logika i teoria mnogości/Wykład 9: Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy kontinuum#twierdzenie_2_9|Wykład 9, Twierdzenie Cantora]]).
 
Niech <math>\displaystyle (X_1 , X_2)</math> będzie przekrojem w <math>\displaystyle \mathbb{R}</math>. Zbiory <math>\displaystyle X_1 , X_2</math> są niepuste.
 
Niech <math>\displaystyle (X_1 , X_2)</math> będzie przekrojem w <math>\displaystyle \mathbb{R}</math>. Zbiory <math>\displaystyle X_1 , X_2</math> są niepuste.
 
Wybierzmy dwie liczby wymierne <math>\displaystyle x_0</math> w <math>\displaystyle X_1</math> i <math>\displaystyle y_0</math> w <math>\displaystyle X_2</math>. (Sprawdź jako
 
Wybierzmy dwie liczby wymierne <math>\displaystyle x_0</math> w <math>\displaystyle X_1</math> i <math>\displaystyle y_0</math> w <math>\displaystyle X_2</math>. (Sprawdź jako
Linia 779: Linia 779:
 
</math></center>
 
</math></center>
  
Jako ćwiczenie podamy sprawdzenie następujących własności ciągów <math>\displaystyle x_i</math> i <math>\displaystyle y_i</math>.
+
Jako ćwiczenie podamy sprawdzenie następujących własności ciągów <math>\displaystyle x_i</math> i <math>\displaystyle y_i</math>:
# ciąg <math>\displaystyle x</math> jest słabo rosnący czyli <math>\displaystyle x_i \leq x_{i+1}</math>.
+
# ciąg <math>\displaystyle x</math> jest słabo rosnący czyli <math>\displaystyle x_i \leq x_{i+1}</math>,
# ciąg <math>\displaystyle y</math> jest słabo malejący czyli <math>\displaystyle y_i \geq y_{i+1}</math>.
+
# ciąg <math>\displaystyle y</math> jest słabo malejący czyli <math>\displaystyle y_i \geq y_{i+1}</math>,
# <math>\displaystyle y_i - x_i = \frac{y_0 - x_0}{2^i}</math>.
+
# <math>\displaystyle y_i - x_i = \frac{y_0 - x_0}{2^i}</math>,
# <math>\displaystyle  | x_{i+1} - x_i |  \leq \frac{y_0 - x_0}{2^{i+1}}</math>.
+
# <math>\displaystyle  | x_{i+1} - x_i |  \leq \frac{y_0 - x_0}{2^{i+1}}</math>,
 
# <math>\displaystyle  | y_{i+1} - y_i |  \leq \frac{y_0 - x_0}{2^{i+1}}</math>.
 
# <math>\displaystyle  | y_{i+1} - y_i |  \leq \frac{y_0 - x_0}{2^{i+1}}</math>.
  
Własności te implikują fakt, że zarówno <math>\displaystyle x_i</math> jak i <math>\displaystyle  y_i</math> są ciągami Cauchyego jak i
+
Własności te implikują fakt, że zarówno <math>\displaystyle x_i</math> jak i <math>\displaystyle  y_i</math> są ciągami Cauchy'ego, jak i
 
to, że są równoważne w sensie definicji liczb rzeczywistych. Zatem istnieje liczba
 
to, że są równoważne w sensie definicji liczb rzeczywistych. Zatem istnieje liczba
rzeczywista <math>\displaystyle G</math> zadana jednocześnie przez aproksymacje <math>\displaystyle x</math> i <math>\displaystyle y</math> czyli
+
rzeczywista <math>\displaystyle G</math> zadana jednocześnie przez aproksymacje <math>\displaystyle x</math> i <math>\displaystyle y</math>, czyli
<math>\displaystyle G= [x]_{\simeq} = [y]_\simeq</math>. Gdy <math>\displaystyle G\in X_1</math> to <math>\displaystyle X_1</math> ma element największy. W
+
<math>\displaystyle G= [x]_{\simeq} = [y]_\simeq</math>. Gdy <math>\displaystyle G\in X_1</math>, to <math>\displaystyle X_1</math> ma element największy. W
 
przeciwnym wypadku <math>\displaystyle G\in X_2</math> i wtedy <math>\displaystyle X_2</math> ma element najmniejszy.
 
przeciwnym wypadku <math>\displaystyle G\in X_2</math> i wtedy <math>\displaystyle X_2</math> ma element najmniejszy.
 
}}
 
}}
Linia 801: Linia 801:
 
<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">   
  
Wiemy, że porządek <math>\displaystyle (\mathbb R, \leq)</math> jest ciągły. Analogiczne rozumowanie do rozwiązania zadania 2.18 (patrz [[#cwiczenie_2_18|ćwiczenie 2.18.]]) prowadzi do udowodnienia nieciągłości <math>\displaystyle (\mathbb R\setminus \mathbb{Q}, \leq)</math> (w roli <math>\displaystyle \rho</math> tym razem bierzemy liczbą wymierną). Ponieważ ciągłość jest przenoszona przez podobieństwo to porządki te nie mogą być podobne.
+
Wiemy, że porządek <math>\displaystyle (\mathbb R, \leq)</math> jest ciągły. Analogiczne rozumowanie do rozwiązania Ćwiczenia 2.18 (patrz [[#cwiczenie_2_18|Ćwiczenie 2.18.]]) prowadzi do udowodnienia nieciągłości <math>\displaystyle (\mathbb R\setminus \mathbb{Q}, \leq)</math> (w roli <math>\displaystyle \rho</math> tym razem bierzemy liczbą wymierną). Ponieważ ciągłość jest przenoszona przez podobieństwo, to porządki te nie mogą być podobne.
 
</div></div>
 
</div></div>

Wersja z 19:50, 17 wrz 2006

Zbiory uporządkowane

Definicja 1.1.

Porządkiem (w wielu podręcznikach jest używana jest również nazwa poset, pochodząca od angielskiego skrótu partially ordered set) nazywamy parę , gdzie jest zbiorem, a jest relacją:

  1. zwrotną,
  2. przechodnią,
  3. antysymetryczną, to znaczy jeżeli oraz , to .

Jeżeli dodatkowo relacja jest spójna (to znaczy taka, że lub ), to porządek nazywamy liniowym.

Często oznaczamy relacje porządkującą jako . Oznaczamy też , gdy oraz .

Definicja 1.2.

Element nazywamy maksymalnym w porządku , gdy Parser nie mógł rozpoznać (nieznana funkcja „\hspace”): {\displaystyle \displaystyle \forall_{x\in X} \;\; a\leq x \hspace*{0.1mm} \Rightarrow a=x} .

Element nazywamy minimalnym w porządku , gdy Parser nie mógł rozpoznać (nieznana funkcja „\hspace”): {\displaystyle \displaystyle \forall_{x\in X} \;\; x \leq a \hspace*{0.1mm} \Rightarrow a=x} .

Element nazywamy największym w porządku , gdy .

Element nazywamy najmniejszym w porządku , gdy .

Definicja 1.3.

Niech oraz . Mówimy, że jest majorantą zbioru , gdy .

Niech oraz . Mówimy, że jest minorantą zbioru , gdy .

Definicja 1.4.

. Element nazywamy supremum zbioru , gdy:

  1. ,
  2. Parser nie mógł rozpoznać (nieznana funkcja „\hspace”): {\displaystyle \displaystyle (\forall_{a\in A} \;\; a \leq b) \hspace*{0.1mm} \Rightarrow a_0 \leq b} .

Łatwo zauważyć, że supremum, o ile istnieje, jest jedyne i jest najmniejszą z majorant. Jeżeli istnieje supremum dla będziemy je oznaczać .

Definicja 1.5.

. Element nazywamy infimum zbioru , gdy:

  1. Parser nie mógł rozpoznać (nieznana funkcja „\hspace”): {\displaystyle \displaystyle (\forall_{a \in A} \;\; b \leq a )\hspace*{0.1mm} \Rightarrow b \leq b_0}

Tak jak w przypadku supremum infimum, o ile istnieje, jest jedyne i jest największą z minorant zbioru. Jeżeli istnieje infimum dla , będziemy je oznaczać .

Ćwiczenie 1.6

Niech będzie ustalonym zbiorem i niech . Zdefiniujmy relację następująco:

Udowodnij, że jest zbiorem uporządkowanym.

Rozwiązanie
Uwaga 1.7.

Nadużywając notacji, będziemy czasem używać symbolu dla oznaczenia relacji zdefiniowanej w poprzednim ćwiczeniu. Zwracamy przy tym uwagę, że nie ma czegoś takiego jak relacja , gdyż musiałaby ona być określona w zbiorze wszystkich zbiorów, który nie istnieje. W przypadku jednak, gdy rozważamy jedynie podzbiory ustalonego zbioru , możemy mówić o relacji bycia podzbiorem. Czasem dla podkreślenia, że mówimy o podzbiorach ustalonego zbioru, będziemy pisać .

Ćwiczenie 1.8

{{{3}}}
Rozwiązanie

Ćwiczenie 1.9

W zbiorze liczb naturalnych zdefiniujemy relację następująco:

Udowodnij, że relacja ta porządkuje zbiór . Czy w tak uporządkowanym zbiorze istnieją elementy najmniejszy i największy?

Rozwiązanie

Ćwiczenie 1.10

W zbiorze funkcji z w (czyli ) zdefiniujmy relację następująco:

Wskazówka
Rozwiązanie

Ćwiczenie 1.11

Niech . W zbiorze zdefiniujemy relację następująco:

Sprawdź, czy relacja jest zwrotna, przechodnia i antysymetryczna.

Wskazówka
Rozwiązanie

Ćwiczenie 1.12

Niech . W zbiorze zdefiniujemy relację następująco:

Udowodnij, że relacja porządkuje zbiór . Czy w porządku istnieją elementy najmniejszy i największy?

Rozwiązanie

Ćwiczenie 1.13

Podaj przykład przeliczalnego porządku, w którym istnieje element najmniejszy i największy.

Rozwiązanie

Ćwiczenie 1.14

Podaj przykład porządku, w którym istnieje element maksymalny, który nie jest elementem największym. Czy istnieje taki porządek, żeby element maksymalny był jedyny?

Rozwiązanie

Ćwiczenie 1.15

Podaj przykład zbioru liniowo uporządkowanego , w którym istnieje podzbiór niemający supremum.

Rozwiązanie

Ćwiczenie 1.16

Udowodnij, że zbiorze uporządkowanym istnieje wtedy i tylko wtedy, gdy w istnieje element najmniejszy.

Rozwiązanie

Ćwiczenie 1.17

Udowodnij, że zbiorze uporządkowanym , jeśli każdy podzbiór ma supremum, to każdy podzbiór ma infimum.

Rozwiązanie

Ćwiczenie 1.18

Podaj przykład porządku takiego, że podzbiór ma supremum wtedy i tylko wtedy, gdy jest skończony.

Rozwiązanie

Definicja 1.19

jest łańcuchem w porządku , gdy każde dwa elementy są porównywalne w sensie . Oznacza to, że porządek indukowany na zbiorze , czyli jest porządkiem liniowym.

Definicja 1.20.

Zbiór jest antyłańcuchem w porządku , gdy żadne dwa różne elementy nie są porównywalne w sensie . Formalnie, jeśli następująca formuła jest prawdziwa:

Ćwiczenie 1.21

Sprawdź, czy suma antyłańcuchów musi być antyłańcychem oraz czy suma łańcuchów musi być łańcuchem.

Rozwiązanie

Ćwiczenie 1.22

Czy antyłańcuch może być łańcuchem?

Rozwiązanie

Dla każdego porządku , zarówno zbiór jego łańcuchów jak i zbiór jego antyłańcuchów jest uporządkowany przez inkluzję. Możemy więc mówić o największym (maksymalnym) ze względu na inkluzję łańcuchu (antyłańcuchu). Łatwo można pokazać, że zawsze istnieje najmniejszy łańcuch i antyłańcuch. Istnienie w każdym posecie maksymalnego łańcucha jest równoważne aksjomatowi wyboru. Tym zagadnieniem zajmujemy się w Wykładzie 11.

Ćwiczenie 1.23

Podaj przykład porządku, w których nie istnieje największy w sensie inkluzji łańcuch ani antyłańcuch.

Rozwiązanie

Ćwiczenie 1.24

Kiedy w porządku istnieje największy w sensie inkluzji łańcuch.

Rozwiązanie

Ćwiczenie 1.25

Kiedy w porządku istnieje największy w sensie inkluzji antyłańcuch.

Rozwiązanie

Ćwiczenie 1.26

Czy porządek, w którym każdy łańcuch jest skończony, musi być skończony? Czy taki porządek może zawierać łańcuchy o dowolnie dużej skończonej mocy?

Rozwiązanie

Ćwiczenie 1.27

Rozważmy zbiór uporządkowany relacją podzielności (czyli ). Wypisz wszystkie łańcuchy maksymalne w sensie inkluzji. Wypisz wszystkie antyłańcuchy maksymalne w sensie inkluzji.

Rozwiązanie

Zbiory liniowo uporządkowane

Definicja 2.1.

Porządki liniowe i nazywamy podobnymi, gdy istnieje bijekcja rosnąca, czyli taka, że jeżeli , to .

Ćwiczenie 2.2

Dla podobieństwa , jeżeli , to

Rozwiązanie

Definicja 2.3.

Porządek nazywamy gęstym, gdy Parser nie mógł rozpoznać (nieznana funkcja „\hspace”): {\displaystyle \displaystyle \forall_{x,y\in X} \;\; x<y \hspace*{0.1mm} \Rightarrow \exists_{z\in X} \;\; x<z<y}

Ćwiczenie 2.4

Gęstość jest przenoszona przez podobieństwo.

Rozwiązanie

Ćwiczenie 2.5

W zbiorze rozważymy dwie relacje porządkujące zdefiniowane następująco:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned f \sqsubseteq_1 g \Leftrightarrow \forall_{n \in \mathbb{N}} f(n) \leq g(n),\\ f \sqsubseteq_2 g \Leftrightarrow [f=g \vee \exists_{n_0 \in \mathbb{N}} (f(n) < g(n)\wedge \forall_{n<n_0} f(n) =g(n))]. \endaligned}

Sprawdź, czy te porządki są podobne.

Wskazówka
Rozwiązanie

Definicja 2.6.

Niech będzie porządkiem liniowym. Przekrojem Dedekinda w nazywamy parę zbiorów , taką że:

  1. .
  2. .
  3. .
  4. i .

Definicja 2.7.

Przekrój daje skok, jeżeli ma element największy i ma element najmniejszy.

Ćwiczenie 2.8

Liniowy porządek jest gęsty wtedy i tylko wtedy, gdy żaden przekrój nie daje skoku.

Rozwiązanie

Ćwiczenie 2.9

W zbiorze rozważymy relację porządkującą zdefiniowaną następująco:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned f \sqsubseteq g \Leftrightarrow [f=g \vee \exists_{n_0 \in \mathbb{N}} (f(n_0) < g(n_0)\wedge \forall_{n<n_0} f(n) =g(n))]. \endaligned}

Sprawdź, czy ten porządek jest gęsty.

Rozwiązanie

Definicja 2.10.

Przekrój daje lukę, jeżeli nie ma elementu największego i nie ma elementu najmniejszego.

Definicja 2.11.

Porządek liniowy nazywamy ciągłym wtedy i tylko wtedy, gdy żaden przekrój nie daje luki.

Twierdzenie 2.12.

W porządku ciągłym każdy niepusty zbiór ograniczony od góry ma supremum.

Dowód

Niech będzie zbiorem ograniczonym od góry. Łatwo zauważyć, że jeżeli jakieś ograniczenie zbioru należy do , to jest jego supremum. Załóżmy zatem, że żadne ograniczenie do nie należy. Utwórzmy parę zbiorów: oraz . Pierwszy jest domknięciem w dół zbioru , czyli wraz z każdym jego elementem dołączamy do niego wszystkie mniejsze. Zatem . Do należą wszystkie ograniczenia górne zbioru więc musi on być niepusty. Z konstrukcji wynika . Korzystając z ciągłości, otrzymujemy, że ma element największy lub ma element najmniejszy. Gdy posiada element największy , to jest on supremum . Istotnie, element góruje nad , więc tym bardziej nad . Gdy element góruje nad , to góruje też nad , zatem jeżeli należy do , musi być równy , gdy zaś należy do , to . W drugim przypadku, gdy w nie ma elementu największego, supremum jest najmniejszy element z . Istotnie, góruje nad . Jeżeli jakiś góruje nad , to również nad . nie może należeć do , bo w nie ma największego. Należy więc do , zatem . Proszę o zwrócenie uwagi na fakt, że możliwe jest, aby zarówno miał element największy, jak i miał element najmniejszy. Wtedy supremum jest ten pochodzący z .

End of proof.gif

Twierdzenie 2.13.

W porządku liniowym , jeżeli każdy niepusty zbiór ograniczony od góry ma supremum, to porządek jest ciągły.

Dowód

Weźmy przekrój Dedekinda . jest ograniczony od góry przez elementy z . , ma więc supremum . Jeżeli , to ma element największy. W przeciwnym przypadku . Gdyby dla pewnego , to zbiór miałby mniejsze ograniczenie górne niż . To jest niemożliwe, musi więc być dla każdego . Zatem jest najmniejszy w .

End of proof.gif

Ćwiczenie 2.14

W porządku liniowym każdy niepusty zbiór ograniczony od dołu ma infimum wtedy i tylko wtedy, gdy porządek jest ciągły.

Wskazówka

Ćwiczenie 2.15.

Udowodnij, że ciągłość jest przenoszona przez podobieństwo.

Wskazówka
Rozwiązanie

Ćwiczenie 2.16

Pokaż, że zbiór liczb naturalnych jest ciągły.

Wskazówka
Rozwiązanie

Ćwiczenie 2.17

Udowodnij, że dla dowolnych liczb rzeczywistych takich, że istnieje liczba wymierna taka, że .

Rozwiązanie

Ćwiczenie 2.18

Pokaż, że zbiór nie jest ciągły.

Wskazówka
Rozwiązanie

Twierdzenie 2.19.

jest ciągła.

Dowód

Przed przystąpieniem do dowodu przejrzyj dowód twierdzenia Cantora 2.9 z wykładu 9 o nieprzeliczalności (patrz Wykład 9, Twierdzenie Cantora). Niech będzie przekrojem w . Zbiory są niepuste. Wybierzmy dwie liczby wymierne w i w . (Sprawdź jako ćwiczenie, że z każdego przekroju da się wybrać liczby wymierne). Skonstruujmy dwa ciągi oraz zdefiniowane indukcyjnie. są zadane.

Jako ćwiczenie podamy sprawdzenie następujących własności ciągów i :

  1. ciąg jest słabo rosnący czyli ,
  2. ciąg jest słabo malejący czyli ,
  3. ,
  4. ,
  5. .

Własności te implikują fakt, że zarówno jak i są ciągami Cauchy'ego, jak i to, że są równoważne w sensie definicji liczb rzeczywistych. Zatem istnieje liczba rzeczywista zadana jednocześnie przez aproksymacje i , czyli . Gdy , to ma element największy. W przeciwnym wypadku i wtedy ma element najmniejszy.

End of proof.gif

Ćwiczenie 2.20

Udowodnij, że porządki i nie są podobne.

Rozwiązanie