Let P be the power set of {a,b,c} Define a function from P to the set of integers as follows: f(A) = |A| . (|A| is the cardinality of A.) Is f injective? Prove or disprove. Is f surjective? Prove or disprove.
I'm having a hard time understanding what this question is asking (as I have with most discrete math problems). What does it mean by "Let P be the power set of..."? What is a power set? Thanks for any help.
1 Answer
The power set of a set is the set of all subsets. So, for example, for the set $\{a,b,c\}$, the power set is:
$\{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$. The function $f$ gives the cardinality of a given subset. For example, $f(\{a,c\})=2$, $f(\emptyset)=0$, and so on.
Then you have to prove whether the function is injective, i.e. if $f(A)=f(B)$ for some subsets $A$ and $B$, does it have to be the case that $A=B$?
And for surjectivity, is it true that for every integer $n$, there is a subset $A\subseteq \{a,b,c\}$ such that $|A|=n$?
