It's just some random thoughts, but I find it confusing.
Here's the classical "prove" that every natural number can be described within eleven words:
Suppose not, then there's a smallest counterexample $n$. Then $n$ can be described as "the smallest natural number that cannot be described within eleven words", which is itself in eleven words, contradiction.
Of course, the proof above is false. But when I tried to do the same thing mathematically, something confusing happened. Suppose $f$ is an arbitrary injective function $f: \mathbb{N} \to \mathbb{N}$. Let $h$ be a bijection from "all finite logical formula" to $\mathbb{N}$. Let $\varphi_n$ denote the formula with $f(h(\varphi_n))=n$. For some $M \in \mathbb{N}$ let $p \in \mathbb{N}$ such that
$$\varphi_p(x) = \neg\exists m\in\mathbb{N}(m<M \wedge \varphi_m(x) \wedge \neg\exists y\in\mathbb{N}(\varphi_m(y))) \wedge\\ \forall y\in\mathbb{N}(y<x \to \exists m\in\mathbb{N}(m<M \wedge \varphi_m(y) \wedge \neg\exists z\in\mathbb{N}(\varphi_m(z))))$$
($x$ is the smallest natural number such that there is no formula $\varphi_m$ with $m<M$ such that $\varphi_m$ "accurately describes" $x$, i.e. $x$ is the only natural number that satisfies $\varphi_m$.)
Let us first assume that $p < M$. If there is an $y \in \mathbb{N}$ that $\neg\exists m\in\mathbb{N}(m<M \wedge \varphi_m(y))$, let $y$ be the smallest such number. Then $\varphi_p(y)$, but $p < M$, contradiction! Therefore every natural number can be accurately described with some formula $\varphi_m$ with $m<M$, but the number of such formula is finite, contradiction! So $p \ge M$.
What does this mean? We have found, constructively, a function $h^{-1} \circ p: \mathbb{N} \to \mathbb{N}$ injective, such that $f(h(h^{-1}(p(M)))) \ge M$ which is $f(p(M)) \ge M$, for every $M$. This is very counter-intuitive, since such a $p$ is usually found inductively.
Is there something wrong in the above construction?