Matematyka.pl

Jak pokazać, że jeśli \(\displaystyle{ f:X \rightarrow X}\) suriekcja i \(\displaystyle{ X}\) skończony, to \(\displaystyle{ f}\) iniekcja?

Formalnie? Indukcją po mocy \(\displaystyle{ X}\).

JK

\(\displaystyle{ f:X \rightarrow X}\)
\(\displaystyle{ n+1=|X|}\)
\(\displaystyle{ x_s,x_t \in X,x_s \neq x_t}\)
\(\displaystyle{ t \neq s}\)
\(\displaystyle{ x_s=f(x_k),x_t=f(x_m),x_k,x_m \in X}\)
\(\displaystyle{ x_k \neq x_m}\)
\(\displaystyle{ k \neq m}\)
Tylko nie wiem jak wykorzystać tutaj założenie indukcyjne.

A co to za znaczki? Dowód zapisujemy zdaniami w języku polskim, a nie samymi znaczkami.

JK

Założyłem, że \(\displaystyle{ X}\) ma \(\displaystyle{ n+1}\) elementów i \(\displaystyle{ f}\) jest suriekcją tylko nie widzę jak wykorzystać założenie indukcyjne.-- 14 cze 2014, o 20:08 --Wie ktoś jak to zrobić?

Myślę, że dobrze wzmocnić w ogóle tezę do \(\displaystyle{ f: X \rightarrow Y}\), przy czym \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) skończone, oraz \(\displaystyle{ \left| X\right|=\left| Y\right|}\). 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ą.

Nie robiłbym tego indukcyjnie. Raczej skorzystałbym z dowodu nie wprost.
Niech zbiór X będzie zbiorem n-elementowym i f jest suriekcją.
Załóżmy, że f nie jest iniekcją. To znaczy, że istnieją takie
\(\displaystyle{ x_1 ,x_2 \in X x_1 \neq x_2 \wedge f(x_1)=f(x_2))}\)
Wykorzystaliśmy już dwa argumenty i jedną wartość funkcji.
Pozostało nam n-2 argumenty i n-1 wartości funkcji.
Argumentów jest mniej niż wartości funkcji. Czyli funkcja nie może być suriekcją, a to jest sprzeczne z założeniem. Więc nasze twierdzenie jest prawdziwe.
Pozdrawiam.

Według mnie bezwzględny formalizm indukcji pozwala uniknąć wrednych próśb o wyjaśnienie takich:

Marmat pisze:Argumentów jest mniej niż wartości funkcji. Czyli funkcja nie może być suriekcją

oczywistości.

No niestety, formalny dowód bez indukcji nie pójdzie. Dowód Marmata to dowód na zasadzie: "no przecież widać, że to oczywiste". Ale oczywistości też trzeba dowodzić.

JK

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.

Wyprowadź powyższe stwierdzenie czysto formalnie z definicji.

Ja jednak pozostanę przy tym co jest w zadaniu tj. \(\displaystyle{ f:X \rightarrow X}\). Tak więc jak w tym przypadku wykorzystać założenie indukcyjne?

Musisz zrobić mniej więcej to samo, co Ponewor, ale będziesz musiał bardziej się nagimnastykować - nie wystarczy usunąć po jednym elemencie, trzeba jeszcze będzie przerobić tę nową funkcję, by była ze zbioru w ten sam zbiór.

Czasem właśnie po to uogólnia się twierdzenia, by dowód był prostszy.

JK

A tak w ogóle to skoro nie wiemy, że \(\displaystyle{ f:X \rightarrow X}\) jest iniekcją to skąd wiadomo, że dla dowolnego \(\displaystyle{ x}\) z \(\displaystyle{ X}\) istnieje taka funkcja \(\displaystyle{ g:X \setminus\left\{ x\right\} \rightarrow X \setminus \left\{ f(x)\right\}}\), która jest dana tym samym wzorem co \(\displaystyle{ f}\)?

Bo to obcięcie funkcji \(\displaystyle{ f}\) do \(\displaystyle{ X \setminus \{x\}}\). Problem polega na tym, że dla takiej funkcji \(\displaystyle{ g}\) nie możesz jeszcze skorzystać z zał. indukcyjnego (bo ono dotyczy funkcji, których dziedzina i przeciwdziedzina są identyczne). Dlatego łatwiej jest zrobić tak, jak proponował Ponewor.

JK