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

Question

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?

Answer 1

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).

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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.