Theory and Applications of Categories, Vol. 21, No. 2, 2008, pp. 21–36.

LIMIT PRESERVING FULL EMBEDDINGS

Dedicated to Professor Walter Tholen on his 60th birthday

V. TRNKOVÁ AND J. SICHLER

Abstract. We prove that every small strongly connected category k has a full embedding preserving all limits existing in k into a category of unary universal algebras. The number of unary operations can be restricted to | mor k | in case when k has a terminal object and only preservation of limits over finitely many objects is desired. And all limits existing in such a category k are preserved by a full embedding of k into the category of all algebraic systems with | mor k | unary operation and one unary relation.

1. Introduction

Let Set be the category of all sets and mappings and let k be a small category. The wellknown Eilenberg-Mac Lane representation M : k → Set of [3], and the Yoneda embedding Y : k → Set^{k^{op}} of k into the category Set^{k^{op}} of all contravariant functors from k to Set and all their natural transformations are faithful functors with somewhat opposite properties. For any a ∈ obj k, the representing object Ma is a model of simplicity – merely a set of moderate size, while the object Y a is a many-sorted algebra in the sense of [1] with | obj k| many sorts and | mor k| many (heterogeneous) operations. On the other hand, the functor Y is nicer because it is full and preserves all limits existing in k, while M has neither of these two properties.

This paper investigates the existence of full and faithful functors Φ : k → K for categories K whose objects have considerably simpler structure than the objects of Set^{k^{op}}, namely categories of (mono-sorted) universal algebras or algebraic systems (cf. [2, 6, 9]) that preserve at least some limits existing in k. Such functors thus occupy an ‘intermediate ground’ between M and Y.

Since for any category K of algebraic systems the forgetful functor V : K → Set preserves limits, the existence of a limit preserving faithful representation Φ : k → K implies that the faithful composite functor V ∘Φ : k → Set must preserve all limits existing in k. But we show this to be impossible for the small category k given in Example 2.1 in Section 2.

The first author gratefully acknowledges the support of MSM 0021620839, a project of the Czech Ministry of Education, and of the grant 201/06/0664 by the Grant Agency of Czech Republic. The second author gratefully acknowledges the support provided by the NSERC of Canada and by MSM 0021620838, a project of the Czech Ministry of Education.

Received by the editors 2008-02-15 and, in revised form, 2008-04-03.

Published on 2008-05-12 in the Tholen Festschrift.

2000 Mathematics Subject Classification: Primary: 08B25, Secondary: 18B15.

Key words and phrases: universal algebra, unary algebra, limit, full embedding, limit preserving functor.

\begin{matrix}c \\ ◯ \end{matrix} V. Trnková and J. Sichler, 2008. Permission to copy for private use granted.

A category k is connected if any pair of k-objects belongs to the transitive closure of the binary relation R on obj k given by aRb iff k(a, b) ∪ k(b, a) ≠ ∅. And k is strongly connected if every hom-set k(a, b) with a, b ∈ obj k is non-void.

For any cardinal λ, let Alg(1 × λ) denote the category of all universal algebras with λ unary operations.

Theorem 2.2 of Section 2 states that every strongly connected small category k has a full embedding into some Alg(1 × λ) that preserves all limits existing in k. The number λ of unary operations is quite large, but in Section 3 it is reduced in case when the strongly connected category k has a terminal object and only preservation of limits of diagrams over finitely many objects is required. Preservation of all limits is restored and the reduced number of unary operations retained when representing unary algebras are enriched by one unary relation, and this is done in Section 4. The final Section 5 applies these results to countable categories and concludes with some open problems.

2. A general representation result

2.1. Example. There exists a connected finite category k for which no faithful functor F : k → Set can preserve all (finite) products existing in k.

Proof. The category k has the object set

obj k = {q, a, p, a_{1}, a_{2}, a_{3}},

and all the non-void hom-sets of k are as follows:

(1) k(p, a_{i}) = {π_{i}} for i = 1, 2, 3,

(2) k(q, r) = {μ_{r}} for all r ∈ obj k \ {q},

(3) k(q, q) = {1_{q}, ϵ} with ϵ^{2} = 1_{q} and k(r, r) = {1_{r}} for all r ∈ obj k \ {q},

(4) k(a, a_{1}) = {ϕ, ψ},

With the obvious composition, it is clear that k is a category.

Since there are no other k-morphisms than those listed above, from (1) and (2) it follows that (p, {π_{1}, π_{2}, π_{3}}) = ∏{a_{1}, a_{2}, a_{3}} and (p, {π_{2}, π_{3}}) = ∏{a_{2}, a_{3}}.

Let F : k → Set be a faithful functor. Then |F q| ≥ 2 because of (3) and hence |F r| ≥ 1 for all r ∈ obj k \ {q} because of (2), so that F s ≠ ∅ for every s ∈ obj k. If F preserves finite products, then the Cartesian product F a_{1} × F a_{2} × F a_{3} of these sets must be isomorphic to F a_{2} × F a_{3}. Since the sets F a_{i} are non-void, this is possible only when F a_{1} is a singleton. And since F is faithful, this contradicts (4).

Definition For any strongly connected small category k, let a functor G : k → Set be defined by

Ga = ∏{k(c, a) | c ∈ obj k} for every a ∈ obj k,

and for any k-morphism p : a → b by

Gp(x) = {p ∘ x_{c} | c ∈ obj k} for every x = {x_{c} ∈ k(c, a) | c ∈ obj k} ∈ Ga.

For any x = {x_{c} | c ∈ obj k} ∈ Ga we write p ∘ x = {p ∘ x_{c} | c ∈ obj k}, so that (p ∘ x)_{c} = p ∘ x_{c}. We call x_{c} ∈ k(c, a) the c-component of x = {x_{c} | c ∈ obj k} ∈ Ga.

The functor G is obviously well-defined and faithful and, as a product of hom-functors, it preserves all limits existing in k.

2.2. Theorem. For any strongly connected small category k, there is a cardinal λ and a full embedding Ψ : k → Alg(1 × λ) that preserves all limits existing in k.

Proof. The proposed full embedding

Ψ : k → Alg(1 × λ)

is carried by the product G = ∏{k(c, −) | c ∈ obj k} of hom-functors just defined. The actual algebra Ψa has the form

Ψa = (Ga; {ω_{z}^{a} | z ∈ Gc and c ∈ obj k}),

where each operation ω_{z}^{a} : Ga → Ga is defined for x = {x_{c} | c ∈ obj k} ∈ Ga by

(ω_{z}^{a}(x))_{d} = x_{c} ∘ z_{d} for every z ∈ Gc and d ∈ obj k.

This makes sense because components z_{d} of z ∈ Gc belong to k(d, c) and x_{c} ∈ k(c, a), so that ω_{z}^{a}(x) ∈ Ga again.

It is clear that Ψ is a well-defined one-to-one functor that preserves all limits. We outline only a proof that Ψ is full. So let

g : (Ga; {ω_{z}^{a} | z ∈ Gc and c ∈ obj k}) → (Gb; {ω_{z}^{b} | z ∈ Gc and c ∈ obj k})

be a homomorphism of these algebras. Choose an x ∈ Ga with x_{a} = 1_{a} and denote p = (g(x))_{a}, so that p ∈ k(a, b). We aim to show that g = Gp [ = Ψp]. We have (ω_{x}^{a}(x))_{d} = x_{a} ∘ x_{d} = 1_{a} ∘ x_{d} = x_{d} for every d ∈ obj k. Thus ω_{x}^{a}(x) = x, that is, x ∈ Ga is a fixpoint of the operation ω_{x}^{a}. Since g is a homomorphism, the element g(x) ∈ Gb is a fixpoint of the operation ω_{x}^{b}, that is, (ω_{x}^{b}(g(x)))_{d} = (g(x))_{d} for every d ∈ obj k. But (ω_{x}^{b}(g(x)))_{d} = (g(x))_{a} ∘ x_{d} = p ∘ x_{d}, and hence (g(x))_{d} = p ∘ x_{d} for every d ∈ obj k. Now let y ∈ Ga be arbitrary. We have (ω_{y}^{a}(x))_{d} = x_{a} ∘ y_{d} = y_{d} for every d ∈ obj k, that is, ω_{y}^{a}(x) = y. But then g(y) = g(ω_{y}^{a}(x)) = ω_{y}^{b}(g(x)). Hence (g(y))_{d} = (ω_{y}^{b}(g(x)))_{d} = (g(x))_{a} ∘ y_{d} = p ∘ y_{d} for every d ∈ obj k, that is, g(y) = (Gp)(y). Therefore g = Gp as claimed.

Although the number of needed operations is finite for any finite k, to represent a given infinite strongly connected category k with | mor k | = κ the proof of Theorem 2.2 may need λ = κ^{κ} unary operations. As will be seen below, this number can be reduced back to κ when some additional assumptions are made.

3. Limits of diagrams over finitely many objects

In this section we prove the following result.

3.1. Theorem. For every strongly connected small category k with a terminal object and infinite | mor k | = κ, there is a full embedding Φ_{0} : k → Alg(1 × κ) preserving all existing limits of diagrams over finitely many objects. For every a ∈ obj k, the algebra Φ_{0}a ∈ Alg(1 × κ) is idempotent.

Theorem 3.1 appears weaker than Theorem 2.2 because it requires that k have a terminal object and does not assert the preservation of all limits. The advantage of Theorem 3.1, however, is that it represents any small category k with infinite κ = | mor k | by algebras with only κ unary operations while Theorem 2.2 requires

λ = ∑ {{∏ |k(d, c)| | d ∈ obj k} | c ∈ obj k}

operations; this number λ can be uncountable even when | mor k| is countable. Theorem 3.1, on the other hand, enables us to similarly represent any strongly connected countable category k with a terminal object in the category Alg(1 × 2). The latter result is the best possible because the number of operations cannot be further reduced. We prove it in Section 5.

The functor Φ_{0} will be carried by a functor F : k → Set we now describe.

Definition Let t denote a terminal object of k and k(c, t) = {∇_{c}} for every c ∈ obj k. The functor F : k → Set is a subfunctor of the functor G from Section 2. Specifically, for any a ∈ obj k we let

F a ⊆ ∏{k(c, a) | c ∈ obj k} = Ga

consist of all sequences x ∈ ∏{k(c, a) | c ∈ obj k} for which there is a γ ∈ k(t, a) such that x_{c} = γ ∘∇_{c} for all but finitely many c ∈ obj k. For any p ∈ k(a, b), the map F p : F a → F b is given by

(F p)(x) = p ∘ x for every x ∈ F a.

For any x ∈ F a, the element p∘x ∈ Gb belongs to F b because (p∘x)_{c} = p∘x_{c} = p∘γ ∘∇_{c} for all but finitely many c ∈ obj k and p ∘ γ ∈ k(t, b). Therefore F is a well-defined functor. Choosing any x ∈ F a with x_{a} = 1_{a}, for any two distinct p, q ∈ k(a, b) we get (F p)(x)_{a} = p ≠ q = (F q)(x)_{a} and hence F p ≠ F q. The functor F is therefore faithful.

Next we show that F has the required preservation property.

3.2. Proposition. The functor F : k → Set preserves existing limits of diagrams over finitely many objects.

Proof. Let D : S → k be a diagram with a finite obj S for which lim D exists in k. Denote lim D = (l, {λ_{s} | s ∈ obj S}), with the morphisms λ_{s} ∈ k(l, Ds) forming a limit cone.

Recall that F is a subfunctor of G such that every F a with a ∈ obj k consists of all those x ∈ Ga = ∏{k(c, a) | c ∈ obj k} for which there is a γ ∈ k(t, a) and a finite A ⊆ obj k such that x_{c} = γ ∘ ∇_{c} for all c ∈ obj k \ A, and that Gp(x) = p ∘ x for any p ∈ k(a, b) and every x ∈ Ga.

The concrete form of limits in Set implies that we need to show that for every system {x^{(s)} ∈ F Ds | s ∈ obj S} satisfying F Dσ(x^{(s)}) = x^{(s′)} for every S-morphism σ : s → s′ there is a unique x ∈ F l such that λ_{s} ∘ x = F λ_{s}(x) = x^{(s)}.

So let {x^{(s)} ∈ F Ds | s ∈ obj S} be such a system. For every c ∈ obj k and every Smorphism σ : s → s′ we then have Dσ ∘ x_{c}^{(s)} = (Dσ ∘ x^{(s)})_{c} = F Dσ(x^{(s)})_{c} = x_{c}^{(s′)}, so that {x_{c}^{(s)} ∈ k(c, Ds) | s ∈ obj S} is a cone over D in k. Since lim D = (l, {λ_{s} | s ∈ obj S}) in k, for each c ∈ obj k there is a unique x_{c} ∈ k(c, l) such that x_{c}^{(s)} = λ_{s} ∘ x_{c}. Thus x = {x_{c} | c ∈ obj k} ∈ Gl and Gλ_{s}(x) = λ_{s} ∘ x = x^{(s)} for every s ∈ obj S. Since {Gλ_{s} | s ∈ obj S} is a limit cone, the element x ∈ Gl is the only one for which λ_{s} ∘x = x^{(s)} for all s ∈ obj S. It thus remains to show that x ∈ F l.

Since x^{(s)} ∈ F Ds for s ∈ obj S, we have a finite set A_{s} ⊆ obj k and γ_{s} ∈ k(t, Ds) such that x_{c}^{(s)} = γ_{s} ∘ ∇_{c} for all c ∈ obj k \ A_{s}. Then the set A = ⋃{A_{s} | s ∈ obj S} is finite because obj S is finite, and x_{c}^{(s)} = γ_{s} ∘ ∇_{c} for every s ∈ obj S and all c ∈ obj k \ A.

Also, if c ∈ obj k \ A then from Dσ ∘ λ_{s} = λ_{s′} for every S-morphism σ : s → s′ it follows that γ_{s′} ∘∇_{c} = λ_{s′} ∘x_{c} = Dσ ∘λ_{s} ∘x_{c} = Dσ ∘γ_{s} ∘∇_{c}. Since k is strongly connected, each terminal morphism ∇_{c} is an epi, and we obtain γ_{s′} = Dσ ∘ γ_{s} for every σ : s → s′ in S. This means that (t, {γ_{s} | s ∈ obj S}) is a cone over D in k, and hence there is a unique γ ∈ k(t, l) such that λ_{s} ∘ γ = γ_{s} for every s ∈ obj S.

Altogether, for every c ∈ obj k \ A and every s ∈ obj S we have λ_{s} ∘ x_{c} = x_{c}^{(s)} = γ_{s} ∘ ∇_{c} = λ_{s} ∘ γ ∘ ∇_{c}. Since {λ_{s} | s ∈ obj S} is a limit cone, it follows that x_{c} = γ ∘ ∇_{c} for every c ∈ obj k \ A. Since A is finite and γ ∈ k(t, l), this means that x ∈ F l.

3.3. Remark. Adding a terminal object to the finite category k of Example 2.1 clearly produces a finite category l that is not strongly connected and has a terminal object, for which no faithful functor H : l → Set preserving (finite) products exists. This naturally leads to a question of characterization of those small categories k with a terminal object for which there is a faithful functor H : k → Set that preserves all limits existing in k.

The following claim proves the essential part of Theorem 3.1.

3.4. Lemma. Any small strongly connected category k with a terminal object t has a full embedding preserving all its existing limits over finitely many objects into the category Alg(1 × κ) of multiunary algebras, where

κ = | mor k | + |⋃{k(t, c) | c ∈ obj k}| .

It is clear that κ = | mor k| in case when | mor k| is infinite.

We prove Lemma 3.4 in 3.5–3.11 below.

3.5. Since a full embedding Φ_{0} : k → Alg(1 × κ) will be carried by the functor F : k → Set, it is clear that Φ_{0} is going to be faithful.

In 3.6 and 3.7, on each set F a with a ∈ obj k we define a multiunary algebra Φ_{0}a.

3.6. First, for any ν ∈ k(c, c′), we define a unary operation o_{ν}^{a} : F a → F a so that for any x = {x_{d} ∈ k(d, a) | d ∈ obj k} ∈ F a, the element o_{ν}^{a}(x) = x′ = {x′_{d} ∈ k(d, a) | d ∈ obj k} has the components

x′_{d} = \{ \begin{matrix}x_{c′} ∘ ν & for d = c, \\ x_{d} & for d ∈ (obj k) \ \{c\}. \end{matrix}

3.7. Second, for any c ∈ obj k and any γ ∈ k(t, c), we define a unary operation ω_{c,γ}^{a} on each F a. For any x = {x_{d} ∈ k(d, a) | d ∈ obj k} ∈ F a, ω_{c,γ}^{a}(x) = x′ = {x′_{d} ∈ k(d, a) | d ∈ obj k} will have the components

x′_{d} = \{ \begin{matrix}x_{c} & for d = c, \\ x_{c} ∘ γ ∘ ∇_{d} & for d ∈ (obj k) \ \{c\}. \end{matrix}

The operation ω_{c,γ}^{a} thus leaves the c-component x_{c} of x unchanged while acting as the ‘right translation’ of x_{c} by the appropriate morphism γ ∘ ∇_{d} for every other component of x.

To see that F p with p ∈ k(a, b) preserves any such operation, note that

((F p)(ω_{c,γ}^{a}(x)))_{d} = p ∘ (ω_{c,γ}^{a}(x))_{d} = \{ \begin{matrix}p ∘ x_{c} & if d = c, \\ p ∘ (x_{c} ∘ γ ∘ ∇_{d}) & if d ≠ c \end{matrix}

and

(ω_{c,γ}^{b}(F p)(x))_{d} = \{ \begin{matrix}((F p)(x))_{c} & if d = c, \\ ((F p)(x))_{c} ∘ γ ∘ ∇_{d} & if d ≠ c. \end{matrix}

From ((F p)(x))_{c} = p ∘ x_{c} it then follows that F p ∘ ω_{c,γ}^{a} = ω_{c,γ}^{b} ∘ F p. Therefore all defined operations are preserved. Consequently, setting

Φ_{0}a = (F a; {o_{ν}^{a} | ν ∈ mor k} ∪ {ω_{c,γ}^{a} | c ∈ obj k and γ ∈ k(t, c)}) for every a ∈ obj k and
Φ_{0}p = F p for every p ∈ k(a, b)

produces a well-defined functor Φ_{0} : k → Alg(1 × κ).

3.8. The functor Φ_{0} : k → Alg(1×κ) preserves all limits of diagrams with finitely many objects existing in k because F : k → Set preserves them, see Proposition 3.2.

3.9. To prove the fullness of Φ_{0}, let g : Φ_{0}a → Φ_{0}b be a homomorphism of these algebras. We select and fix some α ∈ k(t, a), and use it to define a particular (a, α)-discrete element z ∈ F a whose components are given as

z_{c} = \{ \begin{matrix}1_{a} & if c = a, \\ α ∘ ∇_{c} & if c ∈ (obj k) \ \{a\}. \end{matrix}

We denote

p = g(z)_{a}.  (1)

Then p ∈ k(a, b), and we aim to show that g = F p. In order to do this, we first describe the specific element g(z) ∈ F b. Noting that ω_{a,α}^{a}(z)_{a} = z_{a} = 1_{a} and ω_{a,α}^{a}(z)_{c} = z_{a}∘α∘∇_{c} = α ∘ ∇_{c} for any c ≠ a, we conclude that ω_{a,α}^{a}(z) = z and, since g preserves the operation ω_{a,α} we also get ω_{a,α}^{b}(g(z)) = g(z). Thus, first of all, ω_{a,α}^{b}(g(z))_{a} = g(z)_{a} = p and, for any k-object c ≠ a we have ω_{a,α}^{b}(g(z))_{c} = g(z)_{c} = g(z)_{a} ∘α∘∇_{c} = p∘α∘∇_{c} with p∘α ∈ k(t, b). Altogether, this means that g(z) = (F p)(z) for the (a, α)-discrete element z defined in (z) above with the use of the one specified morphism α ∈ k(t, a).

3.10. Next we show that any other α′ ∈ k(t, a) determines the same element p ∈ k(a, b) as that given in (1), so that for any (a, α′)-discrete element z′ ∈ F a given by its ccomponents

z′_{c} = \{ \begin{matrix}1_{a} & if c = a, \\ α′ ∘ ∇_{c} & if c ∈ (obj k) \ \{a\}, \end{matrix}

we also have g(z′) = (F p)(z′). We simply observe that ω_{a,α′}^{a}(z) = z′, from which it follows that ω_{a,α′}^{b}(g(z)) = g(ω_{a,α′}^{a}(z)) = g(z′), and hence p = g(z)_{a} = (ω_{a,α′}^{b}(g(z)))_{a} = g(z′)_{a}. And for c ≠ a, we have g(z′)_{c} = ω_{a,α′}^{b}(g(z))_{c} = g(z)_{a} ∘ α′ ∘ ∇_{c} = p ∘ α′ ∘ ∇_{c}. Altogether, there is a unique p ∈ k(a, b) such that g(z) = (F p)(z) for every (a, α)-discrete element z ∈ F a with α ∈ k(t, a).

3.11. However, we need to show that g(y) = (F p)(y) for every y ∈ F a. Recall that for any y ∈ F a, there exists some γ ∈ k(t, a) such that all but finitely many components of y have the form y_{d} = γ ∘ ∇_{d} with d ∈ obj k. An inductive argument using the operations o_{μ} with μ ∈ mor k will complete the proof of this fact. To this end, let S ⊆ obj k be a finite set such that y_{d} = γ ∘ ∇_{d} for every d ∈ (obj k) \ S. Explicitly then,

y_{d} = \{ \begin{matrix}some μ_{d} ∈ k(d, a) & if d ∈ S, \\ γ ∘ ∇_{d} & if d ∈ (obj k) \ S. \end{matrix}

If a ∉ S, then also y_{d} = γ ∘ ∇_{d} for every d ∈ (obj k) \ S′ for the larger set S′ = S ∪ {a}, so that we may just as well assume that a ∈ S.

So let a ∈ S. Order the finite set S linearly in such a way that a is its last element. We proceed inductively along the order c_{1} < c_{2} … < c_{m} < a of S = {c_{1}, …, c_{m}, a} as follows.

Let c_{1} ∈ S \ {a}, and denote μ_{1} = y_{c_{1}} ∈ k(c_{1}, a). Let z ∈ F a be the (a, γ)-discrete element, and denote z_{1} = o_{μ_{1}}^{a}(z). Thus

(z_{1})_{d} = \{ \begin{matrix}1_{a} & if d = a, \\ μ_{1} & if d = c_{1}, \\ γ ∘ ∇_{d} & if d ∈ (obj k) \ \{a, c_{1}\}. \end{matrix}  (2)

Since g(z_{1}) = g(o_{μ_{1}}^{a}(z)) = o_{μ_{1}}^{b}(g(z)) and because, for every w = {w_{d} | d ∈ obj k}, the operation o_{μ_{1}}^{b} with μ_{1} ∈ k(c_{1}, a) is given by

o_{μ_{1}}^{b}(w)_{d} = \{ \begin{matrix}w_{a} ∘ μ_{1} & if d = c_{1}, \\ w_{d} & if d ∈ (obj k) \ \{c_{1}\}, \end{matrix}

for w = g(z_{1}) we obtain

g(z_{1})_{d} = o_{μ_{1}}^{b}(g(z))_{d} = \{ \begin{matrix}p & if d = a \\ p ∘ μ_{1} & if d = c_{1}, \\ p ∘ γ ∘ ∇_{d} & if d ∈ (obj k) \ \{a, c_{1}\}. \end{matrix}

Therefore (z_{1})_{d} = y_{d} and g(z_{1})_{d} = (F p)(z_{1})_{d} = p ∘ y_{d} for every d ∈ {c_{1}} ∪ ((obj k) \ S). This constitutes the initial induction step. Next suppose that c_{2} ∈ S \ {a, c_{1}} exists. Define z_{2} = o_{μ_{2}}^{a}(z_{1}) with μ_{2} = y_{c_{2}} ∈ k(c_{2}, a); thus

(z_{2})_{d} = \{ \begin{matrix}1_{a} & if d = a, \\ μ_{i} & if d = c_{i} for some i ∈ \{1, 2\}, \\ γ ∘ ∇_{d} & if d ∈ (obj k) \ \{a, c_{1}, c_{2}\}. \end{matrix}  (3)

Using the operation o_{μ_{2}}, we now similarly obtain

g(z_{2})_{d} = \{ \begin{matrix}p & if d = a \\ p ∘ μ_{i} & if d = c_{i} for some i ∈ \{1, 2\}, \\ p ∘ γ ∘ ∇_{d} & if d ∈ (obj k) \ \{a, c_{1}, c_{2}\}. \end{matrix}

Thus (z_{2})_{d} = y_{d} and p ∘ y_{d} = (F p)(z_{2})_{d} = g(z_{2})_{d} for every d ∈ {c_{1}, c_{2}} ∪ ((obj k) \ S). Continuing inductively along the order of S \ {a} = {c_{1}, …, c_{m}}, we conclude that for the element z_{m} = (o_{μ_{m}}^{a} ∘ … ∘ o_{μ_{1}}^{a})(z) we have (z_{m})_{d} = y_{d} and g(z_{m})_{d} = (F p)(y)_{d} for every d ∈ {c_{1}, c_{2}, … c_{m}} ∪ ((obj k) \ S) = (obj k) \ {a}.

In the final step, we apply the operation o_{μ} with μ = y_{a} ∈ k(a, a) to the element z_{m} = (o_{μ_{m}}^{a} ∘ … ∘ o_{μ_{1}}^{a})(z) (or to the element z_{0} = z in the case of S = {a}) in the same argument, to conclude that g(y) = (F p)(y). Since this holds true for any given y ∈ F a, we have g = Φ_{0}p for the k-morphism p : a → b defined by (1) – as was to be shown.

This completes the proof of Lemma 3.4.

3.12. Observation. All operations of any algebra Φ_{0}a with a ∈ obj k are idempotent.

Proof. We consider the operations o_{ν}^{a} : F a → F a first. Recall that for a given ν ∈ k(c, c′) and for any x = {x_{d} ∈ k(d, a) | d ∈ obj k}, the element x′ = o_{ν}^{a}(x) has the components

x′_{d} = o_{ν}^{a}(x)_{d} = \{ \begin{matrix}x_{c′} ∘ ν & for d = c, \\ x_{d} & for d ≠ c. \end{matrix}

Denote x′′ = o_{ν}^{a}(x′). We then have x′′_{c} = o_{ν}^{a}(x′)_{c} = x′_{c′} ∘ ν. If c′ ≠ c then x′_{c′} = x_{c′} and hence x′′_{c} = x_{c′} ∘ ν = x′_{c} while for c = c′ we have x′′_{c} = x′_{c′} ∘ ν = x′_{c} again. For d ≠ c, we have x′′_{d} = x′_{d} = x_{d}. Altogether x′′ = x′ and hence o_{ν}^{a} is idempotent.

Recall that the remaining operations ω_{c,γ}^{a} : F a → F a of Φa with c ∈ obj k and γ ∈ k(t, c) are given by

x′_{d} = ω_{c,γ}^{a}(x)_{d} = \{ \begin{matrix}x_{c} & if d = c, \\ x_{c} ∘ γ ∘ ∇_{d} & if d ∈ (obj k) \ \{c\}. \end{matrix}

Denote x′′ = ω_{c,γ}^{a}(x′). Obviously x′′_{c} = x′_{c} = x_{c} and for d ≠ c we have x′′_{d} = x′_{c} ∘ γ ∘ ∇_{d} and x′_{d} = x_{c} ∘ γ ∘ ∇_{d} and hence x′′_{d} = x′_{d} follows from the equality x′_{c} = x_{c} shown just above. Therefore x′′ = x′, and hence ω_{c,γ}^{a} is also idempotent.

The proof of Theorem 3.1 is now complete.

A weaker form of Theorem 3.1 dealing only with finite products was proved and used already in [13].

4. Representations by algebraic systems

In this section we construct a limit preserving representation of any infinite strongly connected small category k with a terminal object into the category S(1 × κ; 1) of all algebraic systems with κ = | mor k | unary operations and one unary relation. Adding the unary relation thus improves both Theorem 2.2 and Theorem 3.1 for infinite strongly connected small categories with a terminal object.

4.1. Lemma. Let k be a small strongly connected category with a terminal object. Then k can be fully embedded with the preservation of all its existing limits into the category S of algebraic systems having as many unary operations o_{ν} as k has morphisms, one unary relation U, and one α-ary relation R for which the cardinal α is one more than the cardinality of the set of objects of k.

Lemma 4.1 will be proved in 4.2–4.11 below.

4.2. To define a limit preserving functor Φ : k → S, we use the product G : k → Set of hom-functors from Section 2.

4.3. On each Ga = ∏{k(c, a) | c ∈ obj k}, we define the structure of an S-object

Φa = (Ga; U_{a}, R_{a}, {o_{ν}^{a} | ν ∈ mor k})

having a unary relation U_{a} ⊆ Ga, α-ary relation R_{a} ⊆ (Ga)^{α} and unary operations o_{ν}^{a} : Ga → Ga for ν ∈ mor k defined in 4.4–4.6 below.

4.4. First we define the unary relation U_{a} on Ga. To do this, for any c ∈ obj k we let ∇_{c} : c → t denote the unique k-morphism to the terminal object t of k and then set

U_{a} = {{γ ∘ ∇_{c} ∈ k(c, a) | c ∈ obj k} | γ ∈ k(t, a)}.

We show that (Gp)(U_{a}) ⊆ U_{b} for any p ∈ k(a, b). Indeed, for each element e = {γ ∘ ∇_{c} | c ∈ obj k}, the element e′ = (Gp)(e) has every its c-component of the form e′_{c} = p ∘ γ ∘ ∇_{c} in which p ∘ γ ∈ k(t, b), so that e′ ∈ U_{b} ⊆ Gb as claimed.

4.5. Secondly, for any ν ∈ k(c, c′), we define a unary operation o_{ν}^{a} : Ga → Ga by setting, for any x = {x_{d} ∈ k(d, a) | d ∈ obj k} ∈ Ga,

o_{ν}^{a}(x)_{d} = \{ \begin{matrix}x_{d} & for d ≠ c, \\ x_{c′} ∘ ν & for d = c. \end{matrix}

It is clear that any Gp : Ga → Gb with p ∈ k(a, b) preserves these operations.

4.6. Finally we define an α-ary relation R_{a} on Ga. This α-ary relation R_{a} is indexed by the disjoint union G = {0} ∪ obj k. We set

R_{a} = {R_{x,γ} | x ∈ Ga and γ ∈ k(t, a)},

where the entries of each element R_{x,γ} ∈ R_{a} ⊆ (Ga)^{G} are R_{x,γ}(0) = x ∈ Ga and, for any c ∈ obj k the element R_{x,γ}(c) ∈ Ga is given by

R_{x,γ}(c)_{d} = \{ \begin{matrix}x_{d} & if d = c, \\ γ ∘ ∇_{d} & if d ∈ (obj k) \ \{c\}. \end{matrix}  (4)

To verify that (Gp)^{G}(R_{a}) ⊆ R_{b} for every p ∈ k(a, b), choose any R_{x,γ} ∈ R_{a}. Then (Gp)^{G}(R_{x,γ}) ∈ (Gb)^{G} has the following entries. First, the entry at 0 ∈ G is (Gp) ∘ (R_{x,γ}(0)) = G(p)(x) = {p ∘ x_{d} | d ∈ obj k}. For any c ∈ obj k, by (4) we have

[(Gp)(R_{x,γ}(c))]_{d} = \{ \begin{matrix}p ∘ x_{c} & if d = c, \\ (p ∘ γ) ∘ ∇_{d} & if d ∈ (obj k) \ \{c\}. \end{matrix}

Hence (Gp)^{G}(R_{x,γ}) ∈ R_{b}, and (Gp)^{G}(R_{a}) ⊆ R_{b} follows.

4.7. From 4.2–4.6 it follows that setting

Φa = (Ga; U_{a}, R_{a}, {o_{ν}^{a} | ν ∈ mor k}) for a ∈ obj k and Φp = Gp for p ∈ k(a, b)

produces a well-defined one-to-one functor from k to the category S of all algebraic systems with the unary operations o_{ν} and the relations U and R.

4.8. To prove that Φ is full, let g : Ga → Gb be any mapping that preserves all operations and both relations. Select and fix some arbitrary γ ∈ k(t, a). Using this γ, let z ∈ Ga be the element defined by

z_{d} = \{ \begin{matrix}1_{a} & for d = a, \\ γ ∘ ∇_{d} & for d ∈ (obj k) \ \{a\}. \end{matrix}

Then g(z) ∈ Gb has the component g(z)_{a} ∈ k(a, b), and we denote

p = g(z)_{a}.

For γ ∘ ∇_{a} ∈ k(a, a), the mapping g preserves its corresponding operation o_{γ∘∇_{a}}, implying that g(o_{γ∘∇_{a}}^{a}(z)) = o_{γ∘∇_{a}}^{b}(g(z)). From the definition of o_{γ∘∇_{a}}^{a} and of the element z ∈ Ga it follows that for every c ∈ obj k, the element o_{γ∘∇_{a}}^{a}(z) has the c-component o_{γ∘∇_{a}}^{a}(z)_{c} = γ ∘ ∇_{c}. Therefore o_{γ∘∇_{a}}^{a}(z) ∈ U_{a} and hence o_{γ∘∇_{a}}^{b}(g(z)) = g(o_{γ∘∇_{a}}^{a}(z)) ∈ U_{b}. Thus there is a δ ∈ k(t, b) such that o_{γ∘∇_{a}}^{b}(g(z))_{c} = δ ∘ ∇_{c} for all c ∈ obj k. The operation o_{γ∘∇_{a}}^{b} does not change the d-component of its argument for d ≠ a, so that g(z)_{d} = δ ∘∇_{d} for all d ≠ a, with the same δ. For the object a ∈ obj k, the a-component o_{γ∘∇_{a}}^{b}(g(z))_{a} of o_{γ∘∇_{a}}^{b}(g(z)) is g(z)_{a} ∘ γ ∘ ∇_{a} = p ∘ γ ∘ ∇_{a} and from o_{γ∘∇_{a}}^{b}(g(z)) ∈ U_{b} it follows that δ ∘ ∇_{c} = p ∘ γ ∘ ∇_{c} for every c ∈ obj k. Therefore the element g(z) ∈ Gb has the components

g(z)_{d} = \{ \begin{matrix}p ∈ k(a, b) & if d = a, \\ p ∘ γ ∘ ∇_{d} & if d ∈ (obj k) \ \{a\}. \end{matrix}  (5)

To proceed further, we need the following

4.9. Claim. Let c ∈ obj k and μ ∈ k(c, a) be given. Let the element y = {y_{d} | d ∈ obj k} ∈ Ga be defined by

y_{d} = \{ \begin{matrix}μ & if d = c, \\ γ ∘ ∇_{d} & if d ∈ (obj k) \ \{c\}. \end{matrix}

Then g(y) = {p ∘ y_{d} | d ∈ obj k}, that is, g(y) = (Gp)(y) for any such element y ∈ Ga.

Proof. First, let us suppose that a ≠ c, and let z ∈ Ga be the element defined in 4.8. Thus the components of g(z) are as in (5) above. Write z′ = o_{γ∘∇_{a}}^{a}(o_{μ}^{a}(z)). The definition of operations o_{μ} and o_{γ∘∇_{a}} implies that z′ = y. Hence g(y) = o_{γ∘∇_{a}}^{b}(o_{μ}^{b}(g(z))). Since o_{μ}^{b} only replaces the c-component of g(z) by (g(z))_{a} ∘ μ = p ∘ μ and o_{γ∘∇_{a}}^{b} only replaces the a-component of g(z) by (g(z))_{a} ∘ γ ∘ ∇_{a} = p ∘ γ ∘ ∇_{a}, from (5) it follows that g(y) = {p ∘ y_{d} | d ∈ obj k}.

Second, if a = c, then y = o_{μ}^{a}(z) and the calculation is similar but easier. This concludes the proof of Claim 4.9.

4.10. To complete the proof of fullness of Φ, let x = {x_{d} ∈ k(d, a) | d ∈ obj k} ∈ Ga be arbitrary. Let R_{x,γ} ∈ R_{a} ⊆ (Ga)^{G} be the element of R_{a} with the previously specified γ ∈ k(t, a). Recall that the G-tuple R_{x,γ} from R_{a} has the entry R_{x,γ}(0) = x and, for every c ∈ obj k, the entry R_{x,γ}(c) ∈ Ga is given by its components

R_{x,γ}(c)_{d} = \{ \begin{matrix}x_{d} & for d = c, \\ γ ∘ ∇_{d} & for d ∈ (obj k) \ \{c\}, \end{matrix}

so that each R_{x,γ}(c) ∈ Ga has the form to which Claim 4.9 above applies. Therefore, by Claim 4.9, g(R_{x,γ}(c)) = (Gp)(R_{x,γ}(c)), meaning that g(R_{x,γ}(c))_{d} = p ∘ (R_{x,γ}(c))_{d} for every d ∈ obj k. But (Gg)^{G} sends R_{a} into R_{b}, and this implies that g(R_{x,γ}) = R_{v,δ} ∈ R_{b} for some v ∈ Gb and some δ ∈ k(t, b). For any c ∈ obj k, the element R_{v,δ}(c) ∈ Gb has the components

R_{v,δ}(c)_{d} = \{ \begin{matrix}v_{c} & for d = c, \\ δ ∘ ∇_{d} & for d ∈ (obj k) \ \{c\}, \end{matrix}

and R_{v,δ}(0) = v ∈ Gb. But R_{v,δ}(c)_{d} = p ∘ (R_{x,γ}(c))_{d} for all d ∈ obj k, so that v_{d} = p ∘ x_{d} for d = c, and δ ∘ ∇_{d} = p ∘ γ ∘ ∇_{d} for all d ∈ (obj k) \ {c}. What is then the element v ∈ Gb? The element v = R_{v,δ}(0) has the d-component v_{d} = R_{v,δ}(d)_{d} = p ∘ x_{d} ∈ k(d, b). This determines v ∈ Gb uniquely as the element v = {p ∘ x_{d} ∈ k(d, b) | d ∈ obj k}, and hence implies that v = (Gp)(x). Since x ∈ Ga was arbitrary, we conclude that g = Gp. Altogether, this shows that the functor Φ is full.

Remark. Having concluded the proof of fullness of Φ, we comment that the final part of the argument removes the proof’s dependence on the initially selected morphism γ ∈ k(t, a); any other γ′ ∈ k(t, a) would serve the purpose equally well. Indeed, if we choose another γ′ ∈ k(t, a), if z′ ∈ Ga is the element with z′_{a} = 1_{a} and z′_{d} = γ′ ∘ ∇_{d} for d ≠ a, and if p′ = (g(z′))_{a}, then the proof’s procedure shows that g(x) = (Gp′)(x) for every x ∈ Ga. Choosing an x ∈ Ga with x_{a} = 1_{a} then gives p′ = ((Gp′)(x))_{a} = (g(x))_{a} = ((Gp)(x))_{a} = p.

4.11. To show that Φ preserves all limits existing in k, let D : S → k be a diagram with a limit lim D = (l, {λ_{s} ∈ k(l, Ds) | s ∈ obj S}) in k. We claim that lim(Φ ∘ D) = (Φl, {Φλ_{s} ∈ S(Φl, ΦDs) | s ∈ obj S}) in S. The category S is complete, so that lim(Φ ∘ D) = (L, {Λ_{s} ∈ S(L, ΦDs) | s ∈ obj S}) exists in S. Let h : Φl → L denote the unique S-morphism satisfying Λ_{s} ∘ h = Φλ_{s} for every s ∈ obj S.

We know that lim(G ∘ D) = (Gl, {Gλ_{s} : Gl → GDs | s ∈ obj S}) in Set because G preserves all limits. Let V : S → Set denote the standard forgetful functor. There is a unique mapping f : V L → Gl such that Gλ_{s} ∘ f = V Λ_{s} for every s ∈ obj S. But then Gλ_{s} ∘ f ∘ V h = V Λ_{s} ∘ V h = Gλ_{s} for every s ∈ obj S, and hence f ∘ V h = 1_{Gl} because the maps Gλ_{s} form a limit cone.

The functor V : S → Set preserves all limits, so that (V L, {V Λ_{s} : V L → GDs | s ∈ obj S}) is a limit in Set. But then from V Λ_{s} ∘ V h ∘ f = Gλ_{s} ∘ f = V Λ_{s} for every s ∈ obj S it follows that V h ∘ f = 1_{V L}. Therefore the mapping f is a bijection, and we only need to show that f carries an S-morphism L → l.

To see that f preserves the unary relation, it suffices to note that U_{l} ≠ ∅. A similar observation shows that f also preserves the relation R. The unary operations are preserved because any bijection f between two algebras whose inverse h is a homomorphism must be an isomorphism. This completes the proof of Lemma 4.1.

The main result of this section will now easily follow.

4.12. Theorem. If k is an infinite strongly connected small category with a terminal object and | mor k | = α, then there is a full embedding Φ_{1} : k → S(1 × α; 1) preserving all limits existing in k.

Proof. From Lemma 4.1 it follows that there is a full embedding Φ : k → S preserving all limits such that Φa = (Ga; U_{a}, R_{a}, {o_{ν} | ν ∈ α}) ∈ S(1×α; 1, α) is an algebraic system in which U_{a} is a unary relation, R_{a} is an α-ary relation and the α operations o_{ν} on Ga are unary. Indeed, this is because k is infinite, so that | obj k | + 1 ≤ | mor k | = α and hence we can uniformly enlarge the arity | obj k | + 1 of all R_{a} with a ∈ obj k to α when necessary. Henceforth we assume that R_{a} ⊆ (Ga)^{α} for every a ∈ obj k.

Noting that the relations U_{a} and R_{a} are always non-void, in the first step we replace them by the non-void relation V_{a} = U_{a} × R_{a} which is α-ary, thereby defining an algebraic system Θa = (Ga; V_{a}, {o_{ν} | ν ∈ α}) ∈ S(1 × α; α) with one α-ary relation V_{a} and α unary operations o_{ν} : Ga → Ga.

In the second step, we define the algebraic system Φ_{1}a as the extension of the system (Θa)^{α} by α operations that are the composites Δ ∘ p_{i} of the projections p_{i} : (Θa)^{α} → Θa with i ∈ α and the diagonal map Δ : Ga → (Ga)^{α}. Since α is infinite, the algebraic system thus obtained, that is, the system

Φ_{1}a = ((Ga)^{α}; V_{a}^{α}, {o_{ν}^{α} | ν ∈ α} ∪ {Δ ∘ p_{i} | i ∈ α})

belongs to S(1 × α; 1). Setting Φ_{1}p = (Gp)^{α} for every p ∈ k(a, b) then gives rise to a limit preserving one-to-one functor Φ_{1} : k → S(1 × α; 1). A standard argument using the ‘projection’ unary operations Δ ∘ p_{i} with i ∈ α then ensures that Φ_{1} is full, cf. [10].

5. Representations of countable categories

A category U is called alg-universal if for every category Alg(Σ) of algebras of monosorted similarity type Σ there is a full and faithful functor Alg(Σ) → U. There are numerous categories U of algebras or algebraic systems that are alg-universal, see [10]. One consequence of alg-universality of U is that for every small category k there is a full embedding Ψ_{k} : k → U, see [10]. If U is an alg-universal category of algebras or algebraic systems, then these full embeddings are small in the sense that for an infinite k the size of representing objects Ψ_{k}a ∈ obj U satisfies |Ψ_{k}a| ≤ | mor k| for every a ∈ obj k and some are such that every Ψ_{k}a is finite whenever | mor k| is finite (we then say that Ψ_{k} preserves finiteness). Small full embeddings do exist, for instance, into the alg-universal category of all commutative rings with unit [4] and into numerous varieties of non-commutative semigroups [8], but no such full embedding can preserve finiteness. Small full embeddings Ψ_{k} : k → U that also preserve finiteness exist into the category of directed or undirected graphs, into Alg(1 × 2), see [10], and even into certain finitely generated varieties of (0, 1)-lattices [5] and of distributive double p-algebras [7].

But if U is any alg-universal category of algebras or algebraic systems whatsoever, then none of the full embeddings k → U can preserve finite products for the finite category k of Example 2.1. As we shall see below, any countable strongly connected category with a terminal object can be fully embedded into Alg(1 × 2) by a functor preserving limits over finitely many objects, but full embeddings into any alg-universal variety of (0, 1)- lattices or distributive double p-algebras preserving finite products do not exist because of congruence distributivity, see [12]. This is why the present paper is restricted to limit preserving full embeddings into alg-universal categories of unary algebras or algebraic systems.

To reduce the similarity type of algebras (or algebraic systems) representing countable strongly connected categories, we need the following result of [11].

5.1. Proposition. [11] There are limit preserving full embeddings (1) Ψ_{ω} : Alg(1 × ω) → Alg(1 × 2),

(2) for any n ∈ ω, a finiteness preserving Ψ_{n} : Alg(1 × n) → Alg(1 × 2), such that for each λ ∈ ω ∪ {ω}, the functor Ψ_{λ} is carried by the hom-functor Set(γ_{λ}, −) with some suitable cardinal γ_{λ} which is finite whenever λ is.

We now apply the above results to countable categories.

5.2. Corollary. Let k be a strongly connected category with a terminal object and countable | mor k |. Then there is a full embedding Φ′_{0} : k → Alg(1 × 2) preserving all limits of diagrams with finitely many objects existing in k.

Proof. We set Φ′_{0} = Ψ_{ω} ∘Φ_{0}, where Φ_{0} : k → Alg(1×ω) is the functor from Theorem 3.12 and Ψ_{ω} : Alg(1 × ω) → Alg(1 × 2) is the functor from Proposition 5.1(1).

5.3. Corollary. Let k be a strongly connected category with a terminal object and countable | mor k |. Then there is a full embedding Φ′_{1} : k → S(1 × 2 ; 1) preserving all limits existing in k.

Proof. Let Ψ_{ω} be the functor from Proposition 5.1(1). The functor Φ_{1} : k → S(1 × ω; 1) from Theorem 4.12 has the unary relation W = V^{ω} on the objects in its range. Define Φ′_{1} : k → S(1 × 2 ; 1) on k-objects by Φ′_{1}a = (Ψ_{ω}a; Z), with Z = W^{ω}, and by Φ′_{1}p = Φ_{1}p on k-morphisms.

5.4. Corollary. For any finite strongly connected category k, there is a limit preserving full embedding Λ : k → Alg(1 × 2) such that Λa is a finite algebra for every a ∈ obj k.

Proof. If k is finite, then the limit preserving full embedding Ψ : k → Alg(1 × λ) of Theorem 2.2 has λ finite and the objects Ψa are finite for all a ∈ obj k. Set Λ = Ψ_{λ} ∘ Ψ, where Ψ_{λ}; Alg(1 × λ) → Alg(1 × 2) is as in Proposition 5.1(2).n

In conclusion, we ask some naturally arising questions.

Problem 1. Is there a full embedding of Alg(1 × 2) into some Alg(n × 1) that preserves limits over finitely many algebras (or at least products of finitely many algebras)?

Problem 2. For which cardinals κ > ω, if any, is there a full embedding of Alg(1 × κ) into Alg(1 × 2) that preserves limits over finitely many algebras (or products of finitely many algebras)?

Problem 3. Fully characterize the small categories k for which there is a faithful functor H : k → Set preserving all limits (or products) existing in k.

Acknowledgment. We would like to thank David Chodounský for a fruitful discussion.

References

[1] G. Birkhoff and J. D. Lipson, Heterogeneous algebras, J. Comb. Theory 8 (1970), 115–133.

[2] P. M. Cohn, Universal Algebra, Harper and Row, New York, 1965.

[3] S. Eilenberg and S. Mac Lane, General theory of natural equivalences, Trans. Amer. Math. Soc. 58 (1945), 231–294.

[4] E. Fried and J. Sichler, Homomorphisms of commutative rings with unit element, Pacific. J. Math. 45 (1973), 485–491.

[5] P. Goralčík, V. Koubek and J. Sichler, Universal varieties of (0, 1)-lattices, Can. J. Math. 42 (1990), 470–490.

[6] G. Grätzer, Universal Algebra, Second Edition, Springer-Verlag, New York, 1979.

[7] V. Koubek, Finite-to-finite universal varieties of distributive double p-algebras, Comment. Math. Univ. Carolin. 31 (1990), 67–83.

[8] V. Koubek and J. Sichler, Universal varieties of semigroups, J. Austral. Math. Soc. (Series A) 36 (1984), 143–152.

[9] R. McKenzie, G. McNulty, and W. Taylor, Algebras, Lattices, Varieties, Vol. 1, Brooks/Cole, Monterey, California, 1987.

[10] A. Pultr and V. Trnková, Combinatorial, Algebraic and Topological Representations of Groups, Semigroups and Categories, North Holland, Amsterdam, 1980.

[11] J. Sichler and V. Trnková, Clones in topology and algebra, Acta Math. Univ. Comenianae 66 (1997), 243-260.

[12] J. Sichler and V. Trnková, Essential operations in centralizer clones, to appear in Algebra Universalis.

[13] V. Trnková and J. Sichler, All clones are centralizer clones, to appear in Algebra Universalis.

Mathematical Institute of Charles University, Sokolovská 83, 186 75 Praha 8, Czech Republic

Department of Mathematics, University of Manitoba, Winnipeg, Canada R3T 2N2

Email: trnkova@karlin.mff.cuni.cz
      sichler@cc.umanitoba.ca

This article may be accessed at http://www.tac.mta.ca/tac/ or by anonymous ftp at

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/21/2/21-02.{dvi,ps,pdf}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive abstracts of articles by e-mail as they are published. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX2e strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor. Gavin Seal, Georgia Southern University: gseal@georgiasouthern.edu

Transmitting editors.

Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown (at) btinternet.com Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Xerox Palo Alto Research Center: paiva@parc.xerox.com Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca