Is ∀x∀y∀z[φ(x,y)∧p(y,z)->p(x,z)] equivalent to ∀x∀y∀z[φ(x,y)∧p(x,z)->p(y,z)] ?

The only thing I can think of is that this question can be answered if we show that p->q is equals (↔) το q->p, but that's not true because p->q ↔ ¬p->¬q, hence p->q is not equals to q->p. However, I do not know if my logic is correct and if it can be accepted as an answer.

I also think that the (first) ∀x∀y∀z[φ(x,y)∧ part is irrelevant and that i have to focus only to the last part.


It does hold that $$ \forall x \forall y \forall z \, [p(y,z) \to p(x,z)] \quad \longleftrightarrow \quad \forall x \forall y \forall z \, [p(x,z) \to p(y,z)], $$ since $\forall x \forall y$ is the same thing as $\forall y \forall x$. So your logic is incorrect.

Similarly, if $\varphi$ is promised to be symmetric then the equivalence holds, for similar reasons.

A simple example where the equivalence doesn't hold is $\varphi(x,y) = x$, $p(x,y) = x$.

In this case the first statement is $$ \forall x \forall y \forall z \, [x \land y \to x], $$ whereas the second statement is $$ \forall x \forall y \forall z \, [x \land x \to y]. $$ (This assumes that the statements are interpreted as $(\varphi \land p) \to p$ rather than $\varphi \land (p \to p)$.)

| cite | improve this answer | |
  • $\begingroup$ Is there any explanation why ∀x∀y∀z[x∧y→x] is not equivalent to ∀x∀y∀z[x∧x→y]? .... I mean, how would I prove it? $\endgroup$ – George Z. Sep 8 '19 at 15:16
  • $\begingroup$ I'm afraid you'll have to work it out on your own. $\endgroup$ – Yuval Filmus Sep 8 '19 at 15:18
  • $\begingroup$ I see... I tried few things but still not something clear. Anyway thanks for your help. $\endgroup$ – George Z. Sep 8 '19 at 15:21
  • $\begingroup$ Use the definitions. $\endgroup$ – Yuval Filmus Sep 8 '19 at 15:22
  • $\begingroup$ [x∧y→x] => ¬(x∧y)∨x =>¬x∨¬y∨x which is always true. But x∧x→y => x->y which can be false (if y is false). What about this? :) $\endgroup$ – George Z. Sep 8 '19 at 15:44

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.