# $\vDash (\forall x \forall y \forall z (R(x,y) \land R(y,z)\rightarrow R(x,z)))\land (\forall x \exists y R(x,y)) \rightarrow \exists x R(x,x)$

Prove that the following formula is true in every structure or construct a structure as a counterexample where the formula is not true:

$$(\forall x \forall y \forall z (R(x,y) \land R(y,z)\rightarrow R(x,z)))\land (\forall x \exists y R(x,y)) \rightarrow \exists x R(x,x)$$

I have tried to show that for an arbitrary structure that this formula is true for every truth assignment. This got a mess very quickly and I'm not sure if it is correct what I did. My opinion so far is hat this formula is true in every structure because I didn't manage to construct a counterexample.

Does anyone has a hint or an advise to approach exercises of this kind?

• Do you intuitively see what the antecedents say about the relation $R$? What are some examples that satisfy the antecedent? – Mees de Vries Nov 2 '18 at 15:26

First, some intuitions. The hypothesis $$\forall x \forall y \forall z (R(x,y) \land R(y,z) \to R(x,z))$$ means that $$R$$ represents a binary relation that is transitive. A typical example of a transitive relation is the strict order relation $$<$$.
The hypothesis $$\forall x \exists y R(x,y)$$ means that such a transitive relation $$R$$ is "unbounded upwards". If you keep in mind the intuition of $$<$$, this condition is satisfied by the strict order relation $$<$$ over an infinite totally ordered set without greatest element, for instance $$\mathbb{N}$$.
But the strict order relation $$<$$ is not reflexive, i.e. it does not satisfies the thesis $$\exists x R(x,x)$$. This should convince you that the formula $$\big( \forall x \forall y \forall z (R(x,y) \land R(y,z) \to R(x,z)) \land \forall x \exists y R(x,y) \big) \to \exists x R(x,x)$$ is not valid, i.e. there is a structure that does not satisfy this formula.
Formally, let $$\mathcal{N} = (\mathbb{N}, <)$$ where the set $$\mathbb{N}$$ of natural numbers is the domain of $$\mathcal{N}$$ and the usual strict order relation over $$\mathbb{N}$$ is the interpretation in $$\mathcal{N}$$ of the binary symbol $$R$$. As we have seen above, $$\mathcal{N} \not \vDash \big(\forall x \forall y \forall z (R(x,y) \land R(y,z) \to R(x,z)) \land \forall x \exists y R(x,y) \big) \to \exists x R(x,x)$$.
• Another way to phrase $\forall x \exists y.Rxy$ is "there are no sinks". – DanielV Nov 2 '18 at 17:32