Let $A, B$ be sets. Prove that if $A$ and $B$ are equinumerous, then $\mathcal{P}(A)$ and $\mathcal{P}(B)$ are equinumerous.

Let $$A, B$$ be sets. Prove that if $$A$$ and $$B$$ are equinumerous, then $$\mathcal{P}(A)$$ and $$\mathcal{P}(B)$$ are equinumerous.

Hello everyone. I am having some trouble with this proof. I know that I have to show a bijection between $$\mathcal{P}(A)$$ to $$\mathcal{P}(A)$$. For injection, I have to have an $$x_1,x_2$$ such that $$f(x_1)=f(x_2)$$ and $$x_1=x_2$$. For surjection, I have to show that for a $$b$$ in the codomain, there exists an $$a$$ such that $$f(a)=b$$. The part that I don't understand is how to come up with a function so that I can show this injection.

• Hint: Because $A$ and $B$ are equinumerous we know for a fact that there exists a bijection between them. Let $\phi$ be that bijection. Now... let us try to come up with a bijection between $\mathcal{P}(A)$ and $\mathcal{P}(B)$. We can use $\phi$ somehow in that definition. May 28, 2020 at 2:19

1 Answer

By means of an example, let's look at the following:

Let $$A = \{1,2,3,4,5\}$$ and let $$B = \{\text{one},\text{two},\text{three},\text{four},\text{five}\}$$

Notice that $$A$$ and $$B$$ are equinumerous and there is an obvious bijection between $$A$$ and $$B$$, the one mapping an arabic numeral to the corresponding English name for a number. That is, letting $$\phi$$ be the name of that bijection we have $$\phi(1)=\text{one}$$ and $$\phi(2)=\text{two}$$ and so forth...

Now... the power set of $$A$$ looks like $$\mathcal{P}(A)=\{\emptyset,\{1\},\{2\},\dots,\{1,2\},\{1,3\},\dots,\{1,2,3,4,5\}\}$$ is the set of all subsets of $$A$$.

The power set of $$B$$ on the other hand looks like $$\mathcal{P}(B)=\{\emptyset,\{\text{one}\},\{\text{two}\},\dots,\{\text{one,two}\},\{\text{one,three}\},\dots,\{\text{one,two,three,four,five}\}\}$$

Now... there is a natural choice for a bijection between these. What might the natural choice be for what to map $$\{1,3,4\}$$ to for instance?

We can map $$\{1,3,4\}$$ to $$\{\text{one,three,four}\}$$

Now... can you generalize and formalize this natural choice of mapping for arbitrary sets $$A$$ and $$B$$ given a particular bijection $$\phi$$ between $$A$$ and $$B$$?

Now that you have your function you expect should be a bijection between $$\mathcal{P}(A)$$ and $$\mathcal{P}(B)$$, can you now go and prove that it is in fact a bijection?