# The set S of all alignments of digits obtainable by sequence of positive integers is countable?

Is $\left\{ n_k \right\}_{k=1}^{\infty}$ a strictly increasing sequence of positive integers (written in decimal notation). Consider the alignment (infinite) set of digits {${n_1 n_2 n_3}$} format approaching from left to right the terms of the sequence $\left\{ n_k \right\}_{k=1}^{\infty}$ (for example, if $n_k = k^2$ for each k, consider the alignment 149162536 ...). Consider the set S of all alignments of digits obtainable in this way, that is to vary of all sequences $\left\{ n_k \right\}_{k=1}^{\infty}$ strictly increasing positive integers: S is countable?

• I am not sure what the "alignment" is. Is it a concatenation of the decimal strings? – Asaf Karagila Jan 22 '13 at 21:13

If I've understood your question correctly then the answer is no. This can be proved using a diagonal argument.

Suppose you have an enumeration $x_1, x_2, x_3, \dots$ of your set, and when they're listed as a string of digits, the elements of the set are given by $$x_1 = d_{11} d_{12} d_{13} \cdots$$ $$x_2 = d_{21} d_{22} d_{23} \cdots$$ $$x_3 = d_{31} d_{32} d_{33} \cdots$$ $$\vdots$$

Define $x^*$ to be the string of digits whose $i$th digit is $1$ if $d_{ii} \ne 1$ and is $2$ if the $d_{ii}=1$.

Then $x^*$ lies in your set: you can parse the digits as a strictly increasing sequence of integers by taking $n_1$ to be the first digit, $n_2$ to be the next two digits, $n_3$ to be the next three digits, and so on.

But $x^*$ cannot possibly lie in your enumeration: if it did, say $x^*=x_i$, then the $i$th digit must be equal to $d_i$, which is impossible by construction.

• All right, before you posted another proof based on f:S-->(0,1) surjective, but it was wrong maybe because for example 1/2=0.5000... can't be created with infinity alligment strictly increasing?? – Stanisław Jan 22 '13 at 21:39
• @Giacomo: Sort of. This problem could easily be circumvented: any decimal representation of a positive real number with a trailing set of $0$s can be replaced by a representation with a trailing set of $9$s $-$ for example, $\frac{1}{2} = 0.5000\dots = 0.4999\dots$, and so my previous argument could still be used. I edited it because I thought an elementary approach (i.e. diagonalisation) is maybe a nicer way to do the problem than appealing to a surjection argument. – Clive Newstead Jan 22 '13 at 21:42
• Ok beautifull :-) However I could see that the set S has cardinality equal to the number of functions of N in N? Because every sequence is a function of N and in this case the sequence creates only positive integer number. (And after I show that $|N^N|$=$|R|$ ) – Stanisław Jan 23 '13 at 2:43
• @Giacomo: Careful $-$ this would be true if you separated the numbers, i.e. turned them into sequences rather than concatenated strings. But as it is, you could pick, say, $1$ then $2$ then $3$ and then a load of stuff, or $1$ then $23$ and then the same load of stuff, and you'd get the same thing (so it's not bijective). – Clive Newstead Jan 23 '13 at 8:33