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 | ≡ | |
---|
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
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
Binární relace
na množině
je ekvivalencí, pokud je
na
- reflexivní, tj.
![{\displaystyle \forall a\in X:[a,a]\in R\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3549090540fa21a9149dfbf0e01e1cdd93244817)
- symetrická, tj.
![{\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)
- tranzitivní, tj.
![{\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
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 ![{\displaystyle X\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/98c6c570e3a2c130fc8d968160962b5e0fe4b0e0)
![{\displaystyle \bigcup Y=X\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/42505b69110553047d11c083a611a4d58bda9385)
![{\displaystyle (a,b\in Y\land a\neq b)\implies a\cap b=\emptyset \,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6857ae6fb30eb7a1824a84fbd72cc87b83eca3d2)
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:
Platí to i naopak – každý rozklad
množiny
určuje jednoznačně právě jednu relaci ekvivalence:
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ě
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
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
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
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
Uvažme neorientovaný graf
. Na množině vrcholů
lze definovat relaci
jako
existuje cesta z
do ![{\displaystyle v_{2}\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5b4dbed0faaf5bfc8c6098f1fa33b5b9901c72b)
Rozklad třídy
definuje souvislé komponenty grafu
Odkazy
Související články
Externí odkazy