Consider the set $\phi$ consisting of the following formulas.

$$ \exists x \exists y \exists z \neg (x = y ~ \lor x = z ~ \lor y = z) $$ $$ \forall x \exists y ~ gimble(x, y) ~ \land \exists x ~ \neg gimble(x, x) $$ $$ \forall x \forall y \forall z ~ (gimble(x, z) ~ \land ~gimble(y, z) \implies x =y) $$

1) How can I describe a model for $\phi?$

Should I use a table? How would I do that?

2) How can I describe an interpretation that is not a model for $\phi?$

3) Is the set $\phi$: (i) valid, (ii) satisfiable but not valid or (iii) unsatisfiable?

I think that $\phi$ is probably satisfiable but not valid (ii) because it holds under some interpretation e.g. the interpretation for 1) but it is not valid because it does not holds under every interpretation i.e the interpretation for 2)


For a model:

The first sentence says that there are at least three different objects

The second sentence says that everything stands in a 'gimble' relation to something, and there is something not in a 'gimble' relation to itself

the third sentence says that you cannot have two different objects that stand in a 'gimble' relation to the same object.

1) OK, so here is a possible model: take exactly three objects, $a,b$ and $c$, and with the following 'gimble' pairs: $(a,b),(b,c),(c,a)$

If you want something more meaningful: We have 3 persons: Alice, Bob, and Carroll. $gimble(x,y)$ means '$x$ likes $y$. Say that Alice likes Bob, Bob likes Carroll, and Carroll likes Alice, and otherwise there are no more like relations. Note how we indeed have at least three different objects, how everyone likes someone, how there is someone who does not like themselves, and how there are not two different people liking the same person.

2) An interpretation that is not a model: say there is only 1 object $a$ and say that $a$ dos not stand in the 'gimble' relation to itself.

More meaningful: We just have Alice, and Alice does not like herself.

3) Yes, you are right: it is satisfiable (because there is a model) but not valid (because not every interpretation is a model)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.