Ekvivalence (matematika)

Z Wikipedie, otevřené encyklopedie

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 ~.

Obsah

1 Definice
2 Rozklad a třídy ekvivalence
3 Vlastnosti a příklady
4 Související články

[editovat] 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) \,\!$

[editovat] Rozklad a třídy ekvivalence

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

Rozkladem zde rozumíme takovou množinu $Y \subseteq \mathbb{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 \mathbb{P}(X) \,\!$ , kde $\mathbb{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řídu ekvivalence, do které patří prvek $a \isin X \,\!$ značíme $[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) \,\!$

[editovat] Vlastnosti a příklady

[editovat] 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 \} \,\!$

[editovat] 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 \} \,\!$

[editovat] 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 \} \,\!$

[editovat] 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\,\!$