http://horos.rdsor.ro/ijcccv3n4Draft.pdf


Int. J. of Computers, Communications & Control, ISSN 1841-9836, E-ISSN 1841-9844

Vol. III (2008), No. 4, pp. 336-342

Fuzzy Szpilrajn Theorem through Indicators

Irina Georgescu

Abstract: In this paper there are studied some numerical indicators which measure
the degree to which a fuzzy relation verifies some properties (reflexivity, transitivity,
etc. ).The main result is a fuzzy generalization of the Szpilrajn theorem in terms of
such numerical indicators and is applied to any fuzzy relation.
Keywords: fuzzy relation, Szpilrajn theorem, similarity

1 Introduction

The classical Szpilrajn theorem [10] asserts that any partial order can be extended to a total order.
This result has been followed by refinements and generalizations and has been used in applications too
(e. g. consumer theory [8]).

The first fuzzy version of the Szpilrajn theorem has been established by Zadeh [11]. Other fuzzy ver-
sions of this theorem can be found in [4], [6]. In [3] the topic is systematically studied in the framework
of the fuzzy orders with respect to a left–continuous t–norm ∗ and a ∗–similarity relation Ω.

The idea of this paper is the following: instead of studying a property P of a fuzzy relation R (e. g.
reflexivity, transitivity, etc.) to define numerical indicators which should express "the degree to which
the fuzzy relation R verifies the property P". In this way, instead of considering a fuzzy order R on a set
X we will have a number Ord(R) which should measure "the degree to which R is a fuzzy order".

The main result of the paper is a generalization of the Szpilrajn theorem expressed in terms of such
numerical indicators. It is a refinement of Theorem 6.2 in [3] and it is applied to any fuzzy relation.

2 Preliminaries

In this section we shall recall some basic facts on the residuum associated with a left–continuous
t–norm and on fuzzy relations ([1], [2], [4], [5], [7], [9]).

For any a, b ∈ [0,1] we denote a ∨ b = max(a, b) and a ∧ b = min(a, b). More generally, for any set
{ai}i∈I ⊆ [0,1] we denote

∨

i∈I
ai = sup{ai|i ∈ I} and

∧

i∈I
ai = inf{ai|i ∈ I}.

Let ∗ be a left–continuous t–norm [7], [5]. The residuum → associated with ∗ is introduced by
a → b =

∨

{c ∈ [0,1]|a ∗ c ≤ b}.
The biresiduum ↔ is denoted by a ↔ b = (a → b) ∧ (b → a).
We fix a left–continuous t–norm ∗.

Lemma 1. [1], [5] For any a, b, c ∈ [0,1] the following properties hold:

(1) a ∗ b ≤ c iff a ≤ b → c;

(2) a ∧ b = a ∗ (a → b);

(3) a ≤ b iff a → b = 1;

(4) a = 1 → a;

(5) 1 = a → a;

(6) a ≤ a ∗ (a ↔ b).

Copyright © 2006-2008 by CCC Publications



Fuzzy Szpilrajn Theorem through Indicators 337

Lemma 2. [1], [5] For any {ai}i∈I ⊆ [0,1] and a ∈ [0,1] the following properties hold:

(1) (
∨

i∈I
ai) ∗ a =

∨

i∈I
(ai ∗ a);

(2) a → (
∧

i∈I
ai) =

∧

i∈I
(a → ai);

(3) (
∨

i∈I
ai) → a =

∧

i∈I
(ai → a).

Let X be a non–empty subset. A fuzzy subset of X is a function A : X → [0,1]. Denote by F(X ) the
family of the fuzzy subsets of X. For any A, B ∈ F(X ) denote A ⊆ B if A(x) ≤ B(x) for any x ∈ X.

A fuzzy relation on X is a function R : X 2 → [0,1]. R is said to be
• reflexive if R(x, x) = 1 for any x ∈ X;
• symmetric if R(x, y) = R(y, x) for any x, y ∈ X;
• ∗–transitive if R(x, y) ∗ R(y, z) ≤ R(x, z) for all x, y, z ∈ X;
• strongly complete if R(x, y) ∨ R(y, x) = 1 for any x, y ∈ X.
A reflexive, symmetric and ∗–transitive fuzzy relation Ω on X will be called ∗–similarity relation.
Let Ω be a ∗–similarity relation on X and R a fuzzy relation on X. R is said to be:
• Ω–reflexive if Ω(x, y) ≤ R(x, y) for any x, y ∈ X;
• (∗, Ω)–antisymmetric if R(x, y) ∗ R(y, x) ≤ Ω(x, y) for any x, y ∈ X.
A (∗, Ω)–order is ∗–transitive, Ω–reflexive and (∗, Ω)–antisymmetric fuzzy relation R on X. Let R, Q

be two (∗, Ω)–orders on X. We say that Q is an extension of R if R ⊆ Q, i. e. R(x, y) ≤ Q(x, y) for all
x, y ∈ X.

The following fuzzy generalization of the Szpilrajn theorem was proved in [3]:

Theorem 3. Let Ω be a ∗–similarity relation on X . Then any (∗, Ω)–order on X has a strongly complete
extension.

3 Some indicators

Let ∗ be a left–continuous t–norm and Ω be a ∗–similarity relation on X.

Definition 4. For any fuzzy relation R on X let us define:
Re f (R) =

∧

x∈X
R(x, x);

Trans(R) =
∧

x,y,z∈X
[R(x, y) ∗ R(y, z) → R(x, z)];

Re fΩ(R) =
∧

x,y∈X
(Ω(x, y) → R(x, y)];

AntΩ(R) =
∧

x,y∈X
[R(x, y) ∗ R(y, x) → Ω(x, y)];

SC(R) =
∧

x,y∈X
(R(x, y) ∨ R(y, x));

OrdΩ(R) = Re fΩ(R) ∧ AntΩ(R) ∧ Trans(R).

Lemma 5. For any fuzzy relation R the following equivalences hold:

(1) Re f (R) = 1 iff R is reflexive;

(2) Trans(R) = 1 iff R is ∗–reflexive;



338 Irina Georgescu

(3) Re fΩ(R) = 1 iff R is Ω–reflexive;

(4) AntΩ(R) = 1 iff R is (∗, Ω)–antisymmetric;

(5) SC(R) = 1 iff R is strongly complete;

(6) OrdΩ(R) = 1 iff R is a (∗, Ω)–order.

Re f (R) will be called the degree of reflexivity of R, Trans(R) the degree of ∗–transitivity of R, etc.
The indicators introduced above refine the properties of reflexivity, transitivity, etc. of fuzzy relations.
Thus, instead of saying that the fuzzy relation R is reflexive, the real number Re f (R) will measure "the
degree to which R is reflexive".

Proposition 6. Let R be a fuzzy relation on X and x, y, z ∈ X . Then

(1) Re f (R) ≤ R(x, x);

(2) Trans(R) ∗ R(x, y) ∗ R(y, z) ≤ R(x, z);

(3) Re fΩ(R) ∗ Ω(x, y) ≤ R(x, y);

(4) AntΩ(R) ∗ R(x, y) ∗ R(y, x) ≤ Ω(x, y);

(5) OrdΩ(R) ≤ Ω(x, y) ↔ (R(x, y) ∗ R(y, x));

(6) OrdΩ(R) ≤ R(x, x).

4 Main result

In this section we shall prove a generalization of the theorem of Szpilrajn formulated in terms of the
indicators introduced in the previous paragraph. The result will be valid for any fuzzy relations and in
particular one will obtain Theorem 3.

Let ∗ be a left–continuous t–norm and Ω a ∗–similarity relation on X. If R and Q are two fuzzy
relations on X then we denote

R 4 Q iff R ⊆ Q and OrdΩ(R) ≤ OrdΩ(Q).
It is easy to see that 4 is a partial order on the set of the fuzzy relations defined on X. If Q is a fuzzy

relation on X then we denote by Ext(Q) the set of all fuzzy relations R on X with the property that Q 4 R.

Lemma 7. If Q is a fuzzy relation on X then the partially ordered set (Ext(Q), 4) admits a maximal
element.

Proof. We prove that (Ext(Q), 4) is inductive. We consider a chain (Ri)i∈I in Ext(Q): for any i, j ∈ I
we have Ri 4 R j or R j 4 Ri. Of course Q 4 Ri for any i ∈ I. We will denote R =

⋃

i∈I
Ri. It suffices to

prove that R ∈ Ext(Q). It is obvious that Q ⊆ R therefore we have to prove that OrdΩ(Q) ≤ OrdΩ(R).
We show first that

(a) OrdΩ(Q) ≤ Re fΩ(R).
Let x, y ∈ X and i ∈ I. Since Q ⊆ Ri it follows immediately
OrdΩ(Q) ≤ Re fΩ(Q) ≤ Re fΩ(Ri) ≤ Ω(x, y) → Ri(x, y).
By applying Lemma 1 (2) and the previous inequality
OrdΩ(Q) ∗ Ω(x, y) ≤ Ω(x, y) ∗ (Ω(x, y) → Ri(x, y)) =
= Ω(x, y) ∧ Ri(x, y) ≤ Ri(x, y) ≤ R(x, y)
from where according to Lemma 1 (1), OrdΩ(Q) ≤ Ω(x, y) → R(x, y). It follows



Fuzzy Szpilrajn Theorem through Indicators 339

OrdΩ(Q) ≤
∧

x,y∈X
(Ω(x, y) → R(x, y)) = Re fΩ(R).

We intend to prove that
(b) OrdΩ(Q) ≤ AntΩ(R)
Let x, y ∈ X. Then
OrdΩ(Q) ∗ R(x, y) ∗ R(y, x) = OrdΩ(Q) ∗ [

∨

i∈I
Ri(x, y)] ∗ [

∨

j∈I
R j(y, x)] =

=
∨

i, j∈I
OrdΩ(Q) ∗ Ri(x, y) ∗ R j(y, x).

Let i, j ∈ I. Assume that Ri 4 R j therefore Ri ⊆ R j and OrdΩ(Ri) ≤ OrdΩ(R j). Then, according to
Q 4 R j and Proposition 6 (4):

OrdΩ(Q) ∗ Ri(x, y) ∗ R j(y, x) ≤ OrdΩ(R j) ∗ R j(x, y) ∗ R j(y, x) ≤
≤ AntΩ(R j) ∗ R j(x, y) ∗ R j(y, x) ≤ Ω(x, y).
Since this inequality is valid for any i, j ∈ I it follows OrdΩ(Q)∗ R(x, y)∗ R(y, x) ≤ Ω(x, y), therefore,

according to Lemma 1 (1), OrdΩ(Q) ≤ R(x, y) ∗ R(y, x) → Ω(x, y). From here we deduce
OrdΩ(Q) ≤

∧

x,y∈X
[R(x, y) ∗ R(y, x) → Ω(x, y)] = AntΩ(R).

We still have to prove
(c) OrdΩ(Q) ≤ Trans(R).
Let x, y ∈ X. Then
OrdΩ(Q) ∗ R(x, y) ∗ R(y, z) =

∨

i, j∈I
OrdΩ(Q) ∗ Ri(x, y) ∗ R j(y, x)

Let i, j ∈ I. Assume Ri 4 R j therefore Ri ⊆ R j and OrdΩ(Ri) ≤ OrdΩ(R j). According to Proposition
6 (2):

OrdΩ(Q) ∗ Ri(x, y) ∗ R j(y, z) ≤ OrdΩ(R j) ∗ R j(x, y) ∗ R j(y, z) ≤
≤ Trans(R j) ∗ R j(x, y) ∗ R j(y, z) ≤ R j(x, z) ≤ R(x, z)
from where, OrdΩ(Q) ∗ R(x, y) ∗ R(y, z) ≤ R(x, z). By applying Lemma 1 (1) it follows that for any

x, y, z ∈ X we have OrdΩ(Q) ≤ R(x, y) ∗ R(y, z) → R(x, z), from where
OrdΩ(Q) ≤

∧

x,y,z∈X
[R(x, y) ∗ R(y, z) → R(x, z)] = Trans(R).

From (a), (b) and (c) one obtains OrdΩ(Q) ≤ OrdΩ(R). We have shown that (Ext(Q), 4) is inductive.
According to Zorn’s axiom a maximal element exists in Ext(Q).

In the following we will situate ourselves in the case of the Gödel t–norm ∧.

Theorem 8. Let Q be a fuzzy relation on X . Then there exists a fuzzy relation R on X such that Q 4 R
and OrdΩ(Q) ≤ SC(R).

Proof. According to Lemma 7 there exists a fuzzy relation R on X maximal in (Ext(Q), 4). Then Q 4 R.
It remains to prove that OrdΩ(Q) ≤ SC(R). We assume by absurdum that

OrdΩ(Q) 6≤ SC(R) =
∧

x,y∈X
(R(x, y) ∨ R(y, x)).

therefore there exist a, b ∈ X such that OrdΩ(Q) 6≤ R(a, b) ∨ R(b, a) from where OrdΩ(Q) 6≤ R(a, b)
and OrdΩ(Q) 6≤ R(b, a). Assume R(a, b) ≤ R(b, a). According to the lines above, R(b, a) < OrdΩ(Q).
We define a new fuzzy relation R′ on X by

R′(x, y) = R(x, y) ∨ (R(x, b) ∧ R(a, y))
for any x, y ∈ X. We intend to prove that R 4 R′. It is obvious that R ⊆ R′ therefore it remains to

prove that OrdΩ(R) ≤ OrdΩ(R′). From R ⊆ R′ it follows immediately
(1) OrdΩ(R) ≤ Re fΩ(R′)
We establish now the inequality:
(2) OrdΩ(R) ≤ AntΩ(R′)
Let x, y ∈ X. Then



340 Irina Georgescu

OrdΩ(R) ∧ R′(x, y) ∧ R′(y, x) =
= OrdΩ(R) ∧ [R(x, y) ∨ (R(x, b) ∧ R(a, y))] ∧ [R(y, x) ∨ (R(y, b) ∧ R(a, x))] =
= [OrdΩ(R) ∧ R(x, y) ∧ R(y, x)] ∨ [OrdΩ(R) ∧ R(x, y) ∧ R(y, b) ∧ R(a, x)]∨
∨[OrdΩ(R) ∧ R(y, x) ∧ R(x, b) ∧ R(a, y)] ∨ [OrdΩ(R) ∧ R(x, b) ∧ R(a, y) ∧ R(y, b) ∧ R(a, x)]
We will establish the following inequalities:
(a) OrdΩ(R) ∧ R(x, y) ∧ R(y, x) ≤ Ω(x, y);
(b) OrdΩ(R) ∧ R(x, y) ∧ R(y, b) ∧ R(a, x) ≤ Ω(x, y);
(c) OrdΩ(R) ∧ R(y, x) ∧ R(x, b) ∧ R(a, y) ≤ Ω(x, y);
(d) OrdΩ(R) ∧ R(x, b) ∧ R(a, y) ∧ R(y, b) ∧ R(a, x) ≤ Ω(x, y).
In order to obtain (a) we use Proposition 6 (4):
OrdΩ(R) ∧ R(x, y) ∧ R(y, x) ≤ AntΩ(R) ∧ R(x, y) ∧ R(y, x) ≤ Ω(a, b).
We treat now the other three cases. According to Proposition 6 (5) we have
OrdΩ(R) ≤ Ω(a, b) ↔ (R(a, b) ∧ R(b, a)) = Ω(a, b) ↔ R(a, b)
We consider first the case R(x, y) ≤ R(y, x). Then OrdΩ(R) ≤ Ω(x, y) ↔ R(x, y) with the same argu-

ment as above. (b) results like this:
OrdΩ(R) ∧ R(x, y) ∧ R(y, b) ∧ R(a, x) ≤ R(x, y) ∧ [Ω(x, y) ↔ R(x, y)] ≤ Ω(x, y)
Now we treat cases (c) and (d). First we notice that according to Proposition 6 (2):
OrdΩ(R) ∧ R(y, x) ∧ R(x, b) ∧ R(a, y) ≤ Trans(R) ∧ R(a, y) ∧ R(y, x) ∧ R(x, b) ≤ R(a, b)
therefore
OrdΩ(R) ∧ R(y, x) ∧ R(a, y) ≤ R(a, b) ∧ [R(a, b) ↔ Ω(a, b)] ≤ Ω(a, b).
Analogously we obtain:
OrdΩ(R) ∧ R(x, b) ∧ R(a, y) ∧ R(y, b) ∧ R(a, x) ≤ Ω(a, b).
We consider the possible subcases:
(i) Ω(a, b) ≤ R(x, y);
(ii) Ω(a, b) > R(x, y).
According to the proof above, in case (i) the inequalities (c) and (d) are immediate. We are situated

now in case (ii). One notices that
OrdΩ(R) ∧ R(x, b) ∧ Ω(a, b) ∧ R(a, y) ≤ Ω(a, b) ∧ [Ω(a, b) ↔ R(a, b)] ≤ R(a, b) ≤ R(b, a)
therefore
OrdΩ(R) ∧ R(x, b) ∧ Ω(a, b) ∧ R(a, y) ≤ OrdΩ(R) ∧ R(x, b) ∧ R(b, a) ∧ R(a, y) ≤ Trans(R) ∧ R(x, b) ∧

R(b, a) ∧ R(a, y) ≤ R(x, y)
From OrdΩ(R) ∧ R(x, b) ∧ Ω(a, b) ∧ R(a, y) ≤ R(x, y) and Ω(a, b) > R(x, y) it follows
OrdΩ(R) ∧ R(x, b) ∧ R(a, y) ≤ R(x, y).
By using this last inequality we have
OrdΩ(R) ∧ R(y, x) ∧ R(x, b) ∧ R(a, y) ≤ OrdΩ(R) ∧ R(x, b) ∧ R(a, y) ≤ R(x, y)
from where
OrdΩ(R) ∧ R(y, x) ∧ R(x, b) ∧ R(a, y) ≤ R(x, y) ∧ [R(x, y) ↔ Ω(x, y)] ≤ Ω(x, y)
Thus (c) was proved and (d) follows analogously.
The case R(y, x) ≤ R(x, y) is treated analogously. Therefore the inequalities (a)–(d) are true, so

OrdΩ(R) ∧ R′(x, y) ∧ R′(y, x) ≤ Ω(x, y). Cf. Lemma 1 (1) for any x, y, z ∈ X we have OrdΩ(R) ≤
(R′(x, y) ∧ R′(y, x)) → Ω(x, y) therefore

OrdΩ(R) ≤
∧

x,y∈X
[(R′(x, y) ∧ R′(y, x)) → Ω(x, y)] = AntΩ(R′)

Now we establish the inequality
(3) OrdΩ(R) ≤ Trans(R′).
Let x, y, z ∈ X. We prove
(4) OrdΩ(R) ∧ R′(x, y) ∧ R′(y, z) ≤ R′(x, z).
We notice that
OrdΩ(R) ∧ R′(x, y) ∧ R′(y, z) =



Fuzzy Szpilrajn Theorem through Indicators 341

= OrdΩ(R) ∧ [R(x, y) ∨ (R(x, b) ∧ R(a, y))] ∧ [R(y, z) ∨ (R(y, b) ∧ R(a, z))] =
= [OrdΩ(R) ∧ R(x, y) ∧ R(y, z)] ∨ [OrdΩ(R) ∧ R(x, y) ∧ R(y, b) ∧ R(a, z)]∨
∨[OrdΩ(R) ∧ R(y, z) ∧ R(x, b) ∧ R(a, y)] ∨ [OrdΩ(R) ∧ R(x, b) ∧ R(a, y) ∧ R(y, b) ∧ R(a, z)].
Then to prove (4) is equivalent with establishing the following inequalities:
(e) OrdΩ(R) ∧ R(x, y) ∧ R(y, z) ≤ R′(x, z);
(f) OrdΩ(R) ∧ R(x, y) ∧ R(y, b) ∧ R(a, z) ≤ R′(x, z);
(g) OrdΩ(R) ∧ R(y, z) ∧ R(x, b) ∧ R(a, y) ≤ R′(x, z);
(h) OrdΩ(R) ∧ R(x, b) ∧ R(a, y) ∧ R(y, b) ∧ R(a, z) ≤ R′(x, z).
(e) follows by applying Proposition 6 (2):
OrdΩ(R) ∧ R(x, y) ∧ R(y, z) ≤ Trans(R) ∧ R(x, y) ∧ R(y, z) ≤ R(x, z) ≤ R′(x, z).
(f) and (g) follow like this:
OrdΩ(R) ∧ R(x, y) ∧ R(y, b) ∧ R(a, z) ≤ (Trans(R) ∧ R(x, y) ∧ R(y, b)) ∧ R(a, z) ≤ R(x, b) ∧ R(a, z) ≤

R′(x, z);
OrdΩ(R) ∧ R(y, z) ∧ R(x, b) ∧ R(a, y) ≤ (Trans(R) ∧ R(a, y) ∧ R(y, z)) ∧ R(x, b) ≤ R(x, b) ∧ R(a, z) ≤

R′(x, z).
(h) follows similarly. We established (e)–(h), therefore (4) is true. Cf. Lemma 1 (1) for any x, y, z ∈ X

we have OrdΩ(R) ≤ (R′(x, y) ∧ R(y, z)) → R′(x, z), from where
OrdΩ(R) ≤

∧

x,y,z∈X
[(R′(x, y) ∧ R′(y, z)) → R′(x, z)] = Trans(R′)

From (1), (2) and (3) we deduce OrdΩ(R) ≤ OrdΩ(R′) therefore R 4 R′. We can see that
R′(a, b) = R(b, a) ∨ (R(b, b) ∧ R(a, a)) and R(b, a) < OrdΩ(Q) ≤ OrdΩ(R) (since Q 4 R). Then, by

applying Proposition 6 (6):
R(b, a) < OrdΩ(R) ≤ R(b, b) ∧ R(a, a) ≤ R′(a, b).
It follows R 6= R′, contradicting the maximality of R. We conclude OrdΩ(Q) ≤ SC(R), therefore the

theorem is proved.

Remark 9. By Applying Lemma 5 we see that Theorem 3 is a particular case of Theorem 8.

Bibliography

[1] R. Bělohlávek, Fuzzy Relational Systems. Foundations and Principles, Kluwer, 2002.

[2] U. Bodenhofer, Similarity–based Generalizations of Fuzzy Orderings Preserving the Classical Ax-
ioms, International Journal of Uncertainty, Fuzziness and Knowledge Based Systems, Vol. 3, pp.
593–610, 2000.

[3] U. Bodenhofer, F. Klawonn, A Formal Study of Linearity Axioms for Fuzzy Orderings, Fuzzy Sets
and Systems, Vol. 145, pp. 323–354, 2004.

[4] S. Gottwald, Fuzzy Sets and Fuzzy Logic, Vieweg, Braunschweig, 1993.

[5] P. Hájek, Methamathematics of Fuzzy Logic, Kluwer, 1998.

[6] U. Höhle, N. Blanchard, Partial Ordering in L–undeterminate sets, Information Sciences, Vol. 35,
pp. 135–144, 1985.

[7] E. P. Klement, R. Mesiar, E. Pap, Triangular Norms , Kluwer, 2000.

[8] M. Richter, Revealed Preference Theory, Econometrica, Vol. 34, pp. 635–645, 1966.

[9] I. J. Rudas, J. Fodor, Information Aggregation in Intelligent Systems using Generalized Operators,
International Journal of Computers, Communications and Control, Vol. 1, pp. 47–57, 2006.



342 Irina Georgescu

[10] E. Szpilrajn, Sur l’Extension de l’Ordre Partiel, Fundamenta Mathematicae, Vol. 16, pp. 386–389,
1930.

[11] L. A. Zadeh, Similarity Relations and Fuzzy Orderings, Information Sciences, Vol. 3, pp. 177–200,
1971.

Irina Georgescu
Academy of Economic Studies

Department of Economic Cybernetics
Piata Romana No 6, R 70167, Oficiul Postal 22

Bucharest, Romania
E-mail: irina.georgescu@csie.ase.ro

Irina Georgescu received her PhD in Economics (Information
Systems) from Abo Akademi University, Turku, Finland in 2005.
Since then she is a teaching assistant at the Department of Eco-
nomic Cybernetics, Academy of Economic Studies, Bucharest,
Romania. Between 2007–2008 she was a postdoctoral researcher
at Abo Akademi University, Turku, Finland. She is the author
of about 30 scientific publications and of a monograph issued by
Springer. Her research interests are mainly in the area of soft
computing techniques, consumer theory and social choice and
welfare economics.