Provide a model for which the following is true $\forall x\forall y\forall z((S(x,y)\land S(y,z)) \implies S(x,z))$.

126 Views Asked by At

My question relates to the idea of satisfiability. If one can provide a model for which the following formula is true does it mean it is satisfiable?

$$\forall x\forall y\forall z\,((S(x,y) \land S(y,z))\implies S(x,z)). $$

Is the above formula satisfiable if I have the following model:

$A = \{a,b,c\}$

$S = \{(a,b),(b,c),(a,c)\}$?

If it is satisfiable, what would be required to make this formula valid in this model?

If it is not satisfiable what would be an appropriate model to make it satisfiable?

2

There are 2 best solutions below

6
On BEST ANSWER

There are several terminological issues in your question, so (at the risk of appearing too pedantic) let me try to address those.

Given a sentence $\varphi$ and a structure $M$, we can talk about the sentence being true or false in $M$. To talk about true or false, we need both a sentence and a structure.

So the phrases "$\varphi$ is true" and "$\varphi$ is false" make no sense unless we implicitly have a structure $M$ around that we're interested in.

On the other hand, a sentence $\varphi$ is satisfiable if it is true in some structure. And $\varphi$ is valid if it is true in every structure. To talk about satisfiable or valid, we only need a sentence, we don't need a structure.

So the phrases "$\varphi$ is satisfiable in $M$" and "$\varphi$ is valid in $M$" make no sense. On its own, $\varphi$ is either satisfiable or not and either valid or not.

Now to answer your questions one by one, with the above in mind:

If one can provide a model for which the following formula is true does it mean it is satisfiable?

Yes, this is the definition of satisfiable. To prove that $\varphi$ is satisfiable, you can exhibit a structure $M$ in which $\varphi$ is true.

Is the above formula satisfiable if I have the following model? \begin{align*} A &= \{a,b,c\}\\ S&= \{(a,b), (b,c), (a,c)\}\end{align*}

Yes, exhibiting the structure $M = (A,S)$ proves that $\varphi$ is satisfiable, since $\varphi$ is true in $M$.

If it is satisfiable, what would be required to make this formula valid in this model?

This question is not well-formed ("valid in this model" makes no sense). In fact, the sentence is not valid, and you can prove this by exhibiting a structure in which the sentence is false. For example: \begin{align*} A &= \{a,b,c\}\\ S&= \{(a,b), (b,c)\}\end{align*}

If it is not satisfiable what would be an appropriate model to make it satisfiable?

A model doesn't make a sentence satisfiable. It's either satisfiable or it's not. You can prove that a sentence is satisfiable by exhibiting a model, like you did above.

0
On

Yes, it suffices to find a model that satisfies the formula.

Consider $A=\{a\}, S=\{(a,a)\}$.