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.

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

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

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

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

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

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.

Jest zwrotna, nie jest przechodnia ani antysymetryczna.

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.

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

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.

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.

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.

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

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.

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: "Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady".

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.

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.

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.

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.

Ł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\} \).

Dla dowodu nie wprost przypuśćmy, że \( \displaystyle f(x) \leq f(y) \) oraz \( \displaystyle x ≰ 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 ≰ y \).

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.

Tylko jeden z nich jest gęsty.

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.

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.

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.

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

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 ( \overrightarrow{f}^{-1} (Y_1) , \overrightarrow{f}^{-1} (Y_2) ) \) tworzą przekrój.

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.

Użyj warunku z Twierdzenia 2.13 lub zasady minimum (patrz Wykład 7: "Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje").

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.

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

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

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

Wiemy, że porządek \( \displaystyle (\mathbb R, \leq) \) jest ciągły. Analogiczne rozumowanie do rozwiązania Ćwiczenia 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.