Function composition

Revision as of 08:50, 25 February 2025 by imported>Jochen Burghardt (→‎Composition monoids: suggest to link the article about the jargon term "up to", where "up to isomorphism" is one of the examples (see up to#Group theory, linking there directly could be an WP:EASTEREGG); rm adjacent link isomorphism per MOS:SPECIFICLINK;)
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Template:Short description Template:About Template:Redirect-distinguish Template:Redirects Template:Use dmy dates Template:Functions

In mathematics, the composition operator <math>\circ</math> takes two functions, <math>f</math> and <math>g</math>, and returns a new function <math>h(x) := (g \circ f) (x) = g(f(x))</math>. Thus, the function Template:Math is applied after applying Template:Math to Template:Math. <math>(g \circ f)</math> is pronounced "the composition of Template:Math and Template:Math".<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

Reverse composition, sometimes denoted <math>f \mapsto g</math> , applies the operation in the opposite order, applying <math>f</math> first and <math>g</math> second. Intuitively, reverse composition is a chaining process in which the output of function Template:Math feeds the input of function Template:Math.

The composition of functions is a special case of the composition of relations, sometimes also denoted by <math>\circ</math>. As a result, all properties of composition of relations are true of composition of functions,<ref name="Velleman_2006" /> such as associativity.

ExamplesEdit

File:Example for a composition of two functions.svg
Concrete example for the composition of two functions.

PropertiesEdit

The composition of functions is always associative—a property inherited from the composition of relations.<ref name="Velleman_2006"/> That is, if Template:Mvar, Template:Mvar, and Template:Mvar are composable, then Template:Math.<ref name=":0">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> Since the parentheses do not change the result, they are generally omitted.

In a strict sense, the composition Template:Math is only meaningful if the codomain of Template:Mvar equals the domain of Template:Mvar; in a wider sense, it is sufficient that the former be an improper subset of the latter.<ref group="nb" name="NB_Strict"/> Moreover, it is often convenient to tacitly restrict the domain of Template:Mvar, such that Template:Mvar produces only values in the domain of Template:Mvar. For example, the composition Template:Math of the functions Template:Math defined by Template:Math and Template:Math defined by <math>g(x) = \sqrt x</math> can be defined on the interval Template:Math.

File:Absolute value composition.svg
Compositions of two real functions, the absolute value and a cubic function, in different orders, show a non-commutativity of composition.

The functions Template:Mvar and Template:Mvar are said to commute with each other if Template:Math. Commutativity is a special property, attained only by particular functions, and often in special circumstances. For example, Template:Math only when Template:Math. The picture shows another example.

The composition of one-to-one (injective) functions is always one-to-one. Similarly, the composition of onto (surjective) functions is always onto. It follows that the composition of two bijections is also a bijection. The inverse function of a composition (assumed invertible) has the property that Template:Math.<ref name="Rodgers_2000"/>

Derivatives of compositions involving differentiable functions can be found using the chain rule. Higher derivatives of such functions are given by Faà di Bruno's formula.<ref name=":0" />

Composition of functions is sometimes described as a kind of multiplication on a function space, but has very different properties from pointwise multiplication of functions (e.g. composition is not commutative).<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

Composition monoidsEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Suppose one has two (or more) functions Template:Math Template:Math having the same domain and codomain; these are often called transformations. Then one can form chains of transformations composed together, such as Template:Math. Such chains have the algebraic structure of a monoid, called a transformation monoid or (much more seldom) a composition monoid. In general, transformation monoids can have remarkably complicated structure. One particular notable example is the de Rham curve. The set of all functions Template:Math is called the full transformation semigroup<ref name="Hollings_2014"/> or symmetric semigroup<ref name="Grillet_1995"/> on Template:Mvar. (One can actually define two semigroups depending how one defines the semigroup operation as the left or right composition of functions.<ref name="Dömösi-Nehaniv_2005"/>)

File:SVG skew and rotation.svg
Composition of a shear mapping (red) and a clockwise rotation by 45° (green). On the left is the original object. Above is shear, then rotate. Below is rotate, then shear.

If the given transformations are bijective (and thus invertible), then the set of all possible combinations of these functions forms a transformation group (also known as a permutation group); and one says that the group is generated by these functions.

The set of all bijective functions Template:Math (called permutations) forms a group with respect to function composition. This is the symmetric group, also sometimes called the composition group. A fundamental result in group theory, Cayley's theorem, essentially says that any group is in fact just a subgroup of a symmetric group (up to isomorphism).<ref name="Carter_2009"/>

In the symmetric semigroup (of all transformations) one also finds a weaker, non-unique notion of inverse (called a pseudoinverse) because the symmetric semigroup is a regular semigroup.<ref name="Ganyushkin-Mazorchuk_2008"/>

Functional powersEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} If Template:Math, then <math>f:X\to Y</math> may compose with itself; this is sometimes denoted as <math> f^2</math>. That is: Template:Block indent Template:Block indent Template:Block indent

More generally, for any natural number Template:Math, the Template:Mvarth functional power can be defined inductively by Template:Math, a notation introduced by Hans Heinrich BürmannTemplate:Cn<ref name="Herschel_1820"/><ref name="Cajori_1929"/> and John Frederick William Herschel.<ref name="Herschel_1813"/><ref name="Herschel_1820"/><ref name="Peano_1903"/><ref name="Cajori_1929"/> Repeated composition of such a function with itself is called function iteration.

Note: If Template:Mvar takes its values in a ring (in particular for real or complex-valued Template:Math), there is a risk of confusion, as Template:Math could also stand for the Template:Mvar-fold product of Template:Mvar, e.g. Template:Math.<ref name="Cajori_1929"/> For trigonometric functions, usually the latter is meant, at least for positive exponents.<ref name="Cajori_1929"/> For example, in trigonometry, this superscript notation represents standard exponentiation when used with trigonometric functions:

Template:Math.

However, for negative exponents (especially −1), it nevertheless usually refers to the inverse function, e.g., Template:Math.

In some cases, when, for a given function Template:Mvar, the equation Template:Math has a unique solution Template:Mvar, that function can be defined as the functional square root of Template:Mvar, then written as Template:Math.

More generally, when Template:Math has a unique solution for some natural number Template:Math, then Template:Math can be defined as Template:Math.

Under additional restrictions, this idea can be generalized so that the iteration count becomes a continuous parameter; in this case, such a system is called a flow, specified through solutions of Schröder's equation. Iterated functions and flows occur naturally in the study of fractals and dynamical systems.

To avoid ambiguity, some mathematiciansTemplate:Cn choose to use Template:Math to denote the compositional meaning, writing Template:Math for the Template:Mvar-th iterate of the function Template:Math, as in, for example, Template:Math meaning Template:Math. For the same purpose, Template:Math was used by Benjamin Peirce<ref name="Peirce_1852"/><ref name="Cajori_1929"/> whereas Alfred Pringsheim and Jules Molk suggested Template:Math instead.<ref name="Pringsheim-Molk_1907"/><ref name="Cajori_1929"/><ref group="nb" name="NB_Rucker"/>

Alternative notationsEdit

Many mathematicians, particularly in group theory, omit the composition symbol, writing Template:Math for Template:Math.<ref name="Ivanov_2009"/>

During the mid-20th century, some mathematicians adopted postfix notation, writing Template:Math for Template:Math and Template:Math for Template:Math.<ref name="Gallier_2011" /> This can be more natural than prefix notation in many cases, such as in linear algebra when Template:Mvar is a row vector and Template:Mvar and Template:Mvar denote matrices and the composition is by matrix multiplication. The order is important because function composition is not necessarily commutative. Having successive transformations applying and composing to the right agrees with the left-to-right reading sequence.

Mathematicians who use postfix notation may write "Template:Math", meaning first apply Template:Mvar and then apply Template:Mvar, in keeping with the order the symbols occur in postfix notation, thus making the notation "Template:Math" ambiguous. Computer scientists may write "Template:Math" for this,<ref name="Barr-Wells_1990"/> thereby disambiguating the order of composition. To distinguish the left composition operator from a text semicolon, in the Z notation the ⨾ character is used for left relation composition.<ref name="ISOIEC13568"/> Since all functions are binary relations, it is correct to use the [fat] semicolon for function composition as well (see the article on composition of relations for further details on this notation).

Composition operatorEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Given a function Template:Math, the composition operator Template:Math is defined as that operator which maps functions to functions as <math display="block">C_g f = f \circ g.</math>Composition operators are studied in the field of operator theory.

In programming languagesEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Function composition appears in one form or another in numerous programming languages.

Multivariate functionsEdit

Partial composition is possible for multivariate functions. The function resulting when some argument Template:Math of the function Template:Mvar is replaced by the function Template:Mvar is called a composition of Template:Mvar and Template:Mvar in some computer engineering contexts, and is denoted Template:Math <math display="block">f|_{x_i = g} = f (x_1, \ldots, x_{i-1}, g(x_1, x_2, \ldots, x_n), x_{i+1}, \ldots, x_n).</math>

When Template:Mvar is a simple constant Template:Mvar, composition degenerates into a (partial) valuation, whose result is also known as restriction or co-factor.<ref name="Bryant_1986"/>

<math display="block">f|_{x_i = b} = f (x_1, \ldots, x_{i-1}, b, x_{i+1}, \ldots, x_n).</math>

In general, the composition of multivariate functions may involve several other functions as arguments, as in the definition of primitive recursive function. Given Template:Mvar, a Template:Mvar-ary function, and Template:Mvar Template:Mvar-ary functions Template:Math, the composition of Template:Mvar with Template:Math, is the Template:Mvar-ary function <math display="block">h(x_1,\ldots,x_m) = f(g_1(x_1,\ldots,x_m),\ldots,g_n(x_1,\ldots,x_m)).</math>

This is sometimes called the generalized composite or superposition of f with Template:Math.<ref name="Bergman_2011"/> The partial composition in only one argument mentioned previously can be instantiated from this more general scheme by setting all argument functions except one to be suitably chosen projection functions. Here Template:Math can be seen as a single vector/tuple-valued function in this generalized scheme, in which case this is precisely the standard definition of function composition.<ref name="Tourlakis_2012"/>

A set of finitary operations on some base set X is called a clone if it contains all projections and is closed under generalized composition. A clone generally contains operations of various arities.<ref name="Bergman_2011"/> The notion of commutation also finds an interesting generalization in the multivariate case; a function f of arity n is said to commute with a function g of arity m if f is a homomorphism preserving g, and vice versa, that is:<ref name="Bergman_2011"/> <math display="block">f(g(a_{11},\ldots,a_{1m}),\ldots,g(a_{n1},\ldots,a_{nm})) = g(f(a_{11},\ldots,a_{n1}),\ldots,f(a_{1m},\ldots,a_{nm})).</math>

A unary operation always commutes with itself, but this is not necessarily the case for a binary (or higher arity) operation. A binary (or higher arity) operation that commutes with itself is called medial or entropic.<ref name="Bergman_2011"/>

GeneralizationsEdit

Composition can be generalized to arbitrary binary relations. If Template:Math and Template:Math are two binary relations, then their composition amounts to

<math>R \circ S = \{(x,z) \in X \times Z: (\exists y \in Y)((x,y) \in R\,\and\,(y,z) \in S)\}</math>.

Considering a function as a special case of a binary relation (namely functional relations), function composition satisfies the definition for relation composition. A small circle Template:Math has been used for the infix notation of composition of relations, as well as functions. When used to represent composition of functions <math>(g \circ f)(x) \ = \ g(f(x))</math> however, the text sequence is reversed to illustrate the different operation sequences accordingly.

The composition is defined in the same way for partial functions and Cayley's theorem has its analogue called the Wagner–Preston theorem.<ref name="Lipcomb_1997"/>

The category of sets with functions as morphisms is the prototypical category. The axioms of a category are in fact inspired from the properties (and also the definition) of function composition.<ref name="Hilton-Wu_1989"/> The structures given by composition are axiomatized and generalized in category theory with the concept of morphism as the category-theoretical replacement of functions. The reversed order of composition in the formula Template:Math applies for composition of relations using converse relations, and thus in group theory. These structures form dagger categories.

The standard "foundation" for mathematics starts with sets and their elements. It is possible to start differently, by axiomatising not elements of sets but functions between sets. This can be done by using the language of categories and universal constructions.


. . . the membership relation for sets can often be replaced by the composition operation for functions. This leads to an alternative foundation for Mathematics upon categories -- specifically, on the category of all functions. Now much of Mathematics is dynamic, in that it deals with morphisms of an object into another object of the same kind. Such morphisms (like functions) form categories, and so the approach via categories fits well with the objective of organizing and understanding Mathematics. That, in truth, should be the goal of a proper philosophy of Mathematics.

- Saunders Mac Lane, Mathematics: Form and Function<ref>{{#invoke:citation/CS1|citation |CitationClass=web

}}</ref>

TypographyEdit

The composition symbol Template:Math is encoded as Template:Unichar; see the Degree symbol article for similar-appearing Unicode characters. In TeX, it is written \circ.

See alsoEdit

NotesEdit

Template:Reflist

ReferencesEdit

Template:Reflist

External linksEdit