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 ~.
| Znak | ≡ | ≢ | ||
|---|---|---|---|---|
| Název v Unicodu | Identical to | Not identical to | ||
| Kódování | dec | hex | dec | hex |
| Unicode | 8801 | U+2261 | 8802 | U+2262 |
| UTF-8 | 226 137 161 | e2 89 a1 | 226 137 162 | e2 89 a2 |
| Číselná entita | ≡ | ≡ | ≢ | ≢ |
| Názvová entita | ≡ | |||
Zápis "a ~R b" vyjadřuje, že v relaci ekvivalence R jsou a a b v relaci. Tedy že nebo .
Relací ekvivalence nad množinou může být například . Rozkladem pak bude , přičemž množiny a nazýváme třídy rozkladu.
Definice Editovat
Binární relace na množině je ekvivalencí, pokud je na
- reflexivní, tj.
- symetrická, tj.
- tranzitivní, tj.
![{\displaystyle \forall a\in X:[a,a]\in R\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3549090540fa21a9149dfbf0e01e1cdd93244817)
![{\displaystyle \forall a,b\in X:[a,b]\in R\implies [b,a]\in R\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/096f1912c6aeae5b1553bcff5ae980badc53ba0f)
![{\displaystyle \forall a,b,c\in X:(([a,b]\in R\land [b,c]\in R)\implies [a,c]\in R)\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/416f1edbe5db2643b267b99717ff09e9e17b5ed5)
Rozklad a třídy ekvivalence Editovat
Relace ekvivalence určuje jednoznačně rozklad (faktormnožinu) množiny na třídy ekvivalence.
Rozkladem zde rozumíme takovou množinu podmnožin množiny , že sjednocením této množiny je a každé dva prvky množiny jsou disjunktní:
- , kde je potenční množina množiny
Třídy ekvivalence jsou právě podmnožiny , přičemž každá třída ekvivalence obsahuje právě všechny takové prvky z množiny , ž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 , značíme . Z definice je tedy patrné, že tento prvek je ekvivalentní s každým jiným prvkem náležícím do . Rozklad množiny podle ekvivalence je následující množina:
![{\displaystyle [a]_{R}\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a3aa0d16e70b825d693a1136216562758ad9867)
![{\displaystyle a\in [a]_{R}\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c0b5748fe7ca1e78cc67505a85653df0166f32c)
![{\displaystyle X/R=\{[a]_{R}:a\in X\}\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/67a3b2b3deba9369476db2dbe95642a797a39ff3)
Platí to i naopak – každý rozklad množiny určuje jednoznačně právě jednu relaci ekvivalence:
![{\displaystyle [a,b]\in R\Leftrightarrow (\exists y\in Y)(a\in y\land b\in y)\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d7a741686ec7a7cb51e19dc4a10ce6ca24a2ffd)
Příklad rozkladu Editovat
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 Editovat
Identita jako ekvivalence Editovat
Na každé množině je identická relace 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:
Kartézský součin jako ekvivalence Editovat
Na každé množině je kartézský součin (tj. největší možná binární relace na množině ) ekvivalence. Její rozklad má pouze jeden prvek – celou množinu :
Zbytkové třídy jako ekvivalence Editovat
Uvažujme nyní o množině všech přirozených čísel a relaci :
právě když a,b mají stejný zbytek po dělení číslem 7
![{\displaystyle [a,b]\in R\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/827a42c28ecd85e95e659ebfa62cafe6a12c19c3)
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:
Souvislé komponenty grafu jako ekvivalence Editovat
Uvažme neorientovaný graf . Na množině vrcholů lze definovat relaci jako
existuje cesta z do
Rozklad třídy definuje souvislé komponenty grafu
Odkazy Editovat
Související články Editovat
Externí odkazy Editovat
Obrázky, zvuky či videa k tématu ekvivalence na Wikimedia Commons - Ekvivalence (matematika) v encyklopedii MathWorld (anglicky)
- Relace ekvivalence na webu matweb.cz
