I have the following question in Discrete Math 2 in one of my assignments.
A ternary sequence is defined as a function $t\colon\mathbb{N}_0\longrightarrow\mathbb{N}_0$ such that $t(3n+1) = t(3n)+1$ and $t(3n+2) = t(3n+1)+1 = t(3n)+2$, where $\mathbb{N}_0$ is the set of all natural numbers including zero (in my course the natural numbers don't include zero).
The task is to prove that the set of all ternary sequences (denoted as $T$) is uncountable. For that I need to show that $|T|\ge\aleph_0 \land |T|\ne\aleph_0$. I have managed to show that $|T|\ge\aleph_0$ but I am struggling to show that $|T|\ne\aleph_0$.
I need to use (as the question demands that) Cantor's diagonal argument (with proof by contradiction) but I am having troubles finding a proper function.
I assumed there exists a function $F\colon\mathbb{N}_0\longrightarrow T$ which is bijective. As $F(n)$ is a function I'll use the following notation $F_n = F(n)$ From this I can assume that the function looks something along the lines of:
$F_0 = \{(0,F_0(0)),(1,F_0(1)),(2,F_0(2)),\dots\} \\ F_1 = \{(0,F_1(0)),(1,F_1(1)),(2,F_1(2)),\dots\} \\ F_2 = \{(0,F_2(0)),(1,F_2(1)),(2,F_2(2)),\dots\} \\ \vdots$
I am not sure how to build a sequence $t\colon\mathbb{N}_0\longrightarrow\mathbb{N}_0$ such that $t\in T$ and that I won't be able to find an input for it in $F$. I'd love it if someone can give me a hint so that I will be able to solve this question.
Thanks in advance.
Best Answer
Suppose, for arguments sake, $t(3n)=m$, for some $m\in \mathbb N$, then we have a set that looks something like this: $$\{[m],[m+1], [m,m+1], [m,m+1,m+2],...\}$$
does it looks familiar?
Assuming $len(t_i)=|\mathbb N|, i \in \mathbb N$, for each $t_i \in T$, further assume $T$ is countable, then, we have an arbitrary mapping, $M(t_i)=i, i \in \mathbb N$.
Construct the following sequence, $\bar{t}=\alpha_1, \alpha_2,..., \alpha_n$, where each $\alpha_j\neq\beta_j$, where each $\beta_j$ is the $j^{th}$ term in the $j^{th}$ sequence. Hence, we can always create a new $t_k \in T$ such that $t_k$ has no mapping, namely $\bar t$. Therefore, $T$ is uncountable.
In visual terms,
$0:t_0=\beta_{0,0},\beta_{0,1},\beta_{0,2}...$
$1:t_1=\beta_{1,0},\beta_{1,1},\beta_{1,2}...$
$2:t_2=\beta_{2,0},\beta_{2,1},\beta_{2,2}...$
$.$
$.$
$.$
$i:t_i=\beta_{i,0},\beta_{i,1},\beta_{i,2}...$
Where $\beta_{m,n}\in \{m,m+1,m+2\}$
So, $$t_k=(\alpha_0\neq \beta_{0,0}),(\alpha_1 \neq \beta_{1,1}),...,(\alpha_i\neq \beta_{i,i})$$