2
$\begingroup$

I intend to show that $X=\{(x_n)_{n\in\mathbb{N}}\in \mathbb{Z}^{\mathbb{N}}:x_{2i-1}<x_{2i+1}\ \text{and} \ x_{2(i+1)}<x_{2i}\ \forall \ i \in \mathbb{N}\}$, the set of all integer sequences that have increasing odd subsequences and decreasing even subsequences, is uncountable.

Proof. Proof by contradiction using Cantor's diagonal argument. We'll show that there's at least one element in $X$ that is not hit by a function $\varphi\colon \mathbb{N}\to X$.

Suppose that $X$ is countable. Then we can enumerate its sequences $(x_n)_{n\in \mathbb{N}}$ as: \begin{align*} 1\mapsto \varphi(1)&=s_1=(s_{11},s_{12},s_{13},\dots)\\ 2\mapsto \varphi(2)&=s_2=(s_{21},s_{22},s_{23},\dots)\\ 3\mapsto \varphi(3)&=s_3=(s_{31},s_{32},s_{33},\dots)\\ &\vdots\\ n\mapsto \varphi(n)&=s_n=(s_{n1},s_{n2},s_{n3},\dots)\\ &\vdots \end{align*}

Define $s_n(m) := s_{nm}$. Example: $s_1(2)=s_{12}$.

We now build the sequence $s$, defined inductively by: \begin{align*} &s(1)=s_1(1)+1\\ &s(2)=s_2(2)-1\\ &s(2n+1)=\max{(s_{2n+1}(2n+1),s(2n-1))}+1\\ &s(2n)=\min{(s_{2n}(2n),s(2(n-1))}-1 \end{align*}

We see that although $s\in X$, it is not hit by any $n\in\mathbb{N}$. Therefore $\varphi$ is not surjective and $X$ is uncountable.

Is this correct? Any correction or proof-writing tip is obviously appreciated.

$\endgroup$
1
  • 1
    $\begingroup$ Your argument is both correct and clear. $\endgroup$ Sep 21, 2020 at 17:45

1 Answer 1

2
$\begingroup$

Your argument is correct, but it would be somewhat simpler to encode a set into $X$ which is already known to uncountable.

Take for example $\{0,1\}^{\mathbb{N}}$, the uncountable space of binary sequences. Define a function $\Omega$ from $\{0,1\}^{\mathbb{N}}$ to $X$ which sends $(a_1,a_2,a_3\ldots)$ to the sequence $(x_n)$ defined by $x_i=i$ if $i$ is odd, $x_2=0$ and for every $i\geq 1$, $x_{2i+2}=x_{2i}-a_i-1$. Since one can recover $(a_1,a_2,a_3,\ldots)$ from $\Omega((a_1,a_2,a_3,\ldots))$ the function $\Omega$ is injective, and so $X$ must be uncountable as well.

$\endgroup$

You must log in to answer this question.

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