0

I need some help with the following problem. I have to show that the set of formulas $\{\phi_1,\phi_2,\phi_3,\phi_4\}$ has no model, where

$$\begin{align*} \phi_1&=\forall x \forall y \forall z (Rxy \lor Ryz \lor Rxz)\;,\\ \phi_2&=\forall x \forall y \forall z ((Rxy \land Ryz) \rightarrow Rxz)\;,\\ \phi_3&=\forall x \forall y (Rxy \rightarrow Rf(x)f(y))\;,\text{ and}\\ \phi_4&=\forall x (\neg Rxf(f(x))\;, \end{align*}$$

where $R$ is some relation and $f$ is some function.

In particular I don't understand how I can get rid of $f$. I would be very grateful for any hint!

Thank You.

Brian M. Scott
  • 616,228
Logic_Problem_42
  • 1,425
  • I haven't solved it, but one idea is to let $y=f(x), z=f(y)=f(f(x))$ in the first two and see if you can run afoul of $\phi_4$ – Ross Millikan Jun 26 '16 at 20:11

1 Answers1

3

You can proceed as follows, it isn't particularly fast though:

From $\phi_1$ we know $$R(x,f(x)) \lor R(f(x),f(f(x))) \lor R(x,f(f(x)))$$ for each $x$. From $\phi_4$ we know the last disjunct is impossible, so we know $$R(x,f(x))\lor R(f(x),f(f(x))).$$ From $\phi_2$ if both of those are true then $R(x,f(f(x)))$, again contradicting $\phi_4$ so we know the disjunction is exclusive.

Supposing $R(x,f(x))$ applying $\phi_3$ we have $R(f(x),f(f(x)))$, contradicting the disjunction is exclusive. Therefore $R(f(x),f(f(x)))$.

But then we can run the same argument as above with $f(x),f(f(x)),$ and $f(f(f(x)))$ and conclude $R(f(f(x)),f(f(f(x))))$ and so, by $\phi_3$ $R(f(x),f(f(f(x))))$ contradicting $\phi_4$.

James
  • 5,443