How to find a formula that is true for a given model in the First Order Logic?

Question

I think I might have got lost in definitions. I am not sure if this is the right way to deal with models and formulas in the First Order Logic.

I am not looking for the solution for this particular problem. I'm much more interested in the way I should approach this kind of problems in general.

---

Here's what I'm trying to solve:

Let $\mathcal{A}=<A, P^\mathcal{A}, Q^\mathcal{A}>$ be our model. $P$ and $Q$ both take two arguments.

Find a formula $\alpha$ such that $$ \mathcal{A} \models \alpha \iff > P^\mathcal{A} \cup Q^\mathcal{A} \subseteq P^\mathcal{A}\ \circ > Q^\mathcal{A} $$ where $\circ$ is a composition.

---

Here is what I did:

1. I've found a suitable $\alpha$. I think I had a good intuition to try $\alpha = \big( \forall_{x, y \in A} P(x, y) \wedge Q(x, y)\big)$.
2. Now I have to prove that both implications are correct.
3. $(\implies)$
   $$ \mathcal{A} \models \alpha \implies \forall_{x, y \in A} \big( <x,y> \in P^\mathcal{A} \cup Q^\mathcal{A} \implies <x, y> \in P^\mathcal{A}\ \circ Q^\mathcal{A} \big) $$ We now can see that $P$ and $Q$ are both total relations. Hence $P^\mathcal{A} \cup Q^\mathcal{A} = P^\mathcal{A}$ and $P^\mathcal{A}\ \circ Q^\mathcal{A} = P^\mathcal{A}$ so the implication is true.

4. $(\impliedby)$ $$ \mathcal{A} \models \alpha \impliedby \forall_{x, y \in A} \big( <x,y> \in P^\mathcal{A} \cup Q^\mathcal{A} \implies <x, y> \in P^\mathcal{A}\ \circ Q^\mathcal{A} \big) $$ So let's examine the sets we've got: $$ P^\mathcal{A} \cup Q^\mathcal{A} = \{ <x, y> \in A \times A \ | <x, y> \in P^\mathcal{A} \vee <x, y> \in Q^\mathcal{A} \} $$ $$ P^\mathcal{A} \circ Q^\mathcal{A} = \{ <x, y> \in A \times A \ | <x, y> \in P^\mathcal{A} \wedge <x, y> \in Q^\mathcal{A} \} $$ So as we can see, if there is a relation of $x \in A$ and $y \in A$ then $<x,y> \in P^\mathcal{A} \wedge Q^\mathcal{A}$.

5. $\square$

Answer 1

Your $\alpha$ has several problems. First starters, $A$ is not in the language, so you can’t write $\forall x,y\in A$. Moreover, it says that every $x$ and $y$ satisfy $P(x,y)$, which is not at all what you want.

Let’s first write out in detail what it means for an ordered pair $\langle a,b\rangle\in A\times A$ to belong to $P^{\mathscr{A}}\circ Q^{\mathscr{A}}$: it means that there is a $c\in A$ such that $\langle a,c\rangle\in Q^{\mathscr{A}}$ and $\langle c,b\rangle\in P^{\mathscr{A}}$. Thus, the condition on $\mathscr{A}$ that we want to express is that

for any $a,b\in A$, if $\langle a,b\rangle\in P^{\mathscr{A}}$ or $\langle a,b\rangle\in Q^{\mathscr{A}}$, then there is a $c\in A$ such that $\langle a,c\rangle\in Q^{\mathscr{A}}$ and $\langle c,b\rangle\in P^{\mathscr{A}}$.

The formula $\alpha$ should express this in terms of $P$ and $Q$, without any reference to $A$. For instance, a universal quantification $\forall x$ will automatically be interpreted as $\forall x\in A$ when $\alpha$ is interpreted in the model $\mathscr{A}$.

HINT: Take it in short steps; I’ll get you started. Clearly $\alpha$ is going to start with a pair of universal quantifiers, $\forall x\forall y$. (Imagine these as corresponding to $a$ and $b$, respectively, in the highlighted statement about what happens in $\mathscr{A}$, so that this corresponds to ‘for any $a,b\in A$’.)

Inside the quantifiers we have an if-then statement. In $\mathscr{A}$ the if part is

$\langle a,b\rangle\in P^{\mathscr{A}}$ or $\langle a,b\rangle\in Q^{\mathscr{A}}$.

If we remove all reference to the model and replace $a$ and $b$ by $x$ and $y$, respectively, we get

$P(x,y)\lor Q(x,y)$.

Thus, $\alpha$ should look like

$$\forall x\forall y\Big(\big(P(x,y)\lor Q(x,y)\big)\to\beta\Big)\;,$$

where $\beta$ is some formula whose interpretation in $\mathscr{A}$ is

there is a $c\in A$ such that $\langle a,c\rangle\in Q^{\mathscr{A}}$ and $\langle c,b\rangle\in P^{\mathscr{A}}$.

Can you work out now what $\beta$ should be?