I need to find a model for the following formula:

$$(\forall x \forall y \forall z.R(x,y) \wedge R(y,z) \Rightarrow R(x,z)) \wedge (\forall x\forall y.\neg R(x,y) \Leftrightarrow R(y,x))$$

So I need a underlying set and a definition of $R$. The left hand side is transitivity and it is easy to find relations satisfying that. However, I can not seem to find a formula satisfying the right hand side. The "$<$"-relation doesn't work since its negation is "$\geq$" and that is basically the problem with every example I come up with. Is there even some structure satisfying that formula?


The second part of formula is inconsistent. Instantiating $x$ and $y$ to the same element $a$ gives us $\neg R(a,a) \Leftrightarrow R(a,a)$, which is absurd.

If your logical framework allows empty models (which most don't), that would work, though.

  • $\begingroup$ I was thinking the same thing, however I assumed it had to work since its part of my homework asking for a (non-trivial, which is what excludes an empty model) model. Thank you. $\endgroup$ – Staki42 Jul 10 '16 at 16:15

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.