0

So I'm trying to prove the following,

Prove that if $A\sim B$ then $\mathscr{P}(A) \sim \mathscr{P}(B)$.

Here's how I started out to prove there is a function that is injective:

Suppose $A \sim B$. Then we can choose a function $f:A\rightarrow B$ that is one-to-one and onto. Let's define $H: \mathscr{P}(A) \rightarrow\mathscr{P}(B)$. Suppose $H(A)=H(B)$. Then if $x\in A$ then $f(x)\in H(A)$. Also if $y\in B$ then $f(y)\in H(B)$.

My question is can I say $f(x)=f(y)$ and since $f$ was one-to-one $x=y$. So $H$ is injective.

Here's how I started the proof to show $H$ is surjective. I have no idea about this one:

To see that $H$ is onto, suppose $y\in\mathscr{P}(B)$ and $x\in\mathscr{P}(A)$. Since $f$ was onto we can choose a $w\in X$ such that $f(w)=z$, therefore $H(X)=z$ as required.

Any help is appreciated.

Henrik supports the community
  • 6,831
ChemDude
  • 421
  • There are many more elements in the domain of $H$ than just $A$. You seem to not account for the others. – GFauxPas Apr 17 '15 at 21:50
  • You didn't define $H$, you only gave its domain and codomain. $H:X\mapsto {f(a) / a \in X}$. And I think it'd be easier to build its inverse and prove that it is indeed its inverse instead of proving that it's bijective. – xavierm02 Apr 17 '15 at 21:50
  • You need to be specific in how you define $H$, before you can say anything about it. – Henrik supports the community Apr 17 '15 at 21:51
  • So if I define $H:X\mapsto {f(a) / a \in X}$ then can I say H(A)=H(B). And continue on with the proof. Also @xavierm02 I have no idea how to build the inverse and prove it as you said. Could you give me some more information. – ChemDude Apr 17 '15 at 21:59
  • $H(B)$ isn't defined. $B\in \mathcal P(B)$ which is the codomain of $H$. And to prove that a function is the inverse of another, you just prove that when you compose them (on both sides), you get the identity. – xavierm02 Apr 17 '15 at 22:29

2 Answers2

2

By assumption there is a bijection $f:\>A\to B$. We are asked to construct a bijective function $H:\>{\cal P}(A)\to{\cal P}(B)$. Your $H$ is coming out of thin air; therefore it's difficult to prove anything about it.

For this construction we should use the given data, namely the information contained in $f$. How could we use this $f$ to produce a map $H$ that operates on subsets $X\subset A$ instead of on points $x\in A$? The most simple and natural thing is to put $$H(X):=\bigl\{f(x)\in B\>\bigm|\>x\in X\bigr\}\ .$$ In less formal circumstances one would simply write $f(X)$ instead of $H(X)$.

I claim that this $H$ has the desired properties, and leave it to you to provide a proof. There is no new idea needed; just go through the motions.

Let's prove that $H$ is injective! If $X$ and $Y$ are different subsets of $A$ we may assume that there is an $x\in X\setminus Y$. Then $x':=f(x)\in H(X)$, but $x'\notin H(Y)$, because $x'\in H(Y)$ would mean that there is a $y\in Y$ with $f(y)=x'$, and this would contradict the injectivity of $f$. This proves $H(X)\ne H(Y)$.

Christian Blatter
  • 226,825
1

A function $f: A\to B$ naturally induces a function $\mathcal P(f):\mathcal P(A)\to\mathcal P(B)$ that will work.

It's really easy, so try to think about it for a minute, but if you need more help:

Hint: Look at the function that for an element $C\in\mathcal P(A)$ (i.e. $C\subseteq A$) applies $f$ to all elements $c\in C$.

Another hint:

A function $\mathcal P(A)\to\mathcal P(B)$ takes an element $X\in\mathcal P(A)$ i.e. a subset of $A$, which we can write as $\{a_1, a_2,\ldots, a_i\}$, and gives an element of $\mathcal P(B)$ which we could write $\{b_1, b_2,\ldots, b_j\}$.

Henrik supports the community
  • 6,831