Relace ekvivalence
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 ~Rb" 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.
- symetrická, tj.
- tranzitivní, tj.
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
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
Rozklad třídy definuje souvislé komponenty grafu
Odkazy
Související články
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