Let $X$ be a non-empty set and let $F: X \to {\cal P}(X)$ be a function with the following property:


* for $A \subseteq X$ we have $|A| \leq |\bigcup F(A)|$.


Does this imply that there is an injective function $f: X \to X$ such that $f(x)\in F(x)$? (Note: it is clear that the above condition is necessary for this, and it also implies $F(x) \neq \emptyset$ for all $x\in X$.)



Injective subset function
The answer is Yes if $X$ is finite (and possibly also Yes if $X$ is infinite and has $F(x)$ is finite for all $x\in X$, but I don't know off the top of my head about that). The reason why the answer is positive is that this is a reformulation of [Hall's Marriage Theorem](https://en.wikipedia.org/wiki/Hall's_marriage_theorem).


For infinite $X$ consider the following example. Let $X = \omega$ and set 


* $F(0) = \omega \setminus \{0\}$, and
* $F(n) = \{n\}$ for $n \geq 1$.


Then it is clear that an *injective* map $f: \omega\to \omega$ with $f(m) \in F(m)$ for all $m \in \omega$ can't exist: Suppose we have some map $f: \omega\to \omega$ with $f(m) \in F(m)$ for all $m$. Then $f(0) \in \omega\setminus\{0\}$, say $f(0) = p$. But the definition of $F$ forces $f(p) = p$. Therefore $0\neq p$ but $f(0) = f(p)$ so $f$ is not injective.


