Existence in variants of the Axiom of Choice

Question

Let $\{A_i: i \in I\}$ be a nonempty family of nonempty sets. Why is it allowed to prove the Axiom of Choice using the Well Ordering Principle as follows:

There is a well-ordering of $\cup_{i \in I} A_i$. Using this order, there is a first element in each $A_i$. Let $f(i)$ be this first element. Then $f$ is a choice function for this family.

But not to `prove' the Axiom of Choice directly as follows:

Each $A_i$ is nonempty: there is an element of $A_i$. Let $f(i)$ be this element. Then $f$ is a choice function for this family.

Both arguments appeal to the existence of some unspecified object (what well-order? what element of $A_i$?); why is that fine in the first case, but not the second? (The former approach, for instance, is from Aliprantis and Border, Infinite Dimensional Analysis, 3rd ed, p. 20.)

I must admit that I have only read about naive set theory, not axiomatic set theory: perhaps I just haven't learned the rules of the game.

Answer 1

A good visual way to 'see' the problem is this:

For the first method, imagine each well-order of $\cup_{i\in I}A_i$ is a marble, all of which are put into a hat which is the hat of well-orders of that set. We then invoke the well-ordering principle to show that there is at least one marble in that hat, and then reach into that hat and take out a marble (any marble, doesn't matter which one). From here, we use that ordering to pick all our $a_i$'s.

For the second method, instead, for each $i\in I$, represent the $a_i$'s in $A_i$ as marble's in the hat labelled $A_i$ Now we are needing to take a marble from each of the $|I|$ hats we have to construct our choice function, and this is where the problem is: now we have to make many choices, in fact, if we don't have a well-order for $I$, then there is no way to come up with a procedure that we can guarantee will remove a marble from every hat in $I$ (said marbles will be the $f(i)$'s that define our choice function).

Do you see the problem now?

Answer 2

Think about it this way: you're trying to write down instructions for a robot to pick an element from each set. The instructions have to be completely unambiguous.

If you just say, "OK, each set $A_i$ has an element $a_i$; so let $f(i)$ be that element," this clearly doesn't unambiguously tell the robot how to pick some element from each $A_i$. Suppose $A_i=\{x, y\}$ - which one is $a_i$?

On the other hand, suppose you had a well-ordering $W$ of the union of the $A_i$s lying around. You could tell the robot:

• On input $i$,

• go over to $W$,

• and look for the $W$-least element of $A_i$.

• Pick that one.

This is unambiguous! It's dependent on $W$, of course - different $W$s will give different procedures - but as long as you have at least one $W$, you can write this algorithm. To drive this home: if $A_i=\{x, y\}$, then I don't know which of $x$ or $y$ is $a_i$, but I will know as soon as I look at $W$ and see whether $x<_Wy$ or $y<_Wx$. Think of a well-ordering as a kind of disambiguator.

Answer 3

The main issue here is defining concretely, from the existing universe, a choice function (or whatever object).

I have two white socks, plain, new, entirely indistinguishable. I hold one sock in my left hand, and the other in my right. Now I turn around for a few seconds and turn back to you. Did I switch the socks?

You can't tell. Your power of observation made it possible to observe there are two socks, but not to discern them in any meaningful way. So you don't know if I switched them.

So now, if I have infinitely many such pairs, you cannot tell me, in finite time, how to choose one from each pair. Because you have to go to each pair separately, and pick a sock (and mark it so I won't fool you later).

Similarly here. The existence of a well ordering allows us to uniformly label all the socks, all the elements. But when we only know that the sets we want to choose from are nonempty, that is not enough to describe---in the mathematical universe, with out "current" tools---what would be the choice function.

Answer 4

First of all note that the proof of the Axiom of Choice from the Well Ordering Principle is not valid unless you admit the latter as an axiom; it is not a proof of AC per se (which is why ZFC contains AC as axiom), but shows that one can take WOP as axiom instead of AC, and then derive AC from it.

Second, note that in spite of appearances you are not trying to specify a choice function (nobody ever can, even admitting WOP as axiom), but only the existence of a choice function. Note that if you were instead trying to prove the existence of a well ordering, that would be tautological when admitting WOP as axiom: the axiom asserts existence of a well ordering, QED. I did not specify any one well ordering, nor could I, but the proof of its existence is complete (though trivial).

The difference between the two proofs you mention is that the former tries (incorrectly) to combine the tautological "if $X$ is nonempty then there exists an element of $X$" infinitely many times to establish the existence of a choice function, while the latter uses the tautology just once. More precisely it uses the slightly less trivial "if $X$ is nonempty and $F$ is a map $X\to Y$ then $Y$ is nonempty" (with $F$ mapping well orderings to the corresponding choice functions) which is easily proved.

The reason that "infinitely many times" is important, is that one can prove from ZF only that "if $X$ and $Y$ are both nonempty, then $X\times Y$ is nonempty". So ZF will prove the existence of a choice function on a collection of two. A similar proof exists for any finite collection. (This is not a proof by induction, or else one could prove countable choice from ZF, which one cannot.) The statement that the Cartesian product of any collection of nonempty sets is nonempty is precisely the statement AC (and is not provable in ZF).

Answer 5

For why we can "pick from one" but not from infinitely many:

There is a blob. ​ Let x be one. ​ [further reasoning] ​ Thus Q.

is short for

There exists a blob.


For all blobs x:

[further reasoning]
Q

.


For all blobs x, Q. ​ Thus Q.

, using the rule

For formulas Q in which x does not occur free,
from ​ ​ (∀x)(P(x) implies Q) ​ and ​ (∃x)(P(x)) ,
one can deduce Q.

, where P is "is a blob".


That rule might be easier to see indirectly:

If ​ (∀x)(P(x) implies Q) ​ but Q is false, then one must have
not P(x) ​ for each x, in order to make ​ P(x) implies Q ​ true.

There is no similar way to formalize "pick one from each".

Answer 6

For writing things out, it's nice to note that a choice function on the family of sets $\{A_i\}_{i \in I}$ is the same thing as an element of the product $\prod_{i \in I} A_i$. I will use this phrasing of the axiom of choice below.

---

Consider free logic (a.k.a. first-order logic but without the presumption that domains of discourse are nonempty).

In free logic, it's okay to declare elements of empty sets — i.e. you can say "let $x \in \varnothing$". The difference as compared to first-order logic is that $ (x \in S) \implies (\exists x \in S) $ is not a theorem.

Basically, conclusions in free logic are ultimately predicated upon the variables being drawn from inhabited domains, and you get vacuous truth when drawing from empty domains; e.g. a proof of the form

• Let $x \in S$
• ...
• Therefore $P$

is a proof that $ (S \neq \varnothing) \implies P $, or equivalently that $ (S = \varnothing) \vee P $.

---

When doing set theory in free logic, then even without the axiom of choice it's perfectly okay to declare a variable $i \in I$ and then a family $a_i \in A_i$, and then accumulate them to declare a choice function $f$. You don't even need the hypothesis that the $A_i$ are nonempty!

But while it's always fine to declare a choice function $ f \in \prod_{i \in I} A_i $, to derive any interesting consequences we need to prove $\prod_{i \in I} A_i$ is nonempty.

There is a straightforward inductive proof of this fact for finite families of nonempty sets, by recursively invoking the axiom of products to prove $S \times T$ is nonempty if $S$ and $T$ are.

However, this inductive proof does not extend to infinite families.

Answer 7

Below is an excerpt from an old answer of mine that I think addresses the difference between making one choice and making an infinity of choices well.

Note that the kind of reasoning you use in your suggested proof of AC is actually allowed in mathematics in general. But in order to formalize that reasoning in axiomatic set theory we need the axiom of choice. Or in other words, the purpose of the axiom of choice is to state that this kind of reasoning is allowed.

I don't think there's any real way around being at least somewhat familiar with the workings of formal logic and axiomatic set theory for this; otherwise you will have to make do with analogies and semi-intuitive appeals to what you can and cannot imagine doing or what can be told in finite time. Do not let that fool you into thinking that the need for AC is a matter of dogma and opinion; once you have the right prerequisites there is a precise technical way in which it is needed.

The ability to choose single elements during a proof is built into the rules of first-order logic; we don't need a set-theoretic axiom for doing so. More precisely, if we know $\exists x.\varphi(x)$, then it is admissible to pick an $x$ that $\varphi$ holds for. Either the $\exists x$ was proved earlier in the proof -- in which case we actually know a specific thing with this property, because that is how you prove an $\exists$ -- or the $\exists x$ comes from an axiom, in which case the ability to pick such an $x$ is "morally" part of what the axiom promises us.

So when the Axiom of Choice promises us that "$\exists$" a choice function, it doesn't only say that there are choice functions out there, but also that we're allowed to pick one.

---

Now, why would we want to have a choice function exist inside set theory? The main reason is such that we can wrap up the many choices it represents and handle them as a single object -- particularly in the axiom schemas that allow us to supply a formula to specify what we're doing. The formula may contain set parameters, but syntactically it can only contain a finite number of parameters. The Axiom of Choice allows us to parameterize an instance of the axiom schema with an infinity of choices when we need it.

The two axiom schemas this is relevant for is the Axiom of Replacement and the Axiom of Selection.

The Axiom of Replacement allows us to form $\{F(x)\mid x\in A\}$ for any set $A$. The function $F$ does not a priori have to exist as a set within the set-theoretic universe; it can be given by a logical formula. But we need to be able to prove that there is only (or at most) one $F(x)$ for each $x$ -- otherwise the axiom might produce a set so large that it needs to be a proper class instead. However, often we actually want to use an underspecified $F$ that just says "choose something with such-and-such property", where we can prove that at least one something always exists. For this we need to wrap up all of the choices as a set parameter to the formula that represents $F$; the Axiom of Choice is what we need to do that. First-order logic allows us to make single choices one by one during a proof, but not to write down choose something as part of a formula.

The Axiom of Selection allows us to form $\{x\in A\mid \varphi(x)\}$. Here, $\varphi$ can be an arbitrary formula (with parameters), but sometimes we want $\varphi$ to depend on some arbitrary choices that need to be the same for all the $x$s in $A$ we consider. Again the problem -- of part of it -- is that the formula $\varphi$ cannot itself speak about making choices in a controlled way, but we can parameterize $\varphi$ by a choice function that we select once and for all outside the application of the Selection axiom.

(CW since the answer is mostly self-plagiarized).