The "Axiom of Choice" is a feature of theoretical math, and appears to be accepted by the mathematical community. It is one of several claims that I will have to be dragged, kicking and screaming, into accepting as necessary. I've seen several statements of the Axiom that I think I understand, as well as some incomprehensible versions.

Let's be clear: for now, I believe the Axiom to be valid. My problem is in calling it an axiom. As an Axiom, one can choose not to include it. This gives us a larger span of possibilities, including situations where the Axiom is false. Including the Axiom narrows our possibilities. In general, adding an axiom to a definition requires more, and therefore narrows the range of possibilities. As an illustration how adding an axiom narrows our possibilities, consider the definition of a group:

A group is a set (say, G) with a binary operation (generically called multiplication, although any operation serves) satisfying the following requirements (axioms) (*x,* *y, z* are members of G):

- Closure:
*xy* (*x* multiplied by *y*) is a member of G.
- Associativity: (
*xy*)*z* = *x*(*yz*), and can be written *xyz*.
- Right Identity: G has at least one member (
*e*) satisfying *xe = x*.
- Right Inverses: for (at least) one such right identity, there exists
*x*^{-1} satisfying *x**x*^{-1} = e.

An Abelian (or commutative) group has one extra defining property (or axiom): xy = yx. Group multiplication commutes. There are fewer (non-isomorphic) Abelian groups of a given order (number of elements) than groups in general (again, non-isomorphic and of the same order). On the other hand, what would happen if we didn't require associativity? I don't know, but many more set-operations would qualify.

The point is, if we needed the Axiom of Choice as an axiom, it would be possible to define everything in set theory without the Axiom, and have types of set that don't satisfy the axiom. One version goes like this:

Given non-empty sets S_{n}, it is possible to let x_{n} be a member of S_{n}, for each *n*.

Why do we need an axiom to make such a statement? S_{n} is non-empty, and therefore has a member; let x_{n} be a member. I'm going to consider only a countable number of sets -- finite or countably infinite. We can always take our index *n* as a positive integer. Things get squirrelly once we go beyond the countable. At least countably infinite is semi-sane. (We still have to get used to things like infinity+1 = infinity, infinity+1000 = infinity, 2*infinity=infinity, 100*infinity=infinity, infinity^{2}=infinity, infinity^{20}=infinity, and the like. Note, however, that 2^{infinity} is uncountable.)

Perhaps it's some solace that the Axiom is only allegedly needed if the number of sets is infinite. Another statement of the Axiom is that the Cartesian product (or direct product) of an infinite number of non-empty sets is non-empty. Here are some examples of Cartesian products:

The Cartesian product of two sets is a set of ordered pairs:

S_{1} = {1,2} and S_{2} = {7,8,9}: S_{1} x S_{2} = {(1,7),(1,8),(1,9),(2,7),(2,8),(2,9)}

S_{1} = {1,2} and S_{2} = {1,2,3}: S_{1} x S_{2} = {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)}

The standard 52-card deck is the Cartesian product of 13 ranks and four suits. (Example from Wikipedia.)

The numbers in an ordered pair may be duplicated, although not in a set. The Cartesian product of three sets is an ordered triple. In general, the Cartesian product of *n* sets is an ordered *n*-tuple, which may be defined inductively. (Using the inductive definition, one might consider an element of the Cartesian product of 3 sets to be ((a,b),c) rather than (a,b,c). But we can declare them to mean the same thing.)

S_{1} = {1,2}, S_{2} = {1,2}, and S_{3} = {7,8,9}: S_{1} x S_{2} x S_{3} = {(1,1,7),(1,1,8),(1,1,9),(1,2,7),(1,2,8),(1,2,9),(2,1,7),(2,1,8),(2,1,9),(2,2,7),(2,2,8),(2,2,9)}

Since S_{1} = S_{2}, we could have called the example above, S_{1} x S_{1} x S_{3}. One can take the Cartesian product of a set with itself.

The number of elements in the Cartesian product of *N* sets is the product of the numbers of elements from each set. The number of elements in each example Cartesian product above is 6, 6, 52 and 12, respectively. As long as sets with more than one element continue to exist as we increase *N*, the number of elements in their Cartesian product increases rapidly. In fact, it approaches at least the cardinality of the power set of integers -- that limit is uncountable, the same infinity as the real numbers, the same infinity as the power set of the integers, or 2^{infinity,} where "infinity" refers to countable infinity.

The Cardinal product of a countably infinite number of sets consists of all elements of the form (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7}, ...).

I may concede troubles in defining the Cartesian product of an infinite number of sets, but if we surmount that issue, the Cartesian product of an infinite number of sets (of more than one element each) can't be empty, since it's order (number, cardinality) is infinite. Perhaps I should be less arrogant, and instead ask, if we don't assume the Axiom of Choice, how we can get an infinite number of non-empty sets, but their Cartesian product be the empty set? That is, how does the Axiom of Choice restrict the sets that exist?

A shorter statement: if all sets are non-empty, then the Cartesian product of them has at least as many elements as the largest set.

Here's Wikipedia quoting Bertrand Russell on the subject: "The Axiom of Choice is necessary to select a set from an infinite number of pairs of socks, but not an infinite number of pairs of shoes." Wikipedia's comment on Russell's quote: "The observation here is that one can define a function to select from an infinite number of pairs of shoes by stating for example, to choose a left shoe. Without the axiom of choice, one cannot assert that such a function exists for pairs of socks, because left and right socks are (presumably) indistinguishable."

We are supposed to abstract the "pairs of socks" example to represent pairs of indistinguishable objects, because of course, physical socks are distinguishable -- by position if nothing else. In fact, it may be impossible to abstract away the distinguishability of the socks. If the socks are truly indistinguishable, perhaps one literally can't choose between them -- not even at random. In this case, we can't pick out one from a single pair, let alone one from each of an infinite number of pairs.

It's possible that if the socks are truly indistinguishable, then the "pair of socks" are in fact the same sock.

How would this apply to sets of numbers? First of all, we can't have a set of two fives: {5,5}. Either 5 is a member of the set or it isn't. (This should be distinguished from the ordered pair of two fives: (5,5). A single 5 can be plotted on a number line. The ordered pair would be plotted on a plane.) All numbers in a set of numbers are different. The closest thing to a pair of identical numbers is {i,-i} (with i being the square root of -1). But this is the same as the left-shoe, right-shoe example. (Left and right have the same conceptual issue as i and -i.)

If we have finite sets of real numbers, where for each positive integer *n*, S_{n} contains a finite number of real numbers, then even by the standards of the Axiom of Choice, we need not invoke the Axiom. Each set has a minimum number, so we can define *x*_{n} = min(S_{n}). If we allow for a finite number of infinite sets, then one can pick a number from each of those. Then the remaining finite sets all have *x*_{n} = min(S_{n}). So now, we need to deal with an infinite number of infinite sets. In fact, if we have finite sets among the infinite sets, we can always choose for those *x*_{n} = min(S_{n}). So we can limit ourselves to all sets being infinite.

Let's once and for all dispose of the notion that the Cartesian product of the sets is the empty set, simply because the number of elements in the Cartesian product explodes as the number of sets approaches infinity. At worst, the Cartesian product is ill-defined.

So what's to prevent us from saying, "Suppose *x*_{n} is a member of S_{n}, for all positive integers *n*?"

I've heard it claimed that one needs the Axiom of Choice (or a weaker version, the Axiom of Countable Choice) to prove that any infinite set has a countably infinite subset. See, for example, https://proofwiki.org/wiki/Infinite_Set_has_Countably_Infinite_Subset. They first give an intuitive proof, then warn against it. I'm going to formalize their intuitive proof, and challenge anyone to tell me the mistake I've made. The proof uses strong induction. (Prove something for* k=1*, assume it's true for *k=1...n*, then prove it for *n+1*. This proves it for all positive integers.)

S is the infinite set. Let *x*_{1} be a member of S. Now assume that *x*_{1} ... x_{n} are distinct members of S. Let *x*_{n}_{+1} be a member of S - U_{k=1}^{n} {*x*_{k}} -- where U refers to the union, and the "subtraction" refers to S without any element from the union. Then *x*_{1} ... x_{n}_{+1} are distinct members of S. Therefore, by strong induction, *x*_{n} are all distinct members of S, for positive integers *n*. U_{k=1}^{infinity} {*x*_{k}} is a countable subset of S. QED.

If something is actually wrong with this, would they kindly explain with more than something like it takes forever to make such a choice, or that we need to invoke the Axiom of (Countable) Choice to do this. It's clear that the subtracted set is nonempty, because we are removing a finite number of elements from an infinite set. The subtracted set is well-defined by the induction assumption. Therefore, "Let *x*_{n}_{+1} be a member..." has to be valid. If we're talking about infinite time, let's avoid this by letting the *n*^{th} step take 1/2^{n} seconds*. *The total time is one second.

In the spirit of the infinite pairs of socks, I've been considering the two endpoints of a line segment, and three vertices of an equilateral triangle. In both cases, the points are indistinguishable. I might discuss those situations later.

In theoretical math, axioms are used to define objects. See the axioms defining a group above. On the other hand, "axioms" have been thought of as things that are so obvious that they are assumed true, and used as starting points. It's possible that the Axiom of Choice (and the Axiom of Countable Choice) is used in that latter sense of an assumption rather than as part of a definition.

## Recent Comments

Mike40033:You asked a question about negative interest ra... | more »John M:I dont think that is really a difference, in th... | more »Blissex:No, that argument does not work. Because libert... | more »