Editing Hall's marriage theorem (section)

== Infinite families ==

=== Marshall Hall Jr. variant ===
By examining [[Philip Hall]]'s original proof carefully, [[Marshall Hall (mathematician)|Marshall Hall Jr.]] (no relation to Philip Hall) was able to tweak the result in a way that permitted the proof to work for infinite <math>\mathcal F</math>.<ref>{{harvnb|Hall|1986|loc=pg. 51}}</ref> This variant extends Philip Hall's Marriage theorem.

Suppose that <math>\mathcal F = \{A_i\}_{i\in I}</math>, is a (possibly infinite) family of finite sets that need not be distinct, then <math>\mathcal F</math> has a transversal if and only if <math>\mathcal F</math> satisfies the marriage condition.

===Marriage condition does not extend===
The following example, due to Marshall Hall Jr., shows that the marriage condition will not guarantee the existence of a transversal in an infinite family in which infinite sets are allowed.

Let <math>\mathcal F</math> be the family, <math>A_{0}=\mathbb N</math>, <math>A_{i}=\{i-1\}</math> for <math>i\geq 1</math>. The marriage condition holds for this infinite family, but no transversal can be constructed.<ref>{{harvnb|Hall|1986|loc=pg. 51}}</ref>

===Graph theoretic formulation of Marshall Hall's variant===
The graph theoretic formulation of Marshal Hall's extension of the marriage theorem can be stated as follows: Given a bipartite graph with sides ''A'' and ''B'', we say that a subset ''C'' of ''B'' is smaller than or equal in size to a subset ''D'' of ''A'' ''in the graph'' if there exists an injection in the graph (namely, using only edges of the graph) from ''C'' to ''D'', and that it is strictly smaller in the graph if in addition there is no injection in the graph in the other direction. Note that omitting ''in the graph'' yields the ordinary notion of comparing cardinalities. The infinite marriage theorem states that there exists an injection from ''A'' to ''B'' in the graph, if and only if there is no subset ''C'' of ''A'' such that ''N''(''C'') is strictly smaller than ''C'' in the graph.<ref>{{Cite journal|last=Aharoni|first=Ron|date=February 1984|title=König's Duality Theorem for Infinite Bipartite Graphs|journal=Journal of the London Mathematical Society|volume=s2-29|issue=1|pages=1–12|doi=10.1112/jlms/s2-29.1.1|issn=0024-6107}}</ref>

The more general problem of selecting a (not necessarily distinct) element from each of a collection of [[Empty set|non-empty]] sets (without restriction as to the number of sets or the size of the sets) is permitted in general only if the [[axiom of choice]] is accepted.