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)
“After the first powerful plain manifesto
The black statement of pistons, without more fuss
But gliding like a queen, she leaves the station.”
—Stephen Spender (1909–1995)
“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)