An easy proof of Gödel's first incompleteness theorem?

[Stoney Pete]

Hi everybody,

Do you think the following reconstruction of Gödel's first incompleteness theorem is basically correct, or at least in the right ballpark? In my view, this incompleteness result basically turns on the mismatch between the indenumerability of the powerset of ℕ and the enumerability of all theorems of a formal axiomatic system...

Greetings,
Stoney Pete

Here is my reconstruction of Gödel's proof:

Given an effectively axiomatized formal theory T of arithmetic. Then the incompleteness of T follows in principle from the following facts:

(1) Since T is effectively axiomatized, all theorems of T can in principle be enumerated.

(2) The powerset of ℕ (i.e. P(ℕ)) is indenumerable, as shown by Cantor's diagonal argument.

(3) The set W of all effectively enumerable sets of natural numbers is itself also enumerable.

((3) follows from the fact that for each effectively enumerable set there is an algorithm that effectively enumerates it. So W is basically the same set as the set of all algorithms that effectively enumerate some set of natural numbers. And given a general-purpose programming language L, we can in principle effectively enumerate all possible strings of symbols of L and thereby also all possible algorithms, including those that effectively enumerate sets of natural numbers. Thus we can in principle enumerate W.)

From (2) and (3) it follows that W ≠ P(ℕ) and thus that W ⊂ P(ℕ). So we know that there sets in P(ℕ) which are not in W and which are therefore indenumerable. Let V be one of those indenumerable sets.

So for some x∈ℕ it is true that x∈V.

Now suppose, for reductio, that T is complete, i.e. T proves all arithmetical truths. So, in particular, for each x∈ℕ, T proves either that x∈V or -(x∈V).

But in the light of (1) above, we can then enumerate all theorems of the form x∈V. Which is tantamount to saying that we can enumerate V. But this leads to contradiction, since as we have seen V is indenumerable.

Thus T cannot prove for some x∈ℕ that x∈V although x∈V is true. Thus T is incomplete.

 

[stevendaryl]

That doesn't quite do it. What Godel was interested in was the truths in the language of arithmetic. That is, statements that can be formulated using the operations and relations of addition, multiplication, zero, successor, equality. Your set V is not expressible in that language, so the statement x∈V is not a statement of arithmetic, in Godel's sense.

 

[Stoney Pete]

Why is x∈V not expressible in the language of T? I was presupposing that it is expressible in that language... Doesn't it just depend on how rich we make the language of T? If that language is rich enough, x∈V should be expressible in it...

 

[PeroK]

As I understand it, your proof is that there are uncountably many statements (that could be theorems) but only countably many theorems and non-theorems?

 

[Stoney Pete]

Well, I am trying to understand the basic state of affairs that underlies Gödel's first incompleteness theorem. And it seems to me that it basically comes down to this:

Already due to the uncountability (or indenumerability) of P(ℕ) there are uncountably many arithmetical truths. But the theorems of an effectively axiomatized theory T of arithmetic are countable / enumerable (where a theorem is of course a statement proved by T). Thus for any such theory T, there are arithmetical truths that it cannot prove.

 

[stevendaryl]

Why is x∈V not expressible in the language of T? I was presupposing that it is expressible in that language... Doesn't it just depend on how rich we make the language of T? If that language is rich enough, x∈V should be expressible in it...

How do you define V using the language of arithmetic?

 

[Stoney Pete]

Okay, I start to see your point. I guess we can't define V using just the language of Peano arithmetic. We need some set theory to define V. I have to mull this over... Thanks for your input.

 

[stevendaryl]

Already due to the uncountability (or indenumerability) of P(ℕ) there are uncountably many arithmetical truths.

In Godel's sense that is not true. There are only countably many arithmetical truths. As I said, an arithmetical statement is one that can be formulated using the following rules:

Terms:
A term is an expression denoting a natural number. These are the rules for making terms:

1. 0 is a term
2. [itex]x_1, x_2, x_3, ...[/itex] are terms (the variables)
3. If [itex]t[/itex] is a term, then [itex]S(t)[/itex] is a term (the successor of [itex]t[/itex], that is, the number that comes after [itex]t[/itex] when counting)
4. If [itex]s[/itex] and [itex]t[/itex] are terms, then [itex]s + t[/itex] and [itex]s \times t[/itex] are terms.

Statements:

1. If [itex]t[/itex] and [itex]s[/itex] are terms, then [itex]t=s[/itex] is a statement.
2. If [itex]S[/itex] is a statement, and [itex]v[/itex] is a variable, then [itex]\forall v S[/itex] is a statement (all [itex]v[/itex] make [itex]S[/itex] true)
3. If [itex]S[/itex] is a statement, and [itex]v[/itex] is a variable, then [itex]\exists v S[/itex] is a statemen (there is some [itex]v[/itex] that makes [itex]S[/itex] true)
4. If [itex]S[/itex] is a statement, then [itex]\neg S[/itex] is a statement (the negation of [itex]S[/itex])
5. If [itex]S[/itex] and [itex]T[/itex] are statements, then so is [itex]S \wedge T[/itex] ([itex]S[/itex] and [itex]T[/itex] are both true)
6. If [itex]S[/itex] and [itex]T[/itex] are statements, then so is [itex]S \vee T[/itex] (at least one of [itex]S[/itex] or [itex]T[/itex] is true)
7. If [itex]S[/itex] and [itex]T[/itex] are statements, then so is [itex]S \Rightarrow T[/itex] ([itex]S[/itex] implies [itex]T[/itex])

There are only countably many arithmetical statements.

 

[Stoney Pete]

Yes, I see your point. But what is the role of diagonalization in Gödel's proof? In some way I don't understand yet, diagonalization also underlies the construction of the self-referential sentence G in the language of arithmetic which states 'G is unprovable'. And this diagonalization, I would think, must have something to do with the diagonalization that proves the indenumerability of P(ℕ). So, it seems, indenumerability must have something to do with Gödel's proof.

 

[stevendaryl]

Yes, I see your point. But what is the role of diagonalization in Gödel's proof? In some way I don't understand yet, diagonalization also underlies the construction of the self-referential sentence G in the language of arithmetic which states 'G is unprovable'. And this diagonalization, I would think, must have something to do with the diagonalization that proves the indenumerability of P(ℕ). So, it seems, indenumerability must have something to do with Gödel's proof.

Maybe I can come up with a connection between the two.

In Cantor's proof of the uncountability of the set of subsets of the naturals, you start with an assumed enumeration of sets of naturals:

[itex]S_1, S_2, S_3, ...[/itex]

Then you define a new set [itex]S_{diag}[/itex] according to the rule: [itex]n \in S_{diag} \Leftrightarrow n \notin S_n[/itex]

Obviously, [itex]S_{diag}[/itex] cannot be equal to [itex]S_n[/itex] for any value of [itex]n[/itex].

Now, with Godel, the issue is provability, so we modify things in the following way:

Let [itex]S_1, S_2, ...[/itex] be an enumeration of all definable sets of naturals. A set is definable if it has a formula [itex]\phi(x)[/itex] which is true when [itex]x[/itex] is in that set, and false otherwise. We can diagonalize in a different way:

Let [itex]S_{diag}[/itex] be the set of all [itex]n[/itex] such that there is no proof that [itex]n \in S_n[/itex].

Now, it turns out that [itex]S_{diag}[/itex] is actually a definable set. So there is some [itex]n[/itex] such that [itex]S_{diag} = S_n[/itex], since we enumerated all possible definable sets. So this is different from the Cantor case, were we proved there was no such [itex]n[/itex]. However, let's consider the question:

Is [itex]n \in S_{diag}[/itex]?

There are two possibilities: Either it is, or it isn't.

If [itex]n \in S_{diag}[/itex], then by the definition of [itex]S_{diag}[/itex], that means there is no proof of [itex]n \in S_n[/itex]. But since [itex]S_{diag} = S_n[/itex], that means there is no proof that [itex]n \in S_{diag}[/itex]. So it's a true but unprovable statement.

The other possibility is that [itex]n \notin S_{diag}[/itex]. Since [itex]n \in S_{diag}[/itex] if and only if there is no proof of [itex]n \in S_n[/itex], it follows that [itex]n \notin S_{diag}[/itex] if and only if there IS a proof of [itex]n \in S_n[/itex]. But since [itex]S_{diag} = S_n[/itex], that means that there is a proof that [itex]n \in S_{diag}[/itex]. That means that there is a proof of a false statement. That's only possible if your proof system is unsound (proves false statements).

Conclusion: If your proof system is sound (only proves true statements) then there is a true sentence that is not provable by it.

 

[Stoney Pete]

Okay, that's interesting... I'm trying to understand it. Some questions:

-When you write "n ∈ S_diag iff n ∉ S_n" does this mean for example that 2 ∈ S_diag iff 2 ∉ S₂? So the index n is intended to have the same value as the variable n?

-With the formula Φ(x) that defines a set I guess you mean the set's characteristic function f:N→{0, 1}. Is that correct?

 

[SSequence]

There are two 'versions' of first incompleteness theorem, so to speak. Roughly, they are:
(i)-- If a system S is sound then it is incomplete
(ii)-- If a system S is consistent then it is incomplete

The version(i) follows as a direct consequence of halting problem (or more generically, other unsolvable problems that would become solveable if version(i) were to be false). It doesn't use much knowledge that is specific to formal systems or fol I think. However, depending on point of view, it may not be considered that enlightening by some.

I think what is interesting is that apparently it might seem that inference rules of (first-order) logic are too powerful to not be able to prove at least all number-theory truths. So perhaps, in that light it is interesting to see that they aren't.

 

[stevendaryl]

Okay, that's interesting... I'm trying to understand it. Some questions:

-When you write "n ∈ S_diag iff n ∉ S_n" does this mean for example that 2 ∈ S_diag iff 2 ∉ S₂? So the index n is intended to have the same value as the variable n?

Yes.

-With the formula Φ(x) that defines a set I guess you mean the set's characteristic function f:N→{0, 1}. Is that correct?

Well, the language of arithmetic, there are no functions other than plus, times and successor, so no.

An example of using a formula to define a set is: [itex]S \equiv \exists y: y+y = x[/itex]. The formula [itex]S[/itex] has one free variable, [itex]x[/itex] ([itex]y[/itex] is not free, because it is bound by the existential quantifier, [itex]\exists[/itex]). [itex]S[/itex] defines the set of even natural numbers, in the sense that if you replace [itex]x[/itex] by a numeral [itex]n[/itex], you will get a true statement if and only if [itex]n[/itex] is even.

 

[stevendaryl]

There are two 'versions' of first incompleteness theorem, so to speak. Roughly, they are:
(i)-- If a system S is sound then it is incomplete
(ii)-- If a system S is consistent then it is incomplete

I would say that there are three versions:

1. If a system is sound, then it is incomplete.
2. If a system is consistent, then it cannot prove that it is consistent.
   
3. If a system is merely consistent, then it is incomplete.

1. and 2. are due to Godel, even though 1. is, as you say, implied by Turing's proof of the unsolvability of the Halting Problem. To get 2. from 1. is not easy starting with Turing's Halting problem. Godel's approach is the following:

1. Come up with a statement G such that G is true if and only if G is not provable.
2. If G is provable, then "G is provable" is provable. (That's true for any statement whatsoever, not just G)
3. By the way G is constructed, if G is provable, then "G is not provable" is provable.
4. Combining 2&3 gives us: If G is provable then a contradiction is provable (both "G is provable" and "G is not provable")
5. From 4, we get: If G is provable, then the system is inconsistent.
6. From 5, we get: If the system is consistent, then G is not provable.
7. From the construction of G, it follows that: If the system is consistent, then G is true.
8. By 7, if the system could prove its own consistency, then it could prove G.
9. By 5 and 7, if the system could prove its own consistency, then it would be inconsistent.
10. So no consistent system can prove its own consistency.

The final variant, 3., was not proved by Godel, but was proved by Rosser. It's conceivable, based on Godel's proofs, that a system could be complete and consistent but unsound. To be complete, every sentence must be either provable or disprovable. Since no system can prove its own consistency, it could only be complete and consistent if it proved that it was INconsistent. Rosser showed that this isn't actually possible: you can't have a complete consistent theory, either sound or unsound.

 

[Stoney Pete]

In Cantor's proof of the uncountability of the set of subsets of the naturals, you start with an assumed enumeration of sets of naturals:

[itex]S_1, S_2, S_3, ...[/itex]

Then you define a new set [itex]S_{diag}[/itex] according to the rule: [itex]n \in S_{diag} \Leftrightarrow n \notin S_n[/itex]

Obviously, [itex]S_{diag}[/itex] cannot be equal to [itex]S_n[/itex] for any value of [itex]n[/itex].

Let me see if I understand this correctly...

S_diag basically says about itself that it is not on the presumed list of subsets of ℕ. It does this because its definition refers to all sets on the list. Thus, assuming the enumerability of P(ℕ), S_diag also refers to itself. Assuming its place on the list is some number d, then S_diag = S_d. But S_diag is defined as {n I n ∉ S_n}. So we get a contradiction: d ∈ S_d iff d ∉ S_d. Hence P(ℕ) is indenumerable.

I see the connection with diagonalization in Cantor's proof, although S_diag does not literally trace out a diagonal on the list of S₁, S₂, S₃... So in that sense, speaking of a diagonal set is a little misleading, and I can see why I didn't understand it at first. But the net result is the same. Whether we diagonalize on, say, all binary strings and then 'flip' the n-th bit of the n-th string, or we define a set D such that n ∈ D iff n ∉ S_n -- the result in both cases is something (a binary string or a subset of ℕ) that is by definition not on the list...

I guess that defining D in the above way is, although not literally a diagonalization, sufficiently close to it to warrant an extended use of "diagonalization" such that we can say that D 'diagonalizes' out of the enumeration of subsets of ℕ.

Is all of this correct?

 

[SSequence]

I would say that there are three versions:

1. If a system is sound, then it is incomplete.
2. If a system is consistent, then it cannot prove that it is consistent.
   
3. If a system is merely consistent, then it is incomplete.

1. and 2. are due to Godel, even though 1. is, as you say, implied by Turing's proof of the unsolvability of the Halting Problem...

Halting problem does the job for the proof (in the sense of making the proof minimalist/easy), but it still doesn't fully reflect the disconnect. I mean, in the sense that the set of all number-theoretic truths isn't even an arithmetical set (and hence ofc not computable)***.

But the problem/contradiction is that if a given suitably described logical system (in context of godel's theorem) is sound and complete, then a simple program can calculate all the number-theoretic truths (hopefully I haven't misrepresented something important here).

This is ofc all very well-known and hardly anything new.

*** The proof would first require the equivalence of the "definition based on jumps" and "definition based on quantifiers" (the latter one I don't understand confidently). To be a little clearer, I mean that every set which is computable (using an oracle obtained after some maximum finite number of jumps) is also computable via a maximum finite number of quantifiers and vice versa (sorry for being a little too vague here ... I don't remember the quantifier stuff well ...).

I studied some of this stuff probably little over three years ago (but too many important things went well over my head at that time ... I haven't really been able to come back to any of that stuff to consolidate the understanding). At any rate, it seems that one direction of this equivalence should be somewhat trivial (jump definition containing quantifier definition). But the other direction of this equivalence isn't (but a theorem of Emil Post essentially verifies this direction I "think").

 

[SSequence]

To be a little clearer, I mean that every set which is computable (using an oracle obtained after some maximum finite number of jumps) is also computable via a maximum finite number of quantifiers and vice versa (sorry for being a little too vague here ... I don't remember the quantifier stuff well ...).

Since I can't edit the previous post, I would just hasten to add that some kind of distinction between "bounded" and "unbounded" quantifications might be quite important (and perhaps necessary) here. But since I already mentioned I don't remember most of the details, I will leave it here. The "second half" of my previous post is much more confusing than I would have liked (the actual point was covered in the "first half")... probably shouldn't have included it.

==================================