Relace

Relace je takový matematický protějšek normálního pojmu „vztah“. V normálním životě je třeba Monika ve vztahu s Jitkou, konkrétně je to vztah „matka — dcera“. Další takový vztah může být „stát — hlavní město tohoto státu“. Jako příklad můžeme vzít Egypt — Káhira.

Další příklady relací

Vezměme si na pomoc další příklady. V úvodu jsme zmínili relace (vztahy) „být matkou své dceři“ a „být hlavním městem státu“. Podívejme se na další: „být sudým číslem“. V této relaci jsou čísla 2, 4, 8, 18, 58, 66 a mnoho dalších. Čísla 1, 3, −7, 19 nejsou v relaci „být sudým číslem“. Relace z běžného světa může být „být mužem“. Adam, Miroslav, Lukáš nebo Martin jsou v relaci „být mužem“.

Dalším příkladem může být relace „menší než“. Například číslo tři je „menší než“ číslo pět. Matematicky to můžeme zapsat jako 3<5. Nebo relace rovnosti: číslo tři "je rovno" číslu tři, matematicky: 3 = 3.

Můžeme mít i komplikovanější příklady: "otec a matka jsou rodiči dítěte". V této relaci bude trojice lidí: otec Daniel, matka Marie a dítě Krasomila. V matematice bychom mohli vymyslet relaci s třemi prvky takto: součet prvních dvou čísel se rovná třetímu číslu. Například tato čísla, v tomto pořadí, jsou v této relaci: 3, 4, 7, protože 3 + 4 = 7. Tato čísla v relaci nejsou: 3, 5, 12, protože 3 + 5≠12.

Arita relace

Arita je podivně znějící termín, který ale pouze vystihuje, kolik prvků v relaci máme. V předchozích příkladech jsme pracovali s různým počtem prvků. U relace "být mužem" jsme si vystačili s jedním prvkem, můžeme tak říci: "Honza je muž". Stačí nám jedno jméno, jeden prvek. O takové relaci říkáme, že je unární.

V dalším příkladě jsme měli relaci "menší než". Ta pracovala s dvěma čísly, s dvěma prvky. Řekli jsme, že číslo tři je menší než pět. Použili jsme dva prvky, relace je tak binární.

V posledním příkladě jsme používali celkem tři prvky: součet dvou čísel se měl rovnat třetímu. Měli jsme tak čísla a, b, c a muselo platit, že a + b = c. Tato relace by byla ternární.

Pro vyšší arity můžeme použít zápis n-ární relace. Ale můžeme jej použít i pro nižší arity, můžeme binární relaci zapsat jako 2-ární relaci. Prvky relace pak zapisujeme ve formě uspořádaných n-tic. Pokud máme binární relaci, zapisujeme je jako dvojice, obyčejně buď pomocí hranatých závorek nebo pomocí špičatých závorek. Takže pokud chceme zapsat, že čísla tři a pět jsou v relaci "menší než", musíme čísla zapsat jako dvojici: [3, 5], případně <3, 5>. Pozor na to, že musíme dbát na pořadí, opačně by to neplatilo: [3, 5] ≠ [5, 3] — pětka není menší než trojka.

Rodinný příklad

Než se pustíme do matematických definic, zkusíme si ještě jeden typický příklad s rodinou. Mějme tyto členy jedné rodiny:

• Max: dědeček z otcovy strany;
• Josef: otec;
• Drahoslava: matka;
• Sandra: dcera;
• Honza: syn.

Jako první vyhledáme všechny členy rodiny, kteří odpovídají relaci: „být muž“. Jedná se o 1-ární, neboli unární, relaci. V relaci tudíž vždy bude jen jeden prvek, jeden člen rodiny. V tuto chvíli musíme vypsat všechny členy rodiny, kteří jsou mužského pohlaví. Nyní na pořadí nezáleží. Relace „být muž“ tudíž obsahuje tyto prvky: {[Max], [Josef], [Honza]}. Všimněte si, že i když se jedná o unární relaci, použili jsme hranaté závorky. Není to nijak nutné, i bez nich by byl zápis čitelný, ale v rámci konzistence jsem tam závorky ponechal. Soubor všech prvků relace je pak obyčejná množina, proto ty kostrbaté závorky.

Teď si vyhledáme všechny relace „otec — syn“. To je již od pohledu binární relace, ve výsledku se budou vyskytovat uspořádané dvojice prvků. Výsledná množina vypadá takhle: {[Josef, Honza], [Max, Josef]}. Otec Josef je otcem syna Honzy a dědeček Max je otcem otce Josefa. Všimněte si, že opravdu záleží na pořadí, Josef je tam dvakrát, ale jednou na prvním místě na pozici otce a podruhé na druhé pozici na pozici syna.

Zkusíme ještě další relaci: „rodič — dítě“. Tady už toho bude víc, protože na prvním místě může být libovolný z rodičů, jak otec, tak matka a na druhém místě může být libovolné dítě, jak syn, tak dcera. Musíme také brát v úvahu, že dědeček Maxmilián je rodičem Josefa, ale už není rodičem Drahoslavy. Josef a Drahoslava jsou ale oba rodičem Sandry a Honzy. Sandra s Honzou nejsou rodiči nikoho, protože je jim teprve devatenáct a třináct let. Ve výsledku budou tyto uspořádané dvojice: {[Max, Josef], [Josef, Sandra], [Josef, Honza], [Drahoslava, Sandra], [Drahoslava, Honza]}. Všimněte si, že Josef i Drahoslava tam jsou dvakrát — jednou jako rodiče dcery Sandry a podruhé jako rodiče Honzy.

Poslední špek na binární relace. Mějme tuto relaci: „sourozenec — sourozenec“. Zde si musíme uvědomit, že u relací záleží na pořadí, takže kdybychom ve výsledku této relaci napsali pouze „Sandra — Honza“, bylo by to špatně, protože se jedná o zcela jinou uspořádanou dvojici než „Honza — Sandra“. Proto je správný výsledek: {[Sandra, Honza], [Honza, Sandra]}.

A ještě kratičká příklad na ternární relaci: Napište všechny uspořádané trojice této relace: „dědeček — otec — dítě“. V zadání máme pouze jednoho dědečka a jednoho otce, ale dva potomky. Nestačí napsat pouze variaci se Sandrou nebo s Honzou, musíme je tam vypsat oba. Něco jiného by bylo, kdyby na konci místo „dítě“ byl uveden „syn“. Správný výsledek je: {[Max, Josef, Sandra], [Max, Josef, Honza]}.

Definice unární relace

Zkusíme prozkoumat nejjednodušší relace, unární. Pod unární relací rozumíme nějakou množinu prvků. Množina {2, 3} může představovat nějakou relaci. Například relaci „být prvočíslem menším než pět“ nebo „být netriviálním dělitelem čísla šest“, záleží na naší interpretaci.

Bystřejší čtenáři si všimli, že druhá relace je zadefinovaná trochu podivně. Říká, že by relace měla obsahovat netriviální dělitele čísla šest a ve výsledné množině máme čísla 2 a 3. Nechybí nám tam nějaká? Čísla 1 a 6 jsou triviální dělitelé, ta nás nezajímají. Ale měla by tam být i záporná čísla, tedy −2 a −3. Množina všech netriviálních dělitelů čísla 6 vypadá takto: {−3, −2, 2, 3}.

Podobně, jako u funkcí specifikujeme definiční obor, tak u relace specifikujeme nosnou množinu — množinu, ze které vybíráme prvky relace. V předchozích příkladech jsme například specifikovali rodinu, kde byl děda Max apod. Nevybírali jsme otce a děti ze všech rodin na světě. Pokud za nosnou množinu specifikujeme množinu přirozených čísel, pak bude naše relace v pořádku.

V tuto chvíli už se můžeme pustit do definice relace. Pokud máme nosnou množina přirozená čísla, jaké prvky může obsahovat naše unární relace? Zase jen přirozená čísla. Buď všechna nebo jen nějakou podčást. Můžeme tak říci, že daná relace bude podmnožinou množiny přirozených čísel. Obecněji, pokud máme unární relaci R a nosnou množinu M, pak platí, že R ⊆ M, relace R je podmnožinou množiny M.

Definice binární relace

Jak to bude vypadat pro binární relaci? U binární relace jsou prvky relace R uspořádané dvojice. Každý prvek dvojice může být z jiné množiny. Můžeme mít relaci „rodič — počet dětí“. Rodič se bude vybírat z množiny lidí, třeba v Evropě, a počet dětí se bude vybírat z množiny přirozených čísel plus nula.

Jakým způsobem dostaneme ze dvou množin množinu všech možných dvojic? Pomocí kartézského součinu. Máme-li množiny A = {a, b, c}, B = {1, 2}, pak kartézským součinem získáme:

$$A\times B=\left\{[a, 1], [a, 2], [b, 1], [b, 2], [c, 1], [c, 2]\right\}$$

To je množina všech možných dvojic, které můžeme získat tak, že na prvním místě bude prvek z množiny A a na druhém místě prvek z množiny B. Tedy máme-li binární relaci R mezi množinami A a B, pak tuto relaci můžeme definovat jako R ⊆ A × B.

Pokud bychom si ponechali předchozí množiny A a B a zadefinovali si relaci R mezi těmito množinami takto: „písmeno — pořadí písmene v abecedě“, pak tato relace bude vypadat: R = {[a, 1], [b, 2]}. Písmeno c už tam nebude, protože v kartézském součinu A × B se nevyskytuje dvojice [c, 3].

Definice n-ární relace

Na konec zadefinujeme obecnou n-ární relaci R mezi množinami M₁, M₂, …, M_n:

$$R\subseteq M_1\times M_2\times\ldots\times M_n$$

Relace je tak podmnožina uspořádaných n-tic. Příkladem binární relace může být relace „menší než“, neboli <. Tu můžeme definovat mezi nějakými číselnými obory, například mezi přirozenými čísly. Pak to bude relace vypadat takto:

$$< \subseteq \mathbb{N}\times\mathbb{N}$$

(Nelekněte se toho, že je značka < tak podivně na levé straně. Je to jen název relace. Mohlo by tam opět být R, kde by R reprezentovalo relaci menší než.)

Konkrétně by ta relace vypadala takto:

$$\begin{eqnarray} <\quad=&&[1, 2], [1, 3], [1, 4], [1, 5], \ldots\\ &&[2, 3], [2, 4], [2, 5], [2, 6], \ldots\\ &&[3, 4], [3, 5], [3, 6], [3, 7], \ldots\\ &&[4, 5], [4, 6], [4, 7], [4, 8], \ldots\\ &&\ldots\\ && \end{eqnarray}$$

Je to množina uspořádaných dvojic takových, že přirozené číslo na prvním místě je menší než přirozené číslo na druhém místě.

Zápis relací

Relace obvykle pojmenováváme velkými písmeny R, S apod. nebo pomocí zažitých symbolů: <, ⊆, = apod. Z předchozích definic je vidět, že relace je ve skutečnosti množina. Ostatně skoro vše v matematice je vlastně množina :-). Proto, pokud chceme říci, že prvek r patří do relace R, můžeme zapsat jako r ∈ R.

Například můžeme zapsat [1, 3] ∈ < a znamená to, že dvojice čísel jedna a tři patří do relace menší než. U binárních relací se často setkáváme s příjemnějším zápisem, který znáte už ze základní školy. Místo toho, abychom používali operátor býti prvkem ∈, jednoduše napíšeme 1 < 3. Podobně obyčejně nepíšeme [5, 5] ∈ = , ale napíšeme 5 = 5.