Theory and Applications of Categories, Vol. 11, No. 19, 2003, pp. 420–437.

COMPOSITION-REPRESENTATIVE SUBSETS

GARY GRIFFING

ABSTRACT. A specific property applicable to subsets of a hom-set in any small category is defined. Subsets with this property are called composition-representative. The notion of composition-representability is motivated both by the representability of a linear functional on an associative algebra, and, by the recognizability of a subset of a monoid. Various characterizations are provided which therefore may be regarded as analogs of certain characterizations for representability and recognizablity. As an application, the special case of an algebraic theory T is considered and simple characterizations for a recognizable forest are given. In particular, it is shown that the composition-representative subsets of the hom-set T ([1], [0]), the set of all trees, are the recognizable forests and that they, in turn, are characterized by a corresponding finite “syntactic congruence.” Using a decomposition result (proved here), the composition-representative subsets of the hom-set T ([m], [0]) (0 ≤ m) are shown to be finite unions of m-fold (cartesian) products of recognizable forests.

1. Introduction

Motivation for this work comes in part from both algebra and theoretical computer science. In algebra, one has the notion of a representative linear functional on an associative algebra A over a commutative base semi-ring k, and in theoretical computer science, one has the notion of a recognizable subset of a monoid M. Let us start by recalling the first of these closely related concepts. An element f of the dual k-module A^{∗} = Hom_{k}(A, k) is called representative if there exists a corresponding element ∑_{I} g_{i} ⊗ h_{i} of A^{∗} ⊗ A^{∗} (I a finite set) such that f(ab) = ∑_{I}(g_{i}a)(h_{i}b), for all a, b ∈ A. This property is frequently defined over a base field as in say, [A],[BL],[Mo], and the corresponding subspace of representative elements is then denoted by A^{0}. It can be proved, in the case with k a field, that the g_{i} and h_{i} may themselves be chosen to be members of A^{0}. Therefore, the assignment Δ : A^{0} → A^{0} ⊗ A^{0}, f ↦ ∑_{I} g_{i} ⊗ h_{i} defines a coassociative, comultiplication map. Moreover, the assignment ϵ : A^{0} → k, f ↦ f(1) defines a counit map for Δ, and the triple (A^{0}, Δ, ϵ) is then a coassociative, counital coalgebra, in the sense of [S].

On the other hand, a subset L of a monoid M is called recognizable (or a recognizable language in case M is free) if there exists a finite state recognizer the behavior of which equals L. A recognizer is a 4-tuple (η, Q, I, T), where I, T are subsets of the state set Q, and η: M × Q → Q, (w, q) ↦ wq is a mapping making Q a left M-set. That is, for which

Received by the editors and, in revised form, . Transmitted by John Baez. Published on 2003-12-17. 2000 Mathematics Subject Classification: 18B99, 18C99, 08A62, 08A70. Key words and phrases: recognizable language, recognizable forest, representative functional, syn-

tactic congruence, algebraic theory, translates.

\begin{matrix}c \\ ◯ \end{matrix} Gary Griffing, 2003. Permission to copy for private use granted.

1q = q and (vw)q = v(wq), for all v, w ∈ M and q ∈ Q. The behavior of the recognizer is the subset { w ∈ M | wa ∈ T, some a ∈ I }. Thus, an element w of M is accepted, or recognized, if it acts on an element of I (an initial state) and produces an element of T (a terminal state). A subset L is recognizable if L = { w ∈ M | wa ∈ T, some a ∈ I } for some recognizer (η, Q, I, T) with Q a finite set. A “representative-like” characterization for recognizability is given in [E, p.69] which states that a subset L of a monoid M is recognizable if (and only if) there exist finitely many subsets B_{i}, C_{i} of M such that L = ⋃ B_{i}C_{i} (product elementwise in M) and, whenever rs ∈ L, there exists a j with r ∈ B_{j} and s ∈ C_{j}. More generally, rather than use a free monoid, one can use a free Ω-algebra in the sense of universal algebra [C]. Elements of this algebra are referred to as terms, or trees. A recognizable forest [GS] is then a certain subset of trees. The precise definition of a recognizable forest is different from that given above for a recognizable language, and may be found in [GS, p.59]. However, the idea behind the definition is similar in that there exists the notion of a “finite tree recognizer” for recognizing certain trees. The forest recognized by a tree recognizer is called the behavior of the recognizer, and a forest R is called recognizable if there exists a finite tree recognizer whose behavior equals R.

These notions from algebra and theoretical computer science may seem different, but in fact they overlap. Suppose that the base semi-ring k is not a field, but rather the the Boolean semi-ring B whose elements are F and T, with addition and multiplication given by “or” and “and”, respectively. For any monoid M, the power set of M, PM, may be identified (via characteristic functions) with the B-module Map(M, B) of all maps from M to B. Then, a representative element of Map(M, B) corresponds precisely to a subset L of M which is recognizable!

One result of this work is to show that there exists a representative-like characterization for a recognizable forest similar to the representative-like characterization given above for a recognizable subset of a monoid. Indeed, motivated by the definition of a representative functional, especially as it applies to the case above in which the base semi-ring is B, definition 2.1 below introduces the notion of a “composition-representative” subset of a hom-set in any small category. It will then easily follow that in the special case of a category A having one object, a subset of the corresponding monoid A(·, ·) is compositionrepresentative if and only if it is a recognizable subset. Thus, composition-representability may be regarded as a many object version of recognizability. On the other hand, suppose that the category A is an algebraic theory T in the sense of [Law]. Given the objects [0], [1] of T , the hom-set T ([1], [0]) can then be identified with the set of all trees. Theorem 7.3 will show that a subset of T ([1], [0]) is composition-representative if and only if it is a recognizable forest in the sense of [GS]. In Corollary 7.4, a representative-like characterization for a recognizable forest, entirely analogous to the characterization given above for a recognizable language will be given.

The main body of this work will consist of various characterizations, valid for any category A, for which subsets (of a given hom-set) are composition-representative. As motivation, familiar characterizations for recognizability will be used as a guide. Recall, let M be a monoid and L a subset of M. Then L is a recognizable subset if and only if any one of the following equivalent conditions holds (see [E],[Lal])

1. The set { a^{−1}L | a ∈ M } is finite, where for each a ∈ M, a^{−1}L = { b ∈ M | ab ∈ L };

2. There exists a finite monoid N and a homomorphism ψ: M → N such that L = ψ^{−1}(ψ(L));

3. L determines a congruence ∼ in M for which the quotient monoid M/∼ is finite.

In Proposition 3.1, a characterization for a composition-representative subset is given, analogous to condition 1 above, as a certain subset which has a finite set of translates by morphisms. A result analogous to condition 2 is given in Theorem 4.1 where the homomorphism to a finite monoid is replaced by the existence of a functor to a category with finite hom-sets. In section 5, the definition of the “syntactic congruence” determined by a subset of morphisms is given. The connection between the syntactic congruence given here and composition-representability is then provided by Corollary 5.2, where it is shown that a subset R is composition-representative if and only if the corresponding syntactic congruence determined by R has finite index, that is each quotient hom-set is finite. This provides a characterization analogous to condition 3 above. The justification for the name syntactic here derives from the fact that in the case of a category with one object, the corresponding congruence is then exactly the syntactic (or principle) congruence determined by a subset of the corresponding monoid as given in [GS, p.40],[Lal, p.11]. In section 7, the syntactic congruence will be used to characterize a recognizable forest. It will be shown in Theorem 7.3 that a subset R (of trees) is a recognizable forest if and only if the corresponding syntactic category determined by R is finite, that is has finite hom-sets. From the point of view of X-languages, that is subsets of words in the alphabet X, this result can be considered a many object version of the classical result for free monoids ([GS],[Lal]), which characterizes a recognizable X-language as one for which the syntactic congruence has finite index, or equivalently, for which the corresponding syntactic monoid is finite.

It should be pointed out that Rosenthal in [R1],[R2] develops the general notions of a quantaloid (a certain bicategory), quantaloidal nucleus (a certain lax functor which generalizes a congruence), and corresponding quotient category. He then shows [R2],[R3] how a certain quantaloidal nucleus, called by him the syntactic nucleus, is a generalization of a certain specific congruence determined by a set of trees as given in [GS] (which is itself a generalization of the syntactic congruence determined by a language). In the context of forests, the syntactic congruence determined by a forest B, as given in this work (sections 5 and 7), can be seen to be the same as the congruence given by the syntactic nucleus j_{B} determined by B, which appears in [R2, p.204]. Further, in the papers [BK],[R2],[R3], it is shown how bicategories (and bimodules) can be used to provide a beautiful, and elegant, categorical framework in which the notion of the behavior of automata and tree automata are special cases.

The point of view of the present work is less sophisticated than that given in [BK] and by Rosenthal, being the result of a single definition. Nevertheless, certain results regarding the connection between category theory and theoretical computer science, via recognizability, are quickly arrived at and by entirely different means than by those methods given elsewhere in the literature. In subsequent papers, further aspects of compositionrepresentability will appear.

2. Main definition

All categories considered in this work are small. For any triple of objects a, b, c in a category A, composition will be given by the map A(b, c) × A(a, b) → A(a, c), (σ, ν) ↦ σ ∘ ν, and 1_{a} will denote the identity morphism in A(a, a). If γ is a morphism in A(a, c) and b any object, the set

F_{b}(γ) = { (σ, ν) | σ ∈ A(b, c), ν ∈ A(a, b), σ ∘ ν = γ }

(the inverse image of γ along the composition map) will be referred to as the set of all factorizations of γ through b. For any subset S of A(a, c), F_{b}(S) will denote the union of all factorizations through b of all morphisms in S.

2.1. Definition. Let A be a category and a, c any pair of objects. A subset R of A(a, c) is called composition-representative if for each object b in A, there exists a finite index set I_{b} and factor subsets V_{i} of A(b, c), and W_{i} of A(a, b), i ∈ I_{b}, with

F_{b}(R) = ⋃_{i∈I_{b}} V_{i} × W_{i}.

As directly implied by the definition, if R is a composition-representative subset and b an object, the corresponding set ⋃_{i∈I_{b}} V_{i} × W_{i} is uniquely determined by R and b. This set will sometimes be referred to as the b-splitting of R. An easy check shows that both ∅ and A(a, c) are composition-representative subsets of A(a, c), the trivial ones, with bsplittings ∅ and A(b, c)×A(a, b), respectively. More generally, it will be shown that the set consisting of all composition-representative subsets of any hom-set is closed with respect to finite union, intersection, and complimentation. In section 7, when the category A is taken to be an algebraic theory T (see [C],[EW],[Law]), a collection of examples of non-trivial composition-representative subsets will be provided. These subsets are the so-called recognizable forests (see [GS]). As a consequence of this, new characterizations for a recognizable forest will be given.

Applications of the results in this work are given in section 7. In particular, Corollary 7.4 gives an explicit characterization for a recognizable forest analogous to that given in the introduction for a recognizable subset of a monoid. To do this, the definition of composition-representability will be applied to the special case of an algebraic theory T . A recognizable forest will then be characterized as a subset R of trees such that for each 0 ≤ m, there exist finitely many subsets V_{i}, W_{i}, where V_{i} is a certain subset of m-tuples of trees, and W_{i} a certain subset of m-ary operations each of which can be applied to an m-tuple of trees by composition, such that R = ⋃ V_{i} ∘ W_{i} (composite elementwise in T ) and, whenever α∘β is an element of R there exists an index j such that α is an element of V_{j} and β of W_{j}. Thus in this special case, the two conditions composition-representability, and recognizability, will be shown to determine identical forests.

3. Composition-representability and translates

It will be useful to consider the set of “translates” of a given set of morphisms. Various properties which hold for of the set of translates of a fixed set of morphisms will now be proved. In particular, it will be shown that a necessary and sufficient condition for a set of morphisms to be composition-representative is that its set of translates, either left or right, be finite. Thus, for any subset S of A(a, c), object b, and pair of morphisms σ in A(b, c) and ν in A(a, b), consider the sets

σ^{−1}S = { τ ∈ A(a, b) | σ ∘ τ ∈ S } and Sν^{−1} = { τ ∈ A(b, c) | τ ∘ ν ∈ S }.

The set σ^{−1}S is called the left σ-translate, and Sν^{−1} the right ν-translate, of S.

3.1. Proposition. For any category A the following properties hold:

1. (The translate of a translate is a translate)

Let S be a subset of A(a, c), and b, d objects. Then, κ^{−1}(σ^{−1}S) = (σ ∘ κ)^{−1}S for any morphisms σ in A(b, c) and κ in A(d, b). Similarly, (Sν^{−1})μ^{−1} = S(μ ∘ ν)^{−1} for any morphisms ν in A(a, b) and μ in A(b, d).

2. A subset R of A(a, c) is composition-representative if and only if, for any object b, either

i.) the set of all left σ-translates of R, { σ^{−1}R | σ ∈ A(b, c) }, is finite, or

ii.) the set of all right ν-translates of R, { Rν^{−1} | ν ∈ A(a, b) }, is finite.

3. (Translates preserve composition-representability)

Let R be a composition-representative subset of A(a, c), b an object, and σ in A(b, c), ν in A(a, b), morphisms. Then σ^{−1}R, and Rν^{−1}, are composition-representative subsets of A(a, b), and A(b, c), respectively.

Proof. First, property 1. For any objects b, d and morphisms σ ∈ A(b, c) and κ ∈ A(d, b), κ^{−1}(σ^{−1}R) = { ν ∈ A(a, d) | κ ∘ ν ∈ σ^{−1}R }. By associativity, ν ∈ κ^{−1}(σ^{−1}R) if and only if σ ∘ κ ∘ ν ∈ R if and only if ν ∈ (σ ∘ κ)^{−1}R. Therefore κ^{−1}(σ^{−1}R) = (σ ∘ κ)^{−1}R. Similarly, (Sν^{−1})μ^{−1} = S(μ ∘ ν)^{−1} for any morphisms ν in A(a, b) and μ in A(b, d).

For the equivalence of property 2.i with composition-representability, choose an object b. Suppose that R is a composition-representative subset with b-splitting F_{b}(R) = ⋃_{I_{b}} V_{i}× W_{i}. Given σ ∈ A(b, c), let J ⊆ I_{b} be the subset of all indices j such that σ ∈ V_{j}. Then an easy check shows that σ^{−1}R = ⋃_{j∈J} W_{j}. Thus, the set { σ^{−1}R | σ ∈ A(b, c) } is finite. For the converse, suppose that the finite set of all left σ-translates (σ ∈ A(b, c)) of R is (represented by) the set { σ_{1}^{−1}R, …, σ_{k}^{−1}R }. For each i = 1, …, k, let

V_{i} = { τ ∈ A(b, c) | for all ν ∈ σ_{i}^{−1}R, τ ∘ ν ∈ R }.

Then, F_{b}(R) = ⋃_{i=1}^{k} V_{i} × σ_{i}^{−1}R. In fact, suppose that 1 ≤ j ≤ k and that (v, w) ∈ V_{j} × σ_{j}^{−1}R. Then by definition, v ∘ w ∈ R and so (v, w) ∈ F_{b}(R). For the reverse containment, let g ∘ h ∈ R with g ∈ A(b, c) and h ∈ A(a, b). Since the set of translates is finite, there exists j with g^{−1}R = σ_{j}^{−1}R. Thus, h ∈ σ_{j}^{−1}R. Moreover, if ν ∈ σ_{j}^{−1}R then g ∘ ν ∈ R, so that g ∈ V_{j}. Therefore, F_{b}(R) = ⋃_{i=1}^{k} V_{i} × σ_{i}^{−1}R and so R is a composition-representative subset. A similar argument using right ν-translates of R shows the equivalence of property 2.ii with composition-representability.

For property 3, let R be a composition-representative subset of A(a, c), b an object and σ a morphism in A(b, c). By property 2.i above, the set of all left (σ ∘ τ)-translates (τ ∈ A(d, b)) of R is a finite set. Therefore by property 1 above, the set of all left τ-translates of the fixed translate σ^{−1}R is a finite set and hence, by 2.i again, σ^{−1}R is composition-representative. Similarly, by 1 and 2.ii, for any ν ∈ A(a, b), Rν^{−1} is composition-representative whenever R is.

4. Composition-representability and finite hom-sets

In this section, Theorem 4.1 will use a certain functor to a category with finite hom-sets to give a useful characterization for composition-representability. As mentioned in the introduction, this theorem may be considered a many object version of that which in the one object monoid case states the following: A subset L of a monoid M is recognizable if and only if there exists a finite monoid N and a monoid map ψ: M → N such that L = ψ^{−1}ψ(L) (see [E],[Lal]).

Recall from [M], a congruence on a category A is an equivalence relation ∼ on each hom-set such that if σ_{1} ∼ σ_{2} (σ_{1}, σ_{2} in A(x, y)) and ν is in A(x′, x) and τ in A(y, y′), then τ ∘ σ_{1} ∘ ν ∼ τ ∘ σ_{2} ∘ ν. Given any congruence ∼ on a category X, denote by X /∼ the quotient category having as objects the objects of X, and for each pair of objects r, s, the hom-set of morphisms is given by (X /∼)(r, s) = X (r, s)/∼, the quotient set of ∼-classes [σ] with representative σ an element of X (r, s). There exists a corresponding full functor (bijective on objects)

N: X → X /∼  (1)

given by N (r) = r, and N (σ) = [σ], for all morphisms σ in X (r, s) and objects r, s of X.

For any triple x, y, z of objects of A, and pair of subsets P of A(y, z), and Q of A(x, y), their composite is defined and equals the subset of A(x, z) given by P ∘ Q = { p ∘ q | p ∈ P, q ∈ Q }. Using notation from Rosenthal (see [R1],[R2],[R3]), for any pair of subsets J of A(b, c) and S of A(a, c), the symbol J →_{r} S is defined as the largest subset of A(a, b) such that the composite J ∘ (J →_{r} S) is contained in S. That is

J →_{r} S = { τ ∈ A(a, b) | J ∘ { τ } ⊆ S }.

Similarly, for any subset K of A(a, b)

K →_{l} S = { σ ∈ A(b, c) | { σ } ∘ K ⊆ S }.

Further, if F: X → Y is any functor r, s objects of X and H is any subset of morphisms of Y(F(r), F(s)), set

F^{−1}(H) = { γ ∈ X (r, s) | F(γ) ∈ H }.

4.1. Theorem. For any subset R of A(a, c), the following are equivalent:

1. The set R is a composition-representative subset;

2. There exists a category U with finite hom-sets and a functor F: A^{op} → U, which may be taken to be full, such that R = F^{−1}F(R).

Proof. First, 1 implies 2. Fix objects a, c of A and, for now, let R be an arbitrary subset of A(a, c). Define an equivalence relation ≈ on the category A by the following

κ_{1} ≈ κ_{2} if and only if (τ ∘ κ_{1})^{−1}R = (τ ∘ κ_{2})^{−1}R, for all τ ∈ A(x, c),  (2)
where κ_{1}, κ_{2} ∈ A(x′, x) and x, x′ ∈ A.

The relation ≈ is a congruence on A. In fact, suppose that κ_{1} ≈ κ_{2} and let σ ∈ A(x, y), ν ∈ A(y′, x′), where κ_{1}, κ_{2} ∈ A(x′, x) and x, x′, y, y′ ∈ A. To show that σ∘κ_{1}∘ν ≈ σ∘κ_{2}∘ν, let τ ∈ A(y, c). Since κ_{1} ≈ κ_{2} and τ ∘ σ ∈ A(x, c), ((τ ∘ σ) ∘ κ_{1})^{−1}R = ((τ ∘ σ) ∘ κ_{2})^{−1}R. By taking the left ν-translate of each expression in this last equality, and applying Proposition 3.1 and associativity of composition, (τ ∘(σ∘κ_{1}∘ν))^{−1}R = (τ ∘(σ∘κ_{2}∘ν))^{−1}R. Thus, ≈ is a congruence on A.

Let A/≈ denote the quotient category, and N: A → A/≈ the corresponding quotient functor. The functor N further satisfies the property that R = N^{−1}N (R). In fact, it is always true that R ⊆ N^{−1}N (R). Thus, let τ ∈ A(a, c) and N (τ) ∈ N (R). Then for some ν ∈ R, N (τ) = N (ν), that is τ ≈ ν. By display (2) (with x = c and x′ = a) and since 1_{c} ∈ A(c, c), (1_{c} ∘ τ)^{−1}R = (1_{c} ∘ ν)^{−1}R, that is τ^{−1}R = ν^{−1}R. Now, ν ∈ R implies that 1_{a} ∈ ν^{−1}R = τ^{−1}R. Therefore, τ = τ ∘ 1_{a} ∈ R, and R = N^{−1}N (R) as claimed.

Now let R be a composition-representative subset of A(a, c). By Proposition 3.1, for any object x′ the set of left translates { σ^{−1}R | σ ∈ A(x′, c) } is a finite set. Thus, given objects x, x′ and a morphism κ ∈ A(x′, x), there are at most finitely many distinct left translates of the form (τ ∘ κ)^{−1}R with τ ∈ A(x, c). Hence, there are at most finitely many distinct ≈-classes [κ], and the quotient category A/≈ has finite hom-sets. Thus, the category U = (A/≈)^{op} has finite hom-sets and the corresponding functor F: A^{op} → U, with F = N^{op}, satisfies R = F^{−1}F(R).

For the converse, given a category U with finite hom-sets, use the functor F: A^{op} → U given by hypothesis to define a congruence ∼ on A by the following: η ∼ τ if and only if F(η) = F(τ), for all τ, η ∈ A(x, y) with x, y any objects of A. Let b be any object and σ ∈ A(b, c). Then since F(σ) ∈ U(F(c), F(b)) and U has finite hom-sets by hypothesis, there can be no more than a finite number of distinct ∼-classes. Thus ∼ has finite index, and let { [σ_{1}], …, [σ_{k}] } (σ_{i} ∈ A(b, c)) represent the finite set of congruence classes that partition A(b, c). Then, F_{b}(R) = ⋃_{i=1}^{k}[σ_{i}] × ( [σ_{i}] →_{r} R). In fact, if 1 ≤ j ≤ k, v ∈ [σ_{j}] and w ∈ [σ_{i}] →_{r} R, then the composite v ∘ w is an element of R by definition. Thus, (v, w) ∈ F_{b}(R). To see the reverse containment, suppose a composite β ∘ α ∈ R, with β ∈ A(b, c) and α ∈ A(a, b). Then, there exists some j with β ∈ [σ_{j}]. To show that α ∈ [σ_{j}] →_{r} R, it must be shown that if η ∈ [σ_{j}] then η ∘ α ∈ R. Thus, let η ∈ [σ_{j}]. By transitivity η ∼ β, which implies F(η) = F(β). Since β ∘ α ∈ R

F(η ∘ α) = F(α) ∘ F(η) = F(α) ∘ F(β) = F(β ∘ α) ∈ F(R).

Hence, η ∘ α ∈ F^{−1}F(R) = R. Therefore, F_{b}(R) = ⋃_{i=1}^{k}[σ_{i}] × ( [σ_{i}] →_{r} R) and R is a composition-representative subset.

By a completely symmetric argument to that just given above, it can also be shown that F_{b}(R) = ⋃_{j=1}^{t}( [κ_{j}] →_{l} R) × [κ_{j}], where { [κ_{j}] | j = 1, …, t } represents the finite set of ∼-classes that partition A(a, b).

5. The syntactic congruence

A given subset of morphisms will now directly determine a congruence, called the “syntactic congruence” and denoted by ≡, without first considering translates as was done for the congruence ≈ given previously in display (2). It will then be shown that these two congruences are identical, that is τ_{1} ≡ τ_{2} if and only if τ_{1} ≈ τ_{2}, for any objects x, y of A and pair of morphisms τ_{1}, τ_{2} in A(x, y). Thus from Theorem 4.1, the syntactic congruence will have finite index if and only if the subset which determines it is composition-representative.

5.1. Definition. Let a, c be objects of A and S any subset of A(a, c). The set S determines a congruence on A, denoted by ≡ and called the syntactic (or principal) congruence, by the following: For any pair of objects a′, c′ of A and morphisms τ_{1}, τ_{2} in A(a′, c′), then

τ_{1} ≡ τ_{2} provided that σ ∘ τ_{1} ∘ ν ∈ S if and only if σ ∘ τ_{2} ∘ ν ∈ S,
for all ν ∈ A(a, a′), σ ∈ A(c′, c).

As is readily shown (or, see the next corollary), ≡ is indeed a congruence. The corresponding (quotient) category A/≡ is called the syntactic category determined by S. The syntactic category is said to be finite if the congruence ≡ has finite index, that is if each hom-set of A/≡ is finite.

5.2. Corollary. Let R be any subset of A(a, c). The syntactic congruence ≡ and the congruence ≈ given in display (2) are identical; thus, R is composition-representative if and only if the syntactic category determined by R is finite. Moreover, the following are equivalent:

1. The syntactic category determined by R is finite;

2. Given any objects x, y of A and a morphism σ in A(x, y), each ≡-class [σ] is a composition-representative subset of A(x, y), and the set R is saturated by the congruence ≡; that is, R = ⋃_{i=1}^{k}[σ_{i}], σ_{i} in A(a, c), with empty union if R = ∅.

Proof. Let R be an arbitrary subset of A(a, c). Suppose that ≡ is the syntactic congruence determined by R and ≈ is the congruence given by display (2). It will now be shown that the congruences ≡ and ≈ determine identical congruence classes. Let x, y be objects and τ_{1}, τ_{2} ∈ A(x, y) morphisms. If τ_{1} ≡ τ_{2}, then for all ν ∈ A(a, x), σ ∈ A(y, c), σ ∘τ_{1} ∘ν ∈ R if and only if σ ∘τ_{2} ∘ν ∈ R. It follows that for all σ ∈ A(y, c), ν ∈ (σ ∘τ_{1})^{−1}R if and only if ν ∈ (σ ∘ τ_{2})^{−1}R. That is, for all σ ∈ A(y, c), (σ ∘ τ_{1})^{−1}R = (σ ∘ τ_{2})^{−1}R. Therefore, τ_{1} ≈ τ_{2}. Conversely, if τ_{1} ≈ τ_{2}, then N (τ_{1}) = N (τ_{2}), where N: A → A/≈ is the corresponding quotient functor. In the second paragraph of the proof of Theorem 4.1, it was shown that R = N^{−1}N (R). If σ ∘ τ_{1} ∘ ν ∈ R for some ν ∈ A(a, x) and σ ∈ A(y, c), then

N (σ ∘ τ_{2} ∘ ν) = N (σ) ∘ N (τ_{2}) ∘ N (ν) = N (σ) ∘ N (τ_{1}) ∘ N (ν)
= N (σ ∘ τ_{1} ∘ ν) ∈ N (R).

Hence, σ ∘ τ_{2} ∘ ν ∈ N^{−1}N (R) = R. By reversing the roles of τ_{1} and τ_{2}, the condition σ ∘ τ_{2} ∘ ν ∈ R implies that σ ∘ τ_{1} ∘ ν ∈ R (for all ν ∈ A(a, x), σ ∈ A(y, c)), and so τ_{1} ≡ τ_{2}. Thus, τ_{1} ≡ τ_{2} if and only if τ_{1} ≈ τ_{2}. Therefore, the categories A/≡ and A/≈ may be identified, and hence, A/≡ has finite hom-sets if and only if A/≈ has finite homsets. By Theorem 4.1, with (A/≈)^{op} = U, the latter condition is equivalent to R being a composition-representative subset.

To see the equivalence of 1 and 2, given any pair of objects x, y of A and morphism σ ∈ A(x, y), let S = { τ ∈ A(x, y) | τ ≡ σ } denote the ≡-class containing σ, now regarded merely as a subset of A(x, y). The subset S will be shown to be compositionrepresentative. It will suffice, by Theorem 4.1, to show that S = N^{−1}N (S), where N is the functor given above with codomain category now denoted by A/≡. But, this follows immediately by the definition of N and the transitivity of ≡. Since the congruence ≡ has finite index, for each pair of objects x, y of A, the finitely many ≡-classes partition A(x, y). In particular, R ⊆ ⋃_{σ}[σ] (σ ∈ A(a, c)) a finite union of such classes. Moreover, if [σ] ⋂ R ≠ ∅ for some σ ∈ A(a, c), then [σ] ⊆ R. In fact, suppose that γ ∈ [σ] ⋂ R. If τ ∈ [σ], then τ ≡ γ by transitivity. Therefore, N (τ) = N (γ) ∈ N (R). Since the subset R composition-representative, τ ∈ N^{−1}N (R) = R. Thus, [σ] ⊆ R. This shows that R is equal to the union of those (finitely many) classes [σ] for which [σ] ⋂ R ≠ ∅.

Conversely, suppose that R equals a finite union of ≡-classes each of which is a composition-representative subset of A(a, c). Then as (easily follows from) the definition, or the next corollary shows, any finite union of composition-representative subsets of A(a, c) is composition-representative. Hence, R is a composition-representative subset and the syntactic congruence determined by R has finite index.

Recall, if X is any set, then an algebra of sets is any sub-Boolean algebra of the power set Boolean algebra PX. Thus, an algebra of sets is any nonempty subset of PX which is closed with respect to finite union and intersection, and complimentation. Given any category A, the power set of each hom-set, PA(x, y), is a Boolean algebra. For notation, let C_{xy} denote the subset of PA(x, y) consisting of all the composition-representative subsets of A(x, y).

5.3. Corollary. For any pair of objects x, y of a category A, the subset C_{xy} of the Boolean algebra PA(x, y) forms an algebra of sets. That is

1. C_{xy} is closed under finite unions;

2. C_{xy} is closed under finite intersections;

3. C_{xy} is closed under (relative) compliments.

Proof. To see 1 and 2, fix objects x, y and let R and S be composition-representative subsets of A(x, y). For any object z of A, suppose that ⋃_{I_{z}} V_{i} × W_{i} is a z-splitting of R and ⋃_{J_{z}} X_{j} × Y_{j} is a z-splitting of S. Then, as can be easily checked, ⋃_{I_{z}∪J_{z}}{ V_{i} × W_{i} } ∪ { X_{j} × Y_{j} } is a z-splitting for R ∪ S. Similarly, ⋃_{I_{z}×J_{z}}{ V_{i} ∩ X_{j} } × { W_{i} ∩ Y_{j} } is a z-splitting for R ∩ S. Hence, R ∪ S and R ∩ S are each composition-representative subsets. Thus by induction, finite unions and intersections of composition-representative subsets are composition-representative. Now to see 3. For any subsets R, S of A(x, y), the relative compliment of R in S, S \ R, is equal to S ⋂( A(x, y) \ R). Using the result 2 above for finite intersections, it will suffice to show that the compliment A(x, y) \ R is in C_{xy} whenever R is. Thus, let R be a composition-representative subset of A(x, y). Using Corollary 5.2, partition A(x, y) into a finite union of ≡-classes, where ≡ is the finite syntactic congruence on A determined by R. By the same corollary, each such ≡-class is a composition-representative subset, and R is equal to a union over a certain subset of those classes. Therefore the compliment, A(x, y) \ R, equals a finite union (over the complimentary subset) of such classes. By the result 1 above for finite unions, A(x, y) \ R is a composition-representative subset.

The following corollary will show that composition-representability is a certain property of a subset of morphisms R which gets inherited by the factor subsets of morphisms of a b-splitting of R, for any object b. This is analogous to the situation over a base field (as mentioned in the introduction) of a representative element f of the dual space A^{∗} of an associative algebra A, for which the corresponding element ∑_{I} g_{i} ⊗ h_{i} (I finite) of A^{∗} ⊗ A^{∗} may be chosen so that each g_{i}, h_{i} are themselves representative.

5.4. Corollary. Suppose that R is a composition-representative subset in a category A. For any object b of A, the b-splitting of R may be chosen so that the factor subsets are themselves composition-representative.

Proof. Let R be a composition-representative subset of A(a, c), b an object, and ≡ the finite syntactic congruence determined by R. Then, using the functor N: A → A/≡ given in the first half of the proof of Theorem 4.1, the second half of the same proof (with ∼ replaced by ≡ and F replaced by N^{op}) shows that the b-splitting of R may be taken to be F_{b}(R) = ⋃_{i=1}^{k}[σ_{i}] × ( [σ_{i}] →_{r} R), where { [σ_{i}] | i = 1, …, k } represents the finite set of ≡-classes that partition A(b, c). Fix an index 1 ≤ j ≤ k. It will now be shown that [σ_{j}] and [σ_{j}] →_{r} R are each composition-representative subsets. Corollary 5.2 shows that the congruence class [σ_{j}] is a composition-representative subset of A(b, c). Now consider the subset [σ_{j}] →_{r} R of A(a, b). More generally, for any subset J ⊆ A(b, c), it will be shown that J →_{r} R is a composition-representative subset of A(a, b). Set J^{−1}S = ⋃_{σ∈J} σ^{−1}S for any subset S of A(a, c). Then, the following identity holds

J →_{r} R = A(a, b) \ J^{−1}( A(a, c) \ R ).

In fact by definition, τ ∈ J →_{r} R if and only if for all σ ∈ J, σ ∘ τ ∈ R. Thus, τ ∈ J →_{r} R if and only if for all σ ∈ J, σ ∘ τ ∉ A(a, c) \ R. The latter is equivalent to τ ∉ J^{−1}( A(a, c) \ R), which is equivalent to τ ∈ A(a, b) \ J^{−1}(A(a, c) \ R). Thus, the equality in the display holds. By Corollary 5.3, A(a, c)\R is a composition-representative subset. By Proposition 3.1, J^{−1}( A(a, c)\R ) is a finite union of composition-representitive subsets, which by Corollary 5.3, is composition-representative. Then by the identity above, and Corollary 5.3 one more time, J →_{r} R is composition-representative. Therefore, for each b, the b-splitting of R may be written as a finite union ⋃_{I_{b}} H_{i} × K_{i}, with H_{i} and K_{i} composition-representative subsets for all i ∈ I_{b}.

Observe the following. The collection of all composition-representative subsets in a category A can be used to generate a topology making A a topological category, that is a category with a topology on each hom-set, whose composition map is a continuous. In fact, Corollary 5.3 shows that the collection consisting of all composition-representative subsets in a given category A may be regarded as constituting a base of open (and closed) sets for a topology in (each hom-set of) A. Then given R, a member of the base of open sets in A(a, c), and given an object b, consider the inverse image of R along the composition map, that is F_{b}(R). By definition, F_{b}(R) = ⋃_{I_{b}} V_{i} × W_{i} (with I_{b} finite). Corollary 5.4 shows that each subset V_{i}, W_{i} may be chosen to be a member of the base of open subsets. Hence each V_{i} × W_{i}, and thus F_{b}(R) itself, is an open subset of the direct product A(b, c) × A(a, b), and composition is continuous.

6. A decomposition result for product categories

The concept of composition-representability will now be applied to the case of a category which itself consists of the product of finitely many categories. By induction, it will suffice to establish the result for two categories A_{1} and A_{2}. Recall that A_{1} × A_{2} denotes the product category whose objects consist of pairs α = (a_{1}, a_{2}) of objects a_{i} of A_{i}. Given an object γ = (c_{1}, c_{2}), a morphism in (A_{1} × A_{2})(α, γ) consists of a pair (σ_{1}, σ_{2}) of morphisms σ_{i} in A_{i}(a_{i}, c_{i}). Composition (for composable pairs) and identity are given componentwise.

The proof of the next proposition is a general adaptation, using Theorem 4.1 above, of the proof of a corresponding result (see [E]) characterizing recognizable subsets of M × N, where M and N are monoids. This result can also be considered an analogue of the result (see [S]) for associative algebras A, B, over a base field, which asserts that the vector spaces (A ⊗ B)^{0} and A^{0} ⊗ B^{0} may be identified. (Recall, A^{0} denotes the space of representative elements of the dual space A^{∗}.)

6.1. Proposition. Let A_{1}, A_{2} be categories and α, γ objects of A_{1} × A_{2}. Suppose that R is a subset of (A_{1} × A_{2})(α, γ). Then, the following are equivalent:

1. The set R is a composition-representative subset;

2. There exists a decomposition R = ⋃_{j=1}^{p} B_{1j} × B_{2j}, where for each j, B_{ij} is a composition-representative subset of A_{i}(a_{i}, c_{i}) ( i = 1, 2 ).

Proof. First, to see that 1 implies 2, choose objects α = (a_{1}, a_{2}), γ = (c_{1}, c_{2}) of A_{1} ×A_{2}, and let R be a composition-representative subset of (A_{1} × A_{2})(α, γ). By Theorem 4.1, there exists a category U with finite hom-sets and a (contravarient) functor F: A_{1} ×A_{2} → U, such that R = F^{−1}F(R). Now for each i = 1, 2, define a (contravarient) functor H_{i}: A_{i} → U, by the following: Let x_{i}, y_{i} be objects of A_{i}. Set H_{1}(x_{1}) = F(x_{1}, a_{2}), H_{2}(x_{2}) = F(c_{1}, x_{2}), and for any morphism r ∈ A_{1}(x_{1}, y_{1}), set H_{1}(r) = F(r, 1_{a_{2}}), and for any morphism s ∈ A_{2}(x_{2}, y_{2}), set H_{2}(s) = F(1_{c_{1}}, s). The verification that each H_{i} is a functor is immediate. Hence, there exists a (contravarient) functor H: A_{1} ×A_{2} → U, with H = H_{1} × H_{2}. For notation, let U_{i} denote the finite set U(H_{i}(c_{i}), H_{i}(a_{i})) (i = 1, 2), and define the following (finite) subset of U_{1} × U_{2}

E = { (ν_{1}, ν_{2}) | ν_{i} ∈ U_{i} (i = 1, 2), and ν_{1} ∘ ν_{2} ∈ F(R) }.

Observe that the following condition holds: ρ = (r, s) ∈ R if and only if H(ρ) ∈ E. In fact by the definition of H, H(ρ) = (H_{1}(r), H_{2}(s)) and

H_{1}(r) ∘ H_{2}(s) = F(r, 1_{a_{2}}) ∘ F(1_{c_{1}}, s) = F((1_{c_{1}}, s) ∘ (r, 1_{a_{2}}))
= F(r, s) = F(ρ).

Thus, H(ρ) is an element of E if and only if F(ρ) is an element of F(R), that is if and only if ρ is an element of F^{−1}F(R) = R. Therefore, with ν = (ν_{1}, ν_{2})

R = H^{−1}(E) = ⋃_{ν∈E} H^{−1}{ (ν_{1}, ν_{2}) } = ⋃_{ν∈E} H_{1}^{−1}{ ν_{1} } × H_{2}^{−1}{ ν_{2} },

a finite union. Now by Theorem 4.1, each H_{i}^{−1}{ ν_{i} } is a composition-representative subset of A_{i}(a_{i}, c_{i}) for all ν_{i}, where i = 1, 2.

Conversely, let objects α, γ be given as above. Since, by Corollary 5.3, a finite union of composition-representative subsets is a composition-representative subset, it will suffice to let B = B_{1}×B_{2} a subset of (A_{1}×A_{2})(α, γ), where each B_{i} is a composition-representative subset of A_{i}(a_{i}, c_{i}) (i = 1, 2). Then for any object β = (b_{1}, b_{2}) and morphism σ = (σ_{1}, σ_{2}) of (A_{1} × A_{2})(β, γ), it is easy to verify that σ^{−1}B = σ_{1}^{−1}B_{1} × σ_{2}^{−1}B_{2}. Hence

{ σ^{−1}B | σ ∈ (A_{1} × A_{2})(β, γ) } = { σ_{1}^{−1}B_{1} × σ_{2}^{−1}B_{2} | σ_{i} ∈ A_{i}(b_{i}, c_{i}), i = 1, 2 }.

By hypothesis, for each i, the set of translates { σ_{i}^{−1}B_{i} | σ_{i} ∈ A_{i}(b_{i}, c_{i}) } is finite. Thus, the right side of the display is finite and therefore so is the left. By Proposition 3.1, B is a composition-representative subset.

7. Application: Algebraic theories and recognizable forests

Classically, a recognizable forest, as given in [GS], is a specific set of trees in a graded set Ω of n-ary (0 ≤ n) operations. Such forests consist of trees which are accepted by a certain finite state machine. The acceptability of a tree is then defined in terms of certain conditions imposed on the image of the unique map from the initial Ω-algebra to a prescribed finite Ω-algebra. More recently, a categorical interpretation of a recognizable forest, by way of algebraic theories, was given in [BK],[R2],[R3]. This method involves, in part, the theory of categories enriched in certain bicategories and a specific pair (I, T) consisting of an initial, and a terminal, bimodule. In this framework, a recognizable forest consists of those trees which arise as the elements of (a value of) the composite bimodule I ∘ T. On the other hand, [BG] studied recognizable tree series. In that work, the set M of all Ω-trees was taken as the initial Ω-algebra. Then, over a base field F, a certain (proper) subspace of the space of “representative” elements of (F M)^{∗} = Hom_{F} (F M, F), where F M (the vector space with M as a basis) is taken as the initial linear Ω-algebra, was considered. The elements of that subspace are the recognizable tree series. A recognizable tree series may also be regarded as a generalization of a recognizable forest in that weights, other than 0 or 1, are allowed as coefficients (or values) of the trees. These tree series were then characterized as those linear functionals having a certain finite-dimensional space of translates, or equivalently, those that annhilate an ideal of F M having finite codimension, or equivalently, those that factor through a finite-dimensional Ω-algebra. This situation is reminiscent of the characterizations given in, say, [A],[Mo] for A^{0} with A an associative algebra. By analogy, Theorem 7.3 will provide similar characterizations for a recognizable forest, and in Corollary 7.4, a simple “representative-like” characterization for such a forest will be given.

To give a categorical characterization of a recognizable forest, or equivalently, of a recognizable tree series with coefficients from the Boolean semi-ring B, results from previous sections will now be applied to the special case in which the category A is taken to be an algebraic theory T (see [BK],[C],[EW],[Law]). Thus, T is a certain category whose objects are the finite sets [n] = { 1, …, n }, n = 0, 1, …, and in which the (skeleton of the) category of finite sets (and maps) is a subcategory. Note, [0] = ∅ is initial [1] is terminal, and coproduct is disjoint union with [m] the m-fold coproduct of [1] for all 0 ≤ m. The n-ary (0 ≤ n) operations of the theory are the morphisms [1] → [n] of T . In general, for any 0 ≤ m, n, a morphism [m] → [n] of T consists of an m-cotuple [σ_{1}, …, σ_{m}] (induced by the coproduct) of n-ary operations σ_{i}: [1] → [n].

Let Set denote the category of sets and maps. A T -algebra is a product preserving functor G: T^{op} → Set. Thus G([1]) = A is a set, and for 0 ≤ n, G([n]) = A^{n}. Whenever ψ: [1] → [n] is an n-ary operation of T , ψ_{A} = G(ψ): A^{n} → A will denote the corresponding n-ary operation in A. Further, given any m-cotuple morphism [τ_{1}, …, τ_{m}]: [m] → [k] in T , G([τ_{1}, …, τ_{m}]) = (Gτ_{1}, …, Gτ_{m}): A^{k} → A^{m} is the unique corresponding m-tuple map induced by the m maps G(τ_{i}): A^{k} → A (0 ≤ k, m). Since G is product preserving, if an n-ary operation is the jth (coproduct) injection ι_{j}: [1] → [n], then G(ι_{j}) = π_{j}: A^{n} → A is the jth (product) projection.

A morphism of T -algebras is a natural transformation between corresponding functors. Thus given T -algebras F and G with F([1]) = A, G([1]) = B, say, a morphism from F to G is a family of component maps η_{[m]}: A^{m} → B^{m} (0 ≤ m) such that whenever τ: [j] → [k] in T , then η_{[j]} ∘ F(τ) = G(τ) ∘ η_{[k]} holds for all 0 ≤ j, k. Given 1 ≤ k, each component η_{[k]} is determined by the component η_{[1]}. In fact, by taking τ = ι_{i}: [1] → [k] (coproduct injection), then η_{[1]} ∘ π_{i} = π_{i} ∘ η_{[k]}. It follows that a T -algebra morphism (from F to G) can equivalently be described by a map η: A → B such that η (ψ_{A}(a_{1}, …, a_{n})) = ψ_{B}(η a_{1}, …, η a_{n}), for all n-ary operations ψ: [1] → [n] of T (0 ≤ n), and a_{i} ∈ A. With composition taken as (vertical) composition of natural transformations, and identity the identity natural transformation, there results the category of T -algebras.

7.1. Definition. Given an algebraic theory T , the set of trees is the set of all morphisms [1] → [0] in T , that is the hom-set T ([1], [0]). A forest is any subset of T ([1], [0]).

What are referred to here as trees are also called terms in [BK],[R2],[R3]. As is shown in [EW], the set T ([1], [0]) is (a realization of) the free T -algebra on [0], that is the initial object in the category of T -algebras. In particular, suppose that ψ: [1] → [n] is an n-ary (0 ≤ n) operation in T . Then, denoting by ψ_{T} the corresponding n-ary operation in T ([1], [0]), and given n elements ν_{i} of T ([1], [0]), the n-cotuple [ν_{1}, …, ν_{n}]: [n] → [0] is a morphism in T and the corresponding element ψ_{T} (ν_{1}, …, ν_{n}) of T ([1], [0]) is given by the composite

ψ_{T} (ν_{1}, …, ν_{n}) = [ν_{1}, …, ν_{n}] ∘ ψ.  (3)

The universal property follows from the observation that given any T -algebra A, there exists a unique T -algebra morphism given by the map

η: T ([1], [0]) → A, σ ↦ σ_{A},

where σ_{A}: A^{0} → A^{1} is (identified with) the corresponding element of A.

The following definition of a recognizable forest is the characterization given in [GS, p.95] of the formal definition of a recognizable forest as given previously in [GS, p.60].

7.2. Definition. A subset R of T ([1], [0]) is a recognizable forest if there exists a finite T -algebra A such that the unique T -algebra morphism η: T ([1], [0]) → A satisfies R = η^{−1}η(R).

The next Theorem will provide a connection between, algebraic theories, compositionrepresentability, and theoretical computer science via recognizable forests. Using certain bicategories called quantaloids and the corresponding quantaloidal nuclei [R1],[R2],[R3], along with concepts of bimodules for a category enriched in a bicategory [BK], an entirely different treatment of a connection between recognizable forests and algebraic theories was given. Also, a check shows that the syntactic congruence ≡ determined by a forest B, say, is the same as the congruence arising from the syntactic nucleus j_{B} as given by Rosenthal [R2, p.204],[R3, p.294]. Then as the following will show, this congruence is of finite index if and only if the forest B is composition-representative, or equivalently, recognizable.

7.3. Theorem. For any subset R of T ([1], [0]), the following are equivalent:

1. The subset R is a composition-representative subset, equivalently, the syntactic category determined by R is finite;

2. The set R is a recognizable forest.

Proof. First, observe that the equivalence stated in hypothesis 1 is given by Corollary 5.2 in the special case when A = T . To show 1 implies 2, suppose that R is a compositionrepresentative subset of T ([1], [0]). Therefore by Theorem 4.1, there exists a category U with finite hom-sets and a (full) functor F: T^{op} → U with R = F^{−1}F(R). Set B = U(F([0]), F([1])), a finite set. Then, B gets converted into a finite T -algebra as follows. Define a functor G: T^{op} → Set on objects by G([n]) = B^{n}, for all 0 ≤ n. Given an m-cotuple morphism ψ = [ψ_{1}, …, ψ_{m}]: [m] → [n], define G(ψ): B^{n} → B^{m} as the m-tuple map (Gψ_{1}, …, Gψ_{m}) uniquely induced by the m maps G(ψ_{i}): B^{n} → B, which themselves remain to be defined. Thus, for any ψ: [1] → [n], write ψ_{B} = G(ψ) and define such a map ψ_{B}: B^{n} → B by the following (since F is full, each morphism in B is of the form Fν for some ν: [1] → [0])

ψ_{B}(Fν_{1}, …, Fν_{n}) = F([ν_{1}, …, ν_{n}] ∘ ψ),  (4)

for all Fν_{i} ∈ B, 1 ≤ i ≤ n, with ψ_{B} = Fψ for n = 0. In particular, if ι_{j}: [1] → [n] is the jth (coproduct) injection, then one checks that G(ι_{j}) = π_{j} is the jth (product) projection. A check also shows that if ψ: [m] → [n] and φ: [n] → [p], then G(φ ∘ ψ) = G(ψ) ∘ G(φ) for 0 ≤ m, n, p, and, that G preserves identity. Therefore, G is a product preserving functor and B, with this structure, is a (finite) T -algebra. Recall from above that T ([1], [0]) is a T -algebra. Now by regarding the functor F as a map of the corresponding morphism sets, F: T ([1], [0]) → B defines a T -algebra morphism. In fact, by displays (3) and (4)

F(ψ_{T} (ν_{1}, …, ν_{n})) = F([ν_{1}, …, ν_{n}] ∘ ψ) = ψ_{B}(Fν_{1}, …, Fν_{n}),

for all n-ary ψ: [1] → [n] (0 ≤ n) and elements ν_{i} ∈ T ([1], [0]) with 1 ≤ i ≤ n. Thus, R is a recognizable forest.

To show 2 implies 1, let R be a recognizable forest and A a finite T -algebra with η: T ([1], [0]) → A the unique T -algebra morphism such that R = η^{−1}η(R). Suppose that G: T^{op} → Set, G([1]) = A, is a (product preserving) functor providing the T - algebra structure on A. Thus, for each 0 ≤ n, G([n]) = A^{n} is a finite set. Consider the full subcategory S_{0} of Set having as objects the sets A^{n} for 0 ≤ n. The functor G factors through the inclusion functor (S_{0} ⊆ Set) as T^{op} → S_{0} ⊆ Set, and the corestricted functor (G with its codomain restricted) will coninue to be denoted by G. That is, G: T^{op} → S_{0}, where S_{0} is a category with finite hom-sets. Now regard G as a map of corresponding morphism sets and then restrict it (again with the same name) to the hom-set T ([1], [0]). Thus write G: T ([1], [0]) → A, where the set A is being identified with the hom-set S_{0}(A^{0}, A^{1}). Then, by display (3) and since G preserves the (categorical) product in T^{op}

G(ψ_{T} (ν_{1}, …, ν_{k})) = G([ν_{1}, …, ν_{k}] ∘ ψ) = G(ψ) ∘ G([ν_{1}, …, ν_{k}])
= ψ_{A}(Gν_{1}, …, Gν_{k}),

for all k-ary ψ: [1] → [k] (0 ≤ k) and elements ν_{i} ∈ T ([1], [0]) with 1 ≤ i ≤ k. Thus when so restricted, G: T ([1], [0]) → A is a T -algebra morphism which, by uniqueness, must be equal to η. Hence R = G^{−1}G(R) and, by Theorem 4.1, R is a composition-representative subset.

Recall, for any 0 ≤ m, [m] is the m-fold coproduct of [1]. Thus for 0 ≤ m, n, the following map may be regarded as an identification

T ([m], [n]) → (T ([1], [n]))^{m}, [σ_{1}, …, σ_{m}] ↦ (σ_{1}, …, σ_{m}),  (5)

where each σ_{i}: [1] → [n]. Then by way of this identification, any subset of T ([m], [0]) can be canonically identified with a subset of m-tuples of trees. The following corollary will now provide an explicit formulation for the characterization of a recognizable forest as a composition-representative subset.

7.4. Corollary. A subset R of T ([1], [0]) is a recognizable forest if and only if for each 0 ≤ m there exists a finite set of subsets V_{i} of T ([m], [0]) and W_{i} of T ([1], [m]), such that R = ⋃ V_{i} ∘ W_{i} and, whenever α ∘ β is in R there exists an index j such that α is in V_{j} and β in W_{j}. Moreover, each V_{i} may be taken to be the ≡-class [σ_{i}], and W_{i} the corresponding subset [σ_{i}] →_{r} R, where ≡ is the finite syntactic congruence determined by R, and {[σ_{i}]} forms the finite set of ≡-classes that partition T ([m], [0]).

Proof. Let R be a subset of T ([1], [0]). By the previous theorem, R is a recognizable forest if and only if it is a composition-representative subset. Therefore by definition, for any object [m] of T (0 ≤ m), there exist finitely many factor subsets V_{i} of T ([m], [0]) and W_{i} of T ([1], [m]) such that F_{[m]}(R) = ⋃ V_{i} × W_{i}. By Theorem 4.1, the subsets V_{i} and W_{i} may be chosen to have the form asserted above.

Observe, by the comment following Theorem 4.1, there is an alternate form for the factor sets V_{i} and W_{i} occuring in the above corollary. That is, each V_{i} can be taken as [κ_{i}] →_{l} R, and W_{i} as [κ_{i}], where {[κ_{i}]} represents the finite set of ≡-classes that partition T ([1], [m]).

A characterization for the composition-representative subsets of T ([m], [n]) will now be given.

7.5. Corollary. Let 0 ≤ n. If 1 ≤ m, a subset R of T ([m], [n]) is a compositionrepresentative subset if and only if R can be (canonically) identified with a set of the form ⋃_{i=1}^{p} B_{i1} × ⋯ × B_{im}, where for each i, B_{ij} ( j = 1, …, m) is a composition-representative subset of T ([1], [n]). If in this case n = 0 and 1 ≤ m, then each B_{ij} is a recognizable forest. Finally, if m = 0 ( 0 ≤ n) then every subset of T ([0], [n]) is a composition-representative subset.

Proof. For the last statement, if m = 0 the only subsets of T ([0], [n]) are ∅, and T ([0], [n]) itself, each of which are composition-representative subsets. Now let 1 ≤ m. By display (5), R can be canonically identified with a subset of the product (T ([1], [n]))^{m}, the hom-set of a corresponding product category. The first statement now follows from Proposition 6.1 by induction on m, and the second from Theorem 7.3.

One final observation can now be made. By using right translates in an argument similar to that given in the proof of Corollary 5.4, for any subset J of T ([1], [m]) and recognizable forest R in T ([1], [0]), it can be shown that J →_{l} R is a compositionrepresentative subset of T ([m], [0]). By Corollary 7.5, J →_{l} R may then be identified with a finite union of m-fold cartesian products of recognizable forests. In the special case when J = {ψ}, a singelton m-ary operation of T , {ψ} →_{l} R is such a finite union, uniquely determined by R and ψ. Thus, for each m-ary operation ψ: [1] → [m] of T (0 ≤ m), {ψ} →_{l} (·) may be regarded as a non-deterministic m-ary “co-operation” on the set consisting of all recognizable forests.

References

[A] E. Abe, “Hopf Algebras,” Cambridge tracts in math. 74, Cambrige Univ. Press, Cambrige, London, Sydney 1977.

[BK] R. Betti, S. Kasangian, Tree automata and enriched category theory, Rend. Istit. Mat. Univ. Trieste 17 (1-2) (1985), 71-78.

[BG] R.E. Block, G. Griffing, Recognizable formal series on trees and cofree coalgebraic systems, J. Algebra 215 (1999), 543-573.

[BL] R.E. Block, P. Leroux, Generalized dual coalgebras of algebras, with applications to cofree coalgebras, J. Pure Appl. Algebra 36 (1985), 15-21.

[C] P.M. Cohn, “Universal Algebra,” Math. and its Appl. Vol 6, D. Reidel, Dordrecht, Boston, London 1986.

[E] S. Eilenberg, “Automata Languages and Machines,” Vol. A, Academic Press, New York and London 1974.

[EW] S. Eilenberg, J.B. Wright, Automata in general algebras, Inform. and Control 11 (1967), 452-470.

[GS] F. Gécseg, M. Steinby, “Tree Automata,” Akad. Kaidó, Budapest 1984.

[Lal] G. Lallement, “Semigroups and Combinatorial Applications,” Wiley, New York 1979.

[Law] F.W. Lawvere, Functorial semantics of algebraic theories, Proc. Nat. Acad. Sci. U.S.A. 50 (1963), 869-872.

[M] S. MacLane, “Categories for the Working Mathematician,” Springer Verlag, New York, Heldelberg, Berlin 1971.

[Mo] S. Montgomery, “Hopf algebras and their actions on rings,” CBMS number 82, AMS, 1993.

[R1] K.I. Rosenthal, Free quantaloids, J. Pure and Appl. Algebra 72 (1991), 67-82.

[R2] K.I. Rosenthal, Quantaloidal nuclei, the syntactic congruence and tree automata, J. Pure and Appl. Algebra 77 (1992), 189-205.

[R3] K.I. Rosenthal, Quantaloids, enriched categories and automata theory, Appl. Cat. Struct. 3 (1995), 279-301.

[S] M.E. Sweedler, “Hopf Algebras,” W.A. Benjamin, New York 1969.

Department of Mathematics California State University, San Bernardino San Bernardino, CA 92407

Email: griffing@math.csusb.edu

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/11/19/11-19.{dvi,ps}

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.

The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi, Postscript and PDF. Details will be e-mailed to new subscribers. 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}TEX is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at http://www.tac.mta.ca/tac/. You may also write to tac@mta.ca to receive details by e-mail.

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@barrs.org, Associate Managing Editor Lawrence Breen, Université Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of Wales Bangor: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Palo Alto Research Center: paiva@parc.xerox.com Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca, Managing Editor Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca