3203.

81

TEKST ZADATKA

U skupu M={1,2,4,8} M = \{1, 2, 4, 8\} uvedena je relacija aρb⇔ab a \rho b \Leftrightarrow \sqrt{ab} je ceo broj. Napraviti tablicu i nacrtati graf relacije ρ, \rho , zatim dokazati da je relacija ekvivalencije i odrediti klase.

REŠENJE ZADATKA

Zapišimo elemente skupa M M kao stepene broja 2:

M={20,21,22,23}M = \{2^0, 2^1, 2^2, 2^3\}

Neka su a=2x a = 2^x i b=2y, b = 2^y , gde x,y∈{0,1,2,3}. x, y \in \{0, 1, 2, 3\} . Uslov ab∈Z \sqrt{ab} \in \mathbb{Z} možemo zapisati preko eksponenata:

ab=2x⋅2y=2x+y=2x+y2\sqrt{ab} = \sqrt{2^x \cdot 2^y} = \sqrt{2^{x+y}} = 2^{\frac{x+y}{2}}

Da bi rezultat bio ceo broj, eksponent mora biti nenegativan ceo broj, što znači da zbir x+y x+y mora biti paran. Zbir dva broja je paran ako i samo ako su oba parna ili oba neparna (imaju istu parnost).

x≡y(mod2)x \equiv y \pmod{2}

Elementi sa parnim eksponentima su 20=1 2^0 = 1 i 22=4. 2^2 = 4 . Elementi sa neparnim eksponentima su 21=2 2^1 = 2 i 23=8. 2^3 = 8 . Odredimo sve parove relacije ρ: \rho :

ρ={(1,1),(1,4),(4,1),(4,4),(2,2),(2,8),(8,2),(8,8)}\rho = \{(1,1), (1,4), (4,1), (4,4), (2,2), (2,8), (8,2), (8,8)\}

Tablica relacije ρ \rho (gde 1 označava da su elementi u relaciji, a 0 da nisu):

ρ124811010201014101080101\begin{array}{c|cccc} \rho & 1 & 2 & 4 & 8 \\ \hline 1 & 1 & 0 & 1 & 0 \\ 2 & 0 & 1 & 0 & 1 \\ 4 & 1 & 0 & 1 & 0 \\ 8 & 0 & 1 & 0 & 1 \end{array}

Graf relacije ρ \rho se sastoji od 4 čvora {1,2,4,8}. \{1, 2, 4, 8\} . Postoje petlje u svakom čvoru (zbog refleksivnosti), kao i dvosmerne grane između čvorova 1 i 4, odnosno 2 i 8.

Dokazujemo da je relacija ekvivalencije. Prvo, refleksivnost: Za svako a∈M a \in M važi aρa a \rho a jer je kvadratni koren kvadrata celog broja takođe ceo broj.

a⋅a=a2=a∈Z\sqrt{a \cdot a} = \sqrt{a^2} = a \in \mathbb{Z}

Simetričnost: Za svako a,b∈M, a, b \in M , ako važi aρb, a \rho b , to znači da je ab∈Z. \sqrt{ab} \in \mathbb{Z} . Kako je množenje komutativno, važi i bρa. b \rho a .

ba=ab∈Z\sqrt{ba} = \sqrt{ab} \in \mathbb{Z}

Tranzitivnost: Neka je aρb a \rho b i bρc. b \rho c . Prema pravilu parnosti eksponenata, a a i b b imaju istu parnost eksponenta, kao i b b i c. c . Sledi da a a i c c imaju istu parnost eksponenta, pa važi aρc. a \rho c .

ac∈Z\sqrt{ac} \in \mathbb{Z}

Pošto je relacija refleksivna, simetrična i tranzitivna, ona je relacija ekvivalencije. Klase ekvivalencije su podskupovi međusobno ekvivalentnih elemenata:

C1={1,4},C2={2,8}C_1 = \{1, 4\}, \quad C_2 = \{2, 8\}