6
$\begingroup$

(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?

$\endgroup$
  • 1
    $\begingroup$ As far as I can see, More and Most have the same expressive power: if at least one of the sets is infinite, $\operatorname{More}x\,(\phi x,\psi x)\leftrightarrow\operatorname{Most}x\,(\phi x\lor\psi x,\phi x)$. $\endgroup$ – Emil Jeřábek Sep 7 '16 at 8:50
  • $\begingroup$ Thanks, both! @EmilJeřábek, is the claim that: $\ell$($\mathcal{L}(More)$)=$\ell$($\mathcal{L}(Most,Q_0)$)=$\ell$($\mathcal{L}(Most)$)? $\endgroup$ – Sagi Sep 7 '16 at 16:49
  • $\begingroup$ @EmilJeřábek, that can't quite be right: let $\phi x$ be $x \ge 0$, let $\psi x$ be $x \ge 1$. Then the RHS of your equivalence holds but the LHS does not. And in this general context we can not assume that we have a pairing function available to create distinct copies of the sets. $\endgroup$ – Matt F. Sep 7 '16 at 17:22
  • 1
    $\begingroup$ @MattF.: You’re right, the RHS should rather be $\operatorname{Most}x\,(\phi x\lor\psi x,\neg\psi x)$. Anyway, we can in fact assume to have a pairing function, as I will mention shortly in an answer. I was just trying to avoid it here for simplicity. $\endgroup$ – Emil Jeřábek Sep 7 '16 at 17:47
4
$\begingroup$

$\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$.

$\endgroup$
  • $\begingroup$ Not sure if it is right to post here and ask. Is it correct to say 'the quantifier-free fragment of first order theory of real numbers' is feasibility Linear Programming, 'the quantifier-free fragment of first order theory of integers' (fragment of Presburger arithmetic) is feasibility Integer Linear Programming and 'the quantifier-free fragment of first order theory of real numbers with integers as a distinguished subset' is feasibility Mixed Integer Linear Programming and with single $\exists$ quantifier these become optimization versions of LP, ILP and MILP respectively? $\endgroup$ – 1.. Jul 16 '18 at 11:35
  • 1
    $\begingroup$ No, this does not make much sense to me. $\endgroup$ – Emil Jeřábek Jul 17 '18 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.