Klasa abstrakcji

[bajtek]

Treść zadania:

Niech \(\displaystyle{ X =\left\{ 0, 1, \frac{1}{2}, \frac{4}{3}, \frac{3}{2}\right\}}\), a relacja \(\displaystyle{ R}\) będzie określona następująco:

\(\displaystyle{ xRy \Leftrightarrow x-y \in Z}\)

dla \(\displaystyle{ x, y \in X}\). Wówczas:

a. Klasy abstrakcji względem relacji \(\displaystyle{ R}\) to : \(\displaystyle{ \left[ 1\right]}\)R \(\displaystyle{ = \left\{ 0, 1\right\}}\), \(\displaystyle{ \left[ \frac{1}{2} \right]}\) R \(\displaystyle{ = \left\{ \frac{1}{2} , \frac{3}{2}, \frac{4}{3} \right\}}\).

b. Klasy abstrakcji względem relacji \(\displaystyle{ R}\) to : \(\displaystyle{ \left[ 0\right]}\)R \(\displaystyle{ = \left\{ 0, 1\right\}}\), \(\displaystyle{ \left[ \frac{1}{2} \right]}\) R \(\displaystyle{ = \left\{ \frac{1}{2} , \frac{3}{2}\right\}}\) , \(\displaystyle{ \left[ \frac{4}{3} \right]}\) R \(\displaystyle{ = \left\{ \frac{4}{3}\right\}}\).

c. Nie można mówić o klasach abstrakcji, ponieważ \(\displaystyle{ R}\) nie jest relacją równoważności.



I teraz moje pytania, \(\displaystyle{ xRy \Leftrightarrow x-y \in Z}\) to taka relacja \(\displaystyle{ x}\) do \(\displaystyle{ y}\), że \(\displaystyle{ x-y \in Z}\). Mam więc ten przepis, ale co z nim należy zrobić? W jaki sposób mam sprawdzić na nim relacje zwrotności, symetryczności i przechodniości? I jeszcze, czym są klasy abstrakcji? Ale proszę nie o suchą regułkę, tylko o jakiś prosty przykład, bo inaczej chyba nigdy tego nie zrozumiem

[exupery]

A co oznacza, że relacja jest np. zwrotna?

[bajtek]

Że jest w tej relacji do samej siebie. Tzn, że każdy jej el. jest w tej relacji do samego siebie.

[exupery]

zatem \(\displaystyle{ xRx \Leftrightarrow x-x \in Z}\) czy zachodzi to dla każdego elementu?

[bajtek]

Chyba tak... ponieważ niezależnie jakie będzie \(\displaystyle{ x}\), wynik będzie zawsze równy \(\displaystyle{ 0}\), a więc będzie należeć do liczb całkowitych.

[exupery]

Dobrze, no to jedziemy dalej, co powiesz o symetryczności?

[bajtek]

Symetryczna jest wówczas, że jeśli zachodzi w jedną stronę, to zachodzi też w drugą, czyli jeśli \(\displaystyle{ xRy}\) to \(\displaystyle{ yRx}\).

Przechodnia jest wtedy, gdy jeśli jest \(\displaystyle{ xRy}\) oraz \(\displaystyle{ yRz}\) to i również \(\displaystyle{ xRz}\).

Równoważna będzie, gdy zostaną spełnione wszystkie trzy powyższe, razem ze zwrotną.

Widzę, że zwrotną relację było całkiem łatwo wykazać, ale co ze symetrycznością i przechodniością?

Symetryczność:

\(\displaystyle{ xRy \Leftrightarrow x-y \in Z \wedge yRx \Leftrightarrow y-x \in Z}\)

To będzie jakoś tak?

Do tej pory miałem styczność z wypisanymi wszystkimi elementami w postaci par, a nie takim przepisem, więc się z tym gubię..

[mateuszek89]

jeśli chodzi o symetryczność to zauważ że jeśli \(\displaystyle{ x-y \in \mathbb{Z}}\) to przecież \(\displaystyle{ y-x=-(x-y)}\) i to należy do zbioru liczb całkowitych. Dla przechodniości zauważ, że \(\displaystyle{ x-z=(x-y)+(y-z)}\). Po prawej stronie masz sumę dwóch liczb całkowitych z założenia. Co z tego wynika? Pozdrawiam!

[bajtek]

uuu, to jest koszmarne ; /.
Czyli jak... dla symetryczności jak mam to sprawdzić?

Mam wybrać sobie dowolne dwie liczby z \(\displaystyle{ X}\), ale takie i tylko takie, że ich różnica będzie liczbą całkowitą ( wedle założenia \(\displaystyle{ x-y \in Z}\) ) ??

Wtedy, jeśli wezmę np: \(\displaystyle{ x = 1 \frac{1}{2}}\), oraz \(\displaystyle{ y = \frac{1}{2}}\), to \(\displaystyle{ x-y = 1}\) i \(\displaystyle{ y-x = -1}\), czyli obie one są całkowite, czyli relacja symetryczności jest spełniona (bo zachodzi ona dla \(\displaystyle{ xRy}\) a więc jednocześnie dla\(\displaystyle{ yRx}\))?

I kluczowe jest tu założenie o tym, że różnica \(\displaystyle{ x, y}\)ma być l. całkowitą, bo np rel nie bedzie zachodzić dla \(\displaystyle{ x = 1}\) i \(\displaystyle{ y = \frac{1}{2}}\).

Czy dobrze to rozumiem?

[mateuszek89]

tak. Wybierasz 2 dowolne elementy zbioru \(\displaystyle{ X}\) tj. \(\displaystyle{ x,y}\), dla których spełniona jest relacja tzn. ich różnica należy do zbioru liczb całkowitych (\(\displaystyle{ xRy}\)). Teraz musisz sprawdzić czy wtedy \(\displaystyle{ yRx}\) tzn. czy \(\displaystyle{ y-x \in \mathbb{Z}}\). Dlaczego to jest spełnione napisałem już wyżej. Mianowicie jeśli liczba \(\displaystyle{ a \in \mathbb{Z}}\) to liczba \(\displaystyle{ -a \in \mathbb{Z}}\). Nie wystarczy sprawdzić warunku dla jakiś wybranych elementów Twojego zbioru. Musisz udowodnić, że własność zachodzi dla dowolnych el. zbioru. Mam nadzieję, że rozjaśniłem troszkę. Teraz zobacz jak udowodniłem przechodniość wyżej. Dla ćwiczenia możesz sprawdzić czy relacja \(\displaystyle{ R \subseteq \mathbb{Z} \times \mathbb{Z}}\) określona następująco \(\displaystyle{ xRy \Leftrightarrow 3|x-y}\) jest relacją równoważności? Jeśli tak to wypisz jej klasy abstrakcji. Pozdrawiam!

[bajtek]

A więc przechodniość:

Jeśli \(\displaystyle{ xRy \Rightarrow yRz}\), to również \(\displaystyle{ xRz}\), przy założeniu że dla każdego \(\displaystyle{ x, y, z}\) jest tak, że \(\displaystyle{ x-y, y-z, x-z \in Z}\).
Więc samo założenie mówi już, że jest to relacja przechodnia. Zatem mam do czynienia z rel równoważności.

Dobrze?

Jeśli tak to co dalej: klasy abstrakcji, co to jest? Ale powtarzam, nie sucha definicja, to mi nic nie powie
zakładam, że odpowiedź to albo a. , albo b.

[exupery]

Przechodniość:
\(\displaystyle{ xRy \wedge yRz \Rightarrow xRz}\)
Czyli czy z faktu, że \(\displaystyle{ x-y \in \mathbb{Z} \wedge y-z \in \mathbb{Z} \Rightarrow x-z \in \mathbb{Z}}\)??

Odnośnie klas abstrakcji:
Bierzesz dwa elementy, sprawdzasz czy są ze sobą w relacji, jeżeli tak to "wkładasz" je do jednego zbioru, bierzesz 3 element i badasz czy jest w relacji z poprzednim no i jak jest to do zbioru, jak nie to poza zbiór. No i teraz masz już mniej elementów(chodzi o te, które odrzuciliśmy), no i postępujemy z nimi analogicznie i tak do momentu aż każdy będzie w jakimś "worku". Klasą abstrakcji jakiegoś elementu nazwiemy zbiór do którego wrzuciliśmy go.

[bajtek]

Będzie relacją przechodnią, bo jeśli różnica \(\displaystyle{ x - y}\) oraz różnica \(\displaystyle{ y - z}\) mają być z założenia l. całkowitymi, to również \(\displaystyle{ x-z}\) będzie całkowite.


A klasy abstrakcji będą chyba trzy, odpowiedź b. Czy tak?

[mateuszek89]

odpowiedź prawidłowa. Jeśli chodzi o przechodniość to jest tak, bo \(\displaystyle{ x-z=(x-y)+(y-z)}\), a z założenia liczby po prawej stronie są całkowite. Suma liczb całkowitych jest również liczbą całkowitą i tyle. pozdrawiam!