Question about Gödel's Incompleteness Theorem

Question

Gödel used prime factorization to encode each statement with a unique number (which is Gödel numbering).

But I wonder if this statement can be encoded:

"If this statement can be encoded, then this statement is false."

If it can be encoded, then it will be false and the truth will become "This statement can be encoded and this statement is true." And that leads to a contradiction, so it cannot be encoded.

Are there any mistakes? If not, did I just prove that Gödel's numbering is wrong??

Answer 1

Godel proved his result by first setting up a system of mathematical logic that can do the basics of arithmetic. It includes the symbols $\Rightarrow$ "if then", $\wedge$ "and", etc. It also includes the natural numbers and some of their operations. In order for your statement to work, you would need to encode "If this statement can be encoded, then this statement is false." into his system. Then you would need to show that this encoded statement is not itself undecidable. One or both of these things is not possible.

Answer 2

"To encode each statement" is not quite right.

"I had Cheerios for breakfast," for example, cannot be encoded.

The set of things encoded is a quite carefully described set, and metastatements like yours are not within that limited set. Hence your "contradiction" is not a useful one.

As a gratuitous aside: this stuff isn't simple. You have to actually understand the details, not just the broad strokes, before you can start building counterexamples.

Answer 3

It is impossible to encode the statement "Statement X is true." This follows from Tarski's Undefinability Problem:

The formula $True(n)$, which defines the set of Godel numbers $n$ corresponding to true statements in first-order arithmetic, does not exist in first-order arithmetic.

Thus, the statement $Encodable(n) \implies \neg True(n)$ cannot be Godel-encoded because $True(n)$ does not exist as a formula.

Answer 4

The realm in which Gödel's Incompleteness Theorem is discussed isn't really about "true" and "false" statements -- it's about "provable" and "disprovable" statements.

Consider these three statements:

1. I am a blond-haired person.
2. All blond-haired people are taller than four meters.
3. I am taller than four meters.

Statement (3) is provable from statements (1) and (2) -- as in, if you assume some rules about basic logic, and you assume (1) and (2) are true, then (3) will also be true.

But here's the thing -- all three statements are actually false. It turns out that in the real world, I'm not a blond-haired person, not all blond-haired people are taller than four meters, and I'm not taller than four meters.

To "prove" that (3) is true, you need to have call (1) and (2) axioms, which is that you have to just accept that they're true, then add some logic rules, and then you'll have a system that let you deduce that (3) is true.

Now imagine the realm of all possible sentences. Most of those sentences won't make sense. Some of those sentences will be simple sentences that everyone could agree upon being true, like "One and zero are different numbers," and those would be useful as axioms. Some of those sentences would be sentences that might be provable from axioms, like "There are an infinite number of primes".

What mathematicians hoped was that they could have a finite set of axioms, a finite set of logic rules that allowed you manipulate them, and then you could have a system that could take any sentence in the language and tell you whether it was provable from the axioms -- what they call decidable statements. They did this before computers, but you can think of it like, hey, maybe we can write a program that will prove every true statement eventually... ah, but it's pretty easy to write a program that will prove every statement to be true. Read on.

Let's go back to your original proposed statement. Let's give it a name:

Statement A. "If this statement can be encoded, then this statement is false."

Can we prove it? Of course, if we pick the right axioms. I'll just do this:

Axiom B: "Statement A can be encoded."

Axiom C: "Statement A is false."

Wow, I think I can prove Statement A from Axiom B and C. It's so easy I'm not going to even write out the whole proof here; I'm sure you can figure it out.

But, here's the thing. Just like my example with the blond-haired person above, the proof of Statement A doesn't affect anything in the real world. We end up just dismissing it as nonsense. The universe doesn't explode when I say "This sentence is false," no matter how much I believe it. All that we've shown is that if you get to pick your axioms, you can prove or disprove anything. Heck, I could have just chosen Statement A as an axiom and then it's "true" (within the realm of assuming axioms are true) and yet false (in the real world outside).

Actually, it's even worse -- not only is Statement A "true" in the realm of assuming our axioms are true, it's also "false" at the same time, for the reason you outlined in your original question. What you've basically done is that you've created an inconsistent system, a place where a statement can be proven true and also proven false. And it turns out that once you have such a statement in your system, if you're assuming basic logic, then all meaningful statements become both provably true and provably false, and now you're not doing any useful math.

So, what our early 20th-century mathematicians were hoping for, was that you could start with a small finite set of really basic arithmetic axioms, a small finite set of rules of logic to let you build proofs, and that eventually this would be powerful enough to make a complete system -- a system where there would be no undecidable statements, and no inconsistent statements. A statement like yours wouldn't be encodable in this hypothetical ideal system. (Which, of course, would mean it is true, and therefore an undecidable statement, but that's okay, because it's not in the system.)

What Gödel did was to dash the hopes of the mathematicians -- he proved that if you had a finite set of axioms and a finite set of rules, then either the system was inconsistent (you could find a statement that was possible to prove true and possible to prove false), or that there existed an undecidable statement (a statement that was impossible to prove true and impossible to prove false). He did this by assigning numbers to all sentences, then showing that any proof could be reinterpreted as applying specific arithmetic rules to numbers representing axioms and generating numbers that represented provable statements. Then he proved that, if you start with a bunch of finite axioms (call them F), then he could always find a number G that represented the statement "G can't be generated from F". Which means that G is undecidable. (Of course, you could then decide to make G an axiom, but then he would just construct a number H that meant "H can't be generated from F and G", and so on.)

That was pretty amazing.

All you've done is demonstrate the existence of an inconsistent system. That's not nearly as amazing, especially since Epimenides did something similar 2700 years ago, but it's something.