# The ascending tree condition

### 23 December 2001

Abstract.  A strengthening of the ascending chain condition allows a choice-free constructive development of the theory of Noetherian modules. Related topics in the theory of PID's and elementary divisor rings are also explored.

The theory of finitely generated modules over a Noetherian ring admits a satisfactory constructive development by considering finitely presented modules over a coherent Noetherian ring [5]. From a classical point of view, every finitely generated module over a Noetherian ring is finitely presented-in particular, every Noetherian ring is coherent-so this also provides an adequate classical theory. From a constructive point of view, being finitely presented, rather than finitely generated, is a stronger property that must be assumed even if the ring is a field. The definition of Noetherian used in [5] was the ascending chain condition on finitely generated ideals, in the form

If I1 Ì I2 Ì I3 Ì ¼ is a chain of finitely generated ideals, then there exists n such that In = In+1.

With this definition one can, for example, prove the Hilbert basis theorem: If R is a coherent Noetherian ring, then so is the polynomial ring R[X].

What role do (countable) choice axioms play in this development? In order to apply the ACC you have to construct a countable chain. This often requires choice. For example, to prove that a quotient of a Noetherian module is Noetherian, you lift a chain of finitely generated ideals from the quotient to the module. Because there is no canonical way to do that, unless the kernel is finitely generated, you have to invoke choice. Similar problems appear in showing that an extension of a Noetherian module by a Noetherian module is Noetherian.

The question arises as to whether these invocations of choice can be avoided. One interesting way to avoid choice is to replace the ACC by Noetherian induction:

If C is a set of finitely generated ideals with the property that a finitely generated ideal I is in C whenever all finitely generated ideals that strictly contain I are in C, then every finitely generated ideal is in C.

Such a theory was successfully developed by Jacobsson and Löfwall [4] including a proof of the Hilbert basis theorem. They required the ring to be strongly discrete (have a membership algorithm): if I is a finitely generated ideal, and x is an element, then either x Î I or x Ï I. This seems necessary and is reasonable for a theory that emphasizes strict inclusion of ideals. I have yet to learn to love this approach although I have tried, off and on, for many years.

In this paper I present an alternative way to avoid choice by modifying the chain condition. Instead of ascending chains, indexed by the natural numbers, we allow increasing functions on trees. The result is the ascending tree condition.

## 1  The ATC

An acceptable index set is a nonempty set A, with a binary relation a < b, such that for each a Î A there is b Î A with a < b. We will be interested in families of subsets Ia, indexed by A, which are increasing, that is, if a < b, then Ia Ì Ib. We say that an increasing family halts if there exist a < b in A with Ia = Ib.

By a tree we will mean a partially ordered set T with a least element 0 such that for each t Î T

• the set {s Î T:s £ t} is a finite chain, and

• there exists s Î T such that s > t.

So every tree is an acceptable index set. The set N of natural numbers is a tree. A more complicated example is the set of finite sequences of natural numbers partially ordered by extension.

A set C of subsets of a set satisfies the ascending chain condition (the ACC) if any increasing family of elements of C, indexed by the natural numbers N, halts. It satisfies the ascending tree condition (the ATC) if any increasing family of elements, indexed by a tree, halts. Of course ATC implies ACC. The point of using ATC, rather than ACC, is to avoid appeals to countable choice axioms. If you allow such appeals, then the two conditions are equivalent.

Theorem 1 In the presence of the axiom of dependent choices, ATC is equivalent to ACC.

Proof. Let T be a tree and It an increasing family of subsets indexed by T. By the axiom of dependent choices, we can construct a sequence t1 < t2 < t3 < ¼ in T. Define an increasing family In¢, indexed by N, by In¢ = Itn. By ACC, there exists n such that Itn = Itn+1.

It is often easier to construct an increasing family using an acceptable index set rather than a tree. That is the point of considering acceptable index sets. The following theorem shows that the two associated notions of Noetherian are equivalent.

Theorem 2 If a set C of subsets of a set satisfies the ATC, then any increasing family of elements of C, indexed by an acceptable index set, halts.

Proof. Let Ia be an increasing family of elements of C indexed by an acceptable index set A, and let a0 Î A. Let T be the set of nonempty finite sequences a0 < a1 < ¼ < an in A ordered by extension. Note that T is a tree with least element the one-element sequence a0. We get an increasing family Jt indexed by T upon setting J(a0,¼,an) = Ian. So there exist s < t in T such that Js = Jt. If the last elements of s and t are a and b respectively, then a < b and Ia = Ib.

The halting terminology is meant to be suggestive. We can think of an increasing chain In in C as being generated by successive steps of an algorithm, the condition that the algorithm halts being In = In+1. An increasing family indexed by a tree can be thought of as being generated by a nondeterministic algorithm with the same halting condition. There is a strong suggestion here of Brouwer's free choice sequences. A family indexed by a tree is essentially a slight modification of Brouwer's notion of a spread [3].

## 2  Noetherian modules

Define a Noetherian module to be a module that satisfies the ATC on finitely generated submodules. Clearly submodules of Noetherian modules are Noetherian.

Theorem 3 Quotients of Noetherian modules are Noetherian.

Proof. Let j:B® C be an epimorphism with B Noetherian. Let Cn be an increasing family of finitely generated submodules of C indexed by a tree N. Let I consist of pairs (n,A) with n Î N and A a finitely generated submodule of B that maps onto Cn. Set (n,A) < (n¢,A¢) if n < n¢ and A Ì A¢. Then I is an acceptable index set. Consider the family F(n,A) = A indexed by I. As B is Noetherian, there exist n < n¢ and A such that A maps onto both Cn and Cn¢, so Cn = Cn¢.

The obvious attempts to prove this theorem using ACC instead of ATC require choice unless kerj is finitely generated.

Theorem 4 If a module B maps onto a Noetherian module C with Noetherian kernel A, then B is Noetherian.

Proof. Let Fn be an increasing family of finitely generated submodules of B indexed by a tree N. Denote the map from B onto C by j. If m < n, and j(Fm) = j(Fn), then Fn = Fm+K for some finitely generated submodule K of A. Consider the set J consisting of triples (m,n,K) such that m < n and K Ì A is a finitely generated submodule such that Fn = Fm+K. Define (m,n,K) < (m¢,n¢,K¢) if n < m¢ and K Ì K¢.

We show that J is an acceptable index set. Suppose n0 Î N and K0 is a finitely generated submodule of AÇFn0. The set N¢ = {n Î N : n > n0} is an acceptable index set with a transitive order. Consider the increasing family j(Fn) Ì C indexed by N¢. As C is Noetherian, there exist m and n with n0 < m < n and j(Fm) = j(Fn). There is a finitely generated submodule K of A, containing K0, so that Fn = Fm+K. So J is nonempty, and is an acceptable index set. Set

 G(m,n,K) = K.
Then G is an ascending family of finitely generated submodules of A indexed by J. As A is Noetherian, there exist (m,n,K) and (m¢,n¢,K¢) in J with m < n < m¢ < n¢ and K = K¢. So K¢ = K Ì Fm¢ whence Fm¢ = Fn¢.

It follows that finite-rank free modules over a Noetherian ring are Noetherian. With just ACC, you seem to need strong discreteness and coherence to prove this without choice.

The Noetherian induction principle implies ATC.

Theorem 5 A strongly discrete module that admits Noetherian induction is Noetherian.

Proof. To show that every increasing family F, indexed by a tree N, halts, we proceed by Noetherian induction on F0. Choose j > 0 in N. If Fj = F0, then F halts. If Fj ¹ F0, then define F¢ to be the restriction of F to the subtree N¢ = {i Î N : i = j or i > j}. Note that j is the 0 element of N¢. Then F¢ is an increasing family indexed by the tree N¢ such that F0¢ = Fj strictly contains F0. So F¢ halts by the Noetherian induction hypothesis. Therefore F also halts.

## 3  The Hilbert basis theorem

Let R be a ring and consider the polynomial ring R[X], where X commutes with elements of R. Denote by R[X]n the set of polynomials of degree less than n (a rank-n free R-module). Let Ln(I) be the left ideal in R obtained by projecting IÇR[X]n onto the last coordinate of R[X]n (the coefficient of Xn-1). Let L(I) = Èn = 1¥Ln(I).

Theorem 6 If R is coherent, and I is a left ideal in R[X], then Lm(I) is finitely generated for each m £ n if and only if IÇR[X]n is finitely generated.

Proof. Suppose IÇR[X]n is finitely generated. If m £ n, then IÇR[X]m = (IÇR[X]n)ÇR[X]m. As R is coherent, if IÇR[X]n is finitely generated, then so is IÇR[X]m. But Lm(I) is a homomorphic image of IÇR[X]m.

Conversely, suppose Lm(I) is finitely generated for each m £ n. Then there is a finitely generated submodule M of IÇR[X]n such that Lm(I) = Lm(M) for each m £ n. We show that M = IÇR[X]n. Indeed, if f Î IÇR[X]m, then we can find g Î M such that f-g Î IÇR[X]m-1, and induction finishes the proof.

Heinzer and Papick [1] define the Kaplansky Property, (KP):

For each finitely generated ideal I of R[X], the ideals Ln(I), and the ideal L(I) = Èn = 1¥Ln(I), are finitely generated.

In view of Theorem 6, a key lemma [5, VIII Lemma 1.1] for the constructive proof of the Hilbert basis theorem shows that a coherent Noetherian ring satisfies KP. We give a shortened proof of the heart of that lemma.

Theorem 7 Suppose, for each n, that R[X]n is a coherent R-module satisfying the ACC on finitely generated submodules. Then R satisfies KP.

Proof. Let I be a finitely generated left ideal of R[X]. Let M0 be the R-submodule of R[X]n generated by a set of generators of I. Let Mi+1 = Mi+(XMi)ÇR[X]n, which is finitely generated because R[X]n+1 is coherent. If Mi+1 = Mi, then Mj = Mi for all j > i. Such an i exists because R[X]n satisfies the ACC on finitely generated submodules. Let M = Mi. We will show that M = IÇR[X]n and that L(I) = Ln(I).

Now I = åk = 0¥XkM. We will show by induction that

 æè t å k = 0 XkM öø ÇR[X]n = M and Ln+t(I) = Ln(I).
This is true for t = 0. Suppose it's true for t-1. Let f = åk = 0tXkmk with mk Î M for each k. The last coefficient of f Î R[X]n+t, is the last coefficient of mt Î R[X]n which is in Ln(I). If f Î R[X]n, then
 f = X t-1 å k = 0 Xkmk+1+m0 Î R[X]n
so
 X t-1 å k = 0 Xkmk+1 Î R[X]n and t-1 å k = 0 Xkmk+1 Î M
whence f Î M.

A few remarks about Theorem 7 are in order. Extensions of finitely generated coherent modules are coherent [5, III Theorem 2.5] so R[X]n is coherent if R[X]1 = R is. If R is Noetherian (ATC), then R[X]n has the ACC on finitely generated submodules, but without choice we don't know how to derive this from the weaker assumption of ACC on R. However, if R is also coherent and strongly discrete, then we can establish ACC by induction for R[X]n without choice because intersections remain finitely generated and strong discreteness allows us to choose the first place where a chain pauses.

The standard constructive treatments of the Hilbert basis theorem require that the ring also be coherent. So we need to prove inheritance of coherence from R to R[X] in order to iterate. It is desirable to show that strong discreteness is also inherited. That is the content of [5, VIII Lemma 1.3]. Although the ring R there was assumed to satisfy the ACC on finitely generated left ideals, the proof actually shows the following reformulation:

Theorem 8 [MRR VIII.1.3] If R is a coherent ring satisfying KP, then R[X] is a coherent ring. If, in addition, R is strongly discrete, then so is R[X].

It remains to consider the inheritance by R[X] of the Noetherian condition on R-the Hilbert basis theorem proper. Choice is used heavily in the proof in [5, VIII Theorem 1.5]. Using ATC eliminates this.

Theorem 9 If R is a coherent Noetherian ring, then so is R[X].

Proof. A left ideal I in R[X] is said to be supported by n if it is generated by a finite subset of R[X]n. Let It be an ascending family of finitely generated ideals of R[X] indexed by a tree T. If It is supported by n, then there are r > s > t such that IrÇR[X]n = IsÇR[X]n. So the index set T¢ consisting of pairs r < s in T with (r < s) < (u < v) if s < u and there is n so that Is is supported by n and IuÇR[X]n = IvÇR[X]n is acceptable. The family of finitely generated ideals I(r < s) = L(Is) indexed by T¢ is increasing. As R is Noetherian, there exist r < s < u < v in T and n so that Is is supported by n and IuÇR[X]n = IvÇR[X]n, with L(Is) = L(Iv). So L(Iu) = L(Iv) and Iv is supported by n whence Iu = Iv.

## 4  PID's

A principle ideal domain is a Noetherian Bézout domain, so a modification of the definition of Noetherian will have repercussions for PID's. One test to see if you have the right notion of a PID is to show that every PID is an elementary divisor ring. It suffices to diagonalize 2-by-2 matrices. Given a matrix

æ
ç
è
 a
 b
 ·
 ·
ö
÷
ø
construct s and t so that d1 = sa+tb divides both a and b. Then multiply by a matrix of determinant 1 on the right to get:
æ
ç
è
 a
 b
 ·
 ·
ö
÷
ø
æ
ç
è
 s
 -b/d1
 t
 a/d1
ö
÷
ø
= æ
ç
è
 d1
 0
 ·
 ·
ö
÷
ø
.
(*)
Now making a similar move on the left we get a matrix of the form
æ
ç
è
 d2
 ·
 0
 ·
ö
÷
ø
.
where the ideal (d1) is contained in (d2). Note that if (d1) = (d2), then d1 divides the entry below it in (*), so we can diagonalize by making that entry zero with an elementary row operation.. Alternating back and forth, we generate a sequence of elements d1,d2,d3,¼ so that (d1) Ì (d2) Ì (d3) Ì ¼. If (dn) = (dn+1) for some n, as guaranteed by ACC, then we can diagonalize.

The choice problem arises from the fact that the s and t in sa+tb = gcd(a,b) are not unique, so we need choice to form the infinite sequence d1,d2,d3,¼. The ideal generated by sa+tb is unique, but s and t enter into the construction of the new matrix. One could of course define a Bézout domain in terms of a function from R×R to R×R taking (a,b) to (s,t), rather than simply requiring the existence of (s,t) for each (a,b), but this seems unnatural in classical terms. Generally, I think it is desirable to take over classical definitions verbatim as much as possible.

If we have ATC instead of ACC, this proof goes through without choice. The index set here is the set of finite sequences (s1,t1), (s2,t2), ¼ (sn,tn) in R×R that do the row and column operations. The ideal indexed by such a sequence is the ideal generated by the upper left corner of the matrix after performing the n indicated operations. Note how this can be thought of as a nondeterministic algorithm for diagonalizing the matrix.

I had thought that this analysis of the proof that a PID is an elementary divisor ring sufficed to establish the superiority of ATC over ACC in a choiceless environment. In fact, it turns out that I was just looking at the wrong proof. Helmer [2] also worries about using ACC to prove that a ring is an elementary divisor ring, presumably for different reasons. He defines a Bézout domain to be adequate if, given a and c, we can write a = rs such that

1. (r,c) = 1, and

2. (s,t) = 1 if (t,c) = 1.

The two conditions say that you can construct a factor r of a that is maximal with respect to being relatively prime to c. Call an adequate ring superadequate if, instead of 2, it satisfies the stronger and simpler condition

• s divides cn for some n.

Theorem 10 A Bézout domain with ACC is superadequate.

Proof. Suppose a = rs with (r,c) = 1. Let s0 = s and si+1 = si/(si,c). Note that if we set Ii = (si), then Ii+1 = Ii : (c). When the ideals Ii pause we have (sn,c) = 1 and we set r¢ = rsn and s¢ = s/sn. Clearly s¢ divides cn.

An apparently weaker condition suffices to get an elementary divisor ring. Call a Bézout domain subadequate if, given d and (s1,s2) = 1, we can write d = d1d2 with (s1d1,s2d2) = 1. This is implied by adequate: Given a and (t,c) = 1, we can write a = rs with (tr,sc) = 1. The notion of subadequate arises naturally when one tries to construct an element of maximal order in the module presented by a 2-by-2 matrix (aij), that is, the module with generators x1 and x2, and relations a11x1+a12x2 = 0 and a21x1+a22x2 = 0.

Theorem 11 Any subadequate Bézout domain is an elementary divisor ring.

Proof. It suffices to show that if M is a simply presented R-module with generators x1 and x2, then M is a direct sum of two cyclic modules. As R is coherent, so is M [5, III Theorem 2.5]. As M is coherent, the annihilators of elements of M are principle, as are the annihilators of elements of M/Rm for any m Î M. Let Rri be the annihilator of xi and write ri = dsi with (s1,s2) = 1.

By hypothesis, we can write d = d1d2 so that (s1d1,s2d2) = 1. Then ri = d1d2si. The annihilator of d1x2 is Rd2s2, and the annihilator of d2x1 is Rd1s1, so the annihilator of d2x1+d1x2 is Rs1ds2, the least common multiple of the annihilators of x1 and x2. Thus the annihilator of d2x1+d1x2 annihilates M. Choose a1 and a2 so that a1d1-a2d2 = 1. Then d2x1+d1x2 and a1x1+a2x2 generate M. So we may assume that the annihilator of x1 annihilates M, that is, r1M = 0.

Let Rl = {r Î R:rx2 Î Rx1}. Then l divides r2 because r2x2 = 0 Î Rx1. If lx2 = mx1, then r1 divides (r2/l)m because (r2/l)mx1 = r2x2 = 0. But r2 divides r1, because r1x2 = 0, so l divides m. Then x1 and x2-(m/l)x1 are generators that exhibit M as a direct sum of two cyclic modules.

## References

[1]
HEINZER, WILLIAM J. AND IRA J. PAPICK, Remarks on a remark of Kaplansky, Proc. Amer. Math. Soc., 105 (1989) 1-9.

[2]
HELMER, OLAF, The elementary divisor theorem for certain rings without chain condition, Bull. Amer. Math. Soc. 49 (1943), 225-236.

[3]
HEYTING, AREND, Intuitionism, an introduction, North-Holland 1956.

[4]
JACOBSSON, CARL AND CLASFWALL, Standard bases for general coefficient rings and a new constructive proof of Hilbert's basis theorem, J. Symbolic Comput. 12 (1991), 337-371.

[5]
MINES, RAY, FRED RICHMAN AND WIM RUITENBURG, A course in constructive algebra, Springer Verlag 1988.

File translated from TEX by TTH, version 2.27.
On 24 Dec 2001, 09:19.