Math 2.0

Lemma

Strong diagonal lemma

Statement

Let ψ(x)\psi (x) be any formula in the language of TT with only xx as free variable. Then there is a term tt in the language of TT such that T⊢t=⌜ψ(t)⌝T \vdash t = \ulcorner \psi (t) \urcorner.

Trivially, the diagonal lemma follows from the strong diagonal lemma (take φ(x)\varphi (x) to be ψ(t)\psi (t)). Note however that the strong diagonal lemma depends on the language of TT, particularly on whether there is such a term tt. Typically, the strong diagonal lemma fails for theories in the basic language of arithmetic (such as 𝖰\mathsf{Q} or 𝖯𝖠\mathsf{PA}), but holds for primitive recursive arithmetic 𝖯𝖱𝖠\mathsf{PRA} which has a function symbol for each primitive recursive functions.

Further reading

  1. Wikipedia, page 348969, revision 1344931050, Diagonal lemma, section Some generalizations > Strong diagonal lemma. adopted
About this page
Tag7PZDPCVK7Z
URIm2://7PZDPCVK7Z
Kindstatement, lemma
WritingW0 stub
StatusThis copy of the site has no build data. Run m2 status 7PZDPCVK7Z.
Changed4 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • edge uses out: each definition that the statement needs (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.