What does x is free for substitution for y in $\varphi$, but not for z means?

Question

I am studying about first order predicate logic, and I have some difficulties understanding substitution and free variables.

If x is free for substitution for y in $\varphi$, but not for z, where $\varphi$ is a single formula, what would this mean?

Also x,y and z are variables.

Can you give a formula $\varphi$ that satisfies this condition?

Answer 1

Consider the open wff with two free variables

$Fy \to \forall x Gzx$

Then substituting $x$ for $y$ gives us

$Fx \to \forall x Gzx$

Again a wff with two free variables (check you understand this claim). The two expressions can in effect be thought of as available to express the same binary relation.

Substituting $x$ for $z$ in the first wff however gives us

$Fy \to \forall x Gxx$

a wff now with one free variable. What's happened is that, in the second case, what was a free variable gets captured by the quantifier, and so the quantificational structure of the wff is changed. We don't want merely changing the letter we use for a variable to have that sort of effect -- hence, as we say, '$x$' is here not free to be substituted for '$z$' (while preserving quantificational structure).