# Arrange N into a two-dimensional array

## Homework Statement

The problem is to show that arranging N into the two dimensional array:
$$\begin{matrix} 1 & 3 & 6 & 10 & ... \\ 2& 5& 9& ... \\ 4& 8& & \\ 7&... & & \\ ... \end{matrix}$$

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

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.

andrewkirk
Homework Helper
Gold Member
Your approach is a little confusing. You use the symbol ##A_j## but do not say what it is. You then set out to define a function but the bidirectional arrow ##\leftrightarrow## leaves us wondering which way the function goes, and it does not tell us what the domain and range are. We can say nothing about whether a function is bijective unless we know its domain and range.

The classical, and clearest, way to define a function ##f## is to write something like:

'define the function ##f:D\to R## such that ##f(x)=##<formula specifying the result of applying the function to ##x##>'​

This tells us that ##f, D## and ##R## are the function's name, domain and range respectively, and the 'such that' part then tells us what value is obtained by applying it to an arbitrary element of the domain.

I am sorry, I should have been clearer.

The sets ##A_j## refer to the countably infinite sets in the infinite union in the problem statement, that is, to prove that the union n=1An is countably infinite. All that is given about these sets is that they are countably infinite. I misunderstood the meaning of the bidirectional arrow.

My approach is to show that there is a bijection between the infinite union and N. To do this, I use the fact that each row in the array represents a countably infinite subset of N, and that the set of all elements in the array is N. Then I would show that the function that assigns ##n_{ij}##, the ##i^{th}## smallest element in set ##A_j##, to ##x_{ij}##, the ##i^{th}## element of ##R_j##, the ##j^{th}## row in the array, is a bijection. [

So does that mean that I would say that I am defining a function ##f: A_j \rightarrow R_j##?

andrewkirk