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) &gt; g(n)$.


  For each computable function $g$, let $n(g)$ be the smallest $n$ such that $f(n) &gt; 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$.
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$.