Czy dana funkcja jest "na" ?

[M4ksiu]

Mam tutaj 2 zadania - przy czym 1 jest zrobione ( i prosilbym o jego sprawdzenie ) a 2 tak naprawde sprawia problemy z rozwiazaniem:
1) Pokaz, istnienie funkcji \(\displaystyle{ h: A \to A}\), ktora dla funkcji f, g "na" \(\displaystyle{ B}\), \(\displaystyle{ f, g: A \to B}\), daje nastepujaca wlasnosc: zlozenie f i h daje g. Dodatkowo zostala podana definicja funkcji \(\displaystyle{ c: P(A) \to A}\), ze dla dowolnego \(\displaystyle{ D \subseteq A}\) zachodzi \(\displaystyle{ c(D) \in D}\).

Nie wiem do czego jest ta ostatnia informacja. Ja zalozylem, ze skoro funkcje f i g sa "na", to maja ten sam zbior wartosci ( i te sama dziedzine, bo biora argumenty z A ). Zatem potrzebujemy funkcji, ktora przeksztalci argumenty dla g na takie, ktore beda dawac te same wartosci dla f co dla g. Czyli \(\displaystyle{ h( x ) = c( f^{-1}(g(x)) )}\). Funkcja \(\displaystyle{ c}\) wybiera jeden argument z przeciwobrazu dla danej wartosci. Czy to jest ok ?

2) Czy dana funkcja jest "na" ?
\(\displaystyle{ f: P( N \times N ) \to P( N )}\), ze
\(\displaystyle{ f(r) = \{ k \ | \ \exists x \exists y \ ( <x,y> \in r^{k+1} \wedge <a,x> \not\in r \ \wedge <y,b> \not\in r ) \}}\)

Wydawalo mi sie, ze jest, natomiast nie jestem w stanie skonstruowac zadnego "zestawu" relacji, ktore by dawaly "po kolei" podzbiory N ( udalo mi sie skonstruowac taka, ktora daje cale N a tu chyba nalezy stworzyc zestaw dajacy \(\displaystyle{ P(N)}\) ).


Z gory dziekuje za pomoc.

[macciej91]

1) f,g są tylko na, nie ma nic o różnowartościowości, więc nie możesz korzystać z własności funkcji odwrtonych.

[M4ksiu]

I dlatego masz wlasnie funkcje c ( dana w zadaniu ). Bardziej precyzyjne tlumaczenie funkcji h. Jest to funkcja, ktora wybiera jeden argument ( to robi funkcja c ) z posrod tych, dla ktorych funkcja f przyjmuje wartosc funkcji g w punkcie x.

[Heniek1991]

Opracowałem dowód drugiego.

Mamy \(\displaystyle{ f : P(NxN) -> P(N)}\) Funkcja f jest na wtw gdy dla każdego \(\displaystyle{ X \in P(N)}\) istnieje \(\displaystyle{ r \in P(NxN)}\)takie, że\(\displaystyle{ f(r)=X}\)

Weźmy dowolne \(\displaystyle{ X \in P(N)}\) i wskażmy konkretne r. \(\displaystyle{ X \in P(N)}\) czyli \(\displaystyle{ X \subseteq N}\). Niech \(\displaystyle{ X = \left\{ n\right\} \subseteq N}\) Wtedy istnieje \(\displaystyle{ r = \left\{ (0,1), (1,2), ... , (n-1,n) (n, n+1)\right\}}\) takie ze\(\displaystyle{ f(r)={n}}\)

[macciej91]

M4ksiu: nie rozumiesz.
Nie możesz korzystać z funkcji odwrotnych do f i g (co robisz) gdy one nie istnieją (bo nie jest nigdzie powiedziane, że te funkcje są różnowartościowe).

Heniek1991: twój dowód dotyczy tylko "na" N. Natomiast nic nie mówi o "na" P(N).

[M4ksiu]

Opracowałem dowód drugiego.

Mamy \(\displaystyle{ f : P(NxN) -> P(N)}\) Funkcja f jest na wtw gdy dla każdego \(\displaystyle{ X \in P(N)}\) istnieje \(\displaystyle{ r \in P(NxN)}\)takie, że\(\displaystyle{ f(r)=X}\)

Weźmy dowolne \(\displaystyle{ X \in P(N)}\) i wskażmy konkretne r. \(\displaystyle{ X \in P(N)}\) czyli \(\displaystyle{ X \subseteq N}\). Niech \(\displaystyle{ X = \left\{ n\right\} \subseteq N}\) Wtedy istnieje \(\displaystyle{ r = \left\{ (0,1), (1,2), ... , (n-1,n) (n, n+1)\right\}}\) takie ze\(\displaystyle{ f(r)={n}}\)

Czy przypadkiem nie pokazujesz tego tylko dla singletonow ? Zbior potegowy nie sklada sie z samych singletonow a takowy mamy "znalezc" ( w takim sensie, ze kazdy element zbioru potegowego ma byc wynikiem dzialania funkcji z argumentem r ).

[Heniek1991]

A racja, czyli muszę zmienić dwa ostatnie zdania. Mógłbym prosić o jakąś wskazówkę

[M4ksiu]

M4ksiu: nie rozumiesz.
Nie możesz korzystać z funkcji odwrotnych do f i g (co robisz) gdy one nie istnieją (bo nie jest nigdzie powiedziane, że te funkcje są różnowartościowe).

Heniek1991: twój dowód dotyczy tylko "na" N. Natomiast nic nie mówi o "na" P(N).

Nie widze, dlaczego nie. Jedyna roznica przy funkcjach odwrotnych dla 1-1 a nie dla 1-1 jest taka, ze przy funkcji roznowartosciowej kazde \(\displaystyle{ f^{-1}( x )}\) jest jednoelementowe a w drugim przypadku tak nie jest. Funkcja c wybiera jakis element z tych, z przeciwobrazu dla danej wartosci.

[Heniek1991]

Skoro \(\displaystyle{ X \subseteq N}\) to, wezmy dowolny \(\displaystyle{ x \in X}\) i \(\displaystyle{ x \in N}\) Mogę napisać, że biorę x=n i wtedy moja relacja \(\displaystyle{ r = \left\{ (0,1), (1,2), ... , (n-1,n) (n, n+1)\right\}}\) takie ze\(\displaystyle{ f(r)={n}}\)

moze w ten sposób?

M4ksiu obraz i przeciwobraz dotyczą zbiorów, dlatego jak piszesz "małe x" to ludzie myślą o f odwrotnej

[M4ksiu]

Moj blad. Mialem na mysli cos w stylu \(\displaystyle{ \{ g( x ) \}}\) ( singleton wartosci w punkcie x ), czyli przeciwobraz a nie funkcje odwrotna.

A moze ktos wie, czy istnieje relacja nieprzechodnia, ktora daje \(\displaystyle{ f( r ) = \{ 0 \}}\) ? Odpowiedzia jest nie ( wedlug mnie ), ale dowod nie wydaje sie taki trywialny. Probowalem to udowodnic przez definicje funkcji przechodniej i definicji funkcji f, ale to nie objemuje przypadkow, kiedy mamy np. zbior { 0, 1 }.

[Heniek1991]

Skorzystaj z tego, że relacja jest nieprzechodnia gdy implikacja \(\displaystyle{ (x,z) \in r \wedge (z,y) \in r \Rightarrow (x,y) \in r}\) jest niespełniona.

No, a zrobiłeś to zadanie z funkcją na??

[M4ksiu]

Nie zrobilem. A z tego wlasnie korzystalem. Podjalem probe rozwiazania zadania z tej definicji i z definicji funkcji, ale jakos to nie wyszlo. Teraz kombinuje z sama ta definicja w taki sposob:
1) r-nieprzechodnia, wiec arb i brc ale nie arc ( dla przynajmniej jednej trojki a, b, c ).
2) przy r^2 mamy przynajmniej arc w takim wypadku.
Tu zastanawiam sie, czy nie moze byc sytuacji, kiedy arc zostanie wykluczony z wyniku przez warunek funkcji.

[Jan Kraszewski]

Ja bym zaczął od tego, że definicja funkcji \(\displaystyle{ f}\) jest formalnie niepoprawna - występują zmienne wolne \(\displaystyle{ a}\) i \(\displaystyle{ b}\), niejasny jest też zapis \(\displaystyle{ \langle x,y\rangle\in r^{k+1}}\).

JK

[Heniek1991]

Powinno być dla każdego a i dla każdego b.

Chodzi, że istnieją x,y takie, że należą do k+1 - krotnego złożenia relacji r.

[M4ksiu]

Dokladnie tak jak mowi Heniek, panie Kraszewski.