MHB Graph that models one but not both

  • Thread starter Thread starter Andrei1
  • Start date Start date
  • Tags Tags
    Graph Models
AI Thread Summary
The discussion focuses on demonstrating 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 identifying a graph that models one but not both. The empty graph is suggested as a possible solution, but it is noted that the definition of a structure requires a nonempty underlying set, making the empty graph invalid. Additionally, it is clarified that while one sentence may imply the other, this implication does not hold for specific structures. The key takeaway is that both formulas are false in every graph due to the irreflexive nature of the graph relation. Understanding these nuances is crucial for accurately modeling logical sentences in graph theory.
Andrei1
Messages
36
Reaction score
0
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.
 
Physics news on Phys.org
Andrei said:
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).
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Replies
2
Views
6K
Replies
6
Views
2K
Replies
18
Views
2K
Replies
2
Views
2K
Replies
2
Views
1K
Replies
4
Views
2K
Replies
3
Views
2K
Back
Top