16
$\begingroup$

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

Vopěnka'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$ Vopěnka'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 "Vopěnka'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 Vopěnka principles are still just as strong as $VP(\mathcal{L}_I)$.$^{**}$ In general, $VP(\mathcal{L}_I)$ seems to be an upper bound for Vopěnka'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 Vopěnka's Principle stronger than the usual one, and that any weaker form of Vopěnka 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 Vopěnka'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.

$\endgroup$
6
  • 2
    $\begingroup$ 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). $\endgroup$ Aug 8, 2013 at 1:36
  • $\begingroup$ The statement attributed to Friedman in 2005 in the question and many similar statements too were already systematically studied in Ch 6 of Adamek and Rosicky's 1994 book Locally Presentable and Accessible Categories. For a lower bound, they show for example that Vopenka's principle is equivalent to the statement that for any proper class of graphs, one embeds (not elementarily) in another. At the upper end, Vopenka's principle implies that for any proper class of objects in an accessible category, one admits a nonidentity map to another. This includes all AECs for example. $\endgroup$
    – Tim Campion
    Sep 6, 2018 at 23:54
  • $\begingroup$ For a trivial lower bound, note that if $\mathcal L$ is pretty much any form of (set-sized) propositional logic, then $VP(\mathcal L)$ is a theorem of ZFC: there are only set-many models, so if you have a class of them two must agree. $\endgroup$
    – Tim Campion
    Mar 8, 2021 at 22:42
  • $\begingroup$ @TimCampion Propositional logics aren't regular logics in the sense of the question, though. $\endgroup$ Mar 8, 2021 at 22:43
  • $\begingroup$ Okay. If Ebbinghaus and Flum's definition doesn't include propositional logics, I might want to find a more flexible definition, but I suppose that's a matter of taste. $\endgroup$
    – Tim Campion
    Mar 8, 2021 at 22:46

3 Answers 3

3
$\begingroup$

This is a really late answer, but the answer to your question is "No." As a dual to the Theorem 6 that Thomas Benjamin mentions above (which I believe is a result of Stavi), Janos Makowsky proved that Vopěnka's Principle is equivalent to the statement "All logics have a compactness cardinal."

$\endgroup$
2
  • $\begingroup$ The caron is over the "e" not the "o". Also, \v{o} won't compile here. :-) $\endgroup$
    – Asaf Karagila
    Apr 15, 2021 at 8:23
  • $\begingroup$ Just saw this, nice! $\endgroup$ Aug 21, 2022 at 2:31
11
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ Jul 18, 2015 at 18:22
  • $\begingroup$ 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. $\endgroup$ Jul 18, 2015 at 18:25
  • 1
    $\begingroup$ @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)? $\endgroup$ Jul 19, 2015 at 1:08
  • $\begingroup$ 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). $\endgroup$ Jul 19, 2015 at 3:04
  • 1
    $\begingroup$ How about first-order logic, assuming $\neg VP$? :P $\endgroup$ Jul 19, 2015 at 4:11
9
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ This raises the question as to which of these is equivalent to the category theoretic formulation in terms of large discrete categories... $\endgroup$
    – David Roberts
    Aug 8, 2013 at 22:35
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 8, 2013 at 23:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.