Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In proving Gödel's incompleteness theorem, why does he needed the Diagonal Lemma or the Fixed Point Theorem for building a formula $\phi$ that spoke about itself? Can't this formula be built this way:

Diagonal Function. Let $D(x, y)$ be the diagonal function, such that $D$ returns the result obtained by replacing the formula with Gödel number $y$ for all free occurrences of $a$ in the formula with Gödel number $x$.

Example. Let $\psi(a)$ be a formula that affirms that some formula with the Gödel number of $a$ is closed (has no free variables) and $k$ be it's Gödel number. Using Diagonal Function to construct a formula, by applying $D(k, k) = j$, the Gödel number $j$ will already be the Gödel number of a formula affirming that the formula itself has no free variables. I mean, $\ulcorner \psi(\ulcorner \psi(a) \urcorner) \urcorner = j$, or $\ulcorner \psi(\overline{k}) \urcorner = j$.

What i am missing here?

share|cite|improve this question
Are you referring to a particular exposition of Gödel's work? His own original article does not name any "Diagonal Lemma" or "Fixed Point Theorem" -- its lemmas and theorems are simply numbered. – Henning Makholm Jun 2 '12 at 15:01
You are right, i'm referring to Mendelson's (Introduction to Mathematical Logic) exposition on the subject. – felipegf Jun 2 '12 at 15:05
So you're using $D(u,u)$ for what Mendelson (fourth edition, section 3.5) just calls $D(u)$? – Henning Makholm Jun 2 '12 at 15:10
I didn't wanted to define $sub$, but i wanted everyone to see that in fact $D(x,y)$ just replaces all free occurrences of a free variable $a$ (in the $sub$ predicate the Gödel number of the free variable is passed as an argument) in the Gödel number of a formula $x$ for the formula (whose Gödel number is) $y$. In fact, $D(u, u)$ is equivalent to $D(u)$. – felipegf Jun 2 '12 at 15:18
up vote 0 down vote accepted

If I understand your notation correctly, the formula (whose Gödel number is) $j$ does not assert that $j$ itself has no free variables, merely that $\psi(a)$ (which is different from $j$ itself) has no free variables. Which, incidentally, is false because it has $a$ as a free variable.

share|cite|improve this answer
You are right, thank you very much. Do you have any reference on why the diagonal lemma is named after Cantor's diagonal argument? – felipegf Jun 4 '12 at 4:05

Your Answer


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.