Determine whether the given set is countable

Question

Given the set $V = $ { $w$ | $w$ is an infinite sequence in the form of $a_0a_1a_2\ldots$ with $a_i \in \{0,1,2\}$ for all $i \ge 0$ }

Determine if V is countable.

I'm assuming V is countable, and have included what I believe is the proof below, I'm wondering if I am correct in my assumption that it is countable, and if the proof is sufficient.

I have that V is countable, because for each $i \ge 0$ we have a string $w$ that has length $i+1$ and has $3^{i+1}$ permutations. Meaning that if $i = 0$ we could map $1, 2, 3$ to the possible strings, and if $i = 1$ we can map $4, 5, \ldots, 12$ to the 9 strings with length $2$.

This same principle holds for all $i \ge 0$. Therefore there is a correspondence between $\mathbb{N}$ and V.

Answer 1

Let $w \in V$ be a string consisting of only 0s and 1s. We may interpret $w$ as the characteristic function of a set $S_w \subseteq \mathbb{N}$ of natural numbers in the following way: $$ x \in S_w \text{ if and only if } w_x = 1 . $$

This immediately given a bijection between $V_{0,1}$, the strings with only 0s and 1s, and the power set of the natural numbers.

It follows that $V_{0,1}$ is uncountable. Since $V$ has $V_{0,1}$ as a subset, $V$ is uncountable.

Answer 2

Suggested by @Luke's comment, we can argue like this. First, as you likely know, a set $V$ is countable if and only if it can be written as as a sequence $\{s_0, s_1, \dotsc \}$. Suppose that your set $V$ was countable. Then we could describe it as a sequence of infinite strings $$\begin{align} s_0 &= a_{00}\,a_{01}\,a_{02}\dotsm \\ s_1 &= a_{10}\,a_{11}\,a_{12}\dotsm \\ s_2 &= a_{20}\,a_{21}\,a_{22}\dotsm \end{align}$$ and so on, where each $a_{ij} \in \{0,1,2\}$. Since $V$ was assumed to be countable, then by definition, this enumeration must contain all strings in $V$. Now define a string $\hat{s}=d_0d_1d_2\dotsc$ by $$ d_i = \begin{cases} 0 &\text{if $a_{ii} = 1$}\\ 1 &\text{if $a_{ii} = 2$}\\ 2 &\text{if $a_{ii} = 0$} \end{cases} $$ Now we see that $\hat{s}$ isn't in the enumeration $s_i$: It can't be $s_0$ since it differs from $s_0$ in the zero-th digit, $a_{00}$; it can't be $s_1$ since it differs from the first digit, $a_{11}$, and so on, so it's a string that is none of the strings $s_0, s_1, \dotsc$. However, our assumption was that there was an enumeration that consisted of all strings over $\{0,1,2\}$, meaning that $V$ couldn't possibly be countable.

This, by the way, is known as Cantor's diagonal argument. I wish I could claim it as my invention, but Cantor came up with it before almost anyone on SE was born.

---

Your construction was a correct correspondence between $\mathbb{N}$ and all finite strings over $\{0,1,2\}$. Given any $n\in\mathbb{N}$, your correspondence will give a string of $k$ digits, where $k$ is about $\log_3 n$, but notice that we're not dealing with finite strings when we're talking about $V$. If it's any comfort, this is a subtle point that trips a lot of people up (and has led to enormously long and frustrating threads in internet discussion fora).

Answer 3

I think you can use a similar strategy from the proof of the uncountability of the reals.

---

Proof: Assume $V$ is countable.

Let's list a few members of V

$$ \begin{align*} x_{1} &= a_{11}a_{12}a_{13}\dots \\ x_{2} &= a_{21}a_{22}a_{23}\dots \\ \vdots \\ x_n &= a_{n1}a_{n2}a_{n3}\dots \\ \vdots \end{align*} $$

Now, let $y = b_1b_2b_3 \dots$ so that $b_n = \begin{cases} 2 \quad \text{ if $a_{nn} \neq 2$} \\ 0 \quad \text{if $a_{nn} = 2$} \end{cases} $

Since the numbers in the sequence $y$ are either 0 or 2, that means $y \in V$. However, since $y$ differs from $x_n$ in the $n^{th}$ place in the sequence, it is not one of the members $x_n$.

This contradicts out assumption that V is countable.

See Steven Lay's proof for the uncountability of the Reals.