Theory and Applications of Categories, Vol. 25, No. 9, 2011, pp. 247–250.

A SMALL OBSERVATION ON CO-CATEGORIES

PETER LEFANU LUMSDAINE

Abstract. Various concerns suggest looking for internal co-categories in categories with strong logical structure. It turns out that in any coherent category E, all cocategories are co-equivalence relations.

0.1. Definition. Let E be any category. An (internal) co-category Q in E is an internal category in E^{op}, i.e. objects and morphisms in E

\xymatrix{Q^{0} \ar[r]^{l} \ar[r]_{r} & Q^{1} \ar[l]|{i} \ar[r]^{q} & Q^{1} +_{Q^{0}} Q^{1}}

such that the following diagrams commute:

\xymatrix{Q^{0} \ar[r]^{l} \ar[d]_{l} & Q^{1} \ar[d]|{q} & A^{0} \ar[l]_{r} \ar[d]^{r} & Q^{1} \ar[r]^{q} \ar[d]_{q} & Q^{1} +_{Q^{0}} Q^{1} \ar[d]^{[q,ν_{3}]} \\ Q^{1} \ar[r]_{ν_{1}} & Q^{1} +_{Q^{0}} Q^{1} & Q^{1} \ar[l]^{ν_{2}} & Q^{1} +_{Q^{0}} Q^{1} \ar[r]^{[ν_{1},q]} & Q^{1} +_{Q^{0}} Q^{1} +_{Q^{0}} Q^{1}}

\xymatrix{Q^{0} \ar[r]^{l} \ar@{-->}[dr]_{l} & Q^{1} \ar[d]^{i} & Q^{0} \ar[l]_{r} \ar[dl]^{r} &  & Q^{1} \ar[dl]_{1} \ar[d]^{q} \ar[dr]^{1} \\  & Q^{0} &  & Q^{1} & Q^{1} +_{Q^{0}} Q^{1} \ar[l]^{[li,1]} \ar[r]_{[1,ri]} & Q^{1}}

0.2. Definition. A co-category Q is a co-preorder if the maps l, r are jointly epimorphic.

A co-category Q is a co-groupoid if there is a map s : Q^{1} → Q^{1} satisfying the duals of the usual identities for the inverse map of a groupoid.

A co-groupoid Q is a co-equivalence relation if it is a co-preorder.

0.3. Remark. In a co-preorder, the co-composition q is uniquely determined by the maps l, r, i; likewise, in a co-groupoid, the co-inverse map s is determined by the rest of the structure.

Together with the obvious maps, these give categories and full inclusions

\xymatrix{CoEqRel(E) \ar@{^{(}->}[r] & CoPreOrd(E) \ar@{^{(}->}[r] & CoCat(E).}

Received by the editors 2009-02-27 and, in revised form, 2009-03-02.

Transmitted by Peter Johnstone. Published on 2011-04-04.

2000 Mathematics Subject Classification: 18D35.

Key words and phrases: Co-categories, co-groupoids, coherent categories, coherent logic.

\begin{matrix}c \\ ◯ \end{matrix} Peter LeFanu Lumsdaine, 2011. Permission to copy for private use granted.

0.4. Example. If E has all (or enough) pushouts and m : S ↣ A is any monomorphism, then the co-kernel pair of m is a co-equivalence relation

\xymatrix{A \ar[r]^{ν_{1}} \ar[r]_{ν_{2}} & A +_{S} A \ar[l]|{[1_{A},1_{A}]} \ar[r]|{[ν_{1},ν_{3}]} & A +_{S} A +_{S} A.}

This gives the object part of a functor Mono(E) → CoEqRel(E), which (almost by definition) is one half of an equivalence whenever E is co-exact. (Here Mono(E) denotes the full subcategory of E^{·→·} on monomorphisms.)

0.5. Example. A paradigmatic example is the interval I in Top, where I^{0} is a singleton, I^{1} is the unit interval, l and r are the endpoints, I^{1} +_{I^{0}} I^{1} is two copies of the interval joined end to end, and q is the obvious “stretching” map. Unfortunately, this is also of course not an actual co-category — the axioms hold only up to homotopy. However, it provides a very useful mental picture for the arguments below; and if we delete the interior of the interval, we obtain a genuine co-category. See also the examples below for more versions of the interval.

[figure: •; l; i; r; •; •; q; •; •; •]

0.6. Definition. A coherent category is a category with all finite limits, and images and unions that are stable under pullback.

[Johnstone 2002, A1.3–4] gives various basic results on coherent categories, which we will use here without comment.

0.7. Definition. Coherent logic is the fragment of first-order logic built up from atomic formulæ using finite con-/dis-junction and existential quantification.

Coherent logic is discussed in [Johnstone 2002, D1.1–2]; the essential point is that coherent logic can be interpreted soundly in coherent categories, and so may be used as an internal language for working in them.

0.8. Proposition. In a coherent category E, every co-category Q is a co-equivalence relation.

Proof. First, we show that any co-category Q is a co-preorder.

Arguing in the internal logic: given x in Q^{1}, consider q(x), in Q^{1} +_{Q_{0}} Q^{1}. Either there is some y in Q^{1} with q(x) = ν_{1}(y), or else some y with q(x) = ν_{2}(y). In the first case, we then have x = [li, 1]q(x) = li(y); in the second, x = ri(y). Thus any x in Q^{1} is in the image of either l or r, i.e. l and r are jointly covering, hence epi. (Indeed, in the first case x = li(y) = l(il)i(y) = li(li(y)) = li(x), and in the second, x = ri(x).)

Restating this diagrammatically: Q^{1} +_{Q^{0}} Q^{1} is the union of the subobjects ν_{j} : Q^{1} → Q^{1} +_{Q^{0}} Q^{1}, so Q^{1} is the union of the subobjects m_{j} = q^{∗}(ν_{j}):

\xymatrix{P_{j} \ar[r]^{q_{j}} \ar[d]^{m_{j}} & Q^{1} \ar[d]^{ν_{j}} \\ Q^{1} \ar[r]^{q} & Q^{1} +_{Q^{0}} Q^{1}}

So m_{1}, m_{2} are jointly covering. But by the co-unit identities, liq_{1} = [li, 1]ν_{1}q_{1} = [li, 1]qm_{1} = m_{1}, and riq_{2} = m_{2}. Thus liq_{1}, riq_{2} are jointly covering, and hence so are l, r.

Now, we check that any co-preorder is a co-equivalence relation. (We give only the diagrammatic version. Exercise: restate this in the internal logic!) We want to define s : Q^{1} → Q^{1} with sl = r, sr = l. Since l, r are monos with union Q^{1}, the pullback square

\xymatrix{• \ar[r]^{π_{2}} \ar[d]_{π_{1}} & Q^{0} \ar[d]^{r} \\ Q^{0} \ar[r]^{l} & Q^{1}}

is also a pushout, so to construct s as above, it is enough to show that rπ_{1} = lπ_{2}. But π_{1} = ilπ_{1} = irπ_{2} = π_{2}, so rπ_{1} = rπ_{2} = lπ_{1} = lπ_{2}, and we are done.

0.9. Corollary. If E is coherent and has co-kernel pairs of monos, then CoCat (E) ≃ Mono (E). (In particular, this holds if E is a pretopos [Johnstone 2002, A1.4.8].)

Proof. A coherent category is co-effective, so if it has co-kernel pairs, it is co-exact.

0.10. Corollary. For any topos E, CoCat (E) ≃ (E/Ω)_{colax}.

(A colax map (A, φ) → (B, ψ) is a map f : A → B such that φ ≤_{Ω} ψf.)

In particular, inspecting this equivalence, we see that in this case there is a universal internal co-category in E, from which every co-category in E may be obtained uniquely by pullback: it is the co-kernel pair of ⊤ : 1 → Ω.

0.11. Example. The condition that unions are preserved by pullback is crucial: AbGp, for instance, is regular, and has unions, but there is a non-co-preorder co-category corresponding to the interval pictured above, given by the objects

Q^{0} = ⟨v_{0}⟩ Q^{1} = ⟨v_{0}, e_{1}, v_{1}⟩ Q^{1} +_{Q^{0}} Q^{1} = ⟨v_{0}, e_{1}, v_{1}, e_{2}, v_{2}⟩

(with the natural maps making this a pushout), and maps given by the matrices

l = ( \begin{matrix}1 \\ 0 \\ 0 \end{matrix} ) r = ( \begin{matrix}0 \\ 0 \\ 1 \end{matrix} ) i = ( 1 0 1 ) q = ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ) .

This example may be given more structure; it is, for instance, the total space of an natural co-category in Ch(AbGp). Since all the underlying groups are free and of finite rank, dualising by transposing matrices also gives corresponding categories in AbGp and Ch(AbGp).

However, any category in a Mal’cev category is a groupoid (this has been observed by various authors, e.g. in [CKP 1993]), so any co-category in a co-Mal’cev category (e.g. in an Abelian category, or a topos [Bourn 1996]) is a co-groupoid.

0.12. Example. An example of a non-co-groupoid co-category is the interval I in Cat, with I^{0} = (·), I^{1} = (· → ·); seen as a co-simplicial object, this is just the usual inclusion functor Δ ↪ PreOrd ↪ Cat.

Indeed, the functor Cat → SSet → SAbGp → Ch(AbGp) → Ch(AbGp) “take nerve; take free abelian groups; normalise to a complex; quotient out by subcomplex generated in degrees ≥ 2” sends I to the co-category in Ch(AbGp) of the previous example.

Co-categories arise as candidate “interval objects” when using 2-categories to model intensional type theory [Awodey, Warren, 2009]. There, one seeks them in categories with some sort of “weakened” logical structure; the present result confirms the suspicion that examples in classical “strict” logical categories are necessarily fairly trivial.

Many thanks are due to Steve Awodey, for originally posing the question of what co-categories could exist in a topos, and Peter Johnstone, for suggesting and improving parts of the proofs.

References

Steve Awodey and Michael A. Warren, Homotopy-theoretic models of identity types, Math. Proc. Cambridge Philos. Soc. 146 (2009), no.1, pp.45–55, arXiv:0709.0248

    [math.LO]

Dominique Bourn, Mal’cev Categories and Fibration of Pointed Obects, Applied Categorical Structures, Vol.4 (1996), pp.307–327

A. Carboni, G.M. Kelly, M.C. Pedicchio Some remarks on Maltsev and Goursat categories, Applied Categorical Structures, Vol.1 (1993), pp.385–421

Peter Johnstone, Sketches of an Elephant: a Topos Theory Compendium, Oxford University Press (2002)

Dept. of Mathematics, Carnegie Mellon University 5000 Forbes Avenue, Pittsburgh PA 15213, U.S.A.

Email: p.l.lumsdaine@dal.ca

This article may be accessed at http://www.tac.mta.ca/tac/ or by anonymous ftp at

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/25/9/25-09.{dvi,ps,pdf}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information Individual subscribers receive abstracts of articles by e-mail as they are published. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors The typesetting language of the journal is TEX, and L^{A}TEX2e strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor Gavin Seal, Ecole Polytechnique Fédérale de Lausanne:

gavin seal@fastmail.fm

Transmitting editors

Clemens Berger, Université de Nice-Sophia Antipolis, cberger@math.unice.fr Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown(at)btinternet.com Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it

Valeria de Paiva: valeria.depaiva@gmail.com

Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Glasgow, Tom.Leinster@glasgow.ac.uk Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca