Kako da relaciju čitaš kao podskup skupa A×A i kako da proveriš njena svojstva.
Matoteka · Centar znanja · Lekcija 3
Binarne relacije ekvivalencija i poredak
Relacija govori koji su uređeni parovi dozvoljeni. Iz te jednostavne ideje nastaju klase ekvivalencije, poredak brojeva, matrice relacije i veliki deo jezika kojim matematika opisuje strukturu nekog skupa.
Mešanje simetričnosti i antisimetričnosti, i brzopleto proglašavanje relacije poretkom.
Ispitivanje svojstava, nalaženje klasa ekvivalencije i razlikovanje parcijalnog od linearnog poretka.
35 do 45 minuta pažljivog rada
Skupovi, Kartezijev proizvod i osnovna logička preciznost
Sistemsko ispitivanje refleksivnosti, simetričnosti, antisimetričnosti i tranzitivnosti
Canvas matrica relacije sa automatskom analizom osobina
Brza navigacija
Kretanje kroz lekciju
Najstabilniji redosled je: zašto ova tema postoji, kako se nalazi modul i argument, kako se prelazi između oblika, pa tek onda Moivreova formula i koreni.
Zašto je ova lekcija važna
Relacije uvode strukturu u skup
Skup sam po sebi samo okuplja elemente. Relacija kaže kako su ti elementi povezani: kada su ekvivalentni, kada je jedan manji od drugog, kada jedan deli drugi ili kada neki uređeni par jednostavno nije dozvoljen.
Gde se relacije pojavljuju kasnije
- u kongruencijama i radu sa ostacima pri deljenju
- u uređivanju realnih brojeva preko odnosa \(\le\) i \(\ge\)
- u funkcijama, jer se funkcija može posmatrati kao posebna vrsta relacije
Zašto je važna na prijemnom
- često se traži da proveriš da li je data relacija ekvivalencija ili poredak
- klase ekvivalencije se javljaju kroz ostatke pri deljenju
- poredak se krije iza pitanja o uporedivosti, minimumu i maksimumu
Glavna misaona promena
Kada vidiš relaciju, nemoj prvo pitati “šta znači znak”, nego “koje uređene parove ova relacija prihvata”.
Osnovna ideja
Relacija je podskup Kartezijevog proizvoda
Ako su A i B skupovi, binarna relacija između njih je bilo koji podskup skupa A×B. Kada radimo svojstva kao što su refleksivnost i tranzitivnost, najčešće posmatramo relaciju na istom skupu, pa je R ⊆ A×A.
Formalni zapis
\[R \subseteq A \times A\]
Svaki element relacije je uređeni par \((a,b)\). Ako je taj par u relaciji, pišemo \(aRb\).
Šta znači aRb
To znači da uređeni par \((a,b)\) pripada relaciji \(R\). Nije dovoljno da su \(a\) i \(b\) samo elementi skupa; mora baš par \((a,b)\) da bude izabran.
Primer: ako je \(R = \{(1,1),(1,2)\}\), onda važi \(1R2\), ali ne važi \(2R1\).
Kako se relacija prikazuje
- kao skup uređenih parova
- kao matrica relacije
- kao uslov, na primer \(a \equiv b \pmod{3}\) ili \(a \le b\)
\[A = \{1,2,3\}, \qquad R = \{(1,1),(1,2),(2,2),(3,3)\}\]
Ovde važe \(1R1\), \(1R2\), \(2R2\), \(3R3\), ali ne važi \(2R1\) jer par \((2,1)\) nije naveden.
Mikro-provera: ako je R \u2286 A\u00D7A, da li iz a \u2208 A i b \u2208 A automatski sledi aRb?
Ne. To samo znači da je par \((a,b)\) kandidat da bude u relaciji. Tek ako zaista važi \((a,b) \in R\), možemo da pišemo \(aRb\).
Četiri ključna svojstva
Kako se relacija testira korak po korak
U praksi je najbrže da svojstva proveravaš ovim redom: dijagonala za refleksivnost, ogledalo za simetričnost, zabrana dvosmernih veza za antisimetričnost i dvokorak za tranzitivnost.
Refleksivnost
\[\forall a \in A \; (aRa)\]
Svaki element mora biti u relaciji sam sa sobom. U matrici relacije to znači da svi diagonalni parovi \((a,a)\) moraju biti prisutni.
Simetričnost
\[aRb \Rightarrow bRa\]
Ako jedan smer postoji, mora postojati i obrnuti smer. U matrici to znači da je slika u odnosu na dijagonalu ogledalski ista.
Antisimetričnost
\[(aRb \land bRa) \Rightarrow a=b\]
Dvosmerna veza je dozvoljena samo na dijagonali. Ako za različite elemente važe i \(aRb\) i \(bRa\), relacija nije antisimetrična.
Tranzitivnost
\[(aRb \land bRc) \Rightarrow aRc\]
Ako možeš da ideš iz \(a\) u \(b\), pa iz \(b\) u \(c\), onda mora postojati i prečica iz \(a\) u \(c\).
Brzi algoritam
Prvo proveri da li svi diagonalni parovi postoje. Zatim traži par bez ogledala, pa dvosmerni par sa različitim elementima, a na kraju proveri da li svaki dvokorak zatvara trougao.
Mikro-provera: zašto simetričnost i antisimetričnost nisu suprotnosti?
Zato što govore različite stvari. Simetričnost traži da uz svaki par \((a,b)\) postoji i \((b,a)\). Antisimetričnost kaže da, ako oba para postoje, onda moraju biti na dijagonali, odnosno \(a=b\). Relacija jednakosti je i simetrična i antisimetrična.
Interaktivni laboratorijum
Matrica relacije i automatska provera osobina
Izaberi jednu relaciju, klikni bilo koju ćeliju matrice i čitaj je kao uređeni par (a,b). Ispod dobijaš objašnjenje za izabrani par i analizu ključnih svojstava.
Aktivna relacija
Relacija na skupu {0,1,2,3,4,5}
Relacija grupiše brojeve po ostatku pri deljenju sa 3. Ovo je klasičan primer relacije ekvivalencije.
Izabrani uređeni par
Izabrani par je (0,0).
Par (0,0) pripada relaciji jer brojevi 0 i 0 imaju isti ostatak pri deljenju sa 3.
Refleksivnost da
Da. Prisutan je svaki diagonalni par (0,0), (1,1), (2,2), (3,3), (4,4), (5,5).
Simetričnost da
Da. Svaki prisutan par ima i svoj obrnuti par.
Antisimetričnost ne
Ne. Istovremeno važe (0,3) i (3,0) za različite elemente.
Tranzitivnost da
Da. Svaki dvokorak se zatvara direktnim parom.
Klasifikacija
Ova relacija je ekvivalencija. Na skupu {0,1,2,3,4,5} daje klase: {0,3}, {1,4}, {2,5}.
Kako da čitaš matricu
- dijagonala ti odmah govori nešto o refleksivnosti
- ogledalo preko dijagonale proverava simetričnost
- dvosmerni parovi van dijagonale ruše antisimetričnost
- dva uzastopna koraka treba da daju i direktan treći korak
Kako da učiš iz ovog laboratorijuma
Pokušaj da prvo sam pogodiš šta će svojstva biti pre nego što klikneš dugme. Ako ćelije u matrici deluju “ogledalno”, to je signal za simetričnost. Ako dijagonala nije potpuna, relacija nije refleksivna.
Relacije ekvivalencije
Ekvivalencija grupiše elemente u klase
Kada je relacija refleksivna, simetrična i tranzitivna, ona ne uređuje elemente po veličini, već ih razvrstava u grupe elemenata koji su međusobno "isti po nekom kriterijumu".
Kada je relacija ekvivalencija
\[R \text{ je ekvivalencija } \iff R \text{ je refleksivna, simetrična i tranzitivna.}\]
Svaka klasa ekvivalencije okuplja elemente koji su međusobno povezani tom relacijom.
Šta je klasa ekvivalencije
\[[a] = \{x \in A \mid xRa\}\]
Klasa elementa \(a\) sadrži sve elemente koji su u relaciji ekvivalencije sa \(a\).
\[a \sim b \iff a \equiv b \pmod{3}\]
Na skupu \(\{0,1,2,3,4,5\}\) dobijamo tri klase ekvivalencije:
\[[0] = \{0,3\}\]
\[[1] = \{1,4\}\]
\[[2] = \{2,5\}\]
Važna posledica
Klase ekvivalencije ili su potpuno iste ili su disjunktne. Ne mogu se delimično preklapati.
Mikro-provera: ako su [a] i [b] dve klase ekvivalencije i imaju zajednički element, šta sledi?
Tada su iste. Zajednički element preko simetričnosti i tranzitivnosti “spaja” obe klase, pa se pokazuje da svaki element jedne pripada i drugoj.
Relacije poretka
Poredak ne grupiše, nego uređuje
Za poredak je presudno da relacija bude refleksivna, antisimetrična i tranzitivna. Tada možemo da govorimo o tome da je jedan element ispred, ispod ili manji od drugog.
Parcijalni poredak
\[R \text{ je parcijalni poredak } \iff R \text{ je refleksivna, antisimetrična i tranzitivna.}\]
Neki elementi mogu ostati neuporedivi. Klasičan primer je deljivost na skupu \(\{1,2,3,6\}\): brojevi \(2\) i \(3\) nisu uporedivi relacijom deljivosti.
Linearni poredak
\[\forall a,b \in A,\quad aRb \lor bRa\]
Ako su svi parovi elemenata uporedivi, parcijalni poredak postaje linearni. Relacija \(\le\) na realnim brojevima je upravo takav poredak.
\u2264 na realnim brojevima
Refleksivna je jer važi \(x \le x\). Antisimetrična je jer iz \(x \le y\) i \(y \le x\) sledi \(x=y\). Tranzitivna je jer iz \(x \le y\) i \(y \le z\) sledi \(x \le z\).
Deljivost
Na prirodnim brojevima relacija \(a \mid b\) jeste parcijalni poredak, ali nije linearni: \(2 \nmid 3\) i \(3 \nmid 2\), pa nisu svi elementi uporedivi.
Strogi poredak nije isto
Relacija \(<\) nije refleksivna, pa po ovoj definiciji nije relacija poretka koju ovde testiramo. Ona je strogi poredak i ima malo drugačiji skup osobina.
Mikro-provera: da li deljivost na skupu {1,2,3,6} jeste linearni poredak?
Nije, jer brojevi \(2\) i \(3\) nisu uporedivi: ne važi ni \(2 \mid 3\) ni \(3 \mid 2\). Zato je deljivost samo parcijalni poredak.
Vođeni primeri
Od eksplicitnih parova do klasifikacije relacije
Svaki primer pokazuje drugi tip rezonovanja: čitanje skupa parova, proveru svojstava, formiranje klasa i razlikovanje parcijalnog i linearnog poretka.
Primer 1: Eksplicitno zadat skup parova
Neka je na skupu \(A=\{1,2,3\}\) zadato
\[R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}\]
Dijagonala je cela, pa je relacija refleksivna. Parovi \((1,2)\) i \((2,1)\) pokazuju simetričnost, ali ruše antisimetričnost. Tranzitivnost važi, pa je ovo relacija ekvivalencije.
Klase: \(\{1,2\}\) i \(\{3\}\)
Primer 2: Ostaci pri deljenju
Na celim brojevima definišimo
\[a \sim b \iff a-b \text{ je deljivo sa } 4\]
To je ekvivalencija: svaki broj ima isti ostatak kao sam sa sobom, relacija je simetrična, a “isti ostatak” se prenosi kroz tranzitivnost.
Klasa broja 1: \([1]=\{\ldots,-7,-3,1,5,9,\ldots\}\)
Primer 3: Deljivost kao poredak
Na skupu \(A=\{1,2,3,6\}\) posmatraj relaciju
\[aRb \iff a \mid b\]
Relacija je refleksivna, antisimetrična i tranzitivna, pa je parcijalni poredak. Ipak nije linearni, jer \(2\) i \(3\) nisu uporedivi.
Primer 4: \(\le\) kao potpuni model uređenja
Na bilo kom podskupu realnih brojeva relacija \(\le\) ne samo da jeste parcijalni poredak, već su svi elementi uporedivi.
\[x \le y \;\; \text{ili} \;\; y \le x\]
Zbog toga je \(\le\) osnovni primer linearnog poretka.
Ključne formule
Šta treba da ti bude trenutno prepoznatljivo
Ove formule nisu za puko memorisanje. Njih treba odmah povezati sa vizuelnim testom u matrici relacije.
Refleksivnost
\[\forall a \in A,\; (a,a) \in R\]
Svi diagonalni parovi moraju postojati.
Simetričnost
\[(a,b) \in R \Rightarrow (b,a) \in R\]
Svaka veza ima ogledalo preko dijagonale.
Antisimetričnost
\[(a,b),(b,a) \in R \Rightarrow a=b\]
Dvosmerni parovi van dijagonale nisu dozvoljeni.
Tranzitivnost
\[(a,b),(b,c) \in R \Rightarrow (a,c) \in R\]
Dvokorak mora imati direktnu prečicu.
Ekvivalencija
\[\text{refleksivna + simetrična + tranzitivna}\]
Rezultat su klase ekvivalencije i particija skupa.
Parcijalni poredak
\[\text{refleksivna + antisimetrična + tranzitivna}\]
Rezultat je uređivanje, ali ne moraju svi elementi biti uporedivi.
Česte greške
Ovde se najlakše gube poeni
Većina grešaka nastaje zato što učenik proveri samo jedan ili dva para i prerano zaključi.
Mešanje simetričnosti i antisimetričnosti
To nisu suprotna svojstva. Simetričnost traži i obrnuti par, a antisimetričnost ga zabranjuje za različite elemente.
Zaboravljena dijagonala
Dovoljno je da nedostaje samo jedan par \((a,a)\) i relacija više nije refleksivna.
Tranzitivnost se ne proverava nasumično
Moraš pregledati sve relevantne dvokorake. Jedan uspešan primer ne dokazuje tranzitivnost.
Parcijalni nije isto što i linearni poredak
Čim postoje neuporedivi elementi, relacija nije linearni poredak, iako može biti dobar parcijalni poredak.
Veza sa prijemnim zadacima
Kako se ova tema javlja u realnom zadatku
Na prijemnom će tema često biti upakovana u konkretan uslov, a ne pod naslovom "binarne relacije".
Tipično pitanje 1
Data je relacija preko skupa parova ili formule. Potrebno je odrediti koja svojstva važe, a zatim zaključiti da li je relacija ekvivalencija ili poredak.
Tipično pitanje 2
Data je relacija ostataka pri deljenju. Potrebno je formirati klase ekvivalencije ili odrediti broj različitih klasa.
Prijemni kontrolna lista
Napiši skup, proveri dijagonalu, ogledalo i dvokorake, pa tek onda klasifikuj relaciju. Ako je poredak, dodatno proveri da li su svi elementi uporedivi.
Vežbe
Kratka provera razumevanja
Reši samostalno, pa tek onda otvori rešenje.
Zadatak 1: Skup parova
Na skupu \(A=\{1,2,3\}\) data je relacija \(R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}\). Koja svojstva važe?
Rešenje
Relacija je refleksivna, simetrična i tranzitivna, ali nije antisimetrična zbog parova \((1,2)\) i \((2,1)\) sa \(1 \ne 2\). Zato je ovo relacija ekvivalencije.
Zadatak 2: Uporedivost
Na skupu \(\{1,2,3,6\}\) posmatra se relacija deljivosti. Da li su \(2\) i \(3\) uporedivi?
Rešenje
Nisu, jer ne važi ni \(2 \mid 3\) ni \(3 \mid 2\). To pokazuje da deljivost ovde nije linearni poredak.
Zadatak 3: Klasa ekvivalencije
Na skupu celih brojeva važi \(a \sim b \iff a-b\) je deljivo sa \(5\). Odredi klasu \([2]\).
Rešenje
\[[2] = \{\ldots,-8,-3,2,7,12,\ldots\}\]
To su svi brojevi koji daju ostatak \(2\) pri deljenju sa \(5\).
Zadatak 4: Strogi odnos
Na realnim brojevima definisano je \(xRy \iff x<y\). Da li je to relacija poretka po definiciji iz ove lekcije?
Rešenje
Nije, jer relacija nije refleksivna: ne važi \(x<x\). To je strogi poredak, ali ne i poredak u smislu “refleksivna + antisimetrična + tranzitivna”.
Završni uvid
Glavni uvid lekcije
Relacija nije samo znak između dva simbola. Ona je pravilo koje bira tačno određene uređene parove. Iz istog jezgra nastaju i ekvivalencija i poredak.
Najvažniji princip
\[R \subseteq A \times A \qquad \Longrightarrow \qquad \text{ispituj dijagonalu, ogledalo i dvokorake}\]
Ko ove tri provere odradi mirno i sistematski, dobija brz put kroz svaki zadatak sa relacijama.
Završni rezime
Šta treba da zapamtiš iz ove lekcije
Ako ove tvrdnje čitaš bez kolebanja, lekcija je dobro savladana.
1. Binarna relacija
Binarna relacija na skupu \(A\) je podskup skupa \(A \times A\).
2. Zapis aRb
Zapis \(aRb\) znači da uređeni par \((a,b)\) pripada relaciji.
3. Provera svojstava
Refleksivnost proveravaš na dijagonali, simetričnost preko ogledala, a tranzitivnost preko dvokoraka.
4. Ekvivalencija
Relacija ekvivalencije je refleksivna, simetrična i tranzitivna i deli skup na klase ekvivalencije.
5. Parcijalni poredak
Parcijalni poredak je refleksivan, antisimetričan i tranzitivan.
6. Linearni poredak
Linearni poredak je parcijalni poredak u kome su svi elementi uporedivi.