14
$\begingroup$

$\newcommand\Tr{\text{Tr}}$My question is whether there can be a nonstandard model of PA having a unique inductive truth predicate.

Background. If $\mathcal{N}=\langle N,+,\cdot,0,1,<\rangle$ is a model of the first-order PA axioms, then a truth predicate on $\mathcal{N}$, also commonly called a satisfaction class, is a predicate $\Tr\subset N$ obeying the recursive Tarskian truth conditions, that is:

  • (atomic) The $\Tr$ predicate holds of the Gödel code of an atomic formula just in case that atomic formula is true. For example, $\Tr(\underline n+\underline k=\underline r)\iff \mathcal{N}\models n+k=r$, and so on, where $\underline n$ means the term $\underbrace{1+1+\cdots+1}_n$.
  • (conjunction) $\Tr(\sigma\wedge\tau)$ holds if and only if $\Tr(\sigma)$ and $\Tr(\tau)$ both hold.
  • (negation) $\Tr(\neg\sigma)$ holds if and only if $\Tr(\sigma)$ does not hold.
  • (quantifiers) $\Tr(\exists x\varphi(x))$ holds if and only if there is some $n\in N$ such that $\Tr(\varphi(\underline n))$ holds.

Such a truth predicate is said to be inductive, if the model $\langle N,+,\cdot,0,1,<,\Tr\rangle$ expanded by that predicate satisfies induction in the expanded language.

For nonstandard models, the existence of an inductive truth predicate implies that the model is computably saturated, and a countable model is computably saturated if and only if there is an inductive partial truth predicate, one which is defined only on all sentences up to some nonstandard finite level of complexity. Thus, some nonstandard models of PA, the non-computably saturated ones, have no inductive truth predicate. Meanwhile, Krajewsky proved that there can be nonstandard models of PA having more than one distinct truth predicate.

I gave a talk yesterday for the NY Phil Logic Group in which such matters were an important part of the discussion, and Kit Fine asked a great question there:

Question. Can there be a nonstandard model of arithmetic having a unique inductive truth predicate?

The standard model $\mathbb{N}$, of course, has a unique truth predicate, since one can prove by induction that every such predicate must agree with actual arithmetic truth. But for countable nonstandard models, the answer is definitely no, it does not happen. The reason is that if a nonstandard countable model of PA has any inductive truth predicate at all, then it is computably saturated, and so the usual back-and-forth constructions show that the model will have many automorphisms, and furthermore many automorphisms that take true sentences to false ones and vice versa. This is simply because the truth predicate cannot be definable in the base language of arithmetic, and so there must be two elements of the model having the same types in the model in the language of arithmetic, but one is the Gödel code of a true sentence and the other the code of a false sentence. By constructing a tree of such automorphisms, one can get continuum many distinct truth predicates this way. (See also Kossak and Schmerl, Minimal Satisfaction Classes with an Application to Rigid Models of Peano Arithmetic, NDJFL 32(3), 1991.) This back-and-forth argument provides an alternative proof of Krajewsky's result.

But can there be an uncountable affirmative instance of the question? We know that there can be rigid $\omega_1$-like computably saturated models, and that kind of situation is suggestive that an affirmative instance may be possible.

$\endgroup$
2
  • 1
    $\begingroup$ In light of the nature of the proof given in my answer to the question, it is amusing to note that the existence of more than one inductive full satisfaction predicate on the same countable model of PA provides an interesting example of the fact that the union of two inductive expansions of the same model of PA need not be inductive. Of course one can also produce such examples with forcing, but here the expanisons are somehow more tangible, hence making the failure of induction more dramatic. $\endgroup$
    – Ali Enayat
    Nov 11, 2014 at 18:55
  • $\begingroup$ Yes, I agree. Any two truth predicates, in any context with induction able to consider them both, must agree. So different inductive truth predicates cannot satisfy induction in the joint language with both of them. $\endgroup$ Nov 11, 2014 at 19:10

1 Answer 1

13
$\begingroup$

The answer to the question is in the positive.

Let $(\cal{N}^*,\textrm{Tr*})$ be a rather classless elementary extension of $(\cal{N},\textrm{Tr})$, where $\cal{N}$ is a model of PA, and $\textrm{Tr}$ is a full truth predicate on $\cal{N}$, e.g., let $\cal{N}$ be the standard model of PA, and $\textrm{Tr}$ be the usual Tarskian truth predicate on $\cal{N}$.

In the above, "rather classless" means that $(\cal{N}^*,\textrm{Tr*})$ has the property that every subset $X$ of the universe $N^*$ of $\cal{N}^*$ that is piecewise coded in $\cal{N}^*$ is first order definable in $(\cal{N}^*,\textrm{Tr*})$, where $X$ is piecewise coded means that the intersection of $X$ with every topped initial segment of $\cal{N^*}$ is parametrically definable in $\cal{N^*}$ (indeed, it is coded by a single element). See Theorem 2.2.14 (and the preceding two paragraphs) of the Kossak-Schmerl monograph on models of PA for the relevant existence theorem for rather classless models. Such models exist in every uncountable cardinality $\kappa$ of uncountable cofinality and indeed can be arranged to be $\kappa$-like.

On the other hand, it is easy to see that every inductive set is piecewise coded. Therefore, if $\textrm{T}$ is an inductive truth predicate on $N^*$, then $\textrm{T}$ is piecewise coded and by rather classlessness it is definable in $(\cal{N}^*,\textrm{Tr*})$, and in particular the double-expansion $(\cal{N}^*,\textrm{Tr*}, \textrm{T})$ satisfies full induction.

Now, an easy induction carried out internally in $(\cal{N}^*,\textrm{Tr*}, \textrm{T})$ on the complexity of formulae shows that $\textrm{Tr*} = \textrm{T}$. QED

$\endgroup$
2
  • $\begingroup$ Great! I was hoping/expecting you to weigh in on this. $\endgroup$ Nov 11, 2014 at 17:20
  • $\begingroup$ I edited your link to point right at that page. $\endgroup$ Nov 11, 2014 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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