Cardinality for all rational strongly increasing sequences

Question

What is the cardinality for all rational strongly increasing sequences?

Using diagonalization, I can show easily that for each list $f_n$ of sequnces, we can present a sequence which is not in the list.

Indeed, we can define $$a_k = f_{(k)}(k) + 1$$
The sequence is answering our demand to be strongly increasing yet isn't equal to any existing sequence in our list.

From this we can infer the cardinality is $\ge \aleph_0$.
I know the answer is $\aleph$ but how to show it?

By the way,
If you can show another neat way I'd be glad, but I do want to complete the diagonaliztion proof.

Thanks.

Answer 1

The answer is $|\mathbb R|=2^{\aleph_0}$, because for any real number you can find strictly increasing sequence of rationals converging to it.

It's not more, because it's at most than $|\mathbb Q|^{|\mathbb N|}=\aleph_0^{\aleph_0}=2^{\aleph_0}$.

Answer 2

You can make a bijection between strongly increasing sequences and positive sequences, by taking the difference between consecutive terms (ok, one should consider the first term apart in some way). Positive rational sequences are as many as $$ \mathbb N \to \mathbb N $$ which are as many as $2^{\mathbb N}$ (corrected, I was wrong).

Answer 3

A diagonalization argument can be used to show that the set of all strictly increasing sequences is uncountable, but this method is inherently limited. If we let $\mathfrak{S}$ denote the set of such sequences, diagonalization can show that $$\vert\mathfrak{S}\vert>\aleph_{0},$$ i.e., that the set is uncountable. But without appealing to the continuum hypothesis, this does not allow us to conclude that $$\vert \mathfrak{S}\vert=2^{\aleph_{0}}.$$ To reash this conclusion, more work is needed. (Or a different approach, such as that of @user2345215).

Anyway, if you really want to use diagonalization here, you need to do more work to ensure that the new sequence you generate is indeed strictly increasing. Here's one approach:

We start with our presumed exhaustive enumeration of all strictly increasing sequences. Let $\langle a_{n_k}\vert k<\omega\rangle$ be the $n$-th such sequence. Then define a new sequence $\langle b_{j}\vert j<\omega\rangle$ by: $$b_{j}=j+\sum_{k=0}^{j}\vert a_{j_{k}}\vert$$ (where the vertical lines in this last formula denote absolute value, and not cardinality).

Answer 4

There are many answers, but some people prefer $2^\mathbb{N}$ rather than $\mathbb{N}^\mathbb{N}$ and it is easy in this case (not that it really matters, but perhaps it gives them more intuition, whatever). Let $\mathcal{Q}$ be the set of strongly increasing sequences of rational numbers, then $$2^{\mathbb{N}}\ \stackrel{\spadesuit}\leq\ \mathcal{Q}\ \stackrel{\clubsuit} \leq\ 2^{\mathbb{N}}.$$

Injection $f : 2^{\mathbb{N}} \to \mathcal{Q}$ can be given, for example, as

$$f(\mathbf{a}) = n \mapsto 2n + \sum_{k=0}^{n} \mathbf{a}_k \tag{$\spadesuit_1$}$$ or $$f(\mathbf{a}) = n \mapsto \sum_{k=0}^{n} 3^k(1+\mathbf{a}_k).\tag{$\spadesuit_2$}$$

The other direction $g : \mathcal{Q} \to 2^\mathbb{N}$ can be defined by writing rational numbers in unary notation using $1$ as a symbol and $0$ as delimiter, or more formally

\begin{align*} \mathrm{unary}(p,q) &= (0,\underbrace{1,1}_{\text{two ones if $p \geq 0$}},0,\underbrace{1,1,\ldots,1}_{|p|+1 \text{ ones}},0,\underbrace{1,1,\ldots,1}_{q+1 \text{ ones}}) \\ g(\mathbf{b}) &= \mathrm{unary}(\mathbf{b}_0) \star \mathrm{unary}(\mathbf{b}_1) \star \ldots \tag{$\clubsuit$} \end{align*}

where $\star$ denotes sequence concatenation.

I hope this helps $\ddot\smile$