Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

On page 424 of the following paper:

S. Feferman, Harvey M. Friedman, P. Maddy and John R. Steel, ``Does Mathematics Need New Axioms?'' The Bulletin of Symbolic Logic, Vol. 6, No. 4 (Dec., 2000), pp. 401-446

John Steel makes the following remark in footnote 29:

There is the very remote possibility that one could show ZFC settles the questions without actually exhibiting the relevant ZFC-proofs. Goldbach's conjecture and the Riemann hypothesis are $\Pi_1^0$ statements, so one cannot prove them independent of ZFC without also proving them.

Could someone explain to me what kind of result/principle he is referring to here?

I'm guessing it's something of the form: ''For any $\Pi_1^0$ statement $\phi$ in PA (or, possibly, some weaker arithmetic) Ind(ZFC, $\phi$) iff some condition.'' The condition obviously can't be PA $\vdash \phi$ because, by soundness, that would imply that $\phi$ is not independent. But I can't think what other condition would justify Steel's remark.

share|improve this question
2  
The paper can be downloaded from the Bulletin's site, math.ucla.edu/~asl/bsl/0604/0604-001.ps –  Andres Caicedo Jan 10 '13 at 21:59
add comment

4 Answers 4

up vote 12 down vote accepted

I think what John Steel (not Steele) was referring to is a lot simpler than forcing and $\Pi^1_2$ absoluteness. Consider Goldbach's conjecture. If it were false, so there's some even number $n>2$ that is not the sum of two primes, then this fact could be proved in ZFC, and indeed in far weaker systems. The proof would consist of just the calculations checking, for each $k<n$, that at least one of $k$ and $n-k$ is composite (and checking that $n$ is even and $>2$). This shows that, if the Goldbach conjecture is false then it's refutable in ZFC. Therefore, if I knew that the Goldbach conjecture was independent of ZFC --- meaning it's neither provable nor refutable --- then, since it's not refutable, I'd know that it can't be false.

Summary: If we prove that the Goldbach conjecture is independent of ZFC (or even prove half of that, namely that it can't be refuted in ZFC), then we'd have established that it's true.

As indicated above, the same applies with ZFC replaced by far weaker theories; Peano arithmetic is more than enough.

The same also applies to the Riemann Hypothesis, but the argument is more complicated. The point is that, just as in the case of the Goldbach conjecture, if the Riemann Hypothesis were false, then this could be proved in ZFC by just writing out an appropriate computation. Unlike the Goldbach case, though, it's not so obvious what the computation should be. I believe it amounts to computing a sufficiently accurate approximation to a contour integral, over a contour that goes around an off-the-crtical-line zero of the zeta function.

The property of "if false then refutable by a mere calculation" is basically what $\Pi^0_1$ means in the passage cited from Steel.

share|improve this answer
    
I see that Carl Mummert posted an essentially equivalent answer while I was typing mine. Think of mine as a more detailed version of the first paragraph of his. –  Andreas Blass Jan 10 '13 at 20:54
    
if "the Goldbach conjecture is independent of ZFC (or even prove half of that, namely that it can't be refuted in ZFC), then we'd have established that it's true." - true absolutely? Or true w.r.t. some other "layer" of axioms, eg: modus ponens, excluded middle...? What if it's not refutable in ZFC but refutable in some other system like ZF+AD? –  alancalvitti Jan 10 '13 at 21:51
    
On the Riemann hypothesis reformulated as a $\Pi^0_1$ claim: mathoverflow.net/questions/31846/… –  Andres Caicedo Jan 10 '13 at 22:18
1  
@alancalvitti: (1) The truth of the Goldbach conjecture would be established on the same axiomatic basis as its irrefutability. (2) If the Goldbach conjecture were refutable in ZF+AD but not in ZFC, then the Goldbach conjecture would be true and ZF+AD would be omega-inconsistent –  Andreas Blass Jan 10 '13 at 22:28
    
@AndreasBlass, can you explain the terms and relationships above in a geometric context? For example, "sum of a triangle's inside angles equal $\pi$" is independent of the Euclidean axioms without parallel postulate. However this statement is true in Euclidean geometry (ie, with the parallel postulate) and false in non-Euclidean geometries (ie, with parallel postulate substituted by no parallel or multiple parallel lines). Are you saying that the statement $\theta_1 + \theta_2 + \theta_3 = \pi$ is true and Euclidean and non-Euclidean geometries (or perhaps one of these) are omega-inconsistent? –  alancalvitti Jan 11 '13 at 1:25
show 4 more comments

To prove a $\Pi^0_1$ statement $\phi$ is independent of PA means we have to prove PA does not prove $\phi$ and that PA does not prove $\lnot \phi$. Now $\lnot \phi$ is $\Sigma^0_1$, and PA has the property that it can prove any true $\Sigma^0_1$ statement. So if PA cannot prove $\lnot \phi$, then $\lnot \phi$ is false, so $\phi$ is true. The same holds for ZFC, or any other theory whose arithmetical consequences include PA.

The key here is that the proof that PA doesn't prove $\phi$ would be in a system stronger than PA. So there is no contradiction; it's just that a sufficiently strong system, in proving $\phi$ is independent of PA, would also be able to prove $\phi$ is true.

I think the key to understanding the footnote is to look at the sentence to which it is attached:

However, we should recognize that until the problems are actually settled this will almost certainly never be more than an educated guess.29

The two sentences in the footnote are separate comments on that phrase; the second sentence of the footnote is not an elaboration of the first sentence of the footnote.

share|improve this answer
add comment

The reason is that $\Pi^1_2$ statement about the natural numbers is absolute between transitive models of ZFC (with the same ordinals, of course). That means that if $M\subseteq N$ are two "nice" models of ZFC which have the same ordinals, and $\varphi$ is a $\Pi^1_2$ statement about the natural numbers, then $\varphi$ is true in both of them, or false in both of them.

Our main method of proving independence of statements is by a technique called forcing. We start with a "nice" model of ZFC and we extend it by adding a new set, and the result is another "nice" model and they both have the same ordinals. For some statements we may assume that the first model satisfies them and show that the extended model does not, or vice versa. This way we prove a statement is independent of the axioms of ZFC, that is to say that ZFC cannot prove nor disprove it (if ZFC is consistent, of course).

So what we know is that relatively simple statements about the natural numbers cannot be forced to be true, or false. General statements, like the continuum hypothesis can be forced from one truth value to the other.

That been said, it might be another way of proving independence of statements, but currently we mostly know about forcing and compactness, and compactness is not always that useful.

share|improve this answer
    
Thanks a lot for the super quick response, but I'm afraid I don't understand. What is M[G]? What are we assuming about M? I'm sorry but I don't see how Steele's remark follows from this at all...Is the idea this: Let's start with any model M of ZFC and then force a model 'M[G]' in which $\phi$ is true (or false), then $\phi$ is true or false in the model we started with? But how does that ensure it is provable in PA? Why couldn't it turn out to be undecidable? Could I convince you to expand on your answer? –  Chuck Jan 10 '13 at 20:32
    
By the way, I am not the one who downvoted –  Chuck Jan 10 '13 at 20:32
    
@Chuck: I edited. –  Asaf Karagila Jan 10 '13 at 20:38
add comment

Let me add a footnote to Andreas Blass's answer.

Suppose $T$ is a theory which extends PA (or indeed, extends Robinson Arithmetic). Then, for the reasons indicated, if $T$ is consistent, it is $\Pi_1$ sound. [For suppose $\varphi$ is a false $\Pi_1$ sentence. Then $\neg\varphi$ is a true $\Sigma_1$ sentence and so provable in PA. Hence if $T$ proved $\varphi$ it would be inconsistent. Contrapose.]

So suppose you come up with e.g. some Weird and Wonderful set theory $W\&W$ that can do a modicum of arithmetic. And suppose that in $W\&W$ you can prove e.g. the Riemann Hypothesis or Fermat's Last Theorem. Then you don't have to believe in the existence of $W\&W$'s superduperweirdo cardinals, or whatever. You just have to believe that $W\&W$ is consistent -- and bingo, you have an argument for the Riemann Hypothesis. (Echoes here, of course, of the Hilbert Program!)

I remember thinking this was rather magical when I first came across this observation when the world was very much younger: and students can still find it very striking.

share|improve this answer
    
Peter's "you don't have to believe etc" is related to what Steel calls the instrumentalist dodge on the linked paper. –  Andres Caicedo Jan 10 '13 at 23:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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