równoważność relacji kongruencji modulo m

[Eevruu]

Niech \(\displaystyle{ m \in \ZZ}\), \(\displaystyle{ m > 1}\) i niech \(\displaystyle{ R \subseteq \ZZ \times \ZZ}\) będzie relacją kongruencji "modulo m" daną wzorem:

\(\displaystyle{ xRy \Leftrightarrow x = y \pmod{m} \Leftrightarrow m \mid ( x - y ) \Leftrightarrow \exists k \in \ZZ : x = y + mk.}\)

Mam wykazać że relacja \(\displaystyle{ R}\) jest relacją równoważności i nie wiem czy dobrze podchodzę do zadania.

Wiem że muszę pokazać że relacja jest zwrotna, symetryczna i przechodnia, więc czy muszę słownie zapisać dlaczego tak jest? Np. "Relacja jest zwrotna gdyż różnica dwóch takich samych liczb wynosi \(\displaystyle{ 0}\), więc jest zawsze podzielna bez reszty" czy muszę to dowodzić w jakiś sposób z definicji?

[Jan Kraszewski]

Z defnicji, tej ostatniej: \(\displaystyle{ xRy \Leftrightarrow (\exists k \in \ZZ)\, x = y + mk.}\)

Np. \(\displaystyle{ R}\) jest zwrotna, gdyż dla dowolnego \(\displaystyle{ x\in\ZZ}\) mamy \(\displaystyle{ x=x+m\cdot 0}\) i \(\displaystyle{ 0\in\ZZ}\), więc \(\displaystyle{ xRx.}\)

JK

[Eevruu]

Więc analogicznie:

Jeżeli \(\displaystyle{ x = y + mk}\) to \(\displaystyle{ R}\) jest symetryczna dla dowolnego \(\displaystyle{ x}\) i \(\displaystyle{ y}\) bo \(\displaystyle{ y = x + m(-k)}\) a \(\displaystyle{ -k \in \ZZ }\) więc \(\displaystyle{ xRy \Rightarrow yRx}\)

Jeżeli \(\displaystyle{ \begin{cases} x = y + mk_{1} \\ y = x + mk_{2} \end{cases} }\)to \(\displaystyle{ R}\) jest przechodnia dla dowolnego \(\displaystyle{ x, y, z}\) gdyż \(\displaystyle{ x = z + m(k_{1} + k_{2}) }\) a \(\displaystyle{ k_{1} + k_{2} \in \ZZ}\) więc \(\displaystyle{ xRy \wedge yRz \Rightarrow xRz }\)

Czy popełniłem gdzieś błąd?

[Jan Kraszewski]

Spostrzeżenia słuszne, ale forma tak koślawa, że aż zgrzyta w zębach.

Jeżeli \(\displaystyle{ x = y + mk}\) to \(\displaystyle{ R}\) jest symetryczna dla dowolnego \(\displaystyle{ x}\) i \(\displaystyle{ y}\) bo \(\displaystyle{ y = x + m(-k)}\) a \(\displaystyle{ -k \in \ZZ }\) więc \(\displaystyle{ xRy \Rightarrow yRx}\).

Powinno być:

Ustalmy dowolne \(\displaystyle{ x,y\in\ZZ}\) takie, że \(\displaystyle{ xRy.}\) Wówczas istnieje \(\displaystyle{ k\in\ZZ}\) takie, że \(\displaystyle{ x = y + mk}\). Zatem \(\displaystyle{ y = x-mk=x + m(-k)}\) i ponieważ \(\displaystyle{ -k \in \ZZ }\) więc \(\displaystyle{ yRx}\), czego należało dowieść.

Jeżeli \(\displaystyle{ \begin{cases} x = y + mk_{1} \\ y = \red{x} + mk_{2} \end{cases} }\)to \(\displaystyle{ R}\) jest przechodnia dla dowolnego \(\displaystyle{ x, y, z}\) gdyż \(\displaystyle{ x = z + m(k_{1} + k_{2}) }\) a \(\displaystyle{ k_{1} + k_{2} \in \ZZ}\) więc \(\displaystyle{ xRy \wedge yRz \Rightarrow xRz }\)

Masz jedną literówką i sformułowanie także złe. Powinno być:

Ustalmy dowolne \(\displaystyle{ x,y,z\in\ZZ}\) takie, że \(\displaystyle{ xRy}\) i \(\displaystyle{ yRz.}\) Wówczas istnieją \(\displaystyle{ k_1,k_2\in\ZZ}\) takie, że \(\displaystyle{ x = y + mk_1}\) i \(\displaystyle{ y=z+mk_2.}\) Stąd \(\displaystyle{ x=(z+mk_2)+ mk_1=z + m(k_{1} + k_{2})}\) i ponieważ \(\displaystyle{ k_{1} + k_{2} \in \ZZ }\) więc \(\displaystyle{ xRz}\), czego należało dowieść.

JK

[Eevruu]

Dziękuję bardzo za pomoc, rzeczywiście dużo lepsza forma w Pana wykonaniu.