THE UNIVERSITY OF MI C HI GAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Communication Sciences Program Technical Report ON SOME CATEGORICAL ALGEBRA ASPECTS OF AUTOMATA THEORY: THE CATEGORICAL PROPERTIES OF TRANSITION SYSTEMS Yehoshafat Give'on ORA Projects 03105 and 07363 supported by: U. S. ARMY RESEARCH OFFICE (DURHAM) GRANT NO. DA-ARO(D)-31-124-G665 DURHAM, NORTH CAROLINA and DEPARTMENT OF THE NAVY OFFICE OF NAVAL RESEARCH CONTRACT NO. Nonr-1224(21) WASHINGTON, D.C. administered through: OFFICE OF RESEARCH ADMINISTRAT:ION ANN ARBOR February 1966

This report was also a dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in The University of Michigan, 1966.

RESEARCH PROGRESS REPORT Title: "On Some Categorical Algebra Aspects of Automata Theory: The Categorical Properties of Transition Systems," Y, Giveton, University of Michigan Technical Report 03105-43-T. Background: The Logic of Computers Group of the Communication Sciences Program of The University of Michigan is investigating the application of logic and mathematics to the design of computing automata. Applications of the techniques of category theory in the study of automata form a part of this investigation, Condensed Report Contents: The ubiquity and usefulness of homomorphisms in various studies of automata lead us to consider the following problem. What can be said on automata by referring only to homomorphisms of automata? In the report we present a study of this problem with respect to a special type of automaton, namely, with respect to transition systems. Categorical algebra methods are applied to the precise formulation of this problem and to its solution. We find that if W is a monoid belonging to a broad class of monoids, then the categorical abstract properties of transition systems with input W, are determined by the automorphisms of the monoid Wo In particular, any property of automata without output is categorical iff it does not depend on the particular labeling of the input alphabet. This study of the categorical ptoplerties' ofr.'automata has two additional outcomes. First, we realize that categorical algebra methods can be applied to automata with arbitrary input monoids, with results pertinent to the theory of monoidso On the other hand, it indicates a possible usefulness in the study of automata, in particular, in getting a better understanding of the mathematical ideas employed in automata theory, In order to support this point of view with respect to automata theory, we show that many actually studied properties of automata are categorical. And we give an example of a categorical examination and formulation of a particular study of perfect automata. For Further Information: The complete report is available in the major Navy-technical libraries and can be obtained from the Defense Documentation Center, A few copies are available for distribution by the author,

AC: NO WLELDGE.IENTS I am deeply indebted to my thesis advisor, Professor Lawrence C. Lggan of the Pacifi.c Lutheran University, Tacoma, 1iashington. I feel Ji.ept'in exp..ressing my gratitude to him for hiis guidance, encourafeentlel aind for`iis thirourgh and critical reading of the manuscript in all phases of its preparationIl, I -ant- also indelbted to Professor John I1. Ilolland for his constant support and aid during the three years that I worked with the IogFic of Conp.'u)t:ors (;' u).)., I ospecially wis'1 to thank him for adminiiistrat i 1fl ttliC. necessary formnalities without which this dissertation could not have been submllit ted, Professor liehoshua Bar-lHillel introduced me to automata theory and guided nmy early work in this field, at the Applied Logic Branchl of the IHebrew University of Jerusalem, I feel honored by his readiness to serve on my committee, and I wish to thank him for his encouragement and help.. Dr, Armand Brumer and Dr. Richard M. Karp (of IBM Research Center, Yorktown Heights, New York) helped me in two polar aspects, ID)r Brumer guided me in the work on the extension of the generality of my results to a maximally possible broad class of input monoids, while Dr, Karp guided me in the applicational aspects of my work. I wish to thank both of them for the many invaluable and fruitful discussions that I had with them concerning these two aspects of my work. I also wislh to thank Professor Saunders MlacLane of the University of Ch1icago, and I'rofessor Peter Freyd of the University of Pennsylvania v

for their encouraging interest in the categorical aspects of my work. I am deeply grateful to the staff of the Logic of Computers Group at The University of Michigan and especially to its director, Professor Arthur W0 Burks, for the privilege and pleasure of working with them. Warm thanks are extended to Mrs; Ann M, Jacobs and Mrs. Kuniko Misawa for their faithful work on the typing and duplicating of the manuscript, The research reported in this dissertation was conducted at the Logic of Computers Group and was supported by the Department of the Navy, Office of Naval Research, under contract no. Nonr-1224(21), Washington, D.C. and by the U.S. Army Research Office (Durham) under grant number DA-ARO(D)'-31-124, Durham, North Carolina. In particular, I wish to thank Dro Gordon D. Goldstein, of the Information Systems Branch of the U.S. Office of Naval Research for his generous and understanding support. vi

TABLE OF CONTENTS Page ACKNOWLEDGEIIMTIENTS a d a oa o d.. a.. o 6 It 1 V INTRODUCTION, a a a a a o a a a ~ a a a o a a o a a a a a a a 1 PART I PRELIbIINARIES OF CATEGORICAL ALGEBRA INTRODUCTION TO PART I, a, o a,a 7 CHAPTER Ia SOME BASIC NOTIONS OF CATEGORICAL ALGEBRA,.a a a 8 1 Categories d d d,d 0, o o d 6., 6 8 2a The basic morphism types o o a o o 6 a *, 11 3o Functors a d o O a a oa a o. o a o a., a a 12 4, Universal constructions in categories, a, a a 0 a 18 5S Products and sums in categories. a 6 0. d a I,, 21 6, Natural transformations and operations on functors a a 24 CIHAPTER IIo CATEGORICAL PREDICATES IN CATEGORIES a a, a. a a a 33 7d Examples of "obviously categorical" predicates..., a 34 8~ The diagramatical classes of morphisms.,,, 36 9. Automorphism invariant predicates.., a a a a a I 42 10, Degrees of categoricity of categories,a. a. 46 lla The class groups associated with categories a.. a. 49 12a Auto-trivial categories with reconstruction schemes a a 53 13. Non-deterministic reconstruction schemes for the computation of Aut(C) a. * *. * a.. a.. 4 a 64 PART II. THE CATEGORICAL PREDICATES IN CATEGORIES OF SEMIMODULES INTRODUCTION TO PART II a o 4 a. 0 a a a. a..,. a 74 CHAPTER Ia A PRELIMIINARY STUDY OF CATEGORIES OF SEMINMODULES a, 77 1i The definition of $ o d o O. a.a a a a a O 77 2, Products and sums in $W at a a a O a a a a 81 3, The basic types of the morphisms of $1 and the forgetful functor S $ $SW - $ a e a a aa 83 CHAPTER I I THE NON-DETERMINISTIC RECONSTRUJCTION SCIHEMIE FOR $W 88 4. The representation functor of $W a a, a a. a a a. 89 W w 5a The reconstruction functors r $ $ W$ O 93 6. The automorphisms of $W induced by Aut(W) 96 7, The reconstruction theorem for $ o a a a a. a a a a 101

TABLE OF CONTENTS (Concluded) W ~ Page CHAPTER III. TOWARDS THE DISTINGUISHABILITY OF MW IN $ 109 8. The monogenic semimodules.......... 0.. 112 9. The free semomodules, o. o 4 o, 116 10. The structure of the projective W-semimodules..... 118 11 The generators of $ W. 4..,..,, 126 12. The endomorphism monoids of monogenic projective W-semimodules. o.., *.,.., 130 34o On the characterization of MW as a monogenic projective generator of $S,d, 0 O. O. O..,, 4. 133 PART III, APPLICATIONS TO AUTOMATA THEORY INTRODUCTION TO PART III o.......,.,.,. 139 CHAPTER Io ACTUAL AUTOMbATA-TMHEORETIC PROPERTIES OF SEMIMODULES 0 * 142 o1 Graph theoretic properties of semimodules,...0 142 2. Monoid theoretic properties of semimodules...,.. 145 3. Analytical constructions in $ W,. 4 *.,, 147 4. Event properties of semimodules,..... *.. * 151 CHAPTER I I A CATEGORICAL ALGEBRA VERSION OF THE STUDY OF SEMIMODULES 4 4 4 4 4 4 4 4, 6. 4 0 4 i 4 4 * *o 155 5 A categorical reformulation and examination of Fleck's theory of perfect automata. oi...,. o. 4 *, 156 BIBLIOGRAPHY, 0..o a 4. 4 *. o o 4 4 0 0 V.4 a 167 INDEX. 6 O O * 0 4 o o a 0 o 4 o o * 4 a o *.... 169 viii

INTRODUCTION Homomorphisms of automata were defined almost at the beginning of the development of "algebraic" automata theory, To the best of my knowledges BIuchi [2] was the first student of automata who defined homomorpThisms of automata and, in an unpublished paper, drew attention to the importance of homomorphisms as a tool for the study of automata, Recent levelopments in automata theory show that the notion of homomorphisms of automata is, in fact, an efficient tool for solving various problems concerning structure and behavior of automata. This work is directed towards the study of the following problem which seems to be natural in this context. How much information about automata can be derived from the properties of their homomorphisms? We study this problem with respect to automata without output or designated states (i.e., with respect to transition sstens but with an arbitrary input monoid, H-omomorphisms of such transition systems can be defined in various ways, and we choose the simplest type of homomorphism which is the type that is commonly used in automata theory. Informally speaking, we discuss homomorphisms of transition systems which are defined as mappings on the sets of states of transition systems with the same input monoid, and which preserve the effect of the input on the states (i.e,, which preserve the transition functions), Thus, for any monoid W, we have the class of all transition systems with input W, and the class of homomorphisms of such systems. Our problem can be described now as follows, Given an arbitrary input monoid W, what can be said about the transition systems with input W by referring only to their homomorphisms and the algebraic nature of their composition? Before we turn to solve this problem, we have to make precise what 1

is meant by "referring only to homomorphisms and the algebraic nature of their composition",o Since a similar problem can be raised with respect to any type of mathematical system for which homomorphisms are defined, it is clear that we have to explicate the meaning of such a problem in its most general setting, The most natural framework for this explication is categorical algebra, However, in spite of the fact that one can find in the literature some references to particular phenomena which are related to our problem (eog [8; pp, 9.,281]) nobody.has examined before the general idea of properties of mathematical systems" which' are "categorical"' iee, which are definable'in terms of properties of objects in an abstract category", Our intuitions with respect to such properties of mathematical systems lead us to consider two explications for the notion of "categorical" predicateso In Part I of our work, we explain the motivation of each one of these two explications, We give a proof which shows that these two explications are equivalent0 We regard this equivalence as a justification for our intuitions and we state as a thesis that the categorical predicates in any category are precisely the predicates which are of the type defined in either one of the explications, To be specific, our thesis is that the categorical predicates in a category C are those predicates which are invariant under all the automorphism functors of Our problem concerning the homomorphisms of transition systems with input W can be stated now as follows0 What are the categorical predicates in the category of transition systems with input W, where W is an arbitrary monoid? Before we turn to the study of the categorical predicates of transition systems, we elaborate on the general notion of categorical predicate0 It is clear now that the automorphisms of a category C determine tile categorical predicates in C 0 Following some work of Freyd

3 [8; pp028-34] with relation to automorphisms of categories, and which is motivated by the intuitive idea of categorical predicates, we derive several general methods for the determination of the categorical predicates in various types of categories, We indicate the applicability of these methods to various well known categories of mathematical systems. Provided with the results established in Part I, we turn in Part II to the study of the categorical predicates of transition systems, After a preliminary study of the categories of transition systems, we establish a reduction of a characterization of all the categorical predicates in the category of transition systems with input W to the categoricity of a single class of transition systems, We find that for the transition system MW, which is W itself regarded as a transition system with W as input, i:f we can characterize it up to an isomorphism by mes.m':-f a categorical predicate, then the categorical predicates of transi, ion systems and their homomorphisms have a very simple characterization, In particular, in this case, a class of transition systems withl input W which is closed under isomorphisms is categorical iff it is closed iuder modifications of transition systems which are induced by automorphisms of the monoid W Our attention is now drawn to the problem of characterizing MW by means of a categorical predicate, We end Part II with a further study of the categories of transition systems which is directed towards the solution of this problem. We find that under very broad conditions on W the object HMW is characterized categorically as a special kind of a projective generator. In particular, if W satisfies the following if uv = 1 in W, then vu = 1

4 then Mw is characterized up to an isomorphism by means of a categorical predicate~ We note that if W belongs to either one of the following types of monoids. finite monoids, groups9 abelian monoids, free monoids or cancellative monoids9 then W has the above mentioned property, Thus, for a very broad class of monoidsD a class which includes all the types of input monoids employed in automata theory, the categorical predicates of transition systems with input monoid belonging to this class is completely characterized by the automorphisms of the input monoid, The problem whether MW is categorically characterizable for any W is still open~ We note that in order to derive this result concerning the characters ization of MeW 9 we derive several interesting properties of the category of transition systems with input W, They are interesting not only from the point of view of categorical algebra, but also because they indicate a possible application of such a study as the one presented in this work to the d.evelopment of the theory of monoidso In addition to the possible general mathematical attractiveness of these categories, we believe that an application of categorical algebra methods to studies of automata can be proven to be as useful as it has proved to be in obtaining a better understanding of many mathematical ideas, Because of this belief, we add to this work an additional part which gives indications of the relevance of our results to actual automata theory, In Part III, therefore, we review quite a variety of properties which are actually studied in automata theory, and prove that, when we restrict our attention to transition systems, they turn out to be categorical3 We end Part III, and the whole work. with a categorical reformulation and examination of a specific study of a Certain type of automata which is originated by Fleckgs [7J study of the autoemophism groups of automata,

In order to make our work self-contained, we introduce in the beginning of Part I some of the basic notions of categorical algebra~ We assume however some elementary knowledge of group theory, monoid theory, set theory and the fundamental concepts of algebra (see, for example, [3]), A certain familiarity with automata theory is helpful especially for understanding the motivation of our work and the discussions presented in Part III In general, we use the ordinary notation and conventions used in algebra. We make a frequent use of the following scheme for explicit descriptions of functions. By f: T1 >T2 * t1 4t2 we always mean that f is a function from T1 to T2 such that for all tl C T1 we have f(tl) = t2 o Furthermore, if f: T > T is a function, then T1 is the domain of f, T2 is the range of f, and the class of all elements of T2 of the form f(tl) for all tl 1 T1 is the image of f. The function f: T1- T2 is said to be injective iff f(t!) = f(t2) always implies t1 5 t2 o It is surjective iff the image of f is equal to its range, and it is bijective iff it is both injective and surjective. We will refer to functions from classes to classes as assignmets while the term function will be kept to functions from sets to setso

PART I PRELIMINARIES OF CATEGORICAL ALGEBRA 6

INTRODUCTION TO PART I Part I contains the categorical algebra material which is necessary for the fomulation and the study of the problems stated in intuitive terms in the introduction, It consists of two chapters, In Chapter I we present the basic notions of categorical algebra, For a more extensive discussion of categorical algebra the reader is referred to the literature (especially, Freyd [8] and MacLane [13])0 In Chapter II we give two explications for the notion of categorical predicates, which as we prove, turn out to be equivalente The main tool for the determination of the categorical predicates in a given category C is the class of the equivalence classes of the automorphisms of C under natual equivalence~ Since this class has a group structure, we call it the automor hism class group of C, and we denote it by Aut(C) We end this part of the work by providing a method for the computation of Aut(C) which is applicable to many well known categories of mathematical systemso 7

CIHAPTER I, SOME BASIC NOTIONS OF CATEGORICAL ALGEBRA l, Categonies The notion of category is defined in order to present a unified framework in which certain methods universally applicable to many categories can be formulated and developed in the most economical and abstract setting. In its most abstract definition, a category C is a class of morphisms in which a -binary operation, the composition of the morphisms of C is partially defined and is subject to the following axioms. Axiom Io, Associativity: (i) The composition h(gf) is defined iff (hg)f is defined; (ii) if h(gf) is defined, then h(gf) = (hg)f; we write h(gf) = hgf; (iii) hgf is defined iff both hg and gf are defined. Axiom II. Identities- A morphism i of C is said to be an identity morphism (in C ) iff if = f whenever if is defined and gi = g whenever gi is defined, We require: (iv) for each morphism f of C, there exist identity morphisms i and i` in C such that both ivf and fi are definedo In spite of the seemingly abstract remoteness of this notion of a cater gory, it is not difficult to verify the following examples of categories, The category of sets, $, is the category of the triples (f,T1,T2) 2 where T1 and T2 are any sets and f: T1 - T2 is any function from T1 and T_ e The composition rule of S is determined by the ordinary composition of function with the additional restriction that the composition is defined iff the appropriate range is identical with the appropriate domain, ioe0~ (fT1',2)(gsilS2) is defined iff S2 = T1, and then it is equal to (fgSI, T2) o Once this restriction is accepted, we write

9 f T1 -T instead of (f,TlT2) The reader is referred to the literature (MacLane [13; p,48]) for a discussion on the role of this restriction imposed on the composition rule of $ and other categories, In ordinary terms, this restriction amounts to the requirement that every morphism in any category has a unique domain and a unique range, The category of monoids, IM, is the category of all triples (-H,MI1,M2), written as HI o M1 > -2 * where 1 and M2 are arbitrary monoids and tH is a monoid homomorphism from H11 to M2 2 The composition rule of M is defined similarly to the composition rule of $, with the analogous restriction imposed on the ranges and the domains of the composed morphisms, Similarly we have the category C of groups and their homomorphisms, and the category T of topological spaces and continuous maps, In order to realize that the morphisms of a category need not be functions or related to functions, consider the following example~ Let T be a reflexive and transitive relation defined on a class P) We define a category P with morphisms (Pl1,2) whenever (P1DP2) c r. The composition (p1,p2) (qlq2) is defined iff P2 = ql, and then it is equal to ((P1,q2) ~ P thus defined is a category, Usually, a category is defined in mathematics when a certain kind of mathematical object is studied and the morphisms of the desired category are defined as maps from objects to objects, Thus, historically speaking, groups preceded group homomorphisms and linear spaces preceded linear transformations, Categorical algebra, however, is the mathematical manifestation of the point of view that, logically, functions are more basic than sets and group homomorphisms are more basic than groupso Our previous definition of categories expresses this attitude by referring to the morphisms of a category and their composition rule as primitive notions0 There is

10 another definition of categories in which the objects under study seem to play an equally important role as the maps. A category C with objects is defined as a class of objects A,B,C,0dd; together with a family of disjoint classes of morphisms, C(A,B), one for each ordered pair (A,B) of objects of C, and a family of functions C(A,B)x~(B,C)- >~(AC), one for each ordered triple (A,B,C) of objects of C o We denote the image of the ordered pair (f,g) e C(A,B)xC(B,C) under this function by gf, and call it the composition of f and g in C o Also we write f o A -B for f C C(AB), and call A the domain of f, and B the range of f Thus the" composition gf is defined iff'the"ra'nge'of f is the domain of g, We further require the following axioms: Associativity, If f: A — B, g: B -— C and h: C — D then h(gf) = (hg)f o Identities: For any object B, there exists a morphism iB o B —-B such that for any f: A >B and g: B >C we have iBf = f and giB = g o The formal difference between categories with objects and categories as defined before is obvious; categories in general do not need to have objectso From the point of view of categorical algebra this difference is only formal, It is clear that the class of all the morphisms of category C with objects satisfies the axioms specified in our first definition of a category (with morphisms only), On the other hand, the identity morphisms of any category C can be regarded as objects for C in such a way that with these objects C becomes a category with objects according to our second definition,

11 In order to do so, note that in ad (nmorphism) categtoroy C Q for any morphi.sn f there exists precisely a single identity morphism i such that if is defined, Denote this identity morphism by iR(f) Similarly, there exists precisely a single identity morphism i such that fi is defined, and denote it by iD f) f We define C(iD(f) iR(f)) 9 for each morphism f of,3 as the class of all morphisms g of C such that i giD(f) is defined in C It is easy to verify that for any category C, the class of identity morphisms of C as objects together with the classes C(iD(f) iR(f)) for all the morphisms f of C, and the given composition rule of C form a category with objects, From the point of view of categorical algebra, objects of a category are but indices of their identity morphisms9 and the main attention is thus directed towards the morphisms and their composition rule, For a given category C, we will refer to the algebraic structure determined on the class of the morphisms of C by the rule of the composition of the morphisms of C by the term the partial monoid of ~, On the other hand we will always assume that categories have objects, Set theoretic conscience sometimes imposes an additional axiom on categories; namely, that for any objects A and B a the class C(AB) must be a set, Note that the categories S M, C,, T and' all satisfy this axiom, We will not, however, require this of the cate= gories that we intend to mention or study, 2The basic morphism. types The basic morphism types are defined for an arbitrary category C according to their properties as elements in the partial monold of C Whenever one encounters an associative binary operation one is curious

12 to determine the invertible elements and the cancellable elements with respect to the given operation, For example, a morphism f: T1 >T2 of S, the category of sets, is invertible iff f is a bijection; it is left cancellable iff f is an injection, and it is right cancellable iff f is a surjection. The category C6 of groups and the category T of topological spaces are similar to S in this respect, Following the terminology of group theory, we call an invertible morphism j ~ A >B of C (i.e., such that there exists a morphism jy of C such that both jj' and j'j are identity morphisms) an isomorphism in C, and A and B are said to be isomorphic in C i A morphism j: A —-.B of C is called monic iff it is left cancellable in C (i.e, iff jfl = jf2 always implies fl = f2 ) In a dual manner e. A 4B of C is called epic iff it is right cancellable in C e Note that in I, the category of monoids, the isomorphisms have bijective underlying functions, and the monic morphisms are injectiveo In <1 every surjective morphism is epic, but not conversely, For example, the inclusion morphism of the additive monoid of natural numbers into the additive monoid (group) of integers is both monic and epic6 3. Functors Categories are introduced whenever homomorphisms are more important than objects, Thus categories being the objects studied in categorical algebra give rise to functors which are nothing but homomorphisms of categories, Before we give an explicit definition of functors, we discuss a typical example. In the category C of groups, every object C has

13 a carrier S(G), which is the set of elements of G, and every morphism f G1 G2 is determined by an underlying function S(f) * S(G1) ->S(G2) that has some properties, The common notation does not distinguish between G and S(G) and between f and S(f), The passage from groups to their carriers and from group homomorphisms to their underlying function is therefore a twofold assignment S from C to S which has the following properties: (i) for any object G of, S (G) is an object of S; (ii) for any morphism f: G1 G2 of C, S(f) o S(G1) ~S((2) is a morphism of S; (iii) S(i ) ( i ) (iv) S(gf) = S(g)S(f) Functors as assignments on morphisms are homomorphisms of partial monoids, i e they map identity morphisms on identity morphisms and preserve the composition of morphisms, For categories with objects, say C1 and C2, a functor F: C1 - C2 is a twofold assignment, one from the objects of C1 to those of C2 9 and one from the morphisms of C1 to those of C2, both of them are denoted by F and satisfy: (i) if f EC C(A B) then F(f) c C2(F(A),F(B)) (ii) F(iA) = iF(A); (iii) F(gf) = F(g)F(f) Thus, if we denote by CB the class of all functors F o'3 —C from a category IB to a category C, then with the evident definition of composition of functors B xC e r we get a category Cat whose objects are arbitrary categories and

14 whose morphisms are functors. Note that since 5~ is not a set, the category Cat of all categories does not satisfy the additional set=theoretic axiomd Again, since we are dealing with homomorphisms of a certain kind of matthematical system a classification of some types of functors is in place0 The identity assignment IC on the category C (i0e,, IC(A) = A and Ic(f * A >B) = (f o A -B),) is a functor I~ - ~,C, which is an identity morphism in Cat and called the identity functor of C Obviously every identity morphism of Cat is an identity functor, An invertible functor is called an isomorphism of categoyes, and an isomorphism F ~~ - ~C is called an automorphism of C The monic morphisms of Cat are the functors which are injective assignments, and the epic morphisms are the surjective functors, More important and useful than the notions of injective and surjective functors are the notions of "locally injective" and "locally surjective" functors6 A functor F: C1 — ~2 is said to be an embedding, or locally injective iff for any objects A and B of C the assignment PF 1 CI(A r B) ->C2(F(A) F(B)) is injective, Similarly, a functor F P C1 — G2 is said to be full, or locally sur'ective iff F restricted to C (AB) is onto C2(F(A),F(B)), It must be clear that embedding functors need not be injective nor that full functors need be surjective, The foretful functor S C- > $ which was discussed at the beginning of this section, is obviously an embedding functor which is not injective; several groups may have the samle carriert Closely related to S C —t- $ is the functor Fr S -- G defined as followso

5 For any set i wie define Fr(T) to be the free group generated by T, and for f ~ T1 >T2 a morphism of S define Fr(f). Fr(T) --— Fr(T2) to be the unique group homomorphism whose underlying function is an extension of f e The relation between S g -C S and Fr $ — is expressed by the universalit property of the free groups, For any set T denote by gT T - SFr(T) the function which identifies every element of T as a generator of Fr(T) (i,e,, the inclusion of T in the carrier of Fr(T) ) Now for any function f. T — -S(G), from T into the carrier of any arbitrary group C, G there exists a unique group homomorphism f*. Fr(T) ->G such that S(f*)gT = f An analogous pair of functors exists for the category M1 of monoidso S I M- $ is the forgetful functor of.Il which assigns to each monoid M its carrier S(M), and Fr $S - 1 is the free object functor of DI which assigns to each set T the free monoid Fr(T) generated by T 8 The free monoids also have the universality property, Note that the free object functors of CE and of VI are both iny jective0 We will return to discuss their properties and in particular their relationship to the forgetful functors in the sequel, Another example of functors is the well known "commutative diagrams" analyzed as follows, A category in which the class of all morphisms, and therefore the class of all objects, are sets is called smallO Small categories can be viewed as diagram schemes and specific diagrams in a category C with the scheme ) are specific functors from a) to C For example consider the commutative square

16 A - 4 - B h |le C - — f D of morphisms of C where ef = gh d The scheme of this square is a category Sq with four objects agb,c and d, Sq has the following morphisms in addition to the identity morphisms.; ~ a — b, e. b A.d k n: a,c, y e c >d and 6 a —- >d with 6 = e~ = yn e The particular commutative square in C is thus given by the functor F. Sq >~C with F(a) = A, F(b) - B, etc, The category Cat has an important automorphism D which maps every category C on its opposite (or dual) category Cop o The objects of are the objects of C, but the morphisms fp A ->B are in one-one correspondence with the morphisms f: B- )A of C 0 The composition fOPgOP is defined in COP iff gf is defined in C and then we set fOPgOp = (gf)OP Sometimes the opposite category of a given category C is isomorphic to C C For example Sq and SqP are isomorphic categories, but this is not the general case, Every assignment from a category C1 to a category C2 induces in a one-one manner an assignment from COP to CZ If CoP is isomorphic to C1 then every functor from C1 to C2 induces in this manner a functor from G1P to C2 0 In order to cover the case where CiP is not isomorphic to C1 we define an assignment F from C to ~2 to be a contravariant functor iff the induced 1 2

17 assignment from ~1P to C2 is a functor, For example, the obvious assignment C- >C~P is a contravariant functor induced by the identity functor of.oP o The contravariant functors are the "anti-homomorphisms" of categories, We conclude our discussion of functors with the hom-functors, These are the functors which are defined for any category C which satisfies the set-theoretic axiom by considering the sets C(AB) in the following manners5 First, every object A of C determines a functor HA C: - S with I1A(B) - C(A,B), for any object B of ~C Any morphism f a B -C of C induces a function f: HA(B) - LlA(C) defined by f (g: A-> B) = (fg A >C), and 1tA(f) is defined as f Thus IIA is the functor derived from fixing A in C(A,B) and regarding B as a variable, It is therefore often denoted by C(A,-=) If instead of B we regard A as a variable in C(A,B), we get a contravariant functor H: C -'$ with

18 HB (A) =- C(AB) and HB (g: A C) = (g* HB (C) iB i (A)) ) where g is defined by g*(f: C-> B) = (fg: A >B) Similar to IA, I"B is often denoted by C(-,B), 4. Universal constructions in categories We start with an example from group theory. Kernels of group homomorphisms are usually defined "element-wise"; the kernel of f: G!1 >G2 is the group N of all the elements g of G1 for which f(g) is the identity element of G2, However, in practice, kernels are employed in group theory because of their universality properties expressed by certain group homomorphisms, Let kf: N >G1 be the inclusion monomorphism of N in C1, where N is the kernel of f: G >G2, and let O: N — G2 be the trivial homomorphism which maps all of N on the identity element of G2 0 We clearly have the commutative triangle 0 N (C2 kf f 1 which is universal in the following sense, For any commutative triangle

19 of the form 0 G - 0G2 Cwhere 0 - G;G2 is again the trivial homomorphism, there exists a unique homomorphism G- >N which connects the two triangles into a commutative diagram G > 2 \\ C;20 h N >1 Put intuitively, every homomorphism k into G1 which is "killed" by f: G1 G2 is factored uniquely through kf o N G1 " This property follows immediately from the fact that fh = 0 implies that the image of h is included in the kernel of f, The basic idea which underlies this property, and as we will see later also the universality propety of the free objects in categories (eg,, the free groups in G and the free monoids in 1 ), is very simple~ An object T of a category C is said to be terminal in C iff for any object A of C there exists exactly one morphism A -T

20 in ~ Dually, an object J of C is initial in C iff for any object A of C there exists exactly one morphism J *A in C (i.e,, iff J is terminal in ~P )6 We show now that kernels of group homomorphisms are characterizable as terminal objects in especially constructed categories, For any group homomorphism f: G1 )-G2 we define the category IK(f) whose objects are the group homomorphisms h: G- G1 for which hf: G G2 is the trivial homomorphism8 There is a morphism in K(f) from h e G -G1 to h' ~ G' -G1 for each group homomorphism j. G 7G' for which h - h'j 8 By our previous observation we know that kf N — G1 is a terminal object in K(f) 8 On the other hand, the free groups (and in general the free objects in categories that have free objects) give rise to initial objects, Let T be a fixed set, We define the category Fr(T) whose objects are the pairs (uT,G) where G is any group and uT: T >S (G) is any function from T to the carrier of G 8 There is a morphism in IFr(T) from (uTG) to (vT,H) for each group homomorphism f: G -H for which S(f)uT = vT holds in S The universality property of the free group Fr(T) generated by T (as expressed in the previous section) means precisely that (gT,Fr(T)) is an initial object in Fr(T) In general, if T is a terminal object in C, then the only morphism T -T in C must be the identity morphism8 Hence, if T and T2 are terminal objects in C, the morphisms T1 P-T2 and T2 - T1 must be inverse to each other, and so any two terminal objects in C are isomorphic in C 8 Similarly, initial objects are isomorphic in ~ The recognition that certain constructed objects in categories are in fact terminal or initial in some constructed categories, usually

captures the significant and essential properties of the objects, 5 Products and sums in categories Usually, in categories of mathematical systems whose objects are sets with some additional structure, the products of objects are defined "element-wise" by means of cartesian products of the carriers, The notions of products and sums of objects in general categories is reduced to terminal and initial objects in constructed categories: We present here this reduction due to MlacLane [13; ppo 50-51], Let {Aj} be a family of objects of Q indexed by a set J Consider the category V{Ai} whose objects are families fj BfA of morphisms of C indexed by J with an arbitrary but common domain B Ci{A.} has a morphism from {f. B- Aj} to {f?: B' Aj} for each morphism h: B -B9 of C with f.h = fj. for all j E J A terminal object in C{Aj}, if it exists, is called a product diagam of iAj} I Thus a product diagram of {A.} consists of an object P of C, a product object of {A.}, together with a family {p P -— A. of morphisms of ~, indexed by J, such that any family {f B A. } is factored uniquely and "uniformly" through {pj P -;A. } namely f. = pjh for some unique morphism h B P of C but for all j C J 0 The product diagram, being a terminal object in C{Aj 3 is unique up to an isomorphism in C{Aj } I Since isomorphisms in C{Aj} are determined by isomorphisms in C, as it can be easily verified, it follows that the product object P of the product diagrams of {Aj} is unique up to an isomorphism in C, With an abuse of notation we identify isomorphic objects of C and we write P r /{Aj}; while the product object of a two object family {AI A2} is written as AlxA2

22 For example, in the category $ of sets, every family {Tj} of sets indexed by a set J has a product diagram {pj: {Tj} — T.} where HflTj} is the cartesian product of {Tj} and pj is the projection of HI{Tj} on T.k " Note that the definition of the product diagram {p. P -A.} of {A.} as a terminal object in ~{A.} implies not only that any family {fj B -Aj} factors through {pj P -A} via a unique morphism, ) B -P - but also that the correspondence {fj } -h determines a bijcction of sets l{C(BAj)} ->C(B,l{Aj}), where the left=hand "1" denotes the product in S; ie,, the cartesian product of sets0 For the definition of {pj: P — A.} with P = H{A.} implies that' is injective0 On the other hand, for any h E C(Bl{Aj}) 8 we obviously have 4({pjh}) a h o The dual notion of product is that of a sum (or coproduct) of the family {Aj} 0 The sum diagram of {Aj} is an initial object (if it exists) in a category of families of the form {gj. Aj.-C} H here again, the sum diagram {q.j A.j Q} is unique up to an isomorphism in the associated category, and it follows that the sum object Q is unique up to an isomorphism in C 0 We write Q - Z{Aj}, and in particular E{AIA2} a A1+A2 0 In $ every family of sets {Tj} indexed by a set J has a sum diagram {qj. Tj- -— {Tj}} where the sum object E{Tj} is the disjoint union of {Tj} and qi. Ti >{Tj} is the obvious injection of the summand T. into Z{Tj.} Again, the definition of {qj. Aj -Q} as a sum diagram of {Aj} implies a bijection of sets

23 nI{C(Aj, C) } - aC:(Z(Aj}C) Not every category yields the existence of product diagrams and sum diagrams for any family of objects, We say that C admits products (or sums, respectively) iff every set indexed family of objects of ~ has a product diagram (or sum diagram, respectively), Thus S admits both products and sums, The category C of groups and the category M of monoids admit products and sums, The product object of a family of groups or of monoids is their direct product and their sum object is their free producte Cat 9 the category of all categories also admits products and sums (even in a wider sense than the other categories)3 The evident cartesian product of categories yields a product diagram of any family of categories; their disjoint union yields a sum diagram, In particulars if C1 and ~2 are categories, then the objects of C xC2 are the ordered pairs (A1,A2) where Ai is an object of Ci o The morphisms of C XxC are of the form (f 1 f2) ~ (A1iA2);(B1 B2) 1 where f.i A.i - B. are morphisms of C.i The projections Pi ~ CxC2 - C are the functors defined by Pi(Al'A2) = Ai and P (fl f2) fi The fact that {P1DP2} is indeed a product diagram of {C1 C2} is equivalent to the fact that for any pair F. o B —-Ci of functors 1 1 with a common domain 1, there exists a unique functor G B3 - Cl1xC2 with PiG = F.; set ((x) = (F1 (x) F2(x))

24 Suppose now that every two objects in ~ have a product, So let {Pi 1 AXA2 i} and {p BlXB2- Bi} be product diagrams of 1 12 1 1 1 2 1 {A1A2} and {B1VB2} respectively, Then for any pair of morphisms fi e A.i Bi of C, there exists a unique morphism h. A xA 2-B rxB 1 1 1 1A2 12 defined by pih = fiPi By denoting h = flxf2, we find that the product of pairs of objects of C determines a functor xC > —-C, with H(AiA2) = A1xA2 and H(f19f2) = flxf2 A dual treatment for a category C in which every pair of objects {A'1A2} has a sum A1+A2 yields another functor Z o CxC >C 0 6, Natural transformations and op erations on functors We are concerned here with relationships that may exist between two functors that are defined on the same category and have values in a possibly different but common range category, Let F o C1 - C2 and G C — C be two functors from C to 2 when can we say that 1 2 1 2' F and G are essentially identical? First, in order to be able to use F and G interchangeably, we must have at least that for any object A of C1, F(A) and G(A) are isomorphic in C2 Furthermore, we would like to have some relationship which binds F(f) and G(f) for any morphism f of C1 0 This can be achieved by requiring that for any morphism f of C1 D the morphism F(f) and G(f) of C2 are similar in C in the sense that F(f) = pG(f)q for some regular 2 morphisms p and q of C2 D i em p and q are isomorphisms of C2 0 Note that this requirement implies our first requirement6 Next we would like to require that the relationships F(f) = pG(f)q will be "uniform"

25 in the sense that p and q will depend only on the range and domain of f Let us examine a specific example. The universality property of the free objects in a category, say.I, the category of monoids, yields a relationship of this kind between two families of functors from LN1 to $ PFor a fixed set T, we have the following two functorso PM(Fr(T)-) o H —-S. with MI(Fr(T),-)(M) = [q(Fr(T)9M), the set of all monoid homomorphisms from Fr(T) to M, where M is any given monoid; and S(T,-)oS: M — $ with [S(TO-)oS] (M) = [S(T,-)](S(M)) = S(TS(M)), the set of all functions from T to the carrier of M We write S(TS(-)) for (T,-)OS a The universality property of the free monoids implies directly the existence of a one-one correspondence (i,e,, an isomorphism of $ ) a(M): M(Fr(T),M)- - S (TS(M)) given explicitly by [a(H)J](f) = S(f)gT o where gT: T -SFr(T) is the inclusion of T into the carrier of Fr(T), the free monoid generated by T, We prove now in detail that for any monoid homomorphism h. Ml1 ~- M the diagram

26 a (M12) is (F ( (F(T) cm i > t ( Th s ( ('2)) is ommuaive and therefore the two functers (Fr(T) -) and $(TS(c)) are related to each other in the sense described above n Thu -echnical term for this type of relationship is natural equivalence, So let f be an arbitrary element of M(Fr(T),M1); i.e,, f: Fr(T) —- 1 is a morphism of F! from Fr(T) to 11 We chase the diagram along its left edge and get: [a(M2)] [[(Fr(T),-) ] (h) ] (f) = [a(M2)] (hf) = S(hf)gT = S(h)S(f)g; and in the other way we get: [[S(T,S(-))] (h)] [o(Il)](f) = [[$(TO-)](S(h))](S(f)gT) = S(h)S(f)gT 6 Hence the diagram is commutative and M(Fr(T),-) and S(T,S(-)) are naturally equivalent, The notion of natural transformation is a generalization of the notion of natural equivalence, We define a transformation T from' F ~ C1- C2 to G: C1 - C2 to be a family of morphisms t(A) F(A) —>G(A) of C2, one for each object A of C1' A transformation T from F to G is an equialence (of F and G ) iff for

27 any object A of C1, T(A) is an isomorphism of C2, A transformation T from F to G is said to be natural (in symbols T F -G ) iff any morphism f: A -B of C1 yields a commutative square T(A) T (A) G(A) F(f) G(f) U (B) F(B)'(B) of morphisms in C2 A natural equivalence is obviously an equivalence 2 which is natural, We realized that in Cat, the category of a]l1 categoriest the functors were regarded as morphisms of categories, Now it must be clear (and our notation reveals it) that natural transformations of functors can be regarded as morphisms of functors in suitable categories whose objects are functorse Let B and C be any categories, the functor category CB has objects all functors F B >-C and its morphisms are natural transformations of such functors T: F- G with the evident composition of transformations, If IB is a small category then CB satsifies the set-theoretic axiom on categories, An interesting amalgamation of the category Cat with the categories of the form CB is suggested in an unpublished work of J, Benabou. We give here his ideas as presented by MacLane [13; pp,4950], LEIMMA 6,1, Let A, 3 and C be categoriest FP, G A —>B and F2, CG" B-* C functors, and T: F -> and If: F9 —— * G~ be natural transformations of functors Then for any object A of a

28 we have G'C ((A))' F(A)) - T' (G(A))F'(T(A)), PROOF, By applying the commutative square of the natural transformation Tr' F -— G' to the morphism T(A) F(A) -G(A) of B, we get the desired equation, LEMMtA 6,26 With the same notation as in Lemma 6,1, the transformation T,*T from F'oF to G'oG defined by [T'*T](A) = T'(G(A))F' (T(A)) is a natural transformation T F'tF —-- G'oG PROOF. Let f: A -- B be any morphism of A, We want to prove the equality [T'*T] (B)[F'oF](f) = [C'oG](f)[T'*T]( A) Indeed. [T'*T] (B) [FoF](f) = Tt (G(B))F (T(B))F~ (F(f)) T= (G(B))Fr (T(B)F(f)) = r' (G(B))FT (G(f) (T(A)) = C((C(f))T'. C(A))F' (T(A)) [G'oG] (f) ['*T] (A) LEMMIA 603. If we add to the hypothesis of Lemma 6,1 that F", G": G- > are functors with a natural transformation

29 T" ~ F" -— G" then we have the associativity ('r".*').*T = T"*T'l* T) t PROOF, Let A be any object of A D then we have [(T"*T') *T] (A) = [ T"-r] (G(A)) [F"o F] (t(A)) = -r"([G'oG] (A))F"(T' (G(A)))F"F( (CA)) = T"([G'oGC] (A))F"(T' (C(A))F(T(A))) = T"([G'oG] (A))F"([T [*r] (A)) = [T"* (T' *T) ] (A) As a combined result of Lemmata 61,9 6~2 and 6,3 we infer: THEOREM 6.04 The collection iNat of all categories as objects and of morphisms of the form (-r,FG) ~ A -,B where FG e A —-*3 are functors and T ~ F -C is a natural transformation, is a category with the composition rule (T',F',GC )*(TFG) = (t'*T F'oF,G oG) PROOF, All we have to add to the previous lemmata is the proof of the existence of identity morphisms in Nat, We leave it for the reader to verify that for any category A, the morphism (iI _I IA) A- — A of Nat, where iI: IA ~ IA is the identity natural transformation of the identity functor IA of A, is in fact an identity morphism

30 in Nat In order to realize that Nat combines in its structure both the structure of Cat and indirectly the structures of the categories of the form CB, we observe the following properties of Nat First, we define an assignment i from Cat into Nat 0 For any category A set i(A) = A, For any functor F: A > B (i0e,, a morphism of Cat ) we define i(F) to be the morphism (iFOF,F): A,3 of Nat, where i.: F F is the identity natural transformation of PROPOSITION 6.5C i ~ Cat - Nat is an injective functor, PROOF, By its very definition, the assignment i is injective, and it maps identity morphisms of Cat on identity morphisms of Nat Let F: A- >3 and F': B — C be morphisms of Cat and let A be any object of A, then we have iF (F(A)) a F'(i5(A)) = iF,oF(A), and therefore iF'oF(A) a [iF,*iF](A). which implies i(F'oF) = i(F')*i(PF) Thus, if we identify a functor F with its image i (F) in Nat we find that the composition rule * of the morphisms of Nat yields the ordinary composition of functors when it is applied to the image of Cat in Nat c The following proposition describes the manner in which

31 the morphisms of the form i(PF) are combined with any other morphisms of Nat PROPOSITION 6,66 With the notation of Lemma 6ol, for any object A of A we have [i(F )*T'Af - FI (T (A) and [T' *i(F)](A) = T (F(A)); hence we can write i(F')*T = FOoT and T9*i(F) = T1oF 6 PROOF, For the first equation we have [i(FP)*T] (A) = [i(F)] (G(A))F' (CA)) = i (c (A))F (T(A)) = iFo(A)F (T(A)) - F'(T(A)) 0 Similarly, for the second equation we have [TV*i(F)](A) = T'(F(A))FI(iF(A)) = TO(F(A)) As an immediate but important corollary to this proposition, we find that natural equivalence of functors is a congruence relation with respect to the ordinary composition of functors, COROLLARY 6,7, With the notation of Lemma 619, if T o F (- is a natural equivalence, then Fiot ~ a: aoF e F 9G is also a natural equivalence. If T~ ~ F —-> G D is a natural

32 equivalence then T'oF: FoPF -— FtoG is also a natural equivalence, Finally, the categories of thie form C~ appear in Nat as follows0 The partial monoid of the morphisms of CB is precisely the class 1Nat(B,C) provided with the ordinary composition of natural transformations, Tedious, but straightforward, applications of the properties of Nat as expressed by the previous lemmata, yield that the composition rule * of Niat determines a functor *: FNat(A,B)xlat(B,C) — >Nat(A,C) for any categories A, IB and C,

CilAPTER I 1 CATEtORITCAL, PREDICATLES IN CATL(COP(IEMS'IThe notion of categorical nredicates of mornhisms in a given category is nckrC;t. oo& i.nttuitively as those classes of mornhisms thlat can n>e defined "categorically" or "in terms of their properties as morhilisms in an abstract cateoory" (Freyd [8; >.p28j)i. hiowver, this notion was never e>fore exlriicatedI or subjected to nathematical analysis, The procss lby means of which a cdefinition is given to a notion that has b.ete iin urse Dcfore but wiit}hout a sonecific definition is callerd ex2 licationll An cxplication of a given intuitive notion must yield a certain justification to the effect that the intuitive meaning of the given notion is well captured by the suggested definition, This justification is not a matter of proof and, therefore, it is open to informal criticism, The best well known example for an explication in modern mathematics is Turing's explication of the intuitive notion of effective computation, Churches Thesis is the declaration that Turing's explication is well justified (Kleene [11; ppo300301, 376-381]), In this part of the work we give an explication for thle notion ofc categorical predicates in categories, }:irst, we study some examples of "obviously categorical" predicates in some specific categories, This study leads us to some preliminary approximations of the notion of categorical predicates by means of an interpretation of certain expressions of some formal languages. An examination of these approximations yields the first suggestion for a definition in terms of certain diagrams; ie,, functors from an arbitrary fixed category U into the given category ~ o We call the type of the classes of morphisms of C defined by this suggestion diagramatical Next following a generally accepted intuition in general algebra, we suggest that the categorical classes of morphisms 33

34 of C be categorical iff they are closed under all the automorphisms of C W Ve call such classes auto-invariantc Now, as a justification for both suggestions) we prove that a class of morphisms in C is diagramatical iff it is auto-invariant0 Our thesis is that categorical predicates in C are precisely the auto-invariant, or equivalently, the diagramatical classes of morphisms in C e Henceforth we use only the term "cat egori cal", We conclude this chapter with a classification of categories according to the dispersion of their categorical predicates, and with a discussion of some methods for the determination of the categorical predicates in certain types of categories, In particular, we define Aut(C) to be the class group (i0e,, a class with a group structure) of the equivalence classes of the automorphisms of C under nutural equivalence, Obviously, Aut(~) determines the categorical predicates in C, We develop a method for computing Aut(C) which is applicable to many well known categories of mathematical systems, as we will show by some exampleso 7 Exam ples of'obviously categorical" predicates Consider the category N whose objects are the positive integers0 The morphisms of N are the form (m,n) ~ m >n whenever m r5 n, The composition rule of N expresses the transitivity of the relation <, ie,, (m20n2)(mlnl) is defined iff m, and then it is equal to (ml, n2) 0 As usual in categorical algebra, we identify (mm), the identity morphism of m>. with m itself, It is obvious that every morphism of N can be characterized unique. ly by means of its properties as an element in the partial monoid of

the morphisms of N First 1 is characterized as the initial object of N e Then, define a morphism (m,n) to be primitive iff it is not an identity morphism and it does not factor in a non-trivial manner as a product of two morphisms$ Thus, (men) is primitive precisely when (mn) a fg in N for some morphisms f and g of qN, iff exclusively either f or g is an identity morphism0 Clearly (m,n) is primitive iff n is the successor of m C Now 2 is characterized as the only object n of N such that (l,n) is primitive0 And, in general, m+l is characterized as the only object n of N such that (mn) is primitive, By induction, every object or identity morphism of N is uniquely characterized, Hence we can characterize uniquely every morphism (m,n) of N as the only morphism f of N such that nfm is defined in N (i0e0, (m,n) is the only morphism of N from m to n ), From this it follows that every set of morphisms of N can be characterized uniquely by means of a set of conditions, all of them expressed'categorically", This study of N leads us to consider the following elementary formal explication of categorical prediates~ We define a language ECL (i0e,, the Elementary Categorical Lan uage) as follows, ECL has a single type of individual variables denoted by x,y O O,,) A term of ECL is any non-empty finite string of individual variables0 An atomic formula of ECL is of the form t1 = t2 D where t and t2 are any terms of ECLI The comound formulae of ECL are derived from atomic formulae by means of the propositional connectives, and quantifiers over individual variables We refer to the compound formulae of ECL as the elementary categorical f~ormulae: The interpretation of the elementary categorical formulae in a given category C is evidentm Namely, we interpret individual variables as (variables of the) morphisms of C and a string of variables is inter= preted as the composition of the interpretation of the variables

36'(ioe of morphisms), An elementary categorical definition is an elementary categorical formula r, (x with a single free individual variable xc An elementary categorical formula 7r(x) is said to define the class C(Tr(x)) of morphisms of C in case f s C(r(x)) iff there eixsts an interpretation of a(x) in ~ which turns out to be a true statement when x is interpreted as f 0 Thus our first approximation for the notion of categorical predicates in C is the family of all classes of morphisms of C which are defined by elementary categorical definitions0 In other wordsD it should be intuitivel clear that in any category ~. the classes of morphisms of C which are defined by means of elementary categorical definitions are "categorical"V8 We will call such classes of morphisms of C eementarr cate ical classes in C 0 The generalization to many place predicates of morphisms of ~ definable by means of elementary categorical formulae is straightforward0 It is obvious that in any category C, the class of all elementary categorical classes is countable6 This shows that the notion of elementary categorical classes is insufficient as an explication of the notion of 0categorical" classes, For examples we have just agreed that the class of l"categoricaW'i classes in N is not countable, Employing higher order predicate calculi similar-to ECL would not help-us;as long as we use the interpretations of single finite formulae as the definitions of classes of morphisms0 8, The diagr atical classes of morphisms One may consider the possibility of employing infinite formnulae (e0go the xi.,finite formulae derived from the atomic %ror-~ulae of ECL by means of infinite appllcations of propositional connectives and quanti=

37 fiers) for the definition of classes in given categories, In facto the same intuition which leads us to believe that the elementary categorical classes are "categorical", may lead us to believe that classes defined by means of infinite formulae of the kind suggested above are also "'categorical", For example, it is easy to verify that in this fashion we can define all the "categorical" classes in N (ie,, all the sets of morphisms of N ), FurthermoreD it is possible that if we add also un= restricted higher order quantifiers over variables over classes of morphisms, we may get a sufficiently powerful explication for the desired notion of categorical predicates, The unfeasability of such an approach in this formal manner is obvious, Fortunately, categorical algebra is powerful enough to provide us with a rigorous definition of this procedure0 In this section we will discuss a categorical algebra formulation of the "general type of definition of predicates in categories by means of categorical formulae," We begin with two observations that connect the notion of formulae and their interpretations in a given category C with the notion of categories ID and functors from /) to C, Let L be any calculus in which the only non-logical predicate is a binary function, and let ~ e L —-ID denote a certain interpretation of the formulae of L in a category D e Then for any functor T o ID —--.C the obvious composition Te* is also an interpretation of L, but now in C 0 Thus the functors I) -GC transform the interpretations of L in ID into interpretations of L in ~ c On the other hand, any category D can be regarded as a formula in an appropriate calculus L and then functors from ID into C are precisely the interpretations of I) in c A canonical way of regarding D as a formula is to regard it as the0 possibly infinite, conjunction of the atomic formulae (of ECL!) of the form

38 fg = h for all f,g and h such that fg = h is true in t) 8 Thus we are going to consider the following general scheme of definition of predicates in C by means of functors, We restrict our discussion to single place predicates; ide,, to classes of morphisms in C Let f be any class of functors from categories to categories (ic,e,, a class of morphisms of Cat ), let D be any category and let X be a class of morphisms of ID 8 The class K of morphisms of C is said to be definable b X in D via' (in symbols K = <KDTOXC) ) iff K = (in CO)(X); i,e,, f belongs to K iff f = T(x) for some functor T: D- C which belongs to A, and for some x which belongs to X, Thuso under our previous interpretation, D is regarded as a formula, the elements of X, each one in its turns as free variables in ID and 5 is the class of admissible interpretations that may provide interpretations of D in C o Our main concern now is to restrict the types of the classes ~' of the "admissible interpretations" in a manner which suits our intuition with respect to "categorical" predicates, It should be clear that if we do not restrict the type of,D then every class of morphisms in C is definable by means of such a scheme, The restriction of a to "categorical" classes in Cat is not only circular but also does not serve our purpose, For examples if IJ is the class of all identity functors, which is "obviously' categorical in Cat, then every class K of morphisms is definable by K itself in C via ~o On the other hand, if ~ is not restricted to functors which are surjective whenever their range happens to be N, then the only definable classes in N via 5 are either empty or infinite0 The need for a certain kind of surjectiveness of the functors in

39 has a deeper reason than the ad-hoc consideration of the "categorical" classes in t 4 Our guiding intuition here is the following4 Given a category D and a morphism x of D, we want to consider a functor T o D )C so that T(x) will be included in the class defined by x in D o In order that this class can be regarded as "Vcategorical" in C D the functor T ID-) C, in some sense, must specify the "neighborhood" of T(x) in C according to the structure of 1D i0eo, according to the "neighborhood" of x in VD One way to make this requirement precise is to require that every true interpretation of any elementary categorical formula V(x) in D will be transformed by T U D —- C into a true interpretation of r(x) in C, where T(x) is now the interpretation of x as a variable of -r(x) 0 Hence we have to consider as "admissible" functors only those functors which preserve true interpretations of at least the elementary categorical formulae, For example, let n(x) have the form (Vy)(nr(xoy)), where rr(x,y) is an elementary categorical formula with two free variables x and y 0 If we do not know anything about C, and r(x) has a true interpretation in D): then we have to require that a functor T o D —-3 C will be surjective in order to make it possible that T will yield a true interpretation of 7r(x) = (Vy)(ir(xy)) in C For it is clear that "for all y in the ime of T in C 7(xy) represents the transformation of the interpretation of r (x) from D to C via T 0 Hence, if the image of T is all of g, that is, if T is surjective, we get a true interpretation of 7r (x) in C E The following consideration shows that we do not really need surjective functorso In order that "gfor all y in the image of T in C. iT(xcy) "v will be equivalent to "'for all y in C, ir(x~y3 "' it is sufficient to require that all the morphisms of C that occur outside

40 of the image of T in C will not be "relevant" to n7(xy) as interpreted in C via T: U —-D C 0 One way to accomplish it is to require that for any morphism g of C which occurs outside of the image of T and any morphism f of ~ which occurs inside the image of T D both fg and gf will be undefined~ Clearly, such a functor into N must be sure jective but in general T does not have to be surjective, as we will explain later0 In addition to this requirement on the image of T of C D it is natural to require that T: D — C be injective0 For injective functors T: D- — C are those functors for which I) can be regarded as a faithful description of the image of T in C. We are ready now for precise definitions. A class J of morphisms of a category C is an ideal in C iff for any morphism f of C and any morphism j in J 9 if fj is' defined in C then fj belongs to J, and if j f is defined in C then jf belongs to J 0 A class J is said to be bi-ideal in C iff both J and the complement of J in C are ideals in C, Clearly, if J is a bi-ideal in ~ D then for any j in J and any morphism f of C outside of J, both jf and fj are undefined in C o Furthermore, if T e D -C is an injective functor with the property that for any morphism g in the image of T in C and any morphism f of ~ outside of the image of T in C, both fg and gf are undefined in C, then the image of T in C is a bi-idealo By the ime of T in C we mean the class of all T(d) in C for all morphisms d in V 0 In order to see this, note that for an injective functor T e U) —— C with the above mentioned property, both the image of T and its complement in C are closed under the morphism composition in C. Now, if a partition of a category C into two classes which are closed under the morphism composition has the property that for any pair

41 of morphisms f and g, one from each component of the partition, both fg and gf are undefined, then each component is a bi-ideal in ~ We can give a graph-theoretic characterization of the biideals in C as followso First note that every ideal J in C assumes a category structure by restricting the composition rue1 of C to J Now the binary relation'If and g are connected in ~C "? defined on the morphisms of: as the reflexive, symmetric and transitive closure of the relation "'the composition fg is defined in ~ gv, is obviously the minimal equivalence relation which includes the relation" the composition fg is defined in:~ 1" Furthermore, every bi-ideal in C must be a union of equivalence classes under this connectedness and every such union is a bi-ideal in ~, In particular, we have that every category C is a sum (ie,, disjoint union) ECa of categories Ca each one of them is a minimal non=empty bi-ideal in C o The C are the connected coMnO nients of C; i,e,, the equivalence classes of C under the connectedness relation,, We define now a functor T o D- -C to be admissible iff T is an injective functor and the image of T in C is a bi-ideal0 As our first full explication of the notion of categorical (one-place) predicates we suggest the following notion, DEFINITION 8ol6 A class K of morphisms of ~ is diagramatical (in C ) iff there exists a category D and a class X of morphisms of O such that every morphism f in K is of the form f = T(x) for some admissible functor T D — C and some x in X 0 We write K = <(DX C> It is easy to verify that every set K of morphisms of N is dia= gramatical ~ K - <NDKIN>; for the only admissible functor q —- N is

42 the identity functor of N, In general, since the identity functor of any category C is admissibleD we have K c <C,K,C> for any class K of morphisms of C 0 Since every automorphism of C is admissible, the class <C~KC> is closed under all the automorphisms of C o Hence if K is not closed under all the automorphisms of ~C K $ <(,KeC> 9o Automorphism invariant predicates Experience in general algebra leads one to consider another notion as a suitable explication for the notion of categorical predicates, DEFINITION 9o10 A class K of morphisms of a category C is autoinvariant (in C ) iff for any morphism f that belongs to K 9 and any automorphism F of C, F(f) also belongs to K o The motivation for choosing the notion of autoinvariant as an explication of the notion of categorical predicates is derived from the following considerations~ In a group -G, if g e G and a is an automorphism of G D then g and a(g) are indistinguishable simply from their "algebraict properties in C On the other hand0 every one free variable formula in the (formal) theory of groups defines in G a set of elements which is closed under all the automorphisms of G o Note that any group is a category with a single identity morphism and only isomorphisms, In general0 it is obvious that all the elementary~. categorical classes in an arbitrary category C are auto-invariant in C e Furthermore, since for any automorphism F of C and any admissible functor T I-) C,~ the functor FoT - D, 11 C is also admissible, it follows that all the diagramatical classes in C are auto-invariant0 Our goal in this section is to prove the converse0 that is that every auto-invari= ant class is diagramatical1 The equivalence of these two notions can be

43 regarded as a justification for our intuitions in the persuit of an appropriate explication of the notion of categorical predicates, Furthermore, once this equivalence is established and we define categorical classes as either diagramatical classes or, equivalently, auto-invariant classes, the characterization of the categorical classes as auto=invariant will serve as an important tool for the determination of the categorical classes and even the categorical predicates in any given category, If the category C under discussion is connected, that is, if C does not contain any nonbtrivial b -ideals, then every admissible functor into &: must be surjective, Hence, in this case, the only admissible functors C- C are the automorphisms of C, Therefore, if K is an auto-invariant class in C, then K = <C,K3C>, and thus every autoinvariant class in C is diagramatical, The general case is, however, that a category C is a non-trivial sum ECa of minimal bi-ideals Ca, where a belongs to an indexing class A o Given any auto-invariant class K in C, then K = Ka where K = Kn (Cf a c A, is a decomposition of K into a disjoint union of classes Ka each one of the being a class of morphisms in Ca which is a connected category, Now, every automorphism of Ca can be extended into an automorphism of C say by making it the identity on all CE with S 0 a, Hence each K is an auto-invariant class in C D and therefore, by our previous discussion of auto-invariant classes in connected categories, K is diagramatical in C Thus, K is a (class) disjoint union of classes K, where for each a E A D K is diagramatical in the connected component C of C Say K = <D X,C C> with the requirement that if K is emptyg then both D and X are empty~

44 LEMDA 9,26 With the notation introduced above, K = <ZD ZEXa C> PROOFo Let T E -D C be an admissible functor, For any 8 E A 0 denote by T8 its restriction on D8; ioe T8 = ToJ,,where J:; D -, ED) is the canonical inclusion functor, We want to show that for all x CEXa T(x) c K 6 If the range of TB is Ca, then for all x c X we have Ta(x) c KB c_ K o If the range of T8 is C, where y $ B D then CB and Cy are isomorphic categories say by Jy C D and J)yOT OB -C is an admissible functor, The ay Y a isomorphism functor Jay can be extended into an automorphism F of C which interchange C with Ca under JB and its inverse, and leaves the rest of C fixed, Now for every x c X (J oT)(x) c K.K and therefore TB(x) = F(J a(TB(x))) E Ka c K 6 Since for any x E EX we must have x E Xa for some B e A and T(x) = T(x) * it follows that for any x s EX P T(x) c K 6 That is <EDaEX Xa0C> is included in K 6 But obviously K must be included in <ZDa,EX aC> For f E K implies f c K5 for some c A o Hence f - T (x) for some admissible functor T DV - C8 and some x E X8 o Now pick any admissible functor T - D - ~ for all y r S such that 1) is not the empty category0 Y Y Y Y then for the obvious admissible functor ET:EID - C we have a a (ETa)(x) = Ta(x) = f o In conclusion we have proved THEOREM 9636 In any category C, a class of morphisms is diagramatical iff it is auto-invariant~ Note, however, that most of the familiar categories of mathematical systems have either initial or terminal objects6 From this follows that they are connected categories6 Assume that a category C has an object

45 A such that for any object B of C D the class C(ADB) is not empty, l'e prove that C is connected, So let J be any non-empty bi-ideal in C, say f o B — C belongs to J o Now any morphism A -B must belong to J o For if not, it belongs to J. the complement of J, which is also an ideal in C H tence A -B -)C belongs to J o But f B —-C belongs to J D and therefore A —-B --- C belongs also to J 3 which is impossible, By similar arguments we derive that the identity morphism of A must belong to J, any morphism from A to any other object of C must belong to J and any morphism of C must belong to J 0 Hence every bi-ideal in C is trivial0 Dually, if a category C has an object Z such that for any object B of C, the class C(B,Z) is not empty, then C is connected, The restriction of our discussion to one-place predicates is nont essential; but some caution should be observed in generalizing our notions to relations among morphisms0 For example, the "categorical" classes in CxC should not be taken as the "categorical' binary relations in C e To illustrate this. we note that the relation "V f factors through g" defined as " f - gx for some morphism x " is "obviously"' a categorical relation in C But in general, it is not a "categorical" class in the product category Cx~ C The intuitive objection is that "categorically"' speaking, the morphisms of any category, and in our case the morphisms of CEx, are analyzed only as elements in the partial monoid, Thus in general we cannot assume the ability to decompose'categorically" any morphism of CxC as a pair of morphisms of ~ 0 Furthermore0 if we accept0 even as a necessary condition, that every "categorical" class must be auto-invariant, then we cannot accept "s f factors through g " as categorical in ExE d Simply0 the relation " f = gx for some x 9 is in general not preserved under all the automorphisms of CxC, On the other hand, for any automorphism F of C, " f = gx for some morphism x of C " is equiva

46 lent to' F(f) = F(g)x for some morphism x of C'to DEFINITION 9e46 A predicate P(x,y,,, ) is said to be auto-invariant in C iff for any automorphism F of C and any morphisms fg,,,, 0 of C, P(fg,,,, ) and P(F(f)DF(g)0ooo ) are equivalent, Put differently, the auto-invariant a-place predicates in C are the "diagonally" auto-invariant classes in Ca. The analogous generalization of the notion of diagramatical classes is immediate0 A class K of morphisms of CG is a diagramatical a-place predicate in C iff there exists a category ) and a class X of a-tuples of morphisms of U such that (fg,,0, ) belongs to K iff f = T(x), g = T(y) 9~; for some a-tuple (x,y,,eo ) in X and for some admissible functor T -o 1) >~ A similar proof to that of Theorem 9~3 yields THEOREM 905 An a-place predicate P(x,y,,,,o ) on the morphisms of C is auto-invariant iff the class of all a-tuples of morphisms of C that satisfy P(x,y,J, O) is a diagramatical a-place predicate in C Our thesis is then TIESIS 9066 An a-place predicate in a category C is categorical iff it is auto-trivial in C o 10-", Degrees of categoricity of categories In this section we want to classify certain categories according to the distributions of their categorical predicates, DEFINITION 10lOl A class of morphisms of a category C is said to be natural iff it is closed under all those automorphisms of ~ which are naturally equivalent to I~C the identity functor of C o

47 Every categorical class in ~ must be natural since it is closed under all the automorphisms of C e Note also that every isomorphism type in C (ie,, a class of identity morphisms of all the objects of C which are isomorphic in ~ to some arbitrary fixed object in C ) and every txpical class in C (i,e,, a union of isomorphism types in C ) are natural in C The later examples of natural classes are important because typical classes in C represent abstract algebraic properties of objects in C and, in particular, the isomorphism type of any given object in C represents the abstract algebraic structure of the object as an object of C o For example, in the category of groups C, the typical classes are the abstract algebraic properties of groups, and the isomorphism type of any given group G is the algebraic structure of G as a group' We distinguish therefore between three types of categories~ DEFINITION 102o A category C is said to be(i) objective iff every isomorphism type in C is categorical; (ii) transparent iff every natural class in C is categorical; (iii) auto-trivial iff all the automorphisms of C are naturally equivalent to IC. Every autotrivial category is transparent and every transparent category is objective~ It is fairly easy to construct a category C with three objects AB and C such that B and C are isomorphic in C and the only non-identity automorphism of C leaves A fixed and interchanges B and C, and yet it is not naturally equivalent to IC 0 That is, the isomorphism B —-C is not natural0 Hence the natural classes in C are any classes of morphisms of C, and therefore not every natural class is categorical in C In particular the class which consists of

48 the identity morphism of A only is natural but not auto=invariantd Hence C is an objective category which is not transparent~ Note that this example also shows that natural classes of identity morphisms need not be typical. While all the familiar categories which are known to be transparent are, in fact, auto-trivial as well, I do not know of a proof to the effect that every transparent category is autotrivial, nor do I know of any example of a transparent category which is not auto-trivial, If we consider groups as categories, then the automorphism functors of groups are precisely the ordinary automorphisms of groups, and thc automorphism functors of a group G which are naturally equivalent to the identity functor of G are precisely the inner automorphisms of G o Hence a group is transparent iff all its automorphisms preserve conjugatioi.z classes, and a group is auto-trivial iff all its automorphisms are inner automorphisms0 This suggests the following open problem in group theory, Is there a group with only class-preserving automorphisms which have any automorphism which is not inner? In order to understand the nature of this problem, we have to understand the difference between objective, transparent and auto-triviai categories~ The objective categories are those categories in which objects (i0e,, identity morphisms) can be characterized up to an isomorphism by means of a one-place categorical predicate~ Both transparent and auto= trivial categories are categories in which any morphism can be characterized up to a "natural equivalence" by means of a one-place categorical predicate, From this point of view, there is no difference between trans= parent and auto-trivial categories~ In a transparent category C, if f is any morphism and F is any automorphism of ~ D then there exists an f automorphisnm F of C, naturally equivalent to IC, such that F(f) = Ff(f) 0 This is so because the minimal natural class in C which

49 contains f must be auto-invariant, Note the logical structure of the previous statement 11for all F, for all f. there exists Ff o0 such that F (f) = F(f) O Thus it may be the case that for f f g we would have Ff Z F}g If C is an auto-trivial category, then trivially the existential quantifier vthere exists an automorphism Ff naturally equivalent to I~ Ad can be put before the universal quantifier "for all f.. d since we take F = F i_.- The class group s associateod with catees In general a category need not be either auto-trivial or transparent or objective~ In order to determine the deviation of a given category C from being of either one of these types of categories, three class groups associated with C are defined, A class grou is a class which has a group structure, For example for any category C, the class of all automorphisms of C has a group structure with respect to the composition of functors0 even if the carrier of this group may be not a set, The idea of employing class groups in this context is borrowed, with a certain modification, from Freyd's notion of the automorphism class group [8; p,28]o Namely, we define certain equivalence classes in the total class group of the automorphisms of C and show that they are congruenceso Hence, these relations induce quotient class groups0 The choice of the equivalence relations is almost determined by our goal0 We start with the deviation of a category from being objective, A category C is objective iff for any two functors F1 and F2 and object A of C D there exists an isomorphism F1(A) - F2(A), for the identity functor is one of the automorphisms of C According to our termrinology of transformations of functors (cfo Ch0 i, Section 6), a category C is objective iff for any pair of automorphisms F1 and F2,

50 there exists an equivalence from F1 to F2 0 It is natural therefore to inquire about the effect of this equivalence relation (i,e,, F1 and F2 are geuivalent iff there exists an equivalence from F1 to F2 ) on the total class group of the automorphisms of any category C, If F1 and F2 are equivalent, then for any functor F P - >~, FlOF and F2oF are equivalent, If in addition F preserves isomorphisms in C, and an automorphism has this property, then it follows that FoF1 and FoF2 are also equivalent Hence equivalence among the automorphisms of C is a congruence relation, We denote by Ob(C) the quotient class group of the total class group of the automorphisms of C under equiva. lence, We clearly have that Ob(~) is trivial iff C is objective~ If, however C is not objective, then Ob(C) determines the categorical typical classes in C as follows, Let K be a typical class in C and let Fi be any automorphism of C if F1 preserves K and F2 is equivalent to F1 then F2 also preserves K o Hence we have THEOREM ldle For any category C, let Sob be a choice class of Ob(C), (ioe,, a maximal class of automorphisms of C which are mutually not equivalent), Then a typical class K in C is categorical iff it is closed under all the automorphisms in 5ob0 From the properties of Nat (cf. Chd I, Section 6) it follows that natural equivalence of functors determines also a congruence relation in the total class group of all the automorphisms of C a We denote by Aut(C) the quotient class group determined by natural equivalence of automorphisms Aut(C) is trivial iff C is auto-trivial, Furthermore, since natural equivalence of functors is a particular case of equivalence of functors, the congruence determined by natural equivalence is a refinement of the congruence determined by equivalence0 Hence we have a canonical

(cl ass) epimorphism N ~ Aut(C) --- Ob() 0 The kernel of this epimorphism is the quotient class of all natural equivalence classes of automorphisms of L which are equivalent to IC under natural equivalence, Hence N is an isomorphism iff every automorphism of C which is equivalent to IC is naturally equivalent to IC, Put differently, N is an isomorphism iff for any automorphism F of C which is not naturally equivalent to ic, there exists an object A of C which is not isomorphic to F(A) in C Similar to Thorem 1141, we have THlEOREMI 11 20 For any category C D if aut is a choice class of aut Aut.C) H then a natural class of K of morphisms of C is categorical iff it is Closed under all the automorphisms in e aut Note that the condition specified in Theorem 1102 (unlike Theorem 11:1) is not the most economicale For example, if C is transparent and not autostriviaiL then Aut(C) is not trivial and yet all the natural classes in C are by assumption categorical, The third congruence relation is introduced in order to derive the mosts economical condition for natural classes to be categorical We say that the automorphisms P1 and F2 of C are naturally related iff for any morphism f of C there exists f an automorphism Pf of C p naturally equivalent to IE 9 such that F(Fi(f)) = F2(f) e Thus, F1 and F2 are naturally related iff they preserve the same natural classes in C, If F1 and F2 are naturally equivalent, then they are naturally related; take F F2 F1 On the other hands if F and F are naturally related, then they are equivalent, since Ff(A) is isomorphic to A whenever Ff is naturally

equivalent to I I., Hence natural relatedness is an intermediate relation between natural equivalence and equivalence of functors. We prove now that natural relatedness is a congruence relation among the automorpllisms of,. Assuming that F1 and F2 are naturally related, then for any morphism f of C there exists an automorphism F, naturally equivalent to IC 2 with F f(Fl(f)) = F2(f), Hence for any morphism f and any autolnorphism C of, we have F(f)(Fl(G(f))) = F (C(f)); which shows that Tl:1oG anG F2oG are also naturally related, We also have [GoFfO -1](C(l(f))) = G(F2(f)). But since F is naturally equivalent to IC, it follows from the fact that natural equivalence is a congruence, that CGOFoG is naturally equivalent to IC, Hence 1Go and GoT2 are also naturally related. We denote by Tran(C) the quotient class group of the total class group of all the automorphisms of C under natural relatedness. We know by now that the enimorphismr N o Aut(C) -> Ob(C) factors through Tran(C), Furthermore, by the rtrii. of natural relatedness, namely that two automorphisms are naturally related iff they preserve the same natural classes, it follows that E is transparent iff Tran(C) is trivial. By the same argument we derive the following theorem. TIIEOlRED1 11, 3 For any category C, if t is a choice class of tr Tran(t), then a natural class K of morphisms of C is categorical iff it is closed under all the automorphisms in t ~ tr Denote by T: Aut (C) -- Tran (C) the canonical epimorphism from Aut (~) onto Tran(C) 0 The kernel of T is precisely the quotient class of all automorphisms of C; which are

53 naturally related to IC under natural equivalence Hence T is an isomorphism iff for any automorphism F2 of C which is not naturally equivalent to Ic,there exists a morphism f of C such that for all the automorphisms F1 of C which are naturally equivalent to IC, we have F1(f) P F2(f) It turns out that among the three class groups Ob(C), Tran(C) and Aut(C) tlhe largest one (i.e,, Aut(C)) is the easiest to compute, This is fortunate since, after computing Aut(C) 0 one would hope to be able to determine the other groups by examining Aut(C) and by providing the epimorphisms T and N a In the rest of the chapter we discuss a sufficient condition for a category to be auto-trivial, and then generalize it so that we get a procedure by means of which the class group Aut(C) can be computed for a broad class of categories, The class of categories which is covered by the applications of these procedures contains among many other categories the following categories-e the category Cat of all categories, the category of small categories, the category of finite categories, the category of partially ordered sets, the category of sets, the category of monoids, the category of abelian monoids, the category of groups, the category of abelian groups, and categories of moduleso 12o Auto-trivial categories with reconstruction schemes We start with an example adapted from Freyd [8; ppo30-31] concerning \ut (Ca ), where Cab is the category of abelian groups, Broadly speaking, we consider the set ab(ZZG) of the group homomorphisms from Z, the group of integers, to an arbitrary abelian group C e By means of ab point-wise addition we define a binary operation + on G (Z,G) which ab turns G (ZCG) into an abelian group R(G) which is isomorphic to G 0 Since, as it turns out to be, the construction R(G) is "categorical on

54 Gabt, it follows that every isomorphism type in Cab is categorical, and therefore Cab is at least objective, A further examination of the nature of the construction G —— R(G) reveals that ab is auto-trivial, ab To be more specific, consider the forgetful functor S C G- $ with S(G) being the carrier of G, and the functor HfZ ab >S with Hz(G) = ab(ZG) e The family of functions p(G): S(G),Hz(G). g hg * where h: Z IG is the unique homomorphism with h (+1) = g, is an equivalence from S to HZ o For clearly h = h implies gl' g2 g1 g2 (evaluate both h and h at +1 ), and for any f Z - we!-have hf(+l) f For any abeian group IH and any morphism hl h2 ~ Z -Ii t we denote by (hlh2): Z+Z ~11 the unique morphism guaranteed by the sum diagram of Z+Z and by hlDh2 Z -- H o Note that the sum in Cab amounts to the direct product of abelian groupsd (In an element-wise manner, the homomorphism (hlh2): Z+Z OH is given by (hlh2)(mn) = hl(m)+h2(n) o) From the properties of the sum diagram in Cab it follows that for any more phisms f I I 12 and hlh2: Z -H1 we have f(h1,h2) = (fh1,fh2) (The elementswise verification of this equality is trivial,) Let 6 ~ Z -Z+Z be the unique morphism for which both (O0i)6 and (i0O)6 are the identity morphism i of Z, where O o Z -Z is the trivial morphismo (The categorical definition of 0 e Z — Z is

the mlorphism Z->Z which factors through a terminal object of Cab ) Note that the element-swise description of 6: Z — > Z+Z is 6(m) = (m,m) 6 Now we can define the point-wise addition in ab(z,G) as follows. For any h,h: Z -— G, the morphism h +h: Z- -G is defined by 1 2 g1 g2 h +h = (h h ) 6 g1 g2 g1 g2 Hience h +h is described, element-wisely, by gi g2 [h' +h ](m) = h (m)+h (m) gl., 2 g 2 and therefore we have h +h = h 1 g2 g1+g2 dab This proves simultaneously that with this additon, C (Z,G) enjoys an abelian group structure, that we will denote by R(G), and that the bijection p(G): S(G) -G, b (ZG) determines an isomorphism of C with R(cG), Thus, we have a procedure by means of which we can reconstruct an isomorphic copy of any abelian group, Furthermore, once Z is given, ab the rest of the procedure depends only on the abstract structure of Cab The precise meaning of this last statement is that for any automorphism F of C for which F(Z) is isomorphic to Z, R(F(G)) is isomorphic to R(G), and therefore to G, for any given object G of ab We ab T', (Z~i JW prove now that for any automorphism F of Cab, F(Z) is is'c.'orphic to Z; that is, the isomorphism type of Z is categorical in ai D LEMIA 1210. An object X of gab is isomorphic to Z in a iff ab ab (i) for any object A of C, if A is not tel:inal in G ab then C, (X,A) has more than one elements. and

56 2 (ii) if e: X X is an idempotent morphism (io,e,, e = e ) then either e is the identity morphism of X or e factors through a terminal object of Cab (which is the trivial group)~ PROOF. Obviously any isomorphic copy of Z in ab satisfies these two conditions, On the other hand, assume that X is an abelian group with non-trivial homomorphisms into non-trivial groups and such that every idempotent endomorphism of X is a trivial idempotento Now, since Z is not a trivial group, there exists a non-trivial homomorphism h' X >Z o But this is possible iff there exists an epimorphism e e X - Z o Now, if e, X Z is onto, then there exists a homomorphism f Z — X such that ef is the identity morphism of Z o For assume e(x) = +1 for an element x of X: then define f: Z -*X by f(m) = mx o Clearly, fe is an idempotent of X which is not a trivial homomorphism (ie,, fe(y) is not 0 for all y ), hence it must be the identity morphism of X e Thus e: X )Z is an isomorphism. We can conclude now and infer that Cab is objective. An intuitive way to describe this is the following. For any abstract property P of abelian groups, if one wants to determine "categorically" whether a given abelian group G satisfies P, then one has to construct R(G), and G satisfies P iff R(G) satisfies P 0 The rigorous proof that Cab is objective is outlined as follows. Let [G] be the isomorphism type of G ab ab in ab and let F be an arbitrary automorphism of Cab The nature of the construction G — R(G) implies that R(F(;)) is isomorphic to R(G) ab hence G is isomorphic to F(G) o Thus every isomorphism type in ab is categorical and from this follows that C is objective0 We will reexamine the definition of R(G) and show that it yields ab a proof that C is auto-trivial, First, we extend the assignment

57 G —- R(G) into a functor R 6 -ab ab We note that for any morphism ab f G G G2 of Gab, the function IIZ(f) Cab(ZG1) —>~ab(Z,) ~ h Ofh determines a homomorphism R(G1) -R(G2) of abelian groups: [LI4z(f)] (h hg h) [}IZ(f)] ((hg shg )6) = f(h,h )6 gl g2 (fh,fh )d g1 g2 =[Ilz (f)](h 1)+[ Hz(f)](h )9 ab Thus we define R(f) o R(G1) - R(C2) to be the morphism of C which ab ab is determined by HlZ(f) o In this manner we have a functor R: ab ab which satisfies SoR = Hz = ab(z,-) 0 LEMMA 12,2, The functor R. gab; gab is naturally equivalent to ab, the identity functor of Cab In particular, p IGab -R is given by p o S —--; that is, for any abelian group G, the isomorphism p (G) G- -R(G) is the isomorphism determined by p(G) S(G) - ab (Z,G) PROOF, We have shown above that p(G) determines an isomorphism p* (G) G —-,R(G) o We prove now that p S — HZ is a natural equivalence, and this implies that p s I'ab — R is a natural equivalence, So let f G1 > G2 be an arbitrary morphism of Cab, then we have to show that the diagram P*(G1) G1 > R(G1) p*(G2) C'2 > R(C2)

58 is commutative, That is, we have to show that the underlying diagram p (G) ab 5(CG1) >C (Z,G1) fZ (f) P(G2) ab S(G 2) > G (Z,G2) (where here f denotes the underlying function of f: G1 >G2 ) is commutativeo So let g ~ S(G1), and we have [p(G2)](f(g)) = hf(g), and [IIZ(f)][p(Gl)](g) = fh o By evaluating both h and fh at +1 we get h = fh d Hence f(g) g f(g) g P q-ab R is natural equivalence. Now we make precise and detailed the meaning of the "categoricity" of ab ab the construction R: Ca -X c 6 In this particular context, it is sufficient to show that for any automorphism F of G, R and RoF are naturally equivalent. If this is the case, then it follows from Lemma 12o2 that every automorphism F of Gab is naturally equivalent to the identity functor of ab Hence Cab is auto-trivial. Here we give only some hints for the construction of the natural equivalence R > RoF ab ab We define an intermediate functor R: C - a described informally F(Z) as following the construction G — R(G) but instead of Z we take F(Z) o The automorphism F itself determines a natural equivalence oF ~ R —RF(z)OF o The transformation oF is given by the obvious isomorphism R(G) }RFrvz(F(G)) which is determined by

59 F. Eab(ZG) >Eab(F(Z)>F(C)) o The isomorphism F(Z) —Z, whose existence is guaranteed by Lemma 12.1 and its implications, determines a natural equivalence RF(Z) R e Hence we have a natural equivalence RF()OF -RoF, Now by combining the natural equivalences R;RF(z)OF and RF(Z)F F —-ROF, we get the desired natural equivalence R -RoF 6 These discussions lead us to the first condition for auto-trivial categories~ We say that a functor R from a category C (into an arbitrary category) is cate orical on C iff for any automorphism F of C j R and RoF are naturally equivalent, PROPOSITION 12630 A category C is auto-trivial iff there exists a functor R C ->C which is categorical on C and naturally equivalent to IC o PROOF, If C is auto-trivial, then IC is categorical on C and, of course, naturally equivalent to itself, If R. C — C is naturally equivalent to IC and categorical on C, then we have for any automorphism F of C, the natural equivalences IC -C R;, R > RoF and RoF -F Ilence C is auto-trivial, The role that Z plays in the functor R ab ab is emphasized in the following discussion of R 6 First we realize that any group C ab ab ab determines a functor R Ca -C i with SR CRG (GD -) i e6, S(RG(H)) = Gab (GI) for any abelian group H The functor Rg is specified as follows6 For any abelian group H, the group RG(H) is the abelian group with C (G,-I) as its carrier and the addition in RG(}I) is the point-wise addition, The "categorical" definition of the addition in RG({) is given as follows6 The diagonal morphism 6G ~: G ->G+G is defined in an analogous manner to 6 o Z —>Z+Z o For any two morphisms hlph2 ~ G —- H we define hl+ho o C- -H by

60 hl+h2 m (hl'h2)6G' where (hlh2): C+G- H is the unique morphism determined by the sum diagram of G+G and by the morphisms hl,h2: G —-H. Again, since for any morphisms hlh2: G -H1 and h: H1 -H2 we have h(hlh2) = (hhl,hh2), the function Gab (,H1) _ cab(GH2): hl- hh determined by h: H-1 - H2, determines a morphism RG(h): RG (I1)- RG ({ 2) and R IGab Cab is a functor. Now the assignment G — R is an assignment from the objects of ab to(ab ab Ca to the objects of Nat, ), the category with functors cab ab ab Cab as objects and natural transformations as morphisms. It is not difficult to see that this assignment can be extended into r contravariant fuInctor R' Cab ->Nat(Cab Ca )a where for any morphism f G 1 —-C2 of C, RP(f) is the natural t rans format ion R* (f) RG2 >R 2 1 given by [R (f)] (H): R ( (H) 1 RG12 2 R (f) is natural just because of the associativity of the morphism composition in Cab, Note that since the isomorphisms in Nat(Cab,a)

61 are natural equivalences, R, (j) is a natural equivalence for any isomorphism j of Gab ab It is intuitively clear that for each object G of ab, the functor R is defined "'categorically from G ", This intuition expresses the following fact0 For any automorphism F of Cab the restriction of F on C ab(GH). i0e,, the function Cab (C) - ab (F(G), F(tF)) o h —-h F(h) determines an isomorphism aF(H) o R;(H) RFG) ( of - ab LEMAB 122,4 The equivalence aF is a natural equivalence ( CF' RG-R F L for any automorphism F of Cab PROOFo Let f ~ 1! H2 and h o GC -11 be any morphisms of ab G; then we have [aF(H2)] [RG(f)] (h) = [aF(H2)] (fh) = F(fh) F(f) F (h): [RF(G) (F(f)) ] (F(h)) [RF(G) (F(f))] [OF(Hll)] (h) o We are familiar now with the type of argument which yields the proof

62 of the following lemma. LEMMA 12.5. If for some abelian group G, RG is naturally equivalent to IGab, then every automorphism F of C for which F(G) is isomorphic to G is naturally equivalent to I'ab. Since we know by now that RZ is naturally equivalent to I'ab and that the isomorphism type of Z is categorical in C, we have the following expected result, COROLLARY 12o5, The category of abelian groups is auto-trivial. Note that due to the functor R, the categoricity of a single isom6rphism type (i.e., that of Z ) is sufficient not only for the categori. city of every isomorphism type, typical class or natural class in Cab ab but also for the autotriviality of ab The general case is now obvious, DEFINITION 12.6, A Hom-reconstruction scheme for a category C is a contravariant functor R*: C Nat(CC) together with a functor S: ~ - S such that (i) for any object A of ~C SoR *(A) = O(A,-), and (ii) for any object A of C and any automorphism F of C there exists a natural equivalence sc: R* (A) F —> R* FA)) o such that SooF ~ C(A,=) -— C(F(A),F(-)) given by [SooF](f) = F(f) is

63 a natural equivalence, More generally, a general reconstruction scheme for C is any (contravariant or covariant) functor R: C -Nat(~,C) such that for any object A of C and any automorphism F of C, there exists a natural equivalence oF: R*(A) ---- R (F(A))oF ab The role of Z in the reconstruction scheme for ab discussed above, motivates us to give the following definition, DEFINITION 1267, Let C be a category with a general reconstruction scheme R An object M of C is called an R -generator iff R (I) is naturally equivalent to IC e By the usual chain of natural equivalences we derive the following theorem, THEOREM 128,a Let ~ be a category with a general reconstruction scheme R. D and let M be an R =generator in C 0 Then C is autotrivial iff C is transparent; in particular, C is auto-trivial iff the isomorphism type of H in C is categorical~ Most of the familiar auto-trivial categories have an R *generator for some Hom-reconstruction sheme R d For example, the category Mab of abelian monoids has a HIom-reconstruction scheme R in a complete ab analogy with the Liom-reconstruction scheme for G The infinite monogenic monoid is the only R -generator in ab for this reconstruction scheme, and it is distinguished in M by the same properties as Z is

64 ab ab is auto-trivial, distinguished in C (cf0 Lemma 121) o Hence ab is auto-trivial: Freyd shows [8; ppo29, 32-33] that the category of sets $, the category of topological spaces, the category of T1 spaces and the category of Hausdorf spaces all have Hlom-reconstruction shcemes with generators, and therefore, as he points out, they are all auto-trivial, The category S of sets deserves special attention because it leads us to consider another but immediate sufficient condition for auto-trivial categories~ We say that a functor R from a category C (to some arbitrary category) reflects natural equivalences on Aut(C) iff for any two automorphisms F1 and F2 of C, if R~F1 is naturally equivalent to RoF2, then F1 and F2 are naturally equivalent~ It is easily verified that a category C with a functor R from C, which reflects natural equivalences on Aut(~), is auto-trivial iff R is categorical on C o In the example of the category S of sets, the functor S(U,-) $ —- $, where U is any singleton set, is categorical on S, naturally equivalent to Is and it reflects natural equivalences on Aut($) o Hence S is auto-trivial, 13, Non-deterministic reconstruction schemes for the computation of Aut() Freyd [8; pp,29=30, 31-32] shows that some categories (namely Tat, the category of all categories and some of its subcategories, and C, the category of all groups) have reconstruction. schemes similar to Hiomreconstrcution schemes as defined in the previous section0 However, for these categories the reconstruction schemes do not yield objects in the given category in a unique manner, These examples lead us to consider "non deterministi c" schemes, and we will show how such schemes lead to the computation of the class groups Aut(C) for many familiar categories C We start with an illustration based on Freyd's discussion of

65 the category of small categories ([8]; pp,29)30)o We will however apply it to Cat, the category of all categories, Let [H-] be the category with two objects and precisely three morphismso Then for any category C, the morphisms are in one-one correspondence with the functors (ioe,, morphisms of Cat ) from [ —— >] to C. Our problem is to find a suitable definition for a binary operation on the morphisms Cat ([ —-3], ) which will make'thle operation correspond to the composition rule of C o Now, the category C'at has a'n automorphism which is not even equivalent to I the identity fznctor of Cat. Letting 1) C 0]at >Cat be the "opposition" functor that maps every category C on its dual C op then D is an automorphism of Cat which is not equivalent to I Wo e have to show that there exist categories C such that C and C~P are not isomorphic in Cat, For example, every category ~ with initial objects but without terminal objects is not isomorphic to CoP 0 For under isomorphism of categories initial objects are mapped on initial objects, and CTop has terminal objects onlyo The category N, discussed in Section 7, is obviously such a categoryo IHence we must infer that we cannot reconstruct the composition rule of each category C in a unique manner from the class Cat ( [ —- ], C ) a We hope to be able to reconstruct C up to an "oppos t ition" Freyd suggests the following procedure for a reconstruction of C up to an v'opposition"' from the class Cat ([ ->j, C )o Let I and R be the objects of [ —i] and L —>R be the single non-identity morphism of [ —-+] The sum category [ —-] + [ —] in Cat is the disjoint union of [ —-> with itself, That is, it has four objects 1, P.1 " 12 and R2, four identity morphisms and two nonIidentity morphisms L1-..l! and L2 —- R'?2 Let [ —--— ] be the category with three objects L M I anld R, their identity morphisms, a single morphism L- ~-.

66 a single morphism M — R and their unique composition L -R in I[ A>.], There are several functors from [ —-]+[ —->] to [- > >] but only two of them are epic in Cat (ioe., surjective)o Namely, we have an epic functor l: (['+[-[' —q),>[ f >], which maps L1 >R1 on L >M and L2 -R2 on M -R, and an epic functor ~2: ([- ->]+[ i]) — [ > >], which maps L - R1 on M 1>R and L 2 R2 on L -R. Since the difference between,l and w2 is a result of the opposition functor D Cat -— >Cat, we cannot distinguish between =l and r2 in Cat o Let a- [ --- [ — > — >] be the functor which maps L —-R of [ —-] on i -— > R of [ -> —-] Each one of the functors'l * x2 * yields a reconstruction of C as followso Let rr be any epic functor from [ >]+[ —-] to [ —- ->], and let xy [-. —j] —+e any two functors, The functor Tr(xy) [- _ --—.C is defined as the functor z: [-] —- >C for which there exists a functor l... —-- >].-> such that [ —>1 [ A] ([ —q + --— A] ) X commutes, TlEe functor (x,y): ([- >]+[ —— ]) -— C is the obvious functor determined by the sum diagram of [ —— >]+[ —-] in Cat and the functors xy o [ —---— ].., In this manner, the class Cat ([ —>], C ) with

67 the composition rule (xy) IT (xY) becomes a category say, R (C) 0 It is clear that R (C) is isomorphic to C and R (C) is isomorphic to the dual of C 0 =2 In order to verify that this construction (i.e., the predicate "z = lKxy) or z a r2(x,y) ") is categorical in Cat, we leave for the reader the verification of the following statements, (i) The empty category is the initial object of Cat d (ii) The category 1 with a unique morphism is isomorphic to any category LB which is not empty and for which Cat(B,1) contains a unique morphism0 (iii) The category [ —— ] is isomorphic to any category B such that ~Cat(i3,B) has two: elements and CatCB,1B) has three elements, (i'v) The category [ - > >] is isomorphic to any category B3 such that Cat(l1B) has three elements, ~at([-, B) has six elements and thre exists an epic morphism ([- ] -+-[ —]-) —-, B h Cat mi: (v) The functor a: [. >] >[- >.-] is the only functor from [ —] to [ > —] which does not factor through any epic functor ( [ —A]+ [... q) >[...A. From what we have said so far it follows that the typical classes in Cat are categorical iff they are closed under duality, That is, Ob(Cat) is the cyclic group of order two. However, a further exmination of Freyd's construction implies that Aut(Cat) is also the cyclic group of order two, and that any natural class in Cat is categorical iff it is closed under the "opposition" functor D: Cat -Cat d We proceed as follows, BI3ased on the properties of [ —->], we defined above two assignments R and R on the objects of Cat. It is evident, =1 =2

68 that these assignments can be extended into two functors R C Cat —->Cat and R: Cat C-at o I1 T2 This follows from the fact that the assignment [Cat([ —->],-)] (T): Cat ([ —— ],Q 1) — Cat('[ —— ],C2) determines a functor R (T) R (Cl) R(C2) for any functor (ioe,, a morphism of Cat ) T * 1 ~2 ~ The proof of this assertion is straightforward but involved with a tedious diagram chasing as applied to the diagram which defines rr(x,y) above,'Furthermore, for the automorphism D of Cat we have R,- DoR and R 5 Do R o l 1 2 2 12 The procedure, by means of which we can prove that the previous observations on Cat imply that Aut(Cat) is the cyclic group of order two, and that every natural class in Cat is categorical iff it is closed under D, can be characterized by means of the following general definition, DEFINITION 1361, Let M be an object of a category C Denote by C [MI the class of all the objects F(M) of C where F is an automorphism of C and F(M) is isomorphic to bM in C e A (non-deterministic) reconstruction scheme <M, R a e _I-> for the category C with the spec'al ob Mect M is a family of functors R (MCe) C >~, one feir each M,1Q E C[M] and each a in a subgroup A of the total class

69 group of all the automorphisms of C with the following properties0 (i) For any a c F and any M1,M2 E C[A] the functors Ra(M1) and R (M ) are naturally equivalent0 (ii) For any ca,8 C L/ and any MI e C[M], the functors aoRB(M9) and R (M') are naturally equivalent0 (iii) For the identity I of J (i,e,o I is the identity functor of D )D R.(M) is naturally equivalent to I (iv) For any automorphism F of C such that F(M) is isomorphic to M in C (i e, F (M), [M1] ) and for any a C j, there exists an aF 4 such that R (M)oF is naturally equivalent to R (F(M)) 0 As it follows from (ii) and (iii), and by the properties of Nat, for all a e- C the functor R (M) is naturally equivalent to the automorphism a of C ~ We can prove a similar result for all the automorphisms F of C such that F(M) is isonmorphic to M in C (io eo, F(M) ~ C[M] )e LEMMA 13,2, Let <Mh Ra: a c A> be a reconstruction scheme for a category C with the special object M of ~. Then for any automorphism F of ~ such F () is isomorphic to M in:, there exists an cE A such that F is naturally equivalent to R(jm) 0 In particular, by the notation of Definition 1301k (iv), F is naturally equivalent to R (M) where a = I, PROOFr Let aF e - be such that RI(M)oF is naturally equivalent to R (1) o Since F (M) e:[M], R (M) and R (F(M)) are naturally cxF cx FCxF equivalent, Since RI(M) is naturally equivalent to I, RI(Ml)oF is naturally equivalent to F = IoF o In conclusion, F is naturally equivalent to R (M) 0 aF NowD since aF is naturally equivalent to R (HI) we have the followCiF ing result, which will guide most of our work in the rest of the paper0

70 THEJOREr3I 13,3o Let i) R' a c > he a non-deterministic reconstruction scheme for a category C with the special object'I, and let ~A(. be tihe quotient group of' under natural eouivalence, If the isomorphism type of'M. in C is categqorical, then Aut(4) is isomor!phic to 4e*. In particular, a natural class of morphisms of C is categorical iff it is closed under ~ Our examination of Cat shows that Cat has a non-deterministic reconstruction scheme indexed by the group of the two automorphisms I and D o The special object of this scheme is [ >], and since its isomorphism type in Cat is categorical, we get the desired results, Namely, a natural class of Cat is categorical iff it is closed under the "opposition" automorphism [:): Cat - fat, and Aut(~at) is the cyclic group of order two, Freyd [8; pp,29-32] provides us with sufficient information for the definition of non-deterministic reconstruction schemes for many well known categories0 Although we differ slightly from Freyd's terminology and from his concepts, it is clear that the whole work presented in this chapter was motivated by the exercises of Chapter 1 in Freyd's book on abelian categories [8]. Freyd notes that since in the reconstruction scheme for Cat we make use of thle categories [ —-— J [ -+[ —.] and [ > - ], one can reproduce the same scheme for any subcategory of Cat which contains these objects and all the functors among them. To name some important categories of this kind, we derive a result, similar to that about Cat, for each category in the following list: the category of small categories, the category of finite categories and the category of partially ordered sets (i eo. small categories C with C(A,) containing at most a single morphism for any objects A, B, of C ).

71 In addition to these categories of categories, Freyd shows how to reconstruct the multiplication table of any group G from the properties of G(ZDG) in the category ~ of all groups. His construction determines in fact a non-deterministic reconstruction scheme for ~ with the special object Z and indexed by the cyclic group A of the two automorphisms of ~ the identity and D - G 1) which maps every group on its mirror image group. Since Z is distinguished in G by the same facts which distinguish it in Gab the group Aut(~) is isomorphic to * But,// here Ataj is trivial. The automorphism D o 6 -— 6 is naturally equin valent to IlG by the family of isomorphisms a (G) o D(G) >G d g -g- Hence 6 is auto-trivialo It is interesting to note that the same construction suggested by Freyd for G is applicable to Ml, the category of all monoids, Here, howeverD the automorphism D ~ V 4M which carries each monoid into its mirror image is not even equivalent to the identity functor of 1! o For example the three element monoid in which the product of any ordered pair of non-identity elements is equal to the first element in the pair, is obviously not isomorphic to its mirror image,, Hence and both Aut (M) and Ob (M) (and therefore Tran (M) ) are the cyclical group of order two. Furthermore, a natural class in IN is categorical iff it is closed under D ~ -4I o In particular, the class of surjective monoid homomorphisms; as a class of morphisms of 2M, even though it is not identical with the class of the epic morphisms in TM, is nevertheless categorical in t LikewiseD the class of (the identity morphisms of) the free monoids is categorical in T.l D for obviously the mirror image of a free monoid is

72 a free monoid. Note that a monoid F is free iff for any morphism g: F B and any surjective morphism e: A — B of N, there exists a morphism f: F -— A in i such that ef = g. s;ince epic morphisms in N need not be surjective, it is not surprising that the free monoids need not be projective in M. For a definition of projective objects in categories see [8; Prop. 3.31] or in this paper, Part II, Ch. III, Section 10, In fact, the trivial monoid is the only projective object of

PART II THE CATEGORICAL PREDICATES IN CATEGORIES OF SEMIMODULES 73

INTRODUCTION TO PART II Our main concern in this part is to determine the categorical predicates in certain categories of transition systems, Recent studies in automata theory indicate the importance of transition systems and their homomorphisms, Most types of automata which are studied have a free monoid as an input and a component which is defined as a transition system with a free input monoid, Frequently the transition system of an automaton is defined as a mapping from the cartesian product of a set (the set of states of the automaton) with a free monoid (the free monoid generated by the inpt alphabet of the automaton) back to the set of states of the automaton, This function is usually determined as a natural extension of an arbitrary function from the cartesian product of the set of states with the input alphabet back to the set of states (cf. [2], [9] and [16]). A homomorphism of automata of the same kind is usually determined by a homomorphism of their transition systems. Loosely speaking, a homomorphism from a transition system A to a transition system B (with the same input monoid) is a function from the states of A to the states of B which "preserves the functions of A and B ". For a given fixed input monoid W, a category $W of all the transition systems over W is determined by the homomorphisms of transition systems with the obvious composition rule. Before we study the categorical predicates in $W, we define transition systems over an arbitrary input monoid W. Because of a certain analogy with modules, we will refer to these systems by the term "semimodules". We discover non-deterministic reconstruction schemes (cf. Part I, Ch, II, Section 13) for all the categories of semimodules which are defined analogously to $W with a free monoid W. These schemes have a general form for all W, and in particular they are involved with groups of auto74

75 morphisms of $V which are induced by Aut(W), the automorphism group of the input monoid W d Furthermore, for any W, the special object of the reconstruction scheme of $W is W itself regarded as a semimodule. We denote this special object of SW by MW * Guided by Theorem 13,3 in Chapter II of Part I, we proceed and study several conditions under which the isomorphism type of FIW is categorical in $, We find that for a very broad class of input monoids, the semimodule M W is distinguished in $W up to an isomorphism by means of a categorical predicate. This class of input monoids includes all the types of monoids encountered in automata theory (egd, the free monoids, groups, abelian monoids and finite monoids), In order to establish this result, we study the category $ W for an arbitrary input monoid W, and yield the characterization of several categorically interesting classes of semimodules. Unfortunately, we do not have the desired result that for all input monoids W, the isomorphism W type of MW is categorical in $. As for the categorical predicates in $ and the class group Aut($W) D we find the following results: (i) for any monoid W, the class group Aut($W) has a subgroup isomorphic to Aut(W); (ii) if the isomorphism type of MW is categorical in $, then Aut(SW) is isomorphic to Aut(W); (iii) for any monoid W, a categorical class in $W must be closed under the automorphisms of $W induced by Aut(W); (iv) if the isomorphism type of ME is categorical in SW, then a natural class in $W is categorical iff it is closed under the automorphisms of $W induced by Aut(W) The automorphisms of $ which are induced by Aut(W) amount to the "relabeling" of W, in any semimodule over W, under an automorphism

76 of W, In the case of semimodules over a free monoid W, the autos morphisms induced by Aut(W) amount to the permutations of the input alphabet labels, Thus, the categorical properties of transition systems with a free input monoid are precisely those properties which do not depend on the particular labeling of the alphabet letters. In Part III we will examine these properties in detail4

CIIAPTER I: A PRELIMINARY STUDY OF CATEGORIES OF SEMIIMIODULES lo The definition of $ DEFINITION 1,1 A transition system A over a monoid W is a systen of the form A= (XA S(A)xW- >S(A)) where, (i) S(A) is an arbitrary set, the set of states of A; (ii) XA X S(A)xW -S(A) is a function, the transition function of A D which satisfy the following requirements: for any s c S(A), if wi1w2 C W then A (A(SWl),w2) = A(s,wlw2) and if 1 is the identity element of W. then XA(Sl) s For example, Rabin and Scott, in their paper on finite automata [16], show that for any function M o SxV - S, where S and V are sets, there exists a function HI*: SxV*- S, where V* is the free monoid generated by V, such that M*: SxV* S is an extension of M and it is a transition system over Vk* The definition of M1* is the obvious one, Other examples of transition systems over an arbitrary monoid W are the following0 We denote by 0W the unique transition system over W with an empty set of states, The transition function of 0W is the empty function 4xW — - 0 For any singleton set U, we denote by UW the transition system over W with U as its set of states, If U = {z}, then the transition function of JiW is defined by 77

78 XU (z,w) = z for all w E W, Finally, every monoid I can be regarded as a transition system over W which will be denoted by MW. The transition function of MW is defined by the multiplication in W. That is, the set of states of M1W is W and for any wl,W2 C W we define Xy (Wl,W2) = wlw2. Note that HW is a transition system over W precisely because W is a monoid. We notice that transition systems over monoids can appear in mathematics in several contexts. Before we illustrate the ubiquity of transition systems, we introduce the notion of left transition systems as "mirror image" of transition systems. Thus, a left transition system over W has the form B = (X*: WxS(B) —-S(B)) where X* satisfies now the equations BXlwX*B(w2,s)) = X sB(w1w2DS), and X*(l,s) = s It is obvious that the theory of left transition systems is thie theory of transition systems as defined in Definition 1.1, but "through the looking glass". Consider for example monadic algebras ([1], [5]), A monadic algebra A is a set S(A) (the carrier of A ) together with a set 2 (the operator domain of A ) provided with a mapping T from Q to the set of all functions S(A) -— S(A), For any s C S(A) we will write ws instead of [T(w)](S), where w is any arbitrary operator of A (ioe,, X e Q ). Clearly, A can be regarded as a left transition system over *, the free monoid generated by Q. Define A(w,s) = ws The relationship between monadic algebras and finite automata were dis

79 covered first by Buchi (cf. [2] and [17]). Closely related to monadic algebras and its relationships to transition systems is the notion of groups operating on sets [3] and its generalization, the notion of monoids operating on sets. A homomorphism tI of a group G into the group of all permutations on a set S(A) is called an operation of G on S If for g c G and s S (A) we denote by gs the element [H(g)] (s), then the operation H of G on S(A) can be regarded as both a monadic algebra with carrier S(A) and operator domain G (and therefore as a left transition system over G*, the free monoid generated by the set of elements of G ) and a left transition system over G itself, A homomorphism }I of a monoid W into the monoid of all the functions S(A) —S(A) is called an operation of W on SSA. Similar to operations of groups on sets, an operation of a monoid W on a set S(A) yields both a monadic algebra (with carrier S(A) and operator domain W ) and a left transition system over W (with S(A) as its set of states)o Finally, modules over rings with identity ([3], [5]) yield also transition systems when one "forgets" their additive structure.. A (Ieft) module over a ring R with identity is a homomorphism M from R into the ring End(G) of the endomorphisms of an abelian group G C If in a given module M: R -End(G) we ignore both the addition in R and the addition in G, we are left with a homomorphism of the multiplicative monoid of R into the monoid of the functions from the set of elements of G into itself. Hence by "forgetting" the additive structure of modules we get operations of monoids on sets, and therefore left-transition systems. Due to this fact, Cohn [5; pp.53, 55] calls an operation of a group on a set by the term G-module, and an operation of a monoid S on a set by the term S-module,

80 Since the structure of transition systems lacks the essential additive structure of modules, we are reluctant to use the term "W-module" for a transition system over W o However, because of the similarity that exists between transition systems and (right) modules, we suggest the compromising term W-semimodule (or simply semimodule) for referring to a transition system over W o We will reserve the term "transition system" for the contexts in which the relevance to automata theory is apparent. However, the arbitrary decision to discuss right transition systems instead of left transition systems, is motivated by the customary notation used in automata theory (cf0 [9], [16] and [18])0 On the other hand, we borrow from module theory the following notation, Instead of writing "XA(sw)" we will use the abbreviation "sow", especially whenever confusion with respect to the identification of the semimodule under consideration is not possible, For example, with this notation, transition functions (cf0 Definition 1o1) satisfy precisely the multiplicative axioms of right modules: sol = s and so(wlw2) = (sowl)ow2 0 The homomorphisms of transition systems over a fixed input monoid W also resemble the homomorphisms of modules over a fixed ring~ DEFINITION 1a2o Given two W-semimodules A and B, a function f: S(A) —+S(B) is said to determine the homomorphism f: A —- B of W-semimodules iff f(sow) = f(s)ow for all s C S(A) and w c W o Thus, with any function f: S(A) —-S(B) which satisfies the above mentioned condition, we have a unique homomorphism f: A —B of W-semi

81 modules. Obviously a composition of functions which determine homomorphisms of W-semimodules, also determines a homomorphism of W-semimoduleso Hence the class of all W-semimodules together with their homomorphisms forms a category whose composition rule is given by (and only by): (f: A — B)(g C -A) = (fg: C - B) We denote this category by $ 20 Products and sums in SW W As we show in this section, the category $ admits products and sums in an analogous manner to $, the category of sets, Recall that in $ the products are determined by cartesian products and the sums by desjoint union of sets (cf. Part I, Chapter I, Section 5). Let {Ti} be any family of sets indexed by a set I o The cartesian product flTi} is a product object of {Ti} in $ with the obvious projections {pi {Ti} )T.} as a product diagram. If {T!} is another family of sets and {fi: Ti. -T} is a family of functions both indexed by I, then l{fi: Ti-T'}: T{Ti} -t{TI} is well defined as a product object of the family of the subsets T.xT' which represent the functions f. as sets. Similarly, the disjoint union E{Ti} (eg,, E{Ti} = U{Tix{i}} ) is a sum object of {T.} in S with the obvious sum diagram {g.i T.-i Z{Ti}} of injections, As for the family {fi: T — T!} it yields now a sum function Z{f. T. -TZ }: {T.} -Z{T!} o 1 1 1 1 1

82 We leave it for the reader to verify the following lemma which describes the products and sums in S. LEMMA 2.1, Let {Ai} be a family of W-semimodules indexed by some index set I. The object V{Ai} which is defined by S(nI{Ai}) = {S(Ai)} and X ={Ai} ={X}Ai is a froduct object of {A.} in.$W Furthermore, the family {Pi: H{Ai} —Ai} of the homomorphisms determined by the product diagram {Pi: H{S(Ai) } S(Ai)} of {S(Ai)} in $, is a product diagram bf f{A.} in S i The object E(Ai) which is defined by S(1{Ai}) = E{S(Ai)} and XZ{Ai} {XA is a sum object of {Ai} in $. Furthermore, the family {qi: Ai -){Ai}} of the homomorphisms determined by the sum diagram {qi: S(Ai) - Z{S(Ai)}} of {S(Ai)} in $ is a sum diagram of Z{Ai} in sW * Hence we have THEOREM 2.2. The category SW admits products and sums of any set indexed family of objects. The special case where all the objects in the family {Ai} are identical and equal, say, to A, deserves special attention. For a change, let us denote by T the index set of {At} where for all t E T, At = A. In this case, a product object of {At} can be AT, where AT is defined by S(AT) = S(A)T

83 the set of all functions *: T — -..S(A), and ow: T- S(A) is the function which maps any t ~ T on 4(t) w o Similarly, a sum object of {A.} can be ToA, where ToA is defined by S(T A) = TxS(A) and (t,s) w = (t,s.w) o Note that like in any category with products and sums, the products and sums in S yield functors from products of SW to SW as follows, Let T be any index set and denote by ( W)T the product category of the families of objects of SW indexed by T (i.e., (SW)T is a product object in Cat, the category of all categories). The product in $W yields therefore a functor T (S W) VT sW which maps any family of objects of $W indexed by T, on its product object. Similarly the sum in SW yields a functor ST WT SW which maps any object of ($W)Ton its sum'objecti S 3. The basic ty es of the morphisms of $ and the forgetful functor S WS — 5 The W-semimodules are defined as (right) operations of W on sets, The homomorphisms of W-semimodules are determined by suitable functions on sets, As morphisms of $W they may belong to some of the basic types of morphisms in categories (ioe., epic, monic or invertible mnorphisms, that is isomorphisms)0 As functions they may be surjective, injective or

84 bijective (or what have you),. As we noted in Part I, Chapter I, this situation is analogous to that of many familiar categories. First, we note that the assignment S from semimodules to their sets of states and from homomorphisms of semimodules to their underlying functions determines a functor S: $;-s Observe that the very definition of $W implies that S $W >$, the forgetful functor of $W is indeed a functor. Since for any fixed pair of W-semimodules A and B, by definition (Definition 1,2), the underlying functions of the homomorphisms A -— B determine the homomorphisms uniquely, the forgetful functor S: $W -$ is an embedding. We prove now that S: $W $ is surjective but not injective, unless W is the trivial monoid. We define the functor Triv: S$ S;, where for any set T, Triv(T) = TW is the trivial operation of W on T. That is, TW is defined by S(TW) = T and tow = t Any function f: T1 —T2 determines a homomorphism f (T1)w -— (T2) and we define Triv(f: T1 >T2) = (f (T1)W (T2)w) Clearly SoTriv is the identity functor of S, and therefore S is surjective. Furthermore, if W is trivial, then every W-semimodule A is S(A)w, and therefore S(A) = S(B) implies A = B. That is, S is injective and therefore, in this case, S: $W )S is the inverse of Triv: $ W and it is an isomorphism of categories. If W is not trivial, then WW M MW, and yet S(MW) " S(WW) = W o

85 From the definition of the morphisms of S$ (i.e., Definition 102) follows also that a morphism of $W is an isomorphism iff its underlying function is bijective, In one direction, this statement is trivial because every functor maps isomorphisms on isomorphisms0 On the other hand, if the underlying function of a morphism f of $W is bijective, then the inverse function f of f in $ satisfies also the condition stated in Definition 1,2 for the morphisms in. IHence f must be invertible in $W; ie., an isomorphismn From the fact that S S "->$ is an embedding functor follows that it reflects epic and monic morphisms from $ to S o That is, if for a morphism f o A- B, f: S(A) - S(B) is surjective (or respectively, injective), then f: A -B is epic (or respectively, monic) in $ o We prove this statement for the surjective case~ The proof for the dual case follows duallyo Assume that the underlying function f: S(A) —- S(B) of a morphism f: A -+B of $W is surjective, and that glg2 o B >C are morphisms with glf = g2f 0 Since f: S(A) -S(B) is epic in S, the underlying functions of gl ~ B IC and g2: B -C are identical, But S - SW — S is an embedding, and therefore we have g = g2 in SW which proves that f o A —B is epico In order to prove the converse (ioe, that S preserves epic and monic morphisms from $W to S ), we need some preliminaries0 Note also that the arguments used in the forthcoming proof are analogous to a proof to the effect that the forgetful functor of the category 6 of groups preserves epic and monic morphismso DEFINITION 3.1, Let A be a W-semimoduleo A subset T of S(A) is said to determine the subsYStem A(T) of A iff (i) for all t c T and w C W, tow c T, and

86 (ii) A(T) is the W-semimodule defined by S(A(T)) = T and XA(T) is the restriction of kA on T. LEIIA 3.2. If f: A -B is a homomorphism of W-semimodules, then f(S(A)) determines a subsystem of B o We denote by f(A) the subsystem of B determined by f(S(A)) o Subsystems of semimodules determine quotient systems in a natural manner. DEFINITION 3.3. Let C be a subsystem of the W-semimodule B We denote by B/C the object defined by S(B/C) = (S(B)-S(C)) U {s.} where s.* S(B), and the transition function of B/C is identical with X B for any pair s e S(B) and w e W where both s and XB(s,w) are in S(B)-S(C), otherwise we have XB/c(sw) = s*. We define also qC: S(B)- S(B/C) as the function which maps all of S(C) on s*, otherwise it is the identity on S(B)-S(C) It is easy to verify that B/C is a W-semimodule and that qC: S(B) -S(B/C) determines a homomorphism qC: B -B/C of W-semimodules. We call it the canonical morphism from B to B/C o It is by no means the only morphism from B to B/C. For example, we denote by z: B- B/C the morphism whose underlying function maps all of S(B) on s,*. Clearly z = qC iff C = B, and then B/C = {s,*}W We call z:B — B/C the trivial morphism from B to B/C We prove now LEMMA 3,4. If f: A -B is an epic morphism of S, then f: S(A) —S(B) is surjective.

87 PROOF, Consider the canonical morphism qf(A): B B/f(A) and the trivial morphism z: B —- B/f( A) Obviously f: S(A) -> S(B) is surjective iff qf(A) = z a Both zf:A- -B/f(A) and qf(A)f: A -B/f(A) are determined by the same underlying function which maps all of S(A) on s d Hence zf = qf A) f in $ But f is epic in $W, and therefore z = qf A) and f o S(A) >S(B) is surjective, A different argument is reeded for the proof of the dual of 3,4, LEMiA 3,5, If f o A- B is a monic morphism of $W, then f Q S(A) > S(B) is injectiveo PROOF. For any s e S(A) denote by f: MW — A the morphism for which f s(1) = s (and therefore, f s() = s'w for all w e W ), Let Sl s2 c S(A) be such that f(sl) = f(s2) o Then, for f,sf s MW >A we have ff = ff, since both morphisms yield the same state of B! 2 when evaluated at 1 ~ W But f A —-B is monic in $, and therefore f = f Now, by evaluating at 1 c W we get s1 = s2 and s] s2 1 2 therefore f; S (A) >S (B) is injectiveo In conclusion we have THEOREM 3,6, The forgetful functor S o $ -S relates the basic types of the morphisms of $W and $ In particular, a morphism of $ is an isomorphism iff it is both monid and epic, We remark, in passing, that for any W-semimodule A, the set of all the subsystems of A forms a modular lattice with respect to set unions and set intersections, Hence all the composition series theorems hold for W-semimodulesd In particular, if C is a subsystem of B then B/C can be taken as a measure of the interval between B and C for which Jordan-Hilder theorem holds (cfo [5])o

88 CHAPTER II: A NON-DETERMINISTIC RECONSTRUCTION SCHEME FOR $ In this chapter we direct our study of SW towards the discovery of a non-deterministic reconstruction scheme for SI with MW as its special object (cf. Part I, Chapter II, Section 13). We begin with a "representation theorem" for $W stated in Proposition 4.3. This proposition states that every W-semimodule A is isomorphic to a W-semimodule with $W(MIw,A) as its set of states. The transition function of this representation of A is derived from the composition rule of $W itself. Unfortunately, unless W satisfies certain strong conditions (e.g., that W has only a trivial automorphism) this representation of A is not defined categorically from $ (MWA) a We derive this representation from a "representation" functor r* W W* where W* is the endomorphism monoid of MbW in $. Since W* is an isomorphic copy of W, then for any W-semimodule A, every isomorphism W -— W* yields a W-semimodule out of the W*-semimodule r*(A) In particular, for the isomorphism': W )W* which is determined by Io=P(MW) W W $SW(MWJw ): w,f where fw: MW -M1W is determined by fw(1) = w, we get a W-semimodule r* (A) which is isomorphic to A and S(ry (A)) = SWMWA), W W Each isomorphism' W W IW* determines a functor r' S W W ro. $W_- >$I which is naturally equivalent to the identity functor of $W.

89 Our study of Iso(W,W*), the set of all monoid isomorphisms from III to WI* leads us finally to the desired reconstruction scheme for $ In particular, we turn to study the group at of the automorphisms of $W which are induced in a natural manner by the automorphisms of the monoid W A further study of A and the functors r. SW, yields a reconstruction scheme for W with FMW as its special object, and which is inde.xed by A, 4, The representation functor of $ We elaborate here on the key idea of the proof of Lemma 3,5. LEMIMIA 4olo The family of mappings p(A) ~ S(A) >S (M1g,A) s >>f (where fs I -11- A is determined by f (1) = s ), one for each object A of $, determines a natural equivalence p S> (mw, In particular, for any morphism g: A —-B of S and for any s E S(A) we have gfs fg(s) ~ PROOF, We prove first that p(A) is a bijectiono (Note that we used this property of p(A) in the proof of Lemma 3,5~) Since fs(W1 Ww) fs (ww2) = sow w2 = (sOW1) W2 = f (w1).w2 it follows that for all s c S(A), f: IM.l —— A'is indeed a morphism of $ W $W Now if h: W >-A is any morphism of S, then f(l) (w) = h(l)ow = h(w), for all w s W. hence fh(l) = h, which shows that p(A) is surjectiveo On the other hand, if f = f, then by evaluating at 1 we get s~ = s, 0 Thus

90 p(A) ~ S(A) —-$ (Mw,A) is a bijectiono Finally, for any morphism g: A- B of $W we have the equality gf = fg(s) because for any s C S(A) we have (gfs)(l) = g(s) ~ Now, since for any morphism g: A -B and any s c S(A) we have [p(B)g](s) = f and [$W (MW, )(g)][p(A)](s) = g f g(s) s the equality gf = f expresses precisely the requirement that s g(s) the family of bijections p(A) S(A) >$W(Mw,-) determines a natural equivalence p: S - $W(Mw,-). If we apply now Lemma 4.1 to A = MW, we get for all W1,W2 W, ff =f f w W2 fw (w2) ww2f X This equality now expresses precisely the analog of the Cayley Theorem for monids, because the morphisms MWW -MW are determined by the left translations of W. Thus we have COROLLARY 4.2. Let W* denote the endomorphism monoid of MW in $ The bijection p(Mw),W-.$ - ($WMwMw) determines a monoid isomorphism W — W* So far we have the following features of the functor $ (Mw,-) First, for any object A of $ * the set $ (Mw,A) is isomorphic to the set S(A) of states of A o And, the set isomorphism from the carrier of W (which is the set of states of MW ) to SW(Mw,FMw) determines a monoid isomorphism from W to W* o We need now a suitable definition for a function $W(Mw,A) x$ (MWW) is (EW, A), that will yield a transition function of a semimodule over W* with S (MlW,A) as its set of states. The composition rule in SW seems to be

91 a good suggestion~ We define an assignment r* from the objects of $W to the objects of $W* For any W-semimodule A, the object r*(A) is the W*-semimodule defined by S(r*(A)) = S (HW,A) and foh = fh for all f $W (mw,A) and h c $ W(Mw,) o It is easy to verify that r*(A) is indeed a semimodule over W*. Furthermore, for any morphism f - A->B of $W,the function [$ lsw'-)](f): $s(vewA) >S (Mw B): fs >ffs determines a morphism of $ This follows simply from the associativity of the composition rule of $W 5 f(fsh) = (ff )h We denote the morphism 5 S of $ determined by f A -- IB by r*(f): r*(A) --- r*(B). In conclusion, we have a functor r*: $W $W* for which Sor* = S (Mw,-) We call this functor, the representation functor of $ Now Lemma 4.1 implies directly the equality f = f = ff sow f (w) s w S valid for all s e S(A) and w c W l Hence we have that XA S(A) x W > S(A) (Mw,A) x (MW,Mw) > S(MHw,~w) X* (A)

92 commutes for any W-semimodule A o Since p(A) is a bijection and p(MW) is an isomorphism of monoids, we can say that r*(A) represents A in terms of the morphisms and their Composition rule in $ o Unfortunately, W* is not identical with W, and therefore r*(A) is not an object of S o Still we may interpret W* as W, according to various possible isomorphisms from W onto W* For example, let ~o: W — W* be the isomorphism determined by p(Mw): W -- S (MW,Mw) (cf. Corollary 4o2) Furthermore, let r, (A) be the W-semimodule defined by S(ro (A)) = SW (MW,A), and r (A) (fs) f f w Xr*(A)(f, so(w)) Lemma 4,1 implies directly the "representation theorem" stated in the following proposition. PROPOSITION 4~3, With the notation introduced above, for any W-semimodule A, the function p(A): S(A) IS(r o(A)) ~ s Ifs determines an isomorphism pio (A):A -ro (A) of $ It is clear that if there were only a single isomorphism W — W*, then rW (A) is defined categorically from $ W(Mw,A). In this case, r (A) tells us everything that can be said about A in terms of MW go and additional categorical predicates in $ 5 Such a case happens when W has a trivial automorphism group. For note that if k1 and ~2 are two different isomorphisms from W onto W*, then 12l and 2 1 are two non-trivial automorphisms of W 0 Before we elaborate on

93 the effect of Aut(W) on the possible interpretations of r*(A) as a W-semimodule, we define these interpretations as certain functors induced by r*: > —-S and the isomorphisms: g W - )W* W 5, The reconstruction functors r $ $SW Here and in the rest of this chapter we will define several families of functors by means of the usual schemes of definition for semimodules and their homomorphisms that we have employed so far, We will leave for the reader the routine task of verifying that the defined entities are, in fact, W-semimodules, homomorphisms of seminodules, or functors, as the case will be, For the simplicity of our notation we will denote the functor sW (1, W o $W >$ by r:S SS DEFINITION 15,1, Let': W -W* be an isomorphism of monoids, The functor $W $W is defined as follows, For any W-semimodule A, r.(A) is defined by S(rT(A)) = r(A) and Xr (A) (f Sw) = fS (w) For any morphism f A B of $W the morphism r (f): r (A) >r (B) is defined to be the homomorphism whose underlying function is r(f): r(A) r(B) o Note that for any isomorphism.: W — W* we have Sor r = s (w,I-), Furthermore the transition function of r (A) is related to the transition function o:f r*(A) by the equality,(^ ) ( f w )' r (A) (Pfs'(w))

94 valid for any W-semimodule A, s C S(A) and w c W. The relationship between the isomorphisms W >-W* and the automorphisms of W itself is implied from the following lemma. Since the proof of this lemma is straight forward, we spell it out only for one subcase, while the rest of the proof is left for the reader, LEMMA 5.2. Let x: W -W be any function (i.e., from the carrier of W to itself). We define the mapping hx: --- W (Mw) W' by [hx(w)](1) = x(w); i.e., hx(W) = fx(w) ~ Then we have: (i) The correspondence x —-h is a bijection from the set of x functions W -W to the set of functions W ( $W(W,W). (ii) For any x1,x2: W -W we have hx ox2 h xi2 XlOX2 (iii) The function hx: W- (mwMw) determines a homdmorphism of x W, monoids h: W )W* iff x: W —-W itself determines a homomorphism x of monoids. (iv) The function hx is surjective (respectively, injective or bijective) iff x itself is surjective (respectively, injective or bijective). PROOF. We prove that hx::>S (MW, is surjective iff x: W -W is. Assume that h is surjective. Then for any morphism f: MW -iMW there exists a w2 E W such that hx(w2) = fw By t aW 1 1 the evaluation at 1 we get that for any w1 e W there exists a w? E W

95 such that x(w2) = [hx(w)] () = f (1) = wI 1 Ilence x: W — W is surjective. On the other hand, if x: W -— W is surjective, then for any w1 IE I there exists a w2 E 1 with x(w2) = w1 Hience for any wl E W there exists a w2 c W such that x(W2) x(w2) fw which implies that hI W: >W* is surjectiveo The rest of the assertions of this lemma are proven by similar arguments. Note that Lemma 4, 1 implies assertion (iii)o. By combining assertions (iii) and (iv) of Lemma 5~2, we derive the following corollary, COROLLARY 5.3, Let Aut(W) be the automorphism group of W and let Iso(W,W*) be the set of isomorphisms from IV onto W*. The correspondence a >I h determines a bijection from Aut(W) onto Iso(W,W*) o The relationship between this bijection and the functors r $ >S is expressed by the following immediate lemmao LEMIIA 5o 4 For any a e Aut(W) 9 W-semimodule A, s e S(A) and w c W 1 we have ( (A) ( w) = fsh (W) = ff =f rh (A) s s s ca(w) soa(w) cl If, in addition, 8 c Aut(lW), then Xh (A (f~ w) = 4 rh (A)( r SW X (f S ac(w)) Hne in(A)s ih (A) s Hience, in particular,

96 rh (A) (fs w) T (A)(f S,a(w)) Thus, every "reconstruction" functor r: $ s > can be derived from r~ by "modifying the input by an automorphism a of W " (ioe, by a e Aut(W) for which h - o,) This relation of the functors r $W -$W is especially important because of the following property of ro which increases the import of Proposition 4,3. Lemma 4,1 implies not only that p(A): S(A) >S(r~ (A)) determines an isomorphism p (A) A >r (A), for all W-semimodules A, but also that this family of isomorphisms is natural, Namely, the commutative diagram for the natural equivalence p ~ S — S (MW-), that is, the equality gfs = fg(5), implies directly the proof of the following lemma (cf, Lemma 4.1), LESMIA 55.~ The family of isomorphisms p (A) A- >r (A), for all WP0 0 objects A of $, determines a natural equivalence W Furthermore, from the identity functor I of $ to r S: s Furthermore, we have Sop4 = p (ioe... S(p (A)) = p(A) for all objects A of SW ) 6,.. The _automorphisms of S$ induced by Aut (W) The relationships among the reconstruction functors of $W, as expressed in Lemma 5,4, lead us to consider transformations of W-semimodules which are induced by functions x e W —, In particular, we will be interested in those translations which are induced by Aut(W) o So let A be an arbitrary W-semimodule and x: W —W be any function, We define a system AX = (x. S(A)xW —>S(A )) by AA(sw) = XA(sx(w)) o

97 We want to find out under what conditions on x;: W -W AX is a- Wsemimodule for any W-semimodule A ~ In ordet.to, do so, we examlxilic X MW In particular, we examine XA (S,w)' for s = 1, the identity element of x W. 1y the definition of A>!, we have XA (lw) = x(w) Hence Mw is a W-semimodulb iff x: W —-W is a homomorphism of monoidso We denote by End(W) the endomorphism monoid of W o DEFINITION 6,1. For any i ~ End(W) we define the functor T W -> as follows, For any object A of S W T (A) is defined by S(T (A)) = S(A) and AT (A)(sow) = AA(s,4(w)) For any morphism f A-+B, the morphism T (f) T (A)->T-(13) is the homomorphism from T (A) to T (B) with the same underlying function as f ~ A —-;- B It follows immediately from the definition of T~: $ -5 that it is an embedding functor and SoT, = S Note that in our discussion of the properties of the forgetful functor of SW (cfo Section 3), we noted the fact that T (MW) # MW whenever W is not the trivial monoid and where ~ o W -W is the trivial endomorphism of W. The following lemma establishes the fact that the set of the functors T I S >5W induced by End(W) is closed under the composition of functors, and therefore, with this composition, it is a monoid. LEMIMA 6o2, If 1'~2 ~ End(W), then T oT =T

98 PROOF. All we have to show is that for any W-semimodule A we have the equality X[T oT ](A) T (A) 2 420%1 So let s C S(A) and w s W, then we have A[T T ] (A) (sT (T T (A)) (s,w) 1 2 1 2 XT (A) (s'4l(w)) =2 = XA(sO [2o"1] (w)) XT (A)(s w) By evaluating at M, and in particular for the state 1 of W, we get that T1 = T4, implies 1 = * 2 ~ Hence, the mapping T determines an anti-isomorphism of End(W) with the monoid of the functors T. W Y $ S induced by End(W) 0 In particular we have the following corollary. COROLLARY 6.3. If a E Aut(W), then T is an automorphism of $W with ToT-1 = TlT = 1 We can rephrase now the essential part of Lemma 5.4 by the following lemma which also explicates the meaning of "modifying the input by an automorphism a of W " O LEMNA 6040 For any a,B Aut (W) we have Torl = rh and, in particular, since hi is the identity automorphism of W, 4)

99 we have T or = r, a From Lemma 505 we know that p I -re is a natural equivalence with Sop p By the properties of SNat (cf, Part I, Chapter II, Section 6), we derive tlhe following corollary of Lemma 535 and Lemma 6,4, COROLLARY 6 5o For any a s Aut(W1) we have a natural equivalence T op o T r a a h a wh-ere [T Op ](A) = Ta(p (A)) for all objects A of $, and 0 So~[T op ] = p Our goal in the next section is to show that the reconstruction functors r: 5 -SW can be extended into a non-deterministic reconstruction scheme <I, IWR a c A> for W$Y indexed by the group 4 of the automorphisms of SWh induced by the automorphisms of W In particular we will have Ra(M) - rh o Before we do so, we examine A*, the quotient group of A under natural equivalence. LEINMMA 66,~ For any Ec End(W), the underlying function of the endomorphism i - W -W determines a homomorphism of IW'-semimodules o PROOF, From 9(w1w2) = I(w1)i(w2) follows that

100 k(XM w(w1w2 )) xT,(M (W)((wl) W2) COROLLARY 6d7a If a c Aut(W), then: a ~ lIW M T (MbW) is an isomorphism in $ W IHence if F ~ MW >MW is any functor equivalent to T, for some a c Aut(W), then M1H is isomorphic to F(m'W) in S Assume now that T I )T is a natural equivalence of the identity functor of $S with T, for some a e Aut(W). We evaluate the commutative diagram for t: I >Ta at MW and in particular at 1 e S(MW) for an arbitrary morphism f: MW W d Denote by T the isomorphism t(MW): MW >Ta (MW) given by the transformation: I T Note that although we do not necessarily have Ta = a, we must have t(w 1w2) Ta(Wl)a(w2) and t (w) = a (l)a(w) o Furthermore, Ta: W W, the underlying function of the isomorphism T(MW): MW Ta (MW) W is of course injective, Since T o I ). oL is natural, we have tf =f t aO w w a for any morphism f ~ MW -MW M Thus, in particular, we have -1 r (w) [t f ](l) [ft (1) = r (l)w = t (a (w)) But T is injective, and therefore, w = a (w), which implies that a a is the identity automorphism of W o Since T is naturally equivalent to T8 (for a,B ~ Aut(W) ) iff T cloTB is naturally equivalent to the identity functor of $, and T,-loT = T o, we have concluded the proof of the following proposition6 PROPOSITION 6a 8 Let A be the group of the automorphisms T of $ induced by a e Aut(W), and let * be the quotient group of

101 under natural equivalence. Then A* is isomorphic to X; that is, for any a,B c Aut(W), T is naturally equivalent to TB iff a = B Furthermore, if we denote by [Ta] the natural equivalence class of T in the total class group of the automorphisms of SW, then the mapping a —4[T 1] determines a monomorphism (i,e,, monic morphism) of Aut(W) into Aut($W) Thus we know now that every categorical class in SW is closed under the automorphisms in A. The derivation of a reconstruction scheme for $W with the special object MW and indexed by A, will reduce the isomorphism of Y with Aut($W) to the categoricity of the isomorphism type of MW in $ 7, The reconstruction scheme for SW A functor F W is said to be M -invariant iff NW is isomorphic to F(MW) in $, The semimodule MW is said to be distinguishable in SW iff every automorphism of SW is Mw-invariant; that is, iff the isomorphism type of MW is categorical in $W Before we discuss the reconstruction scheme that we have in mind for $W let us make an abuse of our notation, and denote by a both the automorphism of W and the automorphism T of SW induced by a o According to our notation as introduced in Part I, Chapter II, Section 13, we denote by SW[Mw] the class of all semimodules F(MW) where F is any Mw-invariant automorphism of SW, We have to define now, for each a e /A and each M ~ [MW] a functor R (M) $SW In fact, we first define a slightly different class of functorso

102 DEFINITION 7o1l For any M I-invariant automorphism F of $, and W any isomorphism ~ MW —-Fl(Mw) of $S we define the functor r(qbF) $W sW as follows. For any W-semimodule A, the semimodule r(4,F)(A) is defined by S(r(qF)(A)) = $W (F(Mw) F(A)), and X(F(fs),w) = F(f )(o)(w)> ) where X denotes the transition function of r(q,F) (A) o For any morphism g:A —->B of $W we define r(4,F)(g) o r(P,F)(A) > r(,F)(B) to be the homomorphism whose underlying function is sW(F(Mw),F(A) ) - - $W(F(M1) F(B)) (fs) F(g)F(fg ); i.e., r(oF)(g) = r, (f(g)) Recall that o o W —-W*W is the isomorphism determined by P(MW) ~ W -$S (WHlMW); w -— f We prove now the following lemmao LEINIA 7,2, The transformation T(4~F) r r~oF ---— r(4,F) defined by T(cF) (A) $ (MIWF(A)) — $ w(F(w),F(A)) o g - g4) is a natural equivalence

103 PROOF. Obviously T(,F) (A) is bijectiveo Let us verify that it determines a homomorphism of W-semimoduleso if f I IW > F (A) is morphism of $W and w E W, then we have [T(jF)(A)](Xr (p(A))(fw)) = [T(,PF)(A)](fl (w)) = fp (w) ~; o and X([T (,F) (A)] (f)w) = X(f4,w) Thus, for anry W-semimodule A, T(O,F)(A) is an isomorphilism of W-semimodules, We prove now that it is natural, If g' A - >B is a morphism of S, then for any morpihi;l, f'I ->F(A) we have [TG(,F) (B)o(rl, o) (g)] (f) [T(, F) (B)] ( (g)f) o: PT (g) f~; and [r(, F) (g)oT(,T))A)] (f) = [r (, ) (g)] (f~ ) = [(r, oF) (g)] (f ) - F (g)f - ilclce T(~,F) r, oF - r(g,F) is a natural equivalence. 0o

104 Note that if F is the identity functor I of $W and ~ is the identity morphism of MW, then r(O,F) is precisely r and T(o,F) is the identity natural equivalenceo If instead of -O-: + W** we employ any arbitrary isomorphism i C Iso(W,W*) in the definition of r(O,F), we get a family of functors r4,(,F): W $ - Namely the transition function XA of r (0,F) (A) is defined by X4(F(f),w) = F(fS)(4((w)4 ). It is easy to verify that now we have a natural equivalence r(OF): r oF —- r (0, F), defined in a complete analogy with T(O,F). Furthermore, it is clear that we have rh (PF) = aor(4,F) for any a c E Equivalently, we can take the last equality as the definition of rb (,F), and then by the properties of Nat, we derive that aCT(4,F): OorJ oF a-or (QF) 0 is a natural equivalence0 But aor = rh and aor(O,F) = rh (,F),) o aC a and so we have a natural equivalence ao~(%,F) ~ rh oF —+rh (4,F) o Finally, we prove the following lemma that is needed in order that we can choose from thle family of functors r4)(4,F) $ —5 a reconstruction scheme for $o

105 LEMMA 7,3, Let F be an Mw-invariant automorphism of $ 9 ~MW-F-(F(W) an isomorphism in W and E Iso(W,W*). The functor W F restricted to $ (mW,-), determines a natural equivalence T r F rp(JF)-rF) where i(b,F) c Iso(WW*) is determined by [(~F)=] - Fl (~(w)l) ) PROOF, By Lemma 5,2 and the fact that functors preserve isomorphisms, it follows that *9(~F) is an isomorphism of W onto W* o We prove next that for any W-semimodule A, the function T,(A) S (M wA) SW(F (MW) F (A)) fs -— F(f ) f which is obviously a bijection, determines a homomorphism of W-semimoduleso So let f M - A be a morphism and w c W o Then [rF(A)](Xr (A) ( w)) = [ (A) = F(fs~ (OF)) = F(f s)]( w) 1 and Xr () F) T(A)([F(A)()w) = X(F(f s)W) = F(fS)>(w) o Hence TF(A) r4,() F) (A) -— > r ( F)(A) is an isomorphism in S Let now g A -— B be any morphism of SW and let f G - > A be any s W state of r4,(,,)(A) o Then we have

106 [r(CF) (g)otF(A)](fs) = [r,(4 F) (g)](F(fs)) = [ro (F(g))](F(fs)) = F(g)F(fs); and [TF(B)or0(, F)(g)] (f) = [TF(B)] (fs) = F(gf s) = F(g)F(f) o Hence TF is a natural equivalenceo The families of natural equivalences aoT(O,F): rh oF -rh (OF) O ax a and -F' r(~,F) >r(~,F) leave us much freedom in choosing a reconstruction scheme out of the family of functors r (qP) $W, $W For example, for any a E Y and any M E SW[MW] we define R (M) = rh ({PF) where M = F(Mw) and: MW — F(Mw) is any isomorphism, with the provision that if M = MW then both F and { are identities. Lemma 702 and its implications and Lemma 703 imply that <M,Rc: a cx } thus cx

107 defined is a non-deterministic reconstruction scheme for $W with the special object HMW (cfo Part I, Chapter II, Section 13)> In particular, we can infer, either from the properties of reconstruction schemes (ibid, Lemma 13.2) or directly from Lemmata 7,2 and 7o3, that an automorphism F of $W is naturally equivalent to T for some a c Aut(W) iff F is M w-invariant, In conclusion, we have proved the following reconstruction theorem for $ THEOREM 7.4, Let W be any monoid. The mapping a —-[T1] ] where [T,i] is the natural equivalence class of -T in-the total class group of the automorphisms of $, is a group isomorphism of Aut(W) onto Aut($W) iff MW is distinguishable in S W In particular, if M is distinguishable in $, then a natural class of morphisms in $ is categorical iff it is closed under A, the group of the automorphisms of SW induced by Aut(W) Thus, we know how to compute Aut($W) provided that we know that MW W W is distinguishable in $, As for the group Ob(S ), we know that if W is free then Ob(S ) is isomorphic to Aut(S) o We indicate the proof for the case where W is the free monoid generated by two elements, say a and b o Let A be the W-semimodule determined by S(A) = {sasb} XA(sa,a) = Sa XA(Sa,b) = sb A and XA(Sbga) = XA(Sbb) = Sb 0 The monoid W has two automorphisms, the identity and the one determined

108 by the interchanging of a with b a For any automorphism a of W T (A) is isomorphic to A iff a is the identity automorplhism of W1 If W is any free monoid, then for any a E Aut(W) there exists a WIsemimodule A such that A and T (Aa) are not isomorphico Hence, in this case, Aut(S ) and Ob(SW ), and therefore Tran(S W are isomorphic. The construction of A is analogous to the construction of A above, a and will not be given here, If W is an arbitrary monoid, then I do not know whether T is equivalent to I iff a is the identity automaor phism of W. As we will prove in the next chapter, the class of monoids for which MW is distinguishable in W, includes the free monoids,

CHAPTER III: TOWARDS TIIE DISTINGUISI{ABILITY OF MW IN SW Our main result in Chapter II, as expressed by Theorem 7o4, reduces a certain characterization of the categorical predicates in SW to the distinguishability of MW in S, To be specific, we can be sure that the categorical classes in $W are the natural classes which are closed under J (the group of the automorphisms of $W induced by Aut(W) ) only if MW is distinguishable in $, Our goal in this chapter is to establish conditions on W which are sufficient for the distinguishability of MW in $ 0o Unfortunately, we can prove that MW is distinguishable only for a limited class of monoids, The problem whether.MW is distinguishable in $" for any input monoid is still openo However, since our study of SW is motivated by automata theory, we note that our results guarantee the distinguishability of MW for any type of input monoid which is encountered in automata theory. Our search for the conditions for the distinguishability of MW leads us to a further study of the category $W In this study we employ several methods of the theory of abelian categories [8]~ In spite of the poor structure of semimodules (e,go,, in comparison with modules), we derive some properties of $W which may motivate a thorough study of SW with applications to the theory of monoidso For example, our characterization of the projective objects in $W indicates a significant relationship between the structure of SW and the structure of W o W Our strategy in the pursuit of the distinguishability of MW in S is not systematic0 While establishing the reconstruction scheme for $W we have discovered several outstanding properties of MW We check each one of these properties to see whether they yield a characterization of MW o Unfortunately only some of the known properties of HW imply 109

110 a characterization of MW, and even this is true only for some monoids W In particular we do not know how to make use of the following two remarkable properties of MW o The first property is that HMW has an endomorphism monoid isomorphic to W o We made use of this property in the discussion of the reconstruction scheme for S W but it is hard to see what can be said on the structure of a W-semimodule A with endomorphism monoid isomorphic to W. Every obvious attempt to relate this property to the distinguishability of MW fails to extend the class of monoids W for which we know that MW is distinguishable in $ o The second property of MW is related to the previous one but it deserves special attention. The definition of the representation functor r- W 5W* r* S -- $ in Chapter II, Section 4, suggests the following construction. Let C be any category which satisfies the set-theoretic axiom~ for any objects A and B of C D C(A,B) is a set, For any object M of C we define a functor r* o C >SE (M) where E(M) is the endomorphism monoid of M in o For any object A of C, the E(M)-semimodule rF(A) is defined by s(r*(A)) = ~(iA) and Xr(A) (fh) = fh (for all f e C(M,A) and h c E(M))o Because of the associativity of the composition rule in C, the functor ~(N1,-) determines homomorphisms of E(M)-modulese Thus for any morphism g: A - 4B, we define rel(g) ~ rj(A) —--- r*(B) to be the homomorphism determined by the function

lll [~(51a-)] (13): 6(tWmA) > CCFBj' f gf f Clearly, we have Sor* C(Mo1) Now* the functor ri C -— ~ sE() is an embedding iff M is a generator of C; i,e,, iff C(M,l) is an embeddingo (To recall, note that a functor F o C1 >C2 is an embedding iff for any pair of objects A and B of C1 l the function F ~ C (A, B)- >C2 (F(A),F(B)), F f F(f) is injectiveo) Thus we have that every category with a generator, and which satisfies the set-theoretic axiom, has an embedding functor into a category of semimodules0 A natural question arises: when is () a full embedding? We recall that a functor F ~1- C1 is full iff for any pair of objects A and B of C1, the function F: C1(AB) >~2(F(A),F(B)): f — (f) surjective0 It is not difficult to verify that MW has the property expressed by the fact that r* ~ $W_$W* which is precisely r* O $W_-$ E(HW) according to our M. recent notation, is a full embedding functoro That is, for every function $ $ (mW,A) -$ (MWB) which has the property that for every fw M HW — W and every fs I' \W.>A (fsfw) = K(fs)fw there exists a unique morphism f o A — B such that 4 is the underly, ing function of r*(f~): r*(A) — r*(B) o Simply define f o S(A) —+ S(B)

112 by fj(s) = W[(f )](1) o Furthermore, the natural equivalence of the forgetful functor of $ with $W(MW,-) implies that MW is a generator, It is interesting to note that we can make use of the fact that MiW is a generator in order to derive simple conditions which are sufficient for the distinguishability of MW in $ o But we do not know what to infer from the fullness of the functor r* o $W $ W* Nor do we know how to characterize those categories C with a generator M for which the embedding r:' ~ C $E(M) is fullo In this chapter we will discuss mainly three properties of M1AT and show how they yield sufficient conditions for the distinguishability of MWv In doing so we also provide characterizations of the free semimodules, the projective objects and the generators of $S We also discuss briefly the structure of the endomorphism mollo:i.!,L some projective objects in $. 8. The monogenic semimodules Let A be a W-semimoduleo A subset T of S(A) is said to generate A iff S(A) = {tow o t C T and w e W} o In particulars A is said to be monogenic iff there exists a singleton set which generates A, Thus A is monogenic iff there exists an s E S(A) such that S(A) = (s, o w w e t:} It is easy to see that DMw is monogenic, for it is generated by {1} 0 In fact DIW is generated by {u} iff there exists a v C W such that uv = 1, In order to realize that the class of monogenic W-semimodules is categorical in $, we prove the following lemma.

113 LEMMIA 801, A W-semimodule A is monogenic iff for any set {Til of sets which determine subsystems of A, U{Ti} = S(A) implies that S(A) = Tj; for some T.j {T.} PROOF, If A is monogenic, say by So z S(A), and U{Ti} = S(A) then s E T.j for some T.j {Ti} D and therefore T. =.S(A), On the other hand, let Ts = 5ow = {sow. w e W} for all s c S(A) O Then clearly {Ts} is a set of sets which determine subsystems of A, and U{Ts} - S(A) o If for some T (e{TS} we have T = S(A), then A is 0 o generated by {s } o We can translate now the statements of Lemma 801 and its proof and get a categorical characterization of the class of monogenic W-semimodules in $ o Recall that a categorical class in S is any class which is closed under the automorphisms of S PROPOSITION 80,2 The class of the monogenic W-semimodules is cate= gorical in $W PROOF. We make use of the fact that the subsets of S(A) which determine subsystems of A are represented by monic morphisms into A Furthermore. the union of a given set of such subsets represented by monic morphisms, is represented by a monic morphism with a universality property, That is, the union is represented by an initial object in an especially constructed category of the monic morphisms into A, Given a set J of monic morphisms j A ---- A of $ with a common range A, we define a category 3 whose objects are all the monic morphisms b o B —- A such that for any j c J there exists a morphism bj. A. —- B with bb. = j (and therefore bj must be monic) o There exists a morphism in J from (b o B —-A) to (b B 9 —sA) for each morphism f o B — RB with bJf = b (and hence f is monic)o For any

114 set J of monic morphisms of ~I with range A, the category JT has an initial object U(J) o In fact, a monic morphism b o B-A i s i ni tli- i n.7 if4 the ima7e semi.Todule b (B) is determined by the union oCa the images oC tile morphisms in J Hence, an object A of SW is monogenic,- ror any set J of monic morphisms of $W with range A, if U(J) is epic, then J contains an epic morphism, Since obviously monic and epic morphisms are preserved under automorphisms, if A is monogenic and F is an automorphism of $ S then F(A) is also monogenico Hence the class of monogenic W-semimodules is categorical in $ We know that M1ZW is monogenic, Furthermore, it is easy to verify that A is monogenic iff there exists an epic morphism e: MI!W,A o For, A is generated by {s} iff fs: MW -A is epic. We find the first sufficient condition for the distinguishability of M W by insisting that MIES be a "largest" monogenic object of SW. in the sense to be defined presently~ An object M1 of SW is said to be a largest object in a class K of objects of $S iff for any object A in K, if e: A -— M is an epic morphism, then it is an isomorphism. We prove now that MW is a largest monogenic object of SW iff W is unit-regular in the sense that if uv = 1 in W then vu = 1 as well. We say that w C W is a transform of 1 iff w - vu where uv = 1 in W o For any w s W we denote by 1 (w) the subsystem of MW which is determined by wW. We prove first the following lemmao LE LIMA 8,3, If w is a transform of 1 in W, then M (w) is isomorphic to MIW PROOF, Assume that wl = vu where uv = 1. We define the morphism eU o M(w1) MT by

115 e w wl-W W W-lW- -UW w Since uwlw = uvuw = uw' it follows that eu is surjectivem for any w sE W e (vw) = e (wlv) = w It is also injective since eu (W1W) = VUW1W =w W lW By the associativity of the multiplication in W, it follows that e determines a homomorphismo In conclusion e o.l(w ) —- is an isomorphismo Now we have PROPOSITION 8,4 W PW is the largest monogenic object of $W iff W is unit-regular. PROOFO Assume that MW is the largest monogenic object in $, and assume that uv = 1 0 Since M(vu) is isomorphic to MW, it is also a largest monogenic object in SW o We define evu M - M(vu) by e vuW - w —-+vu w vu Clearly, ev M~W - l(vu) is an epic morphismo But M(vu) is a largest vu I monogenic object in W, therefore, eV must be monico That is, vuw1 = vuw2 implies w1 = w2 o Since vuvu = vul, we must have vu = 1, and W is unit-regular, On the other hand, assume that W is unit-regular. Let A be a monogenic W-semimodule generated by {s}, and let e o A —-+hW be an epic morphismo Since e o S(A) —-W is surjective, there exists

116 a v E W such that 1 = e(so v) = e(s )v, and since W is unit-regular, twe have ve(s ) = 1 as well. WVe prove now that e is injective. Asso: e tihat c(s wl) = e(so w2), then we have w1 = Ve(So)W1 - ve(SoW1) = Ve(So.W2) = Ve(S )ow2 = W2, and in particular soawl = so~w2. Thus e: A >M is an isomorphismo 1ience, W is unit-regular iff HW is the largest monogenic object in S w From this proposition and from Proposition 8~2 follows now COROLLARY 8,5o If W is a unit-regular monoid, then 1W is distinguishable in $ 9. The free semimodules We rephrase a nart of Lemma 4.1 (cf. Chanter II) into a form whilicl. rnroves that ":!W is free on 1 ". I'e know from ILemma 4.1 t1hat, for any;-semimodule A and any s c S(A), there exists a unique mornilisr fs: -IJ A with f (1) = s, Thus, if j {l} -4W is the obvious injection, then bMW has the following property. For any W-semimodule A and any function f {l} 1 —i S(A), there exists a unique morphism f* 11, -,A of $ such that as functions we have f*j = f (namely, f* = ff(j) The general notion of free semimodules is now evident. DEFINITION 9,1. A W-semimodule A is said to be free with resnect to an inective function gT' T S(A) iff for any W-semimodule B and for any function f: T —-S(B) there exists a unique morphism f* A — B of $S with f*gT = f in S, the category of sets. As we indicated above, =M is free with respect to the inclusion function j {1} 3,! We can rrove a more general result.

117 LEMMA 9a,2, For any set T, the W-semimodule ToMiW is free with respect to the injection gT T —-TxW t —-(t,l) PROOF. Recall that TiwM is the sum object defined by S(ToMW) = TxW and (t,Wl)Ww2 = (t,w1w2) - Let A be any W-semimodule and f: T -4S(A) be any function, We define f*: TxW S (A) o (t, w) f (t) ow o By its very definition, f* determines a homomorphism f* o ToFIW -A of W-semimodules; and clearly we have f*gT = f Assume that for f1 ~ T oM1 —- A we have ffTg = f ~ Then for any (t,w) s TxW we get fv(t,w) = f(t,l)'~w = f.gT(t) w = f(t) oW = f*(tqw) HIence f' = f*, and so ToMlW is free with respect to gT ~ The definition of the free semimodules suggests their characterization as initial objects in categories especially constructed from $ o The analogy with the free objects in G, the category of groups, and in M1, in the category of monoids, is evident, Cohn [5; Chapter III] describes the general notion of free algebras in the same manner which is suggested by our discussions of the free objects in G and in 1, in Part I, Chapter I, Section 4 of this paper, In particular, we derive the following corollary of Lemma 9e20 COROLLARY 9o3, If A is a free W-semimodule with respect to an injection hT: T —-S(A), then A is isomorphic to Tolw o

118 PROOTr~ IUTe give here a direct nroof which does not depcnd on the general ciharacterization of the free algebras as initial objects some1-: where, o ote, however, that this proof reflects the proof to the effect that initial objects in categories are isomorphic (cf. Part I, Chapter T, Section 4), Since A is free *with respect to h: T —->S(A), there exists a unique morphism gT A- XT0'MW with gThT = g wh' i'ere gT is the injection specified in Lemma 9~2.e Similarly, we have a unique morp} ism T * ---— 1> wi2 h h I ience 1 17 T T T (igT) h i='l. and (gThT)gT = 1 The morphisn hTgT A —>A must be the identity, for there exists a unique mornhism i A —>A for which i hT = h where i = hT o Similarly, gTl T l —MT l~.i is the identity morphism, and therefore A and'1T'i are isomorphico This ciharacterization of the free W-semimodules, is obviously not categorical in its appearance, for it is involved with functions into sets of states, and not only with morphisms, Yet, we will refer to it in the characterization of the projective objects in S to be presented in the next section. 10. The structure ofthe projective'-semimodules. I!ir'INlTION 10,1, An object P of a cateqory 0; is called projcctivC if4f for any morphism g P — 13 and any enic tlorprhi.sm e s A -. o(f 0, there exists a rorphism f o P A of C such that ef = g As we will prove presently, in any category a sum of projective objects is always projectiveo In $', we find that MI? is projective, and therefore every free W-semimodule, by Corollary 9,3, is projective in

119 $ l Moreover, we prove that in $ every projective object is a sum of monogenic projective W-semimodules, Furthermore, a W-semimodule P is monogenic projective iff it is isomorphic to MI(u), the subsystem of zW determined by uW, where u is an idempotent of W o It follows directly from Lemma 8,3 that if W is a monoid in which every idempotent is a transform of 1 (eog, if 1 is the only idempotent of W ), then PM~ is distinguishable in $ by being a monogenic projective object of $S o LEMIMA 10,2,o If (in any category) P is a sum of projective objects then P is projectiveo PROOF. Let P = X{P } be the sum object of {P }, with the sum diagram {js Ps >{P }} Let e ~ A — B be any epic morphism and g.- P --— B be any morphism, If PS is projective (for all s ) then tlhere exists a morphism fs: P >A with ef = gj Let f,E {P } —A be the morphism guaranteed by the sum diagram {js ~ Ps — {P S and the family of morphisms {f ~ Ps-A}. That is, we have fj = f (for all s )o Then (for all s ) we have efj = ef = gjs IlHence' S S S ef:.{Ps } -B is the unique morphism guaranteed by the sum diagram of E{P } for the family {gjs 0 P -B But efj = gij, hence ef - g And so Z{P } is also projective, One can prove directly from the fact that T o-Ml is free, that it must be projective. Wle give here a "categorical"' proof to the same effect, LEMMIA 10o3, M2Il is projective in $ o PROOF. Let e o A —-B be an epic morphism of $S We refer to the commutative diagram of the natural equivalence p' S -5W (1Wv) evaluated at e: A- >B (cf, Lemma 4ol)3 We have [$ (I,1,)](e) = p(B)e(p(A))

120 and tlherefore [S'(UVIw,-)] (e) is surjective, which is just a fancy way to say that for any morphism g: ~.1M >- B there exists a morphism f: ~ 1 with ef = g. IHence Miv is projective. Note that the argument employed in the proof of Lemma 10.3 can be used to'prove the following general statement4, Let ~ be any category with a functor S: C >$ which maps epic morphisms on surjective functions. If P is an object of C such that C(P,-) is naturally equivalent to S, then P is projective in C. Now from Corollary 9.3, Lemma 10.3 and Lemma 10.2, follows the next lemma. LEMIPLA 10().4. Eivery free W-semimodule is projective in $!')ur main tool for studying the projective objects of $ is borrowed fror homological algebra, and is the notion of "splitting sequence" (cf. [13: o6,G]). A sequence j e A -*B )A of morphisms (in any category) is a Sltti1~ e iff ci i. thhe identity morphism of A. In this case we say that A splits thjrouN! B LEMIMA 10.5. (In any category) 1P is projective iff P spl its through some projective object Q PROOF. If 1P is projective, then P splits trivially through I On1 te other hand, assume tlat Q is projective and that P- -- > t is a splitting sequence. Let e: A - B be any epic morphism andi g. I > B any morplhism. Since Q is projective, there exists a morphism

121 ft Q >A with efl = gp d Hence efeg 5 gpq = g which shows that P is also projectiveo As for the projective W-semimodules, we can be more specific and prove that P is a projective object of $ iff P splits through some free W-semimoduleo Note that in any category, if P is projective and A -P is epic, then P splits through A, In SW we have that the transition function XA of any W-semimodule determines an epic homomorphism XA S(A)MW A from the free W-semimodule S(A)oMW onto A H Hence we have LEMMA 10O6 A W-semimodule P is projective iff P splits through some free W-semimodulesd In particular, if P is projective, then there exists a splitting sequence jp AP P - S(P) ~MW > P where the homomorphism Ap is determined by the transition function of P By examining the splitting sequence jp XP P -S(P) MW- I- ) we derive now the following corollary, COROLLARY 10,7o Every projective W-semimodule is a sum (ioe., disjoint union) of monogenic projective W-semimodules.

122 PROOF. The idea of the proof is the following. Clearly, S(P).M P ){{s}.l: s e S(P)}, i.e., S(P). MW is a sum of monogenic projective objects. Hence the splitting sequence of P through S(P)>IMw decomposes as a disjoint union of splitting sequences of the form.s Op P P.... {s }. MW P and P = E{P }. Formally, we proceed as follows. We define for each s c S(P), the W-semimodule Ps as the subsystem of P determined by S(PS) = {s' S(P): jp(s') C S.W} Since jp is monic, we have P = Z{P:s c S(P)} and S jp = {jp s { s}jHw} where jp is determined by the restriction jp{S(P5) of j to S(P). is gi P s) The decomposition of Xp as xp = {p: s F S(P)} is given by Xp Se a W'S(P) ( sow) - SO*W w S SS Clearly we have Xpjp = Xpjp, and ip = iptS(Ps) = Xijpls(ps) = Xpjs = pJp where ix denotes the identity morphism of X. Hence, for all s c S(P), the image of XP is precisely P, and so P is monogenic and it splits through {s}oM1W by means of the splitting sequence jS X S

123 Thus P is a sum of monogenic projective W-semimodules. Note that the empty W-semimodule is projective since it is the only free WI-semimodule with respect to the empty function. In this case our arguments are vacuously valid; the empty semimodule is the sum of the empty family. From Crorollary 10,7 we can infer that every summand of a projective object of SW is projective, Assume that P is a projective W-semimodule and P = A + B in $ o The decomposition of P as a sum of monogenic projective W-semimodules P -= {P } implies that A = E{PS: s e S(A)} and B = Z(P: s E S(B)} Hlence A and B are sums of projective W-semimodules and therefore, by Lemma 10,2, they are both projective, Another important implication of Corollary 10,7 is COROLLARY 10,o8 A W-semimodule P is monogenic projective iff it is isomorphic to a monogenic projective subsystem of MW PROOF, We give here a proof independent of Corollary 10,7, If P is monogenic, then there exists an epic morphism e: Mw -P (cf, Section 8), If in addition P is projective, then for the identity morphism P >P we have a morphism j: P -MW of such that ej is the identity morphism of P H Ience j e P - MW >P is a splitting sequence and j(P) is a subsystem of MW isomorphic to P Thus, in order to characterize the projective objects of SW, it is sufficient to characterize the monogenic projective subsystems of MW o We recall that we denote by M(u) the subsystem of MW determined by uW, A first characterization of the monogenic projective subsystems of

124 of MW is given in the following proposition. PROPOSITION 10.9. A monogenic subsystem M(u) of MW is projective iff there exists a j (u) c W with (i) uw1 = UW2 iff j(u)w1 = j (u)w2 and (ii) u = uj(u) PROOFo Asstule that M(u) is projective. Then, for the epic morphnis; e: MW M(u) which is determines by e: W > uW: w - uw we have a morpliism j M(u) MW with euj being the identity morphism of M(u). Now, since j must be monic, we have (i), and since e j is the identity of M(u), we have u = (euj)(u) = uj(u) On the other hand, assume that there exists a j (u) e W with properties (i) and (ii), The function j: uW - j(u) W: uw - j(u)w is well defined as it follows from (i). Obviously it determines a morphism j M(u) --- MW By (ii) we have that J e M1 (U) -- MW. M (u), where eu(w) = uw, is a splitting sequence. tience M(u) is projective. For any splitting sequence

125 j e M(u) IMw IM(u) we ha-ve that j is monic. Hence M(u) is isomorphic to M(j (u)) = j (M(u)) If, in particular, we have e(w) = uw, then j(u)j(u) = j(uj(u)) = j(e(j(u)): j(u) That is, j(u) is an idempotent of W, and M(u) is isomorphic to M(j(u)) On the other hand if u is an idempotent of W, then Proposition 10,9 implies that M(u) is projective. Note that properties (i) and (ii) are satisfied by u = j(u) iff u is an idempotent of W. In conclusion, we have proved PROPOSITION 10.10. A W-semimodule P is monogenic projective iff it is isomorphic to a subsystem M(u) of MW, where u is an idempotent of W o An alternative proof of Proposition 10.10 can be derived from the isomorphism o W* (cf. Corollary 4.2) and Corollary 10,8, Observe that if P - MW c-p is a splitting sequence, then je M: WI — MW is an idempotent of W* As for the characterization of MW, we can modify now Proposition 8,4~ Lemma 8,3 and the proof of Proposition 8.4 imply PROPOSITION 10.11. FW is the largest monogenic projective object w of $ iff W is unit-regular. PROOF, Note that if uv = 1, then vu is an idempotnet of W o By Proposition 10,10, th-e proof of Proposition 8,L4 yields the proof of Proposition 10,11. TFor example, if 1 is the only idempotent of W, then W\ is

126 unit-regular, Yet, MW is distinguished in SW by being a monogenic projective object of $, as it is implied by Proposition 10.10 and Lemma 8,3. 11, The generators of sW We recall from the introductory discussions of this chapter, the following definition. DEFINITION 11,1. An object G of a category C is called a generator iff C(G,): C >$ is an embedding. Thus, C is a generator of C iff for any two morphisms gl~g2 A — >B of C, if the two functions [~(G,-)](gl): C(G,A):C(GB): f >glf, and [~(C,-)](g2): ~(G,A) >C(GB): f — g2f are identical, then gl = g2 LEIHMMIA 11.2, MW is a generator of $ o $W PROOF, By Lemma 4.1, we have the natural equivalence p: S -- (Mw,,-) and from Section 3, we know that S is an embedding. Wle prove now the general statement: if T1,T2. C1 -C2 are two naturally equivalent functors and T1 is an embedding, then T2 is also an embedding. So let p: T1 >T2 be a natural equivalence, and assume that for some morphisms gl'g2: A - B of C1, we have T2(gl) = T2(g2) v Then for the commutative diagram of p, evaluated once at gl and once at g2 we get

127 -1 -1 p (B)T1 (gl) (p (A)) = T2 (gl) = T2(g2) = p (B)Tl (g2) (p (A)) and therefore T1(gl) = T1(g2), But T1 is an embedding, hence gl = g2 Hence $W(Mw,-) is an embedding, and therefore MW is a generator of $ In order to characterize the generators of $, we follow here Freyd's discussion [8; pp.68-69] on the generators of abelian categories which admit sums, In particular, we find that like in categories of modules W I Let G be any object of $. For any object A of $, we denote by (G,A)oG the W-semimodule $W(G,A).G which can be defined as the sum of the family {Gff f= G and f C S (G,A)} Explicitly, (G,A) G is defined by S((G,A).G) = $ (G,A)xS(G) and (f,s)ow = (f,s.w) for all f C $ (G,A) and w C W. N6te that $W(G,A) may be empty even if G and A are not empty. For any f ~ S (GA) we have the canonical inclusion jf: G f(GA).cG determined by jf(s) = (f,s). Since (G,A)'G is a sum object, its sum diagram (i.e., the family {jf: G;(G,A).G} ), guarantees the existence of a morphism ~(GA) (GA)'G A, determined by the family SW(G,A) of all the morphisms f: G —-A Hence we have for any morphism f: G -A the equality a(GA)3f =

128 We prove now an analogue of a proposition of Freyd's [8; Prop. 3o36]. PROPOSITION ll,,3. (Freyd) A W-semimodule G is a generator of SW iff the morphism a (G,A): (G,A)G >A is epic for all objects A of $W 0 PROOF, Let flof2 ~ A >B be any two morphisms of $ W Assume that for all f. G- A we have flf = fl (GA)jf f2a(G,A)jf' f2f ~ Then, for all f G - >A and for all s ~ S(G), since jf(s) = (f,s), we have [fla(G,A) ](f9s) = [f2a(G,A) ](f's).'Hence9 if for all f: C. —A we have flf = f2f, then fl (A) = f2a (GA) ~ On the other hand, since a(G,A)jf = f, the equality fl (GA) = f2a(G A) implies that for all f: G >A, flf = f2f e Thus fla(G,A) = f2 (G,A) iff [W(G,-)](f) = [$W(G,-)](f2); ioeo, a(G9A) is epic iff $ (G,-) is an embedding, that is, iff G is a generator0 Proposition 113 implies COROILLARY 11.4d A W-semimodule G is a generator of $W iff MW splits through G W PROOF, We prove first that if C is a generator of $, then there exists an epic morphism e: G,MW o Since MW is projective, it follows that FMw splits through G o If C is a generator of $W then ar. u: (G,Mw)G Fw

129 is epic. Hence there exists a state (e,so) of (G,Mw).G (i.e,, e: G C MW and so C S(G) ) such that a(G,M ) (es) = 1 Thus e(s) =[a j]( = a (e,s) e(so)= [ (Gw) je] (s) o(GM W) ) which proves that e: — MW is epic. On the other hand, assume that there exists an epic morphism e: G; LW We prove that for all W-semimodules A, a(CGA) is epic, For the empty W-semimodule 0W, we have that a(CG,;0): (G,0w).G — 0W is epic since it is the identity morphism of 0W X Let A be any non-empty W-semimodule. We want to show that for any s C S(A) there exists a (f,s') c S((G,A).G) such that O(G,A)(fs') = s * Since a (GA)(fs') = f(s'), we want to find a morphism f: G- A and s' S (G) such that f(s') = s, So let s' S (G) be the state of G for which e(s') = 1, and let f: MW - A (i.e., fS(l) = s ), then f e G —-A is a morphism for which [fse](s') = f (1) = s Hence (r,A) is epic and, therefore, G is a generator of S We can express now another characterization of the unit-regular monoids which is equivalent to Proposition 8,4 or Proposition 10.11, as follows,

130 PROPOSITION 11.5. The monoid W is unit-regular iff all the splitting sequences of monogenic generators or of monogenic projective objects in $W are made of isomorphisms only. We note in passing the "polarity" between the monogenic projective objects of $W and the generators of $, Ones are the objects of $ which split through MW and the others are the objects of S for which MW splits through them. Moreover, every summand of a projective object in $W is projective, and as one can easily prove, every sum of a generator (of any category) with any object is also a generator0 12. The endomorphism monoids of monogenic projective W-semimodules We give here an explicit description of the endomorphism monoid E(MI(u)) of the morphisms M(u) -M(u), where u is an idempotent element of W and M(u) is the subsystem of M I determined by uW 0 Let h M(u) >- (u) be any homomorphism and suppose h(u) = uv for v X W. Then v has the property that uwl = uw2 implies uvwl = uvw2 for all Wl,W2 C W; for h(uw) = h(u)w = uvw. Conversely, if v satisfies the requirement that uw1 = uw2 always implies uvwI = uvw2, then the function hv: uW-uW: uw -uvw determines a homomorphism hv: M(u) —-- M(u) o Clearly h = h iff V1 V2 uv1 = uv2 o So let us denote by R(u) the set of all elements v of W1 such that uw1 = uw2 always implies uvw1 = uvw2 o Assume now that u is an idempotent of W. Then it is easily verified that R(u) is a submonoid of W, uR(u) is a subsemigroup of W with u as an identity element, and that v -uv establishes a surjective homomorphism of monoidso

131 c: R(u) —-uR(u) X PROPOSITION 12.1, Let u be an idempotent of W. The function r: uR(u) W$(M(u)*,M(u)): uv:h V where h is determined by V hv: uW OuW: uw -uvw, determines an isomorphism of monoids r: uR(u) -— E(M(u)). PROOF. By our previous observations we know that r is a bijection, Furthermore (and here we give a proof to the effect that uR(u) is a monoid), for any v1,v2 c R(u), we have uv1uv2 = uv1v2 ~ For since vl C R(u) and uv2 = u(uv2), we must have uvlv2 = uvluv2 This yields h h = h vI v2 v1 v2 Thus the endomorphism monoid of a monogenic projective W-semimodule is isomorphic to a homomorphic image of a submonoid of W. If we force the monogenic projective W-semimodules to have endomorphism monoids isomorphic to W in a simple fashion, we end up again with unit-regular monoidso As examples of this phenomenon, consider the following lemmata, LEMMA 12.2. If W does not have a proper submonoid V with a surjective homomorphism onto W, or if W does not have a proper submonoid isomorphic to W, then W is unit-regular. PROOF, Assume that vlv2 1 holds in W. Then by Lemma 8o3, M(v2v1) is isomorphic to MW and v2v1 is an idempotent of W o Hence

132 (v2vl)R(v2vl) is isomorphic to W But W does not have a proper submonoid with a surjective homomorphism onto W, hence R(v2vl) = W o Thus v2V1v = 1 for some v e W, and therefore v2v1 = 1 o COROLLARY 12.3. Every finite monoid is unit-regular. REMARK, Note that one can prove directly (ioe., without reference to semimodules) that every finite monoid is unit-regular. LEMMA 12,4o If for any idempotent u of W we have uR(u) = uW, then R(u) = W and W is unit-regular. PROOF, We prove first that the equality uR(u) = uW is equivalent to R(u) = W o So let w be any element of W, and we want to show that if uR(u) = uW, then for any Wl,W2 c W, uw1 - uw2 implies uwwl = uww2 Now from uw c uR(u) it follows that uw - uv for some v e 11(u) o Hence if uw, = uw2, then uvw1 = uvw2; i.e., uww1 = uww2 Obviously, if R(u) = IV then uR(u) = uW We prove now that if for any idempotent u of W, R(u) = W, then W is unit-regular. So assume that v 1v2 1 holds in W, then v2v1 is an idempotent of W, and therefore R(v2vl) = W ~ We prove now that V2 = v2v2v1 holds in W From R(v2v1) =W and v2v1v2v1 = v2v1 we infer v2v2v1= V2v1 2 V2)V2V1 v2v1(v2) 2, because vlv2 = 1. But, because of the same reason, v2 = v2v2v1 implies 1 Vl = - V1V2V2V1 V2V1, and in conclusion W is unit-regular. LEMMA 12o5. If for any idempotent u of W we have uR(u) = W,

133 then 1 is the only idempotent of W, and W is, therefore, unit-regular, PROOF. From uR(u) = W it follows that uv = 1 for some v z W If, in addition, u is an idempotent, then U = u1l UUV = UV = 1, 13 On the characterization of M as a monoAenic rojective generator of $W Let us say that W satisfies the mO.P property iff MW is distinguishable in $W by being a monogenic projective generator in $W. In this section we derive a structural characterization of the monoids with the m.p.g. property. Unfortunately, there are monoids which do not satisfy the m.p.go property, and the problem whether MW is distinguishable in SW for any monoid W, is open. We know frommCorollary 11.4, that a subsystem M(u) of MW is a generator of SW iff there exists an epic morphism e M(u) -4MW Assume that e(u) = v, then we have (i) vW W, and (ii) uw = uw2 always implies vw = vw2 Conversely, if there exists a v C W with these two properties, then property (ii) insures that e uW W: uw -— vw determines a morphism e: M(u) -MW which is epic by property (i). Furthermore, M(u) is isomorphic to MW iff there exists a v e W with vW = W and such that for any wlw2 C W, uw1 = uw2 is equivalent to vwl = vw2 1 We prove now

134 PROPOSITION 13,1, A W-semimodule is a monogenic projective generator of $W iff it is isomorphic to a subsystem M(u) of M with (i) u2 = u and (ii) there exists a v e W such that vW = W, and vu = v PROOF. Let M(u) be a subsystem of MW with properties (i) and (ii). From (i) it follows that M(u) is a monogenic projective object of SW Define now the function C: uW —W uw — W, where v e W is the element of W whose existence and properties are stated by (ii)o Since vu = v, it follows that e is well defined and that it determines a morphism e: M(u) — I?, which is by property (ii) (i ec vW = W ) an epic morphismo Hence M(u) is also a generator of S On the other hand, if G is a monogenic projective generator of $ then it is isomorphic to a subsystem M(u) of MW, where u is an idempotent of W, and is such that there exists an epic morphism e I (u)- -- W M Assume that e(u) = v, then vW = W, and since uu = u we have vu = e(u)u = e(uu) = e(u) = v + From our observations before Proposition 13a1, and from Proposition 13,l, follows now PROPOSITION 13,2o A monoid W satisfies the mop.go property (ioe., Nw is distinguishable in SW by being a monogenic projective generator of $ ) iff W satisfies the following condition: for any idempotent u of W, if 1F there exists a v C W with vW = W and vu = v,

135 then 2, there exists a v1 c W with v~W = W and vVu = v9 such that vrw1 = v9w2 always implies uw — uw2 0 PROOF. The condition 1o is equivalent to M(u) being a monogenic projective generator of SW, and the consequence 2o is equivalent to M(u) - being also isomophic to MW 6 We prove now that the class of all monoids which satisfy the m~pg, property properly includes the class of all unit-regular monoids, and that it is a proper subclass of all monoidse PROPOSITION 13,3, If W is unit-regular, then W satisfies the m opogo property~ PROOF, Let u be an idempotent of W. and v c W such that vW = W and vu v o From vW = W it follows that uv = 1 for some w E W, and since W is unit-regular, we have wv = 1 as well. Assume that vw1. vw2 holds for some wl w2 c W a Then we have uw1 = uwvw 1 =uwvw2 =uw2 Hence vw1 = vw2 always implies uw1 = uw2 o Hence by Proposition 13,1 and the discussions preceding it, every monogenic projective generator of $W is isomorphic to MW o On the other hand we have LENM1A 13,4, If every idempotent of W is a transform of 1, then W satisfies the mopg property. PROOF~ By Lemma 803 we have that if every idempotent of W is a transform of 1 then every monogenic projective object of $S is isomorphic to HW

136 For example, let W be the monoid generated by the two elements a and b with the single relation ab = 1 o Then the elements of W are all of the form b lak2 where kl,k2 2 0, Simple arithmetic shows that kk k k the idempotents of W are all of the form b a, and since a ob = 1 holds in W, all the idempotents of W are transforms of 1 o Clearly W is not unit-regular, for ba f 1 In conclusion, we have that the class of all monoids with the m~p.g. property properly includes the class of unit-regular monoidso Another example, suggested by Ao Brumer, shows that there are monoids which do not satisfy the mo.pg, property,, Let W be the monoid with u,v, and w as generators, and with the following relations which insure by Proposition 131l that. M(u) is a monogenic projective generator in SW U = U $ vW = 1, V = V o Combinatorial arguments show that x'y = 1 holds in W, for some y C W, k iff x = v for some k > 0; and furthermore, if xoy = 1 holds in W, then xowov = xol holds as wello But wv Z 1 in W, and therefore, by our observations that precede Proposition 13ol, we infer that M(u) is not isomorphic to MW in $ W Hence W does not satisfy the mpogo property. We do not know, for this particular W, whether MW is distinguishable in SW at all. We conclude this section, and this part of the paper, with a review of some well known monoids which are unit-regular0 To begin with, we note without a proof that the class of unit-regular monoids, and also the class of monoids whose idempotents are all transforms of 1, are closed under direct and free products of monoids (ioeo, under the products and sums in IM, the category of monoids), Now, the cancellative monoids (of either side) are obviously monoids with 1 as their only idempotent, and there

137 fore, they are unit-regular, Thus the groups and the free monoids are unit-regular, Needless to say, the abelian monoids are unit-regular, andil we know by Corollary 12,3 that all the finite monoids are unit-regular,

PART III APPLICATIONS TO AUTOMATA THEORY 138

INTRODUCTION TO PART III Let us summarize those of our results whose relevance to automata theory will be discussed in this part of the work~ If W is a monoid which satisfies the mpgo property (e0g,, if W is unit-regular), then Aut($W) is isomorphic to Aut(W) and to the group of the automorphisms of $W which are induced by the automorphisms of W o We'recall' (cf, Part II, Chapter II, Section 6) that the automorphism of SW induced by a s Aut(W) is the automorphism T $-'- W defined as followso For any W-semimodule A 9 the W-semimodule T (A) is defined by S(T (A)) S(A) and XT (A)(slw) (sa(w)) For any morphism f A B of $ D the morphism T (f):T (A) —-T (B) has the same underlying function as f o A —- B The particular isomorphism that exists between Aut($W) and the group A of these automorphisms of SW induced by Aut(W) g whenever MW is distinguishable in W, implies the following characterization of the categorical classes in $W (cfu Part II, Chapter II, Theorem 7,4), A natural class of morphisms of SW is categorical iff it is closed under R. In particular, a typital class of W-semimodules (ie,, a property of isomorphism types in $W) is categorical iff it is closed under /0 In this part of this work, we examine the significance of these results to actual automata theory, First we note that most of the monoids encountered in automata theory, either as input monoids or otherwise9 are unit-regularo For example, in the theory of finite automata [2, 4, 6, 9, 139

140 10, 14p 15, 1.6 17,, 19] mostly free monoids are considered as input monoidso Sometimes direct products of free monoids are considered, for example in the study of multi-tape automata [6], and even cancellative monoids, as in Ginsburg's [9] theory of abstract machineso Thus, it i.s meaningful to wonder about the significance of our study of S to actual automata theory,, A support for the significance of our results should consist at least in the examination of the following problems: 1. In the course of study in automata theory, several snecific nroperties of automata are defined and studied. We will refer to these properties as the actual properties of automata, We will be concerned with the following double edged problem, Are the actual properties of automata categorical? Are there, or could there be, any property of W-semimodules which is, or may be, significant for the development of aultomata theory, and yet not categorical? We will discuss these problems in Chapter I. 2, Categorical algebra is not only a convenient language (in the broad sense of this term) for expressing certain ideas0 While there is quite a common agreement on the fact that the notions of category and functor provide a convenient language for many branches of algebra, the realization that categorical algebra ts also a useful tool of mathematical study is still debatefulo It is interesting to note that certain authors are quite ambivalent about this point, For example, MacLane writes "The notions of category and functor provide not profound theorems, but a convenient language'" [14~ po33], Also, "By now it is expected that each definition of a type of mathematical system be accompanied by a definition of the morphisms of this system~" [14; po34], and later, in the same page, while refering to categories and functors, he writes "vThey have proved useful in the formulation of axiomatic homology, etc "

141 Such an ambivalence cannot be but expected from one of the fathers of categorical algebra, As for the usefulness of the categorical study of $sV to automata theory, it should be clear that the main goal of this particular work is not to prove that categorical algebra methods or "categorical thinking" are useful in automata theory~ We wanted to determine what properties of W-semimodules can be determined by the algebraic properties of the composition of the homomorphisms of W-semimodules., Still we would like to indicate the advantage of using categorical methods in the development of automata theory, Only experience and the future developments of automata theory can judge whether categorical algebra methods will be useful in automata theory as they have been proven to be so in many branches of mathematics (cfo [13; pol,02]), In Chapter II we give an example of a categorical analysis of some basic properties of strongly connected and abelian semimodules which are due to Fleck [7] and iiWeeg [18]o It is the author's belief that categorical algebra methods applied to the study of automata are the known best methods suitable for the understanding of the mathematical ideas that take place in automata theory.

CHAPTER IO ACTUAL AUTOMATA THEORETIC PROPERTIES OF SEMIMODULES During the development of automata theory, various properties were introduced because of their interest or their usefulness for the study of automata, Here, we will examine four types of such properties, and indicate the proof that they are all categorical in the categories of the form $ provided that MW is distinguishable in S W From now on we assume tacitly (unless stated otherwise) that we are concerned only with input monoids WI for which MW is distinguishable in $ From Theorem 7o4 of Part I we know that a class K of W-semimodules is categorical iff (i) K is closed under the automorphisms of $ which are naturally equivalent to the identity functor of $, and (ii) K is closed under X, the automorphisms of $W induced by Aut(W) Hence, in order to prove that a given class K of W-semimodules is categorical, it is sufficient to prove two properties of K o By proving first that K is closed under the isomorphisms inside $S (i.eo, that K is a typical class in $ ), we prove that K is natural. Any automorphism which is naturally equivalent to the identity functor of maps every object onto an isomorphic object6 If in addition to this we prove that K is closed under I, we can infer that K is categorical~ In what follows in proving that any given class of W-semimodules is categorical, we indicate, therefore, only that K has these two propertiesO 1 Gr_ h theoretic pppernties of semimodu esh The category I)X of directed graphs is defined as follows0 An object G of DG is a system of the form 142

143 G <N (G) 0Ad (G)> where N(G) is a set, the set of nodes of G, and Ad(G) is any subset of N(G)xN(G), the set of edges of G o The morphisms of DG are of the form f. C1 G2 where f v N(G1) >N(G2) is a function which "maps A(G1) into A(G2) " in the sense that for any (U1,U2) E A(G1) we have (f(ul),f(u2)) E A(G2) The composition rule of DG is evident, and we have the obvious forgetful functor N f DG —+$ We define a functor UG $ --- DG which maps W-semimodules onto their "underlying graphs", as follows. For any W-semimodule A, the directed graph UG(A) is defined by N(UG(A)) = S(A), and (sls2) e Ad(lUG(A)) iff s2 = slow for some w E W Since every function f: S(A) >S(B) which determines a homomorphism f o A —-— B of W-semimodules determines a morphism of XG as well, we define UG(f) o UG(A) -UG(B) to be precisely the morphism of DG determined by the underlying function of f: A -B o We indicate now the proof of PROPOSITION Llol For any typical class K of directed graphs, the class UG (K) of all W-semimodules A with UG(A) in K is a categorical typical class in $W PROOF. Since for any isomorphism j of W-semimodules UG(j) is an isomorphism in DG, we have that the class UG (K) is natural in $W

144 Since tile automorphisms of SW induced by Aut(W) obviously do not affect the "underlying graphs" of semimodules (that is9 we have the equality "COT = UG for all a C Aut(W) )9 the class UG (K) is also closed under Hence it is categorical typical in S o Examples of actual automata theoretic properties which are covered by this proposition are the following, 1, Set theoretic properties, Every typical class of K of sets in S (ioe,, properties of sets which depend only on cardinalities) determines a typical class of directed graphs with set of nodes belonging to K ) Hlence every property of W-semimodules which depends only on the cardinality of their sets of states (e.g., infinite, finite, etc,) are categorical in $W 2. Connected semimoduleso A semimodule A is called connected iff UG(A) is a connected grapho A directed graph G is called connected iff the transitive closure of the symmetric reflexive closure of the binary relation Ad(C) is the total relation N(G)xN(G) on N(GC) o Clearly, the class of all connected directed graph is typical in DC H Hence the class of all connected W-semimodules is categorical typical in S 3, Strongly connected semimoduleso A W-semimodule A is called strong1 connected iff for any s1,s2 c S(A) D there exists a w C W such that s2 = slow Clearly, a semimodule A is strongly connected iff U(;(A) is strongly connected, that is, iff Ad(UG(A)) is the total binary relation on N(UG(A)) e Now, since the class of all strongly connected directed graphs (i~eo, all complete directed graphs) is obviously typical in PCG, it follows that the class of all strongly connected W-semimodules is categorical typical in $ o 4$ Semimodules with a reset state, A W-semimodule A is said to

145 have a reset state iff there exists an so C S(A) such that for any s E S(A) there exists a w e W, possibly depending on s, such that sOw = so. Clearly, A has a reset state iff UG(A) has a node s such that for any node s of UG(A), (s,s) C Ad(UG(A)). By analogy, we say in this case that s is a reset node of UG(A) o If s is a reset node of a directed graph G1 and j: G1 -G2 is an isomorphism in DG, then j (s) is obviously a reset node of G2, Hence the class of all directed graphs with reset nodes is typical in DG, and, therefore, the class of all W-semimodules with reset states is categorical typical in $W o 2. Monoid theoretic properties of semimodules Recent developments in automata theory (eog0 [12, 19]) bring to light the importance of the transition monoid associated with a finite automaton,'or any W-semimodule A, the transition monoid Mon(A) of A is defined as the monoid of all the functions of the form A A ~ S (A) -S(A): s -— sow A A where T = Tr iff for all s e S(A), sow = sow2 Here we use W1 W2 1 s~wA the "right-wise" notation of functions and denote by (s)Tr the image w sow of s under T Clearly we have A A A (s)t T (s)T r w1 2 w2 and therefore, every W-semimodule A determines a surjective homomorphism of monoids T: W —- >Mon(A) iA A which is determined by t (w) = T. Furthermore, for every epic morphism

146 e A- A B of S W there exists a unique surjective homomorphism of monoids Mon(e): Mon(A) --- Mon(B) with TB = Mon(e)oTA The homomorphism Mon(e) is determined by A B [Mon(e)] (wA) = T, and it is an isomorphism of monoids whenever W W e. A -B is an isomorphism in SW. (Note that for any two epic morphisms ele2 ~ A A B, we have Mon(el) = lon(e2) o) Since also for any a E Aut(W) the function a A T((A) ~ Mor n(A) >Mon(T (A)) T: wT a(W) determines an isomorphicm of monoids r: 1Mon(A) -Mon(T (A)), we infer the following expected proposition, PROPOSITION 2ola If K is a typical class of monoids in 1 the category of monoids, then the class of all W-semimodules A with Mon(A) belonging to K is categorical typical in o A very important class of actual properties of automata is covered by a corollary to Proposition 2o1, Let K be a typical class of groups in C D the category of groups, Denote by K the class of all monoids M with the following property: if G is a subsemigroup of M which is a group, then G belongs to K o Since every subsemigroup of M is mapped by an isomorphism j of H onto a subsemigroup of the range of j, and every image of a group under a homomorphism of semigroups is also a group, we infer that K is typical in IM o Hence we have

147 COROLLARY 2,2, Let K be any typical class of groups in C The class of all W-semimodules A with Mon(A) belonging to K, where K is the class of monoids with group-subsemigroups in K, is categorical typical in $ For the significance of this classification of the W-semimodules, the reader is referred to the literature (e.g., [12, 19]). Other properties of semimodules which are covered by Proposition 2.1 are the following (cf. [7, 18]). 1o Abelian semimodules. A semimodule A is called abelian iff Mon(A) is an abelian monoid. Since, obviously, the class of all abelian monoids is typical in M, the class of all W-semimodules with abelian transition monoids is categorical typical in $W. 2. Semimodules with a group action. A semimodule A is said to have a groupaction iff Mon(A) is a group. Obviously, the class of all W-semimodules with a group action is categorical typical in $ o 3. Analytica! constructions in,$W The problems of composition and decomposition of automata, and hence the problem of construction of automata from components, seem to be essential problems of automata theory, even if it is only recently that they have been seriously attacked, Unlike in group theory or other areas of algebra, these problems are not raised by the desire to understand the objects under study, but by the concrete interpretations and applications of the theory; i.e., by machine design and construction. The semimodules are too poor in structure for studying composition of automata which are strongly involved with outputs, However, they are rich enough for the study of analytical construction to be defined presentlyo Certain recent results in automata theory [10, 19] indicate that evert decom

148 posability of automata with output can be reduced in some significant cases to properties of the semimodules involved. We define analytical constructions as multifunctors on SW (i.e., on some power (SW)& of SW where 4 is any ordinal) which do not depend very much on the particular labeling of the input monoid W a More precisely DEFINITION 310. By an analytical construction on S we mean any functor T o ($W) $W, where ($W)~ is the C-th power category of $W and 4 is any ordinal, such that for any a e Aut(W) there exists a natural equivalence T ~ T oT -— >ToT& a a a where TC: ($W) - ($W)i is the obvious power of Ta: T (x,y,...) * (Ta (x),T (y),oo) If 4 is finite, then we say that T is a finitary analytical construction. It is easy to verify that functors derived from (finitary) analytical constructions by means of substitutions are also (finitary) analytical constructions~ This follows directly from the properties of Nat (cfo Part I, Chapter I, Section 6). The properties of Nat imply also that any functor naturally equivalent to an (finite) analytical construction is also an (finite) analytical construction. For example, products and sums in $W yield multifunctors which are analytical constructions. The subset construction employed in [16] in the reduction of non-deterministic automata to deterministic automata, when it is applied to sW, yields

149 a functor p: $W SW which is a finitary analytical construction~ The explicit definition of the subset construction functor P is as followso For any W-semimodule A, the W-semimodule P(A) is defined by S(P(A)) = {T o TOC S(A)} and ToW = {sow: s C T} o For any morphism f: A -B, the morphism P(f): P(A) P(B) is the homomorphism determined by the obvious function P(f) * S(P(A)):-S(P(B)): T ){f(s) ~ s s T}, Every set T determines two functors T. $W W and T:W W':$ - and: > which map every W-semimodule A onto AT and ToA respectively (cfo Part II, Chapter I, Section 2)o Let us call these functors the T-_power and the T-multinle functorso Clearly both these functors are analytical constructions for any set T o Thus every substitution combination of sums, products, power and multiple constructions and subset construction functors yields only analytical constructions on S o In order to determine whether certain problems related to analytical constructions give rise to categorical predicates, we prove the following 1 emma0 LEMIMA 3o20 If T: (S ) $ is an analytical construction on $ then for every automorphism F of $, the functors FaT and ToF are

150 naturally equivalento PROOF. By our tacit assumption on W, F is naturally equivalent to T for some a c Aut(W) O Hence FoT is naturally equivalent to T oT, and ToFP is naturally equivalent to ToTE Since T is analytical, FoT and ToF are naturally equivalent0 COROLLARY 303o Let T ( () ) — be any analytical construction, and K be any categorical typical class in $ o Then the class of all S-tuples (A1,A2,ooo) of W-semimodules such that T(A1,A2,oo.) belongs to K is categorical typical in $ 0 The examples of analytical constructions on W discussed above have the property that for any a E Aut(W), T oT = ToTE O Let us call a a such constructions regular, The regular constructions have the following property, LEMMA 3040 Let T o (S ) -$W be a regular construction0 If F $ -*$W is a functor with a natural equivalence To F ->T O for some a ~ Aut(W) O such that T(Tr) = T 9 then FoT = ToF PROOF0 For any E-tuple (A,1A2,10o) of W-semimodules, the family T(T (A1),r (A2) o0)oT(T(A1),T(A2)0o) ~ [FoT[(A1,A2o) + T(F(A1)F(A2).1.) ) is the identity natural transformation0 COROLLARY 3T5A Let T: ($S )-$ be a regular construction on $ such that for any automorphism F of S there exists a natural equivalence F ~ F T~ for some a c Aut(W) with T(Tx) = ToT o Then

151 the class of all 5+l tuples (A1,A2 2 0TT(A1A,A2, o0)) is a categorical predicate in $ o While it is easily verified that all the specific analytical constructions discussed above are regular, it is not known whether they satisfy the hypothesis of Corollary 3,5,.4_ Eventp.erties of semimodules Our terminology here is adapted from the study of finite automata as recognition devices (e0g,, [2, 4, 6, 15, 16, 17]). These automata are finite semimodules over finitely generated free monoids provided with a specification of initial and final states, Even though we avoid assigning designated states to semimodules, we can still reduce some properties of automata viewed as recognition systems, to properties of semimodules, A similar procedure can reduce some properties of sequential machines [4, 9, 12] to properties of semimodules. In this section we will briefly discuss some properties of semimodules which have some bearing on their potentialities as components of recognition deviceso Generally and vaguely speaking, the event-properties of W-semimodules are those properties which are involved with the manner by which W is acting on the states, Hence, unless they are involved with properties of the actions of W which are invariant under the automorphisms of W, they would not be categorical0 For example, let w be any element of W which is not kept fixed under all the automorphisms of W o Then the class of all W-semimodules A for which there exists an so e S(A) such that sow = so for all s c S (A) is obviously not categorical. On the other hand, let E be a subset of elements of W which is closed under all the automorphisms of W (eogo, E = W )a Then the class of all W-semimodules A for which

152 there exists an s E S(A) and wo c E such that for all s e S(A) we have sow0 = s, (i0e., w0 is a reset input of A ) is categorical in $ We concentrate now on properties of W-semimodules regarded as potential recognition systems for subsets of W o A W-semimodule A is said to potentially define the event E c W iff there are so e S(A) and F c S(A) such that E = {w s W c F} A family K of subsets of W is said to be symmetrical iff for any E E K and any a c Aut(W), a(E) C K C PROPOSITION 4a1l Let K be a symmetrical family of subsets of W Then the class of all W-semimodules which potentially define events belonging to K is categorical typical in $. Similarly, the class of all W-semimodules which potentially define only events of K is also cater gorical typical in $W PROOF, Isomorphic semimodules behave identically with respect to potential definition of events. That is, if j o A —- B is an isomorphism in S;, s C S(A) and F e S(A), then {w ~ XA(So,w) C F} = {w: B(j(s0o)) w j(F)} o If a E Aut(W), then we have a({w A(so,w) C F}) = {w:XT ()( ) C F} The following are some examples of properties of W-semimodules which are related to actual event properties of finite automata and which fall under Proposition 4 1o

153 1, Ideals in W, A subset E of W is said to be a left ideal in W iff for any w1 C W and w2 c E we have w1w2 cE. Right ideals are defined similarly, A W-semimodule is said to be potentially definite iff it potentially defines a finitely generated right ideal in W 0 Since the family of right ideals in W is obviously symmetrical, the class of potentially definite W-semimodules is categorical typical in $ e Similarly, potentially co-definite semimodules are those which potentially define left-ideals, and the class of potentially co-definite W-semimodules is categorical typical in $W 2, Infinite and finite recognitions. A W-semimodule A is said to have a potentially finite recognition (respectively, infinite recognition) iff it potentially defines a finite (respectively, an infinite) subset of W For some studies of finite automata, with respect to ideal recognitions and finite recognitions, the reader is referred to the literature [15, 16]. Out last example is related to the notion of star-height of regular events introduced by Eggan [6]. 3. Potential star-height and star-height of finite semimodules over a finitely generated free monoidd Let W be a finitely generated free monoid. A W-semimodule A is said to have the potential star-height k iff A potentially defines an event E with star-height k (Eggan [6]). A is said to have the star-height k iff k is the maximal potential star-height that A has, Since the family of subsets E of W with star-height k is symmetrical, we have that the class of all W-semimodules with a potential star-height k, and the class of all W-semimodules with star-height k, are both categorical typical in $ We now can make some concluding remarks with respect to our first problem discussed in the Introduction to Part I IIo The categorical

154 predicates in $W are those predicates which are not affected by an automorphism of W o We reviewed several actual properties of automata and proved that they are categorical in $ d However, with respect to the other side of the fence, we should be aware of the following two facts0 First, a significant part of automata theory is concerned with automata with output, Consequently, the categories $W are not suitable for the representation of such automata, One must consider and examine categories whose objects are the automata under study. Finally, even if we are interested only in semimodules, the significance of the non-cate. gorical properties of W-semimodules is not obvious. Sometimes, the input is dictated in such a way that we are not free to relabel it under automorphisms, In this case, it is very probable that we have to deal with nonecategorical properties of semimodules. The usual case in automata theory is, however, that only properties which are preserved under automorphisms of the input monoid are studied,

CHAPTER II,: A CATEGORICAL VERSION OF THIE STUDY OF SEMIMODULES In this chapter we indirectly discuss our second problem: how useful categorical algebra is in the understanding and in the study of automata? The answer to such a question is not a matter of proof, What we plan to do is to show by means of a brief example that once the right questions are asked with respect to semimodules, categorical algebra can serve as a good guide in the search for their solution. Roughly speaking, a categorical study of any mathematical domain is any study which is directed towards a solution of any kind of problem via the study of functors and natural transformations. The example that we are going to discuss here is quite elementary from the point of view of categorical algebra, because it does not rise above the level of the notion of functor:. Yet, it seems that in spite of the effort in "categorizing" the arguments of a given study (and not to mention the effort in becoming acquainted with categorical algebra), we get a better understanding of the mathematical phenomena under study~ In addition to the categorical approach, we want to illustrate a cater gorical interpretation of the customary notation used to refer to automata or to semimodules. This interpretation is based on our most useful lemma in this paper, From Lemma 4.1 (in Part II, Chapter II, Section 4) we have the equality gfs fg (s)' valid for any morphism g: A >B of S and any s S(M), and where f M IW-AA is given by fs(l) = s, and f):MW B is given by f ()() = s * From this equality we have inferred the equality ff = f S W SoW 155

156 valid for all f MW- A and f ~ b-W MW, and the equality f f f W1 W2 w1w2 valid for any f f: MW > MW. These equalities lead us to change w12 our notation as follows, We will identify any s C S(A) with f ~M —W A oA Hence w c W will mean also f: MW -M> W For any morphism f A — B and s e S(A) we will denote by fs, either the state f(s), or the morphism ff. Under this change of notation, XA(s,w) will be denoted by sw, of course. Any function f: S(A) >S(B) will be taken as a function f: $ (mIvA) - $ (MW B), but once it is recognized that it is an underlying function of a homomorphism (i.e., f(sw) = f(s)w ), it will be identified with f: A — B. The above listed equalities prove that this change of notation is consistent, and in the forthcoming discussion we will hardly mention its existence6 Above all this we reserve the right to use the old notion without any previous warning. 5. A categorical reformulation and examination of Fleck's theory of perfect automata In this section we reformulate some of Fleck's [7] results concerning perfect automata (cf. also Weeg [18]). Perfect semimodules are defined as strongly connected abelian semimodules, It is proven that if A is a perfect W-semimodule, then the transition monoid Mon(A) of A is identical with Aut(A), the automorphism group of A in W, and it has the same cardinality as S(A). Furthermore, it is proven that a perfect semimodule is a product of two semimodules B and C iff Aut(A) is a product of Aut(B) and Aut(C). All these results are due to Fleck [7],

157 DEFINITION 5.10 A W-semimodule A is strongly connected iff every s E S(A) is epic. The projectivity of MIW implies the equivalence of this characterization with the customary definition of strongly connected semimodules (cfo Chapter 1, Section 5). For the projectivity of Mw1 means precisely that for any sl E S(B) and any epic f: A >B there exists an s2 c S(A) with fs2 = s1 i Hence, if A is strongly connected, then for any sl,S2 s S(A) there exists a w c IV with SlW = s2 o On the other hand assume that this holds for a W-semimodule A and let s c S(A). Assume also that for f lf2 A -B we have fls = f2s; hence for all w E W, f1sw = f2sw o Therefore fl = f2, which implies that s c S(A) is epic, The projectivity of M1W also implies that if A is strongly connected and e: A —>B is epic, then B is strongly connected. For let s2 e S(B), then there exists an s1 e S(A) with es1 = s2. But A is strongly connected and so sl is epic, and therefore s2 = es1, is also epic. DEFINITION 5,2. If A is a W-semimodule, then Aut(A) is the group of the two-sided units (i.e., the invertible morphisms) in the endomorphism monoid E (A) of A in S W Mon (A) is the monoid of all the funcA A tions T w S(A) -S(A) with (s)T = sw, for w c W (cfo Section 2)o W W 1W We say that a function h*: S(A)- >S(B) is the result of h ~ A —-B iff h*(s) = hs for all s c S(A). Since we will mostly be concerned with functions S(A) —>S(A) which belong to Mlon(A), we will consistently use the "right-side" notation for functions S(A) -S(B), Thus h* S(A) >-S(B) is the result of h A — >B iff (s)h* = hs for all s c S(A) o

158 It is clear that a function h*: S(A) - S(A) is the result of a morphism A A h A — A iff for any w c W we have h*T = T h* W W Now, for hl,h2: A >A and s c S(A), if s is epic, then by definition his = h2s implies hI = h2. Hence if A is strongly connected, hlh2: A -A and his = h2s for some s e S(A), then h1 = h2 0 In particular, for h: A -A, if hs = s for some s E S(A) then h is the identity morphism of A o In conclusion we have proved the following lemma0 LEMMA 5.3, If A is a strongly connected W-semimnodule, then for any s S (A) the function s*: Aut(A) S(A): h hs is injectiveo In particular, the cardinality of Aut(A) cannot exceed that of S(A). Obviously, the injections s*: Aut(A)- S(A) as defined in Lemma 53, determine the orbits of Aut(A) as acting on S(A) (cf. [3: pp.35-39]). Next we prove the well known property of groups of transformations, that the orbits of Aut(A) in S(A) partition S(A) into disjoint and isomorphic subsets, Denote by orb(s) the image of s* in S(A); i.e., orb(s) = {hs: h E Aut(A)} LEMMA 5,4, Let A be strongly connected W-semimodule and sls2 e S(A) o If orb(sl) orb(s2) ~ 0, then orb(sl) = orb(s2)

159 PROOF. If orb(sl) n orb(s2) P 0, then h s = h2s2 for some hlgh2 h Aut(A) o Hence h2 hs s2 Letting h h h, we have 119 2 2 111 2 2wehave orb(s2) = {gs2: g c Aut(A)} = {ghsl: g c Aut(A)} = {g's1: g' c Aut(A)} = orb(s1) COROLLARY 5.5. Let A* be the quotient set of S(A) under the partition of S(A) into the orbits orb(s), s c S(A) a Then there exists a bijection A* xAut (A) > S (A) PROOF, If c: A* >A is any choice function then 0c: A*xAut(A) S (A): (a,h)- hc(a) (where a ~ A*) is by Lemmata 5,3 and 5,4 a bijectiono Thus, in particular, if S(A) is a finite strongly connected semimodule, then the cordinality of Aut(A) divides that of S(A). We add now the requirement that A be abelian. DEFINITION 5,6, A W-semimodule A is abelian iff Mon(A) is abelian; i.e., iff for any s c S(A) and any wl,w2 E W, SWlW2 = sw2w1 In particular, an abelian strongly connected semimodule is called perfect. From Chapter I, Section 2, we know that an epic morphism e A — B induces a surjective monoid homomorphism Mon(e): Mon(A) -Mon(B) o

160 Hence if A is abelian and e: A -B is epic, then B is abelian too; and if A is perfect, then B is perfect too. We prove now that if A is perfect, then the transition monoid is the group of the underlying functions of Aut(A). With an abuse of notation we write LEMIA 5 7. If A is a perfect W-semimodule then Mon(A) = Aut(A) A PROOF. Since Mon(A) is abelian, every T: S(A) -S(A) is A A A the result of some endomorphism t A -— MA with twS = (S)~T Since w w, W A A A is strongly connected, Tw is surjective and so tA is epic. From now on we drop the superscript A from Tw, and we therefore write T S = Sw Assuming that for some S1,S2 C S(A), TWS1 = TwS2 then, since A is strongly connected, there exists a w1 e W such that = s2 = TwS2 = Tws1; ie., s = TwS1 This implies that T is the identity morphism of A and s1 = s2. Hence every Tw is an isomorphism of A onto A; i.e., Mon(A) c Aut(A). On the other hand, let h C Aut(A) and so E S(R). Since A is strongly connected, we have hso = soWh for some wh E W. We prove now that for all s c S(A), hs = swh o So let w C W be such that s = sow, then hs = hsow = soWhW = so wwh= swh }Hence h = T. In conclusion, Mon(A) = Aut(A) wh COROLLARY 5.8. If A is a perfect semimodule, then for any s C S(A), orb(s) = S(A) o Thus we have a bijection s*: Aut(A)-S(A): h- hs. The identity of Mon(A) with Aut(A), for perfect semimodules A, implies directly that Aut(A) is a (monoid) homomorphic image of W, and

161 that epic morphisms c A —- -B induce surjective monoid homomorphisms Aut (A) -— Aut (B) which are compatible with the homomorphisms from W onto Aut(A) and Aut(B) o We prove now a partial converse to Corollary 5,8, PROPOSITION 5,9, If A is a strongly connected semimodule such that orb(s) = S(A) for some s e S(A) and if Aut(A) is abelian, then A is perfect, PROOF. It suffices to show that A is abelian, so let 11 w2 C W, Since orb(s) = S(A), there are hl,h2 c Aut(A) with h1s = sw1 and h2s = sw2 Now since Aut(A) is abelian, we get sw1W2 = hlsw2: h1h2s = h2hls = h2sw1 = SW2w1, and therefore A is abelian. COROLLARY 5.10a If A is a finite strongly connected semimodule and Aut(A) is abelian with the same cordinality as S(A), then A is perfect. In general, for an arbitrary semimodule A, a morphism from A does not induce any group homomorphism of Aut(A) d We are inclined to say that in order to derive from the assignment A — v>Aut(A) a functor of a suitable subcategory, one does not have much choice, and has to consider perfect semimodules. Furthermore, the previous results precisely establish the fact that the assignment A -'Aut(A), as applied to perfect W-semimodules, determines a functor Tau. Per(W) -- fim(W)

162 from a category of perfect W-semimodules to a category of surjective homomorphisms of W with group images. To be precise, the category Per(W) has all the perfect W-semimodules as objects and all the possible morphisms (they must be epic!) among them, For each object A of Per(W) we define Tau(M) = ('.:: IS. =C(A)) where G(A) = Mon(A) = Aut(A), and T is the surjective monoid homomorA A phism defined by T (w) = o We noted before that every epic morphism of perfect W-semimodules, that is, every morphism e: A >B induces A B a monoid homomorphism Mon(e): G(A) ->G(B) with Mon(e)oT = T o It is natural, therefore, to consider the category Cim(W) whose objects are surjective monoid homomorphisms H: W — G onto abelian groups, There is a morphism of Cim(W) from H.: W )GI to H2 W -G2 whenever there exists a homomorphism H': G1 -G2 with H'H1 = H2 Hence, for any morphism e: A -B of Per(W), the morphism Tau(e): Tau(A) —— Tau(B) is defined to be the one determined by Mon(e) 0 Now our strategy is the following. We prove that the functor Tau v Per(W) — im(W) relate products. That is, every product diagram in Per(W) is mapped under Tau onto a product diagram in Cim, and every product diagram in Cim(W) which comes from a diagram in Per(W) via Tau comes from a product diagram in Per(W) o But before we do so we have first to be convinced that products in Per(W) yield the same product objects as in $W. For this, it suffices to show that a product object in the category of all epic morphisms of SW is precisely a product object in SW. Put differently, that a diagram A2- P —-EA1 of epic morphisms is a product diagram in SW iff it is a product diagram in the subcategory of $W of all the epic morphismso We also have to be

163 convinced ti;at if i: V —-— >( is a product object of 1 ~: Wl — -G1 and ab f2 1I ->CG2 in Cim(W), then C is a product of G1 and G2 in ab And, conversely, for any objects I1: W — >G1 and 112 W >C2 of Cim(W), there exists another object IH: --— G 1XG2 of Cim(W) such that 1': IV -1>C(X12 is a product object of the given two objects in Cimn(WV) In order to prove this, it suffices to show that }H: W — -.C is a product of H1 W I -— G1 and H2: W-;2 in;im iff there exists 1 2 an isomorphism J: C - GlxG2 with 11 G ~ G ------- C i J l2 commutative, where P1 P 1 2 2 G,', GxG2: G2 is a product diagram in ab. he proof of these connections between products of Gim(W) and Gab, and between Per(W) and $, are straightforward product diagram chasing, and it is left for the reader. We prove however that the functor Tau: Per(W) - Cim(W) relates products. IWe define now a second functor Act: Elim(W) -Per(W)

164 as follows~ Every object H: W —-G of Gim(W) determines a perfect W-semimodule G, which amounts to the action of W on G via H' W *G o That is, S((;H) = G and g.w = gH(w) o Since H is surjective, CtI is strongly connected, and since G is abelian, G is abelian too. Furthermore, Aut(G is isomorphic to Go Every morphism h from H1: W- G1 to I2: W >G2 of Cim(W) is determined by a homomorphism H': G1 G2 with G'G1 = (;2 Hence itv G1 CI2 determines a morphism': and so we define' 21 32,and so we define Act (h) = H' a We prove the following two lemmata, which express interesting relationships between the functors Act and Tau. These lemmata will imply that Tau relates products. LEMttIA 5.11. Let A be a perfect W-semimodule and H: W —- CG an object of Gim(W) with a morphism of Cim(W) into Tau(A); i.e., with an epimorphism E: CG Mlon(A) such that E-I = T. Then for any s C S(A) there exists an epic morphism H e G > A s of Per(W) PROOF, Define eS: )A by e (g) = E(g)(s) o Then for all w c W ~ e (gcw) = es(gH(w)) = E(gH(w))(s) = E(g)EH(w)(s) = E(g)t (w)(s) = E(g)sw = e (g)w o Similarly, we have

165 LEMMHA 5,12, Let A and B be perfect W-semimodules with a morphism of Cim(W) from Tau(A) into Tau(B); i.e., with an epimorphism E: Mon(A) —-Mon(B) A B such that ET = T. Then for any s1 E S(A) and s2 C S(B) there exists an (epic) morphism e: A- B of Per(W) with ess(slW) = s2w "1' 2 PROOF: We define e: A -B by! 2 eS S2 (S1W) s2 w Since s 1 s w2 implies T s = T1, and therefore T = T w 1 w 11 w2 W1 W Hence s 1w =s1w2 implies s2w1= s2w2 and therefore e is well defined. Obviously it determines a morphism of Per(W) Thus Lemma 5.11 states that if Gim(H,Tau(A)) is not empty, then Per(Act(H),A) is note empty. Similarly, Lemma 5,12 states that if Gim(Tau(A),Tau(B)~) is not empty, then Per(A,B) is not empty, Our final theorem follows now directly. THEOREM 5.13. The functor Tau: Per(W) >-im(W) relates products. That is, a family {pj: P -Aj.} of morphisms of Per(W) is a product diagram in Per(W) iff the induced family {Tau(pj): Tau(P) —Tau(Aj) }

166 is a product diagram in Gim(W) Now, because of the asserted relations between the products in Gim(W) and the products in ab, and between the products in Per(W) and the products in $, we have COROLLARY 5,14, (Fleck) A perfect W-semimodule A is a product object of the family {Aj} in Per(W) iff Mon(A) is the direct product of {Mon(Aj)} in the category of abelian groups.

BIBLIOGRAPHY 1o Birkhoff, G,, "Structure of Abstract Algebras," Proc. Cambridge Philos. SOc., 29, 441-464 (1935), 2. BUchi, J. R., "Mathematical" Theory of Automata,".Notes, on.material presented by J. Bo Wright and J. R, Biuchi, Communication Sciences 403, Fall 1960, The University of Michigan (Unpublished). 3, Chevalley, C., Fundamental Concepts of Algebra, Acado Press, New York (1956) o 4. Chomsky, N. and Schutzenberger, Mo P., "The Algebraic Theory of ContextFree Languages," in Computer Programming and Formal Systems, Edited by P. Braffort and D, Hirsc herg, North Hollan, Amsterdam (1963). 5o Cohn, P. Mo, Universal Algebra, Harper's Series in Modern Mathematics, Harper & Row, New York (1965) o 6. Eggan, L. C., "'Transition Graphs and the Star-Height of Regular Events," lichigan Math, J., 10, 385-397 (1963). 7. Fleck, Ao C., "Isomorphism Groups of Automata," J. ACM. 9, 469-476 (1962)0 8. Freyd, P., Abelian Categories: An Introduction to the Theory of Functors, Harper's Series inMolwrn Mathematics, Harper & Row, New York (1964), 90 Ginsburg, S., An Introduction to Mathematical Machine Theory, AddisonWesley, Reading, Mass, (1962)10o Hartmanis, J, and Stearns, R. E,, "Pair' Algebra and Automata Theory," Inf, Con., 7, 485-507 (1964)o 11. Kleene, S. C., Introduction to Metamathematics, Van-Nostrand, Princeton (1952) T - 12. Krohn, K, B. and Rhodes, J, L., "Algebraic Theory of Machines," Proc Sm Mat Theory of Automata, Polytechnic Press, Brooklyn, New York, 341-384 (1962). 13. MacLane, S, "Categorical Algebra,'". ~;u1.311AMlS,.71, 40-106 (1965). 14. MacLane, S., Homology, Academic Press, New York (1963). 15. Perles, M,, Rabin, M. O,, and Shamir, E., "The Theory of Definite Automata," IEEE Transactions on Electronic Computers, Vol. EC-12, No 3, June, 1963, 233-2430 16, Rabin, M, Oo0 and Scott, D,, "Finite Automata and Their Decision Problems," IBM J 3, 114-125 (1959)o 167

168 BIBLIOGRAPHY (Concluded) 17. Thatcher, J, W., "Notes on Mathematical Automata Theory," Tech. Note 05662, 03105-26-T, ORA, The University of Michigan (1963). 18, Weeg, G. P,, "The Group and Semigroup Associated with Automata," Proc. Soymp Math. Theor of Automata, Polytechnic Press, Brooklyn, New York, 257-266 (1962) 19. Zeiger, H, P., "Loop Free Synthesis of Finite State Machines," Thesis, M.I.T. (1964),

INDEX of the most re-occurring symbols ordered according to their first occurrence \tW an arbitrary (input) monoid 1, 74, 104, 133, 142; an arbitrary category 2, 8...; t, 11~,'' as a W-semimodule 3, 78, 109, 1 7 7; S the category of sets 8, 640o.; ~I the category of monoids 93, 25, 71; the category of groups 9, 71; C(AB) the class of all morphisms A ->B in C 10, 11oo.; f: A!- B an arbitrary morphism 10, 80...; S a forgetful functor: of groups 13, 85; of monoids 25; of semimodules 83, 89,oo, F C1 12 an arbitrary functor from C1 to ~2 12, 23, 24,,e; ~8 the category of all functors from t3 to C 13, 27, 32; Cat the category of all categories 13, 30, 65; I, (Ic) an identity functor (oif C ) 14, 46..,; 169

170 Fr the free object functor: of groups 14, 20; of monoids 25; D the opposition automorphism of Cat 16, 65; C~p the opposite category of C 16, 65; C(A,-) the covariant hom-functor 17, 25, 88.. o 126; ~C (- ~B) the contravariant hom-functor 18; fn{Aj} a product object of {Aj} 21, 81; A1IxA2 a product object of A1 and A2 21, 239 162; E{A.} a sum object of {Aj} 22, 81, 1199 122; A1+A2 a sum object of A1 and A2 22; ~Cx~2 the product category of ~1 and 1C2 23; T: F -.G an arbitrary natural transformation from F to G 27o00; fT*T Benabou's product of natural transformations 29, 50; T o F Benabou's product of a natural transformation and a functor 31; F' o Benabou's product of a functor and a natural transformation 31, 96, 99, 104; Nat (B,C) Benabou's category of the natural transformations of functors B --- C 32, 60;

171 N the ordered category of the natural numbers 34, 38, 41; (DX,0> the diagramatical class defined by means of X in L) 41, 44; Ob (C) the quotient class group of the automorphisms of C modulo the equivalence of functors 50, 71, 107; Aut(~) the quotient class group of the automorphisms of C modulo the natural equivalence of functors 50, 71, 107; Tran(C) the quotient class group of the automorphisms of C modulo the natural relatedness 52, 71, 108; Gab the category of abelian groups 53, 163; Z the additive group of integers 53; R(G) the abelian group defined on Gab(Z,G) 53; C[M] the class of all objects F(M) of C where F is an automorphism of ~: and F(M). is is-omorphle to M 68, 101; ~4 a certain group of automorphisms of a given category 68, 99, 139; j i modulo natural equivalence 70, 99; S(A) the set of states of a semimodule A, the set $W(MwA) 77.o., 158...; XA the transition function of a semimodule A 77. o, 121;

172 Ov, the empty W-semimodule 77, 129; UW the single state W=semimodule 77; s aw XA(soW) 800 o.; W$v the category of W-semimodule 81..0; AT the (power) semimodule of the functions T - S(A) 82, 149; T.A the (multiple) semimodule defined on TxS(A) 83, 117, 121, 127, 149; f ~ MW >, A the morphism associated with s C S(A) defined by f (1) = s 87, 89. oD 155; p S- $$W (MW-) the natural equivalence determined by s - f 89, 119, 123; W* the endomorphism monoid of NI in $W W 90..o; r? >$W the representation functor of $: 91o; WO b W~ W* the isomorphism determined by P(Mw); i e., by w >f 92, 125; r the functor derived from r* and ~~o~~~~~'92; rjr the reconstruction functor of $ rp determined by an isomorphism: W --- W* 93; hx e W —>W* tile mapping associated with x: W —-W by hx(W) = f(w 94; xx(w)94

173 Aut(W) the automorphism group of W 95, 139, 150, 152; Iso(WW*) the set of all isomorphisms from W to W* 95; p G I, r, the natural equivalence ofW the identity functor of S with 96; T the automorphism functor of $W determined by a s Aut(W) 97..., 139; IM(w) the subsystem of MW with wW as its set of states 114, 123, 130, 133; Mon(A) the transition monoid of a W-semimodule A 145, 156; A the transition S(A) >S(A) given by s sow 145, 158; T the surjective monoid homomorphism w - >TA 145; Mon(e) the surjective monoid homomorphism determined by an epic morphism e of $W 146, 159;

DISTRIBUTION LIST (One copy unless otherwise noted) Technical Library Naval Electronics Laboratory Director Defense Res. & Eng. San Diego 52, California Room 3C-128, The Pentagon Attn: Technical Library Washington, D.C. 2030.1 Dr. Daniel Alpert, Director Defense Documentation Center 20 Coordinated Science Laboratory Cameron Station University of Illinois Alexandria, Virginia 22314 Urbana, Illinois Chief of Naval Research 2 Air Force Cambridge Research Labs Department of the Navy Laurence C. Hanscom Field Washington 25, D.C. Bedford, Massachusetts Attn: Code 437, Information Attn: Research Library, CRMXL R Systems Branch U. S. Naval Weapons Laboratory Director, Naval Research Laboratory 6 Dahlgren, Virginia 22448 Technical Information Officer Attn: G. H. Gleissner, Code K4 Washington 25, D.C. Asst. Dir. for Computation Attention: Code 2000 National Bureau of Standards Commanding Officer 10 Data Processing Systems Division Office of Naval Research Room 239, Building 10 Navy 100, Fleet Post Office Box 39 Washington 25, D.C. New York, New York 09599 Attn: A. K. Smilow Commanding Officer George C. Francis ONR Branch Office Computing Laboratory, BRL 207 West 24th Street Aberdeen Proving Ground. Maryland New York 11, New York Office of Naval Research Office of Naval Research Branch Branch Office, Chicago Office 230 North Michigan Avenue 495 Summer Street Chicago, Illinois 60601 Boston, Massachusetts 02110 Commanding Officer Naval Ordnance Laboratory ONR Branch Office White Oaks, Silver Spring 19 1030 E. Green Street Maryland Pasadena, California Attn: Technical Library Commanding Officer David Taylor Model Basin ONR Branch Office WashingtonD.C. 20007 1000 Geary Street Attnt Code 042, Technical Library San Francisco 9, California

DISTRIBUTION LIST (Concluded) The University of Michigan Lincoln Laboratory Department of Philosophy Massachusetts Institute of Technology Attn: Professor A. W. Burks Lexington 73, Massachusetts Attn: Library National Physical Laboratory Teddington, Middlesex, England Office of Naval Research Attn: Dr. A. M. Uttley, Supt. Washington 25, D.C. Autonomics Division Attn: Code 432 Commanding Officer Dr. Kenneth Krohn Harry Diamond Laboratories Krohn Rhodes Research Institute, Inc. Washington, D.C. 20438 328 Pennsylvania Avenue, S. E. Attn: Library Washington 13, D. C. Commanding Officer and Director U. S. Naval Training Device Center Dr. Larry Fogel Port Washington Decision Science, Inc. Long Island, New York 6508 Pacific Highway Attn: Technical Library San Diego, California Department of the Army Office of the Chief of Research National Bureau of Standards and Development Applications Engineering Section Pentagon, Room 3D442 Washington 25, D. C. Washington 25, D.C. Attn: Miss Mary E. Stevens Attn: Mr. L. H. Geiger National Security Agency Fort George G. Meade, Maryland Attn: Librarian, C-332

UNCLASSIFIED Security Classification DOCUMENT CONTROL DATA - R&D (Security claeesifcation of tite, body of abstract and indexianQ notation must be entered when the overall report is claeeilied) 1. ORIGINATIN G ACTIVITY (Corporate author) 2. REPORT SECURITY C LASSIFICATION Logic of Computers Group Unclassified The University of Michigan 2b GROUP Ann Arbor, Michigan 48104 3. REPORT TITLE ON SOME CATEGORICAL ALGEBRA ASPECTS OF AUTOMATA THEORY: THE CATEGORICAL PROPERTIES OF TRANSITION SYSTEMS 4. DESCRIPTIVE NOTjS (TypR of report and Inclu.tve dal.s) Technical Report S. AUTHOR(S) (Lst name., firt name, inittal) Give' on, Yehoshafat 6. REPORT DATE 7'. TOTAL NO. Ot PAGES 7b. NO. oF RrS February 1966 173 19 8&. CONTRACT OR GRANT NO. 9-. ORIOINATOR'* REPORT NUMBER(S) Nonr 1224(21) 03105-43-T b. PROJECT NO. c. I b. ITRH PRORPCT NO(S) (Aity other numbere hat may be.assi.ed is. reporu d. 10. A V A IL ABILIltY/LIMITAtON NOTICES Qualified requesters may obtain copies of this report from DDC. 11. SUPPL EMENTARY NOTES 1a. SPONSORING MILITARY ACTIVITY Office of Naval Research Department of the Navy Washington, D.C. 13. ABSTRACT The ubiquity and usefulness of homomorphisms in various studies of automata lead us to consider the following problem. What can be said on automata by referring only to homomorphisms of automata? In the report we present a study of this problem with respect to a special type of automaton, namely with respect to transition systems. Categorical algebra methods are applied to the precise formulation of this problem and to its solution. We find that if W is a monoid belonging to a broad class of monoids, then the categorical abstract properties of transition systems with input W are determined by the automorphisms of the monoid W. In particular, any property of automata without output is categorical iff it does not depend on the particular labeling of the input alphabet. This study of the categorical properties of automata has two additional outcomes. First, we realize that categorical algebra methods can be applied to automata with arbitrary input monoids, with results pertinent to the theory of monoids. On the other hand it indicates a possible usefulness in the study of automata, in particular, in getting a better understanding of the mathematical ideas employed in automata theory. In order to support this point of view with respect to automata theory, we show that many actually studied properties of automata are categorical. And we give an example of a categorical examination and formulation of a particular study of perfect automata. DD 1 JINS 4 1473 UNCLASSIFIED Security Classification

UNCLASSIF IED Security Classification 14*K W LINK A LINK L LINK C ROLE WT ROLE WT ROLE WTl 1. algebraic automata theory 2. categorical algebra 3. homomorphisms 4. transition systems 5. monoids INSTRUCTIONS 1. ORIGINATING ACTIVITY: Enter the name and address imposed by security classification, using standard statements of the contractor, subcontractor, grantee, Department of De- such as: fense activity or other organization (corporate author) issuing (1) "Qualified requesters may obtain copies of this the report. report from DDC." 2a. REPORT SECURITY CLASSIFICATION: Enter the over, 2a..REPORT SECUTY CLASSIFICATION: Enter the. ove,-, (2) "Foreign announcement and dissemination of this all security classification of the report. Indicate whether "Restricted Data" is included. Marking is to be in accordance with appropriate security regulations. (3) "U. S. Government agencies may obtain copies of this report directly from DDC. Other qualified DDC 2b. GROUP: Automatic downgrading is specified in DoD Di- users shall request through rective 5200. 10 and Armed Forces Industrial Manual. Enter the group number. Also, when applicable, show that optional. markings have been used for Group 3 and Group 4 as author- (4) "U. S. military agencies may obtain copies of this ized. report directly from DDC. Other qualified users 3. REPORT TITLE: Enter the complete report title in all shall request through capital letters. Titles In all cases should be unclassified.,, If a meaningful title cannot be selected without classification, show title classification in all capitals in parenthesis (5) "All distribution of this report is controlled. Qualimmediately following the title. ified DDC users shall request through 4. DESCRIPTIVE NOTES: If appropriate, enter the type of.o report, e.g., interim, progress, summary, annual, or final. If the report has been furnished to the Office of Technical Give the inclusive dates when a specific reporting period is Services, Department of Commerce, for sale to the public, indicovered. cate this fact and enter the price, if known. 5. AUTHOR(S): Enter the name(s) of author(s) as shown on 11. SUPPLEMENTARY NOTES: Use for additional explanaor in the report. Enter tast name, first name, middle initial. tory notes. If mrlitary, show rank and branch of service. The name of the principal author is an absolute minimum requirement. 12. SPONSORING MILITARY ACTIVITY: Enter the name of the departmental project office or laboratory sponsoring (pay6. REPORT DATE. Enter the date of the report as day, ing for) the research and development. Include address. month, year; or month, year, If more than one date appears on the report, use date of publication 13. ABSTRACT: Enter an abstract giving a brief and factual summary of the document indicative of the report, even though 7a. TOTAL NUMBER OF PAGES: The total page count it may also appear elsewhere in the body of the technical reshould follow normal pagination procedures, i.e., enter the port. If additional space is required, a continuation sheet shall number of pages containing information. be attached. 7b. NUMBER OF REFERENCES: Enter the total number of It is highly desirable that the abstract of classified reports references cited in the report. be unclassified. Each paragraph of the abstract shall end with 8a. CONTRACT OR GRANT NUMBER: If appropriate, enter an indication of the military security classification of the inthe applicable number of the contract or grant under which formation in the paragraph, represented as (TS). (S). (C), or (U) the report was written, There is no limitation on the length of the abstract. How8b, 8c, & 8d. PROJECT NUMBER: Enter the appropriate ever, the suggested length is from 150 to 225 words. military department identification, such as project number, 14. KEY WORDS: Key words are technically meaningful terms subproject number, system numbers, task number, etc. or short phrases that characterize a report and may be used as 9a. ORIGINATOR'S REPORT NUMBER(S): Enter the offt- index entries for cataloging the report. Key words must be cial report number by which the document will be identified selected- so that no security classification is required. Identiand controlled by the originating activity. This number must fiers, such as equipment model designation, trade name, military be unique to this report. project code name, geographic location, may be used as key 9b. OTHER REPORT NUMBER(S): If the report has been words but will be followed by an indication of technical conassigned any other repcrt numbers (either by the originator. The assignment of links, rules, and weights is optional or by the sponsor), also enter this number(s). 10. AVAILABILITY/LIMITATION NOTICES: Enter any limitations on further dissemination of the report, other than those UNCLASSIFIED Security Classification

L866 9Z8;O 9L06 e 1 III I 11111111 IIIIIJIIlr IlilIrr IIIi II NVDIHOI.10 AI ISU3AINn