Welcome to our community

Be a part of something great, join today!

graph that models one but not both

Andrei

Member
Jan 18, 2013
36
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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).