Here is some material I wrote several years ago.
I hope it helps.
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
Thanks for that. I followed most of it.
I think I have the first part of the proof down (that the function g is bijective). Although, I am still not sure how to do the second part of the proof:
"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."
The way it's written it sounds like the afore proof should have guided me to some kind of answer, but I'm not seeing it.
Thanks for the help