Cardinality problem

[stiffy]

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 really don't know where to start with this problem. We just started going over the concept of cardinality yesterday. The only thing I really know about this stuff is that for every element we "point" at in a set A, we create another set {1,2,3...,n}. Then we can create a function that gives us each element from set A by plugging in each element from the counting set.

So, I'm not sure how to show g is a bijection. There just seems to be a lot going on in this problem and a lot of new notation. I would appreciate some direction.

Thank you very much,

Dan

 

[daon]

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 really don't know where to start with this problem. We just started going over the concept of cardinality yesterday. The only thing I really know about this stuff is that for every element we "point" at in a set A, we create another set {1,2,3...,n}. Then we can create a function that gives us each element from set A by plugging in each element from the counting set.

So, I'm not sure how to show g is a bijection. There just seems to be a lot going on in this problem and a lot of new notation. I would appreciate some direction.

Thank you very much,

Dan

Break it down. You have to show (1) g is 1-1, and (2) g is onto.

(1) Let X_B = X_C be two sets in the range of g (so that B and C are both subsets of A). Can you show that B=C? i.e., that B and C contain the same elements of A?
(2) If X_B is an element in the range of g, is there a subset B of P(A) that gets sent to X_B?

For the corollary, use the fact that the number of functions on A getting sent to {0,1} is 2^|A| since each element has a choice of going to 0 or 1.

 

[stiffy]

I am still lost.

When I try to work it out I just get a mess of symbols that don't all connect. I don't see how the characteristic equations helps me show g is 1-1 and onto.

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 again for your help

--Dan

 

[daon]

I am still lost.

When I try to work it out I just get a mess of symbols that don't all connect. I don't see how the characteristic equations helps me show g is 1-1 and onto.

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 again for your help

--Dan

X_B1 and X_B2 are not elements of P(A), they are functions from A to {0,1}.

X_B1 = g(B1).
X_B2 = g(B2).

if X_B1 = X_B2 then, X_B1(a) = X_B2(a) FOR ALL a. That is what it means for two functions to be equal.

Let x be an element in B1. Assume x does not belong to B2. Then X_B1(x) = 1 and X_B2(x)=0. This contradicts the fact they are the same function. Therefore x also belongs to B2. Its the same the other way.
Thus B1 = B2.