A mapping from variables to terms which, when applied to a term or formula, replaces each variable in its domain uniformly by the corresponding term and extends homomorphically to compound terms.

Principle

A substitution sigma = { x1 -> t1, ..., xn -> tn } is extended to terms by replacing variables and applying sigma recursively to function arguments; composition and restriction of substitutions obey algebraic laws and interact critically with variable binding and capture.

Demonstration

With sigma = { x -> f(a), y -> b }, applying sigma to term g(x,y,z) yields g(f(a), b, z). In unification, one seeks a substitution making two terms identical, e.g., unify f(x,a) and f(b,y) yields { x->b, y->a }.

Misapplication

Applying a substitution in the presence of binders (e.g., lambda abstractions) without renaming bound variables leads to variable capture; assuming substitution composition is commutative or that substitutions are invertible without checking conditions is also incorrect.

Consequence

Substitutions instantiate schematic terms into concrete terms, enable unification and matching, drive rule application in rewriting, and are fundamental to inference steps in logic and automated reasoning.

Reversal

Consider anti-substitution or pattern abstraction that extracts a substitution making a concrete term arise from a pattern; anti-substitution is often partial or non-unique, reversing substitution is nontrivial compared to forward application.

Boundary

Defined for free variables of first-order terms and formulas; substitution semantics must be adapted or restricted when binders, higher-order variables, or meta-variables are present, and care is required to avoid capture.

Semantic Tension

Tension between syntactic substitution (textual replacement in terms) and semantic assignment (mapping variables to values in a model); syntactic substitution changes term structure, while semantic assignments relate to valuation and truth.

Synthesis

A substitution is an algebraic map from variables to terms extended homomorphically to compound expressions; it is the mechanism that instantiates variables, underlies unification and rewriting, and requires capture-avoiding discipline in the presence of binders.