Alphaequivalentie

Alphaequivalentie, or alpha-equivalence, is a notion of equality used in the lambda calculus and related formal systems. It identifies terms that have the same structure and binding, differing only in the names chosen for bound variables. In other words, two terms are alpha-equivalent if one can be obtained from the other by renaming bound variables throughout the term.

A classic example is that lambda abstractions λx. x and λy. y are alpha-equivalent. More generally, λx. λy. x y is alpha-equivalent to λa. λb. a b. By contrast, λx. y is not alpha-equivalent to λy. y, because in the first term y is a free variable, while in the second it is bound by the inner abstraction; renaming bound variables cannot change free variables into bound ones.

Formally, alpha-conversion expresses the idea that λx. M ≡α λy. M[y/x], provided y does not occur free in M. The relation alpha-equivalence is an equivalence relation (reflexive, symmetric, transitive) and is a congruence with respect to term formation, meaning that the equivalence is preserved under application and abstraction.

Alpha-equivalence is essential for reasoning about programs and proofs without being tied to arbitrary variable names. It underpins substitution rules to avoid variable capture and is often implemented in compilers and proof systems using techniques such as de Bruijn indices, which eliminate variable names entirely. The term alphaequivalentie is the Dutch-language variant of this concept.