Ekvivalence (matematika)

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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

Rozklad a třídy ekvivalence[editovat | editovat zdroj]

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í:

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Identita jako ekvivalence[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]