Let A be a non-empty set. Consider F = {f : A → {0, 1}}, the set of all functions on A with values in {0, 1}. Consider the function g : P (A) → F , B → X_B , where X_B is the characteristic function of the subset B ⊆ A: X_B(a) = 1, if a∈B, and X_B(a) = 0, if a∉B. Show that g is a bijection. As a consequence show that the number of subsets of a set with n elements is 2^n . This may justify the notation {0, 1}^A used for F.

Where P represents the power set of A.

I am very lost. We just started the chapter on cardinality and I am already struggling . I don't really know how to begin the question, so some direction would be nice. I tried to work out the one-to-one portion of the proof, but I am not sure if I am using the characteristic function correctly. Will I need to use it to show 1-1 and onto?

Here is my stab at 1-1:

Here is an attempt at a 1-1 proof:

So, I choose elements X_B1=X_B2∈P(A) where X_B1 and X_B2 are functions with same domain A and try to show g(X_B1)=g(X_B2). So, then ∃a∈A such that X_B1(a)=X_B2(a). I can then assume X_B1(a)=X_B2(a)=1. So, we know a∈B for both functions. So, g(X_B1)=g(X_B2). Therefore, g is one-to-one.

Is that how I use the characteristic equations? I am having a harder time with the onto proof.

Thanks for your help

--Dan