Fuzzy relations and fuzzy mappings between fuzzy subsets

Mamoru Shimoda

                      mamoru-s@shimonoseki-cu.ac.jp

Shimonoseki City University

Introduction

In fuzzy literature, fuzzy relations and fuzzy mappings are usually treated as those between crisp sets. With our natural interpretation in a Heyting valued model for intuitionistic set theory, we are to define and study fuzzy relations and fuzzy mappings between fuzzy sets, especially between fuzzy subsets of crisp sets. By using membership functions we can characterize fuzzy relations, fuzzy mappings, and equivalence and order relations.

1 The Heyting valued model

Let H be a complete Heyting algebra with operations and constants ∧, ∨, ⋀, ⋁, →, ¬, 0, 1, and ≤. We construct an H-valued model for the extended intuitionistic set theory, which is a first order intuitionistic logic with predicates ∈, = and E (called an existence predicate) together with axioms of intuitionistic set theory. Let V be the class of all crisp sets and On be the class of all ordinals.

Definition 1.1. The H-valued model V^{H} is constructed as follows. For every ordinal α, V_{α}^{H} is defined by induction:

V_{0}^{H} = ϕ, V_{α}^{H} = ⋃_{β<α} V_{β}^{H} (if α is a limit ordinal),
V_{α+1}^{H} = { u = ⟨|u|, Eu⟩; |u| : 𝒟u⟶H, 𝒟u ⊆ V_{α}^{H}, Eu ∈ H, |u|(x) ≤ Eu ∧ Ex for all x ∈ 𝒟u}.

Then V^{H} = ⋃_{α∈On} V_{α}^{H}.

For a sentence φ of V^{H}, the Heyting value ∥φ∥ ∈ H is defined as follows.

Definition 1.2. Let u, v ∈ V^{H} and φ, ψ, φ(a) be formulas of V^{H}. For atomic formulae,

∥Eu∥ = Eu, and by simultaneous induction,

∥u ∈ v∥ = ⋁_{y∈𝒟v} (v(y) ∧ ∥u = y∥), and

∥u = v∥ = ⋀_{x∈𝒟u}(u(x)→∥x ∈ v∥) ∧ ⋀_{y∈𝒟v}(v(y)→∥y ∈ u∥) ∧ Eu ∧ Ev.

For compound formulae, by induction (on the number of logical symbols),

∥φ ∧ ψ∥ = ∥φ∥ ∧ ∥ψ∥,  ∥φ ∨ ψ∥ = ∥φ∥ ∨ ∥ψ∥,
∥φ → ψ∥ = ∥φ∥ → ∥ψ∥,  ∥¬φ∥ = ¬∥φ∥,
∥∀xφ(x)∥ = ⋀_{u∈V^{H}}(Eu → ∥φ(x)∥), and ∥∃xφ(x)∥ = ⋁_{u∈V^{H}}(Eu ∧ ∥φ(x)∥).

An element of the model is called a set in V^{H}. For a sentence φ of V^{H}, φ is valid in V^{H} if ∥φ∥ = 1. We say u is a subset of v in V^{H} (u ⊑ v) if ∥u ⊆ v∥ = ⋀_{x∈𝒟u} (u(x) → ∥x ∈ v∥) = 1. If u ⊑ v and v ⊑ u, we say u and v are similar (u ∼ v). If u ∼ v and Eu = Ev, u and v are said to be equivalent (u ≈ v). Definition 1.3. For every crisp set x in V, x̌ ∈ V^{H} is defined recursively by:

𝒟(x̌) = {y̌; y ∈ x}, Ex̌ = 1, x̌ : y̌ ⟼ 1.

We call x̌ the check set of x.

The canonical embedding which assigns to each crisp set its check set plays an important role in our interpretation. For a bounded formula φ(a_{1}, ⋯, a_{n}) and crisp sets x_{1}, ⋯, x_{n}, φ(x_{1}, ⋯, x_{n}) holds iff ∥φ(x̌_{1}, ⋯, x̌_{n})∥ = 1, and ¬φ(x_{1}, ⋯, x_{n}) holds iff ∥φ(x̌_{1}, ⋯, x̌_{n})∥ = 0. Definition 1.4. Let u, v ∈ V^{H}.

(1) 𝒟{u, v}^{H} = {u, v}, E{u, v}^{H} = Eu ∧ Ev, and {u, v}^{H} : x ⟼ 1.

(2) ⟨u, v⟩^{H} = {{u, u}^{H}, {u, v}^{H}}^{H}.

(3) 𝒟(u ×^{H} v)= {⟨x, y⟩^{H} ; x ∈ 𝒟u, y ∈ 𝒟v}, E(u ×^{H} v) = Eu ∧ Ev, and u ×^{H} v : ⟨x, y⟩^{H} ⟼ u(x) ∧ v(y).

(4) 𝒟(u ∩^{H} v) = 𝒟u ∪ 𝒟v, E(u ∩^{H} v) = Eu ∧ Ev, and u ∩^{H} v : x ⟼ ∥x ∈ u∥ ∧ ∥x ∈ v∥.

(5) 𝒟(u ∪^{H} v) = 𝒟u ∪ 𝒟v, E(u ∪^{H} v) = Eu ∨ Ev, and u ∪^{H} v : x ⟼ ∥x ∈ u∥ ∨ ∥x ∈ v∥.

(6) 𝒟(u\^{H} v) = 𝒟u ∪ 𝒟v, E(u\^{H} v) = Eu ∨ Ev, and u\^{H} v : x ⟼ ∥x ∈ u∥ ∧ ¬ ∥x ∈ v∥. The superscripts and commas may be omitted. We can also define power sets, infinite sums, and so

on. Hence all axioms of (extended) intuitionistic set theory are valid in V^{H}.

A relation in V^{H} is a subset of a cartesian product in V^{H}. For R, u, v ∈ V^{H}, R is a relation from u to v in V^{H} if R is a subset of u ×^{H} v in V^{H}. We often write xRy instead of ⟨xy⟩ ∈ R.

For each set u in V^{H}, the identity relation I_{u} on u is defined by:

𝒟(I_{u}) = {⟨xx⟩; x∈ 𝒟u}, E(I_{u}) = Eu, and I_{u}:⟨xx⟩⟼ u(x).

Definition 1.5. For R, S in V^{H}, the composition S ∘ R and the inverse relation R^{−1} are defined by: 𝒟(S ∘ R) = {⟨xz⟩; x, z ∈ V_{α}^{H}}, E(S ∘ R) = ER ∧ ES, S ∘ R : ⟨xz⟩ ⟼ ∥∃y(xRy ∧ ySz)∥, and

𝒟(R^{−1}) = {⟨xy⟩; x, y ∈ V_{α}^{H}}, E(R^{−1}) = ER, R^{−1} : ⟨xy⟩ ⟼ ∥yRx∥,

where α is a suitable ordinal which satisfies 𝒟R ∪ 𝒟S ⊆ V_{α}^{H}.

The definitions are not affected by the choice of the ordinal α. If R and S are relations from u to v and from v to w respectively, then S ∘ R is a relation from u to w and R^{−1} is a relation from v to u. Definition 1.6. Let R be a relation from u to v in V^{H}.

(1) For A ∈ V^{H}, the image R(A) ∈ V^{H} is defined by:

𝒟(R(A)) = 𝒟v, E(R(A)) = ER ∧ EA, R(A) : y ⟼ ∥(∃x ∈ A)xRy∥.

(2) For B ∈ V^{H}, the inverse image R^{−1}(B) ∈ V^{H} is defined by:

𝒟(R^{−1}(B)) = 𝒟u, E(R^{−1}(B)) = ER ∧ EB, R^{−1}(B) : x ⟼ ∥(∃y ∈ B)xRy∥.

A relation R from u to v in V^{H} is called total if (∀x ∈ u)(∃y ∈ v)(xRy) is valid, and is surjective if (∀y ∈ v)(∃x ∈ u)(xRy) is valid. Similarly, R is injective if (∀x, y ∈ u)(∀z ∈ v)(xRz ∧ yRz → x = y) is valid, and is univalent if (∀x ∈ u)(∀y, z ∈ v)(xRy∧xRz → y = z) is valid. Then R is total iff I_{u} ⊑ R^{−1}∘R, R is surjective iff I_{v} ⊑ R ∘ R^{−1}, R is injective iff R^{−1} ∘ R ⊑ I_{u}, and R is univalent iff R ∘ R^{−1} ⊑ I_{v}.

A relation R on u (that is, a relation from u to u) is called reflexive if (∀x ∈ u)(xRx) is valid. Similarly R is symmetric if ∀x∀y(xRy → yRx) is valid, is transitive if ∀x∀y∀z(xRy ∧ yRz → xRz) is valid, is antisymmetric if ∀x∀y(xRy ∧ yRx → x = y) is valid, and is connected if (∀x ∈ u)(∀y ∈ u)(xRy ∨ yRx) is valid. Then R is reflexive iff I_{u} ⊑ R, is symmetric iff R^{−1} ⊑ R iff R^{−1} ≈ R, is transitive iff R ∘ R ⊑ R, is antisymmetric iff R ∩ R^{−1} ⊑ I_{u}, and is connected iff u × u = R ∪ R^{−1}.

An equivalence relation is a reflexive, symmetric, and transitive relation, an order relation is a reflexive, antisymmetric, and transitive relation, and a total order is a connected order relation. Hence a relation R on u is an equivalence relation iff I_{u} ⊑ R, R^{−1} ⊑ R, and R ∘ R ⊑ R. If R is a relation R^{−1} ∘ R is symmetric, and in addition if R is total R^{−1} ∘ R is reflexive, and if it is univalent R^{−1} ∘ R is transitive.

A mapping in V^{H} is a total and univalent relation in the model. For u, v, f ∈ V^{H}, f is called a mapping from u to v in V^{H} if f is a total and univalent relation from u to v in V^{H}. We write f : u ⟶ v in V^{H} if f is a mapping from u to v. We often write f(x) = y instead of ⟨xy⟩ ∈ f or xfy. A relation f from u to v is a mapping iff I_{u} ⊑ f^{−1} ∘ f and f ∘ f^{−1} ⊑ I_{v}.

An injection (resp. a surjection) is an injective (resp. surjective) mapping, and a bijection is an injective and surjective mapping. A composition of injections (resp. surjections or bijections) is also an injection (resp. a surjection or a bijection). For a relation f from u to v, f is an injection iff I_{u} ≈ f^{−1} ∘ f and f ∘ f^{−1} ⊑ I_{v}, is a surjection iff I_{u} ⊑ f^{−1} ∘ f and f ∘ f^{−1} ≈ I_{v}, and f is a bijection iff I_{u} ≈ f^{−1} ∘ f and f ∘ f^{−1} ≈ I_{v}. Hence for a mapping f : u ⟶ v in V^{H}, f is injective iff I_{u} ≈ f^{−1} ∘ f and is surjective iff f ∘ f^{−1} ≈ I_{v}. For a mapping f in V^{H}, f^{−1} ∘ f is an equivalence relation.

We can define images and inverse images of mappings similarly to those of relations.

2 Relations and mappings between fuzzy subsets

In the following, let X, Y, Z be crisp sets. We call every set in the model V^{H} an H-fuzzy set.

Definition 2.1. For an H-fuzzy set A, the membership function of A on X is the mapping

μ_{A} = μA^{X} : X ⟶ H; x ⟼ ∥x̌ ∈ A∥.

An H-fuzzy subset of X is a subset of X̌ in V^{H}, that is, for A ∈ V^{H},

A is an H-fuzzy subset of X iff A ⊑ X̌.

Lemma 2.1. Every mapping from X to H is the membership function of some H-fuzzy subset of X.

Hence there is a natural correspondence between H-fuzzy subsets of X and mappings from X to H.

Definition 2.2. Let μ, ν be mappings from X to H.

(1) μ ≤ ν iff μ(x) ≤ ν(x) for all x ∈ X.

(2) The mappings μ ∧ ν, μ ∨ ν, ¬ μ : X ⟶H are defined by:

μ ∧ ν : x ⟼ μ(x) ∧ ν(x), μ ∨ ν : x ⟼ μ(x) ∨ ν(x), and ¬ μ : x ⟼ ¬ μ(x) (for all x ∈ X).

The natural correspondence preserves inclusion (order) and the basic set operations.

Proposition 2.2. Let A, B be H-fuzzy sets and all the membership functions below be on X.

(1) If A and B are H-fuzzy subsets of X, then A ⊑ B iff μ_{A} ≤ μ_{B}.

(2) μ_{A∩B} = μ_{A} ∧ μ_{B}, μ_{A∪B} = μ_{A} ∨ μ_{B}, and μ_{X̌\A} = ¬ μ_{A}.

Every relation in the model is called an H-fuzzy relation.

Definition 2.3. For R, u, v ∈ V^{H}, R is an H-fuzzy relation from u to v if it is a relation from u to v in V^{H}. For every R ∈ V^{H}, the membership function of R from X to Y is the membership function of R on X × Y, hence it is the mapping

μ_{R} : X × Y ⟶ H; ⟨xy⟩ ⟼ ∥⟨xy⟩^{∨} ∈ R∥.

An H-fuzzy relation from X to Y is an H-fuzzy subset of X ×Y.

If A, B are H-fuzzy subsets of X, Y respectively, then obviously an H-fuzzy relation from A to B is an H-fuzzy relation from X to Y.

Lemma 2.3. Let A, B be H-fuzzy subsets of X, Y respectively and R be a set in V^{H}. Then

R is an H-fuzzy relation from A to B iff μ_{R}⟨xy⟩ ≤ μ_{A}(x) ∧ μ_{B}(y) for all x ∈ X, y ∈ Y,

where μ_{A}, μ_{B}, μ_{R} be the membership functions on X, Y, X × Y respectively.

Proposition 2.4. Let A, B, C be H-fuzzy subsets of X, Y, Z respectively, R be an H-fuzzy relation from A to B, S be an H-fuzzy relation from B to C, and μ_{R}, μ_{S}, μ_{S∘R}, μ_{R^{−1}} be their membership functions on X × Y, Y × Z, X × Z, Y × X respectively.

(1) The composition S ∘ R is an H-fuzzy relation from A to C, and

μ_{S∘R}⟨xz⟩ = ⋁_{y∈Y} (μ_{R}⟨xy⟩ ∧ μ_{S}⟨yz⟩) for all x ∈ X, z ∈ Z.

(2) The inverse relation R^{−1} is an H-fuzzy relation from B to A, and μ_{R^{−1}}⟨yx⟩ = μ_{R}⟨xy⟩ for all x ∈ X, y ∈ Y.

These are extensions of the defining equations of max-min composition and those of inverse for ordinary fuzzy relations.

Proposition 2.5. Let A, B be H-fuzzy subsets of X, Y respectively, R be an H-fuzzy relation from A to B, and μ_{R} be its membership function on X × Y.

(1) For every C ∈ V^{H}, the image R(C) is a subset of B in V^{H}, and

μ_{R(C)}(y) = ⋁_{x∈X}(μ_{C}(x) ∧ μ_{R}⟨xy⟩) for all y ∈ Y,

where μ_{C} and μ_{R(C)} are the membership functions on X and on Y respectively.

(2) For every D ∈ V^{H}, the inverse image R^{−1}(D) is a subset of A in V^{H}, and

μ_{R^{−1}(D)}(x) = ⋁_{y∈Y} (μ_{D}(y) ∧ μ_{R}⟨xy⟩) for all x ∈ X,

where μ_{D} and μ_{R^{−1}(D)} are the membership functions on Y and on X respectively.

Proposition 2.6. Let A, B be H-fuzzy subsets of X, Y respectively, R be an H-fuzzy relation from A to B, and μ_{A}, μ_{B}, μ_{R} be their membership functions on X, Y, X × Y respectively.

(1) R is total iff ⋁_{y∈Y} μ_{R}⟨xy⟩ = μ_{A}(x) for all x ∈ X.

(2) R is surjective iff ⋁_{x∈X} μ_{R}⟨xy⟩ = μ_{B}(y) for all y ∈ Y.

(3) R is injective iff μ_{R}⟨xz⟩ ∧ μ_{R}⟨yz⟩ > 0 implies x = y for all x, y ∈ X and all z ∈ Y.

(4) R is univalent iff μ_{R}⟨xy⟩ ∧ μ_{R}⟨xz⟩ > 0 implies y = z for all x ∈ X and all y, z ∈ Y.

Theorem 1. Let A be an H-fuzzy subset of X, R be an H-fuzzy relation on A, and μ_{A}, μ_{R} be their membership functions on X, X × X respectively. Then the followings hold.

(1) R is reflexive iff μ_{R}⟨xx⟩ = μ_{A}(x) for all x ∈ X.

(2) R is symmetric iff μ_{R}⟨xy⟩ = μ_{R}⟨yx⟩ for all x, y ∈ X.

(3) R is transitive iff μ_{R}⟨xy⟩ ∧ μ_{R}⟨yz⟩ ≤ μ_{R}⟨xz⟩ for all x, y, z ∈ X

(4) R is antisymmetric iff μ_{R}⟨xy⟩ ∧ μ_{R}⟨yx⟩ > 0 implies x = y for all x, y ∈ X.

(5) R is connected iff μ_{R}⟨xy⟩ ∨ μ_{R}⟨yx⟩ = μ_{A}(x) ∧ μ_{A}(y) for all x, y ∈ X.

Every mapping in V^{H} is called an H-fuzzy mapping.

Definition 2.4. A mapping from u to v in V^{H} is called an H-fuzzy mapping from u to v. An H-fuzzy mapping from X to Y is a mapping from X̌ to Y̌ in V^{H}.

Obviously an H-fuzzy mapping from u to v is a total and univalent H-fuzzy relation from u to v.

Theorem 2. Let A, B be H-fuzzy subsets of X, Y respectively, and μ_{A}, μ_{B} be their membership function on X, Y respectively. Suppose f ∈ V^{H} and ψ = μ_{f} is its membership function on X × Y. Then f is an H-fuzzy mapping from A to B iff ψ satisfies the following three conditions:

(R) ψ⟨xy⟩ ≤ μ_{A}(x) ∧ μ_{B}(y) for all x ∈ X, y ∈ Y,

(E) ⋁_{y∈Y} ψ⟨xy⟩ = μ_{A}(x) for all x ∈ X,

(U) ψ⟨xy⟩ ∧ ψ⟨xz⟩ > 0 implies y = z for all x ∈ X, y, z ∈ Y.

Conversely, if a crisp mapping ψ : X × Y ⟶ H satisfies the three conditions, there is an H-fuzzy mapping f from A to B whose membership function on X × Y is identical with ψ.

Proposition 2.7. Let A, B be H-fuzzy subsets of X, Y respectively, f be an H-fuzzy mapping from A to B, and μ_{f} be its membership function on X × Y.

(1) For every C ∈ V^{H}, the image f(C) is a subset of B in V^{H}, and

μ_{f(C)}(y) = ⋁_{x∈X}(μ_{C}(x) ∧ μ_{f}⟨xy⟩) for all y ∈ Y,

where μ_{C} and μ_{f(C)} are the membership functions on X and on Y respectively.

(2) For every D ∈ V^{H}, the inverse image f^{−1}(D) is a subset of A in V^{H}, and

μ_{f^{−1}(D)}(x) = ⋁_{y∈Y} (μ_{D}(y) ∧ μ_{f}⟨xy⟩) for all x ∈ X,

where μ_{D} and μ_{f^{−1}(D)} are the membership functions on Y and on X respectively.

References

[1] M. Shimoda, Categorical aspects of Heyting-valued models for intuitionistic set theory, Comment. Math. Univ. Sancti Pauli 30(1) (1981) 17–35.

[2] M. Shimoda, A natural interpretation of fuzzy sets and fuzzy relations, submitted, 1998.

[3] M. Shimoda, A natural interpretation of fuzzy sets and relations (abstract), The Bulletin of Symbolic Logic, 5(1) (1999) 132.

[4] M. Shimoda, A natural interpretation of fuzzy mappings, submitted, 2000.

[5] S. Titani, Completeness of global intuiotionistic set theory, J. Symbolic Logic 62(2) (1997) 506–528.