What examples are there of habitual but unnecessary uses of the axiom of
choice, in any area of mathematics except topology?
I'm interested in standard proofs that use the axiom of choice, but where
choice can be eliminated via some judicious and maybe not quite obvious
rephrasing. I'm less interested in proofs that were originally proved
using choice and where it took some significant new idea to remove the
dependence on choice.
I exclude topology because I already know lots of topological examples. For
instance, Andrej Bauer's Five stages of accepting constructive
mathematics
gives choicey and choice-free proofs of a standard result (Theorem 1.4):
every open cover of a compact metric space has a Lebesgue number. Todd
Trimble told me about some other topological examples, e.g. a compact
subspace of a Hausdorff space is closed, or the product of two compact
spaces is compact. There are more besides.
One example per answer, please. And please sketch both the habitual proof
using choice and the alternative proof that doesn't use choice.
To show what I'm looking for, here's an example taken from that paper of Andrej Bauer. It would qualify as an answer except that it comes from
topology.
Statement Every open cover $\mathcal{U}$ of a compact metric space
$X$ has a Lebesgue number $\varepsilon$ (meaning that for all $x \in X$, the
ball $B(x, \varepsilon)$ is contained in some member of $\mathcal{U}$).
Habitual proof using choice For each $x \in X$, choose some
$\varepsilon_x > 0$ such that $B(x, 2\varepsilon_x)$ is contained in some
member of $\mathcal{U}$. Then $\{B(x, \varepsilon_x): x \in X\}$ is a
cover of $X$, so it has a finite subcover $\{B(x_1, \varepsilon_{x_1}),
\ldots, B(x_n, \varepsilon_{x_n})\}$. Put $\varepsilon = \min_i
\varepsilon_{x_i}$ and check that $\varepsilon$ is a Lebesgue number.
Proof without choice Consider the set of balls $B(x, \varepsilon)$
such that $x \in X$, $\varepsilon > 0$ and $B(x, 2\varepsilon)$ is
contained in some member of $\mathcal{U}$. This set covers $X$, so it has
a finite subcover $\{B(x_1, \varepsilon_1), \ldots, B(x_n,
\varepsilon_n)\}$. Put $\varepsilon = \min_i
\varepsilon_i$ and check that $\varepsilon$ is a Lebesgue number.
Best Answer
Sometimes people prove the Schröder–Bernstein theorem by saying it follows easily from the well-ordering theorem, which is equivalent to the axiom of choice. But it can be proved without the axiom of choice. The theorem states that if there is a one-to-one mapping from each of two sets into the other, then there is also a bijection.