Ekvivalence (matematika)

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

Binární relace na množině je ekvivalencí, pokud je na

  • reflexivní, tj.
  • symetrická, tj.
  • tranzitivní, tj.

Rozklad a třídy ekvivalence[editovat | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]

Identita jako ekvivalence[editovat | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]

Uvažme neorientovaný graf . Na množině vrcholů lze definovat relaci jako
existuje cesta z do

Rozklad třídy definuje souvislé komponenty grafu

Odkazy[editovat | editovat zdroj]

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]