Zbiory uporządkowane. Zbiory liniowo uporządkowane. Pojęcia gęstości i ciągłości

Zbiory uporządkowane

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 \hspace {0.1mm} \Rightarrow a=x \).

Element \( \displaystyle a \) nazywamy minimalnym w porządku \( \displaystyle (X,\leq ) \), gdy \( \displaystyle \forall_{x\in X} \;\; x \leq a \hspace {0.1mm} \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) \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 \( \displaystyle A \) będziemy je oznaczać \( \displaystyle \bigvee A \).

Definicja 1.5.

\( \displaystyle A \subset X \). Element \( \displaystyle b_0 \in X \) nazywamy infimum zbioru \( \displaystyle A \), gdy:

  1. \( \displaystyle \forall_{a\in A} \;\; b_0 \leq a \)
  2. \( \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 \( \displaystyle A \), będziemy je oznaczać \( \displaystyle \bigwedge A \).

Ćwiczenie 1.6

Niech \( \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.

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

Dla dowolnego zbioru \( \displaystyle A \), jego zbiór potęgowy \( \displaystyle \mathcal{P}(A) \) jest uporządkowany przez inkluzję. Czy dla dowolnej niepustej rodziny \( \displaystyle r \subset \mathcal{P}(A) \) istnieje supremum i infimum?


Ć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?

Ć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}} [ f R g \Leftrightarrow \exists_{h\in \mathbb{N}^\mathbb{N}} h \circ f = g \circ h]. \)

Sprawdź, czy relacja ta jest zwrotna, przechodnia i 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} [f R g \Leftrightarrow \exists_{x\in I} f(x) \leq g(x)]. \)

Sprawdź, czy relacja \( \displaystyle R \) jest zwrotna, przechodnia i 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} [f R G \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?

Ćwiczenie 1.13

Podaj przykład przeliczalnego porządku, w którym istnieje element najmniejszy i największy.

Ć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?

Ćwiczenie 1.15

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

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.

Ć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.

Ć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.

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.

Ćwiczenie 1.22

Czy antyłańcuch może być łańcuchem?

Ćwiczenie 1.23

Podaj przykład porządku, w których nie istnieje największy w sensie inkluzji łańcuch ani antyłańcuch.

Ćwiczenie 1.24

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

Ćwiczenie 1.25

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

Ć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?

Ć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.

Zbiory liniowo uporządkowane

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 \)

Definicja 2.3.

Porządek \( \displaystyle (X,\leq ) \) nazywamy gęstym, gdy \( \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.

Ćwiczenie 2.5

W zbiorze \( \displaystyle \mathbb{N}^\mathbb{N} \) rozważymy dwie relacje porządkujące zdefiniowane następująco:
\( \displaystyle \begin{align*} 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{align*} \)

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


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.

Ćwiczenie 2.9

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

\( \displaystyle \begin{align*} 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{align*} \)

Sprawdź, czy ten porządek 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 = \{y\in X: \exists_{x\in A} \;\; y \leq x\} \) oraz \( \displaystyle X_2 = \{y\in X: \forall_{x\in A} \;\; y >x\} \). 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.

Ćwiczenie 2.15.

Udowodnij, że ciągłość jest przenoszona przez podobieństwo.


Ćwiczenie 2.16

Pokaż, że zbiór \( \displaystyle \mathbb{N} \) liczb naturalnych 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 \).

Ćwiczenie 2.18

Pokaż, że zbiór \( \displaystyle \mathbb{Q} \) 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: "Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy kontinuum", 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.