What's wrong with this "proof" that Gödel's first incompleteness theorem is wrong?

Question

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 1

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).

Answer 2

Taking this argument, refined by Henning Makholm's observation about quantifying it with ordinals, and combining it with the fact the conclusion of the the incompleteness theorem says you can't actually achieve your goal proves an interesting theorem:

Theorem: There are countable ordinal numbers that cannot be computed by Turing machine

I don't think I've encountered this before, but I found some references on this phenomenon. Here are wikipedia links:

• Recursive ordinal — those well-orderings that can be expressed by computable functions
• Churck-Kleene ordinal — the first nonrecursive ordinal. It is countable.
• Large countable ordinal — more stuff

In my opinion, what's going here in regard to computable functions is really the same phenomenon as uncountability is in set theory. Compare, for an infinite set $S$,

• "$S$ is recursively enumerable" means "there is a computable bijection $\mathbb{N} \to S$"
• "$S$ is countable" means "there exists a bijection $\mathbb{N} \to S$"

The only difference between the two notions is what kind of functions we allow: whether we draw functions from a universe of sets or merely from the universe of Turing machines.

In alternative language emphasizing this analogy, Gödel proves that every complete, consistent extension of PA is computably uncountable. The limitations of your argument are the fact that you can't reach the first computably uncountable ordinal $\omega_1^{CK}$.

Answer 3

Some belated comments on your self-written answer:

This is all more or less correct. There's a theory referred to as "True Arithmetic", which is the set of all sentences in the language of arithmetic which are true in "the intended model".⁽¹⁾ By definition, True Arithmetic is consistent and complete, so by the first incompleteness theorem it must not be recursively enumerable. It follows that, for any theory of arithmetic T which is recursively enumerable, the set of sentences of True Arithmetic that T cannot prove is itself not recursively enumerable, as you observed.

I do have a nitpick with one thing you wrote, though it's not essential to the reasoning:

By " in principle" I mean that if an oracle told us the next godel sentence of this enumeration every time we asked for it, we could, using this oracle, enumerate all the godel sentences in my construction, and thereby "bypass" the limitations implied by godel's theorem.

This is all fine,⁽²⁾ as long as we keep in mind that the "next" Gödel sentence in the enumeration will not correspond with with the "next" theory as ordered by the corresponding ordinals. We do not in fact need an oracle to tell us the next sentence in the latter sense: the oracle is needed to give a single uniform listing of all the Gödel sentences, but the order in which it produces that list cannot correspond with the ordering of the corresponding ordinals.

To illustrate this, recall that your original idea depended on (recursive) lists of ordinals going some way beyond the finite ones. Such lists do indeed exist, but the order of the list cannot correspond to the natural order of the ordinals, since otherwise we'd never get past the finite ones. For example, here's a recursive list of all ordinals below ω+ω (where ω is the first infinite ordinal): 0, ω, 1, ω+1, 2, ω+2, ...

⁽¹⁾ The reference to "the intended model" is needed in order to accommodate the following fact: for any recursively enumerable theory of arithmetic T, there are models of T, i.e. sets of "numbers" together with definitions of 0, 1, +, and · which satisfy the axioms of T, and which are not "the intended model" because e.g. a given Gödel sentence is false in those models. This fact is a result of applying Gödel's completeness theorem (not to be confused with his incompleteness theorems!) to the existence a Gödel sentence.

Technically, the well-definedness of "the intended model", and hence of True Arithmetic, depends on the assumption that all sentences in the language of arithmetic do in fact have a "correct" truth value - an assumption that most working mathematicians take for granted, but that some people interested in the foundations of mathematics reject or at least question: see for instance http://jdh.hamkins.org/question-for-the-math-oracle/

⁽²⁾ If by "bypassing Gödel's theorem" you mean that the list of axioms obtained at the end of this process should be complete, i.e. sufficient for deducing all sentences of True Arithmetic, you might need to be careful about not only which Gödel sentences you list, but what order you list them in: this is the subject of ordinal notations, which I've mostly avoided except to note that the Church-Kleene ordinal, which we're effectively using here, doesn't have a recursively enumerable one.

There is more detail on this in the answers to https://mathoverflow.net/questions/67214/pi1-sentence-independent-of-zf-zfconzf-zfconzfconzfconzf-etc - a question close in spirit to yours, though it uses ZFC instead of Peano arithmetic, and the second incompleteness theorem rather than the first.

Answer 4

Here is a condensation of my thoughts based on the other answers and comments.

This enumeration that I proposed can be compared with functions on the natural numbers: While there are a countable number of natural numbers, there are an uncountable number of functions from natural numbers to natural numbers. Since there are a countable number of Turing machines (since a TM must be described by a finite string), there must therefore be an uncountable number of functions from $N$ to $N$ that cannot be computed.

The same principle holds for the sequence of godel sentences that I formulated: This sequence of godel sentences "in principle" exists, and is countable, and could therefore "in principle" be made into to an enumerable set of axioms (combined with PA). By " in principle" I mean that if an oracle told us the next godel sentence of this enumeration every time we asked for it, we could, using this oracle, enumerate all the godel sentences in my construction, and thereby "bypass" the limitations implied by godel's theorem. However, we don't have an oracle, and have to use a TM to compute these godel sentences. And the problem is, that just as there are incomputable functions $f:N\to N$ due to uncountability of the space of such functions, there are also an uncountable number of orderings on the natural numbers, so that there will necessarily be countable ordinals whose enumeration in terms of natural numbers cannot be computed. In other words if we have a collection with order type equal to such an ordinal, we cannot compute the enumeration of the elements of this collection. (Even though the sentences in this set all consists of finite strings, and the set is countable)

Moreover, since Godel's theorem holds for any enumerable set of axioms, we could employ transfinite induction: Let $\alpha(\Phi)$ mean something like: "Either there is a godel sentence $G^\Phi$ for $\Phi$ (which is not implied by $\Phi$), or $\Phi$ is not recursively enumerable". We could use transfinite induction combined with godel's theorem to show that for any ordinal $\beta$, it must hold that $\alpha(\Phi_\beta)$.

But if $\Phi_\alpha$ is recursively enumerable, we can always add its godel sentence and those of all its successors to the next $\Phi_\gamma$, so if we continue with this process that I described, adding all the godel sentences together, then we must eventually reach a set $\Psi^*$ whose elements are no longer recursively enumerable. Moreover, if we let $\Psi=\Psi^* / PA$ (where $PA$ are the peano axioms), then $\Psi$ is also not recursively enumerable, yet this set contains only those godel sentences which we know from meta-logical analysis are true in standard arithmetic, but unprovable from $PA$.

Hence we can state the following extension of Godel's theorem:

Theorem. Let $\Phi$ be a recursively enumerable and consistent set of axioms containing the peano axioms. Then there exists a non-recursively enumerable and countably infinite set of sentences $\Psi$, such that for all $\psi\in \Psi$: Neither $\Phi \vdash \psi$, nor $\Phi \vdash \neg \psi$

This result (insofar as my informal proof sketch is correct) is much stronger than godel's theorem, and follows quite directly from godel's theorem.

Essentially it says: There are an infinite amount of sentences that are true in standard arithmetic, but we can never know which sentences they are, let alone prove them from a set of first-order axioms. (we can enumerate a subset of them, even an infinite subset, but there is also an infinite subset that we can never find).

EDIT: I think the theorem can be strengthened further: Note that the fact that there exist such a non-enumerable $\Psi$ may by itself not be that interesting, because in principle, it may be that if we take the list of all statements that are true but not provable from $PA$, that this list is suddenly enumerable. ($\Psi$ is a subset of this set, and if a subset is not enumerable, it may still be that the superset is enumerable). But this cannot be the case: Assume that the set $\Omega$ of sentences that are true but unprovable from $PA$ are enumerable. Then we can create a new set $\Phi_\Omega=PA \cup \Omega$, which is enumerable. But then by godel's theorem there exists a godel sentence $G^{\Phi_\Omega}$ such that it, and its negation, are not provable from $\Phi_\Omega=PA \cup \Omega$, but it is still true. But then by the definition of $\Omega$, we have $G^{\Phi_\Omega}\in \Omega$, so that $\Omega \vdash G^{\Phi_\Omega}$. This is a contradiction. Therefore, $\Omega$ cannot be enumerable.

Theorem. Let $\Phi$ be a recursively enumerable and consistent set of axioms containing the peano axioms. Then the set of sentences $\Omega=\{\psi : \text { neither } \Phi \vdash \psi \text{ nor } \Phi \vdash \neg \psi\}$ is countably infinite and not recursively-enumerable.