Diagonalization - Definition and Overview

The term diagonalization is used in two different senses in mathematics:

• The process of finding a diagonal matrix similar to a given square matrix or representing a given linear map. See diagonalizable matrix for more.
• A certain proof technique used to show that one set is larger than another. Examples are Cantor's diagonal argument to show that the set of real numbers is uncountable, the proof of Gödel's incompleteness theorem, and Turing's proof that no algorithm can solve the halting problem. See the Diagonalization Lemma for a more formal version.