relacje równoważności i klasy abstrakcji..

[raphel]

Niech \(\displaystyle{ R _{I} (x,y)}\), oznacza relację zdefiniowaną formułą:
\(\displaystyle{ \exists p I ((\o (p,x) \o (p,y)) (\o(p,y) \o(p,x)))}\)
na \(\displaystyle{ \mathbb{N ^{+} } \mathbb{N ^{+} }}\), gdzie \(\displaystyle{ \mathbb{N ^{+} }= \mathbb{N}}\)\(\displaystyle{ {{0}}}\), \(\displaystyle{ I}\) jest skończonym niepustym zbiorem liczb pierwszych, a \(\displaystyle{ \o(x,y)}\) jest formułą \(\displaystyle{ \exists z (x z=y)}\). Niech \(\displaystyle{ Q _{I} =( \mathbb{N ^{+} } \mathbb{N ^{+} })}\) \(\displaystyle{ R _{I}}\).
a) Czy \(\displaystyle{ R _{I}}\) jest relacją równoważności? Jeśli tak, podaj liczbe klas równoważności relacji \(\displaystyle{ R _{I}}\).
b) Czy \(\displaystyle{ Q _{I}}\) jest relacją równoważności? Jeżeli tak, podaj liczbe klas równoważności relacji \(\displaystyle{ Q _{I}}\).

[Jan Kraszewski]

Najpierw trochę rozkodujemy to zadanie.
\(\displaystyle{ \phi(x,y)\iff x|y}\) (x dzieli y);
\(\displaystyle{ R_I(x,y)\iff (\exists p\in I) (p|x p|y)}\);
\(\displaystyle{ Q_I(x,y)\iff (\forall p\in I)(p|x p|y)}\).

Teraz:
Relacja \(\displaystyle{ R_I}\) nie jest relacją równoważności, bo nie jest zwrotna (jest nawet przeciwzwrotna). Definicję zwrotności znasz, więc powinieneś sobie poradzić z uzasadnieniem.

Relacja \(\displaystyle{ Q_I}\) jest relacją równoważności. Sprawdzenie zwrotności, symetrii i przechodniości jest proste, gdy korzystamy z powyższego opisu.

Klasy abstrakcji relacji \(\displaystyle{ Q_I}\):
Zauważ, że liczby x i y są w relacji \(\displaystyle{ Q_I}\) dokładnie wtedy, gdy mają te same dzielniki pierwsze ze zbioru \(\displaystyle{ I}\). Zatem klas abstrakcji jest dokładnie tyle, ile podzbiorów zbioru \(\displaystyle{ I}\), czyli \(\displaystyle{ 2^{|I|}}\).

JK