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

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
raphel
Użytkownik
Użytkownik
Posty: 657
Rejestracja: 9 gru 2007, o 12:27
Płeć: Mężczyzna
Lokalizacja: Czewa/Wrocław
Podziękował: 84 razy
Pomógł: 138 razy

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

Post autor: raphel » 28 lis 2008, o 21:03

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
Administrator
Administrator
Posty: 26928
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4502 razy

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

Post autor: Jan Kraszewski » 28 lis 2008, o 22:38

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

ODPOWIEDZ