# Prove that there exists an injective mapping $f : B → A$ [closed]

Given a set $$A$$ with $$n$$ elements and $$B = \{A_1,A_2,...,A_n\} ⊆ 2^A$$. Prove that there exists an injective mapping $$f : B → A$$ such that $$f(A_i) ∈ A_i$$ for all $$i ∈ \{1,2,...,n\}$$ if and only if for all I ⊆ {1, 2, . . . , n} the cardinality of $$\bigcup\limits_{i∈I}^{} A_i$$ is at least equal to the cardinality of $$I$$.

I am not sure how to solve this one.

• What exactly does $2A$ mean. Nov 19, 2018 at 21:16
• I assume $2A$ should be $2^A$... Nov 19, 2018 at 21:21
• Sorry typo, is fixed now Nov 19, 2018 at 21:21
• Does $2^A$ stand for all the permutations of A? Nov 19, 2018 at 21:24
• All subset of $A$. I think Nov 19, 2018 at 21:25

## 1 Answer

$$\Rightarrow$$. $$|\bigcup_{i\in I}A_i| \ge |\{ f(A_i) \mid i\in I\}| \ge |I|$$. For the first inequality just select one element from each $$A_i$$, namely $$f(A_i)$$. For the second inequality, use the injectivity of $$f$$.

$$\Leftarrow$$. By an easy induction on $$j$$, one can show that $$\bigcup_{j\in\{1,\dots,i+1\}}A_j$$ contains at least one element from $$A_{i+1}$$ that is not in $$\bigcup_{j\in\{1,\dots,i\}}A_j$$. Pick this element as $$f(A_{i+1})$$.

• What exactly does the first statement show that we need for the second statement? Second one: i goes from 1..n but i+1 can be more than n? Nov 19, 2018 at 23:06
• To me it seems that $|\{f(A_i)∣i∈I\}|≥|I|$ is more like $|\{f(A_i)∣i∈I\}|=|I|$? Nov 19, 2018 at 23:08
• The first and second statements are independent. In the second statement $i$ goes from $0$ to $n-1$. I don't think $|\{f(A_i)\mid i\in I\}| = |I|$ is correct. You could take $A_i=A$ and then for $I=\{1\}$ one has $n$ on the left-hand side and $1$ on the right-hand side. Nov 20, 2018 at 9:16