I am studying a course on ZF Set Theory (without the Axiom of Choice) and am currently looking at the cardinalities of infinite sets. One question that I came across is the following:
Determine the cardinality of non-singleton subsets of $\mathbb{N}$.
If we let $ \mathbb{N}^{(1)}$ denote the set of singleton subsets of the natural numbers, then the set of interest is $ \mathcal{P}( \mathbb{N} ) \setminus \mathbb{N} ^{(1)}$
We know the following:
$$| \mathcal{P}( \mathbb{N} ) | = 2^{\aleph _0}$$
$$ \text{and } | \mathbb{N^{(1)}} | \leq | \mathbb{N} | = \aleph _0 $$
Based on this, it is my suspicion that:
$$ | \mathcal{P}( \mathbb{N} ) \setminus \mathbb{N} ^{(1)}| = | \mathcal{P}( \mathbb{N} ) |= 2^{\aleph _0}$$
But I am unsure how to formalise this and would be grateful for any help in doing so.
Best Answer
One way to do it is as follows: Pick a countably infinite set, $A\subset \mathcal{P}(\mathbb{N})$ that is disjoint from $\mathbb{N}^{(1)}$. One can partition $A$ into two disjoint sets $K,M$ both of cardinality $\aleph_{0}$, now construct a bijection from $\mathcal{P}(\mathbb{N })\to \mathcal{P}(\mathbb{N })\setminus \mathbb{N}^{(1)}$ as follows: Map everything in $(\mathcal{P}(\mathbb{N })\setminus \mathbb{N}^{(1)})\setminus A$ to itself, bijectively map $A$ to $K$ and $\mathbb{N}^{(1)}$ to $M$ (using the fact that they all have the same cardinality).
(Note how generalisable this proof is)