2
$\begingroup$

I am working on the following homework problem for a logic class on Godel's incompleteness theorems and the following question is asked.

Is the converse of Theorem $13.1$ true? Explain.

Theorem 13.1 states, "If a function is $\Sigma_{1}$ it is also $\Pi_{1}$." So, we are asked to prove or disprove that, "If a function is $\Pi_{1}$ it is also $\Sigma_{1}$." I think that the converse is true and I have attempted the question by giving the following "proof",

Assume that $f$ is a $\Pi_{1}$ function. That is, $f$ can be expressed by a strictly $\Pi_{1}$ wff. Let $\Phi(x,y):=\forall \eta_{1} \cdot \cdot \cdot \forall \eta_{k} \varphi(x,y)$ be such a $\Pi_{1}$ wff, where $\varphi(x,y)$ is $\Delta_{0}$. Well, by DeMorgan's law for quantifiers, we have that $\forall \eta_{1} \cdot \cdot \cdot \forall \eta_{k} \varphi(x,y) \equiv \exists \eta_{1} \cdot \cdot \cdot \exists \eta_{k} \neg \varphi(x,y)$, where $\neg \varphi(x,y)$ is again $\Delta_{0}$. So, $\Phi(x,y) = \exists \eta_{1} \cdot \cdot \cdot \exists \eta_{k} \neg \varphi(x,y)$ still expresses $f$ and so since $\Phi(x,y)$ is not only $\Pi_{1}$, but $\Sigma_{1}$, we conclude that $f$ is also $\Sigma_{1}$.

This seems to be a sufficient argument for my tastes (disregard my idiotic proof), but the proof the book gave for Theorem 13.1 seems to be of quite a different style, I will post it here:

Suppose the one-place function $f$ can be expressed by the strictly $\Sigma_{1}$ wff $\varphi(x,y)$. Since $f$ is a function, and maps numbers of unique values, we have $f(m) =n$ if and only if $\forall z ( f(m) = z \rightarrow z = n)$. Hence $f(m)=n$ if and only if $\forall z(\varphi(\bar{m},z) \rightarrow z= \bar{n})$ is true. In other words, $f$ is equally well expressed by $\forall z(\varphi(x,z) \rightarrow z=y)$. But it is a trivial exercise of moving quantifiers around to show that if $\varphi(x,y)$ is strictly $\Sigma_{1}$, then $\forall z(\varphi(x,z) \rightarrow z=y)$ is $\Pi_{1}$.

(Note that, $\bar{x}$ means the value of $x$, meaning $\underbrace{S \cdot \cdot \cdot S}_\text{x times}0$).

It seems that the book is actually using an explicit wff to express $f$, in my case I just keep $\Phi$ as some ethereal wff which we assume expresses $f$; is there any problem with this? I essentially want to know if my proof is adequate, and if not where I went wrong or what I misunderstand. It seems to me utterly trivial to prove both Theorem 13.1 and its converse if the method I provided is correct, which is why I suspect that my method is incorrect. Any suggestions and nudges in the right direction would be greatly appreciated, thank you!

  • 0
    @magma "An Introduction to Godel's Theorems", by Peter Smith.2012-02-25

1 Answers 1

2

The stronger fact is that for a function $f\colon \mathbb{N} \to \mathbb{N}$, the following are equivalent:

  1. $f$ is computable
  2. The graph of $f$ is computable
  3. The graph of $f$ is $\Sigma^0_1$, that is, the graph of $f$ is r.e.

However, it is not true in general that a function with a $\Pi^0_1$ graph (a co-r.e. graph) has to be computable.

To see this, we construct a particular explicit counterexample. First make a helper function $h(e,s)$ as follows: if program $e$ halts in exactly $t$ steps, when run with no input, where $t < s$, then $h(e,s) = t$, otherwise $h(e,s) = 0$. The function $h$ is computable: to compute $h(e,s)$ we only have to run program $e$ for $s$ steps and see whether it halts in some number $t < s$ of steps.

Moreover, for each $e$, the following limit is defined: $g(e) = \lim_{s \to \infty} h(e,s).$

First, $g(e)$ cannot be computable. If it was, then the halting problem would be computably solvable, because if $g(e) = t$ then program $e$ halts if and only if it halts when run for $t$ steps.

It is therefore sufficient for the question to show that $g$ has a $\Pi^0_1$ graph. We know that $h(e,s)$ is computable, so by Theorem 13.1 from the question there is a $\Pi^0_1$ formula $\phi(e,s,t)$ which holds if and only if $h(e,s) = r$. Then $ g(e) = t \Leftrightarrow (\forall s)[ s > t \to \phi(e,s,t)] $ and the right side is a $\Pi^0_1$ formula $\psi(e,t)$ for the graph of $g$, as desired.

  • 1
    Good work in clearing up the unanswered list!!2013-06-07