Generic Vopěnka's Principle

This is a talk at the Rutgers Logic Seminar in New Jersey, May 2, 2016.

It is well-established folklore that Petr Vopěnka introduced Vopěnka's Principle to satirize large cardinals and had the intention of soon showing it to be inconsistent with ${\rm ZFC}$. But his proof broke and Vopěnka's Principle came, over the years, to be viewed as an important set-theoretic principle with strong connections to category theory (see [bibcite key=AdamekRosicky:vopenka]). Vopěnka's Principle asserts that for every proper class of structures of the same first-order language, there are two distinct ones between which there is an elementary embedding. It is not difficult to imagine by considering classes of structures of the form $\langle V_\alpha,\in\rangle$ that Vopěnka's Principle will imply the existence of large cardinals. Vopěnka's Principle is a second-order assertion because we are quantifying over all classes of structures and it can be formalized in ${\rm GBC}$, ${\rm KM}$ or one's favorite class set theory. Here is an elegant reformulation of Vopěnka's Principle: for every sequence $\langle M_\alpha\mid \alpha\in{\rm ORD}\rangle$ of distinct structures of the same first-order language, there are $\alpha<\beta$ such that $M_\alpha$ elementarily embeds into $M_\beta$. I recently stumbled onto this formulation, and so, for fun, let's prove it. I will argue using a class version of Fodor's Lemma, but I suspect that there might be much easier proofs.

Lemma: Suppose $F:{\rm ORD}\to{\rm ORD}$ is regressive. Then $F$ is constant on a proper class.

Proof: Suppose not. Then for every ordinal $\alpha$, there is another ordinal $\gamma_\alpha$ such that for $\gamma>\gamma_\alpha$, $F(\gamma)\neq\alpha$. Let $C_\alpha$ be the tail of the ordinals above $\gamma_\alpha$. It is not difficult to see that the diagonal intersection $C=\Delta_{\alpha\in{\rm ORD}}C_\alpha$ is a class club, and so in particular nonempty. So let $\gamma\in C$. It follows that $\gamma\in C_\alpha$ for all $\alpha<\gamma$. In particular, $\gamma\in C_\delta$, where $F(\gamma)=\delta$. But this is impossible, since by definition of $C_\delta$, $F(\gamma)\neq\delta$. $\square$

In one direction, suppose Vopěnka's Principle holds and that $\langle M_\alpha\mid\alpha\in{\rm ORD}\rangle$ is a sequence of structures of some first-order language. Shift the enumeration to start from 1. Define a regressive $F:{\rm ORD}\to {\rm ORD}$ as follows. If there is $\beta<\alpha$ such that $M_\alpha$ elementarily embeds into $M_\beta$, then we let $F(\alpha)=\beta$ where $\beta$ is least such, and otherwise $F(\alpha)=0$. So there is some $\gamma$ such that $F(\alpha)=\gamma$ for a proper class $\mathcal C$ of $\alpha$. First, suppose $\gamma=0$. By Vopěnka's Principle, there are $\alpha\neq\eta\in \mathcal C$ such that $M_\alpha$ elementarily embeds into $M_\eta$, and so $\alpha<\eta$. Next, suppose $\gamma=\beta>0$. Then there is a proper class of $\alpha$ such that $M_\alpha$ elementarily embeds into $M_\beta$. Since by cardinality considerations, $M_\beta$ has at most $2^{|M_\beta|}$-many elementary substructures, there must be $\alpha_1<\alpha_2$ in $\mathcal C$ such that $M_{\alpha_1}$ and $M_{\alpha_2}$ are isomorphic.

In the other direction now, suppose that for every sequence $\langle M_\alpha\mid\alpha\in{\rm ORD}\rangle$ of distinct structures in the same first-order language there are $\alpha<\beta$ such that $M_\alpha$ elementarily embeds into $M_\beta$. If Global Choice is one of your axioms, then Vopěnka's Principle is immediate. In the absence of Global Choice, such as in the setting where we only take definable classes, our principle might appear to be weaker than Vopěnka's Principle because there might be non-well-orderable classes of structures. But surprisingly this is not the case! So fix a proper class $\mathcal C$ of first-order structures in the same language. Let $\mathcal C_\alpha=\mathcal C\cap V_\alpha$. Now consider the proper class of all structures of the form $\langle V_{\alpha+2},\in, C_\alpha\rangle$ such that $C_\alpha$ has elements of unbounded rank in $V_\alpha$ and $\alpha$ is not inaccessible. This class is clearly well-orderable, so by our assumption there is an elementary embedding $j:V_{\alpha+2}\to V_{\beta+2}$ between two distinct elements of the class. Since $\alpha$ was assumed to not be inaccessible, the critical point $\kappa$ of $j$ is below $\alpha$. So let $M\in C_\alpha$ have rank $\gamma>\kappa$. It cannot be case that $j(\gamma)=\gamma$ since then $j$ would restrict to an embedding $j:V_{\gamma+2}\to V_{\gamma+2}$ violating Kunen's Inconsistency. So $j(\gamma)>\gamma$ and hence $j(M)\neq M$ is in $C_\beta$. Now restrict $j$ to $j:M\to j(M)$ and we have an elementary embedding between two distinct structures in $\mathcal C$.

In first-order set theory, we can consider Vopěnka's Principle for definable classes. Let ${\rm VP}(\mathbf{\Sigma}_n)$ be the first-order assertion that Vopěnka's Principle holds for $\Sigma_n$-definable with parameters classes of structures, with ${\rm VP}(\mathbf{\Pi}_n)$ defined analogously. (One can also consider the light-face ${\rm VP}(\Sigma_n)$ principle, where parameters are not allowed in the definition of the class.) First-order Vopěnka's Principle is then the scheme of assertions ${\rm VP}(\mathbf{\Sigma}_n)$ for every $n\in\omega$. First-order Vopěnka's Principle is a weaker notion via implication, but not via consistency.

Theorem: (Hamkins) There are models of ${\rm GBC}$ in which first-order Vopěnka's Principle holds, but Vopěnka's Principle for all classes fails. However, the two principles are equiconsistent.

The first result comes from a MathOverflow answer and second from a work in progress [1].

First-order Vopěnka's Principle doesn't just imply consistency of large cardinals, but holds precisely when proper classes of certain large cardinals are present in the universe. Recall that $\kappa$ is extendible if for every $\alpha>\kappa$, there is an elementary embedding $j:V_\alpha\to V_\beta$ with ${\rm crit}(j)=\kappa$. Let $C^{(n)}$ be the class club of $\delta$ such that $V_\delta\prec_{\Sigma_n}V$. Bagaria defined that a cardinal $\kappa$ is $C^{(n)}$-extendible if for every $\alpha>\kappa$, there is an extendibility embedding $j:V_\alpha\to V_\beta$ with $j(\kappa)\in C^{(n)}$. Notice that extendible cardinals are $C^{(1)}$-extendible because for any extendibility embedding $j$, $j(\kappa)$ is inaccessible and hence in $C^{(1)}$. It is not difficult to see that ${\rm VP}(\mathbf{\Sigma}_1)$ is a theorem of ${\rm ZFC}$.

Theorem: (Bagaria [2])

In particular, it follows that first-order Vopěnka's Principle holds precisely when for every $n\in\omega$, there is a proper class of $C^{(n)}$-extendible cardinals.

In this talk, I will introduce Generic Vopěnka's Principle which asserts that the embeddings posited by Vopěnka's Principle exist somewhere in the generic multiverse. More precisely, Generic Vopěnka's Principle asserts that for every proper class of structures in the same first-order language, there are two distinct ones between which there is an elementary embedding in some set-forcing extension. I will focus mainly on first-order Generic Vopěnka's Principle, which is the scheme of assertions ${\rm gVP}(\mathbf{\Sigma}_n)$ for $n\in\omega$, each of which asserts that Generic Vopenka's Principle holds for $\Sigma_n$-definable with parameters classes. Each assertion ${\rm gVP}(\mathbf{\Sigma}_n)$ is first-order expressible because we can quantify over the properties of all forcing extensions in $V$ using a theorem of Laver and Hamkins that ground models are definable [3]. But we will see in the next paragraph that this is not even necessary because there are ways to express that an embedding of $V$-structures exists in a forcing extension without quantifying over all of them.

Let's explore for a moment this notion of virtual embeddings, which exist somewhere in the generic multiverse. What are some examples of structures between which there is no elementary embedding in $V$, but such an embedding can be added by forcing?

Example 1: Obviously the reals cannot embed into the rationals in $V$, but any forcing which collapses the continuum to $\omega$ adds an isomorphism between the reals of $V$ and the rationals because in the forcing extension the reals of $V$ are a countable dense linear order without end-points.

Example 2: Suppose $0^{\sharp}$ exists and $\delta=\omega_1^V$. In $L$, there is no nontrivial elementary embedding from $L_{\delta}$ to itself, but the forcing collapsing $\delta$ to $\omega$ adds an elementary embedding $j:L_\delta\to L_\delta$. This is not obvious, but follows easily from the Absoluteness Lemma discussed here.

Notice that both of our examples succeeded by collapsing the structure we wanted to embed to be countable. This is not a coincidence.

Theorem: Suppose $B$ and $A$ are two first-order structures in the same language. The following are equivalent.

There is an another elegant characterization of when an embedding of $V$-structures exists in a forcing extension, due to Schindler, using Ehrenfeucht-Fraisse like games. Suppose $B$ and $A$ are first-order structures in the same language. Consider the following $\omega$-length game $G(B,A)$ where on every move player I plays an element out of $B$ and player II plays an element out of $A$. Let $\{b_n\mid n<\omega\}$ be the moves of player I and $\{a_n\mid n<\omega\}$ be the moves of player II. Player II wins if all maps $f:\{b_0,\ldots,b_n\}\to \{a_0,\ldots,a_n\}$ are finite partial isomorphisms, and otherwise player I wins. Clearly if player II loses she must do so in finitely many steps, and so $G(B,A)$ is a closed game. It follows by the Gale-Stewart Theorem that either player I or player II must have a winning strategy.

Theorem: Suppose $B$ and $A$ are two first-order structures in the same language. The following are equivalent.

The concept of elementary embeddings of $V$-structures existing in the generic multiverse leads naturally to a class of large cardinal notions, the virtual large cardinals, which are discussed here. If $\mathcal A$ is a large cardinal notion characterized by the existence of embeddings of set-sized structures, then a virtual $\mathcal A$ cardinal asserts that the embeddings characterizing $\mathcal A$ exist in some forcing extension. The strength of first-order generic Vopěnka's Principle is measured precisely by such cardinals.

Recall that a cardinal $\kappa$ is remarkable if for every $\lambda>\kappa$, there exists $\bar\lambda<\kappa$ such that in some set-forcing extension, there is an elementary embedding $j:V_{\bar\lambda}\to V_\lambda$ with $j({\rm crit}(j))=\kappa$. Remarkable cardinals are virtually supercompact because Magidor showed that supercompact cardinals are characterized by the existence of remarkable embeddings in $V$. Let's consider the following natural extension of remarkability.

Definition ([4]): A cardinal $\kappa$ is $n$-remarkable if for every $\lambda\in C^{(n)}$, there is $\bar\lambda$ also in $C^{(n)}$ such that in some set-forcing extension there is an elementary embedding $j:V_{\bar\lambda}\to V_\lambda$ with $j({\rm crit}(j))=\kappa$.

Note that remarkable cardinals are $1$-remarkable. It turns out that $n$-remarkable cardinals for $n>1$ are precisely the virtually $C^{(n)}$-extendible cardinals.

Theorem: ([4]) A cardinal $\kappa$ is $n$-remarkable for $n>1$ iff $\kappa$ is virtually $C^{(n)}$-extendible.

With these virtual analogues of the large cardinals used to measure the strength of first-order Vopěnka's Principle we can measure the strength of ${\rm gVP}(\mathbf{\Sigma}_n)$.

Theorem: (([4]) The following are equiconsistent.

If there is a proper class of $n$-remarkable cardinals, then it is not difficult to see the ${\rm gVP}(\mathbf{\Sigma}_{n+1})$ holds. We do not know whether ${\rm gVP}(\mathbf{\Sigma}_{n+1})$ implies outright that there are $n$-remarkable cardinals. Bagaria's proof fails to generalize completely primarily because the virtual version of Kunen's Inconsistency is consistent! In a set-forcing extension there can be embeddings $j:V_\delta\to V_\delta$ where $\delta$ is much larger than the supremum $\lambda$ of the critical sequence, say $\delta=\lambda^+$. This is not difficult see by considering embedding of $V_\delta^L$ resulting from $0^{\sharp}$. So more precisely we have that:

Theorem: If ${\rm gVP}(\mathbf{\Sigma}_{n+1})$ holds then there is a proper class of cardinals $\kappa$ such that $\kappa$ is either $n$-remarkable or virtually rank-into-rank.

Virtually rank-into-rank cardinals are much stronger than $n$-remarkable cardinals. In particular, if $\kappa$ is virtually rank-into-rank, then $V_\kappa$ is a model of proper class many $n$-remarkable cardinals for every $n\in\omega$. So let me end with a question.

Question: Is it possible that there is a model of ${\rm gVP}(\mathbf{\Sigma}_{n+1})$ with boundedly many $n$-remarkable cardinals but unboundedly many virtually rank-into-rank cardinals?

This is joint work with Joan Bagaria and Ralf Schindler.

For slides go to Young Set Theory talk post and scroll down.

References

  1. J. D. Hamkins, “The Vopěnka principle is inequivalent to but conservative over the Vopěnka scheme.” Available at: http://jdh.hamkins.org/vopenka-principle-vopenka-scheme
  2. J. Bagaria, “$C^{(n)}$-cardinals,” Arch. Math. Logic, vol. 51, no. 3-4, pp. 213–240, 2012.
  3. R. Laver, “Certain very large cardinals are not created in small forcing extensions,” Ann. Pure Appl. Logic, vol. 149, no. 1-3, pp. 1–6, 2007.
  4. J. Bagaria, V. Gitman, and R. Schindler, “Generic Vopěnka’s Principle, remarkable cardinals, and the weak Proper Forcing Axiom,” Arch. Math. Logic, vol. 56, no. 1-2, pp. 1–20, 2017.