Why it is necessary to state axiom of choice for a collection of sets instead of for one set?

65 Views Asked by At

Informally, the axiom of choice says that we can choose one element out from any set (if I am right).

However, I dont understand why it is needed stated for a collection of disjoint sets (so that for each set we can choose one element out)?

I think the ability to choose out element from any one set is enough to state the axiom. Then it should be true when the set in in a collection of set (even infinite number of sets).

2

There are 2 best solutions below

0
On

For picking an element from a single (non-empty) set you do not need the AoC. If you have a set from which you can't pick out any elements, then by definition (and the axiom of extensionality) what you have is the empty set.

However, formally, you can only pick out elements from finitely many sets, if you do it one by one. The power of the AoC lies in the fact that it allows you to pick elements (even if the selection happens seemingly one-by-one) from any collection of (non-empty) sets, as long as the collection itself is a set.

9
On

No. You are not right. Choosing from one element is rooted in the rules of logic.

First, remember that we are always working inside a proof. This means that (1) the rules of inference and axioms of logic are more or less all that we have, besides our axioms, and (2) we can only do finitely many things, since proofs are finite in nature.

So choosing from one non-empty set. If $A$ is non-empty, that means that we can prove $\exists a(a\in A)$. Using existential instantiation we can introduce a new constant symbol $a$ and the axiom $a\in A$. This is how we chose an element of $A$.

We did not use the axiom of choice. And by induction, we can also choose from any finitely many sets.1 But what happens if we want to choose from infinitely many sets? Say, from each non-empty subset of $A$? Then we introduce a function symbol, say $F$, and we say that $F(X)\in X$ for all non-empty $X\subseteq A$, or for all $X$ in our family of sets. This lets us talk about infinitely many choices in a finite space.

Sometimes, e.g. when $A=\Bbb N$, we have some additional structure on $A$ that lets us choose these elements uniformly. In the case of $\Bbb N$, this is the linear ordering which provably has a unique minimum element in every non-empty set. So we can define $F$ quite explicitly.

In other times, e.g. when $A=\Bbb R$, we have no reasonable (or unreasonable) way of defining this sort of $F$. And the axiom of choice is necessary if we want to choose an element from every non-empty subset of $\Bbb R$.

To recap: Choosing one element from one set will only use the basic rules of logic, not the axiom of choice. Choosing from infinitely many sets simultaneously requires us to have something called a choice function, which lets us compress infinitely many choices into a finite proof. However, it is not always the case that we can explicitly describe such a choice function. The axiom of choice states that we can always assume that a choice function exists, just by knowing that all the sets are non-empty.

(Just to clarify the terminology, "a collection of sets" really just means "a set of sets", it's just clearer to us, humans, when we use "collection of sets" and not "set of sets". But at the same time, we want to be able and choose from any set of non-empty sets.)


  1. There is a very subtle issue here about choosing elements in the proof, and choosing inside set theory, and I will ignore it here. Not because it doesn't matter, it does, but because I find it to be more instructive to students.