Definitions and Statement of The Theorem
Let S be a family of finite sets, where the family may contain an infinite number of sets and the individual sets may be repeated multiple times.
A transversal for S is a set T and a bijection f from T to S such that for all t in T, t is a member of f(t). An alternative term for transversal is system of distinct representatives or "SDR".
The collection S satisfies the marriage condition (MC) if and only if for each subcollection, we have
In other words, the number of sets in each subcollection W is less than or equal to the number of distinct elements in the union over the subcollection W.
Hall's theorem states that S has a transversal (SDR) if and only if S satisfies the marriage condition.
Read more about this topic: Hall's Marriage Theorem
Famous quotes containing the words definitions, statement and/or theorem:
“What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
—G.C. (Georg Christoph)
“The force of truth that a statement imparts, then, its prominence among the hordes of recorded observations that I may optionally apply to my own life, depends, in addition to the sense that it is argumentatively defensible, on the sense that someone like me, and someone I like, whose voice is audible and who is at least notionally in the same room with me, does or can possibly hold it to be compellingly true.”
—Nicholson Baker (b. 1957)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)