The marriage problem

Question

Suppose $B$ is a finite set and $h: B \to \mathcal P(G)$ is a function, such that for each $x \in B,$ $h(x)$ is a finite subset of $G$ and $$X \subset B \Rightarrow |X| \leq \left|\bigcup \{ h(x) \mid x \in X \} \right|,$$ so that (in particular) $h(x) \neq \emptyset$ for all $x$. Prove that there exists an injective function $f: B \to G$ such that for all $x \in B, f(x) \in h(x)$. Show also that the cardinality condition above and that each $h(x)$ being a finite subset are necessary for the existance of the $f$. HINT: Consider whether or not there is some nonempty subset $C$ of $B$ such that $|C| = \left|\bigcup \{ h(x) \mid x \in C \}\right|$.

I am lost on this question, both on providing counterexample for the condition that $h(x)$ being finitr and the main question. For the counterexample of cardinality condition, we may take $\{1\}$ mapping to the empty set (with $G$ an arbitrary set). I tried following the hint, and I thought it was relatively easy to show that if there exists such a set $C$ then it must be that each $x \in C$ gets mapped to a unique singleton - but I was wrong (and it's false, you can easily create a counterexample)$.

Given the interpretation of $B$ as a set of boys and $G$ as a set of girls the boys like to marry, it "seems obvious" but I cannot prove it rigorously, in context of set theory.

Any help would be considered and appreciated.

Edit: There is no assumption of Axiom of Choice. I think the problem is easy if we assume axiom of choice.

Answer 1

The assumption, that $h(x)$ is finite for each $x\in B,$ is superfluous. For consider the set $B'=\{x\in B:h(x)\text{ is finite}\}.$ First, marry off all the boys in $B';$ after that, it is trivial to find mates for the boys in $B\setminus B'.$

The theorem only goes wrong when some $h(x)$ is infinite and $B$ is infinite. For example, let $B=\{b_0,b_1,b_2,b_3,\dots\},$ let $h(b_n)=\{n\}$ for $n=1,2,3,\dots,$ and let $h(b_0)=\{1,2,3,\dots\}.$

For the main question, the hint should be used in a proof by induction on $|B|.$ Of the two cases in the hint, I think the easier case is the one where there is no such $C,$ so I recommend doing that one first. By the way, I don't think the hint is stated correctly; $C$ should be a nonempty proper subset of $B.$

Finally, you are right that the axiom of choice is not needed, but I don't believe there is any easier proof using the axiom of choice. What did you have in mind?

Answer 2

Missing from the problem statement: the function $f:B\to G$ should be injective.

Here are some further hints:

• If a critical set $C$ exists (whose size is smaller than $B$), then by induction all the boys in $C$ can find wives. Removing those wives from the sets of the boys in $B\setminus C$, you can show that $B\setminus C$ still satisfies the Hall condition. To do this, for any $S\subseteq (B\setminus C)$, apply the Hall condition to $S\cup C$.

• If every nonempty, proper subset $C\subseteq B$ is not critical, then choose a boy $b$ and assign him a wife $w$ arbitrarily. Then $B\setminus \{w\}$ still satisfies the Hall condition, because any $C'\subseteq B\setminus \{b\}$ were willing to marry at least $|C'|+1$ girls, and removing $w$ still leaves that at $|C'|$.