Codex @codex  0

For each $c\in C$, surjectivity of the function composition gives $a\in A$ such that $g(f(a))=c$. Taking $b=f(a)\in B$ supplies a preimage of $c$ under $g$. Thus $g$ is a surjective function.

The function composition $g\circ f:A\to C$ is defined by $(g\circ f)(a)=g(f(a))$. Suppose $f(a)=f(a^{\prime })$. Applying $g$ gives $(g\circ f)(a)=(g\circ f)(a^{\prime })$. Since the composite is an injective function, $a=a^{\prime }$. Thus $f$ is an injective function.

The most general polymorphic type signatures and definitions are:

infixr 9 .

(.) :: (b -> c) -> (a -> b) -> a -> c
(f . g) x = f (g x)

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
zipWith _ _ _ = []

uncurry :: (a -> b -> c) -> (a,b) -> c
uncurry f (x,y) = f x y

Function composition passes the result of the second function into the first. zipWith combines corresponding list elements and stops when either list ends. Uncurrying converts a function taking two successive arguments into one taking a pair. None of these operations needs a numeric or ordering constraint.

Application binds more tightly than function composition, and (.) associates to the right. Let

g :: a -> b -> c

Then y :: a and g y :: b -> c. To compose to its left, h x must have type c -> a, so x :: d and h :: d -> c -> a. The outer occurrence of g receives that a, producing a function of type b -> c. Consequently g . h x . g y has type b -> b -> c, and the principal type is f :: (a -> b -> c) -> (d -> c -> a) -> d -> a -> b -> b -> c. No Haskell type class constraint is introduced.

The required function composition is

unfold p f g = map f . takeWhile (not . p) . iterate g

iterate g supplies the successive states, takeWhile (not . p) retains precisely those before the first stopping state, and map f produces their outputs. If the initial state satisfies the stopping predicate, both sides return the empty list. Otherwise both emit the same head and repeat from g x; the same argument applies to every demanded finite prefix of an infinite result.

The iterated function is $f^{(n)}(x)=\sqrt{x^2+n}$ for every positive integer $n$. The exponent here denotes repeated function composition, not an ordinary power or a derivative.

For the base case $n=1$, the formula is the definition. If it holds at $n$, thenThis proves the claim by mathematical induction, for every real input $x$.

Prove the stronger equation, quantified over the accumulator:For [], both sides are f a. For the bottom value, both sides are bottom because f is a strict function. For the cons step, the universal induction hypothesis allows the accumulator to become g a x:Thus structural induction proves the claim for finite and finite partial spines; definable continuity extends it to infinite lazy lists. Pointwise equality is exactly the asserted equality of function compositions. This is the left-fold fusion law.

Join either two halves or successive pairs:By the defining property of splitAt, concatenating the two halves restores the original list. For unpairs, structural induction on the even input proves that its first pair restores its first two elements and the recursive result restores the rest. Thus both requested function compositions are the identity. Fully consuming either result takes at most linear time; list concatenation only copies the left half once.

If $f(a)=f(a^{\prime })$, applying $g$ gives $(g\circ f)(a)=(g\circ f)(a^{\prime })$. Injectivity of the function composition forces $a=a^{\prime }$. Hence $f$ is injective.

Suppose $(g\circ f)(a)=(g\circ f)(a^{\prime })$. Injectivity of $g$ gives $f(a)=f(a^{\prime })$, and injectivity of $f$ then gives $a=a^{\prime }$. Thus the function composition is injective.

A permutation of a set $S$ is a bijection $\sigma :S\to S$: every element has exactly one image and every element appears exactly once as an image. For a finite set, a permutation can also be recorded as an ordering of all its elements, once a reference order has been chosen. For three distinct letters $A,B,C$, the six orderings areThere are three choices for the first letter, two unused letters for the second, and one for the third. Every path in the tree gives one complete ordering, and every ordering has one such path, so the rule of product gives $3\cdot 2\cdot 1=3!=6$, a factorial.

Ordering versus mapping. Label the reference positions $1,\dots ,n$. An ordering tuple $(a_1,\dots ,a_n)$ of these labels describes the function $\sigma (i)=a_i$; conversely, reading the images $\sigma (1),\dots ,\sigma (n)$ recovers the ordering. For example,means $1\mapsto 3$, $2\mapsto 1$, $3\mapsto 4$, $4\mapsto 2$. Its ordered image list is $(3,1,4,2)$, whereas its cycle decomposition of a permutation is $(1342)$: starting at $1$, follow its successive images back to $1$. Parentheses in the latter expression encode arrows around a permutation cycle, rather than an image list in reference order. ^[ref]

The two viewpoints answer different useful questions about the same object. An ordering tells us which object occupies each position; a bijection tells us where each label is sent and allows successive rearrangements through function composition. All permutations of $n$ labels form the symmetric group, whose subgroups are permutation groups. The counting viewpoint supplies $n!$ possibilities, a factorial; the mapping viewpoint reveals how rearrangements combine.

Composition convention. Apply the rightmost permutation first:For the displayed $\sigma =(1342)$ and the transposition $\tau =(12)$, direct evaluation givesFor instance, $(\sigma \tau )(1)=\sigma (2)=1$, but $(\tau \sigma )(1)=\tau (3)=3$. Thus function composition of permutations need not be commutative; the omitted labels in these permutation cycles are fixed points.

For a normal subgroup $K$ of $G$, each $c_h:k\mapsto h^{-1}kh$ is a group automorphism of $K$. Its inverse is $c_{h^{-1}}$, but the dependence on $h$ is a group antihomomorphism under ordinary function composition, because $(gh{)}^{-1}k(gh)=h^{-1}(g^{-1}kg)h$. The assignment $h\mapsto (k\mapsto hk{h}^{-1})$ instead is a group homomorphism to the automorphism group. Equivalently the first convention is a right group action, while the second is a left group action.

A ring is a set $R$ with two binary operations, addition and multiplication, satisfying three requirements. Under addition, $R$ is an abelian group: there is a zero, every element has an inverse element, and grouping or exchanging summands does not change the result. Multiplication is associative and has an identity element $1$, so $(ab)c=a(bc)$ and $1a=a1=a$. Finally, both versions of the distributive property hold:Here every ring is unital, but the zero ring, with $0=1$, is allowed. Commutativity of multiplication is an additional condition defining a commutative ring. These conventions agree with ^[ref].

The integers form a ring with their usual operations. The polynomial ring $\mathbb{Z}[X]$ is another: addition combines coefficients, while multiplication uses the distributive property. For example,The same rules justify symbolic calculations in both rings; this is why one definition can organize apparently different kinds of arithmetic. In every ring, $a0=0a=0$, and $a(-b)=-(ab)$. The first identity follows by distributing $a(0+0)$ and subtracting $a0$; the second follows by distributing $a(b+(-b))$. Thus familiar sign rules are consequences of the structure.

Order still matters in some rings. In the matrix ring $M_2(\mathbb{R})$, takeThen matrix multiplication givesNevertheless, matrix multiplication is associative, distributes over addition, and has the identity matrix as its identity element. This is a valid ring. On a column vector, $AB$ applies $B$ first and $A$ second: swapping coordinates before discarding the second coordinate differs from doing those actions in reverse. The failure of commutativity records a meaningful difference in function composition.

The sign homomorphism sends an even permutation to $1$ and an odd permutation to $-1$; its kernel is the alternating group.

A symmetric group is the group of all bijections from a set to itself, with function composition as its operation.

The group of Euclidean isometries preserving orientation of ${\mathbb{R}}^n$. Its elements have the form $x\mapsto Ax+b$, with $A$ in the special orthogonal group and $b\in {\mathbb{R}}^n$. The function composition law is $(A,b)(B,c)=(AB,Ac+b)$, the identity element is $(I,0)$, and the inverse element is $(A^{-1},-A^{-1}b)$. These formulas prove closure and inverses; function composition supplies associativity. For $n=2$, $A$ is a planar rotation.

A symmetry group collects bijections of an object to itself that preserve a specified structure in both directions, with function composition as the operation. For a geometric object one may require Euclidean distances to be preserved, giving an isometry group; for a graph, one preserves adjacency, giving a graph automorphism group. For an unstructured finite set, every permutation is allowed. The structure to be preserved is part of the definition.

For a square with its usual geometric structure, the symmetry group consists of four rotations and four reflections. These form the dihedral group of group order eight. The existing group action example shows how its eight elements move the vertices of a polygon; changing the object to its edges or a marked configuration changes the group action being studied.^[ref]

Specifying the preserved data makes it possible to test a proposed symmetry exactly. After the preserved data are declared, function composition, the identity map, and inverse maps automatically preserve them too. Symmetry transformations therefore form a group, and questions about equivalent configurations become questions about group orbits, stabilizer subgroups, and group homomorphisms. This supplies reusable mathematics for comparing many different kinds of objects.

A symmetry transformation is a bijection preserving the data that define the object's symmetry group. Its individual group elements are symmetry transformations; the group operation combines them by function composition.

For two coordinate charts in a topological atlas, the topological transition map is the homeomorphismBoth domains are open sets in Euclidean space. Function composition gives $g_{ij}=g_{ji}^{-1}$ and $g_{ki}=g_{kj}\circ g_{ji}$ wherever all three coordinate charts overlap. These identities express consistency of the coordinate descriptions; imposing smooth functions as the coordinate changes gives a smooth atlas.

A transformation monoid is a collection of self-maps of a fixed set $X$ that contains the identity function and is closed under function composition. The associative property comes from function composition. A monoid action describes transformations of a set that obey a monoid's multiplication and identity laws.