Hlavní obsah

Relace ekvivalence

Učebna Google

Ekvivalentní tvrzení

Než budeme pokračovat, je důležité si zapamatovat, že následující tvrzení jsou ekvivalentní.

$A \equiv B (mod C)$ ‍
$A mod C = B mod C$ ‍
$C | (A - B)$ ‍ (Symbol „|“ znamená „dělí“)
$A = B + K \cdot C$ ‍ (kdee $K$ ‍ je nějaké celé číslo)

To nám umožní používání různých výrazů, které znázorňují tu samou myšlenku.

Například následující tvrzení jsou ekvivalentní:

$13 \equiv 23 (mod 5)$ ‍
$13 mod 5 = 23 mod 5$ ‍
$5 | (13 - 23)$ ‍, $(5 | - 10$ ‍, což platí, neboť $5 \cdot (- 2) = - 10)$ ‍
$13 = 23 + K \cdot 5$ ‍. To platí pro $K = - 2$ ‍: $13 = 23 + (- 2) \cdot 5$ ‍

Kongruence modulo je relace ekvivalence

Přesvědči se, že řezy použité v předchozím příkladu mají následující vlastnosti:

Každý pár hodnot v daném řetězu spolu nějak souvisí
Nikdy nenajdeme žádnou hodnotu ve více než jednom řezu (řezy jsou disjunktní).
Zkombinujeme-li všechny řezy dohromady, vytvoří „kruh“ obsahující všechny hodnoty.

Kruh s řezy, které mají tyto vlastnosti, má relaci ekvivalence.
Relace ekvivalence definuje, jak můžeme rozřezat náš kruh (jak rozdělíme množinu hodnot) do řezů (tříd ekvivalence).

Obecně, relace ekvivalence musí mít tyto vlastnosti:

Kruh: Množina všech hodnot, které nás zajímají.
Řez kruhu: Třídy ekvivalence.
Jak rozřežeme kruh do daných řezů: Relace ekvivalence.

Konkrétně pro předchozí příklad:

Kruh: Množina všech celých čísel.
Řez kruhu označený $B$ ‍: Třída ekvivalence, kde jsou všechny hodnoty $mod C = B$ ‍.
Jak rozřežeme kruh do daných řezů: Použití relace kongruence modulo C $\equiv (mod C)$ ‍.

Proto říkáme, že Kongruence modulo C je relace ekvivalence. Rozděluje celá číslo do C různých tříd ekvivalence.

Proč nás zajímá, že kongruence modulo C je relace ekvivalence?

Znalost toho, že kongruence modulo C je relace ekvivalence, nám říká něco o vlasnostech, které musí splňovat.
Relace ekvivalence jsou relace s následujícími vlastnostmi:

Jsou reflexivní: A je ekvivalentní s A.
Jsou symetrické: Nechť je A ekvivalentní s B, pak je B ekvivalentní s A.
Jsou transitivní: Nechť je A ekvivalentní s B a B ekvivalentní s C, pak je A ekvivalentní s C.

Kongruence modulo je relace ekvivalence pro (mod C). To znamená:

$A \equiv A (mod C)$ ‍
Nechť $A \equiv B (mod C)$ ‍, pak $B \equiv A (mod C)$ ‍.
Nechť $A \equiv B (mod C)$ ‍ a $B \equiv D (mod C)$ ‍, pak $A \equiv D (mod C)$ ‍.

Příklad

Aplikujme tyto vlastnosti na konkrétní příklad pro

mod 5 :

$3 \equiv 3 (mod 5)$ ‍ (vlastnost reflexivity)
Nechť $3 \equiv 8 (mod 5)$ ‍, pak $8 \equiv 3 (mod 5)$ ‍ (vlastnost symetrie)
Nechť $3 \equiv 8 (mod 5)$ ‍ a $8 \equiv 18 (mod 5)$ ‍, pak $3 \equiv 18 (mod 5)$ ‍ (vlastnost transitivity)

Chceš se zapojit do diskuze?

Přihlášení

Setřídit podle:

Zatím žádné příspěvky.

Umíš anglicky? Kliknutím zobrazíš diskuzi anglické verze Khan Academy.