From: waynebro@juliet.caltech.edu (Broughton, Wayne Jeremy)
Newsgroups: alt.atheism
Subject: Re: Undecidability and the FAQ
Summary: What is right and wrong with FAQ #21
Date: 11 Sep 92 20:47:00 GMT
Organization: California Institute of Technology
News-Software: VAX/VMS VNEWS 1.41

OK, I'll throw in my two bits. :-)

It seems that Brian Evans hasn't responded to the post from chisnall@cosc.
canterbury.ac.nz yet, so maybe it has already cleared things up for him; it
seemed to be the most succinct explanation, though the notation was a little
technical.  Anyway, I would like to try to explain everything as I see it. 
I am only trying to clarify things so I apologize in advance if I end up 
unnecessarily writing stuff that everybody knows.

First of all, I am a bit confused about what exactly various people have
been trying to claim, refute, or just say generally; the precise point
of discussion seems a bit nebulous.  I think the debate really centers
on whether a statement in the FAQ is correct (at least it started this
way and is the only relevance of this thread to alt.atheism :-).  BTW,
I am referring to the latest (Sep 2) version of the FAQ, entry #21.  In
fact, I have several comments on this FAQ entry (maybe of interest to 
you, mathew!).

The first sentence of the entry is "Godel's incompleteness result says
that in any formal system which is sufficiently expressive that it can
model ordinary arithmetic, one can formulate expressions which can never
be proven to be valid or invalid ('true' or 'false') within that formal
system."  To be pedantic, this is not strictly true, since as has already
been amply pointed out on this thread the conclusion only applies if the
system is _consistent_.  I think it would be better if it read "...in
any consistent formal system...".

The sentence that really seems to be the bone of contention is the one
"Note that if a proposition is undecidable, the formal system cannot
deduce anything about it -- not even that it is undecidable."  I hold 
that, strictly speaking, this statement is true, though it is sufficiently
vague that its truth seems more accidental than intentional, and it could
stand to be rewritten.  In fact I think the disagreement is somewhat a 
matter of interpretation.  Brian says the FAQ statement "isn't true in
practical terms".  Unfortunately, his attempts to correct it leave open
to interpretation vague phrases like "assuming that ZF is correct", 
"practical consistent system", "knowably undecidable (statements)", etc.
Perhaps these can be improved to give an unambiguous "pragmatic" statement.
But what I and other posters claim is that, purely from the viewpoint
of formal logic, the FAQ statement is correct.  I cannot tell if Brian 
agrees with this last sentence or not.


In article <6lsn6yh@lynx.unm.edu>, bevans@carina.unm.edu (Mathemagician) 
writes...
>                     ....since to have an inconsistent axiom
>system is to be unable to clearly prove things.

I would like to clarify what happens in an inconsistent axiom system:
every statement is a contradiction, both provably true and provably false.
As Brian points out many times, such a system is not of much practical use.
But note that none of its statements can be undecidable: quite the opposite!
So a theory with undecidable statements must be consistent, and so using
G.I.T.#1 we can agree with Brian,

>it may certainly be true that a theory is consistent if and only if it
>contains undecidable statements ....

except that it IS certainly true, for the appropriate class of theories.

Now an inconsistent theory can prove itself to be consistent (inconsistent
theories can prove anything they can state), but a consistent theory 
cannot prove that itself to be consistent, by G.I.T.#2!!  
Isn't logic fun??

So the FAQ statement holds: if a proposition in a given (sufficiently
powerful) theory really is undecidable, then the theory really is 
consistent, and so cannot prove that it is consistent, and so cannot
prove that the proposition is undecidable by the equivalence Brian 
observed above.

What about Brian's counterexample, the Continuum Hypothesis?
Godel & Cohen showed, within ZFC, that if ZFC is consistent then CH
is undecidable in ZFC.  Brian says that if we "assume" ZFC is consistent
at the outset then G & C showed, within ZFC, that CH is undecidable in
ZFC.  The problem is that ZFC cannot, by itself, justify this "assumption",
and so cannot, by itself, justify the undecidability of CH.

Brian claims that

>Godel's Second Theorm of Incompleteness is that it is undecidable
>whether or not the axioms are consistent.  Thus, we assume they are
>which allows us to claim that certain statements are undecidable.

and then formalizes this assumption as a
>"zeroth axiom" that the axioms are consistent.

But he has misstated G.I.T.#2: it really says that if the axioms are
consistent, then it is undecidable (from the axioms alone) that they
are.  But if they are not consistent, then it is very decidable that
they are not!  He then abuses the word "undecidable" to mean that he
is free to choose whether or not the axioms are consistent, thereby
justifying his use of the Zeroth Axiom.  I suppose he meant to add
Axiom 0 to ZFC to give ZFC0; of course this new system can trivially
prove (formally) that ZFC is consistent, but it cannot prove itself 
consistent, and we still don't have ZFC proving itself consistent.

Of course we all agree that ZFC is consistent and so we all agree 
that CH is undecidable in ZFC, but the FAQ statement stands: ZFC
cannot, by itself, prove that CH is undecidable.

(An aside: does anyone know of a generally accepted proof, outside
of ZFC, that ZFC is consistent?  Since ZFC seems to include most all
of ordinary mathematics, such a proof would have to be "meta-mathetical",
I suppose.  I am stabbing in the dark here.)


Enough babbling.  Back to the FAQ.
----------------------------------

It says, "Note also that all of these hypothetical formal systems [axioms
agreed to by both atheists and theists] tell us nothing about the actual
existence of God; the formal systems are just abstractions."  
I don't think I agree with this.  If some of the axioms agreed upon correspond
to statements about the real world, and if it is agreed that the real world
is logical (whatever that means), then logical consequences of these axioms
must also be true (or at least agreed upon) of the real world.  I will not
hold my breath waiting for an acceptable formal system that can adequately
define "god" and prove/disprove the statement "god exists", however. :-)

Finally, I don't think I have ever actually seen the G.I.T.'s used in an
atheism-related argument.  WHO exactly uses these theorems? (agnostics 
claiming that "god exists" is undecidable?)  And HOW exactly are they 
used?  I mean, G.I.T.#1 is a general existence statement; it cannot prove
that any particular statement is undecidable.

Alright, alright, I'm going already.

Wayne J. Broughton
waynebro@juliet.caltech.edu