Choice Function Exists for All Finite Sets

Theorem

Let $\mathbb S$ be a set of sets such that:

$\forall S \in \mathbb S: S \ne \varnothing$

that is, none of the sets in $\mathbb S$ may be empty.

Let $\mathbb S$ be finite.

Then there exists a choice function $f: \mathbb S \to \bigcup \mathbb S$ defined as:

$\forall S \in \mathbb S: \exists x \in S: f \left({S}\right) = x$

Thus, if $\mathbb S$ is finite, we can construct a choice function on $\mathbb S$ by picking one element from each member of $\mathbb S$.

Proof

Proof by induction:

Basis for the Induction

Let $\left|{\mathbb S}\right| = 1$.

Let $S \in \mathbb S$.

Suppose that an $x$ such that $x \in S$ does not exist.

Then for all $x$, we have $x \notin S$.

Thus by definition of the empty set $S = \varnothing$, which contradicts our hypothesis.

Thus we can find an $x \in S$.

We can then construct $f: \mathbb S \to \bigcup \mathbb S$ by defining $f \left({S}\right) = x$.

Induction Hypothesis

We have a choice function for all $\mathbb S$ with $\left|{\mathbb S}\right| = n - 1$.

This is our induction hypothesis.

Induction Step

Now suppose $\left|{\mathbb S}\right| = n$.

Let $S_0$ be a set in $\mathbb S$.

Then $S_0 \ne \varnothing$.

Thus by the basis for the induction we can find a $y$ such that $y \in S_0$.

We also have $\left|{\mathbb S \setminus S_0}\right| = n - 1$.

Thus we can assign a choice function $f_0: \mathbb S \setminus S_0 \to \bigcup \mathbb S \setminus S_0$, by the induction hypothesis.

However, there exists a function $f_1: \mathbb S \setminus S_0 \to \bigcup \mathbb S$ as well.

This is defined by setting $f_1 \left({S}\right) = f_0 \left({S}\right)$.

We can then construct a new function $f: \mathbb S \to \bigcup \mathbb S$, by setting:

$f \left({S}\right) = \begin{cases} f_1 \left({S}\right) & : S \ne S_0 \\ y & : S = S_0 \end{cases}$

This $f$ is therefore a choice function on $\mathbb S$.

$\blacksquare$