# Is there any set theory $T$ such that $T$ plus true arithmetic is complete with respect to statements in set theory?

Is there an effective set theory $T$ such that $T +$$TA$ is consistient and complete. It should at least prove all theorems of $ZF$ true, so that it is a "standard" set theory. In particular, the axiom of infinity is required, since otherwise finite set theory would work, making the answer trivial. By complete, I mean every statement in the language of set theory is either provable or disprovable.

Another way of phrasing this question is what are a set of axioms of $T$ (which is either finite or such that its contents can be listed by a Turing machine), such that for any statement in the language of set theory, it can be decided by $T$ and statements in arithmetic (which are true of the standard integers).

If it fails, perhaps the requirement that $T$ be effective could be replaced by a requirement that $T$ is an Arithmetical set. Also, perhaps $TA$ could be replaced with some other consistent and complete theory of arithmetic (although this wouldn't be as useful as with $TA$).

The nice thing about such a theory is that, once $T$ is finalized, selecting new axioms would be metaphysically simpler, you could say. Instead of arguing over whether a given axiom is actually true of sets or not, the problem would be reduced to arguing about whether statements in arithmetic are true of integers or not (after $T$ has been selected).

tl;dr. Can you have a complete set theory, modulo arithmetic.

• I'd guess that if $V=L+\forall\alpha(L_\alpha\not\models\mathsf{ZFC})$ doesn't do the trick, then perhaps nothing can do the trick. And I doubt it does the trick. – Asaf Karagila Oct 18 '16 at 19:54
• @AsafKaragila I'm not familiar with $L_\alpha$, but wouldn't any statement of the form $X \not \models Y$ be a statement of arithmetic (and therefore already be decided by $TA$)? – PyRulez Oct 18 '16 at 20:08
• The theory would have to settle all questions about the halting problem relative to an oracle for TA. But it cannot do so correctly, since T+TA has the same complexity of TA itself, namely $0^{(\omega)}$. It follows that the theory T can have no model with the standard $\omega$. – Joel David Hamkins Oct 18 '16 at 20:08
• But that doesn't seem yet enough to rule out such a theory....need a better argument. – Joel David Hamkins Oct 18 '16 at 20:18
• @Joel I think a Rosser-style trick should be enough to finish your argument. – Emil Jeřábek Oct 18 '16 at 20:26

There can be no such theory $T$, even if you weaken the requirement to $T$ being merely arithmetically definable, rather than insisting it must be effective.
To see this, consider the theory T+TA, which should be consistent and complete. Let $X$ be the set of Gödel codes of assertions in this theory, and let $A$ and $B$ be $X$-computably inseparable sets, which means that they are disjoint and with an oracle for $X$, we can enumerate each of them, but there is no $X$-computable set containing $A$ and disjoint from $B$. Fix specific programs for enumerating $A$ and $B$ from an oracle for $X$.
Now, let $C$ be the set of numbers $n$ such that T+TA proves that they are enumerated into $A$ before they are enumerated into $B$, using the fixed programs and using what the theory thinks is TA. Because every member of $A$ is enumerated into $A$ by that program on account of only finitely much of the oracle, the theory T+TA will agree on that element being enumerated into $A$, and similarly with $B$. Thus, the set $C$ contains every actual element of $A$ and no actual element of $B$. But $C$ is computable from $X$, since we need only search for proofs from T+TA. Contradiction.