10
$\begingroup$

I'm missing something in the argument for Godel's First Incompleteness Theorem, and I'm hoping that someone can clear up my muddle.

Godel constructs a sentence that is true iff it is unprovable. Here's my understanding of how he constructs it (taken from Peter Smith):

  1. Consider U(y), with open variable y. U(y) is defined as "For all x, x does not code for a sequence of numbers that constitutes a proof of the diagonalization of the wff coded for by y."
  2. The Godel sentence is the diagonalization of U(y). Meaning, the Godel sentence is "For all x, x does not code for a sequence of numbers that constitutes a proof of the diagonalization of U(y)."

The thing that I'm having trouble getting my head around is this: isn't U(y) an open sentence? Meaning, the variable 'y' is free in U(y). It was my understanding that open sentences aren't the sort of things that we could prove or not prove.

Now, I understand that the diagonalization of U(y) itself is not an open sentence, since it takes U(y) as its input. Still, I'm having trouble understanding what a proof of U(y) or its diagonalization would even look like. It seems trivial to me that the diagonalization of an open sentence wouldn't have a proof.

Can somebody check my understanding? What am I missing or misunderstanding? Thanks in advance.

  • 0
    Thinking about this some more, my inclination is that, no, it's not entirely shocking that a sentence constructed in this way (as the diagonalization of U(y) is) is unprovable. The real surprise is that the sentence is, as a consequence, true. Does that make sense?2011-04-24
  • 0
    The best thing to do is forget about the "intuitive description" and look at the formal mathematics.2011-04-24
  • 1
    U(y) is: If you consider y as an encoding of a statement Y(z) with one free variable, then there is no proof of Y(y). Then if u is an encoding of U(y), then U(u) essentially becomes: "There is no proof of U(u)." The statement U(y) is a general statement that might be true for some specific y, and not true for other specific y. But when the specific u is applied, we see Godel's result.2011-04-24
  • 1
    Nobody is stating anything about proving a statement with a free variable. Let's say $z$ encodes the statement Z(x)="x is a prime." Z(x) has a free variable, $x$, but the statement $U(z)$ states: "There does not exist a proof of Z(z)," which can be written as "There does not exist a proof that z is prime."2011-04-24

2 Answers 2