Detaljno o relacijama

> Evo mene opet sa jednim pitanjem.

Nema problema. BTW, formalno pitanje: smijem li ove mailove
(Vase s pitanjima i moje s pokusajima odgovora), preciznije njihove
dijelove koji su relevantni za gradivo, objaviti na webu?

> Jednostavno ne znam kako bi rije1io jedan zadatak,
> toenije, ne znam kako da uopae poenem. Dakle,
> rijee je o relacijama sa pro1lih vje3bi. Zadali ste nam ovakav
zadatak:
>
> bio je zadan skup S = { 1, 2, 3 } od tri elana te relacija
> p : S --- S = {(1,1), (1,3), (2,3), (2,2), (3,3)}

Sitna ispravka. :-- ima manji prioritet nego = s lijeve strane. Ispada
da je S={(1,1),...} . Radije pisite p:S--S; p:={...} ,
ili (bizarnije) (p:={...}):S--S ...

> i trebalo je provjeriti kakve su relacije ( refleksivna,
simetriena,...)

Sitna ispravka: "kakva je relacij_a_" (jednina). Naime, zadana je samo
jedna relacija: p . Treba provjeriti njena _svojstva_ (je li
refleksivna, simetricna, itd...)

> Dakle uopae ne razumijem 1to je ovdje relacija
> ( mo3da sam ne1to propustio kod prepisivanja ali ne vjerujem ).

Vjerojatno jeste, jer mislim da sam egzaktno definirao:

        * relacija r:A--B je podskup Kartezijevog produkta AxB .
        * Kazemo da su dva elementa, a@A i b@B , u relaciji r
        (i pisemo arb ), akko vrijedi (a,b)@r

No nista strasno, kao sto vidite mogu ja i ponoviti. :-)

Primjer je bio (garant ga se sjecate;) onaj sa relacijom
\srce:Cure--Decki , zadanom upravo popisivanjem svih parova koji su u
relaciji... (pa je onda izjava "Ana\srce Filip" upravo znacila
(Ana,Filip)@\srce ).

> Na vje3bama smo inaee imali zadane relacije tipa: <, >,

Jesmo i takve. Sto se tice teorije skupova, svaka od tih relacija isto
je prikaziva u gornjem obliku. Npr.
'<':|N--|N;'<'={(1,2),(1,3),(2,3),(1,4),(2,4),(3,4),(1,5),....}
(jasno ovo?)

> mod i sl. dakle neku operaciju,

mod definitivno jest (sortof) operacija, ali (samim tim) _nije_
relacija.
Relacija je nesto za sto mozemo reci: dva elementa su (ili nisu) u
relaciji.
Operacija je nesto sto je takoder primijenjeno na dva elementa, ali daje
neki _rezultat_, najcesce iz istog skupa iz kojeg su ti elementi.

/Na neki nacin, mozemo reci da relacija takoder daje "rezultat" iz skupa
{DA,NE} (ovisno o tome jesu li njeni "operandi" u relaciji), ali takvo
glediste nije uobicajeno u onom dijelu matha koji cemo mi raditi
(dok je npr. uobicajeno u programskom jeziku C , gdje je '<' operator
bas kao i '+')/

> ali ovdje ne razumijem 1to bi trebala biti!

Sad se nadam da razumijete. p je relacija izmedu brojeva 1, 2 i 3, takva
da npr. vrijedi 1p3 , ali !(1p2) ...

A evo i rjesenja zadatka, kad smo vec tu (ako ste iz ovog gore shvatili
kako bi se zadatak trebao rijesiti, savjetujem Vam da ga rijesite sada,
prije nego sto nastavite citati - a onda provjerite rjesenje):

*refleksivnost: treba za svaki x@{1,2,3} provjeriti vrijedi li xpx
(odnosno, kao sto je receno gore, (x,x)@p ). Za x=1, vrijedi. Za x=2,
vrijedi. Za x=3, vrijedi. Dakle, relacija je refleksivna.

*irefleksivnost, naravno, ne vrijedi - slijedi iz ovog gore.

*simetricnost: treba za svake xpy provjeriti vrijedi li ypx .
Dakle, s (x,y) idemo po relaciji p , i za svaki takav par provjeravamo
je li njegov "transponirani" par (y,x) takoder u p .
/Hint: ne treba provjeravati parove oblika (x,x) . ;-)/
Po tome, prvi par kojeg trebamo provjeriti je (1,3) , i tu vec
simetricnost pada, jer !((3,1)@p) . Krace, pisemo 1p3 ali !(3p1) .

*antisimetricnost: trebamo vidjeti vrijedi li xpy & ypx samo za jednake
x i y . To vrijedi, jer (opet, ne treba provjeravati parove oblika
(x,x) ) su jedini parovi razlicitih u p ovi: (1,3) i (2,3) , a niti za
jedan od njih ne vrijedi da mu je transponirani par u p : !(3p1) &
!(3p2) .

*tranzitivnost: trebamo vidjeti povlaci li xpy & ypz da vrijedi xpz .
Strategija: idemo s parom (x,y) kroz p , i za svaki takav par trazimo
sve z@S takve da ypz . Za sve takve z , provjeravamo vrijedi li xpz .
/Hint_1: ne treba provjeravati parove u kojima je y=x , jer tada
vec ypz sam povlaci xpz . ;-)
Hint_2: ne treba provjeravati one z koji su jednaki y , iz istog
razloga./
Idemo: 1) (x,y)=(1,3) . y=3 , pa je jedini z koji dolazi u obzir jednak
3 , dakle jednak y . Kvacica.
2) (x,y)=(2,3) . y je opet 3 , pa se ponavlja prica iz '1)'...
Sve (relevantne) mogucnosti smo prosli (ako bas zelite, mozete naravno
proci po svim trojkama iz S ... ima ih samo 27 :), dakle relacija je
tranzitivna.

Summa summarum: p je refleksivna, antisimetricna i tranzitivna, dakle
parcijalni uredaj. (( 3 je 'najveci', 1 i 2 su 'manji' od njega, ali su
medusobno neusporedivi. ))

(ovo pod "(())" nije dio rjesenja zadatka, vec samo da dade neki glimpse
o tome zasto takvu stvar zovemo parcijalni uredaj)