Finding out whether a predicate logic formula is true or false.

Question

I'm given the formula: ∃x∃y∃z(P(x, y) ∧ P(z, y) ∧ P(x, z) ∧ ¬P(z, x)).

The universe is all natural numbers. R is the relation corresponding to P. R = {<x, x+1> : x >= 0}

When putting values into the formula I've thought that if x = x then y = x + 1. By using this logic z is equal to x for P(z, y), but z has to be equal to y for P(x, z). I can't think of any other way to do this.

How do I show whether the formula is true or false? Could anyone point me in the right direction?

Answer 1

When putting values into the formula I've thought that if x = x then y = x + 1. By using this logic z is equal to x for P(z, y), but z has to be equal to y for P(x, z). I can't think of any other way to do this.

Indeed.   That is the way to do this.

Let's tidy up your work a bit.

---

You have $P:=\{\langle x, x+1\rangle: x\in\Bbb N^+\}$ Which means $P(x,y)$ is substitutable with $y=x+1$.   Okay, so we shall do that.

$$\exists x~\exists y~\exists z~(P(x, y) \land P(z, y) \land P(x, z) \land\lnot P(z, x))\\\equiv\\\exists x~\exists y~\exists z~(y=x+1 \land y=z+1 \land z=x+1 \land x\neq z+1)$$

Now, assuming this was true, we could find naturals $x,y,z$ where:

• $y=x+1$ and $z=x+1$, so $y=z$
• Also $y=z+1$, so $\underline{y=y+1}$

So...