2

Continuum hypothesis (CH) states that there can be no set whose cardinality is strictly between that of integers and real numbers. Godel, 1940 and Paul Cohen,1963 showed that CH can neither be proved nor be disproved.

How can we assert that a statement is true if it cannot be proven? What are the bases to make such assertions? I know this is a deep subject, and I confess that I don't have technical tools to understand everything on this topic. But I would like to have some understanding on why CH has to be true if it cannot be proven.

Do you have any other examples where statements are absolutely true (i.e with 100% certainty) but cannot be proved??

EDIT: Is "CH cannot be proved" the same as "proof will not exist ever in future"? Or is it that "CH cannot be proved" implies the insufficient human knowledge to prove it?

  • 1
    Some statements are true by virtue of being non-provable (in a given axiom system). Example: Consider the statement P = "There is no odd perfect number." It's currently unknown whether this statement is true or false. Suppose that it's proven that P is undecidable in ZFC. Then it must be true! Because if it's false, then there is an odd perfect number, which can be demonstrated within ZFC by simply writing down the number and its factors. That would make P provably false. Since P is not provably false, it must be true. – Janet Williams Sep 15 '13 at 17:31
  • One cannot prove that the law of gravity will be true tomorrow, but one can believe it's true because the odds are exceedingly great that it will be. – Dave L. Oct 7 '13 at 2:54
  • From a logical standpoint, the only reason is axiomatic. From a scientific standpoint, inductive knowledge is highly reliable and all science bases its work upon them. – Gabriel Oct 20 '17 at 18:30
6

You say:

"But I would like to have some understanding on why CH has to be true if it cannot be proven."

I don't think that there is a consensus that CH has to be true at all. Goedel famously thought it was false (despite showing its consistency with the axioms of ZFC using his inner model construction). Hugh Woodin has conducted two programmes to try and determine the truth value of CH; one (which he has moved away from) using a device called Ω-logic to prove ¬CH and another using his `Ultimate-L' construction with which he hopes to prove CH. Still others (such as Joel Hamkins) think that the plethora of set theoretic models show CH to have no truth value.

One argument that has been advanced for CH having a determinate truth value (we just do not know which) is based on the quasi-categoricity result for second-order ZFC. Attributed to Zermelo, it (roughly) states that given any two models of second-order ZFC either the two are isomorphic or one is isomorphic to an proper initial segment of the other. The key thing to note about these models is that they must be of inaccessible cardinality (which is way bigger than the set of real numbers). Hence the reals must be the same in any two models of ZFC2, and thus CH has a determinate truth value (we just don't know which). Of course, one should be aware that in that argument second-order resources play a key role, which are massively controversial in the context of set-theory.

As for a statement that is obviously true but independent from an axiom system, one example is the Goedel sentence for Peano Arithmetic. Very informally the Goedel sentence (G) for PA holds iff there is no proof of (G) in PA (in the actual proof this uses some recursion theory and is stated by coding the syntax of the formal system). Hence if PA is consistent then (G) is not provable in PA, if it were then there would be no (code of a) proof of (G) in PA, and hence (G) would be unprovable. If on the other hand, its negation is provable, then it's not the case that there is no (code of a) proof of (G), hence there is a proof of (G), thereby contradicting the consistency of PA. Thus neither (G) nor ¬(G) is provable. However, if we look at what the Goedel sentence for PA informally says, then we can see that (assuming the consistency of PA) it must be true; (G) says that (G) is not provable,unprovable and further it is the case that (G) is not provable. One should be aware that, with this argument, in order to show the Goedel sentence to be true one has to assume the consistency of PA. Interestingly this turns out (in a formalised setting) to be equivalent to the consistency statement for PA, and hence there are questions as to actually how much the Goedel sentence line of argument shows.

  • Replace "$\Omega$" with "Ω" (the semicolon is part of the string) – Hunan Rostomyan Sep 19 '13 at 0:42
  • Brilliant, thanks very much. I was a bit confused as to why LaTeX wasn't working! – Neil Barton Sep 19 '13 at 7:00
  • Oh, no problem Neil. Welcome to the forum! – Hunan Rostomyan Sep 19 '13 at 7:24
  • I like your answer, but I am puzzled by the role you see for inaccessible cardinals. The proposition "There exists and inaccessible cardinal" has the same status as CH in ZFC - i.e., it is undecidable. Do you mean that extending ZFC to make the existence of inaccessible cardinals decidable would necessarily determine the status of CH? – Nick R Sep 20 '14 at 21:37
  • You certainly can't decide CH with a proof from any number of large cardinals for subtle reasons to do with the nature of forcing (though you can get some of 2-order arithmetic e.g. PD). However, it's a theorem (Zermelo 1930) that for any two models of 2-order ZFC (with the full semantics; Henkin won't do!) either they're isomorphic or one's isomorphic to an initial V_\kappa of the other for \kappa inaccessible. Since all sets of reals and functions between reals and sets of naturals are formed in the first few stages above V_\omega, CH has the same truth value in every model of ZFC_2. – Neil Barton Sep 22 '14 at 16:54
5

The Gödel–Cohen result establishes the independence of CH from ZF (with or without AC), not from any set theory whatsoever. In general, independence is a logical relation between a set of axioms and a sentence: sentence S is independent of axioms Γ just in case Γ neither proves nor refutes S (more precisely: just in case neither S nor its negation is in the closure of Γ under direct derivability).

The truth of CH is a semantical matter and has no business in independence proofs. CH may be believed to be true by experts, for reasons I cannot hope to understand. Some might even believe that it has to be true, but whether CH is true or not, the important result here is that: if ZF is consistent, it is compatible both with CH and with its negation.

As for examples of truths that cannot be proved, again, I would like to emphasize that provability, like independence, is a relative notion: sentence S is provable in syntactical/proof system Γ just in case there is a proof in Γ with S as its conclusion. Once the relativity of provability is recognized, it's easy to come up with examples of intuitively true but nevertheless unprovable statements such as the following sentence: "everything is self-identical". That sentence is not provable from the axioms of propositional calculus, but it is provable from the axioms of first-order logic with equality.

Update: As regards the edit, if a sentence (e.g. CH) cannot be proved in a system (e.g. ZFC), then it cannot be proved in that system at time t, for any time t. Provability has very interesting connections to modal logic, but it itself is not a notion that depends on time or human knowledge. I wonder, however:

Question. Can, in the context of intuitionistic logic, such a notion of time-dependent provability be realized, say by treating worlds in intuitionistic Kripke models as moments and letting a formula φ be provable at time t in model M just in case (M, t) forces φ? I suspect that the answer is 'yes'.

  • "CH, like Goldbach's Conjecture, is believed to be true by experts, for reasons I cannot hope to understand." -- My understanding is that most experts consider CH to be false. Of course "most" is a relative term here. I don't think anyone's taken a poll. – Janet Williams Sep 14 '13 at 23:26
  • Thanks Janet, edited; I had no intention to take a stance on that. – Hunan Rostomyan Sep 14 '13 at 23:30
1

Logical monism says that either CH is true, or false; logical pluralism says that it is true, or false or undetermined. In other words you get to decide its truth.

Essentially this is because there isn't just one set theory (monism) but many (pluralism).

One should view this in the same way as the passage from euclidean geometry to non-euclidean geometry.

As far as believing something to be true before proving it, Descarte would have said its because the truth is clear & evident.

1

Roughly speaking, in mathematics there are three kinds of statements: Statements which can be proven to be true, statements which can be proven to be false, and statements which can neither be shown to be true nor shown to be false.

With the continuum hypothesis, it has been shown that it cannot be proven to be true, and that it cannot be proven to be false. Unlike what you are stating, there is no reason to believe that it would be true that I would know of, so you should carefully check your source for that information.

There is a famous conjecture called the "Goldbach conjecture", which states that every even number n >= 4 is the sum of two prime numbers. It is considered very very likely that there is no counterexample to this conjecture, but no proof to this conjecture has been found (yet). With this conjecture, we can say that if it is false, then there is a proof that it is false: If the conjecture is false, then there is an even number n >= 4 that is not the sum of two primes. In that case, we could just write down all prime numbers <= n and check that no two of them add up to n, and we would have a proof that n is not the sum of two primes and that therefore the Goldbach conjecture is false.

In other words, if the Goldbach conjecture is undecidable (there is no proof either that it is true nor that it is false), then there cannot be a counterexample to the conjecture, which means it is true.

But this conclusion depends on an argument that is very specific to this particular problem. It works for some other problems, but not for many. And we cannot draw any conclusions from our current inability to prove something. We can only draw conclusions if we can prove that some statement is unprovable.

  • Yes, Goldbach is an excellent and relevant reference in this context. You may note a small typo in your answer - viz. "check that no two of them add up to 4". – Nick R Sep 20 '14 at 22:58
1

There must be indemonstrable truths because if everything were demonstrable, there would be an infinite regress (cf. the regress problem).

Aristotle's Posterior Analytics bk. 1 ch. 3-4 (72b5) says:

Some hold that, owing to the necessity of knowing the primary premisses, there is no scientific knowledge. Others think there is, but that all truths are demonstrable. Neither doctrine is either true or a necessary deduction from the premisses. The first school, assuming that there is no way of knowing other than by demonstration, maintain that an infinite regress is involved, on the ground that if behind the prior stands no primary, we could not know the posterior through the prior (wherein they are right, for one cannot traverse an infinite series): if on the other hand—they say—the series terminates and there are primary premisses, yet these are unknowable because incapable of demonstration, which according to them is the only form of knowledge. And since thus one cannot know the primary premisses, knowledge of the conclusions which follow from them is not pure scientific knowledge nor properly knowing at all, but rests on the mere supposition that the premisses are true. The other party agree with them as regards knowing, holding that it is only possible by demonstration, but they see no difficulty in holding that all truths are demonstrated, on the ground that demonstration may be circular and reciprocal.*

Our own doctrine is that not all knowledge is demonstrative: on the contrary, knowledge of the immediate premisses is independent of demonstration. (The necessity of this is obvious; for since we must know the prior premisses from which the demonstration is drawn, and since the regress must end in immediate truths, those truths must be indemonstrable.) Such, then, is our doctrine, and in addition we maintain that besides scientific knowledge there is its originative source which enables us to recognize the definitions.

*[Circular demonstration ultimately leads to saying "if A is, A must be—a simple way of proving anything." (source).]

See this for the rest of this Aristotle quotation, followed by St. Thomas Aquinas's commentary on it.

0

I share your inability concerning the technical tools and I am far from understand much of it, but I have heared some sidenotes on this in lectures I visited.

Set theory got axioms (at least one kind of set theory, and I think the one in question). From these axioms CH cannot be proved and cannot be disproved. That means, that CH is independent of the axioms of set theory.

0

We should stop caring so much about whether things that cannot be proved are or are not true.

The problem here is a throwback to the idea that the statement is either true or false. Negation is a natural part of human language, but there is no indication that it is a part of greater natural processes.

Even in human psychology, negation is transient and problematic -- aside from effects like some forms of OCD and Tourette's syndrome where the force of a thought is increased by concentrating on its opposite, there is a very direct problem with this outside the realm of disorder -- Don't think of pink elephants.

Approaches to mathematics like Constructivism and Intuitionism that do not admit the Law of the Excluded Middle throw much larger pieces of reality into the realm of the 'might be true but will remain uproveable'. I would suggest this is forward progress, and that allowing a wider range of possible axioms to be considered will help us to work out much more interesting mathematics and a better perspective on ourselves.

So my answer is 'We should never consider the unproven true in mathematics, and you should stop caring about the truth of things that are non-constructively "proven" as well.'

On the other hand, outside mathematics, we consider the highly likely to be true all the time. ('The sun will come up tomorrow' cannot be proven.) And we should admit non-problematic axioms for consideration on the grounds that they seem likely to be true. Ultimately proofs contingent on different ranges of axioms, like the Axiom of Choice, or its opposite, the Axiom of Determinacy, may prove to be so interesting we will admit those axioms as presumed in different domains. That does not make them 'true' only 'useful'.

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.