# Proving Two sets have same cardinality

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?

• You have to show that a bijective map exists. You cannot show that any given map is bijective. Commented Jun 29, 2014 at 14:01
• You haven't said what $f$ is, there's no reason to assume it is injective at all. Certainly not all functions from $B$ to $P(A)$ are injective, so without explicitly constructing the function you cannot complete this proof. Commented Jun 29, 2014 at 14:01

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
Given some $f \in B$ consider $$S_f = \{x \in A : f(x) = 1\} \in P(A)$$ prove this correspondence is a bijection. That is show $f \mapsto S_f$ is a bijection $B \to P(A)$.