MathOverflow is a question and answer site for professional mathematicians. 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

This question was motivated by this recent question by Ricky Demer.

In his paper $\Pi^0_1$ classes and Boolean combinations of recursively enumerable sets, Carl Jockusch showed that there is no completion of Peano Arithmetic which is a Boolean combination of computably enumerable (c.e.) sets. This was generalized to any essentially undecidable theory by James Schmerl in his paper Undecidable theories and reverse mathematics.

Are there similar restrictions on the type of sets which can appear as axiomatizations of completions of Peano Arithmetic or other computably axiomatizable and essentially undecidable theories? (Other than the trivial fact that such axiomatizations cannot be c.e.) Specifically, does every computably axiomatizable theory have a completion which is axiomatizable by a co-c.e. set?

share|cite|improve this question
up vote 7 down vote accepted

Yes. Every consistent c.e. theory has a $\Sigma^0_2$ (even low $\Delta^0_2$) completion, and therefore a completion axiomatized by a $\Pi^0_1$ set.

In more detail, given a c.e. theory $T$, one can construct its completion by the following procedure: let $\{\phi_n\mid n\in\omega\}$ be a computable enumeration of all sentences in the language of $T$, and put

$$\psi_n=\begin{cases}\phi_n&\text{if }T+\{\psi_i\mid i<n\}+\phi_n\text{ is consistent,}\\\neg\phi_n&\text{otherwise.}\end{cases}$$

The branching condition is $\Pi^0_1$, hence the whole thing can be implemented by an algorithm with an oracle for the halting problem. Thus $S=\{\psi_n\mid n\in\omega\}$ is a $\Delta^0_2$ completion of $T$. This completion can be $\Pi^0_1$-axiomatized using Craig's trick: if $S=\{\phi\mid\exists n\,P(n,\phi)\}$, where $P$ is $\Pi^0_1$, then $S$ is axiomatizable by $\{\underbrace{\phi\land\cdots\land\phi}_{n\text{ times}}\mid P(n,\phi)\}$.

share|cite|improve this answer
Can you explain how every $\Sigma^0_2$ theory is axiomatized by a $\Pi^0_1$ set? – François G. Dorais Feb 21 '11 at 13:24
In the same way that every $\Sigma^0_1$ theory is axiomatized by a computable set. I've put it in the answer. – Emil Jeřábek Feb 21 '11 at 13:34
Of course! Thanks! – François G. Dorais Feb 21 '11 at 13:35

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.