Ekvivalence (matematika)

taková binární relace, která je reflexivní, symetrická a tranzitivní
(přesměrováno z Třída ekvivalence)

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 toNot identical to
Kódovánídechexdechex
Unicode8801U+22618802U+2262
UTF-8226 137 161e2 89 a1226 137 162e2 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.  

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:
 

Platí to i naopak – každý rozklad   množiny   určuje jednoznačně právě jednu relaci ekvivalence:  

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

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

Související články

editovat

Externí odkazy

editovat