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.