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?

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

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: keep in mind that 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$.