2 McGee’s theorem

To describe McGee’s result and to put it into a more general framework we define what we mean by a “logic”: A logic (a.k.a. abstract logic) in the sense of Reference Lindström[33] is a pair $L^*=(\Sigma ,T)$ , where $\Sigma $ is an arbitrary set (sometimes also a class) and T is a binary relation between members of $\Sigma $ on the one hand and structures on the other. Members of $\Sigma $ are called $L^*$ -sentences. Classes of the form

$$ \begin{align*}\text{Mod}(\phi)=\{{\mathcal M}:T(\phi,{\mathcal M})\},\end{align*} $$

where $\phi $ is an $L^*$ -sentence, are called $L^*$ -characterizable, or $L^*$ -definable, classes. Abstract logics are assumed to satisfy five axioms expressed in terms of $L^*$ -characterizable classes, corresponding to being closed under isomorphism, conjunction, negation, permutation of symbols, and “free” expansions.Footnote ²⁴ A class $\mathcal {K}$ of models is said to be definable in a logic $L^*$ if there is a sentence $\phi $ in $L^*$ such that

$$ \begin{align*}\mathcal{K}=\text{Mod}(\phi).\end{align*} $$

Every model class is definable in some logic because we can take the model class as a generalized quantifier in the sense of Reference Lindström[32]: Suppose $\mathcal {K}$ is a model class with vocabulary L. For simplicity we assume $L=\{R\}$ where R is a binary predicate symbol. We can associate with $\mathcal {K}$ the generalized quantifier $Q_{\mathcal {K}}$ with the semantics

$$ \begin{align*}{\mathcal M}\models Q_{\mathcal{K}} xy\phi(x,y,\vec{a})\iff (M,\{(b,c)\in M^2 : {\mathcal M}\models\phi(b,c,\vec{a})\})\in\mathcal{K}.\end{align*} $$

Now $\mathcal {K}$ is trivially definable in the extension $\mathcal {L}_{\omega \omega }(Q_{\mathcal {K}})$ of first order logic by the quantifier $Q_{\mathcal {K}}$ by the sentence

$$ \begin{align*}Q_{\mathcal{K}} xyR(x,y).\end{align*} $$

Conversely, every class of models definable in $\mathcal {L}_{\omega \omega }(Q_{\mathcal {K}})$ , or indeed in any abstract logic, is a model class i.e. is closed under isomorphisms. We obtain the following simple and at the same time basic characterization:

2.1 Operations vs. model classes

In the literature, logical operations and model classes are considered to be carriers of logicality. Our paper focuses on model classes and on the extent to which they can be called logical, but here we take a moment to establish the connection between model classes and logical operations. McGee Reference McGee[41] defines an abstract concept of what he calls a logical operation. He goes on to define what it means for a logical operation to be described by a formula of a logic. We review these definitions and establish a close connection between model classes and connectives as well as between definability of a model class and describability of a logical operation.

Suppose M is a non-empty set. By the semantic value (on M) of a formula (of any logic) we mean the set of assignments into M that satisfy the formula. Abstractly, these are just subsets A of $M^{n}$ for some n. A (local) operation f on M maps sequences $\langle A_\alpha : \alpha <\beta \rangle $ of sets $A_\alpha \subseteq M^{n_\alpha }$ to sets $f(\langle A_\alpha : \alpha <\beta \rangle )\subseteq M^n$ . Such a local operation is a logical operation, if it is closed under permutations of M, i.e., if for all permutations $\pi $ of M

$$ \begin{align*}f(\langle \pi^{\prime\prime}A_\alpha : \alpha<\beta\rangle)=\pi^{\prime\prime}f(\langle A_\alpha : \alpha<\beta\rangle),\end{align*} $$

where for any $s=(a_1,\ldots ,a_n)\in A\subseteq M^n$ we define $\pi (s)=(\pi (a_1),\ldots ,\pi (a_n))$ .

Example 3. Suppose $A_0,A_1 \subseteq M^n$ . Conjunction is the logical operation $f^n_\wedge (\langle A_0,A_1\rangle )=A_0\cap A_1$ . Disjunction is the logical operation $f^n_\vee (\langle A_0,A_1\rangle )=A_0\cup A_1$ . Suppose $A\subseteq M^{n+1}$ . The existential quantifier with respect to n is the logical operation $f^{n}_{\exists }(\langle A\rangle )=\{s\upharpoonright \{0,\ldots ,n-1\}:s\in A\}$ .

For the existential second (and higher) order quantifiers to be logical operations would require an extension of the approach to include more general assignments, which we however disregard in this paper. Still, every formula of second (or higher) order logic gives rise (separately) to a logical operation in the above sense. The situation is the same with the so-called team semantics Reference Väänänen[56] where semantic values are sets of sets of assignments, rather than sets of assignments as above.

More generally we have an operation $f_M$ for every non-empty set M. Here we assume that $f_M$ is always an operation on M. We call the (class) mapping $M\mapsto f_M$ a global operation and denote it $\bar {f}$ . We call the global operation $\bar {f}$ a logical operation if it is closed under bijections, i.e., if for all bijections $\pi :M\to N$

$$ \begin{align*}f_N(\langle \pi^{\prime\prime}A_\alpha : \alpha<\beta\rangle)=\pi^{\prime\prime}f_M(\langle A_\alpha : \alpha<\beta\rangle),\end{align*} $$

A formula $\phi (\vec {x})$ with an $n_\alpha $ -ary predicate symbol $P_\alpha $ for each $\alpha <\beta $ is said to describe a local operation f on M if in any model ${\mathcal M}$ with domain M and $P_\alpha ^{\mathcal M}=A_\alpha \subseteq M^{n_\alpha }$ the semantic value of $\phi (\vec {x})$ is $f(\langle A_\alpha : \alpha <\beta \rangle )$ . The concept of a formula describing a global operation is defined similarly.

Example 4. The formula $P_0(\vec {x})\wedge P_1(\vec {x})$ describes the operation $f^n_\wedge $ . The formula $P_0(\vec {x})\vee P_1(\vec {x})$ describes the operation $f^n_\vee $ . The formula $\exists x_n P_0(\vec {x},x_n)$ describes the operation $f^n_\exists $ .

If $\phi (\vec {x})$ is a formula of a logic $L^*$ in the above sense, then the operation described by $\phi (\vec {x})$ is a logical operation, since we assume that truth in every logic $L^*$ that we consider is closed under isomorphisms (cf. Reference Lindström[33]).

An operation $\bar {f}$ can be represented alternatively as the model class in the vocabulary L which has in addition to the predicate symbols $P_\alpha $ , $\alpha <\beta $ , a new predicate symbol P:

$$ \begin{align*}\mathcal{K}_{\bar{f}}= \{{\mathcal M}: {\mathcal M} \text{ is an } L \text{-structure and }P^{\mathcal M}=f_M(\langle P^{\mathcal M}_\alpha:\alpha<\beta\rangle))\}.\end{align*} $$

It is easy to see that the class $\mathcal {K}_{\bar {f}}$ is closed under isomorphisms if and only if the operation $\bar {f}$ is preserved by bijections.

On the other hand, any model class $\mathcal {K}$ can be turned into a logical operation $\bar {f^{\mathcal {K}}}$ as follows. Let for any non-empty set M and relations $\vec {R}$ on M of the right arity:

$$ \begin{align*}f^{\mathcal{K}}_M(\vec{R})=\left\{\begin{array}{ll} M&\text{if } (M,\vec{R})\in\mathcal{K},\\ \emptyset&\text{otherwise.} \end{array}\right.\end{align*} $$

It is easy to see that the class $\mathcal {K}$ is closed under isomorphisms if and only if the operation $\bar {f^{\mathcal {K}}}$ is preserved by bijections.

2.3 The model-theoretic properties of $L_{\infty \infty }$

We now note the different respects in which $L_{\infty \infty }$ deviates from first order logic. First of all, $L_{\infty \infty }$ is badly nonabsolute.Footnote ²⁶ For example, the sentence

(1) $$ \begin{align} \begin{array}{l} \forall x\forall y(\forall z(E(z,x)\leftrightarrow E(z,y))\to x=y)\wedge\\ \forall x_0\forall x_1\ldots\exists y\forall z(E(z,y)\leftrightarrow\bigvee_{n<\omega}z=x_n) \end{array}\end{align} $$

of $L_{\infty \infty }$ which has models exactly in cardinalities $\mu $ such that $\mu ^\omega =\mu $ , is highly non-absolute.Footnote ²⁷ Other failures of absoluteness can be generated by replacing $\omega $ here by any regular cardinal.

A second important model-theoretic property of first order logic is its downward Löwenheim–Skolem theorem. Consider (1). Such a $\mu $ cannot have cofinality $\omega $ and thus $L_{\infty \infty }$ does not have a Löwenheim–Skolem theorem in the same strong sense as first order logic, or even in the sense of, e.g., $L_{\infty \omega }$ (see Theorem 13). That is, $L_{\infty \infty }$ can “omit” cardinals of cofinality $\omega $ in this special sense given by the Löwenheim–Skolem theorem. In contrast, a typical consequence of a Löwenheim–Skolem theorem of $L_{\kappa ^+\omega }$ is that if a definable model class has a model of cardinality $\lambda>\kappa $ then it has models of all cardinalities $\mu $ such that $\kappa \le \mu \le \lambda $ (Theorem 13), whatever their cofinality.

The logic behind Theorem 7, $L_{\kappa ^+\kappa ^+}$ , fails in a strong sense to have a Completeness Theorem. By a result of Dana Scott (published in Reference Karp[29]) the set of valid sentences of $L_{\kappa ^+\kappa ^+}$ is not $L_{\kappa ^+\kappa ^+}$ -definable over $H(\kappa ^+)$ , the set of sets of hereditary cardinality $\le \kappa $ . In contrast, the set of valid sentences of $L_{\kappa ^+\omega }$ is $\Sigma _1$ -definable over $H(\kappa ^+)$ Reference Karp[29], reminiscent of the Completeness Theorem of first order logic which implies that the set of (Gödel numbers of) valid sentences of first order logic is recursively enumerable i.e., $\Sigma _1$ over $HF$ , the set of hereditarily finite sets. In fact, Karp gives a complete axiomatization for $L_{\kappa ^+\omega }$ in Reference Karp[29].

In §5 we replace $L_{\infty \infty }$ by a logic which is almost absolute and which has a strong Löwenheim–Skolem theorem, together with other desirable properties, though it is still the case that the definition is given relative to the size of the models in the class.

3 Löwenheim–Skolem theorems viewed through the spectra of model classes

The fact that the class of all models of cardinality $\kappa $ , for example, satisfies the Tarski–Sher criterion, irrespective of what $\kappa $ is, raises the question, is cardinality a logical property? We saw that in the more subtle case of $\mathcal {K}_{\text {lim}}$ the property of a model of being of a limit cardinality is, according to this criterion, logical; by modifying $\mathcal {K}_{\text {lim}}$ one can generate many other cases. For example, if A is a property of natural numbers, we can consider the class $\mathcal {K}$ of models of cardinality $\aleph _n$ , such that n has property A. The property of a model of belonging to $\mathcal {K}$ is a logical property of the model by the Tarski–Sher criterion, even though to judge whether a particular model is in $\mathcal {K}$ one has to first determine whether the size of the universe is some $\aleph _n$ , and after that one has to determine whether n has property A. This stretches the concept of logicality and entangles it with the concept of what is mathematical. Earlier writers have observed this, so we are not saying essentially anything new here.

Of Feferman’s three objections to the Tarski–Sher criterion of logicality, the third is that it leaves unexplained how logicality is to be understood across domains of different sizes. The existential quantifier, for example, is, in a sense, the same on any domain of any cardinality, but this is not true of many properties which satisfy the Tarski–Sher criterion, for example $\mathcal {K}_{\text {lim}}$ . We suggest that in order that a property of models manifests a greater degree of logicality than is provided by the Tarski–Sher criterion, it should have a definition by a sentence in $L_{\infty \infty }$ or in some other logic in such a way that the same sentence defines the model class in as many cardinalities as possible.Footnote ²⁸ We explore this suggestion below via the concept of a spectrum. Our second suggestion is that a higher grade of logicality would be assigned to the degree to which the logic in question had “first-order-like” model-theoretic properties: absoluteness, a Löwenheim–Skolem theorem, and completeness. $L_{\infty \infty }$ would thus be given a low grade on the logicality scale, being non-absolute, having a limited Löwenheim–Skolem theorem and failing to have a Completeness Theorem. We explore this suggestion in §7 Footnote ²⁹ .

3.1 Spectra

In analysing the structure of a model class, in order to determine whether it is in some sense logical or not or to find out whether it is definable in some interesting logic, it is useful to investigate the cardinalities of models in the class. One might think that mere cardinalities are too rough a measure of any form of logicality but this is, in fact, surprisingly informative. This leads naturally to the concept of a spectrumFootnote ³⁰ :

Definition 12. If $\mathcal {K}$ is a model class, the spectrum of $\mathcal {K}$ is the class $\text {sp}(\mathcal {K})$ of cardinalities of models in $\mathcal {K}$ i.e.,

$$ \begin{align*}\text{sp}(\mathcal{K})=\{|M| : {\mathcal M}\in \mathcal{K}\}.\end{align*} $$

Depending on $\mathcal {K}$ , the spectrum can be a singleton, an interval of cardinals, an initial (or final) segment of the class of all cardinals, or something more complicated, such as the class of all limit cardinals, or all limit cardinals of cofinality $\omega $ (see Figure 1). Even the patterns of finite numbers in spectra of first order sentences is highly interesting [Reference Asser3, Reference Jones and Selman27]. However, we are here concerned with infinite cardinals in a spectrum.

Figure 1

Spectra of some model classes.

The property of a logic which reflects regularity patterns in its spectra is captured by the Löwenheim–Skolem theorem. The spectrum gives indirect information of the possibility that the model class is definable in some logic. Roughly speaking, if the logic has a strong Löwenheim–Skolem property, then the spectra of definable model classes reflect this. If every sentence in the logic which has an infinite model has also a countably infinite model, the most famous case of a Löwenheim–Skolem property, then every spectrum with an infinite cardinal in it has also $\aleph _0$ in it.

Skolem proved that first order logic satisfies $\text {LS}([\aleph _0,\infty ),\{\aleph _0\})$ (see Definition 1) giving rise to the so-called Skolem Paradox: countable first order theories such as set theory have countable models if they have models at all. Now, 100 years after Skolem’s discovery, the indifference of first order logic to the infinite cardinality of its models is often considered a positive rather than negative aspect. Indifference to cardinality is of course closely related to set-theoretical absoluteness and thereby to a desirable quality of logicality. In consequence, the stronger form of $\text {LS}(C,D)$ a logic satisfies the more appropriate the logic is for expressing logical properties.

If a logic satisfies $\text {LS}(C,D)$ , there are consequences for the spectra of definable model classes. Suppose $\mathcal {K}$ is definable in a logic with $\text {LS}(C,D)$ . Then we can make the following conclusions: If there is ${\mathcal M}\in \mathcal {K}$ with $|M|\in C$ , then there is ${\mathcal N}\in \mathcal {K}$ with $|N|\in D$ . On the other hand, if $\mathcal {K}$ contains a model of cardinality $\kappa $ but no models of cardinality $\lambda $ , then $\mathcal {K}$ cannot be definable in a logic with $\text {LS}(C,D)$ such that $\kappa \in C$ and $\lambda \notin D$ . The point is that by looking at the spectrum of $\mathcal {K}$ we can make inferences about its definability in different logics. Thus, if we are given a model class $\mathcal {K}$ but no logic in which it would be definable (apart from the trivial $L(Q_{\mathcal {K}})$ ), and we can discern regular patterns in $\text {sp}(\mathcal {K})$ , we may take it as an indirect indication (albeit not a proof) that $\mathcal {K}$ is definable in a logic with $\text {LS}(C,D)$ for some C and D explaining the found patterns. On the other hand, if $\text {sp}(\mathcal {K})$ does not seem to have regular patterns, we may take it as an indication that no such logic can be found. Thus $\text {sp}(\mathcal {K})$ gives implicit information about the possibility of finding a syntax for $\mathcal {K}$ .

Let us look at the Löwenheim–Skolem properties of the logics $L_{\infty \omega }$ and $L_{\infty \infty }$ .Footnote ³¹ We first recall a basic construction in infinitary logic, based on a class of important formulas due to Scott Reference Scott, Addison, Henkin and Tarski[47]. For any ordinal $\alpha $ let the formula $\eta _\alpha (x)$ with one free variable x and a binary relation symbol $<$ be defined, by transfinite recursion, as follows:

(2) $$ \begin{align} \eta_\alpha(x)\leftrightarrow\forall y(y<x\to\bigvee_{\beta<\alpha}\eta_\beta(y)) \wedge\bigwedge_{\beta<\alpha}\exists y(y<x\wedge\eta_\beta(y)). \end{align} $$

Then for a linear order $(A,<)$ and $a\in A$ we have

(3) $$ \begin{align} (A,<)\models\eta_\alpha(a)\iff(\{b\in A:b<a\},<)\cong(\alpha,<). \end{align} $$

Let

(4) $$ \begin{align} \eta^{\prime}_\alpha\leftrightarrow\forall y\bigvee_{\beta<\alpha}\eta_\beta(y) \wedge\bigwedge_{\beta<\alpha}\exists y\ \eta_\beta(y). \end{align} $$

For a linear order $(A,<)$ we have

(5) $$ \begin{align} (A,<)\models\eta^{\prime}_\alpha\iff(A,<)\cong(\alpha,<). \end{align} $$

Now $\eta ^{\prime }_\alpha $ is in $L_{\kappa \omega }$ whenever $\alpha <\kappa $ . It follows that by combining the sentences $\eta ^{\prime }_\alpha $ , the logic $L_{\kappa \omega }$ can manifest totally arbitrary patterns of spectra in cardinalities below $\kappa $ , roughly for the same reason that any finite set of finite numbers can be the spectrum of a first order sentence. More exactly, if X is an arbitrary set of cardinal numbers below $\kappa $ , then

$$ \begin{align*}\bigvee_{\lambda\in X}\eta^{\prime}_\lambda\in L_{\kappa^+\omega}\text{ and }X=\text{sp}(\bigvee_{\lambda\in X}\eta^{\prime}_\lambda).\end{align*} $$

This shows that when dealing with extensions of $L_{\kappa \omega }$ it makes sense to focus on cardinals $\ge \kappa $ .

The basic facts about the $\text {LS}(C,D)$ type properties of infinitary languages are the following:

Theorem 13 [Reference Dickmann20]

Suppose $\kappa \le \lambda $ are cardinals and $\kappa $ is regular.

1. 1. $L_{\kappa ^+\omega }$ satisfies $\text {LS}([\lambda ,\infty )\},\{\mu \})$ for all $\mu $ such that $\kappa \le \mu \le \lambda $ .

2. 2. $L_{\kappa ^+\kappa ^+}$ satisfies $\text {LS}([\lambda ,\infty ),\{\mu \})$ for all $\mu $ such that $\kappa \kern1.2pt{\le}\kern1.2pt \mu \kern1.2pt{\le}\kern1.2pt \lambda $ and $\mu ^\kappa \kern1.2pt{=}\kern1.2pt\mu $ .

3. 3. $L_{\kappa ^+\omega }$ satisfies $\text {LS}([\beth _{(2^\kappa )^+},\infty ),[\mu ,\infty ))$ for all $\mu $ .

4. 4. $L_{\omega _1\omega _1}$ does not satisfy “For all $\mu \text {LS}([\lambda ,\infty ),[\mu ,\infty ))$ ” for any $\lambda $ below the first inaccessible cardinal (assuming there are inaccessible cardinals).

For a class size logic such as $L_{\infty \omega }$ or $L_{\infty \infty }$ the $\text {LS}(C,D)$ properties hold via their connection to $L_{\kappa \omega }$ or $L_{\kappa \lambda }$ : If $\phi \in L_{\infty \infty }$ , then $\phi \in L_{\kappa \lambda }$ for some (least) $\kappa $ and $\lambda $ and then Theorem 13 applies.

The above theorem shows that the spectra of $L_{\infty \infty }$ are much more complicated than the spectra of $L_{\infty \omega }$ . For example, let $\theta $ be the sentence (1) of $L_{\omega _1\omega _1}$ which has a model of cardinality $\mu $ if and only if $\mu ^\omega =\mu $ . Thus $\text {sp}(\theta )$ (i.e., $\text {sp}(\text {Mod}(\theta ))$ ) is full of “holes” as it misses all cardinals, such as e.g., each $\aleph _{\alpha +\omega }$ , that are $\omega $ -cofinal. Whereas the spectra of sentences of $L_{\kappa \omega }$ cannot have such holes above $\kappa $ . (See Figure 2.)

Figure 2

A difference between $L_{\infty \omega }$ and $L_{\infty \infty }$ .

What does it reveal about logicality if the spectrum is full of ‘holes’? It suggests that we are very far from the situation in which we can claim we have the same logical operation independently of the domain. In the case of $L_{\kappa ^+\omega }$ the spectrum is (above $\kappa $ ) a homogeneous segment of cardinals, either bounded by $\beth _{(2^\kappa )^+}$ or unbounded, and we are closer to having the same logical operation independently of the domain. Thus we judge a model class definable in $L_{\infty \omega }$ as having a greater degree of logicality than a model class definable in $L_{\infty \infty }$ .

In Definition 1 we defined the Löwenheim the Hanf number of an arbitrary logic. These numbers always exist if the class of formulas of the logic is a set. Thus they exist for $L_{\kappa \lambda }$ for any $\kappa $ and $\lambda $ but not for $L_{\infty \omega }$ and $L_{\infty \infty }$ .

The Hanf-number and Löwenheim number of $L^*$ can be easily defined in terms of spectra. Below a spectrum is called bounded if it is a set (rather than a proper class).

(6) $$ \begin{align}\ell(L^*)&=\textrm{sup} \{ \min(\text{sp}(\phi)):\phi\in L^*, \text{sp}(\phi)\ne\emptyset \}\notag\\h(L^*)& = \textrm{sup} \{ \textrm{sup}(\text{sp}(\phi)):\phi\in L^* \text{ and sp}(\phi)\ne\emptyset\ \text{is bounded}\}.\end{align} $$

We saw that Sagi employs Löwenheim numbers as a measure of logicality: the smaller the Löwenheim number the greater the degree of logicality. Thus model classes definable in $L(Q_\alpha )$ have a stronger degree of logicality than those definable in $L(Q_\beta )$ , for $\beta>\alpha $ .

The logic $L(Q_\alpha )$ satisfies for trivial reasons the Löwenheim–Skolem property $\text {LS}([\omega ,\aleph _\alpha ),\{\mu \})$ for all $\mu <\aleph _\alpha $ and the rather strong Löwenheim–Skolem property $\text {LS}([\aleph _\alpha ,\infty )),\{\mu \})$ for all $\mu \ge \aleph _\alpha $ . Thus the spectra have no holes and $\ell (L(Q_\alpha ))=\aleph _\alpha $ . It should be noted that the class size logic $L(Q_\alpha )_{\alpha \in \mathrm {On}}$ is a sublogic of $L_{\infty \infty }$ . Its spectra have a greater degree of regularity than those of $L_{\infty \infty }$ , and thus in that respect it resembles more $L_{\infty \omega }$ . In sum, these two logics, namely $L_{\infty \omega }$ and $L(Q_\alpha )_{\alpha \in \mathrm {On}}$ , both manifest a greater degree of logicality than $L_{\infty \infty }$ , if regularity in spectrum patterns is used as a criterion.

4 Is every model class definable in $L_{\infty \infty }$ irrespective of the cardinality?

Why is it that we cannot replace condition (2) of Theorem 7 with the apparently better condition

(7) $$ \begin{align} \mathcal{K} \text{ is definable in}\ L_{\infty\infty}? \end{align} $$

This would solve the problems of cardinality and domain-relativity—the logical concept would have the same definition in terms of a formal language independently of the cardinality of the domain. However, there is a very simple reason why condition (2) of Theorem 7 cannot be improved to (1): Not every model class is definable in $L_{\infty \infty }$ .

Recall the definition of $\mathcal {K}_{\text {lim}}$ above in §2. It is, strictly speaking, a generalized quantifier in the sense of Reference Mostowski[43] but a rather curious one. It is the existential quantifier in models of successor cardinality and the quantifier “for no x” in models of limit cardinality.

A different kind of generalized quantifier is the class

$$ \begin{align*}W_2=\{(A,<): (A,<)\cong (\alpha+\alpha,\in)\text{ for an ordinal } \alpha\}.\end{align*} $$

This is potential isomorphism closed and not definable even in $L_{\infty \infty }$ Reference Malitz[40]. Note that this model class is clearly second order definable. The model class $W_2$ has a particularly nice spectrum, its infinite part being simply the class of all infinite cardinals. This model class is also set-theoretically absolute (see below §5). In the light of the spectrum criterion, a model being an element of $W_2$ is a logical property of the model of a very high degree of logicality. Looking at a model, can we say that its being a well-order, let alone of a well-order of type $\alpha +\alpha $ for some $\alpha $ , is a logical property? Undoubtedly some would say it is a mathematical rather than a logical property. But it is logical in the Tarski–Sher sense and it has a second order definition which is the same definition in each cardinality. However much it feels like a genuinely mathematical concept, it fulfils the Tarski–Sher criterion of logicality, escapes two of Feferman’s criticisms, and fulfils Sagi’s as well as Bonnay’s criteria. So we may conclude that it is logical of a very high degree.

A third example of a model class undefinable in $L_{\infty \infty }$ is particularly interesting, namely the Härtig quantifier.

4.1 The Härtig quantifier

The Härtig quantifier is defined as follows:

$$ \begin{align*}\begin{array}{lcl} Ixy\phi(x)\psi(y)&\iff&\text{ there are as many } x\ \text{satisfying } \phi(x)\\&&\text{ as there are } y \text{ satisfying } \psi(y). \end{array}\end{align*} $$

Proposition 15 [Reference Herre, Krynicki, Pinus and Väänänen25]

The class of models $(M,A,B)$ , where $A,B\subseteq M$ and $|A|=|B|$ , is not definable in $L_{\infty \infty }$ . Equivalently, the Härtig quantifier is not definable in $L_{\infty \infty }$ .

Proof Two sentences of the logic $L_{\omega \omega }(I)$ are useful here: the sentence $\phi _{\mathrm {lim}}$ which has the class of limit cardinals as its spectrum, and the sentence $\phi _{suc}$ which has the class of infinite successor cardinals as its spectrum. The sentence $\phi _{\mathrm {lim}}$ says that the universe is totally ordered by a linear order in which every element determines an initial segment which has smaller cardinality than the initial segment determined by some bigger element. The sentence $\phi _{suc}$ says that the universe is totally ordered by a linear order in which some element determines an initial segment which has the same cardinality as the initial segment determined by any bigger element, but smaller cardinality than the entire universe. Suppose the Härtig quantifier was definable in $L_{\kappa ^+\kappa ^+}$ , where $\kappa $ is regular. Let $\lambda =2^\kappa $ . If $\lambda $ is a limit cardinal, we can use $\phi _{\mathrm {lim}}$ to derive a contradiction as follows: Let ${\mathcal M}$ be a model of $\phi _{\mathrm {suc}}$ of cardinality $\lambda ^+$ . By Theorem 13 there is a model ${\mathcal N}$ of cardinality $\lambda $ such that ${\mathcal N}\models \phi _{\mathrm {suc}}$ , a contradiction. The case that $\lambda $ is a successor cardinal is similar, but using $\phi _{\mathrm {lim}}$ instead of $\phi _{\mathrm {suc}}$ .

While the logic $L(I)$ with the Härtig quantifier is not a sublogic of $L_{\infty \infty }$ it has some of the properties of the latter that we associate with being very far from first order logic (see §7). For example, it is highly non-absolute. It is also unbounded i.e., capable of defining well-ordering with additional predicates Reference Lindström[32].

Note that the equicardinality concept, built around the existence of a bijection, lies at the very heart of the definition of logicality in the sense of Tarski! It is almost paradoxical then, that equicardinality itself, or more precisely the logic built on the equicardinality quantifier, represents a particularly weak degree of logicality.

5 Defining an arbitrary model class in an absolute logic, but still cardinal dependently

We shall now offer a refinement of McGee’s result (Theorem 7), by replacing $L_{\infty \infty }$ by a substantially weaker infinitary logicFootnote ³³ . Let us first note that we cannot replace $L_{\infty \infty }$ by $L_{\infty \omega }$ because the quantifier $Q_1$ is not CD-definable in the latter.Footnote ³⁴ For another example, the well-ordering quantifier

$$ \begin{align*}{\mathcal M}\models Wxy\phi(x,y,\vec{a})\iff\{(c,d):{\mathcal M}\models\phi(c,d,\vec{a})\}\text{ well-orders } M\end{align*} $$

is definable in $L_{\omega _1\omega _1}$ (see (1)) but not in $L_{\infty \omega }$ Reference Lopez-Escobar[35].

An important quality of $L_{\infty \omega }$ is its absoluteness. Let us recall:

For example, $L_{\infty \omega }$ and $L(W)$ are absolute logics but $L_{\infty \infty }$ is not.

We defined the $\Delta $ -operation in Definition 8. As argued for in Reference Makowsky, Shelah and Stavi[39], $\Delta (L^*)$ can be considered a logic in itself. There is a many-sorted version and a single-sorted version of the $\Delta $ -extension. In the many-sorted version the model class $\mathcal {K}$ may have a many-sorted vocabulary. If $L^*$ is the logic $L_{\infty \omega }$ , or $L_{\kappa ^+\omega }$ , for regular $\kappa $ , there is no difference between the two versions i.e., they coincide Reference Oikkonen, Jensen, Mayoh and Møller[44]. Therefore we continue with the single-sorted version.

Some of the nice properties of the $\Delta $ -operation are:

• • Exactly the same classes of cardinals are spectra of $\Delta (L^*)$ as are of $L^*$ .

• • $\Delta (L^*)$ satisfies $LS(C,D)$ iff $L^*$ does.

• • $\Delta (L^*)$ satisfies the Compactness Theorem iff $L^*$ does.

• • $\Delta (L^*)$ satisfies the (abstract) Completeness TheoremFootnote ³⁵ iff $L^*$ does.

• • If $L^*$ satisfies the Craig Interpolation Theorem, then $\Delta (L^*)$ and $L^*$ are equivalent logics.

• • $\ell (\Delta (L^*))=\ell (L^*)$ .

• • $h(\Delta (L^*))=h(L^*)$ .Footnote ³⁶

If $L^*$ is an absolute logic in the sense of Reference Barwise[4], then $\Delta (L^*)$ is still absolute in the weaker sense that every definable model class is $\Delta _1$ -definable in set theory (with the defining sentence as a parameter). This is a direct consequence of the definition of $\Delta (L^*)$ . However, $\Delta (L^*)$ has a complication which prevents us from concluding that the $\Delta $ -operation preserves absoluteness. Namely, there may be an absolute logic $L^*$ and model classes $\mathcal{K}_0$ and $\mathcal{K}_1$ such that both $\mathcal{K}_0$ and $\mathcal{K}_1$ are in $\Sigma (L^*)$ , $\mathcal{K}_0\cap \mathcal{K}_1= \emptyset $ but the proposition that every model (of the right type) is in $\mathcal{K}_0$ or $\mathcal{K}_1$ is not absolute.Footnote ³⁷ Thus we may not have a $\Sigma _1$ -definition for the set of sentences of $\Delta (L^*)$ even if we have for $L^*$ . Despite this shortcoming of the $\Delta $ -operation, we do have a $\Sigma _1$ -definition for the set of sentences of $\Sigma (L^*)$ when $L^*$ is absolute because with $\Sigma (L^*)$ the above problem ( $\mathcal{K}_0$ and $\mathcal{K}_1$ ) does not arise.

Proof The proof is similar to the proof of Theorem 7 in Reference McGee[41]. Recall the formulas $\eta ^{\prime }_\alpha $ and $\eta ^{\prime }_\alpha $ defined in (1) and (3), with the properties (2) and (4). Suppose $\mathfrak {A}$ is a model of the vocabulary L and $|A|=\lambda $ . Let $f_A:\lambda \to A$ be a bijection and $a<_Ab\iff f_A^{-1}(a)<f_A^{-1}(b)$ . For $\alpha ,\beta <\lambda $ let

$$ \begin{align*}\rho_{\alpha,\beta}(x,y)=\left\{\begin{array}{ll} R(x,y)&\text{ if } \mathfrak{A}\models R(f_A(\alpha),f_B(\beta)),\\ \neg R(x,y)&\text{ if }\mathfrak{A}\not\models R(f_A(\alpha),f_B(\beta)). \end{array}\right.\end{align*} $$

Let

$$ \begin{align*}\Phi_{\mathfrak{A}}\leftrightarrow\forall x\forall y\bigwedge_{\alpha,\beta<\lambda}((\eta_\alpha(x)\wedge\eta_\beta(y))\to\rho_{\alpha,\beta}(x,y)).\end{align*} $$

Now $(\mathfrak {A},<_A)\models \eta ^{\prime }_\lambda $ and $(\mathfrak {A},<_A)\models \eta _\alpha (a)\iff a=f_A(\alpha )$ . Hence $(\mathfrak {A},<) \models \eta ^{\prime }_\lambda \wedge \Phi _{\mathfrak {A}}.$ On the other hand, $(\mathfrak {A}^{\prime },<^{\prime })\models \eta ^{\prime }_\lambda \wedge \Phi _{\mathfrak {A}}$ implies $\mathfrak {A}'\cong \mathfrak {A},$ for if $(\mathfrak {A}^{\prime },<^{\prime })\models \eta ^{\prime }_\lambda \wedge \Phi _{\mathfrak {A}}$ and $g:(A^{\prime },<')\cong (A,<_A)$ , then $g:\mathfrak {A}'\cong \mathfrak {A}$ . Let

$$ \begin{align*}\Theta_{\mathcal{K}}\leftrightarrow\bigvee\{\Phi_{\mathfrak{A}}\ : \ \mathfrak{A}\in\mathcal{K}, A=\lambda\}.\end{align*} $$

Now by the above,

$$ \begin{align*}\begin{array}{lcl} \mathfrak{A}\in\mathcal{K}_\lambda&\iff&(\mathfrak{A},<)\models\eta^{\prime}_\lambda\wedge\Theta_{\mathcal{K}}\text{ for some } < \\ &\iff&(\mathfrak{A},<)\models\eta^{\prime}_\lambda\to\Theta_{\mathcal{K}}\text{ for all } <. \end{array}\end{align*} $$

Since $\eta ^{\prime }_\lambda ,\Theta _{\mathcal {K}}\in L_{(2^\lambda )^+\omega }$ , we are done.

Why is this an improvement? $\Delta (L_{\infty \omega })$ is a sublogic of $L_{\infty \infty }$ , a consequence of the result of Malitz Reference Malitz[40] to the effect that for regular $\kappa $ a valid implication in $L_{\kappa \omega }$ can be interpolated in $L_{2^{(<\kappa )^+\kappa }}$ . It is a proper sublogic because well-ordering is definable in the latter but not in the former. Secondly, the logic $L_{\infty \omega }$ is an absolute logic Reference Barwise[4] and $\Delta (L_{\infty \omega })$ inherits much of the absoluteness of $L_{\infty \omega }$ (see above) while $L_{\infty \infty }$ is badly non-absolute.

The improvement that Theorem 18 represents over Theorem 7 is also based on the fact that $L_{\infty \omega }$ , and thereby also $\Delta (L_{\infty \omega })$ , is a much “tamer” logic than $L_{\infty \infty }$ . In particular:

• • $\Delta (L_{\infty \omega })$ , even $\Sigma (L_{\infty \omega })$ , has a strong Löwenheim–Skolem theorem. This is in contrast to $L_{\infty \infty }$ , which does not have a Löwenheim–Skolem theorem in the same strong form (see Theorem 13).

• • The class of well-orderings is not definable in $\Delta (L_{\infty \omega })$ , while it is definable in $L_{\omega _1\omega _1}$ (see (1)). This is a kind of threshold difference. In general, logics in which the concept of well-order is not definable are much better behaved (in many different respects) than those in which it is. If well-order is definable, the logic can talk about well-founded models of set theory, and thereby about transitive models of set theory. In this way the logic can break through the object theory/metatheory barrier and have access to the background set theory. For a concrete example, consider a sentence $\phi $ which is the conjunction of a sufficiently large finite part $T_0$ of the ZFC axioms, the first order set-theoretical statement $\phi _0$ that there are no inaccessible cardinals, and the $L_{\omega _1\omega _1}$ -sentence

  (8) $$ \begin{align} \displaystyle{\forall x_0\forall x_1\ldots\bigvee_{n<\omega}}\neg x_{n+1}\in x_n. \end{align} $$
  Suppose $\kappa $ is the smallest inaccessible cardinal. Then $\phi $ has a model of cardinality $\kappa $ , namely $V_\kappa $ , but none of bigger cardinality. For suppose M is a model of $\phi $ of cardinality $>\kappa $ . By Mostowski’s Collapsing Lemma Reference Mostowski[42] we may assume M is a transitive model of $T_0$ . Since the cardinality of M is bigger than $\kappa $ , the ordinal $\kappa $ is in M and is therefore inaccessible in M by the downward persistency of inaccessibility. But this contradicts the fact that M is a model of $\phi _0$ . This argument, due to Silver Reference Silver[50], demonstrates the power of (1) to penetrate the object theory/metatheory barrier, which sentences of $\Delta (L_{\infty \omega })$ are unable to do Reference Lopez-Escobar[35].

• • The Hanf number of $\Delta (L_{\kappa ^+\omega })$ is only moderately large, namely $<\beth _{(2^\kappa )^+}$ , while the Hanf number of $L_{\omega _1\omega _1}$ is bigger than the first weakly inaccessible cardinalFootnote ³⁸ (and consistently bigger than the first measurable cardinal). The smallness of the Hanf number is another indication of regularity of patterns in spectra (see (5)).

A weakness of $\Delta (L_{\infty \omega })$ as compared to $L_{\infty \infty }$ is that the former does not have as explicit a syntax as the latter, although we can overcome this by replacing $\Delta (L_{\infty \omega })$ by $\Sigma (L_{\infty \omega })$ . A strength is that its spectra are as regular as those of $L_{\infty \omega }$ , it is equally completely axiomatizable as $L_{\infty \omega }$ , and it is absolute in the sense that its definable model classes are absolute in set theory. Thus it avoids Feferman’s second and third criticisms.

6 Sort logic

We can ask, is there a logic in which every model class whatsoever is definable, irrespective of the cardinality of the domain? That is, not just cardinal dependently? We know already $L_{\infty \infty }$ is not that kind of a logic (§4). McGee points out that we could take a class size disjunction of $L_{\infty \infty }$ sentences and obtain a single ‘sentence’ which works in all cardinalities. As he points out, if we accept class size formulas we should also accept class size logical operations and then we are back in the starting point: to account for class size logical operations we need classes of classes and we start climbing up the type hierarchy beyond first order set theory. If we stick to set size logical operations we can operate within first order set theory.

We could, of course, take every model class as a generalized quantifierFootnote ³⁹ but there is a more canonical logic for this task.

In Reference Väänänen, Chong, Feng, Slaman and Woodin[57] a logic $L^s$ called sort logic was introduced. It is a kind of many-sorted version of second order logic $L^2$ , which allows quantification not only over subsets and relations on the domain of the model but also over subsets and relations on new domains outside the current one. Such quantification happens, for example, when we ask of a given group, whether it is the multiplicative group of a field? We have to “guess” the addition of the field but also the neutral element $0$ and those are both outside the multiplicative group.

More exactly, sort logic arises from $L^2$ by repeated applications of operation $L^*\mapsto \Sigma (L^*)$ (see Definition 8) and negation. Let us define $\Delta _0=L^2$ . If $\Delta _n$ has been defined, let $\Delta _{n+1}$ consist of model classes $\mathcal {K}$ such that both $\mathcal {K}$ and the complement of $\mathcal {K}$ are $\Sigma (\Delta _n(L^2))$ -definable. We get an increasing hierarchy of logics

$$ \begin{align*}\Delta_1\le\Delta_2\le \Delta_3\le \cdots\end{align*} $$

the union of which is sort logic. A fine point is that every level $\Delta _n$ of sort logic is definable in set theory but there is no single formula that defines the entire sort logic.

The above characterization of isomorphism closure is not as elegant as McGee’s theorem 7 simply because the definition of sort logic is more complicated than that of $L_{\infty \infty }$ . However, this theorem has the remarkable advantage over Theorem 7 that the definition of the model class in sort logic holds for models of all cardinalities. As McGee points out, if he wanted to obtain the same level of generality with his method, he would have to take a disjunction of a proper class of $L_{\infty \infty }$ -formulas. Sort logic may be complicated but at least its formulas are sets and not proper classes. In McGee’s case we may need a formula which is not even a set. In the case of sort logic each formula is a set, but the whole logic is not definable, only each level $\Delta _n$ separately is.

7 Is having a Completeness theorem a marker of logicality?

We saw that first order logic and $\mathcal {L}(Q_0)$ are maximally logical under Sagi’s criterion, grading the logicality of these logics by their Löwenheim numbers. We also saw that the degree of logicality of the logics $\mathcal {L}(Q_{\alpha })$ decreases as $\alpha $ increases: if $\alpha \leq \beta $ , then $Q_{\beta }$ is less logical than $Q_{\alpha }$ .

As for other kinds of quantifiers, the quantifiers “more” or Rescher quantifier

$$ \begin{align*}\begin{array}{lcl} Jxy\phi(x)\psi(y)&\iff&\text{there are at least as many } x \text{ satisfying } \phi(x)\\ &&\text{as there are } y \text{ satisfying }\psi(y) \end{array}\end{align*} $$

and the equicardinality or Härtig quantifier (see §4.1) both have the same (very high) Löwenheim number, and are thus less logical than $Q_{\alpha }$ at least for $\alpha $ below the first $\alpha $ such that $\alpha =\aleph _\alpha $ .Footnote ⁴¹ We suggested earlier that the Härtig quantifier is a singular case, in seeming to express the core concept of isomorphism invariance, which is defined in terms of the concept of equicardinality. Under our criteria, the Härtig quantifier is classified as (only) weakly logical even so, not only due to its high Löwenheim number but also because it lacks very seriously a complete axiomatization Reference Väänänen[54].

We remarked earlier that Sagi’s demarcation of logicality for a fixed class of logical constants, which is based on Löwenheim numbers, partitions logical space differently than ours. As we observed, logics that have a completeness theorem do not seem to be tied to the $\aleph $ -hierarchy in any obvious way. For example, Keisler’s axioms

(9) $$ \begin{align} \left\{\begin{array}{ll} \text{Axiom} 0 &\text{Axiom schemes for }\mathcal{L}_{\omega\omega}\\ \text{Axiom} 1 &\neg Qx(x=y\vee x=z)\\ \text{Axiom} 2 &\forall x(\phi\to\psi)\to(Qx\phi\to Qx\psi)\\ \text{Axiom} 3 &Qx\phi(x)\to Qy\phi(y)\\ \text{Axiom} 4 &Qy\exists x\phi\to(\exists xQy\phi\vee Qx\exists y\phi) \end{array}\right. \end{align} $$

are complete for $\mathcal {L}(Q_1)$ , and if $GCH$ is assumed, then they are complete for all $\aleph _{\alpha +1}$ for which $\aleph _{\alpha }$ is regular (hence for $\aleph _n$ for all $n>0$ ). Whereas while $\mathcal {L}(Q_0)$ satisfies the Keisler Axioms, these (or any other recursive set of axioms) are not a complete axiomatisation of $\mathcal {L}(Q_0)$ .Footnote ⁴²

The suggestion here is that having a complete axiomatisation should be a marker of logicality on the simple ground that logics of this kind resemble first order logic in one of its essential, if not most essential property, namely completeness. Except for $Q_0$ , one would then classify “there are very (i.e., uncountably) many” as logical, as dictated by Keisler’s axioms; in particular, the quantifier $Q_1$ would be graded as having a higher degree of logicality than $Q_0$ , as $\mathcal {L}(Q_1)$ is complete with respect to the Keisler Axioms whereas $\mathcal {L}(Q_0)$ is not complete in this respect.Footnote ⁴³ In short, our criterion of logicality, which turns on the degree to which a logic resembles first order logic in its model theoretic properties, comes apart from Sagi’s already at the level of the logics $\mathcal {L}(Q_0)$ and $\mathcal {L}(Q_1)$ .

A possible objection might come from the fact that Keisler’s axioms are satisfied by many different quantifiers, in fact by every $Q_\alpha $ , where $\aleph _\alpha $ is regular. On the other hand, we may consider $Q_1$ logical admitting that from the point of view of logicality it cannot be separated from some other similar quantifiers. What is logical, according to this view, is not so much the cardinality $\aleph _1$ , as, simply, uncountable cardinality—or “very many”—in general, while the failure of $Q_0$ to permit a recursive axiomatization is an indication that there is something mathematical, as against logical, in $Q_0$ . The permutation invariance characterization of logicality does not differentiate between $Q_1$ and $Q_0$ , as the Completeness Theorem criterion does. By the invariance criterion every $Q_\alpha $ is logical, which may seem unintuitive. By further applying the Completeness theorem criterion we can make finer distinctions and see a difference: $Q_1$ is “more logical” than $Q_0$ .

For singular strong limit $\aleph _{\alpha }$ Keisler Reference Keisler, van Rootselaar and Staal[30] proved a Completeness theorem, but with different axioms (no simple set of axioms is currently known). Thus there are (at least) two different “logical” concepts of “very many,” one for $\aleph _{\alpha }$ the successor of regular and one for the singular case. (Successor of singular is open.) The two concepts have different logical content: Keisler’s Axioms for $Q_{\alpha }$ are valid for all regular $\aleph _\alpha $ , and in some cardinalities (successor of regular) they have a Completeness theorem, modulo the $GCH$ , as was noted above. In some other cardinalities (singular) different axioms have to be employed in order to get a completeness theorem. In the base case $\alpha =0$ no effectively given additional axioms can be added to give a completeness theorem.

According to Sagi, “We should distinguish between a logic $\mathcal {L}(Q)$ used to measure the logicality of Q and the logic we ultimately use for validity and logical consequence.”Footnote ⁴⁴ But if metaphysical involvement is inversely related to logicality, then having a completeness theorem should possibly be considered as a marker of logicality also under the Sagi criterion. This is because what the completeness theorem precisely does is to enable the conversion of semantic content, which is metaphysically involved (from the Sagi point of view, presumably), into syntactic content which, presumably, is not. In this connection, the following caveat is important: As Carnap observed [Reference Carnap16] the rules do not fix the interpretation of the logical constants, they have non-standard interpretations. In their Reference Bonnay and Westerståhl[12] Bonnay and Westerståhl present a way to sidestep the problem:

There is also the issue of expressive power, with respect to which the logics built on the quantifiers “most,” “more” and the Härtig quantifier differ. In certain models with an equivalence relation the Härtig quantifier can be seen to be eliminable while the Rescher quantifier is not Reference Hauschild[24]. Thus the Rescher quantifier is strictly stronger than the Härtig quantifier from the point of view of expressive power. The point here is that expressive power should be inversely related to logicality.

Bonnay also ties logicality to syntax via a Completeness theorem, as is spelled out in some detail in [Reference Bonnay10].Footnote ⁴⁵ Here Bonnay proposes a modification of the program of Carnap’s Aufbau [Reference Carnap18], calling for logical expressions to be defined syntactically. It is a feature of his treatment that the absoluteness of a logic plays a crucial role in guaranteeing the robustness of the syntactic definition. Thus $L(Q_0)$ is an absolute logic because it has a recursive syntax, just like first order logic, and its semantics is absolute in transitive models of (even weak) set theory.Footnote ⁴⁶ On the other hand, $L(Q_1)$ is not absolute, even though it has a recursive syntax.Footnote ⁴⁷

Burgess’s Reference Burgess[14] forges a link between absoluteness and the idea of having a proof procedure. He exhibits a quasi-constructive complete proof procedure involving rules with $\aleph _1$ premisses for the hereditary countable part of any absolute logic.

In sum, if one classifies the first order existential quantifier “there is at least one,” as inherently logical, and if as such this quantifier is thought of as having minimal or no semantic content, then is there a principled way to determine when and how higher quantification acquires semantic content, e.g., at what level in the cumulative hierarchy? Sagi’s answer is that logicality diminishes the higher up we are in cumulative hierarchy; while we suggest that logicality kicks in arbitrarily high up, e.g., for all $\aleph _{\alpha +1}$ for which $\aleph _{\alpha }$ is regular, with the $\aleph _0$ case an anomaly, again because of completeness. The intuition here is that logics which have a completeness theorem are close to first order logic in this special sense. This is because completeness enables the conversion of semantic consequence into syntactic consequence via the two Keisler axiomatisations—albeit conditioned on the continuum hypothesis in certain important cases.Footnote ⁴⁸