Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
Your argument doesn't work. Yes, you can give a $\Sigma_1$ representation of the predicate $f(x)\ne z$ by negating, but that's not the same thing as a $\Sigma_1$ representation of $f$. – André Nicolas Feb 25 '12 at 7:01
Okay, that makes sense to me now. Do you have any hints about how I can proceed from here then? – Samuel Reid Feb 25 '12 at 7:02
Look for a non-recursive function which is $\Pi_1$. – André Nicolas Feb 25 '12 at 7:15
Just a simple note on your proposed proof: your assertion that $\forall \eta_1 \cdots \forall \eta_n \varphi (x,y) \equiv \exists \eta_1 \cdots \exists \eta_n \neg \varphi (x,y)$ is false (you would need a "$\neg$" at the start of exactly one of the formulas to make it true). – arjafi Feb 25 '12 at 7:16
@ArthurFischer: Thank you for pointing that out, I realize now that my proposed proof is quite a mess and that my approach was entirely incorrect. – Samuel Reid Feb 25 '12 at 7:19
up vote 2 down vote accepted

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.

share|cite|improve this answer
Better late than never, I hope :) – Carl Mummert Jun 7 '13 at 1:18
Good work in clearing up the unanswered list!! – Asaf Karagila Jun 7 '13 at 2:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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