8. Relacje porządku

Potocznie mówimy, że zbiór skończony $X$ jest w uporządkowany, gdy jego elementy możemy ułożyć w szereg od ``najmniejszego'' do ``największego''. Dla określenia takiego porządku istotna jest relacja ``$x$ poprzedza $y$'', którą często symbolicznie zapisujemy w postaci $x\leq y$. Taka relacja porządku $x\leq y$ jest określona na zbiorze liczb rzeczywistych $\mathbb{R}$. Analizując jej własności formułujemy ogólną definicję.

Definicja 8.1   Załóżmy, że $R$ jest relacją na zbiorze $X$ oraz $x,y\in X$.

(1) Relacja $R$ na zbiorze $X$ jest relacją liniowego porządku (lub krócej: liniowym porządkiem), gdy jest zwrotna, przechodnia, antysymetryczna i spójna.

(2) Jeśli relacja $R$ ma trzy pierwsze własności, nazywamy ją relacją częściowego porządku (lub krócej: częściowym porządkiem).

Załóżmy, że $R$ jest częściowym porządkiem na zbiorze $X$.

(3) Gdy $x\neq y$ i $x R y$, mówimy, że $x$ jest mniejszy od $y$ (poprzedza $y$) i $y$ jest większy od $x$ (w sensie częściowego porządku $R$). Dodatkowo, jeśli nie istnieje element $z\neq x,y$ taki, że $xRz\land zRy$, to mówimy, że $y$ jest następnikiem $x$, zaś $x$ poprzednikiem $y$.

(4) Mówimy, że elementy $x,y$ są porównywalne w tym częściowym porządku, gdy $x R y$ lub $yRx$.

Widzimy więc, że w częściowym porządku nie zawsze wszystkie elementy są porównywalne, w przeciwieństwie do liniowego porządku, gdzie spójność gwarantuje porównywalność każdych dwóch elementów.

Przykład liniowego porządku to relacja $\leq$ na $\mathbb{R}$. Każdy liniowy porządek jest w szczególności częściowy. Przykład częściowego porządku, który nie jest liniowy, to relacja podzielności na zbiorze $\mathbb{N}$ czy też relacja inkluzji $\subseteq$ na zbiorze ${\cal P}(X)$.

Relacje porządku często oznacza się symbolem $\leq$ lub symbolami podobnymi.

Uwaga 8.2   Jeśli $R$ jest relacją częściowego [odpowiednio: liniowego] porządku na zbiorze $X$, to dla $Y\subseteq X$ relacja ograniczona $R\vert _Y$ również jest porządkiem częściowym [odpowiednio: liniowym].

Relacje porządku na zbiorze skończonym wygodnie jest przedstawiać w formie graficznej, w postaci diagramów Hassego. Diagram Hassego składa się z pewnej liczby punktów odpowiadających elementom naszego zbioru. Pary punktów odpowiadające parom (poprzednik, następnik) są połączone niepoziomymi odcinkami. Element $a$ jest mniejszy od elementu $b$ dokładnie wtedy, gdy na rysunku można dojść od punktu odpowiadającego elementowi $a$ do punktu odpowiadającego elementowi $b$ wzdłuż odcinków idąc cały czas w górę.

Przykład 1. Niech $X=\{a,b,c,d,e,f\}$. Na rysunku

przedstawiona jest relacja $R=\{\langle a,a\rangle,\langle b,b\rangle,\langle c,c\rangle,\langle d,d\rangle,\langle e,e\rangle,\langle f,f\rangle\}\cup$
$\{\langle c,a\rangle,\langle d,a\rangle,\langle d,b\rangle,\langle e,b\rangle,\langle f,e\rangle,\langle f,b\rangle\}.$ Oznaczając relację $R$ symbolem $\leq$ mamy więc:

$$a\leq a, b\leq b, c\leq c, d\leq d, e\leq e, f\leq f,$$

$$c\leq a, d\leq a, d\leq b, e\leq b, f\leq e, f\leq b.$$

Relacja ta jest częściowym porządkiem, nie jest jednak liniowym porządkiem, gdyż nie jest spójna (np. $c,d$ nie są porównywalne).

Przykład 2. Rysunek

określa liniowy porządek $\preceq$ na zbiorze $X=\{1,2,3,4,5,6\}$ taki, że $5\preceq 3\preceq 1\preceq 2\preceq 4\preceq 6$ i ogólniej liczba napisana niżej jest mniejsza od liczby napisanej wyżej. Oczywiście $\preceq$ różni się od zwykłego porządku $\leq$ na zbiorze $X$.

Przykład 3. Niech $X=\{0,1,2,3,4,5,6\}$. Rysunek

przedstawia relację podzielności $n\mid m$, która jest częściowym porządkiem na zbiorze $X$ (jako ograniczenie relacji $n\mid m$ na zbiorze $\mathbb{N}$ do zbioru $X$).

Definicja 8.3   Niech $R$ będzie relacją częściowego porządku na $X$. Niech $a\in X$.

1. $a$ jest największy (względem $R$) $\Leftrightarrow(\forall b\in X)(bRa)$
   (tzn. ``$a$ jest większy w sensie $R$ od wszystkich innych elementów $X$'').
2. $a$ jest najmniejszy (względem $R$) $\Leftrightarrow(\forall b\in X)(aRb)$
   (tzn. ``$a$ jest mniejszy w sensie $R$ od wszystkich innych elementów $X$'').
3. $a$ jest maksymalny (względem $R$) $\Leftrightarrow(\forall b\in X)(aRb\Rightarrow a=b)$
   (tzn. ``w $X$ nie ma elementu większego od $a$ w sensie $R$'').
4. $a$ jest minimalny (względem $R$) $\Leftrightarrow(\forall b\in X)(bRa\Rightarrow a=b)$
   (tzn. ``w $X$ nie ma elementu mniejszego od $a$ w sensie $R$'').

W przykładzie 1. elementy $a$ i $b$ są maksymalne, elementy $c,d,f$ są minimalne, nie ma ani elementów największych ani najmniejszych.

W przykładzie 2. $5$ jest elementem najmniejszym i jedynym elementem minimalnym, $6$ jest elementem największym i jedynym elementem maksymalnym.

W przykładzie 3. $0$ jest elementem największym i jedynym maksymalnym, zaś $1$ elementem najmniejszym i jedynym minimalnym.

Uwaga 8.4 (1)   Jeśli $a$ jest największy, to $a$ jest maksymalny.
(2) Jeśli $a$ jest najmniejszy, to $a$ jest minimalny.
(3) Jeśli w $X$ istnieje element największy, to jest on jedyny, ponadto w tym przypadku jest on również jedynym elementem maksymalnym.
(4) Jeśli w $X$ istnieje element najmniejszy, to jest on jedyny, ponadto w tym przypadku jest on również jedynym elementem minimalnym.

Dowód. (1) Załóżmy, że $a$ jest największy. Jest więc większy w sensie $R$ od wszystkich innych elementów $X$. Dlatego nie ma w $X$ elementu większego od $a$ w sensie $R$. To potoczne rozumowanie może być jednak mylące, gdyż może być odczytywane w oparciu o nieadekwatne w tym przypadku intuicje na temat liniowego porządku liczb rzeczywistych (tzn. czytelnik może być nieświadom, gdzie w dowodzie używa się własności częściowego porządku). Dlatego przeprowadzimy dowód bardziej formalnie.

Załóżmy więc jeszcze raz, że $a$ jest największy, tzn.

(a)

dla każdego $x\in X$ mamy $xRa$.

By pokazać, że $a$ jest maksymalny, musimy udowodnić, że

$$(\forall x\in X)(aRx\Rightarrow a=x),$$

czyli że

(b)

dla każdego $x\in X$, jeżeli $aRx$, to $a=x$.

W tym celu rozważamy dowolne $x\in X$. Zakładając, że $aRx$, chcemy pokazać, że $a=x$ (tzn. chcemy pokazać prawdziwość implikacji $aRx\Rightarrow a=x$). Przypuśćmy więc, że $aRx$. Z punktu (a) dostajemy też, że $xRa$. Warunek antysymetryczności daje nam, że $aRx$ i $xRa$ implikuje $a=x$. Dlatego mamy $a=x$, co kończy dowód (b) i (1).

Dowody pozostałych punktów pozostawiamy jako ćwiczenie. $\Box$

Załóżmy teraz, że $R$ jest liniowym porządkiem na zbiorze skończonym $X$. Rozumując podobnie jak w dowodzie uwagi 8.4 można udowodnić, że wtedy istnieją w $X$ elementy największe i najmniejsze (na mocy uwagi 8.4 są one jedyne). Wybieramy więc kolejno $a_1$ jako element najmniejszy w $X$, $a_2$ jako element najmniejszy w zbiorze $X'=X\setminus \{a_1\}$ (względem relacji $R\vert _{X'}$), $a_3$ jako element najmniejszy w zbiorze $X''=X\setminus\{a_1,a_2\}$ (względem relacji $R\vert _{X''}$), i tak dalej. W ten sposób po skończeniu wielu krokach wyczerpiemy zbiór $X$ układając jego elementy w uporządkowany (w sensie $R$) szereg $a_1,a_2,\dots$, od najmniejszego do największego. W szeregu tym elementy wcześniejsze będą mniejsze w sensie $R$ od elementów późniejszych (na mocy przechodniości). Odpowiada to dobrze intuicji związanej ze zwykłym liniowym uporządkowaniem liczb rzeczywistych. Uzasadnia to poprawność naszej definicji liniowego porządku.

Definicja 8.5   Załóżmy, że $R$ jest częściowym porządkiem na zbiorze $X$, $A\subseteq X$ i $b\in X$.

1. $A$ jest łańcuchem $\Leftrightarrow(\forall a,b\in A)(aRb\lor bRa)$
   (Jest to warunek spójności, jedyny brakujący do tego, by $R$ była liniowym porządkiem, dlatego też w tym przypadku warunek ten jest równoważny temu, że $R\vert _A$ jest liniowym porządkiem.)
2. $b$ jest ograniczeniem górnym zbioru $A\Leftrightarrow(\forall a\in A)(aRb)$
   (tzn. $b$ jest równe lub większe (w sensie $R$) od wszystkich elementów $A$).
3. $b$ jest ograniczeniem dolnym zbioru $A\Leftrightarrow(\forall a\in A)(bRa)$
   (tzn. $b$ jest równe lub mniejsze (w sensie $R$) od wszystkich elementów $A$).
4. $b$ jest kresem górnym zbioru $A\Leftrightarrow b$ jest najmniejszym ograniczeniem górnym zbioru $A$.
   Symbolicznie warunek ten można zapisać następująco:

   
   

   $$(\forall a\in A)(aRb)\land(\forall c\in X)((\forall a\in A)(aRc)\Rightarrow bRc).$$
   
   
   Mówi on po pierwsze, że $b$ jest ograniczeniem górnym zbioru $A$, a następnie, że dla dowolnego $c$, jeśli $c$ jest ograniczeniem górnym $A$, to $b$ jest mniejsze lub równe $c$ (w sensie $R$)^8.1.
5. $b$ jest kresem dolnym zbioru $A\Leftrightarrow b$ jest największym ograniczeniem dolnym zbioru $A$ (względem $R$)^8.2.

Badanie istnienia ograniczeń i kresów zbioru $A$ wymaga często nieco wysiłku.

Przykład 4. Rozważmy znów relację podzielności $n\mid m$ na zbiorze $\mathbb{N}$. Zbiór

$$A=\{0,1,2,4,8,16,32,64,\dots\}$$

złożony z $0$ i kolejnych potęg dwójki jest łańcuchem w tym częściowym porządku. Istotnie, jest on liniowo uporządkowany przez relację podzielności. Zbadamy istnienie ograniczeń i kresów górnych i dolnych.

Ograniczenia dolne. Liczba naturalna $n$ jest ograniczeniem dolnym zbioru $A$ (w sensie relacji podzielności) dokładnie wtedy, gdy dla wszystkich $m\in A$ mamy $n\mid m$, tzn. gdy $n$ dzieli wszystkie liczby ze zbioru $A$. Widzimy, że jedyna taka liczba $n$ to $1$. Zatem $1$ jest jedynym ograniczeniem dolnym zbioru $A$, jest w związku z tym największym (w sensie relacji podzielności) takim ograniczeniem czyli jest kresem dolnym zbioru $A$.

Ograniczenia górne. Liczba naturalna $n$ jest ograniczeniem górnym zbioru $A$ ( w sensie relacji podzielności) dokładnie wtedy, gdy dzieli się przez wszystkie liczby ze zbioru $A$. Widzimy, że jedyną taką liczbą $n$ jest $0$. Jest więc ona także kresem górnym zbioru $A$.

Przykład 5. Rozważmy zwykły porządek $\leq$ na zbiorze liczb rzeczywistych $\mathbb{R}$. Jest to liniowy porządek, więc zarówno zbiór $\mathbb{R}$, jak i jego każdy podzbiór, jest tu łańcuchem. Niech $A=\{{1\over n+1}:n\in{\mathbb{N}}\}\cup\{{n+1\over n+2}:n\in{\mathbb{N}}\}=$

$$\left\{1,{1\over 2},{1\over 3},{1\over 4},{1\over 5},\dots\ri... ...eft\{{1\over 2},{2\over 3},{3\over 4},{4\over 5},\dots\right\}.$$

Znajdziemy kresy dolny i górny zbioru $A$.

Ograniczenia dolne. Niech $b\in{\mathbb{R}}$. Dowodzimy, że $b$ jest ograniczeniem dolnym zbioru $A\Leftrightarrow b\leq 0$.

$\Leftarrow$. Załóżmy, że $b\leq 0$. Wtedy oczywiście $b\leq a$ dla wszystkich $a\in A$, gdyż wszystkie liczby ze zbioru $A$ są $\geq 0$. Zatem $b$ jest ograniczeniem dolnym zbioru $A$.

$\Rightarrow.$ Nie wprost. Przypuśćmy, że $b$ jest ograniczeniem dolnym zbioru $A$ oraz nieprawda, że $b\leq 0$, to znaczy mamy $b>0$. Korzystając z własności liczb rzeczywistych^8.3znajdujemy liczbę naturalną $n$ taką, że $0<{1\over n+1}<b$. Ale ${1\over n+1}\in A$, więc skoro $b$ ogranicza z dołu zbiór $A$, to $b\leq{1\over n+1}$. Uzyskana sprzeczność kończy dowód $\Rightarrow$.

Widzimy, że w zbiorze ograniczeń dolnych zbioru $A$ istnieje liczba największa: jest to $0$. Dlatego $0$ jest kresem dolnym zbioru $A$.

Podobnie pokazujemy, że $1$ jest kresem górnym zbioru $A$. Szczegóły pozostawiamy jako ćwiczenie.

Nasza definicja relacji liniowego porządku odzwierciedla własności relacji $\leq$ na $\mathbb{R}$. Definiuje się również tak zwane relacje ścisłego porządku liniowego (i częściowego), odpowiadające własnościom relacji $<$ na $\mathbb{R}$. Mianowicie, mówimy, że relacja $R'$ na zbiorze $X$ jest relacją ścisłego porządku liniowego, gdy ma następujące własności:

1. $(\forall x\in X)(\neg xR'x)$ (przeciwzwrotność)
2. $(\forall x,y\in X)(xR'y\Rightarrow \neg yR'x)$ (ścisła antysymetryczność)
3. $(\forall x,y,z\in X)(xR'y\land yR'z\Rightarrow xR'z)$ (przechodniość)
4. $(\forall x,y\in X)(xR'y\lor yR'x\lor x=y)$ (ścisła spójność).

Gdy relacja $R'$ spełnia warunki 1-3, nazywamy ją ścisłym częściowym porządkiem.

Następująca uwaga pokazuje związek między porządkami i ścisłymi porządkami. Jej dowód opiera sie na spostrzeżeniu, że w przypadku liczb rzeczywistych $x,y$ mamy

$$x\leq y\Leftrightarrow x<y\lor x=y\mbox{ i }x<y\Leftrightarrow x\leq y\land x\neq y.$$

Uwaga 8.6   $R'$ jest relacją ścisłego częściowego [odpowiednio: liniowego] porządku na $X\Leftrightarrow$ $R'$ jest przeciwzwrotna i $R=R'\cup\{\langle x,x\rangle:x\in X\}$ jest relacją częściowego [odpowiednio: liniowego] porządku na $X$.