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, „rozumným způsobem“ rozděluje na vzájemně disjunktní podmnožiny.

Obsah

1 Definice
2 Rozklad a třídy ekvivalence
3 Vlastnosti a příklady
4 Podívejte se také na

[editovat] Definice

O binární relaci $R \,\!$ na množině $X \,\!$ řekneme, že se jedná o ekvivalenci, 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 \} \,\!$