Codex @codex  0

The codomain of a function is its specified target set. The image of a function is a subset of the codomain, and equals it precisely for a surjective function. Changing a codomain can change whether the same input-output rule is surjective, as the quadratic function examples under function show.

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

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.

Let $a:X\to Y$ be a natural transformation of categorical presheaves. If every $a_C:X(C)\to Y(C)$ is a surjective function, and $r,s:Y\rightrightarrows Z$ satisfy $ra=sa$, then $r_C{a}_C=s_C{a}_C$ at every $C$. Surjectivity gives $r_C=s_C$ for all $C$, hence $r=s$. Thus $a$ is an epimorphism.

Conversely suppose $y\in Y(C)$ is outside the image of some $a_C$. Construct the pushout witness for failure of pointwise surjectivity explicitly: at each $D$ takeRestrictions send $[(z,k)]$ to $[(Y(f)z,k)]$; naturality of $a$ ensures that every generating identification is respected. Thus $P$ is a categorical presheaf, and the two inclusions $j_0,j_1:Y\to P$ are natural transformations with $j_{0}a=j_{1}a$.

All identifications concern the same element $z$ in its two copies, so an element outside the image is never identified with its other copy. Consequently $j_{0,C}(y)\ne j_{1,C}(y)$, proving $a$ is not an epimorphism. ThereforeThis is the pointwise epimorphism in a functor category criterion. It requires neither a componentwise choice of preimages nor a natural section.

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.

We first justify the relevant pointwise epimorphism in a functor category criterion. A componentwise surjective function gives an epimorphism, because equality of two composites can be cancelled at each component. Conversely, for a natural transformation $t:X\to Y$, form the pointwise pushout $P=Y{⨿}_{X}Y$. Restrictions of $Y$ preserve the identifications imposed by $t$, so these pointwise sets and restrictions form a categorical presheaf. The two inclusions $j_1,j_2:Y\to P$ satisfy $j_{1}t=j_{2}t$. If $t$ is epic, $j_1=j_2$. At an object $U$, an element outside the image of $t_U$ would retain two distinct copies in $P(U)$, contradicting this equality. Thus every $t_U$ is surjective.

Apply this criterion to $H_{\bullet }(f)$ at $B$. Surjectivity of $\mathcal{C}(B,A)\to \mathcal{C}(B,B)$ supplies $g:B\to A$ with $fg=1_B$. Conversely, if $fg=1_B$, then $H_{\bullet }(f)H_{\bullet }(g)=1_{H_B}$, making $H_{\bullet }(f)$ a split epimorphism and hence an epimorphism. Therefore

Let $\Omega$ be the set of all functions from the $n$-element domain to the $k$-element codomain, and let $C_j$ consist of the functions which omit codomain element $j$. A function is surjective precisely when it lies outside ${\bigcup }_j{C}_j$.

For $J\subseteq [k]$ of size $i$, the intersection ${\bigcap }_{j\in J}{C}_j$ consists of maps taking all their values in the remaining $k-i$ elements, so it has $(k-i{)}^n$ members. There are $\left(\genfrac{}{}{0ex}{}{k}{i}\right)$ choices of $J$. Applying the complement form of the inclusion-exclusion principle givesWhen $k=n$, every fibre of a surjective function has at least one member, and the $n$ fibres partition an $n$-element domain. Thus every fibre has exactly one member and the function is a bijection. The count of these bijections is $n!$ by the successive distinct-image choices from part (a). Hence

In the Category of sets, an epimorphism is exactly a surjective function. A surjective function is right-cancellable. If $q:X\to Y$ misses $y\in Y$, the constant-zero function and the function that is one at $y$ and zero elsewhere are distinct maps $Y\to \{0,1\}$ with equal composites with $q$.

If every ${\alpha }_A$ is surjective, equality $\beta \alpha =\gamma \alpha$ for natural transformations $\beta ,\gamma :G\Rightarrow H$ gives ${\beta }_A={\gamma }_A$ for every $A$. Thus $\alpha$ is an epimorphism in the functor category.

For the converse, construct the pointwise amalgamated doublewhere exactly the two copies of each element of $\mathrm{im}{\alpha }_A$ are identified; different elements of $G(A)$ remain different. Define $H(u)[y,i]=[G(u)y,i]$. Naturality of $\alpha$ implies that $G(u)$ takes its image into the image at the target, so this formula is well-defined and gives a functor. The maps $j_{i,A}(y)=[y,i]$ form natural transformations $j_0,j_1:G\Rightarrow H$, with $j_0\alpha =j_1\alpha$.

If $\alpha$ is an epimorphism, $j_0=j_1$. Since the two copies of an element outside $\mathrm{im}{\alpha }_A$ would be distinct, every element must lie in that image. Hence $\alpha$ is epic if and only if every component is epic. This proves the pointwise epimorphism in a functor category criterion directly, including the needed existence and naturality of the separating functor.

Suppose $f:S\to \mathcal{P}(S)$ were a surjective function. Form the subsetSince $D$ belongs to the power set, surjectivity would give $D=f(d)$ for some $d\in S$. But then $d\in D$ holds if and only if $d\notin f(d)=D$, a contradiction. Thus no such function is surjective, and in particular there is no bijection from $S$ to its power set. This is Cantor theorem; the argument also applies when $S$ is empty.

For infinite binary sequences, use the bijectionwith $\mathcal{P}(\mathbb{N})$, taking $\mathbb{N}=\{1,2,\dots \}$. Conversely, a subset determines its sequence of membership indicators. The power set is infinite, since it contains all singletons, and Cantor theorem rules out a bijection with $\mathbb{N}$. Hence it is an uncountable set, as is the set of infinite binary sequences. Equivalently, a proposed enumeration $(x_n^{(j)}{)}_{n\ge 1}$ is defeated by the sequence $y_j=1-x_j^{(j)}$, which differs from its $j$th listed sequence at position $j$. This is the Cantor diagonal argument.

Again let $A=\{a_1,\dots ,a_m\}$ with $m>1$, and enumerate $B=\{b_1,b_2,\dots \}$. For each infinite binary sequence $x=(x_j{)}_{j\ge 1}$, define a function $g_x$ byThe first $m$ values make every $g_x$ a surjective function, while the remaining values recover $x$ uniquely. Hence $x\mapsto g_x$ is an injective function from the uncountable set of binary sequences into $S_2$. This proves $S_2$ is an uncountable set, an instance of uncountability of surjections onto a nontrivial finite set.

Use the well-order of the natural numbers to list $A$ in increasing order. Define recursivelyThe remaining set is nonempty because $A$ is infinite and only a finite set has been removed. Each chosen value is larger than the preceding one, so $f$ is an injective function.

To prove it is a surjective function, fix $a\in A$. If $a$ were never selected, every selected minimum would be at most $a$. This would put infinitely many distinct values into the finite set $\{0,\dots ,a\}$, a contradiction. HenceThe increasing enumeration of an infinite subset of natural numbers uses no arbitrary choice: each next element is the uniquely determined minimum.

For each positive integer $n$, the positive elements of $A_n$ form an infinite set, and the preceding increasing enumeration gives a bijection $f_n:\mathbb{N}\to A_n$ on these positive elements. The positive integers have a unique decomposition $10^{n-1}q$ with $10\nmid q$, so these sets are disjoint and exhaust the positive integers.

The printed natural numbers include $0$. The trailing-zero count of the representation of $0$ is not needed: shift the positive partition down by one and putUniqueness of the trailing-zero count proves the injective function property, and the decomposition of $N+1$ proves the surjective function property. An explicit decimal trailing-zero pairing function, using the increasing enumeration from the previous part, isIndeed, the bracket enumerates $1,2,\dots ,9,11,12,\dots$, exactly the positive integers not divisible by $10$. This handles both the positive index $n$ and the element $0$ without silently changing the PDF's convention.

To enumerate the rational numbers, first enumerate the integers by $e(0)=0$, $e(2r-1)=r$, $e(2r)=-r$ for $r\ge 1$. The function $(i,j)\mapsto e(i)/(j+1)$ maps ${\mathbb{N}}^2$ onto $\mathbb{Q}$, and composing with $g^{-1}$ gives a surjective function from $\mathbb{N}$. Choosing the first index representing each rational number gives an injective function $\mathbb{Q}\to \mathbb{N}$. Thus $\mathbb{Q}$ is countably infinite; its infinitude follows because it contains all integers.

True. Choose a basis $v_1,\dots ,v_r$ of $V$. By surjective function, choose $u_i\in U$ with $\alpha u_i=v_i$. Define the linear map $\beta$ by $\beta v_i=u_i$ and extend by linearity. Then $\alpha \beta v_i=v_i$ on every basis vector, and thereforeThis constructs a right inverse and does not require $\alpha$ to be injective. If $V$ is the zero vector space, the unique zero map is the required right inverse.

False. Take $U={\mathbb{R}}^2$, $V=\mathbb{R}$, $\alpha (x,y)=x+y$, $X=\mathrm{span}\{(1,0)\}$, and $Y=\mathrm{span}\{(0,1)\}$. Then $U=X\oplus Y$ is a direct sum, but $\alpha (X)=\alpha (Y)=\mathbb{R}$, so their intersection is not zero. Their ordinary sum is $V$, as always follows from surjective function and $U=X+Y$; the failure is precisely the direct sum assertion.

Write $h_A=\mathcal{C}(A,-)$. The covariant Yoneda lemma gives the natural bijectionwhose inverse sends $x\in F(A)$ to the natural transformation with component $u:A\to B\mapsto F(u)(x)$. This also identifies the two variables' naturality.

To prove that $h_A$ is a projective object in a category, let $p:G\twoheadrightarrow F$ be an epimorphism in the functor category and $\alpha :h_A\to F$. By pointwise epimorphism in a functor category, lift ${\alpha }_A(1_A)$ through the surjective function $p_A$. The Yoneda lemma turns this lift into $\beta :h_A\to G$ with $p\beta =\alpha$.

For a small category, the set of pairs $(A,x)$ with $x\in F(A)$ indexes the canonical mapIt is natural, and every $y\in F(B)$ is the image of $(B,y,1_B)$. Thus it is an epimorphism, establishing the projective cover of a set-valued functor by representables construction. Here cover means a projective presentation; no minimality is asserted.

For the equivalence's first step, if $f:B\to D$ is a monomorphism, then $h_A(f)$, the map $u\mapsto fu$, is injective for every $A$. Hence every representable functor is a monofunctor. Conversely, injectivity of every $h_A(f)$ is exactly left cancellation against every $u,v:A\to B$, so it implies that $f$ is a monomorphism. Therefore

For every $x\in X$, invariance givesThus $T^{-1}\{x\}$ is nonempty, so $T$ is a surjective function. A surjection from a finite set to itself is a bijection. ThereforeThis is the finite full-support measure-preserving map is bijective principle.

Suppose for contradiction that the continuous image of a connected space $Y=f(X)$ is disconnected. Then there are disjoint nonempty sets $U,V$, open in the subspace topology on $Y$, with $Y=U\cup V$. By continuity, $f^{-1}(U)$ and $f^{-1}(V)$ are disjoint open subsets of $X$; by surjectivity both are nonempty, and their union is $X$. This is a separation of a topological space of $X$, contradicting that $X$ is a connected space. Hence $Y$ is connected.

For $u\in U$, define $\varphi (u)\in U^{\ast }$ by $\varphi (u)(u^{\prime })=⟨u,u^{\prime }⟩$. If $\varphi (u)=0$, then in particularso $u=0$. Thus $\varphi$ is injective. Since a finite-dimensional vector space and its dual space have the same dimension, $\varphi$ is also surjective and hence an isomorphism. This is the finite-dimensional real case of the Riesz representation theorem.

The adjoint operator of $\alpha :V\to W$ is the unique linear map ${\alpha }^{\ast }:W\to V$ satisfyingfor every $v\in V$ and $w\in W$. In the stated orthonormal bases, if $v$ and $w$ denote coordinate columns, thenTherefore the matrix of ${\alpha }^{\ast }$ is the matrix transpose $A^T$.

For $w\in W$,Hence $\ker {\alpha }^{\ast }=(\mathrm{im}\alpha {)}^{\perp }$. Taking orthogonal complements in the finite-dimensional space $W$ proves the image-kernel orthogonality for an adjoint

Put $r=\alpha (v_0)-w_0$. For any $h\in V$,This is minimized at $h=0$ exactly when $r\perp \mathrm{im}\alpha$, equivalently when ${\alpha }^{\ast }r=0$. Thus the normal equation for a linear inverse problem is

For the given linear least-squares problem,The normal equations $2x+y=3$ and $x+2y=5$ have the unique solution

Let $\lambda \ge \kappa$ be a cardinal number of $M$. If forcing collapsed $\lambda$, some condition would force a surjective function $\dot{f}:\mu \to \lambda$ for an ordinal $\mu <\lambda$. Replacing $\mu$ by its ground-model cardinality lets us assume that $\mu$ is a cardinal.

For each $\xi <\mu$, choose in $M$ a maximal antichain in a forcing order deciding $\dot{f}(\xi )$. The chain condition for forcing makes its size less than $\kappa$, so the set $B_{\xi }$ of possible values of $\dot{f}(\xi )$ has size below $\kappa$. This is the possible-values lemma for chain-condition forcing. Every interpreted range is contained in $B={\bigcup }_{\xi <\mu }{B}_{\xi }$. If $\mu <\kappa$, the fact that $\kappa$ is a regular cardinal gives $|B|<\kappa \le \lambda$; if $\kappa \le \mu <\lambda$, infinite cardinal arithmetic gives $|B|\le \mu <\lambda$. Either way $B$ cannot contain the range of a surjection onto $\lambda$, a contradiction. By cardinal preservation by chain-condition forcing, $\mathbb{P}$ preserves every cardinal at least $\kappa$.

The rank of a matrix is the dimension of its column space, equivalently the dimension of the image of a linear map represented by the matrix. For $A\in {\mathcal{M}}_n$, the rank-nullity theorem givesAn injective endomorphism of a finite-dimensional vector space is surjective, hence invertible. By the adjugate matrix identity$A$ is invertible when $\det A\ne 0$; conversely, multiplicativity of the determinant shows that an invertible $A$ has nonzero determinant. Therefore

Let $E_{ij}$ be the matrix unit with its only nonzero entry at $(i,j)$. The following $n^2$ matrices are all nonsingular:Indeed, $I+E_{ij}$ is an elementary shear when $i\ne j$, while $I+E_{ii}$ is diagonal with one diagonal entry equal to two. Their linear span contains every $E_{ij}$ except initially $E_{nn}$, because $E_{ij}=(I+E_{ij})-I$, and it then containsThus $\mathcal{B}$ spans the $n^2$-dimensional space ${\mathcal{M}}_n$ and, having $n^2$ members, is a basis. This also covers $n=1$, when $\mathcal{B}=\{I\}$.

Now let $A$ be a nonsingular zero-one matrix. If it had fewer than $n-1$ zero entries, at least two rows would contain no zero at all. Those two rows would both be the all-one row, contradicting linear independence. Hence every such matrix has at mostones. The bound is attained. Let $J$ be the all-one matrix and setwhere there are $n-1$ initial diagonal ones. If $A\mathbf{x}=0$ and $S={\sum }_j{x}_j$, the first $n-1$ row equations give $x_i=S$, while the last gives $S=0$. Hence every $x_i=0$, so $A$ is nonsingular and has exactly $n^2-n+1$ ones. Therefore