Title Author Keyword ::: Volume ::: Vol. 19Vol. 18Vol. 17Vol. 16Vol. 15Vol. 14Vol. 13Vol. 12Vol. 11Vol. 10Vol. 9Vol. 8Vol. 7Vol. 6Vol. 5Vol. 4Vol. 3Vol. 2Vol. 1 ::: Issue ::: No. 4No. 3No. 2No. 1

On Separability of Fuzzy Relations

Przemyslaw Grzegorzewski

1Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland, 2Faculty of Mathematics and Information Science, Warsaw University of Technology, Warsaw, Poland
Correspondence to: Przemyslaw Grzegorzewski (pgrzeg@ibspan.waw.pl)
Received August 23, 2017; Revised September 18, 2017; Accepted September 21, 2017.
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract

The problem of separability verification of fuzzy binary relations is considered. A necessary and sufficient condition for separability is given and an efficient algorithm for checking separability that can be easily applied in practice is suggested. The paper is supplemented by a simple test that sometimes might be helpful in detecting non-separability just at one glance.

Keywords : Fuzzy relation, Noninteractive fuzzy relation, Separable fuzzy relation, Connected/disconnected variables
1. Introduction

Fuzzy relation generalize the concept of the classical relation by admitting a partial association between elements of universes of discourse [1, 2]. Hence fuzzy relations can be used for modeling more or less vague relationships between objects. They can formally be treated like fuzzy sets. The notion of fuzzy relation seems to be very natural and useful in various applications. In many cases fuzzy relations describe the actual situation more adequately than the classical ones. For instance, an association between different diseases and possible symptoms, documents and keywords, expected gain and possible states of nature, etc., are rarely of binary nature. Hence, by admitting there different intensity of association we obtain much more adequate mathematical model of the discussed problem (see, e.g., [35]).

Some types of relations are of special importance like fuzzy equivalence relations, fuzzy ordering relations, similarity relations, etc. (for the review and basic mathematical properties see, e.g., [10]). Separable (noninteractive) fuzzy relations are of interest in the case that one looks at a fuzzy relation RX × Y as a fuzzy relationship between two variables or decision rules and with X and Y treated as corresponding sets of all possible values or possible alternatives, respectively. If variables and are disconnected then the choice of the particular value xX of variable does not depend on the choice of the particular value yY of variable and conversely. For some recent applications of separable fuzzy relations and noninteractive variables in different fields one can mention: fuzzy optimization [7], prediction models [8], fuzzy differential equation [9], fuzzy numbers [10], fuzzy weighting [?], fuzzy neural networks [12], the identification of neuro-fuzzy based model with separable input signals [13], engineering applications [14], etc.

Requirements to be met for concluding that a given fuzzy binary relation is separable are not complicated. However, checking all necessary conditions might be tedious, especially if the corresponding relation matrix is large enough. Therefore, an efficient algorithm that simplifies the separability verification would be desirable. Such algorithm is suggested in this contribution.

The paper is organized as follows. In Section 2 we introduce basic notation and concepts connected with fuzzy relations. Section 3 is devoted to separable fuzzy binary relations. A simple sufficient condition showing that variables under study are connected is given in Section 4. By this result in some situations one glance might be enough to detect non-separability. Unfortunately, since this separability test is based on the sufficient condition, it cannot be conclusive generally. Therefore, in Section 5, we prove a necessary and sufficient condition for separability which gives a strong basis for the decisive criterion. The theorem is supplemented by the desired efficient algorithm for checking separability that can be easily applied in practice. The aforementioned considerations and results are illustrated by numerical examples.

2. Fuzzy Relations

A fuzzy binary relation R between crisp sets X and Y is a fuzzy subset of the Cartesian product X × Y, i.e. RX × Y = {(x, y) : xX, yY }. Thus a fuzzy binary relation is a set of ordered pairs {((x, y), R(x, y)) : xX, yY }, where R : X × Y → [0, 1] is the membership function of R. The membership grade R(x, y) ∈ [0, 1] reflects the intensity of relation between x and y. If for some pair (x, y) we have R(x, y) = 1, it denotes that elements x and y are fully related. On the other hand, if R(x, y) = 0 then it means that these elements are unrelated. Finally, intermediate values, i.e. 0 < R(x, y) < 1, indicate a partial association.

From now on we make the assumption that both sets X and Y are finite, i.e. X = {x1, , xn} and Y = {y1, , ym}. Under this assumption a convenient representation of a fuzzy binary relation RX × Y is, the so called, relation matrix [R] = [rij ], where

$rij=R(xi,yj), i=1,…,n, j=1,…,m.$

The height of a fuzzy binary relation R is a real number defined by

$h(R)=maxx∈X maxy∈YR(x,y).$

Thus the height is the largest intensity of the relation obtained by any pair (x, y) ∈ R.

We say that fuzzy binary relations R and Q are equivalent if and only if R(x, y) = Q(x, y) for all xX and yY. A fuzzy relation Q is included in R if and only if

$Q(x,y)≤R(x,y) ∀(x,y)∈X×Y.$

The intersection PQ of two fuzzy binary relations P and Q in X × Y is a fuzzy binary relation RX × Y defined as

$R(x,y)=T(P(x,y),Q(x,y)) ∀(x,y)∈X×Y,$

where T denotes a t-norm, while the union R = PQ of two fuzzy binary relations P and Q in X × Y is defined as follows

$R(x,y)=S(P(x,y),Q(x,y)) ∀(x,y)∈X×Y,$

where S is a t-conorm. Further on we restrict our considerations to classical triangular norms, i.e. T(x, y) = min{x, y} = xy and S(x, y) = max{x, y} = xy in (1) and (2), respectively.

A Cartesian product of two fuzzy sets A and B defined in the universes of discourse X and Y, respectively, is a fuzzy relation A×B in the product space X×Y with the membership function given by (A × B)(x, y) = T(A(x), B(y)),

$(A×B)(x,y)=T(A(x),B(y)),$

where xX, yY and T is a t-norm. As it was mentioned above, in the present contribution we assume that T is a classical t-norm.

Given a fuzzy binary relation RX × Y, its domain, domR, is a fuzzy set on X whose membership function is defined by

$dom R(x)=maxy∈YR(x,y) for all x∈X,$

while its codomain (range), codR, is a fuzzy set on Y with membership function defined by

$cod R(y)=maxx∈X R(x,y) for all y∈Y.$

It is easily seen that domR(x) and codR(y) are equal to the hight of the corresponding row and column of matrix [R], respectively (see [1, 2]). Consequently, each element of X belongs to domR to the degree equal to the strength of its strongest relation to any member of set Y, while each element of Y belongs to codR to the degree equal to the strength of its strongest relation to any member of set X.

The domain and codomain are also called the first projection ProjXR and the second projection ProjYR of a fuzzy binary relation, respectively, i.e. domR = ProjXR and codR = ProjYR.

An operation, which is in some sense an inverse to the projection, is called a cylindric extension. The cylindric extension of domR is a fuzzy relation cyl(domR) ⊆ X × Y with membership function cyl(domR)(x, y) = domR(x) for all xX, yY

$cyl(dom R)(x,y)=dom R(x) for all x∈X,y∈Y$

while the cylindric extension of codR is a fuzzy relation cyl(codR) ⊆ X × Y with membership function cyl(codR)(x, y) = codR(y) for all xX, yY.

$cyl(cod R)(x,y)=cod R(y) for all x∈X,y∈Y.$

Obviously,

$R⊆cyl(dom R)∩cyl(cod R).$

Moreover, it can be shown that the cylindric extensions produce the largest fuzzy relation (in the sense of inclusion) with given projection.

3. Separable Fuzzy Relations

As it is seen from (4) and (5), each binary fuzzy relation RX × Y determines its projections, i.e. domain and range. Conversely, the problem arises whether these two projections suffice to reconstruct the relation R. This usually is not the case. Indeed, both projections do not retain complete information conveyed by the original fuzzy relation, so usually one cannot completely reconstruct a relation from its projections. In general, the reconstruction of a relation via the Cartesian product of its projections is a relation that includes the original relation, i.e.

$R⊆dom R×cod R.$

However, in the special case, we can uniquely reconstruct a fuzzy binary relation from its projections. It happens so if the relation is separable (see [15, 16]), noninteractive [3, 4] or orthogonal [5].

### Definition 1

A fuzzy binary relation RX ×Y isseparableif and only if

$R=dom R×cod R.$

The proof of the following lemma is obvious.

### Lemma 2

The following conditions are equivalent:

1. i) R is separable,

2. ii) R(x, y) = domR(x) ∧ codR(y) ∀xX, ∀yY,

3. iii)R = cyl(domR) ∩ cyl(codR).

Separable fuzzy relations are of special interest in the case that one looks at fuzzy relation as a relationship between two variables, attributes or decision rules and with X and Y treated as corresponding sets of all possible values or possible alternatives, respectively.

### Definition 3

If the relation RX × Y is separable then variablesandare calleddisconnected(noninterative). Otherwise they are connected (interactive).

If variables and are disconnected then the choice of the particular value xX of variable does not depend on the choice of the particular value yY of variable and conversely. One may notice that the notion of disconnected variables can be thought of as being analogous to independent random variables in probability theory.

### Example 1

LetX = {x1, x2, x3, x4} and Y = {y1, y2, y3, y4, y5}. It is easily seen that the fuzzy binary relation R1X×Y described by the relation matrix [R1] given below is separable.

$[R1]=[0.30.40.400.40.30.70.500.70.310.500.90.10.10.100.1].$

Indeed, domR1 = 0.4/x1 + 0.7/x2 + 1/x3 + 0.1/x4and codR1 = 0.3/y1 +1/y2 +0.5/y3 +0/y4 +0.9/y5, hence R1is separable.

Now let us consider a fuzzy binary relation R2X×Y described by the relation matrix [R2] given below

$[R2]=[0.30.40.400.40.30.70.200.70.310.500.90.10.10.100.1].$

Although the projections of these two matrices are identical, i.e. domR2 = domR1and codR2 = codR1, the fuzzy relation R2is not separable, since R2(x2, y3) = 0.2 ≠ domR2(x2) ∧codR2(y3) = 0.5.

To prove that a given fuzzy binary relation RX × Y is separable, where X = {x1, , xn} and Y = {y1, , ym}, one has to check m · n conditions (see condition ii in Lemma 2). Although the conditions to be checked are not difficult, their number might be large (and hence a time necessary for calculations may be long) if the relation matrix is too big. However, let us firstly consider two trivial cases where we get separability immediately.

### Lemma 4

A fuzzy binary relation RX×Y such that R = ∅︀ is separable.

Proof

If R = ∅︀ then R(x, y) = 0 for each xX and yY. Hence domR = ∅︀ and codR = ∅︀ and therefore R = domR × codR which is our claim.

### Lemma 5

A fuzzy binary relation RX×Y such that R(x, y) = 1 for each xX and yY is separable.

Proof

If R(x, y) = 1 for each xX and yY then R = X × Y. Moreover domR = X, codR = Y and thus R = domR × codR which proves the lemma.

The interpretation of Lemma 4 and 5 is also straightforward since if there is no association between two variables or if all their outcomes are fully related, an information about a particular outcome of one of these variables bring no new information on the other variable.

Unfortunately, in all other cases, except of these two trivial situations, we need some time to check all necessary conditions. Therefore, an algorithm which enables to reduce the number of conditions to be checked to solve the problem of possible separability would be desirable. In next section we propose a very simple sufficient condition showing that variables under study are connected which may be used to conclude the lack of separability without any calculations, just at a glance. Then, in Section 5 we prove the necessary and sufficient condition for separability which gives us an efficient algorithm for checking separability of fuzzy binary decisions.

4. A Simple Test for Separability

Let us recall that the support of a fuzzy set A with a membership function A : X → [0, 1] is a crisp subset supp(A) of the universe of discourse X given as follows

$supp(A)={x∈X:A(x)>0}.$

Suppose, sets X = {x1, , xn} and Y = {y1, , ym} describe all possible values of variables and , respectively. Further on following definition will be useful.

### Definition 6

A significant part of a fuzzy relationRX×Y is a fuzzy relation R̃ ⊆ supp(domR) × supp(codR) such that

$R˜(x,y)=R(x,y) ∀x∈supp(dom R),y∈supp(cod R).$

Thus, the significant part of a fuzzy binary relation R is just the reduction of this relation to the Cartesian product supp(domR) × supp(codR). It is easily seen that for a given fuzzy relation RX × Y described by the relation matrix [R] one gets a relation matrix [&] corresponding to by deleting all zero rows and columns in [R]. Therefore [&] is a minor of [R].

### Example 2

Going back to Example 1 one can see that R̃1is described by the following matrix

$[R˜1]=[0.30.40.40.40.30.70.50.70.310.50.90.10.10.10.1].$

In the example given above the significant part of a fuzzy relation under study is equivalent to the support of that relation but it is not a rule. For every binary fuzzy relation R we have supp(R) ⊆ supp(domR) × supp(codR).

Below we state a theorem that provides an easy condition to show that given a fuzzy binary relation is not separable and therefore two variables under study are connected.

### Theorem 7

Let RX×Y be a fuzzy binary relation with membership function R : X×Y → [0, 1] and R ≠ ∅︀. If R is separable then

$supp(R)=supp(dom R)×supp(cod R).$
Proof

Suppose the relation R is separable and, contrary to our claim, that

$supp(R)⊂supp(dom R)×supp(cod R),$

i.e. there exist (x0, y0) ∈ supp(domR) × supp(codR) such that (x0, y0) = 0. By Definition 6 and by condition ii) in Lemma 2 we get

$dom R(x0)∧cod R(y0)=R(x0,y0)=0.$

Hence domR(x0) = 0 or codR(y0) = 0 and therefore either x0 /∈ supp(domR) or y0 /∈ supp(codR) which contradicts our assumption and completes the proof.

Theorem 7 provides a quick test for the lack of separability. Below we give its equivalent version expressed in a more useful matrix representation.

### Corollary 8

If a matrix [ &] corresponding to a fuzzy binary relation R contains a zero element then R is not separable and variablesandare connected.

### Example 3

LetX = {x1, x2, x3, x4} and Y = {y1, y2, y3, y4, y5}. Suppose a fuzzy binary relation R3X×Y is described by the following relation matrix [R3]

$[R3]=[0.30.40.400.40.300.500.70.310.500.90.10.10.100.1].$

Since

$[R˜3]=[0.30.40.40.40.300.50.70.310.50.90.10.10.10.1]$

contains zero element the fuzzy binary relation R3is not separable.

The criterion given in Corollary 8 works, of course, in one direction only: if there are no zeros in the matrix [&], the relation R may be separable or not, and further checking is necessary.

### Example 4

Going back to Example 1 we find that although there is no zero element in [&2] the relation R2is not separable.

Although Theorem 7 specifies only the sufficient condition for separability of fuzzy binary relations, Corollary 8 could be helpful in some situations in concluding that some variables are connected. In the next section we prove the necessary and sufficient condition for separability requires more operations but solves the problem of separability definitely.

5. The Necessary and Sufficient Condition

Let us start from recalling that the strongα-cut of a fuzzy set A with a membership function A : X → [0, 1], where α ∈ [0, 1), is a crisp subset $Aα+$ of the universe of discourse X defined as

$Aα+={x∈X:A(x)>α}.$

It is clear that the support is simply zero α-cut, i.e. $suppA=A0+$. Please, distinguish the strong α-cut from the usual α-cut given by Aα = {xX : A(x) ⩾ α}, which is mostly used in fuzzy context. However, in this contribution strong α-cuts appear more suitable for specifying our main result.

### Theorem 9

Let RX × Y denote a fuzzy binary relation such that R ≠ ∅︀. Then R is separable if and only if

$Rα+=(dom R)α+×(cod R)α+ ∀α∈[0,1).$
Proof

Firstly, let’s note that for any two nonempty fuzzy sets A in X and B in Y and for any α ∈ [0, 1) the following equality holds

$(A×B)α+=Aα+×Bα+.$

Indeed, by [6, 17] we have

$(x,y)∈(A×B)α+⇔(A×B)(x,y)>α⇔min{A(x),B(y)}>α⇔A(x)>α and B(y)>α⇔x∈Aα+ and y∈Bα+⇔(x,y)∈Aα+×Bα+.$

Let us also recall the well-known fact that any two fuzzy sets C and D in the same universe of discourse are equal if and only if their strong α-cut are equal for any α ∈ [0, 1), i.e.

$C=D⇔Cα+=Dα+ ∀α∈[0,1).$

Now suppose that a fuzzy binary relation R is separable. Then, by Definition 9 we have R = domR × codR, so by (19) we obtain

$Rα+=(dom R×cod R)α+ ∀α∈[0,1).$

Now, substituting domR and codR into (18) we receive

$(dom R×cod R)α+=(dom R)α+×(cod R)α+ ∀α∈[0,1),$

and combining (20) with (21) we obtain (17).

Conversely, if (17) holds then by (19) it implies (20). Now, by (18) we have (21), and applying (19) once more, we obtain R = domR × codR, which means that R is separable. Thus the proof is complete.

One can easily notice that Theorem 7 implies from the above Theorem 9. Actually, if R is separable then $Rα+=(dom R)α+×(cod R)α+$ holds for each α ∈ [0, 1) so, in particular, for α = 0, i.e. $R0+=(dom R)0+×(cod R)0+$. Now, keeping in mind that zero α-cut is just the support, we immediately obtain (14) in Theorem 7.

Below we propose a practical and efficient algorithm for checking whether a given fuzzy binary relation is separable, based on Theorem 9. We begin from generalizing the notion of the significant part of a fuzzy relation given in Definition 6.

### Definition 10

Letα ∈ [0, 1). Theα-significant part of a fuzzy relationRX×Y is a fuzzy relation R̃αsuch that

$R˜α(x,y)=R(x,y) for all x∈(dom R)α+,y∈(cod R)α+.$

It is clear that zero α-significant part of a fuzzy relation is usual significant part of a fuzzy relation defined in (13), i.e. 0 = &.

Now, combining Theorem 9 and the notion of the α-significant part of a fuzzy relation we are ready for suggesting the desired algorithm testing whether a given fuzzy binary relation is separable. The general idea can be specified by the following corollary.

### Corollary 11

A fuzzy binary relation R is separable if and only if for anyα ∈ [0, 1) the corresponding matrix [&α] contains no element which is smaller than or equal toα.

### Remark 12

In practice there is no need to check all α ∈ [0, 1) but only those occurring in the relation domain and codomain. Indeed, they are the only ones that can result in omitting one or more rows or columns from the original matrix. Moreover, since their number is no greater than the total number of rows and columns in the matrix, the proposed necessary and sufficient criterion for separability seems to work efficiently in practice. Actually, if X = {x1, , xn} and Y = {y1, , ym} then the cardinality card(W) = ln + m.

### Algorithm

1. Step 1 Given relation matrix [R] find domR = γ1/x1 + + γn/xn and codR = δ1/y1 + + δm/ym.

2. Step 2 Find W = {α : α = γi or α = δj, i = 1, , n; j = 1, , m}.

3. Step 3 For i = 1 to card(W) do: if [&αi] contains an element wαi then R is not separable; STOP.

4. Step 4 R is separable; STOP.

### Remark 13

Although it is not necessary for performing the algorithm given above, it is advisable to order values in W before moving to Step 3. Indeed, if we arrange these values in the increasing order, i.e. if W = {α1, …, αl} so that α1 < α2 < … < αl, then in each next iteration of the loop in Step 3 we would operate with a smaller matrix than in the previous iteration.

We present the way in which our algorithm works in two examples.

### Example 5

Let us consider once more the relation R2given in Example 1, i.e.

$[R2]=[0.30.40.400.40.30.70.200.70.310.500.90.10.10.100.1]$

for which we have domR2 = 0.4/x1+0.7/x2+1/x3+0.1/x4 and codR2 = 0.3/y1 +1/y2 +0.5/y3 +0/y4 +0.9/y5. Thus, the potential values to be checked are only those that appear in the domain or codomain and are smaller than 1, i.e. W = {0, 0.1, 0.3, 0.4, 0.5, 07, 0.9}. So our criteria reduces to check whether [$R˜2α$] contains no element which is smaller or equal toαforαW only.

Forα = 0 we have to omit the fourth column in [R2] and we obtain

$[R˜20]=[0.30.40.40.40.30.70.20.70.310.50.90.10.10.10.1].$

Since [$R˜20$] does not contain 0 we cannot make any conclusion yet and we have to consider the next value in W, i.e. 0.1. Hence we omit all the column and/or the rows that do not contain elements greater than 0.1. It results in

$[R˜20.1]=[0.30.40.40.40.30.70.20.70.310.50.9].$

Sine there is no element smaller or equal to 0.1 in [$R˜20.1$], so we cannot make any conclusion yet and we move to the next value in W, i.e. 0.3. Now we have to omit the first column and we obtain

$[R˜20.3]=[0.40.40.40.70.20.710.50.9].$

However, it is seen that [$R˜20.3$] contain 0.2 which is smaller than the current parameterα = 0.3, so by Corollary 11 the fuzzy binary relation R2is not separable.

### Example 6

Let us consider once more the relation R1given in Example 1, i.e.

$[R1]=[0.30.40.400.40.30.70.500.70.310.500.90.10.10.100.1].$

Here we have identical domain and codomain as in the previous example, so the set W of values to be checked is also the same as before. Thus we can find the followingα-significant parts of the fuzzy relation R1:

$[R˜10]=[0.30.40.40.40.30.70.50.70.310.50.90.10.10.10.1],[R˜10.1]=[0.30.40.40.40.30.70.50.70.310.50.9],[R˜10.3]=[0.40.40.40.70.50.710.50.9],[R˜10.4]=[0.70.50.710.50.9], [R˜10.5]=[0.70.710.9],[R˜10.7]=[10.9], [R˜10.9]=[1].$

Since none of [$R˜1α$] contains any element smaller or equal toα, hence R1is separable.

6. Conclusions

In various problems of approximate reasoning and broadly perceived decision making the information whether variables (attributes) under study are connected/noninteractive and whether the corresponding fuzzy relations are separable is of importance. Therefore, a simple test for separability of fuzzy relations is desirable. In this contribution we have suggested an efficient algorithm for checking separability based on the necessary and sufficient condition. We have also indicated a simple test for detecting interactivity based on the sufficient condition. The suggested methods could be easily applied in practice.

However, some problems in the field remain open. Firstly, in the paper we have restricted our attention to fuzzy binary relations. Therefore, a generalization of the proposed methods for more dimensions would be interesting. Secondly, in this contribution we have adopted the common assumption that the Cartesian product of fuzzy sets is defined with respect to the classical t-norm (i.e. minimum) and, consequently, the minimum operator appears in the definition of separability. However, one may consider there some other t-norms and hence discuss the notion of t-separability.

Conflict of Interest

References
1. Zadeh, LA (1971). Towards a theory of fuzzy systems. Aspects of Networks and Systems Theory. New York, NY: Holt, Rinehart & Winston, pp. 469-490
2. Zadeh, LA (1971). Quantitative fuzzy semantics. Information Sciences. 3, 159-176.
3. Pedrycz, W, and Gomide, F (2007). Fuzzy Systems Engineering: Toward Human-Centric Computing. Hoboken, NJ: Wiley
4. Pedrycz, W, Ekel, P, and Parreiras, R (2010). Fuzzy Multicriteria Decision-Making: Models, Methods and Applications. Hoboken, NJ: Wiley
5. Tettamanzi, A, and Tomassini, M (2001). Soft Computing: Integrating Evolutionary, Neural, and Fuzzy Systems. Berlin, Germany: Springer
6. Klir, GJ, and Yuan, B (1995). Fuzzy Sets and Fuzzy Logic: Theory and Applications. New York, NY: Prentice Hall
7. Inuiguchi, M, and Lodwick, WA (2015). Foundational contributions of K. Asai and H. Tanaka to fuzzy optimization. Fuzzy Sets and Systems. 274, 24-46.
8. Bacani, F, and de Barros, LC (2017). Application of prediction models using fuzzy sets: a Bayesian inspired approach. Fuzzy Sets and Systems. 319, 104-116.
9. Cabral, VM, and Barros, LC (2015). Fuzzy differential equation with completely correlated parameters. Fuzzy Sets and Systems. 265, 86-98.
10. Coroianu, L (2016). Necessary and sufficient conditions for the equality of the interactive and non-interactive sums of two fuzzy numbers. Fuzzy Sets and Systems. 283, 40-55.
11. Pavlacka, O (2011). Modeling uncertain variables of the weighted average operation by fuzzy vectors. Information Sciences. 181, 4969-4992.