Relacja równoważności

Relacja Równoważności

Relacja równoważności to zwrotna, symetryczna i przechodnia relacja dwuargumentowa, która dzieli zbiór na rozłączne podzbiory. Umożliwia ona utożsamianie elementów zbioru, co prowadzi do powstania klas równoważności.

Definicja

Niech $X$ będzie zbiorem. Relację $R\; \backslash subseteq\; X\; \backslash times\; X$ nazywamy relacją równoważności, gdy spełnia następujące warunki:

• Zwrotność: $x\backslash ,R\backslash ,x$ dla każdego $x\; \backslash in\; X$.
• Symetryczność: $x\backslash ,R\backslash ,y\; \backslash Rightarrow\; y\backslash ,R\backslash ,x$ dla dowolnych $x,\; y\; \backslash in\; X$.
• Przechodniość: $(x\backslash ,R\backslash ,y\; \backslash wedge\; y\backslash ,R\backslash ,z)\; \backslash Rightarrow\; x\backslash ,R\backslash ,z$ dla dowolnych $x,\; y,\; z\; \backslash in\; X$.

Elementy $x,\; y\; \backslash in\; X$, dla których $(x,\; y)\; \backslash in\; R$, nazywane są równoważnymi.

Klasy Abstrakcji i Przestrzeń Ilorazowa

Klasa równoważności elementu $x\; \backslash in\; X$ to zbiór $[x]\_\backslash sim\; =\; \backslash \{y\; \backslash in\; X\; :\; y\; \backslash sim\; x\backslash \}$, zawierający wszystkie elementy równoważne z $x$. Przestrzeń ilorazowa $X/\_\backslash sim$ to zbiór wszystkich klas równoważności.

Niezależność

Własność $P(x)$ jest dobrze określona, jeśli przy $x\; \backslash sim\; y$ zachodzi $P(x)\; \backslash iff\; P(y)$. Funkcja $f\backslash colon\; X\; \backslash to\; Y$ jest niezależna od relacji $\backslash sim$, jeśli $x\_1\; \backslash sim\; x\_2$ implikuje $f(x\_1)\; =\; f(x\_2)$.

Rzutowanie

Odwzorowanie $X\; \backslash to\; X/\_\backslash sim$, przypisujące każdemu elementowi jego klasę abstrakcji, nazywane jest odwzorowaniem ilorazowym. Funkcja ta jest zwykle epimorfizmem kanonicznym, zachowującym strukturę algebraiczną, jeśli taka istnieje.

Generowanie przez Relację

Relacja równoważności $R^e$ generowana przez relację binarną $R$ jest najmniejszą relacją równoważności zawierającą $R$.

Przykłady

• Relacja równości w zbiorze $X$, gdzie $x\backslash ,R\backslash ,y$ wtedy i tylko wtedy, gdy $x\; =\; y$.
• Kongruencja modulo 3 w zbiorze $A=\backslash \{1,2,3,4,5,6,7\backslash \}$.
• Równoległość prostych w geometrii.
• Izomorfizm w algebrze abstrakcyjnej.

Kongruencja

Relacja $a\; \backslash backsim\; b\; \backslash iff\; \backslash varphi(a)\; =\; \backslash varphi(b)$, gdzie $\backslash varphi$ jest homomorfizmem, jest relacją równoważności. Pozwala ona na wprowadzenie struktury algebry w zbiorze $A/\_\backslash backsim$.

Przykłady zastosowań obejmują teorię grup, pierścieni i przestrzeni liniowych.