- #1
Stoney Pete
- 49
- 1
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.
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.