0

I want to show that $F_n = \{\{a_1,a_2,...a_n\}: a_i \in \mathbb{N} \mbox{ for } i \in \{1,2,...n\} \}$ is countably infinite by showing that $|F_n| = |\mathbb{N}|$.

So for example $F_1 = \{\{1\}, \{2\},...\}$ and $F_2 = \{\{1\},\{1,2\},\{2,2\},\{1,3\},...\}$

It is easy to show that $F_1$ is countably infinite as there is a bijection $f:\mathbb{N} \rightarrow F_1$ be $f(n) = \{n\}$.

However when it comes to $F_2$ I can't seem to come up with a proof. And this holds for $F_n$ as well.

Just from my hunch, I think this has something to do with the cartesian product of countable sets being countable.

Andrés E. Caicedo
  • 79,201
K.Hu.1106
  • 71

1 Answers1

0

Simple way using unique factorization:

$\{a_i\}|_{i=1}^n \to \prod_{i=1}^n p_i^{a_i} $ where $p_i$ is the i-th prime.

marty cohen
  • 107,799
  • Note that this gives an injection $\mathbb N^n\to\mathbb N$. In order to get a bijection one would need to combine it with an injection in the other direction (which is, of course, easy) using the Bernstein theorem. – hmakholm left over Monica Mar 29 '19 at 13:14