Układ sesji

Relacja porządkująca jest relacją binarną na zbiorze, która jest refleksyjna, antysymetryczna i przechodnia.

Motywacja

Porządkowanie jest powszechnym pojęciem, z którym pracujemy w życiu codziennym. Możemy uporządkować wiele rzeczy w pewien sposób - słowa według alfabetu, uczniów w szkole według wzrostu, towary według ceny. Wszystkie te rzeczy są opisywane przez relację porządkowania, którą zwykle oznaczamy symbolem ≤. Powiązane symbole to: <, >, ≥. Ich znaczenie jest oczywiste.

Czego możemy się spodziewać po takiej sesji? Już z symbolu wynika, że w sesji porządkującej będą elementy, które są równe - chodzi więc o to, aby zdefiniować właściwości sesji jako mniejsze lub równe. Taka sesja powinna być zatem refleksyjna. Musi być prawdą, że a ≤ a.

Co dalej? Z pewnością symetria nie będzie obowiązywać - jeśli mamy porządek według ceny, to jeśli samochód jest tańszy niż chleb, to z pewnością chleb nie będzie również tańszy niż samochód. Czego byśmy się generalnie spodziewali, gdyby było tak, że a ≤ b i jednocześnie b ≤ a? Czy miałoby to w ogóle sens? Tak, jeśli a = b. Jedynym przypadkiem, w którym kolejność elementów osadzonych w sesji nie ma znaczenia, jest sytuacja, w której elementy są takie same - kolejność jest zatem antysymetryczna.

W końcu, jeśli wiemy, że samochód jest droższy niż chleb, a samolot jest jeszcze droższy niż samochód, spodziewamy się, że samolot z pewnością będzie droższy niż chleb. To właśnie opisuje przechodniość.

Częściowe porządkowanie

To, co właśnie zdefiniowaliśmy, jest w rzeczywistości tylko częściowym uporządkowaniem, nie jest kompletne. Dlaczego nie jest kompletne? Spróbujmy zdefiniować porządkowanie na zbiorach. W jaki sposób możemy porównać dwa zbiory?

Mówimy, ż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, ponieważ jeśli mamy A = {1, 2} i B = {1, 2, 3}, to możemy powiedzieć, że A jest mniejszy - B zawiera te same elementy co A, a także zawiera liczbę trzy. Tak więc, na przykład, zastosowanie miałaby następująca sytuacja:

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

Kłopot jednak w tym, że gdybyśmy chcieli porównać te zbiory: A = {a, b} i B = {a, c}. To który z nich jest mniejszy lub większy? Problem polega na tym, że chociaż oba zbiory zawierają element a, drugi element jest zawsze inny. Żaden ze zbiorów nie jest podzbiorem drugiego, więc ani A ≤ B, ani B ≤ A nie mają zastosowania. Takie zbiory są nieporównywalne przy użyciu naszego uporządkowania.

Dlatego definiujemy całkowicie uporządkowany zbiór lub ciąg, jeśli każde dwa elementy zbioru są porównywalne. Na przykład zbiory liczbowe z klasycznym uporządkowaniem są takimi zbiorami. Dla każdych dwóch liczb rzeczywistych a, b można zdecydować, czy a ≤ b czy b ≤ a.

Przykłady z życia

Przykładem, w którym nie opłaca się porównywać, może być uporządkowanie według urody, więc sesja < oznaczałaby "być brzydszym". Może powinniśmy zdefiniować to odwrotnie > jako "bycie ładniejszym", aby być bardziej poprawnym :-). Prawdopodobnie ma sens porównywanie dwóch kobiet do siebie, na przykład "Helenka Vondráčková" < "Agáta Hanychová" w sensie Agáta jest ładniejsza niż Helenka. Albo dwóch mężczyzn: "Jirka Paroubek" < "Vojta Kotek" w sensie Kotek jest ładniejszy od Paroubka.

Problem w tym, że trudno porównywać urodę kobiety i mężczyzny. Czy ładniejsza jest Agata czy Vojta? Czy brzydszy jest nasz skarb narodowy, Helena, czy seksowny mózg Jirka? Wolałbym nie dociekać...

Jeśli w ostatnim przykładzie ograniczymy się do kobiet, możemy powiedzieć, że mamy całkowicie uporządkowany zbiór, ponieważ możemy porównać piękno wszystkich kobiet.

Minimalny i maksymalny element, najmniejszy i największy element

Jeśli mamy uporządkowany zbiór M, to element min ∈ M nazywamy elementem minimalnym, jeśli nie istnieje x ∈ M taki, że x < m. Nie jesteśmy więc w stanie znaleźć elementu, który byłby mniejszy od elementu min.

Element max ∈ M nazywamy maksymalnym, jeśli nie istnieje x ∈ M taki, że x > max. Oznacza to, że nie jesteśmy w stanie znaleźć elementu, który byłby większy.

Poprzednie dwa pojęcia różnią się od pojęć najmniejszego i największego.

Element a ∈ M nazywamy najmniejszym, jeśli dla wszystkich x ∈ M jest prawdą, że a ≤ x. Oznacza to, że najmniejszy element a jest mniejszy lub równy wszystkim innym elementom w zbiorze M.

Element b ∈ M nazywamy największym, jeśli dla wszystkich x ∈ M zachodzi, że b ≥ x. Największy element b jest większy lub równy wszystkim innym elementom w zbiorze M.

Jaka jest różnica między elementem największym a elementem maksymalnym? Może istnieć więcej niż jeden element maksymalny, ponieważ zbiór nie musi być całkowicie uporządkowany. Wracając do przykładu porównywania ludzi na podstawie wyglądu, możemy powiedzieć, że Carmen Electra jest najładniejszą kobietą, a Johnny Depp najładniejszym mężczyzną. Ale nie jesteśmy już w stanie porównać tych dwóch osób ze sobą, nie wiemy, czy ładniejsza jest Carmen Electra czy Johnny Depp.

Tak więc oba elementy są maksymalne. Nie jesteśmy w stanie znaleźć osoby, która byłaby przystojniejsza od Johnny'ego Deppa - Johnny jest przystojniejszy od wszystkich innych mężczyzn i nie możemy porównać go z kobietami. Podobnie Carmen Electra - jest ładniejsza niż wszystkie kobiety i nie możemy porównywać jej z mężczyznami.

Ale żadna z nich nie jest w tym sensie najładniejsza. Ponieważ aby Johnny Depp był najładniejszy/największy, musiałby być ładniejszy niż wszyscy ludzie, w tym wszystkie kobiety. Ale ustaliliśmy już, że nie możemy porównać go do kobiet, więc nie może być najpiękniejszą osobą, jest po prostu, w terminologii teorii porządku, maksymalny.

Prawdopodobnie łatwo jest zauważyć, że jeśli zbiór ma największy element, to ten element jest również maksymalny. Jeśli element a jest większy niż wszystkie inne elementy zbioru (definicja elementu największego), to z pewnością nie możemy znaleźć elementu, który byłby jeszcze większy (definicja elementu maksymalnego).

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

Gdybyśmy chcieli mieć nieskończenie wiele elementów minimalnych, moglibyśmy zdefiniować kolejność R w następujący sposób. Najpierw definiujemy zbiory pomocnicze M_x. Zbiory te będą miały następującą postać: dla wszystkich x przedziału (0, 1), definiujemy zbiór M_x = {y | y = x + n}, gdzie n jest nieujemną liczbą całkowitą. W ten sposób otrzymamy zbiory takie jak poniższy:

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

Na każdym zbiorze M_x definiujemy klasyczny porządek, który oznaczamy przez R_x. Na koniec po prostu ujednolicamy te układy: R = ∪ R_x W tym układzie zawsze możemy porównywać tylko w obrębie oryginalnych ciągów. W ten sposób możemy dowiedzieć się, czy 0,5 ≤ 2,5, ale nie możemy już dowiedzieć się, czy 0,5 ≤ 2,7, ponieważ liczby te nie znajdowały się w tym samym zbiorze M_x, więc nie mamy zdefiniowanego ich związku.

W tej relacji porządkującej każdy element w przedziale (0, 1) jest elementem minimalnym.

Diagramy Hassego

Zbiory uporządkowane możemy przedstawić za pomocą diagramu Hassego. Jest to graf, w którym wierzchołki reprezentują elementy zbioru, a krawędź między wierzchołkami (a, b) mówi nam, że a < b, podczas gdy nie ma c takiego, że a < c < b. Zatem nie ma więcej elementów między elementami a i b. W związku z tym musi być prawdą, że w grafie wierzchołek a jest niższy niż wierzchołek b. Przykład diagramu Hassego:

Ten diagram Hasse'a przedstawia uporządkowany zbiór {A, B, C, D, E, F}. Tutaj, A < B, B < E i oczywiście A < E są prawdziwe, ale nie ma krawędzi między tymi wierzchołkami, ponieważ istnieje wierzchołek B, dla którego A < B < E jest prawdziwy. Elementy E i D są nieporównywalne, ponieważ żaden z nich nie jest powyżej ani poniżej drugiego.

Chociaż diagramy Hasse'a są zwykle wykreślane w ten ładnie wyrównany sposób, nie jest to absolutnie konieczne. Poprzedni diagram Hasse'a może wyglądać następująco:

Innym przykładem może być zbiór: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} Są one naturalnymi dzielnikami liczby 60. Uporządkowanie według podzielności można przedstawić w następujący sposób:

Uporządkowanie według podzielności oznacza, że [a, b] ∈ R tylko wtedy, gdy a dzieli b. Z diagramu możemy zauważyć, że każda liczba ma nad sobą liczby, które dzieli. Na przykład, nad liczbą 6 znajdują się liczby 12, 30 i 60. Nad liczbą 4 znajdują się liczby 12, 20 i 60 itd. I odwrotnie, liczba 3 nie ma nad sobą liczby 10, ponieważ jej nie dzieli - zauważ, że liczba 10 znajduje się wizualnie nad liczbą 3, ale nie ma linii prowadzącej do niej "od dołu do góry". Jeśli przejdziemy tylko w górę od 3, możemy przejść do 15 i 6, a z nich do 30. Do 10 dotrzemy tylko schodząc w dół, czego nie wolno nam robić.