Why are these terms not equivalent?

Question

can can someone please explain me, why these terms are not equivalent when I apply alpha-conversion?

∀x p(x) ∧ q(y) != ∀y p(y) ∧ q(x)

Thanks!

Answer 1

Because while the name of bound variables doesn't matter, the name of free variables does.

For recap: In $\forall x (P(x) \land Q(y))$, the occurence of $x$ is bound by the quantifier $\forall x$, while $y$ is free. In $\forall y (P(y) \land Q(x))$, $y$ is bound by $\forall y$ while $x$ occurs free.

If you look at the definition of the truth value of quantified formulas

$$[[\forall x \phi]]_{v,\mathfrak{A}} = true \text{ iff for all $x$-alternatives } v' \text{ of } v: [[\phi]]_{v', \mathfrak{A}} = true$$ $$[[\exists x \phi]]_{v,\mathfrak{A}} = true \text{ iff there is an $x$-alternative } v' \text{ of } v: [[\phi]]_{v', \mathfrak{A}} = true$$

you see that the current assignment $v$ gets "overwritten" by quantifying over other possible assignments (the $x$-alternatives, i.e. those assignment functions that differ from $v$ at most in the value they assign to the variable $x$, and are the same on all other variables). So the truth value of a formlua where the variable is bound by a quantifier does not depend on the particular assignment function $v$, but on all possible ways of mapping the variable $x$ to entities in the domain - which is the very reason why $\alpha$-conversion can be carried out without changing the interpretation of a formula.

So $\forall x P(x)$ and $\forall y P(y)$ are equivalent, since in any case we are ranging over all possiblities to map variables to elements from the domain, and it doesn't matter which assignment we start with.

However, the same does not happen for free variables, i.e. variables which are not bound by a quantifier, so the interpretation of free variables does depend on the particular assignment function chosen: Since we don't quantify over alternatives assignments and thereby "overwrite" our initial assignment function, but stick to the $v$ we originally started evaluating our formula with, the recursive evaluation will eventually get us to semantic clause that reads

$$[[x]]_{v,\mathfrak{A}} = v(x)$$

- i.e. the interpretation of the variable $x$ is whatever the assignment function $v$ maps it to. So if we choose a different variable and that variable is not bound by a quantifier but evaluated in a free occurrence, then the same assignment function might get us a different interpretation, if it maps the variable $y$ to something different than $x$.

So in general, $P(x)$ and $P(y)$ (without a quantifier) are not equivalent, since their semantics depends on how the current assignment function interprets $x$ and $y$.

This can be illustrated by a simple counterexample: Consider the structure $$\mathfrak{A} = \langle \mathcal{A}, \mathcal{I} \rangle$$ with $$\mathcal{A} = \{0,1\}$$ $$\mathcal{I}(P) = \{0,1\};\ \mathcal{I}(Q) = \{0\}$$ and two different assignment functions: $$v_1: x \mapsto 1, y \mapsto 0$$ $$v_2: x \mapsto 0, y \mapsto 1$$

Then $[[\forall x (P(x) \land Q(y))]]_{v_1, \mathcal{A}} = true$, since every way of mapping $x$ to an element from the domain $\{0,1\}$ makes $P(x)$ true, and $[[y]]_{v_1, \mathcal{A}} = v_1(y) = 0$ with $0 \in \mathcal{I}(Q)$.
But $[[\forall y (P(y) \land Q(x))]]_{v_1, \mathcal{A}} = false$, since every way of mapping $y$ to an element from the domain $\{0,1\}$ makes $P(y)$ true, but $[[x]]_{v_1, \mathcal{A}} = v_1(x) = 1$ with $1 \not \in \mathcal{I}(Q)$.
The converse holds for the assignment function $v_2$: $[[\forall x (P(x) \land Q(y))]]_{v_2, \mathcal{A}} = false$, and $[[\forall y (P(y) \land Q(x))]]_{v_2, \mathcal{A}} = true$.
Hence, $[[\forall x (P(x) \land Q(y))]]_{v_1, \mathcal{A}} = true \neq false = [[\forall y (P(y) \land Q(x))]]_{v_1, \mathcal{A}}$; and since there is an assignment under which the two formulas differ in their truth value, or, put differently, are true under different assignment functions, the two formulas are not equivalent.

BTW: $\forall x (P(x) \land Q(y))$ and $\forall y (P(y) \land Q(x))$ are not terms: Terms are expressions which stand for individuals (= elements from a structure's domain) - i.e. variables, individual constants, and function symbols applied to terms. $\forall x (P(x) \land Q(y))$ is a formula - i.e. an expression which is evaluated as true or false. Terms and formulas are slightly different things.