REHMTN WKL AND ORDERINGS OF COUNTABLE ABELIAN GROUPS 0 $by Kostas Hatzikiriakou $and Stephen G. Simpson Department of Mathematics The Pennsylvania State University University Park, PA 16802, USA March 1, 1988To appear in the Proceedings of the Conference on Logic and Computability,Carnegie-Mellon University, 1987, edited by Wilfried Sieg.This research was partially supported by NSF grant DMS-8701481..x1.P WKL AND ORDERINGS OF COUNTABLE ABELIAN GROUPS 0 $by Kostas Hatzikiriakou $and Stephen G. Simpson.Q4 #1. Introduction. ____________ This is another contribution to the program of Reverse Mathematics. C*The reader who is not familiar with this program nor with RCA , RCA and =0 0WKL , the weak subsystems of Z that we refer to in this paper, should 0 2study [2] and [4]. In [1], Downey and Kurtz used the technique of "building isomorphicstructures" of Ash and Nerode to construct a torsion-free abelian groupwhich cannot be recursively ordered, thus refuting the recursive analog ofLevi's Theorem: "An abelian group is orderable if and only if it istorsion-free" (see [3]). In this paper, using the techniques of Reverse Mathematics, we establishthe precise logical strength of Levi's Theorem for countable abelian groups.Over RCA , Levi's Theorem for countable abelian groups is equivalent to Weak 0 ~Konig's Lemma. From this the above mentioned result of Downey and Kurtz $~follows as a corollary, since Weak Konig's Lemma does not hold in the w-modelof RCA consisting of the recursive sets. 0 This research was partially supported by NSF grant DMS-8701481. #2. The Main Theorem. ________________ 2.1. Definitions (RCA ). Let A be a countable abelian group. A is ___________ 0torsion-free if for all a m A\{0} and for all n m N\{0}, n.a = 0. A isorderable if there exists a linear ordering , on A such that for alla, b, c m A, a , b implies a + c , b + c. 2.2. Remark. Let A be a countable ordered abelian group. Since RCA ______ 90 0includes D comprehension, we can prove within it the existence of the 1positive cone P of A, P = {a: a , 0}. Note that (a) P is closed underaddition, (b) P f -P = {0}, and (c) P g -P = A, where -P = {a: -a m P}.Conversely, given a countable abelian group A and a subset P of A withthe above properties, we can define (within RCA ) the linear ordering 00a , b iff b - a m P; this makes A a countable ordered abelian group. 2.3. Lemma (WKL ). Let A be a torsion-free countable abelian group. _____ 0Then A is orderable. Proof. Let a ,a ,... be an enumeration of A\{0}. We define a tree T _____ 0 1of finite sequences of 0's and 1's. Also, for each s m T, we define a finiteset P { A such that if s is an initial segment of t, then P is a subset of s 7sP . At stage s, T = {s m T: lh(s) = s} is defined. For s = 0, T = {O} t s 20and P = O. Assume that T has been defined. The definition of T splits O s-1 'sinto three cases. Let s = 3m + r, 1 , r , 3. Every natural number m encodesa triple of natural numbers (i,j,k). Assume that s m T . 7s-1Case 1. r = 1. Put s0 m T . Define P = P unless m = (i,j,k) and______ s s0 sa m P , a m P , in which case define P = P g {a + a }. i s j s s0 s i jCase 2. r = 2. Put s0 m T and define P = P , unless m = (i,j,k) and______ s s0 sa + a = 0 in which case put s0 m T and s1 m T and define P = i j s s s0P g {a } and P = P g {a }. s i s1 s jCase 3. r = 3. If 0 n P , put s0 m T and define P = P . If 0 m P ,______ s s s0 s sdo not put s0 nor s1 in T and do not define P nor P . s s0 s1 Claim (RCA ). T is infinite. _____ 0 0 To see this, consider the P formula 1 v(s) = ]s m T (0 n ;P :), )s swhere ;P : is the subsemigroup of A generated by P . For s = 0 we have T = s )s 0{O} and P = O and thus v(0) holds. Assume v(s-1) and let s m T be such O 6s-1that 0 n ;P :. In cases 1 and 3, ;P : = ;P : and thus v(s) holds. For s s s0case 2, assume towards a contradiction that 0 m ;P : and 0 m ;P :, where 2s0 s1P = P g {a} and P = P g {-a}, for some a m A\{0}. Since 0 n ;P :, we s0 s s1 s +shave 0 = k.a + T k .a +i i &imIand 0 = l.(-a) + T l .a .j j )jmJwhere I and J are finite sets, a , a m ;P : and k, l, k , l m N\{0}. !i j s i jSince A is torsion-free, we must have k.a = 0 and l.a = 0. Hence I and J arenonempty. Thus 0 = T l.k .a + T k.l .a m ;P : , imI i i jmJ j j s 70a contradiction. Thus v(s) holds even in case 2. By P induction, it follows 71that v(s) holds for all s m N. Hence T is infinite. ~ By Weak Konig's Lemma, let g be a path through T. Let P = g P , where s Bs sranges over all finite initial segments of g. Note that on the one hand P is 0defined by a S formula and on the other hand, for a = 0, a m P iff -a n P. 1 0Hence P exists by D comprehension, and clearly P g {0} is a positive cone for 1A. This completes the proof of Lemma 2.3. 2.4. Lemma (RCA ). Any countable orderable abelian group is _____ 0torsion-free. 0 Proof. By S induction. Let a m A\{0}. Then a < 0 or a > 0. If _____ 1a > 0, then 1.a = a > 0 and if n.a > 0, then (n + 1).a = n.a + a > 0 + a= a > 0. If a < 0, then 1.a = a < 0 and if n.a < 0, then (n + 1).a =n.a + a < 0 + a = a < 0. 2.5. Theorem. (RCA ). The following are equivalent: _______ 0 ~ (1) Weak Konig's Lemma. (2) Levi's Theorem for countable abelian groups, i.e. "A countableabelian group is orderable if and only if it is torsion-free". Proof. (1) ek (2) follows from the previous lemmas. It remains to prove _____(2) ek (1). We argue in RCA . Let f, g: N -3 N be 1-1 functions such that 0f(m) = g(n) for all m, n m N. Let A be the countable abelian group withgenerators y, x (m m N) and relations m p .x - y = 0 and p .x + y = 0 (n m N), 2n+1 f(n) 2n+2 g(n)where p = 2, p = 3, ... is the enumeration of the prime numbers in 0 1increasing order. Claim (RCA ). A exists and it is torsion-free. _____ 0 To prove this, note that any element a of A can be written uniquely inthe form a = c.y + T a .x *i i %imIwhere I is a finite subset of N, c m Z, a m Z, a = 0 for all i m I, and )i i b (]i m I) ]n [(p , 2.|a | c f(n) = i) d (p , 2.|a | c g(n) = i)]. 2n+1 i 2n+2 i )0The set of these normal forms exists by D comprehension, and hence A exists. )1To see that A is torsion-free, let a = c.y + T a .x be a nonzero element /imI i iof A in normal form and assume, towards a contradiction, that there is somel m N\{0} such that l.a = 0. This implies that for all i m I there existsn m N such that either i = f(n) and p divides l.a , or i = g(n) and p %2n+1 i 2n+2divides l.a . Set q = p or -p as the case may be. Note that the i i 2n+1 2n+2 --1q , i m I, are all distinct. Since |a | < 2 .|q |, we see that q divides l i %i i i G-1and the coefficient of y in the normal form of l.a is l.c + T l.a .q = 0. =imI i i $-1Dividing by l, we get c + T a .q = 0. Setting q = Q q and imI i i imI i * -1 *q = q.q , we see that c.q + T a .q = 0. But then, for all i m I, i i imI i i 1-1q divides a . This is impossible since |a | < 2 .|q |. Hence I = O, hence i i i il.c = 0, hence c = 0, hence a = 0, a contradiction. Thus A is torsion-freeand our claim is proved. By our assumption (2), A is orderable, so let P be a positive cone.Let S = {m: x m P}. Then, for all n, x m P if and only if y m P, and m f(n)x m P if and only if y n P. Thus S separates the ranges of f and g. g(n) *~Hence, by Lemma 3.2 in [2], we have Weak Konig's Lemma. This completes theproof of the theorem. 2.6. Remark. A slightly different proof of Lemma 2.3 could be given ______along the following lines. First, prove in RCA that every finitely /0generated torsion-free abelian group is of the form p Z. (We conjecture 6i