Upward Löwenheim-Skolem-Tarski numbers for abstract logics
V. Gitman and J. Osinski, “Upward Löwenheim-Skolem-Tarski numbers for abstract logics,” Ann. Pure Appl. Logic, vol. 176, no. 8, pp. Paper No. 103583, 2025. Available at: https://doi.org/10.1016/j.apal.2025.103583
First-order logic relies, however minimally, on the set-theoretic background universe in which we work because it uses properties of the natural numbers. Tarski's definition of truth, for instance, requires recursion. The dependence on the set-theoretic background universe 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 more 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 upward 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 upward Löwenheim-Skolem Theorem for first-order logic says that any infinite structure has arbitrarily large elementary superstructures. A very weak version of the upward 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 upward 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, (see, for instance, [1]). 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: ([2]) Fix a logic $\mathcal L$. The upward Löwenheim-Skolem-Tarski number ${\rm ULST}(\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$.
The differences in the definitions of the Hanf and $\text{ULST}$ numbers mirror differences in notions of varying strengths generalizing the downward Löwenheim-Skolem Theorem. The Löwenheim-Skolem number $\text{LS}(\mathcal L)$ of a logic $\mathcal L$ is the smallest cardinal $\kappa$ such that any satisfiable sentence $\varphi$ of $\mathcal L$ has a model of size smaller than $\kappa$. Similar to the $\text{ULST}$ number, the Löwenheim-Skolem-Tarski number $\text{LST}(\mathcal L)$ adds the requirement, that any model of $\varphi$ has to have a substructure of size smaller than $\kappa$ satisfying $\varphi$. As with the Hanf number, it can be shown in ${\rm ZFC}$ that every logic has an $\text{LS}$ number. On the other hand, there is a long history going back to [3] that shows that $\text{LST}$ numbers of logics can have large cardinal strength (see [4]).
Similar to this gain in strength that occurs when switching attention from $\text{LS}$ numbers to $\text{LST}$ numbers, Galeotti, Khomskii and Väänänen showed that the existence of the ${\rm ULST}$ number for second-order logic, ${\rm ULST}(\mathbb L^2)$, implies the existence of very strong large cardinals.
Theorem: ([2]) If ${\rm ULST}(\mathbb L^2)$ exists, then for every $n \in \omega$ there is an $n$-extendible cardinal $\lambda \leq {\rm ULST}(\mathbb L^2)$.
They further conjectured that the strength of the existence of ${\rm ULST}(\mathbb L^2)$ is exactly that of an extendible cardinal. We positively answer their conjecture.
Theorem: If ${\rm ULST}(\mathbb L^2)$ exists, then it is the least extendible cardinal.
We can further strengthen the notion of the ${\rm ULST}$ 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 SULST}(\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 ULST}$ and strong ${\rm ULST}$ 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
- D. Marker, Lectures on infinitary model theory, vol. 46. Association for Symbolic Logic, Chicago, IL; Cambridge University Press, Cambridge, 2016, p. viii+183. Available at: https://doi.org/10.1017/CBO9781316855560
- L. Galeotti, Y. Khomskii, and J. Väänänen, “Bounded symbiosis and upwards reflection,” Arch. Math. Log., 2024.
- M. Magidor, “On the role of supercompact and extendible cardinals in logic,” Israel J. Math., vol. 10, pp. 147–157, 1971.
- M. Magidor and J. Väänänen, “On Löwenheim-Skolem-Tarski numbers for extensions of first order logic,” J. Math. Log., vol. 11, no. 1, pp. 87–113, 2011. Available at: https://doi.org/10.1142/S0219061311001018