-2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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)|.$ $\endgroup$ Apr 27, 2021 at 20:56

1 Answer 1

8
+100
$\begingroup$

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).$

$\endgroup$
3
  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Xander Henderson
    Apr 29, 2021 at 23:11
  • $\begingroup$ @QuantamSpace Thanks! Your answer is more elegant but I’m looking for a solution the book was likely to come up with. @Baretelby’s solution is more likely. $\endgroup$
    – Arbuja
    May 1, 2021 at 10:27
  • 1
    $\begingroup$ 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\,\}$. $\endgroup$ May 1, 2021 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.