Finding Cardinality of Power Set

[crownedbishop]

Homework Statement

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

Homework Equations

P(A) is the power set of A

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 2ⁿ binary strings of length n. We would do the same for S. to show that |S|=2ⁿ. 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.

 

[LCKurtz]

Homework Statement

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

Homework Equations

P(A) is the power set of A

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 2ⁿ binary strings of length n. We would do the same for S. to show that |S|=2ⁿ. 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.

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.

 

[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}.

 

[verty]

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}.

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.

 

[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}

 

[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.

 

[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.

 

[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.

 

[LCKurtz]

@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.

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}.

 

[crownedbishop]

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}.

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

 

[LCKurtz]

The identity map is from P(A) to S.

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.

Anyways, if we define f(a)= 1 if a\inC and f(a)=0 if a\notin.

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).

Then, \forallC\inP(a) and \foralld\inS, we define CRd if f(a)=d(a). Wouldn't it suffice to show that the relation R is a bijective function?

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.