11
$\begingroup$

We know that any (consistent) recursively enumerable theory which can interpret Peano arithmetic is necessarily incomplete. Since set theory interprets Peano arithmetic, we know that set theory is incomplete (or inconsistent) as well. Could it be that this is the only source of incompleteness in set theory?

More precisely:

Is there a recursively enumerable theory $T$ extending ZFC, such that the union of $T$ with all theorems of true arithmetic (interpreted as statements about $\omega$) is complete (and consistent)?

At first I thought that this should have a stupid answer, where we define a theory $S$ to be the "lexicographically first" completion of ZFC, and let $T$ be the collection of statements "if $\varphi$ is contained in $S$, then $\varphi$ is true". The idea is that whether or not a given sentence $\varphi$ is contained in $S$ should be determined by a finite list of arithmetic statements asserting the consistency and inconsistency of various theories. However, the theory $S$ might not be consistent with true arithmetic, and if we instead try to make $S$ be the lexicographically first theory which is consistent with both ZFC and true arithmetic, then we run into a problem, since the statement "this theory is consistent with true arithmetic" no longer seems to be expressible in the language of arithmetic.

If the answer to this question is "yes", then there are some obvious follow-up questions: could such a theory $T$ be $\omega$-consistent? Could it have a well-founded model? (Could it be true?)

Improve this question
$\endgroup$
1
  • $\begingroup$ Another question would be whether there are purely arithmetic statements that are "convincingly incomplete" in the sense that they don't have a preferred truth value. For example, CON(PA) is not convincingly incomplete because it should "obviously" be true. Paris-Harrington is not convincingly incomplete for a similar reason, etc. (Obviously, CH is not a "purely arithmetic" statement.) $\endgroup$
    – Mikhail Katz
    Commented 9 hours ago

2 Answers 2

Reset to default
7
$\begingroup$

There does not exist any r.e. theory $T\supseteq\mathsf{ZFC}$ and any set $A$ of arithmetical sentences (true or otherwise) such that $T+A$ is complete and consistent, because ZFC has a truth predicate for arithmetical sentences. This is a special case of the “Proposition” in https://mathoverflow.net/a/257044, which was rediscovered by A. Enayat, A. Visser, Incompleteness of boundedly axiomatizable theories.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Wow, this is an amazingly general result! $\endgroup$
    – zeb
    Commented 4 hours ago
9
$\begingroup$

Say that a theory $T\supseteq \mathsf{ZFC}$ is CCMA ("complete computable mod arithmetic") iff $T$ is computable but $T^+:=T\cup\mathsf{TA}$ is complete and consistent, where $\mathsf{TA}$ is true arithmetic (phrased set-theoretically as usual).

For very coarse reasons, no CCMA theory has an $\omega$-model: this is because if $T$ is CCMA then $T^+$ is Turing-equivalent to ${\bf 0^{(\omega)}}$, but no $\omega$-model of $\mathsf{ZFC}$ has hyperarithmetic theory. This falls short of proving $\omega$-inconsistency of $T^+$ for any CCMA theory $T$, but it does answer your final question (no CCMA theory can be the true theory of $V$).

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ To attempt to describe things for the OP a bit more softly: The truths of higher levels of set theory, such as truth in $H_{\omega_1}$ or $V_{\omega^2}$ and so forth, are more complicated than arithmetic truth, and so we cannot expect that those truths would be settled correctly by the desired sort of theory. $\endgroup$
    – Joel David Hamkins
    Commented 15 hours ago
  • 1
    $\begingroup$ Noah, in the existence part, your definition is not recursive, since $\theta_{i+1}$ does not depend on $\theta_i$ or the earlier part of the construction. So I think you've haven't said what you intended. It seems you want to add them successively, not independently. $\endgroup$
    – Joel David Hamkins
    Commented 15 hours ago
  • 1
    $\begingroup$ The existence argument seems a bit dubious - there's no guarantee that $\theta_0$ isn't already causing an inconsistency with true arithmetic, regardless of how the later $\theta_i$ are defined. The correctness claim seems to hold up - perhaps a simpler reason is that truth would become definable in any $\omega$-model of $T^+$. $\endgroup$
    – zeb
    Commented 15 hours ago
  • 1
    $\begingroup$ @zeb Ah yes I messed things up with existence. Removing for now ... $\endgroup$
    – Noah Schweber
    Commented 15 hours ago
  • 1
    $\begingroup$ How strange - you answered the question which was originally in my heart, but the technical question I actually ended up asking, about the existence of a CCMA theory, now seems like the more interesting question. I suppose that if no one can resolve that within a day or two I will accept this answer. $\endgroup$
    – zeb
    Commented 14 hours ago

You must log in to answer this question.

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