Relacije

Binarna relacija je skup uređenih parova koji pokazuje koji su elementi dva skupa međusobno povezani.

Neka su $A$ i $B$ skupovi. Binarna relacija $\rho$ između elemenata skupova $A$ i $B$ jeste bilo koji podskup njihovog Dekartovog proizvoda:

$$\rho\subseteq A\times B.$$

Ako uređeni par $(x,y)$ pripada relaciji $\rho$, zapisujemo

$$(x,y)\in\rho$$

ili kraće

$$x\rho y.$$

Oba zapisa čitamo: „$x$ je u relaciji $\rho$ sa $y$”. Ako par ne pripada relaciji, pišemo $(x,y)\notin\rho$ ili $x\mathrel{\not\rho}y$.

Kada je $A=B$, kažemo da je $\rho$ relacija na skupu $A$. Tada važi

$$\rho\subseteq A\times A.$$

Pošto relacija bira neke parove iz Dekartovog proizvoda, redosled elemenata u paru je važan. Iz $(x,y)\in\rho$ ne mora slediti $(y,x)\in\rho$.

Neka je $A=\{a,b,c\}$ i neka je relacija $\rho$ zadata sa

$\rho=\{(a,a),(a,b),(b,b),(c,c)\}.$

Tada važi $a\rho b$, ali ne važi $b\rho a$, jer je $(a,b)\in\rho$, dok $(b,a)\notin\rho$.

Sadržaj

1. Relacije i načini predstavljanja
2. Svojstva relacija
3. Relacije ekvivalencije i poretka

1. Relacije i načini predstavljanja

Relacija zadata uslovom

Relacija se često zadaje uslovom koji povezuje $x$ i $y$:

$$x\rho y\iff P(x,y).$$

To znači da uređeni par $(x,y)$ pripada relaciji tačno onda kada je uslov $P(x,y)$ ispunjen. Na konačnom skupu elemente relacije možemo odrediti proveravanjem svih parova iz $A\times A$.

Postupak je sledeći:

1. napišemo ili sistematski prođemo kroz sve moguće parove $(x,y)$;
2. za svaki par proverimo dati uslov;
3. izdvojimo parove za koje je uslov tačan;
4. proverimo da obe koordinate pripadaju zadatom skupu.

Uslov ponekad možemo rešiti bez proveravanja svih parova.

Tablica relacije

Relaciju na konačnom skupu možemo prikazati tablicom relacije. Elementi skupa stoje u zaglavlju vrsta i kolona. U polje vrste $x$ i kolone $y$ upisujemo $1$ ako je $(x,y)\in\rho$, a $0$ ako je $(x,y)\notin\rho$.

Za relaciju

$$\rho=\{(a,a),(a,b),(b,b),(c,c)\}$$

na skupu $A=\{a,b,c\}$ tablica je

$\rho$	$a$	$b$	$c$
$a$	$1$	$1$	$0$
$b$	$0$	$1$	$0$
$c$	$0$	$0$	$1$

Na primer, jedinica u vrsti $a$ i koloni $b$ znači da je $(a,b)\in\rho$. Nula u vrsti $b$ i koloni $a$ znači da $(b,a)\notin\rho$.

Umesto $1$ i $0$ mogu se koristiti oznake $\top$ i $\bot$. Važno je samo jasno navesti koje oznake predstavljaju pripadanje relaciji.

Graf relacije

Relaciju na konačnom skupu možemo prikazati i usmerenim grafom:

• svaki element skupa predstavlja jedan čvor;
• za svaki par $(x,y)\in\rho$ crtamo strelicu od $x$ ka $y$;
• par $(x,x)$ prikazujemo petljom kod čvora $x$.

Za relaciju

$$\rho=\{(1,0),(2,1),(3,2)\}$$

na skupu $A=\{0,1,2,3\}$ graf izgleda ovako:

Strelice pokazuju smer relacije: $1\to0$, $2\to1$ i $3\to2$.

Kada je element u relaciji sa samim sobom, par $(x,x)$ prikazujemo petljom koja izlazi iz čvora $x$ i vraća se u isti čvor:

Ista relacija može se zapisati skupom parova, tablicom ili grafom. Sva tri prikaza sadrže iste podatke:

Skup uređenih parova	Tablica	Graf
$(x,y)\in\rho$	U vrsti $x$ i koloni $y$ stoji $1$	Postoji strelica $x\to y$
$(x,y)\notin\rho$	U vrsti $x$ i koloni $y$ stoji $0$	Ne postoji strelica $x\to y$
$(x,x)\in\rho$	Na mestu $(x,x)$ stoji $1$	Čvor $x$ ima petlju

2. Svojstva relacija

Svojstva relacije možemo proveravati neposredno iz uslova kojim je zadata, iz skupa uređenih parova, iz tablice ili iz grafa. Za dokazivanje svojstva koristimo proizvoljne elemente skupa. Kada svojstvo ne važi, dovoljno je pronaći jedan kontraprimer.

Refleksivnost

Relacija $\rho$ na skupu $A$ je refleksivna ako je svaki element u relaciji sa samim sobom:

$$(\forall x\in A)\;x\rho x.$$

Isti uslov možemo zapisati kao

$$(\forall x\in A)\;(x,x)\in\rho.$$

Refleksivnost prepoznajemo ovako:

Prikaz relacije	Uslov refleksivnosti
Skup parova	Sadrži $(x,x)$ za svaki $x\in A$
Tablica	Na celoj glavnoj dijagonali stoje jedinice
Graf	Svaki čvor ima petlju

Da bismo dokazali refleksivnost relacije zadate uslovom, u uslov stavljamo $y=x$ i pokazujemo da je dobijeno tvrđenje tačno za svaki $x\in A$.

Da bismo pokazali da relacija nije refleksivna, dovoljno je pronaći jedan element $x\in A$ za koji $(x,x)\notin\rho$.

Simetričnost

Relacija $\rho$ na skupu $A$ je simetrična ako iz $x\rho y$ sledi $y\rho x$:

$$(\forall x,y\in A)\;(x\rho y\Rightarrow y\rho x).$$

Simetričnost prepoznajemo ovako:

Prikaz relacije	Uslov simetričnosti
Skup parova	Uz svaki $(x,y)$ sadrži i $(y,x)$
Tablica	Simetrična je u odnosu na glavnu dijagonalu
Graf	Uz svaku strelicu $x\to y$ postoji i $y\to x$

Za dokaz da relacija nije simetrična tražimo par $(x,y)\in\rho$ čiji obrnuti par $(y,x)$ ne pripada relaciji.

Antisimetričnost

Relacija $\rho$ na skupu $A$ je antisimetrična ako dva različita elementa ne mogu istovremeno biti u relaciji u oba smera:

$$(\forall x,y\in A)\;(x\rho y\land y\rho x\Rightarrow x=y).$$

Ekvivalentno, ako su $x\ne y$ i $(x,y)\in\rho$, onda $(y,x)\notin\rho$.

Prikaz relacije	Uslov antisimetričnosti
Skup parova	Za $x\ne y$ ne sadrži istovremeno $(x,y)$ i $(y,x)$
Tablica	Van glavne dijagonale nema dve jedinice simetrične u odnosu na dijagonalu
Graf	Između različitih čvorova nema strelica u oba smera

Petlje ne narušavaju antisimetričnost, jer je kod para $(x,x)$ već ispunjeno $x=y$.

Ako u relaciji uopšte nema parova različitih elemenata u oba smera, relacija je antisimetrična. Nije potrebno da postoje elementi koji zadovoljavaju obe pretpostavke implikacije.

Tranzitivnost

Relacija $\rho$ na skupu $A$ je tranzitivna ako iz $x\rho y$ i $y\rho z$ sledi $x\rho z$:

$$(\forall x,y,z\in A)\;(x\rho y\land y\rho z\Rightarrow x\rho z).$$

Tranzitivnost prepoznajemo ovako:

Prikaz relacije	Uslov tranzitivnosti
Skup parova	Iz $(x,y)$ i $(y,z)$ sledi da postoji $(x,z)$
Tablica	Ako su polja $(x,y)$ i $(y,z)$ jednaka $1$, onda je i polje $(x,z)$ jednako $1$
Graf	Uz put $x\to y\to z$ mora postojati strelica $x\to z$

Ako ne postoje parovi $(x,y)$ i $(y,z)$ koji mogu da se nadovežu, uslov tranzitivnosti je ispunjen.

Zajednička analiza svih svojstava

Kada treba ispitati više svojstava, najpre odredimo parove relacije ili napravimo tablicu. Zatim svako svojstvo proveravamo odvojeno.

Za rešavanje zadataka korisna je sledeća kontrolna lista:

Svojstvo	Kako ga dokazujemo	Kako ga obaramo
Refleksivnost	Dokažemo $x\rho x$ za svaki $x$	Nađemo $x$ za koji $x\mathrel{\not\rho}x$
Simetričnost	Iz $x\rho y$ izvedemo $y\rho x$	Nađemo $x\rho y$, ali ne i $y\rho x$
Antisimetričnost	Iz $x\rho y$ i $y\rho x$ izvedemo $x=y$	Nađemo različite $x,y$ sa vezama u oba smera
Tranzitivnost	Iz $x\rho y$ i $y\rho z$ izvedemo $x\rho z$	Nađemo $x\rho y$ i $y\rho z$, ali ne i $x\rho z$

3. Relacije ekvivalencije i poretka

Relacije ekvivalencije i relacije poretka određujemo pomoću prethodna četiri svojstva. Obe moraju biti refleksivne i tranzitivne. Razlikuju se po tome što relacija ekvivalencije mora biti simetrična, a relacija poretka antisimetrična.

Relacija $\rho$ na skupu $A$ je relacija ekvivalencije ako je:

1. refleksivna;
2. simetrična;
3. tranzitivna.

Relacija $\rho$ na skupu $A$ je relacija poretka ako je:

1. refleksivna;
2. antisimetrična;
3. tranzitivna.

Skup zajedno sa relacijom poretka naziva se uređen skup.

Jedna relacija može biti i relacija ekvivalencije i relacija poretka. Primer je jednakost:

$$x\rho y\iff x=y.$$

Jednakost je refleksivna, simetrična, antisimetrična i tranzitivna.

Poznati primeri relacija poretka su i $\leq$ na skupovima brojeva i $\subseteq$ na familiji skupova. Relacije $<$ i $\subsetneq$ nisu refleksivne, pa prema navedenoj definiciji nisu relacije poretka.

Klase ekvivalencije

Relacija ekvivalencije deli skup na grupe međusobno ekvivalentnih elemenata. Klasa ekvivalencije elementa $a\in A$ jeste skup svih elemenata koji su u relaciji sa $a$:

$$[a]=\{x\in A\mid x\rho a\}.$$

Za klase ekvivalencije važi:

• svaki element pripada svojoj klasi jer je relacija refleksivna;
• ako je $a\rho b$, onda je $[a]=[b]$;
• ako $a$ i $b$ nisu u relaciji, klase $[a]$ i $[b]$ su disjunktne;
• unija svih različitih klasa jednaka je celom skupu $A$.

Zato klase ekvivalencije čine particiju skupa $A$. Skup svih različitih klasa naziva se količnički skup i označava se sa

$$A/\rho.$$

Kongruencija i klase ostataka

Važan primer relacije ekvivalencije dobijamo pomoću deljivosti. Za ceo broj $n>1$ definišemo

$$x\equiv y\pmod n \iff n\mid(x-y).$$

Ovaj zapis čitamo: „$x$ je kongruentno sa $y$ po modulu $n$”. To znači da $x$ i $y$ daju isti ostatak pri deljenju sa $n$.

Kongruencija je relacija ekvivalencije:

• $n\mid(x-x)$, pa je refleksivna;
• ako $n\mid(x-y)$, onda $n\mid(y-x)$, pa je simetrična;
• ako $n\mid(x-y)$ i $n\mid(y-z)$, onda $n\mid(x-z)$, pa je tranzitivna.

Relacija ekvivalencije i relacija poretka imaju različite uloge. Ekvivalencija razvrstava elemente u disjunktne klase, dok poredak opisuje kako se elementi mogu upoređivati. Zato klase ekvivalencije pripadaju samo delu o relacijama ekvivalencije i ne određuju se za relaciju poretka.