# What is wrong with this proof that $\text{card}(\mathcal{P}(\mathbb{N}))=\aleph_1$?

I'm reading books on set theory and I came up with the following 'proof' that $\text{card}(\mathcal{P}(\mathbb{N}))=\aleph_1$. What is wrong with it? I really cannot tell!

By $\text{card}(\mathcal{P}(\mathbb{N}))$ I mean the cardinality of the power set of the set of nonnegative integers (I also see $\mathbb{N}$ as the set of finite von Neumann ordinals), which is $2^{\aleph_0}$, and by $\aleph_1$ I mean the cardinality of $\omega_1$, which is the least uncountable ordinal and also the least upper bound of the set of all ordinals of cardinality at most $\aleph_0$. Now, $2^{\aleph_0}=\aleph_1$ is the continuum hypothesis, which is independent of ZFC.)

Proof.

Each $\alpha\in\omega_1$ has cardinality at most $\aleph_0$ and each such $\alpha$ is wellordered by $\in$.

Each $a\in\mathcal{P}(\mathbb{N})$ has cardinality at most $\aleph_0$, and each such $a$ is wellordered by $\in$. This is because every $a\in\mathcal{P}(\mathbb{N})$ is a (possibly infinite) set of (finite) ordinals, and every nonempty set of ordinals is wellordered by $\in$.

We can establish an obvious bijection from $\mathcal{P}(\mathbb{N})$ to some set of ordinals $N$, namely $a\mapsto\text{ord}(a)$, i.e. between $a\in\mathcal{P}(\mathbb{N})$ and the order-type of wellordered set $a$. Each ordinal $\text{ord}(a)\in N$ also has cardinality at most $\aleph_0$, and since we know that $\omega_1$ is the least upper bound of all ordinals of cardinality at most $\aleph_0$ (where $\text{card}(\omega_1)=\aleph_1$), then $\text{card}(N)\leq\aleph_1$.

But $\text{card}(\mathcal{P}(\mathbb{N})) = \text{card}(N)$ (due to the existence of a bijection from $\mathcal{P}(\mathbb{N})$ to $N$), so by a diagonal argument $\text{card}(N)>\aleph_0$. It follows that $\text{card}(N)=\aleph_1$, and $\text{card}(\mathcal{P}(\mathbb{N}))=\aleph_1$.

• You’re actually mapping $\wp(\Bbb N)$ onto $\omega+1$: the only possible order types of subsets of $\Bbb N$ are $\omega$ and the finite types. Every finite ordinal is the image of $\aleph_0$ subsets, and $\omega$ is the image of $2^{\aleph_0}$ subsets, so your map is far from being a bijection. – Brian M. Scott Mar 27 '15 at 9:01
• How does the existence of a surjection imply $\mathrm{card}(\mathcal{P}\mathbb{N}) \leq \mathrm{card}(N)$? There is a surjection from reals to naturals. After your edit, how is there a bijections? – Paul Plummer Mar 27 '15 at 9:04
• I thought there was a bijection between $\mathcal{P}(\mathbb{N})$ and some set $N$ of countable ordinals because each $a\in\mathcal{P}(\mathbb{N})$ is countable and wellordered, so it has some countable ordinal. But now I see there are many elements of $\mathcal{P}(\mathbb{N})$ that map to the same ordinal, so this is clearly not the case! – étale-cohomology Mar 27 '15 at 9:16

Note that every set in $\mathcal P(\Bbb N)$ is a subset of $\Bbb N$, so its order type is $\leq\omega$. So this is certainly not a surjection onto $\omega_1$.
You can define a surjection onto $\omega_1$ by considering each set of natural numbers encoding a set of pairs of natural numbers. But then you will also face things which are not well-orders (e.g. things isomorphic to $\Bbb Z$ or $\Bbb Q$ and things which are not partial orders to begin with). And not to mention that there are $2^{\aleph_0}$ subsets of $\Bbb{N\times N}$ which are well-orders of order type $\alpha$ for any $\alpha\geq\omega$.
So that definable surjection onto $\omega_1$ is very much not a bijection either.
• +1 For the answer and +$\aleph_1$ (which is obviously in bijection with the continuum) for the parenthetical. Sadly, at the moment, I don't have a 1 or $\aleph_1$ to give, maybe others will make up for my lack of votes. – Paul Plummer Mar 27 '15 at 9:11