# First-order logic validity question

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!

• Where did you come across this question? There is a quantifier-elimination process for (an extension of) the pure predicate calculus with equality that leads to an answer. – Rob Arthan Oct 25 '18 at 21:46
• It was set as an assignment for beginner computer science students. The question is only worth a single point and it's multiple choice but I'd like to understand it anyway! – Hiraphor Oct 25 '18 at 23:11
• I believe you are right that the answer is $n$ (Henno's answer is addressing a slightly different question). However, the only techniques I can think of for proving this are outside the scope of a beginning CS course. Have you asked your teachers for help? – Rob Arthan Oct 26 '18 at 18:14

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.

• This may just be my awfulness at logic but does each variable x, y, z refer to a different element? Is it possible for them each to refer to the same thing? Why exactly does this formula become invalid when we decrease the number of elements? – Hiraphor Oct 25 '18 at 17:51
• @Hiraphor yes, That’s why we need to state $\lnot(x=y)$ explicitly. – Henno Brandsma Oct 25 '18 at 17:53
• Could I ask why the u is necessary in this formula? – Hiraphor Oct 25 '18 at 17:55
• @Hiraphor only in the exactly 3 case, not in the at least 3 case. – Henno Brandsma Oct 25 '18 at 18:11
• Thank you so much! This really cleared it up for me – Hiraphor Oct 25 '18 at 21:42