Axiom:Axiom of Choice for Finite Sets

From ProofWiki
Jump to navigation Jump to search

Axiom

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


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


Remark

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$.

$\blacksquare$


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.

$\blacksquare$