Abstract Logics

Since the early 20th century, logicians have formalized the study of mathematical structures in the system of first-order logic. But first-order logic itself, the so-called meta-theory of mathematics, does not exist outside of mathematics. It depends on the ambient set-theoretic background in which we choose to work, or at the minimum on some weak fragment of it codifying the properties of natural numbers. Using more of the available set-theoretic background we can define much stronger logics through which we gain access to more advanced properties of mathematical structures.

So what is a logic? Roughly speaking, a logic is an assignment to every mathematical language of a collection of formulas together with a satisfaction relation which tells us which formulas a given structure in a given language satisfies. We are all familiar with first-order logic's recursive definition of formulas and Tarski's satisfaction. Formulas and satisfaction in other logics can be much stranger in nature and they usually gain us much more access to the set-theoretic properties of structures. By a language, here, we simply mean a collection of functions, relations, and constants. I will give a formal definition of logic in a little bit, but I think it is more instructive to start with some examples of different logics and their properties.

Two very basic properties of first-order logic which we take for granted are (1) that there are set-many formulas for every fixed language and (2) that any single formula can mention only finitely much of the language. Although these properties are obvious enough in this case, it turns out that they are fairly important for abstracting away to the desired properties of tractable abstract logics. One of the most useful, surprising, and significant properties of first-order logic is ($\omega$-)compactness, the assertion that if every finite fragment of a theory has a model, then so does the whole theory. Compactness tends to fail for stronger logics, but depending on the existence of large cardinals, they will satisfy $\kappa$-compactness for some cardinal $\kappa$, meaning that if every ${<}\kappa$-sized fragment of a theory has a model, then so will the whole theory. If a logic is $\kappa$-compact, we will say that $\kappa$ is a strong compactness cardinal for the logic. We will say that $\kappa$ is a weak compactness cardinal if $\kappa$-compactness holds for theories of size $\kappa$. Set theorists and model theorists, going back to Tarski, have uncovered a very close connection between large cardinals and compactness cardinals for strong logics.

In first-order logic we can take finite conjunctions and disjunctions of formulas. Using more of the set-theoretic background, we can strengthen first-order logic to allow conjunctions and disjunctions of size less than $\delta$ for some cardinal $\delta$. This gives rise to a family of logics indexed by cardinals $\delta$, the $\mathbb L_{\delta,\omega}$ logics. The weakest such logic $\mathbb L_{\omega_1,\omega}$ allows countable-length conjunctions and disjunctions of formulas. A formula of $\mathbb L_{\delta,\omega}$ can mention a $\gamma$-sized chunk of a language for any $\gamma<\delta$, so we are no longer restricted to only finitely much of the language appearing in a single formula. In $\mathbb L_{\omega_1,\omega}$, we can express, for instance, that there are no nonstandard natural numbers by saying that if $n$ is a natural number, then $$n=0\vee n=1\vee n=2\vee\cdots.$$ We can express that a given first-order type is realized or omitted, by saying that there is/isn't an element satisfying the infinite conjunction of formulas in this type. We can express that a model is recursively saturated because there are only countably many recursive types. More generally, in a logic $\mathbb L_{\delta,\omega}$, for every ordinal $\xi<\delta$, there is a formula $\varphi_\xi(x)$ in a language with a binary relation $E$, which expresses that $(x,E)$ is isomorphic to $\xi$ (argue by transfinite induction). The price for this strength is compactness: consider the theory which says that there is a nonstandard natural number.

How about allowing set-sized conjunctions and disjunctions for a set of any size? This gives the logic $\mathbb L_{\rm {Ord},\omega}$, but actually it will not be a logic under our definition because it fails a number of reasonable properties. For one thing, there are class-many formulas for any language, and for another, a formula can mention arbitrarily large chunks of a language. These failures stand in the way of the existence of strong compactness cardinals. $\mathbb L_{\rm {Ord},\omega}$ does not have a strong compactness cardinal. Why? Suppose $\kappa$ is a strong compactness cardinal for $\mathbb L_{\rm {Ord},\omega}$. Consider the theory with a relation $E$ which says that the universe is isomorphic to $\kappa$ and also has assertions $$\exists x\exists y\, x>\varphi_\xi(y)$$ for every $\xi<\kappa$.

Why stop at long conjunctions and disjunctions? We can also allow long sequences of quantifiers. The logics $\mathbb L_{\delta,\gamma}$, for cardinals $\delta$ and $\gamma$, allow quantifier blocks of length less than $\gamma$. In the logic $\mathbb L_{\omega_1,\omega_1}$ we can express that a relation is well-founded. In the logic $\mathbb L_{\omega_1,\omega_2}$ we can express that the universe is uncountable. We can weaken these logics by adding to $\mathbb L_{\omega_1,\omega}$ the quantifier $Q^{WF}xy$ and define that $Q^{WF}xy\,\varphi(x,y)$ holds whenever $\varphi$ defines a well-founded relation. Similarly we can add the quantifier $Q^{U}x$ and define that $Q^{U}x\,\varphi(x)$ holds whenever there are uncountably many elements satisfying $\varphi(x)$.

Notice how these logic are reliant on more and more of the ambient set-theoretic background to give us more information about the properties of our structures. Can these logics have compactness cardinals? A cardinal $\kappa$ is a weak compactness cardinal for $\mathbb L_{\kappa,\kappa}$ if and only if $\kappa$ is weakly compact (hence the name). A cardinal $\kappa$ is a strong compactness cardinal for $\mathbb L_{\kappa,\kappa}$ if and only if it is strongly compact. (Both results are due to Tarski [1]) Indeed, there is a large cardinal principle under which every logic has a strong compactness cardinal and there is a much weaker large cardinal principle under which every logic has a weak compactness cardinal. We will talk about those in a bit.

Next, let's delve even deeper into the set-theoretic universe to define the second-order logic $\mathbb L^2$ in which we have second-order quantifiers ranging over all relations on the structure. In second-order logic, we can express that a relation is well-founded, that the universe is infinite, and that a relation is isomorphic to a rank initial segment $(V_\alpha,\in)$ of the set-theoretic universe. We can express that a linear order has a countable dense subset or that a graph can be colored in 3 colors or that a group has an infinite abelian subgroup. But despite how strong the logic is, a formula of $\mathbb L^2$ can use only finitely much of a language. A cardinal $\kappa$ is a strong compactness cardinal for $\mathbb L_{\kappa,\kappa}^2$ if and only if it is extendible and the least strong compactness cardinal for $\mathbb L^2$ must be extendible [2] (a cardinal $\kappa$ is extendible if for every $\alpha>\kappa$, there is an elementary embedding $j:V_\alpha\to V_\beta$ with $\text{crit}(j)=\kappa$ and $j(\kappa)>\alpha$). As we can see, strong compactness for $\mathbb L^2$ is a strong property. Extendible cardinals are the second step in the $C^{(n)}$-extendible cardinals hierarchy, introduced by Bagaria [3], they are precisely the $C^{(2)}$-extendible cardinals ($C^{(1)}$-extendible cardinals are the supercompacts). A cardinal $\kappa$ is $C^{(n)}$-extendible if for every $\alpha>\kappa$ such that $V_\alpha\prec_{\Sigma_n}V$, there is an elementary embedding $j:V_\alpha\to V_\beta$ with $\text{crit}(j)=\kappa$, $V_\beta\prec_{\Sigma_n}V$ and $j(\kappa)>\alpha$. Are the rest of the $C^{(n)}$-extendible cardinals strong compactness cardinals for some natural logics?

Väänänen defined a class of very strong logics, the sort logics $\mathbb L^{s,\Sigma_n}$, which generalize second-order logic, by allowing a search throughout the entire universe of sets for an object in some way related to our structure [4]. Second-order logic is a two-sorted logic because it has two sorts of objects: the elements of the model and the relations on the model. This easily generalizes to multi-sorted logics, which can have more different sorts, each sort coming with its own variables and quantifiers. Each sort has its own corresponding universe of objects for the quantifiers to range over. Sort logics are multi-sorted logics with additional special sort quantifiers $\forall^\sim$ and $\exists^\sim$. A formula $\exists^\sim E\,\varphi(E)$ answers the question whether we can expand our existing collection of universes of various sorts by a new sort with a relation $E$ on it satisfying $\varphi(E)$ with respect to the old sorts. The $\Sigma_n$ in $\mathbb L^{s,\Sigma_n}$ limits the sort quantifiers to a $\Sigma_n$-formula. The stratification of sort logic into the $\Sigma_n$-levels is necessary because a satisfaction relation for the full sort logic with arbitrary alternations of sort quantifiers would yield definability of truth. In sort logic, we can express whether a set is isomorphic to a $V_\alpha$ which is $\Sigma_n$-elementary in $V$. We can express whether a group is the additive group of some field. A cardinal $\kappa$ is $C^{(n)}$-extendible if and only if it is a strong compactness cardinal for $\mathbb L^{s,\Sigma_n}_{\kappa,\kappa}$ and the least strong compactness cardinal for $\mathcal L^{s,\Sigma_n}$ must be $C^{(n)}$-extendible [5].

We can also have logics tailor-made for a cause. Suppose, for instance, that you do not want the full power of second-order logic, but you just want to recognize whether a given set with a relation $E$ is isomorphic to a rank initial segment $V_\alpha$. To achieve this we can simply extend first-order logic by a single formula $\varphi_E(x)$ which can be applied to a language with a binary relation $E$, and decree that it holds true whenever $x$ is transitive with respect to the $E$ relation and $(x,E)$ is isomorphic to $V_\alpha$ for some $\alpha$.

With all these examples, we are ready to see a formal definition of abstract logic. First let's formally define languages. A language $\tau$ is a collection of function and relation symbols that come with a finite number arity, as well as constant symbols. Formally, $\tau$ is an ordered quadruple $(\mathfrak F, \mathfrak R, \mathfrak C, a)$ where $\mathfrak F$, $\mathfrak R$, and $\mathfrak C$ are disjoint sets and $a:\mathfrak F\cup\mathfrak R \to \omega$ is the arity function. To every language $\tau$ we associate the corresponding class $\text{Str }\tau$ of all $\tau$-structures, namely sets with interpretations for the relations, functions, and constants in $\tau$. A renaming $f$ between two languages $\tau=(\mathfrak F, \mathfrak R, \mathfrak C, a)$ and $\sigma=(\mathfrak F', \mathfrak R', \mathfrak C', a')$ is a bijection $f:\mathfrak F\cup\mathfrak R\cup\mathfrak C \to \mathfrak F'\cup\mathfrak R'\cup\mathfrak C'$ that preserves the partition and the arities. Informally, a renaming simply gives different names to the functions, relations, and constants of a given language. If there is a renaming $f$ between two languages $\tau$ and $\sigma$, then there is the obvious bijection $f^*$ between $\text{Str }\tau$ and $\text{Str } \sigma$ which takes a $\tau$-structure and maps it to a structure with the same underlying set but with renamed functions, relations, and constants. Now for the definition:

Definition: An abstract logic is a pair $(\mathcal L, \vDash_{\mathcal L})$ satisfying the following conditions.

It is the easiest course of action to restrict logics to sentences and introduce formulas by adding and interpreting constants. Some other sources (see for instance [6]) add other properties such as closure under conjunctions, negations, and quantification.

Let's get back to the large cardinal principle under which every abstract logic has a strong compactness cardinal. Vopenka's principle is the assertion that every class of structures in a common language has two structures which elementarily embed. Bagaria showed that Vopenka's principle is equivalent to the assertion that for every $n<\omega$, there is a $C^{(n)}$-extendible cardinal [3]. Makowsky showed that Vopenka's principle is equivalent to the assertion that every abstract logic has a strong compactness cardinal [7]. In an upcoming joint work with Boney, Dimopolous and Magidor we show that every abstract logic has stationarily many weak compactness cardinals if and only if ${\rm Ord}$ is subtle [8]. The principle ${\rm Ord}$ is subtle asserts that for every class club $C$ and every sequence $\langle A_\xi\mid\xi\in{\rm Ord}\rangle$ with $A_\alpha\subseteq \alpha$, there are $\alpha<\beta\in C$ such that $A_\beta\cap \alpha=A_\alpha$. In this work we also provide compactness characterizations of various virtual large cardinals in terms of a new notion of pseudo-model [8]. Given a language $\tau$ and a theory $T$ in an abstract logic $\mathcal L(\tau)$, we can say informally that a pseudo-model of $T$ is a set $M$ on which we can impose partial $\tau$-structures to interpret all possible small pieces of $T$ with the extension property that any interpretation of a small piece of $T$ can be extended to an interpretation of another small piece of $T$.

References

  1. A. Tarski, “Some problems and results relevant to the foundations of set theory,” in Logic, Methodology and Philosophy of Science, Proceedings of the 1960 International Congress, 1962.
  2. M. Magidor, “On the role of supercompact and extendible cardinals in logic,” Israel Journal of Mathematics, vol. 10, pp. 147–157, 1971.
  3. J. Bagaria, “$C^{(n)}$-cardinals,” Arch. Math. Logic, vol. 51, no. 3-4, pp. 213–240, 2012.
  4. J. Väänänen, “Sort logic and foundations of mathematics,” in Infinity and Truth, vol. 25, C. Chong, Q. Fend, T. Slaman, and H. Woodin, Eds. 2014, pp. 171–186.
  5. W. Boney, “Model theoretic characterizations of large cardinals,” Israel J. Math., vol. 236, no. 1, pp. 133–181, 2020.
  6. C. C. Chang and H. J. Keisler, Model theory, Third., vol. 73. North-Holland Publishing Co., Amsterdam, 1990, p. xvi+650.
  7. J. Makowsky, “Vopenka’s principle and compact logics,” Journal of Symbolic Logic, vol. 50, pp. 42–48, 1985.
  8. W. Boney, S. Dimopoulos, V. Gitman, and M. Magidor, “Model theoretic characterizations of large cardinals revisited,” To appear in the Transactions of the AMS.