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)?
Best Answer
For (Q3), here is a class of structures whose VP is strictly intermediate in strength.
Theorem. The following are equivalent.
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}$.