Skip to main content
added argument avoiding global choice
Source Link
Trevor Wilson
  • 5.5k
  • 29
  • 46

I think IAU is equivalent to Vopěnka's principle. For the other direction, assume Vopěnka's principle fails. Then there is a proper class of structures (WLOG graphs), none of which embeds into any other. Because this is a proper class, there is an injection of $\mathcal{L}_{\infty,\infty}$ into it. In other words, for each sentence $\sigma \in \mathcal{L}_{\infty,\infty}$ we may choose a structure $\mathcal{M}_\sigma$ in such a way that for any two distinct sentences $\sigma,\tau \in \mathcal{L}_{\infty,\infty}$, neither $\mathcal{M}_\sigma$ nor $\mathcal{M}_\tau$ embeds into the other.

Now we define the "diagonal" class of structures $D = \{\mathcal{M}_\sigma \mid \sigma \in \mathcal{L}_{\infty,\infty} \wedge \mathcal{M}_\sigma \not\models \sigma\}$. I claim that its upward closure $D\mathord{\uparrow}$ does not have the form $\operatorname{Mod}(\tau)$ for any sentence $\tau \in \mathcal{L}_{\infty,\infty}$. This is because $\mathcal{M}_\tau \in D\mathord{\uparrow} \iff \mathcal{M}_\tau \in D \iff \mathcal{M}_\tau \not\models \tau \iff \mathcal{M}_\tau \notin \operatorname{Mod}(\tau)$.

The key point is that $\mathcal{M}_\tau \in D\mathord{\uparrow}$ implies $\mathcal{M}_\tau \in D$ because no other structure $\mathcal{M}_\sigma \in D$ can embed into $\mathcal{M}_\tau$.

Edit: The argument can be modified to avoid relying on global choice, as follows.

Assume that we have a counterexample to Vopěnka's principle, meaning a proper class $\mathcal{C}$ of structures (WLOG graphs), none of which embeds into any other. For every sentence $\sigma \in \mathcal{L}_{\infty,\infty}$, define the structure $\mathcal{M}_\sigma = \langle V_\lambda; \in, \{\sigma\}, \mathcal{C} \cap V_\lambda\rangle$ for the least limit ordinal $\lambda$ that is greater than the rank of $\sigma$ (meaning just its Von Neumann rank as a set) and has the additional property that $A \cap \lambda$ has order type $\lambda$ where $A$ is the proper class of ordinals $\{\text{rank}(\mathcal{M}) \mid \mathcal{M}\in C\}$.

Note that for any two distinct sentences $\sigma, \tau \in \mathcal{L}_{\infty,\infty}$ there is no elementary embedding $j : \mathcal{M}_\sigma\to \mathcal{M}_\tau$. If there were, then letting $\kappa$ be the critical point of $j$ (which exists because $j$ maps $\sigma$ to $\tau$) and letting $\mathcal{M} \in \mathcal{C}$ be a structure of rank equal to the $\kappa$th element of $A$, the restriction $j \restriction \mathcal{M}$ is an embedding of $\mathcal{M}$ into some other structure $j(\mathcal{M}) \in \mathcal{C}$ whose rank equals the $j(\kappa)$th element of $A$ and which is therefore different from $\mathcal{M}$. This contradicts the assumption that $\mathcal{C}$ was a counterexample to Vopěnka's principle.

To remove the word "elementary" above and ensure that for any two distinct sentences $\sigma, \tau \in \mathcal{L}_{\infty,\infty}$ there is no embedding $j : \mathcal{M}_\sigma\to \mathcal{M}_\tau$, we just need to modify the structures $\mathcal{M}_\sigma$ in the usual way by adding a relation for every first-order formula. (I didn't want to complicate the notation with this when defining the structures initially.)

Then we can define the diagonal class of structures $D = \{\mathcal{M}_\sigma \mid \sigma \in \mathcal{L}_{\infty,\infty} \wedge \mathcal{M}_\sigma \not\models \sigma\}$ and show that its upward closure $D\mathord{\uparrow}$ does not have the form $\operatorname{Mod}(\tau)$ for any sentence $\tau \in \mathcal{L}_{\infty,\infty}$ as before.

I think IAU is equivalent to Vopěnka's principle. For the other direction, assume Vopěnka's principle fails. Then there is a proper class of structures (WLOG graphs), none of which embeds into any other. Because this is a proper class, there is an injection of $\mathcal{L}_{\infty,\infty}$ into it. In other words, for each sentence $\sigma \in \mathcal{L}_{\infty,\infty}$ we may choose a structure $\mathcal{M}_\sigma$ in such a way that for any two distinct sentences $\sigma,\tau \in \mathcal{L}_{\infty,\infty}$, neither $\mathcal{M}_\sigma$ nor $\mathcal{M}_\tau$ embeds into the other.

Now we define the "diagonal" class of structures $D = \{\mathcal{M}_\sigma \mid \sigma \in \mathcal{L}_{\infty,\infty} \wedge \mathcal{M}_\sigma \not\models \sigma\}$. I claim that its upward closure $D\mathord{\uparrow}$ does not have the form $\operatorname{Mod}(\tau)$ for any sentence $\tau \in \mathcal{L}_{\infty,\infty}$. This is because $\mathcal{M}_\tau \in D\mathord{\uparrow} \iff \mathcal{M}_\tau \in D \iff \mathcal{M}_\tau \not\models \tau \iff \mathcal{M}_\tau \notin \operatorname{Mod}(\tau)$.

The key point is that $\mathcal{M}_\tau \in D\mathord{\uparrow}$ implies $\mathcal{M}_\tau \in D$ because no other structure $\mathcal{M}_\sigma \in D$ can embed into $\mathcal{M}_\tau$.

I think IAU is equivalent to Vopěnka's principle. For the other direction, assume Vopěnka's principle fails. Then there is a proper class of structures (WLOG graphs), none of which embeds into any other. Because this is a proper class, there is an injection of $\mathcal{L}_{\infty,\infty}$ into it. In other words, for each sentence $\sigma \in \mathcal{L}_{\infty,\infty}$ we may choose a structure $\mathcal{M}_\sigma$ in such a way that for any two distinct sentences $\sigma,\tau \in \mathcal{L}_{\infty,\infty}$, neither $\mathcal{M}_\sigma$ nor $\mathcal{M}_\tau$ embeds into the other.

Now we define the "diagonal" class of structures $D = \{\mathcal{M}_\sigma \mid \sigma \in \mathcal{L}_{\infty,\infty} \wedge \mathcal{M}_\sigma \not\models \sigma\}$. I claim that its upward closure $D\mathord{\uparrow}$ does not have the form $\operatorname{Mod}(\tau)$ for any sentence $\tau \in \mathcal{L}_{\infty,\infty}$. This is because $\mathcal{M}_\tau \in D\mathord{\uparrow} \iff \mathcal{M}_\tau \in D \iff \mathcal{M}_\tau \not\models \tau \iff \mathcal{M}_\tau \notin \operatorname{Mod}(\tau)$.

The key point is that $\mathcal{M}_\tau \in D\mathord{\uparrow}$ implies $\mathcal{M}_\tau \in D$ because no other structure $\mathcal{M}_\sigma \in D$ can embed into $\mathcal{M}_\tau$.

Edit: The argument can be modified to avoid relying on global choice, as follows.

Assume that we have a counterexample to Vopěnka's principle, meaning a proper class $\mathcal{C}$ of structures (WLOG graphs), none of which embeds into any other. For every sentence $\sigma \in \mathcal{L}_{\infty,\infty}$, define the structure $\mathcal{M}_\sigma = \langle V_\lambda; \in, \{\sigma\}, \mathcal{C} \cap V_\lambda\rangle$ for the least limit ordinal $\lambda$ that is greater than the rank of $\sigma$ (meaning just its Von Neumann rank as a set) and has the additional property that $A \cap \lambda$ has order type $\lambda$ where $A$ is the proper class of ordinals $\{\text{rank}(\mathcal{M}) \mid \mathcal{M}\in C\}$.

Note that for any two distinct sentences $\sigma, \tau \in \mathcal{L}_{\infty,\infty}$ there is no elementary embedding $j : \mathcal{M}_\sigma\to \mathcal{M}_\tau$. If there were, then letting $\kappa$ be the critical point of $j$ (which exists because $j$ maps $\sigma$ to $\tau$) and letting $\mathcal{M} \in \mathcal{C}$ be a structure of rank equal to the $\kappa$th element of $A$, the restriction $j \restriction \mathcal{M}$ is an embedding of $\mathcal{M}$ into some other structure $j(\mathcal{M}) \in \mathcal{C}$ whose rank equals the $j(\kappa)$th element of $A$ and which is therefore different from $\mathcal{M}$. This contradicts the assumption that $\mathcal{C}$ was a counterexample to Vopěnka's principle.

To remove the word "elementary" above and ensure that for any two distinct sentences $\sigma, \tau \in \mathcal{L}_{\infty,\infty}$ there is no embedding $j : \mathcal{M}_\sigma\to \mathcal{M}_\tau$, we just need to modify the structures $\mathcal{M}_\sigma$ in the usual way by adding a relation for every first-order formula. (I didn't want to complicate the notation with this when defining the structures initially.)

Then we can define the diagonal class of structures $D = \{\mathcal{M}_\sigma \mid \sigma \in \mathcal{L}_{\infty,\infty} \wedge \mathcal{M}_\sigma \not\models \sigma\}$ and show that its upward closure $D\mathord{\uparrow}$ does not have the form $\operatorname{Mod}(\tau)$ for any sentence $\tau \in \mathcal{L}_{\infty,\infty}$ as before.

Bounty Ended with 250 reputation awarded by Noah Schweber
Source Link
Trevor Wilson
  • 5.5k
  • 29
  • 46

I think IAU is equivalent to Vopěnka's principle. For the other direction, assume Vopěnka's principle fails. Then there is a proper class of structures (WLOG graphs), none of which embeds into any other. Because this is a proper class, there is an injection of $\mathcal{L}_{\infty,\infty}$ into it. In other words, for each sentence $\sigma \in \mathcal{L}_{\infty,\infty}$ we may choose a structure $\mathcal{M}_\sigma$ in such a way that for any two distinct sentences $\sigma,\tau \in \mathcal{L}_{\infty,\infty}$, neither $\mathcal{M}_\sigma$ nor $\mathcal{M}_\tau$ embeds into the other.

Now we define the "diagonal" class of structures $D = \{\mathcal{M}_\sigma \mid \sigma \in \mathcal{L}_{\infty,\infty} \wedge \mathcal{M}_\sigma \not\models \sigma\}$. I claim that its upward closure $D\mathord{\uparrow}$ does not have the form $\operatorname{Mod}(\tau)$ for any sentence $\tau \in \mathcal{L}_{\infty,\infty}$. This is because $\mathcal{M}_\tau \in D\mathord{\uparrow} \iff \mathcal{M}_\tau \in D \iff \mathcal{M}_\tau \not\models \tau \iff \mathcal{M}_\tau \notin \operatorname{Mod}(\tau)$.

The key point is that $\mathcal{M}_\tau \in D\mathord{\uparrow}$ implies $\mathcal{M}_\tau \in D$ because no other structure $\mathcal{M}_\sigma \in D$ can embed into $\mathcal{M}_\tau$.