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?

  • 1
    $\begingroup$ I am not sure what the "alignment" is. Is it a concatenation of the decimal strings? $\endgroup$ – 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.

  • $\begingroup$ 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?? $\endgroup$ – Stanisław Jan 22 '13 at 21:39
  • 2
    $\begingroup$ @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. $\endgroup$ – Clive Newstead Jan 22 '13 at 21:42
  • $\begingroup$ 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|$ ) $\endgroup$ – Stanisław Jan 23 '13 at 2:43
  • 1
    $\begingroup$ @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). $\endgroup$ – Clive Newstead Jan 23 '13 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.