# Axiom of Choice and Ascending Chain Condition

Matsumura, in his "Commutative Ring Theory" p. 14 proves that "A partially ordered set $\Gamma$ satisfies the ascending chain condition $\Leftrightarrow$ every nonempty subset of $\Gamma$ has a maximal element."

In proving the $\Rightarrow$ direction, he uses the following argument: Consider a nonempty subset $\Gamma'$ of $\Gamma$. Suppose that $\Gamma'$ has no maximal element. Then "by the axiom of choice" for any $\gamma \in \Gamma'$ we can select an element $\phi(\gamma')$ such that $\phi(\gamma')> \gamma'$. In that way we obtain a nonterminating ascending chain $\gamma' < \phi(\gamma')<\phi^2 (\gamma') <\cdots$, contradiction."

My question is: why is the axiom of choice necessary here? Don't we already have by hypothesis (no maximal element exists) a rule $\phi : \Gamma' \rightarrow \Gamma'$ to assign to each $\gamma'$ the element $\phi(\gamma')$?

-
This has been covered on the site at least once or twice before... – Asaf Karagila Dec 11 '12 at 21:03

The Axiom of Choice is the mechanism that allows you to construct this rule/function. Even though you know that to each $\gamma \in \Gamma^\prime$ there is some $\gamma^\prime \in \Gamma^\prime$ greater than it, this only means that for each $\gamma$ the collection $$A_\gamma = \{ \gamma^\prime \in \Gamma^\prime : \gamma^\prime > \gamma \}$$ is nonempty. It does not provide you a means for constructing a rule to say for each $\gamma$ this is the element of $A_\gamma$ I want! The whole point of the Axiom of Choice is to be able to choose particular elements from possibly infinitely many different nonempty sets where there is no rule to uniformly select a unique element from each.

Note, also, that in this instance, since you are only concerned with generating an increasing sequence of elements of $\Gamma^\prime$, you could get away with using only the Axiom of Dependent Choice), which is quite a bit weaker.

-
This is another nice answer of yours. Plus one. – Rudy the Reindeer Dec 11 '12 at 21:08
Amazing answer, it helped me understand the axiom of choice better. Many thanks :) – Manos Dec 11 '12 at 23:05

No, "no maximal element" doesn't give you a choice function. A choice function is a function $\phi: \mathcal P(\Gamma')\setminus \{\varnothing\} \to \Gamma'$ such that $\phi(x) \in x \subset \Gamma'$ for all subsets $x$ of $\Gamma'$.

If $\Gamma'$ has no maximal element then for every $\gamma \in \Gamma'$ you can find $\gamma'$ such that $\gamma < \gamma'$. Then to construct your infinite ascending chain you use that together with a choice function as follows: start with an element $\gamma$ and consider the set of all elements that are bigger than it (which is non-empty since $\Gamma'$ has no maximal element). You use the choice function to pick an element from this set. To construct the infinite chain you need to make infinitely many choices which is the reason why you need a choice function. If you only made finitely many choices there would not be a need for a choice function.

Whenever you need to make infinitely many choices for which you cannot write down an explicit rule you need the axiom of choice. In this case, you have infinitely many sets from which you need to choose: the set of elements that are bigger than the ones you have already chosen.

-
Thanks. Plus one :) – Manos Dec 11 '12 at 23:11