Would a proposition of first-order logic, with N quantifiers, always held the same logical status (of consistency or validity) no matter if the domain has N members, or N + x members? [x being n finite number]
I intuitively think the answer is YES, but what about any kind of proof?!
In pure predicate calculus (i.e., first-order logic with equality with the empty signature), every formula has a finite or cofinite spectrum, and indeed, one needs more than $n$ quantifiers (in fact, quantifier rank more than $n$) to distinguish the model with $n$ elements from any larger model. The easy way to see this is using Ehrenfeucht–Fraïssé games: in the game played on two sets $A,B$ with no additional structure, the Duplicator has an obvious strategy that allows him to survive for $\min(|A|,|B|)$ rounds. One also needs more than $n$ distinct variables: the same strategy allows Duplicator to win in the infinite-round pebble game with $\min(|A|,|B|)$ pebbles.
On the other hand, as Andres mentioned in the comments, this result is false in richer signatures. For example, the one-quantifier formula $\forall x\,(f(f(x))=x\land f(x)\ne x)$ has a model of size $n$ if and only if $n$ is even.
