Define a proposition and indicate structures

59 Views Asked by At

If $A$ is a set and $M,N \subseteq A×A$ are two binary relations, the composition relation $M∘N \in A×A$ is such that for all $a,b \in A$, $(a,b) \in M∘N$ if there exists $a' \in A$ such that $(a,a') \in M$ and $(a',b) \in N$. Let $L$ be a first order language with equality and $R2 = \{R,Q,P\}$.

a) Define a proposition $\psi$ of $L$ such that a structure $A = (A,.^A)$ is a model of $\psi$ if and only if the relation $P^A$ is a composition of $Q^A$ and of $R^A$ (this means $Q^A∘R^A$).

b) Indicate two structures of $L, A1$ and $A2$, such that $A1 ⊨ \psi$ and $A2 ⊭ \psi$.

1

There are 1 best solutions below

0
On BEST ANSWER

Here's a hint. The problem asks you to write a sentence (a first-order formula with no free variables) in the language $L$ that states that $P$ is $Q \circ R$. You need to translate the definition given in "natural" language in the first paragraph of the exercise.

Then you need to show two structures: one a model of $\psi$ and the other not a model. For that, you can draw graphs with three types of edges: one type for each relation. Two vertices $v_a$ and $v_b$ are connected by a $P$-edge whenever there exists a vertex $v_c$ such that a $Q$-edge connects $v_a$ to $v_c$ and an $R$-edge connects $v_c$ to $v_b$.

It shouldn't take you long to come up with a graph where this holds and another graph where it doesn't.