Cardinalities of power set vs B^A

[Gh0stZA]

Hi everyone,

If $$B^A$$ is the set of functions mapping from $$A \rightarrow B = \{ 0, 1 \}$$, prove that $$|B^A| = |P(A)|$$, where P(A) is the power set of A.

Is it as simple as letting the mapping from B to A be denoted by $$\phi$$ and defining $$a_1, a_2 \in A, a_1 \ne a_2$$ such that $$\phi (a_1) = 0$$ and repeating that for the empty set, and $$\phi (a_2) = 1$$ and then $$\phi ( \{ a_1, a_2 \} ) = \{ 0, 1 \}$$ ?

All help appreciated.

 

[jgens]

Just notice that every map A→{0,1} is the characteristic function of some subset of A.

 

[Gh0stZA]

Just notice that every map A→{0,1} is the characteristic function of some subset of A.

Can you please elaborate on this?

 

[jgens]

Suppose $f \in 2^A$ and define $E=\{x \in A:f(x)=1\}$. Then $f = \chi_E$ and this induces a one-to-one correspondence between the maps in $2^A$ and elements of $\mathcal{P}(A)$.

 

[SteveL27]

Can you please elaborate on this?

In words rather than symbols: You have two buckets, marked YES and NO. You take each element of A and toss it into one of the two buckets. When you're done tossing elements of A into one of the two buckets, whatever's in the YES bucket is a particular subset. But you've also just defined a function from A -> {0,1}.

So subsets and binary functions are the exact same thing. A subset is just the set of elements that got mapped to 1 by some binary function, and vice versa.

The characteristic function of a set is the function that maps the elements of the set to 1, and everything else to 0. For example in the integers, the characteristic function of the even numbers maps 2, 4, 6, etc. to 1, and 1, 3, 5, ... to 0.

So if you have a subset of some set, the characteristic function of the subset is the function that maps each element of the subset to 1. It's the function that tosses exactly those elements into the YES bucket. It's a binary function. Each binary function is the characteristic function of some subset.

 

[Gh0stZA]

I think I understand this concept now. The notation is still a little new to me and I haven't done a lot of "pure" set theory before, especially not recently, but I think I got the basic idea from this.

Thanks guys.

 

[SteveL27]

I think I understand this concept now. The notation is still a little new to me and I haven't done a lot of "pure" set theory before, especially not recently, but I think I got the basic idea from this.

Thanks guys.

Do you mind if I try another explanation? Because once you get this, you'll go, "AHA. That's so OBVIOUS!" rather than, "I think I understand." Because this is really simply once you get it. It's one of those things that just pop into your understanding all at once.

What is a function from a set A to the set {0, 1}. It's simply an assignment of either a zero or a one to each element of the set. You go through the elements of the set one by one and assign each element either a zero or a 1.

Now when you're done, you see that the collection of elements that got assigned 1 is a subset of the original set. So a binary function gives you a subset.

But if you had a subset, you can get back a binary function: namely, the characteristic function of the subset -- the function that assigns 1 to the elements of the subset, and 0 to everything else.

So you see there's a one-to-one correspondence between binary functions and subsets. Given a binary function it defines a subset; given a subset it defines a binary function.

If you just think about this and work out a few simple examples (using finite sets, say) then at some point the obviousness of this correspondence is just going to make you go OH. That is SIMPLE! Once you see it, it's obvious. Until you see it, it's mysterious.