Uporządkowane relacje. Relacja zamówienia

Słowo „porządek” jest często używane w różnych kwestiach. Oficer wydaje polecenie: „Według kolejności liczb oblicz”, operacje arytmetyczne wykonywane są w określonej kolejności, sportowcy są uszeregowani według wzrostu, obowiązuje kolejność wykonywania operacji podczas wykonywania części oraz kolejność słów w zdaniu.

Co jest wspólne we wszystkich przypadkach, gdy mówimy o porządku? Faktem jest, że słowo „porządek” ma następujące znaczenie: oznacza, który element danego zbioru następuje po którym (lub który element poprzedza który).

Postawa " X następuje Na" przechodnie: jeśli " X następuje Na" I " Na następuje z", To " X następuje z" Ponadto zależność ta musi być antysymetryczna: dla dwóch różnych X I Na, Jeśli X następuje Na, To Na nie podąża X.

Definicja. Postawa R na zestawie X zwany związek o ścisłym porządku, jeśli jest przechodni i antysymetryczny.

Poznajmy cechy wykresu i wykresu relacji ścisłego porządku.

Spójrzmy na przykład. Na planie X= (5, 7, 10, 15, 12) dany stosunek R: « X < Na" Zdefiniujmy tę relację, wymieniając pary
R = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.

Zbudujmy jego wykres. Widzimy, że wykres tej zależności nie ma pętli. Na wykresie nie ma podwójnych strzałek. Jeśli od X strzałka idzie Na, i od Na- V z, następnie od X strzałka idzie z(ryc. 8).

Skonstruowany graf pozwala na uporządkowanie elementów zbioru X w tej kolejności:

{5, 7, 10, 12, 15}.

Na ryc. 6 (§ 6 tego rozdziału) kolumny VII, VIII przedstawiają wykresy relacji ścisłego rzędu.

Nieścisła relacja

Przeciwieństwem relacji „mniej niż” w zbiorze liczb rzeczywistych jest relacja „nie mniej”. Nie jest to już relacja o ścisłym porządku. Rzecz w tym, kiedy X = Na, relacje są spełnione X ³ Na I Na ³ X, tj. postawa „nie mniej” jest refleksyjna.

Definicja. Postawa R na zestawie X zwany nieścisły związek, jeśli jest zwrotny, antysymetryczny i przechodni.

Relacje takie są związkiem relacji ścisłego porządku z relacją tożsamości.

Rozważmy relację „nigdy więcej” (£) dla zbioru

X= (5, 7, 10, 15, 12). Zbudujmy jego wykres (ryc. 9).

Nieścisły wykres relacji porządku, w przeciwieństwie do wykresu ścisłej relacji porządku, ma pętle w każdym wierzchołku.

Na ryc. 6 (§ 6 tego rozdziału) kolumny V, VI są wykresami relacji o nieścisłym porządku.

Zamówione zestawy

Zbiór może okazać się uporządkowany (mówią też całkowicie uporządkowany) przez jakąś relację porządku, podczas gdy inny zbiór może być nieuporządkowany lub częściowo uporządkowany przez taką relację.

Definicja. Pęczek X zwany zamówione jakiś związek porządku R, jeśli dla dowolnych dwóch elementów x, y z X:

(X, Na) Î R Lub ( y, x) Î R.

Jeśli R jest relacją ścisłego porządku, to zbiór X uporządkowane według tej relacji podanej: if X, Na dowolne dwa nierówne elementy zbioru X, To ( X, Na) Î R Lub ( y, x) Î R lub dowolne dwa elementy x, y zestawy X są równe.

Ze szkolnych zajęć z matematyki wiadomo, że zbiory liczbowe N , Z , Q , R uporządkowane relacją „mniej niż” (<).

Zbiór podzbiorów pewnego zbioru nie jest uporządkowany poprzez wprowadzenie relacji włączenia (I) lub włączenia ścisłego (S) w powyższym znaczeniu, gdyż istnieją podzbiory, z których żaden nie jest zawarty w drugim. W tym przypadku mówimy, że dany zbiór jest częściowo uporządkowany relacją Í (lub Ì).

Rozważ zestaw X= (1, 2, 3, 4, 5, 6) i zawiera dwie relacje „mniejszy niż” i „podzielony przez”. Łatwo sprawdzić, że obie te relacje są relacjami porządkowymi. Wykres relacji „mniej niż” można przedstawić w postaci promienia.

Wykres relacji „podzielone przez” można przedstawić tylko na płaszczyźnie.

Dodatkowo wykres drugiej relacji ma wierzchołki niepołączone strzałką. Na przykład nie ma strzałki łączącej cyfry 4 i 5 (ryc. 10).

Pierwsza relacja” X < Na„nazywa się liniowym. Ogólnie rzecz biorąc, jeśli relacja jest w porządku R(ścisłe i nierygorystyczne) na planie X ma właściwość: dla dowolnego X, NaÎ X Lub xRy, Lub yRx, nazywa się to relacją porządku liniowego i zbiorem X– zbiór liniowo uporządkowany.

Jeśli zestaw X oczywiście i składa się z N elementy, a następnie uporządkowanie liniowe X sprowadza się do numerowania jego elementów liczbami 1,2,3, ..., N.

Zbiory liniowo uporządkowane mają szereg właściwości:

1°. Pozwalać a, b, c– elementy zestawu X, uporządkowane według relacji R. Jeśli to wiadomo aRw I w Rс, to mówią, że element V leży pomiędzy elementami A I Z.

2°. Pęczek X, uporządkowane liniowo według relacji R, nazywa się dyskretnym, jeśli pomiędzy dowolnymi dwoma jego elementami znajduje się tylko skończony zbiór elementów tego zbioru.

3°. Zbiór liniowo uporządkowany nazywamy gęstym, jeśli dla dowolnych dwóch różnych elementów tego zbioru istnieje element tego zbioru leżący pomiędzy nimi.

Relacja równoważności. Związek relacji równoważności z podziałem zbioru na klasy

Definicja. Postawa R na zestawie X nazywa się relacją równoważności, jeśli jest zwrotna, symetryczna i przechodnia.

Przykład. Rozważ relację „ X kolega z klasy Na„na wielu studentach Wydziału Pedagogicznego. Posiada następujące właściwości:

1) refleksyjność, ponieważ każdy uczeń jest swoim własnym kolegą z klasy;

2) symetria, ponieważ jeśli student X Na, potem uczeń Na jest kolegą z klasy ucznia X;

3) przechodniość, ponieważ jeśli student X- kolega z klasy Na i student Na- kolega z klasy z, potem uczeń X będzie kolegą z klasy ucznia z.

Zatem relacja ta ma właściwości zwrotności, symetrii i przechodniości, a zatem jest relacją równoważności. Jednocześnie wielu studentów Wydziału Pedagogicznego można podzielić na podzbiory składające się ze studentów studiujących na tym samym kierunku. Otrzymujemy 5 podzbiorów.

Relacjami równoważności są także np. relacja równoległości linii, relacja równości figur. Każda taka relacja wiąże się z podziałem zbioru na klasy.

Twierdzenie. Jeśli na planie X biorąc pod uwagę relację równoważności, dzieli ten zbiór na parami rozłączne podzbiory (klasy równoważności).

Prawdziwe jest również stwierdzenie odwrotne: jeśli na zbiorze zdefiniowano dowolną relację X, generuje podział tego zbioru na klasy, to jest to relacja równoważności.

Przykład. Na planie X= (1; 2; 3; 4; 5; 6; 7; 8) określona jest relacja „mają tę samą resztę z dzielenia przez 3”. Czy jest to relacja równoważności?

Zbudujmy wykres tej zależności: (niezależnie)

Relacja ta ma właściwości zwrotności, symetrii i przechodniości, zatem jest relacją równoważności i dzieli zbiór X do klas równoważności. W każdej klasie równoważności będą liczby, które po podzieleniu przez 3 dają tę samą resztę: X 1 = {3; 6}, X 2 = {1; 4; 7}, X 3 = {2; 5; 8}.

Uważa się, że klasę równoważności wyznacza którykolwiek z jej przedstawicieli, tj. dowolny element tej klasy. Zatem klasę ułamków równych można określić, określając dowolny ułamek należący do tej klasy.

Na początkowym toku matematyki spotyka się także relacje równoważności, na przykład „wyrażenia”. X I Na mają te same wartości liczbowe", "figura X równa figurze Na».

Definicja. Postawa R na zestawie X nazywa się relacją porządku, jeśli jest przechodnia i asymetryczna lub antysymetryczna.

Definicja. Postawa R na zestawie X nazywa się relacją ścisłego porządku, jeśli jest przechodnia i asymetryczna.

Przykłady relacje ścisłego porządku: „więcej” na zbiorze liczb naturalnych, „wyżej” na zbiorze osób itp.

Definicja. Postawa R na zestawie X nazywa się relacją nieścisłego porządku, jeśli jest przechodnia i antysymetryczna.

Przykłady relacje o nieścisłym porządku: „nie więcej” na zbiorze liczb rzeczywistych, „być dzielnikiem” na zbiorze liczb naturalnych itp.

Definicja. Pęczek X nazywa się uporządkowanym, jeśli jest na nim określona relacja porządku.

Przykład. Na planie X= (1; 2; 3; 4; 5) dane są dwie relacje: „ X £ Na" I " X- rozdzielacz Na».

Obie te relacje mają właściwości zwrotności, antysymetrii i przechodniości (sam konstruuj wykresy i sprawdzaj własności), tj. są relacjami o nieścisłym porządku. Ale pierwsza relacja ma właściwość powiązania, podczas gdy druga nie.

Definicja. Relacja zamówienia R na zestawie X nazywa się liniową relacją porządku, jeśli ma właściwość powiązania.

W szkole podstawowej uczy się wielu relacji porządku. Już w pierwszej klasie występują relacje „mniej”, „więcej” na zbiorze liczb naturalnych, „krótszy”, „dłuższy” na zbiorze odcinków itp.

Pytania kontrolne

1. Zdefiniuj relację binarną na zbiorze X.

2. Jak napisać oświadczenie, że elementy X I Na są w związku R?

3. Wymień sposoby definiowania relacji.

4. Sformułuj właściwości, jakie mogą mieć relacje. Jak te właściwości odzwierciedlają się na wykresie?

5. Jakie cechy musi mieć relacja, aby była relacją równoważności?

6. Jak relacja równoważności wiąże się z podziałem zbioru na klasy?

7. Jakie cechy musi mieć relacja, aby była relacją porządku?

X (\ displaystyle X) zwany relacja nieścisłego porządku cząstkowego (relacja porządku, relacja refleksyjna), Jeśli tam są

Pęczek X (\ displaystyle X), na którym wprowadza się relację częściowego porządku, nazywa się częściowo zamówione. Nieścisła relacja częściowego porządku jest często oznaczana przez ≼ (\ displaystyle \ preccurlyeq).

Opcje

Częściowa relacja porządku R (\ displaystyle R) zwany porządek liniowy, jeśli warunek jest spełniony

∀ x ∀ y (x R y ∨ y R x) (\ Displaystyle \ forall x \ forall y (xRy \ lub yRx)).

Pęczek X (\ displaystyle X), na który wprowadza się liniową relację porządku, nazywa się uporządkowane liniowo, Lub łańcuch.

Postawa R (\ displaystyle R), spełniający jedynie warunki zwrotności i przechodniości w przedsprzedaży lub quasi-zamówieniu.

Ścisły porządek

Jeśli warunek zwrotności zostanie zastąpiony warunkiem antyzwrotności:

∀ x ¬ (x R x) (\ Displaystyle \ forall x \ neg (xRx)),

wtedy otrzymamy definicję ścisły, Lub antyrefleksyjny porządek częściowy(zwykle oznaczone symbolem ≺ (\ displaystyle \ prec)).

Komentarz. Jednoczesna antyzwrotność i przechodniość relacji pociąga za sobą antysymetrię. Dlatego relacja jest związek o ścisłym porządku wtedy i tylko wtedy, gdy jest antyrefleksyjna i przechodnia.

Ogólnie rzecz biorąc, jeśli R (\ displaystyle R) jest zatem relacją przechodnią, antysymetryczną

R ≼ = R ∪ ( (x, x) | x ∈ X ) (\ Displaystyle R _ (\ preccurlyeq) = R \ puchar \ ((x, x) | x \ w X \)}- porządek refleksyjny R ≺ = R ∖ ( (x, x) | x ∈ X ) (\ Displaystyle R _ (\ prec) = R \ setminus \ ((x, x) | x \ w X \)}- ścisły porządek.

Przykłady

• Na zbiorze liczb rzeczywistych relacje „więcej niż” i „mniej niż” są relacjami ścisłego porządku, a „więcej lub równe” i „mniejsze lub równe” nie są ścisłe.
• Relacja podzielności na zbiorze liczb całkowitych jest relacją nieścisłego porządku.

Wymiar Dusznika-Millera

Fabuła

Oznaki < {\displaystyle <} I > (\ displaystyle >) wynaleziony

Niech R będzie relacją binarną na zbiorze A.

DEFINICJA. Relację binarną R na zbiorze A nazywa się relacją porządku na A lub porządkiem na A, jeśli jest przechodnia i antysymetryczna.

DEFINICJA. Relację rzędu R na zbiorze A nazywamy nieścisłą, jeśli jest zwrotna na A, to znaczy dla każdego z A.

Relację porządku R nazywamy ścisłą (na A), jeśli jest antyrefleksyjna na A, czyli dla dowolnego z A. Jednakże z antyzwrotności relacji przechodniej R wynika, że ​​jest ona antysymetryczna. Dlatego można podać następującą równoważną definicję.

DEFINICJA. Relację binarną R na zbiorze A nazywa się porządkiem ścisłym na A, jeśli jest przechodnia i antyzwrotna na A.

Przykłady. 1. Pozwolić będzie zbiorem wszystkich podzbiorów zbioru M. Relacja włączenia na zbiorze jest relacją nieścisłego rzędu.

2. Relacje na zbiorze liczb rzeczywistych są odpowiednio relacjami porządku ścisłego i nieścisłego.

3. Relacja podzielności w zbiorze liczb naturalnych jest relacją nieścisłego porządku.

DEFINICJA. Relacja binarna R na zbiorze A nazywana jest relacją przedporządkową lub relacją przedporządkową na A, jeśli jest zwrotna i przechodnia.

Przykłady. 1. Relacja podzielności w zbiorze liczb całkowitych nie jest porządkiem. Jest jednak zwrotny i przechodni, co oznacza, że ​​jest to przedsprzedaż.

2. Relacja implikacji logicznej jest porządkiem wstępnym na zbiorze formuł logiki zdań.

Porządek liniowy. Ważnym szczególnym przypadkiem porządku jest porządek liniowy.

DEFINICJA. Relację porządku na zbiorze nazywamy relacją porządku liniowego lub porządkiem liniowym on, jeśli jest on połączony na , tj. dla dowolnego x, y z A

Relację porządku, która nie jest liniowa, nazywa się zwykle relacją porządku częściowego lub porządkiem częściowym.

Przykłady. 1. Relacja „mniejszy niż” na zbiorze liczb rzeczywistych jest relacją porządku liniowego.

2. Relację porządku przyjętą w słownikach języka rosyjskiego nazywamy leksykograficzną. Porządek leksykograficzny na zbiorze słów w języku rosyjskim jest porządkiem liniowym.

Słowo „porządek” jest często używane w wielu różnych kwestiach. Oficer wydaje komendę: „Oblicz w kolejności numerycznej”, w określonej kolejności wykonywane są działania arytmetyczne, ranking zawodników według wzrostu, wszyscy czołowi szachiści są ustawiani w określonej kolejności według tzw. współczynników Elo (amerykański profesor który opracował współczynniki systemu, pozwalające uwzględnić wszystkie sukcesy i porażki zawodników), po mistrzostwach wszystkie drużyny piłkarskie ustawiają się w określonej kolejności itp. Podczas produkcji części obowiązuje kolejność działań, kolejność słów w zdaniu (spróbuj zrozumieć, co oznacza zdanie „na staruszku” nie zasadziłem osła!”

Układając elementy pewnego zbioru jeden po drugim, porządkujemy je w ten sposób lub ustalamy między nimi jakiś związek w celu. Najprostszym przykładem jest naturalny porządek liczb naturalnych. Jej naturalność polega na tym, że dla dowolnych dwóch liczb naturalnych wiemy, która z nich następuje po drugiej lub która jest większa od drugiej, zatem możemy ułożyć liczby naturalne w taki sposób, że większa liczba znajduje się np. na prawo od mniejszego: 1, 2, 3, ... . Oczywiście sekwencję elementów można zapisać w dowolnym kierunku, a nie tylko od lewej do prawej. Samo pojęcie liczb naturalnych zawiera już ideę porządku. Ustalając względny układ elementów dowolnego zbioru, definiujemy w ten sposób na nim pewną binarną relację porządku, która w każdym konkretnym przypadku może mieć swoją nazwę, na przykład „być mniejszym”, „być starszym”, „być być zawarte w „, „śledź” itp. Symboliczne oznaczenia porządku mogą być również różne, na przykład Í itp.

Główną cechą wyróżniającą relację porządku jest to, że ma ona właściwość przechodniości. Jeśli więc mamy do czynienia z sekwencją niektórych obiektów x 1, x 2, ..., x n,..., uporządkowane np. według relacji, potem od tego, co się wykonuje x 1x 2... x rz..., powinno to wynikać z każdej pary x ja, x j elementy tego ciągu są również spełnione x jax j:

Na parę elementów x jaJ na wykresie relacji rysujemy strzałkę z wierzchołka x ja na szczyt x j, czyli od mniejszego elementu do większego.

Wykres relacji porządku można uprościć, stosując tzw. metodę Diagramy Hassego. Diagram Hassego jest skonstruowany w następujący sposób. Mniejsze elementy są umieszczone niżej, a większe wyżej. Ponieważ sama taka reguła nie wystarczy do przedstawienia, rysowane są linie pokazujące, który z dwóch elementów jest większy, a który mniejszy od drugiego. W tym przypadku wystarczy narysować tylko linie dla elementów bezpośrednio następujących po sobie. Przykładowe diagramy Hassego pokazano na rysunku:

Nie musisz dołączać strzałek do diagramu Hassego. Diagram Hassego można obracać w płaszczyźnie, ale nie dowolnie. Podczas obracania należy zachować względne położenie (powyżej - poniżej) wierzchołków diagramu:

Postawa R w obfitości X zwany postawa ścisłego porządku, jeśli jest przechodni i asymetryczny.

Zbiór, w którym zdefiniowana jest relacja ścisłego porządku, nazywa się zamówione. Na przykład zbiór liczb naturalnych jest uporządkowany według relacji „mniejszy niż”. Ale ten sam zbiór porządkuje także inna relacja – „podzielony na” i „więcej”.

Wykres relacji „mniej niż” w zbiorze liczb naturalnych można przedstawić w postaci półprostej:

Postawa R V X zwany stosunkiem nieścisły (częściowy) porządek, jeśli jest przechodni i antysymetryczny. Każda relacja o nieścisłym porządku jest zwrotna.

Epitet „częściowy” wyraża fakt, że być może nie wszystkie elementy zbioru są porównywalne pod danym względem.

Typowymi przykładami relacji porządku częściowego są relacje „nie większe niż”, „nie mniejsze niż” i „nie większe niż”. Cząstka „nie” w nazwach relacji służy wyrażeniu ich zwrotności. Relacja „nie więcej niż” pokrywa się z relacją „mniejszy lub równy”, a relacja „nie mniej” jest tym samym, co „większy lub równy”. W związku z tym nazywany jest również porządek częściowy nie ścisłe w celu. Często częściowa (nieścisła) relacja porządku jest oznaczona symbolem „”.

Relacja włączenia Í pomiędzy podzbiorami pewnego zbioru jest także porządkiem częściowym. Oczywiście nie każde dwa podzbiory są pod tym względem porównywalne. Poniższy rysunek przedstawia kolejność częściowego włączenia do zbioru wszystkich podzbiorów zbioru (1,2,3). Strzałki na wykresie, które powinny być skierowane w górę, nie są pokazane.

Zbiory, w których podano częściowy porządek, nazywane są częściowo zamówione, lub po prostu zamówione zestawy.

Elementy X I Na nazywa się zbiór częściowo uporządkowany porównaj z nami Jeśli XNa Lub NaX. Inaczej nie są porównywalne.

Zbiór uporządkowany, w którym dowolne dwa elementy są porównywalne, nazywa się uporządkowane liniowo, a porządek jest porządkiem liniowym. Porządek liniowy nazywany jest także porządkiem doskonałym.

Na przykład zbiór wszystkich liczb rzeczywistych o porządku naturalnym, jak również wszystkie jego podzbiory, są uporządkowane liniowo.

Istnieje możliwość zamówienia obiektów o najróżniejszym charakterze hierarchicznie. Oto kilka przykładów.

Przykład 1: Części książki są ułożone w taki sposób, że książka zawiera rozdziały, rozdziały zawierają sekcje, a sekcje zawierają podsekcje.

Przykład 2. Foldery w komputerowym systemie plików są zagnieżdżone jeden w drugim, tworząc rozgałęzioną strukturę.

Przykład 3. Relację pomiędzy rodzicami i dziećmi można przedstawić jako tzw drzewo rodzinne, co pokazuje, kto jest czyim przodkiem (lub potomkiem).

Niech na planie A wydano częściowe zamówienie. Element X zwany maksimum (minimum) element zbioru A, jeśli z tego, że XNa(NaX), następuje równość X= ty Inaczej mówiąc element X jest maksimum (minimum), jeśli dla dowolnego elementu Na czy to nieprawda XNa(NaX) lub jest wykonywany X=ty Zatem element maksymalny (minimalny) jest większy (mniejszy) od wszystkich odrębnych od niego elementów, z którymi pozostaje w relacji.

Element X zwany największy (najmniejszy), jeśli dla kogokolwiek NaÎ A wykonane Na< х (х< у).

Zbiór częściowo uporządkowany może mieć kilka elementów minimalnych i/lub maksymalnych, ale nie może być więcej niż jeden element minimalny i maksymalny. Najmniejszy (największy) element jest jednocześnie minimalnym (maksymalnym), ale sytuacja odwrotna nie jest prawdą. Rysunek po lewej stronie przedstawia porządek częściowy z dwoma elementami minimalnymi i dwoma maksymalnymi, a po prawej porządek częściowy z elementami najmniejszymi i największymi:

W skończonym, częściowo uporządkowanym zbiorze zawsze występują elementy minimalne i maksymalne.

Zbiór uporządkowany, który ma największe i najmniejsze elementy, nazywa się ograniczony. Rysunek pokazuje przykład nieskończonego zbioru ograniczonego. Oczywiście nie da się przedstawić nieskończonego zbioru na skończonej stronie, ale można pokazać zasadę jego budowy. Tutaj nie pokazano pętli w pobliżu wierzchołków, aby uprościć rysunek. Z tego samego powodu nie są pokazane łuki umożliwiające wyświetlenie właściwości przechodniości. Innymi słowy, rysunek przedstawia diagram Hassego relacji porządku.

Nieskończone zbiory nie mogą mieć elementów maksymalnych i minimalnych lub obu. Na przykład zbiór liczb naturalnych (1,2, 3, ...) ma najmniejszy element 1, ale nie ma maksimum. Zbiór wszystkich liczb rzeczywistych o porządku naturalnym nie ma ani najmniejszego, ani największego elementu. Jednak jego podzbiór składający się ze wszystkich liczb X< 5, ma największy element (cyfra 5), ​​ale nie ma najmniejszego.