8
$\begingroup$

In this blog post J.D.Hamkins shows that KM set theory can define truth predicate for first-order set theory, which means, I believe, that there is a second-order definition of such predicate and KM shows that it is indeed what we want it to be.

Author claims that it's easy to define partial truth predicates for all $\Sigma_n$, but it's in no way clear to me how such construction would work in ZFC. Even then, to define full truth predicate, we need a way of defining these predicates in second order language with uniform complexity, so that we can then combine them.

I tried looking for such constructions, however I wasn't really successful. My question is then:

How do we define full truth predicate in second order set theory?

I have tried to define such predicate by using a class of witnesses when adding existential quantifiers and similar construction for existential ones, but I didn't manage to make it work.

$\endgroup$
  • $\begingroup$ Are you asking how to define $\Sigma_n$-truth predicate in $\sf ZFC$ or how to define full truth predicate in $\sf KM$? The second answer follows trivially from the first. $\endgroup$ – Asaf Karagila Sep 21 '14 at 18:11
  • $\begingroup$ My main question is about full truth predicate in KM. I'll edit a question. $\endgroup$ – Wojowu Sep 21 '14 at 18:18
  • $\begingroup$ Joel explains the idea behind this construction in the post. Which part baffles you, exactly? $\endgroup$ – Asaf Karagila Sep 21 '14 at 18:38
  • $\begingroup$ I don't really see how we can determine a truth predicate when adding a quantifier. If it's existential quantifier, then I guess we can just find its witness, but how does one make this work for universal quantifiers? My only idea was to separate universe into witnesses and non-witnesses, but I believe that would require higher order of logic. $\endgroup$ – Wojowu Sep 21 '14 at 18:54
  • $\begingroup$ $\forall x\varphi$ is true if and only if $\exists x\lnot\varphi$ is false. If you know that $\exists x\lnot\varphi$ is true, then you know $\forall x\varphi$ is false, and vice versa. $\endgroup$ – Asaf Karagila Sep 21 '14 at 18:57
5
$\begingroup$

Let's say that a formula $\Phi(x, y)$ is a satisfaction predicate for $\mathcal L_\in$ if is satisfies the Tarski clauses; that is, if:

($\in$) $\Phi(``x_i\in x_j", a) \leftrightarrow a(i)\in a(j)$

($=$) $\Phi(``x_i = x_j", a) \leftrightarrow a(i) = a(j)$

($\wedge$) $\Phi(``\phi \wedge \psi", a) \leftrightarrow \Phi(``\phi", a) \wedge \Phi(``\psi", a)$

($\neg$) $\Phi(``\neg\phi", a)\leftrightarrow \neg\Phi(``\phi", a)$

($\exists$) $\Phi(``\exists x_i\phi", a)\leftrightarrow \exists a'=_{i} a\Phi(``\phi", a')$

where $\phi,\psi\in\mathcal L_\in$, $a$ is a function with domain $\omega$, and $a=_{i} a'$ means that $a$ and $a'$ agree except possibly at $i$. We assume that $\Phi(x, y)$ only applies to formula/assignment pairs.

Then we want to show that there is such a predicate in second-order set theory. I like to do this in two steps. First, I define $X$ to be a satisfaction class for $\phi\in\mathcal L_\in$ if $X$ satisfies the Tarski clauses for subformulas of $\phi$ and I prove by induction that any two satisfaction classes for $\phi$ are co-extensive. Second, I prove by induction that every formula in $\mathcal L_\in$ has a satisfaction class. One can then conclude that $\Phi(x, y) =$ "there is a satisfaction class $X$ for $x$ such that $\langle x, y\rangle\in X$" is a satisfaction predicate for $\mathcal L_\in$.

Here's how the second induction goes for the $\exists$ case. Suppose that $X$ is a satisfaction class for $\phi$. Now by predicative comprehension, we define $Y = X \cup \{\langle ``\exists x_i\phi", a\rangle: \exists a'=_{i} a(\langle ``\phi",a'\rangle\in X)\}$. Since $X$ is a satisfaction class for $\phi$, it is easy to see that $Y$ is a satisfaction class for $\exists x_i\phi$, as required.

(It might be interesting to note that this argument doesn't require the full power of MK. In particular, it only uses predicative instances of comprehension. What it requires beyond NBG is separation for $\Sigma^1_1$ formulas (in order to run the inductions in the two steps). But this is an assumption about the sets, not about the classes. In other words, the argument will go through even if you think there are relatively few classes, so long as you think that sets satisfy separation for $\Sigma^1_1$ formulas.)

$\endgroup$
  • 1
    $\begingroup$ Seems like a theme for your set theory answers today, eh? :-P $\endgroup$ – Asaf Karagila Sep 21 '14 at 22:28
  • $\begingroup$ You have also to prove that all satisfaction classes agree---in other words, that there is a unique satisfaction class up to that complexity---and this can also be done by induction. This is a subtle point, because for example there can be models of ZFC (in an expanded language with a predicate symbol for truth) that admit two different truth predicates. Of course, they all agree with actual truth on standard-length formulas, since one can carry out the induction in the meta-theory. Some of those weird models are discussed in my paper jdh.hamkins.org/satisfaction-is-not-absolute. $\endgroup$ – JDH Sep 22 '14 at 2:19
  • $\begingroup$ @JDH I did mention that - I said "First, I define...and I prove by induction that any two satisfaction classes for $\phi$ are co-extensive". But it's cool to see why this ${\it has}$ to be done. Thanks for the reference! $\endgroup$ – GME Sep 22 '14 at 7:44
  • $\begingroup$ Oh, indeed you had mentioned it; I just missed it, sorry to complain! $\endgroup$ – JDH Sep 22 '14 at 11:20
  • $\begingroup$ @JDH No worries! $\endgroup$ – GME Sep 22 '14 at 11:30

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.