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 \,\. +more 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 \land [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 \,\. +more , ž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 \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 \,\. +more , ž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 \,\. +more určuje jednoznačně právě jednu relaci ekvivalence: [a,b] \isin R \Leftrightarrow (\exist y \isin Y)(a \isin y \land b \isin 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. +more}, 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 \,\. +more 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 \,\. +more (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

[url=http://www.matweb.cz/relace-ekvivalence]Relace ekvivalence[/url] na webu [url=http://www.matweb.cz/]matweb.cz[/url]

Kategorie:Logické operace Kategorie:Vlastnosti matematických relací