# Factorial Rings and The Axiom of Choice

It is shown in Lang's Algebra (and many other books I assume) that:

if A if a principal entire ring, then A is a factorial ring.

The proof uses Zorn's Lemma. Is this theorem equivalent to the axiom of choice?

Lang uses Zorn's lemma only in the step that nonzero nonunits in a PID admit irreducible factorizations (not the uniqueness of irreducible factorizations, once we know such factorizations exist). The way he uses Zorn's lemma, I think, is excessive. What follows is how I work out the existence of irreducible factorizations when I teach the abstract algebra class.

Claim: In a PID which is not a field, any nonzero nonunit is a product of irreducibles.

We will use the following lemma (which is not Zorn's lemma).

Lemma: If $R$ is an integral domain and $a \in R$ is a nonzero nonunit which does not admit a factorization into irreducibles then there is a strict inclusion of principal ideals $(a) \subset (b)$ where $b$ is some other nonzero nonunit which does not admit a factorization into irreducibles.

Proof of lemma: By hypothesis $a$ is not irreducible, so (since it is neither 0 nor a unit either) there is some factorization $a = bc$ where $b$ and $c$ are nonunits (and obviously are not 0 either). If both $b$ and $c$ admitted irreducible factorizations then so does $a$, so at least one of $b$ or $c$ has no irreducible factorization. Without loss of generality it is $b$ which has no irreducible factorization. Since $c$ is not a unit, the inclusion $(a) \subset (b)$ is strict. QED lemma.

Now we can prove the claim.

Proof of claim: Suppose there is an element $a$ in the PID which is not 0 or a unit and has no irreducible factorization. Then by the lemma there is a strict inclusion $$(a) \subset (a_1)$$ where $a_1$ has no irreducible factorization.
Then using $a_1$ in the role of $a$ (and the lemma again) there is a strict inclusion $$(a_1) \subset (a_2)$$ where $a_2$ has no irreducible factorization. This argument (repeatedly applying the lemma to the generator of the next larger principal ideal) leads to an infinite increasing chain of principal ideals $$(a) \subset (a_1) \subset (a_2) \subset (a_3) \subset \cdots$$ where all inclusions are strict. (At this step I suppose you may say we need the Axiom of Choice to get an infinite ascending chain, but it's only countably many choices, so really not the full thrust of Zorn's lemma and in any case it feels like a less pedantic use of Zorn's lemma than the way Lang does this.) Such a chain of ideals is impossible in a PID.

Indeed, suppose a PID contains an infinite strictly increasing chain of ideals: $$I_0 \subset I_1 \subset I_2 \subset I_3 \subset \cdots$$ and set $$I = \bigcup_{n \geq 0} I_n.$$ This union $I$ is an ideal. The reason is that the $I_n$'s are strictly increasing, so any finite set of elements from $I$ lies in a common $I_n$. Therefore $I$ is closed under addition and arbitrary multiplications from the ring since each $I_n$ has these properties. Because we are in a PID, $I$ is principal: $I = (r)$ for some $r$ in the ring. But because $I$ is the union of the $I_n$'s, $r$ is in some $I_N$. Then $(r) \subset I_N$ since $I_N$ is an ideal, so $$I = (r) \subset I_N \subset I,$$ which means $$I_N = I.$$ But this is impossible because the inclusion $I_{N+1} \subset I$ becomes $I_{N+1} \subset I_N$ and we were assuming $I_N$ was a proper subset of $I_{N+1}$. Because of this contradiction, nonzero nonunits in a PID without an irreducible factorization do not exist. QED

Lang's argument only uses the axiom of choice in a countable way, as above, but the way he pulls it in makes the application of Zorn's lemma feel a lot more fussy.

• You are using Dependent Choice, rather than Countable Choice, since the later choices depend on the earlier choices. The DC principle is intermediate in strength between Countable Choice and full AC. May 14 '10 at 0:28
• Does this answer the question of whether the ring theorem is equivalent to DC? Can you prove DC from the theorem on rings? I thought this (except for the distinction between AC and DC) was what the original question was about. May 14 '10 at 1:08
• The reason I wrote the above proof is not because I was trying to simplify what is in Lang, but because I was teaching the course using Dummit and Foote's book and noticed their reasoning behind existence of irreducible factorizations in PIDs is wrong. (Look on p. 288 of their 3rd edition and think carefully about the first paragraph.) I aimed to fix what D&F were trying to do, rather than just pull another book off the shelf and use its argument instead. This was about three years ago (and I just cut and pasted what was in my .tex file to generate the answer here when I read the question). May 14 '10 at 1:16
• Gerry, since the ideals in a PID each only require a single generator, whether or not they're constructed that way at first, my gut feeling is that Dependent Choice is not a consequence of irreducible factorizations in all PIDs. Hopefully Joel or others more expert on such matters than I can follow up. May 14 '10 at 1:21
• Gerry, this answer answers the question about whether the fact is equivalent to AC, and it is not, since it is provable from DC, which is weaker than AC. But you are right, the answer raises the question whether the fact is equivalent to DC. May 14 '10 at 1:24

This is an extended comment on Keith's answer:

Another way to think about Keith's argument (or the more general argument for the existence of minimal primes in Noetherian rings) is that one constructs a tree as follows: beginning with an ideal $I$, if it not prime then we may find $J_1, J_2$ properly containing $I$ such that $J_1 J_2 \subset I$, and we make a "factorization tree" joining $I$ to $J_1$ and $J_2$, and then iterate this procedure.

Noetherianness says that each branch of the tree has finite length, and since each edge has finite valence, the whole tree is finite, hence we eventually must reach prime ideals, and we find a finite collection of prime ideals $P_i$ whose product is contained in $I$.

The fact about trees being used can be phrased (in the contrapositive) as: an infinite tree with every vertex of finite valence has an infinite branch. (This has a name, which I forget; it is also what underlies the proof of Bolzano--Weierstrass.) Now the proof of this fact uses DC (as far as I can tell), and it's probably well-known to logicians exactly whether or not it is equivalent to DC (or, at any rate, exactly how strong it is).

The question then becomes whether we can model any tree (whose internal vertices have valence 3) as a factorization tree (in a PID, say, although the possibility of allowing more general Noetherian rings seems reasonable, at least if it helps to give a positive answer).

Added: The result on trees is called Koenig's lemma. (Thanks to Artie Prendergrast-Smith for this.)

I should also note that my original movitation for formulating the above argument was similar to that of Keith: the usual proof of the existence of minimal primes in Noetherian rings uses Zorn's lemma and has a non-constructive feel, whereas the above reformulation feels more concrete.

• I think the fact in question is known as Kőnig's Lemma.
– user5117
May 14 '10 at 10:17
• It is true that you use DC to find the infinite branch, but you are also using AC to build the tree in the first place, since for each I you have chosen $J_1$ and $J_2$. In the case of the question, this amounts to $|R|$ many choices, and this may not be possible just from DC. So I'm not sure that your last paragraph is correct. May 14 '10 at 12:30
• DC is equivalent to the assertion that every tree $T$ in which every node has at least one immediate successor (no need for finiteness) has an infinite branch. Each node of the tree points at the allowed "next" choices, and so the infinite branch is the sequence of choices. May 14 '10 at 12:33
• Dear Joel, Thanks for the corrections and comments. May 14 '10 at 14:43
• Dear Joel, But, if I fix a choice of $I$, isn't it just a question of using DC to construct the tree? May 14 '10 at 14:48