0
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – JMoravitz
    May 28, 2020 at 2:19

1 Answer 1

2
$\begingroup$

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?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .