Versions of Gödel's incompleteness theorems

Question

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?

Answer 1

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.