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

From Studia Informatyczne

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ę \displaystyle (X,R), gdzie \displaystyle X jest zbiorem, a \displaystyle R \subset X^2 jest relacją:

  1. zwrotną,
  2. przechodnią,
  3. antysymetryczną, to znaczy jeżeli \displaystyle (x,y) \in R oraz \displaystyle (y,x) \in R, to \displaystyle x=y.

Jeżeli dodatkowo relacja \displaystyle R jest spójna (to znaczy taka, że \displaystyle \forall_{x,y \in X} \;\; (x,y)\in R lub \displaystyle   (y,x)\in R ), to porządek nazywamy liniowym.

Często oznaczamy relacje porządkującą jako \displaystyle \leq. Oznaczamy też \displaystyle x<y, gdy \displaystyle x \leq y oraz \displaystyle x\neq y.

Definicja 1.2.

Element \displaystyle a nazywamy maksymalnym w porządku \displaystyle (X,\leq ), gdy \displaystyle \forall_{x\in X} \;\; a\leq x \hspace*{0.1mm} \Rightarrow  a=x.

Element \displaystyle a nazywamy minimalnym w porządku \displaystyle (X,\leq ), gdy \displaystyle \forall_{x\in X} \;\; x \leq a \hspace*{0.1mm} \Rightarrow  a=x.

Element \displaystyle a nazywamy największym w porządku \displaystyle (X,\leq ), gdy \displaystyle \forall_{x\in X} \;\; x \leq a.

Element \displaystyle a nazywamy najmniejszym w porządku \displaystyle (X,\leq ), gdy \displaystyle \forall_{x\in X} \;\; a \leq x.

Definicja 1.3.

Niech \displaystyle A \subset X oraz \displaystyle b\in X. Mówimy, że \displaystyle b jest majorantą zbioru \displaystyle A, gdy \displaystyle \forall_{a\in A} \;\; a\leq b.

Niech \displaystyle A \subset X oraz \displaystyle b\in X. Mówimy, że \displaystyle b jest minorantą zbioru \displaystyle A, gdy \displaystyle \forall_{a \in A} \;\; b \leq a.

Definicja 1.4.

\displaystyle A \subset X. Element \displaystyle a_0 \in X nazywamy supremum zbioru \displaystyle A, gdy:

  1. \displaystyle \forall_{a\in A} \;\;  a \leq a_0,
  2. \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 \displaystyle A będziemy je oznaczać \displaystyle \bigvee A.

Definicja 1.5.

\displaystyle A \subset X. Element \displaystyle b_0 \in X nazywamy infimum zbioru \displaystyle A, gdy:

  1. \displaystyle \forall_{a\in A} \;\;  b_0 \leq a
  2. \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 \displaystyle A, będziemy je oznaczać \displaystyle \bigwedge A.

Ćwiczenie 1.6

Niech \displaystyle X będzie ustalonym zbiorem i niech \displaystyle A\subset \mathcal{P}(X). Zdefiniujmy relację \displaystyle \sqsubseteq \subset A\times A następująco:

\displaystyle a \sqsubseteq b \Leftrightarrow a\subseteq b.

Udowodnij, że \displaystyle (A,\sqsubseteq) jest zbiorem uporządkowanym.

Rozwiązanie

Pokażemy, że \displaystyle \sqsubseteq spełnia warunki bycia porządkiem.

1. Dla dowolnego zbioru \displaystyle x mamy \displaystyle x\subset x, więc w szczególności dla elementów \displaystyle a\in A również \displaystyle a\subset a, czyli \displaystyle a \sqsubseteq a. Relacja \displaystyle \sqsubseteq jest więc zwrotna.

2. Dla dowolnych zbiorów \displaystyle x,y,z mamy \displaystyle (x\subset y \wedge y\subset z) \Rightarrow x \subset z. Weźmy dowolne elementy \displaystyle a,b,c\in A, dla których mamy \displaystyle a\sqsubseteq b oraz \displaystyle b\sqsubseteq c. Z definicji \displaystyle \sqsubseteq wynika, że wtedy \displaystyle a\subset b oraz \displaystyle b\subset c. Otrzymujemy więc \displaystyle a\subset c, co oznacza dokładnie, że \displaystyle a\sqsubseteq c. Relacja \displaystyle \sqsubseteq jest więc przechodnia.

3. Dla dowolnych zbiorów \displaystyle x,y z wiemy, że \displaystyle (x \subset y \wedge y\subset x) \Rightarrow x=y. Weźmy dowolne elementy \displaystyle a,b\in A, dla których \displaystyle a\sqsubseteq b oraz \displaystyle b\sqsubseteq a. Wtedy \displaystyle a\subset b oraz \displaystyle b\subset a, skąd otrzymujemy \displaystyle a=b. Relacja \displaystyle \sqsubseteq jest więc symetryczna.

Uwaga 1.7.

Nadużywając notacji, będziemy czasem używać symbolu \displaystyle \subset dla oznaczenia relacji \displaystyle \sqsubseteq zdefiniowanej w poprzednim ćwiczeniu. Zwracamy przy tym uwagę, że nie ma czegoś takiego jak relacja \displaystyle \subset, 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 \displaystyle X, możemy mówić o relacji bycia podzbiorem. Czasem dla podkreślenia, że mówimy o podzbiorach ustalonego zbioru, będziemy pisać \displaystyle \subset_X.

Ćwiczenie 1.8

Dla dowolnego zbioru \displaystyle A, jego zbiór potęgowy \displaystyle \mathcal{P}(A) jest uporządkowany przez inkluzję. Czy dla dowolnej niepustej rodziny \displaystyle r \subset \mathcal{P}(A) istnieje supremum i infimum?

Wskazówka

Sprawdź, czym jest \displaystyle \bigcup r i \displaystyle \bigcap r.

Rozwiązanie

Pokażemy, że dla dowolnej rodziny \displaystyle r\subset \mathcal{P}(A) mamy \displaystyle \bigcup r= \bigvee r oraz \displaystyle \bigcap r= \bigwedge r. Ze względu na symetrię udowodnimy tylko pierwszą równość (uwaga! sytuacja przestaje być symetryczna, jeśli dopuścimy puste rodziny). Pokażemy, że \displaystyle \bigcup r spełnia warunki bycia supremum.

  1. Z własności sumy wynika, że \displaystyle x\in r \Rightarrow x \subset \bigcup r.
  2. Weźmy dowolny element \displaystyle b \in A, dla którego prawdą jest, że \displaystyle \forall_{a\in r}  a \subset b. Weźmy dowolny element \displaystyle z\in \bigcup r, musi on należeć do pewnego zbioru \displaystyle a_z\in r. Ponieważ \displaystyle a_z\subset b, więc \displaystyle z\in b. Wynika stąd, że \displaystyle \bigcup r \subset b.

Ćwiczenie 1.9

W zbiorze liczb naturalnych zdefiniujemy relację \displaystyle | \subset \mathbb{N}^2 następująco:

\displaystyle \forall_{a,b\in \mathbb{N}} [a|b \Leftrightarrow \exists_{c\in \mathbb{N}} c\cdot a =b].

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

Rozwiązanie

Zaczniemy od pokazania, że \displaystyle | jest porządkiem.

1. Dla każdej liczby \displaystyle n\in \mathbb{N} wystarczy dobrać \displaystyle c=1, aby otrzymać \displaystyle 1 \cdot a = a. Więc relacja \displaystyle | jest zwrotna.

2. Weźmy dowolne liczby \displaystyle x,y,z\in \mathbb{N}, dla których \displaystyle x|y oraz \displaystyle y|z. Oznacza to, że istnieją liczby \displaystyle c_1, c_2 \in \mathbb{N} takie, że \displaystyle x \cdot c_1=y oraz \displaystyle y \cdot c_2= z. Z tych dwóch równości otrzymujemy \displaystyle x \cdot (c_1 \cdot c_2)=z. Wobec tego możemy do \displaystyle x dobrać \displaystyle c_3= c_1 \cdot c_2 tak, aby \displaystyle x \cdot c_3= z, a to oznacza, że \displaystyle x|z. Relacja \displaystyle | jest więc przechodnia.

3. Weźmy dowolne liczby \displaystyle n,m, dla których \displaystyle n|m oraz \displaystyle m|n. Oznacza to, że istnieją liczby \displaystyle c_1,c_2\in \mathbb{N}, dla których \displaystyle n \cdot c_1= m oraz \displaystyle m \cdot c_2 = n. Z tych dwóch równości otrzymujemy \displaystyle n\cdot (c_1\cdot c_2) = n. Rozważymy teraz dwa przypadki:

  1. Jeśli \displaystyle n\neq 0 to \displaystyle c_1 \cdot c_2 =1 i ponieważ są to liczby naturalne, to \displaystyle c_1=c_2=1. Oznacza to, że \displaystyle n=1 \cdot m= m.
  2. Jeśli \displaystyle n=0, to wtedy \displaystyle m=0\cdot c_1= 0 = n.

Udowodniliśmy więc, że relacja \displaystyle | jest antysymetryczna.

W porządku \displaystyle (\mathbb{N},|) elementem najmniejszym jest 1, a największym 0. Dla każdej liczby \displaystyle x\in \mathbb{N} możemy dobrać \displaystyle c=0 i wtedy \displaystyle x \cdot c=0, a więc \displaystyle x|0. Dla każdej \displaystyle x\in \mathbb{N} liczby możemy dobrać \displaystyle c=x i wtedy \displaystyle 1 \cdot c =x, co oznacza \displaystyle 1|x.

Ćwiczenie 1.10

W zbiorze funkcji z \displaystyle \mathbb{N} w \displaystyle \mathbb{N} (czyli \displaystyle \mathbb{N}^\mathbb{N}) zdefiniujmy relację \displaystyle R następująco:

\displaystyle \forall_{f,g\in \mathbb{N}^\mathbb{N}} [ f R g \Leftrightarrow \exists_{h\in \mathbb{N}^\mathbb{N}} h \circ f = g \circ h].

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

Wskazówka

  1. Jest zwrotna i przechodnia. Nie jest antysymetryczna.
  2. Aby pokazać, że nie jest antysymetryczna, rozważ funkcję stałą i identyczność.

Rozwiązanie

1. Dla każdej funkcji \displaystyle f\in \mathbb{N}^\mathbb{N} możemy dobrać funkcję \displaystyle 1_\mathbb{N} i wtedy \displaystyle 1_\mathbb{N} \circ f= f \circ 1_\mathbb{N}. Relacja \displaystyle R jest więc zwrotna.

2. Weźmy dowolne funkcje \displaystyle e,f,g\in \mathbb{N}^\mathbb{N}, takie że \displaystyle e R f oraz \displaystyle f R g. Oznacza to, że istnieją funkcje \displaystyle h_1,h_2 \in \mathbb{N}^\mathbb{N}, takie że:

\displaystyle h_1 \circ e = f \circ h_1

oraz:

\displaystyle h_2 \circ f = g \circ h_2.

Składając funkcję z pierwszej równości z funkcją \displaystyle h_2, otrzymujemy:

\displaystyle h_2 \circ h_1 \circ e = h_2 \circ f \circ h_1.

Z powyższej oraz z drugiej równości otrzymujemy:

\displaystyle (h_2 \circ h_1) \circ e = g \circ  (h_2 \circ h_1).

Wobec tego do \displaystyle e wystarczy dobrać funkcję \displaystyle h_3=h_2 \circ h_1, aby otrzymać \displaystyle h_3 \circ e = g  \circ h_3. Udowodniliśmy więc, że relacja \displaystyle R jest przechodnia.

3. Relacja \displaystyle R nie jest symetryczna. Rozważmy funkcję \displaystyle 1_\mathbb{N} oraz funkcję \displaystyle f stale równą 0. Wtedy dobierając \displaystyle h= f, mamy \displaystyle h \circ 1_\mathbb{N}= f \circ h, co oznacza \displaystyle 1_\mathbb{N} R f oraz \displaystyle h \circ f = 1_\mathbb{N} \circ h, co oznacza \displaystyle f R 1_\mathbb{N}. Ponieważ funkcje \displaystyle 1_\mathbb{N} i \displaystyle f są różne, to relacja \displaystyle R nie jest antysymetryczna.

Ćwiczenie 1.11

Niech \displaystyle I=[0,1] \subset \mathbb R. W zbiorze \displaystyle I^I zdefiniujemy relację \displaystyle R następująco:

\displaystyle \forall_{f,g \in I^I} [f R g \Leftrightarrow \exists_{x\in I} f(x) \leq g(x)].

Sprawdź, czy relacja \displaystyle R jest zwrotna, przechodnia i antysymetryczna.

Wskazówka

Jest zwrotna, nie jest przechodnia ani antysymetryczna.

Rozwiązanie

1. Dla dowolnej funkcji \displaystyle f\in I^I mamy \displaystyle f(0)\leq f(0), więc relacja \displaystyle R jest zwrotna.

2. Pokażemy, że relacja \displaystyle R nie jest przechodnia. Weźmy funkcję \displaystyle f_0, która jest stale równa 0, \displaystyle f_1, która jest stale równa 1 oraz funkcję \displaystyle 1_I, czyli identyczność. Wtedy \displaystyle f_1 R 1_I (bo \displaystyle f_1(1)=1 \leq 1_I(1)=1) oraz \displaystyle 1_I R f_0 (bo \displaystyle 1_I(0)=0 \leq f_0(0)=0, podczas gdy nie jest prawdą, że \displaystyle f_1 R f_0, bo dla każdego \displaystyle x\in I mamy \displaystyle f_1(x)=1 > 0=f_0(0).

3. Relacja nie jest antysymetryczna. Weźmy funkcję \displaystyle f_1 stale równą 1 oraz funkcję \displaystyle 1_I. Wtedy biorąc \displaystyle x=1, otrzymamy \displaystyle f_1(x)=1 =1_I(x), czyli \displaystyle f_1(x) \leq 1_I(x), skąd wynika, że \displaystyle f_1 R 1_I oraz \displaystyle 1_I(x) \leq f_1(x), skąd wynika, że \displaystyle 1_I R f_1. Ponieważ \displaystyle 1_I \neq f_1, to relacja \displaystyle R nie jest antysymetryczna.

Ćwiczenie 1.12

Niech \displaystyle I=[0,1] \subset \mathbb R. W zbiorze \displaystyle I^I zdefiniujemy relację \displaystyle R następująco:

\displaystyle \forall_{f,g \in I^I} [f R G \Leftrightarrow \forall_{x\in I} f(x) \leq g(x)].

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

Rozwiązanie

Pokażemy, że \displaystyle R porządkuje zbiór \displaystyle I.

  1. Dla każdej funkcji \displaystyle f\in I^I mamy \displaystyle \forall_{x\in I} f(x)=f(x), a więc w szczególności \displaystyle \forall_{x\in I} f(x)\leq f(x), co oznacza, że \displaystyle f R f. Relacja \displaystyle R jest więc zwrotna.
  2. Weźmy dowolne funkcje \displaystyle f,g,h \in I^I, takie że \displaystyle f R g oraz \displaystyle g R h. Pokażemy, że \displaystyle f R h. Weźmy dowolny element \displaystyle x\in I wtedy \displaystyle f(x) \leq g(x) oraz \displaystyle g(x) \leq h(x). Z przechodniości porządku \displaystyle \leq otrzymujemy \displaystyle f(x) \leq h(x). Wobec dowolności wyboru \displaystyle x otrzymujemy \displaystyle f R h.
  3. Weźmy funkcje \displaystyle f,g dla których \displaystyle f R g oraz \displaystyle g R f. Oznacza to, że:
\displaystyle [\forall_{x\in I} f(x) \leq g(x)] \wedge [\forall_{x\in I} g(x) \leq f(x)].

Jest to równoważne następującej formule:

\displaystyle \forall_{x\in I} [f(x) \leq g(x) \wedge g(x) \leq f(x)].

Z antysymetryczności porządku \displaystyle \leq otrzymujemy \displaystyle \forall_{x\in I} f(x) =g(x). Oznacza to dokładnie, że \displaystyle f=g. Wobec tego relacja \displaystyle R jest antysymetryczna.

Najmniejszym elementem jest funkcja \displaystyle f_0 stale równa zero, a największym elementem jest funkcja \displaystyle f_1 stale równa 1. Dla dowolnej funkcji \displaystyle f\in I^I i dowolnego elementu \displaystyle x\in X mamy \displaystyle f(x)\in I, a więc \displaystyle 0\leq f(x) \leq 1, skąd otrzymujemy \displaystyle f_0 R f oraz \displaystyle  f R f_1.

Ćwiczenie 1.13

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

Rozwiązanie

Wystarczy wziąć zbiór \displaystyle X=[0,1] \cap \mathbb{Q} uporządkowany naturalną relacją mniejszości na liczbach wymiernych. \displaystyle 0 \in \mathbb{Q} jest więc elementem najmniejszym, \displaystyle 1\in \mathbb{Q} jest więc elementem największym. Zbiór \displaystyle X jest nieskończonym podzbiorem zbioru przeliczalnego, więc jest przeliczalny.

Ć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

Rozważmy zbiór \displaystyle \{0,1\} uporządkowany relacją identycznościową. Wtedy każdy jego element jest maksymalny, a żaden nie jest największy, bo są nieporównywalne.

Istnieje też porządek, w którym istnieje dokładnie jeden element maksymalny, który nie jest elementem największym. Niech \displaystyle \flat będzie zbiorem takim, że \displaystyle \flat \notin \mathbb{N} (w roli \displaystyle \flat może wystąpić na przykład zbiór \displaystyle \mathbb R albo \displaystyle \mathbb{N}). Niech \displaystyle M=\mathbb{N} \cup \{\flat\}. Zbiór \displaystyle M uporządkujemy relacją \displaystyle R=\leq_\mathbb{N} \cup \{(\flat,\flat)\}, gdzie \displaystyle \leq_\mathbb{N} jest naturalną relacją porządku w \displaystyle \mathbb{N}. Łatwo sprawdzić, że \displaystyle R jest porządkiem. Wtedy \displaystyle \flat jest elementem maksymalnym (bo jedyny element, który jest z nim porównywalny to on sam, a więc nie może istnieć żaden większy). W dodatku \displaystyle \flat nie jest elementem największym, bo na przykład nie jest większy od 0. Nie ma drugiego elementu maksymalnego, gdyż musiałby być liczbą naturalną. Dla każdej liczby naturalnej natomiast istnieje liczba od niej większa.

Ćwiczenie 1.15

Podaj przykład zbioru liniowo uporządkowanego \displaystyle (X,\leq), w którym istnieje podzbiór niemający supremum.

Rozwiązanie

Takim zbiorem jest \displaystyle \mathbb{N} uporządkowany naturalną relacją \displaystyle \leq. Wtedy cały zbiór \displaystyle \mathbb{N} nie ma supremum, gdyż takie supremum musiałoby być największą liczbą naturalną, a taka nie istnieje.

Ćwiczenie 1.16

Udowodnij, że zbiorze uporządkowanym \displaystyle (X,\leq) istnieje \displaystyle \bigvee \emptyset wtedy i tylko wtedy, gdy w \displaystyle X istnieje element najmniejszy.

Rozwiązanie

Przypuśćmy, że w \displaystyle (X,\leq) istnieje \displaystyle \bigvee \emptyset, oznaczmy ten element przez \displaystyle a_0. Wtedy z definicji supremum otrzymujemy:

\displaystyle \forall_{a\in \emptyset} a \leq a_0

oraz dla każdego \displaystyle b\in X:

\displaystyle (\forall_{a\in \emptyset} a\leq b) \Rightarrow a_0 \leq b.

Pierwsza formuła niewiele mówi, gdyż jest zawsze prawdziwa (rozpisz kwantyfikator ograniczony). Z tego samego powodu zawsze jest prawdziwa przesłanka drugiej z formuł. Wobec tego dla każdego \displaystyle b\in X mamy \displaystyle a_0 \leq b, co oznacza dokładnie, że \displaystyle a_0 jest elementem najmniejszym w \displaystyle X.

Dla implikacji w drugą stronę, jeśli \displaystyle a_0 jest elementem najmniejszym, to prawa strona implikacji w drugiej formule jest zawsze prawdziwa, więc cała implikacja również. Pierwsza formuła jest zawsze spełniona. Wobec tego element \displaystyle a_0 spełnia warunki bycia \displaystyle \bigvee \emptyset, a więc takie supremum istnieje.

Ćwiczenie 1.17

Udowodnij, że zbiorze uporządkowanym \displaystyle (X,\leq), jeśli każdy podzbiór ma supremum, to każdy podzbiór ma infimum.

Rozwiązanie

Przypuśćmy, że \displaystyle (X,\leq) jest zbiorem uporządkowanym, w którym każdy podzbiór ma supremum. Weźmy dowolny zbiór \displaystyle A \subset X pokażemy, że ma infimum. Niech \displaystyle B=\{x \in X : \forall_{a\in A} x \leq a\}, czyli zbiór \displaystyle B jest zbiorem minorant zbioru \displaystyle A. Zbiór \displaystyle B jako podzbiór \displaystyle X ma supremum, oznaczmy je przez \displaystyle s. Pokażemy, że \displaystyle s jest infimum zbioru \displaystyle A. Ponieważ każdy element zbioru \displaystyle A jest majorantą zbioru \displaystyle B, to \displaystyle s musi być mniejszy od każdego elementu z \displaystyle A, gdyż jest najmniejszą majorantą \displaystyle B. Wobec tego, \displaystyle s jest minorantą \displaystyle A i ponieważ jest supremum minorant, to jest największą minorantą, a więc infimum zbioru \displaystyle A.

(Przyjrzyj się, jak powyższe rozumowanie działa w przypadkach, gdy \displaystyle A=X oraz gdy \displaystyle A=\emptyset.)

Ćwiczenie 1.18

Podaj przykład porządku \displaystyle (X,\leq) takiego, że podzbiór \displaystyle A\subset X ma supremum wtedy i tylko wtedy, gdy jest skończony.

Rozwiązanie

Przykładem takiego porządku są skończone podzbiory liczb naturalnych, uporządkowane przez inkluzję; oznaczymy ten porządek przez \displaystyle (\mathcal{P}_{fin}(\mathbb{N}),\subset). Dla dowolnego skończonego zbioru \displaystyle A\subset \mathcal{P}_{fin}(\mathbb{N}) mamy \displaystyle \bigcup A \in  \mathcal{P}_{fin}(\mathbb{N}), a więc zbiór ten ma supremum w \displaystyle \mathcal{P}_{fin}(\mathbb{N}). Jeśli zbiór \displaystyle A jest nieskończony, to \displaystyle \bigcup A jest nieskończony, a więc \displaystyle \bigcup A \notin \mathcal{P}_{fin}(\mathbb{N}), co oznacza, że w \displaystyle \mathcal{P}_{fin}(\mathbb{N}) nie istnieje supremum zbioru \displaystyle A (gdyby istniało, to w zbiorze \displaystyle (\mathcal{P}(\mathbb{N}),\subset) istniałyby dwa suprema zbioru \displaystyle A, co jest niemożliwe).

Definicja 1.19

\displaystyle L \subset X jest łańcuchem w porządku \displaystyle (X,\leq), gdy każde dwa elementy \displaystyle L są porównywalne w sensie \displaystyle \leq. Oznacza to, że porządek indukowany na zbiorze \displaystyle L, czyli \displaystyle (L, R \cap L \times L) jest porządkiem liniowym.

Definicja 1.20.

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

\displaystyle \forall_{a,b\in A} (a \leq b \Rightarrow a=b).

Ć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

Rozważmy zbiór \displaystyle \{0,1\} uporządkowany relacją \displaystyle \{(0,0),(0,1),(1,1)\}. Wtedy zbiory \displaystyle \{0\} oraz \displaystyle \{1\} są antyłańcuchami, podczas gdy ich suma nie jest.

Rozważmy zbiór \displaystyle \{0,1\} uporządkowany relacją \displaystyle \{(0,0),(1,1)\}. Wtedy zbiory \displaystyle \{0\} oraz \displaystyle \{1\} są łańcuchami, podczas gdy ich suma nie jest.

Ćwiczenie 1.22

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

Rozwiązanie

Każdy antyłańcuch jednoelementowy lub pusty jest łańcuchem.

Dla każdego porządku \displaystyle (X,\leq), 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

Rozważmy zbiór \displaystyle \mathcal{P}(2) uporządkowany relacją inkluzji. Wtedy zbiory \displaystyle \{\emptyset\} oraz \displaystyle \{\{1\}, \{0\}\} są różnymi antyłańcuchami maksymalnymi, a więc nie istnieje największy antyłańcuch. Podobnie zbiory \displaystyle \{\emptyset,\{0\},\{0,1\}\} oraz \displaystyle \{\emptyset,\{1\},\{0,1\}\} są różnymi maksymalnymi łańcuchami, więc łańcuch największy również nie istnieje.

Ćwiczenie 1.24

Kiedy w porządku \displaystyle (X,\leq) istnieje największy w sensie inkluzji łańcuch.

Rozwiązanie

W porządku \displaystyle (X,\leq) istnieje największy w sensie inkluzji łańcuch wtedy i tylko wtedy, gdy porządek ten jest liniowy.

Implikacja w lewą stronę jest oczywista, gdyż porządek liniowy jest w całości łańcuchem, a więc łańcuch ten jest największy.

Przypuśćmy teraz, że porządek \displaystyle (X,\leq) nie jest liniowy. Oznacza to, że istnieją przynajmniej dwa nieporównywalne elementy, oznaczmy je przez \displaystyle x,y. Ponieważ zbiory \displaystyle \{x\} oraz \displaystyle \{y\} są łańcuchami, to musiałyby być podzbiorami największego antyłańcucha, gdyby taki istniał. Oznaczałoby to jednak, że w tym łańcuchu znajdują się elementy nieporównywalne, wobec tego taki łańcuch nie istnieje.

Ćwiczenie 1.25

Kiedy w porządku \displaystyle (X,\leq) istnieje największy w sensie inkluzji antyłańcuch.

Rozwiązanie

W porządku \displaystyle (X,\leq) istnieje największy w sensie inkluzji łańcuch wtedy i tylko wtedy, gdy żadne dwa różne elementy \displaystyle X nie są porównywalne.

Implikacja w lewą stronę jest oczywista. Jeśli \displaystyle \leq = 1_X, to cały \displaystyle X jest antyłańcuchem. Ponieważ jest nadzbiorem każdego antyłańcucha, to jest największy.

Przypuśćmy teraz, że \displaystyle \leq \neq 1_X. Wtedy istnieją elementy porównywalne \displaystyle x,y. Przypuśćmy, że istnieje największy antyłańcuch. Wtedy antyłańcuchy \displaystyle \{x\} oraz \displaystyle \{y\} są jego podzbiorami, co oznacza, że w największym antyłańcuchu znajdują się elementy porównywalne. Wobec tego największy antyłańcuch nie istnieje.

Ć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

W zbiorze \displaystyle \mathbb{N} uporządkowanym relacją identyczności, każdy niepusty łańcuch jest singletonem, a więc jest skończony, podczas gdy cały zbiór jest nieskończony.

W zbiorze \displaystyle \mathbb{N} ^2 rozważmy porządek zdefiniowany następująco:

\displaystyle (x_1,y_1) \sqsubseteq (x_2,y_2) \Leftrightarrow (x_1+y_1=x_2+y_2 \wedge x_1 \leq x_2).

W tym porządku z każdy element \displaystyle (a,b) jest porównywalny dokładnie z \displaystyle a+b+1 elementami, wobec czego nie może istnieć nieskończony łańcuch. Z drugiej strony dla dowolnej liczby \displaystyle n\in \mathbb{N} możemy skonstruować łańcuch \displaystyle \{(a,b)\in \mathbb{N}^2: a+b=n\}, który ma dokładnie \displaystyle n+1 elementów.

Ćwiczenie 1.27

Rozważmy zbiór \displaystyle 7=\{0,1,2,3,4,5,6\} uporządkowany relacją podzielności (czyli \displaystyle a|b \Leftrightarrow \exists_{c\in 7} a \cdot c =b). Wypisz wszystkie łańcuchy maksymalne w sensie inkluzji. Wypisz wszystkie antyłańcuchy maksymalne w sensie inkluzji.

Rozwiązanie

Łańcuchy maksymalne:

  1. \displaystyle \{1,2,4,6,0\},
  2. \displaystyle \{1,3,6,0\},
  3. \displaystyle \{1,5,0\}.

Antyłańcuchy maksymalne:

  1. \displaystyle \{1\},
  2. \displaystyle \{0\},
  3. \displaystyle \{5,6\},
  4. \displaystyle \{2,3,5\},
  5. \displaystyle \{4,3,5\}.

Zbiory liniowo uporządkowane

Definicja 2.1.

Porządki liniowe \displaystyle (X,\leq ) i \displaystyle (Y,\leq ) nazywamy podobnymi, gdy istnieje bijekcja \displaystyle f:X \to Y rosnąca, czyli taka, że jeżeli \displaystyle x \leq y, to \displaystyle f(x) \leq f(y).

Ćwiczenie 2.2

Dla podobieństwa \displaystyle f, jeżeli \displaystyle f(x) \leq f(y), to \displaystyle x \leq y

Rozwiązanie

Dla dowodu nie wprost przypuśćmy, że \displaystyle f(x) \leq f(y) oraz \displaystyle x \nleq y. Ponieważ zbiór \displaystyle X jest uporządkowany liniowo, to w takiej sytuacji konieczne jest, aby \displaystyle y\leq x. Skoro \displaystyle f jest rosnąca, to \displaystyle f(y)\leq f(x). Wobec tego mamy \displaystyle f(y)=f(x) i skoro \displaystyle f jest injekcją to \displaystyle x=y, co jest sprzeczne z \displaystyle x \nleq y.

Definicja 2.3.

Porządek \displaystyle (X,\leq ) nazywamy gęstym, gdy \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

Niech \displaystyle (X,\leq ) i \displaystyle (Y,\leq ) będą podobnymi porządkami, a \displaystyle f:X \to Y będzie rosnącą bijekcją. Pokażemy, że jeśli \displaystyle (X,\leq ) jest gęsty, to również \displaystyle (Y,\leq) jest gęsty.

Weźmy dowolne elementy \displaystyle y_1,y_2\in Y takie, że \displaystyle y_1 < y_2. Skoro \displaystyle f jest bijekcją, to istnieją elementy \displaystyle x_1,x_2\in X, dla których \displaystyle f(x_1)=y_1 oraz \displaystyle f(x_2)=y2. Z poprzedniego ćwiczenia wynika, że \displaystyle x_1 < x_2. Ponieważ \displaystyle (X,\leq) jest gęsty, to istnieje element \displaystyle x_3\in X taki, że \displaystyle x_1 < x_3 <x_2, wtedy z monotoniczności i injektywności \displaystyle f otrzymujemy:

\displaystyle y_1 = f(x_1) < f(x_3) < f(x_2)= y_2.

Oznacza to, że istnieje element \displaystyle y_3\in Y, który leży pomiędzy \displaystyle y_1 a \displaystyle y_2. Udowodniliśmy więc, że porządek \displaystyle (Y\leq) jest gęsty.

Ćwiczenie 2.5

W zbiorze \displaystyle \mathbb{N}^\mathbb{N} rozważymy dwie relacje porządkujące zdefiniowane następująco:

\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

Tylko jeden z nich jest gęsty.

Rozwiązanie

Pokażemy, że porządek \displaystyle \sqsubseteq_1 nie jest gęsty, podczas gdy porządek \displaystyle \sqsubseteq_2 jest. Wobec faktu, że gęstość jest przenoszona przez podobieństwo, będzie to oznaczało, że nie są podobne.

Niech \displaystyle f_0 będzie funkcją stale równą 0, a \displaystyle f_1 niech będzie zdefiniowana następująco:

\displaystyle f_1(x)= \left\{\begin{array} {ll} 0, & x >0,  \\ 1, & x=0. \\\end{array} \right.

Z definicji funkcji wynika, że \displaystyle f_0 \sqsubseteq_1 f_1. Przypuśćmy teraz, że istnieje funkcja \displaystyle g taka, że \displaystyle f_0 \sqsubseteq_1 g \sqsubseteq_1 f_1. Wtedy, z definicji \displaystyle \sqsubseteq_1, dla każdego \displaystyle n\in \mathbb{N} \setminus\{0\} mamy:

\displaystyle 0=f_0(x) \leq g(x) \leq f_1(x)=0,

a więc \displaystyle g(x)=0 dla \displaystyle x\neq 0. Dla \displaystyle x=0 otrzymujemy:

\displaystyle 0 = f_0(0) \leq g(0) \leq f_1(0)=1.

Ponieważ \displaystyle g(0)\in \mathbb{N}, to są tylko dwie możliwości, \displaystyle g(0)=0 i wtedy \displaystyle g=f_0 lub \displaystyle g(0)=1 i wtedy \displaystyle g=f_1. Wynika stąd, że nie istnieje funkcja, która znajduje się pomiędzy \displaystyle f_0 a \displaystyle f_1 w sensie \displaystyle \sqsubseteq_1, więc ten porządek nie jest gęsty.

Pokażemy teraz, że \displaystyle \sqsubseteq_2 jest gęsty. Weźmy dowolne funkcje \displaystyle f_1,f_2\in \mathbb{N}^\mathbb{N} takie, że \displaystyle f_1\sqsubseteq_2 f_2. Z definicji \displaystyle \sqsubseteq_2 otrzymujemy, że istnieje \displaystyle n_0\in \mathbb{N} takie, że dla każdego \displaystyle n<n_0 mamy \displaystyle f_1(n)=f_2(n) oraz \displaystyle f(n_0) < g(n_0). Zdefiniujmy funkcję \displaystyle g następująco:

\displaystyle g(x)=\left\{\begin{array} {ll} f_1(x), & x \neq n_0+1,  \\ f_1(x)+1, & x=n_0+1. \\\end{array} \right.

Z definicji od razu wynika, że \displaystyle f_1 \sqsubseteq_2 g. Z drugiej strony mamy też \displaystyle g\sqsubseteq_2 f_2, bo dla \displaystyle n<n_0 mamy \displaystyle g(x)=f_1(x) = f_2(x) oraz \displaystyle g(x)=f_1(x) < f_2(x). Wskazaliśmy więc funkcję \displaystyle g, która znajduje się pomiędzy funkcjami \displaystyle f_1, f_2 w porządku \displaystyle \sqsubseteq. Funkcja ta różni się od \displaystyle f_1 na współrzędnej \displaystyle n_0+1 i od \displaystyle f_2 na współrzędnej \displaystyle n_0. Wobec dowolności wyboru \displaystyle f_1,f_2 porządek \displaystyle \sqsubseteq_2 jest gęsty.

Definicja 2.6.

Niech \displaystyle (X,\leq ) będzie porządkiem liniowym. Przekrojem Dedekinda w \displaystyle (X,\leq ) nazywamy parę zbiorów \displaystyle X_1 , X_2 \subset X, taką że:

  1. \displaystyle X_1 \cup X_2 = X.
  2. \displaystyle X_1 \cap X_2 = \emptyset.
  3. \displaystyle \forall_{x_1 \in X_1, x_2 \in X_2 } \;\; x_1 < x_2.
  4. \displaystyle X_1 \neq \emptyset i \displaystyle X_2 \neq \emptyset.

Definicja 2.7.

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

Ćwiczenie 2.8

Liniowy porządek \displaystyle (X,\leq ) jest gęsty wtedy i tylko wtedy, gdy żaden przekrój nie daje skoku.

Rozwiązanie

Przypuśćmy, że w porządku \displaystyle (X,\leq) istnieje przekrój \displaystyle X_1,X_2, który daje skok. Istnieją wtedy różne elementy \displaystyle x_1, x_2 takie, że \displaystyle x_1 = \bigvee X_1 oraz \displaystyle x_2 =\bigwedge X_2. Weźmy dowolny element \displaystyle z taki, że \displaystyle x_1 \leq z \leq x_2. Element \displaystyle z należy do \displaystyle X, więc musi należeć do któregoś ze zbiorów przekroju. Jeśli \displaystyle z\in X_1, to \displaystyle z\leq x_1 i wtedy \displaystyle z=x_1. Jeśli \displaystyle z\in X_2, to \displaystyle x_2 \leq z i wtedy \displaystyle z=x_2. Wynika stąd, że nie istnieje element leżący pomiędzy \displaystyle x_1 a \displaystyle x_2 w porządku \displaystyle \leq, a więc porządek ten nie jest gęsty.

Przypuśćmy, że żaden przekrój w porządku \displaystyle (X,\leq) nie daje skoku. Pokażemy, że ten porządek jest gęsty. Weźmy dowolne elementy \displaystyle x_1,x_2 \in X takie, że \displaystyle x_1 < x_2. Niech \displaystyle X_1= \{z\in X: z \leq x_1\} oraz \displaystyle X_2= X \setminus X_1. Z konstrukcji wynika, że zbiory \displaystyle X_1,X_2 są przekrojem zbioru \displaystyle X, \displaystyle x_2\in X_2 oraz w zbiorze \displaystyle X_1 istnieje element największy (jest nim \displaystyle x_1). Ponieważ przekrój ten nie może dawać skoku, to w zbiorze \displaystyle X_2 nie może istnieć element najmniejszy. Oznacza to, że w \displaystyle X_2 musi istnieć element \displaystyle z taki, że \displaystyle z < x_2 ( w przeciwnym przypadku \displaystyle x_2 byłby najmniejszy, gdyż \displaystyle X jest uporządkowany liniowo). Ponieważ \displaystyle z\in X_2, to również \displaystyle z\neq x_1. Wskazaliśmy więc element \displaystyle z\in X, dla którego \displaystyle x_1 < z <x_2. Wobec dowolności wyboru \displaystyle x_1,x_2 dowiedliśmy, że porządek \displaystyle (X,\leq) jest gęsty.

Ćwiczenie 2.9

W zbiorze \displaystyle \{0,1\}^\mathbb{N} rozważymy relację porządkującą zdefiniowaną następująco:

\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

Porządek ten nie jest gęsty. Zdefiniujmy funkcje \displaystyle f_1,f_2 następująco:

\displaystyle f_1(x)= \left\{\begin{array} {ll} 0, & x=0; \\ 1, & x\neq0, \\\end{array} \right.
\displaystyle f_2(x)= \left\{\begin{array} {ll} 1, & x=0; \\ 0, & x\neq0. \\\end{array} \right.

Wtedy \displaystyle f_1 \sqsubseteq f_2, gdyż dla \displaystyle n_0=0 mamy \displaystyle f_1(0)=0  < 1 =f_2(0). Przypuśćmy teraz, że funkcja \displaystyle g\in 2^\mathbb{N} jest taka, że \displaystyle f_1 \sqsubseteq g \sqsubseteq f_2. Rozważmy dwa przypadki. Jeśli \displaystyle g(0)=1, to \displaystyle g=f_2, gdyż wtedy nie może istnieć \displaystyle n>0, dla którego \displaystyle g(n)< f_2(n) (bo \displaystyle f_2(n)=0). Jeśli natomiast \displaystyle g(0)=1, to \displaystyle g=f_1, gdyż nie może istnieć \displaystyle n>0, dla którego \displaystyle f_1(n)< g(n) (bo \displaystyle f_1(n)=1). Wynika stąd, że nie istnieje element \displaystyle g\in 2^\mathbb{N} różny od \displaystyle f_1,f_2 taki, że \displaystyle f_1 \sqsubseteq g \sqsubseteq f_2, a więc porządek ten nie jest gęsty.

Definicja 2.10.

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

Definicja 2.11.

Porządek liniowy \displaystyle (X,\leq ) nazywamy ciągłym wtedy i tylko wtedy, gdy żaden przekrój nie daje luki.

Twierdzenie 2.12.

W porządku ciągłym \displaystyle (X,\leq ) każdy niepusty zbiór ograniczony od góry ma supremum.

Dowód

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

image:End_of_proof.gif

Twierdzenie 2.13.

W porządku liniowym \displaystyle (X,\leq ), 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 \displaystyle X_1 , X_2 \subset X. \displaystyle X_1 jest ograniczony od góry przez elementy z \displaystyle X_2. \displaystyle X_1, ma więc supremum \displaystyle a. Jeżeli \displaystyle a\in X_1, to \displaystyle X_1 ma element największy. W przeciwnym przypadku \displaystyle a \in X_2. Gdyby \displaystyle a > x_2 dla pewnego \displaystyle x_2 \in X_2, to zbiór \displaystyle X_1 miałby mniejsze ograniczenie górne niż \displaystyle a. To jest niemożliwe, musi więc być \displaystyle a \leq  x_2 dla każdego \displaystyle x_2 \in X_2. Zatem \displaystyle a jest najmniejszy w \displaystyle X_2.

image:End_of_proof.gif

Ćwiczenie 2.14

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

Wskazówka

Odwróć porządek w \displaystyle X i zastosuj Twierdzenia 2.12 i 2.13 (patrz Twierdzenie 2.12. i Twierdzenie 2.13.) )

Ćwiczenie 2.15.

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

Wskazówka

Niech \displaystyle f: X \rightarrow Y będzie podobieństwem. Weź przekrój Dedekinda \displaystyle ( Y_1 , Y_2 ) w \displaystyle Y. Pokaż, że przeciwobrazy \displaystyle \left( \overrightarrow{f}^{-1}  (Y_1) , \overrightarrow{f}^{-1}  (Y_2) \right) tworzą przekrój.

Rozwiązanie

Niech \displaystyle (X,\leq_X) oraz \displaystyle (Y,\leq_Y) będą podobnymi porządkami, takimi że \displaystyle (X,\leq_X) jest porządkiem ciągłym. Pokażemy, że \displaystyle (Y,\leq_Y) jest ciągły. Niech \displaystyle f:X\rightarrow Y będzie rosnącą bijekcją. Weźmy dowolny przekrój \displaystyle Y_1,Y_2 zbioru \displaystyle Y. Rozważmy zbiory \displaystyle \vec{f}^{-1}(Y_1), \vec{f}^{-1}(Y_2), oznaczmy je przez \displaystyle X_1,X_2. Pokażemy że tworzą one przekrój zbioru \displaystyle X. Z własności przeciwobrazu otrzymujemy natychmiast \displaystyle X_1\cup X_2= X oraz \displaystyle X_1 \cap X_2 = \emptyset. Z suriektywności funkcji \displaystyle f oraz z faktu, że zbiory \displaystyle Y_1,Y_2 są niepuste otrzymujemy, że zbiory \displaystyle X_1, X_2 też są niepuste. Weźmy teraz dowolny element \displaystyle x_1\in X_1 oraz \displaystyle x_2\in X_2. Pokażemy, że \displaystyle x_1 \leq_X x_2. Przypuśćmy, że tak nie jest. Wtedy \displaystyle x_1 >_X x_2 i ponieważ funkcja \displaystyle f jest injektywna i rosnąca, to otrzymamy \displaystyle f(x_1) >_Y f(x_2). Otrzymaliśmy sprzeczność, gdyż \displaystyle f(x_1) \in Y_1 i \displaystyle f(x_2) \in Y_2, a zbiory \displaystyle Y_1,Y_2 są przekrojem \displaystyle Y. Wobec tego konieczne jest, aby \displaystyle x_1 \leq x_2. Dowiedliśmy więc, że zbiory \displaystyle X_1,X_2 są przekrojem \displaystyle X.

Ponieważ \displaystyle X jest ciągły, to w \displaystyle X_1 jest element największy lub w \displaystyle X_2 element najmniejszy. Zajmiemy się najpierw pierwszym przypadkiem. Niech \displaystyle x_1 będzie elementem największym w \displaystyle X_1, pokażemy, że \displaystyle f(x_1) jest największy w \displaystyle Y_1. Weźmy dowolny element \displaystyle y\in Y_1, wtedy ponieważ \displaystyle f jest bijekcją to istnieje \displaystyle z\in X taki, że \displaystyle f(z)=y. Ponieważ \displaystyle y\in Y_1, to \displaystyle z\in X_1. Skoro \displaystyle x_1 jest największy w \displaystyle X_1, to w szczególności \displaystyle z \leq_X x_1 i z faktu, że funkcja \displaystyle f jest rosnąca otrzymujemy \displaystyle f(z)\leq_y f(x_1). Wobec tego \displaystyle f(x_1) jest największym elementem \displaystyle Y_1. Drugi przypadek jest analogiczny. Wynika stąd, że w \displaystyle Y_1 jest element największy albo w \displaystyle Y_2 jest element najmniejszy. Oznacza to, że przekrój \displaystyle Y_1,Y_2 nie daje luki. Wobec dowolności wyboru przekroju \displaystyle Y_1,Y_2 udowodniliśmy, że żaden przekrój nie daje luki, a więc że \displaystyle (Y,\leq_Y) jest ciągły.

Ćwiczenie 2.16

Pokaż, że zbiór \displaystyle \mathbb{N} liczb naturalnych jest ciągły.

Wskazówka

Użyj warunku z Twierdzenia 2.13 (patrz Twierdzenie 2.13.) lub zasady minimum (patrz zasada minimum).

Rozwiązanie

Weźmy dowolny przekrój liczb naturalnych \displaystyle N_1,N_2. Zbiór \displaystyle N_2 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.

Ćwiczenie 2.17

Udowodnij, że dla dowolnych liczb rzeczywistych \displaystyle A,B\in \mathbb R takich, że \displaystyle A<B istnieje liczba wymierna \displaystyle q\in \mathbb{Q} taka, że \displaystyle A\leq q \leq B.

Rozwiązanie

Weźmy dowolne liczby rzeczywiste \displaystyle A,B \in \mathbb R, dla których \displaystyle A<B. Niech \displaystyle a, b\in \mathbb{Q}^\mathbb{N} będą ciągami Cauchy'ego wyznaczającymi odpowiednio liczby \displaystyle A i \displaystyle B. Z definicji mniejszości \displaystyle A<B oznacza dokładnie, że:

\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.

Niech \displaystyle \varepsilon_0 oraz \displaystyle n_0 będą liczbami, o których istnieniu mówi powyższa formuła. Ponieważ \displaystyle a,b są ciągami Cauchy'ego, to dla \displaystyle \varepsilon_1= \frac{\varepsilon_0}{4} można dobrać \displaystyle m_0 takie, że dla dowolnych liczb \displaystyle k,l \geq m_0 będziemy mieli \displaystyle |a_k -a_l| < \varepsilon_1 oraz \displaystyle |b_k -b_l| < \varepsilon_1. Niech teraz \displaystyle N_0 będzie większą z liczb \displaystyle n_0 i \displaystyle m_0. Pokażemy, że liczba \displaystyle a_{N_0}+2 \varepsilon_1 jest szukaną liczbą \displaystyle q.

Zaczniemy od pokazania, że \displaystyle a_{N_0}+2 \varepsilon_1 < B. Wiemy, że:

\displaystyle  a_{N_0}+\varepsilon_0 < b_{N_0} \quad \mbox{(2.1)}

oraz dla każdego \displaystyle k \geq N_0 mamy:

\displaystyle |b_{N_0} - b_k|<\frac{\varepsilon_0}{4}.

Z powyższej nierówności otrzymujemy:

\displaystyle b_{N_0} - \frac{\varepsilon_0}{4}< b_k,

wobec czego z ostatniej równości i z 2.1 otrzymujemy:

\displaystyle a_{N_0}+\frac{3 \varepsilon_0}{4} < b_k,

skąd wynika, że \displaystyle a_{N_0}+2 \varepsilon_1<B.

Pokażemy teraz, że \displaystyle a_{N_0}+2 \varepsilon_1 > A. Wiemy, że dla każdego \displaystyle k\geq N_0 mamy:

\displaystyle |a_{N_0} - a_k|<\frac{\varepsilon_0}{4}.

Oznacza to, że:

\displaystyle a_k< a_{N_0} + \frac{\varepsilon_0}{4},

skąd otrzymujemy:

\displaystyle a_k +\frac{\varepsilon_0}{4} < a_{N_0} +\frac{\varepsilon_0} {2}.

Ponieważ powyższa równość jest prawdziwa dla każdego \displaystyle k \geq N_0, to otrzymujemy \displaystyle A<a_{N_0} +\frac{\varepsilon_0} {2} =a_{N_0} +2\varepsilon_1.

Ćwiczenie 2.18

Pokaż, że zbiór \displaystyle \mathbb{Q} nie jest ciągły.

Wskazówka

Do tego celu przeanalizuj przekrój Dedekinda \displaystyle (X_1 , X_2), gdzie \displaystyle X_1 = \left\{x\in \mathbb{Q}: x\leq\rho\right\} gdzie \displaystyle \rho jest ustaloną liczbą niewymierną oraz \displaystyle X_2 = \mathbb{Q} \setminus X_1.

Rozwiązanie

Niech \displaystyle \rho będzie ustaloną liczbą niewymierną. Istnienie takich liczb wynika z twierdzenia Cantora.

Zdefiniujmy zbiór \displaystyle X_1 następująco:

\displaystyle X_1 =\{x\in \mathbb{Q}: x \leq \rho\}

oraz zbiór \displaystyle X_2=\mathbb{Q} \setminus X_1. Z konstrukcji łatwo wynika, że zbiory \displaystyle X_1,X_2 tworzą przekrój zbioru \displaystyle (\mathbb{Q},\leq). Pokażemy, że taki przekrój daje lukę.

Przypuśćmy, że w zbiorze \displaystyle X_1 istnieje element największy, oznaczmy go przez \displaystyle x_0. Rozpatrzymy zbiór \displaystyle Y_1=\{x \in \mathbb R: x \leq \rho\}. W zbiorze \displaystyle Y_1 elementem największym jest \displaystyle \rho. Ponieważ \displaystyle X_1 \subset Y_1, to \displaystyle x_0 \leq \rho. Ponieważ \displaystyle \rho jest niewymierne, to równość jest wykluczona, czyli \displaystyle x_0 < \rho. Wtedy jednak z ćwiczenia 2.17 (patrz ćwiczenie 2.17.) otrzymujemy, że istnieje \displaystyle z\in \mathbb{Q} takie, że \displaystyle x_0 < z <\rho. Taki element \displaystyle z musi należeć do \displaystyle X_1, co przeczy temu, że \displaystyle x_0 jest największy w \displaystyle X_1. Wobec tego w zbiorze \displaystyle X_1 nie ma elementu największego.

Analogiczny dowód faktu, że w \displaystyle X_2 nie ma elementu najmniejszego pomijajmy (należy rozważyć zbiór \displaystyle Y_2= \{x \in \mathbb R: \rho \leq x\}).

Wobec tego skonstruowany przekrój \displaystyle X_1,X_2 daje lukę, a więc \displaystyle (\mathbb{Q},\leq) nie jest ciągły.

Twierdzenie 2.19.

\displaystyle \mathbb{R} 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 \displaystyle \mathbb{R} (patrz Wykład 9, Twierdzenie Cantora). Niech \displaystyle (X_1 , X_2) będzie przekrojem w \displaystyle \mathbb{R}. Zbiory \displaystyle X_1 , X_2 są niepuste. Wybierzmy dwie liczby wymierne \displaystyle x_0 w \displaystyle X_1 i \displaystyle y_0 w \displaystyle X_2. (Sprawdź jako ćwiczenie, że z każdego przekroju da się wybrać liczby wymierne). Skonstruujmy dwa ciągi \displaystyle x: \mathbb{N} \rightarrow X_1 oraz \displaystyle y: \mathbb{N} \rightarrow X_2 zdefiniowane indukcyjnie. \displaystyle x_0, y_0 są zadane.

\displaystyle x_{i+1} = \left\{ \begin{array} {ll} \frac{x_i + y_i}{2}, & \hbox{gdy } \frac{x_i + y_i}{2} \in X_1 ;\\ x_i , & \hbox{gdy; }  \frac{x_i + y_i}{2} \notin X_1. \end{array}  \right. \;\;\;\;\;\;\;y_{i+1} = \left\{ \begin{array} {ll} \frac{x_i + y_i}{2}, & \hbox{gdy } \frac{x_i + y_i}{2} \in X_2 ; \\ y_i , & \hbox{gdy }  \frac{x_i + y_i}{2} \notin X_2. \end{array}  \right.

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

  1. ciąg \displaystyle x jest słabo rosnący czyli \displaystyle x_i \leq x_{i+1},
  2. ciąg \displaystyle y jest słabo malejący czyli \displaystyle y_i \geq y_{i+1},
  3. \displaystyle y_i - x_i = \frac{y_0 - x_0}{2^i},
  4. \displaystyle  | x_{i+1} - x_i |  \leq \frac{y_0 - x_0}{2^{i+1}},
  5. \displaystyle  | y_{i+1} - y_i |  \leq \frac{y_0 - x_0}{2^{i+1}}.

Własności te implikują fakt, że zarówno \displaystyle x_i jak i \displaystyle  y_i są ciągami Cauchy'ego, jak i to, że są równoważne w sensie definicji liczb rzeczywistych. Zatem istnieje liczba rzeczywista \displaystyle G zadana jednocześnie przez aproksymacje \displaystyle x i \displaystyle y, czyli \displaystyle G= [x]_{\simeq} = [y]_\simeq. Gdy \displaystyle G\in X_1, to \displaystyle X_1 ma element największy. W przeciwnym wypadku \displaystyle G\in X_2 i wtedy \displaystyle X_2 ma element najmniejszy.

image:End_of_proof.gif

Ćwiczenie 2.20

Udowodnij, że porządki \displaystyle (\mathbb R, \leq) i \displaystyle (\mathbb R\setminus \mathbb{Q}, \leq) nie są podobne.

Rozwiązanie

Wiemy, że porządek \displaystyle (\mathbb R, \leq) jest ciągły. Analogiczne rozumowanie do rozwiązania Ćwiczenia 2.18 (patrz Ćwiczenie 2.18.) prowadzi do udowodnienia nieciągłości \displaystyle (\mathbb R\setminus \mathbb{Q}, \leq) (w roli \displaystyle \rho tym razem bierzemy liczbą wymierną). Ponieważ ciągłość jest przenoszona przez podobieństwo, to porządki te nie mogą być podobne.