##  [Substitution](/substitution-0) 

 Definition

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

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

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

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

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

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

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

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

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.