Substitution (algebra)

In algebra, the operation of substitution can be applied in various contexts involving formal objects containing symbols (often called variables or indeterminates); the operation consists of systematically replacing occurrences of some symbol by a given value.

Substitution is a basic operation of computer algebra. It is generally called "subs" or "subst" in computer algebra systems.

A common case of substitution involves polynomials, where substitution of a numerical value for the indeterminate of a (univariate) polynomial amounts to evaluating the polynomial at that value. Indeed this operation occurs so frequently that the notation for polynomials is often adapted to it; instead of designating a polynomial by a name like P as one would do for other mathematical objects one could define say

$P(X)=X^{5}-3X^{2}+5X-17$

so that substitution for X can be designated by replacement inside "P(X)", say

$P(2)=13$ or $P(X+1)=X^{5}+5X^{4}+10X^{3}+7X^{2}+4X-14$.

Substitution can however also applied to other kinds of formal objects built from symbols, for instance elements of free groups. In order for substitution to be defined, one needs an algebraic structure with an appropriate universal property, that asserts the existence of unique homomorphisms that send indeterminates to specific values; the substitution then amounts to finding the image under such a homomorphism.

Substitution is related to, but not identical to function composition; it is also closely related to β-reduction in lambda calculus. In contrast to these notions however, the accent in algebra is on the preservation of algebraic structure by the substitution operation, the fact that substitution gives a homomorphism for the structure at hand (in the case of polynomials, the ring structure).