Set-theoretic arguments often make use of the fact that a particular property $\varphi$ is *local*, in the sense that instances of the property can be verified by checking certain facts in only a bounded part of the set-theoretic universe, such as inside some rank-initial segment $V_\theta$ or inside the collection $H_\kappa$ of all sets of hereditary size less than $\kappa$. It turns out that this concept is exactly equivalent to the property being $\Sigma_2$ expressible in the language of set theory.

**Theorem**. For any assertion $\varphi$ in the language of set theory, the following are equivalent:

- $\varphi$ is ZFC-provably equivalent to a $\Sigma_2$ assertion.
- $\varphi$ is ZFC-provably equivalent to an assertion of the form “$\exists \theta\, V_\theta\models\psi$,” where $\psi$ is a statement of any complexity.
- $\varphi$ is ZFC-provably equivalent to an assertion of the form “$\exists \kappa\, H_\kappa\models\psi$,” where $\psi$ is a statement of any complexity.

Just to clarify, the $\Sigma_2$ assertions in set theory are those of the form $\exists x\,\forall y\,\varphi_0(x,y)$, where $\varphi_0$ has only bounded quantifiers. The set $V_\theta$ refers to the rank-initial segment of the set-theoretic universe, consisting of all sets of von Neumann rank less than $\theta$. The set $H_\kappa$ consists of all sets of hereditary size less than $\kappa$, that is, whose transitive closure has size less than $\kappa$.

**Proof**. ($3\to 2$) Since $H_\kappa$ is correctly computed inside $V_\theta$ for any $\theta>\kappa$, it follows that to assert that some $H_\kappa$ satisfies $\psi$ is the same as to assert that some $V_\theta$ thinks that there is some cardinal $\kappa$ such that $H_\kappa$ satisfies $\psi$.

($2\to 1$) The statement $\exists \theta\, V_\theta\models\psi$ is equivalent to the assertion $\exists\theta\,\exists x\,(x=V_\theta\wedge x\models\psi)$. The claim that $x\models\psi$ involves only bounded quantifiers, since the quantifiers of $\psi$ become bounded by $x$. The claim that $x=V_\theta$ is $\Pi_1$ in $x$ and $\theta$, since it is equivalent to saying that $x$ is transitive and the ordinals of $x$ are precisely $\theta$ and $x$ thinks every $V_\alpha$ exists, plus a certain minimal set theory (so far this is just $\Delta_0$, since all quantifiers are bounded), plus, finally, the assertion that $x$ contains every subset of each of its elements. So altogether, the assertion that some $V_\theta$ satisfies $\psi$ has complexity $\Sigma_2$ in the language of set theory.

($1\to 3$) This implication is a consequence of the following absoluteness lemma.

**Lemma**. (Levy) If $\kappa$ is any uncountable cardinal, then $H_\kappa\prec_{\Sigma_1} V$.

**Proof**. Suppose that $x\in H_\kappa$ and $V\models\exists y\,\psi(x,y)$, where $\psi$ has only bounded quantifiers. Fix some such witness $y$, which exists inside some $H_\gamma$ for perhaps much larger $\gamma$. By the Löwenheim-Skolem theorem, there is $X\prec H_\gamma$ with $\text{TC}(\{x\})\subset X$, $y\in X$ and $X$ of size less than $\kappa$. Let $\pi:X\cong M$ be the Mostowski collapse of $X$, so that $M$ is transitive, and since it has size less than $\kappa$, it follows that $M\subset H_\kappa$. Since the transitive closure of $\{x\}$ was contained in $X$, it follows that $\pi(x)=x$. Thus, since $X\models\psi(x,y)$ we conclude that $M\models \psi(x,\pi(y))$ and so hence $\pi(y)$ is a witness to $\psi(x,\cdot)$ inside $H_\kappa$, as desired. **QED**

Using the lemma, we now prove the remaining part of the theorem. Consider any $\Sigma_2$ assertion $\exists x\,\forall y\, \varphi_0(x,y)$, where $\varphi_0$ has only bounded quantifiers. This assertion is equivalent to $\exists\kappa\, H_\kappa\models\exists x\,\forall y\,\varphi_0(x,y)$, simply because if there is such a $\kappa$ with $H_\kappa$ having such an $x$, then by the lemma this $x$ works for all $y\in V$ since $H_\kappa\prec_{\Sigma_1}V$; and conversely, if there is an $x$ such that $\forall y\, \varphi_0(x,y)$, then this will remain true inside any $H_\kappa$ with $x\in H_\kappa$. **QED**

In light of the theorem, it makes sense to refer to the $\Sigma_2$ properties as the *locally verifiable* properties, or perhaps as *semi-local* properties, since positive instances of $\Sigma_2$ assertions can be verified in some sufficiently large $V_\theta$, without need for unbounded search. A truly local property, therefore, would be one such that positive and negative instances can be verified this way, and these would be precisely the $\Delta_2$ properties, whose positive and negative instances are locally verifiable.

Tighter concepts of locality are obtained by insisting that the property is not merely verified in *some* $V_\theta$, perhaps very large, but rather is verified in a $V_\theta$ where $\theta$ has a certain closeness to the parameters or instance of the property. For example, a cardinal $\kappa$ is measurable just in case there is a $\kappa$-complete nonprincipal ultrafilter on $\kappa$, and this is verified inside $V_{\kappa+2}$. Thus, the assertion “$\kappa$ is measurable,” has complexity $\Sigma^2_1$ over $V_\kappa$. One may similarly speak of $\Sigma^n_m$ or $\Sigma^\alpha_m$ properties, to refer to properties that can be verified with $\Sigma_m$ assertions in $V_{\kappa+\alpha}$. Alternatively, for any class function $f$ on the ordinals, one may speak of *$f$-local* properties, meaning a property that can be checked of $x\in V_\theta$ by checking a property inside $V_{f(\theta)}$.

This post was made in response to a question on MathOverflow.

I always find this equivalence surprising and it is very useful. When I read the MO question that presumably motivated this post, asking about whether there is a locally defined large cardinal which always has a supercompact below it, I mistakenly tried to come with such a notion (I thought of rank-into-rank). But of course, as you point out in your answer, local notions are always $\Sigma_2$ and so this is impossible. It is a great observation!

Because supercompact cardinals are $\Sigma_2$-reflecting.

Yes, that is completely right.

Joel, this is a nice and really helpful post. Just a couple of small remarks.

1. Shouldn’t Levy’s absoluteness lemma be for uncountable cardinals $\kappa$?

2. In your response to the related question on mathoverflow, you say that “$\kappa$ is supercompact”, like other global large cardinal properties, has complexity $\Pi_3$. However, and while this is true for e.g., extendible cardinals, for the case of supercompactness we can do better and show that “$\kappa$ is supercompact” is in fact $\Pi_2$-expressible (see Kanamori Ch. 5, right after 22.8 Exercise). Essentially, the point is that “we know where to look” for the normal measures witnessing (levels of) supercompactness, i.e., we have a bound on the ordinal rank in which we have to search for them, just as you mention in your final paragraph of this post.

Best regards!

Yes, you are right on both counts. I have edited here to insist $\kappa$ is uncountable. And indeed, the failure of the supercompactness of $\kappa$ is clearly locally verifiable, so being supercompact is at worst $\Pi_2$ as you say, and so I have also edited on MO.

Pingback: The universal definition — it can define any mathematical object you like, in the right set-theoretic universe | Joel David Hamkins

Pingback: When does every definable nonempty set have a definable element? | Joel David Hamkins

Dear Joel,

This post is very useful for something (philosophical) I’m writing up now. Is there a way of citing it, or have versions of this appeared in print?

Best,

Neil

Pingback: The otherwordly cardinals | Joel David Hamkins

Dear Dr. Hamkins,

I am afraid to be slightly confused by the exact meaning of this wonderful equivalence: isn’t it the property ψ which is the local one here, and not φ itself?

Thank you.

That is an interesting perspective, but I don’t agree. The statement $\psi$ might not be local—if true in the universe, it might not necessarily be verifiable inside any set. But meanwhile, we are checking whether $\psi$ holds in this local set $V_\theta$. Ultimately, it is $\varphi$ that is local, because it is equivalent to the truth of a statement, $\psi$, inside a set.

Consider this: being the tallest person is not a local property, since one must make global comparisons. But being the tallest-in-your-household is local, since you just have to check if you have the being-the-tallest property in a local region, your household.

I strangely wasn’t notified of your answer… Anyway, okay thank you I got it! Now in my mind occurred the switch of perspective to your point of view, and I agree not to agree.

Nice illustrative example by the way.