First of all : thanks to Sandeep Seth for lending me a wonderful book that introduced me to Godel’s theorem ( and Escher’s Paintings ) The name of the book is “Godel,Escher,Bach The Eternal Golden Braid”.

A wow book !

After the theory of sets was invented Mathematicians started facing

a new kind of problem . Problems related to statements that were neither

true or false . Statements whose truth was indeterminate . FOr example take

the following statement :

A set G that contains all sets that dont contain themselves .

Now does G contain itself ?

Lets suppose it does . But then there is a problem because then the

definition of G would be wrong .

Now lets suppose that it does not . But then the set G would not contain a

set G ( which does not contain itself ) . And that is incomplete .

Paradox ! Paradoxes of this kind are called Russel’s Paradox .

Mathematicians didnt like such inconsistencies in their Math . So

Bertrand Russel and Whitehead tried to make a new system that has

no inconsistiencies. They called it Principia Mathematica .

Another Great Mathematician Hilbert had bigger plans . He challenged

Mathematicians to make a formal system that is complete and consistent

and we could base all mathematics on the top of that .

What is a formal system :

Any system in mathematics contains some axioms . These axioms are

things you assume to find theorems . For example lets invent a new

system . We have a string : KO . The rules of the system are :

a) if we have O at the end then we can add a T at the end of the

string .

b) if we have OT ate the end of the string we can add another OT at the

end .

c) If we have 2 sets of OT at the end then we can remove them .

so our three rules and our strings are axioms . Stuff we start off with .

And a new string that you may invent is a theorem .

Is the string K a theorem in our system ? lets check :

start off with KO and apply rule a to it . Our string becomes KOT .

Now apply rule b we get KOTOT . NOw apply rule c we get K .

So K is a theorem in our system . Any mathematical system proceeds

in a similar way . Theorems and axioms . SO either a statement can be

a theorem( it is true ) or it is false ( its opposite is a theorem ) .

How Hilbert’s program was to reduce mathematics to string analysis .

So that all you need to know is the axioms and you can prove anything .

Just keep applying axiom after axiom and u get a new string which you

call a theorem . You can express any theorem in math as a string :

for example :

there exists no x,y,z : x^3 + y^3 = z ^3

is a statement of fermat’s last theorem

So Hilbert’s program tries to reduce Mathematics to string analysis .

And he propopsed to start off with Principia Mathematica .

But Kurt Godel published a theorem in 1931 that destroyed such hopes .

He said 2 important things :

1) YOU CAN REDUCE ANY FORMAL SYSTEM TO A SYSTEM INVOLVING NATURAL NUMBERS.

for example in our system we can give K a no 10 . O is 2 and T is 3 .

so KO is 1023 and rule c) is that if you have anything followd by 2323 then

you can remove that . SO K is a theorem means that 10 is a valid

no in our system . Similarly all formal systems can be expressed in

terms of natural numbers and then in terms of each other .

b) YOU CAN ALWAYS CREATE A NEW THEOREM THAT CANNOT BE PROVEN ( AND ITS

NEGATION CANNOT BE PROVEN TOO . Ie ANY COMPLETE FORMAL SYSTEM CONTAINS

UNDECIDABLE THEOREMS ) . THis means that there will always be theorems

that will escape the net of our formal methods . These are kind of

theorems that reference themselves . Godel showed this for Principia

Mathematica and then since all formal systems are equiivalent thus

it applies to all branches of Mathematics . Thus provability

is weaker than a formal system .

So what this showed was that Mathematics cannot be made into a formal

system and that the role of intution is still very important .

THis was a great blow to Hilbert’s program . Now no one tries to make

systems that dont have inconsistencies . Because Godel showed that

you cannot do that . If a system is strong enough then there will

always have inconsistencies .