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".)