Foundations of Mathematics I
Foundations of Mathematics I MATH 558
Popular in Course
Popular in Mathematics (M)
This 0 page Class Notes was uploaded by Elaina Osinski on Sunday November 1, 2015. The Class Notes belongs to MATH 558 at Pennsylvania State University taught by Staff in Fall. Since its upload, it has received 8 views. For similar materials see /class/233006/math-558-pennsylvania-state-university in Mathematics (M) at Pennsylvania State University.
Reviews for Foundations of Mathematics I
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/01/15
Math 558 Foundations of Mathematics I Lecture Notes John D Clemens PSU Spring 2005 Contents I Computability 1 Computable Functions Primitive Recursive Functions i i i i i i i i i i i i i i i i i i i Ackermann s Function Register Machines Partial Recursive Functions The Enumeration Theorem Unsolvable Problems i i i i i i i i i i i i i i i i i i i i i i i i Reducibility i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i The Recursion Theorem i i i i i i i i i i i i i i i i i i i i i i i The Arithmetical Hierarchy i i i i i i i i i i i i i i i i i i i i E E E E E E E E E 00IO D1gtJgtDJMgt O Undecidability of Arithmetic 21 The Language of Arithmetic i i i i i i i i i i i i i i i i i i i i 2 2 Arithmetical De nability i i i i i i i i i i i i i i i i i i i i i i 2 3 Godel Numbers of Formulas i i i i i i i i i i i i i i i i i i i i i 00 Decidability of The Real Numbers 31 Quanti er Elimination i i i i i i i i i i i i i i i i i i i i i i i 3 2 Decidability of the Real Numbers i i i i i i i i i i i i i i i i i II Set Theory 4 Informal Set Theory 4 Set Operations i i i i i i i i i i i i i i i i i i i i i i i i i i i 4 2 Cardinal Numbers i i i i i i i i i i i i i i i i i i i i i i i i i 4 3 Ordinal Numbers i i i i i i i i i i i i i i i i i i i i i i i i i i 44 Initial Ordinals and Cardinals i i i i i i i i i i i i i i i i i i i 45 Pure WellFounded Sets i i i i i i i i i i i i i i i i i i i i i i i 5 Axiomatic Set Theory 51 The Language of Set Theory 52 The Axioms of Set Theory i i i i i i i i i i i i i i i i i i i i i i CONTENTS 53 Models of Set Theory 54 Transitive Models l l l l l l l l l l l l l l l l l l l l l l l l l l 5 5 Constructible Sets and the Inner Model L l l l l l l l l l l l l l Part I Computability Chapter 1 Computable Functions Functions The notion of computability is fundamentally about functions Since we will be interested in partial functions we will not always require that each x E X have an image under the map When the domain of f is all of X we say that f is a total function We will sometimes use notation to de ne a function For instance writing f 123i x3 indicates that f is a function of the three variables x1 x2 and 953 whose value on these inputs is 9511 x2 More frequently we will simply write f961962963 xi 95 95 to indicate the same thing We will primarily study functions of the natural numbers For the record N012mi We say a function is kary if its domain is Nk 11 Primitive Recursive Functions We begin by considering a class of functions which may naturally be considered computable This class contains many of the commonly used functions but we will see that there are other functions which are intuitively computable and are not in this class We will start with a collection of very simple functions which are all intu itively computable We then introduce operations for forming new functions which preserve the property of being intuitively computable All the functions we introduce here will be total functions CHAPTER 1 COMPUTABLE FUNCTIONS 3 De nition 11 The initial functions are 1 the zero function Zx 0 and the Oary zero function 0 1 2 The successor function 595 x 1 3 The projection functions Plkx1 xk x1 for k 2 1 and 1 S i S k De nition 12 The primitive recursive operations are 0 Substitution or composition Given 9 N A N and in hm NlC A N with mk 2 0 we say that the function f NlC A N is obtained from g and h1 hm by composition if for all 951 me E N we have f961 a 96k 9011061 a 95k hmx1 a 95k 0 Primitive recursion Given 9 NlC A N and h NIH A N with k 2 0 we say that the function f thl A N is obtained from g and h by primitive recursion if for all 31951 xk we have f0961awaxlc99 1waxk fy1x1awaxk hyfyx1yaaaxkx1wxk Note that primitive recursion produces a wellde ned total function Example 13 A simple example of primitive recursion with k 0 is the factorial function yl Let g 1 and hyz y 1 2 Then f is obtained from g and h using primitive recursion as f01 fy 1 21 1 21 1 y hyfy De nition 14 A function f NlC A N is primitive recursive if it can be generated in nitely many steps from the initial functions using substitution and primitive recursion Equivalently the class of primitive recursive functions is the smallest class of functions containing the initial functions and closed under these two operations We let 77R denote the class of primitive recursive functions Formally we can de ne a hierarchy of functions 73730 the initial functions 7373711 all functions obtained from functions in 7773 using primitive recursive operations 73R U 737 7120 1A Diary function is one with no inputs ie just a constant This will be necessary for technical reasons CHAPTER 1 COMP UTABLE FUNCTIONS 4 The sequence of initial functions and primitive recursive operations we use to obtain a given primitive recursive function f is called a primitive recursive derivation of Example 15 The following functions are all primitive recursive H N 9quot u 9quot 93 Addition f9cy ac y To see this let gy y PH and Mac 2y 2 1 Then f0y y9y fx1yz1yxy1hxfxyy Multiplication 0y0 x1yxyy Exponentiation 9501 xy1 xv 96 Note that we have used recursion on the second coordinate which does not t our literal de nition of primitive recursion however this is never a problem Formally we could de ne a function with the inputs ipped and then recover the original function by composing the ipped function with projections 7 1 if 0 The predecessor function Px x x gt 0 1f ac 0 This is given by the primitive recursion P 0 0 Py 1 y 7 39f gt Restricted subtraction ac 4 y x y 1 x 7 0 otherw1se This is given by 954095 14y1Px y lxiyl x yHQ x CHAPTER 1 COMPUTABLE FUNCTIONS 5 Primitive recursive relations We Will study the computability of relations by considering their characteristic functions Let R be a kary relation on N for some k 2 1 ie R Q Nk Then its characteristic function X3 is de ned as 1 ifx1xk R XE 1 k 0 ifx1xk R We can now say What it means for a relation to be primitive recursive De nition 16 We say a relation R on Nk is primitive recursive if its charac teristic function X3 is a primitive recursive function Example 17 The binary relation ac y77 is primitive recursive since its characteristic function is Xy1 lxi yl Similarly the relations ac S y ac lt y etc are primitive recursive We have the following closure properties of primitive recursive functions and relations Lemma 18 The collection of primitive recursive relations is closed under Boolean operations ie ifP and Q are two kary primitive recursive relations then so are the relations P P Q and P Proof Let Xp and XQ be the characteristic functions of P and Then X iP 14 XP XPAQ XP 39 XQ XPVQ 11XP XQ 1 Lemma 19 Iterated Sums and Products If x y 21 2k is a primitive recursive function then so are yil 9y21w2k Zfxayazla uazk 0 ify 0 10 yil hy21mzkgt H zwlwm 1 veg0 10 Proof We de ne the function 9 as 1171 9w3y21 azk Zfltxayazlvualegt 560 CHAPTER 1 COMPUTABLE FUNCTIONS 6 Then 9 is obtained by primitive recursion 90y21w21c 0 9w1y21w2k 9way21u 2kfway21wWe Hence 9 is primitive recursive and gy21 2C gy y 21 2C is as well The function h is handled similarly 1 Lemma 110 Bounded Conjunction and Disjunction If Rx y 21 one is a primitive recursive relation then so are yil Py21w2k E A Rxy21w2k 560 yil Qy21w2k E V Rxy21w2k 10 Proof Since XR is primitive recursive the previous lemma tells us that yil Xpy21 a 2k H XRxy21 We 560 is primitive recursive as well and XQ is handled similarly 1 Note 111 These are also referred to as bounded quanti cation since they are true respectively if the relation R holds for all X between 0 and y 7 1 or if there exists an ac in this range satisfying R Bounded quanti cation is useful in de ning primitive recursive relations since we can often bound the range of values we need to search Example 112 We can see that the relation Primex E ac is a prime number is primitive recursive since we have 171171 PrimexExgt1 V Vxuvugt1vgt1 u0v0 and the relations ac y ac lt y etc are primitive recursive The following is a similar general principle Lemma 113 Bounded minimization If Rx y 21 one is a primitive re cursive relation then the function f is primitive recursive where the least ac lt ysuch that Rx y 21 2 holds fy21zk if such and exists y otherwise CHAPTER 1 COMPUTABLE FUNCTIONS 7 Proof We multiply each of the possible output values by a test for whether this is the correct value 1171 71 fy21wazk Z xXRZZiawazk39 HG XRway21wazkgt 560 110 yil y H04 XRxyZ1w2k 10 1 Note 114 The bound on the search is crucial to ensure that we produce a primitive recursive function in fact to ensure that we produce a total function We will consider unbounded minimization later Example 115 Let pn the nth prime ie p0 2 p1 3 p2 5 etc Then the function pn is primitive recursive To see this we use a theorem of Euclid which implies that pn 1 S pnl 1 We can de ne the least 95 lt y such that x is prime and x gt 2 y 2 if such exists y otherwise so that f is primitive recursive Then 200 2 Mn 1 fPn1 21000 Example 116 We can see that the quotient and remainder functions for integer division are primitive recursive where Quotientyx x Remaindery x y mod 95 ie y x Quotienty x Remaindery This holds since Quotienty x the least 11 S x such that y lt q 1 x Remaindery x y 4 x Quotienty x Coding of nite sequences We have been dealing with functions de ned over N however often we will be interested in dealing with other sorts of objects We will handle this by coding the given objects as natural numbers Here we consider nite sequences As a rst example we consider a coding of ordered pairs of natural numbers De ne Pairx y 213y CHAPTER 1 COMPUTABLE FUNCTIONS 8 This allows us to code an ordered pair as a natural number in a primitive recursive way What is important is that we can uncode in a primitive recursive way as well Given a code 3 for a pair we have primitive recursive functions which compute the coordinates of the original pair These are 30 the exponent of 2 in the prime factorization of s the least 11 lt s such that Remainders 2w1 y 0 31 the exponent of 3 in the prime factorization of s where the bound works because 71 lt 2 for all n etc We can generalize this to sequences of arbitrary length De nition 117 Given a nite sequence 10 am1gt we de ne its code to be mil Codea0 am1gt H piaz1 10 Note that the empty sequence with m 0 has code 1 Note that we really have a different coding function for each m The ex ponent a1 1 is used in order to be able to determine the length of a coded sequence We will generally simply use 10 am71gt to denote the code of this sequence Note that we can decode in a primitive recursive way as with the pairing function Let fs sz be as follows sz the ith digit of the sequence coded by s the exponent of in the prime expansion of s 739 1 the least 11 lt s such that Remaindersp239w1 y 0 4 1 Most natural relations and operations on sequences are primitive recursive such as the relation 3 codes a sequence Lengths the length of the sequence coded by s the concatenation of two sequences etc Note 118 We will often use 10 am1gt to denote the code of a sequence of arbitrary length When we do this we mean that we apply the mary coding function consistent with the length of the given sequence From the way we have chosen our coding there will always be at most one sequence coded by a g1ven s CHAPTER 1 COMPUTABLE FUNCTIONS 9 Simultaneous recursion De nition 119 We say that the functions f1 and f2 on N are de ned by simultaneous recursion from the functions 91 92 in h if f10951 a 91x1 xk f20x1 xk 92951 xk f1y 1x1xk h1yf1y x1 xkf2y x1 xkx1 xk f2y 1x1xk h2yf1y x1 xkf2y x1 xkx1 xk The class of primitive recursive functions is closed under simultaneous re cursion this is left as an exercise It is also closed under the following more general type of recursion De nition 120 We say that a function f NC1 A N is de ned by course ofUulues recursion from h NI A N if fyx1 xkhyaltf0fawafyi193961wx1c 12 Ackermann s Function We consider a function which will not be primitive recursive yet is intuitively computab e De nition 121 We de ne Ackermann s function Anx as follows First let A0x x1 An1x 1451 1 where we mean the as 1th iterate Then de ne Ackermunn s Function to be 140196 147496 Note that these functions satisfy the following recursion A0x as 1 An10 Ana An195 1 AnAn1x Notice that each An is de ned from the previous by primitive recursion hence each An is primitive recursive Also note that each An requires n iterations of primitive recursion and that these functions have increasing growth rates This suggests that An ac will not be primitive recursive as we will see since we would only be able to use nitely many operations of primitive recursion to de ne it if it were primitive recursive CHAPTER 1 COMPUTABLE FUNCTIONS 10 Example 122 We list the rst few An functions A0x xl A1x lxlx2 A2x l2x12x3 Am 2373 2 A4x 2Tn373where2ln22 ntirnes Another point to note is that the type of recursive de nition we have given is different from simultaneous recursion or courseofvalues recursion The dif ference is that we require potentially larger values of the second coordinate whereas in all of the types of recursion we were allowed for primitive recursive functions would require that the second coordinate be xed or decrease Properties of Ackermann s function We begin with by showing a few properties of Ackerrnann s function which will be used to show that it is not primitive recursive Lemma 123 The functions An satisfy the following properties 1 For all x 14511 2 at 1 2 For all x x lt A x lt Anx 1 5 For all x Anx 1 S A 1x 4 Ifn lt m then A x lt Amx for all x 5 For all x An2x lt A 2x Proof We leave 1 and 5 as exercises 2 We use induction on n First A0xlx2gtxlAoxgtx so this is true for n 0 Suppose it holds for n Then Awe 1 AnAn1xgt Awe A1gt1 2 x 1gt as using our inductive assumption and property 3 An1x ASLETUU AWA E1 2 Anx 1 since An is increasing by 3 and MR1 2 z 1 by 1 4 This follows from 2 and 3 since An lt Anx 1 S A 1x CHAPTER 1 COMPUTABLE FUNCTIONS 11 1 Theorem 124 For my primitive recursive function f there is an M such that for all 951 i i i xn fx1 i i i xn lt AMrnaxx1 i i i Proof We prove this by induction on a primitive recursive derivation of We begin with the initial functionsi Zx0ltx1A0x Sxx1ltx2A1x Plkx1iuxk xl ltxl1lt A0rnaxx1iuxk Next we consider compositioni Let M and N1 i i i Nm be such that gxliuxm lt AMrnaxx1uixm h19 1waxn lt AN1 111334951 Ml hm9 1waxn lt ANmma xxla xn Let N maxN1 i i WNm so that hlx1 i i i xn lt ANrnaxx1 i i i x for alllg39igmi Then fx1 i i i yin gh1x1 i i i xn i i i hmx1 i i i lt AMANrnaxx1 i i i AQ71ltAQltmaxx1mxngtgt where Q maxNM 1 AQrnaxx1iuxn1 S AQ1rnaxx1 i i i Finally we handle primitive recursioni Let M and N be such that 9951 i i i yin lt AMrnaxx1 i i i x My 2 951 i i i yin lt ANrnaxy 2 951 i i i Let Q maxN 1 First we claim that fy 951 i i i xn lt AQy maxx1 i i i This is proved by induction on y First f0x1uixn 9951 i i Win lt AMrnaxx1 i i AQltomx1mxngt CHAPTER 1 COMPUTABLE FUNCTIONS 12 Then assuming this is true for some y fy19 hyfyfath lt ANmaxyfy 9961 HM AQ1maxAQy maxac1 god y 951 x AQ1AQy max9c1 since AQy maxac1 2 y 951 x7 AQy 1 max9c1 l Now y max9c1 xn S 2maxyac1 xn so y 951 57 lt AQ2m3Xfya 951 axn lt AQ2m3 Xfya 951 xnl This shows that f is bounded by AQ2 and nishes the case of primitive recur sion 1 Note 125 In particular using the properties from the lemma for a unary primitive recursive function f there will be some n so that A x is bigger than for all ac We see from the proof of the theorem that this n will roughly correspond to how many steps are needed to de ne This relationship can be made more precise by studying the Axt Hierarchy and the Grzegorczyk Hierarchy of primitive recursive functions Corollary 126 Ackermdnn s function is not primitive recursive Proof If Ackermann s function were primitive recursive then so would be the function 9x Aac 9c A3495 Hence there would be some M such that for all ac 9x lt AMx But then we would have AMM 9M lt AMM a l contradiction Note 127 We will later see that Ackermann s function is computable in a broader sense 13 Register Machines We present a second approach to characterizing computable functions Our previous approach can be considered an inductive de nition We listed several simple functions which we asserted to be computable the initial functions and then described two closure operations which produced new computable functions from others The next approach can be considered a machine model We explicitly describe a procedure for computing a function ie we make precise the notion of an algorithm and say that a function is computable if some such procedure computes it Here we will consider register machines A number of other machine models are often studied such as Turing Machines Markov Algorithms and other formulations of register machines all of these turn out to give the same collection of machinecomputable functions CHAPTER 1 COMPUTABLE FUNCTIONS 13 De nition 128 A register machine consists of a nite sequence of registers R0 Rk and a nite sequence of instructions 10 It We View each register as holding a natural number Each instruction is of one of the three forms 1 Increment instructions 131 Ij Add one to the contents of register R1 and proceed to instruction Ij 2 Decrement instructions R17Ij1k 1f register Rz contains 0 do not change it and proceed to instruction 1 if R contains a number bigger than 0 subtract one from it and proceed to instruction 1k 3 Halt instruction HALT Stop execution of the algorithm A register machine operates as follows It begins with some initial values in its registers It then executes instructions starting with IO and proceeding according to the above rules The machine contains running until it reaches a HALT instruction which need not happen at which time it stops It will be clearer to present register machines using diagrams rather than lists of instructions To do this we dispense with the instruction numbers although officially they are still numbered only labeling Io with START We indicate the three type of instructions as in Figure 11 Eac arrow points to another node indicating the next instruction The two arrows from a decrement instruction are labeled 0 and gt 0 according to the cases of R1 being 0 or not gt0 0 Figure 11 Register machine instructions We can use register machines to compute functions of the natural numbers De nition 129 Let f be an nary partial function from N to N and let M be a register machine We say that M computes f if the following hold for each ntuple x1 957 E 7 1 When the machine M is started running with each register Rz initially containing ac for 1 S i S n and all other registers initially blank the machine eventually halts if and only if the tuple x1 xn is in the domain of F If the machine eventually halts it halts with the register R0 containing the value fac1 x We say that a partial function is register machine computable RMcomputable if there is some register machine M which computes it CHAPTER 1 COMPUTABLE FUNCTIONS 14 Example 130 We show that the addition function is register machine com putable That is we nd a function which when started with x in R1 and y in R2 and all other registers blank halts with x y in register R0 We describe the machine with a diagram START This machine proceeds by rst adding the contents of R1 to R0 and then adding the contents of R2 to R0 Note 131 In de ning the function computed by a particular register machine we really need to specify the arity of the function For instance the machine above computes the binary function of addition however it also computes the unary identity function since if we specify that there is only one input then it is assumed that all other registers in particular R2 are initially 0 Hence we need to refer to the kary function computed by the machine and each machine computes kary functions for all k Example 132 We describe a register machine to compute the following partial function 3 if n is even f n 2 unde ned if n is odd This machine successively subtracts 2 from R1 and adds 1 to R0 if it empties R1 after an even number it halts otherwise it goes into an in nite loop and never halts CHAPTER 1 COMPUTABLE FUNCTIONS 15 Example 133 We construct a register machine to compute the multiplication function This machine repeatedly adds R2 to R0 R1 many times The register R3 is used to keep track of the original value of R2 to restore it at the end of each repetition We Will see that this notion of computable function properly extends the class of primitive recursive functions We rst see that every primitive recursive function is register machinecomputable Lemma 134 Each initial function is RMcomputable Proof The zero function Zx 0 is computed by the trivial machine START The successor function 595 x l is computed by the machine START gt0 Each projection function Plkx1 951C x1 is computed by the machine CHAPTER 1 COMPUTABLE FUNCTIONS 16 START gt0 Lemma 135 The class of RM computable functions is closed under composi firm 1 Proof Suppose the function 9951 i xm and the functions h1x1 i i 9 H m 951 i i i ask are computed by the register machines an 1 i i i m respectively We may assume that the registers used by each machine are dis joint We Will assume that the input registers for machine H are R11 i i R and its output register is R3 the input registers for Q Will be R6 i i R3 and its out register is R0 We Will describe a machine With input registers R1 i i Rk and output register R0 Which computes the composition function fx1 i xk gh1x1 i xk i i hmx1 i xk The idea is to copy the input registers for f into the input registers for each of the hl s compute these functions using the machines H1 and then use these results in the machine Q We illustrate this in the following diagram Where we replace the boxes for the various machines by the corresponding instructions for those machines starting at each one s START instruction and proceeding to the next instruction in the diagram instead of halting START O CHAPTER 1 COMPUTABLE FUNCTIONS 17 Lemma 136 The class of RMcomputable functions is closed under primitive recursion Proof Suppose we have functions 9951 ask computed by the machine Q with input registers R517 Bi and output register R8 and My 2 x1 xk computed by the machine H with input registers R2 R2 R f R2 and output register R3 We will describe a machine to compute the function fy x1 951C obtained from g and h by primitive recursion We will let the input registers of this machine be By R1 Rk e will use a bottomup approach ie we will begin by computing f0x1 me then use this to compute f1x1 xk and so forth until we have computed fy x1 xk We will use a register R to count up the current value of y we are computing and count down Ry until we reach 0 This is illustrated in the following diagram The above three lemmas immediately give us the following Theorem 137 Every primitive recursive function is RMcomputable CHAPTER 1 COMPUTABLE FUNCTIONS 18 We will next see that there are register machinecomputable functions which are not primitive recursive Speci cally we will show that Ackermann s Func tion is RMcomputable The idea will be to use the recursive de nition of Ackermann s function and keep track of a nite sequence which stores the values we need to plug back into in the way that most programming languages use a stack to handle recursive function calls That is when we use the recursion An195 1 AnAn1x to compute An 1 ac 1 we will rst try to calculate An 1 ac but add n to our sequence to remember that we need to plug this value back into A7 We begin with a few preliminary functions for manipulating sequences which will essentially be pushing to and popping from a stack We will show that sev eral functions are primitive recursive and hence are RMcomputable by our previous result Recall the following two primitive recursive functions intro duced in the homework k1 ifsn0nk 0 otherwise RS n1C ifs n0nk Lengths 0 otherwise The function Rs will output the last rightmost number in the sequence coded by s and thus act as a Pop function We need two more functions Lemma 138 The following functions are primitive recursive Pushsnn0nkn ifs n0nk Emses n0nk1 ifs n0nk Proof Note that we only really care about applying these functions to s which code legitimate sequences We can thus de ne Pushs n spLengthsn1 Erases Quotient lt3pLengths 1Rs1gt where as before is the ith prime 1 We can thus assume that we have register machines which compute these func tions We will use these to compute Ackermann s function Theorem 139 Ackermunn s function An ac is RMcomputuble Proof Our inputs for n and ac are R1 and R2 respectively We will use R3 to hold our nite sequence recursion stack Note that by our conventions the empty sequence is coded by the number 1 this was handled slightly differently in lecture The diagram for our machine will be as follows CHAPTER COMPUTABLE FUNCTIONS 19 START Copy a e e a to R3 The machine proceeds as follows We rst set up our sequence in R3 to be the empty sequence coded by 1 We then check if n 0 which we can compute directly as x 1 We do this and then check if our sequence is empty iiei R3 contains 1 If so we can simply output as 1 and halt If not we must plug this value into some other An in this case we remove the last value from the sequence use this as the next 71 value and proceed If n was not 0 we check if x 0 if so we want to calculate A 11 we set up this computation and proceed Otherwise we are in the recursion case we add 71 7 1 to our sequence set up to compute An x 7 1 and proceed 1 14 Partial Recursive Functions We will now extend the class of primitive recursive functions in order to in clude more functions such as Ackermann s function As with the case of RM CHAPTER 1 COMPUTABLE FUNCTIONS 20 computable functions this will involve considering partial functions De nition 140 Let f Nk A N be a partial function We say fac1 xk converges if x1 xk E domf and write fac1 xk Similarly we say fac1 95k diverges if x1 951C domf and write fac1 951C Note 141 When dealing with partial functions we need to keep track of the domain As usual we have that gh1x1 95k hmx1 9 i if and only if hx1 95k 1 for each i and g is de ned at these values For primitive recursion we have that f0 x1 951C 1 i 9951 xk l and fy 15x13 xk t 13 fyax1 axk t and hyafyix1 Jxkix1 ixl l In particular for 1 x1 xk to be de ned we must have fu x1 xk de ned for all 0 S w 3 y De nition 142 Minimization Let Ry x1 xk be a relation We say that the function f9c1 ask is de ned from R by minimization i the least y such that Ry x1 xk holds fx1xk if suchayexists T if no such y exists We write fx1 axle WWW x1 a a 9 when f is de ned from R by minimization Minimization is also known as urecursion unbounded search and the least number operator Note that this is similar to bounded minimization which we encountered earlier except that the search can potentially go on forever in which case the function is unde ned We will see that even when the search always succeeds this is a more powerful operation than bounded minimization Example 143 Let py be a polynomial and let Ryx hold i py ac Then the function fx WW 96 returns the smallest natural number which satis es py ac if such exists and is unde ned if there is no y with py ac De nition 144 The class of partial recursive functions is the smallest col lection of partial functions containing the initial functions and closed under composition primitive recursion and minimization More precisely we de ne R Rn1 all functions obtained from functions in Rn using composition the initial functions 0 or primitive recursion or obtained by minimization from a relation R with X3 in Rn R U 7 n20 Then R is the class of partial recursive functions CHAPTER 1 COMPUTABLE FUNCTIONS 21 De nition 145 We say that a function is total recursive or just recursive if it is a partial recursive function which is total We say that a relation R is recursive if XR is a total recursive function Note that X3 is always a total function We can restate the previous de nition to say that a function obtained by minimization from a recursive relation is partial recursive We will see that the class of partial recursive functions coincides with the class of RMcomputable functions This provides evidence that we have cap tured the intuitive notion of computability We start by showing that each partial recursive function is RMcomputable Lemma 146 The class of RMcomputable partial functions is closed under minimization ie if R is a relation such that XR is RMcomputable and f is obtained from R by minimization then f is RMcomputable Proof Let the register machine M compute XRy x1 951C with input regis ters R5 Rf RE and output register Rg By assumption XR is a total func tion We describe a machine to compute fac1 951C uyRy x1 xk This machine successively computes values of X3 starting with y 0 until R is satis ed at which point if ever if halts outputting the current value of y 1 Corollary 147 Every partial recursive function is RMcomputable Showing that each RMcomputable function is partial recursive will involve more work This will be one consequence of a very useful result presented in the next section 15 The Enumeration Theorem In this section we will develop a system of coding register machines and use it to show in particular that every RMcomputable function is partial recursive Each register machine M will be assigned a number FM l called the Godel number of M We will also refer to these numbers as indices for the functions computed by the machines CHAPTER 1 COMPUTABLE FUNCTIONS 22 De nition 148 Given a register machine instruction I its code or Godel number FI l is de ned to be 20 3 5j if I is an increment instruction 131 Ij FI l 213151 7 C if I is a decrement instruction R17IjIC 22 if I is a HALT instruction Given a register machine M with instructions I0 It its Gz39idel number or code FM l is the code of the sequence FI01rI gt ie t r 1 TI m11 M WHOM where pm is the mth prime We can thus deal with register machines as natural numbers via their Godel numbers We rst see that we can e ectively recognize these codes Lemma 149 The relation RMe where RMe E e is the Gz39idel number of some register machine M is primitive recursive Proof We will need to check that e codes a nite sequence and that each term in the sequence is a valid instruction code ie any instructions to branch to are within the sequence We start by noting that Mn 2 V RMel l0 where RMe 1 holds i e is the Godel number of a machine with instructions 0 l we can use e as an upper bound since as we have seen a code for a sequence of length 1 will be at least 1 We will show that the relation RMe l is primitive recursive RM e is then primitive recursive since it is obtained using bounded disjunction For this we observe that RMe l E Seqe Lengthel1 l l e l A V V V em20315jvem21315j7kem22 m010j0k0 which is a bounded disjunction of primitive recursive relations 1 CHAPTER 1 COMPUTABLE FUNCTIONS 23 De nition 150 For each h 2 0 we let my be the hary function computed by the register machine with Godel number e or the trivial partial function with empty domain if e is not the Godel number of any machine More precisely the nal value of R0 if e FM l for some register machine M which eventually halts when started k with R1x1Rkxk I1awaxk T 1f e 1s not the Godel number of a machine or e FM l but M does not halt when started with R1 x1RC xk If f is a hary partial function and e E N is such that f 9930 we say that e is an index for Note that a given function will have many different indices in nitely many in fact since multiple register machines will compute the same function Before we present the main theorem of this section we prove a simple but useful technical lemma Lemma 151 De nition by cases Let R1 Rn be hary primitive recur sive relations which are mutually exclusive and exhaustive ie each x1 xk satis es exactly one of these relations Let f1 f7 be hary primitive recursive functions and de ne the function f by f1x1 xk if R1x1 xk fx1 xk fnx1 xk if Rnx1 xk Then f is primitive recursive Proof We have fx1 xk 2quot1f1x1 xk XRx1H xk 1 Here is the main theorem about Godel numbering Theorem 152 The Enumeration Theorem For each h 2 0 de ne the h 1ary function Uk as Uk5961 a 95k 999051 axkl Then Uk is partial recursive Note 153 We may view Uk as a universal register machine It is computed by some register machine which is able to use the input e to simulate any other register machine This is the idea behind a programmable computer CHAPTER 1 COMPUTABLE FUNCTIONS 24 Proof The idea will be to encode the state of a register machine as it is run ning ie the current values of the registers as well as the next instruction to execute Together with the Godel number of the machine this will be sufficient information to continue the running of the machine We will encode the state using the following function 00 Statee x1 mg n p0m 1 10 where after having run 71 steps the register machine with Godel number 5 is about to execute instruction 1m and the value of each register R is 2 Note that we have an in nite product however as any machine will use only nitely many register all but nitely many of these terms will be 1 and hence it is wellde ned We will rst show that the State function is primitive recursion We will use the recursion Statee x1 95k 0 p00 p211 pk 1 Statee x1 mg 71 1 Stepe Statee x1 95k where Stepe 2 will output the state of the machine with Godel number 5 after running one step instruction starting in state 2 Note that the initial value Stateex1 xk0 is the starting state of the machine with instruction 0 to be executed the registers R1 k set equal to 951 95k and all other registers equal to 0 We will show that the Step function is primitive recursive which will show that State is primitive recursive We de ne the Step function by cases depending on the type of the next instruction to be executed Note that we will presume that e is actually the Godel number of a register machine and 2 a code for a state we will only actually use it in this case We set MOW W 1 emo 0 NOW 6mo 1 and 2 0 p0kmp23911 if em0 1 and Z1 gt 0 otherwise if if 2 Stepe 2 Z 2 2 where we have used the abbreviations m 20 239 5701 939 5702 k 5ms and we use n here to denote the exponent ofp239 is n this is slightly different from the coordinate function for sequences but essentially the same and prim itive recursive Note that em is the code of the instruction to be executed em0 tells which type of instruction it is and zl1 21 is the value of the register being incremented or decremented Note that when the machine reaches a HALT instruction the state does not change All the conditions are primitive CHAPTER 1 COMPUTABLE FUNCTIONS 25 recursive and are mutually exclusive and exhaustive so by the previous lemma Step is primitive recursive e can now nish the proof by searching for the least n such that the machine has reached a HALT instruction Let St0pea 961 a 96k W 5Stateec1ckno 22 A RM5l ie the least n such that the machine has reached a HALT instruction or unde ned if the machine never halts or e is not the Godel number of a register machine Stop is thus a partial recursive function We lastly can set Uke x1 951C Statee x1 xk Stope x1 xk1 ie we nd the value of R0 in the code of the machine state once it has halted the function is again unde ned it the machine never halts or e does not code a machine This shows that Uk is partial recursive nishing the proof 1 Since we can substitute the Godel number of any given register machine in for e in Uk we obtain the following Corollary 154 Every RMcomputable function is partial recursive Hence the class of RMcomputable functions is the same as the class of partial recursive functions The same sort of analysis used in the Enumeration Theorem can be applied to other notions of computable functions such as Turing Machines Markov Algorithms etc The idea is that any reasonable notion of an algorithm proceeds in steps and we can develop an analogous coding for the state of the algorithm and the stepping function as we did above This presents strong evidence that the class of partial recursive functions has captured the intuitive notion of computability This necessarily imprecise idea is the content of what is known as Church s Thesis Church s Thesis Any intuitively algorithmically computable numbertheoretic function is partial recursive We will henceforth take this as our de nition of a computable function and study the properties of the class of partial recursive functions Another immediate consequence of the Enumeration Theorem is the follow ing Corollary 155 The class of partial recursive functions is the smallest class of partial functions containing the primitive recursive functions and closed under composition and minimization Note in fact that we only need to apply minimization once in order to construct a given partial recursive function A natural question is whether we can avoid using partial functions if we want to study the total recursive functions One approach would be to only allow minimization to be applied to a relation Ry x1 one which has the CHAPTER 1 COMPUTABLE FUNCTIONS 26 property that for each 951 one there is a y satisfying Ry x1 one As we will see in the next section though there will not be an effective algorith mically computable way of determining when a relation has this property The next example gives more evidence that the use of partial functions in studying computability is somehow necessary Example 156 We give an example of a partial recursive function which can not be extended to a total recursive function et 9 A be a partial function We say that a total function f N A N extends 9 if we have 995 for any x E domg ie f simply de nes values for any numbers not originally in the domain of 9 De ne the partial recursive function g by setting gm U1ltxxgt1 wl1x1 where following usual conventions 995 is unde ned when U1x x is unde ned Suppose f were a total recursive function which extended 9 Let 50 be an index for f ie f lt29 But then ee WEMBO U150a 50 so we have that 950 is de ned namely 950 U15050 1 contradicting that feo 950 since 50 E domg Hence 9 can not be ex ten ed to a total recursive function We will use this function 9 later Note that the above is an example of diagonalization The function g itself is not problematic in this regard since we can and in fact must have 95 T when 5 is an index for 9 But this technique shows that we can not have a version of the enumeration theorem for the total recursive functions ie there is no function V1e 951 which is a total recursive function and enumerates all the total recursive unary functions in the way that U1 does for the partial recursive functions Note 157 There is also a characterization of the primitive recursive functions in terms of machines We can de ne a Loop Program as follows We have a number of registers as before and increment and decrement instructions These instructions do not branch though execution always proceeds to the next instruction decrementing a register with value 0 simply does nothing In addition we allow loops of the form for R do S where R is a register and S is a sequence of instructions possible containing other loops this is executed by repeating the instructions in S a number of times equal to the initial value of R1 we can change Rz within the loop but this does not affect how many times the loop is executed The class of Loopcomputable functions turns out to be equal to the class of primitive recursive functions CHAPTER 1 COMPUTABLE FUNCTIONS 27 16 Unsolvable Problems We now turn our attention to which sets are computable De nition 158 A set A Q Nk is recursive if its characteristic function XA is a total recursive function This is the same de nition as for relations and we will treat sets and relations identically Example 159 The set An Nnis prime is recursive since we saw earlier that its characteristic function is in fact prim itive recursive Similarly the sets 3 3 codes a sequence and e e is the Godel number of a register machine are both recursive primitive recursive again There are of course many nonrecursive sets since there are continuum many subsets of the natural numbers but only countably many recursive func tions We are interested though in determining whether certain natural ex plicitly de ned sets are recursive We give a rst example of a nonrecursive set ere Example 160 Let g be the partial function constructed earlier and de ne the set K Q N as K domltggt z 90 i We claim that K is nonrecursive If it were recursive then the function 7 995 ifxEK fz o 3ng would also be recursive since we can produce a register machine which rst computes XKx and halts with output 0 if x Q K otherwise if x E K the machine computes 995 which is de ned and outputs that value But then f would be a total recursive function extending g a contradiction We will be interested in determining when certain problems can be solved algorithmically We introduce the following notation to make this precise De nition 161 A problem is a set A Q Nk for some k We say that the problem is solvable or decidable if the set is recursive otherwise we say that it is unsolvable or undecidable CHAPTER 1 COMPUTABLE FUNCTIONS 28 The idea is that to each such set we associate the problem of determining whether a given number is an element of that set eg the set of primes is associated to the problem Given a particular number determine whether or not it is a prime Thus a problem is solvable if there is an algorithm which when given a particular number determines whether or not the number is an element of the set Example 162 As we have noted above the set of primes and the set of codes for sequences are solvable whereas the set K is unsolvable Certain natural problems occurring in mathematics have been shown to be unsolvable we list several here Example 163 Hilbert s Tenth Problem lnformally Hilbert s Tenth Problem is to determine when a given Diophantine equation has a solution ie given a polynomial px1 xn with integer coef cients to determine whether there are integers a1 17 such that pa1 a7 0 here are several ways of turning this into a precise problem the following theorem of Matijasevic shows that it is unsolvable in a very strong way Theorem 164 Matijasevi There is a polynomial pz0x1 xg with integer coe lcients such that the set n Npna1ag Ofor somea1a9 EZ is not recursive Hence no reasonable algorithmic solution exists Example 165 Word Problems for Groups Let G be a group presented with nitely many generators and relations The word problem for G is to determine given a particular word 11 in the generators of G whether or not w la the group identity element of G The word problem of some groups is solvable such as abelian groups and free groups however Novikov showed that there is a nitely presented group G with an unsolvable word problem Example 166 The Halting Problem A problem which is particularly relevant to our study is The Halting Problem which we de ne to be the set H e e N 990 l Thus the problem is to determine whether a given register machine with code e eventually halts when started with all registers empty We will see below that the set H is not recursive ie the Halting Problem is unsolvable 17 Reducibility We have so far seen one concrete example of a nonrecursive set the set K We wish to develop techniques for showing that other sets are not recursive which avoid direct arguments The idea will be introduce a notion of reducing one problem to another which will give a gauge of relative complexity of problems CHAPTER 1 COMPUTABLE FUNCTIONS 29 De nition 167 let A and B be subsets of N We say that A is manytoone reducible to B or just reducible if there is a total recursive function f N A N such that for all n E N n E A if and only if E B We write A Sm B to indicate that A is reducible to B Thus if A Sm B then a reduction function f allows us to reduce the mem bership problem for A to that for B as the next lemma makes precise Lemma 168 Suppose A Sm B If B is recursive then so is A If A is not recursive then B is not recursive Proof Let f be a recursive function so that n E A iH E B and suppose B is recursive so that X3 is recursive Then XAn X3fn ie XA X13 0 f so that XA and hence A is recursive The second statement is just the contrapositive of the rst 1 Note 169 The relation Sm is a quasiorder ie it is re exive and transitive It is not a linear order though there are sets A and B so that A gm B and B gm A The following theorem will be a key technical tool in producing reductions Theorem 170 The Parametrization Theorem Let 050951 m be a k 1ary partial recursive function Then there is a primitive recursive function fx0 such that for all x0 x1 me E N we have 9950 x1 xk wglzco xl 951C Proof Since 9 is partial recursive there is some register machine which com putes it By an easy modi cation we can set up the machine so that unlike our normal convention this machine uses registers R0 R1 Rk for input and outputs in R0 Call this machine M Now given 950 we want fx0 to produce an index for a machine MacO which takes inputs x1 xk in registers 1 Rk sets register R0 equal to 950 and then runs machine M Thus MacO should look as follows START 950 times Let the instructions of M be J0 L Then the instructions of M10 will be ltR0111a R0Ita J6 Ji x 10 many where the instruction J is the same as Jz except that the branching instructions have their indices increased by 950 to account for their later position in the list CHAPTER 1 COMPUTABLE FUNCTIONS 30 eg if J0 R17JjJC then J6 RF jEOJCEO Recalling that the code of a machine is the code for the sequence of codes for its instructions we ave 1071 t o o m1 F 1 fe FMon H Mm 3 5 H px0m J m0 m0 where er 5 0 if Jm is an increment instruction Finn er 5 0 7 0 if Jm is a decrement instruction er if Jm is a HALT instruction Note that the second product has a xed number of terms which can be de ned explicitly so that the function f is primitive recursive 1 With a little more care we can prove the following version of the Parametrization Theorem generally known as the S M N Theorem Corollary 171 The SMN Theorem For each m and ii there is a prim itive recursive function 3quote x1 95m such that quot394 quot n We 951 a 95m 31 yn wsgex1mxmy1quotHay for ullex1xmy1uyn EN The idea is to apply the above idea to the function Uk and handle several input registers at once Note 172 We can view the Enumeration Theorem and Parametrization The orem as saying that our indexing of partial recursive functions satis es certain good properties If we chose some arbitrary way of assigning indices to the partial recursive functions it would not necessarily satisfy these properties al though most any reasonable indexing will These two theorems will be the chief properties we need and later theorems we prove about the class of partial re cursive functions will not need to refer to the actual coding of register machines just the conclusions of these two theorems We can now prove the unsolvability of the Halting Problem Theorem 173 The Halting Problem is unsoluuble ie the set H 5 E N 903 l is not recursive Proof We will show that the set K is reducible to H since K is not recursive this will show that H is not recursive Consider the function 996 y 5906 U206 96 CHAPTER 1 COMPUTABLE FUNCTIONS 31 which is partial recursive Recall that K x 99995 Applying the Parametrization Theorem there is a primitive recursive function f such that m y a z 8 y for all x and y Then if x E K we have 3995 i so l for all y so w i o l ie E H Similarly if 95 K then 990 T so H Thus f is a reduction of K to H 1 18 The Recursion Theorem We present an important and powerful theorem due to Kleene Theorem 174 The Recursion Theorem or Fixed Point Theorem Let 9e x1 xk be a partial recursive function Then there is an index e0 such that for all 951 xk k 6505x15 xl eox1 xk The following corollary makes the name clearer Corollary 175 Let f N A N be a total recursive function and k 2 1 Then there is an index e0 such that k 7 1c ltPf io 7 wgo Thus if we think of f as a procedure for transforming one register machine into another the theorem says that there will be a machine so that the modi ed machine although it may be a di erent machine will still compute the same partial function ie this function is a xed point77 of Proof of Corollary 175 Let 9ex1 xk Ukfe x1 xk Apply ing the Recursion Theorem we nd an index e0 so t at am m 6lteoz1mzkgt Ukfeox1 xi w iwm am for all 951 xk as desired 1 Proof of Theorem 174 The idea will be to consider register machines which somehow have access to their own indices we will then try to nd such a machine which when given 951 xk evaluates the function 9 on its own index and the inputs x1 x Applying the Parametrization Theorem to 9 we can nd a primitive recur sive function f such that 9w x1 xk lt2lc2 x1xk CHAPTER 1 COMPUTABLE FUNCTIONS 32 and applying it to the function UkU1u u 951 i i xk we can nd a primitive recursive 51 such that k k 99512 951 5x10 ux1v axk Let U be an index for the function f o 51 ie 99151u for all u Then k k 518 W vx1vak W l v 951 a 95k mam i i m so taking 50 dv nishes the proof 1 Example 176 We can use the Recursion Theorem to give another proof that Ackermann s function is recursive We can rewrite the recursive de nition of An x as follows x1 ifn0 Anx An 11 ifngt0andx0 An41Anx1 ifngt0andxgt0 We consider a procedure which take some partial function which is able to correctly compute some values of An and improves it by computing ad ditional values for which the required data is available Speci cally given a partial function Mn 95 1901 95 de ne Mn 95 as x1 ifn0 nx 9014 11 ifngt0andx0 9014 1ltpg2nx41 ifngt0andxgt0 Then using the enumeration and Parametrization Theorems there is a primitive recursive function fe which computes an index for d from an index 5 for lt2 ie 1 w ly Now let 50 be a xed point of f iiei wg zo 193 Then we have 95 1 if n 0 7195 w lwm x 901 11 if n gt 0 and x 0 901 1ltpgnx 1 ifngt0andxgt0 993 ie A satis es the recursive characterization of Ackermann s function so 7 2 An x 7 9950 7195 is recurs1ve as des1red This same technique can be used to show that any wellde ned function de ned using recursion is partial recursive CHAPTER 1 COMPUTABLE FUNCTIONS 33 We next consider the distinction between a partial recursive function and its indices ie the collection of register machines which compute the function De nition 177 We say that a set I Q N is an index set if there is a collection C of partial recursive functions such that IICeltJ 1EC ite I consists of all indices for functions in the class C Equivalently I is an index set if and only if whenever e E I and 239 is such that lt29 10 then 239 E I as well Nontrivial index sets are complicated as the following theorem shows Theorem 178 Rice s Theorem IfI is an index set and I y I and I y N then I is not recursive Proof Since I is recursive iH NI is recursive we may assume that the function 1 with empty domain is in C so that all of its indices are in IC Let a be some index for We may also assume that there is some nontrivial partial function which is not in C so there is some I with 51 y d with b E Ici Now consider the function fx y 2 given by m y z w 1gtltzgt Wm 4 Wm This is partial recursive so there is an e with 995 y 2 fx y From the SMN Theorem we then have m w wig 2 5156131 Let Mac y s e x We then have If 1gty i then y w 1gtz E C and if 551 T then y d E C This reduces some question about halting to the set Ici We now make this precise De ne the set H as H ltxygt1w 1gtyl This is a fuller version of the Halting Problem If we de ne the function hs to be otherwise hs 7 hs0 31 if 3 codes a sequence of length 2 a then we have s E H if and only if hs E Ic ie H reduces the set H to N Ici If we can show that H is not recursive we will then have that N IC is not recursive hence Ic is not recursive To see this we reduce the Halting Problem H to H Let fe e 0 Then we have e E H if and only if fe E H so we are done 1 CHAPTER 1 COMPUTABLE FUNCTIONS 34 This gives us the following immediate corollary Corollary 179 The following index sets are not recursive Tot e lt29 is a total function Con e lt29 is a constant function lnf e domltp 1 is in nite If e W8C f where f is any kary partial recursive function In particular we can not algorithmically determine whether a particular register machine computes a total function further motivating or use of partial functions Also the set of indices for a given function is not recursive however we can effectively produce in nitely many indices for a given function Lemma 180 The Padding Lemma For each h 2 1 there is a primitive recursive function fe n such that 1 For each e and every n ugh n 2 For each e ifn lt m then fen lt fem We skip the proof as the idea is simply to append n irrelevant instructions to the machine with Godel number e We can also use the Enumeration Parametrization and Recursion Theorems to show that all of the partial recursive operations are effective We state two instances of this without proof Theorem 181 For each h and in there is a recursive function f such that A i lw mgm Wm nglwzltfgtlt1au m W What on for allei1imx1xk This says that we can compute an index for a composition of functions from indices for the original functions The analogous statement for primitive recursion is Theorem 182 For each h three is a primitive recursive function f such that Ic1 1C we ox1mxkgt w Rectum k1 Ic2 k1 whale 1x1mxk wt y we y x1 a a me 961 a a a me for all eiyac1 xk CHAPTER 1 COMPUTABLE FUNCTIONS 35 19 The Arithmetical Hierarchy In this section we introduce a hierarchy of sets relations measuring the com plexity of their de nability De nition 183 The Arithmetical Hierarchy We de ne both the classes 28 and Hg to be the class of primitive recursive relations of any arity Given n 2 0 we de ne the class ngrl to be the class of all hary relations P such that P has the form Px1 xkanRxlau xkay where R is a h 1ary relation in the class 119 Similarly we de ne HERA to consist of all relations of the form P9 1 96kEvymxiawaxk where R is a h 1ary relation in the class 29 We de ne the class A9 to equal 29 O H ie those relations which are in both classes Note 184 The superscript of 0 refers to the fact that the quanti ers are applied to objects of level 0 ie natural numbers We can similarly de ne a hierarchy of E relations etc where quanti ers are applied to sets of natural numbers but we will not study this here The level of a relation in the Arithmetical Hierarchy thus corresponds to the number of quanti ers needed to de ne it For instance if R is a primitive recursive relation then the relation Px E 3szHuRx y 2 w is a 2g relation We list some of the basic closure properties of these classes Theorem 185 We have the following 0 n139 N The classes 29 and H9 are both contained in the classes ngrl and H N The classes 29 and H9 are closed under nite conjunction and disjunc tion 93 The classes 29 and H9 are closed under bounded quanti cation 4 For n 2 1 the class 29 is closed under existential quanti cation and the class H9 is closed under universal quanti cation 5 A relation P is in 29 if and only the relation P is in Hg Proof Recall that we showed that the class of primitive recursive relations is closed under conjunction disjunction negation and bounded quanti cation These are all proved by induction on n CHAPTER 1 COMPUTABLE FUNCTIONS 36 1 This is immediate for n 0 since 28 Hg For n 2 1 we easily have that 2 Q HE1 since we can just add a vacuous quanti er one applied to an unused variable and to see that 29 C EEHA we can write P as Px1 xk E 3yRx1 9 y with R in H0 by inductive assump 71711 tion R is then in H9 and hence P is in 20 1 H9 is handled similarly 2 Immediate for n 0 Suppose P1 and P2 are 29 for n 2 1 and we have Plx1 me E 3yR1x1xky with R1 in Hail Then P1x1 xk P2x1 me E 3yR1x1 95k y 3yR2x1 95k y E 3yR1x1 xk y 32R2x1 95k 2 E 3y32R1x1 xk y R2x1 95k The quanti ed expression is Hail by assumption and part 4 will show that this expression is thus in 29 The other cases are handled similarly 3 This is handled similarly to part 4 Let Px1 xkz be 29 for n 2 1 where Px1 xkz E 3yPx1 achz y with R in Hail Then 32Px1 xk 2 E HZHyPx1xkzy E 33Seqs Lengths 2 Pz1 95k 30 51 ie we encode 2 and y as a pair since coding and uncoding of nite sequences is primitive recursive the part inside the quanti er is H0 nil 5 Immediate for n 0 and for n 2 1 with P in 29 and R in Hail we have Px1xk E HyRx1xky E Vy Rx1xky so that dB is in 2971 by assumption and hence P is in Hg 1 Example 186 We can see that the set H e 1gt0 belongs to the class 2 We can write He E RM5 3nmachine e halts after at most 71 steps on input 0 E 3nRMe A 5smceeono 22 where Statee 0 n and RM5 are primitive recursive so that this is 2 Note 187 We often use the notation 3249 951C 1 to indicate that 5 codes a register machine which halts on inputs x1 me after at most 71 steps as discussed above this is a primitive recursive relation of e n 951 xk CHAPTER 1 COMPUTABLE FUNCTIONS 37 The class 2 is of particular importance and we Will give several di erent characterizations of it De nition 188 We de ne the set We Q NC to be We domWE Cl Theorem 189 A kary relation P is in E if and only P domi for some kary partial recursive function 1 ie i P W3 for some e Proof If P is 29 so that Px1 xk E 3yRx1 xk y With R primitive recursive then P domi Where M961 Jxk Mlex1mzkyl is partial recursive Conversely if P domi With 1 999 then Pm gm 2 anw flm m l so P is 2 since the inner relation is primitive recursive as discussed above 1 De nition 190 Let A be an in nite subset of N The principal function of A if the onetoone function 7rA Which enumerates A in increasing order ie 7rA is an increasing function such that A ran7rA Lemma 191 Let A be an in nite subset ofN Then A is recursive and only the principal function 7rA is recursive Proof If A is recursive then 7rA can be obtained using the recursion 7rA0 the least element of A 7rAn 1 Myly gt 7rAn y E A Conversely if 7r A is recursive then y yEAiH VWAxy 10 Which is recursive since the class of recursive predicates is closed under bounded disjunction 1 Theorem 192 For A Q N the following are equivalent 1 A is 29 2 A domi for some partial recursive function 5 A rani for some partial recursive function 4 Either A ll or A rani for some total recursive function CHAPTER 1 COMPUTABLE FUNCTIONS 38 5 Either A is nite or A rani for some onetozme total recursive func tion Proof We have already seen that 1 and 2 are equivalent and it is clear that 5 implies 4 and that 4 implies To see that 3 implies 1 note that if A rani then 3 E A E y E 3x3nltp2x y where e is an index for 1 so this is 29 To see that 1 implies 5 let R be a primitive recursive relation so that x E A E 3yRx y and de ne the set E as B 213112 RxyA x71Rxz Then B is an in nite primitive recursive set so its principal function 7rB is a onetoone recursive functions Note that for each x E A there is a unique y with 2133 E El We can then de ne ii to be 1M WBUIDO ie the power of 2 in 7rBn which is the xcoordinate and we have that ii is a onetoone total recursive function with A ranil 1 Note 193 These sets are generally known as recursively enumerable re setsl We will now develop a better picture of the arithmetical hierarchyl Theorem 194 A kary relation P is in the class A if and only if it is recursiv e Proof If P is recursive so that Xp is a recursive function then P domi where Mr Mylx x ll so that P is 29 since P is also recursive we have that P is also 2 so that P is H as well and hence A Suppose P is A9 and let R1 and R2 be two primitive recursive relations so that 13951 wile E 32131951 3170 E VyR2x1 axle y We can then de ne t total recursive function f by 951 axle iii131051 Jim 3 V 32951 xkayll and we will have Pxiawaxk E R1x1 axkfx1 axk so that P is recursive 11 CHAPTER 1 COMPUTABLE FUNCTIONS 39 Theorem 195 Universal 2 relations For each n 2 1 and h 2 1 there is a relation VICquot such that 1 VICquot is a h lary relation in the class 29 2 For each hary relation P in 29 there is an e E N such that Pac1 ask E ane x1 ask The analogous statement holds for Hg Proof This is done by induction on n Note that by the Enumeration Theorem we can set Vk1 domUC where Uk is the h lary universal partial recursive function If VIC is universal for 29 then Vk is universal for H9 and we can set an1e x1 xk E HkanJr e x1 ask 1 Note 196 There is no analogous universal Ag relation To see this eg for h l suppose there were a Ag binary relation D which was universal for unary Ag relations De ne the relation P as P9c E Dac 9c Then P is A0 so there should be some e so that P9c E De 9c for all as but n then De e E Pe E De e a contradiction Lemma 197 Let A B Q N with A Sm B HE is 29 then so is A ifB is 3 then so is A Proof This is done by induction on n the case of n l is representative so we only give that Suppose R is a primitive recursive relation so that B06 E 3211396 and let f be a total recursive function so that as E A if and only if E B Then we have Am 2 3yRfz y 2 ayazanw 2ltxgt 2 A Ru 2 where e is an index for f so that A is E as well 1 De nition 198 For n 2 l we say that a set E Q N is Eelcomplete if 1 B is in the class 29 2 For any 2 set A we have A Sm B The notion of a Tiacomplete set is de ned similarly CHAPTER 1 COMPUTABLE FUNCTIONS 40 Theorem 199 For each n 2 1 there is a Egcomplete set and a Hgcomplete set A Egcomplete set is not in Hg and a Hgcomplete set is not in 2g Proof Let V1 e as be the universal 2g relation from above Then the set 28 31 V1ne is 29 and a 2g set A with Ax E V1 e as is reducible to this set by the function 25 3 The complement of a 2g set is easily Hgcompletei To see that a Egcomplete set is not in Hg it suf ces to show that there is a 2g set which is not in Hgi If we de ne the set Ax E Vg1xx then the same sort of diagonal argument used above shows that A can not be 2g hence A can not be Hg The case of Hg follows immediately 1 We can thus see that the arithmetical hierarchy is a proper hierarchy Corollary 1100 For n 2 1 we have Ag 2g Ag Hg and 2g U Hg Ag1 ie all inclusions are proper Proof The rst two inclusions are proper by the above theorem since a Eg complete set is not Hg and hence not Ag and similarly for Hgcomplete setsi For the third inclusion we must nd a set in Ag1 which is neither 2g nor Hgi Let A be a Egcomplete set so that A is Hgcomplete and de ne the set E by B2xx AU2xlx A Then B is a Ag1 set since it is the union of a 2g set and a Hg set We have that A is reducible to B by the function 295 so B can not be Hg and negA is reducible to B by the function 995 295 1 so B can not be Eg El Chapter 2 Undecidability of Arithmetic We will apply the results of the previous chapter to show that the theory of arithmetic is undecidable that is there is no algorithm to decide whether a sentence in the language of arithmetic is true or false 21 The Language of Arithmetic By the theory of arithmetic we mean the set of sentences which are true in the structure N 0 1 gt where N 0 1 2 i i is the set of natural numbers 0 and 1 are names for these numbers and denote the binary functions of addition and multiplication on N and denotes the binary relation of equality on Ni We introduce the language we will use for this structure De nition 21 The Language of Arithmetic The language will contain in nitely many variable denoted x0 x1 952 i H although we will often use as y etc for simplicity and symbols for the constants 0 and 1 We next de ne the collection of terms which are built from these inductivelyi That is each variable is a term and 0 and 1 are terms and if t1 and t are two terms then so are t1 t2 and t1 tQi For each natural number n we will use 73 to denote the term 1 1 and call this the standard term for n although often we will just W n times write n to mean the standard term 73 We will similarly abbreviate x x as x and so forth We next de ne formulas An atomic formula is an expression of the form t1 t2 where t1 and t are terms The collection of formulas are built inductively using the Boolean connectives n V and and the quanti ers 3 and Vi That is each atomic formula is a formula and if F and G are formulas and x is a variable then the following expressions are also formulas F F G F G HxF and VxFi 2 CHAPTER 2 UNDECIDABILITY OF ARITHMETIC 42 Example 22 The expression 3295 2 l y is a formula Quanti ed variable range over the natural numbers so the intended meaning of the above is there is a natural number 2 such that x 2 l y Note that we can nd such a 2 i and only if x lt y so we will use the expression x lt y to abbreviate the above formula Example 23 The formula 95gt 1A 3y32ygt l2gt lxyz expresses the property that x is a prime number where expressions involving lt are again used as abbreviations De nition 24 An occurrence of a variable in a formula is said to be bound if it is contained within the scope of a quanti er otherwise the occurrence is called free In the example above the occurrences of x are all free occurrences whereas the occurrences of y and 2 are all bound Note that a variable can occur both freely and bound in the same formula We say that x is a free variable of a formula F is it has at least one free occurrence and we often write Fx to indicate that the only free variable of F is x A sentence is a formula which has no free variables Sentences are formulas to which we can assign a truth value in the structure N by interpreting the functions and equality in the usual way and letting quanti ed variables range over N Note that a formula with free variables does not have a truth value unless we substitute speci c values in for them If Fx1 xk is a formula with free variables x1 xk and n1 me E N then Fn1 mg is the sentence obtained by substituting the standard terms n1 nk in for the respective free occurrences of 951 ask This will then beNeither true or false 22 ArithmeticalDe nability We now consider which relations and functions can be de ned in the language of arithmetic De nition 25 Arithmetical De nability A kary relation R Q N C is a39m39thmetically de nable if there is a formula Fx1 as y in the language of arithmetic such that for all n1 nk E N the relation Rx1 xk is true if and only if the sentence Fn1 mg is true in N A kary partial function f NIC A N is arithmetically de nable if its graph is de nable ie there is a formula Fx1 95k y such that for all n1 nk m E N we have fn1 95k m if and only if the sentence Fn1 nk m is true in N Example 26 The function Quotienty as introduced earlier is arithmetically de nable by the formula Fy x 2 3v x0vltxyxzv CHAPTER 2 UNDECIDABILITY OF ARITHMETIC 43 Note 27 The notion of arithmetically de nable relations is similar to the arithmetical hierarchy discussed earlier There we were allowed to build up relations using quanti ers and connectives starting from the primitive recursive relations here the basic relations we start from are ones of the form t1 t2 where t1 and t are terms We will later see that these two notions coincide We will show that all recursive functions and relations are arithmetically de nable We will do this by induction on functions as we did when we showed that all partial recursive functions are RMcomputable Lemma 28 Each initialfunction is arithmetically de nable Proof The zero function Zx 0 is de ned by the formula FxyExxy0 the ac ac is really irrelevant but we include it just to ensure that ac is a free variable of the formula we will omit such trivialities from now on The successor function 595 ac 1 is de ned by the formula GxyEyx1 and each projection function Pkx1 951C ac is de ned by the formula chx1mxky Ey xl 1 Lemma 29 The class of arithmetically de nable functions is closed under composition ie ifh1ac1 xk m 951 xk an 9 x1 xm are all a39rithmetically de nable then so is the function fac1 xk with fac1 xk gh1x1 xk hmx1 xk Proof Let h1 hm and g be de ned by the formulas H1 Hm and C respectively Then f is de ned by the formula 3y139 quotHymH1x1waxky1 39 AHmx1 axlcaywdAGQla uaymay ie the variable yl ym are used to stand for the intermediate values in the calculation 1 Lemma 210 If the k 1a39ry relation Rx1 xk is a39rithmetically de n able then so is the ka39ry partialfunction fx1 axle Mlex1 a a me 21 de ned from B using minimization CHAPTER 2 UNDECIDABILITY OF ARITHMETIC 44 Proof If R is de ned by the formula Fx1 95k y then f is de ned by the formula Cxl 95k y Fx1 why A existsdz lt y Fx1 xkz El Note 211 A relation is arithmetically de nable if and only if its characteristic function is arithmetically de nable To see this suppose 135 is de ned by the formula Fi39 then XR is de ned by the formula Gay 2 y 1A Fm v y o A we and if XR is de ned by the formula Ci39 y then R is de ned by the formula F9Z39 E G551 The case of primitive recursion will require a bit more work lntuitively we want to imitate the technique for RMcomputability ie compute fy a by successively computing f0 55 f1 9 fy In order to do this though we need an arithmetically de nable way of coding a sequence Although the coding we introduced earlier will turn out to be de nable this is difficult to see a priori so we will develop a new manner of coding sequences which is more transparently de nable This will involve a bit of number theory Recall that two positive integers are relatively prime if the have no common factor other than 1 a set of positive integers is said to be pairwise relatively prime if any two distinct integers in the set are relatively prime Lemma 212 Given a positive integer k we can nd arbitrarily large integers in such that the set m12m1km1 is pairwise relatively prime Proof Let in be any positive integer which is divisible by all of the primes less than k eg any multiple of kl We claim that this in satis es the conclusion Suppose not and let 1 S i lt j S k be such that im 1 and jm 1 are not relatively prime Let p be a prime which is a factor of both im 1 and jm 1 Then p can not be a factor of m Since pljm 1 7 im 1 j 7 im we must have that p is a factor ofj 7 i Since j 7i lt k we must have p lt k But then p is a factor of m by our choice of m a contradiction 1 Example 213 If k 5 then the primes less than k are 2 and 3 so we can take in to be any multiple of 6 So taking in 6 we have that the set 7 13 19 25 31 is pairwise relatively prime CHAPTER 2 UNDECIDABILITY OF ARITHMETIC 45 Lemma 214 Chinese Remainder Theorem Let n1 nk be a set of positive integers which is pairwise relatively prime Then given any nonnegative integers r1 rk with r lt n for 1 S i S k we can nd a nonnegative integer r such that Remainderr n1 r1 for all i Proof let n n1 me For any r with 0 S r lt n de ne the remainder sequence of r to be r1rk where r1 Remainderrn1 for 1 S i S k We want to nd an r whose remainder sequence is the sequence we are given We claim that if 0 S r lt s lt n then the remainder sequences for r and s are different Suppose that r and s have the same remainder sequence Then s 7 r is divisible by each of n1 me since these are pairwise relatively prime we must then have that s 7 r is divisible by their product n But 0 lt s 7 r lt n a contradiction Hence distinct r s give rise do distinct remainder sequences There are exactly n possible remainder sequences and n choices of r hence each possible remainder sequence is obtained from some r This nishes the proo 1 Example 215 Considering the previous example if we choose r1 lt 7 r5 lt 31 then we can nd an r which is a solution to the system of modular equations r E r1 mod 7 r E r5 mod 31 We can view this r together with m 6 as encoding the sequence r1 r5 We now introduce our coding method De nition 216 Godel s function Given nonnegative integers r m and i we de ne the function as r mi Remainderr m 1 1 This is known as Gadel s function Note that this function is arithmetically de nably by the formula Br m i y 0 yltm i113uru m i11y Lemma 217 Given a nite sequence r0 rk of nonnegative integers we can nonnegative integers r and m such that r m r for each 0 S i S k Proof Using k 1 in place of k above we can nd a positive integer in such that r lt im1 for each 0 S i S k and such that the set m1 2m1 k 1m 1 is pairwise relatively prime By the Chinese Remainder Theorem we can then nd an r so that r Remainderr 1m 1 r m for all 0 S i S h 1 CHAPTER 2 UNDECIDABILITY OF ARITHMETIC 46 Hence r and m encode the sequence r0 me via the function We can now prove Lemma 218 The class of arithmetically de nable functions is closed under primitive recursion ie the kary function g and the k 2ary function H are arithmetically de nable then so is the k 1ary function f de ned by f0axiawaxk 9x1waxk fy1x1waxk hyfyx1waxkax1Maxie Proof Let g and h be de ned respectively by the formulas Cxl xk w and Hy 2 x1 ask We want a formula Fy x1 9 w to say that there is a nite sequence r0 ry with re 9951 xk and n1 gi r 951 xk for 0 S i lt y and r1 11 this would clearly de ne We will do this by saying that there are an r and m which encode this sequence via the function which we know from the previous lemma Letting Br m i y be the formula de ning we can take our formula to be 3r3m 3uBr m 0 u Cxl xk Vii 2 y JudiBU mi u BTamai11vAHiauax1H axkav 30771351 This nishes the proof 1 Example 219 We can see that the exponential function fx y y is arith metically de nable by the formula Fx y w 3r3m Br 7110 1 Vii 2 ac JudiBU mi u Brmi1vv uyBrmacw Recalling that the class of partial recursive functions is the smallest class of partial functions containing the initial functions and closed under composition primitive recursion and minimization we thus have Corollary 220 Every partial recursive function is arithmetically de nable Hence we also have that every recursive relation is arithmetically de nable But more is true Corollary 221 The set K eltp 1e is arithmetically de nable so there is an arithmetically de nable set which is not recursive Proof If a function fx1 xk is de ned by the formula Fx1 ask y then the set dom f is de ned by the formula 321F061 a 96k y and the set ranf is de ned by the formula 3x1 kaFx1 ask The set K is the domain of the partial recursive function U2x ac since this function is arithmetically de nable so is K 11 CHAPTER 2 UNDECIDABILITY OF ARITHMETIC 47 We in fact can characterize Which sets are arithmetically de nable Theorem 222 Let P be a kary relation Then the following are equivalent 1 P is arithmetically de nable 2 P is in the arithmetical hierarchy ie P is either 2 0r Hg for some 71 Proof The theorem above in particular shows that every primitive recursive re lation is arithmetically de nable ie every relation in 20 Hg Since applying quanti ers to arithmetically de nable relations yields arithmetically de nable relations induction on 71 shows that every 29 or H9 relation is arithmetically de nable For the converse note that 230 U 2 U H9 7120 7120 consists precisely of relations in the arithmetical hierarchy From the closure properties proved earlier Ego is closed under the Boolean connectives and quan ti cation and contains the primitive recursive relations Since the class of arith metically de nable sets is obtained from the equality relations by applying these operations every arithmetically de nable relation is in 200 1 23 G del Numbers of Formulas We Will noW develop codes for formulas in the language of arithmetic in much the same way as we did for register machines De nition 223 For each formula F in the language of arithmetic we Will ass1gn a natural number rF the Gadel number of F We begin by inductively assigning Godel numbers to terms r01 30 r11 31 We 32 51 for a variable x W1 t1 33 5 7 W1 t21 34 5 7 Where t1 and t are terms We noW inductively de ne Godel numbers for for mulas beginning With atomic formulas W1 if 30 5W 7W FFAG1 2315FF 770 FFvG1 232571 7W F F12335FF vazF12345177F r3x1F72355 7FF1 CHAPTER 2 UNDECIDABILITY OF ARITHMETIC 48 where t1 and t are terms F and G are formulas and x1 is a variable De nition 224 We de ne the following subsets of N leN FF l F is a formula in the language of arithmetic SentN FF l F is a sentence in the language of arithmetic TruthN FF l F is a true sentence in the language of arithmetic Lemma 225 The sets leN and SentN are both primitive recursive Proof This is straightforward and is handled in much the same way as the predicate RMe was 1 We will now see though that the set TruthN is not recursive in fact not even arithmetically de nable This will show that the theory of arithmetic is undecidable There is no algorithm to determine whether a given formula is true or false in N Theorem 226 Every arithmetically de nable setA Q N is reducible to TruthN Proof Let Fx1 be a formula with one free variable 951 which de nes A so that A n E N Fn is truth De ne the function f N A N as r3x1x1 73 Facl l Then for n E N we have that n E A if and only if E TruthN so we will be done if we show that f is recursive This follows from the facts that n 235517711WF1gt gn r951 73 F951 l 2 31 5711731 7FFE1T Mn F951 if 230571 7773 and the function Mn r731 is obtained using primitive recursion M0 r01 3 kn1 Fn 11 335773 771 335W 731 Hence f is obtained by composing primitive recursive functions and is thus primitive recursive so we are done 1 Corollary 227 The set TruthN is not recursive Proof The set K is arithmetically de nable but not recursive since it is thus reducible to TruthN TruthN is not recursive either 1 CHAPTER 2 UNDECIDABILITY OF ARITHMETIC 49 Theorem 228 Tarski The set TruthN is not a m39thmetically de nable Proof Suppose that TruthN were arithmetically de nable so that it was 2 for some n by our earlier theorern Let B be a Sigcomplete set so that B is not in 2 We can not have that B is reducible to TruthN or B would be 29L so we have a contradiction 11 This theorem is often quoted as Arithmetical truth is not arithmetically de n able 77 Chapter 3 Decidability of The Real Numbers We Will noW consider the theory of the real numbers and see that this theory unlike the theory of arithmetic is decidable There is an algorithm to determine Whether a given sentence in the language of the real numbers is true or false in R We Will do this by showing that the class of de nable relations over R is much simpler than for N 31 Quanti er Elimination We extend our earlier de nitions slightly De nition 31 Let L be the language of ordered Tings iiei LLORQ17lt Where 7 is a unary function negation and lt is a binary predicate Everything is noW interpreted in R so that eg quanti ed variables range over R We de ne formulas and Godel numbers as before adding cases for the new symbols 7 and lt De nition 32 We say that two formulas F and G are equivalent F E G if they have the same free variables x1 i xk and de ne the same kary relation This is the same as saying that the sentence Vx1kaFx1iuxkltgt Cxl i i 9 is true in R Where we use F 42gt G as an abbreviation for F G F G Example 33 The formulas F and G with FOB y E 96 lt y Gxy232 z0x22y 50 CHAPTER 3 DECIDABILITY OF THE REAL NUMBERS 51 are equivalent We could thus have omitted lt from the language as we did for N however we will be interested below in what relations are de nable without using quanti ers and without lt we would have to add additional quanti ers to formulas De nition 34 We say that a formula is quanti erfree if it contains no quan ti ers ie it is a Boolean combination of atomic formulas of the form t1 t or t1 lt t for terms t1 and t2 Note 35 The set of terms is the same as the set of polynomials with integer coefficients over the variables since terms are formed from 01 and variables using and 7 The fundamental theorem which will lead to the decidability of R is the following Theorem 36 Quanti er Elimination For any LORformula F there is a quanti erfree formula Fquot such that F E Fquot Example 37 The formula 39511952 bx c 0 is equivalent to the quanti erfree formula a0b0c0a0b 0va 0b274ac20 where y 2 etc abbreviate the obvious formulas Note 38 The only properties ofR we will need are l R is a commutative ordered eld 2 R has the intermediate value property for polynomials ie for any poly nomial px if x lt y px lt py then 3295 lt 2 lt y pz 0 An ordered eld with these properties is called a real closed ordered eld any real closed ordered eld will also admit quanti er elimination To prove the theorem we will study a collection of functions which preserve quanti erfree formulas in an appropriate sense De nition 39 A hary relation A Q RlC is e ective if it is de nable over R by a quanti erfree formula Thus a relation is effective if it is a Boolean combination of sets which are de ned by polynomial equalities and inequalities Note that relations 95 y can be expressed as x gt y n x lt y so we only need to consider Boolean combinations of inequalities De nition 310 A hary partial function f D A R with domf D Q RlC is e ective i l D is an effective set CHAPTER 3 DECIDABILITY OF THE REAL NUMBERS 52 2 For every effective relation Ay 21 2 the relation B given by Bx1 axkazla azn EAfx1 axkazla azn is effective Note 311 For the relation B above to be true we require that 1 xk E dornf Example 312 It can be shown that the function is effective First the domain is effective since it is just the effective set go E R so 2 0 The second property is established by substituting f into all effective relations for instance the relation gt 3 is equivalent to so gt 9 Lemma 313 The functions 96 y x y 7x and ocy are all e ectioe Proof The rst three are immediate since these functions are all part of our language For the fourth note that the domain is xy y y 0 which is easily effective Let Az 117 be an effective predicate we must show that Boc y 23 Aocy13 is effective We know A is a Boolean combination of relations of the form a zna12a0gt0 where each 11 is a polynomial in 13 Then B is a Boolean combination of relations ofthe form n so so Mi a1lt7gtaogto y 3 When n is even this is equivalent to the formula 2 0 A aux awn 1y moi 1 aoyn gt 0 The case when n is odd can be handled in cases or by viewing the polynomial as of degree n 1 with leading coefficient 0 1 Lemma 314 The composition of e ectioe functions is e ectioe Proof We prove this for the case ghx where g and h are effective Let D9 and D be the domains of 9 an 1 by assumption these are effective Then the domain of f Df satis es 1396 E DWU ADAMID Since 1 is effective we have that Dghoc is effective so Df is effective Now suppose that Ay 239 is an effective relation Then Afx5 E A9hx 3 and we know Agy 2739 is effective since 9 is effective and thus Aghx 2739 is effective since 1 is effective 1 CHAPTER 3 DECIDABILITY OF THE REAL NUMBERS 53 Corollary 315 Any rational function is e ectioe Lemma 316 The function sgnx is e ectioe where 1 ifxgt0 sgn9c 0 ifx0 71 ifxlt0 Proof Let Ay 2739 be an effective relation Then Asgnx 239 is equivalent to x gt 0AA12quotx 0A0SVxlt 0AA7127 which is effective so we are done 1 Lemma 317 Let be afunction which takes on only nitely many values all of which are integer Then f is e ectioe and only if for each j E Z the relation 135 E j is e ectioe Proof If f is effective then we can simply substitute f into the effective pred icate y j to see that j is effective For the converse let j1 jn be the values Then the domain D is effective since D55 is equivalent to M 11Vvfij Let Ay 27 be an effective predicate Then Afx 2739 is equivalent to f0 11 A 1401 5 V 39 39 39 V f0 in A 1407 5 which is effective 1 Lemma 318 De nition by Cases Let f1i39 and 132 be e ectioe func tions and let 135 be an e ectioe relation Then the function f is e ectioe where f 1W mm m 122 acme Proof The domain D of f is effective since it is equivalent to 1315 A 35 V D20 A lm where D1 and D2 are the domains of f1 and f2 Let Ay be an effective relation Then the relation 39239 539 E Af55 27 is equivalent to 135 A Af15m5 V 435 A 14035 5 which is effective since both f1 and f2 are 1 This can easily be extended to more than two cases CHAPTER 3 DECIDABILITY OF THE REAL NUMBERS 54 Lemma 319 A function is e ectiue and only iffor every integer d 2 1 and every polynomial qy adyd ay a0 of degree d the function sgnqf55 is an e ectiue function off and a0 ad Proof If f is effective then domsgnqf domf restricted to 9 the al s do not affect convergence and hence is effective We consider for example the effective predicate Ay E y gt 0 Then ASgnqff E Sgn9f9 gt 0 E 110 gt 0 E BOW where B is the effective predicate qy gt 0 and hence is effective since f is For the converse suppose that Ay 239 is effective we must show that the predicate Af55 239 is effective We can view A as a Boolean combination of predicates of the form py5 gt 0 for polynomials py 239 with integer coeffi cients It will thus suffice to show that each of the predicates pf55 27 gt 0 is effective We can consider py 2739 as a polynomial qy whose coefficients are in 2 ie polynomials in 239 with integer coefficients Then 1005 gt 0 E Sgn4ff E1 Since is effective as a function of a and the coefficients of 11 by assumption hence since we are composing this with the polynomials determin ing the coefficients which are effective functions sgnqfi39 is an effective function of a and 27 and we are done 1 The next lemma says that we can effectively nd roots of polynomials Lemma 320 Main Lemma Letpx anx alx a0 E RM be a polynomial Then there are n1 e ectiue functions Md and 515 3J5 of the coe icients such that k Md is the number of roots of pac and the roots are enumerated in increasing order by 516 lt lt 5413 Example 321 This is essentially a generalization of the quadratic formula For n 2 the function Md is de ned by cases depending on sgna1 E 4a0a2 and the roots are again de ned by cases using the quadratic formula Note that we do not care about the values of 1 for i gt k we could if we like specify that these be unde ned Proof This is proved by induction on n where the base case of n 1 is clear Let px be of degree at most n Then the derivative px nanocn 1 2a2x a1 is of degree at most n E 1 so by assumption there are effective functions in t1 tn1 of the coefficients 139 such that the roots of p are t1d lt lt tma39 The function is monotone on each of the intervals 00 t1 t1 t2 tmEla tin tin 00 CHAPTER 3 DECIDABILITY OF THE REAL NUMBERS 55 so each of these intervals contains at most one root of px and there may also be roots at the MS The number of roots of px is thus determined by the values of sgnptl for 1325 m and sgnpt1 71 and sgnptm 1 so we can use de nition by cases to de ne M11 as an effective function of 1quot To show that the fl s are effective note that we can use de nition by cases to determine which interval or endpoint each 1 should lie in so we just consider for example a root 5 55 in the interval t1 t2 where we assume pt1 gt 0 and pt2 lt 0 By the previous lemma it suf ces to show that for each d 2 1 and polynomial 1195 of degree d the function sgnq is effective as a function of 139 and the coefficients of 11 First we can assume that the degree of 1195 is less than n To see this note that by polynomial division we have l196 px ffx WU where the degree of rx is less than n and the coefficients of r are easily seen to be effective functions of the coef cients of p and 11 Since 5 is a root of p 115 re so sgnltqlt gtgt sgnwa hence we may replace q by n By the induction hypothesis we can thus nd the roots of 1195 effectively let these be ul lt lt um Then sgnqx on each of the intervals imaul 1u2 mila um um 00 is determined by the m 1 effective functions sgnqu171sgn lt1 Hisgn lt1 sgnqum1 and the position off relative to the ul s is determined by the positions of the t1 relative to the ul s and the effective functions We can thus use de nition by cases to show that sgnq is an effective function hence f is an effective function completing the lemma 1 Lemma 322 If the predicate Ax1 x2 i i ask is e ective then so is the pred icate Bx2 i i me E 3x1Ax1 x2 i i 95k Proof We may view A as a Boolean combination of inequalities of the form plx1 gt 0 where the coef cients of the pl s are polynomials in 952 i i i 951C with integer coef cients By the Main Lemma the roots of the pl s are thus effective functions of 952 i i xk Let 51 fm be the roots of all of the pl s To see if there is an 951 which satis es the required inequalities it thus suf ces to consider the values at the fl s and at arbitrary points in the intervals they determine Hence the predicate 396114961 962 a 96k is equivalent to a nite disjunction of the form Amx2uixkVAnjx2iuxk CHAPTER 3 DECIDABILITY OF THE REAL NUMBERS 56 where m nj enumerate all the values 1 Lg l and 1 i 1 Since the m s are effective functions of 952 xk it follows that this disjunction is an effective 11 predicate and so B is an effective predicate as desire Theorem 323 Any predicate A Q RlC which is de nable over R is e ective Proof This amounts to showing that any formula of LOR is equivalent to a quanti erfree formula This is proved by induction on the construction of formulas Clearly every atomic formula is quanti erfree lfF E F and 0 E 0 where F and 0 are quanti erfree then F E F F 0 E F 0 and F 0 E F 0 For a formula of the form 395095 y39 where 0 is equivalent to the quanti er free formula 0 we have that 0 de nes an effective predicate Bx The above lemma tells us that the predicate E 395395 is effective and hence is de ned by a quanti erfree formula We thus have that 395095 E H Finally the formula Vac0x is equivalent to dac 0x 3 so we are done 1 Corollary 324 For a predicate A Q RIC the following are equivalent 1 A is e ective 2 A is de nable over R 5 A is de nable over R by a quanti erfree formula The same is true for functions f d A R with D Q RIC Proof This is immediate for predicates from the previous theorem Note that if a function f is effective then the predicate y is effective so de nable by a quanti erfree formula and hence f is de nable by a quanti erfree formula If f is de nable then for any effective predicate Ay 2739 the predicate Af55 239 is equivalent to the de nable predicate 3yy Ay which is thus effective hence f is an effective predicate 11 Restating this we have the main result of this section Theorem 325 Quanti er Elimination If a predicate A Q RlC is de nable over R then it is de nable overR by a quanti erfree formula hence any LOR formula is equivalent to a quanti erfree formu a 32 Decidability of the Real Numbers We use the above results to show that the theory of the real numbers is decidable Theorem 326 There is an algorithm which when given aformula F of LOR produces an equivalent quanti erfree formula F CHAPTER 3 DECIDABILITY OF THE REAL NUMBERS 57 Note 327 What we mean is that there is a recursive function which takes the Godel number of F and outputs the Godel number of Fquot Proof The algorithm can be considering the proof of the Quanti er Elimina tion Theorem and noting that all of the steps are effective 1 Theorem 328 There is an algorithm to determine whether or not a given sentence S of g is true in R ie t e set TruthR FS l S is a true sentence in LOR is recursive Proof In particular the above theorem tells us that given a sentence S we can effectively nd a quanti erfree sentence Squot which is equivalent to S and hence has the same truth value But a quanti erfree sentence is just a Boolean combination of atomic formulas of the form t1 t2 or t1 lt t2 where t1 and t2 are variablefree terms ie ones formed from 0 and 1 using and The truth values of such sentences are easily determined so we done 1 Corollary 329 The theory of the ordered ring of real numbers is decidable Corollary 330 Euclidean Geometry is decidable Proof We using Cartesian analytic geometry we can reduce questions of geom etry to systems of equations in the real numbers and thus interpret Euclidean Geometry in the theory of the real numbers 1 Part II Set Theory Chapter 4 Informal Set Theory In this chapter we present an informal survey of set theory We leave sev eral fundamental concepts unde ned at this point notably the de nitions of sets cardinals and ordinals We present enough of their properties in order to develop the basic theory In the next chapter we will present an axiomatic framework for set theory and give precise de nitions to these concepts 41 Set Operations By a set we mean some collection of objects we will not specify at this point what sort of objects these are We will generally use capital letters X Y etc to denote sets The fundamental relation for sets is the membership relation If a is an object and X is a set we write a E X to indicate that a is a member of X or a is an element of X We view sets as entirely determined by their elements with no additional structure This is known as extensionality Formally for two sets X and Y we ave XYltgtVaa Xltgta Y This should be contrasted with an intensionalview of sets where sets are dis tinguished based on properties that de ne them For instance to use a clas sical example the set of human beings and the set of featherless bipeds are intensionally different since the properties de ning them are different but are extensionally equal since they each have the same members as far as we know We will take extensionality as the de nition of equality between sets We will often use properties to de ne sets If R is some relation on objects we write a Ra to denote the set of objects which satisfy the property R e will see below that we will have to be somewhat more careful in de ning sets this way We will see that some collections of objects are too big77 to be sets so we will later have to specify more carefully exactly which collections of objects are allowed to be sets CHAPTER 4 INFORMAL SET THEORY 60 We will usually avoid this problem by choosing objects from some given set We say that a set Y is a subset of a set X Y Q X if every element of Y is an element of X Formally Y Q X if and only if VaaEY aEX If X is a set and R is a relation we write a E X Ra to denote the set of elements of X which satisfy the property R this is a subset of X We can View sets as objects in their own right and hence allow sets to be elements of other sets An important case of this is the following De nition 41 If X is a set then the power set of X 77X is the set con sisting of all subsets of X ie 77 Y Y Q X Note that the empty set ll and the set X itself are both subsets of X so that ll E 77X and X E 77X Note that if X is a nite set with n elements then 77X has 2 elements since for a given subset each of the n elements can either be an element of the subset or not Also note that there is a distinction between a set X and the set X which has one element the set X We will now present an example showing that not every collection of objects can be considered as a set Theorem 42 Russell s Paradox The collection of all sets is not a set Proof Suppose that the collection S of all sets were itself a set We could then de ne the set D of all sets which are not members of themselves ie DXESX X But now since D E S we have that D E D if and only ifD E D a contradiction Hence S could not have been a set 1 We can view this as saying that some collections of objects are too large to be sets We can also view it as saying that the collection of objects satisfying a given property is not always a set that we should limit ourselves to those objects in some starting set We know de ne some of the standard operations on sets De nition 43 Let X and Y be sets 1 We de ne the union intersection and di erence of X and Y as follows XUYaaEXaEY X YaaEXaEY XYaaEXa Y CHAPTER 4 INFORMAL SET THEORY 61 m l Given two objects a and b there is an object a b called the ordered pair of a and b with the following property al In a2 b2 42gt a1 a2 b1 b2 9quot We de ne the Cartesian product X X Y to be the set XXYabaEXbEYl u l A function f Y A X is a function whose domain is Y and whose range is a subset of Xi We write XY to denote the set of functions from Y to X ilel XYf fYgtXl We call this the exponential of X and Yl We can identify a function f Y A X with the set y E Y Fquot lff is a function and Z is a set we de ne the restriction off to Z f I Z to be the unique function whose domain is domf 0 Z which agrees with f on its domain We write for the range of f I Z ilel fa a E domf Z O l An indexed collection of sets with index set I is a function f whose domain is the set I and such that is a set for each i E It We denote such a collection as Xz i E I to mean X for eachi E It Given an indexed collection we de ne the union intersection and product of the collection as follows UXa3iEIa Xz LEI XaViEIa Xz LEI HXltaiEIgtViEIaEXl LEI Thus the product is the set of all functions whose domain is I and such that E X for all I E It Note that if we take X1 X for alli E I then Hie X1 XI the exponential of X and It An important property of products of indexed collections is the following De nition 44 The Axiom of Choice is the assertion that if Xz i E I is an indexed collection of sets such that X y ll for all i E I then the product is nonempty Hie Xl at Ill CHAPTER 4 INFORMAL SET THEORY 62 A function f E Hie X1 is called a choice function for the collection The Axiom of Choice says that it is possible to nd a choice function for any collec tion ie we can choose an element from each set in the collection Although this seems intuitively obvious the Axiom of Choice has some surprising conse quences which we will consider in the next chapter This axiom turns out to be independent of the other axioms of set theory we will present it is neither provable nor refutable from them and we will generally indicate when a proof requires its use 42 Cardinal Numbers One of the key properties of sets which we will consider is their size De nition 45 Two sets X and Y are said to be equinumerous X R Y if there is a bijection between them ie a onetoone and onto function f X A Y Lemma 46 The relation m is an equivalence relation ie 1 X m X 2 XRY ifand onlyimeX 5 XRY andeZimpliesXmZ Proof This is straightforward 1 We can thus associate to each set X an object cardX called the cardinality or the cardinal number of X We will not specify precisely what these objects are yet The only property we will need now is the following X R Y if and only if cardX cardY De nition 47 We say that It is a cardinal or cardinal number if there is some set X such that It cardX In the case of a nite set X we could take the cardinality of X to be the natural number n where X has n elements The case of in nite sets will require more subtlety as well as a precise notion of set and will be de ned in the next chapter De nition 48 For sets X and Y we write X lt Y if there is a subset Y1 Q Y such that X m Y1 Note that X lt Y if and only if there is an injective function f X A Y Lemma 49 The relation lt has the following properties 1 IfX RX andY mY thenX lt Y ifand only ifX lt Y 2 X lt X for each set X CHAPTER 4 INFORMAL SET THEORY 63 5 IfXltYandYltZthenXltZ 4 IfXltY andYltX thenXmY 5 For any two setsX and Y eitherX lt Y orY lt X or both Proof The rst three parts are straightforward The fourth part is known as the ShroderBernstein Theorem we will prove it and the fth part later using a consequence of the Axiom of Choice known as the WellOrdering Theorem 1 This allows us to de ne an ordering on cardinals De nition 410 For cardinals N and A we say Ki 3 A if X lt Y where X and Y are any sets with N cardX and A cardY Corollary 411 The relation 3 0n cardinals is a linear ordering We can extend the usual arithmetic operations to the class of cardinal num bers De nition 412 Cardinal Arithmetic Let a cardX and A cardY be cardinals with X 0 Y ll We de ne l N A cardXU Y 2 H A cardX X Y 3 Kl card XY Theorem 413 Let N A and a be cardinals Then N N A A N 2 HAMNAM 5 H A A N 4 N39A39 39 AM 5 H AnHAIltln 6 VHFquot Kl a 7 a 0 8 HOIltl KlO0 Hlrltl etc Proof This is straightforward several parts are given as exercises 1 Note 414 We will see later that addition and multiplication of in nite cardi nals is trivial namely Kl Kl maxltl A Cardinal exponentiation will be nontrivial though we will see that several properties of cardinal exponentiation are independent of the standard axioms of set theory CHAPTER 4 INFORMAL SET THEORY 64 Example 415 If It cardX then 2 card77X since each subset of X corresponds to its characteristic function a function from X to the 2elernent set 0 1 Theorem 416 Cantor s Theorem For any cardinal a we have a lt 2 ie for any set X we have X lt 77X but 77X 7g X Proof We see that X lt 77X using the function f X A 77X with fa a for each a E X Suppose now that 77X lt X and let 9177X A X be an injective function De ne the set D by D a E X211 E rang a E g 1a Then D Q X so D E 73X But now we have gD E rang so gD E D if and only gD E g 1gD D a contradiction 1 De nition 417 For an indexed collection M i E I of cardinals we de ne the sum and product of the collection as Z m card X LEI H m card X1 lg lg where m cardXl for eachi E I and the sets X are pairwise disjoint 43 Ordinal Numbers De nition 418 A relational structure is a pair A R where A is a set and R Q A X A is a binary relation on A We often write 11 instead of a b E R or Ra b De nition 419 Let A R and 35 be relational structures An isomor phism between A R and 35 is a bijection f A A B such that for all 11112 E A we have alRaQ if and only if fa1Sfa2 We say that A R and 35 are isomorphic A R E 35 if there is an isomorphism between them Lemma 420 The isomorphism relation E is an equivalence relation on the class of relational structures Proof This is straightforward 1 We can thus associate to each relational structure A R an object typeA R called the isomorphism type of the structure Again we defer de ning these objects explicitly the key property is that we should have A R E B S if and only if typeA R typeB S for relational structures A R and B S CHAPTER 4 INFORMAL SET THEORY 65 De nition 421 A relational structure A R is said to be wellfounded if every nonempty subset X Q A has an Rminimal element ie if ll at X Q A then there is an a E X for which there is no I E X with bRa Example 422 The structure N lt is wellfounded since every nonempty subset has a least element The structure Z lt is not wellfounded since if we take X Z every element a E Z has some I E Z with b lt a Lemma 423 A relational structure A R is wellfounded if and only there is no in nite descending Rchain ie an in nite sequence an n E such that a 1Ran for all n E N Proof If an n E N is an in nite descending Rchain then the set X an n E N has no Rminimal element so A R is not wellfounded Conversely if A R is not wellfounded let X Q A be a nonempty et with no Rminimal element ie Va E de E XbRa We can then take a0 to be any element of X a1 to be some element with alRao a to be some element with a Ral etc to form an in nite descending Rchain Formally we use the Axiom of Choice to de ne this sequence as follows For each a E X de ne the nonempty set Xa b E X bRa the axiom of Choice then tells us that there is a function f with domain X such that fa E Xa for all a E X We then choose a0 E X arbitrarily and let an1 fan for all n e N 1 De nition 424 A linear ordering is a relational structure A R with the following properties 1 If aRb and bRc then aRc 2 For any ab E A exactly one of the following holds aRb a b or bRa This is sometimes called a strict linear ordering A wellordering is a linear ordering which is wellfounde Note 425 If A R is a wellordering and X is a nonempty subset of A then X in fact has an Rleast element ie a unique a E X such that aRb for all I E X with b y a De nition 426 We say that oz is an ordinal or ordinal number if we have oz typeA R for some wellordering A R We generally write otA R ordertype instead of typeA B when A R is a wellordering Note that for each nite set A with n elements there is exactly one isomor phism type of wellorderings on A namely the ordertype of the usual ordering lt on the set 01n E 1 We thus let n denote the ordertype of this ordering De nition 427 We let u otN lt be the ordertype of the usual ordering on the natural numbers CHAPTER 4 INFORMAL SET THEORY 66 De nition 428 Ordinal Arithmetic Let a and be ordinals with a otA R and otB S where A O B ll We de ne 1 a otAUBRUSUAgtlt B 2 01 otA gtlt Ba1b1 12 b2 1st b1 b2 AalRa2 3 03 otC T where C is the set of all functions f B A A which have nite support ie for all but nitely many I E B we have 10 where 10 is the Rleast element of A and T is the ordering on C given by fleQ if and only if f1bRf2b where b is the Sgreatest b E B such that f1b y f2b we can nd a greatest such I because f1 and f2 have nite support Note that the ordering of oz looks like a copy of oz followed by a copy of and the ordering of 01 looks like many copies of oz ie a number of orderings of ordertype oz themselves ordered with ordertype This ordering is called the antilexicographical ordering on A X B Note that for exponentiation the ordering 2 agrees with the de nition of oz oz We should check that these are all wellorderings We check that the ordering of oz is wellfounded leaving the rest as exercises Let X Q A X B be non empty De ne the set X13 as XBb B3a Aab X Then X3 is a nonempty subset of B so it has an Sleast element b0 De ne the set XA as XA a Aab0 EX This is a nonempty subset of A and so has an Rleast element 10 Then the pair 10 be is an element of X which is least in the ordering of A X B Note 429 Unlike cardinal arithmetic ordinal addition and multiplication are not commutative For instance we have that the ordinal 1w 0 whereas the ordinal w 1 y 40 since 40 1 has a greatest element whereas 40 does not Hence 1 w y w 1 Similarly 2 w 40 since this consists of wmany copies of the 2element wellorder whereas the ordinal w 2 40 40 y 40 since 40 40 contains elements with in nitely many predecessors and 40 does not Hence 2 w y w 2 Theorem 430 Let 1 and39y be ordinals Then 1 a va v 239 a va v 339 a va av 4 a va 0 5 at a p CHAPTER 4 INFORMAL SET THEORY 67 6 a00aaa00a0 allaa 7 101 andOO 0fo39roz3 0 1101 lo l Proof This is straightforward and left as an exercise 1 De nition 431 Let A R be a linear orderingl An initial segment of A R is a subset of A of the form I bRa for some element a E A Note that the restriction of R to an initial segment is a linear ordering and if A R is a wellordering then the restriction of R to an initial segment is a wellordering We generally identify an initial segment with this restriction of Rt Theorem 432 Comparability of WellOrderings Let A R and B S be wellorderings Then exactly one of the following holds 1 A R E BS 2 A R some initial segment of B S 5 B S E some initial segment of A R In each case the isomorphism is unique Proof First we show that an isomorphism is unique if it exists Suppose that f1 and f2 are two di erent isomorphisms from A R to B S or some initial segmentl Then the set a E 1411501 1501 is a nonempty subset of A so let a0 be the Rleast elementl Thus f1a0 y f2a0 but f1a f1a for all a E A with aRaOl Since f1a0 y f2a0 we have either f1a0Sf2a0 or f2a0Sf1a0 assume the formerl We must then have f1a0 E ranf2 since any element mapping to it would have to be Rless than aol This contradicts that the range of f2 is either all of B or an initial segment so there could not have been two distinct isomorphisms De ne a partial function f with domf Q A be setting fa the unique I E B such that a aRa R l a aRa E b bSbS l b bSb if such a b exists It is clear that domf is either all of A R or an initial segment of A R and that ranf is either all of B S or an initial segment of B S it will suf ce to check that we can not have both of them being proper initial segments Suppose this were the case and let a0 be the Rleast element of A domf and let be be the S least element of B ranfl Then we have a aRao R l a aRa0 E b bSbo S l b bSb0 as witnessed by f so we would have de ned fa0 b0 contradicting that 1 a0 E domfl CHAPTER 4 INFORMAL SET THEORY 68 The above theorem allows us to de ne an ordering on the class of ordinal num bers De nition 433 For ordinals oz and we set oz lt if oz otA R and otB S where A R is isomorphic to an initial segment of B S We setag ifalt ora Corollary 434 For any ordinals oz and exactly one of the following holds alt a or lta Also ifozlt and ltv thenozlt39y Note 435 Thus the ordering lt on the collection of ordinals behaves like a linear ordering We do not call it a linear ordering though since our de nition of a linear ordering requires the relation to be de ned on a set and we will see that the collection of ordinals is too large to be a set Lemma 436 If AR is a wellordering and B Q A then the relational structure E R0 B X B is a wellordering and otB R B X B S otA R Proof This follows immediately from the comparability of wellorderings 1 De nition 437 We let Ord denote the class of all ordinals Lemma 438 For any ordinal oz the relational structure we 0rd2 lt a vlt lta is a wellordering of ordertype oz Proof Let A R be a wellordering of ordertype 1 De ne f A A lt a by fb otc E A cRbR l c E A cRb It is straightforward to verify that f is an isomorphism so that lt a is a wellordering of ordertype a 1 Thus any wellordering is isomorphic to some initial segment of the ordinals with the relation lt Lemma 439 Let X be a set of ordinals Then there is an ordinal y denoted sup X which is the least upper bound ofX under lt ie oz 3 y for all oz E X and lt y then there is an oz E X with lt oz Proof Let A a H E X lt 1 Then A lt is a wellordering Let y otA lt it is straightforward to verify that A a oz lt y and that y sup X 1 Lemma 440 If X is a nonempty set of ordinals then X has a least element under lt CHAPTER 4 INFORMAL SET THEORY 69 Proof Let oz sup X then X is a nonempty subset of lt 1 Since this set is wellordered under lt X has a least element under lt 1 Note 441 Thus lt behaves like a wellordering on the class of ordinals Theorem 442 Burali Forti Paradox The class 0rd of all ordinals is not a set Proof If 0rd were a set then we would have that the relational structure 0rd lt was a wellordering Hence we could let oz otOrd lt and we would have that 0rdlt ltaltr lta so that 0rd lt would be isomorphic to a proper initial segment of itself con tradicting the uniqueness part of the comparability of wellorderings 1 De nition 443 Let oz be an ordinal We say that oz is a successor ordinal if there is an ordinal such that oz 1 We say that oz is a limit ordinal if we have 1ltaforall with ltw It is straightforward to check that for each ordinal oz exactly one of the following is true oz 0 oz is a successor ordinal or oz is a limit ordinal The ordinal w is a limit ordinal whereas 1 1 is a successor ordinal De nition 444 If C is a collection of objects not necessarily a set then a de nable function with domain C is a suitably de nable rule F which associates to each element a of C a unique object Fa We will not specify precisely what we mean by de nable here Examples of such functions which we will study include functions de ned on the collection of all ordinals The following theorem gives us a useful method for de ning such functions Theorem 445 Tran nite Recursion Let f be the class of all functions whose domain is an initial segment of the ordinals Let G be a function with domain 7 Then there is a unique function F whose domain is 0rd such that for all oz E 0rd 1 aw r 3 lt a Proof Say that a function f E f is good if for all E domf we have Cf l y y lt We rst claim that for each ordinal oz there is at most one good f with domf lt a If f1 y f2 were two good such functions then let y be the least such that f139y y f2 We would thus have f1l ltvf2l ltvaso f1v Gf1l r lt n Gf2 H lt n f2v contradicting our choice of y CHAPTER 4 INFORMAL SET THEORY 70 Thus for each ordinal oz let fa be the unique good f with domf lt a if such exists We claim that fa exists for each a If not let oz be the least such that fa does not exist Then fg exists for all lt oz so the function 9fo 1 lt a is good contradicting the choice of 1 Hence if we set Fa Cfa for each oz this will satisfy the conclusion of the theorem 1 Note 446 We can think of F f lt a as the sequence of values lt a trans nite recursion is then analogous to courseofvalues recursion ie G speci es a way of de ning Fa in terms of ltprevious values of It is often convenient to think of trans nite recursion via cases To de ne a function F on the ordinals we must specify F0 de ne Fa 1 in terms of Fa for successor ordinals and de ne Fa in terms of lt a for a limit ordinal a We have the related induction principle Theorem 447 Trans nite Induction Let P be a relation on ordinals which satis es the following condition 0 Whenever is true for all ordinals lt a then Pa is true as well Then the relation Pa is true for each ordinal oz Again this can be expressed in terms of the three cases 0 successor ordinal limit ordinal Example 448 We could have used trans nite recursion to de ne ordinal arith metic For instance ordinal addition can be de ned by trans nite recursion on the second coordinate as follows a0a a 1a 1 a6supa lt6 foralimit ordinal6 We could use trans nite induction to check that this de nition agrees with the one given previously for all ordinals oz and 44 Initial Ordinals and Cardinals We will use the above properties of the ordinals to give a more precise de nition of cardinal numbers Recall the Axiom of Choice introduced earlier and the notion of a choice function for an indexed collection of sets We shall now introduce the notion of a choice function for a single set We shall generally indicate which proofs require the Axiom of Choice as this axiom is independent of the other axioms of set theory we will present in the next chapter CHAPTER 4 INFORMAL SET THEORY 71 Lemma 449 AC For each set X there is a choice function for X ie a function c277XQlgtX such that CY E Y for each nonempty subset Y of X Proof Let I 77X and let X i for all i E I The Axiom of Choice says that the product Hie X1 is nonempty so there is a function c with domc I and C0 E for all i E I ie c 77X A X is such thatcYEonrll3 Y X 1 Theorem 450 WellOrdering Theorem AC For each setX there is a relation R Q X X X such that the relational structure X R is a wellordering Note 451 Neither the relation nor even its ordertype is unique For instance let X N be the set of natural numbers Then both the relations R1 and R2 are wellorderings of X where R1nmEN2nltm R2nmEN220ltnltmUn00ltn The structure N R1 is the usual ordering of the natural numbers and has ordertype w whereas the structure N R2 has ordertype w 1 with 0 being the RQgreatest element We have seen that w y w 1 ie N R1 N R2 Proof It will suffice to prove the following For any set X there is an ordinal oz such that X m lt a The wellordering of the second set can thus be transferred to X Fix a choice function c for X and x an object a0 E X We de ne a function F on the ordinals by trans nite recursion PW CXF lt an ifXF lta 0 a0 otherwise We claim rst that there is an ordinal oz with Fa a0 If not we have Fa E X for all ordinals oz so by the construction of F we have Fa y for oz y Hence F is injective so if we de ne the set Y as YranFaEX3aFoza then F has an inverse function F 1 de ned on Y which has ranF 1 0rd so 0rd would be a set since the range of a function applied to a set is a set This contradicts the BuraliForti Paradox So let oz be the least ordinal such that Fa a0 and note that a0 whenever oz 3 We then have that F l lt a is onetoone and onto Xsince we must have lt a ll Thus lt a RX as El desire CHAPTER 4 INFORMAL SET THEORY 72 Note 452 The above theorem shows that we can prove the WellOrdering Theorem using the Axiom of Choice The converse is true We can prove the Axiom of Choice using the WellOrdering Theorem The idea is that if we have a wellordering of a set we can de ne a choice function by always choosing the least element under the wellordering There are other theorems equivalent to the Axiom of Choice the most commonly used being Zorn s Lemma We shall discuss the Axiom of Choice in greater detail later Since there are many possible wellorderings we can place on a given set we would like to choose one in a more de nitive fashion We can at least specify the ordertype canonically De nition 453 We say that an ordinal oz is an initial ordinal if for all lt oz ave vrvlta9 vrvlt Every nite ordinal is an initial ordinal So is the ordinal w since any ordinal less than w must be some nite n and vrvltna vivltw since the rst set is nite whereas the second is in nite The ordinal w 1 is not an initial ordinal since y yltwmry yltw1 De nition 454 For any set X let le be the least ordinal oz such that X m lt a We know such an oz exists by the WellOrdering Theorem Note that le is an initial ordinal Lemma 455 IfX Q a then le S a Proof This is immediate from Lemma 436 1 Theorem 456 Let X and Y be sets Then 1 X RY if and only 2 X lt Y if and only S Proof This is straightforward using the previous lemma 1 Hence we have cardX cardY if and only if le We can thus use this as our de nition of cardinality still leaving the de nition of ordinals for later De nition 457 For a set X we let cardX We can now complete the proof of a theorem stated earlier CHAPTER 4 INFORMAL SET THEORY 73 Theorem 458 Let X and Y be sets Then 1 Either X lt Y orY lt X or both 2 IfXltY andYltX thenXmY Proof This follows from the previous theorem using the comparability of well orderings 1 We can now prove some results about cardinal arithmetic To start we see that addition and multiplication of in nite cardinals is trivial Theorem 459 If Kl is an in nite cardinal then H Kl Kl Proof Suppose not and let Kl be the least cardinal for which this fails Thus Kl is an in nite initial ordinal and A A lt Kl for all cardinals A lt Kl We will show that this implies that Kl Kl Kl Let A a E 0rd oz lt Kl and let R ltl A so that A R is a well ordering of ordertype Kl Hence lAl Kl but every initial segment I of A R has lIl lt Kl Let B A X A and de ne a relation S on B X B by 0151S012a 52 13 HMO151 lt 11133012 52 V HMO151 11133012 52 A011 lt 012 V 111334011 51 11133012 52 01 02 51 lt 52 It is straightforward to check that S is a wellordering of B Note that if J is an initial segment of B S then we must have Q I X I or some initial segment I of A R Since then lIl lt Kl we must have M lt Kl by our assumption This says that A R can not be isomorphic to any initial segment of B S We also immediately have that B S can not be isomorphic to any initial segment of A B so by the comparability of wellorderings we have A R E B S in particular A m B A X A so Kl Kl Kl as desired 1 Theorem 460 If Kl and A are in nite cardinals then HAIltlAmaxrltlA Proof Let n maxaA Then MSHA MM2MSMMM and MSwA nMM Theorem 461 If A is an in nite cardinal and 2 S Ii 3 2 then Kl 2 Proof We have 2A 3 M g 2AA 2M 2A 1 CHAPTER 4 INFORMAL SET THEORY 74 We can use the ordinals to give an enumeration of the in nite cardinals De nition 462 Let be an ordinal We de ne to be the least initial ordinal Kl such that Kl gt Note that is a cardinal and if is itself a cardinal then is the least cardinal greater than we refer to it as the successor of in this case De nition 463 We de ne a sequence of ordinals cow for oz E 0rd by trans nite recursion we w wa1 w lt05 supwa oz lt 6 for limit ordinals 6 This sequence then enumerates all of the in nite initial ordinals is all of the in nite cardinals To avoid confusion we generally use the notation Na to refer to the cardinal ca Although cardinal addition and multiplication is simple cardinal exponen tiation turns out to e much more interesting An important problem is the Continuum Problem What is the cardinality of the set of real numbers R We have seen that llRl 2N0 and Cantor s Theorem tells us that 2N0 gt N0 is 2N0 2 N The Continuum Hypothesis CH is the statement that 2N0 N1 This statement turns out to neither be provable nor refutable using the stan dard axioms of mathematics and is said to be independent of these axioms Thus CH is consistent but it is also consistent that eg 2N0 N2 Besides Cantor s Theorem there is one additional requirement that 2N0 have uncount able co nality discussed below but these turn out to be the only restrictions on the possible size of the continuum Another formulation of CH is that every in nite subset of R either be countable or have the same cardinality as R More generally Cantor s Theorem again tells us that 2N 2 Na1 for each ordinal a The Generalized Continuum Hypothesis GCH is the statement that 2N girl for each ordinal a Equivalently GCH says that 2 HT for each in nite cardinal Kl This also turns out to be independent of the standard axioms of set theory We say that a cardinal Kl is uncountable if Kl gt No We consider several properties of uncountable cardinals De nition 464 Let A be an uncountable cardinal We say that A is a successor cardinal if A HT for some cardinal Kl This is equivalent to saying that A Na1 for some ordinal a We say that A is a limit cardinal if HT lt A for every cardinal Kl lt A This is equivalent to saying that A N5 for some limit ordinal 6 Hence every uncountable cardinal is either a successor cardinal or a limit cardinal but not both All of the cardinals N7 for n 2 1 are successor cardinals the rst limit cardinal is NW CHAPTER 4 INFORMAL SET THEORY 75 De nition 465 Let A be an uncountable cardinal We say that A is a strong limit cardinal if 2 lt A for each cardinal N lt A Note that every strong limit cardinal is a limit cardinal If the GCH is true then every limit cardinal is a strong limit cardinal but this need not be true in general De nition 466 let N be an in nite cardinal The co nality of N cofrltl is the least ordinal oz such that N EKG A for some indexed family of cardinals AliltagtwithAlltIltlforalliltoa Note that cofrltl S N is always an initial ordinal ie a cardinal De nition 467 We say that an in nite cardinal N is regular if cofrltl N If cofrltl lt N we say that N is singular For instance N0 is regular since it is not the sum of nitely many nite cardinals On the other hand NW is singular since NW 2 N7 so that cofNw N0 7LltW Theorem 468 Every in nite successor cardinal is regular Proof Let A Hl be an in nite successor cardinal Suppose that a cofA lt A so that A EA zltu withAlltAfor allilta ThenAlS Handngaso ZAlSZHHHHlt zlta iltn a contradiction 1 In particular each of the cardinals N7 for n 2 1 is regular We can naturally ask whether the converse of the above theorem is true ie whether every regular cardinal is a successor cardinal We have that No is a regular cardinal which is not a successor the real question is whether there are others De nition 469 We say that N is weakly inaccessible if N is an uncountable regular limit cardinal We say that N is inaccessible if N is a regular strong limit car ina Every inaccessible cardinal is weakly inaccessible and the GCH implies that every weakly inaccessible cardinal is inaccessible but this need not be true in general We will see that the existence of weakly inaccessible cardinals can not be proved from the standard axioms of set theory ie it is consistent that every uncountable regular cardinal is a successor cardinal CHAPTER 4 INFORMAL SET THEORY 76 45 Pure WellFounded Sets We will now re ne our notion of set so that the only objects we consider are sets ie we will consider only sets whose elements are all sets etc De nition 470 A set X is transitive if every element of X is a subset of X ie for each set Y with Y E X we have Y Q X Note that this is equivalent to saying that if Z E Y E X then Z E X ie the Erelation behaves transitively with respect to X Lemma 471 For each set X there is a smallest transitive set TCX with X Q TCX called the transitive closure of X Proof De ne UX U X UY Y E X is a set We then de ne TC0X X TCn1X UTCnX TCX U T0X nltw Clearly X Q TCX and TCX is transitive since if Y E TCX then Y E TCnX for some n so that Y Q TCW1X Q X It is easy to see that this is the smallest such set since a transitive set containing X must contain UX and so forth 1 ForasetXwe write Eleor xyxyEXacEy De nition 472 We say a set X is wellfounded if the relational structure TCX El TCX is wellfounded Thus X is wellfounded if and only if there is no in nite descending Echain X X0 3 X1 3 X2 3 Wellfounded sets are those which can be built from the bottom De nition 473 We say a set X is pure if every element of TCX is a set ie X is a set every element of X is a set every element of an element of X is a set and so forth De nition 474 For each ordinal oz de ne the set Ra by trans nite recursion as follows R0 Z Ra 77Ra R5 U Ra for limit ordinals 6 Oltlt5 By trans nite induction we see that each Ra is a transitive pure wellfounded set and that Rg E Ra for lt a CHAPTER 4 INFORMAL SET THEORY 77 Theorem 475 We have X E Uaeord Ra if and only if X is a pure well founded set Proof One direction is immediate from the above remarks noting that if X E Ra then TCX Q Ra For the other suppose that X is a pure wellfounded set We claim that for each Y E TCX there is an ordinal oz such that Y E Ra Suppose not and choose an Eminimal Y E TCX for which no such oz exists Thus for each Z E Y we can choose let be the least ordinal such that Z E R Let y supfZ Z E Y Then Y Q R7 so Y E 77R7 R71 a contradiction so the claim is true In particular since X E TCX we have that X E Ra for some oz as we wished 1 De nition 476 We let V be the class of all pure wellfounded sets ie V U Ra aEOrd V is referred to as the universe of pure wellfounded sets The set Ra is sometimes denoted Va De nition 477 le is a pure wellfounded set we let the Tank ofX rankX be the least ordinal oz such that X Q Ra Equivalently rankX suprankY1 Y E X Clearly rankRa oz and Ba X X is a pure wellfounded set with rankX lt a We shall restrict our attention to the universe of pure wellfounded sets so that the only objects we study will be sets As a result we will not have any of the naive objects of standard mathematics such as the natural numbers real numbers etc however we can represent all of the standard mathematical objects as sets and hence use these representations in our treatment of set theory In the rest of this section we will see how to represent several key types of objects as sets namely ordered pairs functions ordinal numbers cardinal numbers natural numbers real numbers De nition 478 ordered pair Let a b a 11 Thus for sets a and b we have a representation for the ordered pair a b We check that this satis es the key property of ordered pairs Lemma 479 We have 11 b1 11212 if and only a1 a2 and b1 b2 Proof For the nontrivial direction suppose 11 b1 122 If 11 b1 then 11 b1 has only one element since 11 b1 a1 and hence 12 b2 has only one element namely 11 so that a b2 a1 b1 and we are done If 11 y b1 then 11 and 12 are the unique singleton elements of 11 b1 and 11212 respectively so we need 11 12 We then have 11 b1 12 b2 from which 1 b2 1 CHAPTER 4 INFORMAL SET THEORY 78 De nition 480 function A function is a set f of ordered pairs which is singlevalued ie VowWWW y e f A x 2 e f e y z The domain off is domf x 33195 y E for x E domf we write for the unique y such that x y E We next introduce a representation of the ordinal numbers due to von Neu mann De nition 481 von Neumann ordinal A non Neumann ordinal is a transitive pure wellfounded set A such that the relational structure A El A is a wellordering Note that each initial segment of a von Neumann ordinal is a von Neumann ordinal The key property is the following Lemma 482 For each ordinal oz there is a unique uon Neumann ordinal A04 such that otAa El A04 oz Proof Using trans nite recursion we can de ne AaA lta It is straightforward to verify that each A04 is a von Neumann ordinal and that it is the unique one of order type oz using the fact that an initial segment of a von Neumann ordinal is a von Neumann ordinal 1 Note that rankAa oz Also note that Aa1 A04 U Ag We can compute the rst few von Neumann ordinals as follows A0 0 A1 QlUle 6 A2 U01 As 3 ill U W 0 3 0 3 0H AWAnnltw We will henceforth identity the ordinal oz with the von Neumann ordinal A04 Note that we then have oz lt a For any set of ordinals X we have supX U X Uaex oz For ordinals oz and we have oz lt if and only if aE andag ifandonlyifag As before we can identify cardinals with initial ordinals We can also identify each natural number n with the von Neumann ordinal n A7 so that N w We brie y sketch representations of Z Q and R There are many ways to do this For Z we can consider 0U X 0 l where the second coordinate CHAPTER 4 INFORMAL SET THEORY 79 determines whether we represent 71 or in For Q we can consider equivalence classes of pairs p q where pq E Z with q y 0 and we identify phql with pg 1 if L L For R we can use either Dedekind cuts or equivalence classes of Cauchy sequences of rationals where we identify two Cauchy sequences if they have the same lirniti Chapter 5 Axiomatic Set Theory We shall now present an axiomatic framework for set theory in an attempt to formalize the notion of a pure wellfounded set We will introduce a system of axioms asserting that certain sets exist and that sets have certain properties a collection satisfying these axioms can be viewed as an interpretation of the notion of a set 51 The Language of Set Theory De nition 51 The language of set theory LST or LE consists of two bi nary relations E and As with arithmetic we have variables x y 2 from which we form atomic formulas of the form x y and x E y We then form the collection of formulas using the connectives n V and 42gt and the quanti ers 3 and Note 52 We did not use the connectives and 42gt earlier we may view F G as equivalent to F G and F 42gt G as equivalent to F G G F The notions of free and bound variables and sentences are the same as before The intended interpretation is that variables range over the class of pure well founded sets and that the E relation represents membership We shall discuss below other interpretations or models of set theory Example 53 The principle of extensionality can be expressed by the following sentence of L VxVyx y 42gt Vuu E x ltgt u E The only nonlogical symbol of the language of set theory is the E relation however in this language we can de ne all of the other notions we have intro duced previously such as subset Q We will show how to express these in LST and shall use them as abbreviations below but the point is that everything we have discussed so far can be expressed in LST De nition 54 We introduce the following abbreviations 80 CHAPTER 5 AXIOMATIC SET THEORY 81 H unordered pair z xy77 is an abbreviation for VuuE2ltgtuxuy 2 singleton z x77 is an abbreviation for 2 x 3 ordered pair 2 x y77 is an abbreviation for 2 x 4 subset x Q 377 is an abbreviation for Vuu E x u E 5 power set 2 73x77 is an abbreviation for Vyy E 2 42gt y Q 6 union of a set of sets 2 U x77 is an abbreviation for VuuEzlt gt3vvExuEv 7 union of two sets 2 x U y77 is an abbreviation for 2 Ux 8 intersection of a set of sets 2 x77 is an abbreviation for VuuE zltgtVvv E x uE 9 intersection of two sets 2 x O y77 is an abbreviation for 2 x 10 empty set x Q is an abbreviation for Vuu E x where u E x abbreviates u E 52 The Axioms of Set Theory We now introduce a collection of axioms of set theory De nition 55 The Axiom of Extensionality is the sentence VxVyx y 42gt Vuu E x ltgt u E This expresses the principle that two sets are equal if and only if they have the same elements De nition 56 The following axioms assert the existence of some basic sets 1 Empty Set Axiom 3xx 2 Pairing Axiom VxVy32z x 3 Union Axiom Vx32z U 4 Power Set Axiom Vx32z CHAPTER 5 AXIOMATIC SET THEORY 82 De nition 57 The Axiom of Foundation is the sentence Vxx 3uu E xAu x The Axiom of Foundation expresses the idea that every set has an Eminimal element since u E x is such that u 0 x ll then there is no 1 E x With v E u Before presenting more axioms we introduce some additional abbreviations De nition 58 We have the following abbreviations 1 Cartesian product 2 x X y77 is an abbreviation for Viiw E 24gt3u3vu E xv E yw 2 function Functionf is an abbreviation for a formula Which says that f is a function ie WW E f E 39632100 zyWxV2Vzxy E foaz E f 2 Z 3 value of a function y f9c77 is an abbreviation for Functionf x y E 4 domain of a function 2 domf77 is an abbreviation for Functionf AVxx E 2 42gt 33195 y E o1 generalized Cartesian product 2 U f77 is an abbreviation for Functionf Vgg E 2 42gt domg domf WW E d0mf 906 E 1 We now continue With our list of axioms De nition 59 The Axiom of Choice AC is the sentence Vf ltFunctionf AVxx E domf y 3E 3 This just expresses in LST our earlier de nition that the product of a family of nonempty sets is nonempty De nition 510 The Axiom of In nity is the sentence 323 E 2 AVxx E 2 xU E The point of the Axiom of In nity is to ensure that there is at least one in nite set note that the set 2 here must have U Q 2 and so be in nite CHAPTER 5 AXIOMATIC SET THEORY 83 The rest of our axioms will fall into two schemes ie in nite collections of axioms The reason for this is that we will want axioms saying that certain things are true for all de nable properties since our language does not allow us to quantify over these properties we must introduce a separate axiom for each property De nition 511 If F is a formula with free variables on 9c7 then the universal closure of F is the sentence V951 Vac F De nition 512 For any formula Fu with free variable u we write 2 u E as Fu77 as an abbreviation for Vuu E 2 42gt u E as De nition 513 The Comprehension Scheme is the set of axioms consisting of the universal closure of each formula of the form 32Vuu E 2 42gt u E as where Fu is a formula in which 2 does not occur freely Note 514 Thus the comprehension scheme asserts that given a set as and a de nable relation we can form the subset of as consisting of those elements which satisfy the relation The requirement that 2 is not a free variable of F is necessary to prevent trivial contradictions such as the set 2 u E as u E Example 515 Together with the other axioms we have introduced the Com prehension Scheme can be used to show that the domain of a function exists since we have domf ac E f 33195 y E The Comprehension Scheme can be used to show that the collection of elements satisfying a given de nable property is a set provided that we have some starting set which we know contains all of the elements in this example the set U U De nition 516 We write 3195 to mean there exists a unique ac ie 3le95 is an abbreviation for 3xVyFy 42gt ac De nition 517 The Replacement Scheme is the set of axioms consisting of the universal closure of each formula of the form Vuu E as 3l UFu 2 3szv E y 42gt Hum E as Fu where Fu v is a formula in which y does not occur freely Note 518 The Replacement Scheme formalizes the notion that if we have any de nable procedure77 applied to a set then the range is a also a set If we have an actual function f ie a set of ordered pairs then the existence of the range of f follows from comprehension much as did the domain above the key point is that the de nable procedure here may have a domain which is too large to be a set as in the procedures we have used in de nitions by trans nite recursion on the ordinals Again the requirement that y not occur freely in Fuv is used to avoid trivial contradictions CHAPTER 5 AXIOMATIC SET THEORY 84 We now de ne the standard collection of axioms of set theory treating the Axiom of Choice separately De nition 519 ZermeloFraenkel Set Theory The axioms of Zermelo Fraenkel Set Theory ZF are the following 1 Axiom of Extensionality F Empty Set Axiom Pairing Axiom F95 Union Axiom 9quot Power Set Axiom o Foundation Axiom T1 Axiom of In nity 00 Comprehension Scheme 3 Replacement Scheme De nition 520 ZFC The axioms of ZermeloFraenkel Set Theory with Choice ZFC consist of the axioms of ZF together with the Axiom of Choice Note 521 The Empty Set Axiom is redundant given the Axiom of In nity and the Comprehension Scheme since given any set x the set 2 u E x u y u is the empty set All of the other axioms can be shown to be independent of one another ie none of the other axioms is a logical consequence of the others The axioms of ZFC are the commonly accepted settheoretic foundation of mathematics and are sufficient to prove all of the theorems of standard mathematics In particular all of the results presented in the previous chapter can be formalized and proved within ZFC Much of axiomatic set theory involves studying the logical consequences of this set of axioms 53 Models of Set Theory The intended interpretation of the language of set theory is the class of pure wellfounded sets however as this notion is necessarily somewhat vague we wish to consider other possible interpretations That is we consider various possible collections of sets and interpretations of the Erelation on these structures We recall the following de nition De nition 522 A relational structure is a pair A E where A is a set and E Q A X A is a binary relation on A CHAPTER 5 AXIOMATIC SET THEORY 85 Note 523 We have speci ed here that A is a set It will also make sense to consider relational structures where A is a de nable class we shall discuss this later De nition 524 Let A E be a relational structure and let F be a sentence of LST We say F is true in A E if F is true when we interpret variables as ranging over the elements of A and interpret ac E y77 as meaning xEy We also say A E models F A E l E Otherwise we say F is false in A 951 xn is a formula with free variables on x7 and a1 17 E A then we can similarly de ne the truth value of Fa1 an in A Example 525 We say a relational structure A E is extensional if the Axiom of Extensionality is true in A This is equivalent to the following condition If ab E A and a y b then c E A cEa y c E A ch For instance any linear ordering is extensional however the structure A 0 1 2 E 01 1 02 is not extensional because c E A cEl 0 c E A cE2 De nition 526 Let S be a set of sentences of LST A model of S is a relational structure A E such that each of the sentences of S is true in A We say that S is consistent if there is a model of S otherwise we say that S is inconsistent We say that a sentence F of LST is a logical consequence of S S b E if F is true in every model of S Note that if S is inconsistent then any sentence F is a logical consequence of S When S is consistent we may ask which sentences are logical consequences of S this is akin to asking which conclusions follow when we take S as a set of axioms For instance the sentence Vacx E ac is a logic consequence of the Pairing Axiom and the Axiom of Foundation since the Pairing Axiom tells us that the set exists and the Axiom of Foundation tells us that there is an element u E such that u ll we must have u ac so that 950 ll hence ac E ac An important type of model is one in which the relation E is the actual membership relation E De nition 527 An Emodel is a relational structure A E such that E 11 b E A X A a E b We write AElA in this case and identify the structure with the set A De nition 528 A model of ZF Tesp ZFC is a relational structure which satis es all of the axioms of ZF resp ZFC We say that a sentence F is a theorem of ZF Tesp ZFC if it is a logical consequence of ZF resp ZFC Much of axiomatic set theory is the study of models of ZF and ZFC in order to determine which sentences are logical consequences of these theories For instance the Axiom of Choice is independent of the axioms of ZF ie neither CHAPTER 5 AXIOMATIC SET THEORY 86 AC nor its negation is a logical consequence of ZF assuming ZF is consistent Similarly the Continuum Hypothesis is independent of ZFC We will see below that AC is consistent with ZF and that CH is consistent with ZFC showing that the negations are consistent uses the method of forcing which we will not cover here Note 529 We may ask whether it is possible to prove that say ZFC is consis tent This presents the following problem Since ZFC is supposed to encompass the standard axioms of mathematics the natural interpretation of the above question would amount to asking whether the axioms of ZFC can prove that ZFC is consistent Godel s Second lncompleteness Theorem tells us though that no sufficiently complex consistent theory can prove its own consistency Hence in order to prove that ZFC is consistent we must use additional axioms we shall give an example of such an additional axiom below De nition 530 Let A E be a relational structure We say that a relation R Q AlC is de nable over A E if there is a formula Fac1 xky1 H ym of LST and elements b1 bm E A such that Ra1akEAkAElFa1akb1bm If B Q A we say that R is de nable over A E with parameters from B if we can choose b1 bm E B above We let DefA Q 77A be the set of all subsets of A which are de nable over A Lemma 531 Let A E be a relational structure If A is a nite set then DefA 77A A is in nite then lDefA lAl and hence DefA is a proper subset of77A Proof If A is nite then any subset of Y Q A is de ned by the formula Fac aca1acan where Y a1 an If A is in nite then any de nable subset is de ned using a formula F of LST and a nite set of parameters from A Since there are only countably many formulas of LST we have lDefAEl S No lAltWl No lAl W and since every singleton a with a E A is de nable we have l DefA lAl 1 De nition 532 Let A E and A E be relational structures We say that A E is a substructure of A E A E Q A E if A Q A and E E A X A We say that A E is an elementary substructure of A E A E lt A E if A E Q A E and for each formula Fac1 xn of LST and elements a1 an E A we have A E l Fa1 a if and only if A E l Fa1 a CHAPTER 5 AXIOMATIC SET THEORY 87 Lemma 533 If A E Q A E then we have A E lt A E if and only if every nonempty subset ofA which is de nable over A E using parameters from A has nonempty intersection with Proof Suppose rst that A E lt A E and let Fac y1 l l l ym be a for mula and a1 l l i am E A s Since the set these de ne over A E is nonempty the sentence 3xFoc a1 l l i am is true in A Hence this sentence is true in A E as well so 39595 E A Fx1ulxka1luam ie the set de ned by F and a1 l l l am has nonempty intersection with AA Conversely suppose every such de nable set has nonempty intersection with A s We prove by induction on formulas that each sentence F is true in A E if and only if it is true in A E This is immediately true for atomic formulas of the form a b or a E b where ab E A since A E Q A The induction steps for connectives are immediate If we have a sentence of the form 3xFx which is true in A E then there is some a E A such that Fa is true in A E hence true in A E and hence 3xFx is true in A On the other hand if this sentence is true in A E then the set de ned by F is nonempty hence has nonempty intersection with A hence 3a E A Fac and hence the sentence is true in A E Finally universal quanti ers are handled using the fact that VxFac is logically equivalent to dx FQc 1 De nition 534 We say a relational structure A E is countable if A is a countable sets Theorem 535 LowenheimSkolem Theorem Every relational structure A E has a countable elementary substructure A E lt A Proof Let c 77A A A be a choice function for Al De ne a sequence of sets by A0 ll An1 CX X Q AX at ll X is de nable over A E using parameters from A7 A U An nltw Then each An Q An1 and each An is countable since there are only countably many sets de nable over A E using parameters from a countable sets Hence A is countablel If X is a nonempty subset of A de nable over A E using pa rameters from A then there is some n such that X is de nable using parameters from An hence CX E X An1 Q X A and so X has nonempty intersection with A s Hence by the previous lemma we have A E lt A 1 Applying this to a model of ZFC we have Corollary 536 Skolem Paradox If ZFC is consistent then there is a countable model of ZFC CHAPTER 5 AXIOMATIC SET THEORY 88 This is called a paradox because the axioms of ZFC prove that there are uncountable sets eg 77w Thus a countable model of ZFC has elements which it thinks are uncountable sets but these sets must really be countable in the real universe of sets The resolution of this paradox is that although in the universe of sets there are bijections between these sets and the natural numbers these bijections are not elements of the countable model and hence the model does not know that these sets are countable The theorem is easily generalized to the following Theorem 537 Let It be an in nite cardinal and let A E be a relational structure such that lAl 2 Kt Let X Q A be such that le S Kt Then there is an elementary substructure A E of A E such that X Q A and lAl Kt 54 Transitive Models We are interested in structures which model as much of ZFC as possible We rst consider which structures model the axioms of Extensionality and Foundation De nition 538 Let S be a set of sentences of LST A transitive model ofS is a transitive set X such that the Emodel X E IX satis es all of the sentences of S We identify the transitive set X with the relational structure X E IX Note that every transitive model X is wellfounded and extensional since for a E X we have a Q Up to isomorphism these turn out to be all of the wellfounded and extensional models Theorem 539 Let A E be a relational structure which is wellfounded and extensional Then there is a transitive pure wellfounded set X called the transitive collapse of A E such that A E g X EIX Moreover the set X and the isomorphism are unique Proof Fix some object a0 E A We trans nite recursion on the rank of a pure wellfounded set ac de ne the function F by the unique a E A such that if such an a exists F9c FacbEAbEa a0 otherwise Let X F 1A ac F9c E A When Fac Fy E A we must have ac y so that F is injective on X hence the inverse function F 1 is well de ned on A and so X is a set Letting f F 1 I A it is immediate that f is an isomorphism between A E and X E IX and we see that X is a transitive pure wellfounded set Verifying that X and f are unique is straightforward using induction on the rank of elements of X 1 Corollary 540 IfA E is a relational structure the following are equivalent 1 A E is wellfounded and extensional CHAPTER 5 AXIOMATIC SET THEORY 89 2 A E is isomorphic to a transitive model X We will hence restrict our attention to transitive models We wish to char acterize when transitive models are models of the various axioms of ZFC We adapt an earlier de nition De nition 541 Let A be a transitive set We say a relation R Q AC is de nable over A if it is de nable over A E IA using parameters from A We let DefA DefA E lA The key idea below is that of relatioizing a sentence to a structure A ie we replace each quanti er 3x by 3x E A77 and each Vx by Vx E A Lemma 542 Let A be a transitive model 1 A satis es the Axiom of Extensionality 2 A satis es the Axiom of Foundation 5 A satis es the Pairing Axiom and only ifA is closed under pairing ie VaVba e A A b e A a 1 b e A A A satis es the union axiom if and only ifA is closed under union ie VaaEA UaEA 3quot A satis es the Empty Set Axiom and only iflll E A A satis es the Axiom of In nity if and only 3a E Aw Q A P gt2 A satis es the Power Set Axiom if and only Vaa E A 7711 0 A E A 8 A satis es the Axiom of Choice and only if every indexed family of nonempty sets in A which is in A has a choice function in A ie if a lg E A and each al is nonempty then A O Hid al at ll A satis es the Comprehension Scheme and only iffor each X E DefA er p VaaEA a XEA N 9 A satis es the Replacement Scheme if and only if for each function F A A A which is de nable over A we have Vaa E A Fa E A Proof This is straightforward since we have simply relativized all of the re quirements to those sets that A knows about 11 CHAPTER 5 AXIOMATIC SET THEORY 90 Lemma 543 Let 6 gt U be a limit ordinal Then R5 satis es all of the axioms of ZFC except possibly the Replacement Scheme Proof Extensionality and Foundation hold because R5 is transitive Empty Set holds because 6 gt 0 and In nity holds because 6 gt 0 R5 is always closed under taking unions or subsets so the Union and the Comprehension Scheme are true Since 6 is a limit ordinal we have that R5 is closed under power set pairing and products and hence satis es Power Set Pairing and the Axiom of Choice 1 In order to determine when R5 satis es the Replacement Scheme we consider inaccessible cardinals Lemma 544 An in nite cardinal A is regular if and only there is no set XQ A with le lt A and supX A Proof Suppose rst there is X Q A with le lt A and supX A Then an ozl A so the co nality of A is at most le so A is not regular Con versely suppose A is not regular and let Ki cofA lt A and A lt A such that EKnAl A Let X EjKCXAz oz lt a Then X Q A le Ki lt A and supXElltKAlA 1 Lemma 545 If A is an inaccessible cardinal then 1 Vacx Q R lt A as E R5 2 Vxx E R lt A 5 RM A Proof 1 De ne p as A A by pu ranku for u E ac Then dye Q A and S lt A so the preVious lemma implies that oz sup dye lt A since A is regular Hence as Q Ra so as E Ra1 Q R since A is a limit ordinal 2 We show that lRal lt A for oz lt A by trans nite induction First lRol 0 Then lRa1ll7 Ral 2W A assuming lRal lt A since A is a strong limit cardinal Finally if 6 lt A is a limit ordinal with lRal lt A for all oz lt 6 then U R ozlt6 lRal g Emmi lt5 alt6 since A is regular Now if as E R we have as E Ra for some oz lt A so as Q Ra and hence M S lRal lt A
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'