1. ## equinumerous power sets

Hi

I am trying to prove that if $A\sim B$ then
$\mathcal{P}(A)\sim \mathcal{P}(B)$

Now $A\sim B$ means that there is some bijection from A to B. And I need
to prove that there is also some bijection from $\mathcal{P}(A)$ to
$\mathcal{P}(B)$. So first thing, I need to come up with some function and then prove that its one to one and onto.

Can people provide me some hints to begin with to come up with such a function ?

Thanks

2. ## Re: equinumerous power sets

Suppose you have a group of people each of whom has his/her passport. You need to show that there are as many subgroups of people as there are subsets of passports. Given a subgroup of people, don't you have an idea which passports you want to associate with this subgroup?

3. ## Re: equinumerous power sets

The function is the easy part, as emakarov hints. If you have f: A <--> B, creating a bijection g: P(A) <--> P(B) is not hard to figure out. For a given subset of A, you can get a unique corresponding subset of B by taking the image of f on the members of the subset.

The remainder of the proof involves showing that this is a bijection. Since f is a bijection, g by its definition is defined everywhere on P(A), so it's a left-total relation. Since f is a function, g is right-definite (g only assigns one subset of B to each subset of A). These two properties imply that g is a function. It remains to show that g is left-definite (injective or one-to-one) and right-total (surjective or onto), but you should be able to figure that out on your own.

4. ## Re: equinumerous power sets

Since $A\sim B$ there is a bijection,

$f:A\to B$

Now consider the set,

$h=\{(s_1,s_2)\in \mathcal{P}(A)\times\mathcal{P}(B)\;|\;s_2=f(s_1) \}$

This is a relation from $\mathcal{P}(A)$ to $\mathcal{P}(B)$.
First we prove that

$h:\mathcal{P}(A)\to \mathcal{P}(B)$

and then we prove that its one to one and onto. So h is a bijection. So

$\mathcal{P}(A) \sim \mathcal{P}(B)$

5. ## Re: equinumerous power sets

That's on the right track but there are details you have wrong. It's not the case that (s1, s2) is necessarily in P(A) x P(B) if s2 = f(s1). f operates on the domain A, while h operates on the domain P(A), so that doesn't make any sense as it is written. Try defining h so that it is the (s, t) in P(A) x P(B) where the elements of t are determined by taking each element in s and applying f.

6. ## Re: equinumerous power sets

Originally Posted by Annatala
f operates on the domain A, while h operates on the domain P(A), so that doesn't make any sense as it is written.
I assume the OP redefined the notation $f(s)$ to mean $\{f(x)\mid x\in s\}$ when $s\in\mathcal{P}(A)$. This is sometimes done. I've also seen people use $f[s]$ to distinguish it from $f(x)$.

7. ## Re: equinumerous power sets

if $s \in \mathcal{P}(A) \Rightarrow s \subseteq A$

and since $f:A\to B$ , we have

$f(s)=\{f(x)\mid x\in s\}$ . This is how Velleman defines it in his book
"How to prove it". So Annatala , I don't understand what you are trying to say.