Foundations of Computer Science Fall 2007 For today you should have: 1) Prepared a presentation on your project. 2) Read Nagel and Newman and answered the questions in notes17. For next time, you should: 1) Prepare for an exam. The three worlds ---------------- syntax, PM: A FAS that maps onto arithmetic semantics, arithmetic: statements about non-negative integers, addition and multiplication meta-math: statements about PM, arithmetic, or meta-math Decoding Godel numbers ---------------------- Assume that we have a dictionary that maps the numbers 1-12 to their symbols, so symbol[7] --> 's' and a function prime_factor that returns a list of tuples, where each tuple is a prime factor and its exponent, sorted by factors: prime_factor(100) --> [(2,2), (5,2)] Then a function that decodes Godel numbers might look like: def decode(n): factors = prime_factor(n) if len(factors) == 1: factor, exponent = factors[0] return decode_singleton(factor, exponent) else: return decode_sequence(factors) def decode_singleton(factor, exponent): if exponent == 1: if n<=12: return symbol[n] else: return NumericalVariable(factor) if exponent == 2: return SententialVariable(factor) if exponent == 3: return PredicateVariable(factor) def decode_sequence(factors): # this function assumes that the sequence is well-formed; # that is, that the sequence of factors is a sequence of # primes starting at 2. seq = [] for factor, exponent in factors: seq.append(decode(exponent)) return seq The result of decode might be a symbol, a variable, a sequence of symbols and variables (an expression) or a sequence of expressions. To generate a string, we would have to "flatten" this structure. Assume that the Variable type has a str function that generates an appropriate letter. If sv2 is the second SententialVariable, then str(sv2) --> 'q' def flatten(s): try: t = [flatten(x) for x in s] return t.join() except: return str(s) In programming classes, you spend a lot of time trying to wrap your head around recursion. This is why. Arithmetization of meta-math ---------------------------- Godel numbering is relatively easy to get your head around, but arithmetization of meta-math is another story. Nagel and Newman given an example: 1) If the string x is a prefix of the string y, then the first n prime factors of x are the same as the first n prime factors of y. So you could test the meta-mathematical relationship is_prefix by purely arithmetic tests on the common factors of GN(x) and GN(y) Hofstadter presents a simpler version that can be made more concrete. 2) If the string x begins with the symbol ~, then the first exponent in its prime factorization is GN('~'), which is 1. So you could test the meta-mathematical relationship tilde_prefix by testing whether the GN(x) is divisible by 2 but not divisible by 4. The surprising thing is that any meta-mathematical statement that can be expressed as a string in PM can also be expressed as an arithmetic statement on Godel numbers. Why? Because the strings in PM are pure syntax; all operations are just string manipulations. And any manipulation of string x has a computable arithmetic effect on GN(x). Dem and Sub ----------- dem(x, z) is an arithmetic expression that denotes a statement about the number x and z that is either a true or false statement in arithmetic Dem(x, z) is a string of symbols that can be constructed by syntactic manipulation of the strings x and z, where x and y have to be numerals (e.g. 'SSSSSSS0') The key is that 1) the string Dem(x, z) expresses a metamathematical statement (under the interpretation of its symbols) 2) if dem(GN(x), GN(z)) is a true statement of arithmetic, then Interp(Dem(x, z)) is a true statement of metamathematics! Similarly: sub(x, y, z) is an arithmetic function of numbers x, y, and z that yield a number Sub(x, y, z) is a string of symbols that can be constructed by replacing instances of the symbol whose Godel number is y with the numeral z wherever it appears in the formula represented by the number represented by the numeral x The key is that sub(GN(x), GN(y), GN((z)) is the Godel number of the string Sub(x, y, z) Question 9 ---------- How do you get from formula (1) to formula (G)? By replacing instances of decode(17) with the string representation of n everywhere it appears in the string that maps to n. How do you evaluate the expression sub(n, 17, n)? By replacing instances of decode(17) with the string representation of n everywhere it appears in the string that maps to n. Question 10 ----------- Therefore G = Sub(n, 13, n) and GN(G) = sub(GN(n), GN(13), GN(n)) One clarification: in the string Sub(n, 17, n), the first n is decoded into an expression and the second n is treated as a numeral Question 11 ----------- What does G mean as a meta-mathematical statement? It means that G cannot be derived in PM. And then the hilarity ensues. First incompleteness theorem ---------------------------- Der(x) = (Ey) Dem(x,y) = 'x is derivable in PM' Draw the tree with three branches: 1) ~Der(G) 2) Der(G) and Der(~G) 3) Der(G) and ~Der(~G) What does each branch mean? Which branches are possible under what assumptions? Second incompleteness theorem ----------------------------- What does A mean as a meta-mathematical statement? It means that PM is consistent. And it turns out that the formula A->G is derivable in PM (no magic involved, just plain old string manipulation). That means that if A is derivable, then G is derivable. So what does that mean for the consistency and/or completeness of PM? We have already seen that if Der(G), PM is inconsistent. Therefore 1) if A is derivable, PM is inconsistent 2) if PM is consistent, A is not derivable! This is the second incompleteness theorem. Implications ------------ 1) Bad news for math? Not really. This result is about math, but doesn't say anything mathematicians have a personal investment in. 2) Bad news for positivism? Well, yes, but it is not clear that a solution to Hilbert's problem would have done what they wanted, anyway. 3) Bad news for the state of human knowledge? The incompleteness theorems are like mining for lead and finding gold. a) if we found a complete, consistent FAS that maps onto arithmetic by brute force, it wouldn't do a thing for the state of human knowledge b) Godel's proof provides a startlingly novel proof technique, the seemingly impossible ability to use math to answer meta-mathematical questions, and an opportunity to marvel at the power of the human brain (and not just the one that came up with it). 4) Bad news for modernism? Well, yes, but mostly because it's been so badly abused. See Franzen, "Godel's Theorem, an incomplete guide to its use and abuse" 5) Bad news for artificial intelligence? Only if you thought an AI would be consistent, despite the obvious observation that natural intelligence (NI) is not. An AI may be a FAS, but it will not be a FAS that maps onto arithmetic. In my opinion, it will use a multivalent logic, many of which are immune to SIC syndrome (silly inconsistency collapse) and SRE (self-referential implosion). For example, Vezerides and Kehagias present a fuzzy logic in which the truth value of "This sentence is false" is 0.5. (http://cogprints.org/3171/) If an AI is anything like a NI, it will be blissfully inconsistent.