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 <!--\; \in \; -->R$.

Relací ekvivalence nad množinou $\{a,b,c\}$ může být například $\left\{\right(a,a),(b,b),(c,c),(b,c),(c,b\left)\right\}$. Rozkladem pak bude $\left\{\right\{a\},\{b,c\left\}\right\}$, přičemž množiny $\left\{a\right\}$ 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 <!--\; \forall \; -->}a\in <!--\; \in \; -->X:[a,a]\in <!--\; \in \; -->R$
• symetrická, tj. $\mathrm{\forall <!--\; \forall \; -->}a,b\in <!--\; \in \; -->X:[a,b]\in <!--\; \in \; -->R⟹<!--\; ⟹\; -->[b,a]\in <!--\; \in \; -->R$
• tranzitivní, tj. $\mathrm{\forall <!--\; \forall \; -->}a,b,c\in <!--\; \in \; -->X:\left(\right([a,b]\in <!--\; \in \; -->R\wedge <!--\; \wedge \; -->[b,c]\in <!--\; \in \; -->R)⟹<!--\; ⟹\; -->[a,c]\in <!--\; \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 <!--\; \subseteq \; -->P\left(X\right)$ 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 <!--\; \subseteq \; -->P\left(X\right)$, kde $P\left(X\right)$ je potenční množina množiny $X$
• $\bigcup <!--\; \bigcup \; -->Y=X$
• $(a,b\in <!--\; \in \; -->Y\wedge <!--\; \wedge \; -->a\ne <!--\; \ne \; -->b)⟹<!--\; ⟹\; -->a\cap <!--\; \cap \; -->b=\mathrm{\varnothing <!--\; \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 <!--\; \in \; -->X$, značíme $[a{]}_R$. Z definice je tedy patrné, že tento prvek $a\in <!--\; \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=\left\{\right[a{]}_R:a\in <!--\; \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 <!--\; \in \; -->R\iff <!--\; \iff \; -->(\mathrm{\exists <!--\; \exists \; -->}y\in <!--\; \in \; -->Y)(a\in <!--\; \in \; -->y\wedge <!--\; \wedge \; -->b\in <!--\; \in \; -->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..}, 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=\left\{\right\{a\}:a\in <!--\; \in \; -->X\}$

Kartézský součin jako ekvivalence

Na každé množině $X$ je kartézský součin $X\times <!--\; \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 <!--\; \times \; -->X)=\left\{X\right\}$

Zbytkové třídy jako ekvivalence

Uvažujme nyní o množině $\mathrm{\omega <!--\; \omega \; -->}$ všech přirozených čísel a relaci $R$:
$[a,b]\in <!--\; \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:
$\mathrm{\omega <!--\; \omega \; -->}/R=\left\{\right\{0,7,14,\dots <!--\; \dots \; -->\},\{1,8,15,\dots <!--\; \dots \; -->\},\{2,9,16,\dots <!--\; \dots \; -->\},\dots <!--\; \dots \; -->\}$

Souvislé komponenty grafu jako ekvivalence

Uvažme neorientovaný graf $G=\left(V,E\right)$. Na množině vrcholů $V$ lze definovat relaci $\mathrm{\rho <!--\; \rho \; -->}$ jako
$\mathrm{\forall <!--\; \forall \; -->}{v}_1{v}_2\in <!--\; \in \; -->V:v_1\mathrm{\rho <!--\; \rho \; -->}{v}_2\iff <!--\; \iff \; -->$ existuje cesta z $v_1$ do $v_2$

Rozklad třídy $\mathrm{\rho <!--\; \rho \; -->}/V$ definuje souvislé komponenty grafu

Odkazy

Související články

• Zjemnění rozkladu
• Uspořádání
• Binární relace
• Ekvivalence (logika)

Externí odkazy

• Obrázky, zvuky či videa k tématu ekvivalence na Wikimedia Commons
• Ekvivalence (matematika) v encyklopedii MathWorld (anglicky)
• Relace ekvivalence na webu matweb.cz

Autoritní data	TDKIV: 000001664 GND: 4141500-0 LCCN: sh85044563 NLI: 987007553014705171