Yesterday I was opportune to watch Dr Raja elucidate the proof of Godel 's
incompleteness theorem .
I still do not know much details of the theorem so I writing it down here in an informal manner.
Basically, what is states is " A statements can be constructed in an axiomatic system which is true but can not be proved or disproved using the axioms of the given axiomatic system ". Or the other statement goes like "No consistent axiomatic system can be complete".
The example that Dr Raja explained goes something like this.
Let there be an alphabet sigma = { (, ), P , N , ~ }
Let there be expression X \in sigma^*
Let us define N(X) to be X(X) called the norm of X
There are four kind of sentences in this language
P(X) - P(X) is true iff X is printable
~P(X) - ~P(X) is true iff X is not printable
PN(X) - PN(X) is true iff N(X) is printable
~PN(X) - ~PN(X) is true iff N(X) is not printable
Let us also have a machine which prints only true sentences. ( in other words only true sentences are printable by the machine )
So now, if X is printable, so is P(X)
Given that a machine prints X then P(X) is true but will the machine print it??
or in other words, is the machine able to print all the true sentences???
The answer to this question is NO
Can you form a sentence which is true in the system discribed above but still won't be printed by the machine?
Hint : Because this is a self referential system, one can think of a sentence which tries to make statement about its own printability.
If you can not think of such a sentence...dont worry as I also was not able think of that then.
The answer is ~PN ( ~PN ) the sentence is true and yet it is not printable. the negation of the sentece is PN ( ~PN ) is false hence won't be printed by the machine.
For axiomatic system one can try to substitute the concept of printability to provability and can derive similar example as well as conclusion.
I have written down whatever I have understood from the talk and whatever I could remember. The information may not be precise or some incosistency may have been introduced because of the long path of information transfer :D
I wish I get such opportunities frequently :-) I am looking forward to IRL workshop for that.
