Arrange N into a two-dimensional array

[jack476]

Homework Statement

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

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_ij be the i^th element of the j^th row of the array. Let n_1j be the minimum of A_j, let n_2j be the next smallest element of A_j, and so on. Then define the function given by n_ij ↔ x_ij, which assigns the i^th smallest element of A_j to the i^th element of the j_th row. It is clear that this function is bijective. Since {n_ij} = ∪^∞_n=1A_n and {x_ij} = N, we therefore have a bijection between ∪^∞_n=1A_n and N, and therefore the infinite union is countable.

 

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

 

[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=1A_n 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]

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