Generation and Characterization of Fuzzy T-preorders

Abstract

This article studies T-preorders that can be generated in a natural way by a single fuzzy subset. These T-preorders are called one-dimensional and are of great importance, because every T-preorder can be generated by combining one-dimensional T-preorders.

In this article, the relation between fuzzy subsets generating the same T-preorder is given, and one-dimensional T-preorders are characterized in two different ways: They generate linear crisp orderings on X and they satisfy a Sincov-like functional equation. This last characterization is used to approximate a given T-preorder by a one-dimensional one by relating the issue to Saaty matrices used in the Analytical Hierarchical Process. Finally, strong complete T-preorders, important in decision-making problems, are also characterized.

INTRODUCTION

T-preorders were introduced by Zadeh (1971) and are very important fuzzy relations, because they fuzzify the concept of preorder on a set. Although there are many works studying their properties and applications to different fields (Zadeh 1971; Valverde 1985; Bodenhofer 1999), authors have not paid much attention to their relationship with the very important representation theorem. Roughly speaking, the representation theorem states that every fuzzy subset μ of a set X generates a T-preorder on X in a natural way and that every T-preorder can be generated by a family of such special T-preorders.

The representation theorem provides us with a method for generating a T-preorder from a family of fuzzy subsets. These fuzzy subsets can measure the degrees to which different features are fulfilled by the elements of a universe X or can be the degrees of compatibility with different prototypes. Reciprocally, from a T-preorder, a family (in fact many families) of fuzzy subsets can be obtained, thus providing semantics to the relation.

This article provides some results of T-preorders related to the representation theorem. Special attention is paid to one-dimensional T-preorders (i.e., T-preorders generated by a single fuzzy subset), because they are the building bricks of T-preorders. The fuzzy subsets that generate the same T-preorder are determined (Propositions 3.1 and 3.3), and one-dimensional T-preorders are characterized in two different ways: in “A Characterization of One-Dimensional T-Preorders” as relations generating linear preorders on X and in “Sincov Functional Equation” by the use of Sincov-like functional equations (Propositions 5.6 and 5.7). Also, the relation between T-preorders and reciprocal matrices (Saaty 1980) will allow us to find a one-dimensional T-preorder close to a given one, as explained in “Approximating T-Preorders by One-Dimensional Preorders.”

A strong complete T-preorder P on a set X is a T-preorder satisfying that for , either or . These are interesting fuzzy relations used in fuzzy preference structures (Fodor and Roubens 1994). It is a direct consequence of Lemma 2.6 (in the following section) that one-dimensional T-preorders are strong complete, but there are strong complete T-preorders that are not one-dimensional. In “Strong Complete T-Preorders,” strong complete T-preorders are characterized using the representation theorem (Propositions 7.4 and 7.5).

The last section of the paper contains some concluding remarks and an interesting open problem: Which conditions must a couple of fuzzy subsets and fulfill in order to exist as a t-norm T with ? Also, the possibility of defining two dimensions (right and left) is discussed.

A section of preliminaries with the results and definitions used throughout the rest of the article follows.

PRELIMINARIES

This section contains the main definitions and properties that are related mainly to T-preorders and that will be used throughout the rest of this article.

Definition 2.1

(Zadeh 1971) Let T be a t-norm. A fuzzy T-preorder P on a set X is a fuzzy relation P : satisfying for all

• 2.1.1. (Reflexivity)

• 2.1.2. (T-transitivity).

Definition 2.2

The inverse or dual of a fuzzy relation R on a set X is the fuzzy relation on X defined for all by

Proposition 2.3

A fuzzy relation R on a set X is a T-preorder on X if and only if is a T-preorder on X.

Definition 2.4

The residuation of a t-norm T is defined for all by

Example 2.5

1. If T is a continuous Archimedean t-norm with additive generator t, then for all .

   As special cases,

   • If T is the Łukasiewicz t-norm, then for all .

   • If T is the product t-norm, then for all .

2. If T is the minimum t-norm, then

Lemma 2.6

Let μ be a fuzzy subset of X and T be a t-norm. The fuzzy relation on X is defined for all by

is a T-preorder on X.

Theorem 2.7

Representation Theorem (Valverde 1985). A fuzzy relation R on a set X is a T-preorder on X if and only if there exists a family of fuzzy subsets of X such that for all

Definition 2.8

A family in Theorem 2.7 is called a g of R and an element of a generating family is called a generator of R. The minimum of the cardinalities of such families is called the dimension of R (dimR) and a family with this cardinality is a basis of R.

A generating family can be viewed as the degrees of accuracy of the elements of X to a family of prototypes. A family of prototypes with low cardinality, especially a basis, simplifies the computations and gives clarity to the structure of X.

The next proposition states a trivial but important result.

Proposition 2.9

is a generator of R if and only if .

Definition 2.10

Two continuous t-norms T, T′ are isomorphic if and only if there exists a bijective map such that .

It is well known that all strict continuous Archimedean t-norms T are isomorphic. In particular, they are isomorphic to the product t-norm and .

Also, all non strict continuous Archimedean t-norms T are isomorphic. In particular, they are isomorphic to the Łukasiewicz t-norm and .

Proposition 2.11

If T, T′ are two isomorphic t-norms, then their residuations also are isomorphic (i.e., there exists a bijective map such that ).

GENERATORS OF ONE-DIMENSIONAL T-PREORDERS

Let us recall that according to Definition 2.8 a T-preorder P on X is one-dimensional if and only if there exists a fuzzy subset of X such that for all .

For a one-dimensional T-preorder P, it is interesting to find all fuzzy subsets that are a basis of P (i.e., ). The next two propositions answer this question for continuous Archimedean t-norms and for the minimum t-norm.

Proposition 3.1

Let T be a continuous Archimedean t-norm, t an additive generator of T, and fuzzy subsets of X; if and only if the following condition holds:

Moreover, if T is non strict, then .

Proof

If , then

where is replaced by because all the values in brackets are between 0 and t(0).

If , then

Let us fix . Then

and

Trivial thanks to Example 2.5.1.□

Example 3.2

With the previous notations,

• If T is the Łukasiewicz t-norm, then

• If T is the product t-norm, then

Proposition 3.3

Let T be the minimum t-norm, μ a fuzzy subset of X, and x_M an element of X with . Let be the set of elements x of X with and . A fuzzy subset ν of X generates the same T-preorder than μ if and only if

Proof

It follows easily from the fact that

□

At this point, it seems that the dimension of P and of should coincide, but this is not true in general, as we will show in the next example. Nevertheless, continuous Archimedean t-norms do coincide in most of the cases, as will be proved in Proposition 3.5.

Example 3.4

Consider the one-dimensional min-preorder P of generated by the fuzzy subset . Its matrix is

whereas the matrix of is

which clearly is not one-dimensional.

Proposition 3.5

Let T be a continuous Archimedean t-norm, t an additive generator of T, μ a fuzzy subset of X and P_μ the T-preorder generated by μ. Then is generated by the fuzzy subset ν of X such that .

Proof

□

Example 3.6

• If T is the t-norm of Łukasiewicz, μ a fuzzy subset of X, and P the T-preorder on X generated by μ (i.e., ), then is generated by , with .

• If T is the product t-norm, μ a fuzzy subset of X such that and P the T-preorder on X generated by μ (i.e., ), then is generated by , with .

Hence, the dimensions of a T-preorder P and its inverse coincide when T is the t-norm of Łukasiewicz (and any other continuous non strict Archimedean t-norm), whereas the product t-norm (and any other continuous strict t-norm) coincide when .

A CHARACTERIZATION OF ONE-DIMENSIONAL T-PREORDERS

For a continuous Archimedean t-norm, a one-dimensional T-preorder P on a set X is characterized by the fact that it generates a linear ordering on X such that if , then equality holds in 2.1.2. (i.e., .

Proposition 4.1

Let T be a continuous Archimedean t-norm and P a T-preorder on X such that for all . P is one-dimensional if and only if there exists a total order on X with first element a and last element b such that if , then .

Proof

Let μ be a fuzzy set of X generating P (i.e., ). Consider a total order on X such that if , then .

If , then

Consider the fuzzy subset μ_a of X defined for all by .

If , then

Hence,

and μ_a is a generator of P.□

SINCOV FUNCTIONAL EQUATION

For continuous Archimedean t-norms, one-dimensionality is related to the fulfillment of the equation constrained to the condition . The resemblance of this equation to the functional equation of Definition 5.1 will allow us to provide a new characterization of one-dimensional T-preorders relating them to Sincov-like functional equations (Propositions 5.6 and 5.7). In the next section, this characterization will be used to approximate a given T-preorder by a one-dimensional one.

Definition 5.1

(Castillo-Ron and Ruiz-Cobo 1992.) A mapping satisfies the Sincov functional equation if and only if for all we have

The following result characterizes the mappings satisfying the Sincov equation.

Proposition 5.2

(Castillo-Ron and Ruiz-Cobo 1992.) A mapping satisfies the Sincov functional equation if and only if there exists a mapping such that

for all .

Proposition 5.3

The real line with the operation * defined by for all is an Abelian group with 1 as the identity element. The opposite of x is .

Replacing the addition by this operation *, we obtain a Sincov-like functional equation:

Proposition 5.4

Let be a mapping. F satisfies the functional equation

(1)

if and only if there exists a mapping such that

for all .

Proof

The mapping satisfies the Sincov functional equation and so .

Replacing the addition with multiplication, we obtain another Sincov-like functional equation:

Proposition 5.5

Let be a mapping. F satisfies the functional equation

(2)

if and only if there exists a mapping such that

for all .

Proof

Simply calculate the logarithm of both sides of the functional equation to transform it to a Sincov functional equation.

If μ is a fuzzy subset of X, we can consider μ as a mapping from X to or to . This will allow us to characterize one-dimensional T-preorders on X when T is the Łukasiewicz or the product t-norm.

Proposition 5.6

Let T be the Łukasiewicz t-norm and P be a T-preorder on X. Consider defined by

F satisfies Equation (1) if and only if P is a one-dimensional T-preorder on X.

Proposition 5.7

Let T be the product t-norm and P be a T-preorder on X. Consider defined by

F satisfies Equation (2) if and only if P is a one-dimensional T-preorder on X.

Due to the isomorphisms of continuous Archimedean t-norms to the Łukasiewicz and product t-norms, the previous results allow us to characterize one-dimensional T-preorders for any continuous Archimedean t-norm.

APPROXIMATING T-PREORDERS BY ONE-DIMENSIONAL ONES

Consider the cases in which different sensors give values to a phenomenon (e.g., the temperature of a room during a day). Due to inaccuracy of the sensors, rounding, and noise, the preordrers generated by the data of the different sensors will not coincide, and if we aggregate them, a T-preorder that is not one-dimensional will be obtained. In this situation, the obtained T-preorder should be replaced by a one-dimensional one close to it.

The Product T-Norm Case

In this subsection we will tackle this problem using ideas from Saaty (1980) for the product t-norm. The definition of reciprocal and consistent matrix will be recalled and related to the previous section. Then the eigenvalues method developed by Saaty (1980) and the logarithmic least squares method (LLSM; Crawford and Williams 1985) will be used to approximate a given T-preorder (in fact any reflexive fuzzy relation) by a one-dimensional T-preorder.

Definition 6.1

(Saaty 1980) An real matrix A with entries is reciprocal if and only if . A reciprocal matrix is consistent if and only if .

If the cardinality of X is finite (i.e., ), then we can associate the matrix with entries with every map . Then F satisfies Equation (2) if and only if A is a reciprocal consistent matrix as defined in Saaty (1980).

Proposition 5.5 can be rewritten in this context by

Proposition 6.2

(Saaty 1980) An real matrix A is reciprocal and consistent if and only if there exists a mapping g of X such that

For a given reciprocal matrix A, Saaty obtains a consistent matrix A′ close to A (Saaty 1980). A′ is generated by an eigenvector associated with the greatest eigenvalue of A (i.e., a mapping g satisfying the previous Proposition 6.2) and fulfills the following properties.

1. If A is already consistent, then .

2. If A is a reciprocal positive matrix, then the sum of its eigenvalues is n.

3. If A is consistent, then there exist a unique eigenvalue different from zero.

4. Slight modifications of the entries of A produce slight changes to the entries of A′.

We can associate a reciprocal matrix with a T-preorder as in Proposition 5.7.

Definition 6.3

(Saaty 1980) The reciprocal matrix associated with a T-preorder is defined by

Then in order to obtain a one-dimensional T-preorder P′ close to a given one P (T is the product t-norm), the following procedure can be used:

• Calculate the consistent reciprocal matrix A associated with P.

• Find an eigenvector v of the greatest eigenvalue of A.

• Divide the coordinates of v by the greatest one to obtain a fuzzy subset μ.

• .

Example 6.4

Let T be the product t-norm and P the T-preorder on a set X of cardinality 5 given by the following matrix.

Its associated reciprocal matrix A is

Its greatest eigenvalue is 5.0003 and an eigenvector for 5.0003 is

This fuzzy set generates , which is a one dimensional T-preorder close to P.

The second most popular method to approximate a reciprocal matrix by a reciprocal and consistent matrix is the LLSM that will be recalled below and used as an alternative method to approximate a T-preorder by a one-dimensional one.

Definition 6.5

For a given reciprocal matrix , the LLSM obtains a vector of positive coordinates generating a reciprocal and consistent matrix close to A by minimizing the function

subject to the condition

Proposition 6.6

(Crawford and Williams 1985) The solution of the LLSM is given by

So, the different w_i are the geometric mean of the entries of the ith file of A.

From this result, the following alternative method to approximate a reflexive fuzzy relation P by a one-dimensional T-preorder can be obtained.

• Calculate the consistent reciprocal matrix A associated with P.

• Find the vector w from A using the LLSM.

• Divide the coordinates of w by its greatest coordinate to obtain a vector μ with values between 0 and 1 (i.e., a fuzzy subset).

• .

Example 6.7

Consider the same T-preorder P as in Example 6.4.

The vector w is and dividing the coordinates of w by 1.58 we obtain

The obtained one-dimensional T-preorder coincides with the one obtained in Example 6.4.

The results of this subsection can be easily generalized to continuous strict Archimedean t-norms.

If T′ is a continuous strict Archimedean t-norm, then it is isomorphic to the product t-norm T. Let be this isomorphism. If P is a T′-preorder, then is a T-preorder. We can find P′ one-dimensional close to as before. Since isomorphisms between continuous t-norms are continuous and preserve dimensions, is a one-dimensional T′-preorder close to P.

The Łukasiewicz T-Norm Case

In this subsection we will modify the last method in order to obtain a one-dimensional T-preorder close to a given reflexive fuzzy relation P when T is the Łukasiewicz t-norm. For that, instead of generating a reciprocal matrix associated with P, we will generate the same matrix F of Proposition 5.6 and minimize a function of F. This procedure will be called the Łukasiewicz Least Squares Method (ŁLSM).

Definition 6.8

Given a matrix , the Łukasiewicz Least Squares Method obtains a vector generating a matrix with close to A by minimizing the function

subject to the condition

Proposition 6.9

The solution of the Łukasiewicz Least Squares Method is given by

Proof

Imposing the gradient of to be 0, we obtain

Considering the condition we obtain the desired result.□

From this last result we can give a method to obtain a one-dimensional T-preorder P′ close to a given reflexive fuzzy relation.

• Calculate the associated matrix A associated with P as in Proposition 5.6.

• Find the vector w from A using the ŁLSM.

• Subtract the smallest coordinate w from all the coordinates of w to obtain a vector μ with values between 0 and 1 (i.e., a fuzzy subset).

• .

Example 6.10

Let T be the Łukasiewicz t-norm and P the T-preorder on a set X of cardinality 5 given by the following matrix.

Its associated matrix A is

The vector w is . Subtracting 0.54 from the coordinates of w we get and is

Again, due to the isomorphisms between continuous Archimedean non strict t-norms and the Łukasiewicz t-norm, the results of this subsection allow us to approximate reflexive fuzzy relations by one-dimensional T-preorders when T is continuous Archimedean non strict.

STRONG COMPLETE T-PREORDERS

Definition 7.1

(Fodor and Roubens 1994) A T-preorder P on a set X is a strong complete T-preorder if and only if for all x, ,

Of course, every one-dimensional fuzzy T-preorder is a strong complete T-preorder, but there are strong complete T-preorders that are not one-dimensional. In Propositions 7.3 and 7.5 these fuzzy relations will be characterized, exploiting the fact that they generate crisp linear orderings.

Lemma 7.2

Let μ be a generator of a strong complete T-preorder P on X. If , then .

Proof

Trivial, because □

Proposition 7.3

Let μ, ν be two generators of a strong complete T-preorder P on X. Then for all if and only if .

Proof

Given , let us suppose that . Then and .□

Proposition 7.4

Let P be a strong complete T-preorder on a set X. The elements of X can be totally ordered in such a way that if , then .

Proof

Consider the relation on X defined by if and only if for any generator μ of P. (If for , for any generator, then choose either or ).□

Reciprocally,

Proposition 7.5

If for any couple of generators μ and ν of a T-preorder P on a set X if and only if , then P is strong complete.

Proof

Trivial.□

CONCLUDING REMARKS

T-preorders have been studied with the help of the representation theorem. The different fuzzy subsets generating the same T-preorder have been characterized and the relationship between one-dimensional T-preorders, Sincov-like functional equations, and Saaty’s (1980) reciprocal matrices has been studied. Also, strong complete T-preorders have been characterized.

We point out two directions toward a future work.

• We can look at the results of “Generators of One-Dimensional T-Preorders” from a different point of view: Let us suppose that we obtain two different fuzzy subsets μ and ν of a universe X by two different measurements or by two different experts. It would be interesting to know in which conditions we could assure the existence of a (continuous Archimedean) t-norm for which .

• A fuzzy subset μ of a set X generates a T-preorder P_μ by , but also another T-preorder (in fact, the inverse of P_μ). In this way, we could define two dimensions of a T-preorder according to whether we consider it generated by families or by families . For instance, the min-preorder of Example 3.4 would have right dimension 1 and left dimension 2.