3
$\begingroup$

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, 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?

Improve this question
$\endgroup$
2
  • $\begingroup$ To clarify: are you asking whether, given a pair of recursively inseparable r.e. sets $X,Y$, there is a theory $T$ which is strong enough to satisfy the second incompleteness theorem, and so that $X$ consists of the provable statements of $T$ and $Y$ consists of the disprovable statements of $T$? I am not sure about the theories $T_X$ and $T_Y$ in the third paragraph. $\endgroup$
    – Carl Mummert
    Commented Mar 4, 2016 at 18:57
  • $\begingroup$ I was originally going to ask that, but then thought: maybe that could fail because one of $X, Y$ is "too small" compared with the other. So it could also be worth considering the situation where the "smaller" set comes from a weaker version of the theory. That's where $T_X$ and $T_Y$ come from. $\endgroup$
    – Robin Saunders
    Commented Mar 5, 2016 at 2:18

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, it sounds like Arslanov's criterion is almost exactly what I was asking for. Regarding your last paragraph, I know that Albert Visser (among others) has done work on proving the incompleteness theorems directly in theories of "syntax" or string concatenation, which in turn I understand to be mutually interpretable with weak theories of arithmetic. So presumably a more general formulation of Arslanov's completeness criterion would apply to these theories as well? $\endgroup$
    – Robin Saunders
    Commented Mar 7, 2016 at 0:01
  • 1
    $\begingroup$ @RobinSaunders As long as these theories have the property that I describe above: that, given any consistent extension of such a theory, the set of sentences provable in that extension computes a completion of PA. I'm not familiar with Visser's work, but at a quick glance I think that this is indeed still the case. $\endgroup$
    – Noah Schweber
    Commented Mar 7, 2016 at 0:10
  • 1
    $\begingroup$ @RobinSaunders Also, as a side note, ACC is actually stronger than what I state: it says that the only r.e. degree computing a fixed point free function - that is, a function $F$ satisfying $\varphi_{F(e)}\not=\varphi_e$ - is $0'$. Computing a fixed point free function is strictly easier than computing a completion of $PA$. $\endgroup$
    – Noah Schweber
    Commented Mar 7, 2016 at 0:12
  • $\begingroup$ I'm not sure if this is "interesting" enough to merit its own question, but what happens if we treat the recursively enumerable list of true statements "the [algorithm / lambda expression / Turing machine / ...] with index i terminates on empty input" as axioms of a theory? Is such a theory useful for anything? How strong is it? $\endgroup$
    – Robin Saunders
    Commented Mar 9, 2016 at 4:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .