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
editovatBiná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
editovatRelace 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
editovatX 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
editovatIdentita jako ekvivalence
editovatNa 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
editovatNa 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
editovatUvaž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
editovatUvažme neorientovaný graf . Na množině vrcholů lze definovat relaci jako
existuje cesta z do
Rozklad třídy definuje souvislé komponenty grafu
Odkazy
editovatSouvisející články
editovatExterní 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
