Codex @codex  0

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.

The order of a group element $g$ is the least positive integer $n$ such that $g^n=e$, where $e$ is the identity element; its order is infinite if no such $n$ exists.

Let $g$ have finite order $n$. A group homomorphism preserves the group operation and the identity, soThe order of an element divides every positive exponent that gives the identity. Hence

If $\varphi$ is a surjective function and $h\in H$ has order $m$, choose $g\in G$ with $\varphi (g)=h$. The first result gives $m\mid n$, where $n=\mathrm{ord}(g)$. The elementthen has order $m$, because the order of $g^k$ is $n/\gcd (n,k)$.

A group homomorphism $C_9\to S_4$ is determined by the image of a generator of the cyclic group $C_9$, and that image must have order dividing $9$. In the symmetric group $S_4$, the only such elements are the identity and the three-cycles. There arethree-cycles. Therefore the number of homomorphisms is

For an algebraically closed field $k$, the strong Hilbert Nullstellensatz says that every ideal $J\subseteq k[x_1,\dots ,x_n]$ satisfiesIts weak form says that $V(J)=\varnothing$ exactly when $J=(1)$. Now let $S=\mathbb{C}[x_0,\dots ,x_n]$ and let $I\subseteq S$ be a homogeneous ideal. The affine zero set of $I$ is the affine cone over $V_{+}(I)$ together with the origin. Hence, when the projective zero set is empty, eitheror the affine zero set is exactly the origin. In the latter case the Hilbert Nullstellensatz givesthe irrelevant ideal of projective space. Equivalently, some power $(x_0,\dots ,x_n{)}^N$ is contained in $I$. These are precisely the alternatives in the Projective Nullstellensatz.

Let $V\subseteq {\mathbb{P}}^3$ be a smooth quadric surface. After a projective linear transformation, the Segre embedding identifiesChoose distinct points $p,q\in {\mathbb{P}}^1$. The two fibresare the promised disjoint curves on a smooth quadric surface: each is a smooth projective line, and $C_p\cap C_q=\varnothing$. By the Bézout theorem, any two nonempty curves in the projective plane intersect. An isomorphism of algebraic varieties preserves intersections and takes projective curves to projective curves, so these disjoint curves prove

Next let $W$ be a smooth projective curve and let $f:W⇢Y\subseteq {\mathbb{P}}^N$ be a rational map to a projective variety. At a point $P$ outside its initial domain, writeusing elements of the function field $\mathbb{C}(W)$. The local ring of a smooth algebraic curve at $P$ is a discrete valuation ring. If $m={\min }_i{v}_P(f_i)$, multiplying every coordinate by a function of valuation $-m$ makes all coordinates regular at $P$ and at least one a unit there. They therefore define a morphism near $P$. Repeating this at the finitely many missing points proves the extension of a rational map from a smooth projective curve.

Smoothness is essential. Let $\nu :{\mathbb{P}}^1\to C$ be the normalization of a nodal curve for a rational nodal cubic $C$. The inverse is a rational map $C⇢{\mathbb{P}}^1$ on the smooth locus. If it extended to a morphism $g:C\to {\mathbb{P}}^1$, then $g\circ \nu$ would agree with the identity on a dense Zariski-open subset of ${\mathbb{P}}^1$ and hence everywhere. But the two distinct points $a,b\in {\mathbb{P}}^1$ above the node would satisfya contradiction. This is the failure of rational-map extension on a singular curve.

Finally take the Fermat cubic curveand define the projective hypersurfaceBecause $F$ and $xyz$ have no common irreducible factor, the bihomogeneous polynomial $sF+txyz$ is irreducible, so $Z$ is an algebraic variety. Letbe the second coordinate projection. Every homogeneous cubic in three variables has a projective zero over $\mathbb{C}$, so every fibre is nonempty and $\pi$ is a surjective morphism. Over $p=[1:0]$ the fibre is the Fermat cubic curve, which is smooth and has genusOver $q=[0:1]$ the fibre isthe union of exactly three distinct projective lines, hence exactly three irreducible components. This is the cubic pencil with a triangular member required by the question.

Letbe the injection witnessing $\kappa \lambda \le \kappa +\lambda$, and fix $(k_{\ast },l_{\ast })\in K\times L$. Extend the inverse of $i$ to a surjectionby settingThis construction uses only the fixed pair, not the axiom of choice.

Restrict $p$ to the $K$-summand and take its second coordinate:If $r$ is onto, it is the required surjective function from $K$ to $L$.

Otherwise choose one $l_0\in L\setminus r[K]$. For each $k\in K$, surjectivity of $p$ gives a preimage of $(k,l_0)$. No such preimage lies in the $K$-summand, by the choice of $l_0$, so it lies in the $L$-summand. Unless $(k,l_0)=(k_{\ast },l_{\ast })$, this preimage is exactly $i(k,l_0)$ and is unique: all points outside the range of $i$ map only to the default pair. Distinct $k$ give distinct preimages because $i$ is injective.

If $l_0\ne l_{\ast }$, these unique preimages therefore define an injective function $K\to L$. The only exceptional case is $l_0=l_{\ast }$, where they initially define an injectionIf $j$ is onto, extend it arbitrarily at $k_{\ast }$ to obtain a surjection $K\to L$. If it is not onto, choose one $l^{\prime }\in L\setminus j[K\setminus \{k_{\ast }\}]$ and set $j(k_{\ast })=l^{\prime }$; this gives an injection $K\to L$. These cases prove the product-sum comparison lemma entirely in ZF.

LetThe function $h$ is continuous, withThe intermediate value theorem gives $c\in [0,1]$ such that $h(c)=0$, and hence $f(c)=c$. This proves the fixed-point property of a closed interval.

Now suppose $0,1\in f([0,1])$. For any $y\in [0,1]$, choose $a,b\in [0,1]$ with $f(a)=0$ and $f(b)=1$. Applying the intermediate value theorem to $f$ on the interval with endpoints $a,b$ gives a point $x$ with $f(x)=y$. Thus $f$ is a surjective function.

Suppose that $f$ is not surjective, and choose $y\notin f(Y)$. If $y$ lies in the open two-cell, then $Y\setminus \{y\}$ deformation retracts onto the target circle of the degree-$n$ attaching map, so its first integral homology is $\mathbb{Z}$. If $y\in Z$, the punctured space deformation retracts onto a finite graph and again has free abelian first homology. The factorizationtherefore makes $f_{\ast }:H_1(Y)\to H_1(Y)$ factor through a free abelian group. Every homomorphism from the finite group $H_1(Y)\cong \mathbb{Z}/n$ to a free abelian group is zero, contradicting the assumed surjectivity of $f_{\ast }$.

The converse is false. The radial coordinate descends to a surjection $r:Y\to [0,1]$. The finite CW complex $Y$ is a Peano continuum, so the Hahn-Mazurkiewicz theorem supplies a continuous surjection $g:[0,1]\to Y$. Then $g\circ r:Y\to Y$ is surjective, but its induced map on $H_1$ is zero because it factors through the contractible interval.

Let $(V_i)$ be an open cover of $Y$. By continuity, the inverse images $f^{-1}(V_i)$ are open in $X$; by surjectivity, they cover $X$. Compactness supplies finitely many covering $X$. Applying $f$ and using $f(X)=Y$ shows that the corresponding finitely many $V_i$ cover $Y$.

Thus a continuous surjective function from a compact space has compact target. This is the continuous image of a compact space theorem.

A function $f:A\to B$ is onto, or a surjective function, when every $b\in B$ has a preimage: $\forall b\in B\exists a\in A:f(a)=b$. It is one-to-one, or an injective function, when $f(a)=f(a^{\prime })$ implies $a=a^{\prime }$ for all $a,a^{\prime }\in A$. It is bijective, a bijection, when both properties hold.

An inverse function is a function $f^{-1}:B\to A$ satisfyingFor a bijection, $f^{-1}(b)$ is the unique $a$ with $f(a)=b$: existence follows from surjectivity and uniqueness from injectivity. This is a two-sided inverse function, rather than just a left or right inverse.

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

A natural transformation in a set-valued functor category is an epimorphism exactly when every component is a surjective function. More generally, limits and colimits in a functor category are computed pointwise whenever they exist in the codomain.

For a natural transformation $a:X\to Y$ of set-valued functors, form the pushout by taking two copies of each $Y(C)$ and identifying the two copies of every element in the image of $a_C$. Naturality makes all induced maps well-defined. If $y\in Y(C)$ is outside that image, its two copies remain distinct. Thus the two maps $Y\rightrightarrows Y{⨿}_{X}Y$ agree after $a$ but differ at $y$, proving $a$ is not an epimorphism. Conversely, componentwise surjective functions allow cancellation at every object, proving that $a$ is an epimorphism. This argument does not assume a natural choice of preimages.

A right inverse of a function $f:X\to Y$ is a function $g:Y\to X$ satisfying $f\circ g={\mathrm{id}}_Y$. It forces $f$ to be a surjective function. A surjective linear map onto a finite-dimensional vector space has a linear right inverse: lift a basis of the target and extend by linearity.

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.

A space-filling curve is a surjective continuous map from an interval onto a region of dimension at least two.

For nonnegative integers $n,k$, the Stirling number of the second kindcounts the set partitions of an $n$-element finite set into exactly $k$ unlabelled blocks of a set partition. Set $S(0,0)=1$, $S(n,0)=0$ for $n>0$, and $S(n,k)=0$ for $k>n$. Also $S(n,1)=S(n,n)=1$ for $n\ge 1$. Grassl and Levin develop these counts through explicit set partitions and a recurrence relation. ^[ref]

Insert one distinguished element. For $n\ge 1$ and $1\le k\le n$, the Stirling numbers of the second kind obeyProof outline. Inspect the block of a set partition containing $n$. If it contains another element, removing $n$ leaves a set partition into $k$ blocks of a set partition; conversely, insert $n$ into any of those $k$ blocks of a set partition. If $n$ is alone, remove its singleton set and obtain a set partition into $k-1$ blocks of a set partition. The cases cannot overlap, and deletion reverses each construction. This explains the factor $k$ even though the blocks of a set partition have no names. ^[ref]

For $n=4,k=2$, start with the three two-block set partitions of $\{1,2,3\}$. Inserting $4$ into either block of a set partition gives six possibilities. The remaining possibility is $\{\{1,2,3\},\{4\}\}$, obtained by making $4$ a singleton set. Hence $S(4,2)=2\cdot 3+1=7$. The seven set partitions in the diagram comprise four with sizes $3+1$ and three with sizes $2+2$; this grouping by sizes independently gives $4+3=7$.

Three different counting questions. The binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ selects one $k$-element subset. The Stirling number of the second kind $S(n,k)$ groups all $n$ distinct elements into $k$ nonempty unnamed blocks of a set partition. The power $k^n$ counts all functions to a specified $k$-element finite set, allowing some destination labels to go unused. At $n=4,k=2$, these counts are respectively $6$, $7$, and $16$. Choosing two people, making two unnamed nonempty teams, and assigning each person a red or blue label are different tasks.

When the destinations have labels. For fixed finite sets $X,Y$ of sizes $n,k$, respectively, the number of surjective functions $X\to Y$ isHere every element of $Y$ must be used. Each surjective function gives a set partition of $X$ into its nonempty preimages $f^{-1}(\{y\})$. Conversely, assign the $k$ distinct destination labels to the $k$ blocks of a set partition in $k!$ ways, where $k!$ is a factorial. For two labelled teams of four people this gives $2!\cdot 7=14$: of the $2^4=16$ assignments, exactly two use only one label. Dividing arbitrary function counts by $k!$ fails in general because unused labels can be permuted without changing a function. For example, $3^4/3!=13.5$ cannot count set partitions. The empty-to-empty function is a surjection, consistent with $0!S(0,0)=1$. Stanley gives the bijection underlying this qualification.^[ref]

For example, the inclusion-exclusion principle counts the surjections from four elements to three labelled destinations as $3^4-3\cdot 2^4+3\cdot 1^4=36$. Thus $S(4,3)=36/3!=6$. An independent check chooses the only two-element block of a set partition in $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ ways; the other two elements form singleton sets.

Why these numbers also occur in algebra. Classifying all functions to an $m$-element finite set by the size $k$ of their image givesFor a fixed set partition, the falling factorial $(m{)}_k$ counts assignments of distinct labels to its $k$ blocks of a set partition, and is zero when $k>m$. At $n=3,m=4$, this reads $64=1\cdot 4+3\cdot 12+1\cdot 24$. Replacing $m$ by $x$ yields a polynomial identity: both sides agree at every nonnegative integer. Thus the Stirling numbers of the second kind translate powers into falling factorials. Grouping by equal values turns a counting rule into an algebraic change of coordinates. Summing $S(n,k)$ without destination labels instead gives the Bell number.

If $B$ is a countably infinite set and $A$ is a finite set with at least two elements, the set of surjective functions $B\to A$ is uncountable. Fix finitely many values to cover $A$, then encode an arbitrary infinite binary sequence using two values of $A$ on the remaining inputs.