# Vopenka's Principle for non-first-order logics

(For simplicity, the background theory for this post is NBG, a set theory directly treating proper classes which is a conservative extension of ZFC.)

Vopenka's Principle ($VP$) states that, given any proper class $\mathcal{C}$ of structures in the same (set-sized, relational) signature $\Sigma$, there are some distinct $A, B\in\mathcal{C}$ such that $A$ is isomorphic to an elementary substructure of $B$. In terms of consistency, we have the following rough upper and lower bounds: $$\text{proper class of extendibles \le Vopenka's Principle \le almost huge.}$$ (I don't know if this is state-of-the-art; more precise bounds, if known, would be welcome!) Thus, even though on the face of it $VP$ does not directly talk about cardinals, it is generally thought of as a large cardinal axiom.

Now, abstract model theory appears to give a framework for generalizing VP. Let $\mathcal{L}$ be any regular logic$^*$; then we can study "Vopenka's Principle for $\mathcal{L}$," $VP(\mathcal{L})\equiv$ "For any proper class $\mathcal{C}$ of $\Sigma$-structures ($\Sigma$ a set-sized relational signature), there are distinct $A, B\in\mathcal{C}$ with $A$ $\mathcal{L}$-elementarily embeddable into $B$." So, for example, taking $\mathcal{L}_I$ to denote first-order logic, $VP$ is just $VP(\mathcal{L}_I)$.

In principle, the resulting principles could have wildly varying large cardinal strengths. In practice, however, this seems to be extremely false.

Weaker Versions: Harvey Freidman has proved (see http://www.cs.nyu.edu/pipermail/fom/2005-August/009023.html) that $VP(\mathcal{L}_I)$ is equivalent to the statement that given any appropriate proper class $\mathcal{C}$ of structures, there are distinct $A$, $B\in\mathcal{C}$ such that $A$ is embeddable (NOT elementarily) into $B$. So $VP(\mathcal{L}_I)$ is equivalent to VP for the quantifier-free fragment of first-order logic.

Stronger Versions: Two reasonable logics to look at for stronger versions of $VP$ are $\mathcal{L}_{II}$ and $\mathcal{L}_{\omega_1\omega}$, second-order and (the smallest standard) infinitary logic respectively. However, the corresponding Vopenka principles are still just as strong as $VP(\mathcal{L}_I)$.$^{**}$ In general, $VP(\mathcal{L}_I)$ seems to be an upper bound for Vopenka's Principles for locally set-sized, definable logics. Since non-definable logics are of limited interest, it's reasonable to look at class-sized logics. The tamest class-sized logic I know of is $\mathcal{L}_{\infty\omega}$, the infinitary logic allowing arbitrary set-sized Boolean combinations but no infinite strings of quantifiers. However, $VP(\mathcal{L}_{\infty\omega})$ is inconsistent: by a famous theorem of Carol Karp, two structures are $\mathcal{L}_{\infty\omega}$-equivalent if and only if they are back-and-forth equivalent, so the class $\mathcal{O}$ of all ordinals (regarded as linear orderings) is a counterexample in any model of $ZFC$.

This all suggests that there are probably no interesting versions of Vopenka's Principle stronger than the usual one, and that any weaker form of Vopenka has to come from a horribly weak - to the point of being probably uninteresting - logic. I find this kind of disappointing. So, my question is:

Are there any interesting logics $\mathcal{L}$ for which $VP(\mathcal{L})$ is different from the usual Vopenka's Principle?

$^*$ The definition of "regular logic" is long and tedious, but it can be found in Ebbinghaus and Flum's book "Mathematical Logic" (Definitions 12.1.2 and 12.1.3). For this post, the details don't really matter; the key points are that the structures considered are the same as for first-order logic, and that everything is classical (i.e., two truth values).

$^{**}$ The proof for $\mathcal{L}_{II}$ goes as follows. Suppose $V\models VP(\mathcal{L}_I)$, and let $\mathcal{C}\in V$ be a proper class of structures in a set-sized relational signature $\Sigma$. Let $\Sigma'$ be the signature consisting of $\Sigma$ together with a new unary relation symbol $S$ and a new binary relation symbol $E$. In $V$, we can construct the class $\mathcal{C}'$ of structures of the form $$A':= A\sqcup (\mathcal{P}(A)\times\lbrace A\rbrace), \quad S^{A'}=\mathcal{P}(A)\times\lbrace A\rbrace, \quad E^{A'}=\lbrace (a, b): a\in A, b=(X, A), a\in X\rbrace$$ for $A\in\mathcal{C}$. Now second-order quantification over a structure in $\mathcal{C}$ can be replaced with first-order quantification over the $S$-part of the corresponding structure in $\mathcal{C}'$. So if $A'$ is first-order elementarily embeddable into $B'$, $A$ must be second-order elementarily embeddable into $B$, so since $V\models VP(\mathcal{L}_I)$ we're done. The proof for $\mathcal{L}_{\omega_1\omega}$ follows similar lines.

-
Issues closely related to more precise consistency strength bounds are addressed by Norman Perlmutter, see his recent preprint The large cardinals between supercompact and almost-huge. In particular, he shows that a cardinal is Vopěnka iff it is Woodin-for-supercompactness (as suggested by Kanamori). – Andrés Caicedo Aug 8 '13 at 1:36

Here is one example where changing the logic leads to inequivalent formulations of Vopenka's principle, but it is a different kind of change in the logic than you describe.

Namely, the change has to do with how one treats classes in set theory. In Gödel-Bernays GBC set theory, it is natural to formalize it as you did, as a single assertion in GBC making a claim about every class. In ZFC, however, set theorists usually consider classes as definable classes only, and so it is natural to formalize Vopenka's principle as a scheme of assertions, one statement for each definable class (as the assertion that for any parameters to be used with that definition, if it defines an Ord-length sequence of structures, then the Vopenka statement holds for it).

Since augmenting any ZFC model with only its definable classes makes it into a GB model (one should force global choice first, if necessary, to get GBC), it might seem that the difference in these formulations wouldn't matter much. But in fact, the two formulations of VP are different, as I argued in my answer to Mike Shulman's question, Can Vopenka's principle be violated definably?. What I proved there is that there can be a model of GBC satisfying the definable version of the Vopenka principle (the scheme), but not the full version in GBC. And the same issue applies to the concept of Vopenka cardinals, giving rise to the notion of almost-Vopenka cardinals.

The end result is that the first-order formulation of VP in ZFC is strictly weaker than the second-order formulation of VP in GBC.

-
This raises the question as to which of these is equivalent to the category theoretic formulation in terms of large discrete categories... – David Roberts Aug 8 '13 at 22:35
I think the answer to that is that it depends on how one treats class-sized objects in the category theory. I believe that there are analogues of definable classes and GBC style classes in category theory, and many category-theoretic issues (e.g. Is there a logical engdofunctor of Set?), depend on those distinctions. – Joel David Hamkins Aug 8 '13 at 23:09

Since the title of your question is, "Vopenka's Principle for non-first-order logics", this, from Magidor's and Vaananen's paper "On Lowenheim-Skolem-Tarski numbers for extensions of first order logic", might be of some relevance:

"Definition 3: Let $\tau$ be a fixed vocabulary. A logic $L$ consists of

1. A set, also denoted by $L$, of "formulas" of $L$. If $\phi$$\in$$L$, then there is a natural number $n_{\phi}$, called the of the sequence of free variables,

2. A relation $\mathcal A$$\vDash$$\phi$[$a_0$,...,$a_{n_{\phi}-1}$] between models of vocabulary $\tau$, sequences ($a_0$,...,$a_{n_{\phi}-1})$ of elements of A and formulas $\phi$$\in$$L$. It is assumed that this relation satisfies the isomorphism axiom, that is, if $\pi$: $\mathcal A$$\cong$$\mathcal B$, then $\mathcal A$$\vDash$$\phi$[$a_0$,...,$a_{n_{\phi}-1}]$ and $\mathcal B$$\vDash \phi[\pi$$a_0$,...,$\pi$$a_{n_{\phi}-1}] are equivalent. We call \tau the vocabulary of the logic L. Definition 4: The Lowenheim-Skolem number LS(L) of L is the smallest cardinal \kappa such that if a theory T$$\subset$$L has a model, it has a model of cardinality \lt max(\kappa,|T|). The Lowenheim-Skolem-Tarski number LST(L) of L is the smallest cardinal \kappa such that if \mathcal A is any \tau-structure, then there is a substructure \mathcal A^{'} of \mathcal A of cardinality \lt$$\kappa$ such that $\mathcal A^{'}$$\prec_{L}$$\mathcal A$."

I can now state their characterization of Vopenka's Principle:

"Theorem 6: Vopenka's Principle holds if and only if every logic has a Lowenheim-Skolem-Tarski number." I leave it for you to decide whether this characterization of Vopenka's Principle is different enough from the usual Vopenka's Principle to adequately answer your question.

-
So, this is not directly related to my specific question - my question was not whether there were alternate characterizations of VP (of which there are lots), or even whether there were any in terms of abstract logics, but specifically whether the specific principles of the form $VP(L)$ were distinct for reasonable natural $L$. Still, this is interesting, so +1. – Noah Schweber Jul 18 '15 at 18:22
By the way, a note about the proof of their Theorem 6: one direction is immediate. Suppose every logic has a LST number, and fix a proper class $C$ of structures. We can now build a silly logic $L_C$ containing first-order logic with a sentence which holds in exactly the structures in $C$. The existence of an LST number of $C$ then immediately implies the existence of lots of nontrivial elementary embeddings in $C$. The nontrivial direction is showing that VP is strong enough to produce LST numbers; for this, Magidor and Vaananen use a version of supercompactness. – Noah Schweber Jul 18 '15 at 18:25
@NoahSchweber: When you ask "whether the specific principles of the form $VP(L)$" are "distinct for reasonable natural $L$", what sort of 'distinctness' would you hope to find, if such 'distinctness' did, in fact, exist (perhaps Thm. 6 suggests that there might not be any versions of $VP$ stronger than the usual one)? – Thomas Benjamin Jul 19 '15 at 1:08
As usually when discussing large-cardinal-like principles, I mean distinct in terms of provable equivalence over ZFC (or related theories), or - even better! - in terms of consistency strength over ZFC (see OP paragraph beginning "in principle"). This is not directly addressed by the result you cite - in particular, it is not clear that "$L$ has a LST number" implies $VP(L)$ (consider non-$L$-elementary classes of structures; $LST(L)$ isn't directly useful here). – Noah Schweber Jul 19 '15 at 3:04
How about first-order logic, assuming $\neg VP$? :P – Noah Schweber Jul 19 '15 at 4:11