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 $aRb$ nebo $(a,b)\in R$ .

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

Definice

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

reflexivní, tj. $\forall a\in X:[a,a]\in R\,\!$
symetrická, tj. $\forall a,b\in X:[a,b]\in R\implies [b,a]\in R\,\!$
tranzitivní, tj. $\forall a,b,c\in X:(([a,b]\in R\land [b,c]\in R)\implies [a,c]\in R)\,\!$

Rozklad a třídy ekvivalence

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

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

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

Třídy ekvivalence jsou právě podmnožiny $X\,\!$ , přičemž každá třída ekvivalence obsahuje právě všechny takové prvky z množiny $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 $a\in X\,\!$ , značíme $[a]_{R}\,\!$ . Z definice je tedy patrné, že tento prvek $a\in [a]_{R}\,\!$ je ekvivalentní s každým jiným prvkem náležícím do $[a]_{R}\,\!$ . Rozklad množiny $X\,\!$ podle ekvivalence $R\,\!$ je následující množina:
$X/R=\{[a]_{R}:a\in X\}\,\!$

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

Příklad rozkladu

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.

Vlastnosti a příklady

Identita jako ekvivalence

Na každé množině $X\,\!$ je identická relace $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:
$X/id_{X}=\{\{a\}:a\in X\}\,\!$

Kartézský součin jako ekvivalence

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

Zbytkové třídy jako ekvivalence

Uvažujme nyní o množině $\omega \,\!$ všech přirozených čísel a relaci $R\,\!$ :
$[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:
$\omega /R=\{\{0,7,14,\ldots \},\{1,8,15,\ldots \},\{2,9,16,\ldots \},\ldots \}\,\!$

Souvislé komponenty grafu jako ekvivalence

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

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

Odkazy

Související články

Externí odkazy

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

Znak	≡		≢
Název v Unicodu	Identical to		Not identical to
Kódování	dec	hex	dec	hex
Unicode	8801	U+2261	8802	U+2262
UTF-8	226 137 161	e2 89 a1	226 137 162	e2 89 a2
Číselná entita	≡	≡	≢	≢
Názvová entita	&equiv;