I am only a first semester undergraduate (of mathematics) so I would appreciate the answers to not be too complicated. Also English is not my first language, so my explanations might be a little off.

While trying to prove that the Powerset $\mathcal{P}(\mathbb{N})$ is uncountable I ran into something that I wasn't able to understand.

So, I define the set $$ \mathbb{N}_n=\{\{a_1,a_2,\ldots,a_n\}:a_i\in \mathbb{N} \; \forall i \text{ and } a_i \neq a_j \; \forall i \neq j\} \text{ for } n \in \mathbb{N} $$ basically the set goes like this $$ \mathbb{N}_0=\{ \emptyset \} \\ \mathbb{N}_1=\{ \{1\},\{2\},\{3\},\ldots \} \\ \mathbb{N}_2=\{ \{1,2\},\{1,3\},\{2,3\},\{1,4\},\ldots \} \\ \vdots $$ and we can conclude that $$ \text{if } \mathbb{N}_i \cap \mathbb{N}_j = \emptyset \text{ then } i \neq j \\ \bigcup\limits_{i \in \mathbb{N} \cup \{0\}} \mathbb{N}_i = \mathcal{P}(\mathbb{N}) $$ Okay, so there are a countable number of sets $\mathbb{N}_i$. Also the set $\mathcal{P}(\mathbb{N})$ is uncountable. Also as briefly mentioned in yesterdays lecture (at my university), a countably infinite union of countable sets is a countable set. From this I have concluded that:

$ \text{There exists an } i \in \mathbb{N} \text{ such that the set } \mathbb{N}_i \text{ is uncountable.} $

Now, there is the possibility of a mistake that I have made in a previous statement. But in the case that I haven't, this last statement seems very counter intuitive to me. I have also tried proving / disproving it but failed.

My question is where have I either made a mistake, or if I haven't how do I prove or disprove my final statement.

  • 14
    $\begingroup$ Your mistake is so common: you didn't pay attention to infinite subsets of $\Bbb{N}$! $\endgroup$ – Crostul Nov 4 '15 at 15:49
  • 2
    $\begingroup$ You just defined $\mathcal{P}_f(\mathbb{N})$ i.e. the finite powerset, which is different from the powerset (whenever you apply it to an infinite set). $\endgroup$ – Bakuriu Nov 5 '15 at 8:14
  • $\begingroup$ From a real number with an infinite decimal expansion, say $3.1415926\ldots$, let us make a subset of the natural numbers in this way: $\{ 3,11,114,1111,11115,111119,1111112,11111116,\ldots\}$ Where is this subset in your $\bigcup_i \mathbb{N}_i$? It is quite clear that I can recover any real number from its subset of naturals constructed in this way, so this shows that there cannot be more reals than subsets of naturals. $\endgroup$ – Jeppe Stig Nielsen Nov 5 '15 at 8:40

Your set is a set of all finite subsets of $\mathbb N$. Notice that none of your sets contains a set of all even numbers: $$\forall (i\in\mathbb N)\ \{ 2k \mid k\in \mathbb N\} \notin \mathbb N_i$$ or any other infinite subset of $\mathbb N$.

  • 9
    $\begingroup$ For an even simpler example, it doesn't include $\mathbb N$! $\endgroup$ – wchargin Nov 4 '15 at 18:37
  • $\begingroup$ @WChargin Right, I missed that one. :( $\endgroup$ – CiaPan Nov 4 '15 at 18:49
  • $\begingroup$ I honestly can't believe that didn't cross my mind >.< Thanks. $\endgroup$ – Atheridis Nov 4 '15 at 20:55

It is false that

$$\mathcal P(\mathbb N)=\bigcup_{i\in\mathbb N}\mathbb N_i$$

In fact, $\bigcup_{i\in\mathbb N}\mathbb N_i$ is precisely the set of all finite subsets of $\mathbb N$. But $\mathcal P(\mathbb N)$ also includes the infinite subsets, of which there are uncountably many.


There are countably many finite subsets of $\Bbb N$. However, $\cal P(\Bbb N)$ also contains infinite subsets of $\Bbb N$, such as $\{2,4,6,\dots\}$, and there are uncountably many infinite subsets of $\Bbb N$.

$\bigcup_i\Bbb N_i$ is the set of finite subsets of $\Bbb N$. To prove that it's countable, I'll provide an explicit bijection between it and $\Bbb N$: EDIT: This is just an injection, not an actual bijection, sorry. $$\{a_1,a_2,a_3,\dots,a_n\}\mapsto2^{a_1}3^{a_2}5^{a_3}\dotsb p_n^{a_n}$$ (Here, I'm assuming that $\Bbb N$ doesn't contain $0$ out of convenience. Also, note that the empty set maps to $1$.)

  • $\begingroup$ Perhaps a better injection simply maps them to $p_{a_1}p_{a_2}\dots p_{a_n}$, where $p_i$ is the $i$th prime. This maps the finite subsets to the square-free numbers. $\endgroup$ – Akiva Weinberger Nov 4 '15 at 20:55

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.