# Are these subsets of the powerset P(N) countable?

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.

• Your mistake is so common: you didn't pay attention to infinite subsets of $\Bbb{N}$! – Crostul Nov 4 '15 at 15:49
• 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). – Bakuriu Nov 5 '15 at 8:14
• 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. – Jeppe Stig Nielsen Nov 5 '15 at 8:40

## 3 Answers

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

• For an even simpler example, it doesn't include $\mathbb N$! – wchargin Nov 4 '15 at 18:37
• @WChargin Right, I missed that one. :( – CiaPan Nov 4 '15 at 18:49
• I honestly can't believe that didn't cross my mind >.< Thanks. – 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$.)

• 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. – Akiva Weinberger Nov 4 '15 at 20:55