Lowenheim numbers for ordinary language quantifiers

Question

(First posted in StackExchange)

I am interested in the Löwenheim numbers associated with quantifiers that are prevalent in ordinary language use, such as "more" and "most".

Definition: The Löwenheim number of a logic L, $\ell$(L), is the least cardinal $\mu$ such that any satisfiable sentence in L has a model of cardinality less or equal to $\mu$ if such exists. Otherwise, $\ell$(L)=$\infty$.

For a logic L and a quantifier $Q$, let L($Q$) be the logic L with $Q$ added to its language. Let $\mathcal{L}$ denote standard first order logic.

So, for instance: Let $Q_\alpha$ be the unary monadic quantifier ``there are at least $\aleph_\alpha$ many''. We have $\ell$($\mathcal{L}(Q_\alpha)$)=$\aleph_\alpha$ for each ordinal $\alpha$.

Another example: Let the Härtig quantifier $I$ be the binary monadic quantifier stating equal cardinality of sets: $I$ is a binary monadic quantifier such that $M\models Ix(\varphi x,\psi x)$ iff $|(\varphi x)^M|=|(\psi x)^M|$. $\ell(\mathcal{L}(I))$ is very high, and is independent of ZFC. $\ell(\mathcal{L}(I))$ is a fixed point of the function $\alpha\mapsto\aleph_\alpha$, and further, Magidor and Väänänen showed that it is consistent with ZFC both that $\ell(\mathcal{L}(I))$ is under the first weakly inaccessible cardinal and that it is above the measurable cardinal (Magidor and Väänänen, 2011).

Are there known results for "most" and "more"? I could only find the following bounds:

Let $Most$ be the binary monadic quantifier such that $M\models Most\ x (\varphi x, \psi x)$ iff $|(\varphi x)^M\backslash (\psi x)^M|<|(\varphi x)^M\cap(\psi x)^M|$. Then I've found the following lower bound: $\ell(\mathcal{L}(Most))\geq\aleph_\omega$.

Let $More$ be the binary monadic quantifier such that $M\models More\ x (\varphi x, \psi x)$ iff $|(\varphi x)^M|>|(\psi x)^M|$. Then we have both $\ell(\mathcal{L}(More))\geq\ell(\mathcal{L}(I))$ and $\ell(\mathcal{L}(More))\geq\ell(\mathcal{L}(Most))$ (due to considerations of expressive power).

Are there better results? And are there other quantifiers from ordinary language that have interesting results?

Answer 1

$\def\L#1{\mathcal L(#1)}\let\fii\varphi\let\eq\leftrightarrow\DeclareMathOperator\I{I}\DeclareMathOperator\most{Most}\DeclareMathOperator\more{More}$I don’t know what other quantifiers from ordinary language are there in the wild, but the three mentioned in the question have the same Löwenheim number:

Theorem: $\ell(\L\I)=\ell(\L\most)=\ell(\L\more)$.

As already noted in the question itself, the inequalities $$\ell(\L\I)\le\ell(\L\more),\qquad\ell(\L\most)\le\ell(\L\more)$$ follow immediately from the fact that the quantifiers $\I x$ and $\most x$ are definable from $\more$ using $$\begin{align*} \I x\,(\fii x,\psi x)&\eq\neg\bigl(\more x\,(\fii x,\psi x)\lor\more x\,(\psi x,\fii x)\bigr),\\ \most x\,(\fii x,\psi x)&\eq\more x\,(\fii x\land\psi x,\fii x\land\neg\psi x). \end{align*}$$

For the $$\ell(\L\more)\le\ell(\L\most)$$ inequality, note that $\more$ is almost definable from $\most$: if $(\fii x)^M$ or $(\psi x)^M$ is infinite, then $$M\models\more x\,(\fii x,\psi x)\eq\most x\,(\fii x\lor\psi x,\neg\psi x).$$ Rather than trying to figure out if we can fix this definition to work for finite sets as well, let me use a different approach: we expand the models in such a way that we can define disjoint union.

Let $\alpha$ be an $\L\more$-sentence. Choose a fresh binary function symbol $p(x,y)$ and constants $a,b$. Let $\theta$ be the FO sentence stating that $p$ is a pairing function, and $a\ne b$. Let $\alpha^*$ be the sentence $\alpha$ in which each subformula of the form $$\more x\,(\fii x,\psi x)$$ is replaced with $$\most z\,(\fii'z\lor\psi'z,\fii'z),$$ where $$\begin{align*} \fii'z&\eq\exists x\,(z=p(x,a)\land\fii x),\\ \psi'z&\eq\exists x\,(z=p(x,b)\land\psi x). \end{align*}$$ Clearly,

• any infinite model in the signature of $\alpha$ can be expanded to a model of $\theta$, and

• if $M\models\theta$, then $M\models\alpha\eq\alpha^*$.

Thus, for any infinite $\kappa$,

$\alpha$ has a model of cardinality $\kappa$ if and only if the $\L\most$-sentence $\theta\land\alpha^*$ has a model of cardinality $\kappa$.

Since $\alpha$ was an arbitrary $\L\more$-sentence, $\ell(\L\more)\le\ell(\L\most)$ follows.

For the remaining $$\ell(\L\more)\le\ell(\L\I)$$ inequality, we can use a similar expansion approach. Let $\alpha$ be an $\L\more$-sentence, and let $<$ be a fresh binary relation symbol. We define $\L\I$-sentences $\alpha^\#$ and $\xi$ as follows:

$\alpha^\#$ is $\alpha$ with each subformula $$\more x\,(\fii x,\psi x)$$ replaced with $$\exists v\,(\I x\,(\psi x,x<v)\land\forall u\,(\I x\,(\fii x,x<u)\to v<u)),$$ that is: there is an initial segment of $<$ of the same size as $(\psi x)^M$ whose no initial segment has the same size as $(\fii x)^M$.

Let $\xi$ be the conjunction of the formulas

• $<$ is a (strict) linear order,

• $\forall\vec y\,\exists u\,\I x\,(\fii(x,\vec y),x<u)$,

for every subformula $\fii(x,\vec y)$ of $\alpha^\#$ with all variables shown (we only need subformulas involved in the translations of $\more$ as above, of course); in words, every definable set in sight has the same size as an initial segment. Again, it is easy to see that

• every infinite model $M$ in the signature of $\alpha$ has an expansion to a model of $\xi$: indeed, if $|M|=\lambda$, then any well order $<$ on the domain of $M$ of type at least $\lambda+1$ will do;

• if $M$ is a model of $\xi$, then $M\models\alpha\eq\alpha^\#$.

Consequently,

$\alpha$ has a model of cardinality $\kappa$ if and only if the $\L\I$-sentence $\xi\land\alpha^\#$ has a model of cardinality $\kappa$

for infinite $\kappa$.