Upward Löwenheim-Skolem numbers for abstract logics
V. Gitman and J. Osinski, “Upward Löwenheim-Skolem numbers for abstract logics,” Manuscript, 2023.
We tend to think of first-order logic, the generally accepted system for formalizing mathematics, as existing entirely outside of mathematics. But even first-order logic relies, however minimally, on the set-theoretic background universe in which we work because it uses properties of natural numbers. Tarski's definition of truth, for instance, requires recursion. The dependence on the set-theoretic background becomes more apparent when we consider stronger logics, such as infinitary logics and second-order logic. In these logics, we can express more properties of the models at the cost of having to use higher levels of the set-theoretic universe to define the logic itself. Niceness properties of strong logics have been shown to be connected to and often equivalent to the existence of large cardinals. For many classical strong logics, for instance, the existence of a strong compactness cardinal is equivalent to the existence of some classical large cardinal. In this article, we investigate upwards Löwenheim-Skolem principles for various classical logics and show that these principles are equivalent to the existence of large cardinals, some classical and some new.
The upwards Löwenheim-Skolem Theorem for first-order logic says that any infinite structure has arbitrarily large elementary superstructures. A very weak version of the upwards Löwenheim-Skolem Theorem holds for all logics. Recall that the Hanf number of a logic $\mathcal L$ is the least cardinal $\delta$ such that for every language $\tau$ and $\mathcal L(\tau)$-sentence $\varphi$, if a $\tau$-structure $M\models_{\mathcal L}\varphi$ has size $\gamma\geq\delta$, then for every cardinal $\overline\gamma>\gamma$, there is a $\tau$-structure $\overline M$ of size at least $\overline\gamma$ such that $\overline M\models_{\mathcal L}\varphi$. The upwards Löwenheim-Skolem Theorem implies, in particular, that the Hanf number of first-order logic is $\omega$. ${\rm ZFC}$ proves that every logic has a Hanf number (see, for instance, (missing reference)). Galeotti, Khomskii and Väänänen strengthened the notion of the Hanf number by requiring that the model $\overline M\models_{\mathcal L}\varphi$ of size at least $\overline\gamma$ is a (not necessarily elementary) superstructure of $M$.
Definition: ([1]) Fix a logic $\mathcal L$. The upward Löwenheim-Skolem number ${\rm ULS}(\mathcal L)$, if it exists, is the least cardinal $\delta$ such that for every language $\tau$ and $\mathcal L(\tau)$-sentence $\varphi$, if a $\tau$-structure $M\models_{\mathcal L}\varphi$ has size $\gamma\geq\delta$, then for every cardinal $\overline\gamma>\gamma$, there is a $\tau$-structure $\overline M$ of size at least $\overline\gamma$ such that $\overline M\models_{\mathcal L}\varphi$ and $M\subseteq \overline M$ is a substructure of $\overline M$.
Galeotti, Khomskii and Väänänen showed that the existence of the ${\rm ULS}$ number for second-order logic, ${\rm ULS}(\mathbb L^2)$, implies the existence of very strong large cardinals.
Theorem: ([1]) If ${\rm ULS}(\mathbb L^2)$ exists, then for every $n \in \omega$ there is an $n$-extendible cardinal $\lambda \leq {\rm ULS}(\mathbb L^2)$.
They further conjectured that the strength of the existence of ${\rm ULS}(\mathbb L^2)$ is exactly that of an extendible cardinal. We positively answer their conjecture.
Theorem: If ${\rm ULS}(\mathbb L^2)$ exists, then it is the least extendible cardinal.
We can further strengthen the notion of the ${\rm ULS}$ number to capture the full power of the upwards Löwenheim-Skolem Theorem.
Definition: Fix a logic $\mathcal L$. The strong upward Löwenheim-Skolem number ${\rm SULS}(\mathcal L)$, if it exists, is the least cardinal $\delta$ such that for every language $\tau$ and every $\tau$-structure $M$ of size $\gamma\geq\delta$, for every cardinal $\overline\gamma > \gamma$, there is a $\tau$-structure $\overline M$ of size at least $\overline\tau$ such that $M\prec_{\mathcal L} \overline M$ is an $\mathcal L$-elementary substructure of $\overline M$.
Notice that we could equivalently define the strong upward Löwenheim-Skolem number analogously to the upward Löwenheim-Skolem number but preserving theories instead of single sentences.
We pinpoint large cardinal notions that are equivalent to the existence of the ${\rm ULS}$ and strong ${\rm ULS}$ numbers for second-order logic, Väänänen's $\Sigma_n$-sort logics $\mathbb L^{s,n}$, the logic $\mathbb L(Q^{WF})$ - first-order logic augmented with the well-foundedness quantifier, the infinitary logics $\mathbb L_{\kappa,\kappa}$, and the logic $\mathbb L(I)$ - first-order logic augmented with the equicardinality quantifier.
References
- L. Galeotti, Y. Khomskii, and J. Väänänen, “Bounded Symbiosis and Upwards Reflection,” Manuscript.