# How would one even begin to try to prove that a simple number-theoretic statement is undecidable?

This question is closely related to this one: Knuth's intuition that Goldbach might be unprovable. It stems from my ignorance about non-standard models of arithmetic. In a comment on the other question, Chandan Singh Dalawat reproduced the following interesting quotation:

There are very many old problems in arithmetic whose interest is practically nil, i.e. the existence of odd perfect numbers, the iteration of numerical functions, the existence of infinitely many Fermat primes $2^{2^n}+1$, etc. Some of these questions may well be undecidable in arithmetic; the construction of arithmetical models in which questions of this type have different answers would be of great importance." (Bombieri, 1976)

What I'd like to know is, what might such a model look like, even roughly? For example, suppose one wanted to construct a model in which there were only finitely many Fermat primes. Would one do something like adjoin a nonstandard integer N, add the statement that all Fermat primes were less than N, and somehow demonstrate that that did not lead to a contradiction? (For all I know, that is an obviously flawed or even ridiculous suggestion.) A slightly more general question is this: is it conceivable that a number-theoretic independence proof might be achieved without one going too deeply into the number theory? (I ask that in the expectation, but not strong expectation, that the answer is no: that you can't get something for nothing.)

• Rather than constructing a model directly, a different tried-and-true approach would be to show that some theorem T has the property that (Peano arithmetic + T) proves the consistency of Peano arithmetic, or proves the totality of some function that is not provably total in PA. You're almost certainly aware of this method; I think you're asking about direct model-theoretic constructions as an alternative. I think it's plausible that not much number theory would be needed, because the number theory needed for the Paris-Harrington theorem and Matiyasevich's theorem is not excessively deep. – Carl Mummert Jun 11 '10 at 20:37
• Wouldn't what you described about Fermat primes in nonstandard models imply that there were hyperfinitely many of them? – Akhil Mathew Jun 11 '10 at 20:39
• @Ankhil: In arithmetic finite/infinite is generally interpreted as bounded/unbounded. – François G. Dorais Jun 11 '10 at 21:09

One method, used in proving the Paris-Harrington result, a statement of Ramsey theory that is independent of PA, works roughly as follows. The statement to be proved has the form $\forall n\ \exists k\ \varphi(n,k)$. Thus, if one considers the function $f$ mapping each $n$ to the least witness $k$, what the statement amounts to is the assertion that $f$ is a total function, that $f(n)$ is defined for all $n$.

Now, the function arising in the Paris-Harrington result is an enormously fast-growing function, of mind-boggling growth. The way the argument works, very roughly, is to work in a nonstandard model $M$ of PA, but find an initial segment $I\lt M$, a cut, such that $f$ jumps over the cut $I$, but such that $I$ continues to satisfiy PA anyway. Thus, in the model $I$, the function $f$ is not total, and so one has the desired model where the statement is false.

• I thought we would answer this roughly at the same time. It's nice that our answers are completely different. – François G. Dorais Jun 11 '10 at 21:03
• Yes, François, how could we resist such an attractive question? But actually, the truth is that these independence proofs are hard. Perhaps this is why there are so few of them. – Joel David Hamkins Jun 11 '10 at 21:08
• Let me fantasize wildly. We could use a positive solution to the Goldbach conjecture to construct a function such as f(n) = smallest prime p such that 2n - p is prime. Obviously this will not be enormously fast growing, but perhaps it is so random and formless that its existence can't be proved in PA. – gowers Jun 11 '10 at 21:20
• @gowers: Maybe, but better luck would be looking at all the enumeration of Goldbach exceptions and proving that it must grow extremely fast... – François G. Dorais Jun 11 '10 at 21:23
• Gowers, random and formless infomration is not necessarily incompatible with PA. For example, one can start with a model of PA, and then force to add a random predicate $X$ (in the sense of set-theoretic forcing), while retaining PA in the language with the predicate. That is, the structure $\langle M,X\rangle$ satisfies PA, even though $X$ is by any account completely wild. – Joel David Hamkins Jun 11 '10 at 21:36

Joel David Hamkins and Francois Dorais have already explained that one of the main techniques for establishing unprovability in PA is to find some fast-growing function hidden in your problem, which grows so fast that PA can't prove that it is total.

It's worth mentioning that Harvey Friedman has for many years been developing quite a different approach for establishing the unprovability of number-theoretic statements in ZFC. In his paper "Finite functions and the necessary use of large cardinals," Ann. Math. 148 (1998), 803-893, Friedman writes:

The general strategy for using large cardinals in the integers is as follows. We start with a discrete (or finite) structure $X$ obeying certain hypotheses $H$. We wish to prove that a certain kind of finite configuration occurs in $X$, assuming that $H$ holds. We define a suitable concept of completion in the context of arbitrary linearly ordered sets. We verify that if $X$ has a completion with the desired kind of finite configuration, then $X$ already has the desired kind of finite configuration. We then show, using hypotheses $H$, that $X$ has completions of every well-ordered type. We now use the existence of a suitably large cardinal $\lambda$. Using large cardinal combinatorics, we show that in any completion of order type $\lambda$, the desired kind of finite configuration exists. Hence the desired kind of finite configuration already exists in $X$.

The key point here is that large cardinals, despite their seemingly exotic nature, contain concrete combinatorial structure that implies the existence of certain kinds of finite combinatorial structures. If you find these structures hidden in your number-theoretic conjecture then you might be able to show that your conjecture requires large cardinal axioms to prove.

I'd like to re-emphasize something that I said in my answer to the other MO question you mentioned. I believe that there is basically no reason to think that the intractability of a conjecture provides evidence of its unprovability. Furthermore, if a conjecture is intractable, then its alleged unprovability is likely to be intractable as well. To establish unprovability from PA or ZFC, you must use some property of PA or ZFC that is somehow related to the structure you are conjecturing about. You need some indication of some fast-growing function or large-cardinal-like combinatorics or something. Otherwise there is no reason to suspect that you can establish unprovability.

• Showing unprovability of a conjecture is more intractable than solving the conjecture. Unprovability requires both an upper bound (a stronger system can prove the conjecture) and a lower bound (a weaker system cannot), settling the conjecture requires only the first. Also, any reasonable problem has a difficulty-conserving concretization, by bounding and discretizing the problem in a generous enough way, and unprovability of the concrete statement implies the absence of counterexamples, i.e., the truth of the statement. – T.. Jun 12 '10 at 18:58

There are several methods for producing non-standard models. For example, via Henkin's method, via ultraproducts, or via cuts of other models. However, some of these methods would not work very well for a Π1 statement like Goldbach's Conjecture. Indeed, these statements reflect to the standard model so if Goldbach's Conjecture is true in any model of arithmetic then it must be true in the standard model.

Nevertheless, one could try to produce a model where Goldbach's Conjecture is false in order to gather evidence against the conjecture. Henkin's method is closest to the one you describe. It proceeds by adding new constants c0,c1,... to the language each of which is assigned to witness an existential quantifier in an infinite process by which one decides the truth of all sentences of the language. To start the process, we might decide that c0 is an even integer which is not the sum of two odd primes. To witness this, we might declare later on that c0 = 2c17 to make sure that c0 is even. Then for every term t that arises along the way, we will add witnesses to the fact that either t > c0, or one of t and c0 - t has a nontrivial factor, whichever does not contradict the current state of affairs. And so on for all sentences, including those which are unrelated to Goldbach's Conjecture. With careful bookkeeping, if our axioms are not contradictory, this will succeed in producing a term model of our axioms. (At the end, you need to mod out by the equivalence relation of provable equality, but those details are best left to the standard logic textbooks.) Unfortunately, without extraordinary insight, we have basically no grasp of what the final structure will be like.

There are more direct methods that work for weaker subsystems of arithmetic. For example, Shepherdson's method is highly successful in producing models of open induction. I described this method in an earlier answer. In fact, Macintyre and Marker [Primes and their residue rings in models of open induction, MR1001418] have refined Shepherdson's method to produce some very curious non-standard models of open induction. In one such model, all non-standard primes are congruent to 3 mod 4, and in another every nonstandard even integer is the sum of two primes. Since open induction is very, very weak one cannot draw many conclusions from this, but the models in question are very concrete.

• (Edit: I added some examples to the last paragraph.) – François G. Dorais Jun 12 '10 at 20:33

I saw this question just after posting an answer of sorts in the preceding discussion:

Knuth's intuition that Goldbach might be unprovable

As far as I know, the "rapidly growing function" method is not fundamentally different from the "statement allows the theory to construct model of itself" technique. It is an interpretation of the latter method, originally provided by Ketonen and Solovay as a more transparent way of understanding the Paris-Harrington proof (which showed that from the finitary function implied by their variant of Ramsey's theorem, one could construct a model of Peano Arithmetic, and this construction could itself be carried out in PA).

To find a model of PA (or ZF, or other expressive formal system) within a given problem such as Goldbach, it has to support the combinatorics entailed in those formal systems, such as the proof-theoretic ordinals up to $\epsilon_0$ or $\Gamma_0$, or large cardinal combinatorics as in Friedman's work. Theorems of Paris-Harrington, Friedman and others that are unprovable in specific systems refer to structures that are reverse-engineered from the combinatorics appearing in mathematical logic.

Thus, to get PA-unprovability from Goldbach or Riemann conjectures one would have to somehow relate prime number distribution to the extremely rigid combinatorics of either (1) models of PA, (2) the syntax of PA as a formal proof system, or (3) $\epsilon_0$ and the proof-theoretic ordinal analysis of PA. This happens only if things like the Weil conjectures and Riemann hypothesis are the tiniest tip of a structural iceberg in number theory, OR, alternatively, if provable relations to formal systems appear generically in lots of problems all over mathematics, in which case there is a machine for resolving large numbers of open problems (e.g., in ZF) en route to demonstrating their unprovability in PA.

EDIT: regarding the discussion below of rapidly growing functions not seeming to appear in Goldbach, it's not necessary that the/a/any Goldbach function $g(n)$ implicit in the conjecture be fast-growing, only that Peano Arithmetic be able to construct from $g(n)$ something else that is rapid. For example, if you look at the set of $n$ such that $g(n) = 3$, this is a subsequence of something analogous to the twin primes, and conceivably could grow very fast if PA can't prove the Twin Prime Conjecture or its ilk.

I had similar questions, and after stumbling around for a long time figured out that Kaye's book Models of Peano Arithmetic is pretty much the first book to read if you want to start building nonstandard models with particular properties (there's plenty of other literature, but Kaye's book seems to be the only introductory one). In particular, section 14.3 covers the material that @Joel discusses in his answer.

I would like to extend the above question: It seems that most previous comments are dealing with independence of number theoretic statements from PA. I would like to know your input regarding the possible independence of number theoretic statements from ZFC. Unlike the Paris-Harrington theorem, in which we got the unprovability of a true statement, I would like to know whether some work has been done on proving the (symmetric/CH-like) independence of number theoretic statements from ZFC. It seems that forcing is not very useful in this situation. Is it likely that such independence results may be somehow connected to possible (non-trivial) independence results from ZFC+V=L?

• Harvey Friedman has arithmetical statements that are consistency-equivalent to Mahlo cardinals. (Last I checked those were the largest cardinals he got, but that was a while ago. Check his webpage.) – François G. Dorais Jun 12 '10 at 19:17
• Thanks, but this is not exactly the kind of independence I was looking for. I was looking for symmetric independence results (in the sense of CH) which relate to the axioms of ZFC alone, without involving large cardinals. – Haim Jun 12 '10 at 19:33
• In Shelah's fascinating (and easily Googlable) article "Logical Dreams," he says that forcing makes the universe "fatter" while increasing the consistency strength makes the universe "taller." You're asking if there's a way to get independent number-theoretic statements by "fattening." As you point out, forcing doesn't seem to be able to touch arithmetic statements. As far as I know, there has been no progress in this direction. It remains an unfulfilled Logical Dream. – Timothy Chow Jun 13 '10 at 1:47

EDIT

Here is my problem. To prove that statement S is undecidable is to

(1) prove that one cannot prove S.

I think I understand the meaning of the second "prove". (It depends of course on the context.) But I don't understand the meaning of the first "prove".

A "solution" would be to replace (1) by

(2) give an informal proof showing that one cannot prove S,

or

(3) give an acceptable argument showing that one cannot prove S.

This seems to be in tune with the following quotation from Cohen's "Set theory and the Continuum Hypothesis" (p. 41):

We have now arrived at a rather peculiar situation. On the one hand $\sim A$ is not provable in $Z_1$ and yet we have just given an informal proof that $\sim A$ is true. (There is no contradiction here since we have merely shown that the proofs in $Z_1$ do not exhaust the set of all acceptable arguments.)

I think it would be an enormous progress to replace (1) by (2) or (3).

In other words, instead of talking about "proving" that some statements are undecidable, it would be wiser, I believe, to talk about giving "informal proofs", or "acceptable arguments", or "convincing evidence", ... that these statements are undecidable.

END OF EDIT

Here is, for what it's worth, my personal conviction on this.

If (like me) you don't believe that "you can't get something for nothing", then you don't believe in Gödel and Cohen's results.

The claim to "get something for nothing" is very openly expressed (in my opinion) by Cohen on page 39 of "Set theory and the Continuum Hypothesis":

The theorems of the previous section are not results about what can be proved in particular axiom systems; they are absolute statements about functions.

Cohen really says: "The theorems of the previous section are proved without invoking any axiom, that is, they are gotten for nothing". Or am I putting words in his mouth?

I think the key is to understand the respective STATUS of the various statements involved. In particular, a clear distinction should be made between mathematical and metamathematical statements.

I also think we should all make an effort to talk unemotionally about such questions.

• +1. I am intrigued by, and quite welcome, a degree of difference of opinion on such foundational matters. I particularly endorse the final paragraph! – Ian Morris Jun 12 '10 at 22:36
• +1 if only to negate the -1 after it was first posted. There are certainly points of view from which Goedel or Cohen's results are less earth-shaking than their historical fame suggests. However, I am not sure what it has to do with "something for nothing", and there is an irreducible core of significant content to Goedel's results (and probably also Cohen's, I just don't understand the latter as well). In other words, Goedelian phenomena are robust enough to appear in some form even if one build and construes one's mathematics on a different (or dissident!) philosophical or formal basis. – T.. Jun 13 '10 at 1:50
• Dear Ian and dear T.: Thank you very much for your comments. – Pierre-Yves Gaillard Jun 13 '10 at 9:29