# Proving that for every computable function f: N → N, there exists a computable function g: N → N such that for every n we have f(n) ≤ g(n)

Prove that for every computable function $f \colon \mathbb N \to \mathbb N$, there exists a computable function $g \colon \mathbb N \to \mathbb N$ such that for every $n$ we have $f(n) ≤ g(n)$.

Can anyone please explain me, why my proof below is not correct?

• Lets assume, for the sake of arriving at a contradiction, that there exists a computable function $f$ such that for every computable function $g$, there
exists an $n$ such that $f(n) > g(n)$.

• For each computable function $g$, let $n(g)$ be the smallest $n$ such that $f(n) > g(n)$. Let $n_0$ be the maximum of $n(g)$ over all computable functions $g$, and assume that this maximum is achieved for $g_0$, that is, $n(g_0) = n_0$.

• Define a function $g_1$ that is equal to $g_0$ for all values except for $n_0$, and for $n_0$ we have $g_1(n_0) = f(n_0)$. This function $g_1$ is computable because $g_0$ is computable and $g_1$ differs from $g_0$ in only one point. By definition, $n(g_1) ≥ n(g_0) + 1$, and this contradicts the fact that $n(g)$ was maximized at $g_0$.

• Um. Just take $g=f$. And if you change the requirement to $f(n)<g(n)$, take $g(n)=f(n)+1$. – David Richerby May 7 '18 at 12:14

The problem with your proof is in the definition of $n_0$. The function $n(g)$ can be unbounded (as a function of $g$).
A much simpler proof would be to take $g = f$.