This article is from the Atheism FAQ, by mathew meta@pobox.com with numerous contributions by others.
"Godel's Incompleteness Theorem demonstrates that it is impossible for
the Bible to be both true and complete."
Godel's First Incompleteness Theorem applies to any consistent formal
system which:
* Is sufficiently expressive that it can model ordinary arithmetic
* Has a decision procedure for determining whether a given string is
an axiom within the formal system (i.e. is "recursive")
Godel showed that in any such system S, it is possible to formulate an
expression which says "This statement is unprovable in S".
If such a statement were provable in S, then S would be inconsistent.
Hence any such system must either be incomplete or inconsistent. If a
formal system is incomplete, then there exist statements within the
system which can never be proven to be valid or invalid ('true' or
'false') within the system.
Essentially, Godel's First Incompleteness Theorem revolves around
getting formal systems to formulate a variation on the "Liar Paradox".
The classic Liar Paradox sentence in ordinary English is "This
sentence is false."
Note that if a proposition is undecidable, the formal system cannot
even deduce that it is undecidable. (This is Godel's Second
Incompleteness Theorem, which is rather tricky to prove.)
The logic used in theological discussions is rarely well defined, so
claims that Godel's Incompleteness Theorem demonstrates that it is
impossible to prove (or disprove) the existence of God are worthless
in isolation.
One can trivially define a formal system in which it is possible to
prove the existence of God, simply by having the existence of God
stated as an axiom. (This is unlikely to be viewed by atheists as a
convincing proof, however.)
It may be possible to succeed in producing a formal system built on
axioms that both atheists and theists agree with. It may then be
possible to show that Godel's Incompleteness Theorem holds for that
system. However, that would still not demonstrate that it is
impossible to prove that God exists within the system. Furthermore, it
certainly wouldn't tell us anything about whether it is possible to
prove the existence of God generally.
Note also that all of these hypothetical formal systems tell us
nothing about the actual existence of God; the formal systems are just
abstractions.
Another frequent claim is that Godel's Incompleteness Theorem
demonstrates that a religious text (the Bible, the Book of Mormon or
whatever) cannot be both consistent and universally applicable.
Religious texts are not formal systems, so such claims are nonsense.
 
Continue to: