szukanie zaawansowane
 [ Posty: 20 ]  Przejdź na stronę 1, 2  Następna strona
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 lis 2011, o 11:52 
Użytkownik

Posty: 148
Lokalizacja: Warszawa
Mam daną funkcję f: X  \rightarrow X taką, że:
f^0 = id_x
f^{n+1} = f^n \circ f
Wskazać, czy istnieje bijekcja f:\mathbb{N}\rightarrow \mathbb{N}, że dla dowolnych m,n: \mathbb{N} jeśli n  \ge 1 to f^n(m)  \neq m.

Jednak trochę nie rozumiem tego. Pierwsza linijka - ok. W drugiej żeby zbudować f^{n+1} muszę wziąć poprzednią i złożyć to z f. I własnie, co to jest ta f? Jest to jakaś dowolna? Czy chodzi o to w zadaniu, żeby własnie znaleźć taką f żeby dla dolnego m,n f^n była bijekcją?

Na przykładzie, weźmy X = \{1,2,2\}. Wtedy definiuję f^0:
f^0(1) = 1
f^0(2) = 2
f^0(3) = 3

Jak zdefiniać np. f^1 zgodnie z tym wzorem indukcji?

Mogę sobie ustalić np f taką, że:
f(3) = 1
f(2) = 2
f(1) = 3

I wtedy f^2 = f^1 \circ f, f^3 = f^2 \circ f itd., czyli za każdym razem składać ją z tą samą f. Czy może z każdym krokiem mogę sobie brać inną f?
Góra
Mężczyzna Offline
PostNapisane: 12 lis 2011, o 18:13 
Administrator

Posty: 21374
Lokalizacja: Wrocław
bemekw napisał(a):
Czy chodzi o to w zadaniu, żeby własnie znaleźć taką f żeby dla dolnego m,n f^n była bijekcją?

Tak, chodzi o to, żeby znaleźć taką funkcję.

bemekw napisał(a):
I wtedy f^2 = f^1 \circ f, f^3 = f^2 \circ f itd., czyli za każdym razem składać ją z tą samą f. Czy może z każdym krokiem mogę sobie brać inną f?

Nie. Funkcja f, jak ją już wybierzesz, jest wybrana "na zawsze", nie możesz jej zmieniać.

JK
Góra
Mężczyzna Offline
PostNapisane: 13 lis 2011, o 11:23 
Użytkownik

Posty: 148
Lokalizacja: Warszawa
Ok, dziękuje, postaram się jakąś wymyślić.
Góra
Mężczyzna Offline
PostNapisane: 13 lis 2011, o 13:25 
Administrator

Posty: 21374
Lokalizacja: Wrocław
Jest taka jedna, bardzo prosta...

JK
Góra
Mężczyzna Offline
PostNapisane: 13 lis 2011, o 13:34 
Użytkownik
Avatar użytkownika

Posty: 401
Lokalizacja: Warszawa-Praga
Też myślę nad tym zadaniem. Jaki można podać przykład??
Góra
Mężczyzna Offline
PostNapisane: 13 lis 2011, o 14:14 
Administrator

Posty: 21374
Lokalizacja: Wrocław
Jan Kraszewski napisał(a):
Jest taka jedna, bardzo prosta...

Przepraszam, po uważniejszej lekturze zadania cofam swoje optymistyczne stwierdzenie.

JK
Góra
Mężczyzna Offline
PostNapisane: 13 lis 2011, o 14:30 
Użytkownik

Posty: 1272
Lokalizacja: Warszawa
w takim razie trzeba jakoś pokazać, że po którymś złożeniu (mi ciągle wychodzą tylko dwa złożenia, ale chyba tak łatwo zawsze nie ma) otrzymamy funkcję identycznościową? f^0 mamy identycznościową, jak tworzymy f^1 to po prostu będzie to nasza wymyślona funkcja i.. po iluś złożeniach chyba zawsze otrzymamy identycznościową?
Góra
Mężczyzna Offline
PostNapisane: 13 lis 2011, o 19:26 
Użytkownik

Posty: 110
Lokalizacja: Warszawa
Nie wiem, czy zmienia to coś w zadaniu, ale poprawne polecenie na końcu treści zadania brzmi:

Wskazać, czy istnieje bijekcja f:\mathbb{N}\mathop{\xrightarrow{1-1}}_{na} \mathbb{N}, że dla dowolnych m,n: \mathbb{N}, jeśli n \ge 1 to f^n(m) \neq m
Góra
Mężczyzna Offline
PostNapisane: 13 lis 2011, o 19:31 
Użytkownik

Posty: 635
Lokalizacja: Białystok / Warszawa
Oznaczenie f:\mathbb{N}\mathop{\xrightarrow{1-1}}_{na} \mathbb{N} już samo w sobie oznacza, że f jest bijekcją(funkcją 1-1 i na).
Góra
Mężczyzna Offline
PostNapisane: 13 lis 2011, o 20:21 
Użytkownik

Posty: 1272
Lokalizacja: Warszawa
i stoimy w miejscu :P
czy ktoś jeszcze uważa, że zawsze po którymś złożeniu otrzymamy identyczność, co znaczy że taka bijekcja nie istnieje? jakieś pomysły na dowód?
Góra
Mężczyzna Offline
PostNapisane: 13 lis 2011, o 20:33 
Użytkownik

Posty: 9836
Lokalizacja: Bydgoszcz
f(x)= \begin{cases}x-2 \ \textrm{dla}\ x \ \textrm{parzystych dodatnich}\\ x+2\ \textrm{dla}\ x \ \textrm{nieparzystych}\\ 1 \ \textrm{dla}\ x =0\end{cases}

Q.
Góra
Mężczyzna Offline
PostNapisane: 13 lis 2011, o 21:08 
Użytkownik

Posty: 1272
Lokalizacja: Warszawa
kurcze.. niesamowite, to działa! ;)
ja pierwsze o czym pomyślałem, to taka sama konstrukcja tyle, że x-1 oraz x+1, ale szybko się zniechęciłem.. na jakiej zasadzie wpadłeś na coś takiego? a dowód, że to zawsze będzie działać, byłby bardzo trudny?
Góra
Mężczyzna Offline
PostNapisane: 13 lis 2011, o 21:33 
Użytkownik

Posty: 9836
Lokalizacja: Bydgoszcz
Pomysł wbrew pozorom jest bardzo prosty. Wyobraźmy sobie, że każda liczba naturalna to punkt (czy jak kto woli: wierzchołek grafu). Łączymy te punkty strzałkami (czy jak kto woli: skierowanymi krawędziami), tak, żeby strzałki szły od argumentu do wartości funkcji.

Warunki, które muszą być spełnione to:
- od każdego punktu wychodzi dokładnie jedna strzałka (bo f jest funkcją)
- do każdego punktu dochodzi dokładnie jedna strzałka (bo f jest bijekcją)
- dodatkowy warunek narzuca nam to, że nie ma żadnych cykli, tzn. takich serii strzałek, że początek pierwszej i koniec ostatniej to ten sam punkt (w szczególności więc żadna strzałka nie idzie z punktu do samego siebie).

Widać, że na przykład funkcja f(x)=x+1 jest prawie dobra, ale tylko "prawie", bo do zera nie dochodzi żadna strzałka. Próba banalnego naprawienia tej usterki powoduje, że pojawia się cykl. Okazuje się jednak, że jeśli podzielimy zbiór liczb naturalnych na dwa nieskończone podzbiory i w jednym strzałki będą szły "w dół", a w drugim "w górę", to jest ok. Podany wzór to jedynie sformalizowanie tego pomysłu.

Formalny dowód, że to jest bijekcja i do tego spełniająca podany warunek jest bardzo łatwy i nie w tym dowodzie leżała trudność zadania.

Q.
Góra
Mężczyzna Offline
PostNapisane: 13 lis 2011, o 22:15 
Użytkownik

Posty: 112
Lokalizacja: Warszawa
Czy można znaleźć również inne takie funkcje - to znaczy czy istnieje tylko jedna taka bijekcja czy więcej - odwołujących się do np. podzielności przez inną liczbę, a nie parzystości, jak w przypadku tej ,,dobrej'' funkcji? Czy podzielenie na trzy lub cztery nieskończone podzbiory by zadziałało i otrzymałbym inną spełniającą warunki zadania funkcję? Wydaje mi się że nie, ale wolę zapytać...
Góra
Mężczyzna Offline
PostNapisane: 13 lis 2011, o 22:24 
Użytkownik

Posty: 1272
Lokalizacja: Warszawa
to, że jest to bijekcja umiem pokazać z definicji.. jednak zastanawiam się, jak ściśle zapisać, że jest to funkcja spełniająca: \forall_{m,n\in\mathbb{N}} \ f^n(m) \neq m..

intuicja jest taka, że na początku dla każdego m\in\mathbb{N} mamy f(m)\neq m co jest oczywiste.. powiedzmy, że zaczynamy wędrówkę w wierzchołku grafu reprezentującym liczbę parzystą m.. w drugim kroku składając tą funkcję z samą sobą dany wierzchołek łączymy z wartością m-2, co tymbardziej zapewnia nam brak identyczności.. kroki te powtarzamy do napotkania wierzchołka 0.. i tutaj jesteśmy tymbardziej uratowani bo następną strzałkę poprowadzimy do 1, z czego wynika że dalsza droga już zawsze będzie prowadziła poprzez wierzchołki reprezentujące liczby nieparzyste.. dlatego skoro zaczęliśmy od parzystej to nigdy nie natrafimy idąc w ten sposób na sytuację kiedy wartość złożenia funkcji od tego parzystego argumentu jest równa temu argumentowi, bo będzie ona nieparzysta..

z kolei rozpoczynając wędrówkę z zera, albo liczby nieparzystej brak identyczności na początku również zapewnia nam różnowartościowość przedstawionej funkcji, a sytuacja od razu staje się dla nas korzystna, bo w każdym następnym kroku będziemy szli do wierzchołka "nieparzystego", a co więcej - o wartości większej o dwa.. także również nie natrafimy na identyczność.. taki przykład: f(1)=3, \ f^2(1)=5, \ f^3(1)=7.. itd, dobrze zrozumiałem?

ale ściśle rzecz biorąc.. indukcja? bo szczerze nie wiem jak to zapisać..
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 20 ]  Przejdź na stronę 1, 2  Następna strona


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Sprawdz czy funkcja jest injekcja, suriekcja,bijekcja  Stopro  4
 bijekcja w odwzorowaniu R na R^2  rubo88  6
 złozenie funkcji czy istnieje  zaq1  4
 Pokaż, że f jest bijekcją i znajdź f  laser15  1
 czy istnieje takie twierdzenie?  izaizaiza  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl