HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Are these 2 equivalent?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
aretheseequivalent

Problem

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.

Solution

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

Context

StackExchange Computer Science Q#113531, answer score: 3

Revisions (0)

No revisions yet.