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.