1 Computable Functions 6,1 1 Primitive Recursive Functions 6. 1 2 The Ackermann Function 13,1 3 Computable Functions 17. 1 4 Partial Recursive Functions 23,1 5 The Enumeration Theorem 25. 1 6 Consequences of the Enumeration Theorem 30,1 7 Unsolvable Problems 34. 1 8 The Recursion Theorem 39,1 9 The Arithmetical Hierarchy 41. 2 Undecidability of Arithmetic 48,2 1 Terms Formulas and Sentences 48. 2 2 Arithmetical De nability 50,2 3 Go del Numbers of Formulas 57. 3 The Real Number System 60,3 1 Quanti er Elimination 60. 3 2 Decidability of the Real Number System 66,4 Informal Set Theory 69. 4 1 Operations on Sets 69,4 2 Cardinal Numbers 71,4 3 Well Orderings and Ordinal Numbers 74. 4 4 Trans nite Recursion 78,4 5 Cardinal Numbers Continued 81. 4 6 Cardinal Arithmetic 83,4 7 Some Classes of Cardinals 85. 4 8 Pure Well Founded Sets 87,4 9 Set Theoretic Foundations 88. 5 Axiomatic Set Theory 92,5 1 The Axioms of Set Theory 92. 5 2 Models of Set Theory 96, 5 3 Transitive Models and Inaccessible Cardinals 99. 5 4 Constructible Sets 103,5 5 Forcing 107,5 6 Independence of CH 111. 6 Topics in Set Theory 114,6 1 Stationary Sets 114. 6 2 Large Cardinals 115,6 3 Ultra lters and Ultraproducts 116. 6 4 Measurable Cardinals 119,6 5 Ramsey s Theorem 119. List of Figures,1 1 Register Machine Instructions 18. 1 2 An Addition Program 18,1 3 The Initial Functions 19. 1 4 Generalized Composition 20,1 5 A Multiplication Program 21. 1 6 Primitive Recursion 22,1 7 Minimization 24,1 8 A Program with Labeled Instructions 27. 1 9 Incrementing Pi 31,1 10 Decrementing Pi 31,1 11 Stopping 32. 1 12 Parametrization 37,List of Tables,1 1 The Ackermann branches 14. Computable Functions,We use N to denote the set of natural numbers. For k 1 the k fold Cartesian product, is denoted Nk A k place function is a function f Nk N and is sometimes. indicated with the lambda notation,f x1 xk f x1 xk. A number theoretic function is a k place function for some k 1. The purpose of this chapter is to de ne and study an important class of. number theoretic functions the recursive functions sometimes called the com. putable functions We begin with a certain subclass known as the primitive. recursive functions,1 1 Primitive Recursive Functions. Loosely speaking a recursion is any kind of inductive de nition and a primitive. recursion is an especially straightforward kind of recursion in which the value. of a number theoretic function at argument x 1 is de ned in terms of the. value at argument x For example the factorial function x x is de ned by. the primitive recursion equations 0 1 x 1 x x 1 A number. theoretic function is said to be primitive recursive if it can be built up by means. of primitive recursions This concept is made precise in the following de nition. Definition 1 1 1 Primitive Recursive Functions The class PR of primitive. recursive functions is the smallest class C of number theoretic functions having. the following closure properties,1 The constant zero function Z x 0 belongs to C. 2 The successor function S x x 1 belongs to C, 3 For each k 1 and 1 i k the projection function Pki x1 xk xi. belongs to C, 4 C is closed under generalized composition This means that whenever the. k place functions,x1 xk g1 x1 xk x1 xk gm x1 xk, and the m place function y1 ym h y1 ym all belong to C then. the k place function,f x1 xk h g1 x1 xk gm x1 xk,also belongs to C Here f is de ned by. f x1 xk h g1 x1 xk gm x1 xk, 5 C is closed under primitive recursion This means that whenever the. k place function x1 xk g x1 xk and the k 2 place function. yzx1 xk h y z x1 xk, belong to C then the k 1 place function yx1 xk f y x1 xk. f 0 x1 xk g x1 xk,f y 1 x1 xk h y f y x1 xk x1 xk,also belongs to C. We now list some examples of primitive recursive functions. Examples 1 1 2,1 The recursion equations,x y 1 x y 1. show that the addition function xy x y is primitive recursive. 2 The recursion equations,x y 1 x y x, show that the multiplication function xy x y is primitive recursive. 3 The recursion equations, show that the exponentiation function xy xy is primitive recursive. 4 As already mentioned the recursion equations, show that the factorial function x x is primitive recursive. We now proceed to further enlarge our library of primitive recursive func. tions First the recursion equations P 0 0 P x 1 x show that the. predecessor function,x 1 if x 0, is primitive recursive We can then obtain the truncated subtraction function. y x y if x y,using primitive recursion equations x 0 1 P x y. subraction is useful because ordinary subtraction is not a function from N2 into. N We shall also have use for,x Note that, The following exercise will become easy after we have developed a little more. Exercise 1 1 3 Show that the Fibonacci function de ned by. b x 2 b x b x 1, is primitive recursive The rst few values of this function are 0 1 1 2 3 5. 8 13 21 34 55, In addition to primitive recursive functions we shall want to consider prim. itive recursive predicates By a k place predicate we mean a subset of Nk If. R Nk is a k place predicate and x1 xk are elements of N we say that. R x1 xk is true if hx1 xk i R otherwise false A number theoretic. predicate is a k place predicate for some k 1, Definition 1 1 4 A k place predicate R Nk is said to be primitive recursive. if its characteristic function,1 if R x1 xk is true. 0 if R x1 xk is false,is primitive recursive, For example the 2 place predicates x y and x y are primitive recursive. since x y x y and x y y, Lemma 1 1 5 Boolean Connectives If P and Q are primitive recursive pred. icates then so are P P Q and P Q Here and denote negation. conjunction and nonexclusive disjunction respectively. Proof We have P P and P Q P Q Also,since P Q P Q de Morgan s law. Lemma 1 1 6 Iterated Sums and Products If f x y z1 zk is a primitive. recursive function then so are,g y z1 zk f x y z1 zk 0 if y 0. h y z1 zk f x y z1 zk 1 if y 0,Proof We have g y z1 zk g y y z1 zk where. g w y z1 zk f x y z1 zk,The recursion equations,g 0 y z1 zk 0. g w 1 y z1 zk g w y z1 zk f w y z1 zk, show that g is primitive recursive hence g is primitive recursive The treatment. of h is similar, Lemma 1 1 7 Finite Conjuction and Disjunction If R x y z1 zk is a. primitive recursive predicate then so are,P y z1 zk R x y z1 zk. Q y z1 zk R x y z1 zk,Proof We have,P y z1 zk R x y z1 zk. Q y z1 zk R x y z1 zk,so our result follows from the previous lemma. Note that x 0 and x 0 can be paraphrased as for all x in the range. 0 x y and there exists x in the range 0 x y respectively These. operators are sometimes called bounded quantifiers. The above lemmas make it easy to show that many familiar predicates are. primitive recursive For example the set i e 1 place predicate of prime num. bers is primitive recursive since,Prime x x is a prime number. x 1 u x v x x u v u 1 v 1, Similarly the following lemma can be used to show that many familiar func. tions are primitive recursive, Lemma 1 1 8 Bounded Least Number Operator If R x y z1 zk is a. primitive recursive predicate then the function,least x y such that R x y z1 zk holds. f y z1 zk if such x exists,y otherwise,is primitive recursive. Proof We have,f y z1 zk x 0 x R x y z 1 z k w 0 R w y z 1 z k. y x 0 R x y z1 zk,so f is primitive recursive, For example consider the function n pn which enumerates the prime. numbers in increasing order The rst few values of this function are p0 2. p1 3 p2 5 p3 7 We want to use the bounded least number operator. to show that n pn is primitive recursive First recall a famous theorem of. Euclid which gives the bound pn 1 pn 1 We can then write p0 2 pn 1. least x pn 1 such that Prime x and x pn Thus n pn is primitive. As another application of the bounded least number operator note that the. Quotient y x y x q,Remainder y x y mod x r, where y q x r 0 r x 0 q are primitive recursive in view of. Quotient y x least q y such that r x y q x r,Remainder y x least r x such that q y y q x r. Using the bounded least number operator we can obtain a primitive recur. sive method of encoding ordered pairs of natural numbers as single numbers. For our pairing function we use uv 2u 3v The unpairing functions are then. z z 0 and z z 1 where,z n least w z such that Remainder z pw 1. the exponent of pn in the prime power factorization of z. Note that 2u 3v 0 u and 2u 3v 1 v, More generally we can encode variable length nite sequences of natural. numbers as single numbers The sequence ha0 a1 am 1 i is encoded by. and for decoding we can use the primitive recursive function zx z x since. a x ax This method of prime power coding will be used extensively in the. proof of the Enumeration Theorem below, The pairing and unpairing functions make it easy to show that the Fibonacci. function is primitive recursive cf Exercise 1 1 3 Namely we rst note that. the auxiliary function x bpair x de ned by,bpair x 2fib x 3fib x 1. is primitive recursive in view of,bpair 0 20 3 1,bpair x 1 2 fibpair x 1 3 fibpair x 0 fibpair x 1. Then x b x is primitive recursive since b x bpair x 0. Exercise 1 1 9 Show that the 2 place number theoretic functions GCD x y. and LCM x y the greatest common divisor and least common multiple of x. and y are primitive recursive, Solution LCM x y least z x y such that Remainder z x Remainder z y. 0 GCD x y xy LCM x y, Exercise 1 1 10 Show that the 1 place number theoretic function f n given. f n 1 f k n,is primitive recursive, Solution Consider the so called course of values function. i e fe n encodes the variable length nite sequence hf 0 f 1 f n 1 i. via prime power coding Then fe n is primitive recursive in view of the recur. sion equations fe 0 1 and,fe n 1 fe n ph n, where h n z 1 k 0 z k n It now follows that f n fe n 1 n. is primitive recursive This general technique is known as course of values. Exercise 1 1 11 Show that the function n nth digit of 2 is primitive. Solution The nth digit of 2 is f n Remainder g n 10 where g n the. least x 4 102n such that x 1 2 2 102n, Exercise 1 1 12 Show that the 1 place number theoretic function. f n the nth decimal digit of 3 141592,is primitive recursive. Hint You may want to use the fact that a b 1 b42 for all integers. a b 1 This result is due to K Mahler On the approximation of Nederl. Akad Wetensch Proc Ser A 56 Indagationes Math 15 30 42 1953. Solution We use the well known series,1 1 1 1 1 n,4 3 5 7 9 n 0. 4 4 4 4 1 n 4,3 5 7 9 n 0, Let Sk be the kth partial sum of this series We have Sk a k b k where the. functions a k and b k are primitive recursive namely. 1 n 4 2k 1,and b k 2k 1 Note also that the functions. g n a b i 10n b 10i a 10n b, h n a b Rem Quot 10g n a b a b 10 the nth digit of a b. is primitive recursive By Mahler s result for each n there exists k 1050n. such that Sk and Sk 1 have the same rst n digits Since lies between Sk. and Sk 1 it follows that Sk and have the same rst n digits so in partic. ular f n the nth digit of Sk Using the bounded least number operator. Vn f n h n a k n b k n where k n the least k 10 such. that m 0 g m a k b k g m a k 1 b k 1 Clearly this is primitive. 1 2 The Ackermann Function, In this section we present an example of a function which is not primitive re. cursive yet is clearly computable in some intuitive sense The precise concept. of computability which we have in mind will be explained in the next section. Definition 1 2 1 We de ne a sequence of 1 place functions An n N as. An 1 x An An An 1,Thus A0 x 2x A1 x 2x A2 x 22 height x etc. Exercise 1 2 2 the Ackermann hierarchy, 1 Show that for each n x An x is primitive recursive. 2 Show that,a An x 1 An x x for all x 1 and all n,b An 1 x An x 1 for all x 3 and all n. 3 Show that for each k place primitive recursive function. x1 xk f x1 xk,there exists n such that,f x1 xk An max 3 x1 xk. for all x1 xk, 4 Show that the 2 place function nx An x is not primitive recursive. This is known as the Ackermann function, 5 Show that the 3 place relation nxy An x y is primitive recursive. Use this to show that the Ackermann function is computable i e recur. sive in the sense of Section 1 3, 1 Show that An 1 2 An 2 4 and An 1 3 An 4 for all n Compute. An x for all n x with n x 8, Solution For all n we have An 1 1 An 1 hence by induction An 1. A0 1 2 Also An 1 2 An An 1 An 2 hence by induction. An 2 A0 2 4 Also for all n and x we have An 1 x 1, An An 1 x in particular An 1 3 An An 1 2 An 4 Table 1 1. shows An x for small values of n x,Table 1 1 The Ackermann branches. 0 1 2 3 4 5,A0 0 2 4 6 8 10,A1 1 2 4 8 16 32,A2 1 2 4 16 2 22. A3 1 2 4 216 22 height 216 22 height 22 height 216. A4 1 2 4 22 height 216 A3 22 height 216,A5 1 2 4 A3 2 height 216. 2 Prove the following,a An x 1 An x x for all x 1 and all n. b An 1 x An x 1 for all x 3 and all n, c For each primitive recursive function f x1 xk there exists n such. that An covers f i e,f x1 xk An max 3 x1 xk,for all x1 xk. d The 1 place function x Ax x is not primitive recursive. e The 2 place function xy Ax y is not primitive recursive. Solution First we prove An x 1 An x x for x 1 by induction. on n For n 0 we have A0 x 1 2x 2 2x A0 x for all,x and A0 x 2x x for x 1 For n 1 and x 1 we have. An 1 x 1 An An 1 x An 1 x by inductive hypothesis Thus. An 1 is strictly monotone Since An 1 0 0 it follows that An 1 x x. Next we prove An 1 x An x 1 for x 3 by induction on x For x 3. we have An 1 3 An 4 as noted above and inductively An 1 x 1. An An 1 x An An x 1 An x 2 since An is strictly monotone. and An x 1 x 2 by what has already been proved, Next we prove that each primitive recursive function is covered by An for. some n We prove this by induction on the class of primitive recursive. functions We begin by noting that the initial functions are covered by. Suppose f is obtained by generalized composition say. f x1 xk h g1 x1 xk gm x1 xk, Let n be such that An covers h and An 1 covers g1 gm We then have. f x1 xk h g1 x1 xk gm x1 xk,An max 3 g1 x1 xk gm x1 xk. An An 1 max 3 x1 xk,An 1 max 3 x1 xk 1,An 2 max 3 x1 xk. i e An 2 covers f,Suppose f is obtained by primitive recursion say. f 0 x1 xk g x1 xk,f y 1 x1 xk h y f y x1 xk x1 xk, Let n be such that An covers h and An 1 covers g We rst claim that.

eight Science and Engineering Practices defined by A Framework for K-12 Science Education. This useful tool eases the transition to the NGSS by providing definitions, examples, and Quick Practice activities to be used as reference while students develop their projects and meet performance expectations. Science and Engineering Practices Handbook

Developing Windows Azure and Web Services - 20487 Course Outline (5 days) Overview In this course, students will learn how to design and develop services that access local and remote data from various data sources. Students will also learn how to develop and deploy services to hybrid environments, including on-premises servers and Windows Azure.

From Evaluating Training Programs, ... new computer system, rather than from training. Kirkpatrick's model is great for trying to evaluate training in a "scientific" way, however, so many variables can be changing in fast-changing organizations that analysis at level 4 can be limited in usefulness. Key Points The Kirkpatrick Four-Level Training Evaluation Model helps trainers to measure the ...

Contextual-based Image Inpainting: Infer, Match, and Translate 3 tion is blurry but contains high-level structure information in the hole. In the translation stage, we train a Feature2Imagenetwork that transforms the feature back into a complete image. It re?nes the contents in the hole and outputs a complete image with sharp and realistic ...

A course in introductory biostatistics is often required for professional students in public health, dentistry, nursing, and medicine, and for graduate students in nursing and other biomedical sciences, a requirement that is often considered a roadblock, causing anxiety in many quarters. These feelings are expressed in

Morgeson et al. / Leadership in Teams 7 way to understand the role of leadership in the context of the team and the different leader-ship sources that can exist ...

Team Players The Committees Recruitment Game ... Team Players: Volunteer Leadership ... marketing sectors of the retail real estate industry, working with the ICSC Team

Review Paper: Leadership styles ... A mechanism of leadership styles affecting team innovation in the private ... Information Industry in Taiwan The leadership style ...