FUNCTORIAL SEMANTICS

OF

ALGEBRAIC THEORIES

AND

SOME ALGEBRAIC PROBLEMS IN THE CONTEXT OF FUNCTORIAL SEMANTICS OF

ALGEBRAIC THEORIES

F. WILLIAM LAWVERE

\begin{matrix}c \\ ◯ \end{matrix} F. William Lawvere, 1963, 1968. Permission to copy for private use granted.

Contents

A Author’s comments 6

1 Seven ideas introduced in the 1963 thesis . . . . . . . . . . . . . . . . . . . 8 2 Delays and Developments . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Comments on the chapters of the 1963 Thesis . . . . . . . . . . . . . . . . 10 4 Some developments related to the problem list in the 1968 Article . . . . . 17 5 Concerning Notation and Terminology . . . . . . . . . . . . . . . . . . . . 18 6 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

References 20

B Functorial Semantics of Algebraic Theories 23

Introduction 24

I The category of categories and adjoint functors 26 1 The category of categories . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2 Adjoint functors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3 Regular epimorphisms and monomorphisms . . . . . . . . . . . . . . . . . 58

II Algebraic theories 61 1 The category of algebraic theories . . . . . . . . . . . . . . . . . . . . . . . 61 2 Presentations of algebraic theories . . . . . . . . . . . . . . . . . . . . . . . 69

III Algebraic categories 74 1 Semantics as a coadjoint functor . . . . . . . . . . . . . . . . . . . . . . . . 74 2 Characterization of algebraic categories . . . . . . . . . . . . . . . . . . . . 81

IV Algebraic functors 90 1 The algebra engendered by a prealgebra . . . . . . . . . . . . . . . . . . . 90 2 Algebraic functors and their adjoints . . . . . . . . . . . . . . . . . . . . . 93 V Certain 0-ary and unary extensions of algebraic theories 97

1 Presentations of algebras: polynomial algebras . . . . . . . . . . . . . . . . 97 2 Monoids of operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 3 Rings of operators (Theories of categories of modules) . . . . . . . . . . . . 105

References 106

C Some Algebraic Problems in the context of Functorial Semantics of Algebraic Theories 108

1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 2 Methodological remarks and examples . . . . . . . . . . . . . . . . . . . . 112 3 Solved problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 4 Unsolved problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5 Completion problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

References 120

Part A Author’s comments

The 40th anniversary of my doctoral thesis was a theme at the November 2003 Florence meeting on the “Ramifications of Category Theory”. Earlier in 2003 the editors of TAC had determined that the thesis and accompanying problem list should be made available through TAC Reprints. This record delay in the publication of a thesis (and with it a burden of guilt) is finally coming to an end. The saga began when in January 1960, having made some initial discoveries (based on reading Kelley and Godement) such as adjoints to inclusions (which I called “inductive improvements”) and fibered categories (which I called “galactic clusters” in an extension of Kelley’s colorful terminology), I bade farewell to Professor Truesdell in Bloomington and traveled to New York. My dream, that direct axiomatization of the category of categories would help in overcoming alleged settheoretic difficulties, was naturally met with skepticism by Professor Eilenberg when I arrived (and also by Professor Mac Lane when he visited Columbia). However, the continuing patience of those and other professors such as Dold and Mendelsohn, and instructors such as Bass, Freyd, and Gray allowed me to deepen my knowledge and love for algebra and logic. Professor Eilenberg even agreed to an informal leave which turned out to mean that I spent more of my graduate student years in Berkeley and Los Angeles than in New York. My stay in Berkeley tempered the naive presumption that an important preparation for work in the foundations of continuum mechanics would be to join the community whose stated goal was the foundations of mathematics. But apart from a few inappropriate notational habits, my main acquisition from the Berkeley sojourn was a more profound acquaintance with the problems and accomplishments of 20th century logic, thanks again to the remarkable patience and tolerance of professors such as Craig, Feferman, Scott, Tarski, and Vaught. Patience began to run out when in February 1963, wanting very much to get out of my Los Angeles job in a Vietnam war “think” tank to take up a teaching position at Reed College, I asked Professor Eilenberg for a letter of recommendation. His very brief reply was that the request from Reed would go into his waste basket unless my series of abstracts be terminated post haste and replaced by an actual thesis. This tough love had the desired effect within a few weeks, turning the tables, for it was now he who had the obligation of reading a 120-page paper of baroque notation and writing style. (Saunders Mac Lane, the outside reader, gave the initial approval and the defence took place in Hamilton Hall in May 1963.) The hasty preparation had made adequate proofreading difficult; indeed a couple of lines (dealing with the relation between expressible and definable constants) were omitted from the circulated version, causing consternation and disgust among universal algebraists who tried to read the work. Only in the new millennium did I discover in my mother’s attic the original handwritten draft, so that now those lines can finally be restored. Hopefully other obscure points will be clarified by this actual publication, for which I express my gratitude to Mike Barr, Bob Rosebrugh, and all the other editors of TAC, as well as to Springer-Verlag who kindly consented to the republication of the 1968 article.

1. Seven ideas introduced in the 1963 thesis

(1) The category of categories is an accurate and useful framework for algebra, geometry, analysis, and logic, therefore its key features need to be made explicit.

(2) The construction of the category whose objects are maps from a value of one given functor to a value of another given functor makes possible an elementary treatment of adjointness free of smallness concerns and also helps to make explicit both the existence theorem for adjoints and the calculation of the specific class of adjoints known as Kan extensions.

(3) Algebras (and other structures, models, etc.) are actually functors to a background category from a category which abstractly concentrates the essence of a certain general concept of algebra, and indeed homomorphisms are nothing but natural transformations between such functors. Categories of algebras are very special, and explicit axiomatic characterizations of them can be found, thus providing a general guide to the special features of construction in algebra.

(4) The Kan extensions themselves are the key ingredient in the unification of a large class of universal constructions in algebra (as in [Chevalley, 1956]).

(5) The dialectical contrast between presentations of abstract concepts and the abstract concepts themselves, as also the contrast between word problems and groups, polynomial calculations and rings, etc. can be expressed as an explicit construction of a new adjoint functor out of any given adjoint functor. Since in practice many abstract concepts (and algebras) arise by means other than presentations, it is more accurate to apply the term “theory”, not to the presentations as had become traditional in formalist logic, but rather to the more invariant abstract concepts themselves which serve a pivotal role, both in their connection with the syntax of presentations, as well as with the semantics of representations.

(6) The leap from particular phenomenon to general concept, as in the leap from cohomology functors on spaces to the concept of cohomology operations, can be analyzed as a procedure meaningful in a great variety of contexts and involving functorality and naturality, a procedure actually determined as the adjoint to semantics and called extraction of “structure” (in the general rather than the particular sense of the word).

(7) The tools implicit in (1)–(6) constitute a “universal algebra” which should not only be polished for its own sake but more importantly should be applied both to constructing more pedagogically effective unifications of ongoing developments of classical algebra, and to guiding of future mathematical research.

In 1968 the idea summarized in (7) was elaborated in a list of solved and unsolved problems, which is also being reproduced here.

2. Delays and Developments

The 1963 acceptance of my Columbia University doctoral dissertation included the condition that it not be published until certain revisions were made. I never learned what exactly those revisions were supposed to be. Four years later, at the 1967 AMS Summer meeting in Toronto, Sammy had thoroughly assimilated the concepts and results of Functorial Semantics of Algebraic Theories and had carried them much further; one of his four colloquium lectures at that meeting was devoted to new results in that area found in collaboration with [Eilenberg & Wright, 1967]. In that period of intense advance, not only Eilenberg and Wright, but also [Beck, 1967], [Bénabou, 1968], [Freyd, 1966], [Isbell, 1964], [Linton, 1965], and others, had made significant contributions. Thus by 1968 it seemed that any publication (beyond my announcements of results [Lawvere, 1963, 1965]) should not only correct my complicated proofs, but should also reflect the state of the art, as well as indicate more systematically the intended applications to classical algebra, algebraic topology, and analysis. A book adequate to that description still has not appeared, but Categories and Functors [Pareigis, 1970] included an elegant first exposition. Ernie Manes’ book called Algebraic Theories, treats mainly the striking advances initiated by Jon Beck, concerning the Godement-Huber-Kleisli notion of standard construction (triple or monad) which at the hands of Beck, [Eilenberg & Moore, 1965], Linton, and Manes himself, had been shown to be intimately related to algebraic theories, at least when the background is the category of abstract sets. Manes’ title reflects the belief, which was current for a few years, that the two doctrines are essentially identical; however, in the less abstract background categories of topology and analysis, both monads and algebraic theories have applications which are complementary, but not identical.

Already in spring 1967, at Chicago, I had identified some of the sought-for links between continuum mechanics and category theory. Developing those would require some concepts from algebraic theories in particular, but moreover, much work on topos theory would be needed. These preoccupations in physics and toposes made it clear, however, that the needed book on algebraic theories would have to be deferred; only a partial summary was presented as an introduction to the 1968 list of generic problems.

The complicated proofs in my thesis of the lemmas and main theorems have been much simplified and streamlined over the past forty years in text and reference books, the most recent [Pedicchio & Rovati, 2004]. This has been possible due to the discovery and employment since 1970 of certain decisive abstract general relations expressed in notions such as regular category, Barr exactness [Barr, 1971], and factorization systems based on the “orthogonality” of epis and monos. However, an excessive reliance on projectives has meant that some general results of this “universal” algebra have remained confined to the abstract-set background where very special features such as the axiom of choice can even trivialize key concepts that would need to be explicit for the full understanding of algebra in more cohesive backgrounds.

Specifically, there is the decisive abstract general relation expressed by the commutativity of reflexive coequalizers and finite products, or in other words, by the fact that the connected components of the product of finitely many reflexive graphs form the product of the corresponding component sets. Only in recent years has it become widely known that this property is essentially characteristic of universal algebra (distinguishing it from the more general finite-limit doctrine treated by [Gabriel & Ulmer, 1971] and also presumably by the legendary lost manuscript of Chevalley). But the relevance of reflexive coequalizers was already pointed out in 1968 by [Linton, 1969], exploited in topos theory by [Johnstone, 1977], attributed a philosophical (i.e. geometrical) role by me [1986], and finally made part of a characterization theorem by [Lair, 1996]. It is the failure of the property for infinite products that complicates the construction of coequalizers in categories of infinitary algebras (even those where free algebras exist). On the other hand, the property holds for algebra in a topos, even a topos which has no projectives and is not “coherent” (finitary). A corollary is that algebraic functors (those induced by morphisms of theories) not only have left adjoints (as proved in this thesis and improved later), but also themselves preserve reflexive coequalizers. The cause for the delay of the general recognition of such a fundamental relationship was not only the reliance on projectives; also playing a role was the fact that several of the categories traditionally considered in algebra have the Mal’cev property (every reflexive subalgebra of a squared algebra is already a congruence relation) and preservation of coequalizers of congruence relations may have seemed a more natural question.

3. Comments on the chapters of the 1963 Thesis

3.1. Chapter I. There are obvious motivations for making explicit the particular features of the category of categories and for considering the result as a guide or framework for developing mathematics. Apart from the contributions of homological algebra and sheaf theory to algebraic topology, algebraic geometry, and functional analysis, and even apart from the obvious remark that category theory is much closer to the common content of all these, than is, say, the iterated membership conception of the von Neumann hierarchical representation of Cantor’s theory, there is the following motivation coming from logical considerations (in the general philosophical sense). Much of mathematics consists in calculating in various abstract theories, specifically interpreting one abstract theory into another, interpreting an abstract theory into a background to obtain a concrete category of structures, and transforming these structures in and among these categories. Now, for one thing, the use of the term “category” of structures of a certain kind had already become obvious in the 1950’s and for another thing the idea of theories themselves as structures whose mutual interpretations would form a category was also evidently possible if one cared to carry it out, and indeed Hall, Halmos, Henkin, Tarski, and possibly others had already made significant moves in that direction. But what of the relation itself between abstract theory and concrete background? To conceptually relate any two things, it is necessary that they belong to a common category; that is, speaking more mathematically, it is first necessary to functorially transport them into a common third category (if indeed they were initially conceived as belonging to different categories); but then if the attempt to relate them is successful, the clearest exposition of the whole matter may involve presenting the two things themselves as citizens of that third category. In the case of “backgrounds” such as a universe of sets or spaces it was already clear that they form categories, wherein the basic structure is composition. In the case of logical theories of all sorts the most basic structure they support is an operation of substitution, which is most effectively viewed as a form of composition. Thus, if we construe theories as categories, models are functors! Miraculously, the Eilenberg-Mac Lane notion of natural transformation between functors specializes exactly to the morphisms of models which had previously been considered for various doctrines of theories. But only for the simplest theories are all functors models, because something more than substitution needs to be preserved; again, miraculously, the additional features of background categories which were often expressible in terms of composition alone via universal mapping properties, turned out to have precise analogs: the operations of disjunction, existential quantification, etc. on a theory are all uniquely determined by the behavior of substitution. Roughly, any collection K of universal properties of the category of sets specifies a doctrine: the theories in the doctrine are all the categories having the properties K; the mutual interpretations and models in the doctrine are just all functors preserving the properties K. The simplest non-trivial doctrine seems to be that of finite categorical products, and the natural setting for the study of it is clear. Thus Chapter I tries to make that setting explicit, with details being left to a later publication [Lawvere, 1966].

Since (any model of a theory of) the category of categories consists of arrows called functors, how are we to get inside the individual categories themselves (and indeed how can we correctly justify calling the arrows functors)? There has been for a long time the persistent myth that objects in a category are “opaque”, that there are only “indirect” ways of “getting inside” them, that for example the objects of a category of sets are “sets without elements”, and so on. The myth seems to be associated with an inherited belief that the only “direct” way to deal with whole/part relations is to write an unexplained epsilon or horseshoe symbol between A and B and to say that A is then “inside” B, even though in any model of such a discourse A and B are distinct elements on an equal footing. In fact, the theory of categories is the most advanced and refined instrument for getting inside objects, because it does provide explanations (existence of factorizations of inclusion maps) and also makes the sort of distinctions that Volterra and others had noted were necessary for the elements of a space (because the elements are morphisms whose domains are various figure-types that are also objects of the category). But there is also a restriction on the wholesale meaningfulness of membership and inclusion, namely that they are meaningless unless both figures A and B under consideration are morphisms with the same codomain. It was the lack of such restriction in the Frege conception that forced Peano to introduce the “singleton” operation and the attendant rigid distinction between membership and inclusion. (A kind of singleton operation does reappear in category theory, but with quite different conception and properties, namely, as a natural transformation from an identity functor to a covariant power-set functor).

The construction in Chapter I (and in [Lawvere, 1966]) of a formula with one more free variable A from any given formula of the basic theory of categories, was a refutation of the above myth. Based on nailed-down descriptions of special objects 1, 2, 3 which serve as domains for the arrows that are the objects, maps, and commutativities in any codomain, this figure-and-incidence analysis is typical of what is possible for many categories of interest. But much more is involved. The analysis of objects as structures of such a kind in a background category of more abstract “underlying” objects is revealed as a possible construction within a category itself (here the category of categories), which is thus “autonomous”. The method is to single out certain trivial or “discrete” objects by the requirement that all figures (whose shape belongs to the designated kind) be constant, and establish an adjunction between the “background” category so defined and the whole ambiance. The assumed exponentiation operation then allows one to associate an interpretation of the whole ambient category into finite diagrams in the background category, with the arrows in the diagrams being induced by the incidence relations, such as, for example, the composition by functors between 3 and 2 in the case of the category of categories.

At any rate, since the whole figure and incidence scheme here is finite (count the order-preserving maps between the ordinals 1,2,3), the proof-theoretic aspect of the problem of axiomatizing a category of categories is at all levels equivalent to that of axiomatizing a category of discrete sets.

The exponentiation operation mentioned above, that is, the ubiquity of functor categories, characterized by adjointness, was perhaps new in the thesis. Kan had defined adjoints and proved their uniqueness, and of course he knew that function spaces, for example in simplicial sets, are right adjoint to binary product. But the method here, and indeed in the whole ensuing categorical logic, is to exploit the uniqueness by using adjointness itself as an axiom [Lawvere, 1969]. The left adjoint characterization (p.19) of the “natural” numbers is another instance of the same principle (I later learned that it is more accurate to attribute it to Dedekind rather than to Peano).

The construction denoted by ( , ) was here introduced for the purpose of a foundational clarification, namely to show that the notion of adjointness is of an elementary character, independent of complications such as the existence, for the codomain categories of given functors, of an actual category (as opposed to a mere metacategory) of sets into which both are enriched (as is often needlessly assumed); of course, enrichment is important when available, but note that notions like monoidal closed category, into which enrichments are considered, are themselves to be described in terms of the elementary adjointness.

The general calculus of adjoints and limits could be presented as based on the ( , ) operation. Note that it may also be helpful to people in other fields who sometimes find the concept of adjointness difficult to swallow. From the simpler idempotent cases of a full reflective subcategory and the dual notion of a full coreflective subcategory, the general case can always be assembled by composing. The third, larger category thus mediating a given adjointness can be universally chosen to be (two equivalent) ( , ) categories, although in particular examples another mediating category may exist.

The ( , ) operation then turned out to be fundamental in computing Kan extensions (i.e. adjoints of induced functors). Unfortunately, I did not suggest a name for the operation, so due to the need for reading it somehow or other, it rather distressingly came to be known by the subjective name “comma category”, even when it came to be also denoted by a vertical arrow in place of the comma. Originally, it had been common to write (A, B) for the set of maps in a given category C from an object A to an object B; since objects are just functors from the category 1 to C, the notation was extended to the case where A and B are arbitrary functors whose domain categories are not necessarily 1 and may also be different. Since it is well justified by naturality to name a category for its objects, the notation Map(A, B) might be appropriate and read “the category of maps from (a value of) A to (a value of) B”; of course, a morphism between two such maps is a pair of morphisms, one in the domain of A and one in the domain of B, which satisfy a commutative square in C. The word “map” is actually sometimes used in this more structured way (i.e. not necessarily just a mere morphism), for example, drawing one-dimensional pictures on two-dimensional surfaces must take place in a category C where both kinds of ingredients can be interpreted.

In the Introduction to the thesis I informally remarked that “no theorem is lost” by replacing the metacategory of all sets by an actual category S of small sets. Of course, (even if S is not taken as the “smallest” inaccessible) many theorems will be gained; some of those theorems might be considered as undue restriction on generality. However, we can always arrange that S not contain any Ulam cardinals (independently of whether such exist in the meta-universe at large) and that yields many theorems of a definitely positive character for mathematics. Often those mathematically positive theorems involve “dualities” between S-valued algebra and S-valued topology (or bornology). For example, consider the contravariant adjoint functor C from topological spaces to real algebras; the “duality” problem is to describe in topologically meaningful ways which spaces are fixed under the adjunction. That all metric spaces X (or even all discrete spaces) should be so fixed (in the sense that X → spec(C(X)) is a homeomorphism) is equivalent to the fact that S contains no Ulam cardinals. The existence of Ulam cardinals is equivalent to the failure of such duality in the simple case which opposes discrete spaces (i.e. S itself) to the unary algebraic category of left M-sets where M is the monoid of endomaps of any fixed countable set [Isbell, 1964].

3.2. Chapter II. There are several possible doctrines of algebraic theories, even within the very particular conception of “general” algebra that is anchored in the notion of finite categorical product. The most basic doctrine simply admits that any small category with products can serve as a theory, for example any chosen such small subcategory of a given large geometric or algebraic category. This realization required a certain conceptual leap, because such theories do not come equipped with a syntactical presentation, although finding and using presentations for them can be a useful auxiliary to the study of representations (algebras). Here a presentation would involve a directed graph with specified classes of diagrams and cones destined to become commutative diagrams and product cones in the intended interpretations in other theories or interpretations as algebras; this is an instance of the flexible notion of sketch due to Ehresmann. The algebras according to this general doctrine have no preferred underlying sets (which does not prevent them from enjoying nearly all properties and subtleties needed or commonly considered in algebra) and hence no preferred notion of free algebra, although the opposite of the theory itself provides via Yoneda a small adequate subcategory of regular projectives in the category of algebras.

Intermediate between the sketches and the theories themselves is another kind of presentation (but this one lacks the fully syntactical flavor usually associated with a notion of presentation): actual small categories equipped with a class of cones destined to become product cones. This rests on the fact that the free category with finite products generated by any given small category exists. Due to that remark the inclusion of algebras into prealgebras (IV.1.1) is itself an example of an algebraic functor, so that its left adjoint is a special case of a general result concerning algebraic adjoints.

The general doctrine of products permits a kind of flexibility in exposition whereby not only can free algebras always be studied in terms of free theories (by adjoining constants as in V.1) and free theories can be reciprocally reduced to the consideration of initial algebras in suitable categories, but moreover all S-sorted theories (for fixed S) are themselves algebras for one fixed theory. Apart from such generalities, perhaps the most useful feature of this doctrine is that it involves the broadest notion of algebraic functor (since a morphism of theories is any product-preserving functor) and that all these still have left adjoints (while themselves preserving reflexive coequalizers). Examples of these are treated in this basically single-sorted thesis as “algebraic functors of higher degree” (IV.2).

For a doctrine of sorted theories and of algebras with underlying “sets”, one needs the further structure consisting of a fixed theory S and a given interpretation of S into the theory being studied; when the theory changes, the change is required to preserve these given interpretations. Then any algebraic category according to this doctrine will be equipped automatically with an underlying (i.e. evaluation) functor to the category of S-algebras. The left adjoint to this underlying functor provides the notion of free algebras. Also the whole semantical process has an adjoint which to almost any functor from almost any category X to the category of S-algebras assigns its unique “structure”, the best approximation to X in the abstract world of S-sorted theories; the adjunction X → sem(strX) is a sort of closure: “the particular included in the induced concrete general”.

Note that there is a slip in Proposition II.1.1 because the underlying functor from Ssorted theories to theories does not preserve coproducts; of course it does permit their construction in terms of pushouts (“comeets”) so that all intended applications are correct (compare V.1).

With the general notion of S-sorted theory discussed above, the free algebras will not be adequate nor will the underlying functor be faithful without some normalization, usually taken to be that the functor A from S to the theory be bijective on objects.

In fact, the theory “is” the functor A and not merely its codomain category. This remains true even in the single-sorted case, on which I chose to concentrate in an attempt to make contact with the work of the universal algebra community. Here S is taken as the opposite of the category of finite sets, and A(n) is the n-fold product of A(1), with the maps π_{i} = A(i) for 1 → n as projections, often abbreviated to A(n) = A^{n}. The further “abuse of notation” (II.1.Def) which omits the functor A entirely has been followed in most subsequent expositions even though it can lead to confusion when (as in a famous example studied by Jonsson, Tarski and Freyd) the specific theory involves operations which make A(2) isomorphic to A(1). Actually, it seems appropriate in the sorted doctrine (as opposed to the unsorted one) to have a uniform source not only for the meaning of A(i), but also of A(s) where s is the involution of a 2-element set.

The discussion of presentations of theories with fixed sorting is entirely parallel to that for presentations of algebras for a fixed theory, because both are special cases of a general construction that applies to any given adjoint pair of functors. In the present case the underlying functor from single-sorted theories to sequences of sets, called “signatures”, has a left adjoint yielding the free theory generated by any given signature (of course the underlying “signature” of that resulting theory is much larger than the given signature). Given such an adjoint pair, the associated category of presentations has as objects quadruples G, E , l, r in the lower category (codomain of the right adjoint) where l and r are morphisms from E to T (G), where T is the monad resulting from composing the adjoints. Note that in the case at hand, E is also a signature, whose elements serve as names for laws rather than for basic operations as in G. Each such (name for a) basic equation has a left hand side and a right hand side, specified by l and r. The act of presentation itself is a functor (when the upper category has coequalizers) from the category of presentations: it consists of first applying the given adjointness to transform the pair l, r into a coequalizer datum in the upper category, and then forming that coequalizer. If the given adjoint pair is monadic, every object will have presentations, for example the “standard” one obtained by iterating the comonad. The full standard presentation is usually considered too unwieldy for practical (as opposed to theoretical) calculation, but it does have one feature sometimes used in smaller presentations: every equation name e is mapped by l to a generating symbol in G (only a small part of T (G)) and the equation merely defines that symbol as some polynomial r(e) in the generating symbols; in other words, all information resides in the fact that those special generators may have more than one definition. That asymmetry contrasts with the traditional presentations [Duskin, 1969] in the spirit that Hilbert associated with syzygies; there one might as well assume that E is equipped with an involution interchanging l and r, because E typically arises as the kernel pair of a free covering by G of some algebra; the resolution can always be continued, further analyzing the presentation, by choosing a free covering (perhaps minimal) of the free algebra on E itself, then taking the kernel pair of the composites, etc. But another mild additional structure which could be assumed for presentations (and resolutions) is reflexivity, in the sense that there is a given map G → E which followed by l, r assures that there be for each generating symbol an explicit proof that it is equal to itself. That seeming banality may be important in view of the now-understood role of reflexivity, not only in combinatorial topology [Lawvere, 1986], but especially in key distinguishing properties of universal algebra itself [Lair, 1996, Pedicchio & Rovati, 2004].

3.3. Chapter III. As remarked already, the main “mathematical” theorem characterizing algebraic categories now has much more streamlined proofs [Pedicchio & Rovati, 2004], embedding it in a system of decisive concepts. It is to be hoped that future expositions will not only make more explicit the key role of reflexive coequalizers, but also relativize or eliminate the dominating role of projectives in order to fully address as “algebraic” the algebraic structures in sheaf toposes, as [Grothendieck, 1957] already did 45 years ago for the linear case.

But the other main result, that semantics has an adjoint called “structure” with a very general domain, appears as a kind of philosophical theorem in a soft mathematical guise. Indeed, that is one aspect, but note that the motivating example was cohomology operations, and that highly non-tautological examples continue to be discovered. Of course if a functor is representable, Yoneda’s lemma reduces the calculation of its structure to an internal calculation. In general the calculation of the structure of a non-representable functor seems to be hopelessly difficult, however the brilliant construction by Eilenberg and Mac Lane of representing spaces for cohomology in the Hurewicz homotopy category (it is not representable, of course, in the original continuous category) not only paved the way for calculating cohomology operations but illustrated the importance of changing categories. Another more recent discovery by [Schanuel, 1982] provides an astonishing example of the concreteness of the algebraic structure of a non-representable functor, which however has not yet been exploited sufficiently in analysis and “noncommutative geometry”. Namely the underlying-bornological-set functor on the category of finite dimensional noncommutative complex algebras has as its unary structure precisely the monoid of entire holomorphic functions. The higher part of the structure is a natural notion of analytic function of several noncommuting variables, and holomorphy on a given domain is also an example of this natural structure. Moreover, a parallel example involving special finite-dimensional noncommutative real algebras leads in the same way to C^{∞} functions.

3.4. Chapter IV. The calculus of algebraic functors and their adjoints is at least as important in practice as the algebraic categories themselves. Thus it is unfortunate that there was no indication of the fundamental fact that these functors preserve reflexive coequalizers (of course their preservation of filtered colimits has always been implicit). As remarked above, “the algebra engendered by a prealgebra” is a special case of an adjoint to a (generalized) algebraic functor. However, contrary to what might be suggested by the treatment in this chapter, the use of that reflection is not a necessary supplement to the use of Kan extensions in proving the general existence of algebraic adjoints: as remarked only later by Michel André, Jean Bénabou, Hugo Volger, and others, the special exactness properties of the background category of sets imply that the left Kan extension, along any morphism of algebraic theories, of any algebra in sets, is already itself again product-preserving. Clearly, the same sort of thing holds, for example, with any topos as background. On the other hand, this chapter could be viewed as an outline of a proof that such adjoints to induced functors should at least exist even for algebras in backgrounds which are complete but poor in exactness properties,

4. Some developments related to the problem list in the 1968 Article

4.1. 1968 Section 4. Problem 2. [Wraith, 1970] made considerable progress on the understanding of which algebraic functors have right adjoints by pointing out that they all involve extensions by new unary operators only. He also gave a general framework for understanding which kinds of identities could be imposed on such unary operations, while ensuring the existence of the right adjoint. These identities can be of a more general kind than the requirement that the new operators act by endomorphisms of the old ones (as treated in Chapter V of the thesis); an important example of such an identity is the Leibniz product rule, the right adjoint functor from commutative algebras to differential algebras being the formation of formal power series in one variable. Such twisted actions in the sense of Wraith are related to what I have called “Galilean monoids” as exemplified by secondorder differential equations [http://www.buffalo.edu/~wlawvere]. Because they always preserve reflexive coequalizers, algebraic functors in our narrow sense will have right adjoints if only they preserve finite coproducts. Problem 3. There are certainly non-linear examples of Frobenius extensions of theories; for example with the theory of a single idempotent, the act of splitting the idempotent serves as both left and right adjoint to the obvious interpretation into the initial theory. See [Kock, 2004] for some interesting applications of Frobenius extensions, which can be viewed dually as spaces carrying a distribution of global support. Problem 4. There has been striking progress by [Zelmanov, 1997] on the restricted Burnside problem. He proved what had been conjectured for over 50 years, in effect that for the theory B(n) of groups of exponent n, the underlying set functor from finite B(n) algebras has a left adjoint, giving rise to a quotient theory R(n) which is usually different from B(n). This raises the question of presenting R(n), i.e. what are the additional identities? As pointed out in the next problem, the structure of finite algebras is typically profinite if the (hom sets of) the theory are not already finite, so this Burnside-Zelmanov phenomenon seems exceptional; but a hope that unary tameness implies tameness for all arities m is realizable in some other contexts, such as modern extensions of real algebraic geometry [Van den Dries, 1998]. Problem 5. Embedding theorems of the type sought here have a long history in algebra and elsewhere. In earlier work it was not always distinguished that there are two separate issues, the existence of the relevant adjoint and the injectivity of the adjunction map to it. Here in this narrowly algebraic context, the answer to the first question is always affirmative, but the second question remains very much dependent on the particular case. It is remarkable that a kind of general solution has been found by [MacDonald & Sobral, 2004]. Naturally, considerable insight is required in order to apply their criterion, thus I still do not know the answer to the Wronskian question posed at the end of Section 2. Geometrically, that question is: given a Lie algebra L, whether a sufficiently complicated vector field on a sufficiently high-dimensional variety can be found so that L can be faithfully represented by commutators of those very special vector fields which are in the module (over the ring of functions) generated by that particular one. Schanuel has pointed out that the question depends on the ground field, because with complex scalars the rotation group in three dimensions can indeed be so represented. Problem 6. Although the use of the bar notation suggests averaging, naturality of it was omitted from mention here. If naturality were included, possibly a suitable Maschke-like class of examples of this analog of Artinian semi-simplicity could be characterized in terms of a central idempotent operation.

4.2. 1968 Section 5. While problems involving the combination of the structuresemantics adjoint pair with the restriction to the finite may indeed be of interest in connection with the general problems of the Burnside-Kurosh type, few works in that sense have appeared, although for example the fact that one thus encounters theories enriched in the category of compact spaces has been remarked. But quite striking, as remarked before, is Schanuel’s result that by combining the finite dimensionality with non-commutativity and bornology, the naturality construction, which here achieved merely the formal Taylor fields, captures in its amended form precisely the hoped-for ring of entire functions.

5. Concerning Notation and Terminology

In order to ease the burden of those 21st century readers who may try to read these documents in detail, let me point out some of the more frequent terminological and notational anachronisms. The order of writing compositions, which we learned from the stalwart Birkhoff-Mac Lane text, was seriously championed for most of the 1960’s by Freyd, Beck and me (at least) because of the belief that it was more harmonious with the reading of diagrams. More recently it has also been urged by some computer scientists. However, the experience of teaching large numbers of students, most of whose courses are with mathematical scientists following the opposite convention, gradually persuaded us that there are other points within the great weight of mathematical tradition where reforms might be more efficiently advocated. (I personally take great comfort in Steve Schanuel’s remark that there is a rational way to read the formulas that is compatible with the diagrams: gf is read “g following f”.)

Some anachronisms are due to the fact the thesis was written before the partial standardization of the “co-” terminology at the 1965 La Jolla meeting: because we could not agree there on whether it is adjoints or co-adjoints that are the left adjoints, the “co-” prefix largely disappeared (from the word adjoint) and Kan’s original left vs. right has been retained in that particular context.

Not exactly anachronistic, but not yet standard either, is my use of the term “congruence relation” for a graph which is the kernel pair of at least one map, in other words, for an “effective equivalence relation”; this definition raises the question of characterizing congruence relations in other terms, that is, in terms of maps in, rather than maps out, and of course the expected four clauses MRST suffice in the simple abstract backgrounds considered here, as well as in others; these are some of the relationships made partially explicit by Barr exactness.

The musical notation “flat” for the algebraic functor induced by a given morphism of theories occurs in print, as far as I know, only in the 1968 paper reprinted here. It was taken from Eilenberg’s 1967 AMS Colloquium Lectures.

There was a traditional fuzziness in logic between presentations of theories and the sort of structures that I call theories. Unfortunately, in my attempt to sharpen that distinction in order to clarify the mutual transformation and rules of its aspects, I fell notationally afoul of one of the relics of the fuzziness. That is, while affirming that arities are sets, not ordinal numbers, and in particular, that the role of the “variables” in those sets is to parameterize projection maps, I inconsistently followed the logicians’ tradition of writing such parameterizations as though the domains were ordinals. Such orderings are often indispensable in working with presentations of theories (or of algebras, for example using Gröbner bases) but they are spurious structure relative to the algebras or theories themselves. (Not only arities, but sets of operation symbols occurring in a presentation, have no intrinsic ordering: for example, the notion of a homomorphism between two rings is well defined because the same symbols, for plus and for times, are interpreted in both domain and codomain; this has nothing to do with any idea that plus or times comes “first”.)

Finally, there was the choice, which I now view as anachronistic, of considering that an algebraic theory is a category with coproducts rather than with products. The “coproduct” convention, which involves defining algebras themselves as contravariant functors from the theory into the background, indeed did permit viewing the theory itself as a subcategory of the category of models. However, for logics more general than the equational one considered here, such a direct inclusion of a theory into its category of models cannot be expected. The “product” convention permits the concrete definition of models as covariant functors from the theory; thus the theory appears itself as a generic model. Moreover, the “product” convention seems to be more compatible with the way in which algebra of quantities and geometry of figures are opposed. In algebraic geometry, C^{∞} geometry, group invariance geometry, etc. it became clear that there were many potential applications of universal algebra in contexts that do not fit the view that signatures are more basic than clones (i.e. that no examples of algebra exist beyond those whose algebraic theories are given by presentations). In these geometric (equally concrete) examples, the algebraic theories typically arise with products, not coproducts. For example, [see also IV. 1 Example 5] the algebraic theory whose operations are just all smooth maps between Euclidean spaces is not likely to ever find a useful presentation by signatures, yet its category of algebras contains many examples (the function algebras of arbitrary manifolds, formal power series, infinitesimals) that need to be related to each other by the appropriate homomorphisms.

6. Outlook

Let me close these remarks by expressing the wish that the results of universal algebra be more widely and effectively used by algebraists in such fields as operator theory and algebraic geometry (and vice-versa). For example, the Birkhoff theorem on subdirectly irreducible algebras is very helpful in understanding various Nullstellensätze in algebraic geometry (and vice-versa), and this relationship could be made more explicit in the study of Gorenstein algebras or Frobenius algebras. That theorem would also seem to be of use in connection with Lie algebra. Another striking example is the so-called “commutator” theory developed in recent decades, which would seem to have applications in specific categories of mathematical interest such as that of commutative algebra, where a direct geometrical description of the basic operation of forming the product of ideals, without invoking the auxiliary categories of modules, has proven to be elusive.

August 30, 2004

References

M. Barr (1971), Exact Categories, Springer LNM 236, 1–120.

J.M. Beck (1967), Triples, algebras and cohomology, Columbia University, Ph.D. Thesis, first published in Reprints in Theory and Applications of Categories, 2, 2003.

J. Bénabou (1968), Structures algébriques dans les catégories, Cahier de Top. et Géom. Diff., 10, 1–126.

C. Chevalley (1956), Fundamental concepts of algebra. Academic Press, NY.

J. Duskin (1969), Variations on Beck’s tripleability criterion, Springer LNM, 106, 74–129.

S. Eilenberg and J.C. Moore (1965), Adjoint Functors and Triples, Ill. J. Math 9, 381– 965.

S. Eilenberg and J. Wright (1967), Automata in General Algebras. Notes distributed in conjunction with the Colloquium Lectures given at the 72nd AMS Summer Meeting.

References 21

P. Freyd (1966), Algebra-valued functors in general categories and tensor products in par-

ticular, Colloq. Math. 14, 89–106. P. Gabriel and F. Ulmer (1971), Lokal präsentierbare Kategorien, Lecture Notes in Math-

ematics 221, Springer-Verlag, Berlin. A. Grothendieck (1957), Sur quelques points d’algbre homologique. Tohôku Math. J. 9,

119–221. J. Isbell (1964), Subobjects, adequacy, completeness and categories of algebras, Rozprawy

Mat. Soc., 36, 1–32. P.T. Johnstone (1977), Topos Theory, Academic Press, NY. J. Kock (2004), Frobenius Algebras and 2D Topological Quantum Field Theories, London

Mathematical Society, Student Texts 59. C. Lair (1996), Sur le genre d’esquissibilité des catégories modelables (accessibles)

possédant les produits de deux. Diagrammes 35, 25–52. F.W. Lawvere (1963), Functorial semantics of algebraic theories, (summary of Ph.D. the-

sis, Columbia) Proc. National Acad. of Sciences 50, 869–872. F.W. Lawvere (1965), Algebraic theories, algebraic categories, and algebraic functors,

Theory of Models, North-Holland, Amsterdam, 413–418. F.W. Lawvere (1966), The category of categories as a foundation for mathematics, La

Jolla Conference on Categorical Algebra, Springer-Verlag, 1–20. F.W. Lawvere (1969), Adjointness in Foundations, Dialectica 23, 281–296. F.W. Lawvere (1982), Review of P.M. Cohn’s Universal Algebra, 2nd Edition, American

Scientist (May-June) 329. F.W. Lawvere (1986), Categories of spaces may not be generalized spaces, as exemplified

by directed graphs, Revista Colombiana de matemticas XX, 147–178. F.E.J. Linton(1965), Some aspects of equational categories, Proceedings of the Conference

on Categorical Algebra, La Jolla, 84–94. F.E.J. Linton (1969), Coequalizers and categories of algebras, Springer LNM 80, 75–90. J. MacDonald and M. Sobral (2004), Aspects of Monads, Categorical Foundations, ed.

M.C. Pedicchio and W. Tholen, 213–268. B. Mitchell (1965), Theory of Categories, Academic Press. B. Pareigis (1970), Categories and Functors, Academic Press.

M.C. Pedicchio and F. Rovati (2004), Algebraic Categories, Categorical Foundations. M.C. Pedicchio and W. Tholen, eds. Cambridge University Press, 269–310.

S. Schanuel (1982), Continuous extrapolation to triangular matrices characterizes smooth functions, JPAA 24, 59–71.

L. Van den Dries (1998), Tame Topology and O-minimal Structures, London Math Society LNS 248, Cambridge University Press.

G.C. Wraith (1970), Algebraic Theories, Aarhus Lecture Note Series 22.

E. Zelmanov (1997), On the restricted Burnside problem, Fields Medalists’ Lectures, World Scientific Series 5, 623–632.

Part B

Functorial Semantics of Algebraic Theories Introduction

In this paper we attempt to achieve a further unification of general algebra by replacing ‘equationally definable classes of algebras’ with ‘algebraic categories’. This explicit consideration of the categorical structure has several advantages. For example, from the category (or more precisely from an underlying-set functor) we can recover, not only the identities which hold between given operations in a class of algebras, but also the operations themselves (Theorem III.1.1).

We also give attention to certain functors between algebraic categories, called ‘algebraic functors’, which are induced by maps between algebraic theories, and show that all such functors have adjoints (Theorem IV.2.1). Thus free algebras, tensor algebras, monoid algebras, enveloping algebras, the extension of a distributive lattice to a Boolean ring, covariant extension of rings for modules, and many other algebraic constructions are viewed in a unified way as functors adjoint to algebraic functors.

There is a certain analogy with sheaf theory here. Namely, our ‘prealgebras’ of a given type form a category of unrestricted functors, whereas ‘algebras’ are prealgebras which commute with a specified class of inverse limits. The analogy with sheaf theory is further seen in the theorem of IV.1.1 which results.

Algebraic functors and algebraic categories are actually themselves values of a certain functor 𝔖 which we call semantics. Semantics itself has an adjoint 𝔖̂ which we call algebraic structure. In addition to suggesting a possible principle of philosophy (namely a generalization of our Theorem III.1.2), these functors serve as a tool which enables us to give a characterization of algebraic categories (Theorem III.2.1). As a consequence we deduce that if X is an algebraic category and ℂ a small category, then the category X^{ℂ} of functors ℂ ^{}X and natural transformations is also algebraic if |ℂ| (the set of objects in ℂ) is finite (Theorem III.2.2—the last condition is also in a sense necessary) if C is strongly connected or the theory of X has constants.

Basic to these results is Theorem I.2.5 and its corollaries, which give explicit formulas for the adjoint of an induced functor between functor categories in terms of a direct limit over a small category defined with the aid of an operation ( , ) which we also find useful in other contexts (this operation is defined in I.1).

Chapters II and V cannot be said to contain profound results. However, an acquaintance with Chapter II is necessary for the reading of III and IV, as part of our basic language, that of ‘algebraic theories’, is developed there. Essentially, algebraic theories are an invariant notion of which the usual formalism with operations and equations may be regarded as a ‘presentation’ (II.2.) Chapter V serves mainly to clarify the rest of the paper by showing how the usual concepts of polynomial algebra, monoid of operators, and module may be studied using the tools of II, III, IV.

Now a word on foundations. In I.1 we have outlined, as a vehicle for the introduction of notation, a proposed first-order theory of the category of categories, intended to serve as a non-membership-theoretic foundation for mathematics. However, since this work is still incomplete, we have not insisted on a formal exposition. One so inclined could of course view all mathematical assertions of Chapter I as axioms. The significance of ‘small’ and ‘large’, however, needs to be explained; in particular, why do we regard the category of all small algebras of a given type as an adequate version of the category of ‘all’ algebras of that type? In ordinary Zermelo-Fraenkel-Skolem set theory ZF_{1}, where the existence of one inaccessible ordinal θ_{0} = ω is assumed, it is known that the existence of a second inaccessible θ_{1} is an independent assumption, and also that if this assumption is made (obtaining ZF_{2}), the set R(θ_{1}) of all sets of rank less then θ_{1} is a model for ZF_{1}. Thus no theorem of ZF_{1} about the category of ‘all’ algebras of a given type is lost by considering the category of small (rank less then θ_{1}) algebras of that type in ZF_{2}; but the latter has the advantage of being a legitimate object (as well as a notion, or meta-object), amenable to the usual operations of product, exponentiation, etc. Our introduction of C_{1} is just the membership-free categorical analogue to the assumption of θ_{1}. In order to have a reasonable codomain for our semantics functor 𝔖, we find it convenient to go one step further and introduce a category C_{2} of ‘large’ categories. However, if one wished to deal with only finitely many algebraic categories and functors at a time, C_{2} could be dispensed with.

Chapter I

The category of categories and adjoint functors

1. The category of categories

Our notion of category is that of [Eilenberg & Mac Lane, 1945]. We identify objects with their identity maps and we regard a diagram

A ^{f}^{}B

as a formula which asserts that A is the (identity map of the) domain of f and that B is the (identity map of the) codomain of f. Thus, for example, the following is a universally valid formula

A ^{f}^{}B ⇒ A ^{A}^{}A ∧ A ^{f}^{}B ∧ B ^{B}^{}B ∧ Af = f = fB.

Similarly, an isomorphism is defined as a map f for which there exist A, B, g such that

A ^{f}^{}B ∧ B ^{g}^{}A ∧ fg = A ∧ gf = B.

Note that we choose to write the order of compositions in the fashion consistent with left to right following of diagrams.

By the category of categories we understand the category whose maps are ‘all’ possible functors, and whose objects are ‘all’ possible (identity functors of) categories. Of course such universality needs to be tempered somewhat, and this can be done as follows. We specify a finite number of finitary operations which we always want to be able to perform on categories and functors. We also specify a finite number of special categories and functors which we want to include as objects and maps in the category of categories. Since all these notions turn out to have first-order characterizations (i.e. characterizations solely in terms of the domain, codomain, and composition predicates and the logical constants =, ∀, ∃, ⇒, ∧, ∨, ¬ ), it becomes possible to adjoin these characterizations as new axioms together with certain other axioms, such as the axiom of choice, to the usual first-order theory of categories (i.e. the one whose only axioms are associativity, etc.) to obtain the first-order theory of the category of categories. Apparently a great deal of mathematics (for example this paper) can be derived within the latter theory. We content ourselves here with an intuitively adequate description of the basic operations and special objects in the category of categories, leaving the full formal axioms to a later paper. We assert that all that we do can be interpreted in the theory ZF_{3}, and hence is consistent if ZF_{3} is consistent. By ZF_{3} we mean the theory obtained by adjoining to ordinary Zermelo-Fraenkel set theory (see e.g. [Suppes, 1960]) axioms which insure the existence of two inaccessible ordinals θ_{1}, θ_{2} beyond the usual θ_{0} = ω.

The first three special objects which we discuss are the categories 0, 1, 2. The empty category 0 is determined up to unique isomorphism by the property that for every category 𝔸, there is a unique functor 0 ^{}𝔸. The singleton category 1 is defined dually; the objects in any category 𝔸 are in one-to-one correspondence with functors 1 ^{}𝔸. A constant functor is any which factors through 1. The arrow category 2 is, intuitively, the category

\begin{matrix}• & \overline{} & • \\ 0 & & 1 \end{matrix}

with three maps, two of which are objects, denoted by 0,1 (not to be confused with categories 0, 1), the third map having 0 as domain and 1 as codomain. The category 2 is a generator for the category of categories, i.e.

∀𝔸, ∀𝔹, ∀f, ∀g, [𝔸 ^{f}^{}𝔹 ∧ 𝔸 ^{g}^{}𝔹 ∧ ∀u[2 ^{u}^{}𝔸 ⇒ uf = ug] ⇒ f = g].

Furthermore 2 is a retract of every generator; i.e.

∀𝔾[𝔾 is a generator ⇒ ∃f, ∃g[2 ^{f}^{}𝔾 ∧ 𝔾 ^{g}^{}2 ∧ fg = 2]].

These two properties, together with the obvious fact that 2 has precisely three endofunctors, two of which are constant, characterize 2 up to unique isomorphism. There are exactly two functors 1 ^{}2, which we denote by 0, 1. For any category 𝔸, we define u ∈ 𝔸 to mean 2 ^{u}^{}𝔸, and if the latter is true we say u is a member of 𝔸 or a map in 𝔸. Although this ‘membership’ has almost no formal properties in common with that of set theory, the intuitive meaning seems close enough to justify the notation. We do have the following proposition for every functor 𝔸 ^{f}^{}𝔹:

∀x[x ∈ 𝔸 ⇒ ∃!y[y ∈ 𝔹 ∧ y = xf]].

Thus ‘evaluation’ is a special case of composition.

The first five operations on categories and functors which we mention are product, sum, equalizer, coequalizer and exponentiation. For any two categories 𝔸, 𝔹 there is a category 𝔸×𝔹, called their product, together with functors 𝔸×𝔹 ^{p}^{}𝔸, 𝔸×𝔹 ^{q}^{}𝔹, called projections, such that

∀ℂ, ∀f, ∀g ℂ ^{f}^{}𝔸 ∧ ℂ ^{g}^{}𝔹 ⇒ ∃!h[hp = f ∧ hq = g].

ℂ
[figure: f; g]
[figure: 𝔸; p; 𝔸 × 𝔹; h; q; 𝔹]

Taking ℂ = 2, it is clear that the maps in 𝔸 × 𝔹 are in one-to-one correspondence with ordered pairs ⟨x, y⟩ where x ∈ 𝔸 and y ∈ 𝔹. (A similar statement holds for objects, as is seen by taking ℂ = 1.) In fact, for any ℂ, f, g, h, as in the diagram, we write h = ⟨f, g⟩. The sum 𝔸 + 𝔹 and the associated injections are described by the dual (coproduct) diagram. Every member 2 ^{u}^{}𝔸 + 𝔹 factors through exactly one of the injections 𝔸 ^{}𝔸+𝔹, 𝔹 ^{}𝔸+𝔹; however, this does not follow from the definition above. Both products and sums are unique up to unique isomorphisms which commute with the ‘structural maps’ (projections and injections, respectively). A similar statement holds for equalizers, coequalizers, and functor categories, which we now define.

Given any categories 𝔸, 𝔹 and any functors f, g such that 𝔸 [figure: f; g] 𝔹 (i.e. 𝔸 ^{f}^{}𝔹∧

𝔸 ^{g}^{}𝔹), there is a category 𝕂 and a functor 𝕂 ^{k}^{}𝔸 such that

kf = kg ∧ ∀ℂ ∀h [ℂ ^{h}^{}𝔸 ∧ hf = hg ⇒ ∃!j [ℂ ^{j}^{}𝕂 ∧ h = jk]].
ℂ
[figure: ..............; j; h]
[figure: 𝕂; k; 𝔸; f; g; 𝔹]

𝕂 is called the equalizer of f, g, but since this is really an abuse of language, we usually write k = fEg. Taking ℂ = 2, it is clear that the members of 𝕂 are in one-to-one correspondence with those members of 𝔸 at which f, g are equal.

Coequalizers are defined dually, and we write k^{∗} = fE^{∗}g, where 𝔹 ^{k∗}^{}𝕂^{∗} is the structural map of the coequalizer 𝕂^{∗} of f, g. The objects in 𝕂^{∗} are equivalence classes of objects of 𝔹, B being equivalent to B′ if there exists a ∈ 𝔸 such that af = B ∧ ag = B′. The maps in 𝕂^{∗} are equivalence classes of admissible finite nonempty strings of maps in 𝔹; here a string ⟨u_{0}, …, u_{n−1}⟩ is admissible iff for every i < n − 1, the codomain of u_{i} is equivalent to the domain of u_{i+1}, in the above sense; two strings are equivalent if their being so follows by composition (i.e. concatenation), reflexivity, symmetry, and transitivity from the following two types of relations: two strings ⟨u_{0}⟩ and ⟨u′_{0}⟩ of length one are equivalent if ∃x ∈ 𝔸 [xf = u_{0} ∧ xg = u′_{0}]; a string ⟨u_{0}, u_{1}⟩ of length two is equivalent to a string ⟨v⟩ of length one if u_{0}u_{1} = v in 𝔹. Thus, for example, the coequalizer of

1 [figure: 0; 1] 2 is the additive monoid ℕ of non-negative integers. (A monoid is a category 𝔸 such that ∃! 1 ^{}𝔸.) This example shows that, in contrast to the situation for algebraic categories (see Chapter III), coequalizers in the category of categories need not be onto, although they are of course ‘epimorphisms’, i.e. maps which satisfy the left cancellation law.

Before defining exponential (functor) categories, we point out that the operation of forming the product is functorial. That is, given any functors 𝔸 ^{f}^{}𝔸′, 𝔹 ^{g}^{}𝔹′, there is a unique functor 𝔸×𝔹 ^{}𝔸′ ×𝔹′ which commutes with the projections; we denote it by f × g. If 𝔸′ ^{f_{1}}^{}𝔸′′, 𝔹′ ^{g_{1}}^{}𝔹′′ are further functors, then (f × g)(f_{1} × g_{1}) = ff_{1} × gg_{1} by uniqueness. Analogous propositions hold for sums.

Now given any two categories 𝔸, 𝔹, there exists a category 𝔹^{𝔸} called the exponential or functor category of 𝔸, 𝔹, together with a functor 𝔸×𝔹^{𝔸} ^{e}^{}𝔹 called the evaluation functor, such that

∀ℂ ∀f [𝔸 × ℂ ^{f}^{}𝔹 ⇒ ∃!g [ℂ ^{g}^{}𝔹^{𝔸} ∧ f = (𝔸 × g)e]].

We sometimes write g = {f}.

𝔸 × ℂ
[figure: f]

[figure: 𝔸 × 𝔹^{𝔸}; 𝔸; g; e; 𝔹]

Taking ℂ = 1, and noting that 𝔸×1 ≅ 𝔸 (isomorphic) for all 𝔸, it follows that the objects in the functor category 𝔹^{𝔸} are in one-to-one correspondence with the functors 𝔸 ^{}𝔹. Since 𝔸 × 2 ≅ 2 × 𝔸, it follows also that the maps in 𝔹^{𝔸} are in one-to-one correspondence with the functors 𝔸 ^{}𝔹^{2} with domain 𝔸 and codomain 𝔹^{2}. The latter is not to be confused with 𝔹 × 𝔹, which is isomorphic to 𝔹^{|2|} (defined below). In fact the members of 𝔹^{2} are in one-to-one correspondence with functors 2 × 2 ^{}𝔹, which in turn can be identified with commutative squares in 𝔹, for 2 × 2 is a single commutative square

[figure: 00; •; •; 01; 10; •; •; 11]

as can be proved using methods described below. The maps in a functor category are usually called natural transformations. Exponentiation is functorial in the sense that given

𝔸′ ^{f}^{}𝔸 , 𝔹 ^{g}^{}𝔹′,

there is a unique functor 𝔹^{𝔸} ^{g^{f}}^{}𝔹^{′𝔸′} such that the diagram

𝔸′ × 𝔹^{𝔸}  \overline{f × 𝔹^{𝔸}  ^{}}𝔸 × 𝔹^{𝔸}

𝔹e_{}

[figure: 𝔸′ × 𝔹′^{𝔸′}; 𝔸′; g^{f}; e′; 𝔹′; g]

is commutative. If 𝔸′′ ^{f_{1}}^{}𝔸′, 𝔹′ ^{g_{1}}^{}𝔹′′ are further functors, then by uniqueness

(gg_{1})^{ff_{1}} = g^{f}g_{1}^{f_{1}}.

Godement’s ‘cinq règles de calcul functoriel’ [Godement, 1958] now follow immediately. Products are associative; in particular for any three categories 𝔸, 𝔹, ℂ, there is a unique isomorphism

𝔸 × (𝔹^{𝔸} × ℂ^{𝔹}) ^{α}^{}(𝔸 × 𝔹^{𝔸}) × ℂ^{𝔹}

which commutes with the projections. Using this we can construct a unique ‘composition’ functor γ such that

𝔸 × (𝔹^{𝔸} × ℂ^{𝔹})  \overline{α ^{}}(𝔸 × 𝔹^{𝔸}) × ℂ^{𝔹}

𝔹 × ℂ^{𝔹} [figure: e; ℂ^{𝔹}]

[figure: 𝔸 × ℂ^{𝔸}; 𝔸; γ; \overline{\overline{e}}; ℂ; \overline{e}]

One has isomorphisms

\begin{aligned}𝔹^{(𝔸+𝔸′)} & ≅ & 𝔹^{𝔸} × 𝔹^{𝔸′} \\ (𝔹 × 𝔹′)^{𝔸} & ≅ & 𝔹^{𝔸} × 𝔹^{′𝔸} \\ 𝔹^{𝔸×𝔸′} & ≅ & (𝔹^{𝔸})^{𝔸′} \\ 𝔹^{1} & ≅ & 𝔹 \\ 𝔹^{0} & ≅ & 1. \end{aligned}

Furthermore, the existence of exponentiation implies that

𝔸 × (𝔹 + ℂ) ≅ 𝔸 × ℂ + 𝔸 × ℂ,

this being a special case of a general theorem concerning adjoint functors Theorem

2.3. The two maps 1 [figure: 0; 1] 2 induce the domain and codomain functors 𝔹^{2} ^{D_{0}}^{}𝔹 and

𝔹^{2} ^{D_{1}}^{}𝔹 for each category 𝔹.

We now define a set to be any category 𝔸 such that the unique map 2 ^{}1 induces an isomorphism

𝔸 ≅ 𝔸^{1} ≅ 𝔸^{2}.

That is, a set is a category in which every map is an object (identity). Note that the word ‘set’ here carries no ‘size’ connotation; we could equally well use the word ‘class’. Two further operations on categories can now be defined. For any category 𝔸, there exists a set |𝔸|_{0} and a functor |𝔸|_{0} ^{i}^{}𝔸, such that

∀𝕊 ∀f [𝕊 ≅ 𝕊^{2} ∧ 𝕊 ^{f}^{}𝔸 ⇒ ∃!h [hi = f]].
𝕊
[figure: f]
[figure: |𝔸|_{0}; h; i; 𝔸]

We call |𝔸|_{0} the set of objects of 𝔸. Every functor 𝔸 ^{f}^{}𝔸′ induces a unique functor |𝔸|_{0} ^{|f|_{0}}^{}|𝔸|_{0} commuting with i, i′, and 𝔸′ ^{f_{1}}^{}𝔸′′ implies |ff_{1}|_{0} = |f|_{0}|f_{1}|_{0}.

The members of |𝔸|_{0} (i.e functors 2 ^{}|𝔸|_{0}) are in one-to-one correspondence with functors 1 ^{}𝔸, and we sometimes, by abuse of notation, use A ∈ |𝔸|_{0} to mean that 1 ^{A}^{}𝔸. Note that |𝔸^{2}|_{0} is the set of maps of 𝔸.

Dually, we define |𝔸|_{1}, the set of components of 𝔸 to be a set which has a map 𝔸 ^{}|𝔸|_{1} universal with respect to functors from 𝔸 to sets. The members of |𝔸|_{1} may be regarded as equivalence classes of objects of 𝔸, two objects A, A′ being equivalent if there exists a finite sequence of objects and maps

A ^{}A_{1} ^{}A_{2} ^{}A_{3} ^{}… ^{}A′

in 𝔸. Clearly this operation is also functorial. The composite map

|𝔸|_{0} ^{}𝔸 ^{}|𝔸|_{1}

is always onto. It is an isomorphism iff 𝔸 is a sum (possibly infinite) of monoids. 𝔸 is connected if |𝔸|_{1} ≅ 1.

The existence of the two operations | |_{0} and | |_{1} implies that products, sums, equalizers, and coequalizers of sets are again sets (again appealing to Theorem 2.3).

We often abbreviate | |_{0} to | | and denote by |𝔸| the set of objects of 𝔸.

Given two functors 𝔸 ^{f}^{}𝔹, 𝔸′ ^{f′}^{}𝔹 with common codomain, we define their meet 𝕄 to be the equalizer of the pair 𝔸 × 𝔸′ [figure] 𝔹 consisting of pf and p′f′ (p, p′ being the projections from the product). The meet satisfies the following:

\begin{matrix}g′f′ = gf ∧ ∀ℂ ∀h ∀h′ [ℂ ^{h}^{}𝔸 ∧ ℂ ^{h′}^{}𝔸′ ∧ h′f′ = hf ⇒ \\ ∃!k[kg = h ∧ kg′ = h′]]. \end{matrix}

ℂ
[figure: ..............; k; h; h′]
𝕄  \overline{g′ ^{}}𝔸′

[figure: 𝔸; g; f; 𝔹; f′]

For example, if f′ is a monomorphism (i.e. cancellable on the right) then so is 𝕄 ^{g}^{}𝔸, which may be called the inverse image of f′ under f. If f is also a monomorphism then so is 𝕄 ^{}𝔹, which may be called the intersection of f, f′.

Comeets are defined dually. For example, the category 3 may be defined as a comeet as follows:

[figure: 1; 0; 2; 2; 1; 01; 3; 12]

Although it does not follow from this definition above, it is a fact about the category of categories that there is exactly one non-constant map 2 ^{}3 in addition to the two displayed above; we denote this third map by 02. Intuitively the category 3 may be pictured thus:

•^{1}

[figure: 01; 12]
0 •  \overline{02  ^{}}• 2

Like 2, 3 is an ordinal; in particular it is a preorder, i.e. a category 𝔸 such that any pair

of maps 1 [figure: A; B] 𝔸 has at most one extension to a map u such that

2 ^{u}^{}𝔸 ∧ A = 0u ∧ B = 1u.
[figure: 1; 0; 2; 1; 1; 2]
[figure: A; B]
[figure: 𝔸; u; 𝔸; u]

We have already pointed out that members of any category 𝔸 ‘are’ simply functors 2 ^{}𝔸. Among such members, we now show how to define the basic predicates domain, codomain, and composition entirely in terms of functors in the category of categories. Suppose x, y, u, a, b are all functors 2 ^{}𝔸. Then

a is the 𝔸-domain of x iff

[figure: 2; a; 𝔸; 1; 0; 2; x]

is commutative.

b is the 𝔸-codomain of x iff [figure: 2; b; 𝔸; 1; 1; 2; x]

is commutative.

and u is a 𝔸-composition of ⟨x, y⟩ iff

2  2
[figure: 0; 12; y; u]
[figure: 1; 3; 02; 𝔸]
[figure: 1; 01; x]
2

is commutative.

By relativising quantifiers to functors 2 ^{}𝔸, one extends the above scheme so that to every formula φ of the usual first-order theory of categories, there is another formula φ_{𝔸} with one more free variable 𝔸, which states in the language of the category of categories that φ holds in 𝔸. In particular, one can discuss a ^{x}^{}b, commutative triangles and squares, etc. in 𝔸. We have the obvious

Metatheorem. If φ is a sentence provable in the usual first-order theory of categories, then the sentence ∀𝔸[φ_{𝔸}] is provable in the first-order theory of the category of categories.

By use of the technique just outlined one can, e.g., deduce the precise nature of domain, codomain, and composition in a functor category or product category.

We say that two functors 𝔸 [figure: f; g] 𝔹 are equivalent iff the two objects

1 ^{{f}}^{}𝔹^{𝔸}, 1 ^{{g}}^{}𝔹^{𝔸}, which correspond to them in the functor category are isomorphic

in 𝔹^{𝔸}. Categories 𝔸, 𝔹 are equivalent if there exist functors 𝔸 [figure: f; g] 𝔹 such that {fg}

is isomorphic in the category 𝔸^{𝔸} to the object {𝔸} and {gf} is isomorphic in 𝔹^{𝔹} to the object {𝔹} ({𝔸} and {𝔹} being the objects in the functor categories corresponding to the respective identity functors). In the latter case, f and g are called equivalences.

There are still some special objects in the category of categories which we will need to describe. Chief among these are C_{1}, the category of small categories and C_{2}, the category of large categories. In terms of the set theory ZF_{3}, a model for C_{i} may be obtained by considering the category of all categories and functors which are of rank less than θ_{i}, the i-th inaccessible ordinal (i < 3).

In terms of the theory of the category of categories, C_{1} may be described as an object such that:

(1) C_{1} has all properties we have thus far attributed to the category of categories. (Here we use the φ_{𝔸} technique.) This includes the existence of 0, 1, 2, E, E^{∗}, | |_{0}, | |_{1}, and exponentiation.

(2) C_{1} is closed under products and sums over all index sets 𝕊 which are equal in size to some object in C_{1}. (The precise meaning of infinite products and sums will be explained in Section 2.) A way of expressing the equipotency condition will be explained below.

(3) For any category ℂ having the properties (1) and (2), there is a functor C_{1} ^{}ℂ which preserves 0, 1, 2, E, E^{∗}, Π, Σ, | |_{0}, | |_{1}, and exponentiation, and which is unique up to equivalence. One can then describe C_{2} by the same three properties, except that (1) now includes

the existence of an object in C_{2} having all the properties in C_{2} which C_{1} has in the master category (i.e. in the theory of the category of categories).

Proposition. C_{1} and C_{2} are unique up to equivalence and there is a canonical C_{1} ^{}C_{2}.

The category C_{0} of finite categories is somewhat more difficult to describe in the firstorder theory of the category of categories, because, as already pointed out, it is not closed under E^{∗}.

The existence of the category S_{0} of finite sets, the category S_{1} of small sets, and the category S_{2} of large sets now follows, as does the existence of categories M_{0}, M_{1}, M_{2} of monoids. Note that these are all objects in our master category. There are also objects 1 ^{{S_{1}}}^{}C_{2}, 1 ^{{M_{1}}}^{}C_{2} in C_{2} which correspond to S_{1}, M_{1}. Of course there are many categories which appear as objects in our master category but which are larger than any object in our category of ‘large’ categories C_{2}, for example C_{2} itself, the Boolean algebra 2^{|C_{2}|}, etc. Whenever we refer to ‘the’ category of sets, monoids, etc., we ordinarily mean S_{1},M_{1}, in general the full category of small objects of the stated sort, choosing any (not larger than) large version.

There is also a category ω which is an ordinal number and which is such that |ω| = |ℕ^{2}|. Of course ω, ℕ, S_{0} are all quite different as categories, but we can choose a version of S_{0} such that

|S_{0}| = |ω| = |ℕ^{2}| = N.

(Note that | | is not preserved under equivalence.) The common(set) value N has the property that there exists an object 1 ^{0}^{}N and a functor N ^{s}^{}N such that for every category ℂ, for every object 1 ^{C}^{}ℂ, and every functor ℂ ^{t}^{}ℂ there exists a unique functor N ^{f}^{}ℂ such that

[figure: 1; 0; N; s; N; 1; ≅; C; ℂ; f; t; ℂ; f]

is commutative. This ‘Peano postulate’ characterizes the triple ⟨N, 0, s⟩ up to a unique isomorphism which preserves 0, s. The elementary properties of recursion follow easily.

Finally we mention two very important operations in the category of categories whose existence can be derived from what we have said. One is dualization, which assigns to each category 𝔸 the category 𝔸^{∗} obtained by interchanging domains and codomains and reversing the order of composition. Each functor 𝔸 ^{f} ^{}𝔹 induces 𝔸^{∗} ^{f^{∗}}^{}𝔹^{∗}, and (fg)^{∗} = f^{∗}g^{∗} for 𝔹 ^{g}^{}ℂ. Also A^{∗∗} ≅ 𝔸. This shows that we must take the two maps

1 [figure: 0; 1] 2 as primitives in formalizing the first-order theory of the category of categories,

because dualization is an automorphism which preserves the categorical structure but interchanges 0 and 1, whereas we need to distinguish between these in a canonical fashion in order to define φ_{𝔸}, C_{1}, etc.

The other operation is one which we denote by ( , ). It is defined for any pair of functors 𝔸 ^{f} ^{}𝔹, 𝔸′ ^{f′}^{}𝔹 with a common codomain, and is determined up to unique isomorphism by the requirement that all three squares below be meet diagrams:

(f, f′)

[figure]
(f, 𝔹)  (𝔹, f′)
[figure]
𝔸  𝔹^{2}  𝔸′
[figure: f; D_{0}; D_{1}; f′]
𝔹  𝔹

It follows that the maps in the category (f, f′) are in one-to-one correspondence with quadruples ⟨u_{0}, x, x′, u_{1}⟩ where u_{0} ∈ 𝔹, u_{1} ∈ 𝔹, x ∈ 𝔸, x′ ∈ 𝔸′ and such that

[figure: •; xf; •; •; u_{0}; x′f′; •; u_{1}]

is a commutative square in 𝔹. The domain of the above map is ⟨u_{0}, xD_{0}, x′D_{0}, u_{0}⟩ and the codomain is ⟨u_{1}, xD_{1}, x′D_{1}, u_{1}⟩, and the composition of ⟨u_{0}, x, x′, u_{1}⟩, ⟨u_{1}, y, y′, u_{2}⟩ is ⟨u_{0}, xy, x′y′, u_{2}⟩. In particular, the objects of (f, f′) are in one-to-one correspondence with triples ⟨a, u, a′⟩ where a ∈ |𝔸|, a′ ∈ |𝔸′|, u ∈ 𝔹, and uD_{0} = af, uD_{1} = a′f′.

For example, if 𝔸 = 1, then f is an object in 𝔹, say f = B, the objects of (B, f′) are in one-to-one correspondence with pairs ⟨u, A′⟩ where B ^{u}^{}A′f′, and the maps in (B, f′) are commutative triangles in 𝔹 of the form:

A′_{0}f′
[figure: u_{0}]
B  x′ ∈ 𝔸′
[figure: u_{1}]
A′_{1}f′ x′f′_{}

In particular, 𝔸′ can be a subcategory of 𝔹.

A case of the ( , ) construction which will play an important role in Chapter III is (C_{2}, {S_{1}}). The objects of this category are functors X ^{U}^{}S_{1} whose codomain is the category of small sets and functions and whose domain is arbitrary large (smaller than θ_{2}) category X. Maps in (C_{2}, {S_{1}}) are commutative triangles

X  \overline{T  ^{}}X′
[figure: U; U′]
S_{1}

If 𝔸 = 𝔸′ = 1, then f, f′ are both objects in 𝔹, and (f, f′) always reduces to a set, the set of maps in 𝔹 with domain f and codomain f′. The condition referred to earlier in the discussion of C_{i} can now be formalized. According to condition (1) in the description of C_{i}, there is an object 1_{i} : 1 ^{}C_{i} having the properties in C_{i} that 1 has in the master category.

Definition. A set 𝕊 is equipollent with a set of C_{i} iff there is an object 1 ^{S}^{}C_{i} in C_{i} such that (1_{i}, S) ≅ 𝕊.

As the final topic of this section, we discuss full, faithful, and dense functors. Let

𝔸 ^{f} ^{}𝔹 be a functor. Note that for every pair of objects 1 [figure: a; a′] 𝔸 in 𝔸, there is an

induced map

(a, a′) ^{}(af, a′f′).

Definition. f is full iff the above induced map is an epimorphism of sets for every pair ⟨a, a′⟩ of objects. f is faithful iff the induced map is a monomorphism of sets for every pair of objects. f is dense iff for every object b ∈ |𝔹| there is an object a ∈ |𝔸| such that af ≅ b in 𝔹. For example, the inclusions C_{1} ^{}C_{2}, M_{i} ^{}C_{i}, and S_{i} ^{}C_{i} are full and faithful, but not dense.

A proof of the following proposition will be found, for example, in Freyd’s dissertation [Freyd, 1960].

Proposition. A functor 𝔸 ^{f}^{}𝔹 is an equivalence iff it is full, faithful, and dense.

2. Adjoint functors

As pointed out in Section 1, for any two objects 1 [figure: A; A′] 𝔸 in a category 𝔸, the category

(A, A′) is a set; however it need not be a small set (or even a ‘large’ set in our sense) so that in general ( , ) does not define a functor 𝔸^{∗} × 𝔸 ^{}S_{1} (although the latter is of course true for many categories of interest). This fact prevents us from giving the definition of adjointness in a functor category S_{1}^{𝔹^{∗}×𝔸} as done by [Kan, 1958]. However we are able to give a definition free of this difficulty by making use of the broader domain of our ( , ) operation.

Note that if 𝔸 ^{f}^{}𝔹, 𝔹 ^{g}^{}𝔸 are any functors, then there is a functor

(𝔹, f) ^{\overline{f}}^{}𝔹 × 𝔸

defined by the outer functors (𝔹, f) ^{}𝔹^{2} ^{D_{0}}^{}𝔹 and (𝔹, f) ^{}𝔸 in the diagram

(𝔹, f)
[figure]
𝔹^{2}  𝔸
[figure: D_{0}; D_{1}; f]
𝔹  𝔹

Similarly, there is a functor (g, 𝔸) ^{\overline{g}}^{}𝔹×𝔸 induced by the outer functors (g, 𝔸) ^{}𝔹 and (g, 𝔸) ^{}𝔸^{2} ^{D_{1}}^{}𝔸 in the diagram

(g, 𝔸)
[figure]
𝔹  𝔸^{2}
[figure: g; D_{0}; D_{1}]
𝔸  𝔸

Note that if ⟨x, b, a, x′⟩ is a typical map in (𝔹, f) (i.e. bx′ = x(af)) then ⟨x, b, a, x′⟩\overline{f} = ⟨b, a⟩, and analogously for \overline{g}.

Definition. If 𝔸 ^{f} ^{}𝔹 and 𝔹 ^{g} ^{}𝔸, then we say g is adjoint to f (and f is coadjoint to g) iff there exists an isomorphism h rendering the triangle of functors

(𝔹, f)  ^{h  ^{}}(g, 𝔸)
[figure: \overline{f}; \overline{g}]
𝔹 × 𝔸

commutative, where \overline{f}, \overline{g} are the functors defined above.

Theorem 1. For each functor 𝔸 ^{f}^{}𝔹, there exists a functor 𝔹 ^{g}^{}𝔸 such that g is adjoint to f iff for every object B ∈ |𝔹| there exists an object A ∈ |𝔸| and a map B ^{φ}^{}Af in 𝔹 such that for every object A′ ∈ |𝔸| and every map B ^{x}^{}A′f in 𝔹, there exists a unique map A ^{y}^{}A′ in 𝔸 such that x = φ(yf) in 𝔹:

B  \overline{φ  ^{}}Af
[figure: x] 𝔹
A′f yf_{}

Proof. If g is adjoint to f, let B be an object in 𝔹. Regarding the identity map (B)g ^{}Bg as an object in (g, 𝔸) and applying the functor h^{−1} we obtain an object B ^{φ}^{}Bgf in (𝔹, f) such that (φ)h = Bg, since \overline{f} = h\overline{g}. If B ^{x}^{}A′f is any object in (𝔹, f) of the displayed form, then (x)h is an object Bg ^{}A. We wish to show that A = Bg, φ satisfy the condition in the statement of the theorem. For this we show that y = (x)h satisfies the above commutative triangle and is uniquely determined by that condition. Consider the objects φ, x ∈ |(𝔹, f)| and Bg, y ∈ |(g, 𝔸)| in the diagrams below. We have

(φ)h = Bg
(x)h = y
[figure: B; u; B; Bg; Bg; Bg]
𝔹  \overline{h_{}}𝔸
[figure: Bgf; φ; v; A′f; x; Bg; Bg; y; A′; y]

Obviously ⟨Bg, y⟩ defines a map Bg ^{}y in (g, 𝔸), i.e. the right hand square above is commutative. Let ⟨u, v⟩ be h^{−1} of ⟨Bg, y⟩. Then the left hand square is commutative (i.e. defines a map φ ^{}x in (𝔹, f)) and, again because of the assumed commutativity property of h, we have u = B (identity map) and v = yf. Hence φ(yf) = x in 𝔹. To show uniqueness, suppose Bg ^{y′}^{}A′ is such that φ(y′f) = x. Then taking u = B, v = y′f, one gets a map φ ^{}x in (𝔹, f) and applying h to it one gets (Bg)y = (Bg)y′, where as before y = (x)h (again using the fact that h commutes with the two functors \overline{f}, \overline{g} to 𝔹 × 𝔸); but Bg is an identity map, hence y = y′.

Conversely, if the condition of the theorem holds, then we choose for each B ∈ |𝔹| a pair ⟨A, φ⟩ satisfying the condition. Then setting Bg = A, a functor |𝔹| ^{}|𝔸| is defined for objects, which by the condition has a well-defined extension to a functor 𝔹 ^{g}^{}𝔸 defined for all maps in 𝔹. We then define a functor (𝔹, f) ^{h}^{}(g, 𝔸) as follows. Given any map x ^{}x′ in (𝔹, f) defined, say, by ⟨b, a⟩ as below,

B  \overline{b  ^{}}B′
[figure: φ; φ′]
Bgf ^{bgf^{}}B′gf
[figure: ..............; yf; ..............; y′f]
[figure: Af; x; af; A′f; x′]

the resulting square

[figure: Bg; bg; B′g; A; y; a; A′; y; ′]

is a map in (g, 𝔸), by uniqueness. Define ⟨x, b, a, x′⟩h = ⟨y, b, a, y′⟩. Then h is clearly a functor (𝔹, f) ^{h}^{}(g, 𝔸) such that \overline{f} = h\overline{g}. It is also clear that h is one-to-one and onto, hence an isomorphism.

The above theorem shows that our notion of adjointness coincides with that of [Kan, 1958].

Corollary. For any functor f, there is up to equivalence at most one g such that g is adjoint to f. If g is adjoint to f and g′ is adjoint to f′ where

𝔸 ^{f}^{}𝔹 ^{f′}^{}ℂ

then g′g is adjoint to ff′. Further if g is adjoint to f and t is co-adjoint to g, then t is equivalent to f.

The above theorem and corollary have obvious dualizations for co-adjoints.

For any categories 𝔸, 𝔻 the unique functor 𝔻 ^{}1 induces a functor 𝔸 ^{}𝔸^{𝔻}.

Definition. 𝔸 is said to have inverse limits over 𝔻 if the functor 𝔸 ^{}𝔸^{𝔻} has a co-adjoint. Dually 𝔸 has direct limits over 𝔻 if 𝔸 ^{}𝔸^{𝔻} has an adjoint. We denote these functors co-adjoint and adjoint to 𝔸 ^{}𝔸^{𝔻} by lim_{←𝔻} and lim_{→𝔻},

respectively, when they exist, or by lim^{𝔸}_{←𝔻}, lim^{𝔸}_{→𝔻} if there is any danger of confusion. (We will violate our customary convention for the order of composition when evaluating limit functors.)

If 𝔻 ^{f}^{}𝔸, then we also sometimes write

f^{←} = lim^{𝔸}_{←𝔻}({f})

f^{→} = lim^{𝔸}_{→𝔻}({f})

if these exist, where {f} is the object in 𝔸^{𝔻} corresponding to f. Note that the latter notation is unambiguous since f determines its domain 𝔻 and codomain 𝔸. (It is ‘ambiguous’ in the sense that the limit functors are defined only up to a unique equivalence of functors.) f^{←} and f^{→} are objects in 𝔸 if they exist.

In particular, if 𝔻 is a set we write

Π_{𝔻} = lim_{←𝔻}

⋆_{𝔻} = lim_{→𝔻}

in any 𝔸 for which the latter exist, and we call these operations product and coproduct, respectively. In the categories S_{i}, C_{i}, or in A_{i} (the categories of finite, small, and large abelian groups), where the practice is customary, we replace ⋆ by ∑, and in the category R_{c} of (small) commutative rings with unit, we replace ⋆ by ⊗. In particular if 𝔻 = |2| and 𝔻 ^{A}^{}𝔸, we write

A_{0} × A_{1} = lim_{←𝔻}(A)

A_{0} ⋆ A_{1} = lim_{→𝔻}(A)

when these exist.

Also, when 𝔻 is a set, say S = |𝔻| ≅ 𝔻, and whenever 1 ^{A}^{}𝔸, we write

A^{S} = lim_{←𝔻}(A𝔸^{𝔻→1})

S · A = lim_{→𝔻}(A𝔸^{𝔻→1})

for the ‘S-fold product and S-fold coproduct of A with itself’, respectively, when these exist. That is, A^{S} is the composite

1 ^{A}^{}𝔸 ^{}𝔸^{𝔻} ^{𝔻^{Π}}^{}𝔸

and S · A is the composite

1 ^{A}^{}𝔸 ^{}𝔸^{𝔻} ⋆_{𝔻}^{}𝔸

where S = |𝔻| ≅ 𝔻. Note that in the categories C_{i} (and S_{i}) the notation A^{S} agrees essentially with the exponential notation already adopted, and that similarly S · A = S′ × A in C_{i}, where S′ in an object in C_{i}, which is a ‘set’ in C_{i}, such that (1_{i}, S′) ≅ S ≅ 𝔻, when such exist (i.e. when S is equipollent to a set of C_{i}.)

The category 𝔼 is defined by the requirement that

[figure: |2|; i; 2; 2; i; 𝔼]

be a comeet diagram. 𝔼 may be pictured thus:

[figure: 0•; •1]

The functors 𝔼 ^{a}^{}𝔸 are in one-to-one correspondence with pairs ⟨a′, a′′⟩ of maps in 𝔸 such that a′D_{0} = a′′D_{0} ∧ a′D_{1} = a′′D_{1} in 𝔸. If lim^{𝔸}_{←𝔼} and lim^{𝔸}_{→𝔼} exist, then we denote by

lim_{←𝔼}(a) ^{a′Ea′′}^{}A

and

A′ a′E^{∗}a′′ ; lim_{→𝔼}^{}(a)

the canonical maps associated with these limits (analogous to φ in Theorem 2.1), where A = a′D_{0} = a′′D_{0} and A′′ = a′D_{1} = a′′D_{1} in 𝔸. We call these limits the equalizer and coequalizer, respectively, of a in 𝔸. Note that (by Theorem 2.1), we have

(a′Ea′′)a′ = (a′Ea′′)a′′
a′(a′E^{∗}a′′) = a′′(a′E^{∗}a′′)

in 𝔸.

If lim^{𝔸}_{←0} and lim^{𝔸}_{→0} exist, then, since 𝔸^{0} ≅ 1, these functors may be regarded as objects in 𝔸, which we denote by 1_{𝔸} and 0_{𝔸}, respectively; these are unique up to unique isomorphism in 𝔸. By Theorem 2.1, 1_{𝔸} is characterized by the property that for every A ∈ |𝔸| there is a unique A ^{}1_{𝔸} in 𝔸; dually for 0_{𝔸}.

Definition. 𝔸 is said to have finite limits iff lim^{𝔸}_{←𝔻} and lim^{𝔸}_{→𝔻} exist for every finite category 𝔻 (i.e. for every 𝔻 such that |𝔻^{2}| is equipollent to a set of C_{0} (or S_{0})). 𝔸 is said to be left complete iff lim^{𝔸}_{←𝔻} exists for every small category 𝔻 (i.e. for every 𝔻 such that |𝔻^{2}| is equipollent to a set of C_{1} (or S_{1})). Dually, 𝔸 is right complete if it has small direct limits. 𝔸 is complete iff it is left complete and right complete.

The following fact was pointed out to the author by Peter Freyd.

Theorem 2. A category 𝔸 is left complete iff 𝔸 has equalizers and arbitrary small products.

Proof. Let 𝔻 be any small category and 𝔻 ^{f}^{}𝔸 any functor. We construct f^{←} as follows. Let |𝔻| ^{\overline{f}}^{}𝔸 be the functor determined by the diagram

|𝔻|  \overline{}𝔻
.................................. \overline{f}  _{}
[figure: |𝔸|; |f|; 𝔸; f]

and consider also the functor |𝔻^{2}| ^{|D_{1}|}^{}|𝔻| where D_{1} is the codomain functor of 𝔻. Then, since |𝔻|, |𝔻^{2}| are both small sets, the existence of the two objects in the diagram below is assured.

Π_{|𝔻|}\overline{f}  [figure: a′; a′′] Π_{|𝔻^{2}|}|D_{1}|\overline{f}

We must now define the maps a′, a′′ in 𝔸. For each 𝔻 ∈ |𝔻|, let Π_{|𝔻|}f̄ ^{p_{D}}^{}Df denote

the canonical projection. (The family of p_{D}’s determines the map of Theorem 2.1 in this case.) For each x ∈ |𝔻^{2}| consider

Π_{|𝔻|}f̄ ^{p_{(xD_{1})}}^{}(xD_{1})f.

This family of maps determines a unique map Π_{|𝔻|}f̄ ^{a′′}^{}Π_{|𝔻^{2}|}|D_{1}|f̄ such that for every x ∈

|𝔻^{2}|, a′′q_{x} = p_{(xD_{1})} where Π_{|𝔻^{2}|}|D_{1}|\overline{f} ^{q_{x}}^{}(xD_{1})f is the canonical projection of the second

product. Now consider also, for x ∈ |𝔻^{2}|, the composite map

Π_{|𝔻|}\overline{f} ^{p_{(xD_{0})}}^{}(xD_{0})f ^{xf}^{}(xD_{1})f.

This family determines a unique Π_{|𝔻|}\overline{f} ^{a′}^{}Π_{|𝔻^{2}|}|D_{1}|\overline{f} such that a′q_{x} = p_{(xD_{0})}(xf) for every

x ∈ |𝔻^{2}|. We now let A denote the equalizer of the functor 𝔼 ^{a} ^{}𝔸 determined by ⟨a′, a′′⟩:

[figure: A; a′Ea′′; Π_{|𝔻|}\overline{f}; a′; a′′; Π_{|𝔻^{2}|}|D_{1}|\overline{f}]

We wish to show A ≅ f^{←}. For each D ∈ |𝔻|, let A ^{φ_{D}}^{}Df be the composite φ_{D} = (a′Ea′′)p_{D}. We need to show that the family φ_{D} for D ∈ |𝔻| defines a map (A)𝔸^{(𝔻→1)} ^{φ}^{}{f} in 𝔸^{𝔻}, and that ⟨A, φ⟩ is universal with respect to that property. Because the maps in 𝔸^{𝔻} are natural transformations, the first is true since for every D ^{x}^{}D′ in 𝔻, we have

φ_{D}(xf) = (a′Ea′′)p_{D}xf = (a′Ea′′)a′q_{x}
= (a′Ea′′)a′′q_{x} = (a′Ea′′)p_{D′}
= φ_{D′}.

To show the universality we consider any other family ψ_{D}, D ∈ |𝔻| such that for every D ^{x}^{}D′ in 𝔻, ψ_{D}(xf) = ψ_{D′}:

Df
[figure: ψ_{D}]
X
[figure: ψ_{D′}]
D′f xf_{}

By the universal property of products (i.e. by Theorem 2.1 applied to Π_{|𝔻|}) the family ψ

determines a unique map X ^{b}^{}Π_{|𝔻|}\overline{f} such that bp_{D} = ψ_{D} for all D ∈ |𝔻|. Then for every

x ∈ 𝔻, we have (in 𝔸)

\begin{aligned}ba′′q_{x} & = & bp_{(xD_{1})} & = & ψ_{(xD_{1})} & = & ψ_{(xD_{0})}(xf) \\ & = & bp_{(xD_{0})}(x\overline{f}) & = & ba′q_{x}. \end{aligned}

By uniqueness, ba′′ = ba′; i.e. b ‘equalizes’ ⟨a′, a′′⟩. Therefore ∃!X ^{y} ^{}A such that y(a′Ea′′) = b. But by construction y is also the unique map satisfying ψ_{D} = yφ_{D} for all

D ∈ |𝔻|. This proves that A ≅ f^{←}.

Because Theorem 2.2 obviously has a dual, we have the

Corollary. A category 𝔸 is complete iff 𝔸 has equalizers, coequalizers, small products, and small coproducts.

Also we can establish a second

Corollary. A category has finite limits iff 𝔸 has inverse and direct limits over the three categories 0, |2|, 𝔼.

Proof. By the proof of Theorem 2.2, we need only show that 𝔸 has products and coproducts over finite sets. We have assumed that lim^{𝔸}_{←0} and lim^{𝔸}_{→0} exist, and for any 𝔸 we have that

lim^{𝔸}_{→1} ≅ lim^{𝔸}_{←1} ≅ {𝔸} in 𝔸^{𝔸^{1}}.

We have also assumed that limits exist over |2| ≅ 1 + 1. Then if n is any finite set for which we know Π_{n} exists, and if n + 1 ^{A}^{}𝔸 is any functor, consider the injections

n ^{j}^{}n + 1, 1 ^{(n)}^{}n + 1 and the binary product (Π_{n}jA) × A_{n}. Defining projections \overline{p}_{0}, …, \overline{p}_{n−1}, \overline{p}_{n} by the compositions

(Π_{n}jA) × A_{n}

[figure: q; q′ = \overline{p}_{n}]

Π_{n}jA

[figure: p_{0}; p_{n−1}]
A_{0} A_{1}  ⋯  A_{n−1}  A_{n}

it is clear that the correct universal mapping property holds, so that (Π_{n}jA) × A_{n} ≅ Π_{n+1}A, completing the proof by induction.

In particular, one can define meets and comeets in 𝔸, for any category 𝔸 satisfying the condition of the corollary, as inverse and direct limits over the categories defined respectively by the comeet diagrams

[figure: 1; 2; 2; •_{0}; •_{1}; •^{0′}; 1; 01; 1; 0′1]

[figure: 1; 2; 2; •_{1}; •^{0}; •^{1′}; 0; 01; 0; 01′]

Note that lim^{𝔸}_{←2} ≅ D_{0} and lim^{𝔸}_{→2} ≅ D_{1} exist for any category.

Definition. A functor 𝔸 ^{f}^{}𝔹 is said to commute with inverse limits over 𝔻 iff lim^{𝔸}_{←𝔻} and lim^{𝔹}_{←𝔻} exist and the diagram

[figure: 𝔸^{𝔻}; f^{𝔻}; 𝔹^{𝔻}; 𝔸; lim^{𝔸}_{←𝔻}; f; 𝔹; lim^{𝔹}_{←𝔻}]

is commutative up to an equivalence in 𝔹^{(𝔸^{𝔻})}. Similarly for direct limits. f is said to be left exact iff f commutes with inverse limits over every finite 𝔻, and f is left continuous iff it commutes with inverse limits over every small 𝔻. Similarly, right exact, right continuous, exact, continuous are defined.

Remark. For additive functors between abelian categories, our notions of exactness are equivalent to the customary ones, as was shown by [Freyd, 1960].

Definition. A functor ℂ ^{u}^{}𝔻 will be called left pacing iff ℂ is small and for every 𝔻 ^{t}^{}𝔸 with 𝔸 left complete,

lim^{𝔸}_{←ℂ}(ut) ≅ lim^{𝔸}_{←𝔻}(t) in 𝔸

(and in particular, the latter exists).

The following two theorems are also due in essence to [Freyd, 1960].

Theorem 3. Let 𝔸 ^{f}^{}𝔹 be a functor with 𝔸, 𝔹 left complete. Then there exists g adjoint to f iff f is left continuous and for every B ∈ |𝔹|, there exists a small category ℂ_{B} and a left pacing functor ℂ_{B} ^{u}^{}(B, f).

Proof. Suppose f has an adjoint g, and suppose 𝔻 is any small category and 𝔻 ^{t}^{}𝔸 is any functor. Let L = lim^{𝔸}_{←𝔻}(t) and let λ_{D}, for D ∈ |𝔻|, denote the associated canonical

maps, i.e. for every D ^{x}^{}D′ in 𝔻, λ_{D}(xt) = λ_{D′}, where L ^{λ_{D}}^{}Dt. We wish to show that Lf, together with λ_{D}f for D ∈ |𝔻|, satisfies the universal property (Theorem 2.1) which characterizes lim^{𝔹}_{←𝔻}(tf). Since (λ_{D}f)(xtf) = λ_{D′}f for every D ^{x}^{}D′ in 𝔻, we need only show that for any family ψ_{D}, having the property that ψ_{D}(xtf) = ψ_{D′}, for all D ^{x}^{}D′ in 𝔻, there is a unique map X ^{y}^{}Lf such that for all D ∈ |𝔻|, ψ_{D} = y(λ_{D}f), where X is the common domain of the ψ_{D}:

Dtf
[figure: ψ_{D}; λ_{Df}]
X  ^{y ^{}}Lf  in 𝔹.
[figure: ψ_{D′}] [figure: λ_{D′f}]
D′tf xtf_{}

To establish this, note that by the definition of adjointness there is an isomorphism (𝔹, f) ^{h}^{}(g, 𝔸) such that h\overline{g} = \overline{f}. In particular, we have

Dt
[figure: (ψ_{D})h]
Xg  in 𝔸.
[figure: (ψ_{D′})h]
D′t xt_{}

Thus there is a unique map Xg ^{\overline{y}}^{}L in 𝔸 such that (ψ_{D})h = \overline{y}λ_{D} for all D ∈ |𝔻|. Then applying h^{−1} we get a unique y ∈ 𝔹 such that ψ_{D} = y(λ_{D}f) for all D ∈ |𝔻|, as required. Also, if f has an adjoint g, the object B ^{φ}^{}Bgf is isomorphic to 1_{(B,f)}, hence the functor 1 ^{}(B, f) determined by the object φ is left pacing.

Conversely, suppose that conditions of the theorem are satisfied. The canonical (B, f) ^{t}^{}𝔸 has an inverse limit A in 𝔸, which we will show satisfies the condition of Theorem 2.1. First we must define a map B ^{φ}^{}Af. For this, let λ_{x} denote the canonical map A ^{}xt, for each object B ^{x}^{}(xt)f in (B, f). For every map x ^{a}^{}x′ in (B, f)

B
[figure: x; x′]
(xt)f  \overline{af  ^{}}(x′t)f

we have λ_{x}a = λ_{x′}. Now since A is also an inverse limit over the small category ℂ_{B} and since f is left continuous, Af is the inverse limit of the functor tf, with associated maps Af ^{λ_{x}f}^{}xtf. Since for every map x ^{a}^{}x′ in (B, f), x(af) = x′ and a = ⟨x, a, x′⟩t, there is a unique map B ^{φ}^{}Af such that φ(λ_{x}f) = x in 𝔹 for every x ∈ |(B, f)|. This defines φ and also shows, for each x, the existence of y satisfying the condition of Theorem 2.1; we need now only show uniqueness, i.e. if φ(yf) = x, then y = λ_{x}. For this consider the equalizer K of the functor 𝔼 ^{}𝔸 defined by ⟨y, λ_{x}⟩:

[figure: K; yEλ_{x}; A; y; λ_{x}; xt.]

Because f is left continuous, Kf is also the equalizer of ⟨yf, λ_{x}f⟩, and since φ ‘equalizes’ the latter, there is a unique z such that the left hand triangle below is commutative in 𝔹:

B
[figure: ...................................................; z; x]
[figure: Kf; (yEλ_{x})f = (yf)E(λ_{x}f); Af; φ; y; λ_{x}; xtf]

As B ^{z}^{}Kf is an object in (B, f), there is a map A ^{λ_{z}}^{}K = zt. For any x′ ∈ |(B, f)| we have:

Kf
[figure: z]
[figure: B; φ; Af; (yEλ_{x})f]
[figure: x′]
x′tf λ_{x′}f_{}

i.e. ⟨z, (yEλ_{x})λ_{x′}, x′⟩ is a map in (B, f) at which t takes the value (yEλ_{x})λ_{x′}. Hence

K = zt
[figure: λ_{z}]
A
[figure: λ_{x′}]
x′t (yEλ_{x})λ_{x′}_{}

i.e. (λ_{z}(yEλ_{x}))λ_{x′} = (A)λ_{x′} for all x′ ∈ |(B, f)|, (A being an identity map). Hence, by the uniqueness stipulation of Theorem 2.1 applied to the case of lim_{←}(t) we have λ_{z}(yEλ_{x}) = A. Then we have immediately y = Ay = λ_{z}(yEλ_{x})y = λ_{z}(yEλ_{x})λ_{x} = Aλ_{x} = λ_{x}, proving that y = λ_{x} is the unique A ^{}xt such that φ(yf) = x in 𝔹. Since this is true for all B ^{x}^{}xt in 𝔹, the condition of Theorem 2.1 is true, so that there exists g adjoint to f.

The dual of Theorem 2.3 implies in particular that a functor which has a co-adjoint must be right continuous (if its domain and codomain categories are complete).

Theorem 4. A functor 𝔸 ^{f}^{}𝔹, with 𝔸, 𝔹 left complete has an adjoint if and only if f commutes with equalizers and all small products and for every B ∈ |𝔹|, there exists a small set 𝕊_{B} of objects in 𝔸 and maps B ^{v_{A}}^{}Af, A ∈ 𝕊_{B}, such that for every A′ ∈ |𝔸| and for every B ^{x}^{}A′f in 𝔹 there is some A ∈ 𝕊_{B} and a map A ^{y}^{}A′ in 𝔸 such that x = v_{A}(yf).

Proof. The necessity of conditions is clear by Theorem 2.3. The first condition is clearly equivalent to left continuity, by Theorem 2.2. Thus by Theorem 2.3 we need only construct a small left pacing ℂ_{B} ^{v}^{}(B, f) to complete the proof of Theorem 2.4. Now the second condition of the theorem may be phrased thus: there is a small set 𝕊_{B} and a functor 𝕊_{B} ^{v}^{}(B, f) such that the property (P) holds for u = v (by taking \overline{x} = A, \overline{y} = yf).

(P) For every object x in the codomain of u, there is an object \overline{x} in the domain of u and a map \overline{x}u ^{\overline{y}}^{}x in the codomain of u.

Since it is clear that property (P) also holds for u in the diagram below, where ℂ_{B} is the full subcategory of (B, f) determined by the image of v,

𝕊_{B}  \overline{v  ^{}}(B, f)
[figure: ..............; u]
ℂ_{B}

the following lemma proves Theorem 2.4; it is also clear that since 𝔸 is complete, 𝔻 = (B, f) has pseudomeets in the sense that for every pair of maps D′ ^{d′}^{}D, D′′ ^{d′′}^{}D in 𝔻 with common codomain, there exists a commutative diagram:

[figure: \overline{D}; D′′; D′; d′; D; d′′]

Lemma. Let ℂ ^{u}^{}𝔻 be a full functor with property (P) where ℂ is small and 𝔻 has pseudomeets. Then u is left pacing.

Proof of Lemma. Consider 𝔻 ^{t}^{}𝔸, 𝔸 left complete; we must show ut^{←} ≅ t^{←} (so that in particular t^{←} exists). By (P) we can, for each D ∈ |𝔻|, choose a definite C_{D}u ^{\overline{y}_{D}}^{}D (C_{D} ∈ |ℂ|) and then define \overline{λ}_{D} to be the composition

ut^{←} ^{λ_{C_{D}}}^{}C_{D}ut ^{\overline{y}_{D}t}^{}Dt

where λ_{C} are the canonical maps associated with ut^{←}. We wish to show that for every D ^{d}^{}D′ in 𝔻, \overline{λ}_{D}(dt) = \overline{λ}_{D′}. Since 𝔻 has pseudomeets we can find \overline{D} and maps such that

C_{D}u \overline{^{\overline{y}_{D}} ^{}}D

[figure]

C\overline{D}u \overline{^{\overline{y}\overline{D}} ^{}}\overline{D}

[figure]

[figure: C_{D′}u; \overline{y}_{D′}; D′; d]

is commutative. Since u is full, the composite maps Cu ^{}C_{D}u and Cu ^{}C_{D′}u ‘come from’ ℂ. Thus on applying t we find that the parts, and hence the whole of the diagram below are commutative:

C_{D}ut  \overline{\overline{y}_{D}t  ^{}}Dt
[figure: λ_{C_{D}}]
ut^{←}  \overline{λ_{C\overline{D}}  ^{}}C\overline{D}ut
[figure: λ_{C_{D′}}] [figure]
[figure: C_{D′}ut; \overline{y}_{D′}t; D′t; dt]

Thus \overline{λ}_{D}(dt) = \overline{λ}_{D′}. We now show the universality of \overline{λ}. Suppose that for each D ∈ |𝔻|, X ^{ψ_{D}}^{}Dt, and for every D ^{d}^{}D′, ψ_{D}(dt) = ψ_{D′} in 𝔸. Then in particular ψ_{Cu}(ct) = ψ_{C′u} for every C ^{c} ^{}C′ in ℂ. Therefore there is a unique z such that X ^{z}^{}ut^{←} and for all C ∈ |ℂ|, ψ_{Cu} = zλ_{C} in 𝔸. But then we have (in 𝔸)

z\overline{λ}_{D} = zλ_{C_{D}}(\overline{y}_{d}t) = ψ_{C_{D}u}(\overline{y}_{D}t) = ψ_{D}.

Since z is also the unique map such that the latter relation holds, the proof of the lemma, and hence of Theorem 2.4, is complete.

Remark. In view of the above two theorems, it is a reasonable conjecture that any given left continuous functor has an adjoint. However, as shown by [Gaifman, 1961], the inclusion of complete small Boolean algebras into all small Boolean algebras does not have an adjoint; hence this family of conjectures cannot be made into a general theorem which omits ‘smallness’ hypotheses like those of Theorems 2.3 and 2.4. The above theorems also suggest that inverse limits are in a sense the ‘canonical’ means for constructing adjoints, whereas the usual constructions of particular adjoint in algebra often look like direct limits (e.g. the tensor product is a quotient of a sum). Some light is shed on this ‘mystery’ by Theorem 2.5 below, together with the observation (substantiated by Chapters III and IV of this paper) that the common functors in algebra are usually closely associated with induced functors between functor categories.

We mention some propositions concerning adjoints of such functors before stating and proving our theorem.

Proposition 1. Let 𝔸 be any small category, X ^{T}^{}Y any functor with an adjoint T̂. Then the induced functor

X^{𝔸} ^{T^{𝔸}}^{}Y^{𝔸}

has the adjoint T̂^{𝔸}.

Proposition 2. If X is left complete and 𝔸 small, then X^{𝔸} is left complete. If 1 ^{A}^{}𝔸 is any object in 𝔸, then the ‘evaluation’ functor

X^{𝔸} ^{X^{A}}^{}X

is left continuous (i.e limits in X^{𝔸} are computed ‘pointwise’).

Proposition 3. If X is left complete and ℂ, 𝔻 are any small categories, then

lim^{X^{𝔻}}_{←ℂ} lim^{X}_{←𝔻} ≅ lim^{X^{ℂ}}_{←𝔻} lim^{X}_{←ℂ}

is a natural equivalence of functors X^{ℂ×𝔻} ^{}X.

The above propositions have obvious dualizations. Proofs will be found, e.g. in [Gray, Theorem 5. Let X be complete, 𝔸, 𝔹 small, and let 𝔹 ^{f}^{}𝔸 be any functor. Then the induced functor

X^{𝔸} ^{X^{f}}^{}X^{𝔹}

has an adjoint. More explicitly, if 𝔹 ^{U}^{}X is any functor, then the value \overline{U} of the adjoint at U is given by the formula

A\overline{U} = lim^{X}_{→(f,A)}(d_{0}^{A}U)

where 1 ^{A}^{}𝔸 is any object in 𝔸 and where d_{0}^{A} is the canonical functor in the meet diagram:

[figure: (f, A); 𝔸^{2}; 𝔹; d_{0}^{A}; f; 𝔸; D_{0}]

Proof. We use again the characterization of Theorem 2.1. Let \overline{U} be defined by the above formula. Since \overline{U}X^{f} = f\overline{U}, our first task is to construct a map

U ^{φ}^{}f\overline{U}

in X^{𝔹}. Since for 1 ^{B}^{}𝔹,

Bf\overline{U} = lim_{→}[(f, Bf) ^{d_{0}}^{}𝔹 ^{U}^{}X],

we have for each map

B′f  \overline{bf  ^{}}B′′f
[figure: x′; 𝔸; x′′]
Bf

in (f, Bf), maps λ_{x′}^{Bf}, λ_{x′′}^{Bf} in X such that:

B′U
[figure: λ_{x′}^{Bf}]
(Bf)\overline{U}
[figure: λ_{x′′}^{Bf}]
B′′U bU_{}

satisfying the universal properties of direct limits. In particular, taking B = B′ and x′ = Bf = B′f = x′′, we get a map

BU ^{φ_{B}}^{}Bf\overline{U}

by defining φ_{B} = λ_{Bf}^{Bf}.

We need to show that whenever B ^{b}^{}B′ in 𝔹,

BU  \overline{φ_{B}  ^{}}Bf\overline{U}
X
[figure: B′U; bU; φ_{B′}; B′f\overline{U}; (bf)\overline{U}]

Now \overline{U} is defined for maps A ^{a}^{}A′ in 𝔸 as follows. Since there is an induced functor (f, A) ^{}(f, A′), there is a map linking the direct limits over these two categories, defined uniquely by the universal property of λ^{A} in the following typical diagram

BU = xd_{0}U
[figure: λ_{x}^{A}; λ_{xa}^{A′}]
A\overline{U}  ^{a\overline{U}  ^{}}A′\overline{U}
[figure: λ_{x′}^{A}; λ_{x′a}^{A′}]
B′U = x′d_{0}U bU_{}

where

[figure: Bf; bf; B′f; Bf; bf; B′f]
[figure: x; 𝔸; x′; (f, a); xa; 𝔸; x′a]
A  A′

for a typical map in (f, A).

In particular, for A = Bf, a = bf, we have λ_{x}^{Bf}(bf) = λ_{x(bf)}^{Bf}. Taking x = bf, this gives

λ_{Bf}^{Bf}(bf)\overline{U} = λ_{bf}^{B′f}.

On the other hand, since

Bf  \overline{bf  ^{}}B′f
[figure: bf; B′f]
B′f

is a map in (f, B′f), we have

(bU)λ_{B′f}^{B′f} = λ_{bf}^{B′f}.

Recalling the definition of φ, this shows

φ_{B}(bfU) = (bU)φ_{B′}

for every B ^{b}^{}B′ in 𝔹. Hence φ is natural, i.e. U ^{φ}^{}f\overline{U} is a map in X^{𝔹}. Now suppose T is any object in X^{𝔸} and

U ^{ξ}^{}fT

any map in X^{𝔹}. We wish to show that there is a unique \overline{U} ^{η}^{}T in X^{𝔸} that φ(ηX^{f}) = ξ. Now by assumption

Bf  \overline{bf  ^{}}B′f
[figure: x; x′]
A

implies

BU  \overline{ξ_{B}  ^{}}BfT
[figure: xT]
AT
[figure: x′T]
[figure: B′U; bu; ξ_{B′}; B′fT; bfT]

i.e. for every x ∈ |(f, A)| we have a map xd_{0}U = BU ^{ξ_{B} (xT)}^{}AT which commutes with every x ^{b}^{}x′. Since A\overline{U} = lim_{→} d_{0}^{A}U, we have a unique A\overline{U} ^{η_{A}}^{}AT such that λ_{x}^{A}η_{A} =

ξ_{B}(xT) for all objects Bf ^{x} ^{}A in (f, A). For every A ^{a} ^{}A′ in 𝔸, λ_{x}^{A}η_{A}(aT) = ξ_{B}(xT)(aT) = ξ_{B}(xa)T = λ_{xa}^{A′}η_{A′} = λ_{x}^{A}(a\overline{U})η_{A′}. That is η_{A}(aT) = (a\overline{U})η_{A′} at each λ_{x}^{A}, hence by uniqueness η is natural, i.e. a map

\overline{U} ^{η}^{}T

in X^{𝔸}. A particular case of the foregoing calculation is that associated with the object Bf ^{Bf}^{}Bf in (f, Bf). We have

ξ_{B} = ξ_{B}(Bf)T = λ_{Bf}^{Bf}η_{Bf} = φ_{B}η_{Bf} = φ_{B}(ηX^{f})_{B}

for every B ∈ |𝔹|, i.e. φ(ηX^{f}) = ξ as required. However, since the latter is only a special case of the condition which originally defined η, its uniqueness may be in doubt; but this follows from φ(ηX^{f}) = ξ, together with the required fact that η is natural. That is, from

\begin{aligned}ξ_{B} & = & λ_{Bf}^{Bf}η_{Bf} \\ η_{A}(aT) & = & (a\overline{U})η_{A′} , for all A ^{a}^{}A′ \end{aligned}

it follows that

ξ_{B}(xT) = λ_{Bf}^{Bf}η_{Bf}xT = λ_{Bf}^{Bf}(x\overline{U}η_{A}) = λ_{(Bf)x}^{A}η_{A} = λ_{x}^{A}η_{A}

for any Bf ^{x}^{}A, and the latter condition does determine η.

In particular, if 𝔹 = 1, 1 ^{f=A_{0}}^{}𝔸, then (f, A) = (A_{0}, A) is a set, d_{0}U is constant, so lim_{→} is the (A_{0}, A)-fold coproduct. Thus we have the

Corollary. If X is complete, 𝔸 small, A_{0} ∈ |𝔸|, then the evaluation at A_{0}

X^{𝔸} ^{}X

has an adjoint. For each X ∈ X, the value of the adjoint at X is the functor whose value at A ∈ |𝔸| is (A_{0}, A) · X.

Thus for every 𝔸 ^{T}^{}X we have

(H^{A_{0}} · X, T) ≅ (X, A_{0}T)

where 𝔸 ^{H^{A_{0}}}^{}S_{1} is the functor whose value at A is (A_{0}, A) and where H^{A_{0}}·X is the functor 𝔸 ^{}X, its value at A is the (A, A_{0})-fold coproduct of X with itself.

In particular, taking X = S_{1}, X = 1_{S_{1}}, we have another

Corollary. For every functor 𝔸 ^{T}^{}S_{1} where 𝔸 is small, and for every A_{0} ∈ |𝔸|,

(H^{A_{0}}, T) = A_{0}T.

Corollary. For any small 𝔸, the functor

𝔸^{∗} ^{}S_{1}^{𝔸}

which takes A_{0} to H^{A_{0}} is full.

3. Regular epimorphisms and monomorphisms

In this section we work in an arbitrary but fixed category, which we will presently require to have finite limits.

Definition. A map K ^{k}^{}A is said to be a regular monomap iff there exist A [figure: f; g] B

such that k = fEg. Dually, a regular epimap is any map having the properties of a coequalizer.

Remark. The notions of regular monomaps and epimaps seem better suited (say in the category of topological spaces) for discussing subobjects and quotient objects than do the more inclusive notions of monomorphisms and epimorphisms. Clearly in any category every retract is a regular monomap and every regular monomap is a monomorphism, (and dually); all these notions, however, can be different. We require in this paper only two or three propositions from the theory of regular epimaps and monomaps.

Proposition 1. If k is an epimorphism and also a regular monomap, then k is an isomorphism.

Proof. If k = fEg, then since k is an epimorphism f = g. Hence K ≅_{k} A.

For the next two propositions assume that our category has finite limits.

Proposition 2. A map k is a regular monomap iff k = (j_{1}q)E(j_{2}q) where q = (kj_{1})E^{∗}(kj_{2}).

K ^{k}^{}A [figure: j_{1}; j_{2}] A ⋆ A ^{q}^{}Q

Proof. Suppose k = fEg. Define t by

[figure: A; j_{1}; A ⋆ A; j_{2}; A]
[figure: f; g]
B t_{}

and let h = (j_{1}q)E(j_{2}q). Then obviously k ≤ h. To show h ≤ k, note that kj_{1}t = kj_{2}t since k = (j_{1}t)E(j_{2}t). That is, t ‘coequalizes’ kj_{1}, kj_{2}. Hence ∃!Q ^{u}^{}B such that t = qu. Then

hf = hj_{1}t = hj_{1}qu = hj_{2}qu = hj_{2}t = hg

where the third equation follows from hj_{1}q = hj_{2}q. Therefore ∃!M ^{z}^{}K such that zk = h, i.e h ≤ k.

[figure: K; k; A; j_{1}; j_{2}; A ⋆ A; q; Q]
[figure: h; t; ..................................; u]
[figure: H; z; B; f; g]

Dually an epimap is regular iff it is the coequalizer of the relation it induces on its domain.

Proposition 3. If k_{1} is a monomorphism and k_{2}k_{1} is a regular monomap, then k_{2} is a regular monomap, and dually.

Proof. Consider

\begin{aligned}q_{3} & = & (k_{2}k_{1}j_{1})E^{∗}(k_{2}k_{1}j_{2}) \\ k_{2}k_{1} & = & (j_{1}q_{3})E(j_{2}q_{3}) \\ q_{2} & = & (k_{2}i_{1})E^{∗}(k_{2}i_{2}) \end{aligned}

K_{2}
.............. z ^{}
X
[figure: x]
[figure: K_{1}; k_{2}; k_{1}; A]

[figure: K_{1} ⋆ K_{1}; i_{1}; i_{2}; k_{1} ⋆ k_{1}; A ⋆ A; j_{1}; j_{2}]

[figure: Q_{2}; q_{2}; v; Q_{3}; q_{3}]

We must show k_{2} = (i_{1}q_{2})E(i_{2}q_{2}). Now k_{2} ‘equalizes’ i_{1}q_{2}, i_{2}q_{2} by definition of q_{2}. We get v since (k_{1} ⋆ k_{1})q_{3} coequalizes k_{2}i_{1}, k_{2}i_{2}, i.e. is a ‘candidate’ for q_{2}. Thus if xi_{1}q_{2} = xi_{2}q_{2}, it follows that xk_{1} equalizes j_{1}q_{3}, j_{2}q_{3}, i.e. is a candidate for k_{2}k_{1}. Therefore ∃!z[xk_{1} = zk_{2}k_{1}]. But k_{1} is a monomorphism, so x = zk_{2}. Finally, z satisfying the last equation is unique, since k_{2} is a monomorphism.

Chapter II

Algebraic theories

1. The category of algebraic theories

Before discussing the category of algebraic theories, we briefly consider the category ({S_{0}}, C_{1}), of which the category of algebraic theories will be a subcategory. Recall that the maps in the category ({S_{0}}, C_{1}) may be identified as commutative triangles

S_{0}
[figure: A; B]
𝔸  \overline{f  ^{}}𝔹

of functors where S_{0} is (any fixed small version of) the category of finite sets and 𝔸, 𝔹 are any small categories. For definiteness suppose |S_{0}| ≅ N.

Definition. Let S_{0} ^{A}^{}𝔸 be an object in ({S_{0}}, C_{1}). If n is any object in S_{0}, we will denote by _{n}A the value at n of A; thus _{n}A is an object in 𝔸. If σ is any map in S_{0}, we will sometimes simply write σ for the value of σ at A. However, in the special case of maps 1 ^{i}^{}n in S_{0}, we will usually write π_{i}^{n} for the value at i of A. For any objects n is S_{0}, an n-ary operation of 𝔸 means any map _{1}A ^{θ}^{}_{n}A in 𝔸. (Note that the notion of n-ary operation really depends on A, not just on 𝔸; however, in what follows we will be justified in the abuse of notation which confuses A with 𝔸.) In particular, each π_{i}^{n}, where i ∈ n in S_{0}, is an n-ary operation of every 𝔸.

Proposition 1. The category ({S_{0}}, C_{1}) has products and coproducts. In fact, the codomain functor ({S_{0}}, C_{1}) → C_{1} is left continuous and (binary) coproducts in ({S_{0}}, C_{1}) are defined by comeet diagrams of the form

S_{0}  \overline{B  ^{}}𝔹
C_{1}
[figure: 𝔸; A; 𝔸 ⋆_{S_{0}} 𝔹]

Proof. These assertions in fact remain valid if C_{1} is replaced by any complete category and {S_{0}} by any object in it. The left continuity statement is obvious. We explicitly verify the ‘coproduct = comeet in C_{1}’ assertion. Let A ^{f}^{}C, B ^{g}^{}C be any maps in ({S_{0}}, C_{1}). Since this implies that Af = C = Bg in C_{1}, and since 𝔸 ⋆_{S_{0}} 𝔹 is a comeet in C_{1},

there exists a unique h in C_{1} such that

S_{0}  \overline{B  ^{}}𝔹
[figure: A ⋆_{S_{0}} B; g]
[figure: 𝔸; A; j; 𝔸 ⋆_{S_{0}} 𝔹; k]
[figure: f] .............. h _{}
ℂ

is commutative in C_{1}. But then h defines the unique map 𝔸 ⋆_{S_{0}} 𝔹 ^{h}^{}ℂ in ({S_{0}}, C_{1}) such

that f = jh and g = kh, i.e. S_{0} ^{A ⋆_{S_{0}}B}^{}𝔸 ⋆_{S_{0}} 𝔹 is the coproduct in ({S_{0}}, C_{1}) of A, B. (The

same proof clearly works for infinite coproducts.) In view of the nature of comeets in C_{1}, this means that in the ({S_{0}}, C_{1})-coproduct any map n ^{x}^{}m is represented by a string

n ^{x_{0}}^{}n_{0} ^{x_{1}}^{}n_{1} → ⋯ → n_{ℓ−2} ^{x_{ℓ−1}}^{}m

where each x_{i} is a map n_{i−1} → n_{i} in either 𝔸 or 𝔹 (n_{−1} being n and n_{ℓ−1} being m); the only relations imposed on strings are that ⟨σA⟩ = ⟨σB⟩ for all σ ∈ S_{0} and that ⟨x_{0}x_{1}⟩ = ⟨y_{0}⟩ if x_{0}x_{1} = y_{0} in 𝔸 or in 𝔹 (and consequences of these relations).

Definition. The category T of algebraic theories is the full subcategory of ({S_{0}}, C_{1}) determined by those objects S_{0} ^{A}^{}𝔸 such that A commutes with finite coproducts and such that |A| is an isomorphism.

Thus for an algebraic theory S_{0} ^{A}^{}𝔸 we have in essence that every object in 𝔸 is of the form _{n}A and that furthermore _{(n+m)}A = _{n}A ⋆_{m}A in 𝔸 for all n, m ∈ |S_{0}|. In view of the structure of S_{0}, the latter condition is equivalent to

nA = n ·_{1}A

for every n ∈ |S_{0}|, where the right-hand side is the n-fold coproduct of _{1}A with itself in 𝔸. It follows immediately that _{1}A is a generator for 𝔸, and that _{0}A = lim^{𝔸}_{→0} (i.e. ∀n ∃! [_{0}A ^{}_{n}A]). The equation _{n}A = n ·_{1}A implies that the maps n ^{}m in 𝔸 are in one-to-one correspondence with n-tuples of m-ary operations of 𝔸.

Proposition 2. Let S_{0} ^{A}^{}𝔸 be an algebraic theory and consider the map _{0}A ^{}_{1}A in 𝔸. This map is always a monomorphism, and if there exists x such that _{1}A ^{x}^{}_{0}A in 𝔸 then _{0}A ^{}_{1}A is a retract.

Proof. If there is no such x, then there is no map from any _{n}A to _{0}A and so _{0}A ^{}_{1}A is vacuously a monomorphism. If there is such an x, then _{0}A ^{}_{1}A ^{x}^{}_{0}A must be the identity since _{0}A = lim^{𝔸}_{→0}.

A particular example of an algebraic theory is the identity functor S_{0}, which we will sometimes call ‘the theory of equality’. It is clear that S_{0} ≅ lim^{T}_{→0}. Any theory S_{0} ^{A}^{}𝔸 such that 𝔸 is equivalent to either 2 or 1 will be called inconsistent.

Proposition 3. Let S_{0} ^{A}^{}𝔸 be an algebraic theory. If there are m [figure: σ; τ] n′ in S_{0}, σ ≠ τ,

such that σA = τA, then the theory is inconsistent.

Proof. For any n ≥ 2, there is n′ ^{τ′}^{}n such that στ′ ≠ ττ′ and 1 ^{j}^{}m such that i_{0} = jστ′ ≠ jττ′ = i′_{0}, but π_{i_{0}}^{n} = π_{i′_{0}}^{n}. There are also n ^{\overline{σ}}^{}n − 1 and n − 1 ^{\overline{τ}}^{}n such

that i_{0}\overline{σ} = i′_{0}\overline{σ} and τ̄σ̄ = n − 1. Then for all 1 ^{i}^{}n, π_{iσ̄τ̄}^{n} = π_{i}^{n}. Since _{n−1}A and _{n}A are coproducts, there are unique _{n}A ^{f}^{}_{n−1}A and _{n−1}A ^{g}^{}_{n}A such that

π_{i\overline{σ}}^{n−1} = π_{i}^{n}f  for all i ∈ n
π_{j\overline{τ}}^{n} = π_{j}^{n−1}g for all j ∈ n − 1.

Now we have gf = _{n−1}A in any case, and due to our hypotheses we have π_{i}^{n}fg = π_{i\overline{σ}}^{n−1} = π_{i\overline{σ}\overline{τ}}^{n} = π_{i}^{n} for all 1 ^{i}^{}n and thus

n−1A ≅ _{n}A for all n ≥ 2.

It follows that

nA ≅ _{1}A for all n ≥ 1,

where the isomorphisms are all induced by maps coming from S_{0}. From this it follows that π_{0}^{2} = π_{1}^{2}, since we always have π_{0}^{2}σ = _{1}A = π_{0}^{2}σ for 2 ^{σ}^{}1, and in our case σA has an inverse. From this it is immediate that

(_{n}A,_{m}A) = 1

for any n and for m ≠ 0. But this implies that 𝔸 is equivalent to either 1 or 2.

Now, since the compositions 0 ^{}1 [figure] 2 are equal in S_{0}, for any algebraic theory 𝔸 we have equal compositions

0A ^{}_{1}A [figure] _{2}A

in 𝔸 and hence equal compositions of maps between sets

(_{1}A,_{0}A) ^{}(_{1}A,_{1}A) [figure] (_{1}A,_{2}A).

However, (_{1}A,_{0}A) need not to be the equalizer of the other two maps. If we denote this equalizer by K, then members of K are called definable constants of the theory. Clearly every expressible constant determines a definable one via 0 ^{}1. Explicitly, a definable constant is a unary operation θ such that θπ_{0}^{2} = θπ_{1}^{2}; an expressible constant is any zero-ary operation.

Proposition 4. If θ is a definable constant of an algebraic theory 𝔸 and if φ is any unary operation, then φθ is a definable constant and θφ = θ.

Proof. The first assertion is obvious and the second follows from the diagram

1A  \overline{φ  ^{}}_{1}A
[figure: θ; _{1}A]
[figure: _{1}A; _{2}A; π_{0}^{2}; _{2}A; π_{0}^{2}; _{1}A]
[figure: θ; _{1}A]
[figure: _{1}A; π_{1}^{2}; _{1}A; _{1}A; π_{1}^{2}]

Proposition 5. For any algebraic theory S_{0} ^{A}^{}𝔸, either every definable constant is expressible or none are. That is, either (_{1}A,_{0}A) ≅ K or (_{1}A,_{0}A) = 0.

Proof. Suppose there exists _{1}A ^{x}^{}_{0}A and let θ be any definable constant. Then by the second assertion of Proposition 1.4, the composite

1A ^{θ}^{}_{1}A ^{x}^{}_{0}A ^{}_{1}A

equals θ, i.e. θx expresses θ.

Note that the ‘expression’ is faithful by Proposition 1.2.

Remark. Evidently one could ‘complete’ (or deplete) algebraic theories with regard to expressibility of constants; however, there seems to be no need to do so. As an example, the algebraic theory of groups can be ‘presented’ (see Section 2) in two ways, one involving a single binary operation x, y ^{}x · y^{−1} as generator, and the second involving a 0-ary generator e, a unary generator x ^{}x^{−1}, and a binary generator x, y ^{}x · y. This actually gives two theories, for in the first case no constant is expressible and in the second case the (only) constant e is expressible. These two theories also give rise to different algebraic categories (see Chapter III), for according to the first theory the empty set is a group, whereas to the second it is not.

Theorem 1. The category T of algebraic theories is complete. Neither the first functor nor the composite in the diagram below

T ^{}({S_{0}}, C_{1}) ^{}C_{1}

is left continuous; coproducts and coequalizers are as described in Lemma 1.1 and Lemma 1.2 below.

Proof. The completeness of the middle category follows from two facts

(1) coproducts are computed coordinate-wise in a product of categories

(2) if k = fEg in C_{1}

S_{0}
[figure: ..............; K; B]
[figure: 𝕂; k; 𝔸; A; f; g; 𝔹]

where A and B are algebraic theories, then K commutes with finite coproducts. To see this consider _{1}K ^{θ_{i}}^{}_{m}K, θ_{i} ∈ 𝕂, i ∈ n. There is a unique y ∈ 𝔸 such that

1Kk
[figure: θ_{i}k]
[figure: _{n}Kk; π_{i}^{n}; y; _{m}Kk]

We need only show ∃x ∈ 𝕂 [y = xk], which will follow from the fact that yf = yg. But this follows at once from the fact that θ_{i}kf = θ_{i}kg, i ∈ n, and A, B, f, g commute with finite coproducts.

Direct limits in T are described by the following lemmas.

Lemma 1. Let Λ be any small set and Λ ^{𝔸}^{}T any functor. Then the coproduct \overline{𝔸} = ⋆_{λ∈Λ}𝔸_{λ} in T may be constructed as follows.

0. If 1 ^{θ}^{}n is a map in some 𝔸_{λ}, then 1 ^{θ}^{}n is a map in \overline{𝔸}.

1. If 1 ^{ϕ_{i}}^{}m, i ∈ n are any maps in \overline{𝔸}, then \{ϕ_{0} … ϕ_{n−1}\} is a map n ^{}m in \overline{𝔸}.

2. If n ^{ϕ}^{}n′ ^{ψ}^{}n′′ are any maps in \overline{𝔸}, then n ^{ϕψ}^{}n′′ is a map in \overline{𝔸}.

3. All maps in \overline{𝔸} are represented by expressions obtained by some finite number of applications of 0,1,2. However, the following relations are imposed on these expressions, as are all relations that follow by reflexivity, symmetry, or transitivity from (a) through (i):

(a) If ϕ ≡ ϕ′ and ψ ≡ ψ′ then ϕψ ≡ ϕ′ψ′,

(b) In some 𝔸_{λ},
1  1
[figure: θ_{i}; ψ_{i}] [figure: φ_{j}]

n′ π_{j}^{n′}_{}
[figure: θ; φ]
[figure: n; π_{i}^{n}; ψ; n′′]

π_{i}^{n}θ = θ_{i} , i ∈ n
π_{j}^{n′}φ = φ_{j} , j ∈ n′
π_{i}^{n}ψ = ψ_{i} , i ∈ n
θφ = ψ

the θ_{i} being n′-ary operations, the φ_{j} being n′′-ary operations and the ψ_{i} also being n′′-ary operations, all of 𝔸_{λ}, then

{θ_{0} … θ_{n−1}}{φ_{0} … φ_{n′−1}} ≡ {ψ_{0} … ψ_{n−1}}.

(c) For any σ ∈ S_{0} and any λ, λ′ ∈ Λ, σA_{λ} ≡ σA_{λ′}.

(d) π_{i}^{n}{ϕ_{0} … ϕ_{n−1}} ≡ ϕ_{i}, i ∈ n, where 1 ^{ϕ_{i}}^{}m for all i ∈ n.

(e) If θ_{i} ≡ θ′_{i}, i ∈ n, where θ_{i}, θ′_{i} are m-ary, then {θ_{0} … θ_{n−1}} ≡ {θ′_{0} … θ′_{n−1}}.

(f) For any n ^{ϕ}^{}m, ϕ = {π_{0}^{n}ϕ … π_{n−1}^{n}ϕ}.

(g) {θ_{0} … θ_{n−1}}{π_{o}^{m} … π_{m−1}^{m}} ≡ {θ_{0} … θ_{n−1}} {π_{0}^{m} … π_{m−1}^{m}}{ϕ_{0} … ϕ_{m−1}} ≡ {ϕ_{0} … ϕ_{m−1}} where the θ_{i} are all m-ary and ϕ_{j} are all k-ary operations of \overline{𝔸}.

(h) θ(ϕψ) ≡ (θϕ)ψ.

(i) For each n, {π_{0}^{n} … π_{n−1}^{n}} ≡ n.

4. Domain and codomain in \overline{𝔸} were specified in the construction, and composition in \overline{𝔸} is by concatenation of representative expressions. Inclusion functors 𝔸_{λ} ^{}\overline{𝔸} are defined in the obvious fashion, and, in view of 3.(c), there is a unique S_{0} ^{\overline{A}}^{}\overline{𝔸} which, for every λ, is equal to A_{λ} composed with the λ-th inclusion.

Proof. \overline{𝔸} is clearly a small category and the inclusions 𝔸_{λ} ^{}𝔸 are clearly functors, as is \overline{A}. We first show that \overline{𝔸} is a theory, i.e. that \overline{𝔸} commutes with finite coproducts. It suffices to show

n\overline{A} ≅ n ·_{1}\overline{A}

the right-hand side being an n-fold coproduct in \overline{𝔸}. So let ϕ_{i}

1\overline{A}
[figure: ϕ_{i}]
[figure: _{n}\overline{A}; π_{i}^{n}; ϕ; _{m}A]

be any maps in \overline{𝔸} and define ϕ = \{ϕ_{0} … ϕ_{n−1}\}. By 3.(d), π_{i}^{n}ϕ = ϕ_{i}. If π_{i}^{n}ϕ′ = ϕ_{i}, then ϕ′ = \{π_{o}^{n}ϕ′ … π_{n−1}^{n}ϕ′\} = \{ϕ_{0} … ϕ_{n−1}\} = ϕ. Thus maps n ^{ϕ}^{}m in \overline{𝔸} correspond exactly to n-tuples of m-ary operations of \overline{𝔸}, i.e. \overline{A} commutes with finite coproducts.

We must also show that \overline{𝔸} = ⋆_{λ∈Λ}𝔸_{λ} in T . So let S_{0} ^{C}^{}ℂ be any object in (\{S_{0}\}, C_{1})

such that |C| is an isomorphism and C commutes with finite coproducts, and let

S_{0}
[figure: C]

λ ∈ Λ
[figure: 𝔸_{λ}; A_{λ}; f_{λ}; ℂ]

be commutative diagrams. Define \overline{𝔸} ^{f}^{}ℂ as follows:

0. If 1 ^{θ}^{}n in 𝔸_{λ}, (θ)f = (θ)f_{λ}.

1. If n ^{ϕ}^{}n′ ^{ψ}^{}n′′ then (ϕψ)f = (ϕ)f(ψ)f.

2. If 1 ^{ϕ_{i}}^{}m, i ∈ n, then {ϕ_{0} … ϕ_{n−1}}f = y where y is the unique map n ^{y}^{}m in ℂ such that π_{i}^{n}y = (ϕ_{i})f.

This defines f on the expressions, and by 3.(a) and 3.(e), f remains well defined on \overline{𝔸}. By definition f is a functor, and λ-th inclusion composed with f is f_{λ}. If f′ has the latter two properties, then f′ satisfies the conditions 0. and 1. in the definition of f. Since \overline{A} and C commute with coproducts, so must f′, i.e. f′ satisfies the condition 2. in the definition of f. Thus f′ = f, so that f is unique.

In an arbitrary algebraic theory we will sometimes use the notation introduced in Lemma 1.1, namely if ⟨θ_{0} … θ_{n−1}⟩ is an n-tuple of m-ary operations, then {θ_{0} … θ_{n−1}} is the unique n ^{}m such that

π_{i}^{n}{θ_{0} … θ_{n−1}} = θ_{i} for i ∈ n.

Definition. By a congruence relation R in an algebraic theory 𝔹 is meant the following.

(0) For each n, m ∈ |S_{0}|, R_{n,m} ⊆ (_{n}B,_{m}B) × (_{n}B,_{m}B).

(1) If n [figure: θ; θ′] n′ [figure: φ; φ′] n′′ in 𝔹 with ⟨θ, θ′⟩ ∈ R_{n,n′} and ⟨φ, φ′⟩ ∈ R_{n′,n′′}, then

⟨θφ, θ′φ′⟩ ∈ R_{n,n′′}.

(2) 1 [figure: θ_{i}; θ′_{i}] m in 𝔹 and ⟨θ_{i}, θ′_{i}⟩ ∈ R_{1,m} for i ∈ n implies

⟨{θ_{0} … θ_{n−1}}, {θ′_{0} … θ′_{n−1}}⟩ ∈ R_{n,m}.

(3) Each R_{n,m} is reflexive, symmetric, and transitive.

It is clear that for any algebraic theory 𝔹 and any congruence relation R in 𝔹, we have 𝔹 ^{η}^{}𝔹/R in T such that ⟨θ, θ′⟩ ∈ R_{n,m} ⇒ θη = θ′η and such that given any 𝔹 ^{f}^{}ℂ in T with the same property, there is a unique completion of the commutative triangle

𝔹
[figure: η; f]
𝔹/R  ^{}ℂ

and that, furthermore, η is full (as a map of categories).

Lemma 2. Let 𝔸 [figure: f; g] 𝔹 in T . Define R_{n,m} to be the set of all pairs n [figure: θ; θ′] m in 𝔹 such

that φf = θ and φg = θ′ for some φ in 𝔸, together with all pairs obtained from these by repeated applications of reflexivity, symmetry, transitivity, composition, and { }. Then R is a congruence relation in 𝔹 and the natural 𝔹 ^{η}^{}𝔹/R is the coequalizer of f, g; i.e. η = fE^{∗}g. Furthermore, R_{n,m} is also the set of all ⟨θ, θ′⟩ such that θη = θ′η

Proof. It is obvious from the definition that R is the smallest congruence relation containing the set of pairs ⟨θ, θ′⟩ for which φf = θ and φg = θ′ for some φ ∈ 𝔸, and the other assertions follow readily from this fact.

2. Presentations of algebraic theories

We define a functor

T ^{T}^{}S_{1}^{N}

as follows. For each algebraic theory 𝔸 ∈ |T |, 𝔸T is the sequence of sets whose nth term is the set (_{1}A,_{n}A). That is, (𝔸T)_{n} is the set of n-ary operations of 𝔸. For each 𝔸 ^{f} ^{}𝔹 in T , fT is the sequence of maps in S_{1} such that (fT)_{n} = (_{1}A, f_{n}) : (_{1}A,_{n}A) ^{}(_{1}B,_{n}B). Clearly T is a functor.

Theorem 1. There is a free algebraic theory over each sequence of small sets, i.e. T has an adjoint F. Further, given any algebraic theory 𝔸, there exists a free algebraic theory 𝔽 and regular epimap 𝔽 ^{}𝔸 in T .

Proof. We first consider a sequence of special cases. Let n ∈ N = |S_{0}|. Define 𝕀_{n} to be the algebraic theory constructed as follows: adjoin a single n-ary operation to S_{0}, consider all expressions formed from S_{0} and this n-ary operation by means of composition and { }, and impose on these expressions relations analogous to those under 3 in Lemma 1.1. Then for any algebraic theory 𝔸,

(𝕀_{n}, 𝔸) ≅ (_{1}A,_{n}A) ≅ (δ_{n}, 𝔸T)

where δ_{n} is the sequence of sets whose k-th entry is 1 if k = n, otherwise 0. Hence 𝕀_{n} is the free algebraic theory over δ_{n}.

Now for any sequence N ^{S}^{}S_{1} of small sets

S = ∑_{n∈N} S_{n} · δ_{n}.

Hence, since adjoint functors are right continuous,

SF = ⋆_{n∈N}S_{n} · 𝕀_{n}

is the free algebraic theory over S.

The second assertion of Theorem 2.1 follows from the more refined statements of Lemmas 2.1 and 2.2.

Lemma 1. For each algebraic theory 𝔸, any n ∈ N, and any 𝕀_{n} ^{}𝔸 in T , there exists a lifting

𝕀_{n}
..............
[figure: 𝔸T F; 𝔸]

Proof. Since 𝕀_{n} = δ_{n}F, the proof is immediate from the characterization of coadjoints (i.e. the dual of Theorem I.2.1)

Lemma 2. If 𝔸 ^{f} ^{}𝔹 in T , then f is a regular epimap iff for every n ∈ N, every 𝕀_{n} ^{}𝔹 admits a lifting

𝕀_{n}
..............
[figure: 𝔸; f; 𝔹]

Proof. The lifting condition is equivalent to f being onto, and it is clear from our discussion of direct limits in T that a map of theories is onto iff it is the coequalizer of the congruence it induces, which by Proposition I.3.2 is equivalent to being a regular epimap.

Definition. By a presentation of an algebraic theory is meant a triple ⟨S, E, f⟩ where S, E ∈ |S_{1}^{N}| and where f : E ^{}SF T × SF T in S_{1}^{N}. The theory presented by ⟨S, E, f⟩ is the coequalizer in T of the maps

EF [figure] SF

corresponding to fp, fp′ under the natural isomorphism (EF, SF) ≅ (E, SF T). Members of S_{n} are called basic polynomials in n variables of the presentation (or, by abuse of language, of the theory presented) and members of E_{n} are called basic identities (or axioms) in n variables of the presentation. Members of (SF T)_{n} are called polynomials in n variables of the presentation, and members of EF T are called identities or theorems of the presentation. Clearly every axiom determines a theorem by means of the canonical E ^{}EF T. The particular polynomial π_{i}^{n} in n variables will be called the ith n-ary variable. Note that we avoid the usual practice of lumping together the n-ary variables for various n. The n-ary variables and the m-ary variables are related only by specified ‘substitutions’ σ.

For any polynomial θ in n variables, we have that

θ ≡ θ{π_{0}^{n} … π_{n−1}^{n}}

is a theorem. More generally if φ_{i} is a polynomial in m variables for each i ∈ n, then the polynomial

θ{φ_{0} … φ_{n−1}}

in m variables is called the result of substituting φ_{i} for the i-th variable in θ. (This order of writing for polynomial composition is the one consistent with writing xf for the value at x of a homomorphism f (see Chapter V).) Note that for a given presentations ⟨S, E, f⟩, the polynomials in n variables of the presentation are mapped canonically onto the set of n-ary operations of the presented algebraic theory 𝔸 by (ηT)_{n} where EF [figure] SF ^{η}^{}𝔸 is the coequalizer diagram defining 𝔸.

Example. The theory of associative rings with unity is presented as follows (writing + and · between the arguments, as usual, rather than writing the operation symbol in front or back).

n  S  E
0 ⊙, 1 empty
1  –  π_{0}^{1} + (−π_{0}^{1}) ≡ (⊙)(0 ^{}1)
(⊙)(0 ^{}1) + π_{0}^{1} ≡ π_{0}^{1}, π_{0}^{1} + (⊙)(0 ^{}1) ≡ π_{0}^{1}
π_{0}^{1} · (1)(0 ^{}1) ≡ π_{0}^{1}, (1)(0 ^{}1) · π_{0}^{1} ≡ π_{0}^{1}
2 +, · empty
3 empty π_{0}^{3} · (π_{1}^{3} · π_{2}^{3}) ≡ (π_{0}^{3} · π_{1}^{3}) · π_{2}^{3}
4 empty (π_{0}^{4} + π_{1}^{4}) + (π_{2}^{4} + π_{3}^{4}) ≡ (π_{0}^{4} + π_{2}^{4}) + (π_{1}^{4} + π_{3}^{4})
(π_{0}^{4} + π_{1}^{4}) · (π_{2}^{4} + π_{3}^{4}) ≡ ((π_{0}^{4} · π_{2}^{4}) + (π_{1}^{4} · π_{2}^{4})) + ((π_{0}^{4} · π_{3}^{4}) + (π_{1}^{4} · π_{3}^{4}))

S_{n} = E_{n} = 0 for n ≥ 5.

Proposition. Let ⟨S, E, f⟩, ⟨S′, E′, f′⟩ be presentations of algebraic theories. Let S ^{h}^{}S′F T be a map in S_{1}^{N} (i.e a sequence of functions) such that there exists a map E ^{g}^{}E′F T for which

[figure: E; g; E′F T; E′]
[figure: f′]
[figure: (SF × SF)T; f; (\overline{h} × \overline{h})T; (S′F × S′F)T]

where \overline{h} corresponds to h via (S, S′F T) = (SF, S′F); then there is a unique map \overline{\overline{h}} of the theory 𝔸 presented by ⟨S, E, f⟩ into the theory 𝔸′ presented by ⟨S′, E′, f′⟩ for which

[figure: SF; \overline{h}; S′F; 𝔸; \overline{\overline{h}}; 𝔸′]

Proof. From the assumption one gets in T by adjointness:

EF  ^{\overline{g}  ^{}}E′F

[figure: SF; \overline{h}; S′F]

[figure: 𝔸; \overline{\overline{h}}; 𝔸′]

Because of the existence of \overline{g}, SF ^{}S′F ^{}𝔸′ coequalizes EF [figure] SF. Hence the unique \overline{\overline{h}} as required exists.

In the terminology we have introduced, the proposition states that a theory map 𝔸 ^{}𝔸′ may be defined by assigning, for each n, a polynomial in n variables of ⟨S′, E′, f′⟩ to every basic polynomial in n variables of ⟨S, E, f⟩, in such a way that axioms of ⟨S, E, f⟩ are mapped into theorems of ⟨S′, E′, f′⟩.

Example. Let 𝔸′ be the theory of associative rings with unity and let 𝔸 be the theory of Lie rings. ‘The’ presentation of the latter differs from that of 𝔸′ in that there is no 1 ∈ S_{0}, in that [,] replaces · in S_{2}, and in that antisymmetry replaces identity in E_{1}, while the Jacobi identity replaces associativity in E_{3}. Then there is a unique map 𝔸 ^{}𝔸′ of the theory of Lie rings into the theory of associative rings with unity defined by interpreting 0, −, + as themselves and by interpreting

[π_{0}^{2}, π_{1}^{2}] ^{}(π_{0}^{2} · π_{1}^{2}) + (−(π_{1}^{2} · π_{0}^{2})).

That the Jacobi identity (and also antisymmetry) are mapped into theorems is shown by the usual calculations.

Chapter III

Algebraic categories

1. Semantics as a coadjoint functor

Definition. Let 𝔸 be an algebraic theory. We say that X is a pre-algebra of type 𝔸 iff X is a functor 𝔸^{∗} ^{}S_{1}, 𝔸^{∗} being the dual of the small category 𝔸. X is called an algebra of type 𝔸 iff X is a pre-algebra of type 𝔸 and X commutes with finite products. Denote by S_{1}^{(𝔸^{∗})} the full subcategory of S_{1}^{𝔸^{∗}} determined by the objects which are algebras. Say that X is an algebraic category iff for some algebraic theory 𝔸, X is equivalent to S_{1}^{(𝔸^{∗})}.

Thus a pre-algebra X of type 𝔸 is a sequence of sets together with, for every _{n}A ^{θ}^{}_{m}A in 𝔸, a map X_{m} ^{θ_{X}}^{}X_{n} in S_{1}, such that (θφ)_{X} = φ_{X}θ_{X}. X is an algebra iff X_{n} ≅ X_{1}^{n} for all finite sets n. Thus in an algebra X of type 𝔸, every n-ary operation θ of 𝔸 determines a map X_{1}^{n} ^{θ_{X}}^{}X_{1} in S_{1}.

The maps in the category of pre-algebras are natural transformations of functors; if f is such a map, then in particular π_{i}^{n}f_{1} = f_{n}π_{i}^{n} for i ∈ n. In an algebra the n-ary variables π_{i}^{n} are mapped into projections, so that f_{n} = f_{1}^{n}. Therefore if X, Y are algebras of type 𝔸, then every map X ^{f}^{}Y in S_{1}^{(𝔸^{∗})} is determined by a single map X_{1} ^{f_{1}}^{}Y_{1} in S_{1} such that for every n and every n-ary operation θ of 𝔸, the diagram

[figure: X_{1}^{n}; f_{1}^{n}; Y_{1}^{n}; X_{1}; θ_{X}; f_{1}; Y_{1}; θ_{Y}]

is commutative in S_{1}. Thus it is clear that if we are given a presentation of an algebraic theory 𝔸, then S_{1}^{(𝔸^{∗})} is precisely the usual category of all algebras of the type associated with the presentation (‘type’ here being used to include specification of identities as well as operations).

We will regard certain facts about algebraic categories as well known, in particular the elementary properties of limits, free algebras, and congruence relations. These needed facts, as well as certain additional statements which are obvious, are recorded in the following three propositions.

Proposition 1. If 𝔸 is any algebraic theory, then the composite functor U_{𝔸} given by

S_{1}^{(𝔸^{∗})}  ^{}S_{1}^{𝔸^{∗}}  ^{}S_{1}

where the second is evaluation at 1, is faithful, and has an adjoint, the value of this adjoint at a small set S being the free 𝔸-algebra over S. In particular, the above composite is left continuous.

The faithfulness is clear from the preceding remarks. Actually, we have shown in a corollary to Theorem I.2.5 that the functor S_{1}^{𝔸^{∗}} ^{}S_{1} has an adjoint, and we will show in Chapter IV that the inclusion S_{1}^{(𝔸^{∗})} ^{}S_{1}^{𝔸^{∗}} has an adjoint, from which it will also follow that S_{1}^{(𝔸^{∗})} is right complete. (It is obvious from the definition and Proposition I.2.3 that S_{1}^{(𝔸^{∗})} is left complete.) Explicitly, the left continuity assertion of Proposition 1.1 means that the underlying set of a product of 𝔸-algebras or of an equalizer of 𝔸-algebra maps is the product or equalizer, respectively, of the underlying sets or S_{1}-maps.

Proposition 2. For any algebraic theory 𝔸, the functor 𝔸 ^{}S_{1}^{𝔸^{∗}} defined by assigning to _{n}A the pre-algebra X such that X_{k} = (_{k}A,_{n}A), has algebras as values, is full and faithful, and commutes with finite coproducts. Identifying the X just defined with _{n}A, we thus have 𝔸 ⊂ S_{1}^{(𝔸^{∗})}, a full subcategory. For any 𝔸-algebra Y, (_{1}A, Y) = Y_{1}. It follows that _{1}A is a generator for S_{1}^{(𝔸^{∗})}, and that the free algebra over a small set S is the S-fold coproduct S ·_{1}A. Thus 𝔸 is precisely the full category of finitely generated free 𝔸-algebras.

0A = lim^{S_{1}^{(𝔸^{∗})}}_{→0}.

Proposition 3. A map of 𝔸-algebras is onto iff it is the coequalizer of the congruence relation which it induces on its domain. In other words, X ^{f}^{}Y is a regular epimap in S_{1}^{(𝔸^{∗})} iff for every _{1}A ^{y}^{}Y there is _{1}A ^{x}^{}X such that xf = y.

Now if 𝔸 ^{f}^{}𝔹 is a map of algebraic theories, then viewed as a functor 𝔸^{∗} ^{f^{∗}}^{}𝔹^{∗} commutes with finite products. Thus we have a factorization

[figure: S_{1}^{(𝔹^{∗})}; S_{1}^{(f^{∗})}; S_{1}^{(𝔸^{∗})}; S_{1}^{𝔹^{∗}}; S_{1}^{f^{∗}}; S_{1}^{𝔸^{∗}}]

That is, S_{1}^{f^{∗}} takes algebras into algebras. S_{1}^{(f^{∗})} defined by the above diagram will be called an algebraic functor (of degree 1; algebraic functors of higher degree are defined and discussed in Chapter IV).

We now point out two facts about algebraic categories and algebraic functors.

Proposition 4. Every algebraic functor of degree 1 commutes with the underlying set functors. That is, if 𝔸 ^{f}^{}𝔹 in T , then

S_{1}^{(𝔹^{∗})}  S_{1}^{(f^{∗})}  ^{}S_{1}^{(𝔸^{∗})}
[figure: U_{𝔹}; U_{𝔸}]
S_{1}

is commutative.

Proof. For X ∈ S_{1}^{(𝔹^{∗})}, XS_{1}^{(f^{∗})}U_{𝔸} = fXU_{𝔸} = (fX)_{1} = X_{(1)f} = X_{1} = XU_{𝔹}.

In particular, each S_{1}^{(f^{∗})} is faithful and left continuous.

Theorem 1. For any algebraic theory 𝔸, the underlying set functor U_{𝔸} has the property

that ({U_{𝔸}}^{n}, {U_{𝔸}}^{m}), the indicated set of natural transformations in S_{1}^{S_{1}^{(𝔸^{∗})}}, is small for any finite sets n, m. In fact

({U_{𝔸}}^{n}, {U_{𝔸}}^{m}) ≅ (_{m}A,_{n}A)

where _{m}A, _{n}A are viewed as objects in 𝔸 (or in S_{1}^{(𝔸^{∗})}).

Proof. The proof of Theorem I.2.5 clearly works equally well if we consider ‘large’ rather then small categories and properties throughout; in particular the category must have a large coproducts. Thus by a corollary to that theorem we can state the following (which one could actually prove directly without appeal to limits):

Let B be any large category and let B ^{T}^{}S_{2} be any functor. If for any B ∈ |B|, H^{B} denotes the functor B ^{}S_{2} whose value at X is (B, X) then

(H^{B}, T) ≅ BT.

We prove Theorem 1.1 by applying this statement with B = S_{1}^{S_{1}^{(𝔸^{∗})}}. Since {U_{𝔸}} = H^{_{1}A}, (H^{B})^{n} = H^{n·B}, and n · _{1}A = _{n}A, we have for any S_{1}^{(𝔸^{∗})} ^{T} ^{}S_{1} that ({U_{𝔸}}^{n}, T) ≅ (H^{_{n}A}, T) ≅ _{n}AT. In the case T = {U_{𝔸}}^{m} = H^{_{m}A}, we therefore have ({U_{𝔸}}^{n}, {U_{𝔸}}^{m}) ≅ (_{m}A,_{n}A).

Definition. Let K be the full subcategory of (C_{2}, {S_{1}}) determined by those objects X ^{U}^{}S_{1} for which ({U}^{n}, U) is small for every finite set n. The functor T^{∗} ^{𝔖}^{}K defined by

\begin{aligned}(𝔸)𝔖 & = & U_{𝔸} \\ (f)𝔖 & = & S_{1}^{(f^{∗})} \end{aligned}

will be called (algebraic) semantics. Here, for 𝔸 ^{f}^{}𝔹 in T , (f)𝔖 = S_{1}^{(f^{∗})} is regarded as a map U_{𝔹} ^{}U_{𝔸} in K, where of course U_{𝔹} and U_{𝔸} are the underlying set functors,

S_{1}^{(𝔹^{∗})}  ^{}S_{1} and S_{1}^{(𝔸^{∗})}  ^{}S_{1}, respectively.

Thus intuitively the semantics functor assigns to each algebraic theory the category of algebras of which it is a theory. However, we find it necessary to include the underlying set functor U_{𝔸} as part of the value at 𝔸 of 𝔖, because the left continuity of semantics, which follows from Theorem 1.2 below, would be destroyed if we defined 𝔸𝔖 to be S_{1}^{(𝔸^{∗})} in C_{2} rather than U_{𝔸} in K.

Note that in (C_{2}, {S_{1}}), and hence in K, direct limits agree with those in C_{2}, but binary products, for example, are defined by meet diagrams of the form

X ×_{S_{1}} X  \overline{}X′
C_{2}
[figure: X; U; S_{1}; U′]

Definition. We define a functor K ^{𝔖̂}^{}T^{∗}, as follows. Given an object X ^{U}^{}S_{1} in K, we consider the object {U} ∈ |S_{1}^{X} |. There is a unique functor S_{0}^{∗} ^{}S_{1}^{X} which commutes with finite products and which maps 1 into {U}. Let U𝔖̂ be the algebraic theory S_{0} ^{}𝔸, where 𝔸 is the dual of the full image of S_{0}^{∗} ^{}S_{1}^{X} . We call U𝔖̂ the algebraic structure

of U. If U ^{T}^{}U′ in K, then U′𝔖̂ ^{T 𝔖̂}^{}U𝔖̂ in T is defined by dualizing the small triangle in

S_{0}^{∗}
[figure]
A^{′∗}  \overline{(T 𝔖̂)^{∗}  ^{}}𝔸^{∗}
[figure]
S_{1}^{X′}  \overline{S_{1}^{T}  ^{}}S_{1}^{X}

the big triangle being commutative since T (U^{′n}) = (T U′)^{n} = U^{n} for n ∈ S_{0}.

Explicitly, the n-ary operations of the algebraic structure of X ^{U}^{}S_{1} are in one-to-one correspondence with the natural transformations {U}^{n} ^{}{U} in S_{1}^{X} . Theorem 1.1 states that 𝔖𝔖̂ ≅ {T^{∗}}, i.e. T^{∗} is a retract of K (up to equivalence).

Theorem 2. Algebraic structure is adjoint to (algebraic) semantics.

Proof. We use again Theorem I.2.1, i.e. given X ^{U}^{}S_{1} in K, we define a ‘universal’ Φ such that

X  \overline{Φ  ^{}}S_{1}^{(U𝔖̂∗)}
[figure: U; U𝔖̂𝔖]
S_{1}

Since in the construction of 𝔸 = U𝔖̂, 𝔸^{∗} is the full image of the functor S_{0}^{∗} ^{}S_{1}^{X} defined by taking n-fold products of U with itself for each n ∈ S_{0}, there is a functor

𝔸^{∗} ^{}S_{1}^{X}

depending on U such that the corresponding

X ^{}S_{1}^{𝔸^{∗}}

has algebras as values. Define Φ as the resulting

X ^{Φ}^{}S_{1}^{(𝔸^{∗})} ^{}S_{1}^{𝔸^{∗}}.

Thus for each X ∈ |X |, (XΦ)_{n} = (XU)^{n} , and for each natural transformation

{U}^{n} ^{θ}^{}{U}

i.e. for each n-ary operation of 𝔸 = U𝔖̂, the corresponding (XΦ)_{1}^{n} ^{}(XΦ)_{1} is just θ_{X}. Thus each map X ^{x}^{}X′ in X determines a map XΦ ^{xΦ}^{}X′Φ of the corresponding U𝔖̂-algebras. By construction Φ(U𝔖̂𝔖) = U. We need to show that Φ has the universal mapping property of Theorem I.2.1.

Consider any algebraic theory 𝔸′ and any functor X ^{T}^{}S_{1}^{(𝔸^{′∗})} for which T U_{𝔸′} = U, i.e. U ^{T}^{}𝔸′𝔖 in K. We must show that there is a unique 𝔸′ ^{f}^{}𝔸 = U𝔖̂ in T such that ΦS_{1}^{(f^{∗})} = T, i.e. such that Φ(f𝔖′) = T. Now by Theorem 1.1, U𝔖̂𝔖𝔖̂ ^{Φ𝔖̂}^{}U𝔖̂ is an isomorphism in T . Thus if T = Φ(f𝔖), then T 𝔖̂ = (Φ(f𝔖))𝔖̂ = (f𝔖𝔖̂)Φ𝔖̂, so that

f𝔖𝔖̂ = (T 𝔖̂)(Φ𝔖̂)^{−1}.

But by Theorem 1.1, the functor T^{∗} ^{𝔖𝔖̂}^{}T^{∗} is equivalent to the identity, in particular full and faithful, so that the equation above, and hence the equation T = Φ(f𝔖), has exactly one solution f.

According to Theorems 1.1 and 1.2 , given any large category X and any ‘underlying set’ functor X ^{U}^{}S_{1} such that (U^{n}, U) is small for all n, there is a well-defined ‘algebraic closure’ of ⟨X , U⟩, i.e. an algebraic category S_{1}^{(U𝔖̂^{∗})} and functor X ^{Φ}^{}S_{1}^{(U𝔖̂^{∗})}, preserving underlying sets, which is universal with respect to underlying set-preserving functors of X into any algebraic category. Further, this universality is accomplished by algebraic functors in the factorization, and an algebraic category is algebraically closed. In fact, X is algebraic iff: Φ : X ≅ S_{1}^{(U𝔖̂^{∗})}. We will presently discuss some ways of constructing reasonable underlying set functors U given only the category X . Note however that Theorems 1.1 and 1.2 place no conditions of faithfulness, left continuity, etc. on the functor U considered; the only condition is that (U^{n}, U) be small.

Example 1. Let X be any large category such that 1 [figure: X; Y] X ⇒ (X, Y) small, and such

that X^{∗} × X ^{(,)}^{}S_{1} defines an object in K. Consider the algebraic structure of (,) and let \overline{X} be the resulting algebraic category. There results

X^{∗} × X  \overline{^{Hom_{X}}  ^{}}\overline{X}
[figure: (,)]
S_{1}

We call Hom_{X} the algebraic Hom-functor of the category X . If, e.g., X is the category of modules over a ring, then \overline{X} is the category of modules over the center of the ring.

Example 2. Let D be the category of division rings. D is not algebraic (e.g. it does not have products); however there is an inclusion D ^{}R where R is the category of associative rings with unity and an obvious underlying set functor U. We thus have

S_{1}^{(U𝔖̂^{∗})}

[figure]

[figure: D; R]
[figure: U]
S_{1}^{}

and a map 𝔸 ^{}U𝔖̂ in T , where R = 𝔸𝔖. However, this map is not an isomorphism; in fact there is an additional unary operation θ in U𝔖̂, which satisfies the identities

\begin{aligned}π_{0}^{1} · θ(π_{0}^{1}) · π_{0}^{1} & ≡ & π_{0}^{1} \\ θ(π_{0}^{2} · π_{1}^{2}) & ≡ & θ(π_{1}^{2}) · θ(π_{0}^{2}) \\ θ(1) & ≡ & 1. \end{aligned}

The maps in the associated category are ring homomorphisms which commute with θ, and the category does of course have products.

Example 3. Let G denote the category of groups, R, 𝔸 as above. Define U′ as R_{c} × G ^{}R ^{}S_{1}, where the first assigns to ⟨R, G⟩ the group algebra of G with coefficients in the commutative ring R. The codomain of 𝔸 ^{}U′𝔖̂ has two additional unary operations, φ, τ, which in this case satisfy the identities:

\begin{aligned}φφ & ≡ & π_{0}^{1} \\ φ(π_{0}^{2} + π_{1}^{2}) & ≡ & φ(π_{0}^{2}) + φ(π_{1}^{2}) \\ φ(π_{0}^{2} · π_{1}^{2}) & ≡ & φ(π_{1}^{2}) · φ(π_{0}^{2}) \\ φ(1) & ≡ & 1 \\ τ(1) & ≡ & 1 \\ τ(π_{0}^{2} + π_{1}^{2}) & ≡ & τ(π_{0}^{2}) + τ(π_{1}^{2}) \\ τ(π_{0}^{2} · π_{1}^{2}) & ≡ & τ(π_{1}^{2} · π_{0}^{2}) \\ φτ & ≡ & τ \\ τφ & ≡ & τ \\ ττ & ≡ & τ \end{aligned}

If, in this example, we replace G by the category of group monomorphisms, then evaluation at the neutral element is also part of the resulting algebraic structure.

Example 4. Let S_{1}^{∗} be the dual of the category of small sets and define S_{1}^{∗} ^{P} ^{}S_{1} by SP = (S, 2) for S ∈ S_{1} (2 = |2|). Then P 𝔖̂ is the theory of Boolean algebras, for by the corollary to Theorem I.2.5, we have (P^{n}, P) = ((H^{2})^{n}, H^{2}) = (H^{2^{n}}, H^{2}) = (2^{n}, 2), (note the two dualizations) and known facts about truth tables complete the proof. The resulting S_{1}^{∗} ^{}S_{1}^{(P 𝔖̂^{∗})} takes each small set into its Boolean algebra of subsets.

Example 5. Let X be the category of compact topological spaces and I the unit interval. Consider X^{∗} ^{(·,I)}^{}S_{1}. There results an embedding of X^{∗} in an algebraic category in which the n-ary operations are arbitrary continuous I^{n} ^{θ}^{}I.

2. Characterization of algebraic categories

Definition. Let X be any large category having finite limits and let G ∈ |X | be such that for any small set S, S · G, the S-fold coproduct of G with itself, exists in X . Then G is a generator for X iff

∀X ∀Y ∀f ∀g [X [figure: f; g] Y ⇒ [f = g ⇔ ∀x [G ^{x}^{}X ⇒ xf = xg]]].

G is projective iff

\begin{matrix}∀X ∀Y ∀f [X ^{f}^{}Y ⇒ [∃h ∃g [f = hE^{∗}g] \\ ⇔ ∀y [G ^{y}^{}Y ⇒ ∃x [G ^{x}^{}X ∧ xf = y]]]]. \end{matrix}

G is abstractly finite iff

∀S ∀f [S is small set ∧ G ^{f}^{}S · G ⇒ ∃F ∃g ∃h [F is a finite set ∧ F ^{g}^{}S∧

G  \overline{f  ^{}}S · G
[figure: h; g · G; ]].]
F · G

The term ‘abstractly finite’ is due to [Freyd, 1960]. Note that our concept of ‘projective’ coincides with the usual one for abelian categories, but differs for some other categories. The definition of G being projective may be rephrased: ‘For every f, f is ‘onto’ (with respect to G) iff f is a regular epimap.’ If 𝔸 is any algebraic theory, then _{1}A is an abstractly finite projective generator for S_{1}^{(𝔸^{∗})}. The abstract finiteness is due to the nature of coproducts in an algebraic category: the value at π_{0}^{1} of a map _{1}A ^{}S ·_{1}A is some n-ary operation θ applied to the various copies of π_{0}^{1}; but this, and hence the whole image of the map, involves at most n of the S-copies of _{1}A.

Definition. Let X be a category and G ∈ |X |. Consider a pair

X [figure: f_{0}; f_{1}] Y

of maps in X . We say that ⟨f_{0}, f_{1}⟩ is RST with respect to G iff the following three conditions hold (in X):

R: ∀y [G ^{y}^{}Y ⇒ ∃x [G ^{x}^{}X ∧ xf_{0} = y ∧ xf_{1} = y]]

S: ∀x [G ^{x}^{}X ⇒ ∃x′ [G ^{x′}^{}X x′f_{0} = xf_{1} ∧ x′f_{1} = xf_{0}]] T: ∀u ∀v [G ^{u}^{}X ∧ G ^{v}^{}X ∧ uf_{1} = vf_{0} ⇒ ∃w [G ^{w}^{}X ∧ wf_{0} = uf_{0} ∧ wf_{1} = vf_{1}]].

We say that ⟨f_{0}, f_{1}⟩ is monomorphic with respect to G iff

∀x ∀x′ [G ^{x}^{}X ∧ G ^{x′}^{}X ∧ xf_{0} = x′f_{0} ∧ xf_{1} = x′f_{1} ⇒ x = x′].

We say that ⟨f_{0}, f_{1}⟩ is a congruence relation with respect to G iff

∀y ∀y′ [G ^{y}^{}Y ∧ G ^{y′}^{}Y ∧ [∀Z∀z[Y ^{z}^{}Z ∧ f_{0}z = f_{1}z ⇒ yz = y′z]]

⇒ ∃!x [G ^{x}^{}X ∧ xf_{0} = y ∧ xf_{1} = y′]].

It is well known that (in our language) if 𝔸 is an algebraic theory, X = S_{1}^{(𝔸^{∗})}, G = _{1}A, then a pair ⟨f_{0}, f_{1}⟩ in X is a congruence relation with respect to _{1}A iff it is monomorphic and RST with respect to _{1}A. In an algebraic category, a pair ⟨f_{0}, f_{1}⟩ is a congruence rela-

tion with respect to _{1}A iff the map X ^{⟨f_{0},f_{1}⟩}^{}Y ×Y is the equalizer of Y ×Y [figure: p_{1}; p_{2}] Y ^{q}^{}Q

where q is the coequalizer of the pair ⟨f_{0}, f_{1}⟩.

Theorem 1. Let X be any large category with finite limits. Then X is algebraic iff there exists G ∈ |X | such that

(1) arbitrary small coproducts of G with itself exist in X;

(2) for every X ∈ |X |, (G, X) is small;

(3) G is an abstractly finite projective generator for X;

(4) for any small set I and any object X, any pair ⟨f_{0}, f_{1}⟩ of maps

X [figure: f_{0}; f_{1}] I · G which is monomorphic and RST with respect to G is also a congruence

relation with respect to G.

Proof. Necessity is clear. Suppose there is an object G satisfying the four conditions, let U = (G, ·) and consider the functor X ^{Φ}^{}S_{1}^{(U𝔖̂^{∗})}. We must show that Φ is full, dense, and faithful. Since G is a generator, faithfulness is clear.

We now show that Φ is full. Note that for any X ∈ |X |, (G, X) is the underlying set of XΦ, and that a map XΦ ^{}Y Φ in S_{1}^{(U𝔖̂^{∗})} may be identified as a map (G, X) ^{f}^{}(G, Y) in S_{1} which commutes with every n-ary operation G ^{θ}^{}n · G from X . Suppose given such an f. We need to show that f = (G, φ) for some X ^{φ}^{}Y in X . Now there is in X

R [figure: α; β] I · G ^{p}^{}X

such that p = αE^{∗}β. (For example, we may take I = (G, X) and note that the obvious p is regular since it is onto with respect to G.) Let, for each i ∈ I, e_{i} denote the i-th injection G ^{}I · G. We first define G ^{φ_{i}}^{}Y, i ∈ I by

φ_{i} = (e_{i}p)f.

Now since I ·G is a coproduct, there is a unique I ·G ^{\overline{φ}}^{}Y such that e_{i}\overline{φ} = φ_{i} for i ∈ I. We need to show that \overline{φ} coequalizes α, β. Consider any G ^{r}^{}R. Since G is abstractly finite, there is a finite set n, a map n ^{k}^{}I, and maps α′, β′ such that rα′(k · G) = rα and rβ′(k · G) = rβ.

[figure: G; r; R; α′; β′; n · G; k · G; I · G; p; X]
[figure: ((k · G)p)f^{n}]
Y\overline{φ}_{}

We show that the triangle is commutative. For each G ^{π_{1}^{n}}^{}n · G, i ∈ n, we have

π_{i}^{n}(k · G)\overline{φ} = e_{(i)k}\overline{φ} = φ_{(i)k} = (e_{(i)k}p)f = (π_{i}^{n}(k · G)p)f = π_{i}^{n}((k · G)p)f^{n},

the last since f commutes with the n-ary operation π_{i}^{n}. Thus (k · G)\overline{φ} = ((k · G)p)f^{n}. Then

rα\overline{φ} = rα′(k · G)\overline{φ} = rα′((k · G)p)f^{n} = (rα′(k · G)p)f
= (rαp)f = (rβp)f = (rβ′(k · G)p)f
= rβ′((k · G)p)f^{n} = rβ′(k · G)\overline{φ} = rβ\overline{φ}

since αp = βp and f commutes with the n-ary operations rα′ and rβ′. Since the foregoing holds for every G ^{r} ^{}R we have that α\overline{φ} = β\overline{φ}, and hence ∃!X ^{φ}^{}Y such that pφ = \overline{φ.} It remains to show that (G, φ) = f. But since p is onto with respect to G, for every G ^{x}^{}X there is G ^{\overline{x}}^{}I · G such that \overline{x}p = x.

n · G ^{_{}θ}  G
[figure: h · G; \overline{x}; x]
I · G  \overline{p  ^{}}X
[figure: φ]
Y \overline{φ}_{}

By abstract finiteness there is a finite set n, an n-ary operation θ, and n ^{h}^{}I such that θ(h · G) = \overline{x}. Then xφ = θ(h · G)pφ = θ(h · G)\overline{φ}. On the other hand (x)f = (θ(h · G)p)f = θ((h · G)p)f^{n} since f commutes with n-ary operation θ. Thus to show xφ = (x)f reduces to showing (h · G)pφ = ((h · G)p)f^{n}. For each i ∈ n, π_{i}^{n}(h · G)pφ = e_{(i)h}\overline{φ} = (e_{(i)h}p)f = (π_{i}^{n}(h · G)p)f = π_{i}^{n}((h · G)p)f^{n}. Hence xφ = (x)f. But this is true for all G ^{x}^{}X, i.e. f = (G, φ). Thus Φ is full.

We now must show that Φ is dense. Denoting _{1}A = (G)Φ, we first show that

(I · G)Φ ≅ I ·_{1}A

in S_{1}^{(U𝔖̂^{∗})} for any small set I.

Since there is in any case a U𝔖̂-map I ·_{1}A ^{λ}^{}( I · G) Φ it suffices to show that λ is one-to-one and onto by Proposition I.3.2; that is, we show that λ induces

(_{1}A, I ·_{1}A) ≅ (G, I · G) = (_{1}A, (I · G)Φ).

Now if I = n, a finite set, this relation is true since both sides are just the set of n-ary operations of the theory U𝔖̂. This fact and abstract finiteness enable us to construct an inverse μ to (_{1}A, λ). For each finite n and n ^{}I we have

(_{1}A, n ·_{1}A) [figure: λ_{n}; \underline{μ_{n}}] (G, n · G)
μ_{n} = λ_{n}^{−1}
[figure: (_{1}A, I ·_{1}A); (_{1}A, λ); (G, I · G)]

Since (G, I · G) = lim_{→}(G, n · G), the maps (G, n · G) ^{}(_{1}A, I ·_{1}A) yield a unique μ, inverse to (_{1}A, λ).

Now assume that Y is an arbitrary U𝔖̂-algebra. Then there is a small set I and a regular epimap I ·_{1}A ^{p}^{}Y. The remaining maps in the following diagrams are constructed as described below.

[figure: X :; S · G; a; b; I · G; q; \overline{Y}]
.................................. \overline{r}  _{}
K_{q} [figure: \overline{α}; \overline{β}]
[figure: S_{1}^{(U𝔖̂^{∗})} :; S ·_{1}A; r; R; α; β; I ·_{1}A; p; Y.]

First, ⟨α, β⟩ is the kernel of p, i.e. α = kp_{1}, β = kp_{2} where k = (p_{1}p)E(p_{2}p), where (I ·_{1}A) × (I ·_{1}A) ^{p_{j}}^{}I ·_{1}A are the two projections. Second, there is a regular epimap r from some chosen S · _{1}A to R. Because Φ preserves coproducts of G with itself, and because Φ is full, there are a, b in X such that aΦ = rα, bΦ = rβ. Define q = aE^{∗}b in X . We wish to show that \overline{Y} Φ ≅ Y where \overline{Y} is the codomain of q. Let ⟨\overline{α}, \overline{β}⟩ be the kernel of q. Because ⟨a, b⟩q_{1}q = ⟨a, b⟩q_{2}q, where (I · G) × (I · G) ^{q_{j}}^{}I · G are the projections, there is a unique S · G ^{\overline{r}}^{}K_{q} in X for which r̄ᾱ = a, \overline{r}\overline{β} = b. Since aq = bq in X, we have rα(qΦ) = (aΦ)(qΦ) = (aq)Φ = (bq)Φ = (bΦ)(qΦ) = rβ(qΦ). Since r is an epimap, α(qΦ) = β(qΦ), and there is a unique Y ^{φ}^{}\overline{Y} Φ such that pφ = qΦ. Because Φ is left exact, ⟨\overline{α}Φ, \overline{β}Φ⟩ is the kernel of qΦ in S_{1}^{(U𝔖̂^{∗})}. Hence there is a unique R ^{ψ}^{}K_{q}Φ such that α = ψ(\overline{α}Φ) and β = ψ(\overline{β}Φ). Then, because ⟨\overline{α}, \overline{β}⟩Φ is a monomorphism, \overline{r}Φ = rψ, and moreover ψ is a regular monomap since ⟨α, β⟩ is. Since r is a regular epimap, there are S′ ·_{1}A [figure] S ·_{1}A with coequalizer r. Let S · G ^{\overline{\overline{r}}}^{}Q be the coequalizer in X of the corresponding S′ · G [figure] S · G. The map \overline{r} also coequalizes the last pair since ⟨\overline{α}, \overline{β}⟩ is a monomorphism. Thus there is a unique η ∈ X such that

S · G  \overline{⟨a, b⟩  ^{}}(I · G)^{2}
[figure: \overline{r}; ⟨\overline{α}, \overline{β}⟩]
[figure: Q; \overline{\overline{r}}; η; K_{q}]

is commutative. Since \overline{\overline{r}}Φ coequalizes S′ · _{1}A [figure] S · _{1}A, there is a unique ξ ∈ S_{1}^{(U𝔖̂^{∗})} such that rξ = \overline{\overline{r}}Φ. Then also ξ(ηΦ) = ψ since r is an epimorphism.

[figure: S ·_{1}A; r; R; ⟨α, β⟩; (I ·_{1}A)^{2}]
[figure: \overline{r}Φ; \overline{\overline{r}}Φ; ξ; ψ; ⟨\overline{α}, \overline{β}⟩Φ]
QΦ

K_{q}Φ ηΦ_{}

Thus ξ is a monomorphism since ψ is. Now \overline{\overline{r}}Φ is a regular epimap because \overline{\overline{r}} is and because Φ takes G-onto maps into _{1}A-onto maps, and by assumption this is equivalent to taking regular epimaps into regular epimaps. Since r is an epimorphism, ξ is therefore a regular epimap and hence an isomorphism (by Proposition I.3.3 and I.3.1), and without loss we may assume QΦ = ξ = R, so that in particular ψ = ηΦ. Because Φ is faithful and ψ is a monomorphism, it follows that η is a monomorphism in X . Now q is also the coequalizer of ⟨η\overline{α}, η\overline{β}⟩. Thus by assumption (4), in order to show that Q ≅ K_{q}, it will be enough to show that ⟨η\overline{α}, η\overline{β}⟩ is RST with respect to G. But this is clear since ⟨α, β⟩ is RST with respect to _{1}A and α = (η\overline{α})Φ, β = (η\overline{β})Φ, while Φ is full and faithful. Therefore η : Q ^{≈}^{}K, so that ψ = ηΦ establishes an isomorphism R ^{≈}^{}K_{q}Φ in S_{1}^{(U𝔖̂^{∗})}, and hence Y = I ·_{1}A/R ≅ I ·_{1}A/K_{q}Φ = \overline{Y} Φ, the last since qΦ is a regular epimap with kernel K_{q}Φ. Thus Φ is dense.

Remark. It will be noted that even in the absence of assumption (4), the correspondence Y ^{}\overline{Y} constructed in the foregoing proof provides an adjoint to Φ. Assumption (4) is needed, for the full category X of torsion-free abelian groups is complete and has an abstractly finite projective generator Z, yet it is not algebraic since the algebraic structure of (Z, ) is the theory of abelian groups, and hence the functor Φ has the category A_{1} of all abelian groups for its codomain. The adjoint in this case consists of dividing by the torsion part.

Sums (coproducts), as well as products and equalizers, in X coincide with those in A_{1}. However, the coequalizer of a pair f_{0}, f_{1} is obtained in X by first taking the coequalizer in A_{1} and then dividing by the torsion part:

X [figure: f_{0}; f_{1}] Y ^{q}^{}K^{∗} ^{η_{K^{∗}}}^{}K^{∗}/K^{∗}T
q = f_{0}E_{A_{1}}^{∗}f_{1} , qη_{K^{∗}} = f_{0}E_{X}^{∗} f_{1}.

This makes it clear that regular epimaps are precisely onto maps, so that Z is projective in X . An explicit counter-example to assumption (4) is obtained by choosing p > 1 and considering

Z × Z [figure: f_{0}; f_{1}] Z

where ⟨x, y⟩f_{0} = x, ⟨x, y⟩f_{1} = x+py. Since the A_{1}-coequalizer is the torsion group Z_{p}, the X -coequalizer is 0, so that the kernel of the coequalizer is not ⟨f_{0}, f_{1}⟩ even though ⟨f_{0}, f_{1}⟩ is monomorphic and RST.

Corollary. An abelian algebraic category is equivalent to the category of modules over some associative ring with unity.

In fact, [Freyd, 1960] has established that any complete abelian category with an abstractly finite projective generator G is equivalent to the category of modules over the endomorphism ring of G.

Corollary. Suppose ⟨S, E, f⟩ is a presentation of an algebraic theory 𝔸, and suppose X is a large category with finite limits. Then X is equivalent to the category of all 𝔸-algebras iff there is an object G in X satisfying conditions (1)-(4) of the theorem and a sequence of maps of sets S_{n} ^{q_{n}}^{}(G, n·G) such that every map n·G ^{}m·G in X can be expressed by composition and { } in terms of S_{0} and S, and such that maps n·G [figure] m·G are equal if and only if their being so follows from E, equations holding in S_{0}, and the fact that n·G is an n-fold coproduct, Theorem 2. If X is any algebraic category and ℂ is small with |ℂ| < ∞, and if either all (C, B) ≠ 0 or X has constant operations, X^{ℂ} is also an algebraic category.

Proof. X^{ℂ} is complete, and since limits and monomorphisms are pointwise-characterized in X^{ℂ}, it follows that every RST monomorphic pair in X^{ℂ} is a congruence relation. (Note that RST, monomorphism and congruence are actually intrinsic concepts, though we defined them in term of a given projective generator.) Thus we need only show that X^{ℂ} has an abstractly finite projective generator. We do this in such a way that the underlying set of a functor A : ℂ ^{}X turns out to be the product Π_{C∈|ℂ|}CAU, where U = (G, ) is the

underlying set functor determined by some chosen abstractly finite projective generator G for X . Consider the composite functor P

X^{ℂ} ^{}X^{|ℂ|} ^{Π}^{}X .

By Theorem I.2.5, the first functor has an adjoint, and of course Π has the adjoint X ^{}X^{|ℂ|} induced by |ℂ| ^{}1. Thus P has an adjoint, so that in particular there is an object \overline{G} ∈ |X^{ℂ}| such that

(\overline{G}, A) ≅ (G, AP)

for every object A ∈ |X^{ℂ}|. Since P is clearly faithful, \overline{G} is a generator.

Since limits are calculated pointwise in X^{ℂ}, a map φ ∈ X^{ℂ} is a regular epimap iff each φ_{C}, C ∈ |ℂ| is a regular epimap in X . Thus to show that \overline{G} is a projective we need to show that φ is \overline{G}-onto iff each φ_{C} is G-onto. If A ^{φ}^{}B in X^{ℂ}, we have in S_{1}

(\overline{G}, A)  \overline{(\overline{G}, φ)  ^{}}(\overline{G}, B)
∥  ∥
(G, AP)  \overline{(G, φP) ^{}}(G, BP)
∥  ∥
Π_{C∈|ℂ|}(G, CA) \overline{Π_{C∈|ℂ|}(G, φ_{C})_{}}Π_{C∈|ℂ|}(G, CB)

But in S_{1}, Π_{C∈|ℂ|}(G, φ_{C}) is onto iff each (G, φ_{C}) is onto. Thus the X^{ℂ}-regular epimaps are

precisely the \overline{G}-onto maps, i.e. \overline{G} is projective.

We now show that \overline{G} is abstractly finite if and only if |ℂ| is finite. For this we need to recall from Theorem I.2.5 the formula for \overline{G}:

(C)\overline{G} = lim^{X}_{→(i,C)}(d_{0}^{C}, G̃)

where |ℂ| ^{i}^{}ℂ is the inclusion and where G̃ is the functor |ℂ| ^{}X constantly equal to G. Since (i, C) in this case is a set (namely the set of all maps in ℂ with codomain C) and since the functor d_{0}^{C} G̃ is constant, we have

(C)\overline{G} = (i, C) · G

the (i, C)-fold coproduct of G with itself in X . Now consider any small set I and any map \overline{G} ^{f}^{}I · \overline{G} in X^{ℂ}. We have

(\overline{G}, I · \overline{G}) ≅ (G, (I · \overline{G})P) ≅ Π_{C∈|ℂ|}(G, (I × (i, C)) · G).

Now since G is abstractly finite, each of the maps \overline{f}_{C} : G ^{}(I×(i, C))·G corresponding to f factors through a sub-coproduct corresponding to a finite I_{C} ⊂ I × (i, C). If \overline{G} is to be abstractly finite, then there must be a finite J ⊂ I such that I_{C} ⊂ J × (i, C) for all C, because the I_{C} can be arbitrary. If |ℂ| is not finite, then the family I_{C} = {⟨C, C⟩} of singletons admits no such J, showing the necessity. For the sufficiency, suppose |ℂ| is finite. Then

J = {j| ∃C ∈ |ℂ| ∃u ∈ (i, C) [⟨j, u⟩ ∈ I_{C}]}

is a finite subset of I such that f factors

\overline{G}  \overline{f  ^{}}I · \overline{G}
[figure]
J · \overline{G}

Remark. It will be noted that if ℂ is a monoid, i.e. |ℂ| = 1, then the underlying set functor constructed for X^{ℂ} in the above proof matches that of X, i.e.

X^{ℂ}  \overline{}X^{|ℂ|} = X
[figure]
S_{1}

is commutative, so that the connecting functor is algebraic of degree one. In Chapter V, we study this case in more detail and in particular determine the algebraic structure of X^{ℂ} ^{P}^{}X ^{}S_{1} in terms of ℂ and the algebraic structure of X ^{}S_{1}.

In case X is the category of modules over a ring R, ℂ arbitrary, I have constructed elsewhere [Lawvere, 1963] a ring R[ℂ] such that, in case |ℂ| is finite, the algebraic structure of X^{ℂ} ^{}S_{1} turns out to be the theory of modules over R[ℂ]. Of course R[ℂ] reduces to the usual monoid ring in case |ℂ| = 1.

Remark. The generator G of Theorem 2.1 is not uniquely determined by X, i.e. X may be represented as S_{1}^{(𝔸^{∗})} for many different non-isomorphic theories 𝔸. For example, if ℂ of Theorem 2.2 is an equivalence relation, i.e. for any two C,C′ ∈ |ℂ| there is exactly one ℂ ^{}C′ in ℂ, then ℂ ^{}1 is an equivalence, so that

X^{ℂ} ^{}X

is also an equivalence. However if |ℂ| > 1, then the theory constructed for X^{ℂ} is different from the given one for X . In particular, if X is the category of R-modules and |ℂ| = n, then R[ℂ] is the ring of n×n matrices over R. Of course, an equivalence which commutes with underlying set functors does induce an isomorphism of theories.

Chapter IV

Algebraic functors

1. The algebra engendered by a prealgebra

Let 𝔸 be an algebraic theory. Recall that a prealgebra X of type 𝔸 is any functor 𝔸^{∗} ^{X}^{}S_{1}, and that an algebra of type 𝔸 is a prealgebra X of type 𝔸 such that X_{n} = X_{1}^{n} for every object n in 𝔸.

Theorem 1. If 𝔸 is any algebraic theory, then the inclusion S_{1}^{(𝔸^{∗})} ^{}S_{1}^{𝔸^{∗}} of algebras into prealgebras admits an adjoint.

Proof. Let X be any prealgebra of type 𝔸. In the free 𝔸-algebra X_{1}F generated by the set X_{1}, consider the smallest 𝔸-congruence XE containing the following relations:

If n ∈ |S_{0}|, if _{1}A ^{θ}^{}_{n}A in 𝔸, and if there is y ∈ X_{n} such that

yθ_{X} = x and yπ_{i}^{n}_{X} = x_{i} for i ∈ n

then

(x_{0}κ, …, x_{n−1}κ)θ ≡_{XE} xκ

where X_{1} ^{κ}^{}X_{1}F U_{𝔸} is the canonical inclusion. Define a prealgebra \overline{X} as follows. For each n ∈ |S_{0}|,

(\overline{X}_{n}) = (X_{1}F /XE)^{n}U_{𝔸}.

For each 1 ^{i}^{}n in S_{0}, \overline{X} maps i into the i-th projection

(\overline{X})_{n} = (\overline{X})_{1}^{n} ^{π_{i}^{n}}^{}\overline{X}_{1}.

For any _{1}A ^{θ}^{}_{n}A in 𝔸, θ\overline{X} is the induced operation on the quotient:

[figure: (X_{1}F)^{n}U_{𝔸}; θ_{X_{1}F}; X_{1}F U_{𝔸}; \overline{X}_{n} = (\overline{X}_{1}F /XE)^{n}U_{𝔸}; η^{n}; θ\overline{X}; (X_{1}F /XE)U_{𝔸} = \overline{X}_{1}; η]

where η is the quotient map. It is clear that \overline{X} is an algebra of type 𝔸.

We define a map X ^{φ}^{}\overline{X} as follows. For each n ∈ |S_{0}| = |𝔸|, φ_{n} is defined by the requirement that

[figure: X_{n}; φ_{n}; \overline{X}_{n} = (X_{1}F /XE)^{n}U_{𝔸}; X_{1}; π_{i}^{n}_{X}; κ; X_{1}F U_{𝔸}; η; \overline{X}_{1} = (X_{1}F /XE)U_{𝔸}; π_{i}^{n}\overline{X}]

is commutative for each i ∈ n, since π_{i}^{n}\overline{X} are projections in S_{1}. We prove that φ is a natural transformation, i.e. a map of prealgebras. Consider any _{1}A ^{θ}^{}_{n}A in 𝔸, and let y ∈ X_{n}. By the definition above we have

yφ_{n}θ\overline{X} = ⟨yπ_{0}^{n}_{X}κη, …, yπ_{n−1}^{n}_{X}κη⟩θ\overline{X} = yθ_{X}κη = yθ_{X}φ_{1}.

Thus for every _{n}A ∈ |𝔸| and every _{1}A ^{θ}^{}_{n}A, we have that

[figure: X_{n}; φ_{n}; \overline{X}_{n}; X_{1}; θ_{X}; φ_{1}; \overline{X}_{1}; θ\overline{X}]

is commutative.

It follows that θ_{X}φ_{m} = φ_{n}θ\overline{X} for any _{m}A ^{θ}^{}_{n}A in 𝔸 since \overline{X}_{m} is a product. Thus X ^{φ}^{}\overline{X} in S_{1}^{𝔸^{∗}}.

We now show that φ is universal. Suppose X ^{f}^{}Y in S_{1}^{𝔸^{∗}} where Y is an algebra.

Define \overline{X} ^{f^{≈}}^{}Y as follows. By the definition of freedom, there is a unique X_{1}F ^{f^{∼}}^{}Y such that κ(f^{∼}U_{𝔸}) = f_{1}. If y ∈ X_{n}, then for any _{1}A ^{θ}^{}_{n}A, yf_{n}θ_{Y} = yθ_{X}f_{1} since f in natural (i.e. a map in S_{1}^{𝔸^{∗}}.) But since Y_{n} = Y_{1}^{n}, by uniqueness we have

yf_{n} = ⟨yπ_{0}^{n}_{X}f_{1}, …, yπ_{n−1}^{n}_{X}f_{1}⟩ = ⟨yπ_{0}^{n}_{X}, …, yπ_{n−1}^{n}_{X}⟩f_{1}^{n}.

Thus

(yθ_{X}κ)(f^{∼}U_{𝔸}) = yθ_{X}κ(f^{∼}U_{𝔸}) = yθ_{X}f_{1}
= yf_{n}θ_{Y} = ⟨yπ_{0}^{n}_{X}, …, yπ_{n−1}^{n}_{X}⟩f_{1}^{n}θ_{Y}
= ⟨yπ_{0}^{n}_{X}, …, yπ_{n−1}^{n}_{X}⟩(κ(f^{∼}U_{𝔸}))^{n}θ_{Y}
= ⟨yπ_{0}^{n}_{X}, … yπ_{n−1}^{n}_{X}⟩κ^{n}(f^{∼}U_{𝔸})^{n}θ_{Y}
= ⟨yπ_{0}^{n}_{X}κ, …, yπ_{n−1}^{n}_{X}κ⟩(f^{∼}U_{𝔸})^{n}θ_{Y}
= ⟨yπ_{0}^{n}_{X}κ, … yπ_{n−1}^{n}_{X}κ⟩θ_{X_{1}F} (f^{∼}U_{𝔸}).

That is, the map X_{1}F U_{𝔸} ^{f^{∼}U_{𝔸}}^{}Y U_{𝔸} takes the congruence relation XE into equality, so there is a factorization

X_{1}F
[figure: η; f^{∼}]
\overline{X} = X_{1}F /XE  \overline{f^{≈}  ^{}}Y

By construction f^{≈} is the unique map such that φ_{1}f^{≈}_{1} = κηf^{≈}_{1} = κf^{∼}_{1} = f_{1} and hence the unique map such that

φf^{≈} = f.

Therefore X ^{φ}^{}\overline{X} satisfies the universal mapping property of Theorem I.2.1, so that the inclusion S_{1}^{(𝔸^{∗})} ^{}S_{1}^{𝔸^{∗}} has the adjoint X ^{}\overline{X}.

Corollary. An algebraic category has arbitrary small coproducts.

Proof. As shown above, the full inclusion S_{1}^{(𝔸^{∗})} ^{}S_{1}^{𝔸^{∗}} has an adjoint. The category S_{1}^{𝔸^{∗}} clearly has coproducts, by Proposition I.2.2 (dualized); namely, the coproduct of a family of prealgebras is just the prealgebra whose value at n is the sum (in S_{1}) of the family of values at n. Now consider any small set Λ and any Λ ^{}S_{1}^{(𝔸^{∗})}. Let X be the direct limit in S_{1}^{𝔸^{∗}} of this functor, and let \overline{X} be the value at X of the adjoint, X ^{φ}^{}\overline{X} the canonical map. Then if Y is any algebra, X_{λ} ^{y_{λ}}^{}Y any family of maps, λ ∈ Λ, we have unique maps

[figure: X_{λ}; e_{λ}; X; φ; \overline{X}]
[figure: y_{λ}; ..............; ..............]
Y

the first since X = ⋆_{λ∈Λ}X_{λ} in S_{1}^{𝔸^{∗}}, the second by adjointness. But this shows that \overline{X} =

⋆_{λ∈Λ}X_{λ} in S_{1}^{(𝔸^{∗})}.

Remark. It is clear that the above proof is much more general than the statement of the corollary. We can actually state the following: If a full subcategory of a right complete category is such that the inclusion admits an adjoint, then the subcategory itself is right complete. Of course, the direct limits in the subcategory will not usually agree with those in the big category, i.e., the inclusion is ordinarily not right continuous, even though it is as left continuous as is possible.

2. Algebraic functors and their adjoints

Definition. Let 𝔸′, 𝔸 be algebraic theories, considered as small categories. Let 𝔸′ ^{f}^{}𝔸 be any functor which commutes with finite coproducts. Then there is a unique factorization

[figure: S_{1}^{(𝔸^{∗})}; T; S_{1}^{(𝔸^{′∗})}; S_{1}^{𝔸^{∗}}; S_{1}^{f}; S_{1}^{𝔸^{′∗}}]

Any functor between algebraic categories which is equivalent to some T constructed as above will be called an algebraic functor.

It is clear that every algebraic functor has a degree, namely the unique k such that (1)f = k, which is also the unique k such that U_{𝔸}^{k} = T U_{𝔸′}, where 𝔸′ ^{f} ^{}𝔸, T are as above. The algebraic functors of degree one are precisely those functors equivalent to some value of the functor

T^{∗} ^{𝔖}^{}K ^{}C_{2}.

Theorem 1. Every algebraic functor has an adjoint.

Proof. Consider the square above. S_{1}^{f} has an adjoint by Theorem I.2.5. The inclusion S_{1}^{(𝔸^{∗})} ^{}S_{1}^{𝔸^{∗}} has an adjoint by Theorem 1.1. The composite provides an adjoint for T since the inclusion S_{1}^{(𝔸^{′∗})} ^{}S_{1}^{𝔸^{′∗}} is full.

Example. If 𝔸′ = S_{0} (the identity functor considered as an object in T ), then the unique S_{0} ^{}𝔸 induces an algebraic functor T (of degree one)

[figure: S_{1}^{(𝔸^{∗})}; T; S_{1}^{(S_{0}^{∗})} ≅ S_{1}; S_{1}^{𝔸^{∗}}; S_{1}^{S_{0}^{∗}}]

whose adjoint T assigns to each S ∈ |S_{1}| the free 𝔸-algebra over S. We have actually analyzed the construction of the free algebra into two steps, as follows. T is equivalent to the composite

[figure: S_{1}^{(𝔸^{∗})}; S_{1}^{𝔸^{∗}}; E_{1}; S_{1}]
[figure]
S_{1}^{S_{0}^{∗}}

where the last is evaluation at 1. By a corollary to Theorem I.2.5 we have an explicit formula for the value of the adjoint Ê_{1} of E_{1} at S:

\begin{aligned}(_{n}A)(S)Ê_{1} & = & (_{1}A,_{n}A)^{∗} · S & = & (_{n}A,_{1}A) · S \\ & = & (_{1}A,_{1}A)^{n} · S & = & (_{1}A,_{1}A)^{n} × S. \end{aligned}

Here (_{1}A,_{1}A)^{n} is the set of all n-tuples of unary operations of 𝔸. The value at (S)Ê_{1} of the adjoint to the inclusion S_{1}^{(𝔸^{∗})} ^{}S_{1}^{𝔸^{∗}} is (S)F where F = T̂ is the free algebra functor, and the natural transformation φ constructed in Section 1 gives in particular a sequence of maps

(_{1}A,_{1}A)^{n} × S ^{φ_{n}}^{}(SF U_{𝔸})^{n}

in S_{1}. Here

⟨⟨θ_{0}, …, θ_{n−1}⟩, s⟩φ_{n} = ⟨sκθ_{0}, …, sκθ_{n−1}⟩

where s ∈ S and where ⟨θ_{0}, …, θ_{n−1}⟩ is an n-tuple of unary operations of 𝔸.

In particular, if 𝔸 is the theory of monoids, then it is known that the underlying set of free monoid is

(S)F U_{𝔸} = ∑_{k∈N} S^{k}

where N is the set of non-negative integers. Also the set of unary operations (_{1}A,_{1}A) ≅ N. Taking _{1}A ^{θ}^{}_{2}A as the multiplication operation, we have

[figure: N^{2} × S; φ_{2}; (∑_{k=0}^{∞} S^{k})^{2}; N × S; θ × S; φ_{1}; ∑_{k=0}^{∞} S^{k}; θ_{SF}]

where

[figure: ⟨i, j, s⟩; φ_{2}; ⟨\underbrace{sss …}_{i}, \underbrace{sss …}_{j}⟩; ⟨i + j, s⟩; φ_{1}; ⟨\underbrace{sss …}_{i+j}⟩.]

Example. Let A be the category of abelian groups, G the category of all (small) groups, M the category of monoids, R the category of rings, M_{c} and R_{c} those of commutative monoids and rings respectively. Let 𝔸 be the theory presented:

\begin{matrix}n & S & E \\ 0 & ϵ & ϵ ≡ νϵ \\ 1 & ν & π_{0}^{1} ≡ νν \end{matrix}

S_{n} = E_{n} = 0 for n > 1. Then there are obvious algebraic functors of degree one

[figure: A; M_{c}; R_{c}]

[figure: G; M; R]

[figure: S_{1}^{(𝔸^{∗})}; S_{1}; A]

forming a commutative diagram. (Actually all these functors are of the type known to logicians as ‘reducts’, i.e. they are induced by maps of theories which are induced by inclusions on the usual presentations.) We now describe their adjoints (the description are mostly immediate from [Bourbaki, (1950–1959)] or [Chevalley, 1956]). First, the adjoint of any composite functor ending at S_{1} is the free-algebra functor of the appropriate type, e.g. the adjoint to S_{1}^{(𝔸^{∗})} ^{}S_{1} assigns to each small set S the 𝔸-algebra X such that X_{1} = {ϵ}+S+S, and ν_{X} switches the last two summands. The adjoint to any of the three vertical functors from the first row to the second consists of ‘dividing by the commutator’ in the appropriate sense. The adjoint to the left vertical arrow from the second row to the third assigns to each 𝔸-algebra X the group obtained by reducing the free group over X_{1} modulo the relations ϵ ≡ e, x · ν(x) ≡ ν(x) · x ≡ e. The adjoint to the vertical functor from rings to abelian groups assigns to each abelian group A the tensor ring Z +A+A⊗A+A⊗A⊗A+…. The adjoints to the two horizontal functors from groups to monoids are described in [Chevalley, 1956], pages 41-42. Finally, the adjoints to the two horizontal functors from rings to monoids assign to a given monoid M the monoid ring Z[M] with integer coefficients.

The fact that the adjoint functors also form a commutative diagram (with arrows reversed) implies, for example, the well-known fact that a free ring may be constructed either as the tensor ring of a free abelian group or as the monoid ring of a free monoid.

The above diagram and discussion have an obvious modification by applying a fixed Λ ∈ R to each category in the right hand column.

The only functors in the above diagram which also have coadjoints are the two from groups to monoids, whose coadjoints assign to a monoid or commutative monoid, respectively, its group of units.

Example. For an example which is not a reduct, consider the functor from rings to Lie rings induced by the T -map defined at the end of Chapter II. The adjoint to this functor assigns to each Lie ring its associative enveloping ring. (See [Cartan & Eilenberg, 1956].)

Example. Let 𝔸 be the theory of commutative associative rings with unity, and 𝔸′ be the theory presented like 𝔸 with the exception that S′_{0} = {i} + S_{0} where i satisfies the identity i^{2} = −1. The adjoint to the obvious reduct is itself an algebraic functor, but of degree two.

Chapter V

Certain 0-ary and unary extensions of algebraic theories

1. Presentations of algebras: polynomial algebras

Consider the functor S_{1} ^{T_{0}}^{}T such that ST_{0} = S · 𝕀_{0}; that is, T_{0} assigns to each small set S the free algebraic theory over the sequence of sets S_{0} = S, S_{n} = 0, n > 0. Since T_{0} is right continuous and full, the subcategory of theories which arise as values of T_{0} is closed under direct limits, in particular coproducts and coequalizers (quotients). The corresponding categories of algebras are not much more complicated than the category of sets itself. For example, we have the

Proposition. If S is any small set, then coproducts in the category S_{1}^{(ST_{0}^{∗})} are ‘wedge products’. That is, given any two ST_{0}-algebras X, Y, their coproduct is the comeet (of sets)

[figure: S; X_{1}; Y_{1}; (X ⋆_{ST_{0}} Y)_{1}]

where S ^{}X_{1}, S ^{}Y_{1} are the unique maps defining the structure of X, Y.

Definition. Let S be any small set, 𝔸 any algebraic theory, N ^{E}^{}S_{1} any sequence of sets, and E ^{r}^{}((𝔸 ⋆ ST_{0})T)^{2} any map in S_{1}^{N} (where T is the functor discussed in II.2). Write 𝔸′ = (𝔸 ⋆ ST_{0})/E for the coequalizer of the corresponding pair of maps ⟨r_{0}F, r_{1}F ⟩ in T , and denote by f the composite T -map

𝔸 ^{}𝔸 ⋆ ST_{0} ^{}(𝔸 ⋆ ST_{0})/E = 𝔸′.

Then by the algebra presented by ⟨𝔸, S, E, r⟩ is meant the 𝔸-algebra (_{0}A′)S_{1}^{(f^{∗})}, where

0A′ = lim^{S_{1}^{(𝔸^{′∗})}}_{→0}. 𝔸′ is the theory of the presentation.

Theorem 1. If X is the algebra presented by ⟨𝔸, S, E, r⟩, then there is an equivalence

(X, S_{1}^{(𝔸^{∗})}) ≅ S_{1}^{(𝔸^{′∗})}

where 𝔸′ is the theory of the presentation. If X is any 𝔸-algebra, then (X, S_{1}^{(𝔸^{∗})}) is algebraic; in fact, there is a presentation of X such that the above relation holds.

Recall that the objects in the category (X, S_{1}^{(𝔸^{∗})}) are maps X ^{}Y of 𝔸-algebras, and that maps in this category are commutative triangles

X
[figure]
Y  \overline{}Y′

is S_{1}^{(𝔸^{∗})}. The Theorem follows from Lemmas 1.1, 1.2, 1.3 below.

Lemma 1. If X is any 𝔸-algebra, then the functor

(X, S_{1}^{(𝔸^{∗})}) ^{V}^{}S_{1}^{(𝔸^{∗})}

has an adjoint, which assigns to each 𝔸-algebra Y the injection X ^{}Y ⋆_{𝔸}X, considered as an object Y V̂ in (X, S_{1}^{(𝔸^{∗})}).

Proof. Since (X ^{}Y ⋆ X)V = Y ⋆ X, there is an obvious map Y ^{φ}^{}Y V̂ V, namely the injection Y ^{}Y ⋆X. If X ^{y}^{}Y′ is any object in (X, S_{1}^{(𝔸^{∗})}), and if Y ^{ψ}^{}yV = Y′ is any map in S_{1}^{(𝔸^{∗})}, then there is a unique map λ in S_{1}^{(𝔸^{∗})} such that

[figure: X; Y ⋆_{𝔸} X; φ; Y]
[figure: y; ψ]
Y′ λ_{}

is commutative. Because the left hand triangle is commutative, λ defines a map Y V̂ ^{λ}^{}y in (X, S_{1}^{(𝔸^{∗})}), which is the unique map such that φ(λV) = ψ.

Lemma 2. Consider the composite functor U:

(X, S_{1}^{(𝔸^{∗})}) ^{}S_{1}^{(𝔸^{∗})} ^{U_{𝔸}}^{}S_{1}.

The value at X ^{}Y of U is the set of maps _{0}A ⋆ X ^{}Y in S_{1}^{(𝔸^{∗})} such that

X
[figure]
0A ⋆ X  \overline{}Y

is commutative. If 𝔸′ = U𝔖̂ is the algebraic structure of U, then the map U ^{Φ}^{}U𝔖̂𝔖 in K is an equivalence, i.e.

(X, S_{1}^{(𝔸^{∗})})  \overline{\begin{matrix}Φ \\ ≈ \end{matrix}  ^{}}S_{1}^{(𝔸^{′∗})}
[figure: U]
[figure: S_{1}^{(𝔸^{∗})}; U_{𝔸}; S_{1}; U_{𝔸′}]

is commutative in C_{2} and Φ is an equivalence of categories.

Proof. The first assertion is immediate by Lemma 1.1. The commutativity in C_{2} follows from our work in Chapter III (where the definition of Φ was given). We need to show that Φ is an equivalence. Now the n-ary operations _{1}A′ ^{θ}^{}_{n}A′ of 𝔸′ are in one-to-one correspondence with commutative triangles

X
[figure]
1A ⋆_{𝔸} X  \overline{}_{n}A ⋆_{𝔸} X

in S_{1}^{(𝔸^{∗})} (where the legs are the injections). In particular, every n-ary operation of 𝔸 determines such a triangle, so that there is a map 𝔸 ^{f}^{}𝔸′ of theories and a corresponding map 𝔸′𝔖 ^{f𝔖}^{}𝔸𝔖 in K. We also have, since _{0}A ⋆_{𝔸} X ≅ X, that the 0-ary operations of 𝔸′ are in one-to-one correspondence with maps _{1}A ⋆_{𝔸} X ^{}X in S_{1}^{(𝔸^{∗})} such that X ^{}_{1}A ⋆_{𝔸} X ^{}X is the identity, which in turn are in one-to-one correspondence with maps _{1}A ^{}X in S_{1}^{(𝔸^{∗})} Therefore (_{0}A′)S_{1}^{(f^{∗})} ≅ X. Since _{0}A′ = lim_{→0}, there is, for each 𝔸′-algebra Y, a unique map _{0}A′ ^{}Y in S_{1}^{(𝔸^{′∗})} which gives a map Y Ψ : X = (_{0}A′)S_{1}^{(f^{∗})} ^{}Y S_{1}^{(f^{∗})} in S_{1}^{(𝔸^{∗})}. There thus results a functor S_{1}^{(𝔸^{′∗})} ^{Ψ}^{}(X, S_{1}^{(𝔸^{∗})}) such that ΨΦ ≅ S_{1}^{(𝔸^{′∗})} and ΦΨ ≅ (X, S_{1}^{(𝔸∗)}).

Lemma 3. If X is any 𝔸-algebra, then the algebraic structure 𝔸′ = U𝔖̂ of the functor (X, S_{1}^{(𝔸^{∗})}) ^{}S_{1}^{(𝔸^{∗})} ^{}S_{1} is the theory of a presentation ⟨𝔸, S, E, r⟩ of which X is the algebra presented.

Proof. It was pointed out in the proof of Lemma 1.2 that X = (_{0}A′)S_{1}^{(f^{∗})}. A map 𝔸 ^{f}^{}𝔸′ of theories was constructed and it was pointed out that (_{1}A, X) ≅ (_{1}A′,_{0}A′). Thus setting S = (_{1}A, X), we have a map g of theories defined by

[figure: 𝔸; 𝔸 ⋆ ST_{0}; ST_{0}]
[figure: f; h]
𝔸′ g_{}

where h corresponds to the isomorphism S ≅ (𝔸′T)_{0} under the isomorphism

(ST_{0}, 𝔸′) ≅ (S, (𝔸′T)_{0})

determined by the definition of T_{0}. Letting 𝕂 be the equalizer of

(𝔸 ⋆ ST_{0})^{2} [figure] 𝔸 ⋆ ST_{0} ^{g}^{}𝔸′

and defining E, r by

𝕂T = E ^{r}^{}((𝔸 ⋆ ST_{0})T)^{2}

it follows that ⟨𝔸, S, E, r⟩ has all the correct properties, as it is clear from Chapter II that g is the coequalizer of

EF ^{}𝕂 ^{}(𝔸 ⋆ ST_{0})^{2} [figure] 𝔸 ⋆ ST_{0}

where F is the free theory functor.

Example. In particular, if S ∈ |S_{1}|, then

(S, S_{1}) ≅ S_{1}^{(ST_{0}^{∗})}.

Example. If Λ ∈ R_{c}, then (Λ, R_{c}) is equivalent to the usual category of commutative associative Λ-algebras. However, if Λ ∈ R, then the usual (algebraic) category of associative Λ-algebras is the full subcategory of (Λ, R) determined by objects Λ ^{x}^{}X such that the image of x lies in the center of X.

The structure of a category of the form (X, S_{1}^{(𝔸^{∗})}) can of course be studied entirely within S_{1}^{(𝔸^{∗})}. This may be considered a partial motivation for the introduction of the following

Definition. If 𝔸 is an algebraic theory and if X is an 𝔸-algebra, then by the algebra of polynomials in n variables with coefficients in X is meant the 𝔸-algebra _{n}A ⋆_{𝔸} X.

Example. If Λ ∈ R, then the algebra of polynomials in n variables with coefficients in Λ in the ring Λ[π_{0}^{n}, …, π_{n−1}^{n}] of polynomials in n noncommuting variables.

Proposition 1. If X, 𝔸, 𝔸′ are as in the preceding Theorem, the members of the algebra of polynomials in n variables with coefficients in X are in one-to-one correspondence with the n-ary operations of 𝔸′.

Proof. Obvious from the foregoing. Here by ‘members’ of _{n}A ⋆_{𝔸} X we mean of course maps _{1}A ^{}_{n}A ⋆_{𝔸} X.

Proposition 2. If X is an 𝔸-algebra, then every n-tuple _{1}A ^{x}^{}X^{n} of members of X determines an evaluation homomorphism _{n}A ⋆_{𝔸} X ^{(x)}^{}X.

Proof. _{1}A ^{x}^{}X^{n} is equivalent to a map _{n}A ^{\overline{x}}^{}X, which together with the identity map X yields

[figure: X; _{n}A ⋆_{𝔸} X; _{n}A]
[figure: X; \overline{x}]
X(x)_{}

Definition. If θ is a polynomial in n variables with coefficients in X (i.e. a member 1A ^{θ}^{}_{n}A ⋆_{𝔸} X of _{n}A ⋆_{𝔸} X) and if x is an n-tuple of members of X, then the composite θ(x) is a member of X, the value at x of θ.

Remark. This shows that it is consistent to write θ(x) for the evaluation (or composition) of polynomials, and xf for the evaluation of homomorphisms f. This may be regarded as another manifestation of the duality between structure and maps as expressed by our Theorem III.1.2.

Example. Let M ∈ M be a monoid, n = 1. Because of the ‘interlacing’ description of the coproduct of monoids, and since _{1}A ≅ N (the additive monoid of non-negative integers) in this case, we see that any unary polynomial θ with coefficients in M can be represented as a string

m_{0} n_{0} m_{1} n_{1} … m_{k−1}n_{k−1}

where m_{i} ∈ M, n_{i} ∈ ℕ for i ∈ k. The value of θ at a member x of M is the product

θ(x) = m_{0}x^{n_{0}}m_{1}x^{n_{1}}m_{2}x^{n_{2}} … m_{k−1}x^{n_{k−1}}.

A similar remark holds for groups, except that the n_{i} may have negative values in that case.

2. Monoids of operators

If M is any small monoid, then there are unique functors 1 [figure] M. If B is any complete category, these induce functors

B^{M} [figure: α; β] B

and we have βα = B. By Theorem I.2.5 and its dual, α and β have adjoints α̂, β̂ and coadjoints α̌, β̌.

Proposition 1.

\begin{aligned}α̂β̂ & = & B & , & α̌β̌ & = & B \\ ββ̂ & = & B & , & ββ̌ & = & B \end{aligned}

Proof. The first two equations follow from the equation βα = B. The other two are immediate since β is full.

Proposition 2. If X ∈ |B^{M}|, then Xβ̂ = X/M, the ‘orbit object’, and there is a regular epimap X ^{}(X/M)β. Xβ̌ = M\X, the ‘fixed object’, and there is a regular monomap (M\X)β ^{}X.

Proof. Immediate from the proof of Theorem I.2.2 and the fact that β̂ = lim^{B}_{→M} while

β̌ = lim^{B}_{←M}.

Remark. If M is not a group, and if e.g. B = S_{1}, then the ‘orbit object’ does not necessarily consist of ‘orbits’ in the usual sense, since these need not form a partition if M is not a group. However, by X/M we mean the quotient by the smallest equivalence (or more generally congruence) relation which requires that any two points on the same orbit are equivalent. In case M is commutative, this equivalence relation is simply

x ≡ y iff ∃m ∃m′ [xm = ym′].

Proposition 3. If B ∈ |B|, then Bα̂ is the functor M ^{}B whose value at the object 1 ^{e}^{}M is the object (e, e) · B in B. For any m′ ∈ M, m′(Bα̂) is the map (e, e) · B ^{}(e, e) · B determined by the commutativity of

[figure: B; B; B; (e, e) · B; j_{m}; m′(Bα̂); (e, e) · B; j_{mm′}]

for every m ∈ (e, e) = |M^{2}| =set of members of M (the j_{m} being the injections into the (e, e)-fold coproduct). Bα̂ is the functor M ^{}B whose value at e is the (e, e)-fold product B^{(e,e)} and whose value at any m′ ∈ M is the map B^{(e,e)} ^{}B^{(e,e)} determined by the commutativity of

[figure: B^{(e,e)}; m′(Bα̌); B^{(e,e)}; B; p_{m′m}; B; B; p_{m}]

for every m ∈ (e, e) (the p_{m} being the projections).

Proof. The formula of the corollary to Theorem I.2.5 specialized to this case.

Remark. In the case M = ℕ, the additive monoid of non-negative integers, B^{∞} = Bα̌α (the ‘object of sequences of B’) is characterized in B by the generalized and dualized Peano’s postulate:

[figure: ∀X ∀t ∀x ∃!f; B^{∞}; s; B^{∞}; e_{0}; B; X; f; t; X; f; x; B; B]

This shows that the N-fold product (and dually coproduct) of an object with itself is a concept which is definable within the first-order theory of a category, whereas infinite products and coproducts in general are of course not first-order definable (without passing to the theory of the category of categories).

By Theorem III.2.2, if B is an algebraic category and M is a small monoid (i.e. category with one object), then B^{M} is also algebraic. Our aim now will be to describe explicitly the algebraic structure of B^{M} ^{}B ^{}S, and to show that the functors α and β discussed above are algebraic functors of degree one.

For any small monoid M, let MT_{1} be the algebraic theory whose n-ary operations are all of the form

mπ_{i}^{n}, m ∈ M, i ∈ n

and which satisfies the relations

m′(mπ_{i}^{n}) = (mm′)π_{i}^{n}

where mm′ on the right hand side is composition in M. This defines a functor

M_{1} ^{T_{1}}^{}T .

In particular (1)T_{1} = S_{0}. Consider the functor

T × M ^{}T

which assigns to ⟨𝔸, M⟩ the algebraic theory

𝔸[M] = (𝔸 ⋆ MT_{1})/R(𝔸, M)

where R(𝔸, M) is the smallest congruence (in the sense of T ) containing all relations of the form

θ{mπ_{0}^{n}, mπ_{1}^{n}, …, mπ_{n−1}^{n}} = mθ{π_{0}^{n}, … π_{n−1}^{n}}

where θ is an n-ary operation of 𝔸 and m ∈ M. In particular 𝔸[1] ≅ 𝔸 for each algebraic

theory, and for each monoid M, the maps 1 [figure] M induce maps 𝔸 [figure: a; b] 𝔸[M] in T .

Theorem 1. For any algebraic theory 𝔸 and for any small monoid M,

S_{1}^{(𝔸^{∗})}^{M} ≅ S_{1}^{(𝔸[M]^{∗})}.

Also, for the functors

S_{1}^{(𝔸^{∗})}^{M} [figure: α; β] S_{1}^{(𝔸^{∗})}

induced by 1 [figure] M we have

\begin{aligned}α & ≅ & S_{1}^{(a^{∗})} \\ β & ≅ & S_{1}^{(b^{∗})}. \end{aligned}

Proof. Both S_{1}^{(𝔸^{∗})}^{M} and S_{1}^{(𝔸[M]^{∗})} are equivalent to the full subcategory of S_{1}^{𝔸^{∗}×M} determined by functors X such that ⟨_{n}A, e⟩X = ⟨_{1}A, e⟩X^{n} for all n ∈ |S_{0}|. By the results of I.2, the functor S_{1}^{𝔸^{∗}} ^{}S_{1}^{𝔸^{∗}×M} induced by 𝔸^{∗} × M ^{}𝔸^{∗} takes S_{1}^{(𝔸^{∗})} into this subcategory. But the restriction of this functor to 𝔸-algebras is β. It follows easily that β = S_{1}^{(b^{∗})}, and similarly α = S_{1}^{(a^{∗})}.

3. Rings of operators (Theories of categories of modules)

Let R be the category of (small) rings and define a functor

R ^{T′_{1}}^{}T

as follows. For each R ∈ |R|, RT′_{1} is the algebraic theory presented as follows. (Note that (Z[π_{0}^{1}], R) is the set of members of R.)

n  S  E
0  ⊙  empty
1  λ  0 + π_{0}^{1}  ≡ π_{0}^{1}
for λ ∈ (Z[π_{0}^{1}], R)  π_{0}^{1} + 0  ≡ π_{0}^{1}
1  ≡ π_{0}^{1}
(⊙)(0 ^{}1)  ≡ 0
(λ + λ′)π_{0}^{1}  ≡ λπ_{0}^{1} + λ′π_{0}^{1}
(λ · λ′)π_{0}^{1}  ≡ λ′(λπ_{0}^{1})
for λ, λ′ ∈ (Z[π_{0}^{1}], R)
2  +  λ(π_{0}^{2} + π_{1}^{2})  ≡ λπ_{0}^{2} + λπ_{1}^{2}
for λ ∈ (Z[π_{0}^{1}], R)
3  empty  empty
4  empty  (π_{0}^{4} + π_{1}^{4}) + (π_{2}^{4} + π_{3}^{4}) ≡ (π_{0}^{4} + π_{2}^{4}) + (π_{1}^{4} + π_{3}^{4})

S_{n} = E_{n} = 0 for n > 4.

Thus ZT′_{1} is the theory of abelian groups, Z[π_{0}^{1}]T′_{1} is the theory of abelian groups

with a distinguished endomorphism, and in general S_{1}^{(RT_{1}^{′∗})} is the category of (right) R-modules.

Proposition 1. For any map φ : Λ ^{}Γ in R, the functor S_{1}^{(φT^{′∗})} has a coadjoint (as well as an adjoint).

Proof. Well known, see e.g. [Cartan & Eilenberg, 1956]. The adjoint is

X ^{}X ⊗_{Λ}Γ

and the coadjoint is

X ^{}Hom_{Λ}(Γ, X).

Proposition 2. The diagram

[figure: R × M; R; T × M; T′_{1}; M; T; T′_{1}]

is commutative (up to equivalence) where the bottom row is the functor ⟨𝔸, M⟩ ^{}𝔸[M] of Section 2, and where the top row is ⟨R, M⟩ ^{}R[M] = R ⊗ Z[M].

Proof. It is well known that S_{1}^{(R[M]T_{1}^{′∗})} ≅ S_{1}^{(RT_{1}^{′∗})^{M}} . By the Theorem of Section 2,

S_{1}^{(RT_{1}^{′∗})^{M}} ≅ S_{1}^{(RT′_{1}[M]^{∗})}. Since these equivalences preserve underlying sets, the algebraic structures are also equivalent by III.1. That is

R[M]T′_{1} ≅ RT′_{1}[M].

References

Bourbaki, N. (1950–1959), Algèbre, II. Eléments de Mathématique, Actualités Sci. Ind., Hermann, Paris. Nos. 1144, 1958; 1032–1236, 1955; 1044, 1958; 1102, 1959; 1179, 1952; 1261, 1958; 1272, 1959.

Cartan, H. and Eilenberg, S. (1956), Homological algebra. Princeton University Press, Princeton, N.J.

Chevalley, C. (1956), Fundamental concepts of algebra. Academic Press, New York.

Eilenberg, S. and Mac Lane, S. (1945), General theory of natural equivalences, Trans. Amer. Math. Soc. 58, 231–294.

Freyd, P.J. (1960), Functor theory. Thesis, Princeton University.

References 107

Gaifman, H. (1961), Free complete boolean algebras. Notices Amer. Math. Soc. 8, 510. Godement, R. (1958), Topologie algébrique et théorie des faisceaux. XIII Publications de

l’Institut de Mathématique de l’Université de Strasbourg, Hermann, Paris, Gray, J.W. (1962), Sheaves with values in a category. National Science Foundation Report

CU-5-62 G 19002. Kan, D.M. (1958), Adjoint functors, Trans. Amer. Math. Soc. 87, 294–329. Lawvere, F.W. (1963), The “group ring” of a small category. Abstract in Notices Amer.

Math. Soc. Mac Lane, S. (1950), Duality for groups, Bull. Amer. Math. Soc. 56, 485–516. Suppes, P. (1960), Axiomatic set theory, Van Nostrand, Princeton, N.J.

Part C

Some Algebraic Problems in the context of Functorial Semantics of

Algebraic Theories

Introduction

The categorical approach to universal algebra, initiated in [Lawvere, 1963] has been extended from finitary to infinitary operations in [Linton, 1966a], from sets to arbitrary base categories through the use of triples (monads) in [Eilenberg & Moore, 1965] and [Barr & Beck, 1966] and from one-sorted theories over l-dimensional categories to Γ-sorted theories over 2-dimensional categories in [Bénabou, 1966]. But despite this generality, there is still enough information in the machinery of algebraic categories, algebraic functors, adjoints to algebraic functors, the semantics and structure superfunctors, etc. to allow consideration of specific problems analogous to those arising in group theory, ring theory, and other parts of classical algebra. The approach also suggests new problems. As examples of the latter we may mention Linton’s considerations of general “commutative” theories [Linton, 1966b], Barr’s discussion of general “distributive” laws [Barr, 1969], and Freyd’s construction of Kronecker products of arbitrary theories and tensor products of arbitrary algebras [Freyd, 1966]. It is our purpose here to indicate some of the “specific” aspects of the approach, and also to mention some of the representative problems which seem to be open. We restrict ourselves to the case of finitary single-sorted theories over sets.

1. Basic concepts

An elegant exposition of part of the basic machinery appears in [Eilenberg & Wright, 1967] – we content ourselves here with a brief summary. An algebraic theory is a category 𝔸 having as objects

1, A, A^{2}, A^{3}, …

and, for each n = 0, 1, 2, 3, …, n, morphisms

A^{n} ^{Π_{i}^{(n)}}^{}A, i = 0, 1, …, n − 1

such that for any n morphisms

A^{m} ^{θ_{i}}^{}A, i = 0, 1, …, n − 1

in 𝔸 there is exactly one morphism

A^{m} ^{⟨θ_{0},θ_{1},...,θ_{n−1}⟩}^{}A^{n}

in 𝔸 so that

⟨θ_{0}, θ_{1}, …, θ_{n−1}⟩Π_{i}^{(n)} = θ_{i}, i = 0, 1, …, n − 1.

The arbitrary morphisms A^{n} ^{φ}^{}A are called the n-ary operations of 𝔸. The algebraic category associated with 𝔸 is the full subcategory

𝔸^{♭} ⊂ S^{𝔸}

consisting of those covariant set-valued functors which are product-preserving; its objects are called 𝔸-algebras and its morphisms 𝔸-homomorphisms. Clearly there is a full embedding 𝔸^{op} ⊂_{→} 𝔸^{♭} which preserves coproducts; its values are the finitely-generated free 𝔸-algebras, where “free” refers to the left adjoint of the functor “underlying”

𝔸^{♭} ^{U_{𝔸}}^{}S

whose value at the algebra X is the value of X at A:

XU_{𝔸} = AX.

The underlying functor is a particular algebraic functor, where the latter means a functor

𝔸^{♭} ^{f^{♭}}^{}𝔹^{♭}

induced by composition of functors from a theory morphism 𝔹 ^{f}^{}𝔸, where a theory morphism is just a functor f such that

(Π_{i}^{(n)}) f = Π_{i}^{(n)}, for all i ∈ n ∈ ω.

Clearly all the theory morphisms determine a category T , and every algebraic functor preserves the underlying functors. Hence f ⇝ f^{♭} determines a semantics functor

T^{op} ^{}(Cat, S)

where the category on the right has as morphisms all commutative triangles

X  \overline{Φ  ^{}}X′
[figure: U; U′]
S

of functors. Switching functor categories a bit shows that structure, the left adjoint of semantics, may be calculated as follows: Given a set-valued functor U, the n-ary operations of its algebraic structure are just the natural transformations U^{n} ^{φ}^{}U, where U^{n} is the n-th cartesian power of U in the functor category S^{X}, i.e. φ is a way of assigning an operation to every value of U in such a way that all morphisms of X are homomorphisms with respect to it. Several applications of Yoneda’s Lemma show that if in fact U = U_{𝔸}, X = 𝔸^{♭} for some theory 𝔸, then the algebraic structure of U is isomorphic to 𝔸. As a corollary every functor 𝔸^{♭} ^{}𝔹^{♭} which preserves underlying sets is induced by one and only one theory morphism 𝔹 ^{}𝔸. More generally, if we denote by 𝕀_{n} the free theory generated by one n-ary operation, then the n-ary operations of the algebraic structure of any X ^{U}^{}S are in one-to-one correspondence with the functors

X ^{Φ}^{}𝕀_{n}^{♭}

for which U = ΦU_{𝕀_{n}}.

Algebraic functors are faithful and possess left adjoints. In fact (as pointed out by M. André and H.Volger), if 𝔹 ^{f} ^{}𝔸 is a morphism of theories then the usual (left) Kan adjoint

S^{𝔹} ^{}S^{𝔸}

corresponding to f actually takes product-preserving functors into product-preserving functors, and so restricts to a functor f_{∗} with

f_{∗} ⊣ f^{♭}.

Thus we have the commutative diagram of functors

𝔹^{op}  \overline{f^{op}  ^{}}𝔸^{op}

[figure: 𝔹^{♭}; ∩; f_{∗}; 𝔸^{♭}; ∩]

[figure: S^{𝔹}; ∩; Kan; S^{𝔸}; ∩]

Explicitly, for any 𝔹-algebra Y, the underlying set of the “relatively free” 𝔸-algebra Y f_{∗} is the colimit of

(f, A) ^{}𝔹 ^{Y}^{}S

where the first factor of this composite is the obvious forgetful functor from the category whose morphisms are triples θ, φ, θ′ with θ, θ′ operations in 𝔸 and φ a morphism in 𝔹 such that

•  \overline{φf  ^{}}•
[figure: θ; θ′]
A

is commutative in 𝔸. In particular, free algebras can be computed by such a direct limit by taking 𝔹 = the initial theory ≃ the dual of the category of finite sets and maps. For the unique f in this case we also write f_{∗} = F_{𝔸}.

Given two theories 𝔸 and 𝔹, the category of all product-preserving functors 𝔹 ^{}𝔸^{♭} has an obvious underlying set functor, whose algebraic structure is denoted by 𝔸⊗𝔹, the Kronecker product of 𝔸 with 𝔹. The Kronecker product is a coherently associative functor T ×T ^{}T having the initial theory as unit object; it also satisfies 𝔸⊗𝔹 ≅ 𝔹⊗𝔸. The foregoing semantical definition of 𝔸⊗𝔹 is equivalent to the following wholly “theoretical” definition.

𝔸 ⊗ 𝔹 = (𝔸 ∗ 𝔹)/R

where 𝔸 ∗ 𝔹 denotes the coproduct in T and R is the congruence relation generated by the conditions that each A^{n} ^{φ}^{}A in 𝔸 should be a “homomorphism” with respect to each A^{m} ^{ψ}^{}A in 𝔹 [(A^{n})^{m} ^{σ}^{}(A^{m})^{n} ^{ψ^{n}}^{}A^{n} being defined as the operation of ψ on A^{n}, σ being the transpose isomorphism] and that, symmetrically, each 𝔹-operation is an “𝔸-homomorphism”. A famous example is: if 𝔾 is the theory of groups, 𝔾 ⊗ 𝔾 is the theory of abelian groups.

2. Methodological remarks and examples

Having briefly described some of the main tools of the functorial semantics point of view in general algebra, we now make some methodological remarks which this point of view suggests. First, many problems will take the forms: Characterize, in terms of T , those 𝔸 for which 𝔸^{♭} has a given property stated in terms of (Cat, S), or characterize those f ∈ T for which f^{♭} has a given property; or for which f_{∗} has a given property. Properties of 𝔸 may be viewed as properties of U_{𝔸} or of F_{𝔸} and as such may have natural “relativizations” to properties of f^{♭} or f_{∗}. Properties of diagrams in T may be “semantically” defined via arbitrary “mixtures” of the processes f ⇝ f^{♭}, g ⇝ g_{∗}, and algebraic structure from properties in (Cat, S), and direct descriptions in T of such properties of diagrams may be sought. Most of the solved and unsolved problems mentioned below are of this general sort. For example, light would be shed on many situations in algebra if one could give a computation entirely in terms of T of the algebraic structure of

𝔾^{♭} ^{g^{♭}}^{}𝕄^{♭} ^{f_{∗}}^{}ℝ^{♭} ^{U_{ℝ}}^{}S

for any given diagram

𝔾 ^{}^{g} 𝕄 ^{f}^{}ℝ

in T . A case in point is that where 𝔾 = theory of groups, 𝕄 = theory of monoids, ℝ = theory of rings with g and f the obvious inclusions; what is sought in the example is in this case the full algebraic structure of group rings - this is a very “rich” theory, having linear “p-th power” unary operations for all p and more generally an n-ary multilinear operation for every element of the free group on n letters (e.g. convolution corresponds to the binary operation of group multiplication). Are these multilinear operations a generating set for the theory in question? Probably this case is simpler than the example in general, since it is equivalent to the structure of

𝔾^{♭} ^{U_{𝔾}}^{}S ^{F_{𝔸}}^{}𝔸^{♭} ^{}S

where 𝔸 is the theory of abelian groups, and 𝔸^{♭} has a convenient tensor product.

Sometimes the problem is in the other direction: for example, the product 𝔸 × 𝔹 of course has an easy description in terms of T , but a bit of computation is needed to deduce from general principles that (𝔸 × 𝔹)^{♭} consists of algebras which canonically split as sets into a product X × Y, where X carries the structure of an 𝔸-algebra and Y the structure of a 𝔹-algebra).

A second general methodological remark is that the structure functor often yields much more information than the usual Galois connection of Birkhoff between classes of algebras of a given type and sets of equations, precisely because in many situations it is natural to change the type. Namely, a subcategory X ⊆ 𝔹^{♭} of an algebraic category (even a full one) may have an algebraic structure with more operations (as well as more equations) than 𝔹, i.e. the induced morphism 𝔹 ^{}𝔸_{X} may be non-surjective, where 𝔸_{X} denotes the algebraic structure of X ^{}𝔹^{♭} ^{U_{𝔹}}^{}S. An obvious example is that in which 𝔹 is the theory of monoids and X is the full subcategory consisting of those monoids in which every element has a two-sided inverse. Two other examples arise from subcategories of the algebraic category of commutative rings: the algebraic structure of the full category of fields includes the theory ℝ_{θ} generated by an additional unary operation θ subject to

\begin{aligned}1^{θ} & = & 1 \\ (x · y)^{θ} & = & x^{θ} · y^{θ} \\ x^{2} · x^{θ} & = & x \\ (x^{θ})^{θ} & = & x \end{aligned}

and similarly the algebraic structure of the category of integral domains and monomorphisms includes the theory ℝ_{e} generated by an additional operation e subject to

\begin{aligned}0^{e} & = & 0 \\ (x · y)^{e} & = & x^{e} · y^{e} \\ (x^{e})^{e} & = & x^{e} \\ x^{e} · x & = & x \end{aligned}

The inclusion of fields in integral domains corresponds to the morphism

ℝ_{e} ^{}ℝ_{θ}

which, while the identity on the common subtheory ℝ_{c} (= theory of commutative rings), takes e into the operation of ℝ_{θ} defined as follows

x^{e} =^{def} x · x^{θ}.

The third general methodological remark is that, within the doctrine of universal algebra, the “natural” domain of a construction used in some classical theorem may be in fact much larger than the domain for which the theorem itself can be proved. For example, the only ℝ_{e}-algebras which can be embedded in fields are integral domains, but the usual “field of fractions” construction is just the restriction of the adjoint functor (ℝ_{e} ^{}ℝ_{θ})_{∗} whose domain is all of ℝ_{e}^{♭}. To the same point, the usual construction of Clifford algebras is defined only for K-modules V equipped with a quadratic form V ^{q}^{}K; these pairs ⟨V, q⟩ do not form an algebraic category. But if we allow ourselves to consider quadratic forms V ^{}S with values in arbitrary commutative K-algebras S, we can

(1) define the underlying set to be V ×S and find that these generalized quadratic forms do constitute an algebraic category,

(2) extend the Clifford algebra construction to this domain and find that there it is entirely a matter if algebraic functors and their adjoints (for this certain idempotent operations have to be introduced, as below). Certain constructions which have the form of algebraic functors composed with ad-

joints to algebraic functors may also be interpretable along the line of the foregoing remark. For example, the “natural” domain of the group ring construction might be said to be the larger category of all monoids, for there it becomes simply the adjoint of an algebraic functor. Similar in this respect is the construction of the exterior algebra of a module, whose usual universal property is not that of a single left adjoint, but does allow interpretation in terms of the composition of algebraic functors and the adjoint of an algebraic functor:

𝔸^{♭} ^{f^{♭}}^{}𝔸_{P}^{♭} ^{g_{∗}}^{}ℝ_{P}^{♭} ^{h^{♭}}^{}ℝ^{♭}

where 𝔸 is the theory of K-modules, 𝔸_{P} is the theory of modules with an idempotent Klinear operator P, ℝ is the theory of K-algebras, and ℝ_{P} is the theory of K-algebras with an idempotent K-linear unary operation P satisfying the equation

(x^{P})^{2} = 0

(f, g, h being the obvious inclusions). Thus one might claim that the natural domain of the exterior algebra functor consists really of modules with given split submodules whose elements are destined to have square zero.

The problem mentioned earlier, of computing the structure of a composition: algebraic functor followed by an adjoint of an algebraic functor, is of relevance also in the above examples, since e.g. the natural anti-automorphism of Clifford algebras is an element of the structure theory of that functor, while composing the exterior algebra functor with the forgetful functor from Lie algebras or K[x]-modules and then taking algebraic structure should yield exterior differentiation and determinant, respectively, as operations in appropriate algebraic theories.

It is obvious and well-known that the constructions of tensor algebras, symmetric algebras, universal enveloping algebras of Lie algebras, abelianization of groups, and of the group engendered by a monoid are all of the form f_{∗} for a suitable morphism f ∈ T . Perhaps less well-known is the theory 𝕄_{(−)} of monoids equipped with a unary operation “minus” satisfying

\begin{aligned}−(−x) & = & x \\ (−x) · (−y) & = & x · y \end{aligned}

and the functor 𝕄_{(−)}^{♭} ^{f_{∗}}^{}ℝ^{♭} associated to the obvious inclusion f of 𝕄_{(−)} into the theory of rings; this functor has the quaternions as one of its values, the eight quaternions {±1, ±i, ±j, ±k} forming an 𝕄_{(−)}-algebra. The quaternions also appear in another way, namely as a value of the Cayley-Dickson monad (triple) which is the composition of a certain algebraic functor with its adjoint and is defined on an appropriate algebraic category of non-associative (not even all alternative) algebras with involution.

An algebraic functor whose adjoint does not seem to have been investigated is the Wronskian, which assigns to each commutative algebra equipped with a derivation x ⇝ x′ the Lie algebra consisting of the same module with

[a, b] =^{def} a · b′ − a′ · b.

For example, is the adjunction always an embedding, giving an entirely different sort of “universal enveloping algebra” for a Lie algebra?

3. Solved problems

For the remainder of this paper we wish to discuss some problems exemplifying the canonical sort of the first methodological remark. Some semantically-defined subcategories of T admit not only simple descriptions entirely in terms of T , but also can themselves be parameterized by single algebraic subcategories. Consider the full subcategory of T determined by those 𝔸 for which U_{𝔸} has a right adjoint (as well as the usual left adjoint F_{𝔸}). These 𝔸 are easily seen to be characterized by the property that for each n = 0, 1, 2, … each 𝔸-operation A^{n} ^{}A factors uniquely through one of the projections Π_{i}^{(n)}. Such unary theories are in fact parameterized by the full and faithful left adjoint of the “unary core” functor

T ^{Un}^{}𝕄^{♭}

where 𝕄 is the theory of monoids with

𝕄(A^{n}, A) ≅ ∑_{k=0}^{∞} n^{k}

and where (𝔸)Un = 𝔸(A, A) as a monoid. Thus we may also say that a theory “is a monoid” iff it is unary. Note that if we denote the left adjoint

𝕄^{♭} ^{}T

to Un by M ⇝ \overline{M}, then we have

\overline{M_{1} × M_{2}} = \overline{M_{1}} ⊗ \overline{M_{2}}

for any two monoids M_{1}, M_{2}.

Another algebraically parameterized subcategory of T consists of all 𝔸 for which 𝔸^{♭} is abelian. We often say that such a theory “is a ring”, for it must necessarily be isomorphic to a value of the full and faithful functor

ℝ^{♭} ^{Mat}^{}T

which assigns to each ring R the category Mat_{R} whose morphisms are all the finite rectangular matrices with entries from R (i.e. the algebraic theory of R-modules). Here ℝ(A^{n}, A) ≅ Z[x_{1}, …, x_{n}] = the set of polynomials with integer coefficients in n noncommuting indeterminates. The functor Mat commutes with the Kronecker product operations defined in the two categories, and has a left adjoint given by 𝔸 ⇝ Z ⊗ 𝔸 where we now mean by Z the theory corresponding to the ring Z (i.e. the theory of abelian groups). Note that while a quotient theory of a ring is always a ring, e.g. the theory of convex sets (consisting of all stochastic matrices) is a subtheory of a ring which is not a ring.

Since 𝔸 ^{}Z ⊗ 𝔸 canonically, we have the adjoint functor

𝔸^{♭} ........^{}(Z ⊗ 𝔸)^{♭}

from the category of 𝔸-algebras to the canonically associated abelian category, and for each 𝔸-algebra X an adjunction morphism X ^{}\overline{X} if we denote by \overline{X} the associated Z ⊗ 𝔸-module. The kernel of this adjunction morphism may be denoted by [X, X], suggesting notions of solvability for algebras over any theory 𝔸, which do in fact agree with the usual notions for 𝔸 = theory of groups, theory of Lie algebras, or theory of unitless associative algebras. Sometimes [X, X] may actually be the empty set; for example, if 𝔸 is a monoid, X is a set on which the monoid acts, then X ^{}\overline{X} is the embedding of X into the free abelian group generated by X (equipped with the induced action of 𝔸).

The composition

𝕄^{♭} ^{⊂}^{}T ^{Z⊗()}^{}ℝ^{♭}

is another way of defining the monoid ring; more generally, for any theory 𝔸 and monoid M, 𝔸 ⊗ M is the theory of 𝔸-algebras which are equipped with an action of M by 𝔸endomorphisms. In fact, thinking of theories as generalized rings often suggests a natural extension of concepts or constructions ordinarily defined only for rings to arbitrary theories. For example consider fractions: the category whose objects are theory-morphisms M ^{}𝔸, M any monoid, 𝔸 any theory, admits a reflection to the subcategory in which M is a group, constructed by first ignoring 𝔸 and forming the algebraic adjoint, and then taking a pushout in T .

Part of the intrinsic characterization of those 𝔸 which are rings is of course the condition that for each n, A^{n} is the n-fold coproduct (as well as product) of A in 𝔸 (in fact this alone is characteristic of semi-rings). Another condition which some theories 𝔸 satisfy is that A^{n} is the 2^{n}-fold coproduct of A; such theories turn out to be parameterized by the algebraic category of Boolean algebras.

One of the famous solved problems of our canonical type is: Which theories 𝔸 are such that in 𝔸^{♭}, every reflexive subalgebra Y ⊆ X × X is actually a congruence relation? The answer is: those for which there exists at least one T -morphism 𝔹_{3} ^{}𝔸, where

𝔹_{3} = 𝕀_{3}/E

is the theory generated by one ternary operation θ satisfying the two equations E:

\begin{aligned}⟨x, x, z⟩θ & = & z \\ ⟨x, z, z⟩θ & = & x. \end{aligned}

For example, if 𝔸 = 𝔾, the theory of groups, one could define such a morphism by

⟨x, y, z⟩θ =^{def} x · y^{−1} · z.

Also ℝ, Mat(R) for any ring R, the theory of Lie algebras, as well as certain theories of loops or lattices, share with 𝔾 the property described.

Also by now well-known, but apparently more recently considered, is the problem: For which 𝔸 does 𝔸^{♭} have a closed (autonomous) structure with respect to the standard underlying set functor U_{𝔸}? The answer is: the commutative 𝔸, meaning those for which every operation is also a homomorphism. Since a monoid or ring is commutative as a monoid or ring iff it is commutative as a theory, one is not surprised to note that in the category of commutative theories, the coproduct is the Kronecker product.

Less classical, but more trivial, is the question: for which 𝔸 is the trivial algebra 1 a good generator for 𝔸^{♭}? The answer is: the affine 𝔸, meaning those for which

A ^{diag}^{}A^{n} ^{φ}^{}A

is the identity morphism for every n-ary 𝔸-operation φ and for every n = 0, 1, 2, …. Being “equationally defined”, the inclusion (of affine theories into all) clearly has a left adjoint, but more interesting seems to be the right adjoint which happens to exist; this assigns to any 𝔸 the subtheory Aff(𝔸) consisting of all (tuples of) those φ which do satisfy the above condition. Noting the first four letters of the word “coreflection”, we call Aff(𝔸) the affine core of 𝔸. The term “affine” was suggested by the fact that

ℝ^{♭} ^{Mat}^{}T ^{Aff}^{}T_{Aff} ^{⊂}^{}T

assigns to each ring its theory of affine modules.

4. Unsolved problems

We now list some semantically-defined subcategories C of T for which good characterizations in terms of T alone do not seem to be known. They will be presented in relativized form, so that none of them are full subcategories of T but all of them contain all the isomorphisms of T . With each such relativized problem C there is a corresponding “absolute” problem: namely to find those 𝔸 such that the morphism f from the initial theory to 𝔸 belongs to the class C. We simply list the condition that arbitrary 𝔹 ^{f}^{}𝔸 belong to C in each case:

(1) f^{♭} takes epimorphisms in 𝔸^{♭} into epimorphisms in 𝔹^{♭}. The corresponding absolute question is: for which 𝔸^{♭} are epimorphisms surjective? so that for example 𝔾 has the property while 𝕄 does not.

(2) f^{♭} has a right adjoint (as well as the usual left adjoint). Note that this second category (2) is included in the category (1) defined above, and that the corresponding absolute question was answered with “unary theories”. However, the present relative question is definitely more general than just morphisms of unary theories since every morphism between rings is included in category (2) as is the inclusion 𝕄 ^{}𝔾 (recall the “group of units”). Since the right adjoint of f^{♭} would have to be represented by f ·X_{1}, X_{1} being the free 𝔸-algebra on one generator, the question is related to the more general one of computing, for any f, the algebraic structure of the set-valued functor 𝔹 ^{}S so represented.

(3) f_{∗} is right adjoint to f^{♭}. This very strong condition obviously implies (2). We call the f satisfying (3) Frobenius morphisms since a typical example is a morphism in T of the form K ^{f}^{}R where K is a commutative ring, R is a ring, and f makes R a Frobenius K-algebra. It does not seem to be known if there are any examples in T of Frobenius morphisms which are not ring morphisms. In the context of triples in arbitrary categories, a characterization in terms of the existence of a “nonsingular associative quadratic form” can be given, but it is not clear what the abstract form of this condition means when restricted back to theories (unless they are rings).

(4) f^{♭} takes finitely generated 𝔸-algebras into finitely generated 𝔹-algebras. A thorough understanding of this category would imply the solution of the restricted Kurosh and restricted Burnside problems as special cases. In fact the restricted Burnside problem belongs to the absolute case of the question, taking 𝔸 = 𝔾_{r} = theory of groups of exponent r, and the restricted Kurosh problem to the case relative to 𝔹 = ground field, taking 𝔸 = theory of algebras satisfying a given polynomial identity.

(5) The adjunction morphism Y ^{}f · (Y f_{∗}) is monomorphic for all 𝔹-algebras Y. This category includes the f defined by the Lie bracket, but not that defined by the Jordan bracket, into the theory of associative algebras over a field. Since when applied to finitely generated free algebras, the adjunction reduces to f itself, it is clear that all f in category (5) are necessarily monomorphisms themselves. But this is not sufficient, as the morphism Z ^{f}^{}Q from the ring of integers to the ring of rationals shows (apply f_{∗} to an abelian group with torsion). Linton has suggested that the universally mono-morphic f in T may coincide with category (5).

(6) f^{♭} reflects the existence of quasi-sections; i.e. for any 𝔸-homomorphism h, if there is a 𝔹-homomorphism g with (h)f · g · (h)f = (h)f, there is an 𝔸-homomorphism \overline{g} with h·\overline{g} ·h = h. The absolute form of this condition applies to a ring 𝔸 if it is semisimple Artinian. Since simplicity, chain conditions, etc. have sense in the category T , it would be interesting if subcategory (6) could be characterized in these terms.

5. Completion problems

Finally, various completion processes on the category of theories are suggested by the adjointness of the structure functor. For example, consider the inclusion S_{fin} ^{}S of finite sets into all sets. Pulling back and composing with this functor yields an adjoint pair

(Cat, S) [figure: .; .; .; .; .; .; .; .] (Cat, S_{fin})

which, when composed with the semantics-structure adjoint pair, yields a triple (monad) on the category T . This triple assigns to each theory 𝔸 the algebraic theory \overline{𝔸} consisting of all operations naturally definable on the finite 𝔸 algebras. For example \overline{𝔾} is the (finitary part of) the theory of profinite groups.

Burnside’s general problem suggests a different, “unary” completion 𝔸̃ for a theory 𝔸, namely let 𝔸̃ be the structure of (the underlying set functor of) the category of those 𝔸algebras which are finitely generated and in which each single element x generates a finite sub-algebra F_{x}. Since this category is a union and semantics is an adjoint we have

𝔸̃ ≅ lim_{⟵}_{F} 𝔸_{F}

where F ranges over finite sets of finite cyclic A-algebras, since structure is an adjoint. Note that this completion is not functorial unless we restrict ourselves to category (4). Since every finite A-algebra satisfies the two finiteness conditions above, one obtains a morphism.

𝔸̃_𝔸

the study of which reflects one form of a generalized Burnside problem.

The functorial completion can also be done relative to a given theory 𝔹_{∘} by using finitely generated or finitely presented 𝔹_{∘}-algebras, and considering theories 𝔸 equipped with 𝔹_{∘} ^{}𝔸. For example, with B_{∘} = a field K, the completion of 𝔸 = K[x] is the full natural operational calculus \overline{K[x]} for arbitrary operators on finite-dimensional spaces; explicitly this ring consists of all functions θ assigning to every square matrix a over K another a^{θ} of the same size, such that for every suitable rectangular matrix b and square a_{1}, a_{2}

a_{1}b = ba_{2} ⇒ a_{1}^{θ}b = ba_{2}^{θ}.

If K is the field of complex numbers, one has

K[[x]]

[figure]

[figure: K[x]; E(K); \overline{K[x]}]

[figure]

K^{K}

where E(K) is the ring of entire functions and K[[x]] the ring of formal power series. (Formal power series also arise as algebraic structure, by restricting to the subcategory where the action of x is nilpotent.) The ring \overline{K[x]} would seem to have a possible role in “formal analytic geometry”; it has over formal power series the considerable advantage that substitution is always defined, so that formal endomorphisms of the formal line would be composable. This monoid is extended to \overline{𝔸}, (the dual of) a category of formal maps of formal spaces of all dimensions by applying the structure-semantical completion process over finite-dimensional K-vector spaces to the theory 𝔸 of commutative K-algebras.

References

M. Barr (1969), Composite cotriples and derived functors. In B. Eckmann, ed. Seminar on Triples and Categorical Homology Theory, Lecture Notes in Mathematicas 80, 336–356, Springer-Verlag.

M. Barr and J.M. Beck (1966), Acyclic Models and Triples. Proceedings of the 1965 La Jolla Conference on Categorical Algebra, Springer-Verlag.

J. Bénabou (1966), Structures algébriques dans les catégories. Thèse de l’Université de Paris.

S. Eilenberg and J.C. Moore (1965), Adjoint Functors and Triples. Ill. J. Math. 9, 381-389.

S. Eilenberg and Wright (1967), Automata in General Algebras. Notes distributed in conjunction with the Colloquium Lectures given at the Seventy-Second Summer Meeting of AMS.

P.J. Freyd (1966), Algebra-valued functors in general and tensor products in particular. Colloq. Math. 14, 89-106.

F.W. Lawvere (1963), Functorial Semantics of Algebraic Theories. Proc. Nat. Acad. Sci. (USA) 50, 869-872.

F.E.J. Linton (1966a), Some Aspects of Equational Categories. Proceedings of the 1965 La Jolla Conference on Categorical Algebra, Springer-Verlag.

F.E.J. Linton (1966b) Autonomous Equational Categories. J. Math. & Mechanics 15, 637-642.

University at Buffalo, Department of Mathematics 244 Mathematics Building, Buffalo, New York 14260-2900

Email: wlawvere@buffalo.edu

This article may be accessed from http://www.tac.mta.ca/tac/reprints or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/tac/reprints/articles/5/
tr5.{dvi,ps}

REPRINTS IN THEORY AND APPLICATIONS OF CATEGORIES will disseminate articles from the body of important literature in Category Theory and closely related subjects which have never been published in journal form, or which have been published in journals whose narrow circulation makes access very difficult. Publication in ‘Reprints in Theory and Applications of Categories’ will permit free and full dissemination of such documents over the Internet.

Articles appearing have been critically reviewed by the Editorial Board of Theory and Applications of Categories. Only articles of lasting significance are considered for publication.

Distribution is via the Internet tools WWW/ftp.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles 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.

Selection of reprints. After obtaining written permission from any copyright holder, any three TAC Editors may propose a work for TAC Reprints to the Managing Editor. The proposal will be reported to all Editors. The Managing Editor may either accept the proposal or require that the Editors vote on it. Before such a vote, the author, title and original publication data will be circulated to Editors. If a 2/3 majority of those TAC Editors responding within one month agrees, the work will be accepted for TAC Reprints. After a work is accepted, the author or proposer must provide to TAC either a usable TeX source or a PDF document acceptable to the Managing Editor that reproduces a typeset version. Up to five pages of corrections, commentary and forward pointers may be appended by the author. When submitting commentary, authors should read and follow the Format for submission of Theory and Applications of Categories at http://www.tac.mta.ca/tac/.

Editorial board.

Michael Barr, McGill University: barr@barrs.org, Associate Managing Editor Lawrence Breen, Université Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of Wales Bangor: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Palo Alto Research Center: paiva@parc.xerox.com Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu 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 Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca, Managing Editor Jiri Rosicky, Masaryk University: rosicky@math.muni.cz 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