Liar's paradox, Godel's theorem and the existence of God..

The liars paradox arises from a famous statement in logic "This statement is false". If the statement was true, then its false and if it was false, then its true, hence leading to a contradiction. But this statement is not just a clever play of words. Infact it carries some very powerful mathematics with it. The statement is often considered a slightly modified version of the famous Godel's First Incompleteness theorem. The theorem was put forward by Godel in a 1931 paper.(I read somewhere that this theorem is in a way equivalent to Turing's Halting problem in computer science, no idea how though)

The official statement is "Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true,but not provable in the theory"


What it means?? Simple, for every formal consistent theory T that uses some amount of number theory in it, there is always a statement called the Godel statement G which is true but cannot be proved in T, which means the theory is incomplete and not every true statement can be proven. If however G can be proved in T, then it means T is inconsistent and some theorem of T is in contradiction with itself.

So what is this Godel statement G that seems to be so damn powerful? Well, it is not unique and can vary from system to system in which its applied but in a meta-logical level it can be simply states as: The statement G for a system, is that "This statement cannot be proven in this formal system" (i.e) G="G cannot be proven in this system". Now lets examine this statement closely. If this statement can be proven in the system, then its false since we assumed the statement cannot be proven, and thus we have just proved a false statement, which implies the system is inconsistent. If the statement cannot be proven, then its true and we have a true statement which cannot be proven in the system, making it incomplete. Still confusing?? Well here is a better version of the proof I found on the net and one I enjoyed a lot. It might need to be read about 2-3 times to really get it but once you do, you realise that the proof is so clever and sneaky, its actually embarassing to relate to. These are the steps:

1. Someone introduces Gödel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all.
2. Gödel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine.
3. Smiling a little, Gödel writes out the following sentence: “The machine constructed on the basis of the program P(UTM) will never say that this sentence is true.” Call this sentence G for Gödel. Note that G is equivalent to: “UTM will never say G is true.”
4. Now Gödel laughs his high laugh and asks UTM whether G is true or not.
5. If UTM says G is true, then “UTM will never say G is true” is false. If “UTM will never say G is true” is false, then G is false (since G = “UTM will never say G is true”). So if UTM says G is true, then G is in fact false, and UTM has made a false statement. So UTM will never say that G is true, since UTM makes only true statements.
6. We have established that UTM will never say G is true. So “UTM will never say G is true” is in fact a true statement. So G is true (since G = “UTM will never say G is true”).
7. “I know a truth that UTM can never utter,” Gödel says. “I know that G is true. UTM is not truly universal.” QED :)


The result is quite significant as it lead to the second Incompleteness theorem, gave an answer to Hilberts second problem and so on and so forth. Yeah, yeah lot of jibber jabber and thingamajings it can do but whats the use to anyone outside core mathematics and comp sci, you ask!! Well here is the interesting extension of this result. Many have tried to show that if we were to construct religion as a formal system T with the existence of God as a fundamental axiom, then we will be able to prove using the theorem that either the axioms are inconsistent and must be self-contradicting, hence calling into question the existence of God!! or the system must be incomplete and there are lot of things still not known in the religion itself, hence putting a dent on religious organisations that claim to know and control every aspect of the religion. But then again, there has been a lot of doubt+opposition to this, as many claim that it simply is not possible to construct something as important as faith like a mathematics based system.
There is another side to using this result as well. It remains an open question till date whether the entire universe can be modeled as a logical system (ie) like one giant computer. If it can be, then the fact that certain aspects of it can be never be explained by us becomes an inherent implication. So then it becomes possible for us to make a statement like "God does exist" which COULD (note: i say could be and not is) be true but can never be proven, not because of our inability to do so, but of the inherent nature of the universe itself!!

Nonetheless its an awesome result \m/ and one that has made me google and read many many pages on its implications outside the realm of maths and computer science. Hope its sparked the same interest in you guys as well.

Cheers
Gnut