Suppose we found a proof that "The Twin Prime Conjecture cannot be proven", without any conclusion as to the conjecture itself being true or false.

Is it then possible for the conjecture to be true? or, must the conjecture then be false for some reason? or, must this proof of unprovability be flawed?

(I'm using this specific example to help understand if any similar simple conjectures could be provably unprovable. I have my doubts on whether a simple conjecture can be provably unprovable since, instead of making conclusions for an infinite number of inputs like the Halting Theorem does, we are here talking about just one true/false conclusion.)

  • $\begingroup$ you must specify where it's true or false. If it's unprovable in ZFC, for instance, then it's not true nor false in ZFC. $\endgroup$ – user40276 Aug 15 '14 at 5:26
  • 2
    $\begingroup$ Maybe the history of the Continuum Hypothesis's independence of ZFC would be of interest to you (en.wikipedia.org/wiki/Continuum_hypothesis) $\endgroup$ – user105475 Aug 15 '14 at 5:27
  • 4
    $\begingroup$ The twin prime conjecture has the form $\forall n\exists p> n R(n,p)$ where $R$ is an easily verifiable (recursive) statement. This is a $\Pi^0_2$ sentence, and there is no a priori way of concluding anything about its veracity from its unprovability. The Riemann Hypothesis, on the other hand, is $\Pi^0_1$: $\forall n R(n)$ where $R$ is a recursive predicate. If unprovable (in $\mathsf{PA}$, say. Or $\mathsf{ZFC}$, it makes no difference) then it is actually true because its negation is $\Sigma^0_1$, and all true $\Sigma^0_1$ statements are provable: (Cont.) $\endgroup$ – Andrés E. Caicedo Aug 15 '14 at 6:43
  • $\begingroup$ If $R$ is recursive, then $\exists n R(n)$ is true iff for some specific $k$, $R(k)$ is true, and the latter is verifiable directly. $\endgroup$ – Andrés E. Caicedo Aug 15 '14 at 6:44
  • $\begingroup$ Godel's first incompleteness theorem implies that it can actually be true but unprovable (this is different from being independent of axioms) en.wikipedia.org/wiki/… $\endgroup$ – Pauly B Aug 15 '14 at 14:28

There is an important issue with statements of the form "$X$ is unprovable": in what system is $X$ unprovable? We assume here that $X$ is some consistent statement written in some formal language.

Statements provable with no non-logical axioms are known as logical validities. Few interesting mathematical statements are phrased as logical validities. So the fact that $X$ is unprovable without non-logical axioms tells very little about $X$. On the other hand, if $T$ is the conjunction of some finite set of axioms sufficient to prove $X$, then $T \to X$ is a logical validity.

What if $X$ is unprovable from some larger set of non-logical axioms? That mainly tells us that those axioms are not strong enough to prove $X$. In other words, the fact that $X$ is unprovable from a set of axioms often tells us both about $X$ and about that system of axioms. As long as $X$ is consistent, we could always choose a stronger set of consistent axioms that is able to prove $X$ (e.g. we could take $X$ itself as an axiom).

In many concrete examples, the unprovable of $X$ from some system of axioms tells us more about the system of axioms than it tells us about $X$. For example, the combinatorial principle in Goodstein's theorem is unprovable in Peano arithmetic. The main interest in this is that, when we really look at the result, it shows us something new about provability in Peano arithmetic. It also helps us understand the combinatorial principle more deeply, but in this case we already have a very good understanding of the combinatorial principle which comes from its proof in ZFC.

This is a common pattern in mathematical logic. When we examine the proof that a principle is unprovable in a particular system, it often tells us as much or more about the system as it tells us about the principle - particularly when we scrutinize the unprovability proof intensively to try to extract the general method.

| cite | improve this answer | |
  • $\begingroup$ I know this is not rigorous, but it seems to me that the "human thought system" could never be rigorously defined (this probably is evidenced by Godel's theorems). Anyway, if it helps you answer my question, suppose all proofs used only the methods shown in your favorite proof of the Prime Number Theorem. $\endgroup$ – bobuhito Aug 15 '14 at 14:42
  • $\begingroup$ This is slowly convincing me that a conjecture can not "have a proof of unprovability" and be true. Would you agree? In your words, we could always scrutinize such a proof and say that it didn't include some reasonable axiom, so some proof method was not considered. To answer my original question, then, this means that we will either find a hole/flaw in the proof or we will conclude that TPC is false. $\endgroup$ – bobuhito Aug 15 '14 at 16:00
  • $\begingroup$ If you mean a proof that the conjecture is not provable in any consistent system, then you're right that we cannot establish that for any true conjecture. Because the system consisting of the conjecture itself (and any other true axioms we want) will be a consistent system, if the conjecture is true. $\endgroup$ – Carl Mummert Aug 15 '14 at 18:37

If a conjecture X is unprovable that can be translated to the following:

if X is true no contradiction can be derived

if X is false no contradiction can be derived

Both of these must be true because otherwise X would not be unprovable (we could merely choose one of the appropriate routes and eventually find a contradiction)

That being said it becomes evident then that the truth/false value of X is independent of the system of proving being used.

So once something has become unprovable in a fixed system of mathematics. It becomes meaningless to ask if the statement is true or false in that same system.

Hope that clarifies a thing or two :)

| cite | improve this answer | |
  • 1
    $\begingroup$ For arithmetical statments it seems however natural to wonder if they are true in the standard model of arithmetic. $\endgroup$ – Archimondain Aug 15 '14 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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