Relations and cancellation in categories

Written by GPT-6.1 Sol (OpenAI), October 2026. Self-checked by the writing AI (GPT-6.1 Sol, Ultra). Original text public domain (CC0).

An arrow can be cancellable without having an inverse. The distinction already appears in an ordered set: there is at most one arrow between two objects, so every arrow is cancellable, although an arrow going strictly upwards has no inverse. Binary relations give a second useful test. A relation can be a monomorphism even when it is not the graph of a function.

We develop these tests directly from composition. We assume the definition of a category and elementary sets and functions. Universes and small categories, Sections 2–3 provides the universe closure and transport results we use. Basic references are [Stacks, Categories], [Schapira, Categories and Homological Algebra] and that preceding lesson. We give the cancellation and relation arguments below, without assuming that limits exist or that every cancellable arrow is invertible.

1. Inverses and one-sided inverses

For arrows \(f:X\to Y\) and \(g:Y\to X\), being inverse means both \(gf=1_X\) and \(fg=1_Y\). Here and below juxtaposition means composition, with the rightmost arrow applied first.

An inverse is unique. If \(g,h\) are inverses of \(f\), then

The identity is its own inverse. If \(f:X\to Y\) and \(u:Y\to Z\) are invertible, \(f^{-1}u^{-1}\) is inverse to \(uf\): multiplying in either order gives the appropriate identity. Explicitly,

In particular, being isomorphic is an equivalence relation on objects: identities give reflexivity, inverse arrows give symmetry, and composition gives transitivity. The invertible endomorphisms of an object form its automorphism group, with composition as multiplication. Closure follows from (1.2), associativity and the unit come from the category, and the inverse stays an endomorphism of the same object.

A monomorphism is an arrow \(f:X\to Y\) such that \(fa=fb\) implies \(a=b\) for every parallel pair \(a,b:T\to X\). Thus, for every object \(T\), postcomposition is injective:

These statements are equivalent because injectivity is exactly the asserted cancellation for two elements of each Hom set. An epimorphism has the reversed test: \(af=bf\) implies \(a=b\) for every \(a,b:Y\to T\). Equivalently, every map \(\operatorname{Hom}(Y,T)\to\operatorname{Hom}(X,T)\), \(a\mapsto af\), is injective.

The opposite category keeps the objects and sets \(\operatorname{Hom}_{\mathcal C^{\mathrm{op}}}(X,Y)=\operatorname{Hom}_{\mathcal C}(Y,X)\). Its composition satisfies \(g\circ_{\mathrm{op}}f=f\circ g\). For three arrows \(f,g,h\) composable in the opposite category, its two associativity expressions are, in the original category, respectively \(f\circ(g\circ h)\) and \((f\circ g)\circ h\). They agree by associativity. Its identities are the original identities: its left identity equation is the original right identity equation, and conversely. This verifies the category laws. Reversing the cancellation test now shows that epimorphisms are precisely monomorphisms in the opposite category.

Suppose \(s:Y\to X\) and \(r:X\to Y\) satisfy \(rs=1_Y\). We call \(s\) a section of \(r\), and \(r\) a retraction of \(s\). The arrow \(s\) is monic: \(sa=sb\) gives \(rsa=rsb\), hence \(a=b\). The arrow \(r\) is epic: \(ar=br\) gives \(ars=brs\), hence \(a=b\). Both statements need only the displayed one-sided identity.

The other composite \(e=sr:X\to X\) satisfies \(e^2=s(rs)r=sr=e\); it is an idempotent. It need not be \(1_X\). For example, include a singleton into a two-element set and retract both elements onto that singleton. The composite on the two-element set is constant and differs from its identity. If \(r\) is also monic, cancel \(r\) in \(r(sr)=r1_X\) to obtain \(sr=1_X\). If \(s\) is also epic, cancel \(s\) in \((sr)s=1_Xs\) to obtain the same equality. Either extra cancellation makes the two arrows inverse.

2. What cancellation survives

Proposition 2.1. Let \(X\xrightarrow{f}Y\xrightarrow{g}Z\) be composable arrows. Composites of monomorphisms are monomorphisms, and composites of epimorphisms are epimorphisms. If \(gf\) is monic, then \(f\) is monic. If \(gf\) is epic, then \(g\) is epic.

Proof. If \(gfa=gfb\) and both arrows are monic, cancellation of \(g\) gives \(fa=fb\); cancellation of \(f\) gives \(a=b\). If \(agf=bgf\) and both arrows are epic, cancellation of \(f\) gives \(ag=bg\), and cancellation of \(g\) gives \(a=b\).

If only \(gf\) is monic, \(fa=fb\) still implies \(gfa=gfb\), so \(a=b\). If only \(gf\) is epic, \(ag=bg\) implies \(agf=bgf\), so \(a=b\). All equalities occur in the indicated Hom sets. \(\square\)

These last implications cannot generally be reversed to claim that \(g\) is monic or \(f\) is epic. A section followed by its retraction has an identity composite, although the retraction from a two-element set to a singleton is not monic, and the singleton inclusion is not epic. The first exercise verifies the set tests used in this example.

An ordered set \((I,\leq)\) gives a category with one arrow \(i\to j\) when \(i\leq j\), and no arrow otherwise. Reflexivity gives identities. Transitivity gives the composite of any composable pair, and uniqueness makes the identity and associativity laws hold. In this category every arrow is both monic and epic: any pair in the cancellation test already consists of the same arrow. An arrow \(i\to j\) is invertible exactly when \(j\leq i\); antisymmetry then says \(i=j\). Thus an arrow between distinct comparable elements is both monic and epic without being invertible. Reversing the order gives precisely the opposite category.

A category is called balanced if every arrow that is both monic and epic is invertible. This is an additional property. The ordered-set calculation explains why the two cancellation conditions alone do not prove it.

3. Functors and the direction of a test

A functor \(F:\mathcal C\to\mathcal D\) assigns objects to objects and arrows \(f:X\to Y\) to arrows \(F(f):F(X)\to F(Y)\). It preserves identities and composition. It preserves isomorphisms because applying it to the two inverse equations gives

A contravariant functor from \(\mathcal C\) to \(\mathcal D\) means a covariant functor from \(\mathcal C^{\mathrm{op}}\) to \(\mathcal D\). It reverses the arrow and composition order. The identity assignments on object and arrow labels give a contravariant map \(\mathcal C\to\mathcal C^{\mathrm{op}}\): the original composite \(gf\) becomes \(f^{\mathrm{op}}\circ_{\mathrm{op}}g^{\mathrm{op}}\), and identities are unchanged. An ordinary \(F\) also induces an ordinary \(F^{\mathrm{op}}:\mathcal C^{\mathrm{op}}\to\mathcal D^{\mathrm{op}}\). For arrows composable in the opposite domain, the original functor law gives

Its identity law is unchanged. Composing two ordinary functors on objects and arrows gives their composite functor because

The functor \(F\) is faithful, full or fully faithful when each of its Hom maps is, respectively, injective, surjective or bijective. It is essentially surjective if every object of \(\mathcal D\) is isomorphic to some \(F(X)\). It is conservative if invertibility of \(F(f)\) implies invertibility of \(f\).

Proposition 3.1. A faithful functor reflects monomorphisms and epimorphisms: if \(F(f)\) has either property, \(f\) has that property.

Proof. For monicity, take \(a,b:T\to X\) with \(fa=fb\). The functor law gives \(F(f)F(a)=F(f)F(b)\). Cancel the monic \(F(f)\), then use injectivity on \(\operatorname{Hom}(T,X)\) to get \(a=b\). For epicity, take \(a,b:Y\to T\) with \(af=bf\). Apply \(F\), cancel the epic \(F(f)\), and use injectivity on \(\operatorname{Hom}(Y,T)\). \(\square\)

Proposition 3.2. Fully faithful functors are conservative. Each of the five properties faithful, full, fully faithful, essentially surjective and conservative is closed under composition of functors.

Proof. If \(F\) is fully faithful and \(F(f):F(X)\to F(Y)\) has an inverse, fullness on \(\operatorname{Hom}(Y,X)\) lifts that inverse to \(h:Y\to X\). Applying \(F\) to \(hf\) and \(fh\) gives identities by construction. Faithfulness on the two endomorphism sets gives \(hf=1_X\) and \(fh=1_Y\). Thus \(f\) is invertible.

For \(\mathcal C\xrightarrow{F}\mathcal D\xrightarrow{G}\mathcal E\), the Hom map of \(GF\) is the composite of the Hom map of \(F\) with that of \(G\) at \(F(X),F(Y)\). Composites of injections, surjections and bijections have the same property, proving the first three assertions. If \(F,G\) are essentially surjective, choose for any \(Z\in\mathcal E\) an isomorphism \(G(Y)\to Z\) and an isomorphism \(F(X)\to Y\). Applying \(G\) to the second and composing gives \(GF(X)\simeq Z\). Only these choices for the given object are needed. If \(F,G\) are conservative and \(GF(f)\) is invertible, conservativity of \(G\) makes \(F(f)\) invertible, and conservativity of \(F\) makes \(f\) invertible. \(\square\)

Faithfulness alone does not supply the inverse lift used here. It also does not say that monomorphisms or epimorphisms are preserved: a target category may have additional parallel test arrows. Exercise 2 makes all three limitations explicit.

4. Relations form a category

Fix a universe \(\mathcal U\). The objects of \(\mathsf{Rel}_{\mathcal U}\) are the members of \(\mathcal U\). An arrow \(R:X\to Y\) is a subset of \(X\times Y\). Write \(xRy\) for \((x,y)\in R\). For \(R:X\to Y\) and \(S:Y\to Z\), define

The identity on \(X\) is the diagonal \(\Delta_X\). For a third relation \(T:Z\to W\), membership of \((x,w)\) in either \(T(SR)\) or \((TS)R\) says exactly that there exist \(y\in Y,z\in Z\) with \(xRy,ySz,zTw\). This proves associativity, including when any of these sets is empty. The equality \(R\Delta_X=R\) follows because its witness must be \(x\) itself. The equality \(\Delta_YR=R\) follows because its witness must be the output element \(y\). Thus these data form a category. Its Hom set is \(\mathcal P(X\times Y)\), a member of \(\mathcal U\) by the universe closure proofs; it is locally \(\mathcal U\)-small.

For a function \(f:X\to Y\), let \(\Gamma_f=\{(x,f(x)):x\in X\}\). The diagonal is \(\Gamma_{1_X}\), and (4.1) gives \(\Gamma_g\Gamma_f=\Gamma_{gf}\). Consequently graphs define a functor

Equality of two graphs says their unique output at each input is the same, so the functor is faithful. It is not full: between two singleton sets the empty relation is an arrow but is not the graph of their unique function. Identifying each function with its graph identifies sets with the subcategory of relations that are graphs of total single-valued functions.

The converse \(R^{\mathrm t}:Y\to X\) satisfies \(yR^{\mathrm t}x\) exactly when \(xRy\). Directly from the existential test,

It is therefore an isomorphism from the opposite relation category to the relation category. Converse reverses cancellation tests, so \(R\) is epic exactly when \(R^{\mathrm t}\) is monic.

Theorem 4.1. The invertible relations are exactly the graphs of bijections.

Proof. Let \(R:X\to Y\) have inverse \(S:Y\to X\). From \(SR=\Delta_X\), each \(x\) has at least one \(y\) with \(xRy\) and \(ySx\). From \(RS=\Delta_Y\), each \(y\) has at least one \(x'\) with \(ySx'\) and \(x'Ry\).

For any pair \(xRy\), use the second assertion to choose such an \(x'\). Then \((x,x')\in SR\), so \(x'=x\) and hence \(ySx\). If \(xRy_1\) and \(xRy_2\), we now have \(y_1Sx\), and therefore \((y_1,y_2)\in RS\); thus \(y_1=y_2\). Each \(x\) has exactly one output, so \(R=\Gamma_f\) for a function \(f:X\to Y\). The second assertion gives surjectivity. If \(x_1Ry\) and \(x_2Ry\), then \(ySx_2\) and \((x_1,x_2)\in SR\), so \(x_1=x_2\). This gives injectivity.

Conversely, for a bijection \(f\), the composition law for graphs gives \(\Gamma_{f^{-1}}\Gamma_f=\Delta_X\) and \(\Gamma_f\Gamma_{f^{-1}}=\Delta_Y\). These are the inverse equations. The proof includes the empty case: if \(X\) is empty and an inverse exists, \(RS=\Delta_Y\) forces \(Y\) empty. The unique empty bijection gives the inverse in that case. \(\square\)

5. Four graded exercises with full solutions

Exercise 1 (introductory: the set cancellation tests). Prove that a function is monic in \(\mathsf{Set}_{\mathcal U}\) exactly when it is injective, and epic exactly when it is surjective. Include empty sets. Deduce that the singleton inclusion into a two-element set and its constant retraction have an invertible composite although neither is invertible. Identify which cancellation implication of Proposition 2.1 cannot be reversed in each case.

Solution. If \(f:X\to Y\) is injective and \(fa=fb\), equality at each element of the common domain gives \(a=b\). If \(f\) is not injective, choose distinct \(x_1,x_2\) with \(f(x_1)=f(x_2)\). The two singleton maps with those values are distinct but have equal composites with \(f\), disproving monicity.

If \(f\) is surjective and \(af=bf\), for each \(y\in Y\) choose an \(x\) with \(f(x)=y\); then \(a(y)=b(y)\). This pointwise argument does not require choosing a simultaneous section. If \(f\) is not surjective, choose \(y_0\in Y\setminus f(X)\). The constant-zero function \(Y\to\{0,1\}\) and the characteristic function of \(\{y_0\}\) are distinct but agree after \(f\), disproving epicity. All test sets and functions belong to the fixed universe by its closure properties. If \(X\) is empty, its function to \(Y\) is injective and is surjective precisely when \(Y\) is empty. The same witnesses handle every nonempty \(Y\). A function to an empty set can exist only when its source is empty.

Let \(s:\{*\}\to\{0,1\}\) send \(*\) to \(0\), and let \(r\) send both elements to \(*\). Then \(rs=1\). The map \(s\) is monic but not epic, and \(r\) is epic but not monic. Thus monicity of the composite does not make its second factor monic, and epicity of the composite does not make its first factor epic. Neither factor is invertible because each fails one necessary cancellation property.

Exercise 2 (intermediate: faithfulness is not enough). Let \(\mathcal A\) have two objects \(a,b\), their identities and one other arrow \(t:a\to b\). Construct faithful functors from \(\mathcal A\) to sets which fail to preserve monomorphisms and which fail to preserve epimorphisms. Construct a faithful functor which sends \(t\) to an isomorphism although \(t\) is not an isomorphism. Check these assertions on all four Hom sets and explain why they do not contradict Proposition 3.1.

Solution. This is the ordered category of \(a<b\), so \(t\) is both monic and epic and has no inverse. The four Hom sets are \(\{1_a\},\{t\},\varnothing,\{1_b\}\). Sending \(a\) to \(\{0,1\}\), \(b\) to a singleton, and \(t\) to the constant function defines a functor: the only required compositions involve identities. Each singleton Hom set maps injectively, and the empty Hom set has an injective map to any target Hom set. The functor is faithful. Its image of \(t\) is not injective, hence not monic by Exercise 1.

Sending \(a\) to a singleton, \(b\) to \(\{0,1\}\), and \(t\) to the function with value \(0\) gives another functor with the same four injectivity checks. Its image of \(t\) is not surjective, hence not epic. Finally, send both objects to a singleton and \(t\) to its identity. All four Hom maps remain injective, but now \(F(t)\) is invertible while \(t\) is not. This functor is not full: the empty Hom set from \(b\) to \(a\) maps to a singleton Hom set. The inverse required in Proposition 3.2 therefore has no lift. Proposition 3.1 reflects cancellation from the image back to the source; it does not assert the preservation or conservativity refuted here.

Exercise 3 (advanced: quotient classes split a relation). Let \(E\) be an equivalence relation on a universe-member set \(X\), and let \(q:X\to Q=X/E\) be the quotient function. Prove in the relation category that

Deduce that \(E\) is idempotent and give its splitting. Explain why no representatives need to be chosen. Check \(X=\varnothing\). Give a two-element idempotent relation which is not an equivalence relation.

Solution. By (4.1), \((x,x')\) belongs to \(\Gamma_q^{\mathrm t}\Gamma_q\) exactly when \(q(x)=q(x')\), which is equivalent to \(xEx'\). For classes \(A,B\), their pair lies in \(\Gamma_q\Gamma_q^{\mathrm t}\) precisely when some \(x\) has both \(q(x)=A\) and \(q(x)=B\). This forces \(A=B\). Conversely, every equivalence class has at least one element, so every diagonal pair occurs. A quotient class is a subset of \(X\), and \(Q\) is a subset of \(\mathcal P(X)\); the universe closure theorem puts \(Q\) in the universe.

Set \(r=\Gamma_q:X\to Q\) and \(s=\Gamma_q^{\mathrm t}:Q\to X\). Equation (5.1) says \(rs=1_Q\) and \(sr=E\), precisely a splitting. Hence \(E^2=s(rs)r=sr=E\). The converse relation \(s\) includes every element of each class, instead of selecting one representative, so no family of representative choices occurs. For empty \(X\), \(Q\) is empty and all relations in (5.1) are empty, which is the diagonal identity on the empty set.

On \(\{0,1\}\), the relation \(0R0,0R1,1R1\) is idempotent. Transitivity gives \(R^2\subset R\), and reflexivity supplies an intermediate element for every pair of \(R\), giving the reverse inclusion. It is not symmetric because \(1R0\) is false, so it is not an equivalence relation. Idempotence alone does not make the equivalence-class construction just used applicable.

Exercise 4 (advanced: cancellation for arbitrary relations). Prove that a relation \(R:X\to Y\) is monic exactly when every \(x\in X\) has a private output: some \(y\in Y\) satisfies \(xRy\) and \(x'Ry\) implies \(x'=x\). Give the dual criterion for epicity. Deduce that the relation category is balanced. Produce a monic relation which is not the graph of a function, and an epic relation with the same failure. Include empty sets in the criteria.

Solution. An arrow from a singleton to \(X\) is an arbitrary subset \(A\subset X\). Postcomposing it with \(R\) gives the subset \(R[A]\subset Y\) of all outputs reached from an element of \(A\). If \(R\) is monic, this map on subsets is injective. For each \(x\), the distinct subsets \(X\) and \(X\setminus\{x\}\) must have different images. Since the second image is contained in the first, some \(y\) lies in the first and not the second. Its input can only be \(x\), and no other input reaches it; this is the required private output.

Conversely, suppose private outputs exist. Let \(A,B:T\to X\) be relations with \(RA=RB\). If \(tAx\), choose a private output \(y\) of \(x\). Then \(t(RA)y\), hence \(t(RB)y\). There is therefore an \(x'\) with \(tBx'\) and \(x'Ry\). Privacy forces \(x'=x\), so \(tBx\). This proves \(A\subset B\); interchanging them gives equality, proving monicity.

By the converse operation (4.3), epicity means that every \(y\in Y\) has a private input: some \(x\) satisfies \(xRy\), and \(xRy'\) implies \(y'=y\). Suppose both criteria hold. For any \(x\), choose a private output \(y\). Epicity supplies for this \(y\) a private input \(x'\). Because \(y\) is private to \(x\), the equality \(x'=x\) follows. The private-input condition then says that \(x\) has no other output. Thus every \(x\) has exactly one output. Every \(y\) has an input by epicity; its input \(x\) has a private output, which must be its unique output \(y\), so no other input reaches \(y\). The relation is consequently the graph of a bijection, and Theorem 4.1 makes it invertible. This proves balancedness.

The relation from a singleton \(\{*\}\) to \(\{0,1\}\) consisting of both pairs is monic: either output is private to \(*\). It is not a function graph because the input has two outputs. For an epic example, take \(X=\{a,b,c\},Y=\{0,1\}\) and pairs \((a,0),(b,1),(c,0),(c,1)\). The input \(a\) is private to \(0\), and \(b\) to \(1\), so it is epic. The input \(c\) has two outputs, so it is not a function graph.

If \(X\) is empty the monicity condition is vacuous, and all relations \(T\to X\) are equal, so it is monic. If \(Y\) is empty the epicity condition is vacuous, and all relations \(Y\to T\) are equal, so it is epic. A relation \(X\to\varnothing\) with nonempty \(X\) is not monic, and a relation \(\varnothing\to Y\) with nonempty \(Y\) is not epic, because the corresponding private witness cannot exist. The unique empty relation is both precisely when both sets are empty, and then is an identity. These are exactly the boundary cases of the two criteria and balancedness argument.

6. References

• [Tensor actions] Tensor actions and absolute algebra presentations, proof of Lemma 1.1, in this course. The complete inverse-lifting argument for fully faithful functors used in Section 3 is the same elementary argument. CC0-1.0.
• [Universes and small categories] Universes and small categories, Sections 2–3, in this course. Universe closure, size transport, powersets, quotients and function graphs. CC0-1.0.
• [Stacks, Categories] The Stacks Project authors and AI-integrated fork contributors. Categories, definition and functor conventions, and monomorphisms and epimorphisms. GFDL-1.2-or-later. Reference for the categorical definitions.
• [Schapira, Categories and Homological Algebra] Pierre Schapira, An Introduction to Categories and Homological Algebra, author-hosted edition dated 1 March 2026, Section 1.3: Definition 1.3.1 and Notation 1.3.3 for categories and cancellation terminology; Example 1.3.4(ii) for binary relations; Definitions 1.3.7 and 1.3.10 for functors and their Hom-set properties. The cancellation, converse-relation and invertibility proofs, including all empty cases, are given in Sections 1–4 and the solutions above.