# Finding Cardinality of Power Set

1. May 20, 2014

### crownedbishop

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

Let S be the set of functions from a set A to {0,1} Prove that |P(A)|= |S|

2. Relevant equations

P(A) is the power set of A

3. The attempt at a solution
I have no idea how to do this... If A is finite then A has n elements, and we can write out the elements from one to n (1,2,3,...,n) in the power set if the element is in the set we can write one for the element. If not we can write zero for it, and thus there are 2n binary strings of length n. We would do the same for S. to show that |S|=2n. Surely, we wouldn't be able to extend this process to any uncountable sets. Maybe it's possible to construct a bijective f from P(A) to S, but I don't see any ways to do this.

2. May 21, 2014

### LCKurtz

Hint: Picking some elements of A to make a subset B is similar to having a function f on A such that for each a in A, f(a) = 1 if a is to be in B and f(a) = 0 if a isn't in B.

3. May 24, 2014

### crownedbishop

Well, could we just define a subset of A by assigning a "0" or "1" to each element aεA? Then the set of all subsets would be the set of all functions from A to {0,1}.

4. May 24, 2014

### verty

Yes, you certainly could decide that functions are more elementary than subsets. Usually it is the other way around but that is certainly logical. But a more standard thing to do is to show there is a bijection between the two sets, which means their cardinality must be the same.

5. May 24, 2014

### HallsofIvy

The assignment of subset X to the function that is 0 if the variable is in X and 1 if x is not in X is a bijection between the subsets of A and the functions from A to {0, 1}

6. May 24, 2014

### LCKurtz

@crownedbishop: You have to show that the map that maps a subset of A to its corresponding function is a bijection. It's easy but you can't just assert it. Show that map is 1-1 and onto.

7. May 25, 2014

### crownedbishop

@LCKurtz, I didn't assert that it is just a bijection, but that it is an identity map. Perhaps, this is not the standard definition of a subset, though.

8. May 25, 2014

### verty

Crownedbishop, you were saying that binary strings can't be extended to the uncountable case, but do you know that you can generate the function directly with a set comprehension? That way, you can work with functions instead of binary strings.

The one caveat is that you must write it in the correct way to comply with the separation axioms. But anyway, a short verbal proof will surely be adequate.

9. May 25, 2014

### LCKurtz

How can it be an identity map when the domain and range are different? The domain is P(A) and the range is the set of functions from A to {0,1}.

10. May 25, 2014

### crownedbishop

The identity map is from P(A) to S.
Anyways, if we define f(a)= 1 if a$\in$C and f(a)=0 if a$\notin$. Then, $\forall$C$\in$P(a) and $\forall$d$\in$S, we define CRd if f(a)=d(a). Wouldn't it suffice to show that the relation R is a bijective function?

11. May 25, 2014

### LCKurtz

The identity function on a set maps the set to itself. $P(A)\ne S$. You are wanting to show these two sets have the same cardinality by finding a bijection between them, and it isn't the identity.

Just so you know, there is a standard name and notation for this function. It is called the characteristic function of a subset and is usually denoted by $\chi_C$ (different subscript for different subset).

Yes it would. That is what you have to do. But I think you could phrase it more simply by stating that the map $\eta:P(A)\to S$ defined by $\eta(C) = \chi_C$ for $C\in P(A)$ is 1-1 and onto. But my whole point in my replies is that that needs to be done.