I am a first-year maths student but I occasionally drift away from our taught material. Some years ago I saw the ZFC axioms for the first time, but now that I am in college, and although the stuff I've been taught so far is nowhere near ZFC (in terms of difficulty), it happened to me that we use the axiom of choice all the time in every module, even if we don't know it by name yet.

For example, in the proof that, for every non-negative integers $a, b$, there exist integers $q, r: a = bq + r$ (with the known restrictions on r), and the proof starts like this: $Choose$ the largest integer $q : qb <= a$... blah blah blah.

Is it the axiom of choice that allows us to execute this simple yet so important step?

And a couple more questions: Can you name some other simple proofs, theorems, results etc for which the axiom of choice is essential?

Also, I've read that AOC has long been a topic of dispute for mathematicians, and that even today, some people do not accept it. Are there any alternative axiomatic systems that work equally well without needing AOC? Thanks!


marked as duplicate by Asaf Karagila set-theory May 10 at 21:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ No, choice is not used in the example you indicate. $\endgroup$ – Andrés E. Caicedo May 10 at 21:37
  • 2
    $\begingroup$ Just because the word is mentioned, it doesn't mean the axiom is invoked. Just like saying that triangles have 3 sides does not mean that Euclidean geometry is number theory in disguise. $\endgroup$ – Andrés E. Caicedo May 10 at 21:39
  • $\begingroup$ It's easy to see how to go about picking the element described. You don't need the axiom of choice. It's when you make infinitely many choices that the axiom of choice comes into play. $\endgroup$ – saulspatz May 10 at 21:39
  • 1
    $\begingroup$ This is not the axiom of choice. It is just a theorem that any non empty set of integers which is bounded from above has a maximum, hence you can obviously take it. $\endgroup$ – Mark May 10 at 21:40
  • 1
    $\begingroup$ More generally, the axiom-of-choice is filled to the brim with questions previously asked about the axiom of choice. Those can be about specifics in a particular proof, or necessity in another, or just broad questions. $\endgroup$ – Asaf Karagila May 10 at 21:52

In the example you give, no choice is actually involved : there is only one such largest integer (it's something you have to prove : both that it exists and that it's unique, but it can be done) and so there is no need to invoke AC.

More generally, for basic number theory it will essentially never come up. More generally, the full-blown AC is usually not needed in basic first year mathematics where you do calculus and stuff, you only need "watered down" versions, such as the axiom of countable choice, or the axiom of dependent choice, which are both strictly weaker than AC, and are way less disputed.

Typically in an analysis proof you'll build a sequence $(x_n)$ where $x_{n+1}$ depends on $x_n$ but not functionally and so you'll have to use the axiom of dependent choice. Sometimes this can be avoided, sometimes not. For instance, the theorem relating sequential continuity at a point and continuity at this point uses some form of choice (although surprisingly and interestingly, global sequential continuity and global continuity are equivalent in ZF for a separable metric space, but the proof is more subtle)

Examples of theorems where the use of the axiom of choice is essential (by which I mean you can't adapt the proof to work without it, because the theorem in question implies AC) in "usual mathematics" are : any vector space has a basis; any ring has a maximal ideal; any product of compact topological spaces is compact; and many others.

As for who accepts it and who doesn't, AC is nowadays part of the standard axioms of maths and so most mathematicians use it freely or don't worry about it; however some mathematicians also worry about where it is used for at least a simple reason : if you can prove something without AC, then it holds with more generality, in more contexts. Also, it is always interesting to know what assumptions you're using when proving something.

  • 2
    $\begingroup$ Not to mention that a lot of the time, "choose $x$ such that ..." is actually an application of $\exists$-elimination which requires no axiom of choice whatsoever, it's just a standard part of first-order logic. $\endgroup$ – Daniel Schepler May 10 at 21:49
  • $\begingroup$ @DanielSchepler: That is the real crux of the matter. It is because students are not even taught basic first-order logic. $\endgroup$ – user21820 May 13 at 3:02

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