46
$\begingroup$

According to this book:

The Axiom of Choice is the most controversial axiom in the entire history of mathematics. Yet it remains a crucial assumption not only in set theory but equally in modern algebra, analysis, mathematical logic, and topology (often under the name Zorn's Lemma).

I am not a set theorist, and I don't pretend to be, but I have heard of some weird things that can happen with choice, such as the Banach–Tarski paradox--paradoxes like these are presumably why the Axiom of Choice was so controversial at first, but I am interested in what would happen without choice.

Question: What notable consequences would occur without the Axiom of Choice?

I found one very interesting example here on an MO thread (reproduced here for ease):

The universe can be very a strange place without choice. One consequence of the Axiom of Choice is that when you partition a set into disjoint nonempty parts, then the number of parts does not exceed the number of elements of the set being partitioned. This can fail without the Axiom of Choice. In fact, if all sets of reals are Lebesgue measurable, then it is possible to partition $2^{\omega}$ into more than $2^{\omega}$ many pairwise disjoint nonempty sets!

What other weird things would result without this axiom? Would it really be a devastating blow to mathematics or is it really not that big of a deal? I'm hoping for examples/answers geared toward the undergrad level--suitable for someone with very little set theory background.

$\endgroup$
  • $\begingroup$ I'm sure there are many mathematicians who routinely work without Choice, including users of this site. $\endgroup$ – Akiva Weinberger Apr 27 '15 at 2:22
  • 1
    $\begingroup$ @SeyhmusGüngören What do you mean? $\endgroup$ – Daniel W. Farlow Apr 27 '15 at 2:43
  • 1
    $\begingroup$ Didn't we have like six of these questions? Just take anything mentioned in the consequences, and remember that without the axiom of choice it is at least consistent that such consequence fails. $\endgroup$ – Asaf Karagila Apr 27 '15 at 3:28
  • 1
    $\begingroup$ (Don't get me wrong, I don't mind writing another long another like that, I'm just wondering if this is really necessary.) $\endgroup$ – Asaf Karagila Apr 27 '15 at 3:32
  • 3
    $\begingroup$ Okay fine, I ended up writing another one of these long answers... $\endgroup$ – Asaf Karagila Apr 27 '15 at 4:07
74
$\begingroup$

Importance is a relative thing.

For a computer scientist, or an applied mathematician, or a combinatorialist working with finite sets the axiom of choice might be the least important axiom in mathematics. As instances involving only finite sets will never require the axiom of choice.

We can see the axiom of choice budding importance when you reach to infinite objects. The axiom is needed to ascertain that countable union of countable sets are countable, it is needed to ensure that every two algebraic closures of $\Bbb Q$ are isomorphic, it is needed to ensure that $\Bbb R$ is not the countable union of countable sets, it is needed to ensure that every filter can be extended to an ultrafilter and as a consequence it gives us Hahn-Banach theorem, the compactness theorem for logic.

The axiom of choice is needed to ensure that every vector space has a [Hamel] basis. It is needed to ensure that every commutative ring with a unit has a maximal ideal. The axiom is needed to make sure that cardinal arithmetic is going along as planned. That the Lowenheim-Skolem theorems hold.

Wherever infinite sets play a role, the axiom of choice is needed to make sure that the formulation of the theorem is simple, and that it is relevant to sets we deem important. Sets like the real numbers, like $\ell_\infty$, sets which are uncountable.

What weird results can happen without the axiom of choice? Pretty much anything, if it needs the axiom of choice in a substantial way, it means that it can fail without the axiom of choice. But there is a usual reminder here. The failure of the axiom of choice is just as non-constructive as the axiom itself, and that means that just saying that the axiom of choice has failed spectacularly doesn't mean that this failure happens in sets which interest the "working mathematician", or even "the working set theorist".

So let me list a few failures of the axiom of choice which occur at the level of the real numbers, which is what we really seem to think is bizarre.

  1. The real numbers can be a countable union of countable sets. This means that most analysis goes out the window, as the usual definition of Borel/Lebesgue measures trivializes. Things can be remedied by working with Borel codes, but everything becomes much harder to manage.

  2. $\Bbb Q$ has two non-isomorphic algebraic closures. We can prove that the usual algebraic closure always exists, or at least there is always a canonical algebraic closure to $\Bbb Q$. But it turns out that there can be a non-canonical as well, and they can be non-isomorphic.

  3. Every ultrafilter on $\Bbb N$ is principal. This means that definitions using ultraproducts and ultralimits (e.g. in the definition of the hyperreal numbers) do not go through; it also means that $\Bbb R$ cannot be well-ordered.

  4. Every set of reals can have the Baire property (it is equivalent to an open set up to a meager set). This might not seem like much, but it is in fact a big deal. This implies, at least in the presence of dependent choice (a strengthening of countable choice), that every linear operator between a Banach space and a normed space is continuous.

    In particular, every linear functional from a Banach space to $\Bbb R$ is continuous, and every functional from $\Bbb R$ to $\Bbb Q$ is continuous. So the reals have no Hamel basis over $\Bbb Q$ and $\ell_2$ is isomorphic to its algebraic dual, which is just its usual topological dual. It also means that $(\ell_\infty/c_0)^*=\{0\}$.

  5. I'd be remiss if I didn't mention the axiom of determinacy. This axiom implies a lot of structure in the land of sets of reals; although this structure is much more complex and strange than we are used to with the axiom of choice. It implies the measurability and other regularity properties of sets of reals, and its consistency strength is higher than all the aforementioned failures, but let's not get into that.

  6. $\Bbb Q$ might not be injective (as an abelian group). In fact, the assertion that every divisible group is injective implies the axiom of choice. And it is consistent that there are no injective groups, in particular $\Bbb Q$ might not be injective.

  7. There might be an infinite Dedekind-finite subset of $\Bbb R$. This means that a lot of definitions go out the window, e.g. continuity by sequences is not equivalent to continuity by $\varepsilon$-$\delta$ when talking about a continuous function at some $x$. It means that there is a tree on whose nodes are real numbers, its height $\omega$, and it is without maximal nodes, but without infinite branches either.

  8. More specifically to the previous one, we can arrange that this set cannot be endowed with a group structure on its own, contradicting the theorem (which is equivalent to full choice) that every non-empty set can be endowed with a group structure.

  9. It is entirely possible that $\Bbb R$ is the union of two disjoint sets, each of strictly smaller cardinality. You heard me.

This list can go on and on and on. So let me stop here. And let me point out that there are many other failures which can happen which may interest "Mathematician Joe", because they prevent nice formulation of theorems.

It's no longer "every commutative ring with unity has a maximal ideal" but rather "every well-orderable commutative ring with unity has a maximal ideal"; and similar additions which force us to restrict to smaller classes of objects, and since there might be commutative rings which are not well-orderable, but still have maximal ideals, this theorem is not satisfying either.

So is the axiom of choice important? To modern mathematics, which deals with infinite objects, the answer is yes. How is it important? It is important by bringing some order to infinite sets and getting them at least a little bit under control.

$\endgroup$
  • $\begingroup$ Wait I don't get what you mean by "failure of the axiom of choice". For example, you say that the reals can be a countable union of countable sets, but does it have to be when we reject the axiom of choice? No, right? $\endgroup$ – user21820 Apr 27 '15 at 13:19
  • 2
    $\begingroup$ No. Of course not. As I said several times, the axiom of choice could fail so far above any set which is interesting to "Mathematician Joe", which of course include the real numbers and their power set and so on. Or that the failure is only about larger families of sets, or something like that, and countable union of countable sets are still countable. But it can be the case that the axiom of choice fails and (or perhaps because) the real numbers are a countable union of countable sets. $\endgroup$ – Asaf Karagila Apr 27 '15 at 13:22
  • $\begingroup$ Ah okay great. Thanks for clarifying! By the way, I don't want to ask yet another question, but since you mentioned that the axiom of choice does not say anything about finite structures, does it have any implications for any definable countable structures that cannot be proven without it? $\endgroup$ – user21820 Apr 27 '15 at 13:26
  • $\begingroup$ Well, this is really a question of what you mean by that. The rationals are a definable countable structure; and you can claim that "there is a unique [up to isomorphism] algebraic closure" is something about the rationals; or you can claim that the canonical algebraic closure is countable, and claiming it is unique up to isomorphism is a claim about that structure. $\endgroup$ – Asaf Karagila Apr 27 '15 at 13:32
  • 1
    $\begingroup$ It might be a good start to read this Math Reviews entry. $\endgroup$ – Asaf Karagila Apr 27 '15 at 14:48
5
$\begingroup$

The axiom of choice is needed to construct a function $f:[0,1]\rightarrow R$, such that $f(r^n)=f(r)$ for $r\in[0,1]$ and all natural numbers $n$, that is a counterexample for the uniqueness in a vibrating string inverse problem.

$\endgroup$
  • 1
    $\begingroup$ A non constant function I'm guessing ? $\endgroup$ – Max Jul 29 '18 at 11:18
  • $\begingroup$ Yes, non-measurable function... $\endgroup$ – DVD Aug 3 '18 at 22:57
  • $\begingroup$ @Max please, see above... $\endgroup$ – DVD Aug 4 '18 at 1:29

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.