From: Mike Oliver
Subject: Re: Continuum Hypotheisis
Date: Wed, 22 Dec 1999 13:29:53 -0800
Newsgroups: sci.math
Keywords: independence vs undecidability
Jonathan Hoyle wrote:
> No need to consider it a "quibble", as
> I find I learn better when I am corrected even on the smaller details.
Well, as long as you're in the mood -- about your use of the term
"undecidable". Your usage here is not entirely nonstandard, but
it's potentially confusing (perhaps even to you) because of
you could confound it with the quite different notion of an
"undecidable theory".
A "decidable theory" is one for which you could write a computer
program that, given a sentence, is guaranteed to terminate and to
tell you whether that sentence is in the theory or not. For example,
the first-order theory of infinite abelian groups is decidable if
I remember correctly; the theory of the integers (by which I mean
all first-order statements that are true of the integers) is not
decidable (nor even r.e. axiomatizable).
But no *single* statement can be undecidable in this sense. I can
write two computer programs, one that prints "CH is true" and halts,
and the other that prints "CH is false" and halts. One of these
programs correctly decides the truth value of CH (we just don't
know which one). Undecidability can only enter in when you have
infinitely many questions to decide.
The better term for what you mean is "independence". Saying
"CH is independent of ZFC" conveys the content of what Goedel
and Cohen proved much more clearly than saying "CH is undecidable".
(Quibble on the quibble: some use "sigma is independent of T"
to mean "T neither proves nor refutes sigma", but others use
it to mean only "T does not prove sigma". If you want to be
sure no one misunderstands you on this point, you can say
"CH is independent of and consistent with ZFC".)