Skip to main content
1 of 4
Noah Schweber
  • 21.2k
  • 10
  • 110
  • 331

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 (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.

Noah Schweber
  • 21.2k
  • 10
  • 110
  • 331