Math 39 Homework #24 The conclusion is inescapable that even for a fixed and well-defined body of mathematical propositions, mathematical thinking is, and must remain, essentially creative. Emil Post

	Reading Read what we will cover in the next class: 6.4. When reading 6.4 pay special attention to the following concepts: Gödel numbering, why we are interested in Gödel numbering, and the list of representable relations that arise in connection with Gödel numbering.

	Problems The following problems are due by the beginning of class on Friday 11/20. Prove the the following functions are representable in PA ( do not use Prop 6.12): s(n) = n+1 pki(n1,...,nk) = ni Prove that the function f(m,n) = m n2 + 2n is recursive. Prove that if X,Y are recursive relations, then the following are recursive: Xc = { x | x not in X} = "X-complement" X U Y X n Y = X intersect Y X # Y = (X \ Y) U (Y \ X) Prove that the following relations are recursive: If n \in N, {n}. Every finite set. { (n,n) | n \in N}.