Countability of a subset of sequences

Question

Let $\mathcal{A} = \{a \in \{1,2,3,4,5\}^\Bbb N : |a_i- a_{i+1}| = 1 \; \forall i\}.$ Is the set $\mathcal{A}$ countable?

I tried an argument like Cantor's diagonalization process but without success. This problem arises when solving the hiding cat puzzle (https://www.youtube.com/watch?time_continue=2&v=yZyx9gHhRXM). Indeed, if that set is countable and $\{a^1, a^2,...\}$ is an enumeration of $\mathcal{A},$ then we can define $a \in \{1,2,3,4,5\}^\Bbb N$ by $a_i = a^i_i.$ Then, the sequence $a$ solves the puzzle.

Answer 1

For any $g\in \{1,3\}^{\Bbb N}$ let $g^*\in \{1,2,3\}^{ \Bbb N}$ where $g^*(2n)=g(n)$ and $g^*(2n-1)=2.$

Then $g^*\in A.$ And if $g,h \in \{1,3\}^{\Bbb N}$ with $g\ne h$ then $g^*\ne h^*.$

So $\{g^*: g\in \{1,3\}^{\Bbb N}\}$ is an uncountable subset of $A$ because $\{1,3\}^{\Bbb N}$ is uncountable (Cantor).

Answer 2

Intuitively, you can encode infinite sequences of $0$s and $1$s as such a sequence: encode $0$ as '$2,1$' and $1$ as '$2,3$'. This ensures that consecutive terms in the sequence are exactly one apart.

For example $0,1,1,0,1,0,\dots$ is encoded as $$2,1,2,3,2,3,2,1,2,3,2,1,\dots$$

This defines an injection $\{0,1\}^{\mathbb{N}} \to \mathcal{A}$, meaning that $\mathcal{A}$ is at least as large as $\{0,1\}^{\mathbb{N}}$, which is uncountable.