Relacje - kiedy są równoważności?

[bemekw]

Ok, więc tak naprawdę musimy rozpatrzyć przypadki gdy mamy \(\displaystyle{ r}\) dane jako \(\displaystyle{ R_{\mathbb{N}}}\) oraz \(\displaystyle{ R_{Parz}}\), bo tylko one są relacjami równoważnościowymi.

-- 20 lis 2011, o 10:58 --

Ok, więc weźmy taką relację równoważnościową \(\displaystyle{ r = R_{\mathbb{N}}}\).
Weźmy taką \(\displaystyle{ f: \mathbb{N} \rightarrow \mathbb{N}}\). Wtedy klasą abstrakcji \(\displaystyle{ [f]_r}\) nazwiemy zbiór wszystkich funkcji, które są w relacji równoważnej \(\displaystyle{ R_{\mathbb{N}}}\) z \(\displaystyle{ f}\). Czyli będzie to zbiór wszystkich takich funkcji \(\displaystyle{ g: \mathbb{N} \rightarrow \mathbb{N}}\), że \(\displaystyle{ f(n) = g(n)}\) Czyli mam podać jakieś wzory ogólne tych funkcji czy jak?

[adambak]

bemekw, ale o którym teraz podpunkcie piszesz? o tym pierwszym:
1. Jakie funkcje należą do \(\displaystyle{ [\lambda n.n]_{r}}\) ?
też się zastanawiam.. ja to widzę tak, że skoro szukamy funkcji, które są w relacji \(\displaystyle{ R_{\mathbb{N}}}\) z tą funkcją identycznościową, to szukamy takich dla których się one pokrywają, czasem częściowo, ale nigdy dla \(\displaystyle{ n\in \mathbb{N}}\) nie przyjmują różnych wartości.. więc, czy odpowiedzią nie będzie, że są to wszystkie funkcje \(\displaystyle{ g : A \rightarrow \mathbb{N}}\), takie, że \(\displaystyle{ g(n)=n}\), gdzie \(\displaystyle{ A \subseteq \mathbb{N}}\)?-- 20 lis 2011, o 14:16 --nie! nie pasuje mi to.. teraz naszym \(\displaystyle{ Z}\) jest zbiór \(\displaystyle{ \mathbb{N}}\).. czy to by znaczyło, że do klasy abstrakcji tej funkcji identycznościowej należy tylko ona sama?

[michael112]

czyli \(\displaystyle{ R_{Z}}\) zawsze jest relacją równoważności[...]

Tak.

Przepraszam, ale jakoś tego nie rozumiem. Jeśli mamy zbiór \(\displaystyle{ Z}\) taki jak podany przykład, tzn. \(\displaystyle{ {3,4,5,6}}\) i funkcje: \(\displaystyle{ f(x)=x+4 \\ g(x)=2x+1 \\ h(x)=3x-3}\), to - jak już zostało napisane, nie istnieje taki \(\displaystyle{ n \in Z}\), że \(\displaystyle{ f(n)=h(n)}\) w podanym wyżej zbiorze (punkt przecięcia \(\displaystyle{ f}\) i \(\displaystyle{ h}\) to \(\displaystyle{ 3\frac{1}{2}}\), który nie należy do \(\displaystyle{ Z}\)) i w ten sposób mamy "załatwiony" \(\displaystyle{ S_{Z}}\). Ale definicja \(\displaystyle{ R_{Z}}\) różni się od \(\displaystyle{ S_{Z}}\) jedynie kwantyfikatorem. Jeżeli nie istnieje taki \(\displaystyle{ n}\), żeby \(\displaystyle{ f}\) i \(\displaystyle{ h}\) przecięły się w choćby jednym punkcie, to tym bardziej nie pokryją się w całym \(\displaystyle{ Z}\).

[adambak]

to "jedynie kwantyfikatorem" robi ogromną różnicę.. zauważ, że w warunku na przechodniość relacji masz implikację.. w takim razie interesują Cię tylko takie funkcje \(\displaystyle{ f,g,h}\), dla których zachodzi:
\(\displaystyle{ \forall_{n\in Z} \ \left( f(n)=g(n) \right)}\)
\(\displaystyle{ \forall_{n\in Z} \ \left( g(n)=h(n) \right)}\)
w takim razie od razu widać, że skoro pierwsze dwie przyjmują te same wartości dla wszystkich argumentów ze zbioru \(\displaystyle{ Z}\) oraz z drugimi dwiema jest to samo, no to \(\displaystyle{ \langle f,h \rangle \in R_Z}\) również.. inne przypadki (jak ten podany przez Ciebie) nas nie obchodzą bo dla nich implikacja równoważności jest spełniona w sposób trywialny.. raz jeszcze podkreślam, że w relacji równoważności mamy implikację, dlatego to implikację sprawdzamy.. ze zwrotnością już tak nie ma.. tam mamy kwantyfikator ogólny, a więc coś musi zachodzić da wszystkich elementów..

[michael112]

Rzeczywiście, teraz już rozumiem. Dziękuję.

[adambak]

niestety drugie zadanie nie jest już takie łatwe...

-- 20 lis 2011, o 17:00 --

jakaś podpowiedź? dla przypomnienia:
dla relacji \(\displaystyle{ R_\mathbb{N}}\), \(\displaystyle{ R_{Parz}}\), gdzie \(\displaystyle{ Parz}\) to zbiór liczb parzystych odpowiedzieć na pytania:
a) jakie funkcje należą do \(\displaystyle{ \left[ \lambda n.n\right]_r}\) ?
b) czy zbiór \(\displaystyle{ (\mathbb{N} \rightarrow \mathbb{N})_{/r}}\) jest skończony?
c) czy istnieje skończona klasa abstrakcji relacji ?
d) czy zbiór \(\displaystyle{ A=\left\{ f: \mathbb{N} \rightarrow \mathbb{N} | f(2011)=0 \right\}}\) jest klasą abstrakcji relacji ?

nie potrafię sobie wyobrazić czy w podpunkcie a) oprócz tej funkcji identycznościowej jakaś funkcja należy do jej klasy abstrakcji..

w b) z kolei co oznacza ten zapis? chodzi o zbiór wszystkich klas abstrakcji, czy jest skończony?

[michael112]

No cóż, to ja pozwolę sobie odświeżyć temat podając moje pomysły na rozwiązanie zadania 2. Od razu założę, że mówimy tylko o dwóch relacjach typu \(\displaystyle{ R}\), bo pozostałe nie będą relacjami równoważności, o czym już wiemy.
(a) no tu już adambak podał odpowiedź, że do klasy abstrakcji relacji \(\displaystyle{ R_{N}}\) należy tylko ta sama funkcja (funkcja identycznościowa) i przychylam się do niej. A może dokładniej: takie funkcje, które w zbiorze \(\displaystyle{ N}\) są identycznościowe, bo nie widzę przeszkód, aby przyjmowały inne wartości poza \(\displaystyle{ N}\) (chyba?).
Jeśli mowa o \(\displaystyle{ R_{Parz}}\), to tak samo, tyle że z dziedziną okrojoną do liczb parzystych.
(b) Oznaczenie \(\displaystyle{ (\mathbb{N}\longrightarrow\mathbb{N})_{/r}}\), o które pytał adambak: to może chodzić o abstrakty (ten symbol znalazłem w skrypcie) i, to też jest czymś podobnym do klas abstrakcji, jeśli nie tym samym. Wydaje mi się, że chodzi o zbiór wszystkich funkcji, które w zbiorze \(\displaystyle{ \mathbb{N}}\) są w relacji \(\displaystyle{ R_{\mathbb{N}}}\) (lub \(\displaystyle{ R_{Parz}}\)) ze sobą.
Tutaj odpowiedź zależy od interpretacji podpunktu a. Jeśli funkcje, które w \(\displaystyle{ \mathbb{N}}\) są identycznościami, a poza tym zbiorem niekoniecznie, to odpowiedź będzie brzmiała: nieskończony, a jeśli to "przyblokujemy", to tylko jedna. Wydaje mi się jednak, że będzie nieskończony, bo określa się funkcje tylko w \(\displaystyle{ \mathbb{N}}\).
(c) I ten punkt mnie zaciekawia, bo pytają się o klasę abstrakcji, więc może to nie to samo, co abstrakt. Już się w tym gubię.
(d) Wydaje mi się, że nie, bo znamy tylko wartość funkcji dla argumentu \(\displaystyle{ 2011}\), a reszta? Może się nie równać wszystkiemu na świecie.

[grazyna19]

A czy to nie jest tak, że skoro ustaliliśmy, że klasy abstrakcji to funkcje identycznościowe to już z tego faktu możemy wywnioskować w podpunkcie d) , że zbiór A nie jest klasą abstrakcji, ponieważ f(2011) \(\displaystyle{ \neq}\) 2011 ?? Czy coś źle interpretuję?

[adambak]

ustaliliśmy, ale pytanie czy dobrze
bo wtedy by się podpunkt c) robił bez sensu.. czy istnieje skończona klasa abstrakcji relacji? no pewnie, ta z podpunktu a).. coś mi tu nie pasuje..

[Jan Kraszewski]

Jak dla mnie notacja, której używacie, jest mocno nieprzyjazna.

No cóż, to ja pozwolę sobie odświeżyć temat podając moje pomysły na rozwiązanie zadania 2. Od razu założę, że mówimy tylko o dwóch relacjach typu \(\displaystyle{ R}\), bo pozostałe nie będą relacjami równoważności, o czym już wiemy.
(a) no tu już adambak podał odpowiedź, że do klasy abstrakcji relacji \(\displaystyle{ R_{N}}\) należy tylko ta sama funkcja (funkcja identycznościowa) i przychylam się do niej. A może dokładniej: takie funkcje, które w zbiorze \(\displaystyle{ N}\) są identycznościowe, bo nie widzę przeszkód, aby przyjmowały inne wartości poza \(\displaystyle{ N}\) (chyba?).

Intuicja adambaka jest słuszna, ale sposób zapisu nie najlepszy. Dla relacji \(\displaystyle{ R_\mathbb{N}}\) klasy abstrakcji są jednoelementowe: \(\displaystyle{ [f]_{R_\mathbb{N}}=\{f\}}\) dla każdego \(\displaystyle{ f\in\mathbb{N}^\mathbb{N}}\). Innymi słowy, relacja \(\displaystyle{ R_\mathbb{N}}\) to po prostu relacja równości.

Jeśli mowa o \(\displaystyle{ R_{Parz}}\), to tak samo, tyle że z dziedziną okrojoną do liczb parzystych.

Ale co "tak samo"? Klasy abstrakcji relacji \(\displaystyle{ R_{Parz}}\) wyglądają tak: \(\displaystyle{ [f]_{R_{Parz}}=\{g\in\mathbb{N}^\mathbb{N}:(\forall n\in\mathbb{N})g(2n)=f(2n)\}}\).

(b) Oznaczenie \(\displaystyle{ (\mathbb{N}\longrightarrow\mathbb{N})_{/r}}\), o które pytał adambak: to może chodzić o abstrakty (ten symbol znalazłem w skrypcie) i, to też jest czymś podobnym do klas abstrakcji, jeśli nie tym samym. Wydaje mi się, że chodzi o zbiór wszystkich funkcji, które w zbiorze \(\displaystyle{ \mathbb{N}}\) są w relacji \(\displaystyle{ R_{\mathbb{N}}}\) (lub \(\displaystyle{ R_{Parz}}\)) ze sobą.

To jest zbiór ilorazowy, czyli zbiór klas abstrakcji. Coś Wam słabo tłumaczą na wykładach...

Tutaj odpowiedź zależy od interpretacji podpunktu a. Jeśli funkcje, które w \(\displaystyle{ \mathbb{N}}\) są identycznościami, a poza tym zbiorem niekoniecznie, to odpowiedź będzie brzmiała: nieskończony, a jeśli to "przyblokujemy", to tylko jedna. Wydaje mi się jednak, że będzie nieskończony, bo określa się funkcje tylko w \(\displaystyle{ \mathbb{N}}\).

Oba zbiory ilorazowe są nieskończone. Zbiór \(\displaystyle{ \mathbb{N}^\mathbb{N}/_{R_{\mathbb{N}}}}\) ma dokładnie tyle elementów, ile jest funkcji z \(\displaystyle{ \mathbb{N}}\) w \(\displaystyle{ \mathbb{N}}\). Dla relacji \(\displaystyle{ R_{Parz}}\) dwie funkcje, które różnią się na liczbach parzystych, wyznaczają różne klasy abstrakcji, czyli klas abstrakcji jest tyle, ile możliwych funkcji ze zbioru liczb parzystych w \(\displaystyle{ \mathbb{N}}\).

(c) I ten punkt mnie zaciekawia, bo pytają się o klasę abstrakcji, więc może to nie to samo, co abstrakt. Już się w tym gubię.

Jak zauważyliśmy, klasy abstrakcji relacji \(\displaystyle{ R_{\mathbb{N}}}\) są jednoelementowe, czyli skończone. Klasy abstrakcji relacji \(\displaystyle{ R_{Parz}}\) są nieskończone. Istotnie, każda klasa abstrakcji tej relacji jest wyznaczone przez pewien wzorzec zachowania się funkcji na liczbach parzystych. Do ustalonej klasy należą zatem funkcje, które na liczbach parzystych zgadzają się z zadanym wzorcem, a na nieparzystych są dowolne. I ta dowolność na nieparzystych powoduje, że w tej (i każdej innej) klasie abstrakcji jest nieskończenie wiele funkcji.

(d) Wydaje mi się, że nie, bo znamy tylko wartość funkcji dla argumentu \(\displaystyle{ 2011}\), a reszta? Może się nie równać wszystkiemu na świecie.

Ten zbiór nie jest klasą abstrakcji ani relacji \(\displaystyle{ R_{\mathbb{N}}}\), ani relacji \(\displaystyle{ R_{Parz}}\), natomiast jest klasą abstrakcji relacji \(\displaystyle{ R_{\{2011\}}}\).

JK

[adambak]

czyli dobrze myślałem z tym zapisem z podpunktu b)..
a problemem nie są wykłady tylko mała ilość ćwiczeń
wszystko zrozumiałe, bardzo dziękuję!

[forget24]

-- 20 lis 2011, o 17:00 --

a) jakie funkcje należą do \(\displaystyle{ \left[ \lambda n.n\right]_r}\) ?

Czyli odpowiedzią na to pytanie jest że dla \(\displaystyle{ R_N}\) są to wszystkie funkcje w postaci \(\displaystyle{ f(n)=g(n)}\), zaś w przypadku \(\displaystyle{ R_{Parz}}\) takie funkcje dla których jest \(\displaystyle{ f(2n) = g(2n)}\) dla dowolnego \(\displaystyle{ n \in N}\)? Coś pewnie poknociłem...

[Jan Kraszewski]

-- 20 lis 2011, o 17:00 --

a) jakie funkcje należą do \(\displaystyle{ \left[ \lambda n.n\right]_r}\) ?

Czyli odpowiedzią na to pytanie jest że dla \(\displaystyle{ R_N}\) są to wszystkie funkcje w postaci \(\displaystyle{ f(n)=g(n)}\), zaś w przypadku \(\displaystyle{ R_{Parz}}\) takie funkcje dla których jest \(\displaystyle{ f(2n) = g(2n)}\) dla dowolnego \(\displaystyle{ n \in N}\)? Coś pewnie poknociłem...

Poknociłeś o tyle, że to był ogólny wzór, a Ty masz wyznaczyć konkretną klasę abstrakcji.

\(\displaystyle{ \left[ id_\mathbb{N}\right]_{R_\mathbb{N}}=\{id_\mathbb{N}\}}\)

\(\displaystyle{ \left[ id_\mathbb{N}\right]_{R_{Parz}}=\{f\in\mathbb{N}^\mathbb{N}:(\forall n\in\mathbb{N})f(2n)=2n\}=\\=\{f\in\mathbb{N}^\mathbb{N}:(\forall n\in Parz)f(n)=n\}}\)

JK

PS. Przykro mi, nie przekonam się do pisania \(\displaystyle{ \lambda n.n}\) zamiast \(\displaystyle{ id_\mathbb{N}}\)...

[forget24]

Tak, chodziło mi tutaj o ogólny wzór takich funkcji, a nie klasy abstrakcji, tak więc czy mój poprzedni zapis w tym względzie jest prawidłowy, czy może powinno być \(\displaystyle{ f(n)=n}\)?

[Jan Kraszewski]

Ale zapis czego? Póki co nic nie zapisałeś, tylko wygłosiłeś pewne stwierdzenie, którego prawdziwość ciężko ocenić. Napisałeś

"dla \(\displaystyle{ R_N}\) są to wszystkie funkcje w postaci \(\displaystyle{ f(n)=g(n)}\)".

Ale co są? Co to znaczy "wszystkie funkcje w postaci \(\displaystyle{ f(n)=g(n)}\)"? W związku z tym Twój zapis nie jest prawidłowy, bo nie wiadomo, co ma oznaczać.

JK