Proof of undefinability of the "Most" quantifier in first-order logic

Question

I believe that the quantifier "Most $x$ have property $P$" is not first-order definable, that is, not definable using universal and existential quantifiers and equality. More precisely, if we restrict our attention to the class of finite $\{P\}$-structures, (where $P$ is a unary predicate symbol), there is no formula of first-order logic that holds precisely of those structures where the cardinality of the set $\{x | P(x)\}$ is strictly greater than its complement $\{x | \neg P(x)\}$. However, I want to see a proof of that statement. It is intuitively plausible to me, but I want a proof that there is no clever way to define that quantifier.

Answer 1

I shall sketch out a proof on a line of an argument that I learnt from Fred Landman's Structures for Semantics (Kluwer Academic Publishers, 1991). Let us first construe the grammatical quantifier most in a mathematical setting.

Suppose we have two sets $A$ and $B$. We denote the elements of the set $A$ by $\alpha$s and the elements of $B$ by $\beta$s. By the sentence

$$\text{most $\alpha$s are $\beta$s}$$

we understand that there are more $\alpha$s that are $\beta$s than $\alpha$s that are not $\beta$s. In set-theoretical terms,

$$\lvert A\cap B\rvert >\lvert A\backslash B\rvert$$

where $\lvert\;\rvert$ denotes the cardinality of a set.

Assume that there is a first-order formula $\upsilon(A, B)$ expressing this relation:

$$\text{most $\alpha$s are $\beta$s}\iff\upsilon(A, B)$$

First, we take up the infinite case. Let the predicate $P(x)$ express that $x$ is $\beta$. Using $P(x)$, we can set down two sequences of first-order formulas:

$\phi_{1}\equiv\exists x_{1}P(x_{1});\qquad\qquad\qquad\qquad\qquad\qquad\;\;\psi_{1}\equiv\exists x_{1}P(x_{1})$

$\phi_{2}\equiv\exists x_{1}\exists x_{2}(P(x_{1})\wedge P(x_{2})\wedge x_{1}\neq x_{2});\qquad\psi_{2}\equiv\exists x_{1}\exists x_{2}(\neg P(x_{1})\wedge\neg P(x_{2})\wedge x_{1}\neq x_{2})$

$\qquad\qquad\qquad\qquad\qquad\vdots\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\vdots$

Thus, we have formulas expressing for any $k$ that at least $k\,\alpha$s are $\beta$s (to use as a reference to $\lvert A\cap B\rvert$)

$$\phi_{k}\equiv\exists x_{1}\exists x_{2}\cdots\exists x_{k}(P(x_{1})\wedge P(x_{2})\cdots\wedge P(x_{k})\wedge x_{1}\neq x_{2}\cdots\neq x_{k})$$

and that at least $k\,\alpha$s are not $\beta$s (to use as a reference to $\lvert A\backslash B\rvert$)

$$\psi_{k}\equiv\exists x_{1}\exists x_{2}\cdots\exists x_{k}(\neg P(x_{1})\wedge\neg P(x_{2})\cdots\wedge\neg P(x_{k})\wedge x_{1}\neq x_{2}\cdots\neq x_{k})$$

We collect all these formulas into a set $\Gamma =\{\upsilon(A, B), \phi_{1}, \phi_{2},\ldots, \psi_{1}, \psi_{2},\ldots\}$. Notice that from the model-theoretic aspect, $\Gamma$ is a theory.

A finite subset $\Gamma_{0}$ of $\Gamma$ is composed of some $\phi$-formulas, some $\psi$-formulas, and possibly, $\upsilon(A, B)$. Thus, $\Gamma_{0}$ states, in effect, that at least $n$ $\alpha$s are $\beta$s (i.e., $\lvert A\cap B\rvert\geq n$) and at least $m$ $\alpha$s are not $\beta$ (i.e., $\lvert A\backslash B\rvert\geq m$). $\Gamma_{0}$ has a model if $n>m$.

By the compactness theorem, there is a model of the theory $\Gamma$ if and only if every finite subset $\Gamma_{0}$ of it has a model. Since any model of $\Gamma$ must satisfy all of the $\phi$-formulas and the $\psi$-formulas, $\Gamma$ has infinite models only. We may observe that both $A\cap B$ and $A\backslash B$ must be infinite on those models.

By Löwenheim-Skolem theorem, since $\Gamma$ has a model, it has a countable model $\mathfrak{A}$. So, $\mathfrak{A}\vDash\upsilon(A, B)$. Since $\mathfrak{A}$ is countable, both $A\cap B$ and $A\backslash B$ are countable. As noted, $A\cap B$ and $A\backslash B$ are infinite on $\mathfrak{A}$. Therefore, $\lvert A\cap B\rvert = \lvert A\backslash B\rvert$. Hence, $\mathfrak{A}\not\vDash\text{most $\alpha$s are $\beta$s}$, whereas, ex hypothesi, $\mathfrak{A}\vDash\upsilon(A, B)$. Therefore, contrary to our assumption, $\upsilon(A, B)$ does not define $\text{most $\alpha$s are $\beta$s}$.

Next, let us consider the case of finite models; we inspect whether there is a first-order formula $\upsilon$ such that for all $\mathfrak{A}_{<\omega}$

$$\mathfrak{A}_{<\omega}\vDash\text{most $\alpha$s are $\beta$s}\iff\mathfrak{A}_{<\omega}\vDash\upsilon(A, B)$$

That is, when interpreted, whatever the cardinalities of the sets involved in $\mathfrak{A}_{<\omega}$ are, $\upsilon(A, B)$ must be true whenever $\text{most $\alpha$s are $\beta$s}$ is true.

Depending on its complexity (measured by the number of quantifiers in the equivalent formula in prefix form or by the maximal blocks of the same type, existential or universal, quantifiers), every first-order formula has a bounding number $N$ above which the truth-value of the formula remains invariant (true or false) irrespective of the cardinalities of the sets involved. Thus, any combination of $\phi$-formulas and $\psi$-formulas have such an $N$.

As for the sentence $\text{most $\alpha$s are $\beta$s}$, there is no bounding number $N$; its truth-value varies with $\lvert A\cap B\rvert$ and $\lvert A\backslash B\rvert$.

We can see this by setting $\lvert A\cap B\rvert$ to $n$ and $\lvert A\backslash B\rvert$ to $m$. If $n>m$, the sentence is true. If $\lvert A\backslash B\rvert$ to a $k$ such that $k>n$, the truth-value of the sentence alternates to false. If $\lvert A\cap B\rvert$ to an $l$ such that $l>k$, the truth-value alternates to true. Since $k, l, n, m$ are arbitrary numbers, whatever $N$ we assume, there is a counter-example to it. Hence, a formula $\upsilon$ formalising the sentence $\text{most $\alpha$s are $\beta$s}$ cannot be first-order. Consequently, the quantifier most, as we know it from the grammar of natural language, is not definable also on finite models.

Answer 2

I think your claim follows from this zero-one law for first-order sentences in finite models.

If $\sigma$ consists of a single unary predicate $P$, then the probability that a random $\sigma$-structure of cardinality $n$ satisfies "most $x$ have property P" approaches $\frac12$ as $n\to\infty$, so this sentence cannot be first-order.