# Gödel's Incompleteness Theorem - Diagonal Lemma

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?

-

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

## 1 Answer

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.

-

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 28, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9049021005630493, "perplexity_flag": "head"}