Diagonalization argument

Definition

A diagonalization argument is a general format of argument that is used to show the existence of a language that lies outside a certain complexity class or cannot be decided by machines of a certain type. The classic application is to showing the existence of undecidable languages via the halting problem.

These arguments are adaptations of the Canton diagonalization argument that shows that a set (whether finite or infinite) cannot be put in bijection with its power set.