2
$\begingroup$

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$.)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You are right that it still works for infinite $X$ if $F(x)$ is always finite. But of course it's trivially false as stated, with no finiteness assumption. I wonder if the OP knows that and just forgot to mention finiteness, or if he really wanted it to be true with no restrictions? $\endgroup$
    – bof
    Commented Aug 25, 2015 at 10:11

You must log in to answer this question.