Difference between undecidable statements in set-theory and number theory?

Question

Do all statements about the integers have a definite truth value? For instance: Goodstein's theorem is clearly true, otherwise we could find a finite counterexample thus it would be possible to disprove it. So the independence proof is also a proof. Godel's theorem only claims there are true statements that are unprovable.

What is it that makes statements about the integers have a clear true/false-value (by some higher-order reasoning), but statements about sets such as AC and CH dont?

Does the higher-order reasoning just become more and more diffuse (or subjective) or is there some fundamental leap between undecidable statements about the integers vs sets?

Answer 1

There is a lot to address here. You might be getting at any of the following points:

The existence of $\Pi_1^0$ statements: A statement is called $\Pi_1^0$ if, if it were false, it could be disproven by a finite amount of data. Goldbach's conjecture, "every even number is the sum of two primes", is $\Pi_1^0$, because to disprove it you just have to give an even number $2n$, and a nontrivial factor of $2n-p$ for each prime $p < 2n$. A $\Pi_1^0$ statement, if undecidable, is always true. See Wikipedia for the rigorous definition and much more.

It is far from the case that all interesting problems in number theory are $\Pi_1^0$. Consider the twin prime conjecture, "there are infinitely many pairs of primes which differ by $2$." This could be undecidable in two different ways. Maybe it is true, but we can't prove it. Or, maybe there are no twin primes past $10^{10^{10}}$, and we can't prove that. Either way, no finite amount of data will settle the issue.

Goodstein's theorem is not $\Pi_1^0$: Contrary to your statement, a finite amount of data cannot disprove Goodstein's theorem. Suppose that you knew that the Goodstein sequence starting at $100$ did not terminate. How could you convince me o this with any finite computation?

Now, in fact, Goodstein's theorem is true, because induction up to $\epsilon_0$ is valid. See this MO question for more. But consider the Collatz conjecture. Like Goodstein's theorem, it says that a recursively defined sequence starting at any integer eventually terminates. It is perfectly possible for Collatz to be either undecidable and true or undecidable and false.

ZFC does prove more than PA: The proof of Goodstein's theorem can be formalized in ZFC. So can the intuitive proof that PA is consistent, namely, "of course it's consistent, it is a set of true statements about $\mathbb{Z}$!" So it is true that being undecidable in ZFC is a lot stronger than being so in PA.

A point of philosophy: Some mathematicians will defend the belief that all statements about $\mathbb{Z}$ are either true or false (though they may be unprovable from the current axioms) but this need not be true about sets. The idea here is that there is only one set of integers, but there are many equally good versions of set theory. Scott Aaronson defends this view here; JDH defends the "more than one set theory" here. (I don't know whether or not JDH thinks there is more than one version of $\mathbb{Z}$.)

Note that this is much stronger than the claim that all $\Pi_1^0$ statements are true or false. Scott, for example, presumably believes that the twin prime conjecture is either true or false, even though no finite amount of computation could ever settle it.

I have not thought enough about this question to form an opinion; it is ultimately a matter of philosophy, not math.

Answer 2

What is it that makes statements about the integers have a clear true/false-value (by some higher-order reasoning), but statements about sets such as AC and CH dont?

The key difference is that

• The set of natural numbers is defined by a sort of "minimailty principle": the natural numbers are, up to isomorphism, the smallest set containing 0 and closed under the function $f(x) = x+1$.

• The collection of all sets is defined by a sort of "maximality principle": it consists of all sets.

This difference makes the natural numbers concrete in a certain way the the collection of all sets is not.

If we try to take the corresponding "minimality" principle for sets, we end up with the constructible universe $L$, or with some sort of minimal submodel of it, for which we can answer many of the questions like AC and CH that are independent of ZFC.

Answer 3

What is it that makes statements about the integers have a clear true/false-value (by some higher-order reasoning), but statements about sets such as AC and CH don't?

This is about the logical complexity of the formulas. We can have statements about integers that uses very high logical complexity (e.g. by quantifying over all subsets of natural numbers). But I guess that is not what you mean by a statement about integers, you probably mean a statement is in arithmetical hierarchy. Similarly, a statement about sets can be very low logical complexity, e.g. if the set is definable by a low complexity statement. What is important here is not the free variables of the statement (the objects the statement is about) but the logical complexity of the statement.

Why arithmetical statements seem more concrete and well-defined (at least to some) than say analytical statements?

One reason is that arithmetical statements do not quantify over infinite objects (which are not as intuitive as finite objects). Another objection is that the analytical statements are impredicative because a definition of the object quantifies over the set of objects that the object itself belongs to (similar to Russell's paradox). There are various views in philosophy of mathematics about which statements are really well-defined and have a definite truth value and which statements do not.

Does the higher-order reasoning just become more and more diffuse (or subjective) or is there some fundamental leap between undecidable statements about the integers vs sets?

It is not about the order of reasoning. The difference is that infinite objects are not like finite objects (objects that at least in principle can be represented physically). I can show you 2 apples but I cannot show you $\aleph_0$ apples. Our intuition about infinite objects is not as good as our intuition about finite ones, e.g. if we try to do the set theory in Cantor's naive way we will ran into paradoxes. Two distinct views about infinite objects are:

• top-down: every possible object is OK (unless something goes wrong), like Cantor's naive set theory, or Frege's system, which have a Comprehension Axiom (which gives objects out of statements).

• bottom-up: only objects we can build by some methods are OK, like current axiomatic set theories like ZFC, which do not have a Comprehension Axiom.

If we are in the first framework, then we need to decide what kind of properties are acceptable definitions of infinite objects. Is Analytical Comprehension OK? What about even more complex Comprehension Axioms?

If we are in the second framework, we need to discuss which methods of building are OK. E.g. is (classical) Power Set axiom OK? What about axiom about existence of an Infinite Set? (Note that without Infinite Set axiom, set theory is similar to PA).

And of course, there are other philosophical views where one rejects that infinite sets and objects exist (some completely reject them and some believe that they do not exist as completed objects, i.e. we only have potentially infinite objects which are limits of specific sequence of finite objects).

Philosophy of mathematics is a big area, if you are interested there nice introductionary articles on Wikipedia and also on SEP, you can find also nice books, surveys, and papers on the topic by checking the reference part of those articles.