FUNCTORIAL SEMANTICS OF ALGEBRAIC THEORIES AND SOME ALGEBRAIC PROBLEMS IN THE CONTEXT OF FUNCTORIAL SEMANTICS OF ALGEBRAIC THEORIES F. WILLIAM LAWVERE (cid:1)c 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 IIIAlgebraic categories 74 1 Semantics as a coadjoint functor . . . . . . . . . . . . . . . . . . . . . . . . 74 2 Characterization of algebraic categories . . . . . . . . . . . . . . . . . . . . 81 IVAlgebraic functors 90 1 The algebra engendered by a prealgebra . . . . . . . . . . . . . . . . . . . 90 2 Algebraic functors and their adjoints . . . . . . . . . . . . . . . . . . . . . 93 3 CONTENTS 4 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 6 7 The 40th anniversary of my doctoral thesis was a theme at the November 2003 Flo- rence 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 set- theoretic difficulties, was naturally met with skepticism by Professor Eilenberg when I arrived (and also by Professor MacLane when he visited Columbia). However, the con- tinuing patience of those and other professors such as Dold and Mendelsohn, and instruc- tors such as Bass, Freyd, and Gray allowed me to deepen my knowledge and love for al- gebra 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 impor- tant 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 ta- bles, for it was now he who had the obligation of reading a 120-page paper of baroque notation and writing style. (Saunders MacLane, the outside reader, gave the initial ap- proval and the defence took place in Hamilton Hall in May 1963.) The hasty prepara- tion 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 ob- scure 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 8 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 fea- tures 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 rep- resentations. (6) The leap from particular phenomenon to general concept, as in the leap from coho- mology 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 natu- rality, 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 9 2. Delays and Developments The 1963 acceptance of my Columbia University doctoral dissertation included the con- dition 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 Func- torial 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 col- laboration with [Eilenberg & Wright, 1967]. In that period of intense advance, not only Eilenberg and Wright, but also [Beck, 1967], [B´enabou, 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, alge- braic 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 cur- rent 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 the- ories have applications which are complementary, but not identical. Already in spring 1967, at Chicago, I had identified some of the sought-for links be- tween 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 sum- mary 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 discov- ery and employment since 1970 of certain decisive abstract general relations expressed in notions such as regular category, Barr exactness [Barr, 1971], and factorization sys- tems 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 re- mained 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 commuta- tivity 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 3 Comments on the chapters of the 1963 Thesis 10 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 pre- sumably by the legendary lost manuscript of Chevalley). But the relevance of reflexive co- equalizers 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 fi- nally made part of a characterization theorem by [Lair, 1996]. It is the failure of the prop- erty 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 them- selves 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 congru- ence 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 fea- tures 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 hier- archical 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 cate- gory 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 be- tween 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 mathemat- ically, 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