The question comes from the book Logic in Computer Science (page 63) written by Michael Huth a.e..

Let $\varphi$ be the sentence $\forall x \forall y \exists z (R(x, y) \rightarrow R(y, z))$, where $R$ is a predicate symbol of two arguments.

$(a)$ Let $A$ be defined as $A = \{a, b, c, d\}$ and $R^M$ be defined as $R^M = \{(b, c),(b, b),(b, a)\}$. Do we have $M \vDash \varphi$?

$(b)$ Let $A' = \{a, b, c\}$ and $R^{M'} = \{(b, c),(a, b),(c, b)\}$. Do we have $M' \vDash \varphi$?

Justify your answer, whatever it is.

My Answer: I received a tip that whenever encountering an implication, I should always check if the condition $p$ in $p \rightarrow q$ is false because then I can assert that it is true. So, in case (a), it states that for all $x$ and for all $y$, $R$ should hold. However, given $x=a$, it doesn't hold since there's no $y$ for $a$. Therefore, I concluded that the model holds here. But I was wrong, and I don't understand what the answer sheet is telling me at all. Can someone please explain?


1 Answer 1


In the case of $M$:

Let $x=b,y=a$. We know that $R(x,y)$ is true. However $R(y,x)$ is false (because $R(y,x)$ could be true only for $y=b$ which is false), which means $M\not\models \phi$. $\square$

In case of your method, I think you could misunderstood how to prove implications. $p \to q$ is false only when $p$ is true, but $q$ is false. When $p$ is false then implication is true for whatever $q$ is. And using this analogy, you assumed you just considere case when $p$ is false, but in this case implication is true (because when $x=a$ then $\neg R(x,y)$)! Furthermore I don't understand how did you concluded that $M \models \phi$.

In case of $M'$:

Suppose $R(x,y)$ for some $x,y \in M'$. We have 3 scenarios, either $y$ is equal to $a$ or $b$ or $c$. When $y=a$, then indeed there's $z$ such that $R(a,z)$ (namely $z=b$). Simmilarily argument works for $y=b$ and $y=c$ which ends the proof (that $M'\models \phi$) $\square$.

  • $\begingroup$ Because R(x,y) is not true for all x's thus it isn't true (period). It is my understanding that there is no cases in this case because we are asked "for all" and if it is not true for all then it is False. That is what I assumed. Also even if we got R(y,z), this will also be false because we don't have a z for all y's. Given that the set is {a,b,c,d} there exists only one "b" that holds true. False -> False = False. I know that I am wrong but still don't get it tho. $\endgroup$ Apr 3 at 8:04
  • $\begingroup$ @Need_MathHelp $R(x,y)$ is not true for any $x,y$ so it's not true that $\forall x,y R(x,y)$. But sentence $\phi$ doesn't asks about that. Formula asks you about exactly this: "Take any $x,y$. Is it true, that there is $z$, such that (assuming $R(x,y)$ is true) $R(y,z)$ is true"? In case of $F\to F$ to be $F$. Well think about implication $p\to q$ as thing that only care about wheter $q$ is true whenever $p$ is true. It doesn't cares about what happens when $p$ is false. "If it's raining I'll go sit in home". If it's not raining then I can sit or not sit in home it doesn't matter $\endgroup$
    – Antares
    Apr 3 at 13:04
  • $\begingroup$ All that matters in this example is what do I do when condition "it is raining" holds. If I won't sit in home when it's raining (i.e when $p$ is true) then the implication would be false (because we have $p$ but $q$ is false). In mathematics we genneraly assign value "true" to $false \to false$. With such an assignment you can also notice that $p \to q$ is equivalent with $\neg p\vee q$ $\endgroup$
    – Antares
    Apr 3 at 13:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .