# Does $\forall x((\forall zR(x,z) \rightarrow \exists yR(y,x)))$ holds in any non-empty model?

I am trying to prove or disprove that the formula $$\forall x((\forall zR(x,z) \rightarrow \exists yR(y,x)))$$ is true in any non-empty model with a predicate R? (the formula is vacuously true when the model is empty set).
I tried using logical equivalences to simplify the formula:
$$\forall x((\forall zR(x,z) \rightarrow \exists yR(y,x))) \equiv \forall x((\exists z\space \neg R(x,z) \vee \exists yR(y,x)) \equiv \forall x\exists z\exists y((\neg R(x,z) \vee R(y,x))$$
Then my intuition said that if our model is not empty for all x, we can choose $$y=x$$ and $$z=x$$; therefore, the statement holds for any non-empty model, however, I've never encountered such a case before so I don't know if my reasoning is correct here, I'll appreciate any insights, thanks !

• Your parentheses are not balanced (they're wrong in every formula) - maybe the first ( should be deleted? Commented Jul 9, 2023 at 12:08
• Yes indeed, the parentheses were not balanced Commented Jul 9, 2023 at 18:23
• You did that correctly. And by the way, any universal is vacuously true in an empty domain, so the statement is true in any domain, empty or not. Commented Jul 9, 2023 at 23:21

As noted in the comment, there is a syntax error (unbalanced parentheses) in the starting formula.

(1) If the syntax error is resolved as $$\forall x(\forall z(R(x,z)\rightarrow\exists yR(y,x)))$$

for any $$\alpha$$ and $$\beta$$ in the domain,

$$\neg R(\alpha,\beta)\vee\exists yR(y,\alpha)$$

must be satisfied. The first disjunct tells that no member of the domain is related to another by $$R$$ (i.e., $$R$$ is an empty relation) and the second disjunct tells that at least a $$y$$ exists that is related to any member of the domain.

In case that $$R$$ is not an empty relation, there must be a member related to any other in the domain, which is not satisfiable in general.

(2) Else, if the syntax error is resolved as the OP carries on $$\forall x(\forall zR(x,z)\rightarrow\exists yR(y,x))$$

we have $$\forall x\exists z\exists y(\neg R(x,z) \vee R(y,x))$$

Therefore, for any $$\alpha$$ in the domain

$$\exists z\exists y(\neg R(\alpha,z) \vee R(y,\alpha))$$

must be satisfied. Hence, there must be at least a $$\beta$$ that $$\alpha$$ is not related to or a $$\gamma$$ that is related to $$\alpha$$.

To simplify analysis, assign $$R$$ to an irreflexive relation, such as <, (reflexive relation is easier) and assign numerical values to the rest of the formula, we see that there must exist $$y$$ or $$z$$ such that for any $$\alpha$$ in the domain

$$\alpha\nless z \vee y < \alpha$$

Clearly, the formula is satisfied in general.

For more complex formulas, I recommend semantic tree method.