Zdefiniujemy teraz kolejny rodzaj relacji – relacje porządku. Warto powtórzyć własności relacji z Definicji 62, 72, 70. Podamy definicje i własności elementów wyróżnionych (np. elementu maksymalnego, największego). Omówimy pewne rodzaje porządków, w tym dobry porządek i podamy twierdzenie Zermelo o dobrym uporządkowaniu (na razie bez dowodu).
Definicja 128. Niech \(X\) będzie niepustym zbiorem a \(R\subset X\times X\) relacją na tym zbiorze. Relację tę nazywamy relacją porządku (częściowego) jeśli relacja \(R\) jest zwrotna, przechodnia i słabo antysymetryczna. Zbiór \(X\) z relacją (częściowego) porządku \(R\) zapisujemy \((X,R)\) i mówimy, że \(X\) jest zbiorem częściowo uporządkowanym.
Relację porządku często oznaczmy symbolem \(\leq \) albo \(\preccurlyeq \), a zapis \(x\leq y\) czytamy standardowo \(x\) jest mniejsze lub równe od \(y\) lub też \(y\) jest większe lub równe od \(x\).
Mówiąc \(x\) jest mniejsze od \(y\) mamy na myśli, że \(x\) jest mniejsze lub równe od \(y\) i \(x\) jest różne od \(y\).
Słowo częściowy pojawia się w powyższej definicji jako podkreślenie faktu, że w danym porządku mogą się zdarzyć elementy, których nie możemy porównać – jak w poniższym przykładzie w punkcie 3.
1. Zbiorem uporządkowanym jest \((\mathbb {N}, \leq )\), gdzie \(\leq \) oznacza standardową nierówność pomiędzy liczbami naturalnymi.
2. Podobnie, zbiorem uporządkowanym jest \((\mathbb {R}, \leq ) \), ale nie \((\mathbb {R},<)\) – relacja \(<\) nie jest zwrotna.
3. Niech \(X=\mathbb {N}^*\). Relację porządku oznaczoną jako \(\preccurlyeq \) zdefiniujmy następująco: \(n\preccurlyeq m \iff n|m\). Łatwo sprawdzić, że \(\preccurlyeq \) jest faktycznie relacją porządku. Faktycznie, relacja jest zwrotna, bo dla każdego \(n\in \mathbb {N}\) \(n\) dzieli \(n\); jest przechodnia, bo jeśli \(n|m \) i \(m|p\) to \(m=kn\) i \(p=lm\) dla pewnych naturalnych \(k\) i \(l\), skąd \(p=lkn\), więc \(n|p\) czyli \(n\preccurlyeq p\). Relacja jest też słabo antysymetryczna, to znaczy \(m\preccurlyeq n \wedge m\preccurlyeq n \Longrightarrow m=n\). Rzeczywiście, mamy \(m=kn \wedge n=lm\) dla pewnych naturalnych \(k,l\), skąd \(m=klm\) a zatem \(k=l=1\) a zatem \(m=n\). W tej relacji mamy na przykład \(3\preccurlyeq 6\) i \(3\preccurlyeq 9\), ale elementy \(6\) i \(9\) są nieporównywalne, bo ani \(6\) nie dzieli \(9\) ani \(9\) nie dzieli \(6\).
4. Na zbiorze takim, jak „drzewko” na poniższym rysunku
Rysunek 8.1:
definiujemy porządek tak, że większe są elementy leżące „wyżej na gałęzi”. Elementy na różnych gałęziach są nieporównywalne.
Uwaga 130. Jeśli mamy dane zbiory częściowo uporządkowane \((X_1, \leq _1),\dots ,(X_k, \leq _k)\) to w iloczynie kartezjańskim \(X_1\times \cdots \times X_k\) możemy zdefiniować porządek przykładowo tak: \((x_1,\dots ,x_k)\preceq (y_1,\dots ,y_k) \iff (x_1\leq _1y_1\wedge x_1\neq y_1)\vee (x_1=y_1\wedge x_2\leq _2 y_2\wedge x_2\neq y_2) \vee \dots \vee (x_1=y_1\wedge \dots \wedge x_{k-1}=y_{k-1}\wedge x_k\leq _k y_k)\). \(\preceq \) nazywamy porządkiem leksykograficznym (na takiej zasadzie układa się wyrazy alfabetycznie).
Uwaga 131. Jeśli mamy podzbiór \(A\) zawarty w zbiorze częściowo uporządkowanym \((X,\leq ) \) to zbiór \(A\) z relacją porządku zacieśnioną do tego zbioru, zapisywany jako \((A, \leq _A)\) też jest zbiorem częściowo uporządkowanym. Zazwyczaj piszemy też \((A,\leq )\) pomijając oznaczenie zacieśnienia.
Niektóre elementy w zbiorze częściowo uporządkowanym mają, ze względu na porządek, pewne interesujące własności. Nazywamy je elementami wyróżnionymi. Poniżej zdefiniujemy i omówimy rodzaje elementów wyróżnionych – elementy maksymalne, minimalne, największe i najmniejsze.
Definicja 132. Niech \((X,\leq )\) będzie zbiorem częściowo uporządkowanym.
\(\bullet \) Element \(x_0\in X\) nazywamy elementem maksymalnym zbioru \(X\), jeśli dla dowolnego \(x\in X\) zachodzi wynikanie \(x_0\leq x\Longrightarrow x_0=x\).
\(\bullet \) Element \(x_0\in X\) nazywamy elementem minimalnym zbioru \(X\), jeśli dla dowolnego \(x\in X\) zachodzi wynikanie \(x\leq x_0\Longrightarrow x_0=x\).
Mówiąc słowami, element \(x_0\) jest elementem maksymalnym jeśli z tego, że jakiś element \(x\) jest od niego większy lub równy wynika, że \(x\) musi być równe \(x_0\), czyli, nie ma elementów, które są większe od naszego \(x_0\) – natomiast mogą być takie, które są z nim nieporównywalne.
Analogicznie, element \(x_0\) jest elementem minimalnym jeśli z tego, że jakiś element \(x\) jest od niego mniejszy lub równy wynika, że \(x\) musi być równe \(x_0\), czyli, nie ma elementów, które są mniejsze od naszego \(x_0\) – natomiast mogą być takie, które są z nim nieporównywalne.
1. Niech \(A\) będzie zbiorem niepustym i niech \(X={\cal P}(A)\) będzie jego zbiorem podzbiorów uporządkowanym przez relację inkluzji. Wtedy \(A\) jest (jedynym) elementem maksymalnym w \(X\) a \(\emptyset \) jedynym elementem minimalnym.
2. Weźmy \((\mathbb {N}^*,\preccurlyeq )\) jak w Przykładzie 129 3., i weźmy podzbiór \(A=\{4,8,12,7,3\}\subset \mathbb {N}\) z relacją \(\preccurlyeq |_A\). Wówczas elementami maksymalnymi w \(A\) są \(8,12,7\) a elementami minimalnymi \(3,4,7\). (\(7\) jest elementem, który jest równocześnie maksymalny jak i minimalny.)
3. Niech teraz \(X=\{2,3,4,\dots \}\) z relacją porządku \(\preceq \) zdefiniowaną następująco: \(x\preceq y\iff y|x\). Jako proste ćwiczenie zostawiamy sprawdzenie, że tak określona relacja \(\preceq \) jest faktycznie relacją porządku. Zbiór \((X, \preceq )\) ma nieskończenie wiele elementów maksymalnych, są to liczby pierwsze. Gdy \(p\) jest liczbą pierwszą a \(n\in X\), to \(n|p\Longrightarrow n=p\).
Zdefiniujemy teraz element największy i najmniejszy.
Definicja 134. Niech \((X,\leq )\) będzie zbiorem częściowo uporządkowanym.
\(\bullet \) Element \(x_0\in X\) jest elementem największym zbioru \(X\) jeśli dla każdego \(x\in X\) zachodzi \(x\leq x_0\).
\(\bullet \) Element \(x_0\in X\) jest elementem najmniejszym zbioru \(X\) jeśli dla każdego \(x\in X\) zachodzi \(x_0\leq x\).
Warto zwrócić uwagę, że każdy element zbioru \(X\) musi być porównywalny z elementem największym (lub najmniejszym) – o ile taki istnieje.
Przyjrzymy się teraz zbiorom uporządkowanym z Przykładu 133.
1. Niech \(A\) będzie zbiorem niepustym i niech \(X={\cal P}(A)\) będzie jego zbiorem podzbiorów uporządkowanym przez relację inkluzji. Zbiór \(A\) jest (jedynym) elementem największym w \(X\) (zawiera każdy jego podzbiór), \(\emptyset \) elementem najmniejszym w \(X\) (zawiera się w każdym podzbiorze).
2. Niech \((X,\leq ) =(\mathbb {N}^*,\preccurlyeq )\). Ten zbiór ma element najmniejszy (\(1\) dzieli każdą liczbę naturalną) i nie ma elementu największego (nie ma liczby naturalnej podzielnej przez wszystkie inne).
3. Niech \((X,\leq )=(\mathbb {N}_{\geq 2},\preceq )\). Ten zbiór nie ma elementu najmniejszego (nie ma w nim liczby naturalnej, która dzieli wszystkie w tym zbiorze), nie ma też elementu największego.
Wykażemy teraz pewne własności poznanych elementów wyróżnionych.
Dowód. Niech \(x_0\) i \(x_1\) będą największymi elementami w zbiorze \(X\). Skoro \(x_0\) jest elementem największym, to \(x_1\leq x_0\). Skoro \(x_1\) jest elementem największym to \(x_0\leq x_1\). Ze słabej antysymetrii relacji porządku dostajemy, że \(x_0=x_1\), a zatem element największy jest jedyny.
Wykażemy teraz, że \(x_0\) – element największy, jest też elementem maksymalnym. Musimy sprawdzić, że dla dowolnego \(x_1\in X\), \(x_0\leq x_1\Longrightarrow x_0=x_1\) Przypuśćmy zatem, że jest jakiś element \(x_1\in X\) taki, że \(x_0\leq x_1\). Zarazem \(x_0\) jest elementem największym, czyli \(x_1\leq x_0\). Stąd (słaba antysymetria) mamy \(x_0=x_1\). Zatem sprawdziliśmy, że \(x_0\) jest elementem maksymalnym. Gdyby istniał inny element maksymalny, powiedzmy \(x_2\) to, ponieważ \(x_0\) jest największym elementem, mamy \(x_2\leq x_0\) skąd, ponieważ \(x_2\) miał być maksymalny, \(x_2=x_0\). □
Kolejne stwierdzenie dotyczy elementu najmniejszego:
Dowód tego stwierdzenia, analogiczny do dowodu Stwierdzenia 136, zostawiamy czytelnikowi jako ćwiczenie.
Przejdziemy teraz do zdefiniowania majoranty (ograniczenia górnego) i minoranty (ograniczenia dolnego) zbioru uporządkowanego.
Definicja 138. Niech \((X,\leq )\) będzie zbiorem częściowo uporządkowanym. Niech \(A\) będzie podzbiorem zbioru \(X\).
\(\bullet \) Element \(M\in X\) nazywamy majorantą zbioru \(A\) jeśli dla każdego \(a\in A\) zachodzi \(a\leq M\).
\(\bullet \) Element \(m\in X\) nazywamy minorantą zbioru \(A\) jeśli dla każdego \(a\in A\) zachodzi \(m \leq a\).
\(\bullet \) Niech \(X=\mathbb {R}\) z naturalnym porządkiem \(\leq \). Niech \(A=\{1, \frac {1}{2}, \frac {1}{3},\dots \}\). Majorantami tego zbioru są na przykład \(2\), \(\sqrt {7}\), \(158.5\), \(1\) a minorantami \(-\sqrt {2}\), \(-30\), \(0\).
\(\bullet \) Dla \(X\) jak poprzednio, niech \(A=[-1,1]\). Majorantami \(A\) są na przykład \(2,\sqrt {17},1\) a minorantami \(-3\), \(-2\), \(-\sqrt {17}\), \(-1\). Zauważmy, że \(1\) jest specjalną majorantą \(A\) (nie ma mniejszej) a \(-1\) specjalną minorantą \(A\) (nie ma większej).
Niech \((X,\leq )\) będzie zbiorem częściowo uporządkowanym. Niech \(A\) będzie podzbiorem zbioru \(X\). Zdefiniujmy dwa zbiory:
\[A_M=\{M\in X: M \text { jest majorantÄĚ } A \},\]
zbiór majorant zbioru \(A\) oraz
\[A_m=\{m\in X: M \text { jest minorantÄĚ } A \},\]
zbiór minorant zbioru \(A\).
Definicja 140. Dla \((X,\leq )\) jak powyżej i podzbioru \(A\subset X\) definiujemy
\(\bullet \) kres górny zbioru \(A\), inaczej supremum \(A\), jako najmniejszy element zbioru \(A_M\) (o ile istnieje). Supremum zbioru \(A\) oznaczamy \(\sup A\).
\(\bullet \) kres dolny zbioru \(A\), inaczej infimum \(A\), jako największy element zbioru \(A_m\) (o ile istnieje). Infimum zbioru \(A\) oznaczamy \(\inf A\).
O jedyności supremum (infimum) mówi następujące stwierdzenie:
Stwierdzenie 141. Niech \((X,\leq )\) będzie zbiorem częściowo uporządkowanym i niech \(A\) będzie podzbiorem zbioru \(X\). Jeśli istnieje element \(X\) będący supremum (infimum) zbioru \(A\) to jest on jedyny.
Kolejne stwierdzenie mówi, że w niektórych przypadkach łatwo zidentyfikować supremum (infimum) zbioru \(A\).
Dowód.
ad. 1. Po pierwsze, \(x_0\) jest majorantą zbioru \(A\), bo z definicji elementu największego mamy dla każdego \(a\in A\): \(a\leq x_0\). Po drugie, jeśli \(x_1\in X\) jest najmniejszą majorantą zbioru \(A\) to w szczególności \(x_0\leq x_1\) (bo \(x_0\in A\)), ale też \(x_1\leq x_0\) bo \(x_0\) jest majorantą a \(x_1\) najmniejszą z majorant. Stąd \(x_0=x_1\).
ad. 2. Dowód jest analogiczny. Po pierwsze, \(x_0\) jest minorantą zbioru \(A\), bo z definicji elementu najmniejszego mamy dla każdego \(a\in A\): \(x_0\leq a\). Po drugie, jeśli \(x_1\in X\) jest największą minorantą zbioru \(A\) to w szczególności \(x_1\leq x_0\) (bo \(x_0\in A\)), ale też \(x_0\leq x_1\) bo \(x_0\) jest minorantą a \(x_1\) największą z minorant. Stąd \(x_0=x_1\). □
Zajmiemy się teraz zdefiniowaniem i omówieniem pewnych specjalnych relacji porządku. Niech zbiór \((X,\leq )\) będzie zbiorem częściowo uporządkowanym.
\(\bullet \) Zbiór \(R\) z naturalnym porządkiem \(\leq \) jest uporządkowany liniowo.
\(\bullet \) Zbiór \(\mathbb {N}^*\) z relacją porządku \(\preccurlyeq \) jak z Przykładu 129.3. nie jest liniowo uporządkowany (np. elementy \(2\) i \(3\) nie są porównywalne).
\(\bullet \) Zbiór \(\{2^n, n\in \mathbb {N} \}\) z relacją porządku \(\preccurlyeq \) jak powyżej jest uporządkowany liniowo.
Uwaga 145. Jeśli zbiór \((X,\leq )\) jest liniowo uporządkowany, to każdy jego podzbiorów \(A\subset X\) z relacją \(\leq |_A\) też jest liniowo uporządkowany.
\(\bullet \) Zbiór \(\mathbb {N}^*\) z relacją porządku \(\preccurlyeq \) jak w Przykładzie 144 powyżej nie jest liniowo uporządkowany, ale jego podzbiór \(A=\{2^n, n\in \mathbb {N} \}\) z relacją porządku \(\preccurlyeq _A\) jest uporządkowany liniowo, czyli jest łańcuchem.
\(\bullet \) Zbiór \(\{3,6,12,18 \}\) z powyższą relacją \(\preccurlyeq \) ma łańcuchy: \(\{3,6,18\}, \{3,6,12\}\).
Kolejny rodzaj uporządkowania zbioru to uporządkowanie gęste.
Definicja 148. Niech zbiór \((X,\leq )\) będzie uporządkowany liniowo. Mówimy, że ten zbiór jest uporządkowany gęsto jeśli
\[\forall _{x,y,z\in X}: x\leq y \wedge x\neq y\ \exists _{z\in X} : x\leq z \wedge z\leq y \ \wedge x\neq z \wedge y\neq z,\]
tzn. pomiędzy każde dwa różne elementy tego możemy wstawić trzeci element tego zbioru, różny od nich.
Przejdziemy teraz do pojęcia dobrego porządku. Załóżmy, że rozważany poniżej zbiór \(X\) jest niepusty. Zdefiniujmy dobry porządek:
Definicja 150. Niech \((X,\leq )\) będzie zbiorem uporządkowanym liniowo. Mówimy, że \((X,\leq )\) jest uporządkowany dobrze (albo, że \(\leq \) jest dobrym porządkiem), gdy każdy niepusty podzbiór zbioru \(X\) ma element najmniejszy (w sensie porządku \(\leq \)), czyli
\[\forall _{A\subset X} \ A\neq \emptyset \Longrightarrow \exists _{ a\in A} \ \forall _{x\in A} \ a\leq x.\]
Na wykładzie 14 udowodnimy ważne twierdzenie, pochodzące od niemieckiego matematyka Ernesta Zermelo. Twierdzenie to mówi, że każdy zbiór można dobrze uporządkować. Poniżej podamy (na razie bez dowodu) pewną wersję tego twierdzenia. Zaczniemy od definicji odcinka początkowego zbioru.
Definicja 152. Niech \(X\) będzie zbiorem uporządkowanym liniowo. Podzbiór \({\cal O}\subset X\) nazywamy odcinkiem początkowym jeśli spełniony jest warunek
\[y\in {\cal O} \wedge x\leq y \Longrightarrow x\in {\cal O}.\]
Odcinkiem początkowym wyznaczonym przez element \(a\in X\) nazywamy
\[{\cal O}(a)=\{ x\in X: x\leq a\wedge x\neq a \}.\]
Domkniętym odcinkiem początkowym wyznaczonym przez element \(a\in X\) nazywamy
\[{\cal D}(a)={\cal O}(a)\cup \{a\}.\]
Przykład 153. Jeśli \((X, \leq )\) jest zbiorem liczb rzeczywistych z naturalnym porządkiem, to dla \(a\in \R \) odcinek początkowy \(\calo (a)\) jest równy \((-\infty ,a)\).
Niech teraz \((X,\leq )\) będzie zbiorem dobrze uporządkowanym. Weźmy funkcję
\[f: {\cal P}(X)\setminus \{X\} \to X\]
taką, że
\[f(A) \in X\setminus A.\]
Możemy teraz sformułować twierdzenie Zermelo.
Jako proste ćwiczenie dla czytelnika proponujemy znaleźć dobre uporządkowanie zbioru \(\Z \).
Powiemy teraz parę słów na temat podobieństwa zbiorów liniowo uporządkowanych (tę część materiału można traktować jako nieobowiązkową).
Niech \((X,\leq )\) i \((X^*,\leq ^*)\) będą dwoma liniowo uporządkowanymi zbiorami.
Definicja 156. Mówimy, że \((X,\leq )\) i \((X^*,\leq ^*)\) są podobne jeśli istnieje bijekcja \(f:X\bij X^*\) taka, że dla wszystkich \(x,y\in X\) zachodzi \(x\leq y \iff f(x)\leq ^* f(y)\).
Przykład 157. Niech \((X,\leq )=(\Z ,\leq )\) i \((X^*,\leq ^*)=(\N ,\leq ^*)\), gdzie dla \(m, n\in \N \) mamy
\[ m\leq ^* n\iff \begin {cases} m \text { parzyste, } n \text { nieparzyste}\\ m \text { parzyste, } n \text { parzyste i } n\leq m\\ m \text { nieparzyste, } n \text { nieparzyste i } m\leq n. \end {cases} \]
Łatwo sprawdzić, że \(\leq ^*\) jest liniowym porządkiem na \(n\). Jeśli zdefiniujemy bijekcję \(f: \Z \bij \N \) wzorem
\[ f(k)=\begin {cases} 2k+1, \ k\geq 0\\ -2k, \ k<0, \end {cases} \]
to nietrudno sprawdzić, że \(m\leq n \iff f(m)\leq ^* f(n)\), a zatem \((\Z ,\leq )\) i \((\N ,\leq ^*)\) są podobne.
1. Wspomniany wyżej zbiór \((\{1-\frac {1}{n}|n\in \N \}\cup \{1\},\leq )\) jest dobrze uporządkowany, jest równoliczny z \(\N \) (zobacz wykład 9), ale nie jest podobny do \(\N \), bo \(1\) jest największym elementem tego zbioru, a w \(\N \) nie ma największego elementu.
2. Zbiory \(\Z \) i \(\Q \) z naturalnym porządkiem nie są podobne – porządek na \(\Q \) jest gęsty, a na \(\Z \) nie.
Uwaga 159. Nietrudno sprawdzić, że relacja podobieństwa zbiorów liniowo uporządkowanych jest relacją równoważności.
Zbiorom liniowo uporządkowanym przypisujemy ten sam typ porządkowy jeśli są podobne.
Zainteresowany czytelnik o typach porządkowych zbiorów może poczytać na przykład w [7].