Relacja równoważności

Relacja równoważności – zwrotna, symetryczna i przechodnia relacja dwuargumentowa określona na pewnym zbiorze 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.

Definicja 
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  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 
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:

 

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.

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 (zob. sekcję tworzenie struktur).

Niezależność 
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 
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 

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ę 
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 
 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.
 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 

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ę:
 w teorii grup przy definiowaniu grup ilorazowych,
 w teorii pierścieni przy określaniu pierścieni ilorazowych,
 w algebrze liniowej przy wprowadzaniu przestrzeni ilorazowych.

Przykłady:
 arytmetyka modularna,
 konstrukcja Grassmana liczb całkowitych,
 ciało liczb wymiernych (powstałe z liczb całkowitych) lub ogólniej ciało ułamków dowolnego pierścienia całkowitego,
 konstrukcja liczb rzeczywistych przy pomocy ciągów Cauchy’ego (poprzez utożsamienie ciągów Cauchy’ego liczb wymiernych o różnicy dążącej do zera),
 klasy równoważności relacji równoliczności zbiorów można utożsamić z liczbami kardynalnymi, a klasy równoważności relacji izomorfizmu zbiorów dobrze uporządkowanych to liczby porządkowe, o ile rozszerzymy pojęcie klasy abstrakcji na klasy,
 redukcja praporządku do porządku,
 konstrukcja topologii ilorazowej.

Przypisy

Bibliografia

Literatura dodatkowa