# Intuition behind the Axiom of Choice

Why is it different to make one choice or many choices than to make infinite choices from a theoretical point of view in which indeed you are not going to do any?

How could that be different from making infinite additions for example $\sum_{i=0}^{+\infty}A_n$.

Thanks a lot.

-
But infinite sums are very different from finite sums. For any positive integer $n$ and real numbers $x_1,\dots,x_n$ the sum $x_1+\ldots+x_n$ is defined directly in terms of the binary operation of addition, and it always exists. If $\langle x_n:n\in\Bbb N\rangle$ is an infinite sequence of real numbers, however, we can’t even define $\sum_{n=0}^\infty x_n$ using just the binary operation of addition: we also need the whole machinery of limits. Moreover, $\sum_{n=0}^\infty x_n$ doesn’t always exist. –  Brian M. Scott Apr 18 '13 at 7:00
@BrianM.Scott Still I don't see why the need of AC. –  Ambesh Apr 18 '13 at 7:02
What do you know about transfinite constructions? Have you read any of the other dozen threads about intuition behind the axiom of choice? –  Asaf Karagila Apr 18 '13 at 7:03
I wasn’t trying to answer that; at the moment I can’t think of anything to add to what I said in answering the other question and in the subsequent comments. I was pointing out that your comparison with addition doesn’t work the way you intended, because it shows another situation in which the infinite case is very different from the finite case. –  Brian M. Scott Apr 18 '13 at 7:05

Making one choice is simple, if a set $A$ is not empty, then $\exists a(a\in A)$, and therefore we can pick such $a$. This is called existential instantiation. But this choice is completely arbitrary. This is important because in mathematics we are always within the context of writing a proof (even if we only play around, we essentially prepare ourselves for such proof).

However making infinitely many arbitrary choices is something we cannot prove to be possible1. The axiom of choice asserts that we can, in fact, many infinitely many choices at once - as long as we could make each one (i.e. the sets were not empty).

Remember that arbitrary sets have absolutely no structure. We only have $\in$ in our language, and we have sets and their elements. Sometimes we are lucky and the elements of the set are nice enough to allow for a definable way of choosing from them. For example if the empty set is a member or something.

But this need not be the case. The axiom of choice allows us to uniformly endow all the sets with a particular structure from which we can define a selection.

In comparison, addition of infinitely many real numbers happens within a complete ordered field, where we have some structure, and we use it to establish a criterion when the sum is finite, and if so what is its value.

Footnotes:

1. I am being deliberately imprecise here. The axiom of choice is more than a generalization of existential instantiation for the infinite case. But the intuition which should guide you, in my opinion, is that.

To give a small taste on why things may break down, if we are working within a universe which has non-standard integers then there would be a product which is finite (from the point of view of that model) and therefore is not empty, but since its index set is a non-standard integer we cannot possible write down a formula which instantiate an element from each set.

But all this require first to understand what does internal and external mean in these contexts, and to understand what are non-standard integers and non-standard models better. So it's all pretty far along the road. It is my firm belief that one should start with the idea that the axiom of choice is indeed some sort of a generalization of existential instantiation, and then learn why it is not.

-
@Asaf_Karagila Forgive my ignorance. But why this "existential instantiation" does not work when we do infinite choices instead of only some? –  Ambesh Apr 18 '13 at 12:20
@Myke: Existential instantiation is part of a proof. How would you write infinitely many of them within a finite proof? You can't. (As with incompleteness, there are delicate points regarding the axiom of choice as an extension of this sort of instantiations, but I deliberately chose to ignore them for this purpose.) –  Asaf Karagila Apr 18 '13 at 12:25
@Myke: Which topics? Logic and set theory? An introductory book would be a reasonable idea. Taking a course is an even better idea, if your university offers one (well, unless the teacher is really bad or something like that). –  Asaf Karagila Apr 18 '13 at 12:28
@Asaf_Karagila I took the course, and this is my state. Everybody hates the logics teacher in my faculty. Yes a book on logics and set theory introductory level would be great. This summer I will read it. –  Ambesh Apr 18 '13 at 12:32

The axiom of choice can be seen as a generalization of the principle of induction. So, since the principle of induction is technically a lot simpler, let's ask why is there a need to accept the principle of induction.

The principle of induction, for the purposes of this answer, says that for a property $P(n)$ about a natural number $n$, if $P(0)$ holds and if $P(n)$ holds, then $P(n+1)$ holds, then in fact $P(n)$ holds for all natural numbers $n$.

This principle seems obvious enough (just like the axiom of choice (in at least one of its forms) seems obvious) so why the fuss about calling it a principle? Well, let's first agree that any proof must be a finite list of characters. Now, how does one argue to convince the skeptic about the validity of the principle of induction? One way is to say, well suppose you want to prove that $P(1)$ holds. Then here is a (finite!) proof: $P(0)$ is known. It is also known that $P(0)\implies P(1)$, thus Modus Ponens tells us that $P(1)$ holds. QED.

This of course is far from proving $\forall n\in \mathbb N \quad P(n)$. So we go on. Suppose you want to establish $P(2)$. Well, here is a (finite!) proof: $P(1)$ was already established (i.e., cut and paste prvious (finite!) proof here), and it is given that $P(1)\implies P(2)$. Thus, Modus Ponens again, gives us that $P(2)$ holds. QED.

Usually one then concludes with the not so convincing argument "and so on" to then argue that we actually established $\forall n\in \mathbb N \quad P(n)$. Well, here is the problem then. We didn't actually prove that! What we did was give a hand-wavy argument that the two assertions 1) $P(0)$ holds and 2) $P(n)\implies P(n+1)$ holds, are sufficient to convince one that one has a recipe for proving $P(n)$ for all $n\in \mathbb N$. In other words, one seems to be convinced that for any given $n$, one can find a (finite!) proof that $P(n)$ holds. But, do we now have a single finite proof that $\forall n\in \mathbb N\quad P(n)$ ? Well, the answer would be yes if you accept the recipe for proofs as an actual proof. In other words, if you accept the principle of induction.

So, accepting the principle of induction can be said to be the acceptance of a finite recipe of finite proofs for $P(n)$ (where the length of the proof of $P(n)$ depends on $n$ and will typically tend to infinity with $n$) as a single finite proof of all $P(n)$ in one go. It seems very reasonable to accept such a proof recipe as a proof, which is why the principle of induction is doubted by very few.

Now, the principle of induction is equivalent to the existence of a least element in any non-finite subset of $\mathbb N$, namely to $\mathbb N$ being well-ordered. The axiom of choice, is equivalent to the existence of a well-ordering on any non-finite set. So the axiom of choice allows for more intricate recipes of proofs and is no longer so easily accepted.

-
Transfinite induction requires no choice whatsoever. Many of the particular constructions we make require us to make arbitrary choices. And even then often we run into problems only at certain points in the construction (often in limit stages). –  Asaf Karagila Apr 18 '13 at 7:54
Also in the second paragraph you have a lowercase $p$ where it should be an uppercase $P$; and in the fourth paragraph you wrote "finte!" instead of "finite". –  Asaf Karagila Apr 18 '13 at 7:56
@AsafKaragila I do think AC is a kind of local-to-global principle of the same kind as induction, however: it says, if I can make a choice locally (i.e. for each member of a set), then I can make a choice globally (i.e. for the whole set at once). –  Zhen Lin Apr 18 '13 at 8:17
@AsafKaragila thanks for the comments. I changed the last paragraph in a way that (I believe) is correct. –  Ittay Weiss Apr 18 '13 at 8:21
@DanChristensen I'm afraid I find your blog entry is highly imprecise. See the comment I left there. Basically, your approach depends on a pre-existing model of PA with induction (in order to rigorously defined the chain you mention there, giving rise to the natural-number-like set). It is then a tautology that what you get is a model of PA with induction, since you build it as an isomorphic copy of a given model of PA with induction. –  Ittay Weiss Apr 18 '13 at 22:46