Impossibility of expressing "there are at least n+1 objects" without using existential quantifiers Let $n$ be a positive integer. I define the first-order signature $L_n$ to consist of $n$ constants $c_1,...,c_n$ and no relation or function symbols besides equality. In $L_n$, for any integer $m$ between $1$ and $n$ inclusive, it is possible to express "there are at least $m$ objects in the universe" using a $\forall$-sentence, in fact a quantifier-free sentence. I conjecture that for any integer $k$ greater than $n$, it is impossible to express "there are at least $k$ objects in the universe" using a quantifier-free or even a $\forall$-sentence, but rather requires an $\exists$-sentence. Is this conjecture true?
 A: It's a standard exercise that $\forall^*$-sentences - that is, sentences of the form $\forall x_1,...,x_n\theta$ with $\theta$ quantifier-free - are preserved under taking substructures: if $\varphi$ is $\forall^*$ and $\mathfrak{A}$ is a substructure of $\mathfrak{B}\models\varphi$, then $\mathfrak{A}\models\varphi$.
This gives an immediate positive answer to your question since every $L_n$-structure has a substructure of size at most $n$.
EDIT: Per your comment, you're actually asking about a weaker property:

Is there a $\forall$-sentence which is satisfiable and all of whose models have size $>k$?

("$\varphi$ expresses [stuff]" is standardly understood as "The models of $\varphi$ are exactly the structures satisfying [stuff].") The argument above still applies: as soon as we have $k>n$, every "big enough" structure has a "too small" substructure, and so no satisfiable $\forall$-sentence can avoid having "too small" models.

Two quick comments:

*

*Incidentally, the converse of the result above (phrased appropriately!) is also true, but definitely harder. If memory serves, Hodges'  model theory book(s) has a good discussion of this and related preservation-characterization theorems. But that's not needed here.


*Your claim that "There are at least $k$ objects" is $L_n$-expressible with a quantifier-free sentence for $k\le n$ is not true, at least not according to the standard meaning of "express" (see above): we can have a structure with lots of elements where all the $c_i$s are equal! What you can do is write, in $L_n$, a quantifier-free sentence whose spectrum (= set of cardinalities of finite models) consists of all numbers $\ge k$ for each fixed $k\le n$. The argument of my answer also shows that even this weaker result is not achievable with a $\forall^*$-sentence if $k>n$, though, so there is a real distinction between $\le n$ and $>n$.
