The process of finding substitutions for variables that make two syntactic expressions (terms) identical according to the term algebra of a logic; outputs a substitution mapping variables to terms when one exists.

Principle

Solve a finite set of term equations by repeatedly decomposing compound terms, orienting variable equalities, applying an occurs-check to avoid cyclic substitutions, and computing the most general unifier when possible.

Demonstration

Unifying f(x, a) and f(b, y) yields the substitution {x ↦ b, y ↦ a}. In first-order resolution, unification is used to make literals syntactically identical before applying the resolution rule.

Misapplication

Omitting the occurs-check and accepting substitutions like x ↦ f(x) produces cyclic or ill-founded terms; or assuming unification always yields a unique substitution even in theories or higher-order settings where multiple incomparable unifiers or none may exist.

Consequence

When applied correctly, unification provides the substitutions needed for automated theorem proving, logic programming, and type inference; the most general unifier preserves maximal generality, enabling reuse and composing proofs or programs.

Reversal

The inverse notion is anti-unification (generalization), which finds the least general generalization of two terms rather than a substitution making them equal; conceptually, reversal shifts from solving equations to finding common structure.

Boundary

Standard (first-order) unification assumes a syntactic term algebra without built-in theories; it excludes equational or theory unification (e.g., modulo associativity or commutativity) and higher-order unification unless explicitly specified, each of which has different algorithms and decidability properties.

Semantic Tension

Tension arises between unification and pattern matching: matching fixes one side as a pattern to instantiate, yielding specialized one-way substitutions, whereas unification is symmetric and may return more general substitutions; another tension is between syntactic and equational unification (theory-sensitive).

Synthesis

Unification is an algorithmic solver for syntactic term equations: by decomposing structures, enforcing occurrence constraints, and computing most general unifiers, it supplies the substitutions that enable variable instantiation in inference, programming, and type-checking.