- #1

- 319

- 125

## Homework Statement

The problem is to show that arranging

**N**into the two dimensional array:

[tex]

\begin{matrix}

1 & 3 & 6 & 10 & ... \\

2& 5& 9& ... \\

4& 8& & \\

7&... & & \\

...

\end{matrix}

[/tex]

leads to a proof that the union of an infinite number of countably infinite sets is countable.

## Homework Equations

none

## The Attempt at a Solution

Let

*x*be the

_{ij}*i*element of the

^{th}*j*row of the array. Let

^{th}*n*be the minimum of

_{1j}*A*, let

_{j}*n*be the next smallest element of

_{2j}*A*and so on. Then define the function given by

_{j},*n*which assigns the

_{ij}↔ x_{ij},*i*smallest element of

^{th}*A*to the

_{j}*i*element of the

^{th}*j*row. It is clear that this function is bijective. Since

_{th}*{n*and

_{ij}} = ∪^{∞}_{n=1}A_{n}*{x*

_{ij}} =**we therefore have a bijection between**

*N*,*∪*and

^{∞}_{n=1}A_{n}**, and therefore the infinite union is countable.**

*N*