Finding structures that are models

53 Views Asked by At

We got 3 formulae expressing that the predicate is reflexive, symmetrical but not transitive

$$F_1=\forall x P(x,x) \\F_2 = \forall x \forall y (P(x,y)\to P(y,x)) \\F_3=\forall x\forall y\forall z (P(x,y)\land P(y,z))\to P(x,z))$$

I wanted to start finding an interpretation which is a model for $F_1, F_2$ and not $F_3$

For $F_3$ to not be satisfied I would need to find a way to make $P(x,z)$ unsatisfiable, but I can't seem to find anything that would keep $P(x,x), P(x,y), P(y,x)$ and $P(y,z)$ satisfiable...

My biggest problem is dealing with the universal quantifiers.

Any hint or help is appreciated!

1

There are 1 best solutions below

0
On

Let $\mathcal{A} = (U_\mathcal{A}, I_\mathcal{A})$ be the structure whose domain is $U_\mathcal{A} = \{1,2,3\}$ and whose interpretation of the predicate symbol $P$ is $I_\mathcal{A}(P) = \{(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)\}$. Then you can easily check that $\mathcal{A} \models F_1$ (i.e. the interpretation of $P$ in $\mathcal{A}$ satisfies reflexivity) and $\mathcal{A} \models F_2$ (i.e. the interpretation of $P$ in $\mathcal{A}$ satisfies symmetry) but $\mathcal{A} \models \lnot F_3$ (i.e. the interpretation of $P$ in $\mathcal{A}$ does not satisfy transitivity, since $(1,2) $ and $(2,3)$ are in $I_\mathcal{A}(P)$ but $(1,3)$ is not).