Substitutieproduct

Substitutieproduct, commonly referred to in English as substitution product or composition, is a mathematical operation used to combine structures by replacing elements of one object with whole objects from another. It appears in several areas of mathematics and theoretical computer science, notably in term manipulation, combinatorics of species, and the study of generating functions.

In logic and term rewriting, a substitution is a mapping from variables to terms. The substitution product (often called composition) of two substitutions σ and τ is obtained by applying τ first and then σ. Formally, it maps each variable to the σ-image of its τ-image. This operation is associative and has the empty substitution as its identity element. For example, if σ = {x ↦ f(y), y ↦ a} and τ = {y ↦ b}, then the composed substitution σ ∘ τ maps x ↦ f(b) and y ↦ a. The substitution product is a fundamental tool for chaining variable replacements in unification, rewriting, and the semantics of programming languages.

In combinatorics, the substitution product describes replacing each atom or building block of one combinatorial class with a whole structure from another class. If F and G are combinatorial species or classes, their substitution product F ∘ G forms new objects by substituting a G-structure into every atomic position of an F-structure. This operation is associative and interacts with other combinatorial operations such as product and sum. In terms of generating functions, substitution often corresponds to the composition of generating functions, a perspective central to the theory of plethysm in combinatorial species.

Applications span algebra, logic, and enumerative combinatorics, where substitution enables modeling of hierarchical or recursive constructions.