Dear Bob: Here is some more on Vaughn's problem. First off, I checked out the reference to the Bloom and Meseguer papers and they both concerned theories for which the operations were order-preserving (or even omega-sup preserving) and this is neither what Vaughn was proposing nor what I, in the last note, suggested. Thus neither one would allow boolean algebras to be models and neither is really relevant. The other thing I checked out is Linton's paper on functorial semantics in SLNM vol. 80. This is the first paper in volume, with a title something like, ``An outline of functorial semantics''. His theory really does implement my suggestion of not having the operations preserve the order at all. He doesn't look at the HSP question. This note will consist of a brief sketch of Linton's paper, followed by some ideas of my own on the HSP problem. Let B be a category. By a B-based theory, I will mean a category T, plus a functor F:B* --> T (B* is the opposite of B) that is an isomorphism on objects. Think of T as having all the arrows of B (Manes would call them the crisp maps), together with others (that Manes calls fuzzy maps). This is not literally true because F needn't be faithful, but it is a good way to think of this. A model of this theory is a functor M:T --> Sets with the property that MF is representable. In fact, it might be better to describe a model as an M, together with an object b of B such that MFa == B(a,b). (Use == for isomorphic). The reason the second way is better is that it avoids having to make choices. If you work out what this all means, it turns out that a model of the theory is an object b of B together with a family of maps Mf:B(a1,b) --> B(a2,b) correspnding to each morphism f:Fa_1 --> Fa_2 of T. Recall that every object of T is of the form Fa for a unique object a of B. This is subject to the conditions that if f=Fg:Fa1 --> Fa2, then Mf is the map B(g,b) induced by g and that M(f.g)=Mf.Mg. Where do these theories come from? Well one way is as follows. Let U:A --> B be a functor. Let T have objects Fa in one-one correspondence with the objects of B. Define T(a1,a2) = NT(B(a1,U-),B(a2,U-)). This might be a proper class and certain care has to be taken in that case, but basically that is how such a category arises. If U has a left adjoint L, then we will get T(a1,a2)=B(ULa2,ULa1), so the question of size cannot arise then. In that case, T is simply the Kleisli category of the triple. Things start to get complicated (not to mention ugly) when you start to look at HSP theorems. If all you want to do is add equations, there is no problem. Here's why. An equation takes the form f=g for f,g:n --> m in T. Although quotient categories are generally quite nasty, they aren't if you never identify objects and we don't. It is easy to see that if M' is a submodel of M and M |- f=g, then so does M'. Products are even easier and it follows from standard category theory that we have an epi-reflective subcategory. For H, we take the set of epimorphisms that are split epimorphisms as posets. Assumng that alpha:M -->> M' is such an epimorphism, represented by the split epimorhism b -->> b', and that M satisfies the equation, the fact that M' does follows from the square B(n,b) ---->> B(n,b') ! ! ! ! Mf! !Mg M'f! !M'g ! ! ! ! v v v v B(m,b) ---->> B(m,b') especially the fact that the upper arrow is epic. For the converse, the crucial is that every object is the target of a poset-split epi from a free algebra and hence if an HSP subcategory contains every free algebra, it contains every algebra. If it doesn't, look at the reflections of those free algebras and there you will find the equations. Warning: what follows is ugly and inelegant. Read on at your own risk. Now really, it seems highly unlikely that you aren't going to want to impose inequalities as well as equalities. (Time out to complain about ``inequation''. If a neologism is genuinely more informative than the old word, fine. ``Inequality'' is criticized as not being antonomous to ``equality''. A reasonable criticism. In what earthly way is ``inequation'' an improvement? Down with it!) Now I have dropped the order relation from the operations and now I will need to reintroduce them for adding inequalities. Yes, but that seems to be what is required. Anyone who can find an elegant way of doing this, hats off. Structure is given by a map T(n,m) --> Hom(B(n,b),B(m,b)), the latter being the set of functions in sets. B(n,b) and B(m,b) are taken to be the discrete sets of maps so that the operations don't preserve order. Now I am going to `remember' that b is ordered and that b(m,b) and in turn Hom(B(n,b),B(m,b)) inherit order relations from that of b. Then I am going to suppose that T is a posets-category so that T(n,m) is ordered and suppose that the above arrow preserves order. This doesn't make the operations order preserving, but rather that if f < g in the order, then the interpretation of f is < the interpretation of g. Not that f and g individually preserve order. You could transpose the above map and find a different way of putting it, but it looks just as ugly. If T arises from an underlying posets functor, you will see that T does naturally become a posets-category. Now we can talk about M |- f<g and such like. And we can look at the full subcategory of M that satisfy that condition. It is no trouble to show that it is closed under products, strict subobjects and posets split epimorphisms and, while I haven't actually checked the details, I believe the converse is true as well. The same argument with free algebras ought to work. Of course, now the free algebra on some poset might be abstractly isomorphic to its previous value, but have a richer order relation. That leads to a new inequality. For both equalities and inequalities, the antecedants will be Horn clauses in the predicates of equalities and inequalites. This additional expressive power is what you get by using operations based on arbitrary posets, rather then sets. For the purposes of computer science, one probably ought to restrict to the case of an aleph_0, or at most aleph_1 accessible theory. This basically means that need look only at finite (or finite and countable) ary operations. Regards, Mike