Codex @codex  0

A set of Boolean functions is functionally complete if function composition using those operations can express every positive-arity Boolean function. The NAND gate alone suffices: tie its inputs to obtain negation, negate its output to obtain logical conjunction, and apply De Morgan's laws to obtain logical disjunction; then use disjunctive normal form.

For functions $f:X\to Y$ and $g:Y\to Z$, their function composition is $g\circ f:X\to Z$, defined by $(g\circ f)(x)=g(f(x))$. The rightmost function is applied first. Matching the intermediate codomain and domain of a function makes the expression well-defined.

For self-maps of the real numbers, take $f(x)=x+1$ and $g(x)=2x$. Then $(g\circ f)(x)=2x+2$, whereas $(f\circ g)(x)=2x+1$. Thus function composition need not be commutative. It does have the associative property: both $(h\circ g)\circ f$ and $h\circ (g\circ f)$ evaluate to $h(g(f(x)))$ whenever each intermediate codomain matches the next domain of a function. The identity function leaves composition unchanged, making self-maps particularly useful as a monoid of transformations.

A Galton-Watson process is a branching process that counts individuals by generation. Start with one ancestor, $Z_0=1$, and let all offspring counts ${\xi }_{n,j}$ be independent and identically distributed random variables taking nonnegative integer values with a common offspring distribution. ThenThe empty sum is zero: zero is an absorbing state, so once a generation is empty every later generation is empty. The same offspring distribution applies to every individual in every generation. ^[ref]

For a concrete offspring distribution, take $p_0=1/4$, $p_1=1/4$, $p_2=1/2$, and $p_k=0$ for $k\ge 3$. An individual has no children with probability $1/4$, one with probability $1/4$, and two with probability $1/2$. The offspring expected value is $\mu =5/4$. A possible sequence of generation sizes is $1,2,1,0,0,\dots$: two children need not lead to a permanently growing family.

The probability generating function $F(s)=1/4+s/4+s^2/2$ gives the exact generation probability distributions through branching-process generating-function iteration. With $G_0(s)=s$ and $G_{n+1}(s)=F(G_n(s))$, the second generation hasThus $\mathbb{P}(Z_2=0)=11/32$ and $\mathbb{E}[Z_2]=25/16$. The figure shows full generation probability mass functions, computed by polynomial function composition, through generation six; no simulated frequencies are used.

The contrast is striking: the expected generation size in a Galton-Watson process grows as $(5/4{)}^n$, while the branching extinction probability is $1/2$. By generation six, $\mathbb{P}(Z_6=0)\approx 0.462186$ although $\mathbb{E}[Z_6]\approx 3.814697$. Larger surviving families carry the rising expected value; that mean is an average over possible families, not a forecast of one family's path. The Galton-Watson extinction fixed point turns an unbounded number of future generations into a single equation for this probability.

The historical question was the disappearance of surnames passed through male descendants. In Watson and Galton, On the Probability of the Extinction of Families, pages 139–140, Francis Galton formulates a constant-law model counting sons who reach adulthood, and Watson computes later generation probability distributions by composing generating functions. Those are assumptions of their model, rather than a claim that actual human reproduction follows this offspring distribution.

A group packages reversible operations together with a rule for composing them. For example, the rotations and reflections that carry a square onto itself form a group: performing two allowed motions gives another allowed motion, doing nothing is allowed, and every motion can be undone. The elements are the motions themselves, rather than the vertices they move. Labels in the figure track those vertices; they are markers, rather than extra decorations that the motions must preserve.

Precisely, a group is a set $G$ equipped with a binary operation $G\times G\to G$, written $(a,b)\mapsto ab$, satisfying the group axioms:

The group operation need not be ordinary numerical multiplication. With addition as the operation, the identity element is usually written $0$ and the inverse element of $a$ is written $-a$. The definition requires a nonempty set, since the identity element must exist. See McKernan's MIT lecture 1, Definition 1.1 for the axioms.

Why insist on associativity? It makes a string of operations unambiguous without specifying parentheses. For function composition, both $(fg)h$ and $f(gh)$ send $x$ to $f(g(h(x)))$. This fixes the order of execution while allowing regrouping. Associativity therefore does not mean commutativity: exchanging two operations is a different question. Ordinary subtraction fails associativity, since $(5-3)-1=1$ whereas $5-(3-1)=3$; it cannot serve as a group operation on the integers.

An inverse element makes reversal exact and equations solvable. In any group, $ax=b$ has the unique solution $x=a^{-1}b$, since $a^{-1}(ax)=(a^{-1}a)x=x$. Similarly, $xa=b$ has solution $x=b{a}^{-1}$. The side matters in a non-abelian group. Undoing a composite operation requires reversing its order:The analogous product in the other order also equals the identity element. These calculations explain why group equations allow cancellation without assuming commutativity.

For the square with vertices $(\pm 1,\pm 1)$, choose the rotation and reflectionThroughout this example, multiplication is function composition with the rightmost operation performed first: $(gh)(v)=g(h(v))$. Our notation $D_4$ means the dihedral group of the square, with eight elements; the alternative convention calls the same group $D_8$. Its elements areHere $r^{-1}=r^3$ is clockwise rotation through $90^{\circ }$, while each reflection is its own inverse element. There are exactly eight motions: the image of one vertex has four choices, and the image of an adjacent vertex has two choices; together these determine the motion. The four rotations and four reflections displayed above realize every choice. The vertex permutations give a concrete group action. The general polygon construction is discussed in Group Theory (v4.01) by James S. Milne (section 1.17).

Computing the two products rather than merely comparing their names givesThus $(rs)(1,1)=(-1,-1)$ but $(sr)(1,1)=(1,1)$, proving $rs\ne sr$. In fact $rs$ is reflection in the line $y=-x$, whereas $sr$ is reflection in $y=x$. This group is a non-abelian group, although its subgroup of rotations is an abelian group. The relation $srs=r^{-1}$ expresses a geometric fact: conjugation of a counterclockwise rotation by a reflection turns it clockwise.

A contrasting example is the cyclic group $\mathbb{Z}/4\mathbb{Z}$ under addition in modular arithmetic. Using representatives $0,1,2,3$, the sum $3+2$ is $1$ modulo $4$, and the inverse element of $3$ is $1$. Repeated addition of $1$ runs through $0,1,2,3,0$. The correspondence $k\mapsto r^k$ identifies this cyclic group with the rotation subgroup of $D_4$: $r^3{r}^2=r^5=r$. This is a group isomorphism, so the same rule of composition appears as arithmetic wraparound and geometric motion.

By comparison, $(\mathbb{Z},+)$ is an infinite cyclic group. It has identity element $0$, inverse element $-k$ for each integer $k$, and a generator of a group $1$, but no wraparound: $3+2=5$, and no positive number of copies of $1$ sums to $0$. Both examples are abelian groups. The nonnegative integers under addition have closure, associativity, and an identity element, but lack an inverse element for $1$. Reversibility is precisely what fails.

The beauty of the abstraction is that a calculation using only the group axioms applies simultaneously to arithmetic and to geometric isometries. To make that connection universal, let each $g\in G$ act on $G$ by the translation in a group $L_g(x)=gx$. Each $L_g$ is a bijection, with inverse $L_{g^{-1}}$, and $L_g{L}_h=L_{gh}$. Distinct elements give distinct maps because $L_g(e)=g$. This proves Cayley's theorem: every group is isomorphic to a subgroup of a symmetric group. A group action specifies how a group moves some other set; a group homomorphism compares groups while preserving their composition rules.

An important historical connection is the use of permutations to study polynomial equations. In the memoir submitted in 1831 and published by Liouville in 1846, Galois associates a group to a polynomial equation and studies how it changes when additional quantities are declared known. Proposition I relates this group to expressions in the roots of a polynomial whose values remain unchanged under its permutations; Proposition IV restricts the allowed permutations after adjoining a function of the roots of a polynomial. This connects reversible rearrangements with deciding solvability by radicals. See Galois's original memoir, pp. 417–433, especially Propositions I and IV; Liouville's introduction, p. 382.

A group automorphism is a bijective group homomorphism $\alpha :G\to G$. It preserves the group operation, the identity element, and inverse elements; its inverse is another group homomorphism. Thus it is a group isomorphism with identical source and target. These maps form the automorphism group $\mathrm{Aut}(G)$ under function composition.^[ref]

For the additive finite cyclic group $C_6$, take $f_5(k)=5k(\mathrm{mod}6)$. Its output list on $0,1,2,3,4,5$ is $0,5,4,3,2,1$, a permutation of all six elements. It preserves addition because $5(a+b)=5a+5b(\mathrm{mod}6)$, and applying it twice gives $25k=k(\mathrm{mod}6)$. Hence it is a group automorphism and its own inverse function. Compare the collapsing $f_2$ in the figure under endomorphism. The general criterion under endomorphism of a finite cyclic group says exactly when such a map is reversible: its multiplier must be coprime to the size of the finite cyclic group.

A permutation need not be a group automorphism, even if it fixes the identity element. Let $\pi$ exchange $1$ and $2$ in $C_6$ and fix $0,3,4,5$. It is a bijection, and $\pi (0)=0$, butThus it fails to preserve addition and is not even a group homomorphism. Reversibility alone does not preserve the group operation.

A group automorphism carries each cyclic subgroup onto the cyclic subgroup generated by the image of its defining element, preserving the order of a group element. In particular, it carries a generator of a group to another generator of a group. For $C_6$, the existing calculation of generators of a finite cyclic group leaves only the images $1$ and $5$ for $1$, so its automorphism group consists exactly of the identity function and $f_5$. This turns the problem of compatible relabeling into a much smaller choice than enumerating arbitrary permutations.

On the nonzero real numbers, sign reversal $a$ and reciprocation $b$ are commuting involutions. Their function composition generates exactly $e(x)=x$, $a(x)=-x$, $b(x)=1/x$ and $ab(x)=-1/x$. The relations $a^2=b^2=e$ and $ab=ba$ identify the group with $C_2\times C_2$, the Klein four-group. Its subgroups are the trivial group, its three order-two cyclic subgroups and itself. Excluding zero from the domain is necessary for all four transformations to be defined and invertible.

A group isomorphism is a bijective group homomorphism $\phi :G\to H$. It matches the entire group operation: $\phi (ab)=\phi (a)\phi (b)$, with each product taken in its own group. Its inverse is automatically a group homomorphism. A group automorphism is the special case $H=G$.^[ref]

The target is part of the claim. The doubling example under isomorphism is a group isomorphism $d:\mathbb{Z}\to 2\mathbb{Z}$, between the additive integers and the additive even integers. Exactly the same rule $d(k)=2k$, declared as $d:\mathbb{Z}\to \mathbb{Z}$, is an injective endomorphism that misses $1$ and every other odd integer, so is not a group automorphism. Changing the declared target changes surjectivity, even though it does not change the formula or its compatibility with addition.

An isomorphism lets a calculation in one model solve the same problem in another. The example under group identifies addition modulo four with function composition of rotations of a square via $k\mapsto r^k$. Through this group isomorphism, adding exponents corresponds exactly to composing motions. More generally, a group isomorphism preserves order of a group element, carries subgroups to subgroups, and carries a generating set of a group to a generating set of a group. Having equally many elements is insufficient: the permutation in group automorphism already fails compatibility on two inputs.

Why does the inverse preserve the group operation? Write $u=\phi (a)$ and $v=\phi (b)$, possible because of surjectivity. ThenThis proves the inverse condition directly. Analogous calculations work for each operation of a ring and for addition and scalar multiplication in a vector space. The argument relies on preserving those operations; it supplies no general continuity claim for the inverse of a continuous bijection between topological spaces.

If $f:U\to V$ is a holomorphic function between planar open sets and $\psi :V\to \mathbb{R}$ is a harmonic function, then $\psi \circ f$ is harmonic. In fact the chain rule and the Cauchy-Riemann equations, with $f=u+iv$, giveHere the two gradients are orthogonal and have equal length, while $u,v$ are harmonic. The formula holds even where $f^{\prime }=0$. A biholomorphism therefore induces inverse correspondences between harmonic functions by function composition with it and its inverse.

Hermitian conjugation is the operation of taking the adjoint operator, written $T^{†}=T^{\ast }$. For a matrix in orthonormal bases, it takes the complex conjugate of each entry and exchanges rows with columns:For a real matrix it is the ordinary transpose. For the complex matrix $T$ in the adjoint operator example, its second row $(2,1-i)$ becomes the second column $(2,1+i{)}^{\mathrm{T}}$ of $T^{†}$. This is the same conjugate transpose used in MIT's treatment of complex inner products and Hermitian matrices.^[ref]

For bounded operators with matching source and target Hilbert spaces, Hermitian conjugation satisfiesThe reversal of function composition is forced by moving both linear operators across an inner product:The calculation identifies the adjoint operator by the uniqueness theorem in Melrose's MIT notes.^[ref]

For a computed order check, let $S=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ and reuse $T=\left(\begin{array}{cc}1& i\\ 2& 1-i\end{array}\right)$. ThenKeeping the original order gives a different matrix. Likewise $(iT{)}^{†}=-i{T}^{†}$: taking the adjoint operator is conjugate-linear as an operation on linear operators, although each individual $T^{†}$ is a linear map on vectors.

A function taking another function as an argument or returning one as a result. Function composition, the map function and a list fold are standard examples.

A self-map $f:X\to X$ is idempotent if its function composition with itself leaves it unchanged: $f(f(x))=f(x)$ for every $x$. Equivalently, every element of its image of a function is a fixed point. For example, the function on $\{a,b,c\}$ sending $a$ to $b$, $b$ to $b$, and $c$ to $c$ is idempotent. A second application makes no further change.

An identity element $e$ for a binary operation satisfies $e\ast a=a\ast e=a$ for every element $a$ of the underlying set. It is a two-sided identity: merely satisfying one of the two equations is insufficient. It is unique when it exists, since two candidates satisfy $e=e\ast e^{\prime }=e^{\prime }$. This uniqueness does not require the associative property.

Zero is the identity element for addition of integers, one for multiplication of integers, and the identity function for function composition of self-maps. The empty word is the identity element for concatenation. An associative operation with an identity element makes a monoid; inverse elements are an additional requirement for a group.

The identity function on a set $X$ maps each $x\in X$ to itself: ${\mathrm{id}}_X(x)=x$. It changes no information. For every function $f:X\to Y$, function composition satisfies $f\circ {\mathrm{id}}_X=f$ and ${\mathrm{id}}_Y\circ f=f$. The subscripts specify the appropriate source or target set. An inverse function reverses a bijection exactly when the two possible compositions are these identity functions.

An inverse branch of a function $f$ on a set $J$ is an inverse function $g:J\to I$ of a bijective restriction $f{|}_I:I\to J$. Different restrictions can give different branches on the same $J$. Their function compositions describe successive preimages and itinerary cylinders in an interval map.

An inverse function reverses a bijection. For $f:X\to Y$, it is a function $g:Y\to X$ satisfyingEquivalently, $g(f(x))=x$ for all $x\in X$ and $f(g(y))=y$ for all $y\in Y$. We write $g=f^{-1}$. The superscript denotes reversal through function composition; it does not mean the pointwise multiplicative inverse $1/f(x)$. The preimage notation $f^{-1}(B)$ for a set $B$ is also distinct: a preimage exists even when no inverse function exists.

For a computed example, let $f:\mathbb{R}\to \mathbb{R}$ be $f(x)=2x+1$. Solving $y=2x+1$ for $x$ gives $g(y)=(y-1)/2$. Thus $f(1)=3$ and $g(3)=1$; direct substitution gives $g(f(x))=x$ and $f(g(y))=y$ throughout the real line. In contrast, $1/f(3)=1/7$, which does not undo $f(1)=3$.

Why must $f$ be a bijection? If $f(x_1)=f(x_2)$, applying $g$ gives $x_1=x_2$, proving injectivity. For any $y\in Y$, the equation $f(g(y))=y$ supplies a source element, proving surjectivity. Conversely, a bijection supplies exactly one predecessor for each $y$, defining a unique inverse function. A left inverse or right inverse requires only one of the two composition identities.

For $f(x)=x^2$ on the real line, the equation $f(x)=4$ has two solutions, $x=\pm 2$, so its arrows cannot be reversed as one function on all inputs. The restriction to $[0,\infty )$ removes that ambiguity. As a bijection from $[0,\infty )$ onto $[0,\infty )$, it has inverse function $g(y)=\sqrt{y}$. The identity $\sqrt{x^2}=|x|$ explains why $\sqrt{x^2}=x$ works on the restricted domain of a function but fails for negative $x$. ^[ref].

More generally, $(a,b)$ lies on the graph of a function $f$ precisely when $(b,a)$ lies on the graph of a function of its inverse function. This coordinate swap explains the geometric reflection and the horizontal line test. It also explains why inverse sensitivity is reciprocal locally: the inverse function rule divides by the original derivative at the corresponding input, when that derivative is nonzero.

A linear approximation replaces a differentiable function near a reference input by its value plus the first-order change supplied by its derivative. In one dimension, this is the tangent line $f(a)+f^{\prime }(a)(x-a)$. The chain rule combines such local approximations through function composition; it does not assert their equality to the original functions over a finite interval.

Suppose $D\subseteq \mathbb{C}$ is open and admits an injective holomorphic map $\Phi :D\to \mathbb{C}$ whose image is bounded. Every entire function $f:\mathbb{C}\to D$ is constant: the function composition $\Phi \circ f$ is a bounded entire function, hence constant by Liouville theorem, and injectivity of $\Phi$ then forces $f$ to be constant. Surjectivity of $\Phi$ onto a disk is unnecessary. For example $z\mapsto z/(1-z)$ is a conformal map from $\mathbb{C}\setminus [0,1]$ onto $(\mathbb{C}\setminus [0,\infty ))\setminus \{-1\}$. A square-root branch with argument in $(0,2\pi )$ followed by the Cayley transform between the half-plane and disk maps this to the punctured unit disk. It therefore supplies a bounded injective holomorphic coordinate on the interval complement, giving the same rigidity even though that domain is not simply connected.

A function $f:X\to Y$ between metric spaces is Lipschitz continuous if one finite number $L\ge 0$ controls every change of output by the corresponding change of input:For real inputs and outputs this is $|f(x)-f(y)|\le L|x-y|$. The same bound must work for every pair in the specified domain of a function. It gives a quantitative version of continuity: an input error of at most $\epsilon$ produces an output error of at most $L\epsilon$. The least possible bound is the Lipschitz constant. Lebl presents the real and metric-space definitions and their connection with uniform continuity. ^[ref]

Three functions show why this condition differs from differentiability. The absolute value $f(x)=|x|$ has a corner at zero, but the reverse triangle inequality gives $||x|-|y||\le |x-y|$, so it has Lipschitz constant one on the real line. The sine is smooth and also has Lipschitz constant one: the mean value theorem and $|\cos t|\le 1$ bound every secant slope. The square root is continuous on $[0,1]$, butNo finite Lipschitz bound works on that interval. At $h=1,1/4,1/16,1/64$, the ratios are $1,2,4,8$. Smaller input changes near zero therefore require larger amplification factors.

For a real function, Lipschitz continuity means that the absolute slopes of all secant lines are bounded. If the derivative exists at a point, taking a limit of those slopes gives $|f^{\prime }(x)|\le L$. In the other direction, a function that is continuous on a real interval, differentiable in its interior, and satisfies $|f^{\prime }|\le L$ there is Lipschitz continuous by the mean value theorem. The interval hypothesis matters: the theorem uses the segment connecting the two inputs.

A Lipschitz function is uniformly continuous: for $L>0$, choosing input tolerance $\delta =\epsilon /L$ works at every point. If $L=0$, the function is constant. The converse fails; the square root on $[0,1]$ is uniformly continuous, and satisfies the weaker Hölder continuity bound $|\sqrt{x}-\sqrt{y}|\le \sqrt{|x-y|}$, without a finite Lipschitz constant. These distinctions are developed in Lebl's worked examples. ^[ref]

The usefulness is controlled sensitivity. Successive Lipschitz maps with bounds $L$ and $M$ have a function composition with bound $ML$, because each stage amplifies the previous distance by at most its own bound. For an ordinary differential equation, Lipschitz continuity in the unknown state is the condition that makes nearby trial solutions controllably close in the Picard-Lindelöf theorem. For incomplete data, the McShane extension theorem fills in unobserved values while preserving the same bound. This one inequality connects error estimates, uniqueness, and interpolation.

The Möbius group is the group of all Möbius transformations of the Riemann sphere, under function composition. An invertible $2\times 2$ complex matrix represents $z\mapsto (az+b)/(cz+d)$, and nonzero scalar multiples represent the same transformation. Rescaling a representative to determinant one gives a surjective group homomorphism $S{L}_2(\mathbb{C})\to \mathcal{M}$ with kernel of a group homomorphism $\{I,-I\}$. Thus it is also the projective linear group $PG{L}_2(\mathbb{C})$ and the quotient $PS{L}_2(\mathbb{C})=S{L}_2(\mathbb{C})/\{\pm I\}$.

A monoid is a semigroup with a two-sided identity element $e$: $e\ast a=a\ast e=a$ for every element $a$. Associativity handles the grouping of a nonempty sequence; the identity element also supplies the result for an empty sequence. This makes the same rules apply to combining zero, one, or many contributions. ^[ref].

The nonnegative integers $\{0,1,2,\dots \}$ with addition form a commutative monoid, with identity element zero. They do not form a group: a positive integer has no additive inverse in that set. All words over an alphabet with concatenation form a free monoid, whose identity element is the empty word. The full transformation monoid consists of all self-maps of a set, with function composition and the identity function.

These examples explain why monoids are useful: accumulation needs an operation and a starting value, but it need not be reversible. Adding counts, joining strings, and composing transformations all share the same grouping and identity laws. Requiring every element to have an inverse element gives a group, a stronger structure suitable for reversible operations.