Past exam question: 2081 Chaitra (Regular), Q1(a)(i)
Open in the Padhaiko appState Diagonalization principle.
Solution
Cantor's Diagonalization Principle: The Diagonalization Principle (introduced by Georg Cantor in 1891) is a mathematical proof technique used to demonstrate that certain infinite sets cannot be enumerated (are uncountable), or that certain computational problems cannot be solved by any Turing machine (are undecidable).
Principle: Given an infinite list of sequences or functions where , one constructs a new sequence whose -th element differs from the diagonal element of the list (e.g., ):
Because differs from the -th sequence in at least the -th position for every , cannot appear anywhere in the enumerated list, proving that the collection is inherently unlistable (uncountable).
Significance in TOC: Used directly to prove the uncountability of real numbers and the undecidability of the Halting Problem ( and ).
The Diagonalization Principle proves uncountability or undecidability by showing that any proposed enumeration of objects can be refuted by constructing a diagonal object that differs from the -th object at position (), guaranteeing is missing from the list.