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

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

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

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

Często oznaczamy relacje porządkującą jako $\le$. Oznaczamy też $x<y$, gdy $x\le y$ oraz $x\ne y$.

Definicja 1.2.

Element $a$ nazywamy maksymalnym w porządku $(X,\le )$, gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \forall_{x\in X} \;\; a\leq x \hspace*{0.1mm} \Rightarrow a=x} .

Element $a$ nazywamy minimalnym w porządku $(X,\le )$, gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \forall_{x\in X} \;\; x \leq a \hspace*{0.1mm} \Rightarrow a=x} .

Element $a$ nazywamy największym w porządku $(X,\le )$, gdy ${\mathrm{\forall }}_{x\in X}x\le a$.

Element $a$ nazywamy najmniejszym w porządku $(X,\le )$, gdy ${\mathrm{\forall }}_{x\in X}a\le x$.

Definicja 1.3.

Niech $A\subset X$ oraz $b\in X$. Mówimy, że $b$ jest majorantą zbioru $A$, gdy ${\mathrm{\forall }}_{a\in A}a\le b$.

Niech $A\subset X$ oraz $b\in X$. Mówimy, że $b$ jest minorantą zbioru $A$, gdy ${\mathrm{\forall }}_{a\in A}b\le a$.

Definicja 1.4.

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

1. ${\mathrm{\forall }}_{a\in A}a\le a_0$,
2. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (\forall_{a\in A} \;\; a \leq b) \hspace*{0.1mm} \Rightarrow a_0 \leq b} .

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

Definicja 1.5.

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

1. ${\mathrm{\forall }}_{a\in A}{b}_0\le a$
2. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (\forall_{a \in A} \;\; b \leq a )\hspace*{0.1mm} \Rightarrow b \leq b_0}

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

Ćwiczenie 1.6

Niech $X$ będzie ustalonym zbiorem i niech $A\subset {𝒫}(X)$. Zdefiniujmy relację $⊑\subset A\times A$ następująco:

$a⊑b\iff a\subseteq b.$

Udowodnij, że $(A,⊑)$ jest zbiorem uporządkowanym.

Rozwiązanie

Pokażemy, że $⊑$ spełnia warunki bycia porządkiem.

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

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

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

Uwaga 1.7.

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

Ćwiczenie 1.8

{{{3}}}

Rozwiązanie

Pokażemy, że dla dowolnej rodziny $r\subset {𝒫}(A)$ mamy $\bigcup r=\bigvee r$ oraz $\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 $\bigcup r$ spełnia warunki bycia supremum.

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

Ćwiczenie 1.9

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

${\mathrm{\forall }}_{a,b\in \mathbb{\mathbb{N}}}[a|b\iff {\mathrm{\exists }}_{c\in \mathbb{\mathbb{N}}}c\cdot a=b].$

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

Rozwiązanie

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

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

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

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

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

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

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

Ćwiczenie 1.10

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

${\mathrm{\forall }}_{f,g\in {\mathbb{\mathbb{N}}}^{\mathbb{\mathbb{N}}}}[fRg\iff {\mathrm{\exists }}_{h\in {\mathbb{\mathbb{N}}}^{\mathbb{\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 $f\in {\mathbb{\mathbb{N}}}^{\mathbb{\mathbb{N}}}$ możemy dobrać funkcję $1_{\mathbb{\mathbb{N}}}$ i wtedy $1_{\mathbb{\mathbb{N}}}\circ f=f\circ 1_{\mathbb{\mathbb{N}}}$. Relacja $R$ jest więc zwrotna.

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

$h_1\circ e=f\circ h_1$

oraz:

$h_2\circ f=g\circ h_2.$

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

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

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

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

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

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

Ćwiczenie 1.11

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

${\mathrm{\forall }}_{f,g\in I^I}[fRg\iff {\mathrm{\exists }}_{x\in I}f(x)\le g(x)].$

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

Wskazówka

Jest zwrotna, nie jest przechodnia ani antysymetryczna.

Rozwiązanie

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

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

3. Relacja nie jest antysymetryczna. Weźmy funkcję $f_1$ stale równą 1 oraz funkcję $1_I$. Wtedy biorąc $x=1$, otrzymamy $f_1(x)=1=1_I(x)$, czyli $f_1(x)\le 1_I(x)$, skąd wynika, że $f_{1}R{1}_I$ oraz $1_I(x)\le f_1(x)$, skąd wynika, że $1_{I}R{f}_1$. Ponieważ $1_I\ne f_1$, to relacja $R$ nie jest antysymetryczna.

Ćwiczenie 1.12

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

${\mathrm{\forall }}_{f,g\in I^I}[fRG\iff {\mathrm{\forall }}_{x\in I}f(x)\le g(x)].$

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

Rozwiązanie

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

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

$[{\mathrm{\forall }}_{x\in I}f(x)\le g(x)]\wedge [{\mathrm{\forall }}_{x\in I}g(x)\le f(x)].$

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

${\mathrm{\forall }}_{x\in I}[f(x)\le g(x)\wedge g(x)\le f(x)].$

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

Najmniejszym elementem jest funkcja $f_0$ stale równa zero, a największym elementem jest funkcja $f_1$ stale równa 1. Dla dowolnej funkcji $f\in I^I$ i dowolnego elementu $x\in X$ mamy $f(x)\in I$, a więc $0\le f(x)\le 1$, skąd otrzymujemy $f_{0}Rf$ oraz $fR{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 $X=[0,1]\cap \mathbb{\mathbb{Q}}$ uporządkowany naturalną relacją mniejszości na liczbach wymiernych. $0\in \mathbb{\mathbb{Q}}$ jest więc elementem najmniejszym, $1\in \mathbb{\mathbb{Q}}$ jest więc elementem największym. Zbiór $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 $\{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 $\mathrm{♭}$ będzie zbiorem takim, że $\mathrm{♭}\notin \mathbb{\mathbb{N}}$ (w roli $\mathrm{♭}$ może wystąpić na przykład zbiór $\mathbb{ℝ}$ albo $\mathbb{\mathbb{N}}$). Niech $M=\mathbb{\mathbb{N}}\cup \{\mathrm{♭}\}$. Zbiór $M$ uporządkujemy relacją $R={\le }_{\mathbb{\mathbb{N}}}\cup \{(\mathrm{♭},\mathrm{♭})\}$, gdzie ${\le }_{\mathbb{\mathbb{N}}}$ jest naturalną relacją porządku w $\mathbb{\mathbb{N}}$. Łatwo sprawdzić, że $R$ jest porządkiem. Wtedy $\mathrm{♭}$ 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 $\mathrm{♭}$ 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 $(X,\le )$, w którym istnieje podzbiór niemający supremum.

Rozwiązanie

Takim zbiorem jest $\mathbb{\mathbb{N}}$ uporządkowany naturalną relacją $\le$. Wtedy cały zbiór $\mathbb{\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 $(X,\le )$ istnieje $\bigvee \mathrm{\varnothing }$ wtedy i tylko wtedy, gdy w $X$ istnieje element najmniejszy.

Rozwiązanie

Przypuśćmy, że w $(X,\le )$ istnieje $\bigvee \mathrm{\varnothing }$, oznaczmy ten element przez $a_0$. Wtedy z definicji supremum otrzymujemy:

${\mathrm{\forall }}_{a\in \mathrm{\varnothing }}a\le a_0$

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

$({\mathrm{\forall }}_{a\in \mathrm{\varnothing }}a\le b)\Rightarrow a_0\le 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 $b\in X$ mamy $a_0\le b$, co oznacza dokładnie, że $a_0$ jest elementem najmniejszym w $X$.

Dla implikacji w drugą stronę, jeśli $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 $a_0$ spełnia warunki bycia $\bigvee \mathrm{\varnothing }$, a więc takie supremum istnieje.

Ćwiczenie 1.17

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

Rozwiązanie

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

(Przyjrzyj się, jak powyższe rozumowanie działa w przypadkach, gdy $A=X$ oraz gdy $A=\mathrm{\varnothing }$.)

Ćwiczenie 1.18

Podaj przykład porządku $(X,\le )$ takiego, że podzbiór $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 $({{𝒫}}_{fin}(\mathbb{\mathbb{N}}),\subset )$. Dla dowolnego skończonego zbioru $A\subset {{𝒫}}_{fin}(\mathbb{\mathbb{N}})$ mamy $\bigcup A\in {{𝒫}}_{fin}(\mathbb{\mathbb{N}})$, a więc zbiór ten ma supremum w ${{𝒫}}_{fin}(\mathbb{\mathbb{N}})$. Jeśli zbiór $A$ jest nieskończony, to $\bigcup A$ jest nieskończony, a więc $\bigcup A\notin {{𝒫}}_{fin}(\mathbb{\mathbb{N}})$, co oznacza, że w ${{𝒫}}_{fin}(\mathbb{\mathbb{N}})$ nie istnieje supremum zbioru $A$ (gdyby istniało, to w zbiorze $({𝒫}(\mathbb{\mathbb{N}}),\subset )$ istniałyby dwa suprema zbioru $A$, co jest niemożliwe).

Definicja 1.19

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

Definicja 1.20.

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

${\mathrm{\forall }}_{a,b\in A}(a\le 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 $\{0,1\}$ uporządkowany relacją $\{(0,0),(0,1),(1,1)\}$. Wtedy zbiory $\{0\}$ oraz $\{1\}$ są antyłańcuchami, podczas gdy ich suma nie jest.

Rozważmy zbiór $\{0,1\}$ uporządkowany relacją $\{(0,0),(1,1)\}$. Wtedy zbiory $\{0\}$ oraz $\{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 $(X,\le )$, 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 ${𝒫}(2)$ uporządkowany relacją inkluzji. Wtedy zbiory $\{\mathrm{\varnothing }\}$ oraz $\{\{1\},\{0\}\}$ są różnymi antyłańcuchami maksymalnymi, a więc nie istnieje największy antyłańcuch. Podobnie zbiory $\{\mathrm{\varnothing },\{0\},\{0,1\}\}$ oraz $\{\mathrm{\varnothing },\{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 $(X,\le )$ istnieje największy w sensie inkluzji łańcuch.

Rozwiązanie

W porządku $(X,\le )$ 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 $(X,\le )$ nie jest liniowy. Oznacza to, że istnieją przynajmniej dwa nieporównywalne elementy, oznaczmy je przez $x,y$. Ponieważ zbiory $\{x\}$ oraz $\{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 $(X,\le )$ istnieje największy w sensie inkluzji antyłańcuch.

Rozwiązanie

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

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

Przypuśćmy teraz, że $\le \ne 1_X$. Wtedy istnieją elementy porównywalne $x,y$. Przypuśćmy, że istnieje największy antyłańcuch. Wtedy antyłańcuchy $\{x\}$ oraz $\{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 $\mathbb{\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 ${\mathbb{\mathbb{N}}}^2$ rozważmy porządek zdefiniowany następująco:

$(x_1,y_1)⊑(x_2,y_2)\iff (x_1+y_1=x_2+y_2\wedge x_1\le x_2).$

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

Ćwiczenie 1.27

Rozważmy zbiór $7=\{0,1,2,3,4,5,6\}$ uporządkowany relacją podzielności (czyli $a|b\iff {\mathrm{\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. $\{1,2,4,6,0\}$,
2. $\{1,3,6,0\}$,
3. $\{1,5,0\}$.

Antyłańcuchy maksymalne:

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

Zbiory liniowo uporządkowane

Definicja 2.1.

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

Ćwiczenie 2.2

Dla podobieństwa $f$, jeżeli $f(x)\le f(y)$, to $x\le y$

Rozwiązanie

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

Definicja 2.3.

Porządek $(X,\le )$ nazywamy gęstym, gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \forall_{x,y\in X} \;\; x<y \hspace*{0.1mm} \Rightarrow \exists_{z\in X} \;\; x<z<y}

Ćwiczenie 2.4

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

Rozwiązanie

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

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

$y_1=f(x_1)<f(x_3)<f(x_2)=y_2.$

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

Ćwiczenie 2.5

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

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

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

Wskazówka

Tylko jeden z nich jest gęsty.

Rozwiązanie

Pokażemy, że porządek ${⊑}_1$ nie jest gęsty, podczas gdy porządek ${⊑}_2$ jest. Wobec faktu, że gęstość jest przenoszona przez podobieństwo, będzie to oznaczało, że nie są podobne.

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

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

Z definicji funkcji wynika, że $f_0{⊑}_1{f}_1$. Przypuśćmy teraz, że istnieje funkcja $g$ taka, że $f_0{⊑}_{1}g{⊑}_1{f}_1$. Wtedy, z definicji ${⊑}_1$, dla każdego $n\in \mathbb{\mathbb{N}}\setminus \{0\}$ mamy:

$0=f_0(x)\le g(x)\le f_1(x)=0,$

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

$0=f_0(0)\le g(0)\le f_1(0)=1.$

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

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

$g(x)=\{\begin{array}{ll}{f}_1(x),& x\ne n_0+1,\\ f_1(x)+1,& x=n_0+1.\\ \end{array}$

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

Definicja 2.6.

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

1. $X_1\cup X_2=X$.
2. $X_1\cap X_2=\mathrm{\varnothing }$.
3. ${\mathrm{\forall }}_{x_1\in X_1,x_2\in X_2}{x}_1<x_2$.
4. $X_1\ne \mathrm{\varnothing }$ i $X_2\ne \mathrm{\varnothing }$.

Definicja 2.7.

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

Ćwiczenie 2.8

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

Rozwiązanie

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

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

Ćwiczenie 2.9

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

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

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

Rozwiązanie

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

$f_1(x)=\{\begin{array}{ll}0,& x=0;\\ 1,& x\ne 0,\\ \end{array}$ $f_2(x)=\{\begin{array}{ll}1,& x=0;\\ 0,& x\ne 0.\\ \end{array}$

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

Definicja 2.10.

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

Definicja 2.11.

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

Twierdzenie 2.12.

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

Dowód

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

Twierdzenie 2.13.

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

Ćwiczenie 2.14

W porządku liniowym $(X,\le )$ 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 $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 $f:X\to Y$ będzie podobieństwem. Weź przekrój Dedekinda $(Y_1,Y_2)$ w $Y$. Pokaż, że przeciwobrazy $(\stackrel{-1}{\overrightarrow{f}}(Y_1),\stackrel{-1}{\overrightarrow{f}}(Y_2))$ tworzą przekrój.

Rozwiązanie

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

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

Ćwiczenie 2.16

Pokaż, że zbiór $\mathbb{\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 $N_1,N_2$. Zbiór $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 $A,B\in \mathbb{ℝ}$ takich, że $A<B$ istnieje liczba wymierna $q\in \mathbb{\mathbb{Q}}$ taka, że $A\le q\le B$.

Rozwiązanie

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

${\mathrm{\exists }}_{\epsilon :\epsilon \in \mathbb{\mathbb{Q}}\wedge \epsilon >0}{\mathrm{\exists }}_{n_0\in \mathbb{\mathbb{N}}}{\mathrm{\forall }}_{k:k\in \mathbb{\mathbb{N}}\wedge k\ge n_0}{a}_k+\epsilon <b_k.$

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

Zaczniemy od pokazania, że $a_{N_0}+2{\epsilon }_1<B$. Wiemy, że:

$a_{N_0}+{\epsilon }_0<b_{N_0}\text{(2.1)}$

oraz dla każdego $k\ge N_0$ mamy:

$|b_{N_0}-b_k|<\frac{{\epsilon }_0}{4}.$

Z powyższej nierówności otrzymujemy:

$b_{N_0}-\frac{{\epsilon }_0}{4}<b_k,$

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

$a_{N_0}+\frac{3{\epsilon }_0}{4}<b_k,$

skąd wynika, że $a_{N_0}+2{\epsilon }_1<B$.

Pokażemy teraz, że $a_{N_0}+2{\epsilon }_1>A$. Wiemy, że dla każdego $k\ge N_0$ mamy:

$|a_{N_0}-a_k|<\frac{{\epsilon }_0}{4}.$

Oznacza to, że:

$a_k<a_{N_0}+\frac{{\epsilon }_0}{4},$

skąd otrzymujemy:

$a_k+\frac{{\epsilon }_0}{4}<a_{N_0}+\frac{{\epsilon }_0}{2}.$

Ponieważ powyższa równość jest prawdziwa dla każdego $k\ge N_0$, to otrzymujemy $A<a_{N_0}+\frac{{\epsilon }_0}{2}=a_{N_0}+2{\epsilon }_1$.

Ćwiczenie 2.18

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

Wskazówka

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

Rozwiązanie

Niech $\rho$ będzie ustaloną liczbą niewymierną. Istnienie takich liczb wynika z twierdzenia Cantora. Zdefiniujmy zbiór $X_1$ następująco:

$X_1=\{x\in \mathbb{\mathbb{Q}}:x\le \rho \}$

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

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

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

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

Twierdzenie 2.19.

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

$x_{i+1}=\{\begin{array}{ll}\frac{x_i+y_i}{2},& \text{gdy }\frac{x_i+y_i}{2}\in X_1;\\ x_i,& \text{gdy; }\frac{x_i+y_i}{2}\notin X_1.\end{array}{y}_{i+1}=\{\begin{array}{ll}\frac{x_i+y_i}{2},& \text{gdy }\frac{x_i+y_i}{2}\in X_2;\\ y_i,& \text{gdy }\frac{x_i+y_i}{2}\notin X_2.\end{array}$

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

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

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

Ćwiczenie 2.20

Udowodnij, że porządki $(\mathbb{ℝ},\le )$ i $(\mathbb{ℝ}\setminus \mathbb{\mathbb{Q}},\le )$ nie są podobne.

Rozwiązanie

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