# Homework Help: Help with proof

1. Sep 5, 2008

### LMKIYHAQ

1. The problem statement, all variables and given/known data

You have a set A. Let $$B^{A}$$ be the set of all functions mapping A into the set B={0,1}. Prove the cardinality of$$B^{A}$$ = the cardinality of the power set of A.

2. Relevant equations[/b

3. The attempt at a solution
I feel about 50% sure about the proof. What do you think? Since A is a set, A has n elements where n is a natural number. Let g be the function mapping A into B s.t {n$$\in$$A : n = 0 or n = 1}. So for each n in A there are 2 distinct possibilities (i. e mapping to 0 or 1). Since $$B^{A}$$ is the set containing all functions of type g, the cardinality of $$B^{A}$$ = $$2^{n}$$, which is also known as the cardinality of the power set of A.

Thanks for helping!

2. Sep 5, 2008

### Dick

If you want to show the cardinalities are equal the easiest way is to exhibit a 1-1 mapping between subsets of A and members {0,1}^A. Your 'proof' doesn't actually ever say what it is. Can you be more explicit? If you have subset S of A define the mapping. If you have a mapping define the subset.

3. Sep 6, 2008

### LMKIYHAQ

I'm not sure how to create a mapping from the power set of A into the interval? Since the problem talks about the functions of A, I'm not sure what the power set of A would look like?

4. Sep 6, 2008

### Dick

It's not an interval. B={0,1} is just the set consisting of the elements 0 and 1. B^A is just the set of all mappings from A->B, i.e. all functions f, such that f(a)=0 or 1 for each a in A. If you have a subset C of A what's the obvious way to define the corresponding function f? If you have a function f what's the corresponding subset C?

5. Sep 7, 2008

### LMKIYHAQ

You said there is an obvious function, but it is not obvious to me. Would the function C (the subset of A) going to B be the function of P(A)? I know we have to show there is a 1-1 function from P(A) to B (to the A). I have no idea how.

6. Sep 7, 2008

### Dick

Given a subset C, to me the obvious function f is f(a)=0 if a is not in C and f(a)=1 if a is in C. Given a function f define C={a such that f(a)=1}. It's called the characteristic function of the subset.