- #1
jack476
- 328
- 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 xij be the ith element of the jth row of the array. Let n1j be the minimum of Aj, let n2j be the next smallest element of Aj, and so on. Then define the function given by nij ↔ xij, which assigns the ith smallest element of Aj to the ith element of the jth row. It is clear that this function is bijective. Since {nij} = ∪∞n=1An and {xij} = N, we therefore have a bijection between ∪∞n=1An and N, and therefore the infinite union is countable.