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?
Best Answer
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.