Zhrnutie na Binárne relácie a ich vlastnosti

## Úvod Binárne relácie sú základným pojmom v matematike, ktorý opisuje väzby medzi pármi prvkov množiny. Tento materiál vysvetlí pojmy reflexívnosť, symetrickosť a tranzitívnosť, ukáže praktické príklady a pomôže vám pochopiť, ako relácie fungujú pri triedení a usporiadaní prvkov. ### Čo je binárna relácia? > Binárna relácia R na množine $A$ je podmnožina kartézskeho súčinu $A \times A$, teda množina usporiadaných dvojíc $[x,y]$ s $x,y \in A$. ## Základné vlastnosti relácií Rozoberieme tri základné vlastnosti, ktoré často skúmame pri binárnych reláciách. ### Reflexívnosť > Hovoríme, že relácia $R$ na množine $A$ je **reflexívna**, ak pre každý prvok $x \in A$ platí, že usporiadaná dvojica $[x,x] \in R$. - Symbolický zápis: $\forall x \in A\;\;[x,x] \in R$. - Príklad: Vzťah "rovnaký vek" medzi ľuďmi je reflexívny, lebo každý má rovnaký vek ako sám seba. ### Symetrickosť > Hovoríme, že relácia $R$ na množine $A$ je **symetrická**, ak pre každé $x,y \in A$ platí: ak $[x,y] \in R$, potom aj $[y,x] \in R$. - Symbolický zápis: $\forall x,y \in A\;\;[x,y] \in R \Rightarrow [y,x] \in R$. - Príklad: "Byť súrodencom" je symetrický vzťah: ak $x$ je súrodenec $y$, potom $y$ je súrodenec $x$. ### Tranzitívnosť > Hovoríme, že relácia $R$ na množine $A$ je **tranzitívna**, ak pre všetky $x,y,z \in A$ platí: ak $[x,y] \in R$ a $[y,z] \in R$, potom $[x,z] \in R$. - Symbolický zápis: $\forall x,y,z \in A\;\;([x,y] \in R \wedge [y,z] \in R) \Rightarrow [x,z] \in R$. - Príklad: Relácia "byť starším ako" je tranzitívna: ak $x$ je starší ako $y$ a $y$ je starší ako $z$, potom $x$ je starší ako $z$. ## Porovnanie vlastností (tabuľka) | Vlastnosť | Podmienka | Príklad | | --- | --- | --- | | Reflexívnosť | $\forall x \in A\;\;[x,x] \in R$ | "rovnaký vek" | | Symetrickosť | $\forall x,y \in A\;\;[x,y] \in R \Rightarrow [y,x] \in R$ | "byť súrodencom" | | Tranzitívnosť | $\forall x,y,z \in A\;\;([x,y] \in R \wedge [y,z] \in R) \Rightarrow [x,z] \in R$ | "byť starším ako" | ## Usporiadanie (porovnávanie viac ako dvoch prvkov) Usporiadanie znamená zoradiť aspoň tri prvky podľa určitého rozmeru alebo vlastnosti. - Usporiadať objekty môžeme podľa tých istých vlastností, na základe ktorých ich porovnávame. - V kontexte binárnych relácií nie vždy dokážeme vytvoriť úplné usporiadanie všetkých predmetov, ak relácia nemá potrebné vlastnosti. > Poznámka: Pre úplné usporiadanie často vyžadujeme reláciu, ktorá je reflexívna, antisymetrická a tranzitívna (tzv. čiastočné alebo úplné usporiadanie). Antisymetričnosť tu nie je rozobratá detailne, pretože je súčasťou iného materiálu. ### Výsledky usporiadania - Pri vhodnom porovnaní viac ako dvoch objektov môžeme dospieť k usporiadaniu predmetov. Takéto usporiadanie môže byť buď čiastočné (nie všetky prvky sú porovnateľné) alebo úplné (každé dve prvky sú porovnateľné). ## Usporiadanie prvkov v skupine – čo má vedieť dieťa | Štandard | Cieľ | Aktivita | | --- | --- | --- | | Základné | Určiť predmet podľa vlastnosti | Porovnať a zoradiť 3 predmety podľa veľkosti alebo dĺžky | - Aktivita: Daj deťom 5 predmetov a požiadaj ich, aby ich zoradili podľa veľkosti. Potom skontrolujte, či poradie vytvára tranzitívny vzťah "väčší než". ## Praktické príklady a aplikácie - Triedenie kníh podľa výšky (relácia "vyšší alebo rovnaký ako") - Priraďovanie priateľstiev v komunitách (symetrická relácia) - Predkovia a následníci v rodokmeni (tranzitívne vzťahy pri predkovi) Fun fact: Binárne relácie sa používajú nielen v matematike, ale aj v počítačových vedách pri modelovaní sietí, databázových vzťahov a pri návrhu grafov. ## Krátke cvičenia (s riešeniami) 1) Nech $A = \{1,2,3\}$ a nech $R = \{[1,1],[2,2],[3,3],[1,2],[2,1]\}$. Je $R$ reflexívna? Je symetrická? Je tranzitívna? - Reflexívna: áno, pretože všetky $[x,x]$ pre $x\in A$ sú v $R$. - Symetrická: áno, pretože pre $[1,2]$ je aj $[2,1]$ a ostatné páry sú symetrické (diagonála je vždy symetrická sama so sebou). - Tranzitívna: nie nutne; skontrolujte kombinácie: máme $