3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.