*Edit: all sets / theories considered below are supposed to be recursively enumerable, although I'd also be interested in any possible generalizations to non-enumerable theories.*


In the comments on [this question](https://mathoverflow.net/questions/232209/relationship-between-first-and-second-incompleteness-theorems), Emil Jeřábek described a theory $T$ whose axioms come from recursively inseparable sets $X, Y$: the language has countably many variables and a single predicate $P$, with $P(n)$ if $n \in X$ and $\neg P(n)$ if $n \in Y$. This theory is essentially incomplete, but in some sense lacks the language to talk about its own consistency; in other words, it satisfies the first incompleteness theorem, but not the second.


I observed that one naturally obtains such a theory $T$ by letting $X$ resp. $Y$ be the sets of (Gödel numbers of) provable resp. disprovable statements of another essentially undecidable theory $T'$; in other words, the axioms of $T$ are precisely the theorems of $T'$, but with the semantics of $T'$ "forgotten". In particular, $T$ could be one of the familiar theories of arithmetic, subject to both incompleteness theorems.


It's then natural to wonder about a converse: can we characterize those pairs of recursively inseparable sets $X, Y$ such that $X$ resp. $Y$ are the sets of (Gödel numbers, under some numbering scheme, of) provable resp. disprovable statements of theories $T\_X$ resp. $T\_Y$, with one of the latter theories being an extension of the other, and both theories subject to the second incompleteness theorem? If not, is there some weaker formulation which works? (e.g. does allowing to iterate this construction make any difference?)


What about going even further: given such a pair $X, Y$, when is it possible to actually construct theories $T\_X, T\_Y$ which do the job?



Theories of arithmetic from recursively inseparable sets
Here's an obstacle to such a construction:



> 
> Suppose $T$ is any theory in the language of arithmetic extending $PA$. Then the set $Pr(T)$ of sentences proved by $T$ computes a complete consistent extension of $PA$.
> 
> 
> 


Proof: We can use a "greedy algorithm" to build such a complete consistent extension. Let $\{\varphi\_i: i\in\mathbb{N}\}$ be a recursive listing of the sentences of arithmetic, and define $\psi\_i$ by recursion as:


* $\psi\_0=\varphi\_0$ if $\neg\varphi\_0\not\in Pr(T)$, $\psi\_0=\neg\varphi\_0$ otherwise.
* $\psi\_{n+1}=\varphi\_{n+1}$ if $[(\bigwedge\_{j<{n+1}}\psi\_j)\implies \neg\varphi\_{n+1}]\not\in Pr(T)$, $\psi\_{n+1}=\neg\varphi\_{n+1}$ otherwise.


Let $S=\{\psi\_n: n\in\mathbb{N}\}$. It's not hard to see that $S$ is computable from $Pr(T)$, and that $S$ is a complete consistent extension of $PA$. $\quad\quad\Box$


This is a problem for the type of construction you suggest, since there are non-recursive r.e. sets which do not compute any complete consistent extension of $PA$. In fact, the **only** r.e. sets which do so are Turing-equivalent to the Halting problem! (This is Arslonov's Completeness Criterion.)


Of course, this assumes that the only way to be "subject to the Second Incompleteness Theorem" is by containing enough of arithmetic. This might not be the case, since it's a little vague exactly which theories are so subject, but it's still worth pointing out.


