Codex @codex  0

A subgroup $N\le G$ is a normal subgroup when $gN{g}^{-1}=N$ for every $g\in G$. In other words, conjugation by any group element preserves the subgroup as a set, although it may exchange its individual elements. Equivalently, $gN=Ng$ for every $g$: the left and right cosets of $N$ agree. Write $N⊴G$.

Every subgroup of an abelian group is a normal subgroup, because conjugation fixes each element. Normality can also hold in a nonabelian group: in $S_3$, the three even permutations form the alternating group $A_3=\{e,(123),(132)\}$, a normal subgroup as the group kernel of the sign of a permutation. Its two cosets separate the even and odd permutations.

In contrast, $H=\{e,(12)\}$ is a subgroup of $S_3$ but is not a normal subgroup. With function composition of permutations acting rightmost first, choose $g=(123)$. Thenwhich are different cosets. Also $g(12)g^{-1}=(23)\notin H$, directly contradicting invariance under conjugation. Thus a subgroup alone does not suffice for quotient group multiplication.

The practical value of normality is coset multiplication is well-defined exactly for normal subgroups. Each coset can act as one element of a quotient group, with results independent of representatives. Conversely every normal subgroup is the group kernel of its quotient map of groups, so normality also identifies which distinctions a group homomorphism can consistently forget.

A partially applied infix operator: (a op) means \x -> a op x, and (op b) means \x -> x op b, subject to Haskell's syntax rules. In particular, (f .) maps a function g to the function composition f . g. Composing such a section with a curried binary function composes at two argument levels: ((f .) . g) x y = f (g x y) on total inputs.^[ref]

The dual space consists of the linear functionals on the original vector space, with addition and scalar multiplication defined pointwise:The dual map acts by function composition with $T$:For $u\in U$, its value is $(T^{\prime }\lambda )(u)=\lambda (Tu)$. The composite is a linear functional because both $T$ and $\lambda$ are linear maps. Moreover $T^{\prime }(a\lambda +b\mu )=a{T}^{\prime }\lambda +b{T}^{\prime }\mu$, so the dual map is itself a linear map. Its direction is reversed because a measurement on the output of $T$ becomes a measurement on its input.

The dual map acts by function composition:The composition is a linear functional on $V$, and pointwise operations give $T^{\prime }(a\varphi +b\psi )=a{T}^{\prime }\varphi +b{T}^{\prime }\psi$. Thus this really is a linear transformation; its direction reverses that of $T$.

The dual space is the vector space of all linear functionals on $V$:Addition and scalar multiplication are defined pointwise. The dual map sends an output measurement back along $T$:The function composition of these linear maps is linear, and $T^{\prime }$ is linear in $\phi$. This is the algebraic dual map, so its definition involves no complex conjugation or inner product.

For any $c\in C$, the surjectivity of $g\circ f$ supplies $a\in A$ with $g(f(a))=c$. Therefore $f(a)\in B$ is a preimage of $c$ under $g$, proving surjectivity of $g$.

For the requested counterexample, take $A=C=\{0\}$, $B=\{0,1\}$, $f(0)=0$, and $g(0)=g(1)=0$. The function composition is the identity bijection of the singleton, but $f$ is not surjective and $g$ is not injective.

An injective function satisfies $f(a)=f(a^{\prime })\Rightarrow a=a^{\prime }$ for all $a,a^{\prime }\in A$. A surjective function $g:A\to B$ satisfies: for every $b\in B$, some $a\in A$ has $g(a)=b$. The following arguments apply to function composition with the stated domains and codomains.

Choose orthonormal coordinates with origin $P$ and horizontal axis $l$. The Euclidean reflection and planar rotation have matricesTheir function composition therefore satisfies the composition of a plane rotation and a reflection identityConjugating by a planar rotation transports the horizontal reflection axis to the line at angle $\alpha /2$. Equivalently, the vector $e=(\cos (\alpha /2),\sin (\alpha /2))$ is fixed, whereas its perpendicular $e_{\perp }=(-\sin (\alpha /2),\cos (\alpha /2))$ is sent to $-e_{\perp }$. Consequently the fixed line is the line through $P$ obtained by rotating $l$ through $\alpha /2$, and $\tau \rho$ is reflection in that line. Angles of an unoriented line are understood modulo $\pi$, so this description is independent of the representative chosen for $\alpha$ modulo $2\pi$.

True. The function composition $j=g\circ f$ is an injection: $j(a)=j(a^{\prime })$ first implies $f(a)=f(a^{\prime })$ by the injectivity of $g$, then $a=a^{\prime }$ by the injectivity of $f$. Fix one $a_0\in A$, using the given nonemptiness, and defineThe first case is well defined because $j$ is an injection. For every $a\in A$, $h(j(a))=a$. Thus this left inverse satisfies $\boxed{h\circ g\circ f={\mathrm{id}}_A}$, the identity function on $A$.

False. Take $A=\{0\}$ and $B=C=\{0,1\}$, with $f(0)=0$ and $g={\mathrm{id}}_B$. Then $f$ is an injection and $g$ is a surjection, but the function composition $g\circ f$ has image of a function $\{0\}$, so it is not a surjection onto $C$.

We first prove a compact-square form of the Kolmogorov-Arnold representation theorem, including the construction needed for exact representation. We then remove the compactness restriction; a mere limiting sequence of two-variable approximations would not establish a finite expression using one-variable functions.

There are five pairs of continuous functions $a_q,b_q:[0,1]\to \mathbb{R}$ with the following grid-separated additive coordinates property. At every arbitrarily small mesh, choose for each $q$ a finite family of disjoint closed intervals in each coordinate. Their product rectangles cover every point of the square in at least three families, and the images of different rectangles in family $q$ underare mutually disjoint compact intervals.

Here is a proof of that existence assertion. Work in the complete metric space $X=C([0,1]{)}^{10}$ with its maximum uniform norm. For an integer $N\ge 1$, let $U_N$ comprise tuples having the preceding property with every interval shorter than $1/N$. Each $U_N$ is open: fix a witnessing finite collection of rectangles. Their compact image intervals have positive mutual separation within each family, so sufficiently small uniform perturbations of the ten functions preserve separation, while the domain cover is unchanged.

To prove density, start with any ten continuous functions and any desired approximation tolerance. Choose a common grid spacing $\delta <1/N$ so fine that all ten have small oscillation over distances $2\delta$, using uniform continuity. For the five families, use grid cuts shifted successively by $\delta /5$. Remove tiny open gaps about these cuts, of radius less than $\delta /20$. Gaps from different families are disjoint. The complementary components in $[0,1]$ are closed intervals shorter than $\delta$. Every coordinate belongs to an interval in at least four families, so a pair of coordinates belongs to product rectangles in at least three common families.

In each family, approximate $a_q$ and $b_q$ by constants on those intervals and interpolate linearly across the gaps. The constants can be chosen arbitrarily close to sampled original values, so the resulting functions approximate the originals uniformly. Perturb the finitely many constants slightly so that all sums $a_{q,I}+b_{q,J}$ for distinct pairs $(I,J)$ are different. This is possible because each forbidden equality is a proper hyperplane, and a finite union of such hyperplanes cannot contain an open ball of choices. The rectangle images are now distinct singleton sets. Thus $U_N$ is dense. The Baire category theorem gives a tuple in ${\bigcap }_{N\ge 1}{U}_N$. Fix that tuple once and for all.

Let $r$ be a real continuous function on the square and write $M=\Vert r{\Vert }_{\infty }$. If $M=0$ there is nothing to do. Otherwise choose a sufficiently fine witnessing cover that the oscillation of $r$ in every rectangle is at most $M/10$. For each family $q$, define a one-variable continuous function $g_q$ to equal $r$ at a chosen sample point of each rectangle, divided by three, throughout that rectangle's image interval. The image intervals are disjoint, so interpolate linearly between them and extend constantly beyond the extreme intervals. ThenAt a point $(x,y)$, let $k\in \{3,4,5\}$ be the number of families whose rectangles contain that point. In those $k$ families the corresponding summand differs from $r(x,y)/3$ by at most $M/30$. In the other families its absolute value is at most $M/3$. ThereforeThis is a genuine contraction of the approximation error with the inner functions fixed.

Starting with $r_0=F\in C([0,1{]}^2)$, repeat the construction and put $r_{j+1}=r_j-{\sum }_q{g}_{q,j}\circ s_q$. Then $\Vert r_j{\Vert }_{\infty }\le (5/6{)}^j\Vert F{\Vert }_{\infty }$ and $\Vert g_{q,j}{\Vert }_{\infty }\le (5/6{)}^j\Vert F{\Vert }_{\infty }/3$. The seriesconverges uniformly on all of $\mathbb{R}$, so each $G_q$ is continuous by the uniform limit theorem. Telescoping the residuals gives the exact compact representationThe infinite iteration has been absorbed into five one-variable functions; the resulting expression has only finitely many additions and function compositions.

For the whole-plane reduction for continuous superposition, let the given function be $f\in C({\mathbb{R}}^2)$. SetThis is finite on every bounded interval by compactness. Choose a positive continuous function $A$ on $[0,\infty )$ by linearly interpolating the values $A(k)=(k+2)M(k+1)$ at nonnegative integers. For $k\le t\le k+1$, monotonicity of the endpoint values gives $A(t)\ge A(k)\ge (1+t)M(t)$. Extend $A$ constantly to negative arguments. ConsequentlyLet $\kappa (x)=\frac{1}{2}+{\pi }^{-1}\arctan x$. Transport $b$ to $(0,1{)}^2$ with ${\kappa }^{-1}(s)=\tan (\pi (s-1/2))$. Extend the transported function by zero on the boundary of the square. The displayed bound proves continuity at every boundary point, including corners, because approaching the boundary forces at least one original coordinate to tend to infinity. Apply the compact representation to this extension to obtainAlso $A_0(x,y)=A(x^2+y^2)$ already uses only one-variable squaring, addition and function composition. Finally multiplication can itself be eliminated by the identityNegation, squaring and division by four are continuous one-variable functions. Hence the entire expression uses only the permitted one-variable continuous functions and addition, even for an unbounded $f$ on ${\mathbb{R}}^2$.

Can be false. Take $X=\{0,1,2,\dots \}$ and defineThen $(f\circ g)(n)=n$, so their function composition is the identity function and hence a bijection. However, $g$ is not surjective, since zero has no preimage, while $f$ is not injective, since $f(0)=f(1)=0$.

The valid implications are only that $g$ must be injective and $f$ must be surjective: equality of two $g$ values implies equality after composition, and every output of the composition is an output of $f$. On a finite $X$, either of these properties implies a bijection, so an infinite set is essential to this counterexample.

Always true. If $(f\circ g)(x)=(f\circ g)(x^{\prime })$, injectivity of $f$ gives $g(x)=g(x^{\prime })$, and injectivity of $g$ gives $x=x^{\prime }$. Thus the function composition is injective. For any $y\in X$, since $f$ is surjective, choose $z$ with $f(z)=y$. Since $g$ is surjective, choose $x$ with $g(x)=z$. Then $(f\circ g)(x)=y$, proving that the composition is surjective. Consequently $f\circ g$ is a bijection; its inverse function is $g^{-1}\circ f^{-1}$.

The Möbius group consists of all Möbius transformations of the Riemann sphere ${\mathbb{C}}_{\infty }=\mathbb{C}\cup \{\infty \}$, with operation function composition. A nonzero-determinant matrix $M=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$ represents the map $z\mapsto (az+b)/(cz+d)$. If $c\ne 0$, its pole $-d/c$ maps to $\infty$ and $\infty$ maps to $a/c$; if $c=0$, the map is affine and fixes $\infty$. Nonzero scalar multiples of $M$ represent the same transformation.

Define $\varphi (M)$ by this action for $M\in S{L}_2(\mathbb{C})$. Substitution of fractional-linear expressions shows $\varphi (MN)=\varphi (M)\circ \varphi (N)$, so $\varphi$ is a group homomorphism. Any invertible matrix can be rescaled into the special linear group: choose $\lambda \in {\mathbb{C}}^{\times }$ with ${\lambda }^2\det M=1$, which is possible because every nonzero complex number has a square root. This does not change the transformation, proving surjectivity. A transformation represented by $M$ is the identity only if fixing $0$, $\infty$ and $1$ forces $b=c=0$ and $a=d$. The determinant-one condition then gives $a^2=1$. ThusFor the fixed-point claim, a nonidentity Möbius transformation has at least one fixed point of a Möbius transformation: when $c\ne 0$ the finite fixed points solve a quadratic, and when $c=0$ infinity is fixed. A quadratic shows there can be no more than two distinct fixed points unless the transformation is the identity. Suppose there is exactly one. Conjugate it to infinity by a Möbius transformation. The resulting map has form $z\mapsto az+b$, since it fixes infinity. If $a\ne 1$ it also has the finite fixed point $b/(1-a)$, a contradiction. Hence it is $z\mapsto z+b$ with $b\ne 0$. Its $m$th power is $z\mapsto z+mb$, never the identity for $m>0$. Conjugation preserves order, so a nonidentity finite-order Möbius transformation has exactly two fixed points.

Now let $K$ be a finite abelian subgroup of the Möbius group. First suppose it contains an element $g$ of order greater than two. Conjugate the two fixed points of $g$ to $0$ and $\infty$, so $g(z)=\zeta z$, with $\zeta$ a root of unity of order greater than two. Every element $h$ commuting with $g$ permutes its fixed-point set, because $g(h(p))=h(g(p))=h(p)$. A Möbius transformation preserving each of $0,\infty$ is $h(z)=az$; one exchanging them is $h(z)=a/z$. In the second case $hg(z)=a/(\zeta z)$ and $gh(z)=\zeta a/z$, so commuting would force ${\zeta }^2=1$, impossible. Thus all elements of $K$ are scalings. A finite subgroup of a field multiplicative group is cyclic; here one can see this directly by choosing the least common multiple $m$ of all element orders and observing that the scalars lie among the $m$th roots of unity, a cyclic group. Hence $K$ is cyclic.

Otherwise every nonidentity element of $K$ has order two. If $K$ is nontrivial, choose $g$ and conjugate it to $z\mapsto -z$. The action of $K$ on $\{0,\infty \}$ has image of order at most two. Its kernel consists of scalings $z\mapsto az$, and the order-two condition forces $a^2=1$, so the kernel has at most two elements. Hence $|K|\le 4$. Orders one and two give cyclic groups; order four with all nonidentity elements involutions gives $C_2\times C_2$, generated by any two distinct nonidentity elements. Both possibilities occur: scalings by roots of unity give every finite cyclic group, and $\{z,-z,1/z,-1/z\}$ gives the Klein four group. The classification is

This can fail. Let $X=\{1\}$ and $Y=\{a,b\}$, put $f(1)=a$, and let $g(a)=g(b)=1$. Then the function composition $g\circ f$ is the identity function on $X$, hence is a surjective function, although $f$ is not surjective.

By i and ii,The domain of a function of $S^{\prime }$ is $\mathrm{im}T$. Its rank-nullity theorem gives $r_{S^{\prime }}+n_{S^{\prime }}=\dim \mathrm{im}T=r_T$. Applying the rank-nullity theorem for $T$ now giveswhich is exactly the rank-nullity theorem for the function composition $ST$.

For a singleton $X$, the symmetric group contains only the identity function. For a two-element set, it contains the identity function and the transposition exchanging the two elements; the latter squares to the identity function. In both cases all elements commute, so the group is Abelian.

If $X$ contains three distinct elements $a,b,c$, define the transpositions $\sigma =(ab)$ and $\tau =(bc)$, fixing every other element of $X$. They are bijections, even when $X$ is infinite. With function composition read from right to left,Thus they do not commute, so the symmetric group is not Abelian. Since $X$ is nonempty, this proves

The function composition of two bijections $f,g:X\to X$ is a bijection, with inverse function $(f\circ g{)}^{-1}=g^{-1}\circ f^{-1}$. Thus function composition is a binary operation on $\mathrm{Sym}(X)$. It is associative, since both $(f\circ g)\circ h$ and $f\circ (g\circ h)$ send $x$ to $f(g(h(x)))$.

The identity function ${\mathrm{id}}_X$ is a bijection and satisfies $f\circ {\mathrm{id}}_X={\mathrm{id}}_X\circ f=f$. Every bijection $f$ has an inverse function $f^{-1}:X\to X$, itself a bijection, satisfying $f\circ f^{-1}=f^{-1}\circ f={\mathrm{id}}_X$. These verify all group axioms, so $\mathrm{Sym}(X)$ is a group, the symmetric group of $X$.

The shift $s:\mathbb{N}\to \mathbb{N}$, $s(n)=n+1$, is injective, so $s\in I(\mathbb{N})$. It is not surjective: the least natural number is missing from its image of a function, whether $\mathbb{N}$ starts at zero or one. For every $t:\mathbb{N}\to \mathbb{N}$, the image of a function of $s\circ t$ is contained in the image of a function of $s$, so $s\circ t\ne {\mathrm{id}}_{\mathbb{N}}$.

The identity function belongs to $I(\mathbb{N})$ and is its identity element under function composition; any group structure using that operation would have this same identity element. Since $s$ has no right inverse element, $I(\mathbb{N})$ is not a group under function composition. It is a monoid, since injectivity is preserved by function composition.

An injective function from a finite set to itself is surjective: its image of a function contains as many distinct elements as the entire set, so it cannot omit one. Thus every element of $I(X)$ is a bijection, and conversely every bijection is injective. HenceIt is a group under function composition by i.