I'm studying on my own over the summer and I'm having a bit of trouble with this question. Also, I don't have any background in this, I haven't taken any classes in this yet so, if you choose to help, please go slow. Thanks. Anyway, here is the problem:
For any set A, finite or infinite, let B be the set of all functions mapping A into the set {0,1}. Show that the cardinality of B is the same as the cardinality of P(A) (power set of A).
Here's what progress I've made. Let f be a mapping from B to P(A). Now I have to show it's injective. Let g,h be elements of B and let x be an element of A:
f(g(x)) = f(h(x))
g, h are elements of B and B maps x to {0,1}. If g(x) = h(x) = 1 or g(x) = h(x) = 0 then we are done. But what about the possibility of g(x) = 1 and h(x) = 0 or vice-versa. How do I deal with that possibility?
Answer
Hint: treat $B$ as a kind of indicator function for $P(A)$ - i.e. if $f:A\to\{0,1\}$ is a function, then $\{a \in A : f(a) = 1\}$ is a subset of A
With regards to your answer, if two sets to have the same cardinality, then there exists a bijective function between them. But that doesn't mean that every function between them has to be bijective (e.g. {0,1} and {0,1} have the same cardinality, but I can take a function that maps everything to 0 - it is not bijective).
So in order to prove that two things have the same cardinality, you need to find a bijection between them, not prove that any function between them is a bijection.
No comments:
Post a Comment