Arrange N into a two-dimensional array

1. Aug 20, 2016

jack476

1. The problem statement, all variables and given/known data
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.
2. Relevant equations
none

3. 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.

2. Aug 21, 2016

andrewkirk

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.

3. Aug 21, 2016

jack476

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$?

4. Aug 21, 2016

andrewkirk

I suggest you start by defining a bijective function from $\mathbb N$ to points in the number lattice you have drawn, where a point in the lattice is represented by a pair of integer coordinates that are the row and column number.

Also, you can't define $n_{1j}$ to be the minimum of $A_j$ because to have a minimum, a set must be ordered, and the problem does not say the sets are ordered. Why not instead use the fact that we are told that each set $A_j$ is countable, which means that there exists at least one bijection $f_j$ between $\mathbb N$ and $A_j$.