55
$\begingroup$

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.

$\endgroup$
17
  • 4
    $\begingroup$ Mostly I'm interested in examples that lie between "transparently obvious how to remove dependence on choice" and "major new idea needed to remove dependence on choice". But what I find interesting may be different from what others find interesting, so let a thousand flowers bloom. $\endgroup$ Feb 17 at 21:22
  • 3
    $\begingroup$ The snake lemma is an interesting case where I'm not sure if the habitual proof where you choose an inverse image should be counted as using the axiom of choice. (If you choose at once an inverse image for each element, you are unnecessarily using Choice, but if you, for each element, choose an inverse image, follow it around the diagram, observe that the destination doesn't depend on your choice, and then map the element to the unique value that works for every choice, you aren't.) $\endgroup$
    – Will Sawin
    Feb 17 at 21:31
  • 5
    $\begingroup$ Zorn's lemma is sometimes invoked to show that the maximal atlas (in the definition of differentiable manifolds) exists, but it is unnecessary. $\endgroup$
    – Z. M
    Feb 17 at 21:32
  • 3
    $\begingroup$ Unfortunately I lost my laptop charger, so I have to use my phone. There are several examples I can give, and will do so once I am back home. $\endgroup$
    – Asaf Karagila
    Feb 18 at 0:58
  • 5
    $\begingroup$ Doyle and Conway's division by three paper. $\endgroup$
    – Jim Conant
    Feb 18 at 3:04

13 Answers 13

40
$\begingroup$

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.

$\endgroup$
1
  • 12
    $\begingroup$ Thanks. I think I'd count that as an example where a significant new idea was needed to pass from the proof using choice to the proof without. As I understand the history, Cantor first proved the theorem using the same proof as you, and only later did Bernstein find a choice-free proof, which was entirely different. (Schröder's only contribution was a wrong proof which he later retracted, but somehow his name stuck -- at least in English. The French, more accurately, call it the Cantor-Bernstein theorem.) $\endgroup$ Feb 17 at 22:02
31
$\begingroup$

It's common to use the axiom of choice to prove that nonzero commutative rings have the invariant basis number property: in other words, that for a nonzero commutative ring $ R $, the $ R $-modules $ R^m $ and $ R^n $ are isomorphic if and only if $ m = n $.

The most common proof of this uses Zorn's lemma to find a maximal ideal $ \mathfrak m $ of $ R $. We can then tensor any isomorphism $ R^m \to R^n $ with $ R/\mathfrak m $ to get an isomorphism of $ R/\mathfrak m $-vector spaces $ (R/\mathfrak m)^m \to (R/\mathfrak m)^n $, which implies $ m = n $ by linear algebra since $ R/\mathfrak m $ is a field.

In fact, however, using Zorn's lemma is unnecessary. One way to see this is by looking at the exterior powers of the modules $ R^n $. The exterior power $ {\bigwedge}^n R^n $ is nonzero because the determinant $ (R^n)^n \to R $ is a surjective map that factors through $ {\bigwedge}^n R^n $, while $ {\bigwedge}^m R^n $ is obviously zero for $ m > n $. Therefore the rank of a free module over a nonzero commutative ring corresponds to its highest order exterior power that doesn't vanish, proving the difficult part of the claim that $ m \neq n $ implies $ R^m \ncong R^n $.

$\endgroup$
3
  • $\begingroup$ What about free modules of infinite rank? $\endgroup$
    – Blazej
    Feb 18 at 20:19
  • 3
    $\begingroup$ @Blazej I'm not even certain if you can get away with dimension being well-defined for vector spaces in the absence of choice. (You of course can't get a basis for every vector space without choice, but I'm not sure if you can show that given there are two infinite bases of a vector space, they must be of equal cardinality.) $\endgroup$
    – Ege Erdil
    Feb 18 at 20:49
  • 8
    $\begingroup$ In fact, it is consistent with ZF that there are vector spaces with bases of different cardinality: mathoverflow.net/questions/402010/… $\endgroup$
    – tj_
    Feb 18 at 21:30
22
$\begingroup$

A good number of theorems in Ramsey theory and related areas are what logicians call $\Pi^1_2$ statements—those of the form "for every set of integers $X$ there is a set of integers $Y$ satisfying some property which only quantifies over integers". Often, the easiest proofs of these results use AC, e.g. in the guise of using a nonprincipal ultrafilter or using nonstandard methods. But a consequence of Shoenfield's absoluteness theorem is that no theorem of this form can require choice for its proof.

A good example of this is Hindman's theorem (any finite coloring of $\mathbb N$ admits an infinite set whose set of finite sums is monochromatic). There's a very nice, quick proof through idempotent ultrafilters, which of course need (a fragment of) AC. There is an elementary proof, but it is much more involved and intricate, requiring you to do all the bookkeeping details by hand.

$\endgroup$
18
$\begingroup$

Turning ZM's comment into an answer: Zorn's lemma is sometimes invoked to show that the maximal atlas (in the definition of differentiable manifolds) exists, but it is unnecessary.

(This question is community wiki.)

$\endgroup$
1
  • $\begingroup$ I've presented this in a graduate course without being aware of the math.SE answer you've linked. I had a faint memory this had been done in some textbook, but cannot recall which one (if it exists at all). What I did was essentially the same as in the math.SE answer (proving first that $C^r$-compatibility of $C^r$ atlases is an equivalence relation in order to show that the union of all $C^r$-compatible atlases is the maximal $C^r$-compatible atlas), but I only glossed over the set-theoretic subtleties regarding the set of all $n$-dimensional $C^r$ atlases on a given set. Thanks for the link! $\endgroup$ Feb 18 at 17:00
14
$\begingroup$

The existence of a Haar measure on any locally compact group was first proven by Weil using the axiom of choice. Cartan later supplied a choice-free proof.

Because the Haar measure is unique up to a scalar factor, this is an example where it seems "obvious" that choice really shouldn't be necessary.

If anybody wants to edit to sketch one or both of the proofs, that would be most welcome!

$\endgroup$
6
  • 9
    $\begingroup$ I'm sure you know this, Tim, but let me just record here that unique existence is no guarantee that AC is unnecessary. There's a whole MO question about this. $\endgroup$ Feb 18 at 13:25
  • 5
    $\begingroup$ @TomLeinster Yes, I certainly wasn't trying to suggest that there should be a general metatheorem saying that unique existence should imply independence of choice, but I didn't actually know any counterexamples, so thanks for the link! $\endgroup$
    – Tim Campion
    Feb 18 at 16:41
  • $\begingroup$ Related to the comment above: does the adjoint functor theorem rely on the axiom of choice? Or weaker, the criterion for representable presheaves? It is also "unique" in some sense. $\endgroup$
    – Z. M
    Feb 18 at 19:43
  • $\begingroup$ @Z.M No, the adjoint functor theorems (whether SAFT or GAFT or some variant) don't use choice. $\endgroup$
    – Todd Trimble
    Feb 18 at 21:28
  • 1
    $\begingroup$ @ToddTrimble: morally the AFT doesn’t require choice — but it’s often stated in the literature in forms that do require choice, by taking the completeness assumption as mere existence of limits, but requiring an actual functor in the conclusion. Of course the real culprit here is a mismatched choice of definitions — the “universal object” conditions should either all be stated as chosen functions (so the input includes chosen limits) or all stated as mere existence conditions (so the output is representability conditions, or an adjoint anafunctor). $\endgroup$ Feb 20 at 10:17
12
$\begingroup$

It is easy to prove the following in Z+CC (Zermelo plus countable choice):

Every uncountable closed set of reals is in bijection with the reals.

I was informed by Asaf that it can be proven in ZF (no choice at all), but that proof appears to use replacement. I hence asked whether it could be proven in just Z, but till today there has been no answer. And whether the answer is yes or no, it would be very interesting. If yes, then the proof is likely to be far from obvious, maybe even not previously known. If no, then we have a theorem that needs either choice or replacement over Z, despite those two principles seeming to be completely unrelated.

$\endgroup$
2
  • 2
    $\begingroup$ This is provable in $Z,$ even in second-order arithmetic. The principle $ATR_0$ is equivalent to every uncountable closed set in a Polish space containing a perfect subset. $\endgroup$ Feb 18 at 21:42
  • 2
    $\begingroup$ The bijection is definable. I've posted an answer to the linked question. $\endgroup$ Feb 19 at 22:12
10
$\begingroup$

I've seen Tychonoff's theorem be used to prove that the $ p $-adic integers are compact. The proof is easy: there is a natural embedding

$$ \mathbb Z_p \to \prod_{k=1}^{\infty} (\mathbb Z/p^k \mathbb Z) $$

whose image is closed, and the infinite product is compact by Tychonoff, so in particular we deduce that $ \mathbb Z_p $ is compact. (This strategy is used in general to show other profinite objects are compact, for instance, infinite Galois groups under the Krull topology.)

The use of Tychonoff (and by extension the axiom of choice) is unnecessary: we can simply adapt the usual proof of Heine-Borel over $ \mathbb R $ to show that $ \mathbb Z_p $ is compact. If there is an infinite open cover with no finite subcover, we can find an infinite descending chain of closed balls in $ \mathbb Z_p $ intersecting at a single point that need infinitely many open balls to cover them, and since an open ball including the single point will cover all sufficiently small closed balls including that point, we get a contradiction.

$\endgroup$
5
  • 4
    $\begingroup$ There is also a simple embedding $\mathbb Z_p \to \mathbb R$ whose image is closed and bounded - send $\sum_i a_i p^i$, $a_i \in \{0,\dots, p-1\}$, to $\sum_i a_i / (2p-1)^i$ $\endgroup$
    – Will Sawin
    Feb 18 at 13:01
  • $\begingroup$ @WillSawin Yes, that works also. $\endgroup$
    – Ege Erdil
    Feb 18 at 13:04
  • 2
    $\begingroup$ The usual textbook presentations of the usual proof of Heine–Borel for $\mathbb R$ invoke the axiom of dependent choice. It could be avoided by a preferred choice of a well-ordering of $\mathbb Q$, although this does not seem to be quite natural. $\endgroup$
    – Z. M
    Feb 18 at 14:11
  • 1
    $\begingroup$ @Z.M What do you mean by the "usual" proof of Heine-Borel for $\mathbb{R}$? There are several common proofs. $\endgroup$ Feb 18 at 15:50
  • 1
    $\begingroup$ @TomLeinster Maybe I thought of the proof that Cauchy-complete totally bounded uniform spaces are compact, forgetting that in this special case one could bisect. $\endgroup$
    – Z. M
    Feb 18 at 19:13
9
$\begingroup$

Many uses of Zorn's lemma really only need transfinite recursion, without any use of AC. Sometimes you don't even need transfinite recursion, but just normal recursion, or even less.

This is especially applicable in specific examples. For instance, you don't need AC to get an algebraic closure of $\mathbb{Q}$.

$\endgroup$
8
  • 1
    $\begingroup$ What about the algebraic closure of a countable field? I have a vague memory that this is another case that doesn't need as much AC as generally advertised. $\endgroup$ Feb 18 at 4:52
  • 3
    $\begingroup$ @DavidRoberts perhaps you are recalling this answer? math.stackexchange.com/a/115060 $\endgroup$ Feb 18 at 5:13
  • 1
    $\begingroup$ Chasing references back, I get to this posting of Stephen Simpson cs.nyu.edu/pipermail/fom/2006-May/010538.html claiming the result, where he refers back to his RM book. $\endgroup$ Feb 18 at 6:29
  • 7
    $\begingroup$ Maybe I'm overlooking something obvious, but to construct an algebraic closure of $\mathbb{Q}$ without using either transfinite induction or choice, can't I just take the set of elements of $\mathbb{C}$ algebraic over $\mathbb{Q}$? $\endgroup$ Feb 18 at 12:17
  • 4
    $\begingroup$ @TomLeinster: You're not missing anything at all. $ℝ$ and $ℂ$ are very special; you don't need AC to prove that $ℂ$ is an algebraic closure of $ℝ$ either! What is more interesting is that any arbitrary countable field (e.g. $ℚ(t)$ where $t$ is an indeterminate) has an algebraic closure (i.e. an algebraic extension that is closed under algebraic extension), without relying on choice. $\endgroup$
    – user21820
    Feb 18 at 15:39
5
$\begingroup$

One of my papers, A comment on the construction of the maximal globally hyperbolic Cauchy development, did this for the existence of the maximal globally hyperbolic Cauchy development for the initial value problem in general relativity.

The TL;DR is that the original proof had a gratuitous use of Zorn's lemma. The fix is similar, but also somewhat different from, the fix removing the use of Zorn from maximal atlases.

$\endgroup$
1
  • $\begingroup$ (To my mind whether this is "non-topology" is slightly questionable...) $\endgroup$ Feb 18 at 16:54
5
$\begingroup$

The supremum of an arbitrary set of measurable functions from a $\sigma$-finite measure space into $\mathbb R\cup \{\pm\infty\}$ exists in the following sense:

Let $F$ be a set of such measurable functions. Then there is measurable $g$ such that $f\le g$ a.e. for all $f\in F$. And if $h$ is such that $f\le h$ a.e. for all $f\in F$, then $g\le h$.

The trick is that the inequalities are required in the a.e. sense. I have seen proofs that use Zorn's lemma (which is tempting), but there is a proof without it (see, e.g., Bogachev's monograph on measure theory, it uses monotone convergence). The result is also surprising because many properties in measure/integration theory have countability built-in.

$\endgroup$
4
$\begingroup$

It is a theorem of ZF that every sequentially continuous function $\mathbb{R}\to\mathbb{R}$ is continuous. The proof is usually given in ZFC (and indeed, Choice is necessary to assert that sequential continuity at a point implies continuity at that point), but a proof can be given in ZF that sequential continuity everywhere implies continuity everywhere: see Herrlich, The Axiom of Choice (2006), theorem 3.15 and subsequent remarks on page 30.

(The proof in ZF is bizarre and somewhat counterintuitive, and since it only works for continuity everywhere, it seems quite defensible to use Choice to prove this.)

$\endgroup$
2
  • 1
    $\begingroup$ I have considered mentioning (at least in a comment) that in Herrlich's book Section 3.2 is called Unnecessary Choice. However, the poster of this question excluded topology and the results in this section seem to be related to topology. In any case, the fact that for global continuity we do not need choice is certainly an interesting result - I'll add a link to a related post on Mathematics: Continuity and the Axiom of Choice. $\endgroup$ Mar 2 at 10:10
  • 1
    $\begingroup$ The proof in the book is neat, but it is also not hard to adapt textbook proofs to this case. Indeed, suppose that $f$ is sequentially continuous at $x$. Suppose that there exists $r>0$ such that, for every $n\in\mathbb N$, there exists a point $u\in B(x,1/n)$ such that $d(f(u),f(x))>r$. Then by sequential continuity of $f$ at $u$, there exists a rational number $v\in B(x,1/n)$ such that $d(f(v),f(x))>r/2$, and we can choose $v_n$ to be the greatest rational number $v\in B(x,1/n)$ such that $d(f(v),f(x))>r/2$ with respect to a well-ordering of $\mathbb Q$. $\endgroup$
    – Z. M
    Mar 2 at 12:31
3
$\begingroup$

My favourite example is from Reverse Mathematics, namely Pincherle's theorem stating that

a locally bounded function on Cantor space is bounded there.

The obvious proof proceeds by contradiction and uses AC:

  1. Suppose $F:2^\mathbb{N}\rightarrow \mathbb{N}$ is unbounded, i.e. $(\forall n\in \mathbb{N})(\exists f \in 2^{\mathbb{N}})(F(f)>n)$.

  2. Apply (countable) choice to obtain a sequence $(f_n)_{n\in \mathbb{N}}$ such that $F(f_n)>n$ for all $n \in \mathbb{N}$.

  3. Use the sequential compactness of Cantor space to show that this sequence has a subsequence $(g_n)_{n\in \mathbb{N}}$ which converges to $g\in 2^\mathbb{N}$.

  4. Since $F$ is locally bounded, $F$ is bounded in a neighbourhood of $g$. However, as $n$ increases, $g_n$ approaches $g$ and $F(g_n)$ becomes arbitrary large. Contradiction.

There is a proof in ZF (and weaker systems) that is more delicate:

in step 2., one considers:

$(\forall n\in \mathbb{N})(\exists \sigma\in 2^{<\mathbb{N}})[(\exists f \in 2^{\mathbb{N}})(F(f)>n) \wedge \sigma = (f(0),..., f(|\sigma|) ]$.

One can apply `numerical choice' to obtain a sequence $(\sigma_n)_{n\in \mathbb{N}}$ such that:

$(\forall n\in \mathbb{N})[(\exists f \in 2^{\mathbb{N}})(F(f)>n) \wedge \sigma_n = (f(0),..., f(|\sigma_n|) ]$.

This `numerical' choice principle is provable in ZF. Now use the sequence $(\sigma_n)_{n\in \mathbb{N}}$ instead of the sequence $(f_n)_{n\in \mathbb{N}}$; the rest of the proof then can be modified to obtain a contradiction on the same way.

$\endgroup$
1
$\begingroup$

You can divide sets by two (or more): in classical ZF, if $A\sqcup A\simeq B\sqcup B$ then $A \simeq B$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.