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$.

  • 7
    $\begingroup$ Um. Just take $g=f$. And if you change the requirement to $f(n)<g(n)$, take $g(n)=f(n)+1$. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.