Prove that $\mathcal{P}(\mathbb{Z}^+)$ is uncountable

Question

Prove: $\mathcal{P}(\mathbb{Z}^+)$ is uncountable

Here is an excerpt from a proof of this result that I am struggling to follow:

As a part of the proof that $\mathcal{P}(\mathbb{Z}^+)$ is uncountable, my textbook defines the set $\bar{{Z}}$ as can be seen in the picture above. What I am confused about, is why we can presume that $\bar{{Z}}$ is not equal to the empty set?

Answer 1

You are correct that $\bar{Z}$ may be empty, but this has no impact on the proof. Regardless of what $\bar{Z}$ is, it is still the case that $\bar{Z}$ is not in the collection of $Z_n$. Since we assumed that the list $Z_n$ was complete, this shows that such a list cannot exist. It will always be missing some subsets - which is precisely the argument being made.

---

Another way to see this is by finding the cardinality explicitly.

Claim: The cardinality of $\mathcal P (\mathbb Z^+)$ is $2^{\aleph _0}$

There are a few different ways to prove the claim. I will get you started on two different approaches:

($1$) The first way is to find an upper and lower bound on the cardinality of $2^{\aleph _0}$ and then apply the Cantor Schroder Bernstein Theorem in order to conclude that the cardinality of $\mathcal P ( \mathbb Z ^+ ) = 2^{\aleph _0}$

We first look for an upper bound: $$ |\mathcal P(\mathbb Z^+) | \leq | \mathcal P( \mathbb Z)| = |2^{\mathbb Z}| = |2|^{|\mathbb Z|} = 2^{\aleph _0}$$ I will leave it to you to find a suitable lower bound in order to apply the Cantor Schroder Bernstein Theorem (note that we need the lower bound to be a set of cardinality $2^{\aleph _0}$).

($2$) Alternatively, a second approach requires you to use the following lemma:

• Lemma: given any bijection $f : X \to Y$, there exists a bijection $g : 2^X \to 2^Y$ where $g(A) = \{f(x)\ |\ x \in A\}$

If you are able to use this result, then the proof is much more direct. We simply need to establish a bijection from $\mathbb N$ to $\mathbb Z^+$ in order to conclude that their power sets also biject each other. And once you have shown that the power sets biject each other, then this immediately proves the result since $2^{\aleph _0}$ is the cardinality of the power set of the natural numbers (by definition).

Again, I will leave the remainder of this proof to you.

---

Explicitly, the above proof may only seem to show that the cardinality of $\mathcal P (\mathbb Z^+)$ is $2^{\aleph _0}$. However, this also shows that $P( \mathbb Z^+)$ is uncountable since we have established a bijection with $\mathcal P (\mathbb{N})$ which is an uncountable set. And any set that bijects an uncountable set is itself uncountable (as required).