Příklady na relace a ekvivalence

Nějaké příklady do diskrétní matematiky.

Příklad 1

Nechť X = {(a, b) | a, b je prvkem Z, b nerovno 0 }. Definujeme (a, b)R(c, d) právě když a*d = b*c. Dokažte, že R je ekvivalence na množině X. Jakou známou množinu tvoří třídy ekvivalence?

Řešení:

Dokážeme, že relace
R = { [ (a, b), (c, d) ] | (a, b), (c, d) je prvkem X, B nerovno 0 nerovnod, a*d = b*c }
je reflexivní, symetrická a zároveň transitivní relace.

Pro reflexivní relaci platí
(a, b)R(a, b), tedy [ (a, b), (a, b) ] je prvkem R
a proto a*b = b*a, což platí. R je reflexivní relace.

Má-li být relace R symetrická musí platit, že (je-li) [ (a, b), (c, d) ] je prvkem R ⇒ [ (c, d), (a, b) ] je prvkem R. A opravdu platí a*d = b*c ⇒ c*b = d*a a proto je R symetrická relace.

Zbývá dokázat transitivitu R. Relace R bude transitivní pokud [ (a, b), (c, d) ] je prvkem R a zároveň [ (c, d), (e, f) ] je prvkem R ⇒ [ (a, b), (e, f) ] je prvkem R. Tedy a*d = b*c a zároveň c*f = d*e ⇒ a*f = b*e. Z první rovnice je a = b*c/d, b = a*d/c, z druhé rovnice f = d*e/c, e = c*f/d. Dosazením do třetí rovnice a úpravou získáme b*e = a*f, což je třetí rovnice a je dokázáno, že relace R je transitivní. Nyní už také můžeme s jistotou prohlásit, že R je ekvivalence. Vytvoříme-li alespoň pro pár hodnot relační tabulku, vidíme, že prvky relace můžeme rozdělit do tříd [(1, 2)], [(2,1)], [(3, 1)],...,[(a, b)] kde a nerovno b a jedné velké třídy [(1, 1)] = [(2, 2)],...,[(a, a)]. Zapíšeme-li a*d = b*c jako a/b = c/d, tedy jako zlomky, mohou třídy ekvivalence tvořit třídy shodných zlomků.

 

Příklad 2

Nechť R je reflexivní a transitivní relace na X. Dokažte, že R průnik R-1 je ekvivalence na X.

Řešení:

R = { (x, y) | x, y je prvkem X, reflexivní a transitivní  }. Porom R-1 = { (y, x) | x, y je prvkem X, (x,y) je prvkem R }. Pro R platí že: (x, x) R a že pokud (x, y) je prvkem R a zároveň (y, z) je prvkem R ⇒ (x, z) je prvkem R. Pro R-1 platí, že (x,x) je prvkem R-1 a že pokud (y, x) je prvkem R-1 a zároveň (x, z) je prvkem R-1 ⇒ (y, z) je prvkem R-1.

Definujeme R průnik R-1 = { (x, y) | x, y je prvkem X, (x, y) je prvkem R a zároveň (x, y) je prvkem R-1 }. R průnik R-1 je reflexivní, neboť platí, že (x, x) je prvkem R průnik R-1 Je také transitivní: (x, y) je prvkem R průnik R-1 a zároveň (y, z) je prvkem R průnik R-1 ⇒ (x, z) je prvkem R průnik R-1. Zbývá dokázat symetrie relace. Musí platit, že  (x, y) je prvkem R průnik R-1 ⇒ (y, x) je prvkem R průnik R-1 . A opravdu, protože pro obě relace R a R-1platí, že (y, z) je prvkem R i R-1 a (x, z) je prvkem R i R-1, potom (y, z), (x,z) je prvkem R průnik R-1a proto musí platit i (x, y), (y, x) je prvkem R průnik R-1, protože v opačném by neplatila transitivita obou relací, což by bylo ve sporu se zadáním.

R průnik R-1 je ekvivalence.