178
$\begingroup$

Knuth's intuition that Goldbach's conjecture (every even number greater than 2 can be written as a sum of two primes) might be one of the statements that can neither be proved nor disproved really puzzles me. (See page 321 of http://www.ams.org/notices/200203/fea-knuth.pdf )

All the examples of such statements I have heard until now were very abstract, but this one is so concrete.

My question is that is there such an example of a statement of this sort that is proved to be unprovable, i.e., for some property $P(n)$, the statement that "every natural number $n$ satisfies $P(n)$". (In the Goldbach case $P(n)$ would be "if $n$ is an even number greater than $2$, then there exists two primes $p$ and $q$ such that $n = p + q$".)

If Knuth is right, it would be very interesting in one sense: the negation of Goldbach is obviously provable if it is true. So if someone proves that Goldbach is not provable, then we would know that Goldbach is true. We would be sure that someone would never come up with an example that would violate the condition. For the practical person, this is as good as it is proven.

Edit: I have learned a lot from the answers, thank you so much!

$\endgroup$
19
  • 39
    $\begingroup$ The way to think about it is this: if Goldbach is independent of PA, then it is true. For example, if we proved the PA-independence of Goldbach in ZFC (say), then ZFC would prove that it was true. $\endgroup$ Jun 11, 2010 at 2:11
  • 21
    $\begingroup$ We do know that every even number is the sum of a prime and either a prime or a product of two primes. This makes the existence of a proof of Goldbach's conjecture sound rather plausible to me. $\endgroup$ Jun 11, 2010 at 6:32
  • 9
    $\begingroup$ Charles, yes, this is conceivable. For example, the existence (or consistency) of a supercompact cardinal is independent of ZFC+Grothendieck, provably so if you assume even larger large cardinals, but you cannot prove this independence in ZFC or in ZFC+Grothendieck or even in ZFC+supercompact. $\endgroup$ Jun 11, 2010 at 12:28
  • 43
    $\begingroup$ Sorry, but I would call this a "completely random guess" rather than an "intuition". $\endgroup$ Apr 16, 2011 at 0:38
  • 25
    $\begingroup$ Knuth is a wonderful and brilliant guy, and I hate to oppose him on this ... but I think the idea that the Goldbach conjecture is undecidable is simply ridiculous. Note that all of Knuth's arguments as to why it might be undecidable apply perfectly well to the odd Goldbach problem (Vinogradov's 3-primes theorem) - and really, in some sense, to any important mathematical theorem ever proved. $\endgroup$ Jul 22, 2011 at 23:24

11 Answers 11

178
$\begingroup$

When we say that a statement is undecidable, this is implicitly with regard to some axiom system, such as Peano arithmetic or ZFC. The reason why statements about arithmetic can be undecidable is that there exist inequivalent models of arithmetic that obey such axiom systems (this is a consequence of the Gödel completeness and incompleteness theorems, assuming of course that the axiom system being used is consistent and recursively enumerable). For instance, the standard or "true" natural numbers obey the Peano axioms, but so do some more exotic number systems (e.g. the nonstandard natural numbers). It is conceivable that a given statement in arithmetic, such as Goldbach's conjecture, holds for the true natural numbers but not for some other number systems that obey the Peano axioms, though personally I view this possibility as remote. (Note that the nonstandard natural numbers satisfy exactly the same first-order statements as the standard natural numbers, by Los's theorem, but one can also construct other, weirder, models of arithmetic which have a genuinely different theory.)

So, if Goldbach's conjecture is undecidable for some given axiom system, what this would imply is that every "true" even natural number larger than 4 is the sum of two primes (otherwise we could disprove Goldbach with an argument of finite length), but that there exists a more exotic number system (larger than the true natural numbers) obeying those axioms which contains some even exotic number that is not the sum of two (exotic) primes. (Note that the length of a proof has to be true natural number, rather than an exotic one, so the existence of an exotic counterexample cannot be directly converted to a disproof of Goldbach.) This is an unlikely scenario, but not an a priori impossible one (as one can see from the example of Goodstein's theorem or the Paris-Harrington theorem).

[Edit: here, as usual, when talking about things like the "true" natural numbers, one has to work in some external reasoning system which may be distinct from the reasoning system one is analysing the decidability of. For instance, one may be using ZFC as one's external reasoning system to analyse what can and cannot be decided in Peano arithmetic, with the true natural numbers then being constructed by, say, the von Neumann ordinal construction combined with the axiom of infinity. Or one could be using an informal external reasoning system, based perhaps on some Platonic beliefs about mathematical objects, that is not explicitly axiomatised. It's best to keep the external system conceptually distinct from any internal ones being studied, as one can get hopelessly confused otherwise.]

$\endgroup$
3
  • 24
    $\begingroup$ "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) $\endgroup$ Jun 11, 2010 at 3:08
  • 12
    $\begingroup$ You have quite a bit meta- and advice-math written down on your page. Do you happen to have summarized your stance on such onthological questions (pro/contra Platonism etc.) somewhere as well? $\endgroup$
    – Nikolaj-K
    Jul 3, 2013 at 9:52
  • 1
    $\begingroup$ I think you mean ''ontological''. $\endgroup$ Jul 31, 2021 at 13:06
126
$\begingroup$

I once heard Don Zagier talk of a more general intuition that the quality that may make some natural statements unprovable is the quality of telling you just what you would expect to happen anyway. For example, the statement that pi has infinitely many zeros in its decimal expansion may be hard, or even impossible, to prove precisely because it would be a miracle if it were false -- so that if it is true it doesn't have to have a reason for being true.

Goldbach's conjecture is an interesting case for this heuristic. If one combines appropriate "the primes are random" heuristics with the experimental knowledge that it is true up to some very large finite number, then one can argue that the probability that it is false is absolutely tiny. So it might seem like a prime candidate for Zagier's class of difficult problem. And indeed it is at the very least extremely difficult. But there are closely related theorems, such as Vinogradov's three-primes theorem (that every sufficiently large odd number is the sum of three primes) that are proved by exploiting the random-like behaviour of the primes. That is, in a sense one actually proves the heuristic that tells you that the theorem is what you would expect to be true. From this point of view, what makes Goldbach hard is that the method of proof breaks down badly: the notions of quasirandomness we have just aren't strong enough to guarantee that sumsets of quasirandom sets have no gaps. (They can tell us things like that almost every even number is a sum of two primes, in a pretty strong sense of "almost every".)

So one might say that, given that the techniques break down, Zagier's criterion applies again. But I'm uneasy about this -- number theorists who have thought much harder about Goldbach's conjecture than I have are agreed that the problem is currently out of reach, but I have sometimes heard them speculating in some detail about what a proof might look like. And Vinogradov's three-primes theorem might look like a great candidate for the criterion to someone who didn't know about the circle method.

But I think one can at least say that it is conceivable that Goldbach's conjecture "just happens to be true", whereas a conjecture that asserts something "unlikely" tends, if it is true, to have to be true for a reason.

$\endgroup$
5
  • 3
    $\begingroup$ How serious would it be, if the idea that Goldbach is unprovable in normal mathematics gained currency? That would mean it is true, as has been said, so that it could be a new axiom. In other words number theorists could go on proving conditional results, but call them something else (results of plus-mathematics, say). This wouldn't be so interesting, because the axiom isn't ambitious, and the conditional results presumably wouldn't be very numerous. It would be better to select a very general form of conjecture on primes, such as the Bateman-Horn conjecture. And hope for a plus-contradiction! $\endgroup$ Jun 11, 2010 at 7:51
  • 4
    $\begingroup$ Has anyone proposed a general conjecture on when a sumset $A+A$ represents all sufficiently large "eligible" integers, where $A$ is a subset of the positive integers? By "eligible" I mean integers not excluded by the mod-p behavior of $A$. $\endgroup$ Jun 11, 2010 at 14:43
  • 11
    $\begingroup$ I'm not sure they have. It's easy to do with Fourier analysis if you look instead at A+A+A, but Fourier analysis isn't sensitive enough to detect (in a meaningful way) that a single point is missed from A+A. A general property that does the job for A+A (even conjecturally) would be extremely interesting. $\endgroup$
    – gowers
    Jun 11, 2010 at 16:52
  • 5
    $\begingroup$ Well, there's Mann's theorem: if $\sigma(A)+\sigma(B)\geq 1$, then $A+B={\mathbb N}$, where $\sigma(A)=\inf_n |A \cap [n]|/n$. The "inf" has been weakened by Jin, at the cost of only finding that the sumset contains all sufficiently large naturals. $\endgroup$ Jun 11, 2010 at 18:32
  • 4
    $\begingroup$ I don't count that because I was (implicitly) asking for a condition that can be applied to sparse sets. I hereby make that requirement explicit. (I don't think zero density is needed for it to be interesting. In fact, it's possible that doing it for any density that's too low for Mann's theorem to apply would be extremely interesting. I'm not just saying that to rule out your suggestion ...) $\endgroup$
    – gowers
    Jun 11, 2010 at 20:03
74
$\begingroup$

It's equivalent to asking about possibilities such as "aliens land on Earth and provide us a proof that Peano Arithmetic can't prove Goldbach", or "an ancient cuneiform tablet is found containing an RSA-encrypted proof that Riemann Hypothesis is independent of Zermelo-Fraenkel set theory". Although in such a scenario Goldbach (resp. RH) would be found to be PA-unprovable, that would happen only as a result of developments so stupendous that Goldbach and its provability become trifling afterthoughts, and one might as well ask directly about probability of alien landings or Babylonian codices.

The only currently known way for Goldbach to be unprovable is if within the additive combinatorics of the prime numbers were encoded a model of Peano Arithmetic (ie., PA could derive a model of itself from a PA-constructible function $g$ such that for all $n>1$, $g(n)$ and $(2n - g(n))$ are odd primes). This would imply a degree of rigidity and intricate structure in the primes so far beyond the existing ideas --- such as the expectation that weak analogues of geometry and topology are manifested in algebraic number theory (zeta functions), or that some degree of probabilistic (quasirandom) structure exists in additive number theory --- as to completely dwarf any mathematics that currently exists.

The equally earth-shaking alternative means by which Goldbach could be shown to transcend PA, is if entirely new methods are found for demonstrating PA-unprovability of relatively "generic" (ordinary, concrete) mathematical statements. Presumably this would mean that not only Goldbach, but a very large number of other open conjectures would be seen to also transcend Peano Arithmetic (and, in the process, be solved in a stronger system such as ZF). A general machine for turning a large volume of conjectures into ZFC theorems with PA unprovability certificates would, in the same way as the alien landings, be of such overwhelming importance and surprise as to make Goldbach itself irrelevant.

While any future discoveries are hypothetically possible, the only existing evidence for the demonstrable PA-unprovability of Goldbach (i.e., for the idea that a proof will be found in a stronger theory, such as ZF, that Goldbach transcends PA) is the body of Goedel-type unprovability and independence results derived in the past 80 years, and nothing in that or any other branch of mathematics suggests either the prospect of incredibly fine structure in the primes or of generic methods for showing unprovability. So to talk seriously of Goldbach or the Riemann Hypothesis being shown to be PA-unprovable is essentially an unadulterated speculation that a totally new species of mathematics will be discovered, a speculation that is not related to any specific feature of any particular number theoretic problem.

$\endgroup$
6
  • 2
    $\begingroup$ Dear T., This is a fantastic answer! Best wishes, Matthew $\endgroup$
    – Emerton
    Apr 16, 2011 at 0:29
  • 14
    $\begingroup$ I am perhaps out of my depth here, but it seems to me that you are arguing that there is (almost) certainly no proof that Goldbach is unprovable. But isn't it possible that Goldbach is unprovable, but there is no proof of the unprovability? I don't think Knuth suggests that Goldbach might one day turn out to be shown to be PA-unprovable, he seems only to say that Goldbach might never be resolved (the reason being that there is no proof). $\endgroup$ Apr 17, 2011 at 7:05
  • 3
    $\begingroup$ If you can prove that it's unprovable, that proves it is true (because if a counterexample exists, that would make it provable, therefore no counterexample can exist.) Which is a contradiction. So it might be unprovable, and impossible to prove it is unprovable. --- Also interesting idea that the distribution of primes could be Turing complete. That would complicate things a lot, and is not at all impossible. Lots of simple systems like cellular automata are Turing complete. $\endgroup$
    – Houshalter
    Apr 24, 2016 at 2:07
  • 3
    $\begingroup$ @Houshalter I don't think this is correct because "provable" and "true" are both two-place predicates. If you could prove in $PA$ that Goldbach is unprovable in $PA$, then yes, you'd get a contradiction (at least I think this goes through). But the possibility usually considered is that the proof Golbach is unprovable in $PA$ would itself be a proof in $ZFC$ (or maybe $ZFC$ plus some additional axioms), in which case there's no contradiction. $\endgroup$ Nov 9, 2022 at 12:06
  • 2
    $\begingroup$ @AlexeyRomanov I think a relevant point is that Goldbachs's conjecture was always (for centuries) strictly a conjecture about the "standard" natural numbers, not about some exotic nonstandard numbers. If it is independent of first order PA, then there is no counterexample in the natural numbers, which is exactly what Goldbach's conjecture says. Which means it is true in an unqualified sense. So while "provable" might be relative to some theory here, "true" is not, since Goldbach was specifically talking about the natural numbers. Either there is a counterexample in the natural numbers or not. $\endgroup$
    – Max
    Oct 4, 2023 at 22:34
64
$\begingroup$

You are right to view the Goldbach conjecture as having a particularly simple logical form. Such statements of the form "for every $n$, property $P(n)$ holds", where $P$ is a particularly simple statement, are known in logic as the $\Pi_1$ statements. These are one step up from the bottom at the entryway to the arithmetic hierarchy. Nevertheless, several of the most famous independence results concern statements at this level of complexity.

  • For example, consistency statements have this complexity. The assertion Con(PA) that the first order Peano Axioms are consistent has the same complexity as Goldbach's conjecture, since it can be viewed as the statement "for every finite sequence of symbols, it is not the proof of a contradiction in PA". But the Incompleteness Theorem shows that if PA is consistent, then Con(PA) is independent of PA, so it is an instance of your phenomenon.

  • Similarly, Con(ZFC) and other consistency statements are independent and have complexity $\Pi_1$, the same as the Goldbach conjecture.

  • Similarly, the famous "I am not provable" statement $\sigma$ of Goedel has complexity $\Pi_1$, for it can be viewed as asserting "for every finite sequence of symbols, it is not a proof of $\sigma$". This statement is true but unprovable (in PA, say), because if it were provable, then it would be false; and so it is not provable, and hence true.

  • Another example arising in considering the halting problem. It is not difficult to prove that there is a particular Turing machine program $p$ such that $p$ does not halt, but this fact is unprovable. (Otherwise, we would be able to solve the halting problem, by searching either for halting behavior or proofs of non-halting.) The statement "for every number $n$, program $p$ does not halt in $n$ steps" is therefore therefore true but unprovable, and has the same $\Pi_1$ complexity as the Goldbach Conjecture.

  • In contrast, the Goodstein theorem, which is provable in ZFC but independent of PA, has a higher complexity than Goldbach, since it is the statement "for every $n$, there is a stage $k$ at which the Goodstein sequence for $n$ reaches $0$". Thus, it has complexity $\Pi_2$, with two alternations of quantifiers.

  • Also, the Paris-Harrington example also has complexity $\Pi_2$, since they have the form "for every $n$, $m$ and $k$, there is a number $N$ such that every $k$-coloring of the $m$-subsets of $N$, there is a good monochromatic subset of size $n$".

Finally, let me remark that before Fermat's Last Theorem was proved, it was often remarked that perhaps FLT might be independent, and logicians dreamed longingly about this possibility. FLT also has complexity $\Pi_1$, since it asserts "for all nonzero $a$, $b$, $c$ and $n\gt 2$, then $a^n+b^n\neq c^n$." But meanwhile, Wiles has proved it, and so our hopes are dashed. (One interesting point is that Wiles' proof is certainly not in PA, but in ZFC or technically, ZFC + Universes, so it is conceivable still that it could be independent of PA.) But perhaps we should class Knuth's remarks about Goldbach along with these previous remarks about FLT---the longings of logicians for a big splash!

$\endgroup$
2
  • 12
    $\begingroup$ How far has Angus MacIntyre got in his project to show that FLT is provable in PA? comlab.ox.ac.uk/seminars/355.html. Colin McLarty writes "It is currently unknown what assumptions are "used in principle" in the sense of being proof-theoretically indispensable to FLT. Certainly much less than ZFC is used in principle, probably nothing beyond PA, and perhaps much less than that." cwru.edu/artsci/phil/Proving_FLT.pdf $\endgroup$ Jun 11, 2010 at 7:20
  • $\begingroup$ @DavidCorfield : This is addressed in another MO question. $\endgroup$ Jan 21, 2020 at 3:16
63
$\begingroup$

The simplest example I can think of is Goodstein's theorem. This, as the name suggest, is provable (in the standard ZFC theory of sets) but is not provable in Peano arithmetics.

I don't want to duplicate Wikipedia, but briefly here is how it goes. Take a number, say $47$ and write it in base $2$, so you get $$47 = 1 \cdot 2^5 + 1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0.$$ Write each exponent in base $2$, rinse and repeat until you cannot simplify anymore. In our case you get $$47 = 1 \cdot 2^{1 \cdot 2^{1\cdot 2^{1 \cdot 2^0}} + 1 \cdot 2^0} + 1 \cdot 2^{1 \cdot 2^{1 \cdot 2^0} + 1 \cdot 2^0} + 1 \cdot 2^{2^{1 \cdot 2^0}} + 1 \cdot 2^{1 \cdot 2^0} + 1 \cdot 2^0.$$

After that subtitute each $2$ with a $3$ and subtract $1$, to get $$1 \cdot 3^{1 \cdot 3^{1\cdot 3^{1 \cdot 3^0}} + 1 \cdot 3^0} + 1 \cdot 3^{1 \cdot 3^{1 \cdot 3^0} + 1 \cdot 3^0} + 1 \cdot 3^{3^{1 \cdot 3^0}} + 1 \cdot 3^{1 \cdot 3^0} + 1 \cdot 3^0 - 1 = 3^{28} + 81 + 27 + 3.$$

Write this number again in expanded base $3$ (in our case we already have it), change each $3$ with a $4$ and subtract $1$ (this time the expanded form will change a bit since we do not have a final $1$).

Proceed in this way and you get a sequence (called the Goodstein sequence of $n$) which becomes abnormously big at a really fast rate and... well, this sequence is eventually $0$. Just subtracting that small $1$ at each step eventually becomes preponderant over the base substitution.

The fact that the Goodstein sequence of $n$ is eventually $0$ is really easy to prove using ordinals, but it turns out it is an unprovable statement with only Peano arithmetics.

$\endgroup$
4
  • 32
    $\begingroup$ "Abnormously"? What a delightful word! It's not just mathematics that I'm learning here =o] $\endgroup$
    – Ian Morris
    Jun 11, 2010 at 10:39
  • $\begingroup$ See also mathoverflow.net/questions/18100/…. $\endgroup$ Sep 6, 2011 at 23:34
  • 3
    $\begingroup$ That's absolutely astonishing! Apart from anything else, why and how on Earth would anyone ever think of studying such an apparently contrived construction in the first place, let alone obtain this amazing result from it? $\endgroup$ Dec 17, 2013 at 15:08
  • 5
    $\begingroup$ @JohnRRamsden The complete base $n$ representation of numbers is quite natural if one is thinking in terms of denotation systems for small countable ordinals. You can use those presentations to represent all ordinals below $\epsilon_0$. From this perspective, our inability to successively subtract one, while moving to a larger base, corresponds to the fact that the ordinals are well-ordered. This is indeed how one proves Goodstein's theorem in ZFC. The fact that the theorem is not provable in PA corresponds to the fact that PA does not prove that $\epsilon_0$ is well-ordered. $\endgroup$ Nov 19, 2016 at 16:49
41
$\begingroup$

Others have mentioned several theorems (Goodstein, Paris-Harrington, Robertson-Seymour, Kruskal) that are unprovable from the axioms of first-order Peano arithmetic. However, these theorems are provable in ZFC, and in fact from much weaker axioms than ZFC. In particular, they are all accepted by the mathematical community as "proven" (unlike, for example, the continuum hypothesis). Although Knuth did not say explicitly what set of axioms he was thinking of, my guess is that he was thinking of axioms with roughly the same logical strength as ZFC. If your question is whether there are any "natural" mathematical statements with the same finitary flavor as Goldbach's conjecture that have been proved to be unprovable in ZFC (assuming ZFC is consistent), then the answer is no.

There is no intrinsic reason why such a finitary statement cannot be proved to be unprovable in ZFC. After all, "ZFC is consistent" is a finitary statement and it is unprovable in ZFC (again, assuming ZFC is consistent). Now, "ZFC is consistent" is not a "natural" mathematical statement like Goldbach's conjecture is; it is a contrived statement obtained by means of diagonalization. But there is no reason in principle that a natural statement like Goldbach cannot be unprovable in ZFC. Harvey Friedman has devoted a significant portion of his career to finding examples of natural finitary mathematical statements that are provably unprovable in ZFC. One of his best examples to date appears towards the end of Martin Davis's Notices article on The Incompleteness Theorem. In my opinion this is a very concrete statement in graph theory that one could imagine coming up as a technical lemma in a graph theory paper.

However, I must admit that I do not find Knuth's reasoning particularly convincing. In my opinion, Knuth makes the common mistake of conflating the psychological difficulty of coming up with a proof with the logical strength needed to prove a theorem. There are many mathematical theorems with difficult proofs whose proofs can nevertheless be formalized in very weak logical systems. Conversely, there are theorems like Paris-Harrington that have easy proofs but whose proofs require more than the usual logical strength. So just because we have no idea how to prove something does not, in my view, provide any compelling evidence that it is independent of some strong logical system like ZFC.

$\endgroup$
10
  • 10
    $\begingroup$ Why is Con(ZFC) contrived? Surely the consistency of a prominent mathematical theory is a fundamental, natural concern. For example, it appears as a hypothesis in innumerable theorems. I don't understand your remark that it is obtained by diagonalization. Perhps you are thinking of Goedel's "I am not provable" statement, to which such remarks are sometimes directed? (But I admit that the second Incompleteness Theorem is usually proved by establishing the equivalence of the I-am-not-provable statment with a consistency statement.) $\endgroup$ Jun 11, 2010 at 3:34
  • 3
    $\begingroup$ "Contrived" in this situation might mean "something a platonic mathematician wouldn't care about." $\endgroup$ Jun 11, 2010 at 4:06
  • 4
    $\begingroup$ The statement Con(ZFC) expresses a natural, fundamental feature of a central mathematical theory; it appears as a hypothesis in hundreds of theorems; and although we can't prove it is true, should it turn out to be false, there would be a profound foundational crisis. How much of this can be said about the Goldbach conjecture? $\endgroup$ Jun 11, 2010 at 12:18
  • 14
    $\begingroup$ For me, a mathematical statement counts as a "natural" independent statement from a formal system only if it makes no reference to the formal system itself (or closely related formal systems). The continuum hypothesis counts as natural. Con(ZFC) doesn't. By the way, I don't believe that a contradiction in ZFC would create a foundational crisis. We'd just analyze the contradiction and scale back to a weaker system that avoids the contradiction but that still suffices for 99.9% of mathematics. Kunen's inconsistency theorem didn't create a crisis; we just discarded Reinhardt cardinals. $\endgroup$ Jun 11, 2010 at 15:13
  • 4
    $\begingroup$ Timothy, re: "no intrinsic reason", there is very much something intrinsic to Goldbach, Riemann, or Mersenne conjectures that makes them unlikely to be independent of ZFC (or PA). Unprovability of those would imply incomprehensibly intricate, rigid structures --- strong enough to encode the syntax, models, or proof theory of a formal system --- in the distribution of primes. The opposite is true for Con(ZF) which does relates directly to a formal system. More details in my post: mathoverflow.net/questions/27755/… $\endgroup$
    – T..
    Jun 13, 2010 at 3:18
19
$\begingroup$

There are also some concrete examples in graph theory, such as Kruskal's tree theorem and the Robertson-Seymour graph minor theorem. These theorems about infinite sequences of graphs were actually proved (by infinitary methods in combinatorics) before it was realized that they are not provable by finitary methods.

Harvey Friedman devised finite versions of the Kruskal and Robertson-Seymour theorems that can be stated, but not proved, in Peano arithmetic. In fact, they are "more unprovable" than Goodstein's theorem, in that they require even stronger systems of arithmetic to prove.

$\endgroup$
18
$\begingroup$

A $\Pi_1^0$ statement is one of the form $\forall n\,\varphi(n)$, where $\varphi(n)$ is some recursively verifiable statement about $n$. This can be made more precise, but I want to keep the description this way, to give an idea of what some of the issues are. The negation of $\Pi^0_1$ statement, if true, is easily provable: After all, all it says is that some fixed number $n_0$ must have an easily verifiable property. You just have to exhibit a counterexample explicitly and it is straightforward to verify its validity.

In practice, of course, we know that there are computational issues that this ignores, but the point remains.

However, it is not so clear that, if true, a $\Pi^0_1$ statement must be provable. And, in fact, that is not the case. Goedel showed this, but his examples are not particularly natural. Now, if you prove that a $\Pi^0_1$ statement is not decidable from PA, the standard (first order) axioms of number theory, then of course the result must be true. Otherwise, its negation would have been provable.

There are a few natural combinatorial $\Pi^0_1$ statements that cannot be verified in PA. Harvey Friedman has worked hard to produce examples of this kind with intrinsic combinatorial interest (if not yet immediate appeal to number theorists), because most natural examples are more complicated: $\Pi^0_2$, essentially assertions that some function is total: For all $n$ there is some $m$ for which something straightforward to verify holds.

Ferretti mentioned Goodstein's theorem, and auniket mentioned Paris-Harrington. I like Goodstein's theorem, because a few years ago I managed to find a formula for the function that computes how long it takes the sequence starting with $n$ to stop. Since this is not provable in PA, the formula was just beyond what can be grasped in first order number theory, and that, I found very interesting.

A variant of Paris-Harrington is a result of Kanamori-McAloon, with which I've also done some work, showing combinatorially that the version for pairs gives rise to a function that grows precisle as Ackermann's function. The point is: Just because something is beyond the grasp of a formal system, does not mean it is beyond our comprehension. Very interesting combinatorics can still happen here.

Stillwell mentioned the graph minor theorem. This is more interesting, in that not only they are beyond PA, but also beyond significant strengthenings of PA.

All of these examples are provable in ZFC, the basic system of axioms of set theory. Harvey Friedman has produced natural examples that go beyond ZFC and involve large cardinals. His page is full of nice examples of this kind, mostly $\Pi^0_2$, but also (recently) several interesting $\Pi^0_1$ ones.

Still, as pointed out by agcl, in all of the $\Pi^0_1$ examples, there is a natural sense in which, once we show the statement is independent of the formal system, then we actually have that it is true.

Although Goldbach's conjecture is $\Pi^0_1$, another very famous problem in number theory, the twin primes conjecture, is not, at least not with our current knowledge. Neither it nor its negation are obviously true if verified independent. I am not saying there is any evidence whatsoever for assuming the twin primes conjecture is independent of PA, in fact, that would be more than unexpected. However, it is much more natural to expect that a natural $\Pi^0_2$ statement, such as this one, is independent, than it is to expect that for a $\Pi^0_1$. And it would be very interesting, because then we would need a different method for verifying its truth, since we would have consistency of both the statement and its negation, and no clear evidence of which holds in the usual (standard) model ${\mathbb N}$.

Coda: A recent thread mentioned a paper where it is claimed that all current approaches, if they show the independence of a $\Pi^0_2$ statement from PA, actually also show it from the (much) stronger system obtained by adding to PA all the true $\Pi^0_1$ statements. Although the claim is something of an exaggeration, it can be made more precise in terms of what kind of model theoretic arguments are used to show the independence. The natural combinatorial examples listed above all fall in this category: They are true, they are independent of PA, and they remain independent in the theory resulting from strengthening PA as explained. Harvey Friedman's examples in ZFC are more interesting in this regard.

[Edited to fix some obvious unintentional lies.]

$\endgroup$
3
  • $\begingroup$ +1 . $\endgroup$ Jun 11, 2010 at 3:06
  • $\begingroup$ You say: "The point is: Just because something is beyond the grasp of <i>a formal system</i>, does not mean it is beyond our comprehension."; I assume you mean here "a particular formal system" rather than "any formal system". $\endgroup$ Jun 11, 2010 at 9:14
  • $\begingroup$ @Hugo: Ha! Sure, I guess. This reminds me of a view that Stephen Hawking once mentioned about the laws of physics, that perhaps the "true ones" we actually cannot know, but at any point in history we have an approximation, and they improve over time (kind of converging to the true ones). $\endgroup$ Jun 11, 2010 at 14:04
9
$\begingroup$

In the paper "Skolem and pessimism about proof in mathematics" (Phil. Trans. R. Soc. A 2005 363, p.2409) Paul Cohen wrote:

"The view that I shall present differs somewhat from this, and is in a sense more radical, namely that it is unreasonable to expect that any reasoning of the type we call rigorous mathematics can hope to resolve all but the tiniest fraction of possible mathematical questions."

$\endgroup$
1
  • $\begingroup$ And still, as René Thom used to say, there is no rigorous definition of the notion of rigor. $\endgroup$ Apr 1, 2015 at 10:11
6
$\begingroup$

Again from combinatorics: The strengthened finite Ramsey theorem>. It was proved by Paris and Harrington that it is true, but not provable in Peano arithmetic. Wikipedia says: "This was the first "natural" example of a true statement about the integers that could be stated in the language of arithmetic, but not proved in Peano arithmetic".

$\endgroup$
0
$\begingroup$

There is already a lot of excellent answers, but I think it is useful to make rigorous your argument that "... if someone proves that Goldbach is not provable, then we would know that Goldbach is true."

You are making the jump from "Goldbach is not provable" to "there exists no counterexample to Goldbach's conjecture". But for that you first needs to assume the consistency of ZFC, because otherwise you can prove anything, and more crucially the soundness of ZFC, i.e., that it only proves true statements, because otherwise "Goldbach is not provable" can be simply a lie.

But if you do assume that ZFC is consistent and sound, then every unprovable statement of the form "for every $n$, property $P(n)$ holds" (for some sufficiently simple $P(n)$) is actually true, as consistency and soundness together with unprovability imply that there exists no counterexample.

This argument I took from the paper "Undecidable problems: a sampler" arXiv:1204.0299.

EDIT: Corrected, see comments.

$\endgroup$
12
  • $\begingroup$ That's not quite true - you need the property $P$ to be appropriately simple (barring additional assumptions, this means $\Sigma^0_1$). That is, you need "being a counterexample" to be absolute. $\endgroup$ May 8, 2015 at 14:21
  • $\begingroup$ Thanks for the correction. But could you expand on that? What would be a non-absolute counterexample? $\endgroup$ May 8, 2015 at 14:34
  • 1
    $\begingroup$ The point is that a counterexample to Goldbach, if it exists, will be both easy to find and easy to prove a counterexample. By contrast, for something like the Continuum Hypothesis, a counterexample might be (1) impossible to effectively describe, so ZFC wouldn't be able to even refer to it, and (2) impossible to prove a counterexample even if it were definable. Here, we learn nothing from the statement "ZFC doesn't prove CH," since ZFC just doesn't have the ability to build and verify a counterexample if one exists. (This is vague, but hopefully helpful?) $\endgroup$ May 8, 2015 at 15:32
  • 1
    $\begingroup$ Absoluteness is a kind of non-verifiability: let's say I have a model $M$ (nice and well-founded) of ZFC and a set $X\in M$. Now, $M$ might think $X$ has size continuum, in the sense that $M$ contains a bijection between $X$ and a set $A\in M$ which $M$ thinks is the set of all reals. But, there might be real numbers not in $M$ - for instance, if $M$ is countable. So there might be a "larger" model of ZFC, $N\supseteq M$, such that there is no bijection - in $N$ - between $X$ and the set $N$ thinks is $\mathbb{R}$. In $N$, $X$ might be a counterexample to CH. $\endgroup$ May 8, 2015 at 15:34
  • 1
    $\begingroup$ But I don't see the point of the downvote. Wouldn't it be more helpful to other people to correct the mistake instead of downvoting the answer? Is there still anything wrong with it? $\endgroup$ May 8, 2015 at 16:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.