Where is the Axiom of choice used?

Question

In Reid's commutative algebra, there is a proof of equivalent conditions of Noetherian rings, especially (1) The set of ideals of $A$ has the a.c.c. $\Rightarrow$ (2) Every ideal in $A$ is finitely generated. I highlighted the sentence that I'm curious about.

Proof) Pick $f_1 \in I$, then if possible $f_2 \in I \setminus (f_1)$, and so on. At each step, if $I \neq (f_1, \cdots, f_k)$, pick $f_{k+1} \in I \setminus (f_1,\cdots,f_k)$. Then by the a.c.c., the chain of ideals $(f_1) \subset (f_1,f_2) \subset \cdots \subset (f_1,\cdots,f_k) \subset \cdots$ must break off at some stage, and this can only happen if $(f_1,\cdots,f_k)=I$. This proof involves an implicit appeal to the axiom of choice.

Where the axiom of choice is used? Is it from constructing the infinite ascending chain?

Answer 1

You are using the Axiom of Dependent Choice to guarantee that there is a sequence of choices of elements $f_i$ that you can make. At no point can you guarantee that you are done, since the generating sets may be unbounded (that is, it's possible that for every $n$ there is an ideal that requires at least $n+1$, though finitely many, elements to be generated).

A way to see it more clearly (and not be dazzled by the fact that you seem to only need to make finitely many choices) is to prove the contrapositive: suppose that $A$ has an ideal $I$ that is not finitely generated. Then proceed as above, using the Axiom of (Dependent) Choice to ensure that you can select the entire sequence $f_1,\ldots,f_n,\ldots$ of elements with the property that $(f_1,\ldots,f_n)\neq(f_1,\ldots,f_n,f_{n+1})$ for each $n$, to get a strictly increasing infinite sequence of ideals. You really do need the Axiom of Dependent Choice here, because you do need to make all the (infinitely many) choices.

Of course, the full force of Choice is used when proving that a ring has ACC on ideals if and only if every nonempty set of ideals has maximal elements.

Answer 2

As lhf commented (and Arturo answered while writing this), we "choose" inductively at each step.

This is a very delicate point really, because at every finite step we can still pick elements without the axiom of choice (or any fragment). However in order to talk about a specific infinite chain we must have some choice.

Here is an example about inductive choice, which works through an infinite case, we build an ordered set whose cardinality is infinite:

• For $a_0$ choose $0$.
• If $a_n$ was chosen, choose $a_{n+1}$ to be $a_n + 1$ and define $a_{n+1}>a_k$ for all $k<n$.

The set $\{a_n\mid n\in\mathbb N\}$ with the order defined in the inductive step gives us an infinite set which is linearly ordered. In this case, the induction works even after the finite stages, we call this a transfinite induction.

However this is not always the case, in the absence of choice consider the perplexing case of Amorphous sets. $A$ is amorphous if and only if $A$ is not finite, and every subset is either finite or co-finite (i.e. sets whose complement is finite).

Now start the same basic induction:

• Choose $a_0\in A$,
• Assume $a_n\in A\setminus\{a_i\mid i<n\}$ and choose $a_{n+1}\in A\setminus\{a_i\mid i\le n\}$

This is all fine, and the induction holds for every finite stage - i.e. you can choose finitely many $a_n$ without a problem. However if you could choose $a_n$ for all $n$ then you have an infinite subset which is isomorphic to the natural numbers.

That is a contradiction. Why? We assumed the set has no infinite subset whose complement is infinite consider the subsets $\{a_{2n}\mid n\in\mathbb N\}$ and its complement - both sets contain infinitely many elements.

This gives us an example of a very similar induction which does not carry over into the infinite cases, i.e. it is not a transfinite induction.

In the proof you gave in the question we use the fact that we can define such infinite sequence, and that it did not stop after finitely many steps. This requires a fragment of choice - The Principle of Dependent Choice - as Arturo said, but this is used frequently through and the result is that without it for most standard [infinitary] mathematics can be found counterexamples (pathological but nonetheless), and with it you can develop most real analysis and "countable" mathematics as we know it.

This takes some time to get used to, and invariably most people use the axiom of choice almost blindly. It makes mathematics "work as we expect it to work" in most cases, and ensures that infinitary processes will work like finitary ones (e.g. choosing from an infinite sets we can always choose another element).