Examples of Axiom of Choice used in introductory-level undergradute math

All of the applications of AoC I've encountered have been in upper level undergraduate or graduate math courses. Are there any basic results from courses like Calc I-III which (unbeknownst to students) rely on AoC?

• By Shoenfield absoluteness, any such statement would have to be at least properly $\Pi^1_3$ (since $\Sigma^1_3$ statements are absolute upwards from $L$). Off the top of my head, I can't think of a statement which is this complicated and appears in the standard calculus sequence. (Note that in many cases, an apparent quantifier over reals can be replaced with a quantifier over rationals - e.g. "$\forall\epsilon>0$" can often be replaced with "$\forall \epsilon>0,\epsilon\in\mathbb{Q}$" - thus bringing down the apparent complexity of the claim.) Dec 2 '17 at 3:08
• Does "Calc I-III" include something such as equivalence of continuity and sequential continuity in general metric spaces? Dec 2 '17 at 3:12
• @HenningMakholm Never mind general metric spaces, I believe you need choice to prove the equivalence for functions $f:\mathbb R\to\mathbb R.$
– bof
Dec 2 '17 at 3:34
• @bof: Hmm, you may be right about that. I imagined this was one of the cases where separable spaces can avoid needing choice, but on further thought that seems to be mistaken. Dec 2 '17 at 3:44
• @Henning: For separable numbers you can avoid countable choice if you talk about continuity everywhere, and not just at a single point. Dec 2 '17 at 8:46

The Axiom of Choice can be used to prove that every vector space has a basis. That's certainly a basic result from a linear algebra course but it's definitely not unbeknownst to students.

• Along the same line that every subspace $U \subseteq V$ has a complement $C$ such that $V = U \oplus C$. Dec 2 '17 at 3:25
• I think you mean to say that the axiom of choice is required to prove that every vector space has a basis, not merely that it can be used. (I believe this to be true, in the sense that "every vector space has a basis" isn't a theorem of ZF without choice, at least according to what a quick Google search showed up.) Dec 2 '17 at 8:51
• @Nathaniel Indeed, the fact that every vector space has a basis is equivalent (in ZF) to the axiom of choice. This is not immediate, but [Blass 84] has a proof. Dec 2 '17 at 9:07
• Well. In a linear algebra course, at least "basic level" one, all spaces are finite dimensional (with the exception, perhaps, of $\Bbb R$ over $\Bbb Q$ as an example for an infinite dimensional space). Dec 2 '17 at 10:38
• I was going to say that the first course a student takes that talks about bases might mention infinite dimensional spaces, but they might not get into what a Hamel basis is when the space is not spanned by a finite set. Dec 2 '17 at 16:30

The axiom of choice can be used to prove that the sequential definition of continuity at a point (for real functions of a real variable) is equivalent to the $\varepsilon$-$\delta$ definition. If your calculus textbook proves that sequential continuity implies epsilon-delta continuity without mentioning the axiom of choice, it's doing something like this:

. . . Then, for each $n\in\mathbb N,$ there is a real number $x_n$ such that $|x_n-x_0|\lt\frac1n$ while $|f(x_n)-f(x_0)|\ge\varepsilon.$ Thus the sequence $x_n$ converges to $x_0,$ while $f(x_n)$ does not converge to $f(x_0)$. . .

Do you see where I used the axiom of choice?

• Is it required? I don't recall it being used in my analysis course which proved that. Dec 2 '17 at 4:09
• @TorsionSquid - how did your analysis course prove that if $f(x_n) \to f(x)$ whenever $x_n \to x$, then $f$ is continuous? Dec 2 '17 at 5:47
• @TorsionSquid: In many analysis courses the lecturer fails to point out (or even realize) the use of choice. I recall that through a careful trick we can avoid the use of choice, but it will be different from the typical proof. But I can't recall the trick at this moment... I myself accidentally used it in this recent post. Dec 2 '17 at 8:44
• I will add that the fact that the two versions of continuity are equivalent if we are talking about global continuity can be shown without AC. However, the proof is more complicated. But if we are talking about continuity at a point, then the equivalence cannot be shown in ZF. More details (and some references) can be found, for example, here: Continuity and the Axiom of Choice. Dec 2 '17 at 9:25
• @user21820. Suppose $f$ is sequentially continuous at every point. If every $(x-1/n,x+1/n)$ contains some $y$ with $|f(x)-f(y))>\epsilon$ then, since there is a sequence in $\Bbb Q$ converging to $y$ so there exists $q\in (x-1/n,x+1/n)\cap \Bbb Q$ with $|f(y)-f(q)|<\epsilon / 2,$ hence $|f(q)-f(x)|>\epsilon /2 .$ Let $<_W$ be a well-order of $\Bbb Q.$ Let $q_n$ be the $<_W$-least $q\in (x-1/n,x+1/n)$ such that $|f(x)-f(q)|>\epsilon /2.$ Dec 2 '17 at 14:47

Here are two which you usually see in the first chapter of most intro to analysis books, and in many "quick set theory coverage" of the first couple of weeks:

1. Every infinite set has a countably infinite subset. Or equivalently, a set is finite if and only if every proper subset has smaller cardinality. Or equivalently, a set is infinite if and only if there is an injection which is not a surjection from the set to itself.

You need strictly less than countable choice to prove this, even though the standard and easy proof is using a bit more. But this is certainly not provable without any use of choice. Not even if these are sets of reals.

2. The countable union of countable sets is countable. Well, even the real numbers can be a countable union of countable sets if choice fails badly enough.

If it is up to me, I'd also include a third, but I am not sure if fits your criteria:

1. A function is surjective if and only if it has a right inverse. This one is in fact equivalent to full choice, and it is often used in basic level courses like discrete mathematics and stuff like that. And it makes sense, but for infinite sets you generally still need choice.
• I have to emphatically agree with Asaf on #3 / right inverse stuff. I will go farther - any young person wanting any chance of competing with future AI/Robotic systems, better learn #3 in high school. Dec 2 '17 at 13:19
• @MikeMathMan: Can you give specific details of your claim? I have not seen any practical engineering or algorithmic design have anything to do with the axiom of choice, not even countable choice. Dec 2 '17 at 13:56
• This was really a tongue-in-cheek comment. But, it is critical for people to learn how to learn, and math is a great testing ground. For just about everyone in the 'real world', you don't need full AoC. See, for example, Bumblebee's answer (linear programming). - opinionated-MikeMathMan Dec 2 '17 at 14:11
• @user (see prior comment) and nytimes.com/2012/07/29/opinion/sunday/is-algebra-necessary.html $\text{Is Algebra Necessary?}$. I certainly wouldn't want to meet with a brain surgeon who couldn't grasp #3 and its subtleties (at some level). Dec 2 '17 at 14:25
• Guys, guys... take it somewhere else, eh? :) Dec 2 '17 at 15:48

A bounded, closed, convex subset of $\Bbb{R}^n$ has extreme points.
Amazingly we need (a weaker version of) axiom of choice to prove this simple fact and this has many applications. For example: To solve a linear program problem only needs to consider extreme points of its feasible region.

• A linear program will have a polytope as feasible region, and surely you do not need choice to prove that it has extreme points. So it seems that you do not need the axiom of choice in practical applications, not quite what your answer seems to be conveying. No? Dec 2 '17 at 13:33
• @user21820: Yes, you are right. For a polytope we do not need AC, but above theorem is not only for polytopes. I mentioned about linear programming only as a simple application which is easy to understand even for a high school student. Dec 2 '17 at 18:42
• My point is that linear programming in practice does not invoke the axiom of choice. So your post is very misleading as it implies that the axiom of choice is needed for many applications. Dec 3 '17 at 3:09
• That might be your point of view, but not mine. Dec 3 '17 at 4:50

The Axiom of Choice is required to prove a basic fact from elementary set theory, commonly used in calculus:

Let $f : A \to B$ be a surjection. Then $f$ has a right inverse, i.e. there exists a function $g : B \to A$ such that $f \circ g = \mathrm{id}_B$.

Proof:

Since $f$ is surjective, $f^{-1}(\{y\})$ is nonempty for every $y \in B$. Hence, $\{f^{-1}(\{y\}) : y \in B\}$ is a family of nonempty pairwise disjoint sets. Using The Axiom of Choice, choose $x_y \in f^{-1}(\{y\})$, and define $g(y) = x_y$ for every $y \in B$. We have $f \circ g = \mathrm{id}_B$, by definition of $g$.

In contrast to this, the converse claim does not require Choice:

Let $f : A \to B$ be right-invertible. Then $f$ is surjective.

Proof:

Since $f$ is right-invertible, there exists $g : B \to A$ such that $f \circ g = \mathrm{id}_B$. Let $y \in B$, and consider $g(y) \in A$. We have $f(g(y)) = y$, by definition of $g$. Therefore, $f$ is surjective.

A similar fact that $f$ is injective if and only if it is left-invertible also follows without Choice.

• While I don't deny that this statement is of importance, I don't recall this result being used in calculus. Could you give an example or two of where it's used? Dec 3 '17 at 6:42
• @Wojowu Some calculus courses (such as mine) at the beginning include a bit of basic properties of functions, such as $f \circ g$ injective implies $g$ injective, $f^{-1}(f(A)) \supseteq A$, $f$ bijective iff $f$ invertible, and the like. I explicitly remember this statement as being one of them, while I only later learned that it is significantly more subtle. Dec 3 '17 at 10:21
• I believe that my answer already mentioned that. Dec 3 '17 at 11:57
• @AsafKaragila Sorry, I missed it. I have credited your answer. Dec 3 '17 at 12:07

A typical example that requires the axiom of choice in full is that every field has an algebraic closure. One can prove without the axiom of choice that every countable field has an algebraic closure, and also that the reals have an algebraic closure (say by using complex analysis instead), which means that for practical purposes one does not appear to need the axiom of choice. But in general you do need choice.

• I don't know if that's a truly lower-level undergraduate, though. Dec 2 '17 at 9:42
• @AsafKaragila: Oh I guess not. But neither is the fact that every vector space has a basis. In 'truly' lower-level undergraduate, one does not do any transfinite recursion. =) Dec 2 '17 at 10:35
• Well, yeah, that is also technically correct, since most "early" vector spaces are finite dimensional. Dec 2 '17 at 10:37

Note I posted this answer with a big delay and now see many answers. Just leaving it up now as a 'summary' answer.

The following assumes that we do not learn about the the Lebesgue integral in any undergraduate math class. Yes, the professor's talk about it, but leave it as extra credit (see comments below). Of course any undergraduate interested in quantum mechanics should examine that material; see When is Lebesgue integration useful over Riemann integration in physics? over at physics.stackexchange.com. For more, see Lebesgue theory and axiom of choice on this site.

Do you need FULL $\mathsf {AoC}$ in undergraduate courses?

$\quad$ Multivariate calculus - no
$\quad$ Linear algebra - yes (for those infinite dim spaces), but 98% of coursework not dependent on it
$\quad$ Abstract algebra (Junior level?) - perhaps

If you are taking a real-analysis courses, you might be interested in

In mathematics, the axiom of dependent choice, denoted by $\mathsf {DC}$, is a weak form of the axiom of choice ($\mathsf {AC}$) that is still sufficient to develop most of real analysis.
It was introduced by Bernays (1942).

For example, you need $\mathsf {DC}$ to prove the following statement:

If $(p_n)$ is a sequence in a compact metric space $X$, then some subsequence of $(p_n)$ converges to a point of $X$.

$\quad$ (see for example Rudin's Theorem 3.6)

Most undergraduate students in advanced calculus will see the implicit use of $\mathsf {DC}_{\mathbb R}$, but you can't beat calculus for those math-intuition-insight correlations.

• Huh. That's weird. I was sure that you needed some choice when you talk about null sets and integration in calculus, or about something like "Every infinite bounded set of reals contains a convergent sequence", and I could swear to god that some choice was needed there. Dec 2 '17 at 15:25
• Thanks @a - i updated my answer and made it wiki. Please feel free to fix it it there remains any math claims that need to be addressed. Dec 2 '17 at 15:40
• @AsafKaragila Along those lines, though not quite calculus, V. Kanovei and M. Katz have a recent paper (in Real Analysis Exchange Vol. 42(2), 2017, pp. 385–390) where they prove that it is consistent with $\mathsf{ZF}$ that there is a positive function on $\mathbb R$ whose Lebesgue integral is 0. Dec 2 '17 at 16:24
• @Andrés: Is this in a model where the notion of "Lebesgue measurable" has a concrete meaning? Dec 2 '17 at 19:47
• @an 101 years ago: van Vleck, E. B. - This new integral of Lebesque is proving itself a wonderful tool. I might compare it with a modern Krupp gun, so easily does it penetrate barriers which were impregnable. Bulletin of the American Mathematical Society, vol. 23, 1916. Dec 2 '17 at 21:25

I realise this is not at all at basic undergraduate level (in fact, it is rather technical), but I think it is a good addition to the results mentioned above.

The existence of a non Lebesgue measurable set is independent of ZF set theory and requires Axiom of Choice. This is a classical result due to Solovay.

However Thychonoff's Theorem, that the product of any collection od topological spaces is compact with respect to product topology is a classical undergraduate level result which is equivalent to Axiom of Choice (apologies if this is mentioned earlier).

Again, more upper-level undergrad, or intro grad level: "in a commutative ring, every proper ideal is contained in a maximal ideal" is equivalent to AC.