# Are these 2 equivalent?

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

• 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? – George Z. Sep 8 at 15:16
• I'm afraid you'll have to work it out on your own. – Yuval Filmus Sep 8 at 15:18
• I see... I tried few things but still not something clear. Anyway thanks for your help. – George Z. Sep 8 at 15:21
• Use the definitions. – Yuval Filmus Sep 8 at 15:22
• [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? :) – George Z. Sep 8 at 15:44