# Is this set of natural sequences countable?

Let $$X$$ be the set of all natural sequences such that the next term is at least twice as large as the previous one, that is

$$X = \{x_n: x_n \in \mathbb{N} \text{ and } x_{n+1} \geq 2x_n \text{ }\forall n\}$$

Is this set countable? I think it isn't, and I would like some feedback on my proof below.

Tentative proof:

We will construct a surjective function $$f: X \rightarrow \{0, 1\}^{\mathbb{N}}$$, where $$\{0, 1\}^{\mathbb{N}}$$ is the set of all binary sequences. For every sequence $$x_n \in X$$, we map it into the sequence $$f(x_n) = s_n = \mathbb{1}\{x_{n+1} > 2x_n\}$$. That is,

$$s_n = \begin{cases} 1, & x_{n+1} > 2x_n \\ 0, & x_{n+1} = 2x_n \end{cases}$$

We now show that $$f$$ is a surjection: take any $$s_n \in \{0, 1\}^{\mathbb{N}}$$, and consider the sequence defined as $$x_1 = 1$$ and

$$x_{n+1} = \begin{cases} 2x_n +1 , & s_n = 1 \\ 2x_n, & s_n = 0 \end{cases}$$

By construction, $$x_n \in X$$ and $$f(x_n) = s_n$$. So for any $$s_n \in \{0, 1\}^{\mathbb{N}}$$ there exists a $$x_n \in X$$ such that $$f(x_n) = s_n$$. Therefore, $$f$$ is a surjection.

We know that $$|\{0, 1\}^{\mathbb{N}}| > |\mathbb{N}|$$ (the set of all binary sequences is not countable); since we constructed a surjection from $$\{0, 1\}^{\mathbb{N}}$$ to $$X$$, we have that

$$|X| \geq |\{0, 1\}^{\mathbb{N}}| > |\mathbb{N}|$$

Therefore, $$X$$ is not countable.

Is this proof correct?

• Do you mean $s_n = 1 \{x_{n+1} > 2 x_n\}$? Aug 19, 2023 at 15:42
• Yes, thank you! Aug 21, 2023 at 16:35

Your proof is fine. Another one could be to notice that the map $$X\to\Bbb N^{\Bbb N},\quad x\mapsto y:\begin{cases}y_1&=x_1\\y_{n+1}&=x_{n+1}-2x_n+1,\;\forall n\in\Bbb N\end{cases}$$ is bijective.
Personally I'd start with the sequence $$(x_n)$$ and define $$y_n = 2^{x_1 + \ldots + x_n + n}$$. Exercise to show $$(x_n) \mapsto (y_n)$$is a bijective map. Hint, you can write down the inversion map explicitly. Then we have
$$y_{n+1} = 2^{x_1 + \ldots + x_n +x_{n+1} + n+1}= 2^{x_1 + \ldots + x_n +n} \cdot 2^{x_{n+1} +1} = y_n \cdot 2^{x_{n+1} +1} \ge 2 y_n.$$