Příklady o relacích Zkoušejte hledat řešení (důkazy) pro následující příklady. Mnoho zdaru! Příklad 2.1. Na množině všech přirozených čísel od 0 do 1000 definujeme binární relaci R následovně: (a, b) R právě když platí a) -1 a2 - b2 4, b) 0 a - b 1 nebo číslo a je trojnásobkem čísla b, c) 0 a - b 1 nebo číslo a je polovinou čísla b. Odpovězte, jaké vlastnosti relace R má: je reflexivní, symetrická, antisymetrická, tranzitivní? Pokud některou z těchto vlastností relace R nemá, napište konkrétními čísly protipříklad. Řešení. a) Není těžké zjistit, že v relaci jsou všechny dvojice (x, x), tedy je to reflexivní relace. Dále zjistíme, že mimo reflexivních dvojic jsou v relaci R už jen dvojice (0, 1), (1, 0), (2, 0), (2, 1). Hrubou silou (probráním těchto pár dvojic) pak ověříme, že relace je i tranzitivní. Pro protipříklad, že R není symetrická, máme (2, 0) R, ale (0, 2) R. Jelikož dále (0, 1), (1, 0) R, ale 0 = 1, není R ani antisymetrická. b) Tato relace je opět reflexivní. Jinak (9, 3), (3, 1) R, ale (9, 1) R ani (1, 3) R, takže R není tranzitivní ani není symetrická. Po chvilce zkoumání také přijdeme na to, že z (a, b) R vyplývá a b, takže R je antisymetrická. c) Tato relace je opět reflexivní. Žádnou z dalších jmenovaných vlastností nemá, jak zjistíme z toho, že (1, 2), (2, 1) R, ale 1 = 2, dále (3, 2) R, ale (2, 3), (3, 1) R. 2 Příklad 2.2. Mějme relaci soudělnosti nad přirozenými čísly, kde dvě čísla x, y jsou v relaci pokud mají společného dělitele většího než 1. Které z vlastností z Definice tato relace má? Řešení. Reflexivní a symetrická, ale není tranzitivní. 2 Příklad 2.3. Nakreslete si částečné uspořádání dělitelností čísel 1, . . . , 12 Hasseovým diagramem. a) Jaký je v něm nejdelší řetězec? b) Je v něm nejmenší či největší prvek? c) Kolik je tam maximálních prvků? 1 Řešení. 1 3 64 2 12 8 75 10 119 dělitelnost: a) délky 4 b) nejmenší 1, největší není c) 6 2 Příklad 2.4. Na systémy všech 5-prvkových podmnožin množiny {1, 2, . . . , 12} definujeme ekvivalenci následovně: Dvě množiny jsou ekvivalentní, pokud mají stejné nejmenší číslo. Kolik tříd ekvivalence v příslušném rozkladu získáme? Jak velká je největší třída? Řešení. 8 tříd (s minimy 1, ..., 8), nejvíce je s minimem 1 ­ celkem 11 4 . 2 Příklad 2.5. Na množině všech slov-řetězců nad běžnou abecedou definujme relaci následovně: Slovo x je v relaci se slovem y pokud je y obsaženo jako podřetězec v x. O jaký známý typ relace se jedná? Zdůvodněte. Řešení. Reflexivní, antisymetrická, tranzitivní, tedy částečné uspořádání. Lineární není, protože dvě slova nemusí být porovnatelná. 2 Příklad 2.6. Na množině všech slov-řetězců nad běžnou abecedou definujme relaci následovně: Slovo x je v relaci se slovem y pokud lze x získat z y jen přeházením písmen. O jaký známý typ relace se jedná? Zdůvodněte. Řešení. Reflexivní, symetrická, tranzitivní, tedy ekvivalence. 2 Příklad 2.7. Mezi všemi studenty na přednášce UInf definujeme následující binární relaci: Každý student je v relaci sám se sebou, tj. je to reflexivní relace. Každý student A je v relaci s jiným studentem B, právě když B sedí a) ve stejné řadě nalevo od A, b) ve stejné řadě jako A nebo v řadě hned za A, c) v poslední řadě (nezáleží, kde sedí A), d) v některé řadě před A. Jaké vlastnosti má tato relace (jako symetrická, antisymetrická, tranzitivní)? Jedná se třeba o částečné uspořádání nebo o ekvivalenci? Vaši odpověď dobře zdůvodněte. 2 Řešení. a) je to částečné uspořádání, b) není symetrická, antisymetrická ani tranzitivní, c) je tranzitivní, ale ne symetrická ani antisymetrická, d) je to částečné uspořádání. 2 3