Given a set $A$ with $n$ elements and $B = \{A_1, A_2, ..., A_n\} \subseteq 2^A$. Prove that there exists an injective mapping $f : B \to A$ such that $f(A_i) \in A_i$ for all $i \in \{1,2,...,n\}$ if and only if for all $I \subseteq \{1,2,...,n\}$ the cardinality of $\bigcup_{i\in I}A_i$ is at least equal to the cardinality of $I$.
I really don't even know where to begin with this one.
- What is $2^A$ supposed to be? Just the 2 power each element of $A$?
- And why do I need $A_1, ...,A_n$?
- Isn't the cardinality of $\bigcup_{i\in I}A_i$ always at least equal to $I$ unless an $A_i = \emptyset$?
How do I even start to prove an injective mapping? The only thing similar to this covered in our lecture were graph colorings and we didn't really do a proof of this sort, the main message was just that colorings are really hard to prove.