Relacja porządku

Relacja porządku to relacja dwuargumentowa w zbiorze, która jest zwrotna, antysymetryczna i przechodnia.

Motywacja

Porządek to zwykłe pojęcie, z którym mamy do czynienia także w codziennym życiu. Mnóstwo rzeczy możemy w jakiś sposób uporządkować — słowa alfabetycznie, uczniów w szkole według wzrostu, towary według ceny. Wszystko to opisuje relacja porządku, którą zwykle oznaczamy symbolem ≤. Powiązane symbole to: <, >, ≥. Ich znaczenie jest oczywiste.

Czego oczekiwalibyśmy od takiej relacji? Już z samego symbolu widać, że w relacji porządku będą elementy, które są takie same — chodzi nam więc o to, żeby zdefiniować własności relacji mniejszy lub równy. Taka relacja powinna więc być zwrotna. Musi zachodzić a ≤ a.

Co dalej? Na pewno nie będzie zachodzić symetryczność — jeśli porządkujemy według ceny i samochód jest tańszy niż chleb, to na pewno nie będzie jednocześnie chleb tańszy niż samochód. Czego w ogóle byśmy się spodziewali, gdyby się zdarzyło, że a ≤ b i jednocześnie b ≤ a? Czy miałoby to kiedykolwiek sens? Tak, gdyby zachodziło a = b. Jedyny przypadek, kiedy nie ma znaczenia kolejność elementów wstawionych do relacji, to sytuacja, gdy te elementy są takie same — porządek jest więc antysymetryczny.

I wreszcie jeśli wiemy, że samochód jest droższy niż chleb, a samolot jest jeszcze droższy niż samochód, to oczekujemy, że samolot na pewno będzie droższy niż chleb. To opisuje przechodniość.

Porządek częściowy

To, co przed chwilą zdefiniowaliśmy, jest tak naprawdę tylko porządkiem częściowym, a nie liniowym. Dlaczego nie jest liniowy? Spróbujmy zdefiniować porządek na zbiorach. W jaki sposób moglibyśmy porównać dwa zbiory?

Powiemy, że zbiór A jest mniejszy lub równy zbiorowi B, jeśli A ⊆ B, czyli jeśli A jest podzbiorem B. Ma to sens, bo jeśli mamy A = {1, 2} i B = {1, 2, 3}, to o A moglibyśmy powiedzieć, że jest mniejszy — B zawiera te same elementy co A, a do tego jeszcze liczbę trzy. Będzie więc zachodzić na przykład:

• {a, c} ≤ {a, b, c, d}
• ∅ ≤ {5, n, x}
• {x, e, s} ≤ {x, e, s}

Kłopot pojawia się jednak, gdy chcemy porównać takie zbiory: A = {a, b} i B = {a, c}. Który z nich jest mniejszy, a który większy? Kłopot polega na tym, że oba zbiory zawierają wprawdzie element a, ale drugi element mają różny. Żaden zbiór nie jest podzbiorem drugiego, więc nie zachodzi ani A ≤ B, ani B ≤ A. Takie zbiory są w naszym porządku nieporównywalne.

Dlatego definiujemy zbiór liniowo uporządkowany, nazywany też łańcuchem, jeśli każde dwa elementy zbioru są porównywalne. Takimi zbiorami są na przykład zbiory liczbowe ze zwykłym porządkiem. Dla każdych dwóch liczb rzeczywistych a, b potrafisz rozstrzygnąć, czy a ≤ b, czy b ≤ a.

Przykłady z życia

Przykładem, kiedy lepiej nie porównywać, mógłby być porządek według urody, relacja < oznaczałaby więc „być brzydszym”. Może powinniśmy raczej zdefiniować to odwrotnie, > jako „być ładniejszym”, żeby było grzeczniej :-). Pewnie ma sens porównywać ze sobą dwie kobiety, na przykład „Ania” < „Kasia” w tym sensie, że Kasia jest ładniejsza niż Ania. Albo dwóch mężczyzn: „Tomek” < „Bartek” w tym sensie, że Bartek jest przystojniejszy niż Tomek.

Problem w tym, że trudno porównywać urodę mężczyzny i kobiety. Kto jest ładniejszy, Kasia czy Bartek? Kto jest brzydszy, Ania czy Tomek? Lepiej tego nie badać...

Jeśli w ostatnim przykładzie ograniczymy się na przykład tylko do kobiet, możemy powiedzieć, że mamy zbiór liniowo uporządkowany, bo potrafimy porównać urodę wszystkich kobiet.

Element minimalny i maksymalny, najmniejszy i największy

Jeśli mamy uporządkowany zbiór M, to element min ∈ M nazwiemy minimalnym, jeśli nie istnieje x ∈ M takie, że x < min. Czyli nie potrafimy znaleźć elementu, który byłby mniejszy niż element min.

Element max ∈ M nazwiemy maksymalnym, jeśli nie istnieje x ∈ M takie, że x > max. Czyli nie potrafimy znaleźć elementu, który byłby większy.

Te dwa pojęcia różnią się od pojęć najmniejszy i największy.

Element a ∈ M nazwiemy najmniejszym, jeśli dla wszystkich x ∈ M zachodzi a ≤ x. Czyli najmniejszy element a jest mniejszy lub równy wszystkim pozostałym elementom zbioru M.

Element b ∈ M nazwiemy największym, jeśli dla wszystkich x ∈ M zachodzi b ≥ x. Największy element b jest większy lub równy wszystkim pozostałym elementom zbioru M.

Jaka jest różnica między elementem największym a maksymalnym? Elementów maksymalnych może być więcej, bo zbiór nie musi być liniowo uporządkowany. Jeśli wrócimy do przykładu porównywania ludzi według wyglądu, możemy powiedzieć, że Carmen Electra jest najładniejszą kobietą, a Johnny Depp najprzystojniejszym mężczyzną. Ale tych dwóch osób nie potrafimy już ze sobą porównać, nie wiemy, czy ładniejsza jest Carmen Electra, czy Johnny Depp.

Oba elementy są więc maksymalne. Nie potrafimy znaleźć osoby, która byłaby ładniejsza niż Johnny Depp — Johnny jest przystojniejszy niż wszyscy inni mężczyźni, a z kobietami nie możemy go porównywać. Podobnie z Carmen Electrą — jest ładniejsza niż wszystkie kobiety, a z mężczyznami nie możemy jej porównywać.

Ale żadne z nich nie jest największe, w tym sensie najładniejsze. Żeby Johnny Depp był najprzystojniejszy/największy, musiałby być przystojniejszy niż wszystkie osoby, łącznie ze wszystkimi kobietami. Ale już powiedzieliśmy, że z kobietami nie możemy go porównywać, dlatego nie może być najładniejszym człowiekiem, jest tylko, w terminologii teorii porządku, maksymalny.

Chyba łatwo zauważyć, że jeśli zbiór ma element największy, to ten element jest jednocześnie maksymalny. Jeśli element a jest większy niż wszystkie pozostałe elementy zbioru (definicja elementu największego), to na pewno nie znajdziemy elementu, który byłby jeszcze większy (definicja elementu maksymalnego).

Przykładem zbioru, który ma element największy i najmniejszy, jest przedział domknięty <0, 1>. Gdybyśmy wybrali ten sam przedział, ale otwarty, to nie miałby ani elementu największego, ani najmniejszego: (0, 1).

Gdybyśmy chcieli mieć nieskończenie wiele elementów minimalnych, moglibyśmy zdefiniować porządek R w taki sposób. Najpierw zdefiniujemy pomocnicze zbiory M_x. Zbiory będą miały taką postać: dla wszystkich x z przedziału (0, 1) definiujemy zbiór M_x = {y | y = x + n}, gdzie n jest nieujemną liczbą całkowitą. Dostaniemy w ten sposób na przykład takie zbiory:

$$\begin{eqnarray} M_{0{,}5}&=&\left\{0{,}5;, 1{,}5;, 2{,}5;, 3{,}5; \ldots\right\}\\ M_{0{,}7}&=&\left\{0{,}7;, 1{,}7;, 2{,}7;, 3{,}7; \ldots\right\}\\ M_{0{,}8}&=&\left\{0{,}8;, 1{,}8;, 2{,}8;, 3{,}8; \ldots\right\} \end{eqnarray}$$

W każdym zbiorze M_x definiujemy zwykły porządek, który oznaczymy R_x. Na koniec bierzemy już tylko sumę tych porządków: R = ∪ R_x. W tym porządku możemy więc porównywać zawsze tylko w obrębie pierwotnych łańcuchów. Możemy sprawdzić, czy 0,5 ≤ 2,5, ale nie możemy już sprawdzić, czy 0,5 ≤ 2,7, bo te liczby nie leżały w tym samym zbiorze M_x, więc ich zależności nie mamy zdefiniowanej.

W tej relacji porządku każdy element z przedziału (0, 1) jest elementem minimalnym.

Diagramy Hassego

Zbiory uporządkowane możemy narysować za pomocą diagramu Hassego. Jest to graf, w którym wierzchołki przedstawiają elementy zbioru, a krawędź między wierzchołkami (a, b) mówi nam, że a < b i jednocześnie nie istnieje c takie, że a < c < b. Czyli między elementami a i b nie ma już żadnego innego elementu. Przy tym w grafie wierzchołek a musi leżeć niżej niż wierzchołek b. Przykład diagramu Hassego:

Ten diagram Hassego przedstawia uporządkowany zbiór {A, B, C, D, E, F}. Przy tym zachodzi: A < B, B < E, oczywiście zachodzi też A < E, ale między tymi wierzchołkami nie ma krawędzi, bo istnieje wierzchołek B, dla którego A < B < E. Elementy E i D są nieporównywalne, bo żaden z nich nie leży nad drugim ani pod drugim.

Chociaż diagramy Hassego zwykle rysuje się tak ładnie wyrównane, nie jest to bezwzględnie konieczne. Poprzedni diagram Hassego może wyglądać też tak:

Kolejnym przykładem może być zbiór: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Są to naturalne dzielniki liczby 60. Porządek według podzielności można przedstawić tak:

Porządek według podzielności oznacza, że (a, b) ∈ R wtedy i tylko wtedy, gdy a dzieli b. Na diagramie możemy zauważyć, że każda liczba ma nad sobą liczby, które dzieli. Na przykład nad liczbą 6 są liczby 12, 30 i 60. Nad liczbą 4 są liczby 12, 20 i 60. Itd. Za to liczba 3 nie ma nad sobą liczby 10, bo jej nie dzieli — uwaga, liczba 10 jest wizualnie nad liczbą 3, ale nie prowadzi do niej „od dołu do góry” żadna linia. Jeśli od liczby 3 będziemy się poruszać tylko w górę, możemy dojść do liczb 15 i 6, a od nich do liczby 30. Do liczby 10 dostalibyśmy się tylko wtedy, gdybyśmy zeszli w dół, a tego robić nie wolno.