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 go 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 go 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].$

Wskazówka

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

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}}$ więc jest elementem najmniejszym, $1\in \mathbb{\mathbb{Q}}$ więc jest 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 nie mają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 są uporządkowane 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łancuch. 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 iniekcją 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 iniektywnoś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.

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

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

Odwróć porządek w $X$ i zastosuj twierdzenia Uzupelnic thm:ciaglosc| i Uzupelnic thm:ciaglosc2|

Ćwiczenie 2.15.

Udowodnij, że ciągłość jest przenoszona przez podobieństwo. 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 iniektywna 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.

Użyj warunku z twierdzenia Uzupelnic thm:ciaglosc2| lub zasady 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}$

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 Uzupelnic eq:rown1| 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. 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 Uzupelnic ex:QgesteWR| 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{ℝ}$. 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 Cauchyego 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 zadania Uzupelnic Qnieciagly| 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.

Twierdzenie Bourbaki- Witt

Rozdział ten jest poświęcony twierdzeniu z którego będziemy korzystali w wykładzie 11 dotyczącym dyskusji nad aksjomatem wyboru.

Wprowadzamy podstawowe definicje

Definicja

Mówimy, że poset $(A,⊑)$ jest łańcuchowo zupełny jeśli każdy łańcuch posiada supremum.

Definicja

Dla posetu $(A,⊑)$ funkcję $f$ przeprowadzającą $A$ w $A$ i taka, że $x⊑f(x)$ dla dowolnego $x\in A$ nazywamy progresją.

Twierdzenie Bourbaki-Witt

Każda progresja na łańcuchowo zupełnym posecie posiada punkt stały.

Dowód:

W czasie tego dowodu zostaną pokazane dodatkowo dwa lematy Uzupelnic lem:l1| i Uzupelnic lem:l2|. Są one częścią całego dowodu. Ustalmy łańcuchowo zupełny poset $(A,⊑)$ i progresję $f$ operującą na nim. W dowodzie niezbędna jest koncepcja zbiorów, które nazwiemy "miłymi". Ustalmy dowolny element $a\in A$. Zbiór $B\subseteq A$ jest miły jeśli spełnia wszystkie poniższe warunki:

• $a\in B$,
• jeśli $x\in B$ to również $f(x)\in B$ i
• jeśli $C\subseteq B$ jest łańcuchem w $(A,⊑)$, to $\bigvee C\in B$.

Bardzo łatwo zauważyć, że przecięcie dowolnej rodziny miłych pozdbiorów jest miłe. Zdefiniujmy "najmilszy" podzbiór $B_0$ jako

$B_0=\bigcap \{B\subseteq A|\text{B jest miły}\},$

wtedy $B_0$ jest oczywiście miły. Równocześnie $B_0$ jest podzbiorem każdego miłego zbioru. Wykażmy parę własności elementów zbioru $B_0$. Po pierwsze żaden element istotnie mniejszy niż $a$ nie jest elementem $B_0$ -- jest to oczywistą konsekwencją faktu, że zbiór $\{x\in A|x\ge a\}$ jest miły, więc jest nadzbiorem $B_0$.

Zdefiniujmy jeszcze mniejszy zbiór

${B_0}^{\prime }=\{x\in B_0|\mathrm{\forall }y\in B_{0}y⊏x⟹f(y)⊑x\}\subseteq B_0$

i wykażmy parę faktów o elementach ${B_0}^{\prime }$.

Lemat

Jeśli $x\in {B_0}^{\prime }$ to, dla każdego $y\in B_0$ mamy $y⊑x\vee f(x)⊑y$.

Dowód

Ustalmy dowolny $x\in {B_0}^{\prime }$ i zdefiniujmy zbiór

$B_x=\{y\in B_0|y⊑x\vee f(x)⊑y\}.$

Wykażemy, że zbiór $B_x$ jest miły i, co za tym idzie, że $B_x=B_0$.

• $a\in B_x$, ponieważ wiemy, że $a⊑x$ dla dowolnego $x\in B_0$,
• Załóżmy teraz, że $y\in B_x$ i wykażmy $f(y)\in B_x$. Jeśli $y\in B_x$ na mocy $f(x)⊑y$, to niewątpliwie $f(x)⊑f(y)$ co kończy ten przypadek. Jeśli natomiast $y⊑x$, to albo $y=x$ i wtedy $f(x)⊑f(y)$, albo $y⊏x$ i wtedy, na mocy definicji ${B_0}^{\prime }$ mamy $f(y)⊑x$ co dowodzi, że również w tym przypadku $f(y)\in B_x$.
• Jeśli $C\subseteq B_x$ jest łańcuchem i dla wszystkich $y\in C$ zachodzi $y⊑x$, to również $\bigvee C⊑x$ i $\bigvee C\in B_x$. Jeśli dla pewnego $y\in C$ mamy $f(x)⊑y$ to również $f(x)⊑\bigvee C$ co należało dowieść.

W kolejnym lemacie dowodzimy, że zbiory ${B_0}^{\prime }$ i $B_0$ są równe

Lemat

Zbiór ${B_0}^{\prime }$ jest miły.

Dowód

Wykażemy, że zbiór ${B_0}^{\prime }$ jest miły a więc

• $a\in {B_0}^{\prime }$, ponieważ wykazaliśmy wcześniej, że $y⊏a$ nie zachodzi dla

żadnego $y\in B_0$.

• Ustalmy $x\in {B_0}^{\prime }$, żeby wykazać $f(x)\in {B_0}^{\prime }$ ustalmy

$y\in B_0$ takie, że $y⊏f(x)$. Na mocy Lematu Uzupelnic lem:l1| dostajemy $y⊑x\vee f(x)⊑y$. Druga część alternatywy stoi w sprzeczności z założeniem, więc $y⊑x$ i albo $y=x$, więc $f(y)⊑f(x)$, albo $y⊏x$ i na mocy założenia $f(y)⊑x⊑f(x)$ co należało pokazać.

• Ustalmy dowolny $C\subseteq {B_0}^{\prime }$

łańcuch w $(A,⊑)$. Załóżmy, że $y⊏\bigvee C$. Jeśli dla jakiegoś $x\in C$ mamy $y⊏x$ wtedy $f(y)⊑x⊑\bigvee C$, co należało pokazać. Przeciwny przypadek jest niemożliwy na podstawie Lematu Uzupelnic lem:l1|. Mielibyśmy wtedy dla każdego $x\in C$ prawdziwe $x=y$ lub $x⊑f(x)⊑y$ co jest sprzeczne z założeniem mówiącym, że $y⊏\bigvee C$.

Tak więc ${B_0}^{\prime }=B_0$, czyli dla dowolnych $x$ i $y$ w $B_0$ mamy, na podstawie Lematu Uzupelnic lem:l1|, $y⊑x$ lub $x⊑f(x)⊑y$. Wnioskujemy, że $B_0$ jest uporządkowany liniowo, czyli jest łańcuchem. Niewątplwie $\bigvee B_0\in B_0$ (na podstawie definicji zbiorów miłych) i $f(\bigvee B_0)\in B_0$ (na podstawie tej samej definicji), więc $f(\bigvee B_0)=\bigvee B_0$ co dowodzi istnienia punktu stałego odwzorowania $f$.

[Koniec dowodu twierdzenia Bourbaki-Witt]