## Can Vopenka’s principle be violated definably?

One form of Vopenka's principle (a large cardinal axiom) states that no locally presentable category contains a full subcategory which is large (= a proper class) and discrete (= contains no nonidentity morphisms). In terms of this definition, my question is:

Can one define a particular locally presentable category C and write down an explicit formula $\phi(x)$ in the first-order language of set theory such that if Vopenka's principle fails, then $\{ x | \phi(x) \}$ is a large discrete full subcategory of C?

But feel free to use any equivalent statement of Vopenka's principle and answer a suitably equivalent version of the question.

-
In the set-theoretic terminology, are you asking whether Vopenka can fail in a GBC model, without failing for any definable class? – Joel David Hamkins Nov 11 2010 at 0:56
Partially, I think. I am also curious whether there is a single specific definable class that always violates Vopenka if anything does, in the same way that there is a single explicitly definable algorithm which solves SAT in polynomial time if anything does. – Mike Shulman Nov 11 2010 at 3:47

This is a very interesting question, and I finally have an answer. (I just had a fruitful conversation about Vopenka in my office with Andrew Brooke-Taylor, who will give a talk on Vopenka for our seminar tomorrow.)

The answer to your question is no, provided that VP is consistent, there can be no such definable class.

The reason has to do with the formalization of VP in set theory, whether one interprets it as a second order axiom or as a first-order scheme. Let me consider the set-theoretic versions of the Vopenka Principle, the assertion that every proper class ordinal-indexed sequence $\langle M_\alpha\mid\alpha\in\text{Ord}\rangle$ of mathematical structures in the same language has some $\alpha\lt\beta$ with an elementary embedding of $M_\alpha$ into $M_\beta$. The principle is equivalent if one restricts to the case where each $M_\alpha$ is a graph, although set-theorists often prefer to restrict to the case where each $M_\alpha$ is a rank-initial segment $V_{\gamma_\alpha}$ of the universe, sometimes with some additional predicates added on the side.

This way of stating the axiom is ambiguous until we specify how one is to interpret the quantification over classes ("for every class sequence..."). The standard formulation of VP insists that this is a second-order quantifier, ranging over all classes, and this can be expressed in GBC by a single statement about all classes. In ZFC, we can express a similar-but-actually-weaker principle as an axiom scheme, ranging over all possible definitions $\varphi$, as the statement "if for every ordinal $\alpha$ there is a unique structure $M_\alpha$ satisfying $\varphi(\alpha,M_\alpha)$, then...".

The same difference arises when defining the Vopenka cardinals. Namely, a cardinal $\kappa$ is a Vopenka cardinal if $\kappa$ is inaccessible and every $\kappa$-sequence of structures $\langle M_\alpha\mid\alpha\lt\kappa\rangle$ with $M_\alpha\in V_\kappa$ has some $\alpha\lt\beta$ with $M_\alpha$ embedding elementarily into $M_\beta$. Alternatively, we could define that $\kappa$ is an almost Vopenka cardinal if $V_\kappa$ satisfies the Vopenka scheme.

The difference in each case is the difference between the boldface concept and a lightface one. Vopenka cardinals are defined by reference essentially to $V_{\kappa+1}$, using all $\kappa$-sequences of structures whether the sequence is definable or not, whereas the almost Vopenka cardinals only consider the sequences definable (with parameters) over $V_\kappa$. And similarly for the full class versions: the full VP uses all classes, but the Vopenka scheme only uses definable classes.

My point is that the weaker definable versions are strictly weaker.

Theorem.

• If the Vopenka Principle holds, then there is a forcing extension $V[G]$ in which the Vopenka Principle fails, but the Vopenka scheme continues to hold.
• Every Vopenka cardinal $\kappa$ is a limit of $\kappa$ many almost-Vopenka cardinals. In particular, the smallest almost-Vopenka cardinal is not a Vopenka cardinal.

Proof. If VP holds, then we may force to add a closed unbounded class C of cardinals avoiding the regular cardinals. This kills the Mahlo-ness of the ordinals, without adding any new sets. Thus, V and V[C] have the same sets, and so V[C] continues to satisfy the Vopenka scheme. But V[C] does not satisfy the full VP, since that implies that Ord is Mahlo.

For the second statement, suppose $\kappa$ is a Vopenka cardinal. It follows that $\kappa$ is Mahlo, in fact it is $\kappa$-Mahlo. Thus, there are numerous inaccessible $\gamma\lt\kappa$ with $V_\gamma$ elementary in $V_\kappa$. Every such $\gamma$ is almost-Vopenka, since the scheme transfers down to $V_\gamma$ by elementarity. QED

This theorem implies that if the Vopenka Principle is consistent at all, then there are models where VP fails, but not for any definable counterexample. So there can be no such definable counterexample as you describe.

I anticipate that you may choose to fall back, and say that you didn't really want the full second-order Vopenka principle, but only the definable version anyway. In this case, a version of my argument will still apply. Namely, we can stratify the definable levels of Vopenka by the $\Sigma_n$ complexity of the definitions involved. The Vopenka scheme is asserting $\Sigma_n$-Vopenka for every natural number $n$ in the meta-theory. If this scheme holds, we have that ORD is definably Mahlo. By the Reflection theorem, we can find an inaccessible cardinal $\gamma$ such that $V_\gamma$ is $\Sigma_n$ elementary in $V$, and so it will continue to satisfy $\Sigma_n$-Vopenka, but not the full Vopenka scheme. If your definition is $\Sigma_n$, then it will therefore not produce a counterexample, even though the VP scheme fails in this model. This is a strong sense in which there can be no definable counterexample as you describe.

-
Joel: Very nice! – Andres Caicedo Nov 18 2010 at 20:56
Oh, please say hi to Andrew from me. – Andres Caicedo Nov 18 2010 at 20:59
Thanks, Andres. I definitely learned something about Vopenka doing this. – Joel David Hamkins Nov 18 2010 at 21:01
The whole argument can be given quickly by the last paragraph: your formula $\varphi$ will have some complexity $\Sigma_n$, but it can happen that $\Sigma_n$-Vopenka holds without $\Sigma_{n+1}$-Vopenka holding, and if your background universe is like that, your formula won't give the counterexample that is needed. – Joel David Hamkins Nov 18 2010 at 21:11
Another way to describe the argument is: if there were such a definable counterexample, then VP would be first order expressible---you just have to say that the counterexample really does define a counterexample. But neither the full second-order version of VP nor the scheme version of VP is first order expressible by a single sentence, for the reasons I explain in my answer. – Joel David Hamkins Nov 19 2010 at 18:36
show 1 more comment