patternMinor
Are these 2 equivalent?
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
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.
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)$.)
$$
\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.