Difficulty: Intermediate | Prerequisites: Comfort with proof by contradiction, basic set theory (countable vs uncountable sets), and familiarity with Turing Machine basics from Section 3.
Diagonalization is one of the most important proof techniques in theoretical computer science, and it originates from pure mathematics. In EECS 376, it sits at the boundary between "what computers can do" and "what they cannot," bridging Cantor's 19th-century work on infinite sets with modern computability theory. You need this tool to understand why certain problems are provably unsolvable by any algorithm. If you are comfortable with Turing Machines from the previous section and know what proof by contradiction looks like, you are ready.
Cantor's diagonalization argument proves the real numbers are uncountable: you cannot list them all, because for any proposed list you can always construct a number that differs from every entry. This technique carries over directly to computer science, where it shows there are more problems than there are programs to solve them, meaning some problems are inherently incomputable.
Diagonalization argument
A proof technique that constructs an object (a number, a string, a language) guaranteed to differ from every item in a proposed enumeration by changing the diagonal entry. In simple terms, you walk down the diagonal of a table and flip each entry, producing something the table cannot contain.
Countable set
A set X is countable if there exists a surjective (onto) function f : N → X. Think of it as: you can assign a natural number label to every element in the set without missing any.
Uncountable set
A set that is not countable. No listing indexed by natural numbers can cover all its elements. The set of real numbers is the classic example.
Complement of a binary string
Given a binary string b, its complement (written with an overline) flips every bit: 0 becomes 1, 1 becomes 0. For example, the complement of 01101 is 10010.
Incomputable (undecidable) problem
A problem for which no Turing Machine (equivalently, no computer program) can produce the correct answer for every possible input. In simple terms, there is no algorithm that always solves it.
Georg Cantor (1891) set out to prove that the infinity of the reals is strictly larger than the infinity of the naturals.
The argument proceeds by contradiction. Assume the reals are countable, meaning you can list every real number in a table A where each row is the binary expansion of one real number.
Each row r_i corresponds to one real, and each column j holds the j-th bit of that real's binary representation.
Take the diagonal entries of the table: A_{1,1}, A_{2,2}, A_{3,3}, and so on.
Define a new number s by flipping each diagonal bit: s_i = complement of A_{i,i}.
By construction, s differs from row 1 in position 1, from row 2 in position 2, and in general from row i in position i.
Therefore s cannot appear anywhere in the table. But the table was supposed to contain every real number, so we have a contradiction.
Conclusion: the reals are uncountable.
Any piece of information (a language definition, a C++ programme, a homework problem) can be encoded as a finite binary string.
The set of all finite binary strings is countable, so the set of all Turing Machines is countable.
The set of all possible languages (decision problems) over a binary alphabet is uncountable, by a diagonalization argument analogous to Cantor's.
Because there are uncountably many problems but only countably many Turing Machines, most problems have no Turing Machine that solves them. These are the incomputable problems.
Countability definition
A set X is countable if there exists a function f : N → X that is surjective (onto).
Complement notation
For a binary string b, the complement is written with an overline. Each bit is flipped: 0 → 1, 1 → 0.
Examples: complement of 00 = 11, complement of 01101 = 10010.
Diagonal construction
Given a table A of binary strings (one per row), define s bit by bit:
s_i = complement of A_{i,i}
This guarantees s differs from every row of A in at least one position.
Diagonalization is the backbone of undecidability results that affect real software engineering. The halting problem (whether a given programme terminates) is undecidable, and that is why no compiler or static analyser can catch all infinite loops. More broadly, any time you hear that a verification task is "in principle unsolvable," diagonalization is usually the proof technique behind that claim.
Students often think "uncountable" just means "really large." It does not. The set of even numbers is infinite and large, but it is still countable. Uncountable specifically means no surjection from the naturals exists.
Some students believe the diagonal argument only works for reals in binary. The argument generalises to any base and to other structures entirely (e.g. sets of languages).
A common error is confusing "uncountably many problems exist" with "no specific problem is incomputable." The argument is existential: it proves incomputable problems exist, and named examples (the halting problem) confirm this concretely.
Students sometimes think the constructed number s could just be added to the table to fix it. It cannot: for any revised table, a new diagonal construction produces yet another missing number.
⚠️ Be prepared to reproduce the diagonal construction step by step: define s_i = complement of A_{i,i}, then explain why s differs from every row.
⚠️ Know the formal definition of countable (a surjection from N to X) and be able to state it precisely.
⚠️ Understand the bridge to computability: Turing Machines are countable, languages are uncountable, therefore incomputable languages exist.
⚠️ Exam questions often ask you to apply the diagonalization technique to a new scenario (not just Cantor's original). Practise the pattern, not just the example.
True or false: The set of all integers is uncountable.
Fill in the blank: A set X is countable if there exists a ______ function f : N → X.
True or false: If you flip every diagonal bit of a table listing all reals, the resulting number must already be in the table.
Fill in the blank: The set of all Turing Machines is ______ (countable / uncountable).
True or false: Diagonalization proves that most languages (decision problems) have no Turing Machine that decides them.
Answers: 1. False (integers are countable). 2. Surjective (onto). 3. False (it cannot be in the table, which is the whole point). 4. Countable. 5. True.
Q: Describe Cantor's diagonalization argument and explain why the constructed number s cannot appear in the table.
A: Assume all reals can be listed in a table A, where row i is the binary expansion of a real number. Construct s by setting s_i = complement of A_{i,i} (flip the i-th diagonal bit). Then s differs from row i in position i for every i, so s cannot match any row. This contradicts the assumption that the table contains all reals.
Q: Why does the existence of uncountably many languages imply that some languages are incomputable?
A: Every Turing Machine can be encoded as a finite binary string, so the set of all Turing Machines is countable. The set of all languages over {0,1} is uncountable (by a diagonalization argument on characteristic sequences). Since there are strictly more languages than Turing Machines, there must be languages with no corresponding Turing Machine, i.e. incomputable languages.
Q: A classmate claims they can fix the diagonal argument by inserting s into the table as a new row. Why does this fail?
A: Inserting s produces a new table, but you can run the diagonal construction again on the new table and produce a fresh number s' that is not in the updated table. No matter how many times you insert the missing number, a new diagonal construction always finds another one missing. The argument works against any proposed complete listing, not just one specific table.
This material connects directly to the halting problem (Sipser Ch. 4), which is proved undecidable using a diagonalization-style argument on Turing Machines rather than real numbers. It also sets the stage for the reductions covered in Section 2 of these notes (Sipser Ch. 5), where you use known undecidable problems to prove new ones undecidable. More broadly, the countable-vs-uncountable distinction reappears throughout complexity theory when classifying problem classes.
Cantor's diagonal argument, diagonalization proof, countable set, uncountable set, surjection, onto function, proof by contradiction, binary representation of reals, incomputable problem, undecidable language, Turing Machine enumeration, cardinality, aleph-null, aleph-one, power set argument, EECS 376, Sipser Chapter 4, computability theory, set theory, countability argument