Relace

Další vlastností relace je, z kolika prvků se skládá. Obecně můžeme mít jakokouliv n-ární relaci. Předchozí příklady byly 2-ární – hezčeji binární – relace, protože tam vstupovaly dva subjekty. Ale můžeme mít klidně 3-ární relaci, kde již vstupují objekty tři. Můžeme například rozšířit předchozí definici relace: „stát – hlavní město tohoto státu – největší řeka v daném hlavním městě”. Této definici by vyhovovala takováto relace: „Česká republika – Praha – Vltava”.

Povšimněte si prosím, že zde záleží na pořadí. V relaci musí být na prvním místě stát, na druhém hlavní město státu a na posledním řeka. Právě proto, že záleží na pořadí, mluví se o prvcích n-ární relace jako o uspořádané n-tici prvků. U binární relace se tudíž jedná u uspořádanou dvojici prvků (jako jsou například souřadnice v rovině). Obvykle se zapisují do špičatých závorek: <Španělsko, Madrid>.

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:

• Maxmilián: dědeček z otcovy strany;
• Josef: otec;
• Drahomíra: matka;
• Sandra: dcera;
• Honzík: syn.

Jako první vyhledáme všechny členy rodiny, kteří odpovídají relaci: „být mužského pohlaví”. Jedná se o 1-ární, neboli unární, relaci. V relaci tudíž vždy bude jen jeden prvek, jeden člen rodiny. Ve vypisování uspořádaných n-tic již pořadí roli nehraje, pořadí je důležité přímo uvnitř uspořádané n-tice. Je to zapříčiněno tím, že relace je vlastně množina. Relace „být mužského pohlaví” tudíž obsahuje tyto prvky (všechny uspořádané n-tice budeme, podle zvyku z množin, zapisovat do kostrbatých závorek): {<Maximilán>, <Josef>, <Honzík>}. To je všechno.

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, Honzík>, <Maxmilián, Josef>}. Otec Josef je otcem syna Honzíka a dědeček Maxmilián je otcem otce Josefa. Je to, doufám, jasné :-).

Zkusíme ještě další relaci: „rodič – potomek”. Tady už toho bude víc. Musíme brát v úvahu, že dědeček Maxmilián je rodičem Josefa, ale už není rodičem Drahomíry. Josef a Drahomíra jsou ale oba rodičem Sandry a Honzíka. Sandra s Honzíkem nejsou rodiči nikoho, protože je jim teprve devatenáct a třináct let. A o Sandře to rodiče ještě neví :-). Ve výsledku budou tyto uspořádané dvojice: {<Maxmilián, Josef>, <Josef, Sandra>, <Josef, Honzík>, <Drahomíra, Sandra>, <Drahomíra, Honzík>}.

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 – Honzík”, bylo by to špatně, protože se jedná o zcela jinou uspořádanou dvojici než „Honzík – Sandra”. Proto je správný výsledek: {<Sandra, Honzík>, <Honzík, 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 – potomek ”. V zadání máme pouze jednoho dědečka a jednoho otce, ale dva potomky. Nestačí napsat pouze variaci se Sandrou nebo s Honzíkem, musíme je tam vypsat oba. Něco jiného by bylo, kdyby na konci místo „potomek” byl uveden „syn”. Správný výsledek je: {<Maxmilián, Josef, Sandra>, <Maxmilián, Josef, Honzík>}.

Relace je množina uspořádaných n-tic. Relace obvykle značíme velkými písmeny stejně jako množiny. Často se značí R a S. Mějme dány dvě libovolné množiny A a B. Relace je poté jakákoliv podmnožina kartézského součinu mezi těmito podmnožinami. Pokud si za obě množiny dosadíme přirozená čísla, můžeme získat takovouto relaci: {<1, 2>, <3, 4>, <74, 42>, <1, 0>}, která je podmnožinou kartézského součinu N×N. Pro n-ární relaci bychom předchozí definici akorát lehce poupravili a místo dvou množin bychom měli n množin a místo uspořádaných dvojic uspořádané n-tice.

Vzhledem k tomu, že relace je množina, můžeme s relacemi provádět klasické množinové operace jako je sjednocení, průnik nebo rozdíl. Relace můžeme také skládat. Jako značka pro skládání relací se používá malé kolečko „o” (protože žádný normální použitelný znak kolečko neexistuje, budu namísto kolečka používat vzhledově podobné písmeno malé „o”. Já vím, prasárna, ale co už.).

Nejprve si nadefinujeme relaci R: ta obsahuje tyto prvky: {<1, 3>, <2, 4>, <3, 5>, <4, 6>, <5, 7>}. Relace S obsahuje tyto prvky: {<8, 3>, <7, 0>, <1, −25>, <5, 30>}. Nyní bychom složení RoS nadefinova­li takto: . Česky by se dalo říct, že pokud skládáte dvě relace, musíte najít takový prvek, který je na druhém místě uspořádané dvojice v první relaci a na prvním místě v uspořadné dvojici druhé relace. Složení relace potom tvoří vždy ty druhé prvky. Tedy musíte najít dvojici <x, y> v R a <y, z> v S (kde tedy y=y) a výsledkem složení pak bude uspořádaná dvojice <x, z>.

Výsledkem našeho předchozího příkladu bude relace: {<5, 0>, <3, 30>}.

Binární relace na jedné množině má několik zásadních vlastností, o kterých je dobré vědět. Máme danou relaci R, která se skládá z uspořadaných dvojic <x, y>, kde x a y bereme z jedné libovolné množiny.

Reflexivní relace

Relace R je reflexivní, když je každý prvek v relaci se sebou samým. Matematicky . Příklad reflexivní relace může rovnost, identita „=”, tedy y=x. Máme-li relaci R, která je podmnožinou kartézského součinu N×N, můžeme říci, že každým prvek a z této množiny je v relaci se sebou samým, s prvkem a, protože a=a.

Jiný příklad může být třeba relace S=N×N, kde x dělí y – x|y. Samozřejmě pod dělitelností je myšleno dělitelné beze zbytku. Takováto relace je reflexivní, protože číslo a bude vždy dělitelné číslem a beze zbytku.

Teď příklad relace, která není reflexivní. To může být relace „větší než” definovaná na stejných množinách jako předchozí relace. Takováhle relace nemůže být reflexivní, protože číslo a nemůže být nikdy větší než číslo a. To je docela nesmysl. Proto tato relace není reflexivní.

Symetrická relace

Relace R je symetrická, když pro všechny dvojice <x, y>, které jsou v relaci R, platí, že také dvojice <y, x> je v relaci R. Zkrátka pokud máte v relaci určitou dvojici, musí být v relaci i dvojice, která vznikne prohozením prvků. 

Příklad symetrické relace může být relace „být sourozenec” z původního příkladu. Jestliže byla Sandra sourozencem Honzíka, musel být zákonitě Honzík sourozencem Sandry.

Dalším příkladem můžeme být relace x+y=10. Jestliže se x+y=10, pak je jisté, že se také y+x=10. Vychází to z komutativního zákonu. Relace je tudíž symetrická, můžeme prohodit prvky uspořádané dvojice a tato nově vzniklá dvojice bude také v relaci.

Jako poslední jeden příklad relace, která není symetrická. Třeba relace R, která je podmnožinou R×R (v tomto zápisu jsou R reálná čísla), kde y=x². Zkusíme si vzít nějakou dvojici, která v této relaci je. Třeba <4, 16>. Zde je jasně vidět, že relace nebude symetrické, protože když to obrátíme – <16, 4> – nebude to již v relaci R (protože 16² docela určitě nejsou 4).

Antisymetrická relace

Relace R je antisymetrická, když jediný případ, kdy můžeme prohodit prvky ve dvojici a nově vzniklá dvojice bude také v relaci R nastane právě tehdy, když ty prvky budou stejné. Matematičtěji: 

Jako příklad antisymetrické relace můžeme uvést relaci „větší nebo rovno”. Jestliže je a větší nebo rovno b a zároveň je b větší nebo rovno a, pak se a=b.

Další příklad je třeba relace R, vzniklá z N×N, kde se y=x+1. V této relaci nejsme dokonce schopni nalézt žádnou dvojici, kterou bychom mohli zaměnit, aby stále náležela relaci. Nemusíme tedy ověřit podmínku, zda jsou prvky v dvojici prohoditelné právě tehdy když jsou stejné – relace je antisymetrická.

Příklad relace, která není antisymetrická je třeba relace „být sourozenec”. Dva lidé mohou být sourozenci, aniž by to byli stejní lidé.

Ještě bych rád upozornil na to, že relace může být symetrická i antisymetrická zároveň. Například již zmíněná identita, ověřte si to ;-).

Transitivní relace

Relace R je transitivní, jestliže x je v relaci s y a zároveň je y v relaci se z, potom i x je v relaci se z. 

Příkladem transitivní relace může být relace „větší než”. Pokud je a větší než b a b je větší než c, potom je jisté, že i a je větší než c.

Další transitivní relace je „rovnoběžnost přímek v rovině”. Jestliže je přímka p rovnoběžná s přímkou q a přímka q je rovnoběžná s přímkou s, potom je přímka p rovnoběžná i s přímkou s.

Příklad relace, která není transitivní je „kolmost přímek v rovině”. Jestliže je přímka p kolmá na přímku q a přímka q je kolmá na přímku s, neznamená to, že přímka p je kolmá na přímku s. Naopak, přímka p je s přímkou s rovnoběžná.

Je-li relace reflexivní, symetrická a transitivní, jedná se o relaci ekvivalence. Je-li relace reflexivní, antisymetrická a transitivní, jedná se o relaci uspořádání.