$\mathcal{R}$ is a relation and $|A'|\leq|h(A')|$ for all $A'\subseteq A\implies \exists$ an injection $f:A\to B$ such that $f\subseteq\mathcal{R}$.

Question

I tried many times but to no avail on this problem. Please shed me some light!

Theorem: Suppose that $\mathcal{R}$ is a relation, $A=\mathrm{dom}(\mathcal{R})$ and $B=\mathrm{ran}(\mathcal{R})$ are finite, $h(A')=\{b\in B\mid \exists a\in A'\text{ such that } a\mathcal{R}b\}$ for $A'\subseteq A$, and that $|A'|\leq|h(A')|$ for all $A'\subseteq A$. Then there exists an injection $f:A\to B$ such that $f\subseteq\mathcal{R}$.

Answer 1

We will prove this theorem by induction on $|A|$. It's clear that the theorem is true for $|A|=1$. Assume it is true for $|A|=n$. For $|A|=n+1$. Consider two cases.

1. $|A'|<|h(A')|$ for all $A'\subseteq A$

Let $A_1=A-\{a\}$ for some $a\in A$, and $b\in h(\{a\})$. Then $|A_1|=n$. For all $A'\subseteq A_1$, $|A'|<|h(A')|\leq |h(A')-\{b\}|+1$. So $|A'|\leq |h(A')-\{b\}|$. Since the theorem is true for $|A|=n$, there is an injection $f':A_1\to B-\{b\}$ such that $f'\subseteq\mathcal{R}$. Since $(a,b)\notin f'$ and $(a,b)\in\mathcal{R}$, $f=f'\cup\{(a,b)\}$ is the required function.

2. There exists $\varnothing\neq A^{*}\subseteq A$ such that $|A^{*}|=|h(A^{*})|$

Let $A_1=A-A^{*}$. We will prove that for all $A'\subseteq A_1,|A'|\leq |h(A')-h(A^{*})|$.

Assume the contrary, there exists $A'\subseteq A_1$ such that $|A'|>|h(A')-h(A^{*})|$. Therefore, $|A'\cup A^{*}|=|A'|+|A^{*}|>|h(A')-h(A^{*})|+|h(A^{*})|=$ $|(h(A')-h(A^{*}))\cup h(A^{*})|=|h(A')\cup h(A^{*})|=|h(A'\cup A^{*})|.$ To sum up, $|A'\cup A^{*}|>|h(A'\cup A^{*})|$. This contradicts the fact that $|A'\cup A^{*}|\leq|h(A'\cup A^{*})|$ [Since $A'\cup A^{*}\subseteq A$].

Thus for all $A'\subseteq A_1,|A'|\leq |h(A')-h(A^{*})|$. So there is an injection $f_1:A_1\to B-h(A^{*})$ such that $f_1\subseteq\mathcal{R}$. We also have an injection $f_2:A^{*}\to h(A^{*})$ such that $f_2\subseteq\mathcal{R}$. Since $f_1\cap f_2=\varnothing$, $f=f_1\cup f_2$ is the required function.