Codex @codex  0

A critical point of a smooth map is an input; a critical value is an output reached from at least one such input. For the fold $F(x,y)=(x,y^2)$, all inputs $(a,0)$ are critical points of a smooth map, and all outputs $(a,0)$ are critical values. The identical coordinate pairs live in different copies of ${\mathbb{R}}^2$. To classify an output $(a,b)$, inspect its entire fiber of a function:For $b>0$ both inputs have matrix rank two, so the output is a regular value. For $b=0$ its input has matrix rank one, so the output is a critical value. For $b<0$ the fiber of a function is the empty set, and the output is a regular value despite being outside the image of a function.

In general, for a smooth map $f:X\to Y$, write $C_f$ for its set of critical points of a smooth map. Its set of critical values is $f(C_f)\subseteq Y$. Equivalently, $q\in Y$ is a critical value if some $p\in f^{-1}(q)$ has a differential that is not surjective. A regular value requires a surjective differential at every input in that fiber of a function. The universal condition holds vacuously for an empty fiber of a function: every output outside $f(X)$ is a regular value. These quantifiers are explicit in Loring W. Tu, An Introduction to Manifolds, Definition 8.22 and its two following remarks.

The distinction is useful when solving equations. For a smooth map $f:X^m\to Y^n$ between smooth manifolds without boundary and a regular value $q$ with nonempty fiber of a function, the regular level set theorem makes $f^{-1}(q)$ an embedded submanifold of dimension $m-n$, with tangent spaceThe implicit function theorem explains the freedom count: locally, $n$ independent equations fix $n$ coordinates and leave $m-n$ free. The rank-nullity theorem gives the same count for the displayed kernel of a linear map. See Eckhard Meinrenken, Differentiable Manifolds, Theorems 1.11 and 1.15 for the local projection description and its consequence for level sets.

For example, $H:{\mathbb{R}}^2\to \mathbb{R}$, $H(x,y)=x^2+y^2$, has gradient $(2x,2y)$ and just one critical point, the origin, with critical value zero. For $c>0$, its fiber of a function is the circle of radius $\sqrt{c}$, a one-dimensional embedded submanifold; negative $c$ are regular values with empty fibers. At $c=0$, the fiber of a function is a single point instead of a circle. A critical value does not force its fiber of a function to be nonsmooth: that singleton is itself a zero-dimensional embedded submanifold, but the regular dimension conclusion $2-1=1$ does not apply.

Nor does a single regular input certify a regular value. The scalar smooth function $h(t)=t^2(t-1)$ has $h^{-1}(0)=\{0,1\}$ and derivative $h^{\prime }(t)=3t^2-2t$. The input zero is a critical point, while the input one is regular because $h^{\prime }(1)=1$. Their shared output zero is nevertheless a critical value. Conversely, different critical points of a smooth map can share one critical value: $f(t)=(t^2-1{)}^2$ sends both critical inputs $-1$ and $1$ to zero. Counting inputs and counting critical outputs are different tasks.

Finally, for $G(t)=(t,t^2):\mathbb{R}\to {\mathbb{R}}^2$, every output on the parabola is a critical value, and every output off it is a regular value with empty fiber of a function. There is no nonempty regular fiber of a function here, so the negative expression $1-2$ never becomes a claimed manifold dimension. Both diagrams show exact mathematical examples, not measured data.

Define the head-count random variable $X:\Omega \to \{0,1,2\}$ byThe four elementary outcomes are inputs to this function; its three numerical values are outputs. Each fiber of a function collects all outcomes giving one value. Under the fair independent model, adding the masses in each fiber gives the probability mass functionConsequently the output values are not equally likely, although the inputs are. Using the reduced sample space $\{0,1,2\}$ with these masses gives the same head-count probability distribution; assigning $1/3$ to each value would describe a different model.

A question about a random variable's value becomes an event on the original sample space by taking an inverse image:For a real-valued random variable, this is an event whenever $D$ is a Borel set, by measurability. In this finite example every subset of $\{0,1,2\}$ is allowed. In particular,This is the same “at least one head” event counted above, expressed through an observable.^[ref]

Every event determined by $X$ is a union of complete fibers. There are $2^3=8$ such events, whereas the full power set of $\Omega$ has $2^4=16$. In particular, the first-head event $A=\{HH,HT\}$ is not determined by $X$: it contains $HT$ but excludes $TH$, although both give $X=1$. Choosing an observable makes calculations simpler precisely by forgetting distinctions; the useful choice is one that retains the distinctions the question needs.

For a surjective function $f:B\to A$ and a function $g:B\to C$, there is a unique function $h:A\to C$ with $g=h\circ f$ if and only if $g$ is constant on each fiber of a function of $f$. Define $h(a)$ to be the common value on $f^{-1}(a)$; it is well-defined and unique because that fiber is nonempty. This uniquely specified value requires no simultaneous arbitrary choices.

For a concrete example, restrict the codomain of the finite function above to its image of a function $I=\{0,1,2\}$, making $f:A\to I$ surjective. Define $g(a)=g(b)=5$, $g(c)=7$ and $g(d)=9$. Then $h(y)=2y+5$ on $I$ gives $g=h\circ f$: knowing the output of $f$ is enough to compute $g$. If instead $g(a)\ne g(b)$, no such $h$ can exist, because $h(f(a))=h(f(b))$ must be the same value.

The surjectivity assumption supplies uniqueness on the full target. If the original unused target value three were retained, the factorization would impose no condition on $h(3)$, and different extensions could agree on every actual input. Thus factorization through a surjection formalizes when a compressed description retains all information needed for a later calculation.

// Target: combinatorics.bigb

For a function $f:X\to Y$ and $y\in Y$, its fiber of a function over $y$ is the set of all inputs producing that one output:Here $f^{-1}(y)$ is shorthand for a preimage of a singleton set, rather than a claim that an inverse function exists. A fiber can contain several inputs or be empty. It describes exactly which distinctions the function forgets.

For the finite function under image and preimage of a function, the fibers over $0,1,2,3$ are $\{a,b\}$, $\{c\}$, $\{d\}$ and the empty set, respectively. The nonempty fibers form a partition of a set: they are disjoint sets whose union is the domain of a function. Every input belongs to the fiber over its unique output, and two fibers with distinct output labels cannot share an input. A function is injective exactly when every fiber has at most one member; it is surjective exactly when every member of its specified codomain has a nonempty fiber.

More generally, $f^{-1}(U)$ is the union of the fibers over all $y\in U$. The relation $x\sim x^{\prime }$ defined by $f(x)=f(x^{\prime })$ is an equivalence relation, and its equivalence classes are precisely the nonempty fibers. The resulting quotient set is naturally in bijection with the image of a function. This links an input partition to the output values actually reached, without choosing one representative from each class.

Fibers are useful when an output is known but the input is not uniquely determined. A solution set $g^{-1}(\{0\})$ is one fiber, and factorization through a surjection explains when another function depends only on the retained output. Quantum hidden subgroup problem algorithms use functions whose fibers are cosets, giving the same idea a structured form in group theory.

A function collision is a pair of distinct inputs $x\ne x^{\prime }$ with $f(x)=f(x^{\prime })$. An injective function has no collisions. For a two-to-one function every nonempty fiber has two elements and hence one unordered collision pair. Finding such a pair through an oracle is the task of quantum collision finding.

In the finite example under image and preimage of a function, the pair $\{a,b\}$ is a function collision: both inputs give zero. The function retains their shared output but loses the distinction between them. If a finite set has more inputs than the number of available outputs, the pigeonhole principle forces a function collision. Equal source and target cardinalities alone do not prevent one.

For a finite function, let $m_y$ be the cardinality of its fiber of a function over $y$. The number of unordered function collisions is ${\sum }_y\left(\genfrac{}{}{0ex}{}{m_y}{2}\right)$, because each pair must lie in one common fiber. The example's nonempty fiber sizes are $2,1,1$, giving exactly one collision pair.

The kernel of a linear map $T:V\to W$ is the vector subspace of inputs sent to zero. Linearity makes it a vector subspace: if $T(v)=T(w)=0$, then $T(av+bw)=0$ for all scalars $a,b$. A vector in the kernel represents a change that the map cannot detect, since $T(x+v)=T(x)$ for every input $x$.

For $T:{\mathbb{R}}^3\to {\mathbb{R}}^2$ given by $T(x,y,z)=(x+y,z)$, the zero-output equations are $x+y=0$ and $z=0$. ThusIncreasing the first input while decreasing the second by the same amount leaves the output unchanged. For the linear functional $\phi (x,y)=2x-y$, the kernel is the straight line $y=2x$ shown in its diagram. A linear map is injective exactly when its kernel is the zero vector subspace, because $T(v)=T(w)$ is equivalent to $T(v-w)=0$.

The kernel describes invisible changes, rather than all inputs that produce a specified nonzero output. If $T(x_0)=b$, the corresponding fiber of a function is the affine solution space of a linear equation $x_0+\ker T$. The difference of two inputs in that fiber belongs to the kernel; an input in that fiber need not. In particular, for $b\ne 0$ the fiber cannot be a vector subspace, since it does not contain the zero vector.^[ref]

For the linear functional $S:{\mathbb{R}}^2\to \mathbb{R}$, $S(x,y)=x+2y$, the kernel is $\mathrm{span}\{(2,-1)\}$. Each fiber $S^{-1}(\{c\})$ is the parallel straight line $(c,0)+\mathrm{span}\{(2,-1)\}$. The input vector space is two-dimensional, but the output is one scalar: a whole straight line of inputs collapses to one point of the output real line.

The nullity of a linear map $T:V\to W$ is $n(T)=\dim \ker T$, the dimension of its kernel. It counts independent input directions that can change without changing the output. For a finite-dimensional vector space $V$, the rank-nullity theorem givesFor an $m\times n$ matrix $A$ of matrix rank $r$, this is $n-r$, using the number of columns, not the number of rows. This dimension identity is ^[ref].

The nullity answers a practical question about a linear system: once one input is known to produce the requested output, how much freedom remains? If $T(x_0)=b$, its fiber of a function over $b$ isIndeed, $T(x)=T(x_0)$ exactly when $T(x-x_0)=0$. Thus every nonempty fiber is an affine subspace of dimension $n(T)$, with the same direction space as the kernel. The kernel itself is the fiber over zero. Outputs outside the image of a linear map have empty fibers; the nullity does not guarantee existence, and we assign no solution-space dimension to an empty fiber here.

In the diagram, $F:{\mathbb{R}}^2\to {\mathbb{R}}^2$ has matrix $\left(\begin{array}{cc}1& 1\\ 0& 0\end{array}\right)$, matrix rank one and nullity one. Its kernel has basis $(1,-1)$, and the full solution of $F(x,y)=(c,0)$ is $(x,y)=(c,0)+s(1,-1)$. One free scalar moves the solution along a straight line; the output $(c,1)$ is impossible.

The existing three-input example $T(x,y,z)=(x+y,z)$ instead has rank two and nullity one. Its image of a linear map is all of ${\mathbb{R}}^2$, andEvery output has a solution straight line. In contrast, $U(x,y,z)=(x+y,0)$ has rank one and nullity two, with kernel basis $(1,-1,0),(0,0,1)$. Its reachable output $(a,0)$ has the solution affine subspacea plane, while $(a,b)$ with $b\ne 0$ has no solution. These two linear maps have the same input and output dimensions but different freedom and reachability. Computing the kernel separates what an output determines from what an extra constraint would have to fix. For either example, a basis of the kernel gives one independent free scalar per basis vector, which is why nullity measures freedom rather than the number of solutions.

Let $x\in X$ and choose holomorphic coordinate charts centred at $x$ and $f(x)$. A nonconstant holomorphic map has a local expansion $w\circ f(z)=c{z}^m+O(z^{m+1})$, where $c\ne 0$ and $m\ge 1$. Taking a local holomorphic $m$th root of the nonvanishing factor and changing the source coordinate gives the exact local form $w=z^m$. The integeris the ramification index of a holomorphic map. A ramification point of a holomorphic map is a source point with ${\nu }_f(x)>1$, equivalently where its derivative vanishes; a branch value of a holomorphic map, also called a branch point here, is the image of such a point in $Y$. These are different sets, one in the source and one in the target.

Every fiber of a function is finite: locally it is the zero set of a nonzero holomorphic function, so its points are isolated, and compactness prevents infinitely many such zeros without an accumulation point. The same argument applied to the local derivatives makes the set of ramification points of a holomorphic map finite. The open mapping theorem and compactness show that $f(X)$ is both open and closed in the connected target $Y$, hence $f$ is surjective.

For any $y\in Y$, the degree of a holomorphic map isTo see independence of $y$, choose disjoint small coordinate charts about its finitely many preimages. The local form $z\mapsto z^{{\nu }_f(x)}$ shows that nearby values have ${\nu }_f(x)$ preimages counted with multiplicity in the corresponding chart. Compactness excludes additional preimages outside these charts for sufficiently nearby values: a sequence of such preimages would have a limit in $f^{-1}(y)$. The displayed sum is therefore locally constant, hence constant on connected $Y$. Away from branch values of a holomorphic map it is the ordinary number of preimages, and $f$ is a $d$-sheeted covering map there.

The Riemann-Hurwitz formula isor, in terms of the two genera,For its proof, choose a triangulation of a surface on $Y$ containing every branch value of a holomorphic map among its vertices. Every open edge and open face has $d$ lifts, since its interior avoids branch values of a holomorphic map. The lifted cells give a finite CW complex structure on $X$. If $V_Y,E_Y,F_Y$ are the target counts and $R={\sum }_x({\nu }_f(x)-1)$, the source counts areIndeed, at a target vertex the deficit from $d$ distinct preimages is precisely ${\sum }_{x\mapsto y}({\nu }_f(x)-1)$, and all nonzero contributions occur over vertices. Taking the alternating sum gives $\chi (X)=d(V_Y-E_Y+F_Y)-R$, as required. This is the Triangulation proof of the Riemann-Hurwitz formula.

Every nonidentity biholomorphism in the finite group $G$ has only finitely many fixed points, by the identity theorem on a Riemann surface and compactness. Because the group action is a faithful group action, the union of these finite sets does not exhaust $X$. A point outside this union has trivial stabilizer subgroup, so its group orbit has $|G|$ points by the orbit-stabilizer theorem. The generic fiber of a function of the projection is such an group orbit, givingMore precisely, put $H=G_x$ and $m=|H|$. Differentiation at $x$ gives a group homomorphism $H\to {\mathbb{C}}^{\times }$. It is injective: if a nonidentity finite-order germ had the form $h(z)=z+a_k{z}^k+O(z^{k+1})$ with $k\ge 2$ and $a_k\ne 0$, then its $q$th iterate would begin $z+q{a}_k{z}^k$, so no positive iterate could be the identity. A germ equal to the identity gives the identity on $X$ by the identity theorem on a Riemann surface. Thus $H$ is a cyclic group, with derivative image the $m$th roots of unity.

For completeness, an explicit local coordinate linearizing $H$ isIt has $w^{\prime }(x)=1$, and reindexing the sum gives $w(hp)=h^{\prime }(x)w(p)$. Therefore a coordinate on the local quotient space is $w^m$. Other translates of a sufficiently small neighbourhood of $x$ are disjoint unless their translating element lies in $H$, so this local quotient space is also a chart for $X/G$. The local cyclic quotient of a Riemann surface consequently gives

A left inverse of $f$ is a function $\ell :B\to A$ satisfying $\ell \circ f={\mathrm{id}}_A$. If such $\ell$ exists and $f(a)=f(a^{\prime })$, applying $\ell$ gives $a=a^{\prime }$, so $f$ is an injection. Conversely, suppose $f$ is an injection and fix $a_0\in A$, possible because $A$ is nonempty. DefineThe first value is unique by injectivity, and $\ell (f(a))=a$ for every $a$. ThusNo choice from a family of nonempty sets is needed here: each preimage in the first case is unique, and the second case uses one fixed element.

A right inverse is a function $r:B\to A$ with $f\circ r={\mathrm{id}}_B$. Its existence makes every $b$ the image of $r(b)$, proving that $f$ is a surjection. Conversely, if $f$ is a surjection, every fiber of a function $f^{-1}(\{b\})$ is nonempty. Using the usual axiom of choice for arbitrary sets, choose $r(b)\in f^{-1}(\{b\})$ for each $b$. Then $f(r(b))=b$, givingThe converse in this second equivalence is the right-inverse characterization of the axiom of choice; it is not an unrestricted choice-free theorem about arbitrary sets.

Choose a right inverse $s:A\to B$ of the surjection $f$, so $f(s(a))=a$, and defineFor each $a$, the element $b=s(a)$ then witnesses both $f(b)=a$ and $g(b)=h(a)$. As in part (a), arbitrary simultaneous choices use the axiom of choice. If $A$ is empty, surjectivity and the existence of $f:B\to A$ force $B$ to be empty, and the unique empty function $h:A\to C$ already meets the requirement.

Suppose $g$ is constant on each fiber of a function of $f$. Since every fiber is nonempty, $h(a)$ must be its common $g$-value: any witness $b$ in that fiber gives that value. This defines exactly one $h$ and yields $g=h\circ f$, an instance of factorization through a surjection.

Conversely, suppose a fiber contains $b,b^{\prime }$ with $f(b)=f(b^{\prime })=a_0$ but $g(b)\ne g(b^{\prime })$. Starting with any admissible $h$, define $h_1,h_2$ to agree with it away from $a_0$, but put $h_1(a_0)=g(b)$ and $h_2(a_0)=g(b^{\prime })$. Both remain admissible, witnessed at $a_0$ by $b$ and $b^{\prime }$ respectively, yet they are distinct. HenceThe distinction is important: the original existence property asks only for one witness in each fiber. Only when $g$ is fiberwise constant does that property force $g=h\circ f$ for every $b$.

For each $y\in Y$, surjectivity makes the fiber of a function $f^{-1}(\{y\})$ nonempty. Choose one element $x_y$ of each such fiber of a function and define $g(y)=x_y$. Then $f(g(y))=y$ for every $y$, proving $f\circ g=I_Y$. For arbitrary sets, the simultaneous selection invokes the usual axiom of choice; this is the right-inverse characterization of the axiom of choice. For finite $Y$ only finitely many choices are needed. If $Y$ is empty, the unique empty function gives the same conclusion.

For a function $f:X\to Y$ and a subset $U\subseteq Y$, its preimage isIt is a subset of the original domain of a function. The notation does not require an inverse function: the preimage of a singleton set can have no members, one member, or many members. In the finite example, $f^{-1}(\{0\})=\{a,b\}$, $f^{-1}(\{1\})=\{c\}$ and $f^{-1}(\{3\})=\varnothing$. The preimage of a singleton set is also its fiber of a function.

For subsets $U,V\subseteq Y$, preimages preserve both unions and intersections:For the intersection, the same input $x$ belongs precisely when its single output $f(x)$ belongs to both $U$ and $V$. There is no opportunity to choose different witnesses, which is what made the image counterexample fail. The identities also hold for arbitrary families of output subsets.

In the finite example, choose $U=\{0,1\}$ and $V=\{0,2\}$. ThenThe intersection of the two preimages is exactly the same set $\{a,b\}$. Complements are preserved with respect to the appropriate source and target sets:For example, the unused output three contributes no extra input: with $U=\{0,2\}$, both sides of the complement identity are $\{c\}$. See Lebl, Proposition 0.3.15: preimages of unions, intersections and complements.

This makes preimages useful for transporting conditions. The solution set of $g(x)=0$ is $g^{-1}(\{0\})$, and a zero set is a preimage of zero. Requiring two output conditions takes the intersection of their preimages. In topology, a continuous function pulls every open set back to an open set; a measurable function pulls the specified measurable sets in its codomain back to measurable sets in its domain of a function. These definitions use preimages because their set operations remain consistent even when the function is noninjective.

For a finite probability distribution $p$ with support $S$ and a total function $f:S\to Y$, assign each image value the combined mass of its preimages. Its support is exactly the finite image $f(S)$, listed without repetitions. Every listed mass is positive because it contains at least one positive source mass.

The fiber of a function construction gives a set partition of $S$, so finite summation gives ${\sum }_{y}q(y)={\sum }_{x\in S}p(x)=1$. This proves nonnegativity and normalization without assuming that $f$ is injective. In code, mapping support values and then overwriting repeated image keys is incorrect; repeated keys must have their masses added. For example, mapping a uniform distribution on four consecutive integers to parity produces two outcomes with mass one half each.

For an odd prime $p$, a nonzero congruence class $a$ is a quadratic residue when $a\equiv x^2(\mathrm{mod}p)$ for some integer $x$. Here "quadratic residue" excludes zero: zero is a square of a number, but is neither a quadratic residue nor a quadratic nonresidue under this convention. Some treatments include zero among quadratic residues; the distinction matters when counting them or discussing their subgroup.^[ref]

Modulo seven, squaring the six nonzero congruence classes givesThus the set of quadratic residues is $Q_7=\{1,2,4\}$, and the quadratic nonresidues are $\{3,5,6\}$. In particular, $x^2\equiv 2(\mathrm{mod}7)$ has exactly the two solutions $x\equiv 3,4(\mathrm{mod}7)$: $3^2=9\equiv 2$ and $4^2=16\equiv 2$. Modulo eleven the quadratic residues are instead $Q_{11}=\{1,3,4,5,9\}$. Two is therefore a quadratic residue modulo seven and a quadratic nonresidue modulo eleven: being a quadratic residue depends on the modulus.

Why do the square roots come in pairs? If $x^2\equiv y^2(\mathrm{mod}p)$, the prime number $p$ divides $(x-y)(x+y)$, so it divides one factor: $y\equiv x$ or $y\equiv -x(\mathrm{mod}p)$. For nonzero $x$ these are distinct, because $p$ is an odd prime. Every nonempty nonzero fiber of a function of $s(x)=x^2$ therefore contains exactly two inputs. Pairing the $p-1$ nonzero congruence classes gives exactly $(p-1)/2$ quadratic residues and $(p-1)/2$ quadratic nonresidues. Including zero gives $(p+1)/2$ different squares, with one rather than two square roots for zero.

The quadratic residues form a subgroup of the multiplicative group of a finite field ${\mathbb{F}}_p^{\times }$, with index of a subgroup two. Indeed, one is a square, $(u^2)(v^2)=(uv{)}^2$, and $(u^2{)}^{-1}=(u^{-1}{)}^2$; the inverses exist because the inputs are nonzero in the prime field. Equivalently, the squaring group homomorphism has kernel of a group homomorphism $\{1,-1\}$ and image of a function $Q_p$. The apparent loss of a sign in squaring becomes a precise division of the nonzero arithmetic into two equal parts.

This structure turns a search for square roots into a yes-or-no test: Euler's criterion detects quadratic residues through modular exponentiation, and the Legendre symbol records the result as a sign. For a general integer modulus, the modular congruence $x^2\equiv a(\mathrm{mod}n)$ still makes sense, but the two-root count and the prime field argument need not survive. For example, $x^2\equiv 1(\mathrm{mod}15)$ has four solutions $1,4,11,14$; the Chinese remainder theorem separates the sign choices modulo three and five.

The assertion that every surjective function has a right inverse is equivalent to the axiom of choice. Choice selects one member of each nonempty fiber of a function, giving a right inverse. Conversely, for a family $(X_i{)}_{i\in I}$ of nonempty sets, the projection from the disjoint union $\{(i,x):i\in I,x\in X_i\}$ onto $I$ is surjective. A right inverse selects one element from each $X_i$, giving a choice function.