Confusion regarding one formulation of the Axiom of Choice.

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.

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.