Informatyka MIMUW

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.