## 116c- Lecture 16

May 24, 2008

We showed that $\Delta_1$ formulas are absolute among transitive models of (enough) set theory, and used this to prove that satisfiability for transitive sets is absolute. More precisely, let $\mathrm{Sat}(a,b,c)$ mean that $a$ is a transitive set $M$, $b$ codes a formula $\varphi(\vec x)$$c$ is a tuple $\vec X$ of elements of $M$, and $M\models\varphi(\vec X)$. Then $\mathrm{Sat}(a,b,c)$ is $\Delta_1$. Using this and the reflection theorem we can conclude that $\Delta_1$ is actually the extent of absoluteness in set theory, meaning that whenever there is a finite $S$ such that $\phi$ is absolute for transitive models of $S$, then $\phi$ is (provably equivalent to) a $\Delta_1$ statement.

We exhibited a few formulas that are not absolute. For example, “$x$ is a cardinal” and “$x=V_\alpha$,” although both are $\Pi_1$ and therefore relativize downwards.

The main application of the absoluteness of satisfiability is that it allows us to define the constructible hierarchy and Gödel’s constructible universe $L$.

Remark. On the other hand, we cannot define in general satisfiability for transitive classes, by Tarski’s undefinability of truth theorem. The difference with the case of sets is that with sets the recursive definition of $M\models\dots$ involves several bounded quantifiers, ranging over finite powers of $M$. With general proper classes $M$, these quantifiers would be unbounded. An easy inductive argument shows that we can define partial satisfiability predicates (and therefore partial truth predicates), meaning that for each natural number $n$ and each class $M$ we can find a $\Sigma_n$ formula that defines satisfiability for $\Sigma_n$ formulas with respect to $M$; although we cannot in general find a uniform definition that works simultaneously for all $n$.