-1
$\begingroup$

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.

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

1 Answer 1

Reset to default
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – plsneedhelp
    Nov 19, 2018 at 23:06
  • $\begingroup$ To me it seems that $|\{f(A_i)∣i∈I\}|≥|I|$ is more like $|\{f(A_i)∣i∈I\}|=|I|$? $\endgroup$
    – plsneedhelp
    Nov 19, 2018 at 23:08
  • $\begingroup$ 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. $\endgroup$
    – Eugen
    Nov 20, 2018 at 9:16

Not the answer you're looking for? Browse other questions tagged .