Elementary theorems that require AC

Question

It seems that AC is hiding (maybe concealed?) even in some elementary results. An example:

Theorem: Let $X \subseteq \mathbb R$ and let $x_0 \in \mathbb R$ be an accumulation point of $X$. Then there exists a sequence $ \{ a_n \}_{n=1}^\infty $ S.T. $ \{ a_n \} \subseteq X$ and $a_n\xrightarrow{n \to \infty} x_0 $.

Proof: For $\mathbb N \ni n > 0$ we denote $A_n := \{ x \in X : |x-x_0| < \frac {1}{n} \}$, since $x_0$ is an accumulation point of $X$ then $ \forall [ 0<n \in \mathbb N ] . A_n \neq \varnothing$.
By A.C. there exists choice function $f:P(X) \setminus \{ \varnothing\} \rightarrow X$ S.T. $\forall [ \varnothing\neq B \subset X] . f(B) \in B$
The sequence $\{ a_n \}$ defined by $a_n := f(A_n)$ satisfies the requirements.

• Can we avoid the use of AC in the Theorem above??
• Can you point out some elementary Theorems that require AC?

Answer 1

Yes, this proof uses countable choice. In an essential way, too. It is consistent (without choice) that there is a dense set if reals without a countably infinite subset. In particular every convergent sequence from that set must be eventually constant. But density means that every real is in the closure.

Other proofs that use the axiom of choice include:

1. Every infinite set has a countably infinite subset;
2. a set is finite if and only if every self-injection is a bijection;
3. the countable union of countable sets is countable; and
4. an infinite tree without maximal nodes, where every level is finite, has a branch.

Slightly less elementary proofs might include

5. Every vector space has a basis; and
6. a vector space is infinite dimensional if and only if its [algebraic] dual has a larger dimension.

The list is really quite large and can fill up several books.

Answer 2

An elementary result using the axiom of dependent choice:

Let $R$ be a ring. Then the statement:

"If $\mathfrak{a}_1 \subset \mathfrak{a}_2 \subset \cdots$ is a sequence of ideals of $R$, then there is $n$ such that for all $m>n$, $\mathfrak{a}_m=\mathfrak{a}_n$."

implies the statement:

"Every non-empty set of ideals of $R$ has a $\subset$-maximal element."

More generally, the implication "A poset $S$ has no infinite strictly descending chains" $\implies$ "$S$ is a well order" is equivalent to the axiom of dependent choice.

By the way, as Asaf mentioned, the axiom of dependent choice is a choice principle which is strictly stronger than the countable axiom of choice and strictly weaker than the axiom of choice.

Answer 3

As pointed out the theorem seem to require the AC, but there seem to be a way around this (in this particular case) by changing definition to:

$x$ is a accumulation point to $X$ if there is a sequence $x_n\in X$ such that $lim_{n\to\infty}x_n = x$.

Then of course the theorem will be trivial to prove. The reverse (that every neighborhood of $x$ intersects $X$) is provable (since the sequence $x_n$ must eventually be confined to any given neighborhood of $x$).

I guess that this is the case for all "elementary" theorem that requires the AC that they can be "solved" by shifting a definition to a version that is equivalent under AC, but only implying the original defining property without AC. In most "elementary" applications to the theory you would probably have an explicit way of doing your choice that's required for the modified definition so you can get away without AC.