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.

1. 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).
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”.
3. Są też różnowartościowe. x_1\neq x_2 \Rightarrow f(x_1)=x_1\neq x_2=f(x_2).
4. 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. :)