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 .