Matematyka.pl

Hm, ja mam napisane, że obcięcie funkcji \(\displaystyle{ f:X \rightarrow X}\) do \(\displaystyle{ X \setminus \left\{ x\right\}}\) to jest taka funkcja \(\displaystyle{ g:X \setminus \left\{ x\right\} \rightarrow X}\) że dla każdego \(\displaystyle{ y}\) z \(\displaystyle{ X \setminus \left\{ x\right\}}\) zachodzi \(\displaystyle{ g(y)=f(y)}\). Jednak tutaj nie tylko jest obcięta dziedzina funkcji ale i przeciwdziedzina, więc skąd wiemy, że tak się da zrobić jak nie wiemy czy \(\displaystyle{ f}\) jest iniekcją?

Jednak tutaj nie tylko jest obcięta dziedzina funkcji ale i przeciwdziedzina, więc skąd wiemy, że tak się da zrobić jak nie wiemy czy f jest iniekcją?

Świetne pytanie. To zawiera się w tym:

Teraz jak rozważysz funkcję \(\displaystyle{ f:X \setminus \left\{ x\right\} \rightarrow Y \setminus \left\{ y\right\}}\) i uzasadnisz, że ta funkcja również jest suriekcją

To nie jest takie proste.

Ponewor pisze:Z przeciwdziedziny wybierasz sobie jakiś element \(\displaystyle{ y}\). Z założenia o tym, że nasza funkcja jest suriekcją istnieje w dziedzinie element \(\displaystyle{ x}\) dla którego \(\displaystyle{ f\left(x\right)=y}\). Teraz jak rozważysz funkcję \(\displaystyle{ f:X \setminus \left\{ x\right\} \rightarrow Y \setminus \left\{ y\right\}}\) i uzasadnisz, że ta funkcja również jest suriekcją, to będziesz mógł skorzystać z założenia indukcyjnego i stwierdzić, że jest iniekcją.

Może się okazać, że nie tylko \(\displaystyle{ x}\) przechodzi na \(\displaystyle{ y}\) i wtedy funkcja \(\displaystyle{ f:X \setminus \left\{ x\right\} \rightarrow Y \setminus \left\{ y\right\}}\) nie jest dobrze zdefiniowana.

Trzeba to zatem zrobić uważniej.

JK

\(\displaystyle{ f:X \rightarrow Y}\) suriekcja, \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) mają tyle samo elementów. \(\displaystyle{ g:X \setminus \left\{ x \in X:y=f(x)\right\} \rightarrow Y \setminus \left\{ y\right\},y \in Y}\) dana wzorem \(\displaystyle{ g(x)=f(x)}\) jest chyba dobrze zdefiniowana tylko teraz z kolei nie wiadomo czy dziedzina i przeciwdziedzina mają tyle samo elementów. Jak więc tutaj można wykorzystać założenie indukcyjne?

To w takim razie skoro nie ma wskazówek jak to zrobić dla \(\displaystyle{ f:X \rightarrow X}\) to czy mógłby ktoś powiedzieć jak to zrobić dla \(\displaystyle{ f:X \rightarrow Y}\) gdzie \(\displaystyle{ |X|=|Y|}\)?
Z założenia mamy \(\displaystyle{ |X|=|Y|=n+1}\) oraz wiemy, że \(\displaystyle{ f:X \rightarrow Y}\) suriekcja i trzeba pokazać, że \(\displaystyle{ f}\) jest iniekcją. No ale żeby skorzystać z założenia indukcyjnego to trzeba mieć zbiory o mniejszej liczbie elementów i funkcję między nimi o której wiemy, że jest suriekcją.

Jakieś wskazówki?

Pomysł z wzięciem \(\displaystyle{ g}\) jest dobry.

Pokaż najpierw, że dla wybranego \(\displaystyle{ y_0}\) oraz \(\displaystyle{ X_0:=f^{-1}(\{y_0\})}\) funkcja
jest istotnie surjekcją. To jest pierwszy krok na drodze do indukcji.

Drugi krok to wykazanie, że istotnie \(\displaystyle{ X_0}\) jest jednoelementowy, co pozwoli stwierdzić, że funkcja \(\displaystyle{ g}\) działa pomiędzy zbiorami o tej samej mocy, a to pozwoli skorzystać z założenia indukcyjnego i tym samym niemal dowieść tezy.

Marmat pisze:Ale przecież z definicji funkcji moc zbioru wartości jest mniejsza lub równa mocy dziedziny.
Nie może być od niej większa , gdyż przeczy to definicji funkcji. Każdemu argumentowi przyporządkowana jest dokładnie jedna wartość funkcji więc wartości jest co najwyżej tyle ile argumentów.

Ta oczywistość będąca istotną własnością funkcji może być rozwiązana na dwa sposoby:

1. Jest to fakt dla Ciebie znany i dowiedziony.

2. Jest to fakt do udowodnienia. Istotnie, definicja przyda się w dowodzie, ale trzeba to jakoś zapisać.

Trzeci krok to wykazanie, że \(\displaystyle{ f}\) jest bijekcją (tak, to też trzeba jakoś uzasadnić). Z tym nie powinno być kłopotu.

Założyłem, że \(\displaystyle{ n \ge 1}\), bo dla \(\displaystyle{ n=0}\) jest trywialne.
Suriektywność \(\displaystyle{ g}\) jest oczywista tylko problem mam z wykazaniem, że \(\displaystyle{ |X_0|=1}\).
Z suriektywności \(\displaystyle{ f}\) i założenia \(\displaystyle{ |X|=n+1}\) dostaję, że \(\displaystyle{ 1 \le |X_0| \le n}\), a więc dla pewnego naturalnego \(\displaystyle{ k}\) jest \(\displaystyle{ f(x_1)=f(x_2)=...=f(x_k)=y_0}\) gdzie te \(\displaystyle{ x_1,...,x_k}\) są parami różne między sobą oraz \(\displaystyle{ f(x_{k+1}) \neq y_0,f(x_{k+2}) \neq y_0,...,f(x_{n+1}) \neq y_0}\) gdzie \(\displaystyle{ x_{k+1},...,x_{n+1}}\) są parami różne między sobą, a to daje mi \(\displaystyle{ f(x_i) \neq f(x_j)}\) dla \(\displaystyle{ 1 \le i \le k, k+1 \le j \le n+1}\).


Tylko nie wiem jak stąd wywnioskować, że \(\displaystyle{ k=1}\) . Mógłbyś podpowiedzieć?

Gdyby \(\displaystyle{ k>1}\), tzn \(\displaystyle{ |X\setminus X_0|\leq n-2}\), to mamy surjekcję zbioru co najwyżej \(\displaystyle{ n-2}\) elementowego w zbiór \(\displaystyle{ n-1}\) elementowy \(\displaystyle{ Y\setminus \{y_0\}}\). Ale wiadomo (?), że to jest niemożliwe, gdyż obraz nie może być liczniejszy od zbioru, którego obraz bierzemy. Stąd \(\displaystyle{ k=1}\).

Powyższe jest wystarczające (chyba, że inni dyskutanci wyrażą inne zdanie) o ile:

moc zbioru wartości jest mniejsza lub równa mocy dziedziny.
Nie może być od niej większa , gdyż przeczy to definicji funkcji. Każdemu argumentowi przyporządkowana jest dokładnie jedna wartość funkcji więc wartości jest co najwyżej tyle ile argumentów.

nie wymaga to dalszego uzasadniania.

A końcówka tego zadania będzie wyglądała tak, że \(\displaystyle{ f}\) jest iniekcją, bo \(\displaystyle{ f=g \cup h}\) gdzie \(\displaystyle{ h:X_0 \rightarrow \left\{ y_0\right\}}\)?

Może zaproponuję inny dowód omiawanego twierdzenia. Nie jest to dowód indukcyjny, ale będę korzystać z równoważnej definicji zbioru skończonego: Zbiór jest skończony wtedy i tylko wtedy, gdy nie jest równoliczny z żadnym swoim podzbiorem właściwym. W pewnym sensie jest to ten sam dowód, który przestawił Marmat. Będę korystał z tw. Cantora-Bernsteina oraz z cytowanego już faktu, że moc zbioru wartości jest mniejsza bądź równa mocy dziedziny.

Dowód: Przypuśćmy, że \(\displaystyle{ f}\) nie jest iniekcją. Istnieją \(\displaystyle{ x\neq y}\) takie, że \(\displaystyle{ f(x)=f(y)}\). Wobec tego \(\displaystyle{ f}\) obcięta do zbioru \(\displaystyle{ A=X\setminus\{y\}}\) jest suriekcją na \(\displaystyle{ X}\), czyli \(\displaystyle{ |A|\ge |X|}\). Z drugiej strony \(\displaystyle{ A}\) jest podzbiorem \(\displaystyle{ X}\), więc \(\displaystyle{ |A|\le|X|}\). Z tw. C-B \(\displaystyle{ |A|=|X|}\), co jest niemożliwe bo \(\displaystyle{ X}\) jest skończony, a \(\displaystyle{ A}\) jest jego podzbiorem właściwym.

rozprzedstud pisze:A końcówka tego zadania będzie wyglądała tak, że \(\displaystyle{ f}\) jest iniekcją, bo \(\displaystyle{ f=g \cup h}\) gdzie \(\displaystyle{ h:X_0 \rightarrow \left\{ y_0\right\}}\)?

Jeśli pytasz o formalne uzasadnienie, to nie. Coś tyko napisałeś i nie za bardzo wiadomo, co z tego wynika albo jak wynika z tego to, co powinno.

Iniektywność wynika z tego, że \(\displaystyle{ g}\) jest bijekcją oraz że \(\displaystyle{ f^{-1}(y_0)=X_0}\) i \(\displaystyle{ X\setminus X_0\cap X_0=\emptyset}\). Ale jak wynika? Tutaj znów wszystko zależy od stopnia wiedzy - jeżeli masz pokazać to z definicji, to powinieneś wziąć dwa elementy \(\displaystyle{ x_1, x_2\in X}\) i pokazać, że \(\displaystyle{ f(x_1)\neq f(x_2)}\). Będą tutaj dwa proste przypadki - albo \(\displaystyle{ x_1\in X_0}\), albo \(\displaystyle{ x_1\notin X_0}\).

Skoro wiemy już, że \(\displaystyle{ g}\) jest bijekcją, \(\displaystyle{ g(x)=f(x)}\) dla \(\displaystyle{ x}\) z \(\displaystyle{ X \setminus X_0}\), \(\displaystyle{ X_0}\) jest jednoelementowy, \(\displaystyle{ f}\) jest suriekcją, więc dla \(\displaystyle{ y_0}\) istnieje \(\displaystyle{ x_0}\) w \(\displaystyle{ X_0}\), że \(\displaystyle{ f(x_0)=y_0}\), więc jak napiszę \(\displaystyle{ h:X_0 \rightarrow \left\{ y_0\right\}}\) to wiadomo, że \(\displaystyle{ h(x)=f(x)}\) dla tego jedynego \(\displaystyle{ x}\) z \(\displaystyle{ X_0}\). Dziedziny i przeciwdziedziny funkcji \(\displaystyle{ g}\) i \(\displaystyle{ h}\) są rozłączne, obie funkcje są bijekcjami, więc dodając te funkcje otrzymujemy funkcję \(\displaystyle{ g \cup h:X \rightarrow Y}\), która jest bijekcją i zarazem \(\displaystyle{ g \cup h=f}\), więc \(\displaystyle{ f}\) jest bijekcją.

O coś takiego mi chodziło.

Ok, ale aby uniknąć tutaj "machania rękami" należy wspomnieć, że korzystasz tutaj z pewnego twierdzenia - obrazowo mówiąc sklejenie (suma mnogościowa) dwóch bijekcji o rozłącznych dziedzinach i przeciwdziedzinach jest bijekcją. A więc znów powołujemy się na pewien fakt, który niekoniecznie musi być "oczywisty", choć jest "widoczny".

Teoria mnogości to wredny dział matematyki

Ok, dzięki. W każdym razie myślę, że ten fakt jestem w stanie bardziej szczegółowo pokazać.

A mam jeszcze pytanie a propos dowodu tego lematu z którego wypływa ten wniosek, że z suriektywności wynika iniektywność: Jeśli \(\displaystyle{ f:X \rightarrow Y}\) jest funkcją i \(\displaystyle{ X}\) jest skończony, to \(\displaystyle{ |f[X]| \le |X|}\).

Próbuję to pokazać indukcją po liczbie elementów \(\displaystyle{ X}\):

Jeśli \(\displaystyle{ |X|=0}\), to \(\displaystyle{ X=\emptyset}\) i wtedy \(\displaystyle{ f[X]=\emptyset}\), a stąd \(\displaystyle{ |f[X]|=0}\) i mamy \(\displaystyle{ |f[X]| =0 \le 0 = |X|}\), czyli teza zachodzi.
Załóżmy, że teza zachodzi dla \(\displaystyle{ 0\le |X|=k <n+1}\).
Aby wykorzystać założenie indukcyjne potrzebuję mieć dziedzinę mniej liczną od \(\displaystyle{ X}\) i w tym celu rozważam pewne funkcje \(\displaystyle{ g:X_1 \rightarrow Y,h:X_2 \rightarrow Y}\) dane wzorami \(\displaystyle{ g(x)=f(x),h(x)=f(x)}\), gdzie \(\displaystyle{ X_1,X_2 \subset X,X_1,X_2 \neq Y,X_1 \cup X_2=X}\).

I teraz nie wiem co dalej:

Teoretycznie mógłbym sobie wziąć takie funkcje \(\displaystyle{ g,h}\), że \(\displaystyle{ X_1 \cap X_2 =\emptyset}\) i wtedy \(\displaystyle{ g \cup h=f}\), tylko problem jest jak wywnioskować stąd, że \(\displaystyle{ |f[X]| \le |X|}\). Z założenia indukcyjnego mam co prawda, że \(\displaystyle{ |g[X_1]| \le |X_1|,|h[X_2]| \le |X_2|}\) a gdyby \(\displaystyle{ g,h}\) były tak dobrane, że \(\displaystyle{ X_1 \cap X_2 = \emptyset}\), to byłoby \(\displaystyle{ |X|=|X_1 \cup X_2|=|X_1|+|X_2|}\). Dodając z kolei stronami nierówności \(\displaystyle{ |g[X_1]| \le |X_1|,|h[X_2]| \le |X_2|}\) otrzymałbym więc \(\displaystyle{ |g[X_1]|+|h[X_2]| \le |X|}\). Gdyby się udało pokazać, że można wziąć takie \(\displaystyle{ g,h}\), że \(\displaystyle{ |g[X_1]|+|h[X_2]|=|f[X]|}\), to dowód byłby zakończony. Tylko niestety nie wiem czy takie \(\displaystyle{ g,h}\) rzeczywiście zawsze można dobrać, czy po prostu ten tok rozumowania jest błędny.

Mógłbyś podpowiedzieć jak to powinienem dokończyć?

Wzięcie \(\displaystyle{ X_1\cap X_2}\) jest dobrym pomysłem.

Jako \(\displaystyle{ g}\) przyjmujesz \(\displaystyle{ f}\) obcięte do \(\displaystyle{ X_1}\), a \(\displaystyle{ h}\) to \(\displaystyle{ f}\) obcięte do \(\displaystyle{ X_2}\). Wtedy

\(\displaystyle{ |f(X)|=|f(X_1\cup X_2)|=|f|_{X_1}(X_1)\cup f|_{X_2}(X_2)|\leq |f|_{X_1}(X_1)|+|f|_{X_2}(X_2)|\leq |X_1|+|X_2|=|X_1\cup X_2|=|X|.}\)

Jedyny szkopół to tak dobrać \(\displaystyle{ X_1}\) oraz \(\displaystyle{ X_2}\), by żaden z nich nie był pusty. I warto jednak zacząć indukcję w przypadku, gdy \(\displaystyle{ |X|=1}\).

Korzystamy tutaj z indukcji zupełnej, rzecz jasna.