Function composition

From Wikipedia for FEVERv2
Jump to navigation Jump to search

This article is about function composition in mathematics. Function composition_sentence_0

For function composition in computer science, see Function composition (computer science). Function composition_sentence_1

"ring operator" redirects here. Function composition_sentence_2

It is not to be confused with operator ring or operator assistance. Function composition_sentence_3

In mathematics, function composition is an operation that takes two functions f and g and produces a function h such that h(x) = g(f(x)). Function composition_sentence_4

In this operation, the function g is applied to the result of applying the function f to x. Function composition_sentence_5

That is, the functions f : X → Y and g : Y → Z are composed to yield a function that maps x in X to g(f(x)) in Z. Function composition_sentence_6

Intuitively, if z is a function of y, and y is a function of x, then z is a function of x. Function composition_sentence_7

The resulting composite function is denoted g ∘ f : X → Z, defined by (g ∘ f )(x) = g(f(x)) for all x in X. Function composition_sentence_8

The notation g ∘ f is read as "g circle f ", "g round f ", "g about f ", "g composed with f ", "g after f ", "g following f ", "g of f", "f then g", or "g on f ". Function composition_sentence_9

Intuitively, composing functions is a chaining process in which the output of function f feeds the input of function g. Function composition_sentence_10

Composition of functions is different from multiplication of functions, and has quite different properties; in particular, composition of functions is not commutative. Function composition_sentence_11

Examples Function composition_section_0

Function composition_unordered_list_0

  • Composition of functions on a finite set: If f = {(1, 1), (2, 3), (3, 1), (4, 2)}, and g = {(1, 2), (2, 3), (3, 1), (4, 2)}, then g ∘ f = {(1, 2), (2, 1), (3, 2), (4, 3)}, as shown in the figure.Function composition_item_0_0
  • Composition of functions on an infinite set: If f: ℝ → ℝ (where ℝ is the set of all real numbers) is given by f(x) = 2x + 4 and g: ℝ → ℝ is given by g(x) = x, then:Function composition_item_0_1

Function composition_description_list_1

  • (f ∘ g)(x) = f(g(x)) = f(x) = 2x + 4, andFunction composition_item_1_2
  • (g ∘ f)(x) = g(f(x)) = g(2x + 4) = (2x + 4).Function composition_item_1_3

Function composition_unordered_list_2

  • If an airplane's altitude at time t is a(t), and the air pressure at altitude x is p(x), then (p ∘ a)(t) is the pressure around the plane at time t.Function composition_item_2_4

Properties Function composition_section_1

The composition of functions is always associative—a property inherited from the composition of relations. Function composition_sentence_12

That is, if f, g, and h are composable, then f ∘ (g ∘ h) = (f ∘ g) ∘ h. Since the parentheses do not change the result, they are generally omitted. Function composition_sentence_13

In a strict sense, the composition g ∘ f is only meaningful if the codomain of f equals the domain of g; in a wider sense, it is sufficient that the former be a subset of the latter. Function composition_sentence_14

Moreover, it is often convenient to tacitly restrict the domain of f, such that f produces only values in the domain of g. For example, the composition g ∘ f of the functions f : (−∞,+9] defined by f(x) = 9 − x and g : [0,+∞) → ℝ defined by g(x) = √x can be defined on the interval [−3,+3]. Function composition_sentence_15

The functions g and f are said to commute with each other if g ∘ f = f ∘ g. Commutativity is a special property, attained only by particular functions, and often in special circumstances. Function composition_sentence_16

For example, |x| + 3 = |x + 3| only when x ≥ 0. Function composition_sentence_17

The picture shows another example. Function composition_sentence_18

The composition of one-to-one functions is always one-to-one. Function composition_sentence_19

Similarly, the composition of onto functions is always onto. Function composition_sentence_20

It follows that the composition of two bijections is also a bijection. Function composition_sentence_21

The inverse function of a composition (assumed invertible) has the property that (f ∘ g) = g∘ f. Function composition_sentence_22

Derivatives of compositions involving differentiable functions can be found using the chain rule. Function composition_sentence_23

Higher derivatives of such functions are given by Faà di Bruno's formula. Function composition_sentence_24

Composition monoids Function composition_section_2

Main article: Transformation monoid Function composition_sentence_25

Suppose one has two (or more) functions f: X → X, g: X → X having the same domain and codomain; these are often called transformations. Function composition_sentence_26

Then one can form chains of transformations composed together, such as f ∘ f ∘ g ∘ f. Such chains have the algebraic structure of a monoid, called a transformation monoid or (much more seldom) a composition monoid. Function composition_sentence_27

In general, transformation monoids can have remarkably complicated structure. Function composition_sentence_28

One particular notable example is the de Rham curve. Function composition_sentence_29

The set of all functions f: X → X is called the full transformation semigroup or symmetric semigroup on X. Function composition_sentence_30

(One can actually define two semigroups depending how one defines the semigroup operation as the left or right composition of functions.) Function composition_sentence_31

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

A fundamental result in group theory, Cayley's theorem, essentially says that any group is in fact just a subgroup of a permutation group (up to isomorphism). Function composition_sentence_33

The set of all bijective functions f: X → X (called permutations) forms a group with respect to function composition. Function composition_sentence_34

This is the symmetric group, also sometimes called the composition group. Function composition_sentence_35

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. Function composition_sentence_36

Functional powers Function composition_section_3

Main article: Iterated function Function composition_sentence_37

If Y X, then f: X→Y may compose with itself; this is sometimes denoted as f. That is: Function composition_sentence_38

Function composition_description_list_3

  • (f ∘ f)(x) = f(f(x)) = f (x)Function composition_item_3_5

Function composition_description_list_4

  • (f ∘ f ∘ f)(x) = f(f(f(x))) = f (x)Function composition_item_4_6

Function composition_description_list_5

  • (f ∘ f ∘ f ∘ f)(x) = f(f(f(f(x)))) = f (x)Function composition_item_5_7

More generally, for any natural number n ≥ 2, the nth functional power can be defined inductively by f  = f ∘ f  = f  ∘ f, a notation introduced by Hans Heinrich Bürmann and John Frederick William Herschel. Function composition_sentence_39

Repeated composition of such a function with itself is called iterated function. Function composition_sentence_40

Function composition_unordered_list_6

  • By convention, f  is defined as the identity map on f 's domain, idX.Function composition_item_6_8
  • If even Y = X and f: X → X admits an inverse function f , negative functional powers f  are defined for n > 0 as the negated power of the inverse function: f  = (f ).Function composition_item_6_9

Note: If f takes its values in a ring (in particular for real or complex-valued f ), there is a risk of confusion, as f  could also stand for the n-fold product of f, e.g. f (x) = f(x) · f(x). Function composition_sentence_41

For trigonometric functions, usually the latter is meant, at least for positive exponents. Function composition_sentence_42

For example, in trigonometry, this superscript notation represents standard exponentiation when used with trigonometric functions: sin(x) = sin(x) · sin(x). Function composition_sentence_43

However, for negative exponents (especially −1), it nevertheless usually refers to the inverse function, e.g., tan = arctan ≠ 1/tan. Function composition_sentence_44

In some cases, when, for a given function f, the equation g ∘ g = f has a unique solution g, that function can be defined as the functional square root of f, then written as g = f . Function composition_sentence_45

More generally, when g = f has a unique solution for some natural number n > 0, then f  can be defined as g. Function composition_sentence_46

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. Function composition_sentence_47

Iterated functions and flows occur naturally in the study of fractals and dynamical systems. Function composition_sentence_48

To avoid ambiguity, some mathematicians choose to use ∘ to denote the compositional meaning, writing f(x) for the n-th iterate of the function f(x), as in, for example, f(x) meaning f(f(f(x))). Function composition_sentence_49

For the same purpose, f(x) was used by Benjamin Peirce whereas Alfred Pringsheim and Jules Molk suggested f(x) instead. Function composition_sentence_50

Alternative notations Function composition_section_4

Many mathematicians, particularly in group theory, omit the composition symbol, writing gf for g ∘ f. Function composition_sentence_51

In the mid-20th century, some mathematicians decided that writing "g ∘ f " to mean "first apply f, then apply g" was too confusing and decided to change notations. Function composition_sentence_52

They write "xf " for "f(x)" and "(xf)g" for "g(f(x))". Function composition_sentence_53

This can be more natural and seem simpler than writing functions on the left in some areas – in linear algebra, for instance, when x is a row vector and f and g denote matrices and the composition is by matrix multiplication. Function composition_sentence_54

This alternative notation is called postfix notation. Function composition_sentence_55

The order is important because function composition is not necessarily commutative (e.g. matrix multiplication). Function composition_sentence_56

Successive transformations applying and composing to the right agrees with the left-to-right reading sequence. Function composition_sentence_57

Mathematicians who use postfix notation may write "fg", meaning first apply f and then apply g, in keeping with the order the symbols occur in postfix notation, thus making the notation "fg" ambiguous. Function composition_sentence_58

Computer scientists may write "f ; g" for this, thereby disambiguating the order of composition. Function composition_sentence_59

To distinguish the left composition operator from a text semicolon, in the Z notation the ⨾ character is used for left relation composition. Function composition_sentence_60

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). Function composition_sentence_61

Composition operator Function composition_section_5

Main article: Composition operator Function composition_sentence_62

Given a function g, the composition operator Cg is defined as that operator which maps functions to functions as Function composition_sentence_63

Composition operators are studied in the field of operator theory. Function composition_sentence_64

In programming languages Function composition_section_6

Main article: Function composition (computer science) Function composition_sentence_65

Function composition appears in one form or another in numerous programming languages. Function composition_sentence_66

Multivariate functions Function composition_section_7

Partial composition is possible for multivariate functions. Function composition_sentence_67

The function resulting when some argument xi of the function f is replaced by the function g is called a composition of f and g in some computer engineering contexts, and is denoted f |xi = g Function composition_sentence_68

When g is a simple constant b, composition degenerates into a (partial) valuation, whose result is also known as restriction or co-factor. Function composition_sentence_69

In general, the composition of multivariate functions may involve several other functions as arguments, as in the definition of primitive recursive function. Function composition_sentence_70

Given f, a n-ary function, and n m-ary functions g1, ..., gn, the composition of f with g1, ..., gn, is the m-ary function Function composition_sentence_71

This is sometimes called the generalized composite of f with g1, ..., gn. Function composition_sentence_72

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. Function composition_sentence_73

Here g1, ..., gn 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. Function composition_sentence_74

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. Function composition_sentence_75

Note that a clone generally contains operations of various arities. Function composition_sentence_76

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 i.e.: Function composition_sentence_77

A unary operation always commutes with itself, but this is not necessarily the case for a binary (or higher arity) operation. Function composition_sentence_78

A binary (or higher arity) operation that commutes with itself is called medial or entropic. Function composition_sentence_79

Generalizations Function composition_section_8

The composition is defined in the same way for partial functions and Cayley's theorem has its analogue called the Wagner–Preston theorem. Function composition_sentence_80

The category of sets with functions as morphisms is the prototypical category. Function composition_sentence_81

The axioms of a category are in fact inspired from the properties (and also the definition) of function composition. Function composition_sentence_82

The structures given by composition are axiomatized and generalized in category theory with the concept of morphism as the category-theoretical replacement of functions. Function composition_sentence_83

The reversed order of composition in the formula (f ∘ g) = (g ∘ f ) applies for composition of relations using converse relations, and thus in group theory. Function composition_sentence_84

These structures form dagger categories. Function composition_sentence_85

Typography Function composition_section_9

The composition symbol ∘ is encoded as U+2218 ∘ RING OPERATOR (HTML ∘ · ∘, ∘); see the Degree symbol article for similar-appearing Unicode characters. Function composition_sentence_86

In TeX, it is written \circ. Function composition_sentence_87

See also Function composition_section_10

Function composition_unordered_list_7

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: composition.