1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rob Arthan Oct 25 '18 at 21:46
  • $\begingroup$ 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! $\endgroup$ – Hiraphor Oct 25 '18 at 23:11
  • $\begingroup$ 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? $\endgroup$ – Rob Arthan Oct 26 '18 at 18:14
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Hiraphor Oct 25 '18 at 17:51
  • $\begingroup$ @Hiraphor yes, That’s why we need to state $\lnot(x=y)$ explicitly. $\endgroup$ – Henno Brandsma Oct 25 '18 at 17:53
  • $\begingroup$ Could I ask why the u is necessary in this formula? $\endgroup$ – Hiraphor Oct 25 '18 at 17:55
  • $\begingroup$ @Hiraphor only in the exactly 3 case, not in the at least 3 case. $\endgroup$ – Henno Brandsma Oct 25 '18 at 18:11
  • $\begingroup$ Thank you so much! This really cleared it up for me $\endgroup$ – Hiraphor Oct 25 '18 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.