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?
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)$.