Hall's Marriage Theorem/General Set

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathcal S = \langle S_k \rangle_{k \in I}$ be an indexed family of finite sets.

For each $F \subseteq I$, let $\displaystyle Y_F = \bigcup_{k \mathop \in F} S_k$.

Let $Y = Y_I$.


Then the following are equivalent:

$(1): \quad \mathcal S$ satisfies the marriage condition: for each finite subset $F$ of $I$, $\left\vert{F}\right\vert \le \left\vert{Y_F}\right\vert$.
$(2): \quad$ There exists an injection $f: I \to Y$ such that $\forall k \in I: f \left({k}\right) \in S_k$.


Proof

$(2)$ implies $(1)$

Suppose that for some finite $F \subseteq I$, $\left\vert{F}\right\vert > \left\vert{Y_F}\right\vert$.

Then $\left\vert{F}\right\vert \not \le \left\vert{Y_F}\right\vert$.

So there can be no injection from $F$ to $Y_F$.


Thus there can be no injection from $I$ to $Y$ satisfying the requirements.

$\Box$


$(1)$ implies $(2)$

Let $\Phi \left({x}\right)$ be the set of all elements of $y$ in the expression of $x$.



Let $\mathcal F$ be the set of all partial functions $g$ from $I$ to $Y$ such that:

$g$ is one-to-one.
If $\left({k, y}\right) \in g$, then $y \in S_k$.

Then for any $k \in I$, $\left\{ {g \left({x}\right): g \in \mathcal F \land k \in \operatorname{Dom} \left({g}\right)}\right\}$ is finite.

$\mathcal F$ has finite character:

Let $g \in \mathcal F$.

Let $F$ be a finite subset of $I$.

Then $g \restriction F$ is obviously in $\mathcal F$.

Suppose instead that $g$ is a partial function from $I$ to $Y$.

Let the restriction of $g$ to each finite subset of $\operatorname{Dom} \left({g}\right)$ be in $\mathcal F$.

Then $g$ is one-to-one, as follows:

Let $p, q \in \operatorname{Dom} \left({g}\right)$ with $p \ne q$.

Then $\left\{ {p, q}\right\}$ is a finite subset of $\operatorname{Dom} \left({g}\right)$.

Thus:

$g \restriction \left\{ {p, q}\right\} \in \mathcal F$

Thus:

$g \left({p}\right) \ne g \left({q}\right)$

Let $\left({k, y}\right) \in g$.

Then:

$\left({k, y}\right) \in g \restriction \left\{{k}\right\}$

So:

$y \in S_k$

Thus:

$g \in \mathcal F$

So we see that $\mathcal F$ has finite character.


Let $F$ be a finite subset of $I$.

By the finite case, there is an element of $\mathcal F$ with domain $F$.

By the Cowen-Engeler Lemma, $\mathcal F$ has an element $\phi$ whose domain is $I$.

That is, $\phi$ is a mapping from $I$ to $Y$.

But a one-to-one mapping is an injection, so $\phi$ is an injection from $X$ to $Y$.

By the definition of $\mathcal F$:

$\forall k \in I: \phi \left({k}\right) \in S_k$

$\blacksquare$

Boolean Prime Ideal Theorem

This theorem depends on the Boolean Prime Ideal Theorem (BPI), by way of Cowen-Engeler Lemma.

Although not as strong as the Axiom of Choice, the BPI is similarly independent of the Zermelo-Fraenkel axioms.

As such, mathematicians are generally convinced of its truth and believe that it should be generally accepted.


Source of Name

This entry was named for Philip Hall.