Theory and Applications of Categories, Vol. 7, No. 2, 2000, pp. 23–37.

A PSEUDO REPRESENTATION THEOREM FOR VARIOUS CATEGORIES OF RELATIONS

M. WINTER

Transmitted by Andrew Pitts

ABSTRACT. It is well-known that, given a Dedekind category R the category of (typed) matrices with coefficients from R is a Dedekind category with arbitrary relational sums. In this paper we show that under slightly stronger assumptions the converse is also true. Every atomic Dedekind category R with relational sums and subobjects is equivalent to a category of matrices over a suitable basis. This basis is the full proper subcategory induced by the integral objects of R. Furthermore, we use our concept of a basis to extend a known result from the theory of heterogeneous relation algebras.

1. Introduction

The calculus of binary relations has played an important rôle in the interaction between algebra and logic since the middle of the nineteenth century. A first adequate development of such algebras was given by de Morgan and Peirce. Their work has been taken up and systematically extended by Schröder in [14]. More than 40 years later, Tarski started with [15] the exhaustive study of relation algebras, and more generally, Boolean algebras with operators.

The papers above deal with relational algebras presented in their classical form. Elements of such algebras might be called quadratic or homogeneous; relations over a fixed universe. Usually a relation acts between two different kinds of objects, e.g. between boys and girls. Therefore, a variant of the theory of binary relations has evolved that treats relations as heterogeneous or rectangular. A convenient framework to do so is given by category theory [1, 12, 13].

Under certain circumstances, i.e. relational products exist or the point axiom is given, a relation algebra may be represented in the algebra Rel of concrete binary relations between sets [5, 6, 11, 13]. In other words, the algebra may be seen as an algebra of Boolean matrices.

As known, not every (homogeneous or heterogeneous) relation algebra or Dedekind category need be representable and therefore need not be an algebra of Boolean matrices [1, 3, 4]. In this paper, we will show that it is possible in every Dedekind category R with relational sums and subobjects to characterize a full subcategory B such that the matrix algebra B^{+} with coefficients from B is equivalent to R. This equivalence is not necessarily an isomorphism since isomorphic objects from R may be identified under this equivalence. The objects of B are the integral objects of R. Integral objects are defined to be those objects A such that the set of relations R[A, A] on A is an integral relation algebra in the sense of [2]. They may be characterized by the fact that their identity morphism is an atom. We call B the basis of R.

Received by the editors 1999 and, in revised form, 2000 February 7.

Published on 2000 February 16.

2000 Mathematics Subject Classification: 18D10,18D15,03G15.

Key words and phrases: Relation Algebra, Dedekind category, Allegory, Representability, Matrix Algebra.

\begin{matrix}c \\ ◯ \end{matrix} M. Winter, 2000. Permission to copy for private use granted.

As shown in [1, 17], every Dedekind category may be embedded into one with relational sums and subobjects and hence into one which is equivalent to a matrix algebra. This embedding and the equivalence above is not a trivial one. We show that B is never isomorphic or equivalent to R and hence, a proper subcategory of R.

Furthermore, we want to demonstrate the strength of our concept of a basis of a Dedekind category. Therefore, we reprove that every atomic Dedekind category may be embedded into a product of so-called simple algebras. It turns out that this product is characterized by an obvious equivalence relation on the class of objects of B.

The paper is organized as follows. In Section 2, we briefly recall some basic definitions of various categories of relations. Section 3 is dedicated to matrix algebras with coefficients taken from a given Dedekind category. The integral objects and the basis are introduced in Section 4. Afterwards in Section 5, we prove our main theorem, i.e. a pseudo-representation theorem for atomic Dedekind categories. Finally in Section 6, we reprove the theorem mentioned above.

We assume that the reader is familiar with the basic concepts of allegories, Dedekind categories and the theory of heterogeneous relation algebras. We use the notation of [13].

2. Categories of Relations

Throughout this paper, we use the following notations. To indicate that a morphism R of a category R has source A and target B we write R : A → B. The collection of all morphisms R : A → B is denoted by R[A, B] and the composition of a morphism R : A → B followed by a morphism S : B → C by R; S. Last but not least, the identity morphism on A is denoted by 𝕀_{A}.

In this section we recall some fundamentals on Dedekind categories [7, 8]. This kind of categories is called locally complete division allegories in [1]. For further details we refer to [1, 12, 13].

2.1. Definition. A Dedekind category R is a locally small category satisfying the following:

1. For all objects A and B the set R[A, B] is a complete distributive lattice. Meet, join, the induced ordering, the least and the greatest element are denoted by ⊓_{AB}, ⊔_{AB}, ⊑_{AB}, ⊥⊥_{AB}, ⊤⊤_{AB}, respectively.

2. There is a monotone operation ^{⌣} (called conversion) such that for all relations Q : A → B and R : B → C the following holds

(Q; R)^{⌣} = R^{⌣}; Q^{⌣}, (Q^{⌣})^{⌣} = Q.

3. For all relations Q : A → B, R : B → C and S : A → C the modular law

Q; R ⊓ S ⊑ Q; (R ⊓ Q^{⌣}; S)

holds.

4. For all relations R : B → C and S : A → C there is a relation S/R : A → B (called the left residual of S and R) such that for all Q : A → B the following holds

Q; R ⊑ S ⟺ Q ⊑ S/R.

All the indices of elements and operations are usually omitted for brevity and can easily be reinvented.

Note that the class of complete distributive lattices is equivalent to the class of complete Heyting algebras. A Dedekind category R is called an atomic Dedekind category if every hom-set of R is an atomic lattice. If every hom-set R[A, B] of R is a Boolean algebra, R is called a Schröder category. We denote the complement of a relation R : A → B by \overline{R}. An atomic Schröder category is also called a heterogeneous relation algebra.

We use the phrase “R is a relational category” as a shorthand for fact that R is one of the structures defined above.

In the next lemma we collect some properties we will need throughout this paper. Proofs may be found in [1, 9, 10, 12, 13, 16, 17, 18]. 2.2. Lemma. Let R be a Dedekind category, A, B, C objects of R and Q ∈ R[A, B], R_{1}, R_{2} ∈ R[B, C] and S ∈ R[A, C]. Then we have

1. Q; R_{1} ⊓ S ⊑ (Q ⊓ S; R_{1}^{⌣}); R_{1},

2. Q; (R_{1} ⊔ R_{2}) = Q; R_{1} ⊔ Q; R_{2},

3. Q; (R_{1} ⊓ R_{2}) ⊑ Q; R_{1} ⊓ Q; R_{2},

4. Q ⊑ Q; Q^{⌣}; Q,

5. ⊤⊤_{AA}; ⊤⊤_{AB} = ⊤⊤_{AB},

6. ⊤⊤_{AB}; ⊤⊤_{BB} = ⊤⊤_{AB},

7. ⊤⊤_{AB}; ⊤⊤_{BA}; ⊤⊤_{AB} = ⊤⊤_{AB}. An important class of relations is given by mappings.

2.3. Definition. Let Q ∈ R[A, B] be a relation.

1. Q is called univalent iff Q^{⌣}; Q ⊑ 𝕀_{B},

2. Q is called total iff 𝕀_{A} ⊑ Q; Q^{⌣} or equivalently iff Q; ⊤⊤_{BA} = ⊤⊤_{AA} (or, Q; ⊤⊤_{BC} = ⊤⊤_{AC} for all C),

3. Q is called a map iff Q is univalent and total. In the next lemma we collect two fundamental facts concerning univalent relations.

Proofs may be found in [1, 9, 10, 12, 13, 16, 17, 18].

2.4. Lemma. Let Q ∈ R[A, B] be univalent and R, S ∈ R[B, C]. Then we have

1. Q; (R ⊓ S) = Q; R ⊓ Q; S,

2. If R is a Schröder category and Q a mapping then \overline{Q; R} = Q; \overline{R}.

We define the notion of a homomorphism between relational categories as usual.

2.5. Definition. Let R and S be Dedekind categories and F : R → S a functor. Then F is called a homomorphism between Dedekind categories iff

1. F (_{i∈I} S_{i}) = _{i∈I} F (S_{i}),

2. F (⨆_{i∈I} S_{i}) = ⨆_{i∈I} F (S_{i}),

3. F (R^{⌣}) = F (R)^{⌣},

hold for all relations R, S_{i} with i ∈ I for some index set I. If R and S are Schröder categories and F fulfills, in addition,

4. F (\overline{R}) = \overline{F (R)},

F is called a homomorphism between Schröder categories.

A pair of homomorphisms F : R → S, G : S → R is called an equivalence iff F ∘ G and G ∘ F are naturally isomorphic to the identity functors, e.g. F and G are inverses of each other up to isomorphism.

The relational description of disjoint unions is the relational sum [13, 18]. This construction corresponds to the categorical product. By conversion, a Dedekind category is self-dual. Therefore, a product is also a coproduct. Here we want to define this concept for not necessarily finite sets of objects.

2.6. Definition. Let {A_{i} | i ∈ I} be a set of objects indexed by some set I. An object ∑_{i∈I} A_{i}, together with relations ι_{j} ∈ R[A_{j}, ∑_{i∈I} A_{i}] for all j ∈ I, is called a relational sum of

{A_{i} | i ∈ I} iff for all i, j ∈ I with i ≠ j the following holds

ι_{i}; ι_{i}^{⌣} = 𝕀_{A_{i}},  ι_{i}; ι_{j}^{⌣} = ⊥ ⊥_{A_{i}A_{j}},  ⨆_{i∈I} ι_{i}^{⌣}; ι_{i} = 𝕀_{∑_{i∈I} A_{i}}.

R “has relational sums” iff for every set of objects the relational sum does exist.

For a set of two objects {A, B}, this definition corresponds to the usual definition of a relational sum. As known, categorical products and hence relational sums, are unique up to isomorphism.

For given sets of relations Q_{i} ∈ R[A_{i}, C] and R_{i} ∈ R[A_{i}, B_{i}] for all i ∈ I and relational sums (∑_{i∈I} A_{i}, ι_{i})_{i∈I} and (∑_{i∈I} B_{i}, ι′_{i})_{i∈I}, we use the notation

⋁_{i∈I} Q_{i} := ⨆_{i∈I} ι_{i}^{⌣}; Q_{i}  ∑_{i∈I} R_{i} := ⋁_{i∈I} R_{i}; ι′_{i} = ⨆_{i∈I} ι_{i}^{⌣}; R_{i}; ι′_{i}.

Theory and Applications of Categories, Vol. 7, No. 2 27

⋁_{i∈I} Q_{i} is the coproduct morphism, i.e., it is the unique relation S such that ι_{i}; S = Q_{k} for all i ∈ I. 2.7. Lemma. Let ∑_{i∈I} A_{i} be the relational sum of {A_{i} | i ∈ I} and ∑_{j∈J} B_{j} be the relational sum of {B_{j} | j ∈ J}. Then for all R_{ij} ∈ R[A_{i}, B_{j}] the following holds

1. If R is a Schröder category then \overline{⨆_{i∈I,j∈J} ι_{i}^{⌣}; R_{ij}; ι_{j}} = ⨆_{i∈I,j∈J} ι_{i}^{⌣}; \overline{R_{ij}}; ι_{j},

2. ι_{k_{1}}^{⌣}; R_{k_{1}l_{1}}; ι_{l_{1}} ⊓ ι_{k_{2}}^{⌣}; R_{k_{2}l_{2}}; ι_{l_{2}} = ⊥⊥_{∑_{i∈I} A_{i} ∑_{j∈J} B_{j}} for all k_{1}, k_{2} ∈ I, l_{1}, l_{2} ∈ J with k_{1} ≠ k_{2}

or l_{1} ≠ l_{2}. Proof. 1. By Lemma 2.4, we have

\overline{⨆_{i∈I,j∈J} ι_{i}^{⌣}; R_{ij}; ι_{j}} = (⨆_{i∈I} ι_{i}^{⌣}; ι_{i}); \overline{⨆_{i′∈I,j′∈J} ι_{i′}^{⌣}; R_{i′j′}; ι_{j′}}; (⨆_{j∈J} ι_{j}^{⌣}; ι_{j})
= ⨆_{i∈I,j∈J} ι_{i}^{⌣}; ι_{i}; \overline{⨆_{i′∈I,j′∈J} ι_{i′}^{⌣}; R_{i′j′}; ι_{j′}}; ι_{j}^{⌣}; ι_{j}
= ⨆_{i∈I,j∈J} ι_{i}^{⌣}; \overline{⨆_{i′∈I,j′∈J} ι_{i}; ι_{i′}^{⌣}; R_{i′j′}; ι_{j′}; ι_{j}^{⌣}}; ι_{j}
= ⨆_{i∈I,j∈J} ι_{i}^{⌣}; \overline{R_{ij}}; ι_{j}.

2. Suppose k_{1} ≠ k_{2}. Then we have

ι_{k_{1}}^{⌣}; R_{k_{1}l_{1}}; ι_{l_{1}} ⊓ ι_{k_{2}}^{⌣}; R_{k_{2}l_{2}}; ι_{l_{2}} ⊑ ι_{k_{1}}^{⌣}; (R_{k_{1}l_{1}}; ι_{l_{1}} ⊓ ι_{k_{1}}; ι_{k_{2}}^{⌣}; R_{k_{2}l_{2}}; ι_{l_{2}})
= ⊥ ⊥_{∑_{i∈I} A_{i} ∑_{j∈J} B_{j}}.

The case l_{1} ≠ l_{2} is shown analogously.

Subsets inside a Dedekind category may be represented in two different ways; by vectors (a relation v such that v = ⊤⊤; v) or partial identities (a relation l such that l ⊑ 𝕀). These two concepts are equivalent and may both be used to characterize subobjects. 2.8. Definition. Let l ∈ R[A, A] be a partial identity. An object B together with a relation ψ ∈ R[B, A] is called a subobject of A induced by l iff

ψ; ψ^{⌣} = 𝕀_{B}, ψ^{⌣}; ψ = l.

A Dedekind category “has subobjects” iff for all partial identities there exists a subobject. Notice, that we have Q; R = Q ⊓ R for all partial identities Q and R (see [1, 16]).

2.9. Definition. Let R be a Dedekind category. Then R_{sub} is defined as follows:

1. The class of objects of R_{sub} is given by the class of partial identities of R.

2. The set of relations R_{sub}[l_{1}, l_{2}] between two partial identities l_{1} : A → A and l_{2} : B → B of R is defined as the set of relations R : A → B such that R = l_{1}; R; l_{2}.

The proof of the following lemma may be found in [1, 17].

2.10. Lemma. Let R be a relational category. Then R_{sub} is a relational category of the same kind with subobjects.

Obviously, the functor F : R → R_{sub} defined by

F (A) := 𝕀_{A}, F (R) := R

is an embedding of the corresponding relational categories.

3. Matrix Algebras

Given a Dedekind category R, an algebra of matrices with coefficients from R may be defined.

3.1. Definition. Let R be a Dedekind category. The algebra R^{+} of matrices with coefficients from R is defined by:

1. An object of R^{+} is a function from an arbitrary I to Obj_{R}.

2. For every pair f : I → Obj_{R}, g : J → Obj_{R} of objects from R^{+}, the set of morphisms R^{+}[f, g] is the set of all functions R : I×J → Mor_{R} such that R(i, j) ∈ R[f(i), g(j)].

3. For R ∈ R^{+}[f, g] and S ∈ R^{+}[g, h], composition is defined by

(R; S)(i, k) := ⨆_{j∈J} R(i, j); S(j, k).

4. For R ∈ R^{+}[f, g], conversion is defined by

R^{⌣}(j, i) := (R(i, j))^{⌣}.

5. For R, S ∈ R^{+}[f, g], union and intersection are defined by

(R ⊔ S)(i, j) := R(i, j) ⊔ S(i, j), (R ⊓ S)(i, j) := R(i, j) ⊓ S(i, j).

6. Identity, zero and universal elements are defined by

\begin{matrix}𝕀_{f}(i_{1}, i_{2}) := \{ \begin{matrix}⊥⊥_{f(i_{1})f(i_{2})} : & i_{1} ≠ i_{2} \\ 𝕀_{f(i_{1})}  : & i_{1} = i_{2}, \end{matrix} \\ ⊥⊥_{fg}(i, j) := ⊥⊥_{f(i)g(j)},  ⊤⊤_{fg}(i, j) := ⊤⊤_{f(i)g(j)}. \end{matrix}

7. If R is a Schröder category negation is defined by

\overline{R}(i, j) := \overline{R(i, j)}.

Obviously, a morphism in R^{+} may be seen as an (in general non-finite) matrix indexed by objects from R. The proof of the following result is an easy exercise and is, therefore, omitted.

3.2. Lemma. Let R be a relational category. Then R^{+} is a relational category of the same kind.

Furthermore, the possibility to build a disjoint union ⨄_{i∈I} J_{i} of an arbitrary set {J_{i} | i ∈

I} of sets indexed by I gives us the following lemma.

3.3. Lemma. R^{+} has relational sums.

Proof. Let {f_{i} : J_{i} → Obj_{R} | i ∈ I} be a set of objects of R^{+}. Then the function h : ⨄_{i∈I} J_{i} → Obj_{R} defined by h(j) := f_{i}(j) iff j ∈ J_{i} is also an object of R^{+}. Now, we

define

ι_{i}(j_{1}, j_{2}) := \{ \begin{matrix}⊥⊥_{f_{i}(j_{1})h(j_{2})} : & j_{1} ≠ j_{2} \\ 𝕀_{f(j_{1})} : & j_{1} = j_{2}. \end{matrix}

An easy verification shows that the above definition gives the required relational sum.

Obviously, R may be embedded into R^{+} by sending each R to the 1 × 1 matrix (R). It is easily checked that R_{sub}^{+} has relational sums, too. Hence, every relational category may be faithfully embedded into a relational category of the same kind with relational sums and subobjects.

4. Integral Objects and the Basis of R

Following concepts used in algebra, we call an object A integral if there are no zero divisors within the subalgebra R[A, A]. In other words, the homogeneous relation algebra given by the set R[A, A] is an integral relation algebra in the sense of [2]. Later on, the class of integral objects will define the basis of R.

4.1. Definition. An object A of a Dedekind category is called integral iff ⊥⊥_{AA} ≠ ⊤⊤_{AA} and for all Q, R ∈ R[A, A] the equation Q; R = ⊥⊥_{AA} implies either Q = ⊥⊥_{AA} or R = ⊥⊥_{AA}.

There are two other simple properties characterizing the integral objects of a Dedekind category.

4.2. Lemma. Let R be an atomic Dedekind category. Then the following properties are equivalent:

1. A is an integral object, 2. Every non-zero relation in R[A, A] is total,

3. 𝕀_{A} is an atom.

Proof. 1. ⇒ 3. : Suppose 𝕀_{A} is not an atom. Since R[A, A] is atomic there are at least two different atoms Q ⊑ 𝕀_{A} and R ⊑ 𝕀_{A}. We have Q; R = Q ⊓ R = ⊥⊥_{AA} which contradicts A is integral.

3. ⇒ 2. : Let Q : A → A be nonzero and suppose 𝕀_{A} ⊓ Q; Q^{⌣} = ⊥⊥_{AA}. Then we conclude a contradiction

Q = 𝕀_{A}; Q ⊓ Q
⊑ (𝕀_{A} ⊓ Q; Q^{⌣}); Q
= ⊥ ⊥_{AA}; Q
= ⊥ ⊥_{AA}.

Since 𝕀_{A} is an atom we follow 𝕀_{A} ⊓ Q; Q^{⌣} = 𝕀_{A} and hence 𝕀_{A} ⊑ Q; Q^{⌣}.

2. ⇒ 1. : Suppose Q; R = ⊥⊥_{AA} and R ≠ ⊥⊥_{AA}. Since R is total we conclude

Q = Q; 𝕀_{A} ⊑ Q; R; R^{⌣} = ⊥ ⊥_{AA}; R^{⌣} = ⊥ ⊥_{AA},

which gives us the assumption.

The special properties of the relations in R[A, A] mentioned in the last lemma may be transferred to the relation in R[A, B] for an arbitrary object B.

4.3. Lemma. Let A be an integral object of an atomic Dedekind category.

1. If Q; R = ⊥⊥_{BC} with Q ∈ R[B, A] and R ∈ R[A, C] then either Q = ⊥⊥_{BA} or R = ⊥⊥_{AC}.

2. If S ≠ ⊥⊥_{AB} then S; ⊤⊤_{BC} = ⊤⊤_{AC} for all C.

Proof. 1. Q; R = ⊥⊥_{BC} implies Q^{⌣}; Q; R; R^{⌣} = Q^{⌣}; ⊥⊥_{BC}; R^{⌣} = ⊥⊥_{AA}. Since A is integral, we have either Q^{⌣}; Q = ⊥⊥_{AA} or R; R^{⌣} = ⊥⊥_{AA}. In the first case we conclude using Lemma 2.2 Q ⊑ Q; Q^{⌣}; Q = Q; ⊥⊥_{AA} = ⊥⊥_{BA}. The other case is handled similarly.

2. Analogously to 1. ⇒ 3. and 3. ⇒ 2. of the last lemma by using 1.

Notice, that the last lemma implies that all non-zero relations in R[A, B] are total if A is integral.

4.4. Definition. Let R be a Dedekind category. The basis B_{R} of R is defined as the full subcategory given by the class of all integral objects.

As usual, we omit the index R in B_{R} when its meaning is clear from the context.

4.5. Theorem. Let R be an atomic Dedekind category with relational sums, and let B be the basis of R. Then B is a proper subalgebra of R.

Proof. Let A be an object of B and ι_{1} : A → A + A and ι_{2} : A → A + A the relational sum. Suppose 𝕀_{A+A} is an atom. Then we have

ι_{1}^{⌣}; ι_{1} ⊑ ι_{1}^{⌣}; ι_{1} ⊔ ι_{2}^{⌣}; ι_{2} = 𝕀_{A+A}.

Now, we distinguish two cases:

1. ι_{1}^{⌣}; ι_{1} = ⊥⊥_{A+AA+A}: We conclude

𝕀_{A} = 𝕀_{A}; 𝕀_{A} = ι_{1}; ι_{1}^{⌣}; ι_{1}; ι_{1}^{⌣} = ι_{1}; ⊥ ⊥_{A+AA+A}; ι_{1}^{⌣} = ⊥ ⊥_{AA},

which contradicts to 𝕀_{A} being an atom.

2. ι_{1}^{⌣}; ι_{1} = 𝕀_{A+A}: We conclude

ι_{2}^{⌣}; ι_{2} = 𝕀_{A+A}; ι_{2}^{⌣}; ι_{2} = ι_{1}^{⌣}; ι_{1}; ι_{2}^{⌣}; ι_{2} = ι_{1}^{⌣}; ⊥ ⊥_{AA}; ι_{2} = ⊥ ⊥_{A+AA+A},

which also leads to a contradiction because of the symmetry of ι_{1} and ι_{2}.

This completes the proof.

The last theorem has shown that the definition of the basis of a Dedekind category is not trivial, i.e. the basis usually does not correspond to the whole algebra.

In the rest of this section we want to define an equivalence relation ≈ on the basis of R. Later on, it turns out that the equivalence classes of ≈ characterize the simple components of the category.

4.6. Lemma. All integral objects A of an atomic Dedekind category have at most two ideal elements, namely ⊥⊥_{AA} or ⊤⊤_{AA}.

Proof. Suppose R : A → A is an ideal element. Since 𝕀_{A} is an atom R ⊓ 𝕀_{A} is either ⊥⊥_{AA} or 𝕀_{A}. Suppose R ⊓ 𝕀_{A} = ⊥⊥_{AA}. Then we have

R = R; 𝕀_{A} ⊓ ⊤ ⊤_{AA}
⊑ R; (𝕀_{A} ⊓ R^{⌣}; ⊤ ⊤_{AA})
= R; (𝕀_{A} ⊓ R)^{⌣}
= R; ⊥ ⊥_{AA}
= ⊥ ⊥_{AA}.

If R ⊓ 𝕀_{A} = 𝕀_{A} we conclude ⊤⊤_{AA} = ⊤⊤_{AA}; 𝕀_{A} ⊑ ⊤⊤_{AA}; R = R.

The last lemma leads to the following definition.

4.7. Definition. We define a relation ≈ on the class of integral objects of R by

A ≈ B : ⟺ ⊤ ⊤_{AB}; ⊤ ⊤_{BA} = ⊤ ⊤_{AA}.

4.8. Lemma. ≈ is an equivalence relation on the basis of R.

Proof. By Lemma 2.2 ≈ is reflexive. Symmetry is implied by the following property

(∗) ⊤ ⊤_{AB}; ⊤ ⊤_{BA} = ⊤ ⊤_{AA} ⟺ ⊤ ⊤_{BA}; ⊤ ⊤_{AB} = ⊤ ⊤_{BB}.

To prove this property, suppose ⊤⊤_{AB}; ⊤⊤_{BA} = ⊤⊤_{AA} and ⊤⊤_{BA}; ⊤⊤_{AB} = ⊥⊥_{BB}. Then by using Lemma 2.2

⊤ ⊤_{AB} = ⊤ ⊤_{AB}; ⊤ ⊤_{BA}; ⊤ ⊤_{AB} = ⊤ ⊤_{AB}; ⊥ ⊥_{BB} = ⊥ ⊥_{AB}

we get a contradiction. The other implication follows by duality.

To prove transitivity suppose A ≈ B and B ≈ C. By definition we have ⊤⊤_{AB}; ⊤⊤_{BA} = ⊤⊤_{AA} and ⊤⊤_{BC}; ⊤⊤_{CB} = ⊤⊤_{BB}. By (∗) we get ⊤⊤_{BA}; ⊤⊤_{AB} = ⊤⊤_{BB} and ⊤⊤_{CB}; ⊤⊤_{BC} = ⊤⊤_{CC}. Using Lemma 2.2 we conclude

⊤ ⊤_{CC} = ⊤ ⊤_{CB}; ⊤ ⊤_{BC}
= ⊤ ⊤_{CB}; ⊤ ⊤_{BB}; ⊤ ⊤_{BC}
= ⊤ ⊤_{CB}; ⊤ ⊤_{BA}; ⊤ ⊤_{AB}; ⊤ ⊤_{BC}
⊑ ⊤ ⊤_{CA}; ⊤ ⊤_{AC}

and hence A ≈ C.

Between two objects of different equivalence classes of ≈ there exists only one relation. Later on, this property gives us the possibility to separate those components.

4.9. Lemma. Let A and B be integral objects of an atomic Dedekind category. Then the following properties are equivalent:

1. A ≈ B,

2. ⊤⊤_{AB} ≠ ⊥⊥_{AB}.

Proof. 1. ⇒ 2. : Since A ≈ B we have ⊤⊤_{AB}; ⊤⊤_{BA} = ⊤⊤_{AA}. From this we conclude ⊤⊤_{AB} ≠ ⊥⊥_{AB} because otherwise we have ⊤⊤_{AB}; ⊤⊤_{BA} = ⊤⊤_{AB}; ⊥⊥_{BA} = ⊥⊥_{AA}.

2. ⇒ 1. : Lemma 4.3 gives us the assertion.

Notice, that the last lemma is still valid if only A is integral. Furthermore, this lemma implies that R = ⊥⊥_{AB} for all R ∈ R[A, B] if A ≉ B.

5. A Pseudo Representation Theorem

Now, we are able to prove our main theorem.

5.1. Theorem. Let R be an atomic Dedekind category with relational sums and subobjects and let B be the basis of R. Then R and B^{+} are equivalent. Furthermore, if R is a relation algebra R and B^{+} are equivalent as relation algebras.

Proof. First, we show that every object A of R is isomorphic to a relational sum ∑_{i∈I} A_{i}

of objects from B. Let {l_{i} | i ∈ I} be set of all atoms l_{i} ⊑ 𝕀_{A}. Because R has subobjects, this gives us a set {A_{i} | i ∈ I} of objects and a set {ψ_{i} | i ∈ I} of morphisms with

ψ_{i}; ψ_{i}^{⌣} = 𝕀_{A_{i}}, ψ_{i}^{⌣}; ψ_{i} = l_{i}.

Together with the computations

ψ_{i}^{⌣}; ψ_{i}; ψ_{j}^{⌣}; ψ_{j} = l_{i}; l_{j} = l_{i} ⊓ l_{j} = ⊥ ⊥_{AA},
ψ_{i}; ψ_{j}^{⌣} = ψ_{i}; ψ_{i}^{⌣}; ψ_{i}; ψ_{j}^{⌣}; ψ_{j}; ψ_{j}^{⌣} = ψ_{i}; ⊥ ⊥_{AA}; ψ_{j}^{⌣} = ⊥ ⊥_{A_{i}A_{j}}
and ⨆_{i∈I} ψ_{i}^{⌣}; ψ_{i} = ⨆_{i∈I} l_{i} = 𝕀_{A}.

and the uniqueness of a relational sum, we have A ≅ ∑_{i∈I} A_{i} and ψ_{i} = ι_{i}.

Suppose R ⊑ 𝕀_{A_{i}}. Then we have

ψ_{i}^{⌣}; R; ψ_{i} ⊑ ψ_{i}^{⌣}; ψ_{i} = l_{i}.

Now, we distinguish two cases:

1. ψ_{i}^{⌣}; R; ψ_{i} = ⊥⊥_{AA}: We conclude

R = ψ_{i}; ψ_{i}^{⌣}; R; ψ_{i}; ψ_{i}^{⌣} = ψ_{i}; ⊥ ⊥_{AA}; ψ_{i}^{⌣} = ⊥ ⊥_{A_{i}A_{i}}.

2. ψ_{i}^{⌣}; R; ψ_{i} = l_{i}: We conclude

R = ψ_{i}; ψ_{i}^{⌣}; R; ψ_{i}; ψ_{i}^{⌣} = ψ_{i}; l_{i}; ψ_{i}^{⌣} = ψ_{i}; ψ_{i}^{⌣}; ψ_{i}; ψ_{i}^{⌣} = 𝕀_{A_{i}}.

This shows that 𝕀_{A_{i}} is an atom and hence A_{i} in B. Now, we define the required equivalence F : R → B^{+}, G : B^{+} → R by

F (A) := f : I → Obj_{B} with f(i) = A_{i},
F (R) := h : I_{1} × I_{2} → Mor_{B} with h(i_{1}, i_{2}) = ψ_{i_{1}}; R; ψ_{i_{2}}^{⌣},
G(f) := ∑_{i∈I} f(i),
G(h) := ⨆_{i∈I,j∈J} ψ_{i}^{⌣}; h(i, j); ψ_{j}

for all R ∈ R[A, B], objects A ≅ ∑_{i∈I_{1}} A_{i}, B ≅ ∑_{i∈I_{2}} B_{i}, f ∈ Obj_{B^{+}} and h ∈ B^{+}[f, g]. Using

Lemma 2.4 and 2.7 an easy computation shows that F and G are homomorphisms of Dedekind/Schröder categories.

Moreover, we have (G ∘ F)(A) = ∑_{i∈I} A_{i} ≅ A such that there is a natural isomorphism

between G ∘ F and the identity on R. Conversely, we have

(F ∘ G)(f)(i, j) = F ( ⨆_{i∈I,j∈J}ψ_{i}^{⌣}; f(i, j); ψ_{j})
= ψ_{i}; ( ⨆_{i∈I,j∈J}ψ_{i}^{⌣}; f(i, j); ψ_{j}); ψ_{j}^{⌣}
= f(i, j).

This completes the proof.

The embedding theorems in Section 2 and 3 give us the following corollary.

5.2. Corollary. Every atomic Dedekind category may be embedded into an atomic Dedekind category which is equivalent to a matrix algebra over a suitable basis.

6. Simplicity

It is known that every homogeneous relation algebra may be embedded into a product of simple algebras. This theorem is an application of general a concept from universal algebra. In [17] it was shown that this theorem can be extended to arbitrary heterogeneous relation algebras. Furthermore, it was shown that simplicity can be characterize by just one equation, the so-called Tarski-rule

Q ≠ ⊥ ⊥_{AB} implies ⊤ ⊤_{CA}; Q; ⊤ ⊤_{BD} = ⊤ ⊤_{CD}

for all Q : A → B and A, B, C, D.

In this section, we want to reprove the embedding theorem above using our concept of the basis of a Dedekind category and the induced equivalence relation ≈.

6.1. Lemma. Let R be an atomic Dedekind category with relational sums and subobjects such that all objects of basis B are equivalent (in resp. to ≈). Then R is simple.

Proof. We show that B^{+} is simple. The equivalence of B^{+} and R then implies the assertion. Let e : I → B, f : J → B, g : K → B and h : L → B be objects of B^{+} and ⊥⊥_{fg} ≠ R ∈ B^{+}[f, g]. By definition there is a j′ ∈ J and a k′ ∈ K such that R(j′, k′) ≠ ⊥⊥_{f(j′)g(k′)}. From Lemma 4.3 and the fact that all objects of B are equivalent we conclude

⊤ ⊤_{e(i)f(j′)}; R(j′, k′); ⊤ ⊤_{g(k′)h(l)} = ⊤ ⊤_{e(i)f(j′)}; ⊤ ⊤_{f(j′)h(l)} = ⊤ ⊤_{e(i)h(l)}

for all i ∈ I and l ∈ L. This gives us

(⊤ ⊤_{ef}; R; ⊤ ⊤_{gh})(i, l) = ⨆_{j∈J,k∈K}(⊤ ⊤_{ef}(i, j); R(j, k); ⊤ ⊤_{gh}(k, l))

Theory and Applications of Categories, Vol. 7, No. 2 35

= ⨆_{j∈J,k∈K}(⊤ ⊤_{e(i)f(j)}; R(j, k); ⊤ ⊤_{g(k)h(l)})
= ⊤ ⊤_{e(i)h(l)}
= ⊤ ⊤_{eh}(i, l)

and hence ⊤⊤_{ef}; R; ⊤⊤_{gh} = ⊤⊤_{eh}.

Let B_{≈} be the set of equivalence classes of ≈, and B_{k} be the full subcategory of B induced by the equivalence class k. By the last lemma B_{k}^{+} is simple. 6.2. Definition. Let K be a set, and R_{k} for all k ∈ K be Dedekind categories. The product Dedekind category ∏_{k∈K} R_{k} is defined as follows:

1. An object of ∏_{k∈K} R_{k} is a function f : K → ⋃_{k∈K} Obj_{R_{k}} such that f(k) ∈ Obj_{R_{k}}.

2. A morphism in ( ∏_{k∈K} R_{k})[f, g] is a function Q : K → ⋃_{k∈K} R_{k}[f(k), g(k)] such that Q(k) ∈ R_{k}[f(k), g(k)].

3. The operations and constants are defined componentwise by

(Q; S)(k) := Q(k); S(k),
(Q ⊓ R)(k) := Q(k) ⊓ R(k),
(Q ⊔ R)(k) := Q(k) ⊔ R(k),
Q^{⌣}(k) := Q(k)^{⌣},
𝕀_{f}(k) := 𝕀_{f(k)},
⊤ ⊤_{fg}(k) := ⊤ ⊤_{f(k)g(k)},
⊥ ⊥_{fg}(k) := ⊥ ⊥_{f(k)g(k)},

for all Q, R ∈ ∏_{k∈K} R_{k}[f, g] and S ∈ ∏_{k∈K} R_{k}[g, h].

4. If R is a Schröder category negation is defined by \overline{Q}(k) := \overline{Q(k)}.

An easy verification shows that ∏_{k∈K} R_{k} is indeed a relational category of the same kind as the components R_{k}. 6.3. Theorem. Let R be a small atomic Dedekind category. Then B^{+} and ∏_{k∈B_{≈}} B_{k}^{+} are isomorphic.

Proof. Let f : I → Obj_{B} and g : J → Obj_{B} be objects of B^{+} and R ∈ B^{+}[f, g]. Furthermore, let

I_{k} := {i ∈ I | f(i) is a object of B_{k}},
J_{k} := {j ∈ J | g(j) is a object of B_{k}},
f_{k} : I_{k} → Obj_{B_{k}} such that f_{k}(i) = f(i),
R_{k} : I_{k} × J_{k} → Mor_{B_{k}} such that R_{k}(i, j) = R(i, j).

Then we define a functor F : B^{+} → ∏_{k∈B_{≈}} B_{k}^{+} by

F (f)(k) := f_{k},
F (R)(k) := R_{k}.

Using Lemma 4.9 we get

F (R; S)(k)(i, l) = (R; S)_{k}(i, l)
= (R; S)(i, l)
= ⨆_{j∈J} R(i, j); S(j, l)
= ⨆_{j∈J_{k}} R(i, j); S(j, l)
= ⨆_{j∈J_{k}} R_{k}(i, j); S_{k}(j, l)
= ⨆_{j∈J_{k}} F (R)(k)(i, j); F (S)(k)(j, l)
= (F (R)(k); F (S)(k))(i, l)

and hence F (R; S) = F (R); F (S). An easy verification shows the other required properties of F and is, therefore, omitted.

Combining our two main theorems, we get the following corollary.

6.4. Corollary. Let R be a small atomic Dedekind category with relational sums and subobjects. Then R and ∏_{k∈B_{≈}} B_{k}^{+} are equivalent. Furthermore, if R is a relation algebra

R and ∏_{k∈B_{≈}} B_{k}^{+} are equivalent as relation algebras.

Again, using the embedding theorems we get the following corollary.

6.5. Corollary. Every small atomic Dedekind category may be embedded into an atomic Dedekind category which is equivalent to a product of simple matrix algebras.

Acknowledgements. I am grateful to Gunther Schmidt and the unknown referee for reading, commenting and contributing to this paper.

Theory and Applications of Categories, Vol. 7, No. 2 37

References

[1] P. Freyd and A. Scedrov, Categories, Allegories (North-Holland, Amsterdam, 1990).

[2] B. Jónsson and A. Tarski, Boolean algebras with operators, Algebra Universalis 15 (1982) 127-167.

[3] R.C. Lyndon, The representation of relation algebras, Ann. of Math. (2) 51 (1950) 707-729.

[4] R.C. Lyndon, The representation of relation algebras, II, Ann. of Math. (2) 63 (1956) 294-307.

[5] R. Maddux, Some sufficient conditions for the representability of relation algebras, Algebra Universalis 8 (1978) 162-172.

[6] R. Maddux and A. Tarski, A sufficient condition for the representability of relation algebras, Notices Amer. Math. Soc. 23 (1976) A-477.

[7] Olivier, J.P., Serrato, D.: Catégories de Dedekind. Morphismes dans les Catégories de Schröder. C.R. Acad. Sci. Paris 290 (1980) 939-941.

[8] Olivier, J.P., Serrato, D.: Squares and Rectangles in Relational Categories - Three Cases: Semilattice, Distributive lattice and Boolean Non-unitary. Fuzzy sets and systems 72 (1995), 167-178.

[9] G. Schmidt, Programme als partielle Graphen, TU München, TUM-I7813 (1978).

[10] G. Schmidt, Programs as partial graph I: Flow equivalence and correctness, Theoret. Comput. Sci. 15 (1981) 1-25.

[11] G. Schmidt and T. Ströhlein, Relation Algebras: Concept of points and representability, Discrete Mathematics 54 (1985) 83-92.

[12] G. Schmidt and T. Ströhlein, Relationen und Graphen (Springer, 1989); English version: Relations and Graphs, Discrete Mathematics for Computer Scientists, EATCS Monographs on Theoret. Comput. Sci. (Springer, 1993).

[13] G. Schmidt, C. Hattensperger and M. Winter, Heterogeneous Relation Algebras, in: C. Brink, W. Kahl and G. Schmidt, ed., Relational Methods in Computer Science, Advances in Computing Science (Springer, Vienna, 1997).

[14] E. Schröder, Algebra der Logik, 3. Band (Teubner, Leipzig, 1895).

[15] A. Tarski, On the calculus of relations, J. Symbolic Logic 6 (1941) 73-89.

[16] L.H. Chin and A. Tarski, Distributive and modular laws in the arithmetic of relation algebras, University of California Press, Berkeley and Los Angeles (1951).

[17] M. Winter, Strukturtheorie heterogener Relationenalgebren mit Anwendung auf Nichtdeterminismus in Programmiersprachen (Dissertationsverlag NG, Kopierladen GmbH, München 1998)

[18] H. Zierer, Relation Algebraic Domain Constructions, Theoret. Comput. Sci. 87 (1991) 163-188.

Department of Computer Science, University of the Federal Armed Forces Munich, 85577 Neubiberg, Germany

Email: thrash@informatik.unibw-muenchen.de

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/7/n2/n2.{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 Lawrence Breen, Université Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: carboni@fis.unico.it 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 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 Andrew Pitts, University of Cambridge: Andrew.Pitts@cl.cam.ac.uk Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca 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: walters@fis.unico.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca