Relacja równoważności

relacja zwrotna, symetryczna i przechodnia

Relacja równoważnościzwrotna, symetryczna i przechodnia relacja dwuargumentowa określona na pewnym zbiorze[1] utożsamiająca ze sobą w pewien sposób jego elementy, co ustanawia podział tego zbioru na rozłączne podzbiory według tej relacji. Podobnie każdy podział zbioru niesie ze sobą informację o pewnej relacji równoważności[2].

Definicja edytuj

Niech   będzie dowolnym zbiorem. Relację   nazywamy relacją równoważności wtedy i tylko wtedy, gdy jest ona

  • zwrotna, tzn. dla dowolnych   zachodzi
 
  • symetryczna, tzn. dla dowolnych  
 
  • przechodnia, tzn. dla dowolnych   zachodzi wynikanie
 

Dwa elementy   takie, że   oznacza się symbolicznie  [3][4] i nazywa się równoważnymi lub tożsamymi w sensie R. Relacje równoważności oznacza się zwykle symbolami     lub podobnymi.

Klasy abstrakcji i przestrzeń ilorazowa edytuj

Niech   będzie zbiorem, na którym określono relację równoważności   Klasą równoważności lub klasą abstrakcji (także warstwą) elementu   nazywa się zbiór[5]:

 

czyli zbiór wszystkich elementów zbioru   równoważnych z   Jeżeli relacja równoważności znana jest z kontekstu, pisze się zwykle po prostu  

Dowolny element ustalonej klasy abstrakcji nazywa się jej reprezentantem; w szczególności reprezentantem klasy   jest element   Każdy element   należy do dokładnie jednej klasy abstrakcji, mianowicie   Wynika stąd, że dwie klasy równoważności odpowiadające elementom   i   są albo identyczne, co zachodzi, gdy   albo rozłączne, gdy   czyli

  wtedy i tylko wtedy, gdy  

W powyższy sposób na zbiorze   wyznaczony jest podział na klasy abstrakcji. Wspomniany podział, czyli zbiór wszystkich warstw oznaczany   nazywa się przestrzenią ilorazową lub krótko ilorazem (zbioru)   przez (relację)   Zasada abstrakcji mówi, że dla każdego podziału zbioru istnieje pewna relacja równoważności, a każda relacja równoważności ustanawia pewien podział zbioru[2].

Relacji równoważności w zbiorze   odpowiada relacja równości w przestrzeni ilorazowej   Własność ta umożliwia tworzenie nowych struktur przez utożsamienie niektórych elementów w zbiorze[6] (zob. sekcję tworzenie struktur).

Niezależność edytuj

Niech   będzie pewną własnością elementów   taką, że jeśli   to   jest prawdziwe, o ile   jest prawdziwe (czyli wtedy, ze względu na symetrię – po zamianie   na   i   na    ). Wtedy własność   nazywa się dobrze określoną lub niezależną od (wyboru reprezentantów) relacji   (niektórzy autorzy piszą też „zgodną z  ”). Sytuacja ta ma miejsce np. w teorii charakterów grup skończonych.

Częstym przypadkiem jest funkcja   dowolnych zbiorów; jeżeli z   wynika   to o   mówi się, że jest niezależna od wyboru reprezentantów relacji   lub krótko: niezależna od   Przypadek ten można wyjaśnić za pomocą diagramu przemiennego, zob. niezmiennik.

Rzutowanie edytuj

Przekształcenie   dane wzorem   (każdemu elementowi przypisana jest jego klasa abstrakcji) nazywa się odwzorowaniem ilorazowym. Jest ono zawsze funkcją „na”. Ponieważ utożsamianie pewnych elementów zbioru jest podobne do przeprowadzania geometrycznej operacji rzutu (w której utożsamiane są obiekty leżące „pod” rzutowanym obiektem), to przekształcenie to nazywa się również rzutowaniem kanonicznym bądź naturalnym.

Jeżeli na zbiorze   ustalona jest struktura algebraiczna, to wymaga się zwykle, aby rzutowanie ją zachowywało (tzn. by rzut danej algebry był algebrą tego samego typu). Jeśli tak jest, to odwzorowanie ilorazowe nazywa się wtedy epimorfizmem kanonicznym (naturalnym) (zob. transformacja naturalna).

Warto wspomnieć o klasie równoważności odpowiadającej elementowi   relacji opisanej w sekcji niezależność dla funkcji   Jest nią przeciwobraz   Taką relację nazywa się niekiedy jądrem funkcji   Każdą relację równoważności można traktować jako jądro przekształcenia  

Dzielenie przez zbiór edytuj

Osobny artykuł: topologia ilorazowa.

Jeżeli relacja równoważności   utożsamia ze sobą wszystkie elementy zbioru   tzn.   to często „zapomina się” o niej i zamiast   pisze się po prostu   Konstrukcję tę nazywa się czasami sklejeniem zbioru   do punktu.

Uwaga!
W teorii grup to oznaczenie stosuje się dla grup ilorazowych, które są przykładami przestrzeni ilorazowych. Aby wynikiem „dzielenia” grupy   pozostała grupa wymaga się, aby dzielnik   nie był tylko zwykłą podgrupą, ale grupą specjalnego rodzaju – tzw. podgrupą normalną (inna nazwa to dzielnik normalny), która gwarantuje prawidłowość i jednoznaczność konstrukcji grupy ilorazowej.
Odpowiednia relacja równoważności dana jest następująco: jeśli   jest podgrupą normalną w   to   jest zbiorem klas abstrakcji relacji   zadanej wzorem   Podobnie ma się rzecz z pierścieniami ilorazowymi i ideałami w teorii pierścieni, w ogólności jednak jednoznaczne struktury ilorazowe w pozostałych działach algebry powstają już wyłącznie przez wskazanie relacji, nie zaś podstruktury o specjalnych własnościach.

Generowanie przez relację edytuj

Relację równoważności na zbiorze   generowaną przez relację binarną   definiuje się jako najmniejszą relację równoważności, która zawiera   jako podzbiór. Można ją scharakteryzować jako relację

 

gdzie   jest identycznością na zbiorze   a operacja   oznacza branie domknięcia przechodniego relacji.

Przykłady edytuj

  • W dowolnym zbiorze   zdefiniowana jest relacja:
      wtedy i tylko wtedy, gdy  
Jest to istotnie relacja równoważności nazywana równością. Klasami abstrakcji są zbiory jednoelementowe (singletony)  
  • W zbiorze   określona jest relacja:   wtedy i tylko wtedy, gdy   i   dają taką samą resztę z dzielenia przez 3 (kongruencja modulo 3). Pokazuje się, że jest to relacja równoważności. Jej klasami abstrakcji są:
     
     
     
Poszczególne warstwy są rozłączne, a przestrzenią ilorazową jest zbiór:
 
  • W geometrii relacjami równoważności są m.in. przystawanie i podobieństwo.
  • W zbiorze prostych na płaszczyźnie określona jest relacja równoległości: proste   i   są równoważne, gdy są równoległe. Klasami abstrakcji są kierunki.
  • W algebrze abstrakcyjnej każdy izomorfizm wprowadza relację równoważności uznającą struktury danej teorii za nierozróżnialne (mające te same własności).
  • W dowolnym grafie nieskierowanym   zdefiniujmy relację na wierzchołkach:
      gdy istnieje ścieżka z   do   (być może jest to ścieżka pusta, jeżeli  ).
Wyznaczony przez tę relację podział nazywa się podziałem grafu na spójne składowe[7].
  • Podobną relację określa się w grafach skierowanych: określamy, że   gdy istnieją ścieżki z   do   i z   do   Relacja   daje w wyniku podział grafu na silnie spójne składowe.

Kongruencja edytuj

Osobny artykuł: kongruencja.

Jeżeli   jest homomorfizmem pewnej algebry ogólnej   na   to relacja

 

określona w   jest relacją równoważności (i warstwy   pokrywają się z klasami abstrakcji w relacji  ). Określając w odpowiedni sposób działania w zbiorze   można wprowadzić w nim strukturę algebry – wspomniana algebra ilorazowa jest izomorficzna z   Konstrukcja ta pojawia się:

Przykłady:

Przypisy edytuj

  1. relacja równoważności, [w:] Encyklopedia PWN [dostęp 2021-10-01].
  2. a b Guzicki i Zakrzewski 2005 ↓, s. 155–171.
  3. Helena Rasiowa: Wstęp do matematyki współczesnej. Wyd. 6. Warszawa: Państwowe Wydawnictwo Naukowe, 1977, s. 62.
  4. Wiktor Marek, Janusz Onyszkiewicz: Elementy logiki i teorii mnogości w zadaniach. Wyd. 12. Warszawa: Wydawnictwo Naukowe PWN, 2006, s. 37. ISBN 83-01-14547-1.
  5. klasy abstrakcji, [w:] Encyklopedia PWN [dostęp 2022-03-12].
  6. ilorazowa konstrukcja, [w:] Encyklopedia PWN [dostęp 2022-03-12].
  7. Robert Wilson: Wprowadzenie do teorii grafów. Wydawnictwo Naukowe PWN, 1985, s. 30, 41.

Bibliografia edytuj

Literatura dodatkowa edytuj

  • Zbigniew Furdzik i inni, Nowoczesna matematyka dla inżynierów. Część I Algebra, Kraków: Wydawnictwo AGH, 1993, ISSN 0239-6114.