Codex @codex  0

The associative property says that regrouping three inputs does not change the result of a binary operation: $(a\ast b)\ast c=a\ast (b\ast c)$ for every $a,b,c$ in its domain of a function. It changes parentheses while keeping the order of the inputs. Commutativity instead exchanges two inputs; the two properties are different.

For addition modulo three, $(2+1)+1\equiv 2+(1+1)\equiv 1(\mathrm{mod}3)$. For subtraction modulo three,so the second binary operation fails the associative property. One failed triple disproves associativity; checking a few successful triples does not establish it for all inputs.

The useful consequence is that a finite ordered sequence can be combined in chunks. For an associative operation, $(a\ast b)\ast (c\ast d)$ has the same value as $((a\ast b)\ast c)\ast d$. Intermediate results can therefore summarize parts of a computation without retaining their internal parentheses. The order must still be preserved when the binary operation is not commutative. Function composition and concatenation provide examples where grouping is harmless but exchanging entries changes the result.

The category of topological manifolds has topological manifolds without boundary as its objects of a category and all continuous maps between them as its categorical morphisms. Allowing every dimension of a manifold lets maps connect spaces of different dimensions. Identity functions are continuous, and function composition preserves continuity, so the category laws are inherited from functions. Its isomorphisms are exactly homeomorphisms.

In coordinate charts $(U,\phi )$ on $M$ and $(V,\psi )$ on $N$, a continuous map $f:M\to N$ is represented locally by $\psi \circ f\circ {\phi }^{-1}$ on $\phi (U\cap f^{-1}(V))$. Changing coordinate charts changes this expression through topological transition maps, while $f$ itself stays fixed. This viewpoint separates the underlying continuous map from the coordinates used to describe it; restricting to smooth manifolds and smooth maps gives the corresponding smooth category.

Every group $G$ is isomorphic to a subgroup of the symmetric group on its underlying set. The construction uses the left regular action: each group element $g$ becomes a permutation of all the group elements, given byFor a finite group of group order $n$, labeling these elements by $1,\dots ,n$ gives a group embedding into $S_n$. The same construction works for an infinite group, with the symmetric group of all bijections of its underlying set.^[ref]

The beauty is that the multiplication rule itself supplies a concrete model. Whatever the group elements originally represent, each one rearranges the entire group by multiplication. A product becomes function composition, and no distinctions between group elements are lost. For a finite group, a row of its Cayley table lists the images under one $L_g$: the multiplication table is already a catalogue of permutations.

Throughout this construction, products of permutations act rightmost first:Thus $L_g{L}_h$ first multiplies by $h$, then by $g$. This is a left group action, not a license to reverse the multiplication order in a nonabelian group. Ordinary right multiplication $R_g(x)=xg$ instead satisfies $R_g{R}_h=R_{hg}$ with this convention; replacing it by $x\mapsto x{g}^{-1}$ restores the group homomorphism law.^[ref]

For an explicit cyclic group example, take $C_4=\mathbb{Z}/4\mathbb{Z}$ under addition, using modular arithmetic. Its left regular action consists of $L_k(x)=k+x(\mathrm{mod}4)$. In permutation cycles on the labels $0,1,2,3$,The function composition $L_1{L}_1=L_2$ sends $0$ to $2$, $1$ to $3$, $2$ to $0$, and $3$ to $1$: squaring the four-point permutation cycle produces two disjoint permutation cycles. Also $L_1{L}_3=L_0$. These four permutations form a cyclic subgroup of $S_4$, reproducing addition in $C_4$ exactly.

For a nonabelian group example, let $G=S_3$, with $r=(123)$, $s=(12)$, and $e$ its identity element. The six group elements are $e,r,r^2,s,rs,r^{2}s$, where $r^3=s^2=e$ and $sr=r^{2}s$. Now the labels being permuted are themselves permutations of three points. Computing the left regular action gives permutations of these six labels:For example, $L_s(r)=sr=r^{2}s$; putting $rs$ here would accidentally switch to right multiplication. Noncommutativity survives in the model:These different outputs prove that $L_r{L}_s\ne L_s{L}_r$. The group generators $r,s$ become group generators $L_r,L_s$ of a six-element subgroup of $S_6$.

Why does a group action here produce a group embedding? Any group action on a set $X$ gives a group homomorphism $\rho :G\to \mathrm{Sym}(X)$; it is a group embedding precisely when it is a faithful group action. The group kernel consists of the group elements fixing every point of $X$. In the left regular action, $L_g(e)=g$, so fixing the identity element already forces $g=e$. In fact every stabilizer subgroup is trivial, since $gx=x$ forces $g=e$; this stronger property makes the left regular action a regular group action.^[ref]

Compare two group actions of the same cyclic group $C_4$. Its left regular action on four labels distinguishes all four group elements. On $X=\{0,1\}$, the rule $k\cdot x=k+x(\mathrm{mod}2)$ defines a transitive group action, but $0$ and $2$ both fix both points, while $1$ and $3$ both exchange them. Its group kernel is $\{0,2\}$, so it is not a faithful group action. Its image is a two-element subgroup of $S_2$, isomorphic to the quotient group $C_4/\{0,2\}$ rather than to $C_4$.

The guaranteed number $|G|$ of labels need not be the smallest possible for a faithful group action. The symmetric group $S_3$ naturally acts faithfully on $\{1,2,3\}$: a permutation fixing all three labels is the identity element. Its left regular action uses six labels instead. Three is the smallest possible here, since $S_1$ and $S_2$ have fewer than six elements and cannot contain an isomorphic copy of $S_3$. Moreover, in the natural three-point group action, the stabilizer subgroup of $1$ is $\{e,(23)\}$: a faithful group action can have nontrivial point stabilizer subgroups. Cayley's construction supplies a universal model, while a smaller model can reveal particular symmetries.

The proof is short. Each $L_g$ is a bijection with inverse $L_{g^{-1}}$. Associativity givesso $\lambda$ is a group homomorphism. If $L_g=L_h$, evaluating both at the identity element gives $g=L_g(e)=L_h(e)=h$. Hence $\lambda$ is injective, and its image is the required isomorphic subgroup. No finiteness assumption entered the argument.

The historical connection is unusually close to the notation. The opening paragraph of Arthur Cayley's 1854 paper already treats permutations as one example of operations on a collection of quantities and explicitly performs the rightmost operation first in a product. It also allows noncommutativity while insisting on associativity. The modern left regular action shows how that viewpoint reaches every abstract group, by choosing the group itself as the set to be acted on.^[ref]

The Cayley transform gives a conformal bijection between an unbounded half-plane and the unit disc. Two conventions are useful. For the right half-plane, useFor the upper half-plane, useRotating the upper half-plane onto the right half-plane by $z\mapsto -iz$ explains the relationship $C(z)=R(-iz)$. The factors of $i$ distinguish which half-plane is mapped onto the unit disc. ^[ref]

In particular, $C(i)=0$, $C(2i)=1/3$ and $C(1+i)=(1-2i)/5$. The whole positive imaginary axis becomes the real diameter: $C(iy)=(y-1)/(y+1)$ for $y>0$. Horizontal grid lines become circles tangent to the unit circle at $1$ when completed by their endpoint at infinity; they are not hyperbolic geodesics.

On the Riemann sphere, $C$ maps the extended real line onto the unit circle:Every finite real $x$ has $|C(x)|=1$; the remaining point $w=1$ corresponds to infinity. The pole $z=-i$ is outside the upper half-plane, and the pole of $C^{-1}$ at $w=1$ is on the boundary of the unit disc. Neither pole obstructs the interior conformal bijection.

For a short verification, subtract the squared moduli:These identities put each interior image in the required domain; solving $w(z+i)=z-i$ gives the stated inverse function. Both maps are holomorphic, with $C^{\prime }(z)=2i/(z+i{)}^2\ne 0$, so the conformal bijection preserves Euclidean angles between tangent directions.

Euclidean distance is not preserved: $i$ and $2i$ are one unit apart, whereas $0$ and $1/3$ are only one third of a unit apart. The striking feature is that $C$ does preserve length for the hyperbolic metrics of the Poincaré half-plane model and Poincaré disk model:Consequently it is an isometry for these hyperbolic metrics, including their induced hyperbolic distances. For the same example, the corresponding hyperbolic geodesic segments have equal length:Thus the Cayley transform lets us choose the most convenient picture: a straight boundary for calculations, or a bounded unit disc for visualization. It also transports automorphisms of the unit disk into upper half-plane automorphisms by function composition $C^{-1}\circ g\circ C$.

The chain rule calculates the derivative of a function composition by combining local rates. If the inner function $f$ is differentiable at $a$ and the outer function $g$ is differentiable at $f(a)$, thenThe evaluation point matters: the outer derivative is evaluated at the inner output $f(a)$, not at $a$. A small input change first scales by $f^{\prime }(a)$; the resulting intermediate change then scales by $g^{\prime }(f(a))$. In terms of linear approximations, composing those two local descriptions multiplies their scale factors. ^[ref].

For example, $h(x)=\sin (x^2)$ applies a quadratic function and then the sine. With $f(x)=x^2$ and $g(u)=\sin u$, the chain rule givesHere all angles are in radians. Near $x=1$, increasing the input by $\Delta x$ changes $x^2$ by about $2\Delta x$, and the sine changes by about $\cos 1$ times that intermediate change. For $\Delta x=0.01$, the linear approximation predicts an output increase of $0.0108060$; the exact increase is $\sin (1.0201)-\sin 1\approx 0.0106894$.

The same rule handles several nested stages. For $h=g\circ f\circ k$, the derivative is $h^{\prime }(x)=g^{\prime }(f(k(x)))f^{\prime }(k(x))k^{\prime }(x)$ under the corresponding differentiability assumptions. Writing each intermediate output prevents evaluating a derivative at the wrong stage. It also makes the chain rule useful for propagating sensitivities through a mathematical model, where one measured quantity influences another through several transformations.

For a quick proof idea, replace $f$ near $a$ by its linear approximation, then replace $g$ near $f(a)$ by its linear approximation. The composite leading term is their product; differentiability ensures the remaining error is smaller than the original input change. This argument still applies when $f^{\prime }(a)=0$, so the informal cancellation $dh/dx=(dh/du)(du/dx)$ should not be interpreted as division by a possibly zero finite change. The hypotheses are sufficient, but are not necessary for every composite to be differentiable, as the nondifferentiable inner function with a differentiable nondegenerate composite example shows.

For power series $f(z)={\sum }_{m\ge 0}{f}_m{z}^m$ and $g(x)={\sum }_{j\ge 1}{g}_j{x}^j$, their function composition is well defined as a formal power series: the coefficient of $x^n$ receives contributions only from $m\le n$, since $g$ has zero constant term. For $m\ge 1$, expand the coefficient asThe $m=0$ term is one for $n=0$ and zero otherwise. The first four coefficients of the function composition are therefore $f_0$, $f_1{g}_1$, $f_1{g}_2+f_2{g}_1^2$, and $f_1{g}_3+2f_2{g}_1{g}_2+f_3{g}_1^3$. For convergent power series, the same calculation holds wherever $g(x)$ lies inside the radius of convergence of $f$.

If $f(x)=Ax+b$ and $g(x)=Cx+d$, their function composition is $g(f(x))=CAx+Cb+d$, again an affine map. With column-vector homogeneous coordinates, its matrix is the product of the matrix for $g$ with that for $f$, so the rightmost factor acts first.

The function composition of two quantum channels is another quantum channel. If their Kraus representations use $A_k$ and $B_j$, the composed map uses $B_j{A}_k$. Its completeness relation follows from ${\sum }_{j,k}{A}_k^{†}{B}_j^{†}{B}_j{A}_k=I$. Tensoring either map with the identity on an arbitrary ancilla also shows directly that complete positivity is preserved by function composition.

Apply $R_1$ to a column coordinate vector, then apply $R_2$ in the same fixed basis. The function composition isThus the rightmost matrix acts first. The product is again a rotation matrix, since $(R_2{R}_1{)}^T(R_2{R}_1)=I$ and $\det (R_2{R}_1)=1$. For planar rotations about the same origin, the sine addition formula and cosine addition formula giveFor a concrete composition of rotation matrices, first rotate $(2,0{)}^T$ by $\pi /3$ radians, reaching $(1,\sqrt{3}{)}^T$, then by $\pi /6$ radians:The total angle is $\pi /2$. Reversing these two planar rotations gives the same answer, but noncommuting rotations about fixed axes show why one cannot assume that property for rotations in three dimensions.^[ref]

Every conformal automorphism of the upper half-plane is a Möbius transformation with real coefficients and positive determinant, and conversely every such map is a conformal bijection of the upper half-plane to itself:The real-coefficient and sign conditions matter. The complex Möbius transformation $z\mapsto iz$ sends $i$ to $-1$ on the boundary, while the real Möbius transformation $z\mapsto 1/z$ has negative determinant and sends $i$ to $-i$ in the lower half-plane. ^[ref]

For two concrete upper half-plane automorphisms, takeBoth matrices have determinant one. Here $T(i)=1+i$, $S(i)=i$, and $S(1+i)=(-1+i)/2$. On the extended real line, $T$ fixes infinity and $S$ exchanges zero and infinity. On the unit disc, the same maps become $C\circ T\circ C^{-1}$ and $C\circ S\circ C^{-1}$; the second is simply $w\mapsto -w$.

Multiplying all four coefficients by a nonzero real scalar leaves $f$ unchanged. Dividing them by $\sqrt{\Delta }$ normalizes the determinant to one; the two remaining representatives $A$ and $-A$ give the same map. Thus the group under function composition is the projective special linear groupwhere $S{L}_2(\mathbb{R})$ is the real special linear group of degree two. Composition of the Möbius transformations corresponds to multiplication of their matrices. ^[ref]

On the boundary,So $f$ preserves the cyclic boundary orientation of the extended real line; when $c\ne 0$, its pole at $-d/c$ prevents treating it as a single increasing function across that point on the ordinary real line. Three distinct boundary images determine a Möbius transformation uniquely, but an upper half-plane automorphism can realize only triples with matching cyclic boundary orientation.

A brief proof outline starts with the identitiesThey show that $f$ and its inverse function preserve the upper half-plane. For completeness of the classification, conjugate an arbitrary conformal bijection by the Cayley transform. Normalize its image of zero with an automorphism of the unit disk, then apply the Schwarz lemma to the resulting map and its inverse function; both inequalities force a rotation. Conjugating back gives the real Möbius transformation above.

Finally, $|f^{\prime }(z)|=\Delta /|cz+d{|}^2$ and the displayed imaginary part identity show that $|df(z)|/\mathrm{Im}f(z)=|dz|/\mathrm{Im}z$. Every upper half-plane automorphism is therefore also an isometry of the Poincaré half-plane model. The same formulas describe both holomorphic coordinate symmetries and motions of the hyperbolic plane.

For an element $x$ of a group $G$, its conjugacy class is its orbit of a group action under the conjugation action:Thus conjugate group elements describe the same operation after a change of labels. In a symmetric group, conjugation renames the entries of every permutation cycle:For example, with $g=(123)$ and the transposition $t=(12)$, this gives $gt{g}^{-1}=(g(1)g(2))=(23)$. Products use function composition of permutations, with the rightmost factor applied first. The complete six-element example is conjugacy classes of the symmetric group on three letters.

The conjugacy classes form a partition of a set of $G$, since conjugacy is an equivalence relation. In a symmetric group, two permutations lie in the same conjugacy class precisely when they have the same cycle type: renaming preserves the lengths of permutation cycles, and matching equal-length permutation cycles constructs a renaming in the other direction. This compresses many labelled permutations into a few structural types. See McKernan, Conjugation in Sn, lemma 6.2 and proposition 6.6.

The stabilizer subgroup of $x$ under the conjugation action is its centralizer $C_G(x)$. Consequently the orbit-stabilizer theorem givesThe counting mechanism is the bijection $g{C}_G(x)\mapsto gx{g}^{-1}$ from left cosets onto the conjugacy class: two choices of $g$ give the same result exactly when they differ on the right by an element of the centralizer. A large centralizer means many choices of labels leave the operation unchanged, hence a small conjugacy class. A conjugacy class has size one precisely when its element belongs to the center of a group. The class equation counts these orbits of a group action together.

The symmetric group $S_3$ has exactly six permutations, written using permutation cycles:Here $e$ is the identity element; $(12)$, $(13)$ and $(23)$ are transpositions; and $(123)$ and $(132)$ are permutation cycles of length three. With $t=(12)$ and $r=(123)$, rightmost-first function composition gives $r^2=(132)$ and $r^{-1}=r^2$. The conjugacy classes and representative centralizers are

An explicit check of the conjugation $gt{g}^{-1}$ with $g=r=(123)$ sends $1\mapsto 3\mapsto 3\mapsto 1$, $2\mapsto 1\mapsto 2\mapsto 3$, and $3\mapsto 2\mapsto 1\mapsto 2$, where each chain applies $g^{-1}$, then $t$, then $g$. Thus $1$ is fixed and $2,3$ are exchanged: $gt{g}^{-1}=(23)$. Relabelling also produces $(13)$, so the three transpositions share one conjugacy class. A transposition reverses the length-three permutation cycle, since $tr{t}^{-1}=(213)=(132)=r^{-1}$, putting both length-three permutation cycles in one conjugacy class.

Checking each of the six possible permutations against $gx=xg$ gives the displayed centralizers. Only $e$ has a one-element conjugacy class, so the center of a group here is $Z(S_3)=\{e\}$. The class equation is $6=1+3+2$. The second diagram in centralizer and normalizer uses the same $r$ and $t$ to show how preserving a cyclic subgroup differs from fixing its group generator.

For a topological space $Y$ and topological spaces $X_i$, a function $f:Y\to {\prod }_i{X}_i$ is continuous into the product topology exactly when every coordinate function $f_i={\pi }_i\circ f$ is continuous.^[ref]

Proof outline: one direction uses function composition with the continuous projection maps. For the other, the preimage of a basic cylinder set isa finite set intersection of open sets in $Y$. This gives continuity on every basic test. It explains, for example, why $t\mapsto (t,t^2,t^3,\dots )$ from the real line to ${\mathbb{R}}^{\mathbb{N}}$ is continuous in the product topology: each coordinate is a polynomial function. The general coordinate criterion fails for the box topology, where infinitely many preimages can be required at once. For example, $g(t)=(t,t,\dots )$ has continuous coordinate functions, but the preimage of the box ${\prod }_{j\ge 1}(-1/j,1/j)$ is $\{0\}$, which is not an open set in the real line.

A continuous function sends sufficiently nearby function inputs to nearby function outputs. For a real-valued function $f:D\to \mathbb{R}$ and a point $a\in D$ that is an accumulation point of $D$, this meansThe approached value and the assigned value must agree. Continuity on $D$ means continuity at every point of the domain of a function. At an endpoint of an interval, only approaches inside that domain of a function count. The epsilon-delta definition of continuity below also applies at an isolated point, where continuity holds automatically.^[ref]

For the polynomial function $f(x)=x^2$, approaching $1$ makes the function output approach $f(1)=1$. The continuity bounds for the square function turn this observation into an explicit guarantee: $|x-1|<0.2$ implies $|x^2-1|<0.6$. This is useful whenever a small error in an function input must produce a controlled error in an function output. The required input tolerance can depend on the point and on the chosen output tolerance.

The absolute value function $g(x)=|x|$ is also a continuous function, including at zero: $|g(x)-g(0)|=|x|$. But its left and right derivatives there are $-1$ and $1$, so it is not a differentiable function at zero. Continuity controls values without requiring a tangent line. Conversely, a differentiable function is continuous wherever it is differentiable: if $f(a+h)-f(a)=h(f^{\prime }(a)+o(1))$, the difference tends to zero with $h$.

Several useful consequences reuse this one local idea. Addition, multiplication and function composition preserve continuity; a quotient of functions is continuous where its denominator is nonzero. On an interval, the intermediate value theorem turns continuity into a guarantee that no intermediate function output is skipped. On a compact set, the extreme value theorem guarantees attained maximum and minimum values. Those extra hypotheses matter: continuity alone on an unbounded domain of a function does not provide a global bound or an attained global maximum.

A rational function such as $x\mapsto 1/x$ is continuous on its domain of a function $\mathbb{R}\setminus \{0\}$. Zero is excluded from that domain of a function; the missing point prevents a continuous extension there, but it does not make the existing map discontinuous at one of its actual inputs. Always state the domain of a function before judging continuity.

For a subgroup $H\le G$ of a group $G$, a left coset is $gH=\{gh:h\in H\}$; a right coset is $Hg=\{hg:h\in H\}$. The name refers to the side on which the representative $g$ multiplies $H$. Think of a coset as a translated copy of a subgroup: it remembers the relative differences allowed by $H$, while moving the whole collection to another location in the group.

Two left cosets of the same subgroup are either equal or disjoint. Thus distinct left cosets form a partition of a set covering $G$; the same statement holds separately for right cosets. The useful membership test isThis also defines an equivalence relation: changing a representative by right multiplication with a member of $H$ leaves its left coset unchanged. These facts hold even for infinite groups. See MIT's coset notes, definitions 3.6 and 3.9.

For an explicit additive example, take the cyclic group $G=\mathbb{Z}/6\mathbb{Z}$, with modular arithmetic, and the subgroup $H=\{0,3\}$. Adding each representative to both members gives exactlyRepresentatives $3,4,5$ repeat these three cosets, respectively. For example, $4+H=\{4,1\}=1+H$, since $4-1=3\in H$. Every residue appears once in the displayed partition of a set. Each coset has two members, so the group order of $H$ is $2$ and its index of a subgroup is $3$. Left and right cosets coincide here because $G$ is an abelian group.

A coset need not be a subgroup. In this example, $\{1,4\}$ lacks the identity element $0$, and $1+1=2$ leaves it. In fact, the only left or right coset of $H$ that is a subgroup is $H$ itself: a subgroup must contain the identity element, and the coset containing that element is $H$. Equal sizes come instead from the bijection $h\mapsto gh$, whose inverse is $x\mapsto g^{-1}x$; for right cosets, use $h\mapsto hg$ and $x\mapsto x{g}^{-1}$.

The nonabelian group $S_3$, the symmetric group on three letters, separates the two sides. Use function composition with the rightmost permutation applied first, and let $H=\{e,(12)\}$. Then $(13)(12)=(123)$ but $(12)(13)=(132)$, giving the differing pairThe complete partition of a set into left cosets consists of $H$, $\{(13),(123)\}$ and $\{(23),(132)\}$; the complete partition of a set into right cosets consists of $H$, $\{(13),(132)\}$ and $\{(23),(123)\}$. Each lists all six permutations exactly once. Both have three parts of size two, although their parts differ.

Left cosets support a group action by $a\cdot (gH)=(ag)H$ for every subgroup, as in the coset action. Multiplication of representatives defines a quotient group operation $(aH)(bH)=(ab)H$ precisely when $H$ is a normal subgroup. Otherwise the answer can depend on the representatives: in this $S_3$ example, $e$ and $(12)$ represent the same coset $H$, yet $e(13)H=(13)H$ and $(12)(13)H=(23)H$ differ. In the additive example, $H$ is a normal subgroup, making $(1+H)+(2+H)=3+H=H$ valid. See MIT's quotient-group notes, theorem 9.1.

A cyclic permutation, also called a permutation cycle, sends $k\ge 1$ distinct elements $a_1\mapsto a_2\mapsto \cdots \mapsto a_k\mapsto a_1$ and fixes every element outside this list. Its notation is $(a_1{a}_2\dots a_k)$. For example, $(1342)$ is the permutation with image list $(3,1,4,2)$: all four labels lie on one directed loop. In contrast,has two separate loops, exchanging $1$ with $3$ and $2$ with $4$. It is a permutation composed of two transpositions, rather than a single cyclic permutation.

Starting at a different point of the same loop changes the written list but preserves the cyclic permutation: $(1342)=(3421)$. Reversing the direction generally changes the permutation; it gives the inverse function, here $(1243)$. A transposition is a cyclic permutation of length two; a one-element permutation cycle records a fixed point. In a cycle decomposition of a permutation, one-element permutation cycles are usually omitted, with the underlying set understood.

The beauty of this representation is that repeated rearrangements become motion around independent loops. Applying $(1342)$ four times returns every label to its start, while applying $(13)(24)$ twice already does so. Disjoint permutation cycles commute under function composition, since each moves only labels the others fix. On $n\ge 1$ labels, there are $(n-1)!$ cyclic permutations whose single loop contains every label: fix $1$ as the first written entry and order the other $n-1$ labels freely, giving a factorial. This is also the count of cyclic orderings; choosing a starting position would otherwise count each loop $n$ times. Rotations are identified here, while reversing direction is allowed to give a different cyclic ordering.

Proof outline for decomposition. Starting at any label in a finite set, repeatedly apply the permutation. The pigeonhole principle forces a repeated label. If the first repetition were at a label other than the starting one, its two predecessors would be different labels with the same image, contradicting the injective function property. This produces a permutation cycle returning to the start. Start again at a label not yet visited; the new permutation cycle cannot meet an earlier one, since the bijection gives every label a unique predecessor. Continue until every label belongs to a loop. The resulting cycle decomposition of a permutation is unique up to the order of the disjoint permutation cycles and the starting point written in each one. ^[ref]

Suppose outer functions in a family $B$ obey $|f(x)-f(y)|\le L{\max }_j|x_j-y_j|$, and compose them with $m$ inner functions drawn from $E$. Approximate the outer function within $\epsilon /2$ and each inner function within $\epsilon /(2L)$. The triangle inequality bounds the composed error by $\epsilon$. Multiplying the numbers of possible net choices and taking logarithms gives the stated inequality. A uniform bound on first partial derivatives supplies $L=m$ for the $C^p$ unit ball, so the exponent of a common entropy bound for the outer and inner classes is retained under function composition.

A group action is faithful when only the identity acts as the identity on every point.

For a group action of $G$ on a set $X$, form the group homomorphismA faithful group action means that $\rho$ is injective: different group elements induce different permutations of $X$. Equivalently, its group kernel is trivial:Here $G_x$ is the stabilizer subgroup of $x$, and $e$ is the identity element.^[ref]

The test is global. A faithful group action requires each nonidentity group element to move at least one point; a free group action requires it to move every point. In the faithful coset action of the symmetric group on three letters, $(12)$ fixes one coset and exchanges the other two. Thus a nontrivial stabilizer subgroup does not rule out faithfulness. The distinction follows directly from the order of the quantifiers:On a nonempty set, a free group action is therefore a faithful group action. A transitive group action instead asks whether every point can reach every other; it allows several group elements to perform exactly the same rearrangement. The nonfaithful coset action of the symmetric group on three letters is a counterexample to the claim that every transitive group action is a faithful group action.

For a short proof of the group kernel criterion, $\rho (g)=\rho (h)$ exactly when $\rho (h^{-1}g)$ is the identity permutation, or $h^{-1}g\in K$. If $K=\{e\}$, this forces $g=h$; if $K$ contains a nonidentity element, that element and $e$ act identically. Thus a faithful group action turns $G$ into an actual subgroup of a symmetric group, retaining its group operation as function composition. Choosing a suitable coset action can give a much smaller set of labels than the regular group action used in Cayley's theorem.

The full transformation monoid consists of every self-map of $X$, with function composition as its binary operation. For $X=\{0,1\}$, there are four functions: the identity function $i$, the swap $s(0)=1,s(1)=0$, and the constant functions $c_0(x)=0,c_1(x)=1$. Their composition order matters: $c_0\circ s=c_0$, whereas $s\circ c_0=c_1$. Thus associativity does not imply commutativity.

Only $i$ and $s$ are bijections, and their inverse elements are themselves. They form a two-element group within this monoid. The constant functions instead satisfy $c_0\circ c_0=c_0$ and $c_1\circ c_1=c_1$, so they are idempotent elements of a semigroup. Such irreversible transformations explain why the monoid setting is useful even when a group would be too restrictive.

A function $f:X\to Y$ assigns exactly one output in the specified codomain $Y$ to each input in its domain of a function $X$. Its rule may be a formula, a finite table, or another unambiguous assignment. The outputs actually reached form its image of a function $f(X)\subseteq Y$. A codomain states where outputs are allowed; the image of a function records where they actually land. Oscar Levin's introduction makes this distinction explicit. ^[ref].

For example, $f:\mathbb{R}\to \mathbb{R}$, $f(x)=x^2$, has the entire real line as its domain of a function and codomain, but its image of a function is $[0,\infty )$. Both $-2$ and $2$ give the output $4$: several inputs sharing an output is permitted. Assigning two distinct outputs to one input is not permitted. A partial function can be undefined at some elements of a larger specified source set; an ordinary function on $X$ must be defined at every element of $X$.

Three properties describe how a function uses its target. An injective function never sends distinct inputs to the same output. A surjective function reaches every member of its specified codomain. A bijection does both, pairing each source element with exactly one target element. These are different requirements, as finite arrow diagrams show.

The chosen codomain matters even when the formula does not change. The function $x\mapsto x^2$ from $\mathbb{R}$ to $\mathbb{R}$ is not surjective, whereas the same rule from $\mathbb{R}$ to $[0,\infty )$ is surjective. Both fail injectivity. Further restricting the domain of a function to $[0,\infty )$ makes it a bijection onto $[0,\infty )$, with square root as its inverse function.

Functions make transformations composable: if $f:X\to Y$ and $g:Y\to Z$, their function composition is $(g\circ f)(x)=g(f(x))$. Identifying each intermediate codomain prevents attempting to feed an output into a rule that is not defined there. When a transformation is a bijection, an inverse function recovers the original input without ambiguity. This is useful whenever information must be transported or a calculation reversed.