Proof by contradiction, that a set of all binary sequences, where "1" cant be twice in a row, is uncountable

Question

I emphasize that I want to prove it by contradiction using cantor diagonal method.

$$A = \{ (a_i) \mid \text{$a_i$ all the binary sequence where $1$ doesn't appear twice in a row}\}.$$

So I'm assuming $A$ is a countable set, and trying to find a contradiction by finding $(a_i)$ in $A$ but not listed.

My first attempt was to take the diagonal and change every $0$ to $1$ and vice versa.

a1 = 01001...
a2 = 10100...
a3 = 01000...
a4 = 00001...
a5 = 10101...

For this example my attempt fail because I will get 11110 which is definitely not part of $A$ (because $1$ appears twice in a row).

The next attempt was to change $0$ to $1$ only if there is not a $1$ in the previous digit.

For this attempt I will get 10100, which is definitely in $A$, but also mentioned before $(a_2)$, so it isn't a contradiction.

Answer 1

Consider each sequence $a_n$ as a sequence of two-digit groupings. So for instance $0101001010...$ would become $01\,\,01\,\,00\,\,10\,\,10...$

Now construct the sequence which has $01$ as its $n$th two-digit grouping if $a_n$ has $00$ as its $n$th two-digit grouping; otherwise it has $00$. This constructed sequence belongs to $A$ but differs from every $a_n$.

Answer 2

The set $A$ consists of all binary strings which never contain $11$ as a substring. Most such strings can be described as a sequence of positive integers, where the number in the $n$-th slot represents the number of zeros between the $n$-th and $(n+1)$-st occurrence of $1$. For example, the sequence $$(1,2,3,4,\dotsc)$$ represents the binary string $$01001000100001\dotsc.$$ This description will not account for a string which ends with an infinite number of zeros, but this can be patched up by appending a new element (say, $\infty$) to the integers, and repeating this element after the final $1$. So, for example, the sequence $$(1,2,4,\infty,\infty,\infty)$$ represents the string $$ 01001000010000000000\dotsc. $$ It is also possible for the first letter of such a string to be $1$, so allow the first term of a sequence describing an element of $A$ to be zero. For brevity of notation, let $B$ denote this set of sequences. That is, if $b \in B$, then $$ b = (b_1, b_2, b_3, b_4, \dotsc), $$ where $b_1 \in \mathbb{N}\cup\{0\}$; $b_j \in \mathbb{N}\cup\{\infty\}$ for all $j > 1$;, and if $b_j = \infty$, then $b_{j+1} = \infty$.

There is a one-to-one correspondence between elements of $A$ and sequences of the type described above; it is is sufficient to show that this set of sequences is uncountable, which can be done using the traditional diagonalization argument: let $f : \mathbb{N} \to B$ be any function. The goal is to show that $f$ cannot be surjective. To do this, construct a sequence $b = (b_1, b_2, \dotsc)$ in $B$ which is not in $f(\mathbb{N})$ as follows:

For each $n \in \mathbb{N}$, let $f(n) = ( f(n)_1, f(n)_2, f(n)_3, \dotsc )$. That is, $f(n)_j$ denote the $j$-th term of $f(n)$. Then

• if $f(n)_j\ne \infty$, then set $b_j = f(n)_j+1$, and

• if $f(n)_j = \infty$, then set $b_j = 1$.

---

NB: The diagonalization argument is often taught as a "proof by contradiction". I am not a big fan of that argument. Rather, the point is that if $\operatorname{card}(D) \ge \operatorname{card}(E)$, then there must be a surjective map from $D$ to $E$. To show that no such surjection exists, it is sufficient to show that if $f : D \to E$ is any map, then there must be at least one element $e \in E$ which is not in the image of $f$. If this can be done, then it has been shown that $\operatorname{card}(E) < \operatorname{card}(E)$.

In this case, take $D = \mathbb{N}$ and $E = B$ (where $B$ is the set I have defined above, which is in one-to-one correspondence with the set $A$ of strings defined in the question). The argument above shows that there cannot be a surjective map from $\mathbb{N}$ to $B$, hence $\operatorname{card}(\mathbb{N}) < \operatorname{card}(B) = \operatorname{card}(A)$.

Answer 3

Fact 1. Every $a\in A$ satisfies $a_i=0$ for infinitely many $i\in \mathbb N$.

Assume by contradiction that $A$ is countable, say $A=\{a^1,a^2,\dots\}$.

Let $z_1 \in \mathbb N$ be minimal, such that $a_{z_1}^1 = 0$. Now recursively define $z_{n}\in \mathbb N$ minimal such that $z_{n}>z_{n-1} +1$ and $a_{z_{n}}^{n}=0$. These $z_i$ exist by Fact 1.

Now we define a new sequence $b$ by setting $$ b_{z_i} = 0,\quad b_{z_i+1}=\text{flip}(a^i_{z_i+1}) $$ and $b_j=0$ when $j$ is not $z_i$ or $z_i+1$ for some $i$. By definition $b\neq a^i$ for every $i\in\mathbb N$. Furthermore, $b$ is well-defined since $z_{n}>z_{n-1} +1$.

And by construction we have $b\in A$, which is a contradiction.

Answer 4

Every $1$ is always followed by a $0$, so you can replace any $10$ with a $1$, and you're now able to form any arbitrary binary string.

This works the other way too (add a $0$ after every $1$), giving you a bijection between $A$ and all binary strings. Thus $A$ is uncountable.

It's not a diagonalization proof, but it's simpler IMO

Answer 5

You can prove $A$ uncountable as follows. (Here I denote the set of all infinite binary sequences by $2^\mathbb N$.)

0. Prove $2^\mathbb N$ uncountable by the usual diagonal argument.

1. Define a function $f : 2^\mathbb N \to A$ as follows:

   $$ f(x)_n := \begin {cases} x_k & \text {if $n = 2k$ for some $k$} \\ 0 & \text {otherwise} \end {cases} $$

   In other words, $f$ interleaves its argument with a sequence of zeroes; the image of $f$ is the set of all binary sequences where every odd-indexed item is zero. $f$ is easily proven injective: if $x$ and $y$ differ at position $k$, then $f(x)$ and $f(y)$ differ at position $2k$. Therefore $|2^\mathbb N| = |f[2^\mathbb N]|$.

2. You can now say $A$ is uncountable, because you have exhibited uncountably many elements of it. Said differently, since $f[2^\mathbb N] \subseteq A$, we have that $|\mathbb N| < |2^\mathbb N| = |f[2^\mathbb N]| \le |A|$, or simply $|\mathbb N| < |A|$. $\blacksquare$

The above is probably not a proof your instructor had in mind, but it does rely on a diagonal argument; just one applied to $2^\mathbb N$ and not to $A$ itself. If you study it for a while, however, and think how the argument is transformed “through” the mapping $f$, it should give you a few ideas how to apply the diagonal argument to $A$ more directly:

• For example, from a surjection $a : \mathbb N \to A$, you should be able to construct a surjection $a' : \mathbb N \to f[2^\mathbb N]$ by skipping each element of $A \setminus f[2^\mathbb N]$, apply the diagonal argument to $f[2^\mathbb N]$ by constructing a sequence $x$ such that $x_{2k} = 1 - a'(k)_{2k}$, and $x_{2k+1} = 0$; notie that $x$ cannot be $a'(k)$ for any $k$, because it differs at index $2k$. Therefore $x$ is not in the image of $a'$ and $a'$ could not have been a surjection. Then say that since $a'$ cannot be a surjection, then $a$ could not have been a surjection either.
• Or even more directly: given a surjection $a : \mathbb N \to A$, construct a sequence $x$ like before directly from $a$, and apply the same argument.

After all, the point of the diagonal argument is not the diagonal itself, i.e. that you must use the exact same index twice with a sequence of sequences. The diagonal is just a convenient way to navigate two indexing dimensions at once and exhibit an element not previously enumerated.