✖

Relace ekvivalence

Kapitoly: Relace, Operace s relacemi, Binární relace, Binární relace na množině, Relace ekvivalence, Relace uspořádání, Svazy

Relace ekvivalence je binární relace na množině, která je reflexivní, symetrická a transitivní.

Motivace

Relace ekvivalence představuje jakési zjemnění relace rovnosti. Vždy můžeme rozhodnout, že jsou dva prvky množiny stejné, tj. že a = a. Ale někdy se nám hodí zjistit, zda jsou si dva prvky pouze podobné, ne nutně stejné. Neboli — zda mají stejnou nějakou zásadní vlastnost. Například dvě knihy můžeme považovat za podobné, pokud mají stejný žánr — nebo pomocí ekvivalence: dvě knihy jsou ekvivalentní pokud mají stejný žánr.

Co bychom od takové ekvivalence čekali? Vezměme si jiný příklad. Dvě slova jsou podobná/ekvivalentní, pokud jsou stejně dlouhá.

Asi bychom čekali, že pokud změříme podobnost dvou stejných slov, že nám vyjde, že jsou podobné. Tedy pro všechna slova musí platit, že jsou podobná/ekvivalentní sama se sebou. V řeči relací: relace ekvivalence musí být reflexivní.

Dále pokud je slovo „potok“ podobné/ekvivalentní slovu „Agáta“, pak jistě očekáváme, že i slovo „Agáta“ bude ekvivalentní se slovem „potok“. Jinými slovy nezáleží na pořadí. V řeči relací: relace ekvivalence musí být symetrická.

A nakonec pokud je slovo „smrt“ podobné/ekvivalentní se slovem „pták“ a slovo „pták“ je ekvivalentní se slovem „noha“, pak očekáváme že i dvojice slov „smrt“ a „noha“ budou ekvivalentní. Tedy relace ekvivalence musí být i transitivní.

Nic dalšího od ekvivalence neočekáváme.

Příklady

Další příklady ekvivalencí:

  • Bydlet ve stejném městě. Jirka určitě bydlí ve stejném městě jako Jirka (reflexivita). Pokud Jirka bydlí ve stejném městě jako Ondra, pak i Ondra bydlí ve stejném městě jako Jirka (symetrie). A pokud Ondra bydlí ve stejném městě jako Martin, pak i Jirka bydlí ve stejném městě jako Martin (transitivita).
  • Písně se stejným autorem. Píseň „Zuřivý monolog syna poklopu“ má jistě stejného autora jako píseň „Zuřivý monolog syna poklopu“ (reflexivita). Pokud mají písně „Zuřivý monolog syna poklopu“ a „Válka na zvradlech“ stejného autora, pak i „Válka na zvradlech“ a „Zuřivý monolog syna poklopu“ mají stejného autora (symetrie). A pokud „Válka na zvradlech“ a „Výprava za pravdou špíny“ mají stejného autora, pak i „Zuřivý monolog syna poklopu“ a „Výprava za pravdou špíny“ mají stejného autora (transitivita).
  • [a, b] ∈ R právě když a − b je sudé číslo; a, b jsou celá čísla. Reflexivita: a − a = 0, nula je sudé číslo. Symetrie: označme c = a − b. Pak b − a = −(a − b) = −c. Pokud je c sudé, pak musí být i −c sudé. Transitivita: označme p = a − b, dále q = b − c. Víme, že p i q jsou sudá čísla. Nyní máme dokázat, že a − c je sudé číslo. Do této rovnice za c dosadíme c = b − q: a−(b − q), což se rovná a − b + q. Z předpokladů víme, že a − b je sudé číslo. Pokud k sudému číslu přičteme další sudé číslo q, dostaneme opět sudé číslo.
  • Rovnost. Rovnost je ekvivalence, je to zároveň nejmenší ekvivalence na libovolné množině M.

Triviální ekvivalence

Máme neprázdnou množinu M. Jaká je nejmenší možná ekvivalence R na množině M? Nejmenší možná podmnožina kartézského součinu M × M je prázdná množina ∅. Splňuje prázdná množiny podmínky ekvivalence?

Určitě je symetrická, jelikož relace R nemá žádné prvky, tak podmínka symetrie je automaticky a triviálně splněna. Podobně transitivita. Problém je s reflexivitou. Definice říká, že pro všechny prvky x množiny M platí, že [x, x] ∈ R. Je toto splněno? Množina M je neprázdná, takže obsahuje nějaký prvek, například q. Je dvojice [q, q] v relaci R? Není. Relace R tak není reflexivní.

Jaká je nejmenší relace splňující reflexivitu? Relace rovnosti. Relace R musí obsahovat minimálně dvojice [x, x] pro všechny prvky M. Což je právě relaci identity. Je takováto relace symetrická? Jednoduše je vidět, že ano. Podobně je snadno vidět, že je i transitivní. Nejmenší relace ekvivalence na množině M je tak relace identity, značíme idM, a obsahuje dvojice [x, x] pro všechny x ∈ M.

Jaká je největší možná ekvivalence na množině M? Největší podmnožina je celá množina M × M. Splňuje podmínky ekvivalence? Je asi triviálně vidět, že ano.

Třída ekvivalence

Každá ekvivalence rozdělí množinu M na systém disjunktních množin, které pak nazýváme třídy ekvivalence.

Mějme množinu všech slov M a ekvivalenci R stejně dlouhé slovo. Tedy [a, b] ∈ R právě když slova a a b mají stejnou délku. Tato ekvivalence rozdělí množinu slov do několika menších množin, které budou vždy obsahovat slova stejné délky. Jednotlivé třídy ekvivalence můžeme rozlišit pomocí spodního indexu, který bude zároveň rozlišovat délku slov v dané množině:

  • M1 = {a, i, o, e, …}
  • M2 = {ve, do, se, my, mi, …}
  • M3 = {ale, bez, ten, tam, …}
  • M4 = {smrt, park, lest, niva, …}
  • …

Všimněte si dvou věcí: 1) jednotlivé množiny jsou navzájem disjunktní, nemají žádný společný prvek. 2) všechny prvky v každé jednotlivé množině jsou navzájem ekvivalentní. Všechna slova v množině M3 jsou navzájem ekvivalentní, protože všechna slova mají délku tři, tedy stejnou délku, což je podmínka ekvivalence.

Přitom každý prvek jednoznačně definuje svou třídu ekvivalence. To obvykle zapisujeme pomocí notace M[x], kde x ∈ M. Pokud bychom napsali M[ale], tak tím jednoznačně definujeme třídu ekvivalence, kterou jsme si už označili jako M3.

Jak vlastně najdeme třídu ekvivalence, pokud známe nějaké x ∈ M? Projdeme všechny prvky v M a zjistíme, které z těchto prvků jsou ekvivalentní s prvkem x. To budou všechny prvky, které budou součástí třídy ekvivalence M[x].

Pro M[ale] bychom prošli všechna slova v M a uchovali v M3 taková slova, která mají délku tři.

Definice a vlastnosti třídy ekvivalence

Třídu ekvivalence bychom si mohli zadefinovat takto. Mějme množinu M a na ní definovanou ekvivalenci R. Pak třídou rozkladu, který obsahuje prvek x ∈ M, rozumíme:

$$M[x] = {y \in M; [x, y] \in R}$$

Definice říká, že to jsou všechna y, která jsou ekvivalentní se zadaným prvkem x. Protože relace ekvivalence je reflexivní, tak se tam tímto způsobem dostane i samotný prvek x — protože x je ekvivalentní samo se sebou.

Rozkladem ekvivalence pak rozumíme množinu všech tříd ekvivalence. Takže rozkladem množiny všech slov by byla množina {M1, M2, M3, …}.

Základní vlastnosti tříd ekvivalence:

  • [a, b] ∈ R právě tehdy, když M[a] = M[b]. Pokud máme dva prvky a, b, které jsou ekvivalentní, pak se musí jejich třídy ekvivalence rovnat.
  • Naopak, pokud neplatí [a, b] ∈ M, pak také M[a] ≠ M[b], přesněji M[a] ∩ M[b] = ∅. Pokud máme dva prvky, které nejsou ekvivalentní, pak jsou jejich třídy rozkladu disjunktní.
  • Sjednocení všech tříd ekvivalence musí dát původní množinu M: M1 ∪ M2 ∪ … ∪ Mn = M. (Předchozí zápis je jen pro konečný počet tříd ekvivalence, ale obecně jich může být nekonečně mnoho.)

Příklady rozkladů ekvivalence

První příklad, lichá a sudá čísla:

Mějme jednoduchou ekvivalenci R definovanou na přirozených číslech N. [a, b] ∈ R právě tehdy když a i b je liché nebo a i b je sudé. Příklady prvků: [1, 7], [13, 9], [4, 6], [8, 136]. Určíme nyní rozklad této ekvivalence na třídy ekvivalence.

Začneme postupně. Čemu bude rovna třída N[1]? Musíme najít všechna čísla, která jsou ekvivalentní s číslem jedna. Dle podmínky ekvivalence to jsou všechna lichá čísla, takže N[1] = {1, 3, 5, 7, 9, …}.

Čemu bude rovna třída N[2]? Nalezneme všechna čísla, která jsou ekvivalentní s dvojkou. To jsou všechna sudá čísla: N[2] = {2, 4, 6, 8, 10, …}.

Nyní N[3]. Jaká čísla jsou ekvivalentní s trojkou? Všechna lichá čísla. Tím ale získáme množinu N[1], kterou jsme si spočítali v předminulém odstavci. Podobně pro N[4], tam zase opět množinu sudých čísel.

Vidíme, že dále už by se stále opakovaly tytéž množiny. Je to vidět i z toho, že ať vezmeme jakékoliv další přirozené číslo n, tak už bude platit, že n ∈ N[1] nebo n ∈ N[2]. Jiná přirozená čísla než lichá a sudá nemáme, takže tyto dvě množiny tvoří rozklad ekvivalence.

Je to podobné, jako kdybychom si představili ekvivalenci na množině lidí a i b je muž nebo a i b je žena. Pak bychom jako rozklad dostali množinu žen a množinu mužů.

Druhý příklad, absolutní hodnota:

Mějme ekvivalenci R na množině celých číslech Z definovanou takto: [a, b] ∈ R právě tehdy, když |a| = |b|. (Ty svislé čáry jsou absolutní hodnota.) Opět půjdeme postupně:

  • Z[0] = {0}. Nula je v relaci pouze s nulou.
  • Z[1] = {−1, 1}. Jednička je v relaci s jedničkou a s minus jedničkou, protože |1| = |−1|.
  • Z[2] = {−2, 2}. Dvojka je v relaci s dvojkou a s minus dvojkou.
  • Z[3] = {−3, 3}.
  • …

Asi je jasné, jak to bude pokračovat. Celým rozkladem by tak byla množina tříd:

$${{a, -a}; a \in \mathbb{Z}_0^+}$$

(Tedy všechny dvojice a, −a, kde a je celé nezáporné číslo.) Vidíte, že tříd je nekonečně mnoho.

Hledáme programátory!