Axiom:Axiom of Choice for Finite Sets

From ProofWiki
Jump to navigation Jump to search


Let $\mathcal S$ be a non-empty family of finite, non-empty sets.

Then there exists a choice function for $\mathcal S$.


The axiom of choice for finite sets is trivially implied by the axiom of choice, but it is strictly weaker.

Proof from the Ordering Principle

By the Axiom of Union, $\mathcal S$ has a union.

Let $U = \bigcup \mathcal S$.

By the Ordering Principle, there is a total ordering $\preceq$ on $U$.

For each $S \in \mathcal S$, $S$ is a chain in $U$.

By Finite Non-Empty Subset of Totally Ordered Set has Smallest and Greatest Elements, each $S \in S$ has a minimum.

Let $f:\mathcal S \to U$ be defined by:

$f(S) = \min S$

Then $f$ is a choice function for $\mathcal S$.


Proof from Hall's Marriage Theorem

We can assume without loss of generality that $\mathcal S$ is pairwise disjoint.

We will show that $\mathcal S$ satisfies the marriage condition. That is, for each finite subset $\mathcal F$ of $\mathcal S$, $|\mathcal F| \le \left|{\bigcup \mathcal F}\right|$:

Let $\mathcal F$ be a finite subset of $\mathcal S$.

By the Principle of Finite Choice, $\mathcal F$ has a choice function $f_{\mathcal F}: \mathcal F \to \bigcup \mathcal F$ such that for each $S \in \mathcal F$, $f_{\mathcal F}(S) \in S$.

Since $\mathcal S$ is pairwise disjoint, $f_{\mathcal F}$ is an injection.

Thus $|\mathcal F| \le \left|{\bigcup \mathcal F}\right|$.

By Hall's Marriage Theorem for sets of finite sets, $\mathcal S$ has a choice function.