Relacije i svojstva
D Neka su A i B skupovi.
Relacija izme~du A i B je bilo koji
skup ure~denih parova kojima je prva komponenta u A a druga
u B ~ dakle, bilo koji podskup njihovog Kartezijevog
produkta:
r:A--B :<=> r C= AxB.
Ako je (a,b)@r (gdje su a@A i b@B),
tad ka~zemo: a i b su u relaciji
r, ili a je u relaciji sa
b, i pi~semo arb.
P Zadana su dva skupa, i jedan podskup njihovog Kartezijevog
produkta ~ dakle, jedna relacija izme~du njih.
Cure:={Ana,Branka,Cvijeta} De~cki:={Damir,Emil,Filip}
♥:Cure--De~cki; ♥:={(Ana,Filip),(Branka,Damir)}
Ana♥Filip , !(Cvijeta♥Damir) ,
(A_d@De~cki)(!_c@Cure)(c♥d) ,
(E_c@Cure)!(E_d@Decki)(c♥d)
S Ima puno primjera relacij~a ~ npr. me~du skupovima asistenata
i kolegija na fakultetu, relacija dr~zi_vje~zbe_iz
( Vekydr~zi_vje~zbe_izEM1 ). No bolje za prou~cavanje od
tako op~tenitih su binarne relacije. (Ubudu~te, ako se ne ka~ze
druga~cije, sve relacije bit ~te binarne.)
D Binarna relacija je relacija izme~du skupa i samog
sebe: r:A--A, odnosno
r C= AxA =: A2.
Tad se umjesto "relacija izme~du A i A" ka~ze
jednostavno "relacija na (skupu) A".
P Primjeri (binarnih) relacij~a:
- Na skupu
R, relacija <= ("manje ili
jednako") (P 2<=5)
- Na skupu
Q, relacija < ("strogo manje")
- Na skupu svih pravaca u ravnini, relacija
||
("paralelno") (P p||p)
- Na
P(S) (S univerzalni skup),
relacija C= ("podskup")
- Na skupu
N, relacija | ("dijeli")
(P 3|6)
D Za binarnu relaciju r na
(univerzalnom) skupu A, ka~zemo da je:
- refleksivna ako
((A_a))(ara);
- irefleksivna ako
((A_a))!(ara) (Na to
nije isto ~sto i negacija refleksivnosti, koja je
(E_a)!(ara));
- simetri~cna ako
arb=>bra (R
a i b se podrazumijevaju univerzalno
kvantificirane po A);
- antisimetri~cna ako
arb&bra=>a=b (Na to
uklju~cuje slu~caj kad !(arb&bra));
- tranzitivna ako
arb&brc=>arc (O
tada se arb&brc ~cesto zapisuje
kao arbrc).
P Primjeri relacija s njihovim svojstvima:
- paralelnost pravaca u ravnini ~ refl,sim,tranz (!tranz u
ravnini Loba~cevskog:)
- okomitost pravaca u ravnini ~ irefl,sim
<= na N ~ refl,antisim,tranz
< na R ~ irefl,antisim,tranz
C= na P(S) ~ refl,antisim,tranz
- "disjunktan" na
P(S) ~ sim
(!irefl ~ (0,0))
| na Z ~ refl,tranz
(!antisim ~ (2,-2))
| na N ~ refl,antisim,tranz
- "relativno prost" na
N ~ sim
(!irefl ~ (1,1))
= na S ~ refl,sim,antisim,tranz
A2 na A ~ refl,sim,tranz
0 na S ~ irefl,sim,antisim,tranz
0 na 0 ~ refl,irefl,sim,antisim,tranz
(~:)
D Binarna relacija se zove jo~s nekim posebnim imenima, ako
ispunjava nekoliko gornjih svojstava odjednom:
- parcijalni ure~daj (PU), ako je refleksivna, antisimetri~cna i
tranzitivna;
- irefleksivni parcijalni ure~daj (IPU), ako je irefleksivna i
tranzitivna (Dz Doka~zite da to povla~ci antisimetri~cnost); te
- relacija ekvivalencije (RE), ako je refleksivna, simetri~cna i
tranzitivna.
P Paralelnost u euklidskoj ravnini je RE. < je
IPU. <= i C= su PUovi. No postoji jedna
bitna razlika izme~du ta dva PUa: Dok svaka dva broja
mo~zemo usporediti po veli~cini
((A_x@R)(A_y@R)(x<=y V y<=x)),
to op~tenito ne mo~zemo sa skupovima i relacijom "podskup": npr., niti
je {1} podskup od {2}, niti je
{2} podskup od {1}. Ka~zemo da za relaciju
C= postoje neusporedivi elementi. PU koji
nema neusporedivih elemenata (poput <= gore) zove se jo~s i
totalni ure~daj ili TU.