# Countermodels in Predicate Calculus

Team,
I need to give a counter model for $\exists x \forall y ((Rxy \land \neg Ryx) \rightarrow (Rxx \leftrightarrow Ryy))$.

To do that, though, I'm trying to paraphrase this into a sentence in English. I'm having trouble. Can anyone help me with the paraphrase so that I can get thinking about the counter model?

• I presume you meant $\exists x\forall y$ or $\exists y\forall x$. Which is it? – Alex Kruckman Nov 1 '17 at 19:06
• I have made the relevant corrections. – Rusty Nov 1 '17 at 19:37

Ugh .. there is really no fluent reading of this in English that will actually help you further understand what this statement is claiming.

So, instead, just work with the formula and see how we can make it false.

So, how can we make $\exists x \forall y ((Rxy \land \neg Ryx) \rightarrow (Rxx \leftrightarrow Ryy))$ false? Well, that would be the same as making $\neg \exists x \forall y ((Rxy \land \neg Ryx) \rightarrow (Rxx \leftrightarrow Ryy))$ true, and bringing the negation inside, that statement is equivalent to:

$\forall x \exists y ((Rxy \land \neg Ryx) \land \neg (Rxx \leftrightarrow Ryy))$

OK, so we clearly need at least two different objects, otherwise we cannot have both $Rxy$ and $\neg Ryx$, so let's say we have $a$ and $b$, and so when we let $x=a$, we need $Rab$ and $\neg Rba$. OK, so now we also need $\neg (Raa \leftrightarrow Rbb))$, meaning we need exactly one of $Raa$ and $Rbb$, so let's say we have $Raa$ but not $Rbb$.

Are we there? No, because while the $\exists y ((Rxy \land \neg Ryx) \land \neg (Rxx \leftrightarrow Ryy))$ is true for $x=a$, it is not true for $x=b$, since we cannot pick $y=a$ for $x=a$.

OK, so we need a third object $c$, so that we have $Rbc$ and $\neg Rcb$, and since we need $\neg (Rbb \leftrightarrow Rcc)$ and we don't have $Rbb$, we do need $Rcc$. But that means that for $x=c$ we can neither pick $y=a$ nor $y=b$ to make the $\exists y ((Rxy \land \neg Ryx) \land \neg (Rxx \leftrightarrow Ryy))$ true, so we need a fourth object $d$!

OK, so we have $Rcd$ and $\neg Rdc$, and since we have $Rcc$ we need $\neg Rdd$. OK, can we make $\exists y ((Rxy \land \neg Ryx) \land \neg (Rxx \leftrightarrow Ryy))$ true for $x=d$ by picking $y=a$? Yes, as long as we make we make sure that $Rda$ and $\neg Rad$.

To sum up, then, the counterexample is one that has $4$ objects in the domain, call them $a$, $b$, $c$, $d$, and where we have $Raa$, $Rcc$, $Rab$, $Rbc$, $Rcd$, and $Rda$, and no other pairs in relation $R$

• Can I not have a counterexample with one a and b in the domain and s.t. Rab and Rbb? In other words, I don't quite get a why that counter model does not suffice. – Rusty Nov 1 '17 at 20:24
• I've done the truth truth for what the negated statement that the claim is equivalent to, and I have an open branch where Raa, $\neg Rba$ and Rab. So, why can that not just be a diagram of my counter model, a model with two things in the domain and <a,b> and <a,a>? – Rusty Nov 1 '17 at 20:36
• @Rusty Wait, you know truth trees?!? Anyway, it does not work with that interpretation, for the original claim $\exists x \forall y ((Rxy \land \neg Ryx) \rightarrow (Rxx \leftrightarrow Ryy))$ would be true: just pick $x = b$. Why? because for any $y$ that you pick (whether $a$ or $b$), the conditional is true. Why? Because in both cases the antecedent is false – Bram28 Nov 1 '17 at 20:39
• But if the negation of the original formula has an open branch, the negation is true. and that's what i want to show, yeah? – Rusty Nov 1 '17 at 20:49
• @Rusry Yes, you have the right idea (you're working with a truth tree, right?) But a branch is only open and finished when it all universals it conatins has been instantiated with all constants. I am certain that in your branch you have a universal that is not instantiated with the $b$, and oince you do that, you'll see you need a $c$! – Bram28 Nov 1 '17 at 20:59

Suppose "Rxy" translates "x loves y". Then the sentence could be translated back into awkward English as: "Someone is such that if they love but are unloved by everybody, then they love themselves if and only if everyone loves themselves". The English translation doesn't really help to show this, but it's a tautology, so there is no countermodel.