Foundations of Computer Science Fall 2007 For today you should have: 1) Read from Casti and answered the questions in notes16. 2) Finished your Prolog project. 3) Prepared for a quiz. For next time, you should: 1) Prepare a presentation on your project. 2) Read Nagel and Newman and answer the questions below. The MIU System -------------- From Hofstadter, "Godel, Escher, Bach" Symbols: M, I, U Axiom: MI Rules: 1) xI -> xIU 2) Mx -> Mxx 3) xIIIy -> xUy 4) xUUy -> xy Is MU in the theorem? Philosophy of Math ------------------ Mathematical Realism: R1: mathematical entities exist independent of the human mind R2: mathematical truths are discovered R3: the same truths would be discovered by any mathematicians Canonical proponent: Plato Intuitionism: I1: mathematical objects are a construction of the mind to say that an object exists, there has to be a constructive process for creating it not sufficient to refute its non-existence I2: to say that a statement is true is exactly to say that it can be proved reject the law of the excluded middle, since it is not always true that either A or not-A can be proved generally don't accept proof by contradiction also not wild about the axiom of choice and infinity. I3: mathematical objects exist in the mind language can be used to help another person reconstruct an object, but the language has no official role Canonical proponent: Luitzen Egbertus Jan Brouwer, known to his friends as Bertus Formalism: F1: mathematics is the study of formal axiom systems (symbols, axioms, and rules for manipulating strings of symbols) F2: contrary to I3, the product of mathematics is the language, not the brain state F3: in the strong form, mathematics is _just_ string manupulation in the deductivist form, you can attach meaning to mathematical statement if you accept the axioms and a mapping of the symbols onto something in the world F4: "true and false" apply only at the semantic level "provable and not provable" apply only at the symbol level Canonical proponent: David Hilbert Positivism: "a severe theory of meaning that makes liberal use of the word 'meaningless'" P1: Mathematical statements are logical consequences of their axioms, and are meaningless. Mathematical equation simply says that the meaning of both sides is the same. P2: A descriptive statement (as opposed to a mathematical one) without a verification process is meaningless. P3: The meaning of a descriptive statement is that the verification process would be successful. Canonical proponent: Ludwig Wittgenstein, who may or may not have menaced Karl Popper with a fire poker. Hilbert's program ----------------- 1900 version: (#2 on the list presented at the Paris conference of the International Congress of Mathematicians) Find a provably consistent FAS that derives all true statements of arithmetic (of non-negative integers) 1920 version: a provably consistent formal system that could derive all true statements in all mathematics Clarification: completeness is only meaningful if you are trying to attach semantics to a FAS. The association of a FAS with semantics is called an interpretation. If a string A can be derived from the axioms, it is derivable, provable, or "in the theorem" A FAS "maps onto a semantic system (Allen's language)" if 1) there exists an interpretation such that every derivable string A maps to a statement Interp(A) that is true in the semantic system Example: consider a FAS with only one axiom, the ASCII string '49 43 49 61 50', and no generative rules. If we use the interpretation 49 -> 1 43 -> + 61 -> = 50 -> 2 Then the axiom maps to the statement 1+1=2. Assuming that we also apply the usual interpretation of numerals and symbols, this is a true statement in the semantic system we call arithmetic. So it is easy to come up with any number of FASs that map onto a given semantic system. It's harder to find one that's complete. A FAS+Interpretation is complete if 1) the Interpretation maps the FAS onto a semantic system 2) every true statement in the semantic system maps to a string that is derivable This is what Hilbert was asking for, but in addition, the FAS+Interp had to be provably consistent: A FAS+Interp is consistent if there is no pair of strings, A and B, in the theorem that map to statements Interp(A) and Interp(B) that are contradictory (in the semantic system). So it is fairly easy to be consistent. Any FAS+Interp that maps onto a consistent semantic system will be consistent. Test your understanding ----------------------- Question: if an FAS derives a statement A, and Interp(A) is false, what does that tell us about the consistency and/or completeness of the FAS? Question: how could you possibly prove consistency? In general, I don't know. But in a system that contains basic logic, it is provable that p -> (~p -> q) In words, this means that if we can derive p and ~p for any p, then we can derive any string q. The contrapositive of this statement is that if there is an string q that we cannot derive, then there is no pair (p, ~p) that can be derived. So, in a system with basic logic, you can prove consistency just by finding one string that can't be derived! Well, how do you do that? One more prerequisite: meta-math -------------------------------- To understand incompleteness, it is useful to keep separate (at least for now) three levels: 1) syntax: strings of symbols. (y)(Ex)(x=Sy) 2) semantics Under the interpretation called Peano Arithmetic, the string '(y)(Ex)(x=Sy)' denotes the statement "For all y there exists an x such that x is the successor of y" 3) meta-math Meta-mathematical sentences include: a) "(y)(Ex)(x=Sy)" is a string in PA b) "(y)(Ex)(x=Sy)" is a derivable string in PA c) In PA, the string '(y)(Ex)(x=Sy)' denotes the statement "For all y there exists an x such that x is the successor of y" d) PA is consistent e) PA is complete f) In MIU, there are no derivable strings with n Is and n divisible by 3. Therefore MU is not a derivable string. Enter Godel (please draw in the umlaut) ----------- First incompleteness theorem: in any consistent FAS where all derivable strings map to true statements about arithmetic, there are true statements about arithmetic that cannot be derived in the FAS. Second incompleteness theorem: in any FAS that can be mapped onto statements about arithmetic+consistency, a) if it is possible to derive the statement that the FAS is consistent, then the FAS is inconsistent. b) if the FAS is consistent, then it is not possible to derive a statement of its consistency Big Idea #1: arithmetize syntax construct a mapping between strings in the FAS and numbers. Big Idea #2: arithmetize meta-math construct a string in the FAS that maps to a statement that means "this string can not be derived" this string is the Godel sentence, denoted G. Now there are only two possibilities: If G cannot be derived, then Interp(G) is true, but that means it is a true statement that cannot be derived; hence the FAS is not complete. If G can be derived, then it turns out that ~G can also be derived, which means that the FAS is inconsistent. If we assume that arithmetic is consistent, or if we prove by other means that it is, then neither G nor ~G can be derived, and so G is "formally undecidable". This implies that if arithmetic is consistent, then Interp(G) is true. That was the first incompleteness theorem. So all this is left is 1) how to construct G. 2) how to get from the first theorem to the second. That's where Nagel and Newman come in. Nagel and Newman reading questions ---------------------------------- Please write "Nagel and Newman, Godel's Proof, New York University Press, 2001" on your handout. 1) What's a Godel number? 2) What are the three kinds of variables that can be encoded? 3) If you had to decode a Godel number, how would you distinguish between a sequence of symbols and a sequence of formulas? 4) Is every number the Godel number of some expression? 5) What arithmetic operation can be used to check whether one formula is a prefix of another? 6) What is the meta-mathematical statement associated with Dem(x, y)? 7) If you evaluated the expression Sub(y, 17, y), what kind of thing would you get (string, number, meta-mathematical statement)? 8) What meta-mathematical process does Sub(y, 17, y) describe? 9) What is the relationship between formula (1) and formula (G)? 10) What is the Godel number of formula (G)? 11) What is the meta-mathematical statement associated with (G)? 12) Why do N&N say that P is "essentially incomplete"? 13) What is the meta-mathematical interpretation of formula (A)? From now on, let's choose the branch that says that the meta-mathematical statement "Arithmetic is consistent" is true. 14) How do we know that G is true? 15) How do we know that A->G is true?