Relacja równoważności

[gower9]

Witam, bardzo proszę o pomoc w rozwiązaniu tego zadania:
\(\displaystyle{ \hbox{Jaka musi być funkcja }f:A \rightarrow A\hbox{, żeby relacja dana warunkiem}\\
xry\iff \exists_{n}( f^{n}(x)=y \vee f^{n}(y)=x)\\
\hbox{była relacją równoważności. Ile może być klas abstrakcji?}}\)

Nie mam pojęcia, jak zrobić przechodniość (przypadek \(\displaystyle{ f^{n}(x)=y \wedge f^{n}(z)=y}\))

[Jan Kraszewski]

Wszystko będzie dobrze, gdy założysz, że \(\displaystyle{ f}\) jest bijekcją.

JK

[gower9]

Wystarczy nawet, że jest injekcją... Ale to nie rozwiązuje problemu. Bo są funkcje nieróżnowartościowe, dla których ta relacja też jest przechodnia...

[Jan Kraszewski]

Bo są funkcje nieróżnowartościowe, dla których ta relacja też jest przechodnia...

Mógłbyś podać przykład?
I kontekst zadania, bo jest ono sformułowane bardzo ogólnie i nie jest do końca jasne, na co mamy nakładać warunki - na funkcję, czy na zbiór \(\displaystyle{ A}\) i na funkcję itd.
Gdzie się natknąłeś na to zadanie?

JK

[gower9]

Zadanie podałem w całości, a natknąłem się na nie na ćwiczeniach...

Weź sobie A={1,2,3,4}
f(1)=2;
f(2)=3;
f(3)=4;
f(4)=2;

Nie jest to injekcja, a relacja jest przechodnia

Edit: Wygodnie się o tym myśli, jak narysujesz sobie zbiór A z punkcikami i strzałki między nimi.
Wtedy, \(\displaystyle{ f^{n}(x)=y}\) oznacza, że jest droga od x do y

[Jan Kraszewski]

Edit: Wygodnie się o tym myśli, jak narysujesz sobie zbiór A z punkcikami i strzałki między nimi. Wtedy, \(\displaystyle{ f^{n}(x)=y}\) oznacza, że jest droga od x do y

To akurat wiem...

A na jakich ćwiczeniach?

Wydaje mi się, że funkcja musi być taka, by wykluczyć sytuację, która sprawia Ci kłopot. Dokładniej, nie może być dwóch argumentów \(\displaystyle{ x,y\in A}\), których orbity nie są rozłączne, ale żadna nie zawiera się w drugiej (gdzie przez orbitę elementu \(\displaystyle{ x}\) rozumiem zbiór \(\displaystyle{ \{a\in A:(\exists n\in\mathbb{N})a=f^n(x)\lor x=f^n(a)\}}\)).

Ale to mało elegancka charakteryzacja funkcji...

JK

[gower9]

Podstawy matematyki, I rok. To jest moja praca domowa... Masz jakiś pomysł?

[Jan Kraszewski]

Napisałem powyżej. Na jakiej uczelni?

JK

[gower9]

Uniwersytet Warszawski, ja wymyśliłem coś takiego:

Jeśli podzielimy funkcję na cykle (na schemacie są to po prostu kółeczka:)), to mamy równoważność, wtw do każdego cyku jest maksymalnie jedno "liniowe dowiązanie" (odcinek wpadający do cyklu)

np
f(1)=2
f(2)=3
f(3)=4
f(4)=5
f(5)=2
f(6)=6
f(7)=8
f(8)=7

To jest jeszcze mniej ładne,..

[Jan Kraszewski]

To istotnie jest pierwszy narzucający się pomysł. Weź jednak pod uwagę, że nie zawsze da się podzielić funkcje na cykle (gdy \(\displaystyle{ A}\) będzie nieskończony) i wtedy jeszcze trudniej to opisać.

Moja propozycja obejmuje Twój pomysł.

A z kim masz ćwiczenia (i wykład)?

JK

[gower9]

prof. Urzyczyn

[Jan Kraszewski]

Poprawka:

Dokładniej, nie może być dwóch argumentów \(\displaystyle{ x,y\in A}\), których orbity nie są rozłączne, ale żadna nie zawiera się w drugiej (gdzie przez orbitę elementu \(\displaystyle{ x}\) rozumiem zbiór \(\displaystyle{ \{a\in A:(\exists n\in\mathbb{N})a=f^n(x)\lor x=f^n(a)\}}\)).

Lepiej:

Dokładniej, nie może być dwóch argumentów \(\displaystyle{ x,y\in A}\), których orbity są różne, ale nie są rozłączne

(jak jedna orbita zawiera się w drugiej, to są równe, co jest dość oczywiste, ale po nocy budziło moje nieuzasadnione wątpliwości...).

JK