6
$\begingroup$

For example, let's say that Goldbach's conjecture turns out to be unprovable. This would mean that a program cannot devise a way to check whether any counterexample exists. This seems to mean that there in fact is no counterexample - as we can develop a program that checks until some particular number, then if it stops, then write a program that starts from that number to some number and so on. This is all finite. If an even integer that cannot be represented by the sum of two primes is found, then the process would be finite.

This all seems for me to imply that a theorem is in fact true - but I am not sure if this is right reasoning.

Edit:

My intention when I wrote "unprovable" was independent. That's my mistake.

OK. So, let's say Goldbach's conjecture is independent of PA, but we prove Goldbach's conjecture in a stronger (informally, more powerful) theory (I guess there are many...). This would mean (correct me if I am wrong here) that we select one model of PA, let's say standard one, and then prove that the conjecture is true in that model using a more powerful theory.

So as Asaf says, ZFC has no one standard model - so is that the reason why consistency of continuum hypothesis cannot be settled, while other theorems that relate to PA technically can be settled as true or not in particular model?

Edit 2:

I know that continuum hypothesis can be settled in an extension of ZFC (as either true or false for a particular model of ZFC, and it would depend on different kinds of extension) - so a better rephrase of the edit above would be: can there be any statement of PA that cannot be proven true or false for a particular model of PA using a more powerful theory? And can anyone tell me more about

$\endgroup$
  • $\begingroup$ What do you mean by "statement of PA that cannot be proven true or false for a particular model of PA"? In general, just proving a statement of PA is the same as proving that the statement holds in the standard model of PA, and there are certainly many particular statements of PA which particular stronger theories cannot prove. $\endgroup$ – Carl Mummert Jun 26 '13 at 12:00
6
$\begingroup$

There are two reasons why the Goldbach conjecture could turn out to be unprovable: either it is false or it is independent.

If it is false, then there is some counterexample somewhere that we may or may not find someday. This isn't particularly interesting.

If it is independent, then it is not provable that a counterexample exists (this is what you were saying in the question, but for this you need the negation of the Goldbach conjecture to be unprovable). What does this mean? Well, if the conjecture was false, then there would be some counterexample, some large integer not expressible as a sum of two primes. But then we could (in principle) write a proof that this integer is a counterexample, going through all of the pairs of primes below it and adding them. There is a finite number of cases to check, so such a proof would exist. But we were assuming that it is not provable that a counterexample exists. Therefore the conjecture must in fact be true!

Now, this argument is very dependent on this particular context. First of all, we have a standard model of PA, where we can (by default) interpret things as true or false. By the completeness theorem, if the Goldbach conjecture were independent, it would be true in some model of PA, but that model might not be the standard model.

Secondly, it is important that the Goldbach conjecture is a very simple statement. It has a single quantifier (it is what is called a $\Pi^0_1$ statement). As soon as we would have to deal with more quantifiers (for example, checking that "for every foo some bar exists such that baz") we wouldn't be able to convert the existence of an arbitrary counterexample into a proof as we did here.

$\endgroup$
  • $\begingroup$ @sets I'm not sure I understand your question. If a statement is independent of your theory, you need to use additional information about your particular model to determine whether the statement is or isn't true there. This additional information will tend to be "external" to your theory. $\endgroup$ – Miha Habič Jun 26 '13 at 11:31
  • $\begingroup$ @MihaHabič sorry for unclear comment. I edited my question, so I guess that clarifies the matter. $\endgroup$ – sets Jun 26 '13 at 11:33
6
$\begingroup$

Yes.

When there is a standard interpretation of a theory, for example the natural numbers have a standard model. Then if something is independent of the theory, but true in the standard model then it is often regarded as true.

Good examples are the Paris-Harrington theorem and the Goodstein theorem, which are true in $\Bbb N$ but the first-order theory of $\sf PA$ cannot prove them.

It should be remarked that not all mathematical theories have standard models, or even "intended interpretation". There is no such model of $\sf ZFC$, so in a very deep sense the continuum hypothesis is independent from $\sf ZFC$. (In a fit of nomenclature confusion, there is a concept of standard models of $\sf ZFC$, but this is not the same things as the standard model of $\sf PA$.)

$\endgroup$
  • $\begingroup$ Many people do think there is an intended interpretation of ZFC, of course, the one that consists of all pure well-founded sets. Of course there is no way to tell whether CH is true in that interpretation. $\endgroup$ – Carl Mummert Jun 26 '13 at 11:15
  • $\begingroup$ @Carl: Of course, this is why we still have the term "a standard model of $\sf ZFC$", but there is no model which is unique up to isomorphism like we have in the cases of $\Bbb N$ and $\Bbb R$. $\endgroup$ – Asaf Karagila Jun 26 '13 at 11:40
  • $\begingroup$ !Asaf: for people who believe the concept of "all pure well founded sets" is sensible, there is indeed a unique class model (up to isomorphism) that contains all these sets. The isomorphism is constructed by transfinite induction on rank, level-by-level. $\endgroup$ – Carl Mummert Jun 26 '13 at 11:43
  • 1
    $\begingroup$ I am raising this point mostly because the existence of a unique intended interpretation of ZFC has been, for a long time, a common (if not dominant) view among set theorists. The novelty of Hamkins' recent "multiverse" argument is precisely that it is incompatible with the existence of an intended interpretation of ZFC. $\endgroup$ – Carl Mummert Jun 26 '13 at 11:53
  • $\begingroup$ Carl, my point is that a universe is not a model. $\endgroup$ – Asaf Karagila Jun 26 '13 at 13:16

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.