Axiom:Marriage Condition

Definition

Let $\SS = \family {S_k}_{k \mathop \in I}$ be an indexed family of finite sets.

For each $F \subseteq I$, let:

$\ds Y_F = \bigcup_{k \mathop \in F} S_k$.

$\SS$ satisfies the marriage condition if and only if:

for each finite subset $F \subseteq I : \card F \le \card {Y_F}$.

This Hall's Marriage Theorem is so called for the following reason:

Let $I$ be a set of women.

Suppose that each woman $k$ is romantically interested in a finite set $S_k$ of men.

Suppose also that:

each woman would like to marry exactly one of these men

and:

each man in $\ds \bigcup_{k \mathop \in I} S_k$ would like to marry at most one woman in $I$.

Then this theorem gives a condition under which it is possible to match every woman to a man.