10
$\begingroup$

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?

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

2 Answers 2

14
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .