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

Zdroj