REHMTN.Q4 COUNTABLE VALUED FIELDS IN WEAK SUBSYSTEMS OF SECOND ORDER ARITHMETIC Kostas Hatzikiriakou %and Stephen G. Simpson* Department of Mathematics The Pennsylvania State University University Park, PA 16802 September 4, 1987*Simpson's research was partially supported by NSF grant DMS-8701481.P COUNTABLE VALUED FIELDS IN WEAK SUBSYSTEMS OF SECOND ORDER ARITHMETIC Kostas Hatzikiriakou and Stephen G. Simpson #0. Introduction. ____________ This paper is part of the program of reverse mathematics. We assume thereader is familiar with this program as well as with RCA and WKL , the 80 0two weak subsystems of second-order arithmetic we are going to work withhere. (If not, a good place to start is [2].) In [2], [3], [4], many well-known theorems about countable rings,countable fields, etc. were studied in the context of reverse mathematics.For example, in [2], it was shown that, over the weak base theory RCA , the E0statement that every countable commutative ring has a prime ideal is ~equivalent to weak Konig's Lemma, i.e. the statement that every infinite{0,1} tree has a path. >~ Our main result in this paper is that, over RCA , weak Konig's Lemma 50is equivalent to the theorem on extension of valuations for countable fields.The statement of this theorem is as follows: "Given a monomorphism ofcountable fields h : L -3 K and a valuation ring R of L, there exists a &-1valuation ring V of K such that h (V) = R." In [5], Smith produces a recursive valued field (F,R) with a recursive ~algebraic closure F such that R does not extend to a recursive valuation ~ ~ring R of F. However, there is little or no overlap between the contentsof the present paper and [5]. #1. Countable valued fields in RCA . _______________________________0 1.1 Definition (RCA ). A countable valued field consists of a __________ 0countable field F together with a countable linearly ordered abelian group Gand a function ord : F -3 Gg{%} satisfying: (i) ord(a) = % iff a = 0, (ii) ord(a.b) = ord(a) + ord(b), (iii) ord(a+b) , min(ord(a),ord(b)). Such a function is called a valuation on F. 1.2 Definition (RCA ). A subring V of a countable field F is called __________ 0 '* -1a valuation ring of F iff for any x m F = F \ {0} either x m V or x m V. 1.3 Theorem (RCA ). A valuation ring V of a countable field F is a _______ 0local ring, i.e. it has a unique maximal ideal M consisting of all 1Vnon-units of V. 7-1 Proof. The set of non-units of V, M = {a m V : a n V}, exists by _____ V 0D comprehension, an axiom scheme that RCA includes. We prove that 1 (0 5-1M is an ideal. Let x, y m M . We can assume x.y m V. Then V V -1 x + y -11 + x.y = _____ m V. If x + y were not in M , then _____ would y #V x + y -1belong to V, whence y m V and this would contradict the fact thaty m M . Now, let x m M and y m V. Then x.y m M . If not, V V V -1 -1 -1 -1(x.y) m V, i.e. y .x m V, whence x m V which contradicts the factthat x m M . Hence M is an ideal which clearly is the unique maximal V Videal of V. =y 1.4 Theorem (RCA ). Every valuation on a countable field F gives rise _______ 0to a valuation ring of F and, conversely, every valuation ring of acountable field F gives rise to a valuation on F. Proof. Suppose ord is a valuation on F. The set _____ %0V = {a m F: ord(a) , 0} exists by D comprehension and it is a valuation %1ring of F; the unique maximal ideal of V is M = {a m F : ord(a) > 0}. 0V 3* -1Conversely, let V be a valuation ring of F. Let V = {a m V : a m V}. 0 *This set exists by D comprehension. V is a subgroup of the 1 *multiplicative group F = F \ {0}, so we may form the quotient group * * '*G = F /V . The elements of G are those a m F such that [b((b* | the least (in the sense of < ) c such that c m F and *N | &-1ord(a) = 8 c.a m V*, if a = 0, | | % ,if a = 0. 6 Fy The previous theorem allows the following equivalent definition of acountable valued field. 1.5 Definition (RCA ). A countable valued field consists of a countable __________ 0field F and a valuation ring V of F. We write (F,V). 1.6 Definition (RCA ). An extension h : (F,R) --3 (K,V) of countable __________ 0 @-1valued fields is a field monomorphism h : F --3 K such that h (V) = R. 1.7 Remark. Suppose h : (F,R) --3 (K,V) is an extension of countable ______ &* *valued fields as above. Let ord : F --3 G and ord : K --3 G be !F F K Kthe valuations associated with (F,R) and (K,V) as in Theorem 1.4. Then, "^there is an obvious monomorphism h : G --3 G such that the following 'F Kdiagram commutes: &h !F -----3 K !| | ord ord F | ^ | K !2 h 2 !G -----3 G "F KConversely, given any such commutative diagram, there is a correspondingextension of countable valued fields. These facts can be proved in RCA . H0 #2. Proof of the main theorem. _________________________ To prove our main theorem, we need the following two lemmas. 2.1 Lemma (WKL ). Let K be a countable field, R a countable commutative _____ 0ring, I an ideal of R, and h : R --3 K a ring monomorphism. Then thereexists a valuation ring V of K such that h(R) { V { K andh(I) { M h V. V Proof. We argue in WKL . The method is similar to the one used in the _____ 0construction of a prime ideal of a countable commutative ring. (See Theorem3.1 in [2]). Let a ,a ,... be an enumeration of K. Let b ,b ,... be an 0 1 &0 1enumeration of h(R). Let c ,c ,... be an enumeration of h(I). Note that 0 1 !0h(R) and h(I) are defined by S formulas and, hence, they can be !1enumerated within RCA . 0 We define a tree T by induction on s = lh(s) and simultaneously we definefinite sets X { K, s m T, with the property that s h t implies X { X . s 6s tAt stage s, T = {s m T : lh(s) = s} is defined. For s = 0, let T = {O} s 80and X = O. Assume T is defined and let s m T . The construction O s-1 s-1splits into the following 5 cases. For convenience assume that s = 5m + r,0 , r < 5. r = 0. For each s m T , put s0 m T and let X = X g {b }. s-1 s s0 s m r = 1. For each s m T , put s0 m T and let X = X , unless s-1 s s0 sm = (i,j,k) (every natural number encodes a triple of natural numbers) anda , a m X in which case let X = X g {a +a }. i j s s0 s i j r = 2. For each s m T , put s0 m T and let X = X , unless s-1 s s0 sm = (i,j,k) and a , a m X in which case let X = X g {a .a }. i j s s0 s i j r = 3. For each s m T , put s0 m T and let X = X , unless s-1 s s0 sm = (i,j,k) and a .a = 1 in which case put s0, s1 m T and let i j #sX = X g {a } and X = X g {a }. s0 s i s1 s j r = 4. For each s m T , put s0 m T and let X = X , unless s-1 s s0 sm = (i,j,k) and a m X and a .c = 1 in which case put neither s0 nor i s i js1 m T and do not define X and X . s s0 s1 Claim (RCA ). T is infinite. _____ 0 0 Proof: Consider the P formula 1 v(s) = ]s m T (1 n I ) , )s swhere I is the ideal generated by I inside the ring R[X ], i.e. the s 4sring generated by R g X inside K. (Note that I and R[X ] are s s s 0defined by S formulas; we do not assume that they exist as sets.) 1 Now, v(0) holds since I is an ideal of R. Assume that v(s-1)holds, s m T and 1 n I . If r = 0,1,2, then I = I and so v(s) s-1 s s0 sholds. If r = 3, then, either only s0 was thrown into T , whence =sX = X and I = I and so v(s) holds, or both s0, s1 m T and s0 s s0 s *s -1X = X g {a}, X = X g {a }, for some a m K. In this case assume that s0 s s1 s1 m I and 1 m I . Then, we have: s0 s1 %n (I) 1 = a + a .a + ... + a .a , a m I , i = 1,...,n. 0 1 n i s -1 -m (II) 1 = b + b .a + ... + b .a , b m I , i = 1,...,m. 0 1 m i s 0By the S least element principle we may assume that m, n are chosen as 1small as possible and, by symmetry, we may assume that n , m. Now, we have: n n n-m n n-1 n-m(II) ek a = b .a + ... + b .a ek (1-b ).a = b .a + ... + b .a , 0 m 0 1 m ,n-1 n-m (I) ek (1-b ) = (1-b ).a + ... + a .b .a + ... + a .b .a , 0 0 0 n 1 n m .n-1 n-m i.e. 1 = b + (1-b ).a + ... + a .b .a + ... + a .b .a , 0 0 0 n 1 n mso 1 can be written as a polynomial in a of degree smaller than n withcoefficients in I . (The above computation is taken from the standard stextbook proof of the extension of valuations theorem; see, for instance,Lemma 9.1, section II, in [1].) This is a contradiciton. Hence, either1 n I or 1 n I and so v(s) holds. Since RCA includes s0 s1 "0 0P induction (see Lemma 1.1 in [2]), we have that v(s) holds for all 1s m N. Hence, T is infinite. ~ Now, by weak Konig's Lemma let f be a path through T. Let V = D0 g X . Then, V is a valuation ring of K (because of cases r = 1, 2, 3) s 0shfand h(R) { V (because of case r = 0). Moreover, every element of h(I) is 0 J0a non-unit of V (because of case r = 4). However, V is defined by a S 0 &0 1formula and, so, may not exist. Hence, consider the following tree S of allsequences s m Seq satisfying: 2 For all i, j, k < lh(s) (i) a = b ek s(i) = 1 i j (ii) s(i) = s(j) and a + a = a ek s(k) = 1 i j k (iii) s(i) = s(j) and a .a = a ek s(k) = 1 i j k (iv) a .a = 1 ek s(i) = 1 or s(j) = 1 i j (v) a = c and a .a = 1 ek s(k) = 0. i j i k To see that S is an infinite tree, let s m N. Then let 50X = {i < s: ]n(a m X )}. X exists by bounded S comprehension 1 f[n] 1 *s(see Lemma 1.6 in [2].) So, define s m 2 by #^1 if i m X, s(i) = 8 \$0 if i n X. #6 Then, s exists and s m S since V is a valuation ring of K, h(R) { *0V , and every element of h(I) is a non-unit of V . So, S is infinite 0 20and hence there is a path g through it. Let V = {a : g(i) = 1}. Then, 6i 0this set exists by D comprehension and it is a valuation ring of K, 1(conditions (ii), (iii), (iv)) such that h(R) { V (condition (i)). Bycondition (v), all elements of h(I) are non-units, hence h(I) { M , where EV 20M is the maximal ideal of V which exists by D comprehension (Theorem V 011.3). By 2.2 Lemma (RCA ). Lemma 2.1 implies the theorem on extension of _____ 0valuations for countable fields: "Given a monomorphism of countable fieldsh : L -3 K and a valuation ring R of L, there exists a valuation ring V -1of K such that h (V) = R." Proof. Assume Lemma 2.1. Then, given the monomorphism h : L -3 K and _____the valuation ring R of L, there is a valuation ring V of K such that <-1h(R) { V { K and h(M ) { M h V. We need to prove that h (V) = R. Let a R V 8-1m R, then h(a) m h(R), hence h(a) m V and so a m h (V). Let a m -1h (V), then h(a) m V. Then, if h(a) = 0, we have a = 0, hence a m R. 2-1 -1If h(a) = 0, then a = 0 and if a n R then a m M , whence h(a ) m 8R 1h(M ) { M . Hence, _____ m M , whence 1 m M , a contradiction. So a m R. R V h(a) V V Now, we are ready to prove the following: 2.3 Theorem (RCA ). The following are equivalent: _______ 0 ~ (i) Weak Konig's Lemma; (ii) The theorem on extension of valuations for countable fields. Proof. (i) k (ii) follows from Lemmas 2.1 and 2.2. (ii) k (i). Assume _____(ii). Let f, g : N 3 N be two 1-1 functions such that f(n) = g(m), [ n, mm N. Consider the field K = Q(x : n m N) and the field L = Q(y ,z : n m !n n nN). Let h : L 3 K be the field monomorphism defined via h(y ) = x and ?n f(n)h(z ) = x , [n m N. On L we define a valuation as follows: Let a m n g(n)Q(y z : n m N), say a = p/q, p,q m Q[y ,z : n m N]. Let p = n, n "n n 1* -1 -1p(y ,y ,...,z ,z ,...) m Q[y ,z : n m N]. Let p = p(s,s,...,s ,s ,...) = 0 1 0 1 n n r a i -1 * T c s m Q[s,s ], c = 0. Let o(p ) = min{a : 1 , i , r}. Define i i ii=1 * *ord(a) = o(p ) - o(q ). Clearly, this is a valuation on L. Let R = {a:ord(a) , 0}. Then, by (ii), there is a valuation ring V of K such that -1h (V) = R. Let X = {n : x m V}. For m m N, we have: x m V (since n f(m) -1 8-1h (x ) = y m R), hence f(m) m X; x n V (since h (x ) = z n f(m) m g(m) g(m) mR), hence g(m) n X. Hence, [m(f(m) m X and g(m) n X). So assuming (ii) weproved (over RCA ) the statement: "If f,g : N 3 N are 1-1 functions and f(n) 0= g(m) [m,n m N, then ]X[m(f(m) m X and g(m) n X)." But, over RCA , this is C0 ~equivalent to weak Konig's Lemma (see Lemma 3.2 in [2]) and, hence, we aredone. Ey.Q2 !References !__________[1] O. Endler, Valuation Theory, Springer-Verlag, 1972.[2] H. Friedman, S. Simpson, R. Smith, Countable algebra and set existence axioms, Annals of Pure and Applied Logic, 25 (1983), pp. 141-181; addendum, 27 (1983), pp. 319-320.[3] S. Simpson and R. Smith, Factorization of polynomials and 0 S induction, Annals of Pure and Applied Logic, 31 (1986), pp. 289-306. 1[4] S. Simpson, Ordinal numbers and the Hilbert Basis Theorem, Journal of Symbolic Logic, to appear.[5] R. Smith, Splitting algorithms and effective valuation theory, Aspects of Effective Algebra, ed. by J. N. Crossley, Upside Down A Book Company, 1980.