# Hall's Marriage Theorem for correspondence

Let $$A=\{A_1,....A_n\}$$ be a collection of subsets of a finite set $$X$$. A selection for $$A$$ is the image of an injective function $$f:A\to X$$ such that $$f(A_i)\in A_i$$ for every $$A_i\in A$$.

Hall's marriage theorem shows that , $$A$$ has a selection if and only if for each subset $$S\subseteq A$$,

$$|S|\leq |\cup_{i\in S} A_i|.$$

I wonder if it is possible to generalize this result and obtain a similar condition for a choice correspondence $$f:A\rightrightarrows X$$ that selects for each $$A_i$$ more than one elements, i.e. $$f(A_i)\subset A_i$$ and $$|f(A_i)|=2$$ and all selected elements are distinct.

Any ideas or suggestions?

Yes, this is a straightforward extension. Instead of the sequence $$A_1,A_2,\ldots,A_n$$ consider the sequence $$A_1,A_1,A_2,A_2,\ldots,A_n,A_n.$$ The Hall condition for this sequence amounts to $$\left|\bigcup_{i\in S}A_i\right|\ge2|S|.$$
• @sam This doesn't work very well with your (incorrect) definition of a choice function. You should define a choice function as an injection $f:\{1,2,\dots,n\}\to X$ instead of an injection $f:\{A_1,A_2,\dots,A_n\}\to X$ for just this reason, that you don't want to require the sets $A_i$ to be distinct. – bof Nov 30 '18 at 12:51