Proof of undefinability of the “Most” quantifier in first-order logic

logicquantifiers

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.

Best Answer

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.