Diagonalization

 

🧩 What is Diagonalization?

Definition

Diagonalization is a proof technique used to show that some sets are uncountable, or equivalently, that no enumeration (listing) of all elements in that set is possible.

It was introduced by Georg Cantor in the late 19th century to prove that:

The set of all real numbers (ℝ) is uncountable.

Later, this same method was applied in computability theory to show that:

There are languages that cannot be recognized by any Turing machine.

---

💡 The Idea in Simple Terms

Let’s start from a countable set $S=\{s_1,s_2,s_3,\mathrm{.}\mathrm{.}\mathrm{.}\}$ Its power set $2^S$ is the set of all subsets of $S$.

Every subset $T \subseteq S$ can be represented as an infinite binary sequence:

• 1 in position i → means $s_i \in T$
  

• 0 in position i → means $s_i\mathrm{\notin }T$

So, each subset corresponds to a sequence like:

T1: 011001...
T2: 110010...
T3: 100011...

If we try to list all possible subsets (as T1, T2, T3, ...),
we can visualize them in a table like this:

	s₁	s₂	s₃	s₄	s₅	...
T₁	0	1	1	0	0	...
T₂	1	1	0	0	1	...
T₃	1	0	0	1	1	...
...	...	...	...	...	...	...

Now, look at the diagonal (the elements in bold):

0 (from T₁, s₁), 1 (from T₂, s₂), 0 (from T₃, s₃), ...

If we flip each bit (change 0 → 1 and 1 → 0), we get a new sequence.

This new sequence differs from each Ti in at least one position (the diagonal one).

Hence, it cannot be any of the Ti listed.

➡️ Therefore, our assumption that we could list all subsets (that 2^S is countable) is false.

So, 2^S is uncountable.

---

🧠 Connection to Automata Theory and Computability

This same diagonalization argument is used in automata theory and computability to show deep results about languages and Turing machines.

---

1️⃣ Step 1: Turing machines are countable

Each Turing machine can be represented by a finite description —
a finite sequence of symbols over a finite alphabet.

Hence, we can enumerate all possible Turing machines:

$$M_1, M_2, M_3, M_4, \dots$$

✅ Therefore, the set of all Turing machines is countable.

---

2️⃣ Step 2: The set of all languages over an alphabet Σ is uncountable

Each language is a subset of all possible strings (Σ*).

Since Σ* is countable, its power set (the set of all subsets, i.e., all possible languages)
is uncountable, by Cantor’s diagonalization.

$$\text{Languages over Σ are uncountable.}$$

---

3️⃣ Step 3: There are more languages than Turing machines

Because:

• Turing machines are countable.

• Languages are uncountable.

Therefore, there must be languages that no Turing machine can recognize.

---

4️⃣ Step 4: Consequence

This leads to one of the most profound results in computability:

There exist languages that are not recursively enumerable.

That means:

• No Turing machine can even enumerate all their valid strings.

• These languages are beyond computation.

---

🔍 Example of Diagonalization Used in Computability

To show that some language is not Turing recognizable, we use the diagonal language:

$$L_d = \{ w_i \mid w_i \text{ is not accepted by } M_i \}$$

\where:

• $M_i$ is the i-th Turing machine in our enumeration.

• $w_i$ is the i-th string in Σ*.

Now, we ask:

Is there a Turing machine that recognizes $L_d$?

If there were such a machine $M_d$, then $M_d = M_k$ for some k.

Now, ask whether $w_k \in L_d$:

• If $M_k$ accepts $w_k$, then by definition $w_k \notin L_d$.

• If $M_k$ rejects $w_k$, then by definition $w_k \in L_d$.

❌ Contradiction.

Hence, no Turing machine can recognize $L_d$.
This is another use of diagonalization — proving non-recognizability.

---

🧾 Summary

Concept	Explanation
Diagonalization	Technique to construct a new element not in any countable list
Origin	Introduced by Georg Cantor
Used to prove	Some sets (like real numbers or power sets) are uncountable
In Automata Theory	Shows there are more languages than Turing machines
Consequence	Some languages are not Turing recognizable
Related theorem	“The set of recursively enumerable languages is countable; the set of all                 languages is uncountable.”

---

🧩 Intuitive Understanding

Diagonalization is like saying:

“No matter how you try to list all possible things,
I can always construct a new one that isn’t in your list.”

This insight leads to the understanding that:

• Not everything that exists mathematically is computable.

• Some problems can never be solved by any algorithm.