# Do we need Axiom of Choice to make infinite choices from a set?

According to the answers to this question, we do not need choice to pick from a finite product of nonempty sets, even if each of the sets is infinite. The axiom of choice is required to ensure that a infinite product of nonempty sets is non-empty. i.e. $\prod_{i \in I} A_i \neq 0$.

Now, let $A_i = \mathbb{R}$. The answers to this question (and the one linked above) says we do not need choice to pick an element $x_0 \in \mathbb{R}$. Suppose, I want an arbitrary sequence of real numbers $X = (x_n)_{n =1}^{\infty}$. Then, I will have to make an infinite number of "picks" from $\mathbb{R}$.

Is it right to say that the resulting sequence $X \in \prod_{i \in I} \mathbb{R}$ and that we need choice to ensure that it exists? Why or why not?

You need to go to the rational numbers, in order to ensure that every equation of the form $nx=m$ has a solution with $m,n$ natural numbers. Does that mean that there are no solutions, to any choice of $n,m$ in $\Bbb N$?

No, it doesn't. $4x=8$ still has a solution in $\Bbb N$.

Similarly with the axiom of choice. It is needed to ensure that every product of non-empty sets is non-empty. It doesn't mean that it is needed for proving each and every product of non-empty sets is non-empty, though.

If all the sets you choose from are the same, then constant choices are choices that you can always make. If all the sets you choose from have a particular structure on all of them (e.g. they are all finite sets of real numbers), then you can choose from them all (e.g. they are all finite sets of real numbers, take the minimal element).

The axiom of choice is being overused, and in many cases it isn't needed for a particular argument of interest. Not the say that it is never needed, or rarely needed. It just gets overused plenty. And that might be dangerous (see the third panel).

• Nice explanation. According to math.vanderbilt.edu/~schectex/ccc/choice.html, no one has ever found a suitable choice function for the product of all nonempty subset of the real line, but we can use choice to ensure that there is at least one. However, someone could eventually find a choice function, which means we won't need choice anymore right? (unless its proven to be equivalent to choice) – Jean Valjean Jul 4 '14 at 15:08
• Yes, it is true that we cannot prove the existence of a choice function for $\prod_{\varnothing\neq A\subseteq\Bbb R}A$. But as I wrote, the axiom of choice is needed to prove that every product is non-empty. It doesn't mean that it is needed for each product separately. – Asaf Karagila Jul 4 '14 at 15:14
• Yes right. Oops, I meant to say then we won't need choice anymore for that particular product (all nonempty subset of the reals), since someone came up with a choice function. But the choice is still needed to prove that every product is non-empty. (i.e. there does not exist such a product that is nonempty) Thanks for the explanation. – Jean Valjean Jul 4 '14 at 15:49
• To be accurate we do need some part of the axiom of choice to prove that the product of all non-empty sets of real numbers have a choice function. But we don't need it to show that every product of non-empty sets of real numbers is non-empty. – Asaf Karagila Jul 4 '14 at 18:16
• Just to check my understanding: your second line is true because there is a product of non-empty sets of reals, $\prod_{i \in \mathbb{N}} \mathbb{R}$, which does not need choice. Since we can just pick $x_i = 42$. your first line is true because no one has found a choice function, and according to the notes I linked, there are reasonable model-theoretic arguments against finding one (not sure if it has been decisively proven yet). – Jean Valjean Jul 4 '14 at 19:04

No. You may simply pick $x_i=42$ for all $i\in I$.

• The absolute answer for the meaning of life and everything else. – Mark Fantini Jul 5 '14 at 8:57

As Hagen points out in his answer, it is not always necessary. Sometimes, when the sets involved are specially nice, you can just write down an element in the product (as Hagen has done). However this is not always possible.

The best way I've heard this put is the following (I think it is due to Hilbert, but I'm not sure), the idea of which is as follows.

If you have infinitely many pairs of shoes then you don't need to use choice. You can just pick the left shoe from each pair and you have your set. However if you have infinitely many pairs of socks, then you do need choice (you can't say pick the left sock because there is no way to differentiate between them).

To reiterate, in the presence of nice enough sets, you might have some form of canonical "choice" that makes AC redundant. However in the presence of arbitrary sets you do need to invoke AC.

EDIT: Apparently the saying is due to Russel and not Hilbert.

• So, it is like $P$ vs $NP$ algorithms in computation complexity? If a given problem has a polynomial time algorithm (canonical choice), we are done. Else, the problem is in $NP$ and may or may not be in $P$. (might still have a canonical choice but no one currently knows it . however choice says one exist) i.e. an infinite product of nonempty set might have a choice function, but if one is currently not available, we use choice to say there is an arbitrary one. however, one might be "discovered". – Jean Valjean Jul 4 '14 at 14:21
• The shoes and socks belong to Betrand Russell's feet I beleive – Tom Collinge Jul 4 '14 at 14:22
• Danul: You thought wrong. @Tom: If Russell had owned all of these shoes and socks, the earth would have collapsed into a black hole about a century ago. (Also, I believe that it wasn't shoes and socks, but rather books and shoes, or boots and socks. But boots were involved there.) – Asaf Karagila Jul 4 '14 at 14:58
• The saying is Russell's and, oddly enough, was originally about boots and not socks. "If the right and left boots in each pair are indistinguishable, we cannot discover any property belonging to exactly half the boots." B. Russell, On some diﬃculties in the theory of transfinite numbers and order types, Proc. London Math. Soc. Sec. Sci., 4, (1907), 29–53. – Andrés E. Caicedo Jul 4 '14 at 15:28
• @Jean: P vs NP is not as simple. If P=NP, then all problems in NP have polynomial time algorithms. The hard part is not even finding them, but proving that they are polynomial-time algorithms. We know how to write down a concrete algorithm that (provably) solves your favorite NP-complete problem, but which runs in polynomial time if and only if P=NP -- see Levin's universal search theorem. – Henning Makholm Jul 4 '14 at 15:42

Short: First-order logic does not permit infinitely long statements. Infinitary logics do.

To elaborate a little on Danul G's answer: If you can write a finite-length prescription for how to select each element from a collection, then you do not need choice. If, however, you would need an infinite-length prescription, then your prescription would be invalid.

Hagen von Eitzen has provided an example of a finite prescription that selects a single element from each of a collection of copies of a set containing an element "42".

Part of the difference is that we are on a "first name basis" with every element of $\mathbb{R}$. (Actually, we aren't. We could only say that for the computables, and I at least, only know some thin subset of even this much smaller set.) We can easily call them out by name and each disjoint pair of them is obviously distinguishable. (Even this requires a caveat -- the problem of identifying computable expressions equivalent to zero is undecidable. Meh.) In this sense, the real numbers are a collection of shoes -- distinguishable elements.

Suppose instead I gave you a product of "an infinite collection of sets (about which I will tell you nothing other than they are each not empty)". Then you don't know any of the elements by name -- they are all indistinguishable, like socks (before you wear them and asymmetrically stretch them). You can't write a prescription (finite or otherwise) that picks out an element of each set. You can write the natural language sentence "$f$ picks out an element of each set", but in formalizing that description you will not find a finite prescription. You will get "$f$ picks an element from the first set, then $f$ picks an element from the second set, ..." where "..." entails an infinitely long prescription. First order logic (and any other finitary logic) does not permit infinitely long statements. Unless we add an axiom that says we can. The Axiom of Choice allows this for exactly the construction we are discussing, but does not (directly) introduce any other infinitary constructions.

• This is probably one of the best explanation of the axiom of choice that I have ever read. (for a general audience who have never done set theory or logic of course) – Jean Valjean Jul 4 '14 at 22:26
• @Jean: And like all layman explanations, it contains a very very delicate mistake. Which is why explanations to the layman are not good for people who try and do mathematics (this point is so delicate that only a year and a half ago I finally understood it well enough; and I have made it on this very site before). – Asaf Karagila Jul 5 '14 at 1:44
• The mistake is that the universe may contain non-standard integers, in which case you cannot write a sentence like $\exists x_1\ldots\exists x_n(\bigwedge x_i\in A_i)$ or something like that, because this $n$, from the meta-theory's point of view, is infinite. However internally to the model it is finite. How do we overcome this issue? $\sf ZF$ proves induction. And using induction we can show that for all finite collections there is a choice function. – Asaf Karagila Jul 5 '14 at 1:47
• @AsafKaragila: And so, ..., you find a finite prescription for the particular function you want. As, described. – Eric Towers Jul 5 '14 at 3:20
• It may be worth pointing out that what you get from the fact that any two real numbers are "obviously distinguishable" in a uniform way is that there is a choice function for any sequence of finite sets of real numbers (just pick the least real from each finite set) and that this holds more generally if $\mathbb{R}$ is replaced with any linearly ordered set. – Trevor Wilson Jul 5 '14 at 8:12

The Axiom of Choice asserts that products of infinite collections of non-empty sets exist. So it is only needed when you want to simultaneously choose an element from each of an infinite collection of non-empty sets, ie select an element of the product. That is all. You do not need the Axiom of Choice to choose an element from an infinite set, or to choose infinitely many elements from a single set, or to perform any operation on a finite collection of sets.

Edit: Any function X -> Y is a subset of XxY. Furthermore, if X and Y are sets, even infinite sets, then so are XxY and any subset of XxY. So all functions between sets are well-defined sets, and the Axiom of Choice is not required for their definition. In particular, since an infinite sequence is a function from the naturals into a set, defining an infinite sequence does not require the Axiom of Choice.

• Isn't choosing infinitely (say, countably infinite) many elements from a set (say, $\mathbb{R}$) the same as picking an element in the cartesian $\prod_{i \in \mathbb{N}} \mathbb{R}$? – Jean Valjean Jul 4 '14 at 22:23
• @Jean: No, you only choose from one set here. – Asaf Karagila Jul 5 '14 at 1:42
• @AsafKaragila: I am confused about the difference between a real valued sequence $X = (x_n)_{n=1}^{\infty}$ (choosing countably infinitely many elements from $\mathbb{R}$) and an element of $\prod_{i \in \mathbb{N}} \mathbb{R}$. – Jean Valjean Jul 5 '14 at 16:51
• @Jean: There is no difference. Who said that there is a difference? – Asaf Karagila Jul 5 '14 at 16:59
• @AsafKaragila - Thanks. In the case of the Axiom of Dependent Choice, we are picking also infinitely many elements from a set. Except we now have a condition for each pick (the relation). Is it right to say that picking infinitely many elements without condition from a set never requires choice, but if there is a condition, we might require choice? – Jean Valjean Jul 5 '14 at 20:50