Lambda calculus
Capture-avoiding substitutions

Suppose t {\displaystyle t}, s {\displaystyle s} and r {\displaystyle r} are lambda terms, and x {\displaystyle x} and y {\displaystyle y} are variables.The notation t {\displaystyle t} indicates substitution of r {\displaystyle r} for x {\displaystyle x} in t {\displaystyle t} in a capture-avoiding manner. This is defined so that:

For example, (λ x. x) = λ x. (x) = λ x. x {\displaystyle (\lambda x.x)=\lambda x.(x)=\lambda x.x}, and ((λ x. y) x) = ((λ x. y)) (x) = (λ x. y) y {\displaystyle ((\lambda x.y)x)=((\lambda x.y))(x)=(\lambda x.y)y}.

The freshness condition (requiring that y {\displaystyle y} is not in the free variables of r {\displaystyle r}) is crucial in order to ensure that substitution does not change the meaning of functions.

For example, a substitution that ignores the freshness condition could lead to errors: (λ x. y) = λ x. (y) = λ x. x {\displaystyle (\lambda x.y)=\lambda x.(y)=\lambda x.x}. This erroneous substitution would turn the constant function λ x. y {\displaystyle \lambda x.y} into the identity λ x. x {\displaystyle \lambda x.x}.

In general, failure to meet the freshness condition can be remedied by alpha-renaming first, with a suitable fresh variable.For example, switching back to our correct notion of substitution, in (λ x. y) {\displaystyle (\lambda x.y)} the abstraction can be renamed with a fresh variable z {\displaystyle z}, to obtain (λ z. y) = λ z. (y) = λ z. x {\displaystyle (\lambda z.y)=\lambda z.(y)=\lambda z.x}, and the meaning of the function is preserved by substitution.
detectable_content:number_placeholders[6], keywords:existence