0
$\begingroup$

This continues my question here.

I think the following versions of Gödel's incompleteness theorems must be true, but I can't find references. I would be happy if specialists could help.

To give accurate formulations I need the following definition which is a modification of Shoenfield's construction of interpretation of a theory in another theory [Shoenfield, 4.7].

Let $S$ and $T$ be formal theories over the predicate logic. Let us say that $S$ has an interpretation in $T$, if

  • the alphabet of $T$ contains the alphabet of $S$,

  • to each propositional symbol $p$ in the signature of $S$ we assigned an extended propositional symbol $p'$ (of the same arity) in $T$ in the sense of [Kunen,II.15.1]

  • to each functional symbol $f$ in the signature of $S$ we assigned an extended functional symbol $f'$ (of the same arity) in $T$, again in the sense of [Kunen,II.15.1]

  • in the arising correspondence between formulas $\varphi\mapsto\varphi'$ each axiom $\varphi$ in $S$ turns into a theorem $\varphi'$ in the theory $S'$ that appears as an extension by definitions of $T$.

The versions of Gödel's theorems I am interested in are the following:

Theorem 1. Suppose $T$ is a consistent theory where the Peano arithmetic has an interpretation. Then $T$ is incomplete.

Theorem 2. Suppose $T$ is a consistent theory where the Peano arithmetic has an interpretation. Then the proposition that $T$ is consistent is not deducible in $T$.

Questions:

  1. Is this correct?

  2. If yes, where is it written?

  3. If no, then perhaps it is possible to modify the formulations so that they become true?

$\endgroup$
  • 2
    $\begingroup$ The first version is certainly false. You need some limitations on recursive enumerability. Otherwise take the theory of any model of PA. $\endgroup$ – Asaf Karagila Jun 11 '17 at 11:00
  • $\begingroup$ Asaf, I don't understand. Suppose I take a model in ZFC, what is wrong with it? $\endgroup$ – Sergei Akbarov Jun 11 '17 at 11:31
  • $\begingroup$ You can also take PA itself. An example is not a proof... $\endgroup$ – Asaf Karagila Jun 11 '17 at 11:32
  • 1
    $\begingroup$ I did give a counterexample. $\endgroup$ – Asaf Karagila Jun 11 '17 at 11:34
  • 1
    $\begingroup$ See Godel's Incompleteness Th : "one must first explain the key concepts essential to it, such as “formal system”, “consistency”, and “completeness”. Roughly, a formal system is a system of axioms equipped with rules of inference, which allow one to generate new theorems. The set of axioms is required to be finite or at least decidable, i.e., there must be an algorithm (an effective method) which enables one to mechanically decide whether a given statement is an axiom or not." ... $\endgroup$ – Mauro ALLEGRANZA Jun 11 '17 at 15:30
4
$\begingroup$

This is an expansion on Asaf's answer. I am at this point rather confused about the OP's specific point of confusion, so I'll frame this answer in a purely formalist manner: the following argument is naturally expressible in the language of, and provable from, ZFC. If the OP doubts this, please point to a specific concern.


Suppose $M$ is a structure - that is, a set together with some functions, relations, and constants on that set named by symbols in some language $\Sigma$. Then associated to $M$ is the theory of $M$ - the set $$Th(M)=\{\varphi\in Sentence(\Sigma): M\models\varphi\}$$ of sentences true in $M$. This is a complete theory, since for every sentence $\varphi$ we have $M\models\varphi$ or $M\models\neg\varphi$.

Note that this is a fundamental difference between structures and theories: for a theory $T$, of course we need not have $T\models\varphi$ or $T\models\neg\varphi$ for all sentences $\varphi$.

Now if $M$ is a complicated enough structure - say, $M=(\mathbb{N}; +, \times)$ - then $Th(M)$ will interpret (say) PA. Note that I'm speaking of an interpretation of one theory in another theory, not about a structure in a theory, a theory in a structure, or a structure in a structure; there are many kinds of interpretation, and this is why in my opinion it's unhelpful most of the time to think of models as a kind of interpretation. So I'll keep using the word "structure" to talk about an individual, well, "structure."

So your formulation of Goedel's incompleteness theorem is wrong: for certain structures $M$, the theory $Th(M)$ is a complete theory which interprets PA.

Examining the proof of Goedel's incompleteness theorem in detail (which one should always do when one is interested in generalizing something), we see that the crucial facts about PA (or whatever theory we're applying it to) are:

  • PA-provability is definable, and

  • basic facts about PA-provability are provable inside PA.

This winds up meaning that the theory has to be recursively axiomatized. The following is a true statement:

If $T$ is a recursively axiomatized theory which interprets PA, then either $T$ is incomplete or $T$ is inconsistent.

(Technically you need a twist on Goedel's argument to conclude this, provided by Rosser; Goedel's original argument had an additional "correctness" assumption on $T$, namely $\omega$-consistency.)

A similar point holds for the second incompleteness theorem.

$\endgroup$
  • $\begingroup$ Noah, as far as I understand, my statements will be true if I replace there "Suppose $T$ is a recursively axiomatizable consistent theory" instead of "Suppose $T$ is a consistent theory", right? $\endgroup$ – Sergei Akbarov Jun 11 '17 at 20:13
  • $\begingroup$ @SergeiAkbarov Yes, that's correct (and is basically what I said in the bolded part at the end of my answer). $\endgroup$ – Noah Schweber Jun 11 '17 at 20:15
  • $\begingroup$ Oh! That is fine! This is indeed helpful! Thank you! $\endgroup$ – Sergei Akbarov Jun 11 '17 at 20:16
  • 2
    $\begingroup$ I don't have the text on hand, though, so I can't comment specifically. Here's a quick test to tell if a theory is recursively axiomatized: can you tell whether a given sentence is an axiom of the theory? If so, it's recursively axiomatized. For instance, PA has an infinite collection of induction axioms; however I can easily recognize whether a sentence is one of these since the induction axioms are exactly those of a certain easily-recognizable form. Similarly with the replacement and separation schemes of ZFC. Meanwhile every finitely axiomatized theory is of course recursively axiomatized. $\endgroup$ – Noah Schweber Jun 11 '17 at 20:51
  • 1
    $\begingroup$ And again, I'll reiterate: there's nothing weirder about the theorem "The theory of a structure exists and is complete, regardless of the structure," ontologically speaking, than about the theorem "Every commutative ring which is not a field has a nontrivial proper ideal" - for a formalist, both of them have to be preceded by a phrase like "ZFC proves that ...". If you're e.g. comfortable informally thinking of rings as actual objects in order to understand theorems about them, that same comfort applies here; if not, you'll be equally uncomfortable with almost all mathematics. $\endgroup$ – Noah Schweber Jun 12 '17 at 18:45

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.