I'm a beginner learning first-order logic and I have a couple of difficulties understanding the following question:
"Let L be a first order language with just one predicate, =, and no constants or function symbols. Let A be a sentence that is valid in a structure M if and only if M has at least n elements in its domain. What is the smallest number of variables required to write such a sentence A?"
How should the whole problem be written or structured? Based on my intuition I think the solution is n, because it makes sense that if I were to assign each element to a single variable, decreasing the number of elements (but keeping the variable referring to essentially nothing) would invalidate the sentence. I only have binary marks and no explanations/mark schemes so I'd like to understand how to approach this question since I'm only working on a theory!
For $n=3$ I would for example use the formula:
$$\exists x: \exists y: \exists z: \lnot(x=y) \land \lnot(x=z) \land \lnot(y=z) \land \left(\forall u: (u=x) \lor (u=y) \lor (u=z)\right)$$
which uses $4$ variables. So $n+1$ suffices for a model of exact size $n$. I cannot show that fewer cannot suffice, though. Maybe others have ideas for that.
added for at least $n$, only the first part is needed. And then I need $n$ variables plus a lot of not equal clauses. I don't see how we could do it with fewer but again, no proof for that.