I need to build a proof for the following sentences
$φ_1=∀_xp(x,x)$
$φ_2=∀_x∀_y(p(x,y) \rightarrow p(y, x))$
$φ_3=∀_x∀_y∀_z(p(x,y)\land p(y,z) \rightarrow p(x, z))$
which express the reflexivity, symmetry, and transitivity of the predicate p.
I need to show that none of these sentences is a logical consequence of the other two by choosing, for each pair of sentences, an interpretation that satisfies two sentences from them, but does not satisfy the third one.
Essentially I am requested to find three binary relations where each one satisfies just two of these properties.
I can find several proofs on the web why symmetry and transitivity do not imply reflexivity. However, I can not find those solutions for the other two cases as requested in this exercise:
- symmetry and reflexivity
- transitivity and reflexivity
So I am trying to build a proof for such exercise as follows:
Considering the domain D={a,b,c}
Symmetry and Reflexivity:
$m_1 (p)=\{(a,a),(b,b),(c,c),(a,b),(b,a),(b,c),(c,b)\}$
Symmetry and Transitivity :
$m_2 (p)=\{(a,b),(b,a),(b,c),(c,b),(a,c),(c,a)\}$
Transitivity ansd Reflexivity:
$m_3 (p)=\{(a,a),(b,b),(c,c),(a,b),(b,c)\}$
However, they clearly do not attend those rules $\forall$x, $\forall$y, and $\forall$z. How can I accomplish that?
$m_1$ and $m_2$ seem alright. $m_3$ is almost there $-$ if you get rid of $(b,c)$, then it becomes transitive and reflexive but not symmetric. It is easy to see that the presence of $(a,b)$ and the absence of $(b,a)$ breaks symmetry, while the inclusion of $(a,a),(b,b),(c,c)$ ensures reflexivity. Why is it transitive though? Recall what it means to be transitive: if we have both $(x,y)$ and $(y,z)$, then we must necessarily have $(x,z)$ as well. Let's see if that works here.
$x=a:$ we have $(a,a)$, so let $y=a$. What are all the possible $z$s, i.e. stuff that $y=a$ is related to? Since the only pairs starting with $a$ are $(a,a),(a,b)$, so only choices for $z$ are $a,b$. Let us check if $(x,z)$ holds for either $z$. We find that indeed, $(a,a)$ and $(a,b)$ hold, so all good.
But we also have $(a,b)$, so now let's let $y=b$. Then what could $z$ be? The only pair starting with $b$ is $(b,b)$, so the only possible value of $z$ is $b$. Let's see if $(x,z)=(a,b)$ holds... it does!
$x=b:$ we have $(b,b)$, so $y$ can only be $b$, but as discussed earlier, $z$ can only be $b$ too, so we only have to check if $(x,z)=(b,b)$ exists, which it indeed does.
Similarly for $x=c$.
It looks really long when I describe it like this, but once you get the hang of it you'll be able to 'spot it' right away.