Question

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?

Answer 1

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)\}$.