Composition (Function)

Definition

Composition (Function)

Let and be functions. Their composition is

First apply to , then apply to the result. The rightmost function is applied first, and the output of must be a valid input to .

Several inner functions

Let and . Combining the inner outputs into a tuple defines

All inner functions receive the same input ; their outputs become the arguments of . This is the composition rule used for primitive-recursive functions.

Identity and Associativity

The identity function leaves its input unchanged. For ,

For , and , composition is associative:

Parentheses do not change the result, but the order generally does: and need not agree, and one may be undefined because the types do not match.

Injectivity and Surjectivity

For and , let denote the image of , and let be restricted to this image. Then

An injective composition cannot recover distinctions lost by , but only needs to preserve distinctions among values that actually reaches. A surjective composition must reach every element of through those values.

Consequently, if both functions are injective, their composition is injective; if both are surjective, their composition is surjective. Conversely, injectivity of forces injectivity of , and surjectivity of forces surjectivity of , but neither forces both constituent functions to have the property.

Example

Order matters

Let and on . Then

Only the intermediate image matters

Let be , and let be . Then

The composition is the identity on , hence both injective and surjective. Yet is not injective, since , and is not surjective onto , since it never returns a negative integer.