====== Logika - Zadanie 211. ======
Cudowne zadanie! Sam miód!
Tą jedyną funkcją jest identyczność. Pokażemy, że jest monotoniczną bijekcją typu $\mathbb{N}\rightarrow\mathbb{N}$ i że nie istnieje żadna inna taka funkcja. Identyczność to oczywiście funkcja $f$ taka, że $f(x)=x$ dla każdego $x$.
  - Izomorfizmu porządkowego pewnie jeszcze nie znacie, ale każdy wie, że $f$ jest monotoniczna, jeśli dla dowolnych $x_1,x_2$ mamy $x_1\leq x_2\Rightarrow f(x_1)\leq f(x_2)$. No i mamy: $f(x_1)=x_1\leq x_2=f(x_2)$.
  - Bijekcje zwykle są "na". Weźmy dowolne $y\in\mathbb{N}$. Wtedy dla $x=y$ mamy $f(x)=y$, więc identyczność jest "na".
  - Są też różnowartościowe. $x_1\neq x_2 \Rightarrow f(x_1)=x_1\neq x_2=f(x_2)$.
  - No a teraz załóżmy nie wprost, że istnieje taka funkcja z $\mathbb{N}$ w $\mathbb{N}$, która jest monotoniczną bijekcją, ale nie jest identycznością. Czyli: $[\forall x_1,x_2\in\mathbb{N}.x_1\leq x_2\Rightarrow f(x_1)\leq f(x_2)]\wedge[\forall y\in\mathbb{N}.\exists x\in\mathbb{N}.f(x)=y]\wedge[\forall x_1,x_2\in\mathbb{N}.x_1\neq x_2 \Rightarrow f(x_1)\neq f(x_2)]\wedge[\exists x\in\mathbb{N}.f(x)\neq x]$.
    * Weźmy więc tego $x$, dla którego $f(x)\neq x$ i oznaczmy go przez $x_1$.
    * Weźmy też tego $x$, dla którego $f(x)=x_1$, niech to będzie $x_2$.
    * Załóżmy teraz, że $x_1\leq x_2$. Wtedy, $f(x_1)\leq f(x_2)=x_1$.
    * Oznacza to, że istnieje $x_3< x_1$ taki, że $f(x_1)=x_3 \wedge f(x_3)\neq x_3$.
    * Jeśli natomiast $x_2\leq x_1$, to $f(x_2)\leq f(x_1)$.
    * Wtedy $x_1 < f(x_1)$ i to $x_2=x_3<x_1$ taki, że $f(x_3)\neq x_3$.
    * W obydwu przypadkach znajdujemy $x_3$ ostro mniejsze od $x_1$, co w obliczu skończonej ilości liczb naturalnych mniejszych od $x_1$ prowadzi nas indukcyjnie do wniosku, że $f(0)\neq 0$.
    * Niech więc $x_4=f(0)$, a $f(x_5)=0$.
    * $0\leq x_5 \Rightarrow x_4 \leq 0$, a że $x_4\neq 0$, to $x_4<0$, co jest niemożliwe w $\mathbb{N}$. Sprzeczność.

Zadanie dla ambitnych: zrobić ten ostatni podpunkt wprost. :)