# Why does $|A|\le|B|$ imply $|\mathcal{P}(A)|\le|\mathcal{P}(B)|$? (Use elementary notations; for beginners to advanced math)

Edit: @QuantamSpace’s answer contains advanced notation. I need notation that is more elementary, using Chapter 5.4 in A Transition To Advanced Math: 8th Edition

According to the answer key the following is true: If $$|A|\le|B|$$ then $$2^{|A|}\le 2^{|B|}$$.

For finite sets, if $$|A|\le|B|$$ then $$2^{|A|}\le 2^{|B|}$$. Since $$|\mathcal{P}(A)|=2^{|A|}$$ and $$|\mathcal{P}(B)|=2^{|B|}$$, $$|\mathcal{P}(A)|\le|\mathcal{P}(B)|$$. However, for infinite sets, does this hold?

Attempt (EDIT: My Attempt is wrong. You can ignore this part.)

According to my textbook I learned the following (using Cantor's Theorem):

$$|A|\le \mathcal|{P}(A)|$$ and $$|B|\le \mathcal|{P}(B)|$$.

Moreover, since $$|A|\le|B|$$, $$f:A\xrightarrow{1-1}B$$, $$i:A\xrightarrow{1-1}\mathcal{P}(A)$$ and $$g:B\xrightarrow{1-1}\mathcal{P}(B)$$.

To prove a counter example we need that $$h:\mathcal{P}(B)\to\mathcal{P}(A)$$ is one-to-one so that $$|\mathcal{P}(B)|\le|\mathcal{P}(A)|$$.

Now suppose if $$|A|\le |B|$$ then $$|\mathcal{P}(A)|\le|\mathcal{P}(B)|$$; also suppose $$i=h \circ g \circ f$$. We already know $$i$$ is one-to-one. Hence, since $$h \circ g$$ is one-to-one, $$f$$ is one-to-one. Therefore $$\mathcal{P}(B)\le\mathcal{P}(A)$$. This is a contradiction. Hence we have shown a counter example.

Question: Am I correct. Is the answer key wrong?

• You don't need Cantor to show $|A|\le |P(A)|$. The injection $x\mapsto \{x\}$ already gives this. Cantor's theorem gives the stronger $|A|<|P(A)|.$ Also, even if your argument were correct, showing $|P(B)|\le |P(A)|$ would not suffice since this does not imply $|P(A)|\not\le |P(B)|.$ Apr 27, 2021 at 20:56

Note that the assumption $$|A| \le |B|$$ means that there is one-one function $$f: A \to B$$. Define a function $$F: \mathcal{P}(A) \to \mathcal{P}(B)$$ by $$F(X)= f[X]:= \{f(x): x \in X\}$$ for $$X \in \mathcal{P}(A)$$.
Then $$F$$ is one-one. To see this, assume that $$X \ne Y$$. Then without loss of generality, we may assume that $$X \not\subseteq Y$$ and thus there is $$x \in X$$ such that $$x \notin Y$$. Then note that $$f[X] \ne f[Y]$$, because if they would be equal, then $$f(x) \in f[Y]$$ so there would be $$y \in Y$$ with $$f(x) = f(y)$$ which would imply that $$x=y\in Y$$, since $$f$$ is injective. This contradicts the fact that $$x \notin Y$$.
That $$F$$ is injective means precisely that $$|\mathcal{P}(A)| \le |\mathcal{P}(B)|$$, and we are finished.
Intuitively, you can expect this to be true as well: $$|A| \le |B|$$ means that you can embed $$A$$ as a subset of $$B$$, and a subset of $$B$$ is a subset of $$A$$ so we see that $$\mathcal{P}(A)$$ can be seen as a subset of $$\mathcal{P}(B).$$
• Since the title explicitly asks for elementary notations, I think it would be better to avoid overloading the name $f$ to also denote a function $\mathcal P(A)\to\mathcal P(B)$, indeed the same function as $F$, which you do when writing $F(X)=f(X)$ for $X\in\mathcal P(A)$. It would be clearer to expand its definition, by saying: $F(X)=\{\, f(x)\mid x\in X\,\}$. May 1, 2021 at 13:05