# How many uncountable subsets of power set of integers are there?

The question is to determine how many uncountable subsets of ${P(\mathbb Z)}$ are there.

I think that the answer is $2^c$.

Let $A=\{B\in P(P(\mathbb Z)):B \text{ is uncountable}\}$

$P(P(\mathbb Z))$ has $2^c$ elements, so cardinality of $A$ is at most $2^c$.

Of course, I'm having trouble with the lower bound and I'm trying to find an injective function from some set of cardinality $2^c$ into $A$.

If anybody has any idea, I'd be very grateful!

• Handwaving: For any $C \subset P(\mathbb Z )$ and $D= P(\mathbb Z ) \ C$, either $C$ is uncountable or $D$ is uncountable or both are, as their union is uncountable. So at least "half" of the subsets of $P(\mathbb Z )$ are uncountable, and "half" of $2^c$ is also $2^c$ Commented Nov 22, 2017 at 22:08

Try to first argue this about $\Bbb R$. How many uncountable subsets does $\Bbb R$ have?

Then note that because $\Bbb R$ and $\mathcal P(\Bbb Z)$ have the same cardinality, any bijection witnessing this would map uncountable subsets of $\Bbb R$ to uncountable subsets of $\mathcal P(\Bbb Z)$. So the answer would be the same.

Write $P(\Bbb Z)$ as a disjoint union of sets $A$ and $B$ each of cardinality $c$. There are $2^c$ sets $A\cup X$ with $X\subseteq B$, each of which is uncountable.

Yes, the answer is $2^c$. Here's a "proof:" the number of uncountable subsets of $P(\mathbb{Z})$ is $P(P(\mathbb{Z}))$ minus the number of countable subsets of $P(\mathbb{Z})$. The number of those is $(2^{\aleph_0})^{\aleph_0}=2^{\aleph_0}$, which is $<2^c=\vert P(P(\mathbb{Z}))\vert$.

There are a couple steps there that need to be filled in (counting the number of countable subsets, and showing that "big $-$ small $=$ big"), but these are standard results, and if you haven't seen them before they're good exercises.

• I don't understand why $(2^{\aleph_0})^{\aleph_0}=2^{\aleph_0}$. Is this a known result? Commented Nov 22, 2017 at 17:39
• @EricDuminil Yes, it's quite well-known - it's a special case of the cardinal arithmetic equality $(\alpha^\beta)^\gamma=\alpha^{\beta\cdot\gamma}$ together with $\eta\cdot\theta=\max\{\eta,\theta\}$. So this is one of the usual exponent rules that continues to hold for cardinal exponentiation. If you haven't seen it before, it's a good exercise (and closely related to Currying). Commented Nov 22, 2017 at 17:47

Start with your definition (after renaming the bound variable) and add a second definition: $$A=\{X\in P(P(\mathbb Z)):X \text{ is uncountable}\} \\ B=\{X\in P(P(\mathbb Z)):X \text{ is countable}\}$$

Consider $f(X) = \overline{X}$ (the complement of $X$ relative to $P(\mathbb Z)$) as a function $f: B \rightarrow A$. This is a function because every countable subset of $P(\mathbb Z)$ must have an uncountable complement. Given $X \cup \overline{X} = P(\mathbb Z)$, since the RHS is uncountable, the LHS must also be uncountable, so if $X$ is countable (and in $B$), $\overline{X}$ is uncountable (and in $A$).

The complement is injective by elementary set theory. Since an injection from $B$ to $A$ exists, $|B| \leq |A|$. But then we have: $$A \cup B = P(P(\mathbb Z)) \\ A \cap B = \emptyset \\ |A| + |B| = |P(P(\mathbb Z))| \\ |A| + |A| \geq |P(P(\mathbb Z))| \\ 2|A| \geq |P(P(\mathbb Z))| \\ |A| \geq |P(P(\mathbb Z))|$$

We already know that: $$A \subset P(P(\mathbb Z)) \\ |A| \leq |P(P(\mathbb Z))|$$

So the equality follows by Schröder–Bernstein.

Here's a simple injective argument with no prerequisites (except the Schroder-Bernstein theorem at the end, since this only shows that the cardinality is at least $2^\frak{c}$, and it's clearly at most $2^\frak{c}$):

Let $N=\{X\subseteq\Bbb N\mid 0\in X\}$. $N$ is uncountable, because every subset of ${\cal P}(\Bbb N^+)$ can be injected into $N$ by adding $0$. Every $A\subseteq {\cal P}(\Bbb Z)$ such that $N\subseteq A$ is thus also uncountable, so it suffices to prove there are at least $2^\frak{c}$ subsets $N\subseteq A\subseteq {\cal P}(\Bbb Z)$.

Let $\Bbb Z^-=\Bbb Z-\Bbb N$. For each subset $B\subseteq{\cal P}(\Bbb Z^-)$ (of which there are $2^\frak{c}$ many), let $B^*=\{N\cup X\mid X\in B\}$. Since $X$ and $N$ are disjoint (each element of $N$ has $0$ and each element of $X$ does not), the function $X\in B\mapsto N\cup X$ is injective, so $\{B^*\mid B\subseteq{\cal P}(\Bbb Z^-)\}$ also has cardinality $2^\frak{c}$. But now we are done, because every $B^*$ is a distinct uncountable subset of ${\cal P}(\Bbb Z)$.

Rather than inject something into A, another approach is to inject the set of countable subsets into A. This proves that the cardinality of A is at least as large as the cardinality of the set of countable subsets.

You will then have to argue that given infinite sets A and A', if $|A| \ge |A'|$ then $|A| = |A \cup A'|$ , but that follows pretty easily from transfinite math.

• @Noah Schweber You seem to have ignored my second paragraph. Commented Nov 23, 2017 at 21:29
• Ah, d'oy, that was not my finest moment. (I can't un-downvote unless you edit, unfortunately.) Commented Nov 23, 2017 at 21:37