Školjka

%V0 Neka je $a_1<a_2<...<a_n<...$ skup brojeva takvih da postoji $x$ takav da je $f(x_i)=a_i \forall i$ Uzmimo $x:f(x)=a_1$ Ako $x>1$ tada $f(x)>f(f(x-1)) \newline a_1>f(f(x-1))$ Kontradikcija! Dakle $x=1$ Uzmimo sada $x:f(x)=a_2$ $f(x)>f(f(x-1)) \newline a_2 > f(f(x-1)) \newline f(f(x-1))=a_1 \newline f(x-1)=1$ To znaci da je broj $1$ pogoden funkcijom, pa je ocito $a_1=1$ $f(f(x-1))=1 \newline f(x-1)=1 \newline x-1=1 \newline x=2$ Pretpostavimo sada za indukciju da smo pokazali da je $f(1)=a_1,f(2)=a_2,...,f(n)=a_n$ i $a_1=1,...,a_{n-1}=n-1$ I da $f(x)=a_i \Rightarrow x=i \forall i \leqslant n$ Uzmimo $x:f(x)=a_{n+1}$ $f(x)>f(f(x-1)) \newline f(f(x-1)) \in \{a_1,...,a_n\} \newline f(x-1) \in \{1,...,n\}$ Kada bi $f(x-1)<n$ tada $x<n+1$ pa $f(x)<a_{n+1}$ Kontradikcija! Dakle $f(x-1)=n$ pa je $a_n=n$ $f(x-1)=n=a_n \newline x-1 =n \newline x=n+1$ Time smo dovrsili korak indukcije i pokazali da je jedina funkcija $f(n)=n$