Proof of Locality of Predicative Formulas: Truth Depends Only on the Values of the Free Variables

The proof is an argument of the metatheory: an induction on the build-up of formulas by the rules of Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (ii). Throughout, $Z_{1},\dots,Z_{m}$ and $C_{1},\dots,C_{m}$ are as in the statement.

Assignments. Here an assignment $\alpha$ gives a set $\alpha(u)$ to each variable $u$ of a finite list of distinct set variables, called its list, and gives $C_{1},\dots,C_{m}$ to $Z_{1},\dots,Z_{m}$. Let $\psi$ be a formula whose free set variables are on the list $u_{1},\dots,u_{r}$ of $\alpha$ and whose class variables are among $Z_{1},\dots,Z_{m}$. We say that $\psi$ holds under $\alpha$ when the statement obtained, as in Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (iv), by reading $\psi$ as $\psi(u_{1},\dots,u_{r},Z_{1},\dots,Z_{m})$, with $\alpha(u_{i})$ assigned to $u_{i}$ and $C_{l}$ to $Z_{l}$, holds. For a set variable $y$ and a set $c$, let $\alpha[y:=c]$ be the assignment that gives $y$ the value $c$ and agrees with $\alpha$ on every other variable; its list is that of $\alpha$, with $y$ added at the end if it is not already on it.

The strengthened claim. We prove, for every formula $\psi$, the following statement $(*)$ about $\psi$: if $\psi$ is predicative and its class variables are among $Z_{1},\dots,Z_{m}$, then for all assignments $\alpha$ and $\beta$ whose lists contain the free set variables of $\psi$ and which give the same set to each of them, $\psi$ holds under $\alpha$ if and only if $\psi$ holds under $\beta$.

The clauses follow from $(*)$. Let $a_{1},\dots,a_{n}$, $b_{1},\dots,b_{p}$ and $c_{1},\dots,c_{p}$ be sets. Let $\alpha$ have list $x_{1},\dots,x_{n},y_{1},\dots,y_{p}$ and give $a_{i}$ to $x_{i}$ and $b_{j}$ to $y_{j}$; let $\gamma$ have the same list and give $a_{i}$ to $x_{i}$ and $c_{j}$ to $y_{j}$; and let $\beta$ have list $x_{1},\dots,x_{n}$ and give $a_{i}$ to $x_{i}$. By the way the statement defines $\varphi(a_{1},\dots,a_{n})$ and $\varphi(a_{1},\dots,a_{n},b_{1},\dots,b_{p})$, the formula $\varphi$ holds under $\alpha$ exactly when $\varphi(a_{1},\dots,a_{n},b_{1},\dots,b_{p})$ holds, under $\gamma$ exactly when $\varphi(a_{1},\dots,a_{n},c_{1},\dots,c_{p})$ holds, and under $\beta$ exactly when $\varphi(a_{1},\dots,a_{n})$ holds. The lists of all three assignments contain $x_{1},\dots,x_{n}$, among which are the free set variables of $\varphi$, and all three give $a_{i}$ to $x_{i}$. Since $\varphi$ is predicative with class variables among $Z_{1},\dots,Z_{m}$, $(*)$ for $\varphi$ applied to $\alpha$ and $\gamma$ gives (i), and applied to $\alpha$ and $\beta$ gives (ii).

Parts of a predicative formula. If $\psi$ is $\neg\chi$, $(\chi\wedge\chi')$ or $\exists y\,\chi$, then every part of $\chi$ (and of $\chi'$) is a part of $\psi$. Hence if $\psi$ is predicative, so are $\chi$ and $\chi'$: a part $\exists X\,\theta$ of $\chi$, with $X$ a class variable, would be such a part of $\psi$, against Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (v). Likewise the class variables of $\chi$ and $\chi'$ are among those of $\psi$. By Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (iii), the free variables of $\neg\chi$ are those of $\chi$, those of $(\chi\wedge\chi')$ are those of $\chi$ together with those of $\chi'$, and those of $\exists y\,\chi$ are those of $\chi$ other than $y$.

In each case below, let $\psi$ be predicative with class variables among $Z_{1},\dots,Z_{m}$, and let $\alpha$ and $\beta$ be as in $(*)$; the induction hypothesis is $(*)$ for the formulas from which the last rule builds $\psi$, for all assignments.

Atomic formulas. Let $\psi$ be $s\in t$ or $s=t$ with $s$ and $t$ variables. It has no part of the form $\exists v\,\theta$, so by Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (iii) each of $s$ and $t$ is a free variable of $\psi$. If it is a set variable, it is on both lists, and $\alpha$ and $\beta$ give it the same set; if it is a class variable, it is some $Z_{l}$, and both give it $C_{l}$. By Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (iv), $\psi$ read under an assignment is the statement that the value of $s$ is an element of, respectively equal to, the value of $t$; it involves only the values of $s$ and $t$, which are the same under $\alpha$ and under $\beta$. So $\psi$ holds under $\alpha$ if and only if it holds under $\beta$.

Negation. If $\psi$ is $\neg\chi$, then $\chi$ is predicative with class variables among $Z_{1},\dots,Z_{m}$ and has the same free set variables as $\psi$, so $(*)$ for $\chi$ shows that $\chi$, and hence, by Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (iv), its negation $\psi$, holds under $\alpha$ if and only if it holds under $\beta$.

Conjunction. If $\psi$ is $(\chi\wedge\chi')$, then $\chi$ and $\chi'$ are predicative with class variables among $Z_{1},\dots,Z_{m}$ and their free set variables are free set variables of $\psi$, so $(*)$ for $\chi$ and for $\chi'$ shows that each of them, and hence, by Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (iv), their conjunction $\psi$, holds under $\alpha$ if and only if it holds under $\beta$.

Existential quantification. Let $\psi$ be $\exists v\,\chi$. Since $\psi$ is predicative, $v$ is a set variable by Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (v); call it $y$. Every occurrence of $y$ in $\psi$ lies inside the part $\exists y\,\chi$, so by Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (iii) $y$ is not a free variable of $\psi$, and by Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (iv) the statement obtained from $\psi$ under $\alpha$ does not involve any value $\alpha$ gives $y$, whether or not $y$ is on the list of $\alpha$: it is the statement "there is a set $y$ such that $\chi$", in which the other listed variables keep their values. So $\psi$ holds under $\alpha$ if and only if there is a set $c$ such that $\chi$ holds under $\alpha[y:=c]$, and likewise for $\beta$. The free set variables of $\chi$ are among those of $\psi$ and $y$; they are on the lists of $\alpha[y:=c]$ and $\beta[y:=c]$, and these two assignments agree on each of them: both give $y$ the value $c$, and on a free set variable of $\psi$, which is different from $y$, they agree with $\alpha$ and $\beta$, which agree there. As $\chi$ is predicative with class variables among $Z_{1},\dots,Z_{m}$, $(*)$ for $\chi$ gives, for every set $c$, that $\chi$ holds under $\alpha[y:=c]$ if and only if it holds under $\beta[y:=c]$. Hence there is a set $c$ for which $\chi$ holds under $\alpha[y:=c]$ if and only if there is one for which it holds under $\beta[y:=c]$; that is, $\psi$ holds under $\alpha$ if and only if it holds under $\beta$.

Every formula is obtained by finitely many applications of the rules of Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (ii), and the cases above cover each rule, the hypothesis being used only for the formulas from which the rule builds $\psi$. So $(*)$ holds for every formula, and both clauses follow as shown.