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

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

2010-06-11T20:19:26Z

This question is closely related to this one: http://mathoverflow.net/questions/27755/knuths-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.)

Answer by Joel David Hamkins for How would one even begin to try to prove that a simple number-theoretic statement is undecidable?

2010-06-11T20:59:56Z

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.

Answer by François G. Dorais for How would one even begin to try to prove that a simple number-theoretic statement is undecidable?

2010-06-11T21:00:15Z

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 Π₁ 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 c₀,c₁,... 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 c₀ is an even integer which is not the sum of two odd primes. To witness this, we might declare later on that c₀ = 2c₁₇ to make sure that c₀ is even. Then for every term t that arises along the way, we will add witnesses to the fact that either t > c₀, or one of t and c₀ - 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.

Answer by Timothy Chow for How would one even begin to try to prove that a simple number-theoretic statement is undecidable?

2010-06-12T00:15:19Z

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.

Answer by T. for How would one even begin to try to prove that a simple number-theoretic statement is undecidable?

2010-06-12T08:45:39Z

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

http://mathoverflow.net/questions/27755/knuths-intuition-that-goldbach-might-be-unprovable/27914#27914

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.

Answer by Pierre-Yves Gaillard for How would one even begin to try to prove that a simple number-theoretic statement is undecidable?

2010-06-12T09:36:26Z

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,

(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.

Answer by Adam for How would one even begin to try to prove that a simple number-theoretic statement is undecidable?

2010-06-12T18:05:15Z

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.

Answer by Haim for How would one even begin to try to prove that a simple number-theoretic statement is undecidable?

2010-06-12T19:08:19Z

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?