First Order Logic Question

Question

$\forall x\ \forall y\ P(x,y) \to \forall x\ \forall y\ P(y,x)$

Is this a tautology?

Is there a set method that we can use to find whether a wff is a tautology?

Answer 1

If with the term tautology you mean also a valid formula of first-order logic, the answer is : YES.

In general, we have that : $\forall x \forall y \varphi$ and $\forall y \forall x \varphi$ are equivalent.

Thus, $∀x∀y P(x,y) \to ∀x∀y P(y,x)$ is equivalent to $∀x∀y P(x,y) \to ∀y∀x P(y,x)$.

In addition, you can "rename" the bounded variable without chenging the "meaning" of a formula, and thus $∀y∀x P(y,x)$ is equivalent to : $∀x∀y P(x,y)$.

In conclusion, the initial formula is equivalent to :

$∀x∀y P(x,y) \to ∀x∀y P(x,y)$,

which is valid (it is an instance of the tautology : $p \to p$).

---

You can prove it "formally" with a Natural Deduction derivation of :

$\forall x \forall y P(x,y) \vdash \forall x \forall y P(y,x)$.