2

I need to find a formula, which is satisfiable in all interpretations of a domain with $k >2$ elements, but shouldn't be satisfiable in any domains with $k \le 2$ elements.

I've found something like this: $$ \forall x, \ \exists y, z : \left[ A(x,x) \cup A(y,y) \cup A(z,z) \right] \equiv \left[ \text{not}A(x,y) \cup \text{not}A(y,z) \cup \text{not}A(x,z) \right] $$

But there is still an error in this. Has anyone an idea of a correct formula?

Thanks a lot!

user110492
  • 31
  • 2
  • I have fixed the $\LaTeX$. Please let me know if I made a mistake. The $\cup$ represents $\text{AND}$. – Ahaan S. Rungta Nov 21 '13 at 17:04
  • Hint: the only quantifier you need is "exists", the only propositional operation you need is "and", and the only relation you need is $\neq$. You will need three variables. – goblin GONE Nov 21 '13 at 17:06

1 Answers1

1

Hint: In the predicate calculus with equality, we could say that there exist $x$, $y$, $z$ such that $x\ne y$ and $y\ne z$ and $x\ne z$.

In the predicate calculus with a binary predicate symbol $A$, our sentence could say that $A$ is an equivalence relation, and then copy the predicate calculus with equality version, with $A(s,t)$ replacing $s=t$.

André Nicolas
  • 507,029
  • It's also important, that the formula is satisfiable in ALL interpretations. As I understand it, that means that the predicate A can be any binary predicate (e.g. '=', 'not equal', '<' and so on) and the formula still has to be true for k > 2 and false otherwise. Or am I wrong? – user110492 Nov 22 '13 at 06:37
  • The sentence with equality is in fact true in all structures with more than $2$ elements, and false in all smaller structures. That is much stronger than satisfiability. The same is true of the binary predicate version, if (as in the answer) the sentence incorporates the axioms for equivalence relation. – André Nicolas Nov 22 '13 at 15:34