2
$\begingroup$

One formulation of the Axiom of Choice is:

The Cartesian product of non-empty sets is always non-empty.

Cartesian product is defined as making "every possible pair" between elements of two sets. The implication is that through some aritrarily selected algorithm, we can select each element one-by-one, and pair it with another element (from another set). Does the Axiom of Choice imply that without assuming such an axiom, no such algorithm can exist? What if the elements are ordered? If I have a linearly ordered set, and I state that I my method of selection of elements is I will move from the lowest element to the highest element, am I still using the Axiom of Choice somehow? Is choosing even the lowest element in a set an exercise of the Axiom of Choice?

Thanks

$\endgroup$
  • 1
    $\begingroup$ Well, in the cartesian product of a huge ammount (!) of sets, how do you "choose" an element from each set to form an element in the cartesian product and show it isn't empty? Well, there you go: that's AC ! $\endgroup$ – DonAntonio Mar 31 '14 at 12:42
  • $\begingroup$ A total order isn't enough. (How do you choose the lowest positive real number? Or even the lowest real number?) To make that work, you need a well-ordering (usually taken to be a well-ordering of the discrete union of all the sets of which you're taking the product) to guarantee that there is always a lowest element. And thus you have a hint to the equivalence of AC to the well-ordering principle. $\endgroup$ – Arthur Mar 31 '14 at 12:45
  • $\begingroup$ @DonAntonio- I don't get it. If all the sets are ordered, why can't you just choose the owedt element from all, and hence show that the cartesian product is non-empty? $\endgroup$ – algebraically_speaking Mar 31 '14 at 12:45
  • $\begingroup$ The well ordering of any set is equivalent with AC, @algebraically_speaking. I'm afraid we're going around a circle here... $\endgroup$ – DonAntonio Mar 31 '14 at 12:48
  • 1
    $\begingroup$ The Axiom of Choice can be used to show that every set is well-orderable, and from the reasoning you mentioned, the converse is readily proved. That's what Don is saying--he's not saying that without AC, no set is well-orderable (and there are many cartesian products that are non-empty without AC, too). $\endgroup$ – Cameron Buie Mar 31 '14 at 12:54
3
$\begingroup$

Cartesian product of two sets is used to "make every possible pair". And that is true even without the axiom of choice. If you take the product of any two non-empty sets then the product of them is non-empty.

But what about Cartesian product of three sets? Are these pairs? Triplets? If these are pairs, what coordinate is the additional one, is it $((a,b),c)$ or $(a,(b,c))$? Well, these questions don't matter because we have a natural identification between all three options, triplets and the two type of pairs. So instead we can define redefine the Cartesian product of $A$ and $B$ as the set of functions from $\{0,1\}$ into $A\cup B$ such that $f(0)\in A$ and $f(1)\in B$. It is not hard to see why this gives us the same structure as ordered pairs.

The thing about this approach is that now the product of three sets can be thought of as functions from $\{0,1,2\}$ rather than pairs of pairs and so on. Whenever we add more sets, we just increase the index set.

Another wonderful benefit of this definition is its extendability to infinite products. If you insist that products are just pairs of pairs of pairs, and so on. What objects do you have when you take the product of infinitely many sets? It is a nice exercise to see that such object would have to be ill-founded. So we cannot have that in the presence of regularity (and we don't want to have that in general).

On the other hand, with the proposed definition as functions taking the product of infinitely many sets is easy. We have an index set $I$ and a family of sets $A_i$ and we just take functions such that $f(i)\in A_i$. Does that look familiar? It should. It is in fact the definition of a choice function.

So it turns out that the Cartesian product of sets is actually the set of choice functions from them. The axiom of choice assures that every family of non-empty sets has a choice function, and therefore the Cartesian product of any family of non-empty sets is non-empty. But as I said, for finite families of sets we can prove that we don't need the axiom of choice for choosing. That is, the Cartesian product of finitely many sets (however large they might be, just not empty) is non-empty. In particular $A\times B$ is never empty if neither set is empty.

You also made several other mistakes.

  1. Without the axiom of choice it is not true that every set is ordered. Not well-ordered, and not linearly ordered. It is true that there are ordered sets, both well-ordered and linearly ordered, but it is possible for sets which cannot be linearly ordered to exist.

  2. Not every linear order has a least element. And not every set which can be linearly ordered can necessarily be well-ordered.

  3. Sets are not ordered sets. Ordered sets are sets which have a fixed structure endowed on them. If I just give you $\{a,b\}$, you can either order it as $a<b$ or $b<a$. But seeing how I haven't given you any information on what $a$ and $b$ are exactly, you have no preference for one way over the other. Therefore if you want this set to be ordered you have to choose an ordering.

    It is possible that there is a countable family of pairs like that, that are so indiscernible from one another, that it is impossible to endow them all with orders at the same time. You can of course order each pair individually, and therefore you can order finitely many of them. But you cannot choose an order for each and every one of them at the same time without an appeal to the axiom of choice.

Regardless to that, if you are given structured sets. That is, sets which come along with a fixed structure, then it is possible to choose from each, under certain circumstances (e.g. the structures are well-orders, or there is some fixed element in each of the sets, etc.)

So if I would have given you $\{a,b\}$ and $a<b$; for each of the aforementioned pairs, then of course you can choose the minimal element in each pair.

But the point is that it is not necessary that every set can be ordered, and even if it is ordered, it is usually the case that there are many different (even if isomorphic) orders on each set, and to choose one for each set would be an appeal to the axiom of choice.

$\endgroup$
  • $\begingroup$ I don't see how the case would differ if the number of sets is infinite. Say the number of sets is $\aleph$. Then why can't we select the lowest element from each set? Is it because we can;t "access" all $\aleph$ sets? $\endgroup$ – algebraically_speaking Mar 31 '14 at 12:48
  • $\begingroup$ @algebraically_speaking, you're again assuming we can well-order all those sets. See the comments above. $\endgroup$ – DonAntonio Mar 31 '14 at 12:49
  • 1
    $\begingroup$ @algebraically_speaking: Things don't exist just because you want them to. We need to prove their existence. Even if all sets can be well ordered, you may still have to access an infinite amount of information, which you cannot "just do". If a set can be well ordered to begin with, and it is not a singleton then there are many ways to well order it. How do you choose which order? Of course if the orders are given then you are right, assuming they are well orders. $\endgroup$ – Asaf Karagila Mar 31 '14 at 12:53
  • $\begingroup$ @algebraically_speaking: I edited my answer (now that I sit in front of a keyboard). $\endgroup$ – Asaf Karagila Mar 31 '14 at 15:20
  • $\begingroup$ Thanks Asaf for your detailed answer. $\endgroup$ – algebraically_speaking Apr 2 '14 at 2:33
3
$\begingroup$

Let me clear up a few definitions before answering.

We say a set $X$ is indexed by a set $I$ if there is a function from $I$ onto $X$--we typically denote this function by something like $i\mapsto X_i,$ which allows us to write $X=\{X_i\}_{i\in I}$ or $X=\{X_i\mid i\in I\}.$ Every set can be indexed by itself, of course.

Given an indexed set of sets $\{X_i\}_{i\in I}$ we may define the Cartesian product of the sets $X_i$ by $$\prod_{i\in I}X_i:=\left\{f:I\to\bigcup_{i\in I}X_i\mid \forall i\in I,f(i)\in X_i\right\}.$$ That is, the elements of a Cartesian product are functions from the index set into the union of all the sets, such that each $i$th element is a member of the $i$th set in the collection. This is the same idea as what is going on in the finite case, only the "tuples" aren't necessarily ordered (or even orderable, as far as we care).

To see why these are "the same," take any two sets $A,B.$ We can readily index the set $\{A,B\}$ with the set $\{1,2\},$ by $1\mapsto A,2\mapsto B$--that is, we can rewrite $A=X_1,B=X_2$ for the indexed notation. So, on the one hand, the elements of $$\prod_{i\in\{1,2\}}X_i$$ are functions on $\{1,2\}$ such that $1$ is sent to an element of $X_1=A,$ and $2$ is sent to an element of $X_2=B.$ But such functions are effectively ordered pairs whose first entry is an element of $A$ and whose second entry is an element of $B,$ meaning that this product is effectively the same as $A\times B$ in the sense you may be more familiar with. Note that the indexing makes a difference--if we'd chosen the indexing $1\mapsto B,2\mapsto A,$ then it would be "more natural" to say that the Cartesian product (in the sense defined above) was the same as $B\times A$ in the sense that you're used to.


Now, where is it that the Axiom of Choice comes into play in ensuring that arbitrary Cartesian products of non-empty sets are non-empty? Well, let's start with an arbitrary non-empty indexed set of non-empty sets $\{X_i\}_{i\in I}.$ As it stands, we don't know anything about the set $I$ or the sets $X_i,$ except that they are non-empty. They may not necessarily be orderable at all so far as we are assuming. Even if we were to add the assumption of orderability, then we would still have to choose an ordering for each set $X_i$ (and for $I,$ if we like, though it isn't really necessary), and unless $X_i$ is a singleton, there will be more than one way to order $X_i$ if it can be ordered at all. Even if we assume that each set $X_i$ is already ordered, it won't be enough! After all, not every ordered set has a least element, as mentioned before, and though we could always "fix" a given order of that nature by pulling an element out of the usual order, and calling it the least element under a new order, we may have to choose which element to make the least element for every $X_i$! So, we would have to make the assumption that each $X_i$ is ordered in such a way that it has a least element, or your argument doesn't work. This is a fairly tall assumption, and (it turns out) requires the Axiom of Choice to prove that it is even possible! After all, even if we know that $X_i$ admits such an order for each $i\in I,$ we still have to choose an order for each such $X_i,$ and in general unless $X_i$ is a singleton, there will be more than one way to do this!


Let me outline (most of) the proof of the equivalence of some common formulations of the Axiom of Choice.

The following are equivalent:

  • The Cartesian product of (a non-empty indexed set of) non-empty sets is non-empty.
  • For every non-empty set $\mathcal A$ of pairwise-disjoint non-empty sets, there exists a set (which we'll call a "choice set" for $\mathcal A$) containing exactly one element from each element of $\mathcal A.$
  • Every non-empty set of non-empty sets admits a choice function).
  • Every set admits a well-order.

For the first implication (Cartesian product implies choice set), recall that every set can be indexed, so taking the Cartesian product of the elements of $\mathcal A,$ and picking out an element $f$ from this Cartesian product, the range of $f$ can be shown to be a choice set for $\mathcal A.$

For the second implication (choice set implies choice function), start with a non-empty set $X$ of non-empty sets, then note that $\mathcal A:=\bigl\{\{A\}\times A\mid A\in X\bigr\}$ is a non-empty set of pairwise disjoint non-empty sets. Furthermore, a choice set for $\mathcal A$ can be shown to be a choice function for $X.$

Proving the third implication (choice function implies well-orderability) is the most non-trivial of the results, and I won't get into it here, but I wanted to mention it.

The fourth implication (well-orderability implies Cartesian product), start with a non-empty indexed set of non-empty sets $\{X_i\}_{i\in I}.$ Since $\bigcup_{i\in I}X_i$ is a set, then it is well-orderable, so pick any well-ordering for this union. Now, by definition of well-ordering, we have a least element for each $X_i,$ so we can show that $\prod_{i\in I}X_i$ is non-empty, letting $f:I\to\bigcup_{i\in I}X_i$ be defined by letting $f(i)$ be the least element of $X_i$ for each $i\in I.$


Alternately, we can leave out the well-orderability, and prove that choice function implies Cartesian product. Indeed, suppose we have a non-empty indexed set of non-empty sets $\{X_i\}_{i\in I}.$ Let $g$ be a choice function for $\{X_i\}_{i\in I},$ meaning that $g:\{X_i\}_{i\in I}\to\bigcup_{i\in I}X_i$ is such that $g(X_i)\in X_i$ for all $i\in I.$ Defining $f(i)=g(X_i)$ for each $i\in I$ makes $f$ an element of $\prod_{i\in I}X_i,$ as desired.

$\endgroup$
  • $\begingroup$ When I finally get behind an actual keyboard and plan on revise my answer, you make this plan almost irrelevant. :-) $\endgroup$ – Asaf Karagila Mar 31 '14 at 14:49
  • $\begingroup$ @Caneron Buie- What I understood is that when there are multiple ways of doing something, and we don't have a clear choice of which way to choose, we use the AC to accomplish the task using an arbitrary way. Can this be stretched further? Say there are multiple ways of reaching a destination. And the ways can be ordered in different ways- comfort, length, etc. The selection of one particular order, or an arbitrary way, requires AC? Everyday choices, in some sense (I know I'm digressing from set theory) requires AC? $\endgroup$ – algebraically_speaking Apr 1 '14 at 4:02
  • $\begingroup$ Say there is only one way to order a set (assume for a moment). Then either choosing that order and selecting its lowest/highest element, or choosing an altogether different element still requires AC? $\endgroup$ – algebraically_speaking Apr 1 '14 at 4:03
  • 1
    $\begingroup$ @algebraically_speaking: That's not quite true. If we need to make any finite number of arbitrary choices, we can, with no need to use AC. So, if there are multiple ways of accomplishing a task, then the set of ways of accomplishing said task is non-empty, and we simply pick an arbitrary way from that set of all ways, with no need for AC. For example, if we know (somehow) that a given set can be ordered, we can just pick any ordering of that set to do the job. However, if we don't know enough about the set to conclude that it is orderable, then we can let Choice do it for us. $\endgroup$ – Cameron Buie Apr 1 '14 at 15:03
  • 1
    $\begingroup$ I think Russell put it rather well: AC would be needed to select one sock from each of infinitely-many pairs of socks (assumed indistinguishable), but not from infinitely-many pairs of shoes (as we could just pick the right shoe from each pair, for example). $\endgroup$ – Cameron Buie Apr 1 '14 at 15:13

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.