17
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Related: math.stackexchange.com/questions/1703489/… $\endgroup$ – Henning Makholm Apr 1 '18 at 10:54
  • 1
    $\begingroup$ Please, pay attention to this: when you say "the proof of Gödel's theorem is as follows: For any decidable and consistent set of axioms Φ that contain (or imply) the first order Peano's axioms..." you are omitting the fact that actually Godel's first incompleteness theorem hold for every semidecidable (which is more general than decidable) and consistent set of first-order axioms that imply Peano axioms. $\endgroup$ – Taroccoesbrocco Apr 1 '18 at 11:10
  • $\begingroup$ @CarlMummert - Do you refer to Craig's theorem? I had forgotten it, thank you fro the reminder. Sorry for my worthless comment. $\endgroup$ – Taroccoesbrocco Apr 1 '18 at 22:01
  • $\begingroup$ Yes, that is the theorem. Your comment was something that seems like it should be right, so many people have thought it was right over time. The key point, of course, is that we can move to a different set of axioms for the same theory. $\endgroup$ – Carl Mummert Apr 1 '18 at 22:10
  • $\begingroup$ Cool, I didn't know that had a name. Though I'll probably have forgotten the name the next time I need to refer to the result ,,, $\endgroup$ – Henning Makholm Apr 2 '18 at 11:42
24
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I think you misunderstood the OP regarding the second problem. I think the claim was: the set is countable (as a subset of a countable set), hence it can be enumerated. [The definition of can be enumerated probably shifted during the argument.] $\endgroup$ – Carsten S Apr 1 '18 at 14:31
  • $\begingroup$ @CarstenS, yes indeed, my point was that the set of godel sentences is countable, and can therefore be enumerated. I made this point because the set of possible sets of sentences is not countable, and hence one might think that since each such set has a godel sentence, the set of godel sentences is not countable either. I made the point that this is obvioiusly a wrong conclusion, and that instead the set of godel sentences is countable, and can therefore potentially be enumerated. $\endgroup$ – user56834 Apr 1 '18 at 15:31
  • 2
    $\begingroup$ A question about your point: "And there is (vividly speaking, but can be made precise) so far to infinity that ..." Could you specify what you mean by "far to infinity"? I assume you don't mean that they are uncountable? Also, could you elaborate (at least informally) why the combined theory is not recursively axiomatized anymore? And why there are not enough turing machines to "describe" these theories? What exactly does "describe" mean here? Represent them in natural numbers? Intuitively it seems to me that the process I described already gives a blueprint for such turing machines. $\endgroup$ – user56834 Apr 1 '18 at 15:36
  • $\begingroup$ @Programmer2134, Hurkyl's answer addresses your latest questions. The idea is that, as Henning said, if you want to formalize the notion of "going to infinity and then continuing", your theories need to correspond to ordinals (to actually enumerate the axioms, you'll want ordinal notations, but the idea is the same without worrying about that). But whatever ordinal you use for your "final" theory, there's always a bigger ordinal that you haven't used, for the same reason that there's no biggest integer; and your theory will be missing the corresponding axiom. $\endgroup$ – Robin Saunders Apr 2 '18 at 1:19
  • $\begingroup$ There is a limit to how large ordinals can get whilst still possessing a notation, i.e. a way to use that ordinal to computably enumerate axioms (or anything else). The smallest ordinal that has no notation is the Church-Kleene ordinal mentioned by Hurkyl. But there's no largest ordinal that does have a notation, because "take the next ordinal instead" is a computable operation on ordinal notations. $\endgroup$ – Robin Saunders Apr 2 '18 at 1:22
7
$\begingroup$

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:

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}$.

$\endgroup$
  • 3
    $\begingroup$ In particular, each of the Gödel sentences constructed along the way refers to a particular theory, which itself refers to a particular well ordered set of previous theories. So a "possible Gödel sentence" would include an ordinal notation for some countable ordinal $\eta$ and a sequence of theories $T_\alpha : \alpha < \eta$. This is why we can't enumerate "all possible" Gödel sentences, because every particular r.e. ordinal notation system is bounded strictly below $\omega_1^{CK}$. This is the relevant Wikipedia article: Ordinal notation $\endgroup$ – Carl Mummert Apr 1 '18 at 21:31
  • 1
    $\begingroup$ (Actually, that article is pretty incomprehensible, but it should be the relevant article, in a perfect world.) $\endgroup$ – Carl Mummert Apr 1 '18 at 21:35
  • 1
    $\begingroup$ @Programmer2134: An ordinal is computable if there is a program that decides a subset of $\mathbb N\times\mathbb N$ such that this subset is an order relation and $\mathbb N$ with this order is order-isomorphic to the ordinal we're talking about. $\endgroup$ – Henning Makholm Apr 2 '18 at 11:23
  • 1
    $\begingroup$ @Programmer2134: Recursively enumerable is a standard concept in computability theory. I don't think there's a wide consensus whether "enumerable" should mean "countable" or "recursively enumerable", so people generally just use the two latter terms instead. $\endgroup$ – Henning Makholm Apr 2 '18 at 11:33
  • 3
    $\begingroup$ @Programmer2134: Just because the mapping exists doesn't mean that the mapping is computable, which is what is needed here. (Your argument here sounds like it would also prove that every infinite subset of $\mathbb N$ is computable, which we know is not the case). $\endgroup$ – Henning Makholm Apr 2 '18 at 12:00
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm not sure quite how Stack Exchange's notification system is set up, so just in case: I've posted a response to this in a separate answer. Hope it helps! $\endgroup$ – Robin Saunders Apr 4 '18 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.