Tale of math reach its border
Frege wait for printer
End of last tale, Frege sit at his desk in Jena. Volume two of Grundgesetze at the printer. Twenty-five winter of work nearly done. The dream of Leibniz almost finished.
Then on , letter arrive at Frege door. Letter come from big island called Britain. Letter written by young big brain Frege never meet. Young big brain only thirty winter old. Name is Bertrand Russell.
Letter is short. Letter is polite. Russell open with admiration. Then Russell ask one simple question.
One question. A life’s work destroyed.
what Russell ask
Frege system rest on one idea. Any property define a set. Property “is a man” define set of all men. Property “is bigger than three” define set of all number bigger than three. Sound obvious. Sound innocent. Nobody for two thousand winter find anything wrong with it.
Russell ask sneaky question. Take property “is a set that does not contain itself”. Most set do not contain themselves. Set of all dog is not itself a dog. Set of all number is not itself a number. Set of all spoon is not itself a spoon. So most set fit this property. By Frege rule, this property must define a set. Call this set R. R is set of all set that do not contain themselves.
Does R contain itself? Two possible answer.
Suppose R contain itself. Then R have the property of containing itself. But R only contain set that do not contain themselves. So R cannot be in R. Contradiction. Suppose R not contain itself. Then R have the property of not containing itself. R is exactly the kind of set that belong in R. So R must be in R. Contradiction again.
Both answer wrong. No third answer. The set R cannot exist. Frege rule say it must exist. This is Russell paradox.
The trouble is self-reference. R is defined by talking about itself. Paradox
crawl in. Big brain in centuries ahead see this same shape in many costume. The liar say grug is
lying
. The barber shave every man who not shave himself; does he shave himself? Same trick
every time.
why one question break everything
Reader might say: small problem. Just rule out one weird set. Problem solved. But it not work like that.
Big brain have rule called principle of explosion. From one contradiction, you can prove anything. Two plus two is five. Moon is made of cheese. Grug is queen of England. Each one provable. In any system with one contradiction.
Suppose grug have proved some statement P. P is both true and false. Pick any other statement Q. Q can be silly. Q can be anything. Q can be grug queen of England. P is true. So “P or Q” is true too. At least one is true. But P is also false. So in “P or Q”, the truth must come from Q. Therefore Q. Argument work for any Q. Anything Q at all. The system is broken. Totally and finally. One contradiction make every proof worthless.
Twenty-five winter of careful building. One simple question. Whole building collapse.
Frege answer with grace
Frege get the letter. Frege read it. Frege understand at once.
Frege write back six day later. . Frege not angry. Frege not in denial. The English translation is usually:
Your discovery of the contradiction has surprised me beyond words and, I should almost like to say, left me thunderstruck, because it has rocked the ground on which I meant to build arithmetic.
Volume two of Grundgesetze already at the printer. Frege cannot recall it. Twenty-five winter of work cannot be unprinted. Frege do something rare and brave. Frege add an appendix at the last moment. Nothing worse can happen to a scientific writer than this. The foundation of his work shaken. After the work is finished. Frege say so plainly in the appendix. A letter from Mr Bertrand Russell put him here. Frege try to patch the system. Patch not work. Frege half-know it. Frege publish anyway. With the patch. With the admission.
Frege barely write about logic again. He go to ancient spirits in . The big brain who try to ground all of mathematics in pure logic go to ancient spirits thinking he fail. He not fail. He find the limit. But he cannot see this from where he stand.
Russell try to fix it himself
Russell feel the weight of what he do. Russell work on the same project as Frege. From across the sea. Before reading Frege, Russell think the foundation could be made solid. Russell break Frege foundation. Now Russell decide he must build the thing back up himself.
Russell partner with old teacher Alfred North Whitehead. The two write the foundation of mathematics again. This time without the hole. The work take ten winter. They publish in three volume between and . Title is Principia Mathematica. Same title as Newton famous book from two centuries before. Borrowed on purpose. They want to do for logic what Newton did for physics.
Their solution: theory of types. Sort everything into level. Level zero is plain object: dog, spoon, number. Level one is set of plain object: set of dog, set of spoon. Level two is set of set: set of all set of dog. And so on, up the tower. Now make hard rule. A set at level n can only contain thing at level n minus one. Set of dog (level one) can contain dog (level zero). It cannot contain itself. Itself is at level one, not level zero. Wrong type. The whole question “does this set contain itself” become not allowed to ask. Like asking what colour the number seven is. Just not a question that fit the rule.
The Russell paradox cannot even be stated in this system. The hole is closed. But the price is high. Theory of type is heavy. Every simple thing now need careful tracking. Which level does this live on? Which level does that live on? Mathematician using the system feel like he carry many heavy box up a hill.
Famous part of Principia: to prove that one plus one equal two from pure
logic, the book take many hundred page. The thing every five winter old know come out only deep into
Volume One. Proposition ✱54.43. With small remark from the author: the above proposition
is occasionally useful.
The full proof come later still. Volume Two. After addition is
properly defined.
Hundreds of page to prove a thing every child know. Big brain love to mock this. Big brain miss the point. Principia not trying to teach anyone what one plus one is. Principia trying to show one thing. Arithmetic can be reduced to pure logic. No leap. No hidden assumption. Every step legal. Hundreds of page is the cost of being honest. Russell and Whitehead pay it. Their book stand. Their book also stand as warning. This is what it cost to keep the foundation safe. Maybe too high a cost.
Hilbert have plan
Across the water, in German town of Göttingen, another big brain watch all this.
David Hilbert born in . One of the most respected mathematician alive. After Russell paradox, one question keep him awake. Naive set theory have a hole at the bottom. So how does any mathematician know their own foundation safe? Maybe other hole hide.
Hilbert do something nobody do before. He treat the formal system itself as a thing to study. Mathematics is what mathematicians do inside the system. Hilbert step outside. He ask: what is the system itself like? Does it have hole? Can it prove every truth? Can it prove its own safety? Hilbert call this new study metamathematics. Mathematics about mathematics.
To ask such question, Hilbert must first say what a formal system is. Three thing. A precise language for writing statement. A set of axiom: starting statement assumed true. A set of rule: ways to get new statement from old. Run rule on axiom long enough. You get every theorem the system can prove. Nothing else. Nothing left to taste. Nothing left to instinct. A machine could check every step.
This is now the standard picture of formal system. Hilbert give it.
In the early 1920s, Hilbert lay out a plan. What should such a system achieve? Plan come to be called Hilbert programme. Plan have four goal.
- Goal one: formalise everything.
- Take all of mathematics. Write it in one precise formal language. Spell out every axiom. Spell out every rule of inference. Make it so a machine could check every proof.
- Goal two: prove it consistent.
- Show that the system can never derive a contradiction. Use only safe reasoning to do this. Hilbert call this finitary method. So no one can later complain the proof of consistency rest on something shaky.
- Goal three: prove it complete.
- Show that every true statement of mathematics can be derived from the axiom. No truth out of reach.
- Goal four: prove it decidable.
- Show there exist a mechanical procedure. Give it any mathematical statement. Procedure decide in finite step: is this provable?
If Hilbert programme succeed, mathematics is forever safe. Every truth reachable. Every proof checkable. Every question answerable. In principle. Just by following the rule.
Hilbert give a famous speech in his hometown Königsberg. . The day before he retire. Six word from this speech get carved on his tombstone:
Wir müssen wissen, wir werden wissen.
We must know, we will know.
Hilbert not know it on that podium. The wall already crack. Same Königsberg gathering. Day before. Smaller room. A quiet twenty-four winter old big brain stand up at a roundtable. He read a short announcement. Big brain name was Kurt Gödel. Hilbert not in the room. But one mathematician was in the room. Young Hungarian called John von Neumann. Reader will meet him again in a later tale. Von Neumann understand at once what Gödel say. He pull Gödel aside after the session for a long conversation.
Hilbert give his big speech the next day. By all account, he have no idea what just happened. The foundation he want to prove safe. Already shown out of reach. The day before.
young big brain Gödel break plan
Kurt Gödel born in . City of Brno. Then in Austria-Hungary. Quiet child. Study at the University of Vienna. Not say much. Think a lot.
Year . A few moon after the Königsberg announcement. Gödel publish the full paper. Title: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. On formally undecidable proposition of Principia Mathematica and related systems. Title name Principia Mathematica on purpose. Paper aim straight at Russell book. And at Hilbert programme. Gödel is twenty-five winter old.
Paper contain two theorem. They become known as Gödel incompleteness theorem. Among the most important result in the history of mathematics.
Gödel pull a trick. He show every statement about numbers can itself be turned into a number. Each symbol get a number. Each formula is a sequence of symbol. So each formula get a number too. Built from its symbol numbers. Each proof is a sequence of formula. So each proof get a number too. Built from its formula numbers.
Trick is called Gödel numbering. Once you have this, statement about number can also be statement about statement about number. Because the statement are number. The system now able to talk about itself.
Gödel use this to build one specific sentence. Call it G. G say:
G has no proof in this system.
Sometimes this sentence make grug brain hurt. But grug try to tell you simple. One rule first: a consistent system cannot prove false thing. Ever. Now ask: is there a proof for G? Two case. If yes, the system prove G. But G say there is no proof. So the system prove a false thing. The system not consistent any more. If no, then G is true. G say it has no proof, and indeed it has none. True. But now the system has a true sentence it cannot prove. The system not complete any more. Either way, the system lose something. Suppose it consistent. Then it cannot prove G. So a true sentence sit outside its reach. So it not complete. Consistency force incompleteness. The system that want to prove every truth must accept it can prove false thing. The system that want to be safe must accept some truth always out of reach. Cannot have both.
This is the First Incompleteness Theorem. Any consistent formal system big enough for ordinary arithmetic must contain true statement it cannot prove. Hilbert goal three is gone. Completeness is impossible. Not because Hilbert pick the wrong system. Because no sufficiently powerful system can be complete. The wall is built into the world.
Gödel use the same trick a second time. Imagine another statement inside the system. Call it Con. Con say: this system is consistent. Now ask: can the system prove Con? Two case. If the system prove Con false, then the system is admitting it can prove false thing. The system not consistent. Useless. If the system prove Con true, something strange happen. The argument grug just give for the First Theorem use only ordinary arithmetic reasoning. Adding number. Comparing number. Checking whether one number is the Gödel number of a proof of another. All ordinary. So the system itself is strong enough to carry out the same argument. Gödel show this. Painful detail, but he show it. So the system can prove this conditional inside itself: if I am consistent, then G has no proof. Now the system also prove Con, which say I am consistent. Stick the two together. The system prove G has no proof. But G say G has no proof. So the system has proved G. But the First Theorem already show: a consistent system cannot prove G. Contradiction. So a consistent system cannot prove Con either. The system simply cannot prove its own consistency. Not from inside.
This is the Second Incompleteness Theorem. No powerful enough consistent system can prove its own consistency. Not using only its own resource. Hilbert goal two is gone too. The clean finitary consistency proof Hilbert want cannot exist. To prove a system consistent, you must step outside the system. Step into something stronger. But you cannot prove the stronger thing consistent. Not without stepping outside it too. And so on. Ladder never end.
Hilbert old by then. By most account he eventually accept the result. But the world around him changing. Much darker than incompleteness. The political demon about to eat Göttingen entirely. Most mathematicians in Hilbert school are Jewish. Most driven out. Or worse. In the years that follow. Hilbert go to ancient spirits in . In a Germany he no longer recognise. Few people come to his funeral. War make funeral small.
Gödel survive him by many winter. But Gödel own life become strange. A demon possess him. The demon
whisper one thing over and over. Your food is poisoned.
Gödel believe the demon. He only eat
what his wife Adele prepare. Adele go to hospital in . Gödel stop
eating. He go to ancient spirits in . Weighing about
thirty kilogram. The man who prove no formal system can trust itself. In the end cannot trust any
food his wife not check.
History is cruel. This tale makes grug always a bit sad.
one question still survive
After Gödel paper, three of Hilbert four goal are settled. Formalisation, succeeded. Completeness, impossible. Internal consistency proof, impossible. Fourth goal still open.
Fourth goal is decidability. Is there a mechanical procedure? Give the procedure any mathematical statement. Does it decide in finite step whether the statement provable? Not whether it is true. Just whether some proof exists for it.
Question have a name. Hilbert and his student Wilhelm Ackermann name it in their textbook. The German word: Entscheidungsproblem. Mean decision problem.
But what is a mechanical procedure? Everyone use the word. Nobody say exactly what it mean. Everyone know one when they see one. Long division is a mechanical procedure. Adding two number is a mechanical procedure. Following a recipe is almost a mechanical procedure. But what do all mechanical procedure share? Written down precisely. No hand-waving. No example. No “you know what grug mean”. Nobody have such a definition.
what grug learn
Frege try to ground all of mathematics in pure logic. One question from Russell collapse the foundation. The problem is self-reference. One contradiction is enough to break a whole logical system. From one contradiction, every statement become provable.
Russell and Whitehead rebuild on theory of type. Self-reference is no longer allowed. The cost is heavy.
Hilbert see the crisis and turn it into a plan. Make mathematics safe forever. Formalise. Prove consistent. Prove complete. Prove decidable. Hilbert invent the whole way of thinking about formal systems to even ask such question.
Gödel break the plan. No system big enough for arithmetic can prove every truth. No such system can prove its own consistency.
But mathematics itself stand. Inside the border: enormous, working mathematics. Solid as ever. At the border: certain self-referential question. No formal system can settle them from inside itself. Beyond the border: nothing. Most discipline never get to know their limit. Mathematics know.
One question survive. Hilbert decision problem. Is there a mechanical procedure that decide which statement have proof? Still open. But to answer it, someone must first say what mechanical procedure mean. Word everybody use. Nobody have defined.
what grug worry about next
Two thousand winter of mathematics. At the centre now sit a question. Mathematics itself cannot answer it. Not without language from somewhere new.
What is computation? What is an algorithm? When something is mechanical, what exactly does that mean?
One more thing worth grug saying. Russell paradox and Gödel sentence look different. Both are the same trick underneath. Take a thing. Make it talk about itself. Watch it break. Self-reference is the hammer. Reader will see the hammer swing again very soon. The big brain who answer Hilbert last question use it too. Same hammer. Soon a third time.
In year , two young big brain answer the question. Working separate. Ocean apart. One in England. Other in America. Not knowing the other work on it too.
Grug come to them next.