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

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

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

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

Definicja 1.2.

Element $\displaystyle a$ nazywamy maksymalnym w porządku $\displaystyle (X,\leq )$, gdy $\displaystyle \forall _{x\in X}\;\;a\leq x\Rightarrow a=x$.

Element $\displaystyle a$ nazywamy minimalnym w porządku $\displaystyle (X,\leq )$, gdy $\displaystyle \forall _{x\in X}\;\;x\leq a\Rightarrow a=x$.

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

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

Definicja 1.3.

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

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

Definicja 1.4.

$\displaystyle A\subset X$. Element $\displaystyle a_{0}\in X$ nazywamy supremum zbioru $\displaystyle A$, gdy:

1. $\displaystyle \forall _{a\in A}\;\;a\leq a_{0}$,
2. $\displaystyle (\forall _{a\in A}\;\;a\leq b)\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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle A} będziemy je oznaczać Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle \bigvee A} .

Definicja 1.5.

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle A \subset X} . Element Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle b_0 \in X} nazywamy infimum zbioru Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle A} , gdy:

1. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle \forall_{a\in A} \;\; b_0 \leq a}
2. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle (\forall_{a \in A} \;\; b \leq a ) \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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle A} , będziemy je oznaczać Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle \bigwedge A} .

Ćwiczenie 1.6

Niech Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle X} będzie ustalonym zbiorem i niech $\displaystyle A\subset {\mathcal {P}}(X)$. Zdefiniujmy relację $\displaystyle \sqsubseteq \subset A\times A$ następująco:

$\displaystyle a\sqsubseteq b\Leftrightarrow a\subseteq b.$

Udowodnij, że $\displaystyle (A,\sqsubseteq )$ jest zbiorem uporządkowanym.

Rozwiązanie

Pokażemy, że $\displaystyle \sqsubseteq$ spełnia warunki bycia porządkiem.

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

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

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

Uwaga 1.7.

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

Ćwiczenie 1.8

{{{3}}}

Rozwiązanie

Pokażemy, że dla dowolnej rodziny $\displaystyle r\subset {\mathcal {P}}(A)$ mamy $\displaystyle \bigcup r=\bigvee r$ oraz $\displaystyle \bigcap r=\bigwedge r$. Ze względu na symetrię udowodnimy tylko pierwszą równość (uwaga! sytuacja przestaje być symetryczna, jeśli dopuścimy puste rodziny). Pokażemy, że $\displaystyle \bigcup r$ spełnia warunki bycia supremum.

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

Ćwiczenie 1.9

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

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

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

Rozwiązanie

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

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

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

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

1. Jeśli $\displaystyle n\neq 0$ to $\displaystyle c_{1}\cdot c_{2}=1$ i ponieważ są to liczby naturalne, to $\displaystyle c_{1}=c_{2}=1$. Oznacza to, że $\displaystyle n=1\cdot m=m$.
2. Jeśli $\displaystyle n=0$, to wtedy $\displaystyle m=0\cdot c_{1}=0=n$.

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

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

Ćwiczenie 1.10

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

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

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

$\displaystyle h_{1}\circ e=f\circ h_{1}$

oraz:

$\displaystyle h_{2}\circ f=g\circ h_{2}.$

Składając funkcję z pierwszej równości z funkcją $\displaystyle h_{2}$, otrzymujemy:

$\displaystyle h_{2}\circ h_{1}\circ e=h_{2}\circ f\circ h_{1}.$

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

$\displaystyle (h_{2}\circ h_{1})\circ e=g\circ (h_{2}\circ h_{1}).$

Wobec tego do $\displaystyle e$ wystarczy dobrać funkcję $\displaystyle h_{3}=h_{2}\circ h_{1}$, aby otrzymać $\displaystyle h_{3}\circ e=g\circ h_{3}$. Udowodniliśmy więc, że relacja $\displaystyle R$ jest przechodnia.

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

Ćwiczenie 1.11

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

$\displaystyle \forall _{f,g\in I^{I}}[fRg\Leftrightarrow \exists _{x\in I}f(x)\leq g(x)].$

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

Wskazówka

Jest zwrotna, nie jest przechodnia ani antysymetryczna.

Rozwiązanie

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

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

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

Ćwiczenie 1.12

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

$\displaystyle \forall _{f,g\in I^{I}}[fRG\Leftrightarrow \forall _{x\in I}f(x)\leq g(x)].$

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

Rozwiązanie

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

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

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

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

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

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

Najmniejszym elementem jest funkcja $\displaystyle f_{0}$ stale równa zero, a największym elementem jest funkcja $\displaystyle f_{1}$ stale równa 1. Dla dowolnej funkcji $\displaystyle f\in I^{I}$ i dowolnego elementu $\displaystyle x\in X$ mamy $\displaystyle f(x)\in I$, a więc $\displaystyle 0\leq f(x)\leq 1$, skąd otrzymujemy $\displaystyle f_{0}Rf$ oraz $\displaystyle fRf_{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 $\displaystyle X=[0,1]\cap \mathbb {Q}$ uporządkowany naturalną relacją mniejszości na liczbach wymiernych. $\displaystyle 0\in \mathbb {Q}$ jest więc elementem najmniejszym, $\displaystyle 1\in \mathbb {Q}$ jest więc elementem największym. Zbiór $\displaystyle X$ jest nieskończonym podzbiorem zbioru przeliczalnego, więc jest przeliczalny.

Ć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 $\displaystyle \{0,1\}$ uporządkowany relacją identycznościową. Wtedy każdy jego element jest maksymalny, a żaden nie jest największy, bo są nieporównywalne.

Istnieje też porządek, w którym istnieje dokładnie jeden element maksymalny, który nie jest elementem największym. Niech $\displaystyle \flat$ będzie zbiorem takim, że $\displaystyle \flat \notin \mathbb {N}$ (w roli $\displaystyle \flat$ może wystąpić na przykład zbiór $\displaystyle \mathbb {R}$ albo $\displaystyle \mathbb {N}$). Niech $\displaystyle M=\mathbb {N} \cup \{\flat \}$. Zbiór $\displaystyle M$ uporządkujemy relacją $\displaystyle R=\leq _{\mathbb {N} }\cup \{(\flat ,\flat )\}$, gdzie $\displaystyle \leq _{\mathbb {N} }$ jest naturalną relacją porządku w $\displaystyle \mathbb {N}$. Łatwo sprawdzić, że $\displaystyle R$ jest porządkiem. Wtedy $\displaystyle \flat$ jest elementem maksymalnym (bo jedyny element, który jest z nim porównywalny to on sam, a więc nie może istnieć żaden większy). W dodatku $\displaystyle \flat$ nie jest elementem największym, bo na przykład nie jest większy od 0. Nie ma drugiego elementu maksymalnego, gdyż musiałby być liczbą naturalną. Dla każdej liczby naturalnej natomiast istnieje liczba od niej większa.

Ćwiczenie 1.15

Podaj przykład zbioru liniowo uporządkowanego $\displaystyle (X,\leq )$, w którym istnieje podzbiór niemający supremum.

Rozwiązanie

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

Rozwiązanie

Przypuśćmy, że w $\displaystyle (X,\leq )$ istnieje $\displaystyle \bigvee \emptyset$, oznaczmy ten element przez $\displaystyle a_{0}$. Wtedy z definicji supremum otrzymujemy:

$\displaystyle \forall _{a\in \emptyset }a\leq a_{0}$

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

$\displaystyle (\forall _{a\in \emptyset }a\leq b)\Rightarrow a_{0}\leq b.$

Pierwsza formuła niewiele mówi, gdyż jest zawsze prawdziwa (rozpisz kwantyfikator ograniczony). Z tego samego powodu zawsze jest prawdziwa przesłanka drugiej z formuł. Wobec tego dla każdego $\displaystyle b\in X$ mamy $\displaystyle a_{0}\leq b$, co oznacza dokładnie, że $\displaystyle a_{0}$ jest elementem najmniejszym w $\displaystyle X$.

Dla implikacji w drugą stronę, jeśli $\displaystyle a_{0}$ jest elementem najmniejszym, to prawa strona implikacji w drugiej formule jest zawsze prawdziwa, więc cała implikacja również. Pierwsza formuła jest zawsze spełniona. Wobec tego element $\displaystyle a_{0}$ spełnia warunki bycia $\displaystyle \bigvee \emptyset$, a więc takie supremum istnieje.

Ćwiczenie 1.17

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

Rozwiązanie

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

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

Ćwiczenie 1.18

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

Definicja 1.19

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

Definicja 1.20.

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

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

Rozważmy zbiór $\displaystyle \{0,1\}$ uporządkowany relacją $\displaystyle \{(0,0),(1,1)\}$. Wtedy zbiory $\displaystyle \{0\}$ oraz $\displaystyle \{1\}$ są łańcuchami, podczas gdy ich suma nie jest.

Ć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 $\displaystyle (X,\leq )$, zarówno zbiór jego łańcuchów jak i zbiór jego antyłańcuchów jest uporządkowany przez inkluzję. Możemy więc mówić o największym (maksymalnym) ze względu na inkluzję łańcuchu (antyłańcuchu). Łatwo można pokazać, że zawsze istnieje najmniejszy łańcuch i antyłańcuch. Istnienie w każdym posecie maksymalnego łańcucha jest równoważne aksjomatowi wyboru. Tym zagadnieniem zajmujemy się w Wykładzie 11.

Ć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 $\displaystyle {\mathcal {P}}(2)$ uporządkowany relacją inkluzji. Wtedy zbiory $\displaystyle \{\emptyset \}$ oraz $\displaystyle \{\{1\},\{0\}\}$ są różnymi antyłańcuchami maksymalnymi, a więc nie istnieje największy antyłańcuch. Podobnie zbiory $\displaystyle \{\emptyset ,\{0\},\{0,1\}\}$ oraz $\displaystyle \{\emptyset ,\{1\},\{0,1\}\}$ są różnymi maksymalnymi łańcuchami, więc łańcuch największy również nie istnieje.

Ćwiczenie 1.24

Kiedy w porządku $\displaystyle (X,\leq )$ istnieje największy w sensie inkluzji łańcuch.

Rozwiązanie

W porządku $\displaystyle (X,\leq )$ istnieje największy w sensie inkluzji łańcuch wtedy i tylko wtedy, gdy porządek ten jest liniowy.

Implikacja w lewą stronę jest oczywista, gdyż porządek liniowy jest w całości łańcuchem, a więc łańcuch ten jest największy.

Przypuśćmy teraz, że porządek $\displaystyle (X,\leq )$ nie jest liniowy. Oznacza to, że istnieją przynajmniej dwa nieporównywalne elementy, oznaczmy je przez $\displaystyle x,y$. Ponieważ zbiory $\displaystyle \{x\}$ oraz $\displaystyle \{y\}$ są łańcuchami, to musiałyby być podzbiorami największego antyłańcucha, gdyby taki istniał. Oznaczałoby to jednak, że w tym łańcuchu znajdują się elementy nieporównywalne, wobec tego taki łańcuch nie istnieje.

Ćwiczenie 1.25

Kiedy w porządku $\displaystyle (X,\leq )$ istnieje największy w sensie inkluzji antyłańcuch.

Rozwiązanie

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

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

Przypuśćmy teraz, że $\displaystyle \leq \neq 1_{X}$. Wtedy istnieją elementy porównywalne $\displaystyle x,y$. Przypuśćmy, że istnieje największy antyłańcuch. Wtedy antyłańcuchy $\displaystyle \{x\}$ oraz $\displaystyle \{y\}$ są jego podzbiorami, co oznacza, że w największym antyłańcuchu znajdują się elementy porównywalne. Wobec tego największy antyłańcuch nie istnieje.

Ć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 $\displaystyle \mathbb {N}$ uporządkowanym relacją identyczności, każdy niepusty łańcuch jest singletonem, a więc jest skończony, podczas gdy cały zbiór jest nieskończony.

W zbiorze $\displaystyle \mathbb {N} ^{2}$ rozważmy porządek zdefiniowany następująco:

$\displaystyle (x_{1},y_{1})\sqsubseteq (x_{2},y_{2})\Leftrightarrow (x_{1}+y_{1}=x_{2}+y_{2}\wedge x_{1}\leq x_{2}).$

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

Ćwiczenie 1.27

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

Antyłańcuchy maksymalne:

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

Zbiory liniowo uporządkowane

Definicja 2.1.

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

Ćwiczenie 2.2

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

Rozwiązanie

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

Definicja 2.3.

Porządek $\displaystyle (X,\leq )$ nazywamy gęstym, gdy $\displaystyle \forall _{x,y\in X}\;\;x<y\Rightarrow \exists _{z\in X}\;\;x<z<y$

Ćwiczenie 2.4

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

Rozwiązanie

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.

Ćwiczenie 2.5

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

$\displaystyle {\begin{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))].\end{aligned}}$

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

Wskazówka

Tylko jeden z nich jest gęsty.

Rozwiązanie

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.

Definicja 2.6.

Niech $\displaystyle (X,\leq )$ będzie porządkiem liniowym. Przekrojem Dedekinda w $\displaystyle (X,\leq )$ nazywamy parę zbiorów $\displaystyle X_{1},X_{2}\subset X$, taką że:

1. $\displaystyle X_{1}\cup X_{2}=X$.
2. $\displaystyle X_{1}\cap X_{2}=\emptyset$.
3. $\displaystyle \forall _{x_{1}\in X_{1},x_{2}\in X_{2}}\;\;x_{1}<x_{2}$.
4. $\displaystyle X_{1}\neq \emptyset$ i $\displaystyle X_{2}\neq \emptyset$.

Definicja 2.7.

Przekrój $\displaystyle X_{1},X_{2}$ daje skok, jeżeli $\displaystyle X_{1}$ ma element największy i $\displaystyle X_{2}$ ma element najmniejszy.

Ćwiczenie 2.8

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

Rozwiązanie

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.

Ćwiczenie 2.9

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

$\displaystyle {\begin{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))].\end{aligned}}$

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

Rozwiązanie

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\neq 0,\\\end{array}}\right.$ $\displaystyle f_{2}(x)=\left\{{\begin{array}{ll}1,&x=0;\\0,&x\neq 0.\\\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.

Definicja 2.10.

Przekrój $\displaystyle X_{1},X_{2}$ daje lukę, jeżeli $\displaystyle X_{1}$ nie ma elementu największego i $\displaystyle X_{2}$ nie ma elementu najmniejszego.

Definicja 2.11.

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

Twierdzenie 2.12.

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

Dowód

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

Twierdzenie 2.13.

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

Ćwiczenie 2.14

W porządku liniowym $\displaystyle (X,\leq )$ 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 $\displaystyle 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 $\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 \left({\overrightarrow {f}}^{-1}(Y_{1}),{\overrightarrow {f}}^{-1}(Y_{2})\right)$ tworzą przekrój.

Rozwiązanie

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.

Ćwiczenie 2.16

Pokaż, że zbiór $\displaystyle \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 $\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.

Ćwiczenie 2.17

Udowodnij, że dla dowolnych liczb rzeczywistych $\displaystyle A,B\in \mathbb {R}$ takich, że $\displaystyle A<B$ istnieje liczba wymierna $\displaystyle q\in \mathbb {Q}$ taka, że $\displaystyle A\leq q\leq B$.

Rozwiązanie

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

Ćwiczenie 2.18

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

Wskazówka

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

Rozwiązanie

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 (patrz ćwiczenie 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.

Twierdzenie 2.19.

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

$\displaystyle x_{i+1}=\left\{{\begin{array}{ll}{\frac {x_{i}+y_{i}}{2}},&{\hbox{gdy }}{\frac {x_{i}+y_{i}}{2}}\in X_{1};\\x_{i},&{\hbox{gdy; }}{\frac {x_{i}+y_{i}}{2}}\notin X_{1}.\end{array}}\right.\;\;\;\;\;\;\;y_{i+1}=\left\{{\begin{array}{ll}{\frac {x_{i}+y_{i}}{2}},&{\hbox{gdy }}{\frac {x_{i}+y_{i}}{2}}\in X_{2};\\y_{i},&{\hbox{gdy }}{\frac {x_{i}+y_{i}}{2}}\notin X_{2}.\end{array}}\right.$

Jako ćwiczenie podamy sprawdzenie następujących własności ciągów $\displaystyle x_{i}$ i $\displaystyle y_{i}$:

1. ciąg $\displaystyle x$ jest słabo rosnący czyli $\displaystyle x_{i}\leq x_{i+1}$,
2. ciąg $\displaystyle y$ jest słabo malejący czyli $\displaystyle y_{i}\geq y_{i+1}$,
3. $\displaystyle y_{i}-x_{i}={\frac {y_{0}-x_{0}}{2^{i}}}$,
4. $\displaystyle |x_{i+1}-x_{i}|\leq {\frac {y_{0}-x_{0}}{2^{i+1}}}$,
5. $\displaystyle |y_{i+1}-y_{i}|\leq {\frac {y_{0}-x_{0}}{2^{i+1}}}$.

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

Ćwiczenie 2.20

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

Rozwiązanie

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