15
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ Probably too trivial, but in the language of equality we can prove Vopenka's Principle. $\endgroup$ – Asaf Karagila Apr 22 '15 at 14:40
  • 2
    $\begingroup$ 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. $\endgroup$ – Joel David Hamkins Apr 22 '15 at 18:11
  • $\begingroup$ @JoelDavidHamkins quite right, fixed. $\endgroup$ – Noah Schweber Apr 23 '15 at 5:05
  • $\begingroup$ @AsafKaragila yes, that's why I say that the pure sets provide a trivial example. $\endgroup$ – Noah Schweber Apr 23 '15 at 5:06
15
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ What is $0^\sharp$? :-| $\endgroup$ – Mariano Suárez-Álvarez Apr 23 '15 at 2:55
  • $\begingroup$ @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. $\endgroup$ – Joel David Hamkins Apr 23 '15 at 3:00
  • $\begingroup$ 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^+}$. $\endgroup$ – Miha Habič Apr 23 '15 at 3:12
  • $\begingroup$ @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. $\endgroup$ – Joel David Hamkins Apr 23 '15 at 11:15
11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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?). $\endgroup$ – Noah Schweber Apr 22 '15 at 13:38
  • 7
    $\begingroup$ @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. $\endgroup$ – Adam Przeździecki Apr 22 '15 at 14:21
  • 2
    $\begingroup$ @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. $\endgroup$ – Noah Schweber Apr 23 '15 at 5:04
  • 1
    $\begingroup$ 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. $\endgroup$ – Keith Millar Dec 8 '19 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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