Theory and Applications of Categories, Vol. 10, No. 11, 2002, pp. 220–247.

DERIVED OPERATIONS IN GOGUEN CATEGORIES

MICHAEL WINTER

ABSTRACT. Goguen categories were introduced in [13] as a suitable categorical description of L-fuzzy relations, i.e., of relations taking values from an arbitrary complete Brouwerian lattice L instead of the unit interval [0, 1] of the real numbers. In this paper we want to study operations on morphisms of a Goguen category which are derived from suitable binary functions on the underlying lattice of scalar elements, i.e., on the abstract counterpart of L.

1. Introduction

To handle uncertain or incomplete information, Zadeh [16] introduced the concept of fuzzy sets. Later on, Goguen [5] generalized this concept to L-fuzzy sets and relations for an arbitrary completely distributive lattice L (or at least a complete Brouwerian lattice) instead of the unit interval [0, 1] of the real numbers. To model linear logic Barr [1] uses ∗-autonomous lattices for L. Later on, those lattices are replaced by ∗-autonomous categories to generalize the lattice construction. It is well-known that the category of L-fuzzy relations between sets constitutes a Dedekind category introduced in [8].

On the other hand, in [13] it was shown that a suitable algebraic formalization for arbitrary L-fuzzy relations demands an extra operator. In particular, it was shown that there is no formula in the theory of Dedekind categories expressing the fact that a given L-fuzzy relation is 0-1 crisp, i.e., all entries are either the least element 0 or the greatest element 1. Therefore, the concept of Goguen categories was introduced. It was shown that the standard model of L-fuzzy relations is indeed a Goguen category and that the abstract notion of crispness in this theory coincides with 0-1 crispness of L-fuzzy relations.

Since t-norms are suitable candidates for conjunctions and t-conorms for disjunction they are widely used within applications of fuzzy theory. Usually, operations on fuzzy sets and/or relations derived from t-norms and t-conorms are the basic means to combine several parts of a fuzzy system. For example, the decision-module within a fuzzy controller, i.e., the process deciding which rule on the linguistic variables is activated with a certain degree, may be modeled by a suitable composition operator. Therefore, every theory intended on describing fuzzy systems should be able to model such operations. The corresponding notion of t-norms and t-conorms for complete Brouwerian lattices is given by complete lattice-ordered semi groups introduced in [5].

The aim of this paper is to define such derived operations within arbitrary Goguen categories and prove their basic properties. This shows once more (cf. [13, 14, 15]) that Goguen categories are suitable to describe arbitrary L-fuzzy systems.

Received by the editors 2002 March 20 and, in revised form, 2002 May 27.

Transmitted by Michael Barr. Published on 2002 June 24.

2000 Mathematics Subject Classification: 18B10, 03G15.

Key words and phrases: Goguen category, Fuzzy Relation, Dedekind category.

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

We assume that the reader is familiar with the basic concepts of allegories [4] and/or Dedekind categories [8].

2. Lattices and Antimorphisms

In this section we will introduce some well-known results from lattice theory (cf. [2]). We denote a lattice and the induced ordering by (L, ⊔, ⊓) resp. ⊑.

A lattice is called complete iff for every subset M ⊆ L (including ∅) the least upper bound ⨆ M and the greatest lower bound M of M in L exists. Notice, that a complete lattice has a least element 0 = ⨆ ∅ = L and a greatest element 1 = ∅ = ⨆ L.

A distributive lattice L is called a complete Brouwerian lattice iff L is complete and x ⊓ ⨆ M = ⨆_{y∈M}(x ⊓ y) holds for all x ∈ L and M ⊆ L.

Suppose f : L [figure] L is a monotone function, i.e., x ⊑ y implies f(x) ⊑ f(y) for all x, y ∈ L, on a complete lattice L. If a is an element from L such that a ⊑ f(a) then there exists a least fixpoint μ_{f}(a) of f greater or equal to a, i.e., f(μ_{f}(a)) = μ_{f}(a), a ⊑ μ_{f}(a) and if f(b) = b and a ⊑ b then we have μ_{f}(a) ⊑ b.

A predicate 𝔓 is called admissible (or continuous) iff for every set M ⊆ L the property 𝔓(x) for all x ∈ M implies 𝔓(⨆ M). The so-called principle of fixpoint induction states that for every admissible predicate 𝔓, monotone function f : L [figure] L, and a ∈ L with a ⊑ f(a) we may conclude from 𝔓(a) (basis step) and 𝔓(b) implies 𝔓(f(b)) for every b ∈ L (induction step) that 𝔓(μ_{f}(a)) holds. For n-ary predicates we get a similar result by taking the n-ary product of the underlying lattices.

The set of all functions between two lattices (L_{1}, ⊓, ⊔) and (L_{2}, ⊓, ⊔) may be ordered pointwise. This structure is again a lattice, and will be denoted by (L_{1} [figure]L_{2}, ⊔, ⊓). This lattice inherits interesting properties from L_{2}, i.e., if L_{2} is a complete Brouwerian lattice then so is L_{1} [figure] L_{2}.

A function f : L_{1} [figure]L_{2} is called antitonic iff x ⊑ y implies f(y) ⊑ f(x) for all

x, y ∈ L_{1}. The set of all antitone functions L_{1} [figure: ⊒]L_{2} constitutes a sublattice of L_{1} [figure] L_{2}. Again, this sublattice inherits interesting properties from L_{1} [figure] L_{2}. A function f : L_{1} [figure]L_{2} is called an antimorphism iff f(⨆ M) = f(M) for all

subsets M of L_{1}. Every antimorphism is antitonic, and we have f(0) = f(⨆ ∅) = ∅ = 1. The set of all antimorphisms L_{1} [figure: anti] L_{2} need not to be a sublattice of L_{1} [figure] L_{2} or L_{1}

[figure: ⊒] L_{2}. But this set forms a closure system, i.e., is closed under arbitrary intersections and contains the greatest function x ↦ 1. Therefore, it induces the following closure operation

τ(f) := {h | f ⊑ h and h antimorphism}.

τ is a monotone mapping from L_{1} [figure]L_{2} to L_{1} [figure: anti]L_{2}, and we have f ⊑ τ(f) and τ^{2}(f) = τ(f) for all f. Now, L_{1} [figure: anti] L_{2} together with the operations τ(⨆_{i∈I} f_{i}) and _{i∈I} f_{i} forms a complete lattice.

Unfortunately, the definition of τ gives us no information about the image of τ(f) for a given value x ∈ L_{1}. Therefore, consider the following operation

φ(f)(x) := ⨆_{{M⊆L_{1} \atop ⊔M=x}} _{y∈M} f(y).

This φ is monotonic, expanding and we have the following.

2.1. Lemma. Let L_{1} be a complete Brouwerian lattice, L_{2} a complete lattice and f : L_{1} [figure] L_{2} be antitonic. Then we have τ(f) = μ_{φ}(f).

A proof may be found in [14]. The last lemma gives us the possibility to prove properties of τ using fixpoint induction.

Later on, we will use a slightly modified definition of φ.

2.2. Lemma. Let L_{1} be a complete Brouwerian lattice, L_{2} a complete lattice and f : L_{1} [figure] L_{2} be antitonic. Then we have

φ(f)(x) = ⨆_{{M⊆L_{1} \atop ⊔M⊒x}} _{y∈M} f(y).

Proof. The inclusion ⊑ is trivial. Suppose M is a subset of L_{1} such that ⨆ M ⊒ x. Then define N := {x ⊓ y | y ∈ M} and conclude

⨆ N = ⨆_{y∈M}(x ⊓ y) = x ⊓ ⨆ M = x.

Furthermore, x ⊓ y ⊑ y and hence f(y) ⊑ f(x ⊓ y). This implies _{y∈M} f(y) ⊑ _{z∈N} f(z) and

⨆_{⊔M⊒x}_{y∈M} f(y) ⊑ ⨆_{⊔M=x}_{y∈M} f(y) = φ(f)(x).

3. Dedekind Categories

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 [figure] B. The collection of all morphisms R : A [figure] B is denoted by R[A, B] and the composition of a morphism R : A

[figure]B followed by a morphism S : B [figure]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 [8, 9]. This kind of categories are called locally complete division allegories in [4].

3.1. Definition. A Dedekind category R is a category satisfying the following:

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

2. There is a monotone operation ^{⌣} (called converse) mapping a relation Q : A [figure] B to Q^{⌣} : B [figure]A such that for all relations Q : A [figure]B and R : B [figure]C the following holds: (Q; R)^{⌣} = R^{⌣}; Q^{⌣} and (Q^{⌣})^{⌣} = Q.

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

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

4. For all relations R : B  [figure] C and S : A  [figure] C there is a relation S/R : A  [figure] B

(called the left residual of S and R) such that for all X : A [figure]B the following holds: X; R ⊑ S ⟺ X ⊑ S/R.

Notice, that by convention composition binds more tightly than meet. Therefore, axiom 3 may be written as Q; R ⊓ S ⊑ Q; (R ⊓ Q^{⌣}; S).

Corresponding to the left residual, we define the right residual by Q\R := (R^{⌣}/Q^{⌣})^{⌣}. This relation is characterized by Q; Y ⊑ R ⟺ Y ⊑ Q\R.

3.2. Definition. Let L be a complete Brouwerian lattice. Then the structure of L-fuzzy relations is defined as follows:

1. The objects are sets.

2. A relation Q : A [figure] B between two sets A and B is function from A × B to L.

3. For Q : A  [figure] B and R : B  [figure] C composition is defined by

(Q; R)(x, z) := ⨆_{y∈B} Q(x, y) ⊓ R(y, z).

4. For Q : A [figure] B the converse is defined by Q^{⌣}(x, y) := Q(y, x).

5. For Q, S : A [figure] B join and meet are defined by

(Q ⊔ S)(x, y) := Q(x, y) ⊔ S(x, y), (Q ⊓ S)(x, y) := Q(x, y) ⊓ S(x, y).

6. The identity, zero and universal elements are defined by

𝕀_{A}(x, y) := \{ \begin{matrix}0 : & x ≠ y \\ 1 : & x = y, \end{matrix} \begin{matrix}⊥ ⊥_{AB}(x, y) := 0, \\ ⊤ ⊤_{AB}(x, y) := 1. \end{matrix}

There are some differences between the last definition and the corresponding one in [1]. First of all, in our definition the objects are usual sets (or L-fuzzy sets with trivial structure maps). Furthermore, we do not require any extra structure on L so far. Later on, possible extra structure is used to define new operations on this category. Notice, that the contravariant involution on L-fuzzy relations in [1] is in our framework a combination of a negation operation and converse.

224  MICHAEL WINTER

The L-fuzzy relations constitute a Dedekind category. Such a relation is called 0-1 crisp iff R(x, y) = 0 or R(x, y) = 1 holds for all x and y. Crisp relation may be identified with classical relations, i.e., with relations over the truth values. Consequently, for crisp relations we will use the term R(x, y) as a shorthand for R(x, y) = 1.

In the next lemma we have collected some basic properties of relations in a Dedekind category. We will use these properties throughout the paper without mentioning. Proofs may be found in [3, 4, 10, 11, 12]. 3.3. Lemma. Let R be a Dedekind category, A, B, C, D objects of R and Q_{1}, Q_{2}, Q_{i} : A [figure]B, R_{1}, R_{2}, R_{i} : B [figure]C for i ∈ I, S, S_{1}, S_{2} : A [figure]C and T : B

[figure] D. Then we have

1. ⊥ ⊥ _{AB}^{⌣} = ⊥ ⊥_{BA}, ⊤ ⊤ _{AB}^{⌣} = ⊤ ⊤_{BA} and 𝕀_{A}^{⌣} = 𝕀_{A},

2. ⊤ ⊤_{AA}; ⊤ ⊤_{AB} = ⊤ ⊤_{AB}; ⊤ ⊤_{BB} = ⊤ ⊤_{AB}; ⊤ ⊤_{BA}; ⊤ ⊤_{AB} = ⊤ ⊤_{AB},

3. Q_{1}; ⊥ ⊥_{BC} = ⊥ ⊥_{AB}; R_{1} = ⊥ ⊥_{AC},

4. (_{i∈I} R_{i})^{⌣} = _{i∈I} R_{i}^{⌣},

5. (⨆_{i∈I} R_{i})^{⌣} = ⨆_{i∈I} R_{i}^{⌣},

6. if Q_{1} ⊑ Q_{2} and R_{1} ⊑ R_{2} then Q_{1}; R_{1} ⊑ Q_{2}; R_{2},

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

8. Q_{1}; (⨆_{i∈I} R_{i}) = ⨆_{i∈I} Q_{1}; R_{i},

9. Q_{1}; (_{i∈I} R_{i}) ⊑ _{i∈I} Q_{1}; R_{i},

10. (Q_{1} ⊓ S; ⊤ ⊤_{CB}); T = Q_{1}; T ⊓ S; ⊤ ⊤_{CD},

11. Q_{1} ⊑ Q_{1}; Q_{1}^{⌣}; Q_{1},

12. S/𝕀_{C} = S and 𝕀_{A}\S = S,

13. Q_{2} ⊑ Q_{1}, R_{2} ⊑ R_{1} and S_{1} ⊑ S_{2} implies S_{1}/R_{1} ⊑ S_{2}/R_{2} and Q_{1}\S_{1} ⊑ Q_{2}\S_{2},

14. (S/R_{1}); R_{1} ⊑ S and Q_{1}; (Q_{1}\S) ⊑ S,

15. _{i∈I}(S/R_{i}) = S/ ⨆_{i∈I} R_{i} and _{i∈I}(Q_{i}\S) = ⨆_{i∈I} Q_{i}\S.

In some sense a relation of a Dedekind category may be seen as an L-relation. The lattice L may equivalently be characterized by the ideal relations, i.e., a relation J : A

[figure] B satisfying ⊤ ⊤_{AA}; J; ⊤ ⊤_{BB} = J, or by the scalar relations.

3.4. Definition. A relation α : A [figure]A is called a scalar on A iff α ⊑ 𝕀_{A} and ⊤ ⊤_{AA}; α = α; ⊤ ⊤_{AA}. The set of all scalars on A is denoted by Sc_{R}(A).

The notion of ideal elements was introduced by Jónsson and Tarski [6] and the notion of scalars by Furusawa and Kawahara [7].

For an element l of a complete Brouwerian lattice L we may define a scalar in the category of L-fuzzy relations by

α_{l}(x, y) = \{ \begin{matrix}l iff & x = y, \\ 0 iff & x ≠ y. \end{matrix}

Obviously, this constitutes an isomorphism between L and the lattice of scalars. Therefore, we identify the elements of L and the scalar relations.

Notice that we have α; β = α ⊓ β since scalars are partial identities. Furthermore, the collection of ideal elements on A is isomorphic to the collection of scalars on A via the mappings ϕ(J) := J ⊓ 𝕀_{A} and ϕ^{−1}(α) := α; ⊤ ⊤_{AA}.

3.5. Lemma. Let α, β be a scalar on A and Q ∈ R[A, B]. Then we have

1. α; Q = α; ⊤ ⊤_{AB} ⊓ Q,

2. α; Q = Q; ( ⊤ ⊤_{BA}; α; ⊤ ⊤_{AB} ⊓ 𝕀_{B}),

3. (α ⊓ β); Q = α; Q ⊓ β; Q.

Proof. 1. We immediately conclude

α; ⊤ ⊤_{AB} ⊓ Q = (α; ⊤ ⊤_{AA} ⊓ 𝕀_{A}); Q Lemma 3.3 (10)
= α; Q.  ϕ is an isomorphism

2. Consider the following computation.

Q; ( ⊤ ⊤_{BA}; α; ⊤ ⊤_{AB} ⊓ 𝕀_{B}) = ⊤ ⊤_{AA}; α; ⊤ ⊤_{AB} ⊓ Q Lemma 3.3 (10)
= α; ⊤ ⊤_{AA}; ⊤ ⊤_{AB} ⊓ Q α scalar
= α; ⊤ ⊤_{AB} ⊓ Q  Lemma 3.3 (2)
= α; Q  by 1.

3. The inclusion ⊑ is trivial. Using the modular law and the isomorphism ϕ we conclude

α; Q ⊓ β; Q ⊑ (α ⊓ β; Q; Q^{⌣}); Q ⊑ (α ⊓ β; ⊤ ⊤_{AA}); Q = (α ⊓ β; ⊤ ⊤_{AA} ⊓ 𝕀_{A}); Q = (α ⊓ β); Q

and hence the assertion.

4. Goguen Categories

In [13], it was shown that we need an additional concept to define a suitable algebraic theory of L-fuzzy relations. Our approach introduces two operations mapping every relation to the greatest crisp relation it contains resp. to the least crisp relation it is included in. We now give the abstract definition.

4.1. Definition. A Goguen category G is a Dedekind category with ⊥ ⊥_{AB} ≠ ⊤ ⊤_{AB} for all objects A and B together with two operations ^{↑} and ^{↓} satisfying the following:

1. R^{↑}, R^{↓} : A  [figure] B for all R : A  [figure] B.

2. (^{↑},^{↓}) is a Galois correspondence, i.e., S ⊒ R^{↑} ⟺ R ⊑ S^{↓} for all R, S : A [figure] B.

3. (R^{⌣}; S^{↓})^{↑} = R^{↑}^{⌣}; S^{↓} for all R : B  [figure] A and S : B  [figure] C.

4. If α ≠ ⊥ ⊥_{AA} is a nonzero scalar then α^{↑} = 𝕀_{A}.

5. For all antimorphisms f : Sc_{G}(A) [figure: anti]G[A, B] such that f(α)^{↑} = f(α) for all α ∈ Sc_{G}(A) and all R : A [figure] B the following equivalence holds

R ⊑ ⨆_{{α:A [figure] A \atop α scalar}}α; f(α) ⟺ (α\R)^{↓} ⊑ f(α) for all α ∈ Sc_{G}(A).

The obvious definition of ^{↑} and ^{↓} for L-fuzzy relations gives the standard model.

4.2. Theorem. Let L be a complete Brouwerian lattice. Then the Dedekind category of L-fuzzy relations together with the operations

R^{↑}(x, y) := \{ \begin{matrix}1 iff & R(x, y) ≠ 0 \\ 0 iff & R(x, y) = 0 \end{matrix} , R^{↓}(x, y) := \{ \begin{matrix}1 iff & R(x, y) = 1 \\ 0 iff & R(x, y) ≠ 1 \end{matrix} ,

is a Goguen category.

A proof of the theorem above and all other properties in this section not given here may be found in [13].

According to the definitions in the last theorem we define crispness in an arbitrary Goguen category as follows.

4.3. Definition. A relation R : A [figure]B of a Goguen category is called crisp iff R^{↑} = R (or equivalently R^{↓} = R). The crisp fragment G^{↑} of G is defined as the collection of all crisp relations of G.

Notice, that the fact that (^{↑},^{↓}) is a Galois correspondence implies

1. R ⊑ R^{↑↓} and R ⊒ R^{↓↑},

2. R^{↑} = R^{↑↓↑} and R^{↓} = R^{↓↑↓},

DERIVED OPERATIONS IN GOGUEN CATEGORIES  227

3. (⨆_{i∈I} R_{i})^{↑} = ⨆_{i∈I} R_{i}^{↑} and (_{i∈I} R_{i})^{↓} = _{i∈I} R_{i}^{↓}.

A strong version of Axiom 5, where both inclusions are replaced by equality, is also valid.

In the next lemma we have collected some basic properties of Goguen categories. 4.4. Lemma. Let G be a Goguen category. Then the following holds:

1. 𝕀_{A}^{↑} = 𝕀_{A}.

2. R^{↓↑} = R^{↓}.

3. R^{↑↓} = R^{↑}.

4. ^{↑} is a closure and ^{↓} a kernel (or co-closure) operation, i.e., ^{↑} is monotonic, R ⊑ R^{↑}, R^{↑↑} = R^{↑} and ^{↓} is monotonic, R^{↓} ⊑ R, R^{↓↓} = R^{↓}.

5. R = R^{↑} ⟺ R^{↓} = R.

6. ⊥ ⊥ _{AB}^{↑} = ⊥ ⊥_{AB} and ⊤ ⊤ _{AB}^{↓} = ⊤ ⊤_{AB}.

7. R^{⌣}^{↑} = R^{↑}^{⌣} and R^{⌣}^{↓} = R^{↓}^{⌣}.

8. (R; S^{↑})^{↑} = R^{↑}; S^{↑} and (R^{↑}; S)^{↑} = R^{↑}; S^{↑}.

9. For all nonzero ideal relations J^{↑} = ⊤ ⊤_{AB} holds.

10. (α\R^{↑})^{↓} = R^{↑} for all ⊥ ⊥_{AA} ≠ α ∈ Sc_{G}(A).

11. R = ⨆_{{α:A [figure] A \atop α scalar}}α; (α\R)^{↓},

12. R^{↑} = ⨆_{{α≠ ⊥ ⊥_{AA} \atop α scalar}} (α\R)^{↓}.

The relation (α\R)^{↓} is called the α-cut of R. For L-fuzzy relation it is characterized by the following lemma. 4.5. Lemma. For an L-fuzzy relation R : A [figure] B and a scalar α on A we have

(α\R)^{↓}(x, y) ⟺ R(x, y) ⊒ α.

Proof. Define a crisp relation Q : A [figure] B by

Q(x′, y′) := \{ \begin{matrix}1 & iff x′ = x and y′ = y \\ 0 & otherwise. \end{matrix}

Then we conclude

(α\R)^{↓}(x, y) ⟺ Q ⊑ (α\R)^{↓} by definition of Q
⟺ Q ⊑ α\R  since Q is crisp
⟺ α; Q ⊑ R
⟺ α ⊑ R(x, y),

where the last equivalence follows from (α; Q)(x, y) = α and (α; Q)(x′, y′) = 0 if x′ ≠ x or y′ ≠ y.

The last lemma shows that Lemma 4.4 (11) is an abstract version of the so-called α-cut Theorem of fuzzy theory.

In [13] it was shown that the sets Sc_{G}(A) and Sc_{G}(B) of scalars on A resp. on B are isomorphic via the mapping α ↦ ⊤ ⊤_{BA}; α; ⊤ ⊤_{AB} ⊓ 𝕀_{B}. Therefore, we identify those sets, and properties like Lemma 3.5 (2) become α; Q = Q; α. We call the set of scalars the underlying lattice of G and denote it by Sc[G].

Any relation on an object A with ⊤ ⊤_{AA} = 𝕀_{A} is a scalar. Therefore, such an A may be seen as the object of the underlying lattice. We call a Goguen category G trivial iff ⊤ ⊤_{AA} = 𝕀_{A} holds for all object A and non trivial otherwise.

4.6. Lemma. Let α be a scalar and Q : A [figure] B. Then we have (α\Q)^{↓}^{⌣} = (α\Q^{⌣})^{↓}.

Proof. The computation

X ⊑ (α\Q)^{↓}^{⌣} ⟺ X^{⌣} ⊑ (α\Q)^{↓}
⟺ α; X^{⌣}^{↑} ⊑ Q
⟺ α; X^{↑}^{⌣} ⊑ Q Lemma 4.4 (7)
⟺ (X^{↑}; α)^{⌣} ⊑ Q α partial identity
⟺ X^{↑}; α ⊑ Q^{⌣}
⟺ α; X^{↑} ⊑ Q^{⌣} Lemma 3.5 (2)
⟺ X ⊑ (α\Q^{⌣})^{↓}

shows the assertion.

Furthermore, in [13] it was shown that G^{↑} is a subcategory of G and together with the operations of G a simple Dedekind category, i.e., the collection of crisp relations is closed under all operations and we have

R ≠ ⊥ ⊥_{AB} ⟹ ⊤ ⊤_{CA}; R; ⊤ ⊤_{BD} = ⊤ ⊤_{CD}

for all crisp relations R. Since ⊥ ⊥_{AA} ≠ ⊤ ⊤_{AA} and hence 𝕀_{A} ≠ ⊥ ⊥_{AA} this implies that G is uniform, i.e., ⊤ ⊤_{AB}; ⊤ ⊤_{BC} = ⊤ ⊤_{AC}.

4.7. Lemma. Let Q, R : A [figure] B be crisp relations and α, β ∈ Sc[G]. Then we have

α; Q ⊑ β; R ⟺ α = ⊥ ⊥_{AA} or Q = ⊥ ⊥_{AB} or (α ⊑ β and Q ⊑ R).

Proof. The implication ⇐ is trivial. Suppose α; Q ⊑ β; R, α ≠ ⊥ ⊥_{AA} and Q ≠ ⊥ ⊥_{AB}. Then we have

α = α; ⊤ ⊤_{AA} ⊓ 𝕀_{A}  ϕ is an isomorphism
= α; ⊤ ⊤_{AA}; Q; ⊤ ⊤_{BA} ⊓ 𝕀_{A} Q ≠ ⊥ ⊥_{AB} and crisp
= ⊤ ⊤_{AA}; α; Q; ⊤ ⊤_{BA} ⊓ 𝕀_{A} α scalar
⊑ ⊤ ⊤_{AA}; β; R; ⊤ ⊤_{BA} ⊓ 𝕀_{A}
= β; ⊤ ⊤_{AA}; R; ⊤ ⊤_{BA} ⊓ 𝕀_{A} β scalar
⊑ β; ⊤ ⊤_{AA} ⊓ 𝕀_{A}
= β  ϕ is an isomorphism.

Furthermore, we get Q = α^{↑}; Q^{↑} = (α; Q)^{↑} ⊑ (β; R)^{↑} ⊑ R^{↑} = R since Q and R are crisp and α ≠ ⊥ ⊥_{AA} implies α^{↑} = 𝕀_{A}.

From the last lemma we may easily deduce the value of an α-cut of a scalar and an ideal element.

4.8. Lemma. Let α, β ∈ Sc[G]. Then we have

(α\β)^{↓} = \{ \begin{matrix}⊤ ⊤_{AA} & iff & α = ⊥ ⊥_{AA} \\ 𝕀_{A} & iff & ⊥ ⊥_{AA} ≠ α ⊑ β \\ ⊥ ⊥_{AA} & otherwise \end{matrix} (α\(β; ⊤ ⊤_{AB}))^{↓} = \{ \begin{matrix}⊤ ⊤_{AB} & iff & α ⊑ β \\ ⊥ ⊥_{AB} & otherwise \end{matrix}

Proof. Using Lemma 4.7 we conclude

X ⊑ (α\β)^{↓} ⟺ α; X^{↑} ⊑ β
⟺ X = ⊥ ⊥_{AA} or α = ⊥ ⊥_{AA} or (α ⊑ β and X ⊑ 𝕀_{A})
and Y ⊑ (α\(β; ⊤ ⊤_{AB}))^{↓} ⟺ α; Y^{↑} ⊑ β; ⊤ ⊤_{AB}
⟺ Y = ⊥ ⊥_{AB} or (α ⊑ β and X ⊑ ⊤ ⊤_{AB})

which implies the assertion.

Last, but not least, we prove a technical lemma which later will be used several times.

4.9. Lemma. Let f : Sc[G] [figure] G[A, B] be an antitone mapping such that f(α) is crisp for all α. Then we have

1. ⨆_{α∈Sc[G]} α; f(α) = ⨆_{α∈Sc[G]} α; τ(f)(α),

2. (β\( ⨆_{α∈Sc[G]} α; f(α)))^{↓} = τ(f)(β) for all scalars β.

Proof. 1. The inclusion ⊑ is trivial since τ is a closure. The other direction follows from β; τ(f)(β) ⊑ ⨆_{α∈Sc[G]} α; f(α) for all β. This property is shown by fixpoint induction.

Therefore, we define a predicate by

𝔓(g) : ⟺ β; g(β) ⊑ ⨆_{α∈Sc[G]} α; f(α) for all scalars β.

This predicate is admissible since 𝔓(g_{i}) for all i ∈ I implies

⨆_{i∈I}(β; g_{i}(β)) ⊑ ⨆_{α∈Sc[G]} α; f(α) ⟺ β; ⨆_{i∈I} g_{i}(β) ⊑ ⨆_{α∈Sc[G]} α; f(α)
⟺ β; (⨆_{i∈I} g_{i})(β) ⊑ ⨆_{α∈Sc[G]} α; f(α)

and hence 𝔓(⨆_{i∈I} g_{i}).

The basis step is trivial since 𝔓(f) is valid. Now, suppose 𝔓(g) which is equivalent to g(β) ⊑ β\( ⨆_{α∈Sc[G]} α; f(α)). Then we conclude

β; φ(g)(β) = β; ( ⨆ ; ⨆ M=β _{γ∈M} g(γ))
= ⨆ ; ⨆ M=β β;_{γ∈M} g(γ)
⊑ ⨆ ; ⨆ M=β β;_{γ∈M}(γ\( ⨆_{α∈Sc[G]} α; f(α))) induction hypothesis
= ⨆ ; ⨆ M=β β; (β\( ⨆_{α∈Sc[G]} α; f(α)))  Lemma 3.3 (15) and ⨆ M = β
= β; (β\( ⨆_{α∈Sc[G]} α; f(α)))
⊑ ⨆_{α∈Sc[G]} α; f(α)

and hence 𝔓(φ(g)). The principle of fixpoint induction gives us 𝔓(τ(f)).

2. By 1. we have ⨆_{α∈Sc[G]} α; f(α) = ⨆_{α∈Sc[G]} α; τ(f)(α). Using the strong version of Axiom 5

of a Goguen category we get the assertion.

5. Lattice-Ordered Semigroups

In fuzzy theory t-norms and t-conorms are essential for defining new operations for fuzzy sets or relations. The corresponding notion for L-fuzzy relations is given by complete lattice-ordered semigroups introduced in [5].

5.1. Definition. Let L be a distributive lattice with least element 0 and greatest element 1, ∗ a binary operation on L and e, z ∈ L. Then (L, ∗, e, z) is called a lattice-ordered operator set, abbreviated loos, iff 1. ∗ is monotonic in both arguments,

2. e is a left and right neutral element for ∗, i.e., x ∗ e = e ∗ x = x for all x ∈ L,

3. z is a left and right zero for ∗, i.e., x ∗ z = z ∗ x = z for all x ∈ L.

If ∗ is associative (L, ∗, e, z) is called a lattice-ordered semigroup (losg). Furthermore, if L is a complete Brouwerian lattice and ∗ is continuous (distributes over arbitrary unions), i.e.,

x ∗ ⨆_{i∈I} y_{i} = ⨆_{i∈I}(x ∗ y_{i}) and (⨆_{i∈I} y_{i}) ∗ x = ⨆_{i∈I}(y_{i} ∗ x)

for all nonempty sets I. (L, ∗, e, z) is called a complete lattice-ordered operator set/semigroup (cloos/closg). Finally, the structures defined above are called commutative if ∗ is.

As usual, e and z are unique, i.e., if e′ (z′) is another left and right neutral element (left and right zero) for ∗ then e′ = e (z′ = z).

Notice, that for L = [0, 1], e = 1 and z = 0 we get the usual definition of t-norms and for e = 0 and z = 1 of t-conorms.

(L, ⊓, 1, 0) and (L, ⊔, 0, 1) are commutative losg’s. Furthermore, we may define the following operations

x ⊛ y := \{ \begin{matrix}x & iff & y = 1, \\ y & iff & x = 1, \\ 0 & otherwise. \end{matrix} x ⊞ y := \{ \begin{matrix}x & iff & y = 0, \\ y & iff & x = 0, \\ 1 & otherwise. \end{matrix}

Again, (L, ⊛, 1, 0) and (L, ⊞, 0, 1) are commutative losg’s. 5.2. Lemma. Let (L, ∗, 1, z) be a loos. Then we have the following:

1. z = 0, i.e., x ∗ 0 = 0 ∗ x = 0 for all x ∈ L,

2. x ⊛ y ⊑ x ∗ y ⊑ x ⊓ y for all x, y ∈ L,

3. ∗ = ⊓ iff u ∗ u = u for all u ∈ L.

Proof. 1. x ∗ 0 ⊑ 1 ∗ 0 = 0 and 0 ∗ x ⊑ 0 ∗ 1 = 0 and hence z = 0.

2. The second inclusion follows immediately from x ∗ y ⊑ x ∗ 1 = x and x ∗ y ⊑ 1 ∗ y = y. Suppose x ⊛ y ≠ 0. Then x = 1 or y = 1, and hence x ⊛ y = 1 ⊛ y = y = 1 ∗ y = x ∗ y resp. x ⊛ y = x ⊛ 1 = x = x ∗ 1 = x ∗ y.

3. ⇒ is trivial, and ⇐ follows from 2. and x ⊓ y = (x ⊓ y) ∗ (x ⊓ y) ⊑ x ∗ y. If the identity 1 of (L, ∗, 1, z) in the last lemma is replaced by 0 a dual version may

be proved. 5.3. Lemma. Let (L, ∗, 0, z) be a loos. Then we have the following:

1. z = 1, i.e., x ∗ 1 = 1 ∗ x = 1 for all x ∈ L,

2. x ⊔ y ⊑ x ∗ y ⊑ x ⊞ y for all x, y ∈ L,

3. ∗ = ⊔ iff u ∗ u = u for all u ∈ L.

Proof. Analog to Lemma 5.2.

6. Operations Derived From Lattice Ordered Semigroups

Within applications of fuzzy theory usually union, meet and composition operators derived from t-norms resp. t-conorms, or more general from commutative closg, are used. In this section we want to define such operations in an arbitrary Goguen category and prove their basic properties.

Throughout this section, unless otherwise stated, let G be a Goguen category and ∗ an operation such that (Sc[G], ∗, ϵ, ζ) is a loos. Furthermore, suppose ⊗ is an operation on relations such that

1. ⊗ is defined for all pairs of relations from G[A, A] for all objects A and it value is

within G[B, B] for a suitable B and if Q ⊗ R is defined for Q : A [figure] B and R : C [figure] D then ⊗ is defined for all pairs of relations from G[A, B] and G[C, D],

2. if Q ⊗ R is defined for Q : A  [figure]B and R : C  [figure]D and within G[E, F] then

Q ⊗ ⊥ ⊥_{CD} = ⊥ ⊥_{AB} ⊗ R = ⊥ ⊥_{EF},

3. if ⊤ ⊤_{AB} ⊗ ⊤ ⊤_{CD} is defined and within G[E, F] then ⊤ ⊤_{AB} ⊗ ⊤ ⊤_{CD} = ⊤ ⊤_{EF},

4. ⊗ distributes over arbitrary unions in both arguments, i.e., for all Q, Q_{i}, R, R_{i} with i ∈ I we have

Q ⊗ (⨆_{i∈I} R_{i}) = ⨆_{i∈I}(Q ⊗ R_{i}) and (⨆_{i∈I} Q_{i}) ⊗ R = ⨆_{i∈I}(Q_{i} ⊗ R)

whenever the application of ⊗ is defined,

5. for all α, β ∈ Sc[G] and relations Q : A  [figure]B, R : C  [figure]D such that Q ⊗ R is

defined and within G[E, F] we have

(α_{E} ⊓ β_{E}); (Q ⊗ R) = (α_{A}; Q) ⊗ (β_{C}; R),

6. ⊗ is closed on G^{↑}, i.e., for all crisp relations Q, R such that Q ⊗ R is defined Q ⊗ R is crisp.

Notice that ⊓ and ; satisfy the properties above. 1,2 and 4 follow immediately from the definition of a Dedekind category. For meet property 3 is trivial and for composition it follows from the fact that 𝕀 is crisp and that the crisp relations constitute a simple Dedekind category. Property 6 is true since the crisp relations are closed under all relational operations. Finally, property 5 is shown as follows.

(α ⊓ β); (Q ⊓ R) = (α ⊓ β); ⊤ ⊤_{AB} ⊓ Q ⊓ R  Lemma 3.5 (1)
= α; ⊤ ⊤_{AB} ⊓ β; ⊤ ⊤_{AB} ⊓ Q ⊓ R Lemma 3.5 (3)
= α; Q ⊓ β; R  Lemma 3.5 (1),
(α ⊓ β); Q; R = α; β; Q; R  α, β partial identities
= α; Q; β; R  Lemma 3.5 (2)

Now, we may define ∗ based operations as follows.

6.1. Definition. Let Q, R be relations such that Q ⊗ R is defined. Then we define

Q ⊗_{∗} R := ⨆_{α,β∈Sc[G]}(α ∗ β); ((α\Q)^{↓} ⊗ (β\R)^{↓}).

First of all, we want give an alternative definition of Q ⊗_{∗} R which corresponds to its α-cut representation.

6.2. Lemma. Let Q, R be relations such that Q ⊗ R is defined. Then we have

Q ⊗_{∗} R = ⨆_{α∈Sc[G]} α; ( ⨆_{{β,γ∈Sc[G] \atop β∗γ⊒α}}((β\Q)^{↓} ⊗ (γ\R)^{↓})).

Proof. This may be obtained from

Q ⊗_{∗} R = ⨆_{α,β∈Sc[G]}(α ∗ β); ((α\Q)^{↓} ⊗ (β\R)^{↓})
= ⨆_{α∈Sc[G]} α; ( ⨆_{{β,γ∈Sc[G] \atop β∗γ=α}}((β\Q)^{↓} ⊗ (γ\R)^{↓}))

= ⨆_{α∈Sc[G]} α; ( ⨆_{{β,γ∈Sc[G] \atop β∗γ⊒α}}((β\Q)^{↓} ⊗ (γ\R)^{↓})),

where the last equality is shown as follows. The inclusion ⊑ is trivial and ⊒ is implied by α; ((β\Q)^{↓} ⊗ (γ\R)^{↓}) ⊑ (β ∗ γ); ((β\Q)^{↓} ⊗ (γ\R)^{↓}) for β ∗ γ ⊒ α.

The connection between the last lemma and the α-cut representation is given as follows. Define f : Sc[G] [figure] G^{↑}[E, F] by

f(α) := ⨆_{{β,γ∈Sc[G] \atop β∗γ⊒α}}((β\Q)^{↓} ⊗ (γ\R)^{↓}).

From the following computation with α ⊑ α′

f(α′) = ⨆_{{β,γ∈Sc[G] \atop β∗γ⊒α′}}((β\Q)^{↓} ⊗ (γ\R)^{↓}) definition f
⊑ ⨆_{{β,γ∈Sc[G] \atop β∗γ⊒α}}((β\Q)^{↓} ⊗ (γ\R)^{↓}) α ⊑ α′ ⊑ β ∗ γ
= f(α)  definition f

we conclude that f is antitonic. By Lemma 4.9 (2) and the last lemma Q ⊗_{∗} R = ⨆_{α∈Sc[G]}(α_{E}; τ(f)(α)) follows.

Second, we want to show that the definition above corresponds to the componentwise definition in the case of L-fuzzy relations. Notice, that ;_{∗} and the composition defined in [1] coincide.

6.3. Theorem. Let Q, R be L-fuzzy relations between the sets A and B, and let S be a L-fuzzy relation between B and C. Then we have

1. (Q ⊓_{∗} R)(x, y) = Q(x, y) ∗ R(x, y),

2. (Q;_{∗} S)(x, z) = ⨆_{y∈B} Q(x, y) ∗ S(y, z).

Proof. 1. By the definitions of α-cuts and meet we conclude

((α\Q)^{↓} ⊓ (β\R)^{↓})(x, y) ⟺ (α\Q)^{↓}(x, y) and (β\R)^{↓}(x, y)
⟺ Q(x, y) ⊒ α and R(x, y) ⊒ β.

This immediately implies

(Q ⊓_{∗} R)(x, y) = ⨆_{α,β∈Sc[G]}((α ∗ β); ((α\Q)^{↓} ⊓ (β\R)^{↓}))(x, y)
= ⨆_{{α,β∈Sc[G] \atop ((α\Q)↓⊓(β\R)↓)(x,y)}} α ∗ β

= ⨆_{{α,β∈Sc[G] \atop Q(x,y)⊒α and R(x,y)⊒β}} α ∗ β

= Q(x, y) ∗ R(x, y),

where the last equality follows from the monotonicity of ∗.

2. Again, by the definitions of α-cuts and composition we conclude

((α\Q)^{↓}; (β\S)^{↓})(x, z) ⟺ ∃y ∈ B : (α\Q)^{↓}(x, y) and (β\S)^{↓}(y, z)
⟺ ∃y ∈ B : Q(x, y) ⊒ α and S(y, z) ⊒ β.

This implies

(Q;_{∗} S)(x, z) = ⨆_{α,β∈Sc[G]}((α ∗ β); ((α\Q)^{↓}; (β\S)^{↓}))(x, z)
= ⨆_{{α,β∈Sc[G] \atop ((α\Q)↓;(β\S)↓)(x,z)}} α ∗ β

= ⨆_{{α,β∈Sc[G] \atop ∃y∈B: Q(x,y)⊒α and S(y,z)⊒β}} α ∗ β

= ⨆_{y∈B} Q(x, y) ∗ S(y, z),

where the last equality is shown as follows. Suppose Q(x, y) ⊒ α and S(y, z) ⊒ β. Then

we get α ∗ β ⊑ Q(x, y) ∗ S(y, z) ⊑ ⨆_{y∈B} Q(x, y) ∗ S(y, z) and hence

⨆_{{α,β∈Sc[G] \atop ∃y: Q(x,y)⊒α and S(y,z)⊒β}} α ∗ β ⊑ ⨆_{y∈B} Q(x, y) ∗ S(y, z).

On the other hand, for all y ∈ B we have

Q(x, y) ∗ S(y, z) ⊑ ⨆_{{α,β∈Sc[G] \atop ∃y: Q(x,y)⊒α and S(y,z)⊒β}} α ∗ β

since Q(x, y) ⊒ Q(x, y) and S(y, z) ⊒ S(y, z), which implies the assertion.

Notice, that the lemma above is true for arbitrary loos, i.e., whatever ϵ is. Therefore, we may define the following meet and union operations on L-fuzzy relations Q, R : A

[figure] B by

Q ∧_{×} R := Q ⊓_{×} R, Q ∨_{+} R := Q ⊓_{+} R,

for arbitrary (Sc[G], ×, ⊤ ⊤ , ⊥ ⊥) and (Sc[G], +, ⊥ ⊥ , ⊤ ⊤). These definitions correspond to the usual definition of t-norm based meet resp. t-conorm based union of fuzzy relations.

Unfortunately, ⊗_{∗} is not an operation on scalars since

α ⊗_{∗} ⊥ ⊥_{AA} = ⨆_{γ,δ∈Sc[G]}(γ ∗ δ); ((γ\α)^{↓} ⊗ (δ\ ⊥ ⊥_{AA})^{↓}) = (α ∗ ⊥ ⊥_{AA}); (𝕀_{A} ⊗ ⊤ ⊤_{AA}) = α; ⊤ ⊤_{AA}

if ϵ = ⊥ ⊥ and ⊗ is composition. But it is an ideal element such that we may switch to those elements using the isomorphism ϕ. Therefore, we define a new operation for scalars by α ˜⊗_{∗} β := ((α; ⊤ ⊤_{AA}) ⊗_{∗} (β; ⊤ ⊤_{AA})) ⊓ 𝕀_{B}. By Property 1 of ⊗ the operation ˜⊗_{∗} is well-defined.

6.4. Lemma. Let α and β be scalars such that α ⊗ β is defined. Then we have

1. (α; ⊤ ⊤_{AA}) ⊗_{∗} (β; ⊤ ⊤_{AA}) = ⨆_{{γ,δ∈Sc[G] \atop γ⊑α and δ⊑β}}(γ ∗ δ); ⊤ ⊤_{BB},

2. (α; ⊤ ⊤_{AA}) ⊗_{∗} (β; ⊤ ⊤_{AA}) = ((α; ⊤ ⊤_{AA}) ⊗_{∗} (β; ⊤ ⊤_{AA})); ⊤ ⊤_{BB}.

Proof. 1. We immediately conclude

(α; ⊤ ⊤_{AA}) ⊗_{∗} (β; ⊤ ⊤_{AA}) = ⨆_{γ,δ∈Sc[G]}(γ ∗ δ); ((γ\(α; ⊤ ⊤_{AA}))^{↓} ⊗ (δ\(β; ⊤ ⊤_{AA}))^{↓})
= ⨆_{{γ⊑α \atop δ⊑β}}(γ ∗ δ); ⊤ ⊤_{BB} Lemma 4.8 and 2 and 3 of ⊗.

236  MICHAEL WINTER

2. Using 1. the computation

(α; ⊤ ⊤_{AA}) ⊗_{∗} (β; ⊤ ⊤_{AA}) = ⨆_{{γ⊑α \atop δ⊑β}}(γ ∗ δ); ⊤ ⊤_{BB}
= ( ⨆_{{γ⊑α \atop δ⊑β}}(γ ∗ δ); ⊤ ⊤_{BB}); ⊤ ⊤_{BB}
= ((α; ⊤ ⊤_{AA}) ⊗_{∗} (β; ⊤ ⊤_{AA})); ⊤ ⊤_{BB}

shows the assertion.

Using ˜⊗_{∗} we may compare ∗ with corresponding ∗ based operation as follows. 6.5. Lemma. Let α and β be scalars such that α ⊗ β is defined. Then α ˜⊗_{∗} β = α ∗ β. Proof. We immediately conclude

α ˜⊗_{∗} β = ((α; ⊤ ⊤_{AA}) ⊗_{∗} (β; ⊤ ⊤_{AA})) ⊓ 𝕀_{B}
= ( ⨆_{{γ⊑α \atop δ⊑β}}(γ ∗ δ); ⊤ ⊤_{BB}) ⊓ 𝕀_{B}  Lemma 6.4 (1)
= ⨆_{{γ⊑α \atop δ⊑β}}(γ ∗ δ); ⊤ ⊤_{BB} ⊓ 𝕀_{B}
= ⨆_{{γ⊑α \atop δ⊑β}}(γ ∗ δ)  ϕ is an isomorphism
= α ∗ β,

where the last equality follows from the monotonicity of ∗.

By Lemma 5.2 (2) ⊓ is the strongest t-norm like operation. This leads to the following property of the corresponding ∗ based operation. 6.6. Lemma. Let Q and R be relations such that Q ⊗ R is defined. Then we have Q ⊗_{∗} R = Q ⊗ R for all Q and R iff ∗ = ⊓. Proof. The implication ⇐ follows from

Q ⊗_{⊓} R = ⨆_{α,β∈Sc[G]}(α ⊓ β); ((α\Q)^{↓} ⊗ (β\R)^{↓})
= ⨆_{α,β∈Sc[G]}(α; (α\Q)^{↓} ⊗ β; (β\R)^{↓}) Property 5 of ⊗
= ( ⨆_{α∈Sc[G]} α; (α\Q)^{↓}) ⊗ ( ⨆_{β∈Sc[G]} β; (β\R)^{↓}) Property 4 of ⊗
= Q ⊗ R  Lemma 4.4 (11).

The computation

α ∗ β = α ˜⊗_{∗} β  Lemma 6.5
= ((α; ⊤ ⊤_{AA}) ⊗_{∗} (β; ⊤ ⊤_{AA})) ⊓ 𝕀_{B}

DERIVED OPERATIONS IN GOGUEN CATEGORIES  237
= ((α; ⊤ ⊤_{AA}) ⊗ (β; ⊤ ⊤_{AA})) ⊓ 𝕀_{B} assumption
= ((α; ⊤ ⊤_{AA}) ⊗_{⊓} (β; ⊤ ⊤_{AA})) ⊓ 𝕀_{B} as shown above
= α ˜⊗_{⊓} β
= α ⊓ β  Lemma 6.5

proves the other implication.

Since ⊔ is the weakest t-conorm like operation by Lemma 5.3 (2) we get a similar result for ⊗ = ⊓. 6.7. Lemma. let Q, R : A [figure] B be relations. Then we have Q ⊓_{∗} R = Q ⊔ R for all Q and R iff ∗ = ⊔. Proof. The implication ⇐ follows from

Q ⊓_{⊔} R = ⨆_{α,β∈Sc[G]}(α ⊔ β); ((α\Q)^{↓} ⊓ (β\R)^{↓})
= ⨆_{α,β∈Sc[G]}(α; ((α\Q)^{↓} ⊓ (β\R)^{↓}) ⊔ β; ((α\Q)^{↓} ⊓ (β\R)^{↓}))
⊑ ⨆_{α,β∈Sc[G]}(α; (α\Q)^{↓} ⊔ β; (β\R)^{↓})
= ( ⨆_{α∈Sc[G]} α; (α\Q)^{↓}) ⊔ ( ⨆_{β∈Sc[G]} β; (β\R)^{↓})
= Q ⊔ R  Lemma 4.4 (11)
= ( ⨆_{α∈Sc[G]} α; ((α\Q)^{↓} ⊓ ⊤ ⊤_{AB}))  Lemma 4.4 (11)

⊔ ( ⨆_{β∈Sc[G]} β; ( ⊤ ⊤_{AB} ⊓ (β\R)^{↓}))

= ( ⨆_{α∈Sc[G]}(α ⊔ ⊥ ⊥_{AB}); ((α\Q)^{↓} ⊓ ( ⊥ ⊥_{AB}\R)^{↓}))

⊔ ( ⨆_{β∈Sc[G]}( ⊥ ⊥_{AB} ⊔ β); (( ⊥ ⊥_{AB}\Q)^{↓} ⊓ (β\R)^{↓}))

⊑ ⨆_{α,β∈Sc[G]}(α ⊔ β); ((α\Q)^{↓} ⊓ (β\R)^{↓})
= Q ⊓_{⊔} R.

The computation

α ∗ β = α ˜⊓_{∗} β  Lemma 6.5
= ((α; ⊤ ⊤_{AA}) ⊓_{∗} (β; ⊤ ⊤_{AA})) ⊓ 𝕀_{A}
= ((α; ⊤ ⊤_{AA}) ⊔ (β; ⊤ ⊤_{AA})) ⊓ 𝕀_{A}  assumption
= (α; ⊤ ⊤_{AA} ⊓ 𝕀_{A}) ⊔ (β; ⊤ ⊤_{AA} ⊓ 𝕀_{A})
= α ⊔ β  ϕ is an isomorphism

proves the other implication.

238  MICHAEL WINTER

Suppose (L, ∗, 1, 0) is a loos and R is a crisp L-fuzzy relation. Then we have

(Q ⊓_{∗} R)(x, y) = Q(x, y) ∗ R(x, y) = Q(x, y) ⊓ R(x, y) = (Q ⊓ R)(x, y). The next lemma shows that this property is true in general. 6.8. Lemma. Let ϵ = 𝕀. Furthermore, let Q and R be relations such that Q ⊗ R is defined. If Q or R is crisp then we have Q ⊗_{∗} R = Q ⊗ R. Proof. Suppose R is crisp. The computation

Q ⊗_{∗} R = ⨆_{α,β∈Sc[G]}(α ∗ β); ((α\Q)^{↓} ⊗ (β\R)^{↓})
= ⨆_{{α∈Sc[G] \atop β≠ ⊥ ⊥}}(α ∗ β); ((α\Q)^{↓} ⊗ (β\R)^{↓}) Lemma 5.2 (1)
= ⨆_{{α∈Sc[G] \atop β≠ ⊥ ⊥}}(α ∗ β); ((α\Q)^{↓} ⊗ R)  Lemma 4.4 (10)
= ⨆_{α∈Sc[G]}(α ∗ 𝕀); ((α\Q)^{↓} ⊗ R)  ∗ is monotonic
= ⨆_{α∈Sc[G]} α; ((α\Q)^{↓} ⊗ R)  ϵ = 𝕀
= ⨆_{α∈Sc[G]}(α ⊓ 𝕀); ((α\Q)^{↓} ⊗ R)
= ⨆_{α∈Sc[G]}(α; (α\Q)^{↓} ⊗ R)  Property 5 of ⊗
= ( ⨆_{α∈Sc[G]} α; (α\Q)^{↓}) ⊗ R  Property 4 of ⊗
= Q ⊗ R  Lemma 4.4 (11)

shows the assertion. The second assertion is shown analogously.

Lemma 5.2 may be lifted to the ∗ based operation as follows. 6.9. Lemma. Let ϵ = 𝕀. Furthermore, let Q and R be relations such that Q ⊗ R is defined. Then we have the following.

1. Q ⊗_{∗} ⊥ ⊥ = ⊥ ⊥ ⊗_{∗} R = ⊥ ⊥,

2. Q ⊓_{∗} ⊤ ⊤ = Q and ⊤ ⊤ ⊓_{∗} R = R,

3. Q ⊗_{⊛} R ⊑ Q ⊗_{∗} R ⊑ Q ⊗ R. Proof. 1. The assertion follows immediately from

Q ⊗_{∗} ⊥ ⊥ = Q ⊗ ⊥ ⊥ Lemma 6.8
= ⊥ ⊥  Property 2 of ⊗.

The second assertion is shown analogously.

2. Consider the computation

Q ⊓_{∗} ⊤ ⊤ = Q ⊓ ⊤ ⊤ Lemma 6.8

DERIVED OPERATIONS IN GOGUEN CATEGORIES  239
= Q.

The second assertion is shown analogously.

3. follows immediately from Lemma 5.2 and Lemma 6.6.

Replacing 𝕀 by ⊥ ⊥ we may state a kind of a dual version of the last two lemmata. 6.10. Lemma. Let ϵ = ⊥ ⊥. Furthermore, let Q and R be relations such that Q ⊗ R is defined. If Q or R are crisp then we have Q ⊗_{∗} R = (Q ⊗ ⊤ ⊤) ⊔ ( ⊤ ⊤ ⊗ R). Proof. Suppose R is crisp. Consider the computations

⨆_{α∈Sc[G]}(α ∗ ⊥ ⊥); ((α\Q)^{↓} ⊗ ⊤ ⊤) = ⨆_{α∈Sc[G]} α; ((α\Q)^{↓} ⊗ ⊤ ⊤)  Lemma 5.3 (1)
= ⨆_{α∈Sc[G]}(α ⊓ 𝕀); ((α\Q)^{↓} ⊗ ⊤ ⊤)
= ⨆_{α∈Sc[G]}(α; (α\Q)^{↓} ⊗ ⊤ ⊤)  Property 5 of ⊗
= ( ⨆_{α∈Sc[G]} α; (α\Q)^{↓}) ⊗ ⊤ ⊤  Property 4 of ⊗
= Q ⊗ ⊤ ⊤  Lemma 4.4 (11)
⨆_{{α∈Sc[G] \atop β≠ ⊥ ⊥}}(α ∗ β); ((α\Q)^{↓} ⊗ R) = ⨆_{α∈Sc[G]}(α ∗ 𝕀); ((α\Q)^{↓} ⊗ R) ∗ is monotonic
= ⨆_{α∈Sc[G]}((α\Q)^{↓} ⊗ R)  Lemma 5.3 (1)
= ( ⨆_{α∈Sc[G]} (α\Q)^{↓}) ⊗ R  Property 4 of ⊗
= ( ⊥ ⊥ \Q)^{↓} ⊗ R  Lemma 3.3 (13)
= ⊤ ⊤ ⊗ R.

Together this implies using Lemma 4.4 (10)

Q ⊗_{∗} R = ⨆_{α,β∈Sc[G]}(α ∗ β); ((α\Q)^{↓} ⊗ (β\R)^{↓})
= ⨆_{α∈Sc[G]}(α ∗ ⊥ ⊥); ((α\Q)^{↓} ⊗ ( ⊥ ⊥ \R)^{↓}) ⊔ ⨆_{{α∈Sc[G] \atop β≠ ⊥ ⊥}}(α ∗ β); ((α\Q)^{↓} ⊗ (β\R)^{↓})
= ⨆_{α∈Sc[G]}(α ∗ ⊥ ⊥); ((α\Q)^{↓} ⊗ ⊤ ⊤) ⊔ ⨆_{{α∈Sc[G] \atop β≠ ⊥ ⊥}}(α ∗ β); ((α\Q)^{↓} ⊗ R)
= (Q ⊗ ⊤ ⊤) ⊔ ( ⊤ ⊤ ⊗ R).

The second assertion is shown analogously.

The next lemma is again a lifting of a corresponding result (Lemma 5.3) of the last section. 6.11. Lemma. Let ϵ = ⊥ ⊥. Furthermore, let Q and R be relations such that Q ⊗ R is defined. Then we have the following.

240  MICHAEL WINTER

1. If ⊤ ⊤_{AB} ≠ ⊥ ⊥_{AB} and ⊤ ⊤_{CD} ≠ ⊥ ⊥_{CD} then Q ⊗_{∗} ⊤ ⊤_{CD} = ⊤ ⊤_{AB} ⊗_{∗} R = ⊤ ⊤,

2. Q ⊓_{∗} ⊥ ⊥ = Q and ⊥ ⊥ ⊓_{∗} R = R,

3. Q ⊗_{⊔} R ⊑ Q ⊗_{∗} R ⊑ Q ⊗_{⊞} R. Proof. 1. The assertion follows immediately from

Q ⊗_{∗} ⊤ ⊤_{CD} = (Q ⊗ ⊤ ⊤_{CD}) ⊔ ( ⊤ ⊤_{AB} ⊗ ⊤ ⊤_{CD}) Lemma 6.10
= ( ⊤ ⊤_{AB} ⊗ ⊤ ⊤_{CD})  ⊗ monotonic by property 4
= ⊤ ⊤  Property 3 of ⊗.

2. Consider the computation

Q ⊓_{∗} ⊥ ⊥ = (Q ⊓ ⊤ ⊤) ⊔ ( ⊤ ⊤ ⊓ ⊥ ⊥) Lemma 6.10
= Q

The second assertion is shown analogously.

3. follows immediately from Lemma 5.3.

In the rest of this section we want to prove some basic properties of ∗ based operations and the structures induced by them. We start with the following theorem. 6.12. Theorem. Let ⊗ be commutative. Then ⊗_{∗} is commutative iff (Sc[G], ∗, ϵ, ζ) is a commutative loos. Proof. The implication ⇐ follows from

Q⊗_{∗}R = ⨆_{α,β∈Sc[G]}(α∗β); ((α\Q)^{↓}⊗(β\R)^{↓}) = ⨆_{α,β∈Sc[G]}(β ∗α); ((β\R)^{↓}⊗(α\Q)^{↓}) = R⊗_{∗}Q.

The computation

α ∗ β = α ˜⊗_{∗} β  Lemma 6.5
= ((α; ⊤ ⊤_{AA}) ⊗_{∗} (β; ⊤ ⊤_{AA})) ⊓ 𝕀_{B}
= ((β; ⊤ ⊤_{AA}) ⊗_{∗} (α; ⊤ ⊤_{AA})) ⊓ 𝕀_{B}
= β ˜⊗_{∗} α
= β ∗ α  Lemma 6.5

shows the other implication.

Next, we want to focus on associativity. Therefore, we need the following technical lemma. 6.13. Lemma. Let (Sc[G], ∗, ϵ, ζ) be a cloos, g : Sc[G] [figure] G^{↑}[A, B] be antitonic, h : Sc[G]

[figure] G^{↑}[C, D] an antimorphism and ⊗ defined on G[A, B] and G[C, D]. Furthermore, let

f(α) := ⨆_{{β,γ∈Sc[G] \atop β∗γ⊒α}} τ(g)(β) ⊗ h(γ),  f̄(α) := ⨆_{{β,γ∈Sc[G] \atop β∗γ⊒α}} g(β) ⊗ h(γ).

Then we have τ(f) = τ(f̄).

Proof. The inclusion ⊒ is trivial since g ⊑ τ(g) and ⊗, ⊔ and τ are monotonic.

Obviously, f̄ is antitonic and by property 6 of ⊗ a function from Sc[G] to G^{↑}[E, F] for suitable objects E and F. Therefore, we may prove the other inclusion by fixpoint induction. We define a predicate

𝔓(k, l) : ⟺ ∀α ∈ Sc[G] : ⨆_{{β,γ∈Sc[G] \atop β∗γ⊒α}}(k(β) ⊗ h(γ)) ⊑ l(α).

This predicate is admissible since

∀i ∈ I : 𝔓(k_{i}, l_{i}) ⇔ ∀i ∈ I, α ∈ Sc[G] : ⨆_{β∗γ⊒α}(k_{i}(β) ⊗ h(γ)) ⊑ l_{i}(α)
⇒ ∀α ∈ Sc[G] : ⨆_{i∈I} ⨆_{β∗γ⊒α}(k_{i}(β) ⊗ h(γ)) ⊑ ⨆_{i∈I} l_{i}(α)
⇔ ∀α ∈ Sc[G] : ⨆_{β∗γ⊒α} ⨆_{i∈I}(k_{i}(β) ⊗ h(γ)) ⊑ (⨆_{i∈I} l_{i})(α)
⇔ ∀α ∈ Sc[G] : ⨆_{β∗γ⊒α}((⨆_{i∈I} k_{i}(β)) ⊗ h(γ)) ⊑ (⨆_{i∈I} l_{i})(α)
⇔ ∀α ∈ Sc[G] : ⨆_{β∗γ⊒α}((⨆_{i∈I} k_{i})(β) ⊗ h(γ)) ⊑ (⨆_{i∈I} l_{i})(α)
⇔ 𝔓(⨆_{i∈I} k_{i}, ⨆_{i∈I} l_{i}).

The basis step 𝔓(g, f̄) is trivial. First, we want to show the following property

(∗) ⨆_{β∗γ⊒α} ⨆ ; ⨆ M=β _{δ∈M}(k(δ) ⊗ h(γ)) ⊑ ⨆ ; ⨆ N⊒α_{ζ∈N} ⨆_{μ∗γ⊒ζ}(k(μ) ⊗ h(γ)).

Suppose β ∗ γ ⊒ α and ⨆ M = β. If M = ∅ the left side of (∗) equals ⊥ ⊥ and the inclusion is trivial. Therefore, let M ≠ ∅. Then we define N := {δ ∗ γ | δ ∈ M} and conclude

⨆ N = ⨆_{δ∈M}(δ ∗ γ)
= (⨆ M) ∗ γ) ∗ is continuous and M ≠ ∅
= β ∗ γ
⊒ α.

Furthermore, we have k(δ) ⊗ h(γ) ⊑ ⨆_{μ∗γ⊒δ∗γ}(k(μ) ⊗ h(γ)) since δ ∗ γ ⊒ δ ∗ γ. This implies

δ∈M(k(δ) ⊗ h(γ)) ⊑ _{ζ∈N} ⨆_{μ∗γ⊒δ∗γ}(k(μ) ⊗ h(γ)) and hence (∗). Now, suppose 𝔓(k, l). Then

we conclude for α ∈ Sc[G]

⨆_{β∗γ⊒α}(φ(k)(β) ⊗ h(γ)) = ⨆_{β∗γ⊒α}(( ⨆ ; ⨆ M=β _{δ∈M} k(δ)) ⊗ h(γ))
= ⨆_{β∗γ⊒α} ⨆ ; ⨆ M=β((_{δ∈M} k(δ)) ⊗ h(γ)) Property 4 of ⊗
⊑ ⨆_{β∗γ⊒α} ⨆ ; ⨆ M=β _{δ∈M}(k(δ) ⊗ h(γ)) ⊗ monotonic

⊑ ⨆ ; ⨆ N⊒α_{ζ∈N} ⨆_{μ∗γ⊒ζ}(k(μ) ⊗ h(γ)) by (∗)
⊑ ⨆ ; ⨆ N⊒α_{ζ∈N} l(ζ)  induction hypothesis
= φ(l)(α)  Lemma 2.2

and hence 𝔓(φ(k), φ(l)). The principle of fixpoint induction gives us f ⊑ τ(f̄) which implies τ(f) ⊑ τ^{2}(f̄) = τ(f̄).

Notice, that a version of the last lemma, where h(γ) and g(β) resp. τ(g)(β) are exchanged, may also be proved.

6.14. Lemma. Let (Sc[G], ∗_{1}, ϵ_{1}) and (Sc[G], ∗_{2}, ϵ_{2}) be cloos’s. Then we have

1. (Q ⊗_{∗_{1}} R) ⊗_{∗_{2}} S = ⨆_{α,β,γ∈Sc[G]}((α ∗_{1} β) ∗_{2} γ); (((α\Q)^{↓} ⊗ (β\R)^{↓}) ⊗ (γ\S)^{↓}),

2. Q ⊗_{∗_{1}} (R ⊗_{∗_{2}} S) = ⨆_{α,β,γ∈Sc[G]}(α ∗_{1} (β ∗_{2} γ)); ((α\Q)^{↓} ⊗ ((β\R)^{↓} ⊗ (γ\S)^{↓})).

Proof. 1. Define the following functions

\begin{aligned}g(α) & := & ⨆_{{β,γ∈Sc[G] \atop β∗_{1}γ⊒α}}((β\Q)^{↓} ⊗ (γ\R)^{↓}), & h(α) & := & (α\S)^{↓}, \\ f(α) & := & ⨆_{{β,γ∈Sc[G] \atop β∗_{2}γ⊒α}}((β\(Q ⊗_{∗_{1}} R))^{↓} ⊗ h(γ)), & f̄(α) & := & ⨆_{{β,γ∈Sc[G] \atop β∗_{2}γ⊒α}}(g(β) ⊗ h(γ)). \end{aligned}

f, f̄ and g are antitonic and by property 6 of ⊗ functions from Sc[G] to crisp relations. Furthermore, h is an antimorphism, and we have

f(α) = ⨆_{β∗_{2}γ⊒α}((β\(Q ⊗_{∗_{1}} R))^{↓} ⊗ h(γ))
= ⨆_{β∗_{2}γ⊒α}((β\( ⨆_{δ∈Sc[G]} δ; g(δ)))^{↓} ⊗ h(γ))  Lemma 6.2
= ⨆_{β∗_{2}γ⊒α}((β\( ⨆_{δ∈Sc[G]} δ; τ(g)(δ)))^{↓} ⊗ h(γ))  Lemma 4.9 (1)
= ⨆_{β∗_{2}γ⊒α}(τ(g)(β) ⊗ h(γ)).  Lemma 4.9 (2),
f̄(α) = ⨆_{β∗_{2}γ⊒α}(g(β) ⊗ h(γ))
= ⨆_{β∗_{2}γ⊒α}(( ⨆_{μ∗_{1}ν⊒β}((μ\Q)^{↓} ⊗ (ν\R)^{↓})) ⊗ h(γ))
= ⨆_{β∗_{2}γ⊒α} ⨆_{μ∗_{1}ν⊒β}(((μ\Q)^{↓} ⊗ (ν\R)^{↓}) ⊗ h(γ)) Property 4 of ⊗
= ⨆_{β∗_{2}γ⊒α} ⨆_{μ∗_{1}ν⊒β}(((μ\Q)^{↓} ⊗ (ν\R)^{↓}) ⊗ (γ\S)^{↓})
= ⨆_{(μ∗_{1}ν)∗_{2}γ⊒α}(((μ\Q)^{↓} ⊗ (ν\R)^{↓}) ⊗ (γ\S)^{↓}),

⨆_{α∈Sc[G]} α; f̄(α) = ⨆_{α∈Sc[G]} α; ( ⨆_{(μ∗_{1}ν)∗_{2}γ⊒α}(((μ\Q)^{↓} ⊗ (ν\R)^{↓}) ⊗ (γ\S)^{↓}))
= ⨆_{α,β,γ∈Sc[G]}((α ∗_{1} β) ∗_{2} γ); (((α\Q)^{↓} ⊗ (β\R)^{↓}) ⊗ (γ\S)^{↓}),

where the last equality follows analogously to the corresponding equality in the proof of Lemma 6.2. This implies

(Q ⊗_{∗_{1}} R) ⊗_{∗_{2}} S = ⨆_{α∈Sc[G]} α; f(α)  Lemma 6.2
= ⨆_{α∈Sc[G]} α; τ(f)(α) Lemma 4.9 (1)
= ⨆_{α∈Sc[G]} α; τ(f̄)(α) Lemma 6.13 and the computation above
= ⨆_{α∈Sc[G]} α; f̄(α)  Lemma 4.9 (1),

such that the assertion follows from the computation above.

2. is shown analogously.

Now, we are ready to state our theorem concerning associativity of ⊗_{∗}.

6.15. Theorem. Let ⊗ be associative and (Sc[G], ∗, ϵ, ζ) complete. Then ⊗_{∗} is associative iff (Sc[G], ∗, ϵ, ζ) is a losg.

Proof. The implication ⇐ follows immediately from Lemma 6.14. Suppose ⊗_{∗} is associative. Then for all α, β, γ ∈ Sc[G] we conclude

(α ∗ β) ∗ γ

= (α ˜⊗_{∗}β) ˜⊗_{∗}γ  Lemma 6.5
= (((((α; ⊤ ⊤_{AA}) ⊗_{∗} (β; ⊤ ⊤_{AA})) ⊓ 𝕀_{A}); ⊤ ⊤_{AA}) ⊗_{∗} (γ; ⊤ ⊤_{AA})) ⊓ 𝕀_{A}
= ((((α ⊗_{∗} β); ⊤ ⊤_{AA} ⊓ 𝕀_{A}); ⊤ ⊤_{AA}) ⊗_{∗} (γ; ⊤ ⊤_{AA})) ⊓ 𝕀_{A}  Lemma 6.4
= (((α ⊗_{∗} β); ⊤ ⊤_{AA}) ⊗_{∗} (γ; ⊤ ⊤_{AA})) ⊓ 𝕀_{A}  ϕ isomorphism
= (((α; ⊤ ⊤_{AA}) ⊗_{∗} (β; ⊤ ⊤_{AA})) ⊗_{∗} (γ; ⊤ ⊤_{AA})) ⊓ 𝕀_{A}  Lemma 6.4

and analogously α ∗ (β ∗ γ) = ((α; ⊤ ⊤_{AA}) ⊗_{∗} ((β; ⊤ ⊤_{AA}) ⊗_{∗} (γ; ⊤ ⊤_{AA}))) ⊓ 𝕀_{A}. The assertion follows immediately.

If ⊗ =; one may ask about a categorical structure induced by ;_{∗}. The answer is given in the next theorem.

6.16. Theorem. Let (Sc[G], ∗, ϵ, ζ) be complete and G non trivial. Then G together with composition ;_{∗} and identity morphisms ϵ is a category iff (Sc[G], ∗, ϵ, ζ) is a losg with ζ = ⊥ ⊥.

Proof. First of all, we have

Q;_{∗} ϵ = ⨆_{α,β∈Sc[G]}(α ∗ β); (α\Q)^{↓}; (β\ϵ)^{↓}

= ⨆_{{α,β∈Sc[G] \atop β≠ ⊥ ⊥}}(α ∗ β); (α\Q)^{↓}; (β\ϵ)^{↓} ⊔ ⨆_{α∈Sc[G]}(α ∗ ⊥ ⊥); (α\Q)^{↓}; ⊤ ⊤_{BB}
= ⨆_{{α,β∈Sc[G] \atop ⊥ ⊥ ≠β⊑ϵ}}(α ∗ β); (α\Q)^{↓} ⊔ ( ⨆_{α∈Sc[G]}(α ∗ ⊥ ⊥); (α\Q)^{↓}); ⊤ ⊤_{BB}  Lemma 4.8
= ⨆_{α∈Sc[G]}(α ∗ ϵ); (α\Q)^{↓} ⊔ ( ⨆_{α∈Sc[G]}(α ∗ ⊥ ⊥); (α\Q)^{↓}); ⊤ ⊤_{BB}  ∗ monotonic
= ⨆_{α∈Sc[G]} α; (α\Q)^{↓} ⊔ ( ⨆_{α∈Sc[G]}(α ∗ ⊥ ⊥); (α\Q)^{↓}); ⊤ ⊤_{BB}
= Q ⊔ ( ⨆_{α∈Sc[G]}(α ∗ ⊥ ⊥); (α\Q)^{↓}); ⊤ ⊤_{BB}.  Lemma 4.4

and ϵ;_{∗} Q = Q ⊔ ⊤ ⊤_{AA}; ( ⨆_{α∈Sc[G]}( ⊥ ⊥ ∗ α); (α\Q)^{↓}) analogously. For ⇐ it is sufficient to show

that ϵ;_{∗} Q = Q;_{∗} ϵ = Q for ζ = ⊥ ⊥ and all Q. Using the computation above, this follows from

Q;_{∗} ϵ = Q ⊔ ( ⨆_{α∈Sc[G]}(α ∗ ⊥ ⊥); (α\Q)^{↓}); ⊤ ⊤_{BB} = Q.

ϵ;_{∗} Q = Q is shown analogously.

Now, suppose ϵ is the identity and A is an object such that ⊤ ⊤_{AA} ≠ 𝕀_{A}. Then we have

γ = γ;_{∗} ϵ
= γ ⊔ ( ⨆_{α∈Sc[G]}(α ∗ ⊥ ⊥); (α\γ)^{↓}); ⊤ ⊤_{AA} computation above
= γ ⊔ ( ⨆_{α⊑γ}(α ∗ ⊥ ⊥)); ⊤ ⊤_{AA}  Lemma 4.8 and 3.3 (2)
= γ ⊔ (γ ∗ ⊥ ⊥); ⊤ ⊤_{AA}  ∗ monotonic

which is equivalent to (γ ∗ ⊥ ⊥); ⊤ ⊤_{AA} ⊑ γ. From Lemma 4.8 we conclude γ ∗ ⊥ ⊥ = ⊥ ⊥ since ⊤ ⊤_{AA} ≠ ⊥ ⊥_{AA} and ⊤ ⊤_{AA} ⋢ 𝕀_{A}. ⊥ ⊥ ∗ γ = ⊥ ⊥ is shown analogously such that ζ = ⊥ ⊥ follows.

Since converse is a well-behaved operation we get the following theorem.

6.17. Theorem. Let (Sc[G], ∗, ϵ, ζ) be a closg. Then we have (Q;_{∗} R)^{⌣} = R^{⌣};_{∗} Q^{⌣} for

all Q : A  [figure] B and R : B  [figure] C.

Proof. The computation

(Q;_{∗} R)^{⌣} = ( ⨆_{α,β∈Sc[G]}(α ∗ β); (α\Q)^{↓}; (β\R)^{↓})^{⌣}
= ⨆_{α,β∈Sc[G]} (β\R)^{↓}^{⌣}; (α\Q)^{↓}^{⌣}; (α ∗ β)^{⌣}
= ⨆_{α,β∈Sc[G]} (β\R)^{↓}^{⌣}; (α\Q)^{↓}^{⌣}; (α ∗ β) (α ∗ β) partial identity
= ⨆_{α,β∈Sc[G]}(α ∗ β); (β\R)^{↓}^{⌣}; (α\Q)^{↓}^{⌣} Lemma 3.5 (2)

DERIVED OPERATIONS IN GOGUEN CATEGORIES  245
= ⨆_{α,β∈Sc[G]}(α ∗ β); (β\R^{⌣})^{↓}; (α\Q^{⌣})^{↓} Lemma 4.6
= R^{⌣};_{∗} Q^{⌣}

shows the assertion.

Last but not least, we will focus on continuity of ⊗_{∗}. 6.18. Theorem. Let (Sc[G], ∗, ϵ, ζ) be a cloos. Then we have

(⨆_{i∈I} Q_{i}) ⊗_{∗} R = ⨆_{i∈I}(Q_{i} ⊗_{∗} R) and Q ⊗_{∗} (⨆_{i∈I} R_{i}) = ⨆_{i∈I}(Q ⊗_{∗} R_{i})

for all Q, Q_{i}, R, R_{i} with i ∈ I whenever the application of ⊗_{∗} is defined. Proof. Define g(α) := ⨆_{i∈I} (α\Q_{i})^{↓}. Then g is antitonic and a function from Sc[G] to G^{↑}[A, B]. Furthermore, we have

⨆_{i∈I} Q_{i} = ⨆_{i∈I} ⨆_{α∈Sc[G]} α; (α\Q_{i})^{↓} Lemma 4.4 (11)
= ⨆_{α∈Sc[G]} α; (⨆_{i∈I} (α\Q_{i})^{↓})
= ⨆_{α∈Sc[G]} α; g(α)
= ⨆_{α∈Sc[G]} α; τ(g)(α)  Lemma 4.9 (1)

and hence (β\(⨆_{i∈I} Q_{i}))^{↓} = τ(g)(β) by Lemma 4.9 (2). Furthermore, let

f(α) := ⨆_{β∗γ⊒α} τ(g)(β) ⊗ (γ\R)^{↓} and f̄(α) := ⨆_{β∗γ⊒α} g(β) ⊗ (γ\R)^{↓}.

Then we conclude

(⨆_{i∈I} Q_{i}) ⊗_{∗} R = ⨆_{α∈Sc[G]} α; ( ⨆_{β∗γ⊒α} (β\(⨆_{i∈I} Q_{i}))^{↓} ⊗ (γ\R)^{↓}) Lemma 6.2
= ⨆_{α∈Sc[G]} α; ( ⨆_{β∗γ⊒α} τ(g)(β) ⊗ (γ\R)^{↓})  computation above
= ⨆_{α∈Sc[G]} α; f(α)
= ⨆_{α∈Sc[G]} α; τ(f)(α)  Lemma 4.9 (1)
= ⨆_{α∈Sc[G]} α; τ(f̄)(α)  Lemma 6.13
= ⨆_{α∈Sc[G]} α; f̄(α)  Lemma 4.9 (1)
= ⨆_{α∈Sc[G]} α; ( ⨆_{β∗γ⊒α} g(β) ⊗ (γ\R)^{↓})

= ⨆_{α∈Sc[G]} α; ( ⨆_{β∗γ⊒α}(⨆_{i∈I} (β\Q_{i})^{↓}) ⊗ (γ\R)^{↓})
= ⨆_{α∈Sc[G]} α; ( ⨆_{β∗γ⊒α} ⨆_{i∈I}((β\Q_{i})^{↓} ⊗ (γ\R)^{↓})) Property 4 of ⊗
= ⨆_{i∈I} ⨆_{α∈Sc[G]} α; ( ⨆_{β∗γ⊒α} (β\Q_{i})^{↓} ⊗ (γ\R)^{↓})
= ⨆_{i∈I}(Q_{i} ⊗_{∗} R)  Lemma 6.2

The second equality is shown analogously.

As usual, for a continuous binary operation a residuated operation may be defined.

6.19. Theorem. Let (Sc[G], ∗, ϵ, ζ) be a cloos. Then there are operations ⊲_{∗} and ⊳_{∗} such that

\begin{aligned}& Q ⊗_{∗} X ⊑ R ⟺ & X ⊑ Q ⊲_{∗} R \\ and & Y ⊗_{∗} S ⊑ R ⟺ & Y ⊑ R ⊳_{∗} S, \end{aligned}

whenever the application of ⊗_{∗} is defined.

Proof. Define Q ⊲_{∗} R := ⨆{X | Q ⊗_{∗} X ⊑ R}. Then we have

Q ⊗_{∗} (Q ⊲_{∗} R) = Q ⊗_{∗} (⨆{X | Q ⊗_{∗} X ⊑ R})
= ⨆_{Q⊗_{∗}X⊑R}(Q ⊗_{∗} X)  Theorem 6.18
⊑ R

and hence the first equivalence. The second operation is defined by R ⊳_{∗} S := ⨆{Y | S ⊗_{∗} Y ⊑ R}. Its required property is shown analogously.

The last theorem shows that an inclusion Q;_{∗} X ⊑ R has a greatest solution in X, namely Q ⊲_{∗} R. Furthermore, the equation Q;_{∗} X = R has a solution (X = Q ⊲_{∗} R) iff Q;_{∗} (Q ⊲_{∗} R) = R.

7. Conclusion

We have shown that operations derived from lattice-ordered semigroups may be defined in an arbitrary Goguen category, i.e., without using the coefficients from L of concrete Lfuzzy relations. This shows again that Goguen categories constitute a convenient algebraic theory for this kind of mathematical objects.

Using the new operations it is possible to interpret several applications of fuzzy/Lfuzzy relations within Goguen categories. For example, we may express the behavior of a fuzzy controller by an operation within a suitable Goguen category. Consequently, we are able to proof a lot of properties about it by reasoning in the abstract theory of Goguen categories. This theory is based on Dedekind categories, which are well-known, basically equational and element-free. Therefore, we get a nice algebraic theory to reason about L-fuzzy controllers. Furthermore, it seems to be advantageous not to involve special properties of the underlying lattice L and of the operations defined on it as far as possible.

Goguen categories and their applications are part of further investigations.

DERIVED OPERATIONS IN GOGUEN CATEGORIES  247

References

[1] Barr M.: Fuzzy models of linear logic. Mathematical Structures in Computer Science, 6 (3) (1996), 301-312

[2] Birkhoff G.: Lattice Theory. American Mathematical Society Colloquium Publications Vol. XXV, 3rd edition (1940).

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

[4] Freyd P., Scedrov A.: Categories, Allegories. North-Holland (1990).

[5] Goguen J.A.: L-fuzzy sets. J. Math. Anal. Appl. 18 (1967), 145-157.

[6] Jónsson B., Tarski A.: Boolean algebras with operators, I, II, Amer. J. Math. 73 (1951) 891-939, 74 (1952) 127-162

[7] Kawahara, Y., Furusawa H.: Crispness and Representation Theorems in Dedekind Categories. DOI-TR 143, Kyushu University (1997).

[8] 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.

[9] 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.

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

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

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

[13] Winter M.: A new Algebraic Approach to L-Fuzzy Relations Convenient to Study Crispness. INS Information Science 139, 233-252 (2001).

[14] Winter M.: Representation Theory of Goguen Categories. Submitted to Fuzzy Sets and Systems

[15] Winter M.: Relational Constructions in Goguen Categories. in: de Swart, H. (eds): Participants Proceedings of the 6th International Seminar on Relational Methods in Computer Science (RelMiCS). Katholieke Universiteit Brabant, Tilburg, Niederlande, pp. 222-236 (2001)

[16] Zadeh L.A.: Fuzzy sets, Information and Control 8 (1965), 338-353.

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/10/11/10-11.{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 North Wales: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.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, 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