REHMTN ORDINAL NUMBERS AND THE HILBERT BASIS THEOREM Stephen G. Simpson Department of Mathematics Pennsylvania State University University Park, PA 16802 submitted September 16, 1986 accepted April 2, 1987 for publication in the Journal of Symbolic LogicThis research was partially supported by NSF grant MCS-8317874..P ORDINAL NUMBERS AND THE HILBERT BASIS THEOREM Stephen G. Simpson #1. Introduction. ____________ In [5] and [21] we studied countable algebra in the context of "reversemathematics." We considered set existence axioms formulated in the languageof second order arithmetic. We showed that many well known theorems aboutcountable fields, countable rings, countable abelian groups, etc. areequivalent to the respective set existence axioms which are needed to provethem. One classical algebraic theorem which we did not consider in [5] and[21] is the Hilbert Basis Theorem. Let K be a field. For any natural numberm, let K[x ,...,x ] be the ring of polynomials over K in m commuting 1 mindeterminates x , ..., x . The Hilbert Basis Theorem asserts that for all K 1 mand m, every ideal in the ring K[x ,...,x ] is finitely generated. This "1 mtheorem is of fundamental importance for invariant theory and for algebraicgeometry. There is also a generalization, the Robson Basis Theorem [11],which makes a similar but more restrictive assertion about the ringK;x ,...,x : of polynomials over K in m noncommuting indeterminates. 1 m In this paper we study a certain formal version of the Hilbert BasisTheorem within the language of second order arithmetic. Our main result isthat, for any or all countable fields K, our version of the Hilbert Basis @wTheorem is equivalent to the assertion that the ordinal number w is wellordered. (The equivalence is provable in the weak base theory RCA .) Thus B0 wthe ordinal number w is a measure of the "intrinsic logical strength" of theHilbert Basis Theorem. Such a measure is of interest in reference to thehistoric controversy surrounding the Hilbert Basis Theorem's apparent lack ofconstructive or computational content. Recall Gordan's famous remark: "Thatis not mathematics, that is theology!" (See Bell [1], Noether [8].) We also prove that the analogous formal version of the Robson Basis Aw @wTheorem is equivalent to the assertion that the ordinal number w is wellordered. (Again the equivalence is provable in RCA .) Thus the "intrinsic 30logical strength" of the Robson Basis Theorem is strictly and measureablygreater than that of the Hilbert Basis Theorem. The plan of this paper is as follows. In #2 we give the precisestatements of our main results relating basis theorems to ordinal numbers. In#3 the main results are proved using several definitions and lemmas relatedto the theory of well partial orderings. The proofs of three of those lemmasare postponed to #4. This research was partially supported by NSF grant MCS-8317874. I wouldlike to thank my colleague Edward Formanek for bringing Robson's papers [10]and [11] to my attention..p40 #2. Hilbertian and Robsonian rings within RCA . __________ ___ _________ _____ ______ 0 H0 Recall that RCA is the subsystem of second order arithmetic with S 0 31 0induction and D comprehension. The reader is assumed to be familiar with 1RCA and to have at least some acquaintance with the technique of formalizing 0mathematics within RCA . Roughly speaking, the mathematical content of 0RCA is similar to the positive content of recursive mathematics. The biggest 0difference is that RCA allows only a very restricted form of induction on the 0natural numbers, while recursive mathematics allows unrestricted induction.For basic information about RCA , see [5], [17], [20], [21]. 0 Most of the definitions and arguments of this paper are meant to beformalized within RCA . Within RCA we use N to denote the set of all natural 0 0numbers. (If we are working within a non-w-model of RCA , then N includes the 80nonstandard integers.) We use i, j, k, l, m, n, ... as variables ranging overelements of N. As in [5] and [21], a countable commutative ring R is defined within RCA M0to consist of a set |R| { N together with binary operations + , . : |R| x |R| -3 |R|, R Ra unary operation - : |R| 3 |R|, and distinguished elements 0 , 1 m |R| R )R Rsatisfying the usual commutative ring axioms, including 0 = 1. We routinelywrite R instead of |R| and employ the usual notation of modern algebra. (Alsowithin RCA we can similarly define the notions of countable field, countable 0ring, countable partial ordering, etc.) Within RCA we can prove that for any countable field K and any m m N, 0there exists a countable commutative ring K[x ,...,x ] consisting of 0 plus -1 m ~all (Godel numbers of) expressions of the form 5i i #]::" 1 m f(x ,...,x ) = } a x ...x 1 m i ...i 1 m #[;;' 1 m i +...+i ,n !1 m mwhere ;i ,...,i : m N , m m N, a m K, and a = 0 for at least 1 m i ...i i ...i !1 m 1 m mone ;i ,...,i : m N with i +...+i = n. This is the ring of polynomials in 1 m 1 mm commuting indeterminates x , ..., x over K. 1 m 2.1. Definition. Within RCA , let R be a countable commutative ring. __________ 0We say that R is Hilbertian if for every sequence ;r : k m N: of elements of 4kR, there exists k m N such that for all j m N there exist s ,...,s m R such ;0 kthat r = T r .s . j i i i,k 2.2. Remark. There is a subsystem of second order arithmetic known as ______ACA which is somewhat stronger than RCA . (See [5], [17], [20].) Within 0 $0ACA , it is not hard to show that a countable ring R is Hilbertian if and only 0if every ideal of R is finitely generated. (An ideal of R is a set I { R suchthat 0 m R, 1 n R, r +r m I for all r , r m I, and r.s m I for all r m I and 1 2 1 2s m R.) In RCA however, the assertion that R is Hilbertian seems to be a 0little stronger than the assertion that every ideal of R is finitelygenerated. We may explain the distinction as follows. As in [5] and [17], 0define a S ideal of R to be a sequence ;r : k m N: such that (1) r m R and 1 k kr = 1 for all k m N; (2) for all i, j m N there exists k m N such that r +r k Gi j= r ; and (3) for all i m N and s m R there exists j m N such that r .s = r . k @i j 0Within RCA , the notion of a S ideal of R is more general than the notion of 0 1an ideal of R. It is not hard to show within RCA that R is Hilbertian if and 10 0only if every S ideal of R is finitely generated. 1 In our main result (Theorem 2.7 below), it would be possible to replace"K[x ,...,x ] is Hilbertian" by "every ideal of K[x ,...,x ] is finitely 1 m '1 mgenerated." We have chosen to emphasize the Hilbertian property, mainlybecause it seems to be more useful in applications to algebraic geometry, etc.In addition, most of the work of proving our main result goes into showing wthat the well orderedness of w implies Hilbertianness of K[x ,...,x ] for all =1 mm m N. Thus our use of the Hilbertian property leads to a more definitiveresult. We now discuss ordinal notations. 2.3. Definition. We define the set E of notations for ordinals less __________than e , and the ordering < of these notations. The definition is given by 0the following inductive clauses. 0a a 11 m 1. If a , ... , a belong to E, then w + ... + w belongs to E. 1 m 2. If a , ... , a and b , ... , b belong to E, then 1 m 1 n a a b b 1 m 1 n w + ... + w < w + ... + wif and only if either (a) m < n and a = b , ..., a = b ; or (1 1 m m(b) a = b , ..., a = b , a < b for some k < min(m,n). 1 1 k k k+1 k+1 We use a, b, g, ... to denote elements of E and we refer to such elementsas ordinals less than e . We sometimes identify b < e with the set of its 0 0predecessors, i.e. b = {a: a < b}. Ha I1We use 0 to denote the element of E which is the empty sum, i.e. 0 = w + a m $0 1... + w where m = 0. We also write 1 = w and w = w . We identify m m Nwith the element of E which is the sum of m 1's, i.e. m = 1 + ... + 1 ^----(----& !m times. 2.4. Proposition. The following facts are provable within RCA . ___________ .0 1. The set E = {a: a < e } exists. 0 2. The binary relation < exists and is a linear ordering of E. 3. 0 , a for all a. 4. a + 1 is the immediate successor of a. 5. a < w if and only if a = m for some m m N. w m 6. a < w if and only if a < w for some m m N. w m w w 7. a < w if and only if a < w for some m m N. Proof. Within RCA we can prove that the universe of all total number- _____ 0theoretic functions is closed under composition, primitive recursion, andminimalization. (See #2 of [20] or Chapter II of [17].) Thus the usual proofthat E and < are primitive recursive can be imitated to show within RCA that G0these sets exist. The rest of the lemma is straightforward. (Generalizing parts 5, 6 and 7 of the above proposition, we may note thatRCA proves the following. For any a < e and limit ordinal b < e , a < b if 0 %0 0and only if a < b[m] for some m m N. Here ;b[m]: m m N: is the standardfundamental sequence for b, as defined for instance in Buchholz-Wainer [2].) 2.5. Definition. Within RCA we make the following definitions. A __________ 0descending sequence through e is a function f: N 3 {a: a < e } such that 0 0f(k+1) < f(k) for all k m N. We say that e is well ordered, abbreviated +0WO(e ), if there is no descending sequence through e . We say that a < e 0 /0 0is well ordered, abbreviated WO(a), if there is no descending sequencethrough e beginning with a. 0 From Gentzen's work, it is well known that ACA does not prove WO(e ), 30 0but that, for each (standard) a < e , ACA proves WO(a). In the case of the #0 0weaker system RCA , we have the following. 0 2.6. Proposition. ___________ ?m 1. For each (standard) natural number m, RCA proves WO(w ). 20 !w 2. RCA does not prove WO(w ). 0 w m 3. RCA proves: WO(w ) if and only if WO(w ) for all m m N. 0 w m w w 4. RCA proves: WO(w ) if and only if WO(w ) for all m m N. 0 Proof. Part 1 is straightforward. _____ Part 2 is a consequence of the following result which is essentially dueto Parsons [9] (although Parsons did not consider the system RCA ). The @0provably total recursive functions of RCA are just the primitive recursive )0 wfunctions. If WO(w ) were provable in RCA , we could use this to show that *0the Ackermann function is a provably total recursive function of RCA , D0contradicting Parsons' result. (For a Gentzen-style proof of Parsons' result,see Sieg [14]. For a model-theoretic proof, see Chapter IX of Simpson [17].) Parts 3 and 4 follow immediately from parts 6 and 7 of Proposition 2.4.(More generally, RCA proves: for any limit ordinal b < e , WO(b) if and only 0 $0if WO(b[m]) for all m m N. This is an immediate consequence of theparenthetical remark following the proof of Proposition 2.4.) The following theorem is the main result of this paper. 2.7. Theorem. Within RCA it is provable that the following assertions _______ 0are pairwise equivalent. 1. For all m m N and all countable fields K, the commutative ringK[x ,...,x ] is Hilbertian. (This is our formal version of the Hilbert Basis 1 mTheorem.) 2. For each m m N, there exists a countable field K such that thecommutative ring K[x ,...,x ] is Hilbertian. 1 m w w 3. WO(w ), i. e. the ordinal number w is well ordered. This theorem will be proved in ## 3 and 4. We now discuss Robson's noncommutative generalization of the HilbertBasis Theorem. Within RCA we make the following definitions. Given m m N, let x , ..., 0 71x be m noncommuting indeterminates. We use m &* <w W = {x ,...,x } = {x ,...,x } m 1 m 1 mto denote the set of monomials in x , ..., x . Another way to view W is as #1 m mthe free monoid generated by x , ..., x . (A monoid is a semigroup with a 1 mdistinguished identity element.) Yet another way to view W is as the set of ;mall finite sequences of elements of the set {x ,...,x } (including the empty .1 msequence). This is referred to in computer science as the set of words on thealphabet x , ..., x (including the empty word). 1 m For all w m W we write |w| = the length of w. A typical element of W m 8mis a formal product w = x ...x and in this case we have |w| = l. i i 1 l Within RCA we can prove that, for all countable fields K and all m m N, 0 <~there exists a ring K;x ,...,x : consisting of 0 plus all (Godel numbers of) 1 mexpressions of the form #]:" #} f = a u #[;' u "|u|,nwhere n m N, u m W , a m K, and a = 0 for at least one u with |u| = n. m u uThus K;x ,...,x : is the ring of polynomials over K in m noncommuting 1 mindeterminates x , ..., x . 1 m A polynomial h m K;x ,...,x : is said to be homogeneous of degree 1 ml if it is nonzero and of the form &]:" &}(1) h = c w &[;' w %|w|=lwhere w m W and c m K. In this case we write |h| = l. m w If w m W is of length l, say w = x ...x , then for any u , u , ..., m i i 0 1 )1 lu m W we write l m w[u ,...,u ] = u x u ...x u . 0 l 0 i 1 i l +1 lIf h m K;x ,...,x : is homogeneous of degree l as in (1) above, then we write 1 m &]:" &} h[u ,...,u ] = c w[u ,...,u ]. 0 l [;' w 0 l %|w|=lThus |h[u ,...,u ]| = |u | + ... + |u | + l. 0 l 0 l An ideal is said to be homogeneous if it is generated by its homogeneouselements. A homogeneous ideal I of K;x ,...,x : is said to be insertive if '1 mfor all l m N and all homogeneous polynomials h of degree l, h m I impliesh[u ,...,u ] m I for all u , ..., u m W . The Robson Basis Theorem (cf. 0 l 0 l mTheorem 3.15 of [11]) asserts that for any field K and any m m N, everyinsertive homogeneous ideal of K;x ,...,x : is finitely generated qua "1 minsertive homogeneous ideal. We shall consider a slightly different, butequivalent, formulation. (Compare Remark 2.2 above.) 2.8. Definition. Within RCA we make the following definition. Let K __________ 0be a countable field. For m m N, we say that K;x ,...,x : is Robsonian if, 11 mfor every sequence ;h : k m N: of homogeneous elements of K;x ,...,x :, there k '1 mexists k m N such that for all j m N we have ]:" ]::::::::::::::::" } } h = a h [u ,...,u ] j [;' [;;;;;;;;;;;;;;;;' i,u ,...,u i 0 l .0 l i 6i i,k |u |+...+|u |+l =l 0 l i j !ifor some a m K, where l = |h | for all k m N. i,u ,...,u k k 0 l i The second main result of this paper is as follows. 2.9. Theorem. Within RCA it is provable that the following assertions _______ 0are pairwise equivalent. 1. For all countable fields and all m m N, the ring K;x ,...,x : is =1 mRobsonian. (This is our formal version of the Robson Basis Theorem.) 2. For each m m N, there exists a countable field K such that the ringK;x ,...,x : is Robsonian. 1 m w w w w 3. WO(w ), i. e. the ordinal number w is well ordered. This theorem will be proved in ## 3 and 4 along with Theorem 2.7..p40 #3. Well Partial Orderings. ____ _______ _________ The purpose of this section is to prove the main results of the previoussection, Theorems 2.7 and 2.9. In order to do so, we need to discuss certainaspects of the theory of well partial orderings, within RCA . Our discussion ;0is self-contained. For general background on well partial orderings, thereader may consult [3], [4], [11], [12], [13], [15], [19], [22]. Within RCA we make the following definitions. A countable partial 0ordering A consists of a set |A| { N together with a binary relation , FA{ |A|x|A| which is reflexive (a , a for all a m |A|), transitive (a , as !A $Aand as , at imply a , at) and antisymmetric (a , as and as , a imply a = A A A Aas). We usually write A instead of |A| and , instead of , . :A 3.1. Definition (RCA ). A countable partial ordering A is said to be __________ 0well partially ordered if, for all infinite sequences ;a : k m N: of elements 8ka m A, there exist i and j such that i < j and a , a . k /i j 3.2. Lemma. The following is provable in RCA . For any countable _____ #0partial ordering A, the following assertions are equivalent. 1. A is well partially ordered. 2. For all infinite sequences ;a : k m N: of elements a m A, there &k kexists k such that for all j there exists i , k such that a , a . ;i j Proof. We reason within RCA . The implication from 2 to 1 is trivial _____ 0(take j = k + 1). We prove the implication from 1 to 2. Assume that A is well partially ordered. Let ;a : k m N:, a m A, be 5k kgiven. By recursive comprehension, let X be the set of all j m N such that~ ]i (i < j c a , a ). i j We claim that [j ]i (i m X c a , a ). Suppose not. Let j be such that #i j[i (a , a 3 i n X). By recursion on k we shall define an infinite sequence i jof natural numbers ;i : k m N:. We begin by putting i = j. Assume k 0inductively that a , a . Then i n X so we can find i < i such that i j k k+1 k ka , a , a . Thus ;i : k m N: is an infinite descending sequence of i i j k k+1 knatural numbers. This contradiction proves our claim. We claim that X is finite. If not, let p : N 3 X be the one-to-one .Xfunction which enumerates the elements of X in increasing order. Considerthe sequence ;a : k m N:. By well partial orderedness of A, there exist p (k) Xi and j such that i < j (hence p (i) < p (j)) and a , a . This X X p (i) p (j) 4X Xcontradicts the fact that p (j) m X. Our claim is proved. X Since X is finite, let k m N be an upper bound for X. Our first claimimplies that [j ]i (i , k c a , a ). This completes the proof of Lemma 3.2. i j 3.3. Definition (RCA ). If ;A : 1 , i , m: is a finite sequence of __________ 0 icountable partial orderings, we can form the m-fold Cartesian product m A x ... x A = Q A = {;a ,...,a :: a ,...,a m A}. 1 m i 1 m 1 m i=1This is again a countable partial ordering under the product relation:;a ,...,a : , ;as,...,as: if and only if a , as and ... and a , as. 1 m 1 m 1 1 m m In particular, we have the m-fold Cartesian power m N = N x ... x N &^----(----& +mwhere N is the set of natural numbers with the usual ordering. 3.4. Lemma. The following is provable in RCA . For any m m N and any _____ #0countable field K, the following are equivalent. 1. The commutative ring K[x ,...,x ] is Hilbertian. !1 m %m 2. The m-fold Cartesian power N is well partially ordered. Proof. We reason within RCA . Fix m and K. _____ 0 Assume first that K[x ,...,x ] is Hilbertian. Let 1 m ;;e ,...,e :: k m N: k1 km (mbe an infinite sequence of elements of N . For each k m N define a monomial e e k1 km M = x ...x m K[x ,...,x ]. k 1 m 1 mSince K[x ,...,x ] is Hilbertian, we have ]k [j 1 m M = g M + ... + g M j 0 0 k kfor some g , ..., g m K[x ,...,x ]. Take for instance j = k + 1. A simple 0 k 1 mcancellation argument shows that M is divisible by M for at least one i , "j ik. Thus ;e ,...,e : , ;e ,...,e : i1 im j1 jm min N , and i < j. Since the sequence ;;e ,...,e :: k m N: is arbitrary, we )k1 km msee that N is well partially ordered. This proves that 1 implies 2. 0m For the converse implication, assume that N is well partially ordered.Let ;f : k m N: be an infinite sequence of elements of K[x ,...,x ]. Let k 31 m 0f(h) be the S formula which says that h m K[x ,...,x ] and 1 1 m h = f g + ... + f g #0 0 k k ?0for some k m N and g , ..., g m K[x ,...,x ]. Since f(h) is S , we can 0 k 1 m 1prove within RCA that there exists a sequence ;h : k m N: such that [h (f(h) 0 k#3 ]k (h = h )). (See [20, Lemma 2.1].) Now for each k m N let M be the k 5kleading monomial of h . This means that M is the lexicographically first k k 8e e 9k1 kmmonomial in h of highest total degree. Identify M = x ...x with the k %m 1 m m mm-tuple ;e ,...,e : m N . Since N is well partially ordered, we see by k1 kmLemma 3.2 that there exists k such that for all j there exists i , k suchthat M is divisible by M . j i Fix such a k. We claim that, for all j,(2) h = g h + ... + g h j 0 0 k kfor some g , ..., g m K[x ,...,x ]. We shall prove this by induction on the 0 k 1 mordering of leading monomials. Given j, let i , k be such that M is Ajdivisible by M , say M = M N where N is another monomial. Then, for an i j i j jappropriate constant c m K, h - c N h has a leading monomial which is j j j j iprior to M in the ordering of leading monomials. Also h - c N h = h for j .j j j i lsome l m N. Hence by inductive hypothesis (* * h - c N h = g h + ... + g h j j j i 0 0 k k * * -*for some g , ..., g m K[x ,...,x ]. Hence (2) holds with g = g + c N , 0 k 1 m i i j j *g = g for all l , k, l = i. l l This completes the proof of Lemma 3.4. 3.5. Remark. The above proof that 3.4.2 implies 3.4.1 is similar to a ______proof of the Hilbert Basis Theorem which is due to Gordan [6], [7]. 3.6. Lemma. The following is provable in RCA . For any m m N, the _____ #0following are equivalent. %m 1. The m-fold Cartesian power N is well partially ordered. m 2. The ordinal w is well ordered. The proof of this lemma will be presented in #4. Proof of Theorem 2.7. The theorem follows immediately from Proposition _____ __ _______ ___2.6.3 and Lemmas 3.4 and 3.6. 3.7. Definition (RCA ). If A is a countable partial ordering, we can __________ 0 *form the countable set A of all finite sequences of elements of A. We *partially order A by putting ;a : i < k: , ;b : j < l: if and only if there i j H*exist j < ... < j < l such that a , b , ..., a , b . Thus A is a 0 k-1 0 j k-1 j +0 k-1countable partial ordering. In particular, taking A = {x ,...,x } where x , ..., x are noncommuting !1 m 1 mindeterminates, we have the set of monomials /* W = {x ,...,x } m 1 mas in #2. Using the notation of #2, we see that for all w and ws m W , w , ws Emif and only if w[u ,...,u ] = ws for some u , ..., u m W , where l = |w|. 0 l 0 l m 3.8. Lemma. The following is provable in RCA . For any m m N and any _____ #0countable field K, the following assertions are equivalent. 1. The ring K;x ,...,x : is Robsonian. 1 m 2. The set of monomials W is well partially ordered. m Proof. We omit the proof, which is entirely analogous to the proof of _____Lemma 3.4 above. 3.9. Lemma. The following is provable in RCA . For all m m N, if the _____ #0 Dm Cwset of monomials W is well partially ordered, then the ordinal w is well m+1ordered. 3.10. Lemma. The following is provable in RCA . For all m m N, if the _____ #0 m+1 wordinal w is well ordered, then the set of monomials W is well partially :mordered. The proofs of the previous two lemmas will be presented in #4. Proof of Theorem 2.9. The theorem follows immediately from Proposition _____ __ _______ ___2.6.4 and Lemmas 3.8, 3.9 and 3.10..p40 #4. Effective reification. _________ ___________ The purpose of this section is to complete the arguments of #3 by provingLemmas 3.6, 3.9 and 3.10. Two of the proofs are based on the notion ofreification which is defined below. The following definitions are made within RCA . Let A be a countable 20partial ordering. A finite sequence s = ;a : i < k: of elements a m A is +i isaid to be bad if there do not exist i and j such that i < j < k and a , a . Fi jIn this case we write A = {a m A: a / a for all i < k} s i = {a m A: s+;a: is bad}.For any a m A we write s A (a) = A = {b m A : a / b}. s s+;a: sThe countable set consisting of all bad finite sequences of elements of A isdenoted Bad(A). Note that the existence of Bad(A) is provable in RCA . E0 4.1. Definition (RCA ). Let A be a countable partial ordering. For a < __________ 0e , a reification of A by a is a mapping 0 f: Bad(A) -3 a + 1such that f(s+;a:) < f(s) for all s m Bad(A), a m A . 3s 4.2. Lemma. The following is provable in RCA . Let A be a countable _____ #0partial ordering. If there exists a reification of A by a, and if a is wellordered, then A is well partially ordered. Proof. We reason within RCA . Let f: Bad(A) 3 a+1 be a reification of A _____ 0by a. Suppose that A is not well partially ordered. Then there exists aninfinite sequence ;a : k m N: of elements a m A which is bad, i.e. there do k knot exist i, j m N such that i < j and a , a . For each k m N put a = (i j kf(;a : i < k:). Then ;a : k m N: is an infinite descending sequence of i kordinals less than or equal to a. This contradicts the assumption that a iswell ordered. Our lemma is proved. 4.3. Remark. A large part of the work in this section is devoted to ______finding explicit, effectively given reifications of the well partial orderingswhich were considered in #3. Our treatment of reification is self-contained.For general background on reification, the reader may consult DeJongh andParikh [3], Schmidt [12], and Statman [22]. We shall make use of the following definition and lemma. 4.4. Definition. Within RCA we define the natural sum of ordinals less __________ 0than e by 0 a a b b g g 1 m 1 n 1 m+n (w + ... + w ) + (w + ... + w ) = w + ... + wwhere ;g ,...,g : is a permutation of ;a ,...,a ,b ,...,b : such that 1 m+n 1 m 1 ng , ... , g . The natural product is defined by 1 m+n a a b b 1 m 1 n (w + ... + w ) w (w + ... + w ) a +b a +b a +b 1 1 i j m n = w + ... + w + ... + wwhere i = 1, ..., m and j = 1, ..., n. Note that in this paper we use + and wexclusively to denote the natural sum and natural product. 4.5. Lemma. The following facts are provable within RCA . _____ .0 1. (a + b) + g = a + (b + g). 2. a + b = b + a. 3. a + b < a + b if and only if b < b . 1 2 1 2 g )g g 4. w is additively indecomposable, i.e. a < w and b < w imply ga + b < w . 5. (a w b) w g = a w (b w g). 6. a w b = b w a. 7. a w b < a w b if and only if b < b . 1 2 1 2 8. (a + b) w g = (a w g) + (b w g). g 0g g w 0w w 9. w is multiplicatively indecomposable, i.e. a < w and b < w g wimply a w b < w . Proof. The proof is straightforward. _____ We now prepare for the proof of Lemma 3.6. For u , v , w we write [u,v) = {a: u , a < v}. Given an m-fold mCartesian product Q [u ,v ) with u , v , w for each i, we define i i i i i=1 m m | Q [u ,v )| = Q (v -u ) i i i i i=1 i=1where on the right hand side Q denotes natural product. :m 4.6. Sublemma (RCA ). Suppose that ;a ,...,a : m Q [u ,v ) where ________ 0 1 m i i 8i=1u , v , w for each i. Then i i m m(3) T | Q [u (s),v (s))| < | Q [u ,v )|. i i i i s i=1 i=1Here T denotes natural sum, s = ;s : 1 , i , m: ranges over all m-tuples of "i0's and 1's which do not consist entirely of 1's, and "^ [u ,a ) if s = 0, &i i i [u (s),v (s)) = 8 i i "6 [a ,v ) if s = 1. &i i i Proof. We reason within RCA . Let k be the number of i's such that _____ 0v = w. Suppose first that k = 0. In this case, the sublemma follows easily iby observing that the disjoint union "m g Q [u (s),v (s)) &i i s i=1 'mis a proper subset of the finite set Q [u ,v ). *i i %i=1 Ik Suppose now that k > 0. The right hand side of (3) is of the form w w nwhere n < w. Let us say that s is wild if s = 0 for some i such that ,iv = w, otherwise tame. If s is wild, the contribution of s to the left hand i ksside of (3) is of the form w w ns where ks < k and ns < w. Hence, by Lemma 8k4.5.4, the total contribution of all the wild s's is < w . On the other hand, ;kthe total contribution of all the tame s's is of the form w w nt wherent < n. (The inequality nt < n follows from the special case k = 0 which hasalready been proved.) Thus the total left hand side is k k k < w + (w w nt) , w w n.This completes the proof of Sublemma 4.6. 4.7. Sublemma. The following is provable in RCA . For each m m N, there ________ #0 m mexists a reification of N by w . Proof. We reason within RCA . Fix m m N. We shall define a reification _____ 0 m m m mf: Bad(N ) 3 w +1. For s m Bad(N ) we shall define f(s) , w by primitiverecursion on the length of s. (See [20, pp. 788-789].) The value of f(s) 2mwill be obtained in terms of a decomposition of (N ) into a disjoint union, 4s (m m(4) (N ) { g Q [u ,v ) , s ij ij !jmJ i=1where J is a finite index set and u , v , w for all j m J, i = 1, ..., m. #ij ijWe shall then define )m f(s) = T | Q [u ,v )|. -ij ij "jmJ i=1 We begin with the trivial decomposition .m m m (N ) = N = Q [0,w) ;: ,i=1and accordingly we define %m 4m f(;:) = | Q [0,w)| = w . #i=1 m Now fix s m Bad(N ) and assume inductively that we have already defined +m mf(s) according to a decomposition (4) of (N ) . Given ss = s+;a: m Bad(N ), -s &mwe want to define f(ss). Since a m (N ) , there is a unique js m J such that (s m >ma = ;a ,...,a : m Q [u ,v ). As our decomposition of (N ) , we take 1 m ijs ijs ss i=1 m m(4) with Q [u ,v ) replaced by g Q [u (s),v (s)) as in Sublemma ijs ijs ijs ijs i=1 s i=1 Bm4.6. It is easy to check that this provides a decomposition of (N ) as Dssrequired. The fact that f(ss) < f(s) follows from Sublemma 4.6 and Lemma4.5.4. This completes the proof of Sublemma 4.7. Proof of Lemma 3.6. We reason within RCA . Fix m m N. _____ __ _____ ___ 0 m Assume first that w is well ordered. By Sublemma 4.7 there exists a m m 'mreification of N by w . Hence by Lemma 4.2 it follows that N is wellpartially ordered. This proves half of our lemma. &m For the other half, assume that N is well partially ordered. Define a m m imapping g: w 3 N by g( T a ww ) = ;a : i < m:. Note that g(a) , g(b) i i i*the property that h (u) , h (v) implies u , v for all u, v m A . The t tcountable partial ordering C will be of the form t(8) C = g Q B t ik %imI kmK ,iwhere I and the K , i m I, are finite index sets, g denotes finite disjoint i L*union, Q denotes finite Cartesian product, and each B is either A or (A ) 5ik s sfor some s m Bad(A). The ordinal value of any such countable partial ordering /f(s) f(s)+1 .w * wis defined in terms of f as follows: |A | = w , |(A ) | = w , (s s| Q B | = Q |B | (natural product), and | g D | = T |D | (natural sum). k k i i kmK kmK imI imI * *We then define f (t) = |C | for each t m Bad(A ). t G* It remains to define the mappings h as in (7), for each t m Bad(A ). We (tshall do this by primitive recursion on the length of t. We begin by letting !* * * *h be the identity mapping of (A ) = A into C = (A ) = A . Thus we ;: ;: ;: ;:have /f(;:)+1 a+1 &* w w f(;:) = |C | = |(A ) | = w , w . ;: ;: * * * Now let ts = t+;u: m Bad(A ) and assume that h : (A ) 3 C and f (t) = 3t t t|C |, with C as in (8), have already been defined. Our goal is to define t t *h . Since u m (A ) , we have h (u) m C , hence h (u) m Q B for a unique ts t t t t ik 9kmK