Edit: I've added an answer myself, based on the other answers and comments.
Here is a very very informal "proof" (sketch) that Gödel's theorem is wrong (or at least that the idea of the proof is wrong) :
Roughly, the proof of Gödel's theorem is as follows: For any decidable and consistent set of axioms $\Phi$ that contain (or imply) the first order Peano's axioms in first order language, we can construct a Gödel sentence $G^\Phi$, such that neither $\Phi\vdash G^\Phi$ nor $\Phi\vdash \neg G^\Phi$, but where we know from an argument in the meta-language that $G^\Phi$ is true. For any such $\Phi$, we will therefore have a counterexample to the completeness of the theory $Th(\Phi)$. Therefore we know that no such $\Phi$ can be complete (where complete means that all first order statements can be proven or disproven from it).
Here is a failed proposal to "circumvent" Gödel's theorem that I have already heard someone make: Just define $\Phi_1=\Phi\cup \{G^\Phi\}$, and since we know that $G^\Phi$ is true in arithmetic, we know that $\Phi_1$ is consistent. The problem of course is: We can now formulate a new Gödel sentence $G^{\Phi_1}$, which cannot be proven from in $\Phi_1$, even though it is true in standard arithmetic.
Now here is my proposal:
Rather than trying to add individual Gödel sentences to the set of axioms, we simply take the enumeration procedure, such that it enumerates $\phi_i \in \Phi$ for the original set of axioms $\Phi$, and also enumerates all successive Gödel sentences $G^{\Phi}, G^{\Phi_1}, G^{\Phi_2},...$. This is possible, since $\Phi$ is decidable, and decidable sets of finite strings are enumerable, so we can enumerate them successively, as $\phi_1, \phi_2, \phi_3$, where $\phi_1$ is the first statement of the enumeration of $\Phi$, and $\phi_2 = G^\Phi$, and $\phi_3$ is the second statement of the enumeration of $\Phi$, etc...
We can then define the set of axioms $\Phi_\infty = \{\phi_1, \phi_2, ...\}$. This will also have a Gödel sentence $G^{\Phi_\infty}$. But what we can simply do, is add this to the enumeration procedure as well. And then the next one, and the next, and so forth. We take this process to infinity, just as we did for $\Phi$, and just keep going.
Every time a Gödel sentence pops up, we simply add it to the enumeration. Now note that: since the set of first order sentences is countable, the set of Gödel sentences is countable as well (since it is a subset of the set of first order sentences). Therefore we can in this procedure described above enumerate all possible Gödel sentences.
The resulting set of sentences forms an enumerable and consistent set of sentences $\Psi$ that contains the original $\Phi$, and additionally
contains the Gödel sentences of all possible sets of axioms $\Phi_x$. Therefore The Gödel sentence of $\Psi$ must be in $\Psi$ itself.
Moreover, we can then create a "decidable version" of $\Psi$, by defining $\Psi^*=\{\psi_1, \psi_1 \land \psi_2, \psi_1 \land \psi_2\land \psi_3, ... \}$, for all $\psi_1, \psi_2,... \in \Psi$. We therefore have a consistent and decidable set of first order sentences that are true in standard arithmetic, contain Peano's axioms, and bypass Gödel's proof of incompleteness.
This is obviously a contradiction with Gödel's theorem. So where is my "proof sketch" wrong?
Answer
There are at least two problems here.
First, when you say "we take this process to infinity and just keep going", that is a very informal description, and without spending some work on making it more concrete you have no good reason to expect it can actually be made to work.
Fortunately, such work has in fact been done, and the standard way of making it concrete is to speak about process steps indexed by transfinite ordinal numbers, which I'm going to suppose is what you are proposing.
Then, however, a real problem arises: Gödel's procedure only works when the original theory is recursively axiomatized, that is, it is computable whether a given proposed sentence is one of its axioms or not. In order to do this for one of your intermediate theories, you need to be able to algorithmically describe the process that produced the theory. And there is (vividly speaking, but can be made precise) so far to infinity that there are not enough Turing machines to describe the structure of each of the theories you encounter along the way. So at some point you're going to approach a point where the process that produced the axioms you already have is so complex that the combined theory is not recursively axiomatized anymore, and then the incompleteness theorem stops working.
A second, comparatively minor, problem comes later in your argument:
since the set of first order sentences is countable, the set of Gödel sentences is countable as well (since it is a subset of the set of first order sentences). Therefore we can in this procedure described above enumerate all possible Gödel sentences.
This argument seems to be the form: "There are a countable infinity of foos in total; here we have a set of countably-infinite many foo; therefore the set contains all of them", which is not valid -- consider e.g. the situation where a "foo" is a natural number and the set in question contains all the perfect squares.
(Note also that you don't seem to have defined what a "possible Gödel sentence" means, which you really ought to do before claiming that you have all of them).
No comments:
Post a Comment