. 58
( 60 .)



e f

9.4 Free Triples 315
Proof. Begin with f0 = f . Let f1 : C1 ’ B be de¬ned using the de¬ning property

of a sum by f1 —¦ e0 = f and f1 —¦ c1 = b —¦ Rf . We will de¬ne fn for n ≥ 1 inductively;
notice that after f1 we are using a pushout rather than a sum, so our induction
hypothesis will have to carry with it a commutativity condition.
So assume that f0 , · · · , fn have been de¬ned in such a way that
(a) fi : Ci ’ B;

(b) fi —¦ ci = b —¦ Rfi’1 ; and
(c) fi —¦ ei’1 = fi’1 .

Then b —¦ Rfi —¦ Rei’l = b —¦ Rfi’1 , so we can legitimately de¬ne fi+1 by requiring
that fi+1 —¦ ci+1 = b —¦ Rfi and fi+1 —¦ ei = fi . The induced map f then clearly
satis¬es the required identities.
By Lemma 8, the objects (C , c : RC ’ C ) form a solution set for the un-

derlying functor U : (R: C ) ’ C , which therefore has a left adjoint as required.

Exercises 9.4

1. Prove that if C is a category with countable sums and R an endofunctor which
preserves countable sums, then R generates a free triple.

2. (Lambek)
(i) Let R be an endofunctor of a category C . Show that if a: RA ’ A is an

initial object in (R: C ), then a is an isomorphism.
(ii) Prove that an endofunctor which has no ¬xed points does not generate a
free triple.
(iii) Prove that the covariant power set functor which takes a map to its direct
image does not generate a free triple.

3. Formulate and prove a trans¬nite generalization of Theorem 7 analogous to
the way in which Exercise 2 of Section 9.3 generalizes Theorem 8 of that section.

J. Ad´mek and J. Rosiˇky, Locally Presentable and Accessible Categories. Cam-
a c
bridge University Press (1994).
H. Applegate, Categories with models. Dissertation, Columbia University (1965).
H. Applegate and M. Tierney, Categories with models. Springer Lecture Notes
in Mathematics 80, 156-243 (1969).
M. Barr, Exact categories, in Exact Categories and Categories of Sheaves,
Springer Lecture Notes in Mathematics 236, 1-120. 1971.
M. Barr, Toposes without points. J. Pure and Applied Algebra 5, 265-280 (1974).
M. Barr, Coequalizers and free triples. Math. Z. 116 (1970), 307-322.
M. Barr, J. Beck, Homology and standard constructions, in Seminar on Triples
and Categorical Homology Theory. Springer Lecture Notes in Math. 80
(1969), 245-335.
M. Barr, R. Diaconescu, Atomic Toposes. J. Pure Applied Algebra, 17 (1980),
M. Barr, R. Par´, Molecular Toposes. J. Pure Applied Algebra, 17 (1980), 127-
M. Barr and C. Wells, Category Theory for Computing Science, 3rd Edition. Les
Publications CRM (1999).
A. Bastiani and C. Ehresmann, Categories of sketched structures. Cahiers de
Topologie et G´ometrie Di¬´rentielle 13 (1973), 1-105.
e e
J. M. Beck, Triples, Algebras, and Cohomology. Ph. D. Thesis, Columbia Uni-
versity (1967).
J. B´nabou, Structures alg´briques dans les cat´gories. Cahiers de Topologie et
e e e
G´ometrie Di¬´rentielle 10 (1968), 1-126.
e e
J. B´nabou, Structures alg´briques dans les cat´gories. Cahiers de Topologie et
e e e
G´ometrie Di¬´rentielle 13 (1972), 103-214.
e e
G. Birkho¬, On the structure of abstract algebras. Proc. Cambridge Phil. Soc.
31 (1935), 433-454.

318 References
A. Blass, The interaction between category theory and set theory. Preprint, Uni-
versity of Michigan (1983).
A. Boileau and A. Joyal, La logique des topos. J. Symbolic Logic 46 (1981), 6-16.
F. Borceux, Handbook of Categorical Algebra I, II and III. Cambridge University
Press (1994).
M. C. Bunge, Toposes in logic and logic in toposes. (To appear, Proc. of the
meeting of the Soc. for Exact Philosophy, April, 1983.)
H. Cartan and S. Eilenberg, Homological Algebra. Princeton University Press,
C. C. Chang and H. J. Keisler, Model Theory. North-Holland, 1973.
P. M. Cohn, Universal Algebra. D. Reidel Publishing Company, 1982.
A. Day, Filter monads, continuous lattices and closure systems. Canadian J.
Math. 27 (1975), 50-59.
B. Day, Note on the Stone representation theorem.
P. Deligne, La conjecture de Weil I. I. H. E. S. Publ. Math. 43 (1974), 273-307.
R. Diaconescu, Axiom of choice and complementation. Proc. Amer. Math. Soc.
51 (1975), 176-178.
R. Diaconescu, Change of base for toposes with generators. J. Pure Applied Al-
gebra 6 (1975), 191-218.
E. Dubuc and G. M. Kelly, A presentation of topoi as algebraic relative to cate-
gories or graphs.
J. Duskin, Variations on Beck™s tripleability criterion. Springer Lecture Notes in
Mathematics 106, 74-129 (1969).
B. Eckmann and P. Hilton, Group-like structures in general categories. Math.
Ann. 145 (1962), 227.
C. Ehresmann, Introduction to the theory of structured categories. Charles
Ehresmann, “uvres compl`tes et comment´es III, 2, 591-676. (Noted by V.
e e
C. Ehresmann, Probl`mes universels relatifs aux cat´gories n-aires. C.R.A.S. 264
e e
(273-276), 1967a.
C. Ehresmann, Sur les structures alg´briques. C.R.A.S. 264 (840-843), 1967b.
C. Ehresmann, Esquisses et types de structures alg´briques. Bul. Inst. Polit. Ia¸i
e s
t. XIV(XVIII), Fasc. 1-2 (1968), 1-14. Reprinted in ’uvres compl`tes et
comment´es IV, 1, 19-33.
S. Eilenberg and S. MacLane, General theory of natural equivalences. Trans. A.
M. S. 58, 1945, 231-244.
References 319
S. Eilenberg and J. C. Moore, Adjoint functors and triples, Illinois J. Math. 9,
381-398 (1965).
G. D. Findlay, Re¬‚exive homomorphic relations. Can. Math. Bull. 3 (1960), 131-
M. Fourman, The logic of topoi, in Handbook of Mathematical Logic, J. Barwise,
ed. North-Holland, 1977.
P. Freyd, Abelian Categories: An introduction to the theory of functors. Harper
and Row, 1964.
P. Freyd, Several new concepts: lucid and concordant functors, pre-limits, pre-
completeness, the continuous and concordant completions of categories. In
Category theory, homology theory and their applications III: Proceedings of
the Batelle Institute Conference, Seattle, 1968. Springer Lecture Notes in
Mathematics 99 (1969), 196-241.
P. Freyd, Aspects of topoi. Bull. Austral. Math. Soc. 7 (1972), 1-72 and 467-480.
Corrections (preprint), 1973.
P. Freyd and A. Scedrov, Categories, Allegories. North-Holland Mathematical
Library 39. North-Holland (1990).
P. Gabriel and F. Ulmer, Lokal pr¨sentierbare Kategorien, Springer Lecture Notes
in Mathematics 221. Springer-Verlag, 1971.
R. Godement, Th´orie des faisceaux. Hermann (1958).
J. Goguen, J. Meseguer, An initiality primer. Preprint, (1983a), SRI Interna-
tional, Computer Science Laboratory, 333 Ravenswood Ave., Menlo Park,
CA, USA, 94025.
J. Goguen, J. Meseguer, Completeness of many-sorted equational logic. To ap-
pear in Houston J. Math. (1983b).
A. Grothendieck, Sur quelques points d™alg`bre homologique, Tohˆku Math. Jour-
e o
nal 2, 1957, 119-221.
A. Grothendieck, Cohomologie ´tale des sch´mas. Seminaire de G´ometrie
e e e
Alg´brique de L™I. H. E. S. 1964.
A. Grothendieck, J. L. Verdier, Th´orie des topos. in SGA 4 Expos´s I-VI (1963-
e e
4), reprinted in Springer Lecture Notes in Math. 269-270 (1972).
J. W. Gray, Formal Category I: Adjointness for 2-Categories. Springer Lecture
Notes in Math. 391 (1974).
P. Huber, Homotopy theory in general categories. Math. Ann. 144, 361-385
J. R. Isbell, General functorial semantics. (You must have this reference in your
320 References
P. T. Johnstone, Topos Theory. Academic Press, 1977.
P. T. Johnstone, G. Wraith, Algebraic theories in toposes, in Indexed Categories
and their Applications, Springer Lecture Notes in Mathematics 661 (1978).
D. M. Kan, Adjoint functors. Trans. A. M. S. 87, 1958, 294-329.
G. M. Kelly, On the essentially-algebraic theory generated by a sketch. Bulletin
Australian Mathematical Society 26 (1982), 45-56.
G. M. Kelly, A uni¬ed treatment of trans¬nite constructions for free algebras,
free monoids, colimits, associated sheaves, and so on. Bulletin Australian
Mathematical Society 22 (1980), 1-83.
J. F. Kennison, On limit-preserving functors. Illinois Jour. Math. 12, 616-619
J. F. Kennison and D. Gildenhuys, Equational completion, model induced triples
and pro-objects. J. Pure Applied Algebra 1 (1971), 317-346.
H. Kleisli, Comparaison de la r´solution simpliciale ` la bar-r´solution. in
e a e
Cat´gories Non-Ab´liennes, L™Universit´ de Montr´al (1964), 85-99.
e e e e
H. Kleisli, Every standard construction is induced by a pair of adjoint functors.
Proc. A. M. S. 16, 544-546 (1965).
A. Kock and G. E. Reyes, Doctrines in categorical logic. In Handbook of Math-
ematical Logic, J. Barwise, editor. North-Holland, 1977.
Anders Kock, Synthetic Di¬erential Geometry. London Mathematical Society
Lecture Note Series 51. Cambridge University Press, 1981.
A. Kock and G. Wraith, Elementary toposes. Aarhus Lecture Notes 30, 1971.
J. Lambek and P. Scott, Introduction to higher-order categorical logic. Cam-
bridge Studies in Advanced Mathematics 7. Cambridge University Press
F. W. Lawvere, Functorial semantics of algebraic theories. Dissertation, Columbia
University (1963). Announcement in Proc. Nat. Acad. Sci. 50 (1963), 869-
F. W. Lawvere, An elementary theory of the category of sets. Preprint (1965).
F. W. Lawvere, The category of categories as a foundation for mathematics. Pro-
ceedings of the Conference on Categorical Algebra at La Jolla. Springer-
Verlag (1966).
F. W. Lawvere, Quanti¬ers and sheaves. Actes du Congr`s International des
Math´maticiens, Nice (1970), 329-334.
F. W. Lawvere, Continuously variable sets: algebraic geometry = geometric logic.
Proc. A. S. L. Logic Colloquium, Bristol, 1973. North-Holland (1975),135-
References 321
F. W. Lawvere, Introduction. Toposes, Algebraic Geometry and Logic. Springer
Lecture Notes in Math. 445 (1975), 3-14.
F. W. Lawvere, Variable sets, ´tendu, and variable structures in topoi (Notes by
S. E. Landsburg), Lecture Notes, University of Chicago (1976).
F. W. Lawvere, Variable quantities and variable structures in topoi. in Algebra,
Topology and Category Theory: a collection of papers in honor of Samuel
Eilenberg. Academic Press (1976), 101-131.
F. E. J. Linton, Some aspects of equational categories. Proceedings of the Con-
ference on Categorical Algebra at La Jolla. Springer-Verlag (1966).
F. E. J. Linton, An outline of functorial semantics, Springer Lecture Notes in
Mathematics 80, 7-52 (1969a).
F. E. J. Linton, Applied functorial semantics, Springer Lecture Notes in Mathe-
matics 80, 53-74 (1969b).
F. E. J. Linton, Coequalizers in categories of algebras, Springer Lecture Notes in
Mathematics 80, 75-90 (1969c).
S. Mac Lane, Duality for groups. Bull. A. M. S. 56, 1950, 485-516.
S. Mac Lane, Categories for the Working Mathematician 2nd Edition. Springer-
Verlag, 1998.
S. Mac Lane and I. Moerdijk, Sheaves in Geometry and Logic. Springer-Verlag
A. I. Mal™cev, On the general theory of algebraic systems. Math. Sbornik, N. S.
35 (1954). 3-20.
M. Makkai and G. Reyes, First Order Categorical Logic. Lecture Notes in Math-
ematics 611. Sringer-Verlag, 1977.
C. McLarty, Elementary Categories, Elementary Toposes. Oxford Logic Guides
21. Clarendon Press (1992).
C. J. Mikkelsen, Lattice Theoretic and Logical Aspects of Elementary Topoi.
Aarhus University Various Publications Series 25, 1976.
B. Mitchell, The full embedding theorem. Amer. J. Math. 86, 1964, 619-637.
B. Mitchell, Theory of Categories. Academic Press, 1965.
P. Mulry, Generalized Banach-Mazur functionals in the topos of recursive sets.
J. Pure Applied Algebra, 26 (1982), 71-83.
G. Osius, Categorial set theory: a characterization of the category of sets. J.
Pure Applied Algebra, 4 (1974), 79“119.
G. Osius, Logical and set theoretical tools in elementary topoi. Model Theory
and Topoi, Lecture Notes in Mathematics 445 (1975), 297“346.
322 References
R. Par´, Connected components and colimits, J. Pure Applied Algebra, 3 (1973),
R. Par´, D. Schumacher, Abstract families and the adjoint functor theorem, in
Indexed Categories and their Applications, Springer Lecture Notes in Math-
ematics 661 (1978).
J. Peake and G. R. Peters, Extensions of algebraic theories. Prof. A. M. S. 32
(1972), 356-362.
H. Rasiowa and R. Sikorski, The Mathematics of Metamathematics. Polish Sci-
enti¬c Publishers, Warsaw (1963).
G. Reyes, From sheaves to logic. In Studies in Algebraic Logic, A. Daigneault,
ed. MAA Studies in Math., 9, Mathematical Association of America, l974.
R. Rosebrugh, On algebras de¬ned by operations and equations in a topos. J.
Pure and Applied Algebra 17 (1980), 203-221.
J. Shoen¬eld, Mathematical Logic. Addison-Wesley, 1967.
R. Street, Notions of topos. Bull. Australian Math. Soc. 23 (1981), 199-208.
R. Street, The family approach to total cocompleteness and toposes, Reprint,
School of Mathematics and Physics, McQuarrie University, North Ryde,
NSW 2113, Australia (1983).


. 58
( 60 .)