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

From ProofWiki
Jump to navigation Jump to search


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

Let $\SS$ be a non-empty set of finite, non-empty sets.

Then there exists a choice function for $\SS$.

Proof from Hall's Marriage Theorem

Without loss of generality, suppose $\SS$ is pairwise disjoint.

We will show that $\SS$ satisfies the marriage condition.

That is, for each finite subset $\FF$ of $\SS$:

$\card \FF \le \card {\bigcup \FF}$

as follows:

Let $\FF$ be a finite subset of $\SS$.

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

Since $\SS$ is pairwise disjoint, $f_\FF$ is an injection.

Thus $\card \FF \le \card {\bigcup \FF}$.

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