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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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