# Undecidable existence theorems

Many conjectures about the natural numbers have the property that for any particular natural number, it is decidable (under some set of axioms like ZFC) whether or not the conjecture holds for that number. Nonexistence of odd perfect numbers and the Goldbach conjecture have this property, for instance.

When is it possible for the conjecture itself to be undecidable in ZFC? Intuitively I would expect never, since if it were undecidable I could find a counterexample in the universe where the conjecture is false, "port" it to the universe where it is true, and get a contradiction.

The top answer in this question, however, writes that this intuitive argument is flawed, since the natural numbers in one universe might contain elements that aren't natural numbers in the other. I don't understand how this is possible: can't I define $\mathbb{N}$ in a way that's provably unique (up to isomorphism) under ZFC? If so, how can adding an independent axiom to ZFC change the makeup of $\mathbb{N}$? Is there an easy example of how this can occur?

-

The natural numbers are well-defined within ZFC -- so in any model of ZFC there is only one set that represents the natural numbers. However, if we have two different models of ZFC, their respective natural numbers do not need to be isomorphic at the metalevel. So if one of the models has something that, within that model, is an odd perfect number, then it is not necessary that this something has a counterpart in the other model.

Intuitively (to the extent one can trust intuition in these matters), this is because ZFC is not strong enough to ensure that the $\mathbb N$ within a model is really the natural numbers -- there are models whose $\mathbb N$ is larger than the true naturals. That this must be so follows from Gödel's incompleteness theorem; there can be no first-order-theory that captures the the true natural numbers uniquely and is strong enough to do basic arithmetic.

So adding a false-but-undecidable statement to ZFC as an extra axiom will just result in a theory where none of its models have "true" natural numbers. It can still be consistent, it just doesn't describe the set theory we intuitively expect to be working in.

-
The existence of nonstandard models also follows directly from the compactness theorem, of course; it's not just an artifact of incompleteness. The theory of the reals is complete in the language of ordered fields, but it still has nonstandard models. –  Carl Mummert Sep 28 '11 at 10:56

Adding to Henning's answer, the "flaw" that ZFC is not strong enough to determine the natural numbers up to isomorphism (i.e., if ZFC is consistent, then there are different models of ZFC with non-isomorphic $\mathbb N$'s) is due to the fact that ZFC is a first order theory. That is, quantification is over elements of the structure, in this case over sets. Every first order theory that has an infinite model (and all models of set theory are infinite) has arbitrarily large models. And there are models of ZFC with arbitrarily large versions of $\mathbb N$. Here large means when looked at from the outside.

When one talks about undecidable statements in number theory, one usually considers not ZFC as the base theory, but some form of arithmetic, i.e., all the variables of our statements range over numbers. However, the problems are exactly the same as above, and the situation is even simpler, since you only have to consider models of arithmetic. But the problem remains. The first order theory of arithmetic does not determine $\mathbb N$ up to isomorphism.

The connection to Gödel's incompleteness theorems is as follows: If ZFC is consistent (which we assume it is), then ZFC does not prove its own consistency (this is the second incompleteness theorem). It follows that ZFC together with the statement that it is inconsistent is actually consistent (mind bending, I know). This implies that there is a model of ZFC that knows a proof of $0=1$ from ZFC. Inside this model, that proof can be coded into a natural number in some computable way. Now that natural number does not correspond to an actual natural number that we know in the real world, because otherwise we would have a proof of the inconsistency of ZFC. But we assumed that we don't have such a proof.

The same argument works for Peano Arithmetic, which has as its models just versions of $\mathbb N$, without any "sets" other than numbers.

-
Everything here is true, but one should not conclude from it that moving to a second-order theory instead would fix all our troubles. A second-order theory for arithmeric (or, I presume, set theory) can fix a model uniquely up to isomorphism, but there can still be undecidable sentences because in the move from first to second order we lose logical completeness (the property that every statement that is true in all models has a proof). –  Henning Makholm Sep 29 '11 at 23:26