$F = \forall x R(x,x)$

$G = \forall x \forall y \forall z (R(x,y) \land R(y,z) \rightarrow R(x,z))$

a) Find a model for $G$, that isn't a model for $F$.

b) Does a domain $D$ exist, so that $val_{D,I,\beta}(F) = true$ for every Interpretation $(D',I)$ with $D = D'$.

c)Does a domain $D$ exist, so that $val_{D,I,\beta}(G) = true$ for every Interpretation $(D',I)$ with $D = D'$.

d)Is $F$ valid? Is $G$ valid? Explain your answer.

I'm doing exercises from a textbook, but there aren't any answers.

a)$D = \mathbb{N}$

$I(R) = \{(x,y) \in D \times D | x < y\}$

The relation is transitive, but can't be reflexive.

I don't understand what is meant in b) and c).

d)For $F$ or $G$ to be valid, they would have to be true for every Interpretation $I$. Like in a) we found an interpretation for which $F$ isn't valid.

Wouldn't this then answer b), that such a domain doesn't exist for every Interpretation $I$.

Is there a simple example for a non transitive relation?

  • $\begingroup$ Most relations aren't transitive. Just try and build a nontransitive relation on a three-element set. $\endgroup$ – Patrick Stevens Dec 17 '19 at 7:30

For b) and c), you need to find a set $D$ such that, however you interpret the relation symbol $R$, $F$ (resp. $G$) will hold. Hint : consider $D := \emptyset$.

For d), Just take $D = \{0,1,2\}$ and interpret $R$ as follow : $\{(0,1),(1,2)\}$.

  • 1
    $\begingroup$ @franz3 Then the answer for b) is no because you can always interpret $R$ to be the empty relation. For c), the answer is yes : take $D $ to be any singleton. $\endgroup$ – Olivier Roche Dec 17 '19 at 8:44

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.