Graph that models one but not both

[Andrei1]

Here is an exercise from Shawn Hedman's course of logic, like all others I have posted.

Show that the sentences $\forall x \exists y\forall z(R(x,y)\wedge R(x,z)\wedge R(y,z))$ and $\exists x\forall y\exists z(R(x,y)\wedge R(x,z)\wedge R(y,z))$ are not equivalent by exhibiting a graph that models one but not both of these sentences.

I would say that only the empty graph is the correct solution, because if a structure is not empty then I can derive $\exists xR(x,x)$ from each of the given sentences.

 

[Evgeny.Makarov]

I would say that only the empty graph is the correct solution, because if a structure is not empty then I can derive $\exists xR(x,x)$ from each of the given sentences.

You are basically right, but here is a couple of remarks. Definition 2.13 (in the 2006 edition) requires that the underlying set of a structure is nonempty, so the empty graph is not a structure. Second, it is wrong to say about two sentences A and B that A derives B if some structure has some property. We can say that B is a consequence of A, but this is irrespective of any particular structure (it means that M models B if M models A for all models M). What is the case here is that $\exists x\,R(x,x)$ is the consequence of either of the two given formulas, so these formulas are false in every graph (because the graph relation is supposed to be irreflexive: p. 66).