Category:Hall's Marriage Theorem
Jump to navigation
Jump to search
This category contains pages concerning Hall's Marriage Theorem:
Finite Indexed Family of Finite Sets
Let $\SS = \family {S_k}_{k \mathop \in I}$ be a finite indexed family of finite sets.
For each $F \subseteq I$, let $\ds Y_F = \bigcup_{k \mathop \in F} S_k$.
Let $Y = Y_I$.
Then the following are equivalent:
- $(1): \quad \SS$ satisfies the marriage condition: for each finite subset $F \subseteq I : \card F \le \card {Y_F}$.
- $(2): \quad$ There exists an injection $f: I \to Y$ such that $\forall k \in I: \map f k \in S_k$.
General Indexed Family of Finite Sets
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$.
Let $Y = Y_I$.
Then the following are equivalent:
- $(1): \quad \SS$ satisfies the marriage condition: for each finite subset $F \subseteq I : \card F \le \card {Y_F}$.
- $(2): \quad$ There exists an injection $f: I \to Y$ such that $\forall k \in I: \map f k \in S_k$.
Pages in category "Hall's Marriage Theorem"
The following 4 pages are in this category, out of 4 total.