# The set of Godel numbers of true sentences.

Tarski's Theorem on the undefinability of truth gives me a bit of a headache, and as a beginner I am still trying to grapple with its consequences. Here's a question.

Let $T$ be the set of Godel numbers of sentences $\sigma$ such that $V \models \sigma$.

Now, I know that by Tarski's theorem, there is no formula that defines $T$ - that is to say, there is no first order formula $\tau (x)$ such that for each $n$, $n \in T \leftrightarrow V \models \tau (n)$.

I can live with that, because obviously some sets are not definable. (Indeed, most are not definable.) But must $T$ exist somewhere in $V$, even if it not definable? The argument is not so obvious to me. Or will this depend on background assumptions? (Whether $V=L$, or whether this or that large cardinal exists, and so on ...)

-
Regarding your claim that "most [sets] are not definable", see mathoverflow.net/questions/44102/…, as well as de.arxiv.org/abs/1105.4597. –  Joel David Hamkins Aug 15 '12 at 15:03

$\let\eq\leftrightarrow\def\god#1{\ulcorner#1\urcorner}$The question as such is not formally precise. The existence of a truth set is not expressible in the language of ZFC, so one cannot assert it from inside $V$, only from outside. My reading of the question is as follows. Let $\mathcal M=(M,E)$ be a model of ZFC, and $T^\mathcal M$ be the set of Gödel numbers of all sentences true in $\mathcal M$. Under which conditions does $\mathcal M$ contain $T^\mathcal M$, in the sense that there exists $t\in M$ such that $\{x\in M:(x,t)\in E\}=\{n^\mathcal M:n\in T\}$? I will write this as $\mathcal M\models T\in V$.

If $T^\mathcal M$ is in $\mathcal M$, then so is the set $\{n:\mathcal M\models n\in\omega\land\exists a\in T^\mathcal M\\,n\le a\}$, i.e., the standard natural numbers. Thus, this can happen only if $\mathcal M$ has standard integers (i.e., it is an $\omega$-model).

In particular, every model of set theory has an elementary extension which satisfies $T\notin V$, so you cannot guarantee the existence of $T$ by any first-order axioms.

On the other hand, models of $T\in V$ do exist: for example, if $\kappa$ is an inaccessible cardinal, then $V_\kappa$ contains the set of all sentences true in itself (as it contains every set of integers).

However:

Proposition. If an extension $S$ of ZFC has an $\omega$-model at all, then it also has an $\omega$-model satisfying $T\notin V$.

Proof: We may assume that $S$ is a complete theory, hence it is the theory of an $\omega$-model $\mathcal M_0$. We need to show that there exists a model of $S$ which omits the types \begin{align*} p(t)&=\{\phi\eq\god\phi\in t:\phi\text{ a sentence}\},\\\\ q(x)&=\{x\in\omega\}\cup\{x\ne n:n\in\omega\}. \end{align*} By the omitting types theorem, it suffices to verify that neither type has a generator. If $q$ had a generator $\alpha(x)$, then $S$ proves $\alpha(x)\to x\in\omega$ and $\alpha(x)\to x\ne n$ for every natural number $n$, hence $\mathcal M_0\models\forall x\\,\neg\alpha(x)$. Since $S$ is complete, $\alpha$ is inconsistent with $S$, and thus cannot be a generator.

If $p$ had a generator $\alpha(t)$, then $S$ proves $$\tag{\*}\alpha(t)\to(\phi\eq\god\phi\in t)$$ for every sentence $\phi$. Using self-reference, let $\phi$ be a sentence such that ZFC proves $$\phi\eq\exists t\\,(\alpha(t)\land\god\phi\notin t).$$ Then it is easy to see that $(\*)$ leads to $S\vdash\forall t\\,\neg\alpha(t)$, hence $\alpha$ is no generator. QED

François Dorais suggested in the comments that a more relaxed reading of $\mathcal M\models T\in V$ could be that there is $t\in M$ such that $T^\mathcal M=\{n\in\omega:\mathcal M\models n\in t\}$. In other words, $\mathcal M$ satisfies $T\in V$ iff it realizes the type $p$ above. Under this reading, every consistent extension $S$ of ZFC has a model which satisfies $T\in V$, but is not an $\omega$-model (and moreover, every recursively saturated model of ZFC has this property). On the other hand, the same omitting types argument as above shows that every such $S$ also has a model which satisfies $T\notin V$.

-
Nice! Here's a followup: Can $T$ fail to exist in a model with only standard natural numbers (i.e., with no non-standard natural numbers?) –  neophyte neologican Aug 14 '12 at 16:03
@Trevor: Right, the question is imprecise. The existence of a truth set is not expressible in the language of ZFC, so one cannot assert it from inside $V$, only from outside. My reading of the question was as follows. Let $\mathcal M=(M,E)$ be a model of ZFC, and $T^\mathcal M$ be the set of Gödel numbers of all sentences true in $\mathcal M$. Under which conditions does $\mathcal M$ contain $T^\mathcal M$, in the sense that there exists $t\in M$ such that $\{x\in M:(x,t)\in E\}=\{n^\mathcal M:n\in T\}$? –  Emil Jeřábek Aug 14 '12 at 17:38
Another way to avoid the nonstandard integers problem is to ask whether one can find a $T$ in $V$ that realizes the partial type $\{\ulcorner\sigma\urcorner \in T : V \vDash \sigma\}\cup\{\ulcorner\sigma\urcorner \notin T : V \vDash \lnot\sigma\}$. In other words, $T$ can say whatever about nonstandard integers but it has to say the right thing about standard integers. (Again, this only makes sense if we look at $V$ from outside.) –  François G. Dorais Aug 14 '12 at 18:45
@François: This is also sensible, and it leads to a quite different answer: writing the type as $\{\sigma\leftrightarrow(\ulcorner\sigma\urcorner\in T):\sigma\text{ a sentence}\}$ makes it clear that the answer is positive for any recursively saturated model of ZFC. –  Emil Jeřábek Aug 14 '12 at 18:52
Nice proof (in the edit). I have a terminological quibble, though: I think "standard model" in the context of set theory usually means well-founded (maybe even transitive, i.e., already collapsed). If just the natural numbers are standard, I'd call it an $\omega$-model or and $\omega$-standard model. –  Andreas Blass Aug 15 '12 at 14:44

I understood the question Platonistically, with $V$ meaning the real universe of all sets. On this understanding, the answer is yes, $T$ is a set and $V$ contains it. That fact, however, is not provable in ZFC; indeed, it cannot even be formulated in ZFC, because ZFC lacks the means to say what should be in $T$ (by Tarski's theorem). In order to formalize the question in set theory, I'd want to add to ZFC a satisfaction predicate (for formulas in the $\in$-language of ZFC) and axioms saying that it behaves correctly with respect to the syntactic construction of formulas. I would then be strongly tempted to also add all instances of the replacement schema that can be formed using the satisfaction predicate (in addition to the language of ZFC). With that addition, I could prove my affirmative answer to the original question.

If one interprets $V$ as not meaning the Platonic real world but rather some arbitrary model of ZFC, then Emil has correctly explained the situation.

What if one interprets $V$ as a model, containing nonstandard integers, of my proposed theory "ZFC plus satisfaction predicate plus replacement for formulas that use satisfaction"? Then Emil said (correctly) that this model won't contain its truth set, because that set contains infinitely many standard natural numbers and no non-standard ones. I said that my proposed theory proves "the truth set exists", so it would seem that the model should contain its truth set. Fortunately, there is no contradiction here. When "the truth set exists" is interpreted in such a model, "the truth set" refers to the set of all those natural numbers of the model (including nonstandard ones) that code sentences and make the satisfaction predicate true. That set is in the model; its subset of standard elements, the "genuine" truth set, is not. (An analogous explanation applies to Trevor's comment about the set of codes of arbitrary sentences being or not being in the model.)

-

Allow me to complement the other answers by mentioning that Kelly Morse set theory KM proves the existence of a satisfaction predicate for first-order set-theoretic truth, and consequently in Kelly-Morse set theory you can prove the existence of your truth sets as desired.

A satisfaction predicate is a class $T$ of pairs $\langle \varphi,a\rangle$, which obeys the following Tarskian conditions:

• (atomic truth) $T$ contains $\langle \varphi,\vec a\rangle$ for atomic $\varphi$ just in case $\varphi(\vec a)$ holds.
• (Boolean combinations) $T$ contains $\langle \varphi\wedge\psi,\vec a\rangle$ just in case it also contains $\langle \varphi,\vec a\rangle$ and $\langle \psi,\vec a\rangle$, and similarly, it contains $\langle \neg\varphi,\vec a\rangle$ just in case it doesn't contain $\langle \varphi,\vec a\rangle$.
• (quantifiers) $T$ contains $\langle \exists x\varphi,\vec a\rangle$ if and only if there is some $b$ such that $T$ contains $\langle\varphi,(b,\vec a)\rangle$, where we place $b$ in the right position to be interpreted by variable $x$.

A partial satisfaction predicate, in contrast, satisfies these requirements for all formulas up to a specified syntactic complexity. It is not difficult to prove that if $T$ is a partial satisfaction class for $\Sigma_n$ formulas, then one may define from it a partial satisfaction class for $\Sigma_{n+1}$ formulas, simply by applying one more step of the inductive definition of truth. Furthermore, one may prove by induction that if there is a partial satisfaction class for $\Sigma_n$ formulas, then it is unique.

It follows from those observations that one may prove in KM by induction on the natural numbers that for every natural number $n$ there is a partial satisfaction class for $\Sigma_n$ formulas, and furthermore, that these partial satisfaction classes agree with each other, cohering into a full satisfaction class $T$ that works with all formulas.

In particular, in Kelly-Morse, you have your desired truth sets about first-order truth.

(Note that the induction that partial satisfaction classes exist is a second order claim, and although it can be proved by induction in KM, this part of the argument cannot be carried out in ZFC.)

-
However, KM cannot define truth of all sentences in its language, as in Tarski’s theorem. –  Emil Jeřábek Aug 15 '12 at 17:41
Yes, the situation for second-order sentences would be much the same as you explained for ZFC. –  Joel David Hamkins Aug 15 '12 at 17:46
Nevertheless, for any fixed class, as in Goedel-Bernays set theory, the theory KM can prove the existence of a (unique) satisfaction class for first-order assertions in the language of set theory augmented by a predicate for that class parameter. So in KM we may definably and uniformly refer to first-order truth with any finite number of class parameters. –  Joel David Hamkins Aug 15 '12 at 17:49