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.

Improve this question
$\endgroup$
7
  • $\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 ♦
    Commented Oct 18, 2016 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$
    – Christopher King
    Commented Oct 18, 2016 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
    Commented Oct 18, 2016 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
    Commented Oct 18, 2016 at 20:18
  • $\begingroup$ @Joel I think a Rosser-style trick should be enough to finish your argument. $\endgroup$
    – Emil Jeřábek
    Commented Oct 18, 2016 at 20:26

1 Answer 1

Reset to default
12
$\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.

Improve this answer
$\endgroup$
4
  • $\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$
    – Christopher King
    Commented Oct 18, 2016 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
    Commented Oct 18, 2016 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$
    – Christopher King
    Commented Oct 19, 2016 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$
    – Christopher King
    Commented Jul 7, 2017 at 3:37

You must log in to answer this question.

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