2

In first-order logic with equality, we can define "there exists at least $n$ objects $x$ such that $P(x)$", for each specific positive integer $n$. However, I think this probably can't be done in first-order logic without equality, except for the trivial case $n=1$. But how to formally prove that it can't be done? More generally, is it true that if we add finitely many quantifiers $Q_2, Q_3, .... , Q_n$ to the language, where $Q_k$ means "there are at least $k$ objects such that", then we still will not be able to define all the remaining quantity quantifiers, $Q_{n+1}, Q_{n+2}, ... $ etc?

user107952
  • 20,508

1 Answers1

2

Let $L_n$ be first-order logic without equality augmented by the quantifiers "$\exists^{\ge k}$" for $k\le n$. I'll take the approach that in $L_n$ we do have the symbol "$=$," but it can be interpreted as any equivalence relation; of course it doesn't affect the details.

To show inexpressibility of $\exists^{\ge n+1}$ in $L_n$ we just have to exhibit a pair of structures which are $L_n$-equivalent but are not $L_{n+1}$-equivalent. And this is easy to do: for each $i$, let $A_i$ be the "pure indiscrete set," that is the structure in the empty language where "$=$" is interpreted trivially ($x=y$ for all $x,y$) with $i$ elements. You can show$^*$ that $Th_{L_n}(A_i)=Th_{L_n}(A_j)$ whenever $i,j<n$ or $i,j\ge n$, but clearly if $i<n\le j$ then $Th_{L_n}(A_i)\not=Th_{L_n}(A_j)$ (the latter contains "$\exists^{\ge n}x(x=x)$" but the former doesn't).

$^*$There's probably a cute semantic way of doing this, but honestly it's probably easiest to just explicitly compute $Th_{L_n}(A_i)$ as a function of $n,i$. The point is that:

  • All atomic formulas are true under every variable assignment, and Booleans behave the same across all structures.

  • "$\exists^{\ge n}$" behaves like negation if $i<n$ and like affirmation (I guess we can call it that?) if $i\ge n$.

And those two facts inductively determine the whole $L_n$-theory of $A_i$.

Noah Schweber
  • 245,398