Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given the diagonal lema stated as above:

Diagonal Lema. Let $\mathfrak{T}$ be a theory wich is capable of representing the primitive recursive functions, and a codification schema for formulas in $\mathfrak{T}$ such that $\ulcorner \phi \urcorner$ is the codification of $\phi$. For all formulas $\psi(x)$ where $x$ is it's only free variable, we have $\mathfrak{T} \vdash \delta \leftrightarrow \psi(\ulcorner \delta \urcorner)$.

Why is it called after Cantor's diagonal arugment? Giving the justification why the standard diagonalization technique for demonstrating that the set of reals isn't contable is straightforward, but for this lemma it isn't.

share|improve this question

3 Answers 3

up vote 1 down vote accepted

Are you asking why it is named "Diagonal Lemma"?

It doesn't seem to be named directly after Cantor, but I suspect Cantor's argument was an early, influential use of arguments that make use of the diagonal elements of some structure.

The term "diagonal" is now often used to refer to the mapping $i \mapsto A(i,i)$ whenever $A(i,j)$ parametrizes some natural collection of objects (or just the image of this mapping). Another analogy is that of the diagonal of a matrix. The Diagonal Lemma can be viewed as constructing an object on a certain diagonal, hence the name.

share|improve this answer

Firstly your diagonal lemma is not correct. The correct formulation is the following:

Diagonal Lema. Let $\mathfrak{T}$ be a theory wich is capable of representing the primitive recursive functions, and a codification schema for formulas in $\mathfrak{T}$ such that $\ulcorner \phi \urcorner$ is the codification of $\phi$. For all formulas $\psi(x)$ where $x$ is it's only free variable, there is a formula $\delta$ such that $\mathfrak{T} \vdash \delta \leftrightarrow \psi(\ulcorner \delta \urcorner)$.

I think in this form you should see some resemblance to Cantors diagonal argument.

share|improve this answer

Unfortunately, a formula δ such that T ⊢ δ ↔ ψ(┌δ┐) is not analogous to Cantor's method. Cantor did not codify, which generates a novel term for an existing sequence, rather his method generates a novel sequence in the same terms. The diagonal method implicit in Godel flipping provability, then incorporating it within the existing axiomatic system to render it undecidable. Thematically, generating a statement within the existing sequence that can't be incorporating in it, is a bit like Cantor's new series drawn from the set's flipped diagonals, since it's a new series that doesn't exist in the set. This thematic similarity, however, has to do with generating a novel sub-set within an existing set, while Cantor's "diagonalization" refers to a specific method of generating such a sub-set. Calling the theme "diagonal lemma" is perhaps misguided, since diagonal suggests a geometric shape implicit in Cantor's method, a method that Godel didn't use. There's not diagonal in diagonal lemma. Other lemmas are more literal. Horseshoe Lemma, for example, is named because the diagram that forms the lemma looks like a horseshoe.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.