Sprawdź relację równoważności - ocb?

[bybek5]

Mam problem z rozwiązywaniem tego typu zadań. Nie mogę za bardzo znaleźć dobrze wytłumaczonych przykładów i dlatego te problemy. Znam teorie ale ciężko to w praktyce zastosować. Mianowicie jak rozwiązać takie zadania:

a)
\(\displaystyle{ \bigwedge\limits_{x,y,z\in Z} xRy \Leftrightarrow 5|(x-y)}\)

b)
\(\displaystyle{ X = \{1,2,3,4,...,16\} \bigwedge\limits_{x,y\in X} xRy \Leftrightarrow 4|( x^{2} - y^{2} )}\)

Znalazłem na forum podobne zadanie do podpunktu a), mianowicie:

\(\displaystyle{ 3|(a-a)\quad 3|0}\)
jest to prawdą, więc relacja jest zwrotna.
Symetria:
\(\displaystyle{ 3|(a-b)\quad 3|-(a-b)\quad 3|(b-a)}\)
tak więc relacja jest symetryczna.
Przechodniość:
\(\displaystyle{ 3|(a-b)\quad \&\quad 3|(b-c)}\)
z tego wynika, że
\(\displaystyle{ 3|(a-b)+(b-c)\quad 3|(a-c)}\)
i jest przechodnia.

To ten przykład rozwiązuje się praktycznie tak samo. Ale jak zapisać do tego jeszcze klasę abstrakcji i określić jej ilość.

P.S. Proszę o nieusuwanie wątku. I jeśli ktoś w Was zna stronę z fajnymi przykładami to będę zobowiązany.

[Crizz]

Co do pierwszego przykładu: \(\displaystyle{ xRy \Leftrightarrow 5|(x-y)}\), natomiast \(\displaystyle{ 5|(x-y) \Leftrightarrow x-y=5k,k\in Z}\).
To oznacza, że \(\displaystyle{ y=5k-x,k\in Z}\), zatem klasą abstrakcji elementu x jest zbiór \(\displaystyle{ \{5k-x:k\in Z\}}\). Jak łątwo zauważyć, to jest zbiór liczb dających z dzielenia przez 5 resztę tę samą, co x. To oznacza, że klas abstrakcji jest tylko tyle, ile możliwych reszt z dzielenia przez 5, czyli 5.

Odpowiednie własności relacji z drugiego przykładu sprawdzasz w zasadzie identycznie, a elementów tej relacji jest tak mało, że klasy abstrakcji możesz wyznaczyć mechanicznie (w miarę rozwiązywania na pewno wpadnesz na to, klasy względem których elementów będą równe itp.)

[bybek5]

a jeszcze takie podstawowe pytanie, bo chyba to jakoś źle rozumuje: z czego wynika, że \(\displaystyle{ xRy \Leftrightarrow 5|(x-y)}\) jest relacją zwrotną czy symetryczną.

Bo na przykład: \(\displaystyle{ 5|(x-x) \rightarrow 5|0}\) - to dlaczego to jest relacja zwrotna?

Albo \(\displaystyle{ 5|(x-y) \rightarrow 5|(y-x)}\) Podstawiając pod to liczby: 5|(3-2) to jest 5|(1). A odwrotnie 5|(2-3) to jest 5|(-1). I to jest symetryczne?

I znalazłem jeszcze taki przykład:

\(\displaystyle{ xRy \Leftrightarrow 2|x+y}\)

\(\displaystyle{ xRx \Leftrightarrow 2|x+x}\), zwrotna
\(\displaystyle{ xRy \Leftrightarrow 2|x+y \Rightarrow 2|y+x}\), symetryczna
\(\displaystyle{ xRy \Leftrightarrow (2|x+y ^ 2|y+z) \Rightarrow 2|x+z}\), przechodnia

Klasy abstrakcji:
\(\displaystyle{ [0] = \{0,1,2,4,6,8...\}

[1] = \{1,3,5,7,9...\}

[2] = \{0}\}

[3] = \{1\}}\)

Czy te dwie ostatnie klasy są poprawne ?

[Jan Kraszewski]

\(\displaystyle{ 5|(x-x) \rightarrow 5|0}\) - to dlaczego to jest relacja zwrotna?

Bo 5 jest dzielnikiem zera (każda liczba całkowita jest dzielnikiem zera).

Albo \(\displaystyle{ 5|(x-y) \rightarrow 5|(y-x)}\) Podstawiając pod to liczby: 5|(3-2) to jest 5|(1). A odwrotnie 5|(2-3) to jest 5|(-1). I to jest symetryczne?

A dlaczego nie? Jeśli z fałszu wynika fałsz, to jest dobrze, nieprawdaż? Zresztą, spróbuj zrozumieć, co znaczy w tym przypadku symetria - przecież jeśli 5 dzieli jakąś liczbę, to dzieli także liczbę do niej przeciwną.

I znalazłem jeszcze taki przykład:

\(\displaystyle{ xRy \Leftrightarrow 2|x+y}\)

\(\displaystyle{ xRx \Leftrightarrow 2|x+x}\), zwrotna
\(\displaystyle{ xRy \Leftrightarrow 2|x+y \Rightarrow 2|y+x}\), symetryczna
\(\displaystyle{ xRy \Leftrightarrow (2|x+y ^ 2|y+z) \Rightarrow 2|x+z}\), przechodnia

Klasy abstrakcji:
\(\displaystyle{ [0] = \{0,1,2,4,6,8...\}

[1] = \{1,3,5,7,9...\}

[2] = \{0}\}

[3] = \{1\}}\)

Czy te dwie ostatnie klasy są poprawne ?

A gdzieś Ty to znalazł?! To przecież w ogóle nie ma sensu - klasy abstrakcji muszą być rozłączne! Zakładając, że relacja jest na \(\displaystyle{ \mathbb{N}}\), to tylko klasa \(\displaystyle{ [1]}\) jest poprawnie wyznaczona.

JK

[bybek5]

Dzięki za odpowiedzi. A mógłbyś jeszcze pokazać jak będą wyglądać wszystkie klasy abstrakcji dla tego przykładu?

P.S. Wiesz może gdzie są w necie rozwiązane tego typu zadania?

[Jan Kraszewski]

Zastanów się, jaki podział zbioru liczb naturalnych zadaje ta relacja, albo, z innej strony, jakie liczby są ze sobą w relacji. Skoro w jednej klasie abstrakcji są liczby nieparzyste, to...

JK

PS. Samo oglądanie rozwiązań może nie pomóc - trzeba zrozumieć, na czym polega proces abstrahowania.

[bybek5]

to w drugiej muszą być parzyste czyli : \(\displaystyle{ [0] = \{0,2,4,6,8...\}}\) . I to są wszystkie klasy, tak?
A liczby minusowe?

[Jan Kraszewski]

Tak, ta relacja ma dwie klasy abstrakcji.

Z treści (błędnego) rozwiązania można domniemywać, że relacja jest zadana na zbiorze liczb naturalnych, więc liczb minusowych (zwanych zazwyczaj ujemnymi) nie ma. Gdybyś rozważał tę relację na zbiorze liczb całkowitych, to rozwiązanie będzie podobne - sam już zauważyłeś, jakie liczby są w jednej klasie, a jakie w drugiej.

JK