Notes: Friday 19 March 2004

Schedule

• Since we will not cover everything you need to know for PS6 in class until Monday, you now have two options for Problem Set 6:
  • Turn it in on Monday, 22 March as originally scheduled, but without answering questions 7 and 8.
  • Turn it in on Monday, 29 March (one week later, answering all questions).
• Monday, 22 March: Read GEB, Aria with Diverse Variations and Chapter 13. This chapter proves that the halting problem is not decidable, and introduces the Church-Turing Thesis (which we will explore more in later classes). You will not be assigned to read Chapter XIV, but it goes into more depth on Gödel's proof and is recommended.
• Problem Set 7 will be out on 29 March and due on 7 April.
• Problem Set 8 will be out on 7 April; part I will be due on 12 April, part II will be due on 26 April (last day of class).
• Exam 2 will be handed out on 14 April and due on 19 April.

Notes

Axiomatic System — a formal system that attempts to codify a branch of knowledge into axioms and inference rules that produce all true statements.

What does it mean for an axiomatic system to be incomplete?

What does it mean for an axiomatic system to be inconsistent?

What can we say about an axiomatic system that is complete and consistent?

Undecidable — a statement is undecidable in a given axiomatic system if it cannot be proven either true or false inside that system.

Russell's Paradox

S is the set of all sets that are not members of themselves.
Is S a member of itself?

If S is an element of S, then S is a member of itself and should not be in S. If S is not an element of S, then S is not a member of itself, and should be in S.

Gödel's Incompleteness Theorem: All logical systems of any complexity are incomplete: there are statements that are true that cannot be proven within the system.

Gödel's Proof: (condensed)
1. G: This statement of number theory does not have any proof in the system of Principia Mathematica.
2. If G were provable, then PM would be inconsistent. If G is unprovable, then PM would be incomplete. Hence, PM cannot be both complete and consistent!

Links

• Aristotle's Logic
• Gödel's Incompleteness Theorem — several short explanations of what Gödel proved
• Around Gödel's Theorem — hyper-textbook by Karlis Podneiks
• On Formally Undecidable Propositions Of Principia Mathematica and Related Systems [PDF] — Gödel's original paper. It starts:

  The development of mathematics in the direction of greater exactness has–as is well known–led to large tracts of it becoming formalized, so that proofs can be carried out according to a few mechanical rules. The most comprehensive formal systems yet set up are, on the one hand, the system of Principia Mathematica (PM) and, on the other, the axiom system for set theory of Zermelo-Fraenkel. These two systems are so extensive that all methods of proof used in mathematics today have been formalized in them, i.e. reduced to a few axioms and rules of inference. It may therefore be surmised that these axioms and rules of inference are also sufficient to decide all mathematical questions which can in any way at all be expressed formally in the systems concerned. It is shown below that this is not the case, and that in both the systems mentioned there are in fact relatively simple problems in the theory of ordinary whole numbers which cannot be decided from the axioms. This situation is not due in some way to the special nature of the systems set up, but holds for a very extensive class of formal systems...

In connection with the interview for his US citizenship, Gödel once told me that for this occasion he had studied how the Indians had come to America. Einstein and O.Morgenstern were his witnesses, and Morgenstern has told different people about aspects of the event. The following account is given by H-Zemanek and E.Kvhler. Even though the routine examination G was to take was an easy matter, G prepared seriously for it and studied the US Constitution carefully. On the day before the interview G told Morgenstern that he had discovered a logical-legal possibility of transforming the United States into a dictatorship. Morgenstern saw that the hypothetical possibility and its likely remedy involved a complex chain of reasoning and was clearly not suitable for consideration at the interview. He urged G to keep quiet about his discovery. The next morning Morgenstern drove Einstein and G from Princeton to Trenton. Einstein was informed; on the way he told one tale after another, to divert G from his Constitution-theoretical explanations, apparently with success. At the office in Trenton, the official in charge was Judge Philip Forman, who had inducted Einstein in 1940 and struck up a friendship with him. He greeted them warmly and invited all three to attend the (normally private) examination of G.

The judge began, "You have German citizenship up to now." G interrupted him, "Excuse me sir, Austrian." "Anyhow, the wicked dictator! but fortunately that is not possible in America." "On the contrary," G interjected, "I know how that can happen." All three joined forces to restrain G so as to turn to the routine examination.
From Hao Wang, Reflections on Kurt Gödel.

Years ago, the Princeton physicist John Wheeler began to wonder whether Heisenberg's uncertainty principle might not have some deep connection to Gödel's incompleteness theorem (probably the second most misunderstood discovery of the 20th century). Both, after all, seem to place inherent limits on what it is possible to know. But such speculation can be dangerous. "Well, one day [Wheeler recounts] I was at the Institute of Advanced Study, and I went to Gödel's office, and there was Gödel. It was winter and Gödel had an electric heater and had his legs wrapped in a blanket. I said, 'Professor Gödel, what connection do you see between your incompleteness theorem and Heisenberg's uncertainty principle?' And Gödel got angry and threw me out of his office."
Jim Holt, Uncertainty About the Uncertainty Principle: Can't anybody get Heisenberg's big idea right?,
Slate, 6 March 2002.