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.

13more comments