9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Oct 18 '16 at 19:54
  • $\begingroup$ @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$)? $\endgroup$ – PyRulez Oct 18 '16 at 20:08
  • 4
    $\begingroup$ 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$. $\endgroup$ – Joel David Hamkins Oct 18 '16 at 20:08
  • $\begingroup$ But that doesn't seem yet enough to rule out such a theory....need a better argument. $\endgroup$ – Joel David Hamkins Oct 18 '16 at 20:18
  • $\begingroup$ @Joel I think a Rosser-style trick should be enough to finish your argument. $\endgroup$ – Emil Jeřábek Oct 18 '16 at 20:26
11
$\begingroup$

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.

So there is no such theory T.

$\endgroup$
  • $\begingroup$ "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" Could you expand on this? $\endgroup$ – PyRulez Oct 18 '16 at 20:46
  • 2
    $\begingroup$ The point is that we cannot be sure that the theory T+TA is sound, and so what it proves happens with the oracle might not be the same as what actually happens. But we know that the elements of A are enumerated by the A-program before they are enumerated by the B-program, and this relies on only finitely much of the oracle, which is expressed as a single assertion of TA. So the theory will prove that every individual element of A is in C, and that the individual elements of B are definitely not in C. $\endgroup$ – Joel David Hamkins Oct 18 '16 at 20:52
  • 1
    $\begingroup$ I guess that King's program to complete set theory modulo arithmetic has failed. It was much shorter lived than Hilbert's program. $\endgroup$ – PyRulez Oct 19 '16 at 1:47
  • $\begingroup$ Is there a way to generalize these results. It seems that they could be generalized beyond arithmetic and set theory. $\endgroup$ – PyRulez Jul 7 '17 at 3:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.