How does substitution work in predicate logic?

Question

the problem described (in swedish unfortunately)

I have a problem regarding substitution of a predicate logic formula. I am supposed to replace x with t, (t is equal to f(y)) where it's absolutely necessary. My suspicion is that the formula won't change, since x is a bound variable at one place and ∀y(Q(f(y),y)) isn't allowed for some reason? Can someone solve this problem for me and explain why the solution is like that? I would be very grateful!

Answer 1

No, the substitution $\Phi[t/x]$ will change the formula.

Let

$\Phi := Px \to \forall y (Q(x,y) \land \exists x R(y,x))$.

In it, the two left occurrences of $x$ are free. Thus the substitution of $x$ with $f(y)$ as $t$ will produce the formula :

$\Phi[t/x] := P(f(y)) \to \forall y(Q(f(y),y) \land \exists x R(y,x))$.

As you can see, the second occurrence of $x$ is in the scope of a quantifier $\forall y$; this has the effect that, after substitution, the variable $y$ in $f(y)$ has been "captured" by the quantifier, producing an incorrect result.

Thus, if we assume that the substitution must produce a correct result, we have first to rewrite the formula using e.g. $z$ as bound variable in place of $y$, to get :

$\Phi := Px \to \forall z (Q(x,z) \land \exists x R(z,x))$.

Now we can safely perform the substitution $\Phi[t/x]$.

---

The rules for "correct" substitutions in FOL are managed through the concept of "a term being free for (or : substitutable) a variable in a formula"; see this post for the formal definition.