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:[a,a]\in R\,\!}$
• symetrická, tj. ${\displaystyle \forall a,b\in X:[a,b]\in R\implies [b,a]\in R\,\!}$
• tranzitivní, tj. ${\displaystyle \forall a,b,c\in X:(([a,b]\in R\land [b,c]\in R)\implies [a,c]\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 [a]_{R}\,\!}$. Z definice je tedy patrné, že tento prvek ${\displaystyle a\in [a]_{R}\,\!}$ je ekvivalentní s každým jiným prvkem náležícím do ${\displaystyle [a]_{R}\,\!}$. Rozklad množiny ${\displaystyle X\,\!}$ podle ekvivalence ${\displaystyle R\,\!}$ je následující množina:
${\displaystyle X/R=\{[a]_{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 [a,b]\in R\Leftrightarrow (\exists y\in Y)(a\in y\land b\in y)\,\!}$

X a Y jsou v relaci, pokud (X mod 10) = (Y mod 10). Rozkladem celých čísel podle této relace jsou pak množiny, z nichž jedna je {…, -38, -28, -18, -8, 2, 12, 22, 32 …}, jiná je {…, -37, -27, -17, -7, 3, 13, 23, 33 …} atd.
Nebo státy X a 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 [a,b]\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