Relacja porządku ścisłego i nieścisłego. Ich właściwości, przykłady. Relacje porządku Ścisłe relacje porządku

Ostatni przykład wprowadza koncepcję porządku alfabetycznego.

Alfabet jest krotką parami odrębnych znaków zwanych literami alfabetu. Przykładem jest alfabet dowolnego języka europejskiego, a także alfabet składający się z 10 cyfr arabskich.Na komputerze klawiatura i niektóre narzędzia pomocnicze określają alfabet prawidłowych znaków.

Słowo w alfabecieA - krotka znaków alfabetu A. Słowo zapisywane jest symbolami alfabetycznymi w rzędzie, od lewej do prawej, bez spacji.Liczba naturalna jest słowem w alfabecie cyfrowym.Formuła nie zawsze jest słowem ze względu na nieliniowy układ symboli, obecność indeks górny (wykładniki) i dolny (indeksy zmiennych, podstawy logarytmów), symbole, kreski ułamkowe, rodniki znaków itp.; jednakże według niektórych konwencji można go zapisać w postaci ciągu znaków, który wykorzystuje się np. w programowaniu komputerów (np. znak potęgowania zapisuje się jako 2 znaki mnożenia pod rząd: 5**3 oznacza trzecią potęgę liczby numer 5.

Porządek leksykograficzny (alfabetyczny) - dla różnych słów w alfabecie z uporządkowanym

symbole ustalają kolejność: , if

możliwość prezentacji , przy którym albo

(podsłowo może być puste) lub - puste podsłowo

W tej definicji - przedrostek (podsłowo początkowe) taki sam dla obu słów - lub pierwsze z lewej strony są różne

znaków, albo - ostatni znak w słowie - ogon

słowa podrzędne.

Zatem o kolejności alfabetycznej słów decyduje pierwszy symbol z lewej strony, który je odróżnia (na przykład słowo KONUS poprzedza słowo COSINUS, ponieważ różnią się one najpierw trzecią literą, a N poprzedza S w alfabecie rosyjskim). Uważa się również, że znak spacji poprzedza dowolny znak alfabetu - w przypadku, gdy jedno ze słów jest przedrostkiem innego (na przykład CON i CONE)

Ćwiczenia. Sprawdź, czy porządek alfabetyczny liczb naturalnych mających tę samą liczbę miejsc po przecinku pokrywa się z ich porządkiem według wielkości.

Pozwalać A - częściowo zamówiony zestaw. Element nazywa się maksymalny V A, jeśli nie ma elementu dla którego A< b. Element A zwany największy V A, jeśli dla każdego innego niż A element ukończony B<а-

Ustalane symetrycznie minimalne i najmniejsze elementy. Pojęcia największych i maksymalnych (odpowiednio najmniejszych i minimalnych) elementów są różne - patrz. przykład na ryc. 14. Zestaw na rys. 14,a ma największy element R, jest to również maksimum, istnieją dwa minimalne elementy: si i t, nie ma najmniejszego. Natomiast na rys. 14b mamy do czynienia ze zbiorem mającym dwa elementy maksymalne / i J, nie ma największego, minimalnego, czyli najmniejszego - jednego: T.

Ogólnie rzecz biorąc, jeśli zbiór ma największy (odpowiednio najmniejszy) element, to jest tylko jeden (może nie być żadnego).

Elementów maksymalnych i minimalnych może być kilka (może ich w ogóle nie być – w nieskończonym zbiorze; w ostatecznym przypadku – musi być).

Spójrzmy na jeszcze dwa przykłady. - relacja na planie N:

„Y dzieli X", Lub "X jest dzielnikiem liczby Y”(Na przykład,

) jest zwrotny i przechodni. Rozważmy to na skończonym zestawie dzielników liczby 30.

Relacja jest relacją częściowego porządku (nieścisłą)

i jest reprezentowany przez następującą macierz rzędu 8, zawierającą 31 znaków

Odpowiedni obwód z 8 wierzchołkami musi zawierać 31 ogniw. . Jednak wygodniejsze będzie przeglądanie, jeśli wykluczymy 8

łączniki-pętle obrazujące zwrotność relacji (elementy diagonalne macierzy) oraz spójniki przechodnie, tj. więzadła

Jeśli istnieje liczba pośrednia Z taka, że

(na przykład łącznik od). Następnie w schemacie

Pozostanie 12 więzadeł (ryc. 15); brakujące ogniwa są sugerowane „przez przechodniość”. Liczba 1 jest najmniejsza, a liczba 30

największe elementy w . Jeśli wykluczymy z liczby 30 i

rozważ zatem ten sam częściowy porządek w zestawie

nie ma elementu maksymalnego, ale są 3 elementy maksymalne: 6, 10, 15

Teraz zbudujmy ten sam obwód dla relacji opartej na wartości logicznej

(zbiór wszystkich podzbiorów) zbioru trzyelementowego

Zawiera 8 elementów:

Sprawdź, czy pasujesz do elementów a, b, c, odpowiednio liczby 2, 3, 5 oraz operacje łączenia zbiorów to mnożenie odpowiednich liczb (tj. np. podzbiór odpowiada

iloczyn 2 5 = 10), to macierz relacji będzie dokładnie taka

tak samo jak w przypadku relacji ; schematy tych dwóch zależności z opisanymi

skróty pętli i spójników przechodnich pokrywają się aż do zapisu (patrz ryc. 16). Najmniejszym elementem jest

I największy -

Relacje binarne R na zestawie A I S na zestawie W są nazywane izomorficzny, jeśli pomiędzy A i B możliwe jest nawiązanie korespondencji jeden do jednego, w której, jeśli (tj.

elementy są ze sobą powiązane R), następnie (zdjęcia

te elementy są ze sobą powiązane S).

Zatem zbiory częściowo uporządkowane są izomorficzne.

Rozważany przykład pozwala na uogólnienia.

Relacja logiczna jest porządkiem częściowym. Jeśli

Te. pęczek mi zawiera P elementy, a następnie każdy

odpowiada podzbiorze P-wymiarowy wektor z

składowe , gdzie jest funkcją charakterystyczną

ustaw A/ . Zbiór wszystkich takich wektorów można uznać za zbiór punktów P-wymiarowa przestrzeń arytmetyczna o współrzędnych 0 lub 1, czyli inaczej mówiąc, jako wierzchołki P-wymiarowy

sześcian jednostkowy, oznaczony jako , tj. sześcian o krawędziach o jednostkowej długości. Dla n = 1, 2, 3 wskazane punkty reprezentują odpowiednio końce odcinka, wierzchołki kwadratu i sześcianu – stąd potoczna nazwa. Dla /7=4 graficzną reprezentację tej zależności przedstawiono na ryc. 17. W pobliżu każdego wierzchołka 4-wymiarowego sześcianu odpowiedni

podzbiór zbioru 4-elementowego i czterowymiarowy

wektor reprezentujący funkcję charakterystyczną tego podzbioru. Wierzchołki odpowiadające podzbiorom różniącym się obecnością dokładnie jednego elementu są ze sobą połączone.

Na ryc. 17 czterowymiarowy sześcian jest przedstawiony w taki sposób, że na jednym

poziomie nieporównywalne elementy układają się w pary zawierające w rekordzie tę samą liczbę jednostek (od 0 do 4), czyli inaczej mówiąc tę ​​samą liczbę elementów w reprezentowanych podzbiorach.

Na ryc. 18a, b - inne wizualne reprezentacje 4-wymiarowego sześcianu;

na ryc. 18a oś pierwszej zmiennej OH skierowany w górę (celowe odchylenie od pionu, aby różne krawędzie sześcianu nie połączyły się):

w tym przypadku trójwymiarowy podsześcian odpowiadający X= 0 znajduje się poniżej i dla X= 1 - wyższy. Na ryc. 186 tej samej osi OH skierowany od wewnątrz sześcianu na zewnątrz; odpowiada wewnętrznemu podsześcianowi X= Aha, i ten zewnętrzny jest X = 1.

W
Plik materiałów przedstawia obraz 5-wymiarowego sześcianu jednostkowego (s. 134).

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.

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

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:

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ą

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

Właściwości relacji:

1) refleksyjność;

2) symetria;

3) przechodniość.

4) łączność.

Postawa R na zestawie X zwany odblaskowy, jeśli chodzi o każdy element zestawu X można powiedzieć, że jest w związku R Ze sobą: XOdbiór Jeśli relacja jest zwrotna, to w każdym wierzchołku grafu znajduje się pętla. I odwrotnie, graf, którego każdy wierzchołek zawiera pętlę, jest wykresem relacji zwrotnej.

Przykładami relacji zwrotnych są relacja „wielokrotność” na zbiorze liczb naturalnych (każda liczba jest wielokrotnością samej siebie) oraz relacja podobieństwa trójkątów (każdy trójkąt jest do siebie podobny) i relacja „równości” ( każda liczba jest sobie równa) itp.

Istnieją relacje, które nie mają właściwości zwrotności, na przykład relacja prostopadłości odcinków: ab, ba(nie ma ani jednego odcinka, o którym można powiedzieć, że jest prostopadły do ​​siebie) . Dlatego na wykresie tej zależności nie ma ani jednej pętli.

Relacja „dłuższa” dla odcinków, „więcej o 2” dla liczb naturalnych itp. nie ma właściwości zwrotności.

Postawa R na zestawie X zwany antyrefleksyjna, jeśli dla dowolnego elementu ze zbioru X zawsze fałszywe XOdbiór: .

Istnieją relacje, które nie są ani refleksyjne, ani antyrefleksyjne. Przykładem takiej relacji jest relacja „punkt X symetryczny aż do bólu Na stosunkowo proste l", zdefiniowany na zbiorze punktów płaszczyzny. Rzeczywiście, wszystkie punkty linii prostej l są względem siebie symetryczne oraz punkty, które nie leżą na linii prostej ja, same w sobie nie są symetryczne.

Postawa R na zestawie X zwany symetryczny, jeśli warunek jest spełniony: z faktu, że element X jest w stosunku do elementu y, wynika, że ​​element y jest w związku R z elementem X:xRyyRx.

Wykres relacji symetrycznej ma następującą cechę: wraz z każdą strzałką wychodzącą X Do y, wykres zawiera strzałkę skierowaną od y Do X(ryc. 35).

Przykładami relacji symetrycznych mogą być: relacja „równoległości” odcinków, relacja „prostopadłości” odcinków, relacja „równości” odcinków, relacja podobieństwa trójkątów, relacja „równości” ułamki itp.

Istnieją relacje, które nie mają właściwości symetrii.

Rzeczywiście, jeśli segment X dłuższy od odcinka Na, a następnie segment Na nie może być dłuższy niż segment X. Wykres tej zależności ma osobliwość: strzałka łącząca wierzchołki jest skierowana tylko w jednym kierunku.

Postawa R zwany antysymetryczny, jeśli dla jakichkolwiek elementów X I y od prawdy xRy powinno być fałszywe yRx: : xRyyRx.

Oprócz relacji „dłuższej” na wielu odcinkach występują inne relacje antysymetryczne. Na przykład relacja „większy niż” dla liczb (jeśli X więcej Na, To Na nie może być więcej X), postawę „więcej” itp.

Istnieją relacje, które nie mają ani właściwości symetrii, ani właściwości antysymetrii.

Relacja R na zbiorze X zwany przechodni, jeśli z tego elementu X jest w związku R z elementem y, i element y jest w związku R z elementem z, wynika, że ​​element X jest w związku R z elementem z: xRy I yRzxRz.

Wykres relacji przechodniej, z którego pochodzi każda para strzałek X Do y i od y Do z, zawiera strzałkę skierowaną od X Do z.

Relacja „dłuższy” na zbiorze segmentów ma również właściwość przechodniości: jeśli segment A dłuższy od odcinka B, odcinek B dłuższy od odcinka Z, a następnie segment A dłuższy od odcinka Z. Relacja „równości” na zbiorze odcinków ma również właściwość przechodniości: (a=b, b=c)(a=c).

Istnieją relacje, które nie mają własności przechodniości. Taka relacja to np. relacja prostopadłości: jeśli odcinek A prostopadle do odcinka B i segment B prostopadle do odcinka Z, a następnie segmenty A I Z nie prostopadle!

Istnieje jeszcze inna właściwość relacji, zwana właściwością powiązania, a relacja, która ją posiada, nazywana jest powiązaną.

Postawa R na zestawie X zwany połączony, jeśli dla jakichkolwiek elementów X I y z tego zbioru spełniony jest warunek: if X I y są różne, to też X jest w związku R z elementem y lub element y jest w związku R z elementem X. Używając symboli, można to zapisać w następujący sposób: xyxRy Lub yRx.

Na przykład relacja „większy niż” dla liczb naturalnych ma właściwość łączenia: dla dowolnych odrębnych liczb x i y można stwierdzić: albo x>y, Lub y>x.

W grafie połączonych relacji dowolne dwa wierzchołki są połączone strzałką. Prawdziwe jest również stwierdzenie przeciwne.

Istnieją relacje, które nie mają właściwości powiązania. Taka relacja to na przykład relacja podzielności na zbiorze liczb naturalnych: takie liczby możemy nazwać x i y niezależnie od numeru X nie jest dzielnikiem liczby y, brak numeru y nie jest dzielnikiem liczby X(liczby 17 I 11 , 3 I 10 itp.) .

Spójrzmy na kilka przykładów. Na planie X=(1, 2, 4, 8, 12) podana jest relacja „liczba”. X wielokrotność liczby y" Skonstruujmy wykres tej zależności i sformułujmy jej właściwości.

Relację równości ułamków nazywamy relacją równoważności.

Postawa R na zestawie X zwany relacja równoważności, jeśli jednocześnie ma właściwości zwrotności, symetrii i przechodniości.

Przykładami relacji równoważności są: relacje równości figur geometrycznych, relacje równoległości linii (pod warunkiem, że linie pokrywające się są uważane za równoległe).

W omawianej powyżej relacji „równości ułamków” zbiór X podzielić na trzy podzbiory: ( ; ; }, {; } , (). Podzbiory te nie przecinają się, a ich suma pokrywa się ze zbiorem X, tj. mamy podział zbioru na klasy.

Więc, jeżeli na zbiorze X dana jest relacja równoważności, to generuje ona podział tego zbioru na parami rozłączne podzbiory – klasy równoważności.

W ten sposób ustaliliśmy, że relacja równości na zbiorze
X=( ;; ; ; ; ) odpowiada podziałowi tego zbioru na klasy równoważności, z których każda składa się z równych ułamków.

Zasada podziału zbioru na klasy przy użyciu relacji równoważności jest ważną zasadą matematyki. Dlaczego?

Po pierwsze, równoważny oznacza równoważny, wymienny. Dlatego elementy tej samej klasy równoważności są wymienne. Zatem ułamki należące do tej samej klasy równoważności (; ; ), są nie do odróżnienia z punktu widzenia relacji równości i ułamka można zastąpić innym np . I ta zamiana nie zmieni wyniku obliczeń.

Po drugie, skoro klasa równoważności zawiera elementy nierozróżnialne z punktu widzenia jakiejś relacji, przyjmuje się, że klasę równoważności wyznacza którykolwiek z jej przedstawicieli, tj. dowolny element klasy. Zatem dowolną klasę ułamków równych można określić, określając dowolny ułamek należący do tej klasy. klasa równoważności przez jednego przedstawiciela pozwala na badanie zbioru przedstawicieli klas równoważności zamiast wszystkich elementów zbioru. Na przykład relacja równoważności „mieć tę samą liczbę wierzchołków”, zdefiniowaną na zbiorze wielokątów, generuje podział tego zbioru na klasy trójkątów, czworokątów, pięciokątów itp. właściwości właściwe danej klasie są uwzględniane u jednego z jej przedstawicieli.

Po trzecie, podział zbioru na klasy przy użyciu relacji równoważności służy do wprowadzenia nowych koncepcji. Na przykład pojęcie „wiązki linii” można zdefiniować jako to, co linie równoległe mają ze sobą wspólnego.

Innym ważnym rodzajem relacji jest relacja porządku. Rozważmy problem na planie X={3, 4, 5, 6, 7, 8, 9, 10 ) relacja „mają tę samą resztę z dzielenia przez 3 " Ta relacja generuje podział zbioru X na klasy: wszystkie liczby po podzieleniu przez 3 okazuje się, że to pozostałość 0 (to są liczby 3, 6, 9 ). W drugim - liczby podzielone przez 3 reszta jest 1 (to są liczby 4, 7, 10 ). Trzecia będzie zawierać wszystkie liczby, które po podzieleniu przez 3 reszta jest 2 (to są liczby 5, 8 ). Rzeczywiście powstałe zbiory nie przecinają się, a ich suma pokrywa się ze zbiorem X. Dlatego relacja „mają tę samą resztę przy dzieleniu przez 3 ", zdefiniowany na planie X, jest relacją równoważności.

Weźmy inny przykład: wielu uczniów w klasie można posortować według wzrostu lub wieku. Należy zauważyć, że ta relacja ma właściwości antysymetrii i przechodniości. Albo wszyscy znają kolejność liter w alfabecie. Zapewnia to postawa „powinnam”.

Postawa R na zestawie X zwany związek o ścisłym porządku, jeśli jednocześnie ma właściwości antysymetrii i przechodniości. Na przykład relacja „ X< y».

Jeśli relacja ma właściwości zwrotności, antysymetrii i przechodniości, to taka będzie nieścisły związek. Na przykład relacja „ Xy».

Przykładami relacji porządku są: relacja „mniejszy niż” na zbiorze liczb naturalnych, relacja „krótsza” na zbiorze odcinków. Jeśli relacja porządku ma również właściwość powiązania, to mówi się, że tak jest liniowa relacja porządku. Na przykład relacja „mniejszy niż” na zbiorze liczb naturalnych.

Pęczek X zwany uporządkowany, jeżeli jest na nim określona relacja porządku.

Na przykład wielu X={2, 8, 12, 32 ) można uporządkować za pomocą relacji „mniej niż” (rys. 41) lub można to zrobić za pomocą relacji „wielokrotność” (ryc. 42). Ale będąc relacjami porządku, relacje „mniejsze niż” i „wielokrotne” porządkują zbiór liczb naturalnych na różne sposoby. Relacja „mniej niż” pozwala porównać dowolne dwie liczby ze zbioru X, ale relacja „wielokrotność” nie ma tej własności. OK, kilka liczb. 8 I 12 nie ma związku z relacją „wielokrotność”: tak nie można powiedzieć 8 wiele 12 Lub 12 wiele 8.

Nie należy sądzić, że wszystkie stosunki dzielą się na stosunki równoważności i stosunki porządku. Istnieje ogromna liczba relacji, które nie są ani relacjami równoważności, ani relacjami porządku.

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. Ma 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?