I’ve always found mathematics and mathematicians mysterious though I must admit I have no formal relations with mathematics as such. In fact, my own competence in this subject is rather pathetic. But then I never talk about mathematics as mathematicians do. My intellect has been a frustrating point but it never affected my curiosity. But still I find mathematics to be an intriguing enigma which never ceases to amaze me. It is a deep mystery for me for many reasons, mostly from philosophical point of views. For example I really don’t understand the connection between universe and mathematics. Is mathematics a tool devised by humans to understand universe or is it really a language of universe? Mathematics seems to be ultimate model of rigorous reasoning. Mathematics is supposed to solve problems but at times it poses tough questions about its own existence. At times, it really punches our ideas, our intuitions and our reasoning very hard. This has happened many times.
For example, when Pythagoras discovered that square root of 2 is an irrational number, it made him greatly uncomfortable, really uncomfortable. It just didn’t go well with greek ideas of philosophies and intuition. It is said Pythagoras tried hard to suppress the finding that square root of 2 is irrational. In another case, Euclid’s axioms of geometry which are so simple that they are taught to us when we are merely 12-13 years old. But Euclid’s fifth axiom baffled mathematicians for several centuries. Euclid’s fifth postulate of parallel postulate states, “If a line segment intersects two straight lines forming two interior angles on the same side that sum to less than two right angles, then the two lines, if extended indefinitely, meet on that side on which the angles sum to less than two right angles.” It looks quite obvious. But mathematicians were not satisfied. Eventually, it turned out there are geometries such as elliptic geometry in which fifth postulate is false. The geometry Einstein used for Relativity Theory is non-euclidean geometry. But this doesn’t mean the geometry Euclid invented is false.
Hilbert, the Formalist.
We must know. We will know. – David Hilbert
In more recent history, more of such instances have happened. When Georg Cantor talked about different kinds of infinities, it made a lot of mathematicians uncomfortable. Cantor faced so much resistance that it affected his sanity. He suffered from repeated bouts of depression. He felt isolated and rejected. You might say infinity is infinity. What is there to talk about different kinds of infinities? But Cantor challenged this notion. At around the same time something else was going on. To put it mildly, mathematics was facing an existential crisis in a sense. It was something philosophical and fundamental. Mathematicians were solving problems. But Mathematicians were also questioning mathematics itself. Cantor was one of the central figures amidst this saga of crisis mathematics was beginning to face. Until then, mathematicians weren’t that much bothered about defining things. They didn’t bother to define what ‘+’ or ‘=’ means. Or what numbers like 1, 2, 5 and so on mean. They went along their intuitions just like we still do with these ‘+’ type of operations and numbers in daily life. When we say 1+1=2, we really think, subconsciously, that 1 banana and 1 more banana means 2 bananas. But mathematicians also asked what is to mean by ‘1’ and ‘+’ in logical terms in mathematical context. How to define them? This kind of reasoning led to Logic Theory and Cantor’s Naive Set Theory in particular. There was a reason why it was called naive. So during those periods, there were efforts to put mathematics on solid foundations. Geometry had already been properly formulated. It later turned out that, thanks to Russell, there were some problems with Naive Set Theory. Russell pointed out Naive Set Theory leads to some disturbing paradoxes such as Russell’s paradox. This made Hilbert, the ultimate formalist, uneasy. Around the same time, there were two factions among mathematicians: formalist and intuitionist. Hilbert was formalist. Poincare was intuitionist. Hilbert believed we can devise a rigorous mathematical system in which there is no ambiguity, every mathematical statement can be defined in clear notational language. Every mathematical truth can be ‘mechanically’ derived from axioms of mathematics. And the set of axioms will be consistent and provably so. In effect, he wanted mathematics to be consistent, complete and decidable. This was an ambitious task. No room for intuition. No ambiguity. As described above, Naive Set Theory proved to be a problematic. Attempts were made to resolve this mess. Most notable attempt was made by Russell and Whitehead. They took this task of redefining mathematics from the scratch. The together wrote three volumes of Principia Mathematica which were published in 1910, 1912 and 1913. This was a giant effort. To give you an idea, it took around 300 pages of Principia Mathematica just to prove 1+1=2. This was in a sense Hilbert’s program being executed.
During early 1920s, Hilbert proposed a program to put all of mathematics on solid axiomatic foundation. It should be noted that this is not the first time Hilbert talked about this for the first time. He was talking about it in 1900. It was just that he clearly stated his ambitions in 1921. In 1928, he posed Entscheidungsproblem or decision problem. Above, I talked about the terms consistency, completeness and decidability. Let me make these terms clear in brief. Consistency means one should not be able to prove a statement and its negation as well. You don’t want a theory in which you can prove both 1+1=2 and 1+1≠2. That would be absurd. Such system would be termed inconsistent. Completeness means every true statement should be provable within that system. Every true statement should formally follows from the axioms of that system. Finally, decidability means we can decide in advance whether some statement (or its negation) is provable or not. In hindsight, people always believed mathematics don’t produce wrong results and everything is provable. If there is some inconsistency, it is because we understood mathematics poorly. If we couldn’t prove something, this only meant it was only a matter of time when it would be proved. Hilbert went along these lines of thinking. He wanted mathematics to be pure, logical, structured, unambiguous and explainable without any aid of intuition.
Then Arrived Godel, The Disruptor
Hilbert’s program was doomed to fail. And it failed rather spectacularly. Its failure changed the mathematical philosophy forever. In 1931, Godel published 2 results which ended Hilbert’s program rather prematurely. His two results are known as Incompleteness Theorems. There were two of them. The first Incompleteness theorem deals with completeness aspect of Hilbert’s program. In simple terms, it says there are some true statements in a mathematical system which cannot be proved within that system. More specifically, a mathematical system can’t be both complete and consistent at the same time. It doesn’t matter what kind of axioms you chose or how many of them you chose. There will always be at least one statement which would be true but can’t be proved within the concerned system. Obviously, our bet is on consistency which means we have to sacrifice completeness. This was revolutionary and counter-intuitive result. In essence, Godel cleverly turned the statement “This statement is unprovable” in mathematical statement and showed it had to be true and unprovable. His proof is rather involved and used some innovative techniques. His second Incompleteness theorem was even more shocking. It simply says a system’s consistency just can’t be proved from within the system. If you have proved a system’s consistency, this means there was some inconsistency in axioms themselves. So you can only believe that the set of axioms you working with is consistent. There is nothing you can do about that. As I mentioned above, Godel’s proofs are too complex to be understood by laymen. But there is a way to prove them in just 2 lines and with no mathematics. More on that later.
(Apart from Incompleteness theorems, Godel also proved one theorem which is known as Completeness Theorem. For a casual reader, Completeness theorem is ‘exact opposite’ of First Incompleteness theorem. Incidentally, Godel proved Completeness theorem before Incompleteness theorems.) Godel was only 24 when he proved these results.
So, as we saw, Godel’s theorems shattered Hilbert’s dreams. The virtues of completeness and provable consistency became evasive. But what about decidability? Godel didn’t settle this question. So there was still some room for a technique which can be developed to decide whether a problem is provable or not. Godel said some truths can’t be proved. Can we decide which truth can be proved and which can’t be? The answer was provided by Alan Turing.
Welcome Mr. Turing!
Alan Turning is called father of modern computer science and justifiably so. His contribution to computer science is enormous and fundamental. He developed the rigorous notion of what is computability. He also showed there are problems which computers cannot solve. He devised a theoretical machine called Turing Machine which is capable of computing whatever can be computed, given enough time and memory. So far there is no such problem which is shown to be unsolvable by Turing Machine and yet has been solved otherwise. Turing Machine is such a powerful yet very simple idea. Suppose you want to find a counterexample for Goldbach’s conjecture. If you find one such example, Goldbach’s conjecture would be shown to be wrong. You write a program for this, run it on Turing Machine and wait for it to halt. If it halts at some point, may be after a million years, it simply means it has found a counterexample. After all, Turing Machine promises to solve any problem it is solvable at all. But it didn’t talk about how long it will take to solve. Not very helpful. Maybe we should be able to predict in advance whether it is going to halt in future. But Turing didn’t stop here. He went on to show that there were some problems which Turing Machine couldn’t solve. The famous Halting problem, discovered by Turing himself, was one such problem. On basic level Halting Problem says, given any arbitrary program and input for this program, one cannot decide whether Turing Machine is ever going to stop if it tries to solve that program. That means there can’t be no universal algorithm which can tell you in advance that Turing machine is going to stop at some point or it will continue to run. You simply don’t want to write a program which, when executed, never stops and sadly there is no way to decide whether a program will eventually output something. Let me illustrate this more clearly. Suppose you write a program to check whether some very large number is prime or not. Now I want to check the primality of the number. So you run your program on computer and feed the input. You wait and wait and keep waiting. You wish for some ways to check whether some program will eventually stop. Finally you get an algorithm to check this. You apply that algorithm on your primality testing program. It outputs that program will eventually stop. Notice that it doesn’t tell whether number is prime or not. It merely tells that your primality testing program will eventually decide that given number is prime or not. That is what decidability means. And Turing showed there is no such algorithm which can decide for all programs.
That means mathematicians will have to rely on their old school tricks and intuition. (Remember I already talked about how Hilbert wanted to eliminate the notion of intuition from mathematics?) Anyway, this conclusion was the final blow to Hilbert’s program. A consistent system can’t be complete. You cannot prove its consistency. And now you can’t talk about decidability. Game is over. Goodbye Hilbert’s absolute formalism. (By the way, almost around the same time, Alonzo Church also proved the same thing. In fact, his result came out before Turing’s. But Turing approach was more intuitive, tangible and visionary. Both are credited for solving the decidability problem.) Like Godel, Turing was only 24 when he proved his results.
Turing’s Work also Implies Godel’s results
Before I forget, I told you Godel’s theorems can be proved without any mathematics. The way Godel proved them is quite complex and involves some genius strokes such as Godel numbering. Godel assigned unique number to every symbol, operation and statements. He assigned the statement “This statement is unprovable.” a unique number. Anyway, we can deduce those theorems from Turing’s work. Think about what Godel said. He said a system can’t be both consistent and complete at the same time. Let me assume otherwise, that is a system can indeed be both consistent and complete at a time. If that is the case, every true statement should be provable. Obviously, we have axioms of that system. We write a program which generates every true statement which results from those axioms. Remember, every computer program and inputs to this program are merely long strings of binary digits. A program can take another program as its input. That is what your browser, which is a program, does when it runs some script which is another program. Also, halting problem is ultimately a mathematical statement which again is merely a string of binary digits in the framework of computer science. All we have to do is to write a program to enumerate all the theorems which follow from our axiomatic system. Finally, for a given program Q, we look for the statement “Q eventually halts” or “Q runs forever” in those theorems. Since our system is complete, we will eventually find one of these statements in our theorems. But this means we have found a way to decide whether Q eventually halts or runs forever. That is a contradiction. This means our system can’t be both consistent and complete. And that is just what First Incompleteness theorem is.
The crust of this whole historical story is that, no matter how we try to define things, there will always be some form of ambiguity which cannot be avoided. In mathematics, it is extremely difficult to define basic objects such as natural numbers. Provability is a weaker notion than truth. It is not the failing of mathematics. It is rather the failing of language in which mathematics is defined. This also means there will always be room for intuition based understanding of mathematics. Essentially Hilbert was indirectly trying to develop such a mathematical system which can be understood by computers. He kind of envisaged that computer should be able to enumerates all theorems from the axioms of the system. Of course computers didn’t exist even in theory back then. But in hindsight, Hilbert, in a sense, was talking about a computer language. If you read Godel’s original paper or Turing’s paper, you will see the structure of programming languages. Through this mathematical crisis, computer science was born. (One very serious caveat: I wrote this whole story on a very very basic level. All the technicalities has been sacrificed to make this blog more readable. If you are interested, you are advised to read from technical sources.)
It is said Godel’s work, in addition to Relativity, is probably the most misunderstood and abused work. In any case, it has profound implications on everything philosophical. For example, there is this race to find a Grand Unified Theory in physics which will explain everything. Now scientists say this is not possible in light of Godel’s work. In particular, see this Stephen Hawking’s lecture ‘Godel and End of Physics‘. Freeman Dyson (man, I admire him very very much) also concluded something similar.
P.S. – Let me be honest. There are hundreds of articles and blogs you can find on Internet which is so similar to this blog that I may be excused of plagiarism. The purpose of writing this blog is something personal. I wanted to write this blog the way I understood things. That is the whole point.