(X, £) (lub (X,<), если порядок строгий).

Definicja 2: Zbiór, na którym dana jest relacja porządku, nazywa się częściowo zamówiony.

Przykład: A jest zbiorem. ( P (A), H), łatwo sprawdzić, że stosunek Í jest relacją porządku P (A).

Definicja 3: Nazywa się relację porządku R względem A kompletny ( liniowy ) zamówienie, jeśli " x, yнA (xR y Ú yR x). Zbiór (A, R) nazywamy liniowo uporządkowanym.

Przykłady:

1. relacja £ na R jest relacją pełnego porządku. Zatem ( R,£) - uporządkowane liniowo.

2. i tutaj ( P (A), H) nie jest uporządkowany liniowo

3. x£y Û y x na zestawie N nie jest kompletnym zamówieniem

Definicja 4: niech (A, £) jest zbiorem częściowo uporządkowanym. Nazywa się element aОА najmniejszy / największy / w A jeśli " xОA (a £ x) /x £ a /. Element bОА nazywa się minimum maksimum / jeśli " xнA (x£ a z x=a) /a £ x z a=x /.

Zadanie: Udowodnij, że dla zbioru liniowo uporządkowanego pojęcia największego (najmniejszego) i maksymalnego (minimalnego) elementu są zbieżne. Podaj przykład częściowo uporządkowanego zbioru, w którym nie pasują.

Skład związku

Niech będą dane zbiory A, B i C oraz relacje S między A i B (czyli SÌA´B) oraz R między B i C (RÌB´C). Zdefiniujmy nową relację między A i C w następujący sposób:

Definicja 1: Zbiór wszystkich par (x, y) takich, że istnieje zнB takich, że (x, z)н S i (z,y)н ​​R nazywamy skład relacji S i R. Wyznaczony: R o S . Zatem R o S М A ´ C .

R oS = ((x, y)| $zнB((x,z)нSu(z,y)нR)) lub x R o Sy Û $zнB(xSzÙzRy).

Przykład 1 : Niech A=(1, 2, 3), B=(1, 2, 3, 4, 5, 6), C=(3, 6, 9, 12), s = ((1,2), (2 0,4), (3,6)), r=((1,3), (2,6), (3,9), (4,12)). Wtedy r o s=((1.6), (2.12)).

Zilustrujmy sytuację na obrazku:

Przykład 2 : Niech s i r będą relacjami na N takie że

S = ((x,x+1)nxn N) i r = ((x 2 ,x)нxн N). Wtedy D r = (x 2 ïxО N)=(1,4,9,16,25,...) i D s = N.

D r o s = (xïxÞ NÙ x+1=y 2 )=(3,8,15,24,...).

W przypadku, gdy relacja jest zdefiniowana na zbiorze, można ją połączyć ze sobą:

sos = s 2 = ((x,x+2)½xn N) i ror = r 2 = ((x 4 ,x)½xn N}.

Za pomocą tej notacji można zdefiniować n-tą potęgę relacji:

, gdzie nО N,n>1.

Na przykład dla relacji z przykładu 2 mamy:

,

Chciałbym uzupełnić analogię mnożeniem. W tym celu wprowadzamy następującą naturalną definicję:

Definicja 2: Nazywa się relacje binarne równy, jeśli są równe jako podzbiory, czyli R=S jeśli "x,y((x,y)nRw(x,y)nS).

Oczywiste jest, że relacje muszą być zdefiniowane na tych samych zbiorach.

Twierdzenie (właściwości kompozycji relacji): Dla dowolnych relacji binarnych R, S, T zachodzą równości:

1. (RoS)oT = Ro(SoT)

2. (RoS) -1 = S -1 lub R -1

Dowód:

1) Dla dowolnych x i y mamy:

x(RoS)oTy º $z(xTzÙ(zRoSy)) º $z$t(xTzÙ(zStÙtRy)) º $z$t((xTzÙzSt)ÙtRy) º $t(($z(xTzÙzSt))ÙtRy) º $t((xSoTt)ÙtRy) º xRo(SoT)y.

2) x(RoS) -1 y º yRoSx º $z(ySzÙzRx) º $z(xR -1 zÙzS -1 y) º xS -1 lubR -1 y.

co było do okazania

Komentarz: jeśli R jest relacją na zbiorze A, to jasne jest, że I A oR=RoI A =R. Oznacza to, że I A zachowuje się jak jednostka podczas mnożenia liczb. Nie można jednak przeprowadzić pełnej analogii. Ponieważ, na przykład, przemienność, w ogólnym przypadku nie ma miejsca, ponieważ RoS można określić, ale SoR nie. Także równość R -1 oR=RoR -1 = I A nie zawsze ma sens.

Zamknięcie związku

Pojęcie domknięcia jest podstawowym pojęciem matematycznym i jest stosowane w większości gałęzi matematyki. Zilustrujmy to pojęcie ogólnym przykładem: weźmy obiekt x 0 i proces P, który zastosowany sekwencyjnie generuje pewien zbiór, a więc wyznacza ciąg x 1 , x 2 , ..., x n , . .. tak, że x 1 ОP(x 0), x 2 ОP(x 1),..., x n ОP(x n -1),...

Definicja 1: nazywa się zbiór zawierający wszystkie elementy wszystkich ciągów, które można otrzymać za pomocą procesu P i zaczynając od x 0 zamknięcie procesu P względem x 0 .

Jest oczywiste, że wynikiem będzie znalezienie P n (x 0) dla niektórych N. Ten N nie wiemy z góry, to zależy od samego procesu. Co więcej, jeśli weźmiemy element y z tego zamknięcia i zastosować do niego proces R, nie dostaniemy nic nowego. Oznacza to, że zestawu nie można w ten sposób rozszerzyć - jest on domknięty!

Przykład : Weźmy kwadrat S oznaczony ABCD i rozważmy proces r, który polega na obróceniu kwadratu zgodnie z ruchem wskazówek zegara o 90°:

Niech relacja A będzie dana na pewnym zbiorze. Następnie:

Definicja 2: domknięcie przechodnie relacja A na danym zbiorze nazywa się relacją A + :

Zatem z nieprzechodniej relacji A na pewnym zbiorze można skonstruować przechodnią relację A + .

Przykłady:

1. r - stosunek włączony N: r=((x, y)| y=x+1), wtedy r + =((x, y)| x

2. wł Q: s=((x, y)| x

3.t wł Q: t=((x, y)| x×y=1), wtedy r + =((x, x)| x¹0)

4. Niech L będzie zbiorem stacji londyńskiego metra; L=(a, b, c) kolejne stacje. N=((x, y)| y następuje po x). Stąd (a, b), (b, c) нN; ponadto (a, a), (b, b), (c, c), (a, c) н N 2 . Stąd N + = L'L

Ogólnie rzecz biorąc, domknięcie przechodnie nie jest zwrotne (przykład 2).

Niech A będzie relacją na X. Niech A 0 = I X .

Definicja 3: Zapięcie odblaskowe A* relacja A nazywana jest relacją . To jest .

Przykłady:

1. r*=((x, y)| x£y)

Często używana jest forma wrostka: .

Jeśli relacja jest zdefiniowana na zbiorze, to możliwa jest następująca definicja:

Przykładami zbiorów z wprowadzonymi na nich relacjami binarnymi są wykresy i częściowo uporządkowane zestawy.

Dla zdefiniowanych właściwości:

refleksyjność(Język angielski) refleksyjność): ;

Postawa R na planie X zwany odblaskowy jeśli o każdym elemencie zbioru X można powiedzieć, że jest w związku R Ze sobą: xRx. 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 grafem relacji zwrotnej.

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

Antyrefleksyjność(Język angielski) nierefleksyjność): ;

Postawa R na planie X zwany antyrefleksyjny, jeśli dla dowolnego elementu ze zbioru X zawsze fałszywe xRx:.

Symetria(Język angielski) symetria): ;

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

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

Antysymetria(Język angielski) antysymetria): ;

Postawa R zwany antysymetryczny, jeśli dla dowolnych elementów X I y poza prawdą xRy następuje fałsz yRx: : xRyyRx.

przechodniość(Język angielski) przechodniość): ;

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

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

połączenie (angielski) łączność): ;

Postawa R na planie X zwany powiązany, jeśli dla dowolnych 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 elementu y jest w związku R z elementem X. Z symbolami to definicja można zapisać tak: xyxRy Lub yRx.

Na przykład relacja „większy niż” dla liczb naturalnych ma właściwość bycia spójnym: dla dowolnych różnych liczb x i y można stwierdzić, że x>y lub y>x.

asymetria(Język angielski) relacja asymetryczna): .

Wyróżnia się następujące rodzaje relacji:

quasi-porządek quasi-porządek) - zwrotny przechodni;

równorzędność równorzędność) - zwrotny symetryczny przechodni;

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

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

W relacji „równości ułamków” omówionej powyżej 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 rozłączne parami podzbiory - klasy równoważności.

częściowe zamówienie częściowe zamówienie) - zwrotny antysymetryczny przechodni;

relacja binarna na planie nazywa się częściowa relacja porządku(Język angielski) częściowa relacja porządku

refleksyjność(Język angielski) refleksyjność): .

Antysymetria(Język angielski) antysymetria): jeśli i wtedy.

przechodniość(Język angielski) przechodniość): jeśli i wtedy.

„większy lub równy” i „mniejszy lub równy” - porządek nieścisły i liniowy, ale niepełny.

Relacja „jest dzielnikiem” na zbiorze liczb naturalnych jest relacją częściowego porządku.

ścisły porządek ścisły porządek) - antyrefleksyjny antysymetryczny przechodni;

relacja binarna na planie nazywa się ścisła relacja porządku częściowego(Język angielski) ścisła relacja porządku), jeśli ma następujące właściwości:

Antyrefleksyjność(Język angielski) nierefleksyjność): - nie wykonany.

Antysymetria(Język angielski) antysymetria): jeśli i wtedy.

przechodniość: (Język angielski) przechodniość) jeśli i wtedy.

Na zbiorze liczb rzeczywistych relacje „większe niż” i „mniejsze niż” są relacjami ścisłego porządku

porządek liniowy całkowite zamówienie) jest całkowitym antysymetrycznym przechodniem;

Jeśli relacja porządku ma również właściwość powiązania, wówczas mówi się, że jest relacją porządku liniowego. Na przykład relacja „mniej niż” na zbiorze liczb naturalnych.

relacja binarna na planie nazywa się liniowa relacja porządku(Język angielski) całkowita relacja porządku) jeśli jest to relacja częściowego porządku i ma następującą własność: albo, albo.

dominacja (angielski) przewaga) - antyrefleksyjny antysymetryczny.

tolerancja

Relacja tolerancji (lub po prostu tolerancja) na zbiorze X jest relacją binarną, która spełnia właściwości refleksyjność I symetria, ale niekoniecznie przechodni. Zatem relacja równoważności jest szczególnym przypadkiem tolerancji.

W przeciwieństwie do relacji równoważności, która daje podział zbioru elementów, na podstawie których jest zdefiniowany, na nieprzecinające się podzbiory, relacja tolerancji daje pokrycie tego zbioru. Relacja tolerancji jest również wykorzystywana np. przy klasyfikowaniu informacji w bazach wiedzy.

Na poziomie merytorycznym tolerancja oznacza, co następuje. Każdy przedmiot jest nie do odróżnienia od samego siebie (właściwość zwrotności), a podobieństwo dwóch obiektów nie zależy od kolejności, w jakiej są porównywane (właściwość symetrii). Jeśli jednak jeden obiekt jest podobny do drugiego, a ten drugi jest podobny do trzeciego, to wcale nie oznacza to, że wszystkie trzy obiekty są do siebie podobne (w związku z tym właściwość przechodniości może nie obowiązywać).

Relacja tolerancji jest często używana do opisania relacji podobieństwa między rzeczywistymi przedmiotami, relacji znajomości lub przyjaźni między ludźmi. We wszystkich tych przypadkach niekoniecznie zakłada się, że właściwość przechodniości jest zachowana. Rzeczywiście, Iwanow może być zaznajomiony z Pietrowem, Pietrow z Sidorowem, ale jednocześnie Iwanow i Sidorow mogą być sobie obcy.

Relacja na zbiorze słów będzie również tolerancyjna, jeśli zostanie zdefiniowana jako obecność co najmniej jednej wspólnej litery. Na przykład w tym przypadku przecinające się słowa krzyżówki są ze sobą powiązane.

Przykłady relacji

Przykłady relacje refleksyjne: równość, równoczesność, podobieństwo.

Przykłady stosunki nierefleksyjne: „zaopiekuj się”, „zabaw”, „nerw”.

Przykłady stosunki przechodnie: „większy niż”, „mniejszy niż”, „równy”, „podobny”, „powyżej”, „północ”.

Przykłady relacje symetryczne: równość (=), nierówność, stosunek równoważności, podobieństwo, jednoczesność, niektóre stosunki pokrewieństwa (np. braterstwa).

Przykłady stosunki antysymetryczne: większy niż, mniejszy niż, większy lub równy.

Przykłady relacje asymetryczne: stosunek „większego niż” (>) i „mniejszego niż” (<).

relacja binarna na planie nazywa się relacja równoważności(Język angielski) równoważna relacja binarna), jeśli ma następujące właściwości:

refleksyjność: .

Symetria: Jeśli następnie.

przechodniość: jeśli i wtedy.

Relacja równoważności jest oznaczona symbolem. Wpis typu jest odczytywany jako „równoważny”

Postawa równość() jest trywialnym przykładem relacji równoważności na dowolnym zbiorze.

Postawa moduł równości: na zbiorze liczb całkowitych.

Postawa równoległość linie proste na płaszczyźnie.

Postawa podobieństwa postacie w samolocie.

Postawa równorzędność na układzie równań.

Postawa łączność wierzchołki w grafie.

Postawa być tej samej wysokości na wielu ludziach.

Nazywa się system niepustych podzbiorów zbioru rozdzielać(Język angielski) przegroda) tego zestawu, jeśli:

Zestawy są tzw klasy ta partycja.

Jeśli relacja równoważności jest dana na zbiorze M, to generuje podział tego zbioru na klasy równoważności takie, że:

dowolne dwa elementy tej samej klasy są w relacji

dowolne dwa elementy różnych klas nie są w związku

Rodzina wszystkich klas równoważności zbioru tworzy zbiór tzw zestaw czynników, Lub faktoryzacja zestawy z szacunkiem i oznaczone.

Równość jest klasycznym przykładem relacji równoważności na dowolnym zbiorze.

Rozważmy relację równości na zbiorze ułamków X = ( ). Ten związek:

Odruchowo, ponieważ każdy ułamek jest sobie równy;

Jest symetryczny, ponieważ z faktu, że ułamek jest równy ułamkowi, wynika, że ​​ułamek jest równy ułamkowi;

Jest przechodnia, ponieważ z faktu, że ułamek jest równy ułamkowi, a ułamek jest równy ułamkowi, wynika, że ​​ułamek jest równy ułamkowi.

O relacji równości ułamków mówi się, że jest relacją równoważności.

Definicja. Relacja R na zbiorze X nazywana jest relacją 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, relacja równoległości prostych (pod warunkiem, że pokrywające się linie są uważane za równoległe).

Dlaczego ten rodzaj relacji jest wyróżniany w matematyce? Rozważmy relacje równości ułamków, dane na zbiorze X = ( ). (Rys. 7).

Widzimy, że zbiór jest podzielony na trzy podzbiory: Podzbiory te nie przecinają się, a ich suma pokrywa się ze zbiorem X, czyli mamy podział zbioru X na klasy. To nie przypadek.

W ogóle jeśli relacja równoważności jest dana na zbiorze X, to generuje podział tego zbioru na rozłączne parami podzbiory (klasy równoważności).

Ustaliliśmy więc, że relacja równości na zbiorze ułamków

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.

Odwrotność jest również prawdziwa: jeśli jakakolwiek relacja dana na zbiorze X generuje podział tego zbioru na klasy, to jest to relacja równoważności.

Rozważmy na przykład na zbiorze X = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) relację „mają taką samą resztę z dzielenia przez 3”. Generuje podział zbioru X na klasy: jedna będzie zawierała wszystkie liczby, przy dzieleniu przez 3, reszta to 0 (są to liczby 3, 6, 9), druga - liczby, przy dzieleniu przez 3, reszta wynosi 1 (są to liczby 1, 4, 7, 10), aw trzecim - wszystkie liczby, po podzieleniu przez 3, reszta wynosi 2 (są to liczby 2, 5, 8). Rzeczywiście, otrzymane podzbiory nie przecinają się, a ich suma pokrywa się ze zbiorem X. Zatem relacja „mają tę samą resztę z dzielenia przez 3” dana na zbiorze X jest relacją równoważności. Zauważ, że twierdzenie o związku między relacją równoważności a podziałem zbioru na klasy wymaga udowodnienia. Upuszczamy to. Powiemy tylko, że jeśli relacja równoważności ma nazwę, to odpowiadające jej nazwy nadawane są klasom. Na przykład, jeśli na zbiorze segmentów określona jest relacja równości (a jest to relacja równoważności), to zbiór segmentów dzieli się na klasy równych segmentów (patrz rys. 4). Relacja podobieństwa odpowiada podziałowi zbioru trójkątów na klasy trójkątów podobnych.

Mając więc relację równoważności na pewnym zbiorze, możemy ten zbiór podzielić na klasy. Ale można też zrobić odwrotnie: najpierw podzielić zbiór na klasy, a następnie zdefiniować relację równoważności, zakładając, że dwa elementy są równoważne wtedy i tylko wtedy, gdy należą do tej samej klasy rozważanego podziału.

Zasada dzielenia zbioru na klasy za pomocą pewnej relacji równoważności jest ważną zasadą matematyki. Dlaczego?

Po pierwsze, równoważny - to znaczy równoważny, zamienny. 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, a ułamek można zastąpić np. innym. A zamiana ta nie zmieni wyniku obliczeń.

Po drugie, ponieważ w klasie równoważności znajdują się elementy nierozróżnialne z punktu widzenia jakiejś relacji, uważa się, że klasę równoważności określa którykolwiek z jej przedstawicieli, tj. dowolny element tej klasy. Tak więc każdą klasę równych ułamków można określić, określając dowolny ułamek należący do tej klasy. Zdefiniowanie klasy równoważności przez jednego przedstawiciela pozwala zamiast wszystkich elementów zbioru badać zbiór poszczególnych przedstawicieli z klas równoważności. Na przykład relacja równoważności „mają taką samą liczbę wierzchołków” podana na zbiorze wielokątów generuje podział tego zbioru na klasy trójkątów, czworokątów, pięciokątów i tak dalej. Właściwości charakterystyczne dla określonej klasy są rozważane na jednym z jej przedstawicieli.

Trzeci, do wprowadzenia nowych pojęć służy podział zbioru na klasy za pomocą relacji równoważności. Na przykład pojęcie „wiązki linii” można zdefiniować jako wspólną cechę linii równoległych.

Ogólnie rzecz biorąc, każda koncepcja, z którą dana osoba operuje, reprezentuje pewną klasę równoważności. „Stół”, „dom”, „książka” - wszystkie te pojęcia to uogólnione idee dotyczące różnych konkretnych przedmiotów, które mają ten sam cel.

Relacje porządku są kolejnym ważnym rodzajem relacji. Jest to określone w następujący sposób.

Definicja. Relacja R na zbiorze X nazywana jest relacją porządku, jeśli jednocześnie posiada właściwości antysymetrii i przechodniości.

Przykładami relacji porządku są: relacje „mniejsze niż” na zbiorze liczb naturalnych; relacja

„krótsze” na zbiorze segmentów, ponieważ są antysymetryczne i przechodnie.

Jeśli relacja porządku ma również właściwość powiązania, wówczas mówi się, że jest relacją porządku liniowego.

Na przykład relacja „mniej niż” na zbiorze liczb naturalnych jest relacją porządku liniowego, ponieważ ma właściwości antysymetrii, przechodniości i łączności.

Definicja. Zbiór X nazywamy uporządkowanym, jeśli zdefiniowano na nim relację porządku.

Tak więc zbiór N liczb naturalnych można uporządkować, jeśli ustawimy na nim relację „mniej niż”.

Jeśli relacja porządku podana na zbiorze X ma właściwość łączności, to mówi się, że zbiór X jest uporządkowany liniowo.

Na przykład zbiór liczb naturalnych można uporządkować zarówno za pomocą relacji „mniej niż”, jak i za pomocą relacji „mnożenie” - obie są relacjami porządku. Ale relacja „mniej niż” w przeciwieństwie do relacji „mnożenie” ma również właściwość bycia połączonym. Stąd relacja „mniej niż” porządkuje zbiór liczb naturalnych liniowo.

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

Klasy pierwiastków równoważnych i ich własności

Niech %%R%% będzie relacja równoważności na zestawie %%M%% i %%a%%, jakiś element z %%M%%. Rozważ zbiór wszystkich elementów z %%M%%, które są w relacji %%R%% do elementu %%a%%.

Klasa równoważności%%Mama%%

nazywa się zbiór wszystkich elementów %%M%%, które są w relacji %%R%% do elementu %%a%%, czyli zbiór

$$ M_a = \(x \w M: x~R~a\). $$

Przykład

Niech %%M%% będzie zbiorem wszystkich mieszkańców Rosji, a %%R%% relacją równoważności „mieszkania w tym samym mieście”. Znajdź równoważne klasy elementów %%M_a%% dla %%a \in M%%.

Klasa elementów równoważna elementowi %%a%% to: $$ M_a = \(x \in M: x \text( mieszka w tym samym mieście co osoba ) a\) $$

W zależności od elementu %%a%% otrzymujemy kilka klas równoważności. Na przykład klasa równoważności mieszkańców Moskwy czy Petersburga.

Własności klas równoważności

Niech %%R%% będzie relacją równoważności na zbiorze %%M%%, a %%M_a, M_b, \dotsc, M_z, \dotsc%% będą klasami równoważności dla relacji %%R%%. Wtedy te klasy mają następujące właściwości.

Obiekt 1

Każdy element %%a \in M%% spełnia warunek $$ a \in M_a $$

Rzeczywiście, z definicji klasa %%M_a = \(x \in M: x~R~a\)%%. Wówczas element %%a%% musi spełniać warunek %%a \in M_a \leftrightarrow a~R~a%%, co jest prawdziwe, ponieważ relacja %%R%% jest zwrotna z definicji relacji równoważności. Dlatego %%a \in M_a%%.

w konsekwencji tej własności możemy powiedzieć, że każda klasa %%M_a%% jest zbiorem niepustym.

Nieruchomość 2

Niech %%M_a%% i %%M_b%% będą klasami równoważności dla relacji %%R%%. Klasy %%M_a%% i %%M_b%% są równe wtedy i tylko wtedy, gdy element %%a%% jest w relacji %%R%% do elementu %%b%%. $$ M_a = M_b \leftrightarrow a~R~b. $$

Nieruchomość 3

Niech %%M_a%% i %%M_b%% będą klasami równoważności dla relacji %%R%%. Wtedy klasy %%M_a%% i %%M_b%% nie mają wspólnych elementów. $$ M_a \neq M_b \rightarrow M_a \cap M_b = \varnic $$

Nieruchomość 4

Suma wszystkich klas równoważności zbioru %%M%% jest równa zbiorowi %%M%%. $$ \bigcup_(a\in M)(M_a) = M. $$

Ustaw partycję

Zbiór podzbiorów %%M_i%%, gdzie %%i \in I%% (do zbioru indeksów), nazywa się zbiór %%M%% rozdzielać ustawia %%M%%, jeśli spełnione są następujące warunki:

1. Każdy z podzbiorów %%M_i%% nie jest pusty.
2. Suma wszystkich podzbiorów %%M_i%% równa się zbiorowi %%M%%.
3. Dwa różne podzbiory %%M_i%% i %%M_j%%, gdzie %%i \neq j%%, nie mają wspólnych elementów.

Twierdzenie. Niech %%R%% będzie relacją równoważności na zbiorze %%M%%. Wtedy zbiór klas równoważności zbioru %%M%% tworzy jego podział.

Rzeczywiście, jeśli weźmiemy klasy równoważności %%M_a%% jako podzbiory %%M_i%%, to wszystkie trzy warunki zostaną spełnione:

1. Każda klasa równoważności jest zbiorem niepustym wg nieruchomość 1.
2. Sumą wszystkich klas równoważności jest zbiór %%M%% wg nieruchomość 4.
3. Dwie różne klasy równoważności nie mają wspólnych elementów, zgodnie z art nieruchomość 3.

Wszystkie warunki definicji partycji są spełnione. Stąd klasy równoważności są partycją zbioru %%M%%.

Przykłady

Niech zbiór %%M = \(1, 2, 3, 4, 5, 6, 7, 8, 9, 0 \)%% to następujące zbiory zbiorów mogą być podziałem tego zbioru:

1. %%A_1 = \(1, 2, 3\), A_2 = \(4, 5, 6, 7\), A_3 = \(8, 9, 0 \)%%.
2. %%B_1 = \(0, 7, 2\), B_2 = \(1, 3, 5\), B_3 = \(4, 6, 8, 9\)%%.

Ale następujące kolekcje nie są partycjami:

1. %%C_1 = \(1, 2, 3\), C_2 = \(4, 5, 6, 7\), C_3 = \(8, 9, 0, 3\)%%.
2. %%D_1 = \(0, 7, 2\), D_2 = \(1, 3, 5 \), D_3 = \(4, 6, 8, 9\), D_4 = \varnic%%.
3. %%E_1 = \(0, 1, 2\), E_2 = \(3, 4, 5\), E_3 = \(6, 7, 8\)%%.

Kolekcja zestawów %%C_i%% nie jest partycją, ponieważ nie spełnia warunku 3 podziału zbioru: zbiory %%C_1%% i %%C_3%% mają wspólny element %%3%%.

Kolekcja zestawów %%D_i%% nie jest partycją, ponieważ nie spełnia warunku 1 partycjonowania zbioru: zbiór %%D_4%% jest pusty.

Kolekcja zestawów %%E_i%% nie jest partycją, ponieważ nie spełnia warunku podziału zbioru 2: suma zbiorów %%E_1, E_2%% i %%E_3%% nie tworzy zbioru %%M%%.