2
$\begingroup$

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?

  • 0
    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)$.2012-06-02

2 Answers 2

1

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.

  • 0
    You are right, thank you very much. Do you have any reference on why the diagonal lemma is named after Cantor's diagonal argument?2012-06-04