Editing Diagonal lemma (section)

{{Short description|Statement in mathematical logic}}
{{Other uses|Diagonal argument (disambiguation){{!}}Diagonal argument|Diagonalization (disambiguation)}}In [[mathematical logic]], the '''diagonal lemma'''  (also known as '''diagonalization lemma''', '''self-reference lemma''' or '''fixed point theorem''') establishes the existence of [[self-referential]] sentences in certain formal theories.

A particular instance of the diagonal lemma was used by [[Kurt Gödel]] in 1931 to construct his proof of the [[Gödel's incompleteness theorems|incompleteness theorems]] as well as in 1933 by [[Alfred Tarski|Tarski]] to prove his [[Tarski's undefinability theorem|undefinability theorem]]. In 1934, [[Rudolf Carnap|Carnap]] was the first to publish the diagonal lemma at some level of generality.<ref>See Smoryński 2022, Sec. 3.</ref> The diagonal lemma is named in reference to [[Cantor's diagonal argument]] in set and number theory.

The diagonal lemma applies to any sufficiently strong theories capable of representing the diagonal function. Such theories include [[Peano axioms#First-order theory of arithmetic|first-order Peano arithmetic]] <math>\mathsf{PA}</math>, the weaker [[Robinson arithmetic]] <math>\mathsf{Q}</math> as well as any theory containing <math>\mathsf{Q}</math> (i.e. which interprets it).<ref>See Hájek and Pudlák 2016, Chap. III.</ref> A common statement of the lemma (as given below) makes the stronger assumption that the theory can represent all [[General recursive function|recursive functions]], but all the theories mentioned have that capacity, as well.