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 \isin X:[a,a] \isin R\,\!$
• symetrická, tj. $\forall a,b \isin X:[a,b] \isin R \implies [b,a] \isin R \,\!$
• tranzitivní, tj. $\forall a,b,c \isin X:( [a,b] \isin R \and [b,c] \isin R) \implies [a,c] \isin 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 \isin Y \and 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 \isin X \,\!$, značíme $[a]_R \,\!$. Z definice je tedy patrné, že tento prvek $a \isin [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 \isin X \} \,\!$

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

Příklad rozkladu

Rozklad celých čísel podle relace "x-y je násobek deseti" je množina deseti nekonečných množin, z nichž jedna je {..., -38, -28, -18, -8, 2, 12, 22, 32 ...}, jiná je {..., -37, -27, -17, -7, 3, 13, 23, 33 ...} 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 \isin 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] \isin 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

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

Externí odkazy

• (anglicky)  Ekvivalence (matematika) v encyklopedii MathWorld