Return to Answer

The weak Vopěnka principle (WVP) and semi-weak Vopěnka principle (SWVP) are both equivalent to the large cardinal principle "Ord is Woodin". These results now appear in a paper on the ArXiV. I kept the proof that Ord is Woodin implies SWVP as part of this MathOverflow answer (see below), but removed the outline of the proof that WVP implies Ord is Woodin because the paper contains a better proof of that now.

I will use the form of WVP which says that the opposite of the category of ordinals cannot be fully embedded in the category of graphs. In other words, there is no sequence of graphs $(G_\alpha : \alpha < \mathrm{Ord})$ such that for all $\alpha < \beta$ there is no homomorphism from $G_\alpha$ to $G_\beta$, and for all $\alpha \le \beta$ there is a unique homomorphism from $G_\beta$ to $G_\alpha$.

SWVP (see Adámek and Rosický, On Injectivity in Locally Presentable Categories) says that there is no sequence of graphs $(G_\alpha : \alpha < \mathrm{Ord})$ such that for all $\alpha < \beta$ there is no homomorphism from $G_\alpha$ to $G_\beta$, and for all $\alpha \le \beta$ there is at least one homomorphism from $G_\beta$ to $G_\alpha$.

For every similarity type consisting of finitary relation symbols, the category of all structures of this type can be fully embedded into the category of graphs (see Hedrlín and Pultr, On full embeddings of categories of algebras,) so replacing graphs by more general relational structures yields equivalent statements of WVP and SWVP.

"Ord is Woodin" means that for every class $A$ there is an $A$-strong cardinal. See Kanamori, The Higher Infinite for the definition of $A$-strong cardinal. For maximum generality, we work in GB + AC. (As a special case, the results hold in ZFC for definable classes $A$.)

Proof that Ord is Woodin implies SWVP.

Assume Ord is Woodin and let $(G_\alpha : \alpha \in \mathrm{Ord})$ be a sequence of graphs such that for all $\alpha \le \beta$ there is at least one homomorphism from $G_\beta$ to $G_\alpha$. We will show that for some ordinal $\kappa$ there is a homomorphism from $G_\kappa$ to $G_{\kappa+1}$.

We can write $G_\alpha = G(\alpha)$ where $G$ is a class function with domain Ord. Because Ord is Woodin, some cardinal $\kappa$ is $G$-strong. Take a cardinal $\beta$ greater than $\kappa$ and greater than the von Neumann rank of the graph $G(\kappa+1)$, meaning $G(\kappa+1) \in V_\beta$. Because $\kappa$ is $\beta$-$G$-strong, there is a transitive class $M$ containing $V_\beta$ and an elementary embedding $j : (V;\in) \to (M;\in)$ such that the critical point of $j$ is $\kappa$ and $V_\beta \subset M$ and $j(\kappa) > \beta$ and $j(G) \restriction \beta = G \restriction \beta$. We describe the latter condition by saying that $j$ coheres with $G$.

Because $j$ coheres with $G$, the graph $G(\kappa+1)$ is equal to $j(G)(\kappa+1)$, so it is on the sequence $j(G)$, which is an Ord-sequence of graphs in $M$. Note that $j(G(\kappa)) = j(G)(j(\kappa))$ by the elementarity of $j$, so the graph $j(G(\kappa))$ is also on the sequence $j(G)$. We have $j(\kappa) > \kappa+1$, so by our assumption on the sequence $G$ and the elementarity of $j$, we have a homomorphism $j(G(\kappa)) \to G(\kappa+1)$ in $M$ and therefore in $V$. We also have a homomorphism $G(\kappa) \to j(G(\kappa))$ in $V$ given by $j \restriction G(\kappa)$. Composing these, we obtain a homomorphism $G(\kappa) \to G(\kappa+1)$, as desired.

The weak Vopěnka principle (WVP) and semi-weak Vopěnka principle (SWVP) are both equivalent to the large cardinal principle "Ord is Woodin". These results now appear in a paper on the arXiv. I kept the proof that Ord is Woodin implies SWVP as part of this MathOverflow answer (see below), but removed the outline of the proof that WVP implies Ord is Woodin because the paper contains a better proof of that now.

I will use the form of WVP which says that the opposite of the category of ordinals cannot be fully embedded in the category of graphs. In other words, there is no sequence of graphs $(G_\alpha : \alpha < \mathrm{Ord})$ such that for all $\alpha < \beta$ there is no homomorphism from $G_\alpha$ to $G_\beta$, and for all $\alpha \le \beta$ there is a unique homomorphism from $G_\beta$ to $G_\alpha$.

SWVP (see Adámek and Rosický, On Injectivity in Locally Presentable Categories) says that there is no sequence of graphs $(G_\alpha : \alpha < \mathrm{Ord})$ such that for all $\alpha < \beta$ there is no homomorphism from $G_\alpha$ to $G_\beta$, and for all $\alpha \le \beta$ there is at least one homomorphism from $G_\beta$ to $G_\alpha$.

For every similarity type consisting of finitary relation symbols, the category of all structures of this type can be fully embedded into the category of graphs (see Hedrlín and Pultr, On full embeddings of categories of algebras,) so replacing graphs by more general relational structures yields equivalent statements of WVP and SWVP.

"Ord is Woodin" means that for every class $A$ there is an $A$-strong cardinal. See Kanamori, The Higher Infinite for the definition of $A$-strong cardinal. For maximum generality, we work in GB + AC. (As a special case, the results hold in ZFC for definable classes $A$.)

Proof that Ord is Woodin implies SWVP.

Assume Ord is Woodin and let $(G_\alpha : \alpha \in \mathrm{Ord})$ be a sequence of graphs such that for all $\alpha \le \beta$ there is at least one homomorphism from $G_\beta$ to $G_\alpha$. We will show that for some ordinal $\kappa$ there is a homomorphism from $G_\kappa$ to $G_{\kappa+1}$.

We can write $G_\alpha = G(\alpha)$ where $G$ is a class function with domain Ord. Because Ord is Woodin, some cardinal $\kappa$ is $G$-strong. Take a cardinal $\beta$ greater than $\kappa$ and greater than the von Neumann rank of the graph $G(\kappa+1)$, meaning $G(\kappa+1) \in V_\beta$. Because $\kappa$ is $\beta$-$G$-strong, there is a transitive class $M$ containing $V_\beta$ and an elementary embedding $j : (V;\in) \to (M;\in)$ such that the critical point of $j$ is $\kappa$ and $V_\beta \subset M$ and $j(\kappa) > \beta$ and $j(G) \restriction \beta = G \restriction \beta$. We describe the latter condition by saying that $j$ coheres with $G$.

Because $j$ coheres with $G$, the graph $G(\kappa+1)$ is equal to $j(G)(\kappa+1)$, so it is on the sequence $j(G)$, which is an Ord-sequence of graphs in $M$. Note that $j(G(\kappa)) = j(G)(j(\kappa))$ by the elementarity of $j$, so the graph $j(G(\kappa))$ is also on the sequence $j(G)$. We have $j(\kappa) > \kappa+1$, so by our assumption on the sequence $G$ and the elementarity of $j$, we have a homomorphism $j(G(\kappa)) \to G(\kappa+1)$ in $M$ and therefore in $V$. We also have a homomorphism $G(\kappa) \to j(G(\kappa))$ in $V$ given by $j \restriction G(\kappa)$. Composing these, we obtain a homomorphism $G(\kappa) \to G(\kappa+1)$, as desired.

The weak Vopěnka principle (WVP) seems to be equivalent to the large cardinal principle "Ord is Woodin", and also to the semi-weak Vopěnka principle (SWVP), by a proof that I will outline below. From what I can tell, all that was previously known about the relationship between WVP, SWVP, and large cardinals is that VP implies SWVP, SWVP implies WVP, and WVP implies there is a proper class of measurable cardinals.

"Ord is Woodin" means that for every class $A$ there is an $A$-strong cardinal. See Kanamori, The Higher Infinite for the definition of $A$-strong cardinal and a reformuation in terms of extenders. For maximum generality, we work in GBC. (The proof also works in ZFC for definable classes $A$.)

Because $j$ coheres with $G$, the graph $G(\kappa+1)$ is equal to $j(G)(\kappa+1)$, so it is on the sequence $j(G)$, which is an Ord-sequence of graphs in $M$. Note that $j(G(\kappa)) = j(G)(j(\kappa))$ by the elementarity of $j$, so the graph $j(G(\kappa))$ is also on the sequence $j(G)$. We have $j(\kappa) > \kappa+1$, so by our assumption on the sequence $G$ and the elementarity of $j$, we have a homomorphism $j(G(\kappa)) \to G(\kappa+1)$ in $M$ and therefore in $V$. We also have a homomorphism $G(\kappa) \to j(G(\kappa))$ in $V$ given by $j \restriction G(\kappa)$. Composing these, we obtain a homomorphism $G(\kappa) \to G(\kappa+1)$, as desired.

Proof that WVP implies Ord is Woodin.

(This is a bit more complicated. I haven't fully checked the details, so some skepticism is warranted.)

Assume that there is a class $A$ such that there is no $A$-strong cardinal. We will construct an Ord-sequence of relational structures that is a counterexample to the WVP. Let $C$ be the class of all cardinals $\lambda$ such that $\beth_\lambda = \lambda$ and no cardinal $\kappa < \lambda$ is $\lambda$-$A$-strong. By our anti-large cardinal hypothesis, $C$ is a proper class (in fact a club class.) Each element of $C$ will be used to define a corresponding relational structure.

Let $\mathcal{L}$ be the language of set theory with an additional unary predicate for $A$. We will use the letter $\varphi$ to denote $\mathcal{L}$-formulas. For a formula $\varphi \in \Sigma_1$ (denoting complexity in terms of the Levy hierarchy) with $n$ free variables, we may define a corresponding $n$-ary relation on $V$ by $$R_\varphi = \{(x_1,\ldots,x_n) : (V;\in,A) \models \varphi[x_1,\ldots,x_n].$$ (The limitation on the complexity of $\varphi$ allows us to avoid metamathematical complications here.) For every cardinal $\lambda$, we define an equivalence relation $\sim_\lambda$ on $V$ by $x \sim_\lambda y \iff x \cap \lambda = y \cap \lambda$.

Now we can define an Ord-sequence of relational structures $(\mathcal{M}_\alpha : \alpha \in \mathrm{Ord})$ that is a counterexample to WVP. For every ordinal $\alpha$, we define the structure $$\mathcal{M}_\alpha = (V;R_\varphi, \mathord{Ord}\setminus \alpha)_{\varphi \in \Sigma_1}\big/\mathord{\sim}_{\lambda_\alpha},$$ where $\mathord{Ord}\setminus \alpha$ is a unary relation consisting of all ordinals $\ge \alpha$, and $\lambda_\alpha$ is the least element of $C$ that is strictly greater than $\alpha$. (Note that although we started with a proper-class-sized structure, taking the quotient by $\mathord{\sim}_{\lambda_{\alpha}}$ results in a set-sized structure of cardinality $2^{\lambda_{\alpha}}$.)

Lemma. For every $\lambda \in C$, every homomorphism $h : (V;R_\varphi)_{\varphi \in \Sigma_1} \to (V;R_\varphi)_{\varphi \in \Sigma_1} / \mathord{\sim}_\lambda$, and every $x \in V$, we have $h(x) = [x]_{\mathord{\sim}_\lambda}$. (The only homomorphism is the quotient map.)

Sketch of proof. Assume toward a contradiction that $h(x) \ne [x]_{\mathord{\sim}_\lambda}$ for some $x$. Then we have $h(x) = [y]_{\mathord{\sim}_\lambda}$ for some $y \not\sim_\lambda x$, meaning there is some ordinal $\alpha < \lambda$ such that $\alpha \in x \iff \alpha \notin y$. Because $h$ is a homomorphism, this implies $h(\alpha) \ne [\alpha]_{\mathord{\sim}_\lambda}$ as well. Define $\kappa$ to be the least ordinal such that $h(\kappa) \ne [\kappa]_{\mathord{\sim}_\lambda}$. Then $\kappa < \lambda$ and $h(\kappa) = [\kappa']_{\mathord{\sim}_\lambda}$ for some ordinal $\kappa'$ such that $\kappa < \kappa' \le \lambda$. (Note that every ordinal above $\lambda$ is equivalent to $\lambda$ itself.) Define $\zeta = \{\alpha < \lambda : h(\alpha) \ne [\lambda]_{\sim_\lambda}\}$. Note that $\zeta$ is an initial segment of $\lambda$ and is therefore an ordinal, and we have $\kappa \le \zeta \le \lambda$ and $h(\zeta) = [\lambda]_{\sim_\lambda}$. (In the typical "short extender" case we just have $\zeta = \kappa$.) Although $h$ is not an elementary embedding, $\kappa$ behaves somewhat like the critical point of an elementary embedding, and we can adapt the usual argument to get a $(\kappa,\lambda)$-extender "induced" by $h$ (the existence of which contradicts our anti-large-cardinal hypothesis) as follows. For all $a \in [\lambda]^{\mathord{<}\omega}$ we can define $E_a \subset \mathcal{P}([\zeta]^{|a|})$ by $X \in E_a \iff a \in Y$ for some (equivalently, for all) $Y$ such that $[Y]_{{\sim}_\lambda} = h(X)$. Then each $E_a$ is a $\kappa$-complete measure on $[\zeta]^{|a|}$, and $(E_a : a \in [\lambda]^{\mathord{<}\omega})$ is an extender witnessing that $\kappa$ is $\lambda$-$A$-strong, which is a contradiction. (There are some details to check here.)

Now we will use the lemma to show that $(\mathcal{M}_\alpha : \alpha \in \mathrm{Ord})$ is a counterexample to WVP:

Claim 1. For all $\alpha < \beta \in \mathrm{Ord}$, there is no homomorphism $\mathcal{M}_\alpha \to \mathcal{M}_\beta$.

Proof. Suppose toward a contradiction that there are $\alpha < \beta$ and a homomorphism $h: \mathcal{M}_\alpha \to \mathcal{M}_\beta$. Forgetting about the unary relations $\mathord{Ord}\setminus \alpha$ and $\mathord{Ord}\setminus \beta$, we can regard $h$ as a homomorphism $(V;R_\varphi)_{\varphi \in \Sigma_1}/\mathord{\sim}_{\lambda_\alpha} \to (V;R_\varphi)_{\varphi \in \Sigma_1}/\mathord{\sim}_{\lambda_\beta}$. Moreover, because the unary relation was preserved, we have $h([\alpha]_{\mathord{\sim}_{\lambda_\alpha}}) \ne [\alpha]_{\mathord{\sim}_{\lambda_\beta}}$. Therefore composing $h$ with the quotient map $(V;R_\varphi)_{\varphi \in \Sigma_1} \to (V;R_\varphi)_{\varphi \in \Sigma_1}/\mathord{\sim}_{\lambda_\alpha}$ gives a homomorphism $(V;R_\varphi)_{\varphi \in \Sigma_1} \to (V;R_\varphi)_{\varphi \in \Sigma_1}/\mathord{\sim}_{\lambda_\beta}$ that is not the quotient map, contradicting the lemma.

Claim 2. For all $\alpha \le \beta \in \mathrm{Ord}$, there is only one homomorphism $\mathcal{M}_\beta \to \mathcal{M}_\alpha$, namely the quotient map given by the fact that $\mathord{\sim}_{\lambda_\beta} \subset \mathord{\sim}_{\lambda_\alpha}$.

Suppose toward a contradiction that there are $\alpha \le \beta$ and a homomorphism $h: \mathcal{M}_\beta \to \mathcal{M}_\alpha$ that is not the quotient map. For this part we don't need the unary relations $\mathord{Ord}\setminus \beta$ and $\mathord{Ord}\setminus \alpha$ at all. We can regard $h$ as a homomorphism $(V;R_\varphi)_{\varphi \in \Sigma_1}/\mathord{\sim}_{\lambda_\beta} \to (V;R_\varphi)_{\varphi \in \Sigma_1}/\mathord{\sim}_{\lambda_\alpha}$. Composing $h$ with the quotient map $(V;R_\varphi)_{\varphi \in \Sigma_1} \to (V;R_\varphi)_{\varphi \in \Sigma_1}/\mathord{\sim}_{\lambda_\beta}$ gives a homomorphism $(V;R_\varphi)_{\varphi \in \Sigma_1} \to (V;R_\varphi)_{\varphi \in \Sigma_1}/\mathord{\sim}_{\lambda_\alpha}$ that is not the quotient map, contradicting the lemma again.

The weak Vopěnka principle (WVP) and semi-weak Vopěnka principle (SWVP) are both equivalent to the large cardinal principle "Ord is Woodin". These results now appear in a paper on the ArXiV. I kept the proof that Ord is Woodin implies SWVP as part of this MathOverflow answer (see below), but removed the outline of the proof that WVP implies Ord is Woodin because the paper contains a better proof of that now.

"Ord is Woodin" means that for every class $A$ there is an $A$-strong cardinal. See Kanamori, The Higher Infinite for the definition of $A$-strong cardinal. For maximum generality, we work in GB + AC. (As a special case, the results hold in ZFC for definable classes $A$.)

Because $j$ coheres with $G$, the graph $G(\kappa+1)$ is equal to $j(G)(\kappa+1)$, so it is on the sequence $j(G)$, which is an Ord-sequence of graphs in $M$. Note that $j(G(\kappa)) = j(G)(j(\kappa))$ by the elementarity of $j$, so the graph $j(G(\kappa))$ is also on the sequence $j(G)$. We have $j(\kappa) > \kappa+1$, so by our assumption on the sequence $G$ and the elementarity of $j$, we have a homomorphism $j(G(\kappa)) \to G(\kappa+1)$ in $M$ and therefore in $V$. We also have a homomorphism $G(\kappa) \to j(G(\kappa))$ in $V$ given by $j \restriction G(\kappa)$. Composing these, we obtain a homomorphism $G(\kappa) \to G(\kappa+1)$, as desired.

The weak Vopěnka principle (WVP) seems to be equivalent to the large cardinal principle "Ord is Woodin" by a proof that I will outline below. As far as I know, both directions are new.

It will be useful to observe that for every similarity type consisting of finitary relation symbols, the category of all structures of this type can be fully embedded into the category of graphs (Hedrlín and Pultr, On full embeddings of categories of algebras,) so replacing graphs by more general relational structures yields an equivalent statement of WVP.

Proof that Ord is Woodin implies WVP.

Assume Ord is Woodin. We will prove the following statement, which clearly implies WVP:

(S) For every sequence of graphs $(G_\alpha : \alpha \in \mathrm{Ord})$, if there is a homomorphism $G_\beta \to G_\alpha$ for all $\alpha < \beta \in Ord$, then there is a homomorphism $G_\kappa \to G_{\kappa + 1}$ for some $\kappa \in Ord$.

(As a consequence, we will end up showing that statement S is equivalent to WVP. I don't know whether this equivalence was already known, or whether it can be proved without involving Woodinness.)

Let $(G_\alpha : \alpha \in \mathrm{Ord})$ be a sequence of graphs as in statement S. We can write $G_\alpha = G(\alpha)$ where $G$ is a class function with domain Ord. Because Ord is Woodin, some cardinal $\kappa$ is $G$-strong. Take a cardinal $\beta$ greater than $\kappa$ and greater than the von Neumann rank of the graph $G(\kappa+1)$, meaning $G(\kappa+1) \in V_\beta$. Because $\kappa$ is $\beta$-$G$-strong, there is a transitive class $M$ containing $V_\beta$ and an elementary embedding $j : (V;\in) \to (M;\in)$ such that the critical point of $j$ is $\kappa$ and $V_\beta \subset M$ and $j(\kappa) > \beta$ and $j(G) \restriction \beta = G \restriction \beta$. We describe the latter condition by saying that $j$ coheres with $G$.

Because $j$ coheres with $G$, the graph $G(\kappa+1)$ is equal to $j(G)(\kappa+1)$, so it is on the sequence $j(G)$, which is an Ord-sequence of graphs in $M$. Note that $j(G(\kappa)) = j(G)(j(\kappa))$ by the elementarity of $j$, so the graph $j(G(\kappa))$ is also on the sequence $j(G)$. We have $j(\kappa) > \kappa+1$, so by our assumption on the sequence $G$ and the elementarity of $j$, we have a homomorphism $j(G(\kappa)) \to G(\kappa+1)$ in $M$ and therefore in $V$. We also have a homomorphism $G(\kappa) \to j(G(\kappa))$ in $V$ given by $j \restriction G(\kappa)$. Composing these, we obtain a homomorphism $G(\kappa) \to G(\kappa+1)$. This proves statement S.

The weak Vopěnka principle (WVP) seems to be equivalent to the large cardinal principle "Ord is Woodin", and also to the semi-weak Vopěnka principle (SWVP), by a proof that I will outline below. From what I can tell, all that was previously known about the relationship between WVP, SWVP, and large cardinals is that VP implies SWVP, SWVP implies WVP, and WVP implies there is a proper class of measurable cardinals.

SWVP (see Adámek and Rosický, On Injectivity in Locally Presentable Categories) says that there is no sequence of graphs $(G_\alpha : \alpha < \mathrm{Ord})$ such that for all $\alpha < \beta$ there is no homomorphism from $G_\alpha$ to $G_\beta$, and for all $\alpha \le \beta$ there is at least one homomorphism from $G_\beta$ to $G_\alpha$.

For every similarity type consisting of finitary relation symbols, the category of all structures of this type can be fully embedded into the category of graphs (see Hedrlín and Pultr, On full embeddings of categories of algebras,) so replacing graphs by more general relational structures yields equivalent statements of WVP and SWVP.

Proof that Ord is Woodin implies SWVP.

Assume Ord is Woodin and let $(G_\alpha : \alpha \in \mathrm{Ord})$ be a sequence of graphs such that for all $\alpha \le \beta$ there is at least one homomorphism from $G_\beta$ to $G_\alpha$. We will show that for some ordinal $\kappa$ there is a homomorphism from $G_\kappa$ to $G_{\kappa+1}$.

We can write $G_\alpha = G(\alpha)$ where $G$ is a class function with domain Ord. Because Ord is Woodin, some cardinal $\kappa$ is $G$-strong. Take a cardinal $\beta$ greater than $\kappa$ and greater than the von Neumann rank of the graph $G(\kappa+1)$, meaning $G(\kappa+1) \in V_\beta$. Because $\kappa$ is $\beta$-$G$-strong, there is a transitive class $M$ containing $V_\beta$ and an elementary embedding $j : (V;\in) \to (M;\in)$ such that the critical point of $j$ is $\kappa$ and $V_\beta \subset M$ and $j(\kappa) > \beta$ and $j(G) \restriction \beta = G \restriction \beta$. We describe the latter condition by saying that $j$ coheres with $G$.

Because $j$ coheres with $G$, the graph $G(\kappa+1)$ is equal to $j(G)(\kappa+1)$, so it is on the sequence $j(G)$, which is an Ord-sequence of graphs in $M$. Note that $j(G(\kappa)) = j(G)(j(\kappa))$ by the elementarity of $j$, so the graph $j(G(\kappa))$ is also on the sequence $j(G)$. We have $j(\kappa) > \kappa+1$, so by our assumption on the sequence $G$ and the elementarity of $j$, we have a homomorphism $j(G(\kappa)) \to G(\kappa+1)$ in $M$ and therefore in $V$. We also have a homomorphism $G(\kappa) \to j(G(\kappa))$ in $V$ given by $j \restriction G(\kappa)$. Composing these, we obtain a homomorphism $G(\kappa) \to G(\kappa+1)$, as desired.