Ekvivalence (matematika)

Pojem ekvivalence je v matematice používán pro binární relaci, která množinu, na které je definována, rozděluje na vzájemně disjunktní podmnožiny. Obvyklé značení relace je pomocí infixu ≡ nebo ~.

Zápis "a ~_R b" vyjadřuje, že v relaci ekvivalence R jsou a a b v relaci. Tedy že ${\displaystyle aRb}$ nebo ${\displaystyle (a,b)\in R}$.

Relací ekvivalence nad množinou ${\displaystyle \{a,b,c\}}$ může být například ${\displaystyle \{(a,a),(b,b),(c,c),(b,c),(c,b)\}}$. Rozkladem pak bude ${\displaystyle \{\{a\},\{b,c\}\}}$, přičemž množiny ${\displaystyle \{a\}}$ a ${\displaystyle \{b,c\}}$ nazýváme třídy rozkladu.

Binární relace ${\displaystyle R\,\!}$ na množině ${\displaystyle X\,\!}$ je ekvivalencí, pokud je ${\displaystyle R\,\!}$ na ${\displaystyle X\,\!}$

• reflexivní, tj. ${\displaystyle \forall a\in X:\in R\,\!}$
• symetrická, tj. ${\displaystyle \forall a,b\in X:\in R\implies \in R\,\!}$
• tranzitivní, tj. ${\displaystyle \forall a,b,c\in X:((\in R\land \in R)\implies \in R)\,\!}$

Relace ekvivalence určuje jednoznačně rozklad (faktormnožinu) množiny ${\displaystyle X\,\!}$ na třídy ekvivalence.

Rozkladem zde rozumíme takovou množinu ${\displaystyle Y\subseteq {\mathcal {P}}(X)\,\!}$ podmnožin množiny ${\displaystyle X\,\!}$, že sjednocením této množiny je ${\displaystyle X\,\!}$ a každé dva prvky množiny ${\displaystyle Y\,\!}$ jsou disjunktní:

• ${\displaystyle Y\subseteq {\mathcal {P}}(X)\,\!}$, kde ${\displaystyle {\mathcal {P}}(X)\,\!}$ je potenční množina množiny ${\displaystyle X\,\!}$
• ${\displaystyle \bigcup Y=X\,\!}$
• ${\displaystyle (a,b\in Y\land a\neq b)\implies a\cap b=\emptyset \,\!}$

Třídy ekvivalence jsou právě podmnožiny ${\displaystyle X\,\!}$, přičemž každá třída ekvivalence obsahuje právě všechny takové prvky z množiny ${\displaystyle X\,\!}$ , že každé dva v rámci této třídy jsou navzájem ekvivalentní ve smyslu dané relace. Každý z těchto prvků je ekvivalentní i se sebou samým (reflexivita). Třídu ekvivalence, do které patří právě nějaký prvek ${\displaystyle a\in X\,\!}$, značíme ${\displaystyle _{R}\,\!}$. Z definice je tedy patrné, že tento prvek ${\displaystyle a\in _{R}\,\!}$ je ekvivalentní s každým jiným prvkem náležícím do ${\displaystyle _{R}\,\!}$. Rozklad množiny ${\displaystyle X\,\!}$ podle ekvivalence ${\displaystyle R\,\!}$ je následující množina:
${\displaystyle X/R=\{_{R}:a\in X\}\,\!}$

Platí to i naopak – každý rozklad ${\displaystyle Y\,\!}$ množiny ${\displaystyle X\,\!}$ určuje jednoznačně právě jednu relaci ekvivalence: ${\displaystyle \in R\Leftrightarrow (\exists y\in Y)(a\in y\land b\in y)\,\!}$

• Nechť ${\displaystyle X}$ a ${\displaystyle Y}$ jsou v relaci, pokud mají stejný zbytek po dělení deseti ${\displaystyle \textstyle X\equiv Y{\pmod {10}}}$. Rozkladem celých čísel podle této relace je pak deset množin, například ${\displaystyle \{\ldots ,-28,-18,-8,2,12,22,\ldots \}}$ nebo ${\displaystyle \{\ldots ,-27,-17,-7,3,13,23,\ldots \}}$.

• Nechť státy ${\displaystyle X}$ a ${\displaystyle Y}$ jsou v relaci, pokud se v nich platí stejnou měnou. Potom v jedné množině bude {Česká republika}, protože pouze zde se platí českou korunou, v jiné {Rakousko, Slovensko, Francie, Belgie…}, protože zde se platí eurem, atd.

Na každé množině ${\displaystyle X\,\!}$ je identická relace ${\displaystyle id_{X}\,\!}$ ekvivalence. Všechny její třídy ekvivalence jsou jednoprvkové, takže rozklad podle identické relace obsahuje stejný počet prvků, jako původní množina:
${\displaystyle X/id_{X}=\{\{a\}:a\in X\}\,\!}$

Na každé množině ${\displaystyle X\,\!}$ je kartézský součin ${\displaystyle X\times X\,\!}$ (tj. největší možná binární relace na množině ${\displaystyle X\,\!}$ ) ekvivalence. Její rozklad má pouze jeden prvek – celou množinu ${\displaystyle X\,\!}$:
${\displaystyle X/(X\times X)=\{X\}\,\!}$

Uvažujme nyní o množině ${\displaystyle \omega \,\!}$ všech přirozených čísel a relaci ${\displaystyle R\,\!}$:
${\displaystyle \in R\,\!}$ právě když a,b mají stejný zbytek po dělení číslem 7

Tato relace je ekvivalence (jedná se dokonce o speciální algebraickou ekvivalenci, která je nazývána kongruence). Její rozklad má sedm tříd ekvivalence:
${\displaystyle \omega /R=\{\{0,7,14,\ldots \},\{1,8,15,\ldots \},\{2,9,16,\ldots \},\ldots \}\,\!}$

Uvažme neorientovaný graf ${\displaystyle G=\left(V,E\right)}$. Na množině vrcholů ${\displaystyle V\,\!}$ lze definovat relaci ${\displaystyle \rho \,\!}$ jako
${\displaystyle \forall v_{1}v_{2}\in V:v_{1}\ \rho \ v_{2}\Leftrightarrow }$ existuje cesta z ${\displaystyle v_{1}\,\!}$ do ${\displaystyle v_{2}\,\!}$

Rozklad třídy ${\displaystyle \rho /V\,\!}$ definuje souvislé komponenty grafu

• Zjemnění rozkladu
• Uspořádání
• Binární relace
• Ekvivalence (logika)

• Obrázky, zvuky či videa k tématu ekvivalence na Wikimedia Commons
• Ekvivalence (matematika) v encyklopedii MathWorld (anglicky)
• Relace ekvivalence na webu matweb.cz