Axiom of choice

From Apeirology Wiki
Jump to navigation Jump to search

The axiom of choice is a somewhat controversial axiom in set theory, which is included in the axiomatic system of ZFC. It asserts that every family \(X\) of nonempty sets has a choice function, i.e. a map \(f: X \to \bigcup X\) so that, for all nonempty \(x \in X\), \(f(x) \in x\). Essentially, for a collection of sets, it is possible to find a function which chooses one element from each "bag" in this collection of bags. In many cases, the axiom of choice is trivial and intuitive. For example, one can see that the axiom of choice is equivalent to the assertion that the Cartesian product of any collection of nonempty sets is nonempty. Note that the assertion that the Cartesian product of finitely many nonempty sets is nonempty is obvious, but it's possible to define Cartesian product of infinitely many sets. Despite these simple characteristics, the axiom of choice is not a theorem of ZF, and it has some consequences that may be counterintuitive.

For example, the axiom of choice is highly nonconstructive and doesn't actually tell somebody what that choice function looks like. Similarly, the axiom of choice tells us there is some well-order on the real numbers, but it is a theorem that there is no well-order on the real numbers. In general, the axiom of choice implies every set can be well-ordered: that is, for every set \(X\), there is a relation on \(X\) which imbues it with the structure necessary for it to be considered a well-ordered set. All finite sets, and even countable sets, can be trivially well-ordered, and in most cases this well-ordering will be definable, but the uncountable case is unclear. The proof that the axiom of choice implies that every set can be well-ordered is relatively simple. Namely, let \(Y\) be the family of subsets of \(X\). Let \(f\) be a choice function for \(Y\). Then define, via transfinite recursion, the ordinal indexed sequence \(a_\xi\) of elements of \(X\) by \(a_\xi = f(X \setminus \{a_\eta: \eta < \xi\})\). Every element of \(X\) shows up somewhere in this sequence. Therefore, define \(\leq\) by \(a_\xi \leq a_\eta\) iff \(\xi \leq \eta\). This is well-defined, and it is a well-order since the ordinals are well-ordered.

Furthermore, the axiom of choice implies the law of excluded middle, which means constructivist mathematicians tend to work in ZF rather than ZFC.

Lastly, and most famously, the axiom of choice implies the Banach-Tarski paradox. In particular, using the axiom of choice, it's possible to decompose any ball in 3D space into a finite number of disjoint subsets, which can then be put back together in a different way to yield two identical copies of the original ball. Indeed, the reassembly process involves only moving the pieces around and rotating them without changing their shape. This is counterintuitive, but not truly paradoxical as the pieces themselves are not "solids" in the usual sense, but infinite scatterings of points.