Ekvivalence (matematika)

Šablona:Charmap 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. $\mathrm{\forall }a\in X:[a,a]\in R$
• symetrická, tj. $\mathrm{\forall }a,b\in X:[a,b]\in R⟹[b,a]\in R$
• tranzitivní, tj. $\mathrm{\forall }a,b,c\in X:(([a,b]\in R\wedge [b,c]\in R)⟹[a,c]\in 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 𝒫(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 𝒫(X)$, kde $𝒫(X)$ je potenční množina množiny $X$
• $\bigcup Y=X$
• $(a,b\in Y\wedge a\ne b)⟹a\cap b=\mathrm{\varnothing }$

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\in X$, značíme $[a{]}_R$. Z definice je tedy patrné, že tento prvek $a\in [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\in X\}$

Platí to i naopak – každý rozklad $Y$ množiny $X$ určuje jednoznačně právě jednu relaci ekvivalence: $[a,b]\in R\iff (\mathrm{\exists }y\in Y)(a\in y\wedge b\in y)$

Příklad rozkladu

• Nechť $X$ a $Y$ jsou v relaci, pokud mají stejný zbytek po dělení deseti $X\equiv Y(\mathrm{mod}10)$. Rozkladem celých čísel podle této relace je pak deset množin, například $\{\dots ,-28,-18,-8,2,12,22,\dots \}$ nebo $\{\dots ,-27,-17,-7,3,13,23,\dots \}$.

• Nechť 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…}, protože zde se platí eurem, atd.

Vlastnosti a příklady

Identita jako ekvivalence

Na každé množině $X$ je identická relace $i{d}_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/i{d}_X=\{\{a\}:a\in 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]\in 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,\dots \},\{1,8,15,\dots \},\{2,9,16,\dots \},\dots \}$

Souvislé komponenty grafu jako ekvivalence

Uvažme neorientovaný graf $G=(V,E)$. Na množině vrcholů $V$ lze definovat relaci $\rho$ jako
$\mathrm{\forall }{v}_1{v}_2\in V:v_1\rho v_2\iff$ 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

• Šablona:Commonscat
• Šablona:MathWorld
• Relace ekvivalence na webu matweb.cz