# What is the cardinal number of all strictly increasing sequences?

What is the cardinal number of all strictly increasing sequences? I was able to find an injection from $(0,1)$ into the set of all strictly increasing sequnces by defining $i(a)=(a,1,2,3,4,\dots)$, where $a\in (0,1)$(Am I correct?). But I think that its cardinality is bigger than continuum. How do I prove that?

-
Sequences of integers or reals, or something else? – anon Feb 11 '12 at 0:17
@anon: sequences of real numbers. – spohreis Feb 11 '12 at 0:21

Fix a strictly increasing sequence whose limit is $1$, for example: $$a_n=\frac{n}{n+1}$$

Now for every $c\in (0,1)$ the sequence $c_n=c\cdot a_n$ is strictly increasing and converges to $c$. Thus we easily obtain that there are at least $2^{\aleph_0}$ many strictly increasing sequences.

On the other hand every sequence is a function from $\mathbb N$ into $\mathbb R$. Since $\left|\mathbb R\right|=\left|\{0,1\}^\mathbb N\right|$ we have that $\left|\mathbb R^\mathbb N\right|=\left|\left(\{0,1\}^\mathbb N\right)^\mathbb N\right|$.

From How to show $(a^b)^c=a^{bc}$ for arbitrary cardinal numbers? we deduce that this set, therefore, has the same cardinality as $\{0,1\}^{\mathbb N\times\mathbb N}$. Using Cantor's pairing function (or a different method) we have that $|\mathbb N|=|\mathbb N\times\mathbb N|$, thus obtaining: $$\left|\mathbb R^\mathbb N\right|=\left|\{0,1\}^{\mathbb N\times\mathbb N}\right|=\left|\{0,1\}^\mathbb N\right|=|\mathbb R|$$

So we have that the set of all strictly increasing sequences is a subset of $\mathbb R^\mathbb N$, so it cannot be more than $2^{\aleph_0}$ but on the other hand we have at least $2^{\aleph_0}$ many sequences in this set.

By Cantor-Bernstein we therefore have that this set has $2^{\aleph_0}$ many elements.

-
Thank you very much for this answer and for the other information. Terrific! – spohreis Feb 16 '12 at 0:28

I assume you mean the set of all strictly increasing sequences of real numbers. As you observe, this is at least as large as the continuum. It's clearly at most as large as the set of all sequences of reals, which has cardinality $\left |\mathbb{R}\right |^{\left |\mathbb{N}\right |}=\left(2^{\aleph_0}\right)^{\aleph_0}$=$2^{(\aleph_0 \cdot \aleph_0)}=2^{\aleph_0}$. So by Cantor-Bernstein, the set of strictly increasing sequences of reals has the cardinality of the continuum.

-
Sorry, but I can't see how it is clear from your answer that the set of all strictly increasing sequences of real numbers has the cardinality of continuum. – spohreis Feb 14 '12 at 0:34

Consider the bijection between strictly increasing and (almost) strictly positive sequences of reals:

$$(a_1,a_2,a_3,a_4,\cdots)\stackrel{\sim}{\mapsto}(a_1,\,a_2-a_1,\,a_3-a_2,\,a_4-a_3,\cdots).$$

This explicitly demonstrates the cardinality is equal to $|\mathbb{R}\times\mathbb{R}_{>0}\times\mathbb{R}_{\ge0}\times\cdots|=\mathfrak{c}^{\aleph_0}=\mathfrak{c}$.

-

Let $N$ denote the set of positive integers and let $F: N \rightarrow N \times N$ be a bijection.

If $\{ a_n \}$ is any sequence of numbers in $( 0,1 )$ then define define a new number $x \in [0,1]$ the following way:

the nth digit of $x$ is the $m$th digit of $x_k$, where $F(n)=(m,k)$.

Prove that this is an injective function from the set of all sequences in $(0,1)$ to the interval $[0,1]$.

-