Axiom:Axiom of Choice for Finite Sets/Proof from Hall's Marriage Theorem

From ProofWiki
Jump to: navigation, search


Suppose that Hall's Marriage Theorem holds for all sets of finite sets.

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

Then there exists 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.