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:
“The loosening, for some people, of rigid role definitions for men and women has shown that dads can be great at calming babies—if they take the time and make the effort to learn how. It’s that time and effort that not only teaches the dad how to calm the babies, but also turns him into a parent, just as the time and effort the mother puts into the babies turns her into a parent.”
—Pamela Patrick Novotny (20th century)
“Most personal correspondence of today consists of letters the first half of which are given over to an indexed statement of why the writer hasn’t written before, followed by one paragraph of small talk, with the remainder devoted to reasons why it is imperative that the letter be brought to a close.”
—Robert Benchley (1889–1945)
“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)