\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \)
deepdream of a sidewalk
Show Question
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \)
Math and science::Analysis::Tao::08. Infinite sets

Axiom of Choice

There are a few different ways of presenting this axiom differing in their readability.

1: choice function (brilliant.org)

Let \( \mathcal{I} \) be a set (which we will use for indexing). For each \( i \in \mathcal{I} \) let \( S_i \) be a set. We call the set of these sets a collection, denoted as \( \{ S_i \}_{i \in \mathcal{I} } \). So the collection contains one set for each element in \( \mathcal{I} \).

A choice function is a function

\[ f : \mathcal{I} \rightarrow \bigcup_{i \in \mathcal{I}} S_i \]

such that \( f(i) \in S_i \text{ for all } i \in \mathbb{I} \). The axiom of choice states that for any indexed collection of nonempty sets, there exists a choice function.

2: Cartesian product of indexed collection (brialliant.org)

The Cartesian product of an indexed collection of nonempty sets is nonempty:

\[ S_i \neq 0 \; \forall i \in \mathcal{I} \implies \prod_{i \in \mathcal{I}} S_i \neq 0 \]

It's worth noting that the axiom of choice is only an interesting statment when the indexing set \( \mathcal{I} \) is infinite; it is easy to show that the finite case is true without using the axiom of choice.

3: binary predicates

Let \( X \) and \( Y \) be sets, and let \( P(x, y) \) be a binary predicate pertaining to an object \( x \in X \) and \( y \in Y \) such that for every \( x \in X \) there is at least one \( y \in Y \) such that \( P(x, y) \) is true. [How can one assert the existance of such a predicate?] Then there exists a function \( f : X \rightarrow Y \) such that \( P(x, f(x)) \) is true for all \( x \in X \).


Source

p200