# Show that the set $\mathbb{N} \times \mathbb{N}$ can be expressed as the union of a countably infinite family of countable infinite sets.

I know that $\mathbb{N}$ is countably infinite and that countability infinite sets can be split into countably infinite subsets.

$\mathbb{N} \times \mathbb{N}$ = $\{(n,n) |$ $\forall n \in \mathbb{N}\}$

Can I describe this as the union of two pairwise disjoint subsets of the ordered pairs of even numbers and those of odd numbers?

i.e.:

$\{(2,2), (4,4), (6,6), ... (m,m)\}$ $\forall m \in \mathbb{N}_m$ where $\mathbb{N}_m$ is the set of all even natural numbers.

$\{(1,1), (3,3), (5,5), ... (n,n)\}$ $\forall n \in \mathbb{N}_n$ where $\mathbb{N}_n$ is the set of all odd natural numbers.

Surely the union of these two sets is equivalent to $\mathbb{N} \times \mathbb{N}$?

I also have to show that the union of pairwise disjoint countably infinite sets are countably infinite.

• $\mathbb N \times \mathbb N$ is not $\{ (n, n) : n \in \mathbb N \}$. It is $\{ (n, m) : n, m \in \mathbb N\}$. If your question pertains to $\mathbb N \times \mathbb N$, you could write $\mathbb N \times \mathbb N = \bigcup_{n \in \mathbb N} \{ (n, m) : m \in \mathbb N \}$, which is a countably infinite union of countably infinite sets. – Jon Warneke May 22 '16 at 1:18
• You seem to have omitted $(1,4)$ and $(2,3)$. – MJD May 22 '16 at 1:30
• How can I show that such a set like that given in your example is countably infinite? More specifically how do I prove surjectivity? I can probably figure out injectivity. – J00S May 22 '16 at 3:49
• You seem to have asked the wrong question. It is obvious that $\mathbb{N}\times\mathbb{N}$ is the union of a countable infinity of countably infinite sets. But your real question seems to be: why is $\mathbb{N}\times\mathbb{N}$ countable? – almagest May 22 '16 at 5:40

The claim that the union of $\{(1,1),(3,3),...\}$ and $\{(2,2),(4,4),...\}$ is the same as $\mathbb{N}\times\mathbb{N}$ is false because you are ommiting pairs of the form $(e,o)$ and $(o,e)$, where $e$ is an even number and $o$ is an odd number, which clearly belong to $\mathbb{N}\times\mathbb{N}$.