3 Generators

In this section we study the structure and characterize the generators of a given T-indistinguishability relation E. A generator is defined in the following natural way:

will denote the set of all generators of E. It follows immediately from the representation theorem that, given a T-indistinguishability relation E on X, the set of fuzzy subsets of X is a generating family of E and will be denoted by . The next definition will play as important role in order to give a more convenient characterization of the generators of a T-indistinguishability relation E.

It is worth noting that if X is a finite set then E is represented by a matrix and may be understood as the max-T product of E by the column vector representing the fuzzy set h.

The elements and structure of the generators' set is determined in the following proposition.

Taking into account Definition 3.2, the next proposition follows immediately

If X is a finite set, the columns of the matrix associated to E are the images of the classical singletons and the image of a classical set is obtained as the supremum of elements of the set .

Next we study and characterize the T-indistinguishability relations generated by a single function h.

From now on, in order to simplify the proofs, only T-indistinguishability relations E such that if , will be considered. Anyway, if is the equivalence relation in X, if, and only if , then the induced T-indistinguishability relation on the quotient set satisfies the mentioned condition. Therefore, if E is generated by a function h, then h is injective.

In the sequel, it will also be assumed that has a maximum and a minimum in X. The point of X where these extrem values are reached will be denoted by i , that is:

Under this hypothesis, if E is generated by h, then

It follows from the properties of (Valverde, 1985) and then,

If E is generated by the function h, and with , then if T is an archimedean t- norm, both, and are generators of E.

If E is a similarity i.e. a T-indistinguishability relation with , then is a generator of E.

Remark: It can be proved that if E is a unidimensional T- indistinguishability relation generated by , T is Archimedean and Min, then and are the only generating columns.

The following theorem gives a characterization of the unidimensional T- indistinguishability relations that completes the results of (Ovchinnikov, 1984) for probabilistic relations.

Let E be a T-indistinguishability relation with T archimedean and t is additive generator such that for any .

For similarity relations the existence of an injective column is a suficient condition for unidimensionality, therefore:

The above results open the path in order to summarize in a minimal set of generators the information contained in such relations. On the other hand, the characterization of unidimensional relations, shows that these relations define a "betweeness" in the underlying set X, structured as a chain, giving a "geometrical" interpretation of the unidimensionality. Finally, the existing duality between T-indistinguishability relations and a type of generalized metrics, leads to the interesting problem of the study of the topological structures induced by these metrics.

Next, the problem of determining a minimal generating family for a similarity relation over a finite set X, is completely solved. This result may be an important tool in all algorithms dealing with similarity relations because all the information contained in the matrix representing the mentioned relation can be 'packed' in a few (even one!) fuzzy sets. As an application, two versions of an algorithm for the automatic search of one of such families are presented.

Let E be a similarity relation and , will denote the fuzzy set defined by

and the similarity generated by i.e.

It is immediate to prove that

In a similarity, there exists a close relation between the columns i.e. the fuzzy sets defined in (3.3), considered as generators and, the values of the similarity, as it is shown in the following

The representation theorem allows to introduce the concept of dimensionality of any T-indistinguishability relation generalizing the definition of (Ovchinnikov, 1984) for probabilistic relations.

Note, that this minimal cardinal always exists, since any set of cardinal numbers is a well-ordered set. In the following sections, it will be assumed that X is a finite set of cardinality n () and the fuzzy set defined by will be termed the column associated to .

In order to determine the dimension of a given similarity relation E, the following definitions will be needed:

The order of a similarity E () is the minimum of the orders of its maximal columns

Finally, if E is a similarity relation over a finite set and then Im. That is, the cardinality of the values' set of a similarity is bounded by the cardinality of the set where such relation is defined. Moreover, if is a generating family of a similarity relation E, there exists another family of generators with the same cardinality such that for any and , Im.

The next theorem gives an upper bound for the dimension of a similarity relation and allows to build an algorithm for the automatic search of minimal generating systems.

We present two versions of an algorithm, even though both are based on theorem 3.5, they basically differ in their efficiency and complexity. The first one always selects a minimal generating system, but presents higher difficulties than the second one in its implementation.

The second version, in some pathological cases, selects a generating system with one element more than the dimension of the similarity but it presents a more iterative structure and, therefore, enables an easier implementation. More details and examples about these algorithms can be found in (Jacas, 1987,1988)

Algorithm 1.

1. Compute the columns' orders and select the maximal ones.
2. Compute the similarity order and the upper bound of the dimension .
3. Select a maximal column whose order is the similarity order.
4. Build column vectors of dimension n and initialize them with 1's.
5. If is a unrepeated value in , do for any j. Do this assigment for all unrepeated values in .
6. Select a repeated value in and find its associated set .
7. For any pair of elements of , , such that , do , , .
8. For any element of not selected in the preceding step, do for some j, such that any pair of elements , included in this step there exists a j such that .
9. If there exists in another repeated value, select it and go to step 6.
10. If for two elements , with different repeated values , , for all j, select p such that and do .
11. Delete all constant columns.
12. End.

Algorithm 2.

1. Counter , .
2. Compute the columns orders and select the maximal one.
3. Compute the similarity order and calculate .
4. Select a maximal column whose order equals the similarity order.
5. Counter Counter+1 , .
6. If C=1, build columns of dimension N and initialize then with 1's and do
   for any x of X. Go to 6, otherwise.
7. Select a repeated value of and find the set associated to .
8. If , go to 13.
9. Select the similarity . Do , .
10. If order of E is n-1, go to 12.
11. Do for any x of X such that .
12. For any element x not being selected in 10, do for some j such that for any pair of elements , selected in this step there exists a j with and .
13. Select another repeated value and go to 4.
14. End.