key: cord-0060997-ryktoejv
authors: Winter, Michael
title: Sharpness in the Fuzzy World
date: 2020-04-01
journal: Relational and Algebraic Methods in Computer Science
DOI: 10.1007/978-3-030-43520-2_20
sha: eccc6f1532261191382519e4ba8a8f581caf7373
doc_id: 60997
cord_uid: ryktoejv

In this paper we focus on a fuzzy version of the so-called (un)sharpness property of relational products in arrow/fuzzy categories. It is shown that the fuzzy version can be reduced to a regular (un)sharpness problem. As a consequence we obtain that relational products are also sharp in the fuzzy sense if all relational products and powers exist. This result is important in applications of arrow/fuzzy categories since relational products, and, hence, the fuzzy version of the (un)sharpness problem, are integral components of these applications.

In this paper we are interested in working with multi-valued relations in an abstract setting. In particular, we are interested in a framework for working with so-called Lrelations algebraically. Given a complete Heyting algebra L, an L-relation Q between two sets A and B is just a function Q : A × B → L, i.e., the relation provides a membership value Q(a, b) from the Heyting algebra L indicating to what degree the pair (a, b) is in relation Q. L-relations generalize (regular) relations in the following sense. As usual a relation R between two sets A and B is simply a set of pairs, i.e., R ⊆ A × B. Alternatively, R can be represented by its characteristic function R : A × B → B where B is the set of (Boolean) truth values. If we identify true with the greatest element and false with the smallest element of the Heyting algebra L we immediately obtain L-relations as a generalization of regular relations. In particular, we call an L-relation returning 0 or 1 for every pair a crisp relation. Obviously, a crisp L-relation corresponds to a regular relation.

Allegories [3] establish a suitable framework for working with any kind of relations. In particular, they provide an axiomatic system that characterizes the usual operations on relations such as the set-theoretic operation (meet) and (join) as well as the additional operations ; (composition) and . (converse) of relations. Arrow categories [12] [13] [14] add two operations . ↑ (support) and . ↓ (kernel) that allow to define crispness, and, hence, to formulate properties of L-relations. In particular, R ↑ represents the smallest crisp relation containing R, and R ↓ represents the greatest crisp relation contained in R. In the work mentioned above it has been shown that arrow categories provide a suitable framework for working with L-relations for a fixed Heyting algebra L.

In the theory of fuzzy (or L-fuzzy relations) one often uses additional operations. The standard operation computes the degree of membership of a pair (a, b) in the intersection of two L-relations Q and R as the meet of the two corresponding membership degrees, i.e., we have

where ∧ on the right-hand side denotes the meet in the Heyting algebra L. Often we are interested in an operation where the degree is computed by applying a commutative and integral quantale (or t-norm like for short) operation * to the two membership degrees instead of the meet operation of the lattice. Hence, we define a new operation on relations

where (L, * ) is a complete Heyting algebra with a t-norm like operation. Similarly, we can also define a composition operation based on * by

In [17] a set of axioms for these operations was introduced, and we will call an arrow category together with these new operations and a suitable set of axioms a fuzzy category (cf. Definition 11) . Hence, fuzzy categories are very suitable as an algebraic/categorical framework for L-fuzzy relations. In the following we will use the notation Q : C → A to denote the fact that Q is a L-relation (or regular relation) between the sets C and A. If A×B is the cartesian product of the sets A and B, then we can define the so-called fork (or right tupling) operation

In other words, Q R relates c with the pair (a, b) if c is related to a in Q and c is related to b in R. The join (or left tupling) operation S T : A × B → D for two relations S : A → D and T : B → D is defined similarly. In the abstract theory of allegories the cartesian product can be defined abstractly by so-called relational products. This definition is based on the projection functions as relations. Using the projections it is easily possible to derive the fork and join operation algebraically. The so-called sharpness problem focuses on the following simple equation

It is easy to verify this equation for concrete relations. In the abstract setting, however, this equation needs not to be valid. A counter example was provided in [5] . Therefore, we call a product sharp (resp. unsharp) if the previous equation is valid (resp. not valid) in the abstract setting. It is worth mentioning that the sharpness property is closely related to the representation problem of allegories. The existence of all products implies representability as well as sharpness. Conversely, a representable allegory is obviously embedded in a category satisfying sharpness, i.e., satisfies sharpness itself since products are unique up to isomorphism. Anyhow, sharpness is often necessary to prove properties about certain constructions algebraically. For example, if P(A) denotes the relational power of A, an abstract version of the power set, then one can easily define a relation M : P(A) × P(A) → P(A) (in fact a map) that maps a pair of subsets of A to their intersection. In order to verify typical properties of this relation algebraically sharpness of the products involved is usually needed. To our knowledge there are three different theorems showing sharpness under certain specific conditions. The first theorem is due to Zierer [18] . It requires two suitable additional products to exist in order to prove the desired property. In particular, this theorem shows that sharpness holds if the underlying allegory has all relational products. This result was later improved by Desharnais [1] . A consequence of the latter theorem is that sharpness is already valid if only one additional relational product exists. Last but not least, in [11] it was shown that sharpness always holds if one of the relations involved is between an object B and its relational power P(B). More precisely, if, for example, R of the sharpness equation has type B → P(B), then the singleton relation syQ(I B , ε) : B → P(B) mapping an element of b of B to the singleton set {b} is a map parallel to R which can be used to show sharpness (cf. Theorem 16 in the fuzzy case).

In an L-fuzzy setting we are often interested in a modified version of the relation M introduced above. As already mentioned above we are often interested in computing the intersection of two L-fuzzy sets by using a t-norm like operation * , i.e., the degree of membership of an element in the intersection of two sets A and B is computed by * instead of the lattice meet. This leads to a relation M * obtained from M by replacing the regular fork operation in the algebraic definition of M by a fork based on * , i.e., by the operation (Q * R)(c, (a, b)) = Q(c, a) * R(c, b).

At this point we want to mention at least one important application of M * . A relation algebraic approach to L-fuzzy topological spaces [6] , similar to the approach taken in [11] , requires the usage of M * already in the definition of those spaces. One of the axioms requires that the set of open sets is closed under this modified intersection. Consequently, we are interested in showing basic properties of this ( * -based) meet operation. Several of these properties require a fuzzy version of the sharpness problem, i.e., the equation

We will sketch one of these properties and its proof briefly in the conclusion. As in the regular case it is easy to verify sharpness for concrete L-relations (Theorem 14) but an algebraic proof is not possible without further assumptions. In fact, since it is possible to choose the lattice meet as the t-norm like operation * , the regular sharpness condition is a special case of the fuzzy version above. Unfortunately, none of the three theorems mentioned above can be applied immediately since the t-norm based operations * and * , do not satisfy all properties of their counterparts and ;. In fact, the first theorem mentioned above [18] is based on the fact that composition with a map from the left distributes over meet. The additional two products are used to modify the fork on the left of the composition into a suitable map. In the fuzzy setting * , composition with a map from the left only distributes over * if the map is, in addition, crisp. Consequently, a straightforward generalization to the fuzzy case does not seem possible. The second theorem relies heavily on the modular inclusion and the fact that is idempotent. Only weaker versions of the modular inclusion are valid for * , and * .

Furthermore, * is not necessarily idempotent so that this theorem cannot be generalized to the fuzzy case either. In this paper we will show that the last of the three theorems can be generalized to the fuzzy case (Theorem 16), which then will be used to reduce the fuzzy sharpness problem to a regular one (Theorem 18).

Suppose L is a complete Heyting algebra which smallest element 0, greatest element 1, meet ∧ and join ∨. Then an L-relation R between two sets A and B is a function R : A × B → L. The relational operations on L-relations are based on the operations of L in the usual way, e.g., meet and composition ; are defined as

Please note that we use the convention that composition is from left to right, i.e., Q; S means Q first, and then S . As already mentioned in the introduction the special case of B-relations corresponds to regular (set-theoretic) relations represented by their characteristic function.

In this section we want to introduce several categories as an abstract framework to work with L-relations.

In this section we want to recall some basic notions from categories, allegories and arrow categories [3, 13, 14] . Furthermore, we will introduce fuzzy categories as an extension of arrow categories adding t-norm like operations on relations.

We will write R : A → B to indicate that a morphism R of a category C has source A and target B. Composition and the identity morphism are denoted by ; and I A , respectively.

First, we are going to introduce Dedekind categories [7, 8] . These categories are called locally complete division allegories in [3] .

Meet, join, the induced ordering, the least and the greatest element are denoted by , , , AB , AB , respectively. 

A → B the following holds:

It is easy to verify that the collection of all L-relations between sets for a given complete Heyting algebra L forms a Dedekind category.

Throughout this paper we will use some basic properties of relations in Dedekind categories such as AB = BA , AB = BA , I A = I A , the monotonicity resp. antitonicity of the operations, and the fact that composition distributes over join from both sides without mentioning.

An important class of relations is given by maps.

A → B is called 1. univalent (or partial function) iff Q ; Q I B , 2. total iff I A Q; Q , 3. injective iff Q is univalent, 4. surjective iff Q is total,

It is well known that Q is total iff Q; BC = AC . We will use this equivalence in the remainder of the paper without mentioning.

The following property about maps is used later. A proof can be found in [13] .

Using converse a second residual can be defined by Q\R := (R /Q ) . This operation is characterized by the equivalence Q; X R iff X Q\R. Together the two residuals allow the definition of the so-called symmetric quotient. This construction is defined by syQ(Q, R) := Q\R Q /R . Consequently the symmetric quotient is characterized by Q; X R and R; X Q iff X syQ(Q, R). In the following lemma we have collected some basic properties of the symmetric quotient that are needed in the remainder of the paper. A proof can be found in [2, 13] . 

The equation AB ; BC = AC for all objects A, B and C can easily be shown for L-relations but does not follow from the axioms of a Dedekind category. However, two special cases of this equation where one of the two universal relations on the left-hand side is homogeneous can be verified in any Dedekind category, i.e., we have AA ; AB = AB ; BB = AB for all objects A and B. If the general equation holds, then we call the Dedekind category uniform.

Any Dedekind category allows to identify the membership values used in an abstract manner by using so-called scalar relations.

The notion of scalars was introduced by Furusawa and Kawahara [4] . An L-relation is a scalar iff every element of A is related to itself with a fixed degree a from L. Therefore, there is a one-one correspondence, i.e., a isomorphism of complete Heyting algebras, between the scalar relations on A and the lattice L. Because of this isomorphism we will occasionally identify scalars and the elements from L by using α for the scalar as well as the corresponding element (via the isomorphism) from L.

A crisp L-relation R satisfies R(x, y) = 0 or R(x, y) = 1 for all pairs (x, y). These relations can be identified with Boolean valued relations, i.e., regular set-theoretic relations. The notion of crispness cannot be defined abstractly in the theory of Dedekind categories [12, 13] . Because of this arrow categories were introduced [13, 14] . These categories add two operations (.) ↓ and (.) ↑ to Dedekind categories. Intuitively, the downarrow (or kernel) operation maps an L-relation R to the greatest crisp relation included in R and the up-arrow (or support) operation maps R to the least crisp relation that includes R.

AB for all objects A and B together with two operations ↑ and ↓ satisfying the following:

A relation R : A → B of an arrow category A is called crisp iff R ↑ = R (or equivalently R ↓ = R). The collection of crisp relations is closed under all operations of a Dedekind category, and, hence, forms a sub-Dedekind category of A [13, 14] . In particular, we will need the following lemma. A proof can be found in [13, 15] .

A be an arrow category, Q : A → B, and R : B → C. Then we have:

It was mentioned above that the collection of all L-relations forms a uniform Dedekind category. Unlike Dedekind categories in general, arrow categories are always uniform [13] . It is worth mentioning that the proof of this fact requires scalars and Axiom 4 of arrow categories, i.e., two concepts that are otherwise not used in this paper.

The abstract version of a cartesian product is given by a relational (or direct) product [9, 10] . In the context of arrow categories we are usually interested in relational products for which the projections are crisp.

with two relations π : A × B → A and ρ : A × B → B so that the following equations hold π ↓ = π, ρ ↓ = ρ, π ; π I A , ρ ; ρ I B , π ; ρ = AB , π; π ρ; ρ = I A×B .

An arrow category has products if the relational product for each pair of objects exists.

It follows immediately from the definition above that the two projections are crisp maps.

Using the projections of a relational product we now introduce the fork (or right tupling) operation Q R : C → A × B of two relations Q : C → A and R : C → B by Q R := Q; π R; ρ . Analogously, the left tupling operation S T : A × B → D for two relations S : A → D and T : B → B is defined as S T := π; S ρ; T . We will adopt the convention that composition binds tighter than the operations defined above. The (un)sharpness problem of relational products is the validity of the equation

The equation above is easy to verify for concrete relation but does not follow from the axioms of a relational product. As mentioned in the introduction sharpness can be shown by requiring additional structure (cf. [1, 11, 18] ). In particular, the relational product is sharp iff all relational products exists.

An abstract version of power sets is given by the notion of a relational (or direct) power [10] . Please note that in the context of arrow categories we are interested in the set of all L-fuzzy subsets of A, i.e., in the set of all functions f : A → L. This leads to the following definition of a relational power in arrow categories that differs from previous definitions [16] . Compared to the previous definitions of the relational power the definition above adds the kernel operation to the symmetric quotient in both axioms. Without this modification the relational power in the case of L-relations would not contain all fuzzy subsets of A. On the other hand, the is element relation ε is no longer extensional, and, hence, the inclusion (or subset) relation ε\ε is just a pre-order, i.e., not necessarily antisymmetric. For a concrete example explaining this situation in detail we refer to [16] . Lemma 7 (2) 3. We only show the first equation since the second follows from the first by using converse. First, we have

The inclusion Q; syQ(Q, ε) ↓ ε follows analogously. This immediately implies Q ε; syQ(Q, ε) ↓ = ε; syQ(ε, Q) ↓ using (1) and Lemma 3.

As already mentioned in the introduction in applications of L-fuzzy theory so-called t-norm like operations are important. If L is a complete lattice, then L, * with a binary operation * on L is called a partially ordered (Abelian) monoid iff 1. L, * , 1 is a bounded Abelian monoid, i.e., * is associative and commutative with the greatest element 1 of L as neutral element, 2. * is monotonic in both parameters.

If * distributes over arbitrary unions in both parameters, then we call * continuous. A continuous partially ordered Abelian monoid is also known as commutative integral quantale. For simplicity and its analogy to t-norm operations in fuzzy sets we call the operation * of a continuous partially ordered Abelian monoid a t-norm like operation.

Given a complete Heyting algebra L with a t-norm like operation * we can define two new operations on L-relations based on * by

In [17] the basic properties of these operations, in particular, the validity of versions of the modular inclusion for * and * , instead of and ; was investigated. This study lead to the following abstract definition of a fuzzy category.

and * , so that the following holds: 

for all P, Q : A → B, R : B → C, and S : A → C.

The following lemma collects some immediate consequences of the definition above. Proof. 1. We have Q * R Q * R ↑ = Q R ↑ Q by the monotonicity of * and Axiom 3. The second property follows analogously. 2. This is an immediate consequence of Axiom 3 since AB is crisp. 3. We compute

by (1) 4. This is just the dual (via . ) of Axiom 7. 5. This is an immediate consequence of Axiom 7 and (4) since I A and I B are crisp.

In the remainder of the paper we will use the Axioms (1)-(8) and the lemma above without mentioning. In the following lemma we show some basic properties of relations in fuzzy categories that are needed in the remainder of the paper. Proof. 1. This follows immediately from 

. This follows immediately from

This completes the proof.

In a fuzzy category we can define a fuzzy right tupling Q * R : , (a, b) ) * (S * T ) ((a, b) , d)

i.e., we have (

Similar to the regular sharpness problem, the inclusion of (FS) follows without any further assumptions. 

Proof. The following computation (Q * R) * , (S * T ) = (Q; π * R; ρ ) * , (π; S * ρ; T ) (Q; π ) * , (π; S ) * (R; ρ ) * , (ρ; T ) exchange inclusion

shows the assertion.

As mentioned in the introduction there are several theorems showing regular sharpness under certain additional assumptions. Only one of these results can be generalized to the fuzzy version of the unsharpness problem. Proposition 3.2.1 of [11] basically requires that an injective map exists in parallel to the relation R of the right-tupling in the sharpness equation. The precise situation in the fuzzy case is visualized in Fig. 1 . In order to prove the fuzzy version (Theorem 16) of Proposition 3.2.1 we need to require that f is, in addition, crisp. 

Proof. In order to show the inclusion , consider the following computation

= (Q * f ; U) * , (π; S * ( A×B,B * ρ; (U * , R)) * , T ) A×B,B crisp = (Q * f ; U) * , (π; S * (π; π ; ρ * ρ; (U * , R)) * , T ) π; π ; ρ = A×B,B = (Q * f ; U) * , (π; S * ((π; π * ρ; (U * , R); ρ ); ρ) * , T ) Lemma 13 (2) = (Q * f ; U) * , (π; S * (π; π * ρ; (U * , R); ρ ) * , ρ * , T ) ρ crisp = (Q * f ; U) * , (π; S * (π; π * ρ; (U * , R); ρ ) * , (ρ; T )) ρ crisp (Q * f ; U) * , (π; π * ρ; (U * , R); ρ ) * , ((π; π ) * , (π; S ) * ρ; T ) Lemma 13(3)

The converse inclusion was already shown in Lemma 15.

As an immediate consequence of the previous theorem we obtain sharpness if one of the relations is between an object B and its relational power P(B). The situation of the following corollary is visualized in Fig. 2 . Proof. This follows immediately from Theorem 16 with f = I B and U = syQ(I B , ε) ↓ where the relation U is a crisp and injective map by Lemma 10(2).

Please note that the previous corollary immediately implies (ε * ε) * , (S * T ) = ε * , S * ε * , T for appropriate relations S and T .

We are now able to prove the main theorem of this paper. It shows the fuzzy version of sharpness if a suitable crisp version of sharpness holds. As above the situation of the theorem and its proof is visualized in Fig. 3 . Proof. First, consider the following computation

Corollary 17

= (ε * ε) * , (π; syQ(ε, Q) ↓ ; π * ρ; syQ(ε, R) ↓ ; ρ ) = (ε * ε) * , (π; syQ(ε, Q) ↓ ; π ρ; syQ(ε, R) ↓ ; ρ ) both relations crisp = (ε * ε) * , (π; syQ(ε, Q) ↓ ρ; syQ(ε, R) ↓ ).

The equation

analogously. Furthermore, we have (π; syQ(ε, Q) ↓ ρ; syQ(ε, R) ↓ ) * , (syQ(S , ε) ↓ ; π syQ(T , ε) ↓ ; ρ ) = (π; syQ(ε, Q) ↓ ρ; syQ(ε, R) ↓ ); (syQ(S , ε) ↓ ; π syQ(T , ε) ↓ ; ρ ) crisp rel.

= π; syQ(ε, Q) ↓ ; syQ(S , ε) ↓ ; π ρ; syQ(ε, R) ↓ ; syQ(T , ε) ↓ ; ρ assump.

= π; syQ(ε, Q) ↓ ; syQ(S , ε) ↓ ; π * ρ; syQ(ε, R) ↓ ; syQ(T , ε) ↓ ; ρ crisp rel.

= syQ(ε, Q) ↓ ; syQ(S , ε) ↓ ; π * syQ(ε, R) ↓ ; syQ(T , ε) ↓ ; ρ as well as (ε * ε) * , (syQ(ε, Q) ↓ ; syQ(S , ε) ↓ ; π * syQ(ε, R) ↓ ; syQ(T , ε) ↓ ; ρ ) = ε * , (syQ(ε, Q) ↓ ; syQ(S , ε) ↓ ; π ) * ε * , (syQ(ε, R) ↓ ; syQ(T , ε) ↓ ; ρ ) Corollary 17 Combining the computation above immediately leads to the fuzzy version of sharpness of the product A × B.

In [1] it was shown that the regular sharpness property from C via A × B to D holds, i.e., for all relations Q : C → A, R : C → B, S : A → D, and T : B → D, if one of the additional products A × C, B × C, A × D or B × D exists. Combining this with the result of the main theorem we obtain that fuzzy sharpness from C via A × B to D holds if the objects P(C), P(D), P(C) × P(C), P(D) × P(D) and either one of the products A × P(C) × P(C), B × P(C) × P(C), A × P(D) × P(D) or B × P(D) × P(D) exists.

From this discussion we immediately obtain the following corollary.

Corollary 19. Let F be a fuzzy category with relational products and powers. Then fuzzy sharpness holds.

In this paper we have introduced the fuzzy unsharpness problem. This problem is obtained by replacing and ; in the regular unsharpness problem by the t-norm based operations * and * , . We have shown that the fuzzy unsharpness problem can be reduced to the regular unsharpness problem if some additional relational products and powers exist. As a consequence we obtained Corollary 19 stating fuzzy sharpness if the fuzzy category has all relational products and powers.

In the opinion of the author the results of this paper show once again that (un)sharpness is more a structural problem related to relational products and representability than a problem related to the specific operations used in the equation.

Last but not least, we want to state a property that requires fuzzy sharpness in its proof. The actual proof is omitted due to lack of space. Suppose ε 1 : A → P(A), ε 2 : P(A) → P(P(A)), π 1 , ρ 1 : P(A) × P(A) → P(A), and π 2 , ρ 2 : P(P(A)) × P(P(A)) → P(P(A)) are given. Then the binary ( * -based) meet relation M * : P(A) × P(A) → P(A) defined by M * = syQ(ε 1 * ε 1 , ε 1 ) ↓ maps two fuzzy subsets of A to their t-norm based intersection, i.e., M * ((B, C), D) iff D(a) = B(a) * C(a) for all a ∈ A. Similarly, the join relation J : P(P(A)) → P(A) defined by J = syQ(ε 1 ; ε 2 , ε 1 ) ↓ maps a set of fuzzy subsets of A to their union. The property below now states that the ( * -based) meet of the two unions of two sets of fuzzy sets M and N is equal to the union of the set obtained by taking the ( * -based) meet of all pairs of sets from M and N:

(π 2 ; J ρ 2 ; J); M * = syQ(ε 1 ; M * ; (π 1 ; ε 2 * ρ 1 ; ε 2 ), ε 1 ) ↓ In the proof of this property fuzzy sharpness is needed several times. The most general case takes the form:

(ε 1 * ε 1 ); (ε 2 ; π 2 * ε 2 ; ρ 2 ) = ε 1 ; ε 2 ; π 2 * ε 1 ; ε 2 ; ρ 2 .

Monomorphic characterization of n-ary direct products

A Study on Symmetric Quotients. University of the Federal Armed Forces Munich, Bericht Nr

Crispness and representation theorems in Dedekind categories

On the derivation of identities involving projection functions

A Relation-Algebraic Approach to L-Fuzzy Topology. Submitted to Relational and Algebraic Methods in Computer Science

Catégories de Dedekind. Morphismes dans les Catégories de Schröder

Squares and rectangles in relational categories -three cases: semilattice, distributive lattice and Boolean non-unitary

Relations and Graphs

Relational Mathematics

Relational Topology. LNM

A new algebraic approach to L-fuzzy relations convenient to study crispness

Goguen Categories -A Categorical Approach to L-fuzzy Relations

Arrow categories. Fuzzy Sets Syst

Membership values in arrow categories

Type-n arrow categories

T-norm based operations in arrow categories

Programmierung mit Funktionsobjekten: Konstruktive Erzeugung semantischer Bereiche und Anwendung auf die partielle Auswertung. Dissertation, TU München, TUM-I8803