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


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

  • 3
    $\begingroup$ 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. $\endgroup$ – Brian M. Scott Mar 27 '15 at 9:01
  • $\begingroup$ 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? $\endgroup$ – user29123 Mar 27 '15 at 9:04
  • 1
    $\begingroup$ 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! $\endgroup$ – é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.

(And a tip for the future: whenever you write "the obvious surjection" or "the obvious bijection", you should at least write it in full details for yourself to make sure it's really obvious. Because obviously, it's not that obvious.)

| cite | improve this answer | |
  • 1
    $\begingroup$ +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. $\endgroup$ – user29123 Mar 27 '15 at 9:11
  • $\begingroup$ Aha! So it was impossible to construct that 'obvious' bijection. Thank you sir! $\endgroup$ – étale-cohomology Mar 27 '15 at 9:24
  • $\begingroup$ Also, note taken of your advice. Again, thank you! $\endgroup$ – étale-cohomology Mar 27 '15 at 9:45

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.