3208. Relacije | Balkan Tutor

TEKST ZADATKA

U skupu $A = \{1, 2, 3, \dots, 10\}$ zadata je relacija $x \rho y \Leftrightarrow 7 \mid x + 6y .$ Dokazati da je $\rho$ relacija ekvivalencije i naći klase ekvivalencije.

REŠENJE ZADATKA

Da bismo olakšali dokazivanje, transformišemo uslov relacije. Primetimo da se izraz može zapisati na sledeći način:

x + 6y = x - y + 7y

Kako je $7y$ uvek deljivo sa 7 za svaki ceo broj $y ,$ uslov $7 \mid x + 6y$ važi ako i samo ako važi $7 \mid x - y .$ Dakle, relacija se svodi na kongruenciju po modulu 7:

x \rho y \iff 7 \mid (x - y)

Dokazujemo refleksivnost. Za svako $x \in A$ važi:

x - x = 0

Kako je 0 deljivo sa 7, sledi da $7 \mid (x - x) ,$ odnosno $x \rho x .$ Relacija je refleksivna.

Dokazujemo simetričnost. Pretpostavimo da važi $x \rho y ,$ odnosno $7 \mid (x - y) .$ Tada postoji ceo broj $k$ takav da je:

x - y = 7k

Množenjem jednačine sa -1 dobijamo:

y - x = 7(-k)

Pošto je $-k$ takođe ceo broj, sledi da $7 \mid (y - x) ,$ odnosno $y \rho x .$ Relacija je simetrična.

Dokazujemo tranzitivnost. Pretpostavimo da važi $x \rho y$ i $y \rho z .$ To znači da $7 \mid (x - y)$ i $7 \mid (y - z) .$ Zbir dva broja deljiva sa 7 je takođe deljiv sa 7:

(x - y) + (y - z) = x - z

Sledi da $7 \mid (x - z) ,$ odnosno $x \rho z .$ Relacija je tranzitivna.

Pošto je relacija refleksivna, simetrična i tranzitivna, dokazali smo da je $\rho$ relacija ekvivalencije.

Sada tražimo klase ekvivalencije. Klasa ekvivalencije elementa $a$ definiše se kao skup svih elemenata $x \in A$ koji su u relaciji sa $a :$

[a] = \{ x \in A \mid x \rho a \} = \{ x \in A \mid 7 \mid (x - a) \}

Ovo znači da u istu klasu spadaju brojevi iz skupa $A$ koji daju isti ostatak pri deljenju sa 7. Računamo klase za elemente skupa $A = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} :$

\begin{aligned} [1] &= \{1, 8\} \\ [2] &= \{2, 9\} \\ [3] &= \{3, 10\} \\ [4] &= \{4\} \\ [5] &= \{5\} \\ [6] &= \{6\} \\ [7] &= \{7\} \end{aligned}

79