# When does Vopěnka's principle hold?

Vopěnka's principle (VP) is the statement that, given any proper class $\{\mathcal{A}_\eta: \eta\in ON\}$ of first-order structures in the same language, there are some $\alpha\not=\beta$ with $\mathcal{A}_\alpha$ elementarily embeddable into $\mathcal{A}_\beta$. There are several other equivalent formulations of VP - see http://ncatlab.org/nlab/show/Vop%C4%9Bnka%27s+principle.

VP is a very strong large cardinal axiom - in particular, it implies the existence of a proper class of extendible cardinals. However, this needn't stop us from showing that many nice classes of structures aren't counterexamples to VP:

• Say a class of structures $\mathcal{C}$ satisfies VP if $\mathcal{C}$ is a proper class and, for any sub-proper class $\mathcal{D}\subseteq\mathcal{C}$, there are distinction $\mathcal{A}_0,\mathcal{A}_1\in\mathcal{D}$ with $\mathcal{A}_0$ elementarily embeddable in $\mathcal{A}_1$.

(Note: to avoid annoyance, let's work in some theory like $NGB$ which can directly treat classes.)

My question is:

(Q1) What are some classes which we can prove - in ZFC (maybe + additional assumptions whose consistency strength is much weaker than full VP) - satisfy VP?

A trivial example is the class of pure sets; an easy, but not quite trivial, example is the class of ordinals (viewed as linear orders). But in general this seems a very hard problem. For example,

(Q2) Does the class of linear orders have VP?

EDIT: after Joel's answers below, Q2 is the only question which remains open.

I suspect the answer to this smaller question is yes, via some clever argument (perhaps using Laver's theorem), but I don't see it.

An interesting side question is whether, by restricting our attention to certain classes of structures, we can find principles of intermediate strength:

(Q3) Are there "natural" (say, $\mathcal{L}_{\omega_1\omega}$-definable) classes of structures $\mathcal{C}$ such that "$\mathcal{C}$ satisfies VP" has nontrivial consistency strength over ZFC (yet still much weaker consistency strength than full VP)?

• Probably too trivial, but in the language of equality we can prove Vopenka's Principle. – Asaf Karagila Apr 22 '15 at 14:40
• Noah, I guess in the definition of satisfies VP, you want to insist that $\cal D$ and $\cal C$ are proper classes, rather than merely classes. – Joel David Hamkins Apr 22 '15 at 18:11
• @JoelDavidHamkins quite right, fixed. – Noah Schweber Apr 23 '15 at 5:05
• @AsafKaragila yes, that's why I say that the pure sets provide a trivial example. – Noah Schweber Apr 23 '15 at 5:06
• An equivalent formulation of VP says that for any Ord-indexed sequence $(A_\alpha)_{\alpha <Ord}$ of objects of $\mathcal C$, there exists $\alpha < \beta$ and a morphism $A_\alpha \to A_\beta$. E.g. in Adamek-Rosicky, this is one of the first equivalent statements shown. (The flexibility about which $\mathcal C$ you assert this for while getting an equivalent to VP is similar to the original formulation.) This formulation is stronger and I think more natural since one needn't think about rigid objects. I don't know how similar the variant of Noah's question using this formulation would be. – Tim Campion Feb 4 at 1:30

For (Q3), here is a class of structures whose VP is strictly intermediate in strength.

Theorem. The following are equivalent.

1. The class $L$ of constructible sets satisfies Vopěnka's principle. That is, any proper class of structures individually in $L$ has one elementarily embedding into the other.
2. $0^\sharp$ exists (see zero sharp).

Proof. $(1\to 2)$. Assume $L$ satisfies VP. Consider the structures of the form $\langle L_{\delta^+},\in,\delta\rangle$. We get an elementary embedding $j:L_{\delta^+}\to L_{\gamma^+}$. This is known to imply that $0^\sharp$ exists. Thanks to a helpful discussion with Gunter Fuchs, here is an outline: let $\kappa$ be the critical point of $j$, and consider the induced $L$-ultrafilter $\mu$ on $\kappa$ defined by $X\in\mu\iff\kappa\in j(X)$. The ultrapower of $L_{\delta^+}$ by $\mu$ maps into $L_{\gamma^+}$ and hence is well-founded. To see that the full ultrapower of $L$ by $\mu$ is well-founded, consider any countably many functions $s_n:\kappa\to\text{Ord}$ in $L$. If $0^\sharp$ does not exist, we can cover this family of functions with a family of $\omega_1$ many functions in $L$. The union of the ranges of these functions has collectively size $\kappa$ altogether at worst, and so $L$ can find isomorphic copies inside $L_{\kappa^+}$, but the ultrapower of $L_{\kappa^+}$ by $\mu$ is well-founded. So the ultrapower of $L$ by $\mu$ is well-founded, and so we have a nontrivial elementary embedding of $L$ to $L$ and so $0^\sharp$ exists.

$(2 \to 1)$. Assume $0^\sharp$ exists and $\cal C$ is a proper class of structures, with ${\cal C}\subset L$. So each element of $\cal C$ is defined in $L$ by some formula $\varphi$ using some ordinal-indiscernible parameters. By going to a subclass, we may assume that they are all defined using the same formula. Suppose that $A\in\cal C$ is defined by $\varphi$ using indiscernible parameters $\theta_0,\ldots,\theta_n$, and $A'\in \cal C$ is much further along, defined using indiscernibles $\theta_0',\ldots,\theta_n'$, in the same relative order, but much larger (although possibly some of them are the same), and plenty of room. Let $j:L\to L$ be an elementary embedding that arises by mapping $\theta_i\mapsto\theta_i'$ and other indiscernibles suitably. It follows that $j(A)=A'$, and that $j\upharpoonright A:A\to A'$ is elementary. So $\cal C$ satisfies VP. QED

Since $0^\sharp$ has intermediate consistency strength between ZFC and full Vopěnka's principle, this is an instance of (Q3).

The argument appears to generalize to the following:

Theorem. The following are equivalent, for any $x\subset\text{Ord}$.

1. The class $L[x]$ satisfies Vopěnka's principle. That is, any proper class of structures individually in $L[x]$ has one elementarily embedding into the other.
2. $x^\sharp$ exists.
• What is $0^\sharp$? :-| – Mariano Suárez-Álvarez Apr 23 '15 at 2:55
• @MarianoSuárez-Alvarez I added a link in the post to zero sharp on Wikipedia. It is a large cardinal axiom that is equivalent to the existence of a nontrivial elementary embedding $j:L\to L$, but also has a characterization in terms of the existence of robust order-indiscernibles for the constructible universe. – Joel David Hamkins Apr 23 '15 at 3:00
• Very nice. In the $(1\to 2)$ direction of the proof you could avoid the appeal to Jensen covering by collapsing an elementary substructure of $L_{\delta^+}$ containing $\kappa$ and the $s_n$ to get an ill-foundedness already in the ultrapower of $L_{\delta^+}$. – Miha Habič Apr 23 '15 at 3:12
• @MihaHabič Great idea! But we should take an elementary substructure in a much larger $L_\theta$, since the $s_n$ are not necessarily in $L_{\delta^+}$. The point should be that by condensation, it collapses down into $L_{\delta^+}$, and gives a counterexample to well-foundedness there, which is a contradiction. – Joel David Hamkins Apr 23 '15 at 11:15

It seems to me that the following

• Vopěnka's principle (that is, for all first-order structures)
• Vopěnka's principle for graphs
• Vopěnka's principle for partial orders
• Vopěnka's principle for fields
• Vopěnka's principle for rings
• Vopěnka's principle for groups

are all equivalent, because we can code any first-order structure into a graph or a partial order in such a way that an elementary embedding of the coding structure will also be an elementary embedding of the original structure. That is, given a structure $M$ we can find a graph $\Gamma_M$, such that there is a definable set of nodes representing the elements of $M$ and the operations applied to those elements. Thus, if $j:\Gamma_M\to \Gamma_{M'}$ is elementary, we can find a corresponding elementary map $h:M\to M'$.

Similarly, graphs can be coded into fields, which are contained in the rings, and I believe that one can also code structure into groups and many other kinds of mathematical objects.

I'm less sure, however, about coding structure into linear orders.

• Yes, the reason I picked linear orders is that it is unclear what kind of coding power they have - for example, if $X\subseteq\omega$ is computable in every copy of some countable linear order $L$, then $X$ is computable (Richter); on the other hand, isomorphism for linear orders is Borel complete (folklore?). – Noah Schweber Apr 22 '15 at 13:38
• @Joel David Hamkins "[...] and I believe that one can also code structure into groups" -- An equivalent statement of Vopenka's Principle in the category of GROUPS is described in arxiv.org/abs/0912.0510 (Adv. Math. 225 (2010) 1893−1913) and in the category of ABELIAN GROUPS in arxiv.org/abs/1104.5689 (Adv. Math. 257 (2014) 527−545). The latter solved a problem of Isbell - it was unexpected that one could encode Vopěnka by ABELIAN GROUPS. Another comment - the very first formulation of Vopěnka was for graphs. – Adam Przeździecki Apr 22 '15 at 14:21
• @AdamPrzeździecki that's a fascinating result about abelian groups - it doesn't answer my question fully, but if you post it as an answer I'll vote it up. – Noah Schweber Apr 23 '15 at 5:04
• I'd just like to note that the kind of coding that is being done here is, I think, full embeddings from one category into another, since "VP for category C" is equivalent to "Ord cannot be fully embedded into C" which of course means that if A and B can be fully embedded in each other (like the groups can be with the abelian groups) then VP for A is the same as VP for B. – Keith Millar Dec 8 '19 at 7:25