Difference between revisions of "Vopenka"
Zetapology (Talk | contribs) m (→Locally Presentable Categories: specified that graphs must be simple directed in the characterization) |
Zetapology (Talk | contribs) m (→Locally Presentable Categories) |
||
Line 52: | Line 52: | ||
A "locally small category" $C$ is one with only set-many morphisms between any two objects of $C$. This is one where the objects of $C$ behave "set-like" in the sense that, usually, the number of morphisms between two set-sized objects is at most the number of functions between their universes (like in groups and in graphs). A "locally presentable category" is a locally small category with a couple more really nice properties; you can "generate" all of the objects from set-many objects in the category. | A "locally small category" $C$ is one with only set-many morphisms between any two objects of $C$. This is one where the objects of $C$ behave "set-like" in the sense that, usually, the number of morphisms between two set-sized objects is at most the number of functions between their universes (like in groups and in graphs). A "locally presentable category" is a locally small category with a couple more really nice properties; you can "generate" all of the objects from set-many objects in the category. | ||
− | Vopěnka's principle intuitively states that if you have a locally presentable category $C$, then any proper class of objects of $C$ has some objects $c | + | Vopěnka's principle intuitively states that if you have a locally presentable category $C$, then any proper class of objects of $C$ has some nonisomorphic objects $c$ and $d$ where $c$ has a morphism into $d$. |
=== Woodin cardinals === | === Woodin cardinals === |
Revision as of 15:56, 4 December 2018
Vopěnka's principle is a large cardinal axiom at the upper end of the large cardinal hierarchy that is particularly notable for its applications to category theory. In a set theoretic setting, the most common definition is the following:
For any language $\mathcal{L}$ and any proper class $C$ of $\mathcal{L}$-structures, there are distinct structures $M, N\in C$ and an elementary embedding $j:M\to N$.
For example, taking $\mathcal{L}$ to be the language with one unary and one binary predicate, we can consider for any ordinal $\eta$ the class of structures $\langle V_{\alpha+\eta},\{\alpha\},\in\rangle$, and conclude from Vopěnka's principle that a cardinal that is at least $\eta$-extendible exists. In fact if Vopěnka's principle holds then there are a proper class of extendible cardinals; bounding the strength of the axiom from above, we have that if $\kappa$ is almost huge, or even almost-high-jump, then $V_\kappa$ satisfies Vopěnka's principle.
Contents
Formalizations
As stated above and from the point of view of ZFC, this is actually an axiom schema, as we quantify over proper classes, which from a purely ZFC perspective means definable proper classes. A somewhat stronger alternative is to view Vopěnka's principle as an axiom in second-order set theory capable to dealing with proper classes, such as von Neumann-Gödel-Bernays set theory. This is a strictly stronger assertion. [1] Finally, one may relativize the principle to a particular cardinal, leading to the concept of a Vopěnka cardinal.
Vopěnka cardinals
An inaccessible cardinal $\kappa$ is a Vopěnka cardinal if and only if $V_\kappa$ satisfies Vopěnka's principle, that is, where we interpret the proper classes of $V_\kappa$ as the subsets of $V_\kappa$ of cardinality $\kappa$. Because of a characterization of Vopěnka's principle in terms of graphs, a cardinal $\kappa$ is Vopěnka if and only if $\kappa$ is inaccessible and any set $\kappa$-sized set $G$ of nonisomorphic graphs has some $g_0$ and $g_1$ with $g_0$ a proper subgraph of $g_1$. (Need to cite sources)
Perlmutter [1] proved that a cardinal is a Vopěnka cardinal if and only if it is a Woodin for supercompactness cardinal.
As we mentioned above, every almost huge cardinal is a Vopěnka cardinal.
Equivalent statements
$C^{(n)}$-extendible cardinals
The schema form of Vopěnka's principle is equivalent to the existence of a proper class of $C^{(n)}$-extendible cardinals for every $n$; indeed there is a level-by-level stratification of Vopěnka's principle, with Vopěnka's principle for a $\Sigma_{n+2}$-definable class corresponds to the existence of a $C^{(n)}$-extendible cardinal greater than the ranks of the parameters. [2]
Strong Compactness of Logics
Vopěnka's principle is equivalent to the following statement about logics as well:
For every logic $\mathcal{L}$, there is a cardinal $\mu_{\mathcal{L}}$ such that for any language $\tau$ and any $\mathcal{L}(\tau)$-theory $T$, $T$ is satisfiable if and only if every $t\subseteq T$ such that $|t|<\mu_{\mathcal{L}}$ is satisfiable. [3]
This $\mu_{\mathcal{L}}$ is called the strong compactness cardinal of $\mathcal{L}$. Vopěnka's principle therefore is equivalent to every logic having a strong compactness cardinal. This is very similar in definition to the Löwenheim–Skolem number of $\mathcal{L}$, although it is not guaranteed to exist.
Here are some examples of strong compactness cardinals of specific logics:
- If $\kappa\leq\lambda$ and $\lambda$ is strongly compact or $\aleph_0$, then the strong compactness cardinal of $\mathcal{L}_{\kappa,\kappa}$ is at most $\lambda$.
- Similarly, if $\kappa\leq\lambda$ and $\lambda$ is extendible, then for any natural number $n$, the strong compactness cardinal of $\mathcal{L}^n_{\kappa,\kappa}$ ($\mathcal{L}_{\kappa,\kappa}$ with $n+1$-th order logic) is at most $\lambda$. Therefore for any natural number $n$, the strong compactness cardinal of $n+1$-th order finitary logic is at most the least extendible cardinal.
Locally Presentable Categories
Vopěnka's principle is equivalent to the axiom stating "no large full subcategory $C$ of any locally presentable category is discrete." (Sources needed). Equivalently, no large full subcategory of Graph (the category of all graphs) is discrete; that is, for any proper class of simple directed graphs, there is at least one pair of nonequal graphs $G$ and $H$ in the class such that $G$ is a subgraph of $H$. This is a $\Pi^1_1$ statement, so the least Vopěnka cardinals are not even weakly compact (although the least weakly compact cardinal is much, much, much smaller than the least Vopěnka cardinal, if it exists).
Intuitively, a "category" is just a class of mathematical objects with some notion of "morphism", "homomorphism", "isomorphism", (etc.). For example, in Set, the category of all sets, homomorphisms are just injections, and isomorphisms are bijections. In categories of groups and models, homomorphisms and isomorphisms share their actual names.
A "locally small category" $C$ is one with only set-many morphisms between any two objects of $C$. This is one where the objects of $C$ behave "set-like" in the sense that, usually, the number of morphisms between two set-sized objects is at most the number of functions between their universes (like in groups and in graphs). A "locally presentable category" is a locally small category with a couple more really nice properties; you can "generate" all of the objects from set-many objects in the category.
Vopěnka's principle intuitively states that if you have a locally presentable category $C$, then any proper class of objects of $C$ has some nonisomorphic objects $c$ and $d$ where $c$ has a morphism into $d$.
Woodin cardinals
There is a strange connection between the Woodin cardinals and the Vopěnka cardinals. In particular, Vopěnkaness is equivalent to two strengthening variants of Woodinness, namely the Woodin for Supercompactness cardinals and the $2$-fold Woodin cardinals. As a result, every Vopěnka cardinal is Woodin.
Elementary Embeddings Between Ranks
An equivalent statement to Vopěnka's principle is that for any proper class $C\subseteq ORD$, there are $\alpha\in C$, $\beta\in C$, and a nontrivial elementary embedding $j:\langle V_\alpha;\in,P\rangle\rightarrow\langle V_\beta;\in,P\rangle$. Vopěnka's principle quite obviously implies this. The reason the converse holds is because every elementary embedding can be "encoded" (in a sense) into one of these. For more information, see [4].
Other points to note
Whilst Vopěnka cardinals are very strong in terms of consistency strength, a Vopěnka cardinal need not even be weakly compact. Indeed, the definition of a Vopěnka cardinal is a $\Pi^1_1$ statement over $V_\kappa$ (Vopěnka's principle itself is $\Pi^1_1$), and $\Pi^1_1$-indescribability is one of the equivalent definitions of weak compactness. Thus, the least weakly compact Vopěnka cardinal must have (many) other Vopěnka cardinals less than it.
External links
References
- Perlmutter, Norman. The large cardinals between supercompact and almost-huge. , 2010. arχiv bibtex
- Bagaria, Joan and Casacuberta, Carles and Mathias, A R D and Rosický, Jiří. Definable orthogonality classes in accessible categories are small. Journal of the European Mathematical Society 17(3):549--589. arχiv bibtex
- Makowsky, Johann. Vopěnka's Principle and Compact Logics. J Symbol Logic www bibtex
- Kanamori, Akihiro. The higher infinite. Second, Springer-Verlag, Berlin, 2009. (Large cardinals in set theory from their beginnings, Paperback reprint of the 2003 edition) www bibtex