Undecidability and the Truth of the Continuum Hypothesis

[funkstar]

Is undecidability strong enough to give us truth/falsehood, even though we cannot prove it inside any given theory?

Consider the continuum hypothesis. It is undecidable, so, clearly, there's no counterexample of a set with cardinality between the integers and the reals (in standard ZF). Otherwise, such a set would disprove the CH. Is this strong enough for us to argue (as a metatheorem) that the CH is actually true?

What does this imply for ZF with the negated CH as an axiom? Clearly, it can't be inconsistency, because the CH was undecidable, but something "feels wrong."

(Please feel free to get arbitrarily technical, btw.)

 

[matt grime]

The existence of a set with cardinality between the naturals and the continuum is certainly possible. It might even be in some model of ZF (in fact could well be). So, no CH is not 'actually' true.

 

[funkstar]

The reason I ask is that I recall an argument that if Fermat's Last Theorem was undecidable, then it would automatically be true. In ran along the lines that if it couldn't be proven false, then no counterexamples could exist. This certainly seems reasonable, so it was concluded that if FLT was undecidable, then ZF extended with ts negation would at least be $$\omega$$-inconsistent.

Besides the fact that we know that FLT is not undecidable, is there something wrong with this reasoning?

Why doesn't this reasoning extend to the CH as well?

 

[shmoe]

I recall something to that effect as well, if a statement could be proven false with a counterexample then it couldn't be undecidable, FLT and the Riemann Hypothesis for example. I would imagine that a precise formulation of this would involve being able to verify that your "counterexample" is actually a counterexample in a finite amount of time, like you could with FLT or RH, but not with CH.

I could be wrong though- it's been awhile and my understanding of this stuff was just enough to know that my understanding was dodgy and shouldn't always be trusted.

 

[chronon]

We don't actually know that Fermat's last theorem is provable from the standard axioms for the integers - there may well be non-standard models in which it is false. (see http://www.chronon.org/Articles/fermat_undecidable.html). However, in the case of the integers we feel that we understand them enough to distinguish between the 'true' integers and non-standard models of them*, and in the 'true' integers FLT is true. With transfinite set theory we don't have the same intuitive knowledge about what we are dealing with and so it is less reasonable to accept a statement just because we can't write down a counterexample.

* Of course this feeling might not be justified - see God gave us the integers...

 

[CrankFan]

Is undecidability strong enough to give us truth/falsehood, even though we cannot prove it inside any given theory?

Formal undecidability is with respect to a specific formal theory, not all of them. For example if you add CH to the axioms of ZF you get a formal theory in which CH is decidable.

What you're asking about only works if the statement in question is roughly of the form for all $$n \in \mathbb{N}$$, P(n) holds. Sentences of this form are known as $$\Pi_1^0$$ sentences. If a $$\Pi_1^0$$ sentence turns out to be false then there is a counter example in the natural numbers.

If a $$\Pi_1^0$$ sentence turns out to be independent of ZF then there can't be any counter examples because verifying simple arithmetic statements like 2 + 2 = 4 is trivial in ZF. If there are no counter examples then it must be true.

CH isn't a $$\Pi_1^0$$ sentence so you can't conclude that it is true on the basis of its independence from ZF.EDIT: Thanks to shmoe I finally got my $$\Pi_1^0$$ 's looking okay. Although I was expecting something more bold, like the Pi in \Prod, this wll do just fine.

 

[shmoe]

EDIT: can't seem to get the TeX working for Pi_0_1, which should be a capital Pi with subscript 1 and superscript 0

Maybe $$\Pi_1^0$$?

So the basic idea is that you would be able to systematically work your way through the P(n) statements and if a counterexample existed, you'd be able to find it in a finite amount of time?

 

[CrankFan]

If "for all n in N, P(n)" has a counter example: k then "not P(k)" is a theorem of ZF.

 

[funkstar]

Ok, that seem very reasonable.

Thanks.