3
$\begingroup$

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?

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

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

$\endgroup$
  • 1
    $\begingroup$ Another way to phrase $\forall x \exists y.Rxy$ is "there are no sinks". $\endgroup$ – DanielV Nov 2 '18 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.