0
$\begingroup$

So I just realised that in all the work I have seen (which is literally a drop of the ocean) on First Order Logic, I never really saw anything on expressiveness of FOL with arbitrary number of variables and unary predicates. Intuitively it seems to me that unary predicates are only as expressive as propositions, but is it true ? are there formulas in First Order Logic with unary predicate and finite number of variables which cannot be expressed in First Order Logic with two variables ? (I am strictly talking of a language which is function free and has only unary predicates and finite set of variables)

$\endgroup$
1
2
$\begingroup$

Does the identity predicate count as part of the logic? In which case "there are exactly two $F$s" can be expressed using three variables but not two.

$\endgroup$
1
  • $\begingroup$ Oops thanks for the answer, I read your answer in a hurry (on a phone) earlier. I think yes identity predicate counts, but it would be nice to have more complex examples in a an equality free language $\endgroup$
    – SagarM
    Jul 22 '20 at 17:17

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.