# Categories of(I,I)-Fuzzy Greedoids

Authors: Zhen-Yu Xiu; Fu-Gui Shi
Journal: Journal of Function Spaces
 (2015)

---

## Abstract

The concepts ofI-greedoids, fuzzifying greedoids, and (I,I)-fuzzy greedoids are introduced and feasibility preserving mappings between greedoids are defined. Then I-feasibility preserving mappings, fuzzifying feasibility preserving mappings, and (I,I)-fuzzy feasibility preserving mappings are given as generalizations of feasibility preserving mappings. We study the relations among greedoids, I-greedoids, fuzzifying greedoids, and (I,I)-fuzzy greedoids from a categorical point of view.


---

## Body

## 1. Introduction

Greedoids have been invented by Korte and Lovász in [1, 2]. Originally, the main motivation for proposing this generalization of the matroid concept came from combinatorial optimization. The optimality of the greedy algorithm could in several instances be traced back to be an underlying combinatorial structure that was not a matroid but a greedoid. Optimality of the greedy solution for a broad class of objective mappings characterizes these structures. Many algorithmic approaches in different areas of combinatorics and other fields of numerical mathematics define the structure of a greedoid. Examples are scheduling under precedence constraints, breadth first search, shortest path, Gaussian elimination, shellings of trees, chordal graphs and convex sets, line and point search, series-parallel decomposition, retracting and dismantling of posets and graphs, and bisimplicial elimination.The fuzzification of matroids was first investigated by Goetschel and Voxman [3] and the concept of fuzzy matroids was introduced, where a family of independent fuzzy sets was defined as a crisp family of fuzzy subsets of a finite set satisfying certain set of axioms. Subsequently many authors investigated Goetschel-Voxman fuzzy matroids (see [3–12]). The concept of M-fuzzifying matroids was introduced as a new approach to the fuzzification of matroids by Shi [13], and his approach to the fuzzification of matroids preserves many basic properties of crisp matroids (see [14–17]). Particularly, the categorical relations among matroids, fuzzy matroids, and fuzzifying matroids are studied [18], and the main results are shown as follows:(1)M⊂r,cFYM≅CFM⊂cFM,where r, c in the diagram mean, respectively, reflective and coreflective.In [19], the concepts of L-matroids and (L,M)-fuzzy matroids are introduced as generations of matroids and were widely investigated (see [20–23]). In [22], the relations among matroids, [0,1]-prematroids, fuzzifying matroids, and bi-fuzzy prematroids were studied from a categorical viewpoint. The main results are summarized as follows:(2)M⊂r,cIM,FYM⊂r,cIIFM,M⊂r,cFYM≅CPIM⊂cIM⊂r,cIIFM,where r, c in the diagram mean, respectively, reflective and coreflective. In order to see the relations clearly, we give the following equivalent diagram:The aim of this paper is to introduce the concepts ofI-greedoids, fuzzifying greedoids, and (I,I)-fuzzy greedoids and study the relations among greedoids, I-greedoids, fuzzifying greedoids, and (I,I)-fuzzy greedoids from a categorical point of view. It is easy to prove that greedoids and feasibility preserving mappings form a category, fuzzifying greedoids and fuzzifying feasibility preserving mappings form a category, I-greedoids and I-feasibility preserving mappings form a category, and (I,I)-fuzzy greedoids and (I,I)-fuzzy feasibility preserving mappings form a category. In what follows, they are denoted by G, FYG, IG, and IIFG, respectively. CPIG denotes the category of closed and perfect I-greedoids and I-feasibility preserving mappings as morphisms.The paper is organized as follows. In Sections3 and 4, the concepts of I-greedoids, fuzzifying greedoids, and (I,I)-fuzzy greedoids are introduced, respectively. In Section 5, we show that FYG is isomorphic to CPIG and is a concretely coreflective full subcategory of IG. In Section 6, we show that G can be embedded in FYG as a simultaneously concretely reflective and coreflective full subcategory and IG is a simultaneously concretely reflective and coreflective full subcategory of IIFG. In Section 7, G can be embedded in IG as a concretely coreflective full subcategory and FYG is a reflective full subcategory of IIFG. In summary, we show that where r, c in the diagram mean, respectively, reflective and coreflective.


## 2. Preliminaries

Throughout this paper,I=[0,1] and E is a nonempty finite set. We denote the set of all subsets of E by 2E and the set of all fuzzy subsets of E by IE.ForA,B⊆E, A-B={e∈E:e∈A,e∉B}.Fora∈(0,1] and A⊆E, define a fuzzy set a∧A as follows: (5)a∧Ae=a,e∈A;0,e∉A.A fuzzy set a∧{e} is called a fuzzy point and denoted by ea.Fora∈(0,1] and A∈IE, we define(6)Aa=e∈E:Ae≥a,Aa=e∈E:Ae>a.Definition 1 (see [24]).
IfI is a nonempty subset of 2E, then the pair (E,I) is called a (crisp) set system. A set system (E,I) is called a matroid if it satisfies the following conditions: (I1)
∅∈I.(I2)
IfA∈I, B∈2E, and B⊆A, then B∈I.(I3)
IfA,B∈I and |A|<|B|, then there is e∈B-A such that A∪{e}∈I.Definition 2 (see [25]).
A greedoid is a pair of(E,F), where F⊆2E is a set system satisfying the following conditions: (G1)
For everyA∈F there is an e∈A such that A-{e}∈F.(G2)
ForA,B∈2E such that |A|<|B|, there is an e∈B-A such that A∪{e}∈F.The sets in F are called feasible (rather than “independent”).Remark 3.
In [25], (G1′) and (G2) together define greedoids as well (G1) and (G2), where (G1′) ∅∈F. Obviously, (G1) in Definition 2 could be replaced by the weaker axiom (G1′) and greedoids are defined as generalizations of matroids.Definition 4.
Let(Ei,Fi)(i=1,2) be greedoids. A mapping f:E1→E2 is called a feasibility preserving mapping from (E1,F1) to (E2,F2) if f-1(A)∈F1 for all A∈F2.Remark 5.
In [26], a function between two convex structures, called a convexity preserving function, inverts convex sets into convex sets. Here, similarly, we give a mapping between two greedoids, which inverts feasible sets into feasible sets and is called a feasibility preserving mapping.Definition 6 (see [13]).
A mappingI:2E→M is called an M-fuzzy family of independent sets on E if it satisfies the following conditions: (FI1)
I∅=⊤M.(FI2)
For anyA,B∈2E, A⊇B⇒I(A)⩽I(B).(FI3)
For anyA,B∈2E, if |A|<|B|, then ⋁e∈B-AI(A∪{e})⩾I(A)∧I(B).If I is an M-fuzzy family of independent sets on E, then the pair (E,I) is called an M-fuzzifying matroid. For A∈2E, I(A) can be regarded as the degree to which A is an independent set.Definition 7 (see [19]).
A subfamilyI of LE is called a family of independent L-fuzzy sets on E if it satisfies the following conditions: (LI1)
χ∅∈I.(LI2)
A∈LE, B∈I, and A⊆B⇒A∈I.(LI3)
IfA,B∈I and b=Bn|A|(n) for some n∈N, then there exists e∈F(A,B) such that (b∧A[b])∪eb∈I, where F(A,B)={e∈E:b⩽B(e),bA(e)}.If I is a family of independent L-fuzzy sets on E, then the pair (E,I) is called an L-matroid.Definition 8 (see [19]).
A mappingI:LE→M is called an M-fuzzy family of independent L-fuzzy sets on E if it satisfies the following conditions: (LMFI1)I(χ∅)=⊤M.(LMFI2) For anyA,B∈LE, A⊆B⇒I(A)⩾I(B).(LMFI3) Ifb=Bn|A|(n) for A,B∈LE and for some n∈N, then (7)⋁e∈FA,BIb∧Ab∪eb⩾IA∧IB.If I is an M-fuzzy family of independent L-fuzzy sets on E, then the pair (E,I) is called an (L,M)-fuzzy matroid.Remark 9.
(1) In [13, 19], L and M denote completely distributive lattices. In [22], when L=M=[0,1], an (L,M)-fuzzy matroid is also called bi-fuzzy prematroid, an L-matroid is called [0,1]-prematroid, and an M-fuzzifying matroid is called a fuzzifying matroid.
(2) WhenL is replaced by the interval [0,1], it is easy to see JL=L∖{⊥L}=(0,1].Definition 10 (see [19]).
LetA be an L-fuzzy set on a finite set E. Then the mapping |A|:N→L defined by, ∀n∈N, |A|(n)=⋁{a∈L:Aa≥n} is called the L-fuzzy cardinality of A.Lemma 11 (see [19]).
For a finite setE, it holds that |A|[a]=Aa for any A∈LE and any a∈J(L).Lemma 12 (see [19]).
LetG⊆E. Then |b∧G|(n)=(b∧|G|)(n) for any n>0 and for any b∈L∖{⊥L}.


## 3.I-Greedoids

Based on Definitions2 and 7, we give the following definition.Definition 13.
A subfamilyF of IE is called a family of feasible fuzzy sets on E if it satisfies the following conditions: (IG1)
χ∅∈F.(IG2)
IfA,B∈F and |B|(n)≥b>|A|(n) for some n∈N, then there exists e∈F(A,B) such that (b∧A[b])∪eb∈F, where (8)FA,B=e∈E:Be≥b>Ae.If F is a family of feasible fuzzy sets on E, then the pair (E,F) is called an I-greedoid.Theorem 14.
LetF⊆IE; ∀a∈(0,1], define F[a]={A[a]:A∈F}. If (E,F) is an I-greedoid, then (E,F[a]) is a greedoid for any a∈(0,1].Proof.
Suppose that(E,F) is an I-greedoid. Now we prove that, ∀a∈(0,1], (E,F[a]) is a greedoid.(1)
Obviously,∅=(χ∅)[a]∈F[a] for any a∈(0,1].(2)
IfA,B∈F[a] and |A|<|B|, then there are G,H∈F such that A=G[a], B=H[a], and |G[a]|<|H[a]|. Next we prove a∧G[a], a∧H[a]∈F.
IfG[a]=∅, then it is obviously a∧G[a]∈F.
If|G[a]|=n≥1, let G[a]={e1,e2,…en}. Since χ∅,G∈F, it is easy to see that there exists n1∈N such that |G|(n1)≥a>|χ∅|(n1). By (IG2), there exists e1∈F(χ∅,G) such that (a∧(χ∅)[a])∪(e1)a∈F, where F(χ∅,G)={e∈E:G(e)≥a>χ∅(e)}. We get (e1)a∈F and e1∈G[a].
Since(e1)a,G∈F, it is easy to see that there exists n2∈N such that |G|(n2)≥a>|(e1)a|(n2). By (IG2), there exists e2∈F((e1)a,G) such that (a∧((e1)a)[a])∪(e2)a∈F, where F((e1)a,G)={e∈E:G(e)≥a>(e1)a(e)}. We get a∧{e1,e2}∈F and {e1,e2}⊆G[a].
Continue the above process and we can obtaina∧G[a]∈F.
Analogously, we can obtaina∧H[a]∈F.
Since|G[a]|<|H[a]|, take n∈N such that |G[a]|<n≤|H[a]|. Then by Lemma 12, |a∧G[a]|(n)=(a∧|G[a]|)(n)=0<a=(a∧|H[a]|)(n)=|a∧H[a]|(n). Since a∧G[a],a∧H[a]∈F, there is e∈E such that (a∧H[a])(e)>(a∧G[a])(e) and (a∧(a∧G[a])[a])∪ea∈F. It is easy to see that G[a](e)=0, H[a](e)=1, and (a∧G[a])∪ea=(a∧(a∧G[a])[a])∪ea∈F. This implies that e∈H[a]=B, e∉G[a]=A, and A∪{e}=G[a]∪{e}=((a∧G[a])[a]∪ea)[a]∈F[a].
Therefore(E,F[a]) is a greedoid for any a∈(0,1].Corollary 15.
Let(E,F) be an I-greedoid. If A∈F, then ∀a∈(0,1], a∧A[a]∈F.Remark 16.
If(E,F) is an [0,1]-prematroid, it is obvious to see that Corollary 15 holds by (LI2). An I-greedoid (E,F) need not satisfy (LI2). However, by Theorem 14, Corollary 15 still holds. This is an important property for I-greedoids. Many results of I-greedoids in this paper are based on this property.Definition 17.
AnI-greedoid (E,F) is called a perfect I-greedoid if it satisfies the following condition: ∀A∈IE, if, ∀a∈(0,1], a∧A[a]∈F, then A∈F.By Corollary15 and Definition 17, we can easily obtain the following corollary.Corollary 18.
AnI-greedoid (E,F) is a perfect I-greedoid if it satisfies the following condition: ∀A∈IE, if, ∀a∈(0,1], A[a]∈F[a], then A∈F.Example 19.
LetE={3,4,5}. Define A∈IE by(9)
A
e
=
0
,
e
=
3
;
1
3
,
e
=
4
;
1
2
,
e
=
5
,and F⊆IE by F=B∈IE:B≤1/2∧{5}∪B∈IE:B≤1/3∧{3,4,5}-1/3∧{3}. It is easy to verify that (E,F) is an I-greedoid but it is not perfect, since a∧A[a]∈F for all a∈(0,1] but A∉F.Lemma 20.
Let(E,F) be an I-greedoid. If 0<a≤b≤1, then F[a]⊇F[b].Proof.
LetA∈F[b]. By the definition of F[b], there exists G∈F such that A=G[b]. By Corollary 15, we have b∧A=b∧G[b]∈F. Then A=(b∧A)[a]∈F[a].Theorem 21.
Let(E,F) be an I-greedoid. Define F∗={A∈IE:∀a∈(0,1],A[a]∈F[a]}. Then (E,F∗) is an I-greedoid. Moreover, if (E,F) is perfect, then F=F∗.Proof.
(1) Obviously,(χ∅)[a]=∅∈F[a] for any a∈(0,1]. Thus χ∅∈F∗.
(2) LetA,B∈F∗, and |B|(n)≥b>|A|(n) for some n∈N. Then |B|[b]>|A|[b]. By Lemma 11, we know that |B[b]|>|A[b]|. Since A[b],B[b]∈F[b] and (E,F[b]) is a greedoid, there exists e∈B[b]-A[b] such that A[b]∪{e}∈F[b]. In this case, ((b∧A[b])∪eb)[b]=A[b]∪{e}∈F[b]. It is obvious that ((b∧A[b])∪eb)[a]=A[b]∪{e}∈F[b]⊆F[a] for every a≤b and ((b∧A[b])∪eb)[a]=∅∈F[a] for every a>b. This implies that (b∧A[b])∪eb∈F∗.
(3) It is obvious thatF⊇F∗. Since (E,F) is perfect, by Corollary 18, F⊆F∗. Hence F=F∗.Corollary 22.
Let(E,F) be an I-greedoid. Then (E,F) is perfect if and only if F={A∈IE:∀a∈(0,1],A[a]∈F[a]}.Definition 23.
Let(Ei,Fi)(i=1,2) be I-greedoids. A mapping f:E1→E2 is called an I-feasibility preserving mapping from (E1,F1) to (E2,F2) if fI←(A)∈F1 for all A∈F2, where fI←(A)=A∘f.Theorem 24.
Let(Ei,Fi)(i=1,2) be I-greedoids and let f:E1→E2 be an I-feasibility preserving mapping from (E1,F1) to (E2,F2). If (E1,F1) is a perfect I-greedoid, then the following conditions are equivalent:(1)
f is an I-feasibility preserving mapping from (E1,F1) to (E2,F2).(2)
f is a feasibility preserving mapping from (E1,F1[a]) to (E2,F2[a]) for each a∈(0,1].Proof.
(
1
)
⇒
(
2
) Let A∈F2[a]. Then there exists A~∈F2 such that A=A~[a]∈F2[a]. Since f is an I-feasibility preserving mapping from (E1,F1) to (E2,F2), fI←(A~)∈F1. We have fI←(A~)[a]=f-1(A~[a])=f-1(A)∈F1[a]. This implies that f is a feasibility preserving mapping from (E1,F1[a]) to (E2,F2[a]) for each a∈(0,1].
(
1
)
⇐
(
2
) Assume that f is a feasibility preserving mapping from (E1,F1[a]) to (E2,F2[a]) for each a∈(0,1]. Let A∈F2. Then A[a]∈F2[a] for all a∈(0,1]. Thus fI←(A)[a]=f-1(A[a])∈F1[a] for all a∈(0,1]. Since (E1,F1) is a perfect I-greedoid, by Corollary 18, fI←(A)∈F1. Therefore f is an I-feasibility preserving mapping from (E1,F1) to (E2,F2).Theorem 25.
Let(E,F) be an I-greedoid. Then, ∀a∈(0,1], (E,F[a]) is a greedoid. Since E is a set finite, there is at most a finite number of greedoids on E. Thus there is a finite sequence 0=a0<a1<⋯<ar-1<ar=1 such that(1)
ifb,c∈(ai-1,ai)(1≤i≤r), then F[b]=F[c];(2)
ifai-1<b<ai<c<ai+1(1≤i≤r-1), then F[b]⫌F[c].The sequence 0=a0<a1<⋯<ar-1<ar=1 is called the fundamental sequence for (E,F).Proof.
We define an equivalence relation~ on (0,1] by a~b⇔F[a]=F[b]. Since E is a finite set, the number of greedoids on E is finite. Thus there exist at most finitely many equivalence classes which are, respectively, denoted by I1,I2,…,In. Next we prove that each Ii(i=1,2,…,n) is an interval. We only need to show that, ∀a,b∈Ii with a≤b, if c∈[a,b], then c∈Ii. Since a≤c≤b, by Lemma 20, we know that F[a]⊇F[c]⊇F[b]. As a,b∈Ii, F[a]=F[c]. Thus c∈Ii by the definition of Ii. This implies that Ii is an interval. Let ai-1=inf⁡Ii and ai=sup⁡Ii(i=1,2,…,n). Obviously, the sequence 0=a0<a1<⋯<ar-1<ar=1 is the fundamental sequence for (E,F).Definition 26.
AnI-greedoid (E,F) with the fundamental sequence 0=a0<a1<⋯<ar-1<ar=1 is called a closed I-greedoid if whenever ai-1<a≤ai(1≤i≤r), then F[a]=F[ai].Theorem 27.
Let(E,F) be an I-greedoid with the fundamental sequence 0=a0<a1<⋯<ar-1<ar=1. Then (E,F) is a closed I-greedoid if and only if it satisfies the following condition:(C)∀a∈(0,1] and A∈2E, if b∧A∈F for all 0<b<a, then a∧A∈F.Proof.
Suppose that(E,F) satisfies (C); ∀a∈(ai-1,ai)(i=1,2,…,n), then F[a]⊇F[ai]. Let A∈F[a] for all a∈(ai-1,ai). Then a∧A∈F for all a∈(ai-1,ai); thus b∧A∈F for all 0<b<ai. Since F satisfies (C), ai∧A∈F. Thus A=(ai∧A)[ai]∈F[ai]. This implies that F[a]⊆F[ai] for all a∈(ai-1,ai). Therefore, F[a]=F[ai] for all a∈(ai-1,ai]; that is, (E,F) is closed. Conversely, assume that (E,F) is a closed I-greedoid. Let a∈(0,1], A∈2E, and b∧A∈F for all 0<b<a. Since a∈(0,1], a∈(ai-1,ai] for some i=1,2,…,n. Take b0∈(ai-1,a)⊆(ai-1,ai]. Then b0∧A∈F and thus A∈F[b0]. Since (E,F) is closed, A∈F[ai]. Hence ai∧A∈F. By Corollary 15, we have a∧A=a∧(ai∧A)[a]∈F. This means that F satisfies (C).


## 4.(I,I)-Fuzzy Greedoids and Fuzzifying Greedoids

Definition 28.
A mappingF:IE→I is called a fuzzy family of feasible fuzzy sets on E if it satisfies the following conditions: (IIFG1)F(χ∅)=1.(IIFG2) If|B|(n)≥b>|A|(n) for A,B∈IE and for some n∈N, then (10)⋁e∈FA,BFb∧Ab∪eb⩾FA∧FB,where F(A,B)={e∈E:B(e)≥b>A(e)}.If F is a fuzzy family of feasible fuzzy sets on E, then the pair (E,F) is called an (I,I)-fuzzy greedoid.Definition 29.
A mappingF:2E→I is called a fuzzy family of feasible sets on E if it satisfies the following conditions: (FYG1)F(∅)=1.(FYG2) For anyA,B∈2E, if |A|<|B|, then ⋁e∈B-AF(A∪{e})⩾F(A)∧F(B).If F is a fuzzy family of feasible sets on E, then the pair (E,F) is called a fuzzifying greedoid. For A∈2E, F(A) can be regarded as the degree to which A is a feasible set.Theorem 30.
LetF:IE→I be a mapping. Then the following conditions are equivalent:(1)
(E,F) is an (I,I)-fuzzy greedoid.(2)
For eacha∈(0,1], (E,F[a]) is an I-greedoid.(3)
For eacha∈[0,1), (E,F(a)) is an I-greedoid.Proof.
(
1
)
⇒
(
2
) (IG1) It is obvious that χ∅∈F[a] for any a∈(0,1].
(IG2) IfA,B∈F[a] and |B|(n)≥b>|A|(n) for some n∈N, then, by (IIFG2), we have ⋁e∈FA,BF((b∧A[b])∪eb)⩾F(A)∧F(B). Further by A,B∈F[a], we obtain ⋁e∈FA,BF((b∧A[b])∪eb)⩾a. Then there exists e∈F(A,B) such that F((b∧A[b])∪eb)⩾a; that is, (b∧A[b])∪eb∈F[a]. This shows that F[a] satisfies (IG2). Therefore (E,F[a]) is an I-greedoid for each a∈(0,1].
(
2
)
⇒
(
1
) (IIFG1) For any a∈(0,1], χ∅∈F[a]. We have F(χ∅)=1.
(IIFG2) Suppose thatA,B∈[0,1]E and |B|(n)≥b>|A|(n) for some n∈N. In order to prove (IIFG2), take a∈(0,1] and F(A)∧F(B)≥a. Then F(A)≥a and F(B)≥a. This implies A,B∈F[a]. Hence, by (IG2), there exists e∈F(A,B) such that (b∧A[b])∪eb∈F[a]. This implies F((b∧A[b])∪eb)⩾a. Further we have ⋁e∈FA,BF((b∧A[b])∪eb)⩾a. By the arbitrariness of a, we obtain ∨e∈FA,BF((b∧A[b])∪eb)⩾F(A)∧F(B).
Analogously, we can obtain(1)⇔(3).Corollary 31.
LetF:2E→I be a map. Then the following conditions are equivalent:(1)
(E,F) is a fuzzifying greedoid.(2)
(E,F[a]) is a greedoid for each a∈(0,1].(3)
(E,F(a)) is a greedoid for each a∈[0,1).Definition 32.
Let(Ei,Fi)(i=1,2) be (I,I)-fuzzy greedoids. A mapping f:E1→E2 is called an (I,I)-fuzzy feasibility preserving mapping from (E1,F1) to (E2,F2) if F1(fI←(A))≥F2(A) for all A∈IE2, where fI←(A)=A∘f.Definition 33.
Let(Ei,Fi)(i=1,2) be fuzzifying greedoids. A mapping f:E1→E2 is called a fuzzifying feasibility preserving mapping from (E1,F1) to (E2,F2) if F1(f-1(A))≥F2(A) for all A∈2E2.Theorem 34.
Let(Ei,Fi)(i=1,2) be (I,I)-fuzzy greedoids and let f:E1→E2 be an (I,I)-fuzzy feasibility preserving mapping from (E1,F1) to (E2,F2). Then the following conditions are equivalent:(1)
f is an (I,I)-fuzzy feasibility preserving mapping from (E1,F1) to (E2,F2).(2)
f is an I-feasibility preserving mapping from (E1,(F1)[a]) to (E2,(F2)[a]) for each a∈(0,1].(3)
f is an I-feasibility preserving mapping from (E1,(F1)(a)) to (E2,(F2)(a)) for each a∈[0,1).Proof.
(
1
)
⇒
(
2
) Let f be an (I,I)-fuzzy feasibility preserving mapping from (E1,F1) to (E2,F2) and a∈(0,1]; ∀A∈(F2)[a], we have F1(fI←(A))≥F2(A)≥a and fI←(A)∈(F1)[a]. In other words, f is a fuzzy feasibility preserving mapping from (E1,(F1)[a]) to (E2,(F2)[a]) for each a∈(0,1].
(
1
)
⇒
(
2
) Next we need to prove that F1(fI←(A))≥F2(A) for any A∈IE. Let F2(A)≥a. Then A∈(F2)[a]. Since f is an I-feasibility preserving mapping from (E1,(F1)[a]) to (E2,(F2)[a]) for each a∈(0,1], fI←(A)∈(F1)[a]; that is, F1(fI←(A))≥a. By the arbitrariness of a, we have F1(fI←(A))≥F2(A). Therefore f is an (I,I)-fuzzy feasibility preserving mapping from (E1,F1) to (E2,F2).
Analogously, we can obtain(1)⇔(3).Corollary 35.
Let(Ei,Fi)(i=1,2) be fuzzifying greedoids and let f:E1→E2 be a fuzzifying feasibility preserving mapping from (E1,F1) to (E2,F2). Then the following conditions are equivalent:(1)
f is a fuzzifying feasibility preserving mapping from (E1,F1) to (E2,F2).(2)
f is a feasibility preserving mapping from (E1,(F1)[a]) to (E2,(F2)[a]) for each a∈(0,1].(3)
f is a feasibility preserving mapping from (E1,(F1)(a)) to (E2,(F2)(a)) for each a∈[0,1).Theorem 36.
Let(E,F) be a fuzzifying greedoid. Then, ∀a∈(0,1], (E,F[a]) is a greedoid. Since E is a finite set, there is at most a finite number of greedoids that can be defined on E. Thus there is a finite sequence 0=a0<a1<⋯<ar-1<ar=1 such that(1)
ifb,c∈(ai-1,ai](1≤i≤r), then F[b]=F[c];(2)
ifai-1<b≤ai<c≤ai+1(1≤i≤r-1), then F[b]⫌F[c].The sequence 0=a0<a1<⋯<ar-1<ar=1 is called the fundamental sequence for (E,F).Proof.
Fora,b∈(0,1], we can easily check that if a≤b, then F[a]⊇F[b]. We define an equivalence relation ~ on (0,1] by a~b⇔F[a]=F[b]. Since E is a finite set, the number of greedoids on E is finite. Thus there exist at most finitely many equivalence classes which are, respectively, denoted by I1,I2,…,In. Next we prove that each Ii(i=1,2,…,n) is a left open and right closed interval. It is trivial that each Ii(i=1,2,…,n) is an interval. Suppose that ai=sup⁡Ii and (E,Fi) is the corresponding cut greedoid with respect to Ii. Then Fi⊇F[ai] holds. For all A∈Fi, A∈F[r] and F(A)≥r for all r∈Ii. It follows that F(A)≥ai and A∈F[ai]. Thus Fi⊆F[ai]. Hence Fi=F[ai] and ai∈Ii. Obviously, the sequence 0=a0<a1<⋯<ar-1<ar=1 is the fundamental sequence for (E,F).


## 5. FYG as a Subcategory of IG

In this section, we will study the relation between fuzzifying greedoids and fuzzy greedoids from the viewpoint of category theory.Theorem 37.
Let(E,F) be a fuzzifying greedoid, and σ(F)={A∈IE:∀a∈(0,1],A[a]∈F[a]}. Then (1)
σ(F)[a]=F[a](∀a∈(0,1]);(2)
(E,σ(F)) is a closed and perfect I-greedoid.Proof.
(1)∀a∈(0,1], suppose that A[a]∈σ(F)[a], where A∈σ(F). Then A[a]∈F[a] by the definition of σ(F). This means that σ(F)[a]⊆F[a](∀a∈(0,1]). Conversely, assume that A∈F[a]. It is obvious that (a∧A)[b]=A∈F[a]⊆F[b] for every a≥b and (a∧A)[b]=∅∈F[b] for every a<b. Hence a∧A∈σ(F). So A=(a∧A)[a]∈σ(F)[a]. This implies that σ(F)[a]⊇F[a](∀a∈(0,1]). Therefore σ(F)[a]=F[a](∀a∈(0,1]).
(2) It is easy to see thatσ(F) satisfies (IG1). Now we prove that σ(F) satisfies (IG2). Suppose that A,B∈σ(F) and |B|(n)≥b>|A|(n) for some n∈N. Then |B|[b]>|A|[b]. We know that |B[b]|>|A[b]|. Since A[b],B[b]∈F[a] and (E,F[b]) is a greedoid, there exists e∈B[b]-A[b] such that A[b]∪{e}∈F[b]. In this case, ((b∧A[b])∪eb)[b]=A[b]∪{e}∈F[b]. It is obvious that ((b∧A[b])∪eb)[a]=A[b]∪{e}∈F[b]⊆F[a] for every a≤b and ((b∧A[b])∪eb)[a]=∅∈F[a] for every a>b. This implies that (b∧A[b])∪eb∈σ(F).
By (1) and the definition ofσ(F), σ(F)={A∈IE:∀a∈(0,1],A[a]∈F[a]}={A∈IE:∀a∈(0,1],A[a]∈σ(F)[a]}. By Corollary 22, (E,σ(F)) is a perfect I-greedoid. By Theorem 36, (E,σ(F)) is a closed I-greedoid.Theorem 38.
Let(Ei,Fi)(i=1,2) be fuzzifying greedoids. If f:E1→E2 is a fuzzifying feasibility preserving mapping from (E1,F1) to (E2,F2), then f is an I-feasibility preserving mapping from (E1,σ(F1)) to (E2,σ(F2)).Proof.
Sincef is a fuzzifying feasibility preserving mapping from (E1,F1) to (E2,F2), f is a feasibility preserving mapping from (E1,(F1)[a]) to (E2,(F2)[a]) for each a∈(0,1] by Corollary 35. By Theorem 37, f is a feasibility preserving mapping from (E1,σ(F1)[a]) to (E2,σ(F2)[a]) for each a∈(0,1]. Since (E1,σ(F1)) is perfect, by Theorem 24, f is an I-feasibility preserving mapping from (E1,σ(F1)) to (E2,σ(F2)).Theorem 39.
Let(E,F) be a closed and perfect I-greedoid. Define a map δ(F):2E→I by (11)δFA=⋁a∈0,1:A∈Fa.Then(1)
δ(F)[a]=F[a] for all a∈(0,1];(2)
(E,δ(F)) is a fuzzifying greedoid.Proof.
(1)∀a∈(0,1], suppose that A∈F[a]. Then δ(F)(A)≥a by the definition of δ(F). We have A∈δ(F)[a]. This means that δ(F)[a]⊇F[a]. Conversely, assume that A∈δ(F)[a]; that is, δ(F)(A)≥a. Since (E,F) is a closed I-greedoid, there exists b∈(0,1] such that b≥a and A∈F[b]. By b≥a, F[a]⊇F[b]. This means that δ(F)[a]⊆F[a]. Therefore δ(F)[a]=F[a] for all a∈(0,1].
(2) By (1) and Corollary31, (E,δ(F)) is a fuzzifying greedoid.Theorem 40.
Let(Ei,Fi)(i=1,2) be closed and perfect I-greedoids. If f:E1→E2 is an I-feasibility preserving mapping from (E1,F1) to (E2,F2), then f is a fuzzifying feasibility preserving mapping from (E1,δ(F1)) to (E2,δ(F2)).Proof.
Sincef is an I-feasibility preserving mapping from (E1,F1) to (E2,F2), f is a feasibility preserving mapping from (E1,F1[a]) to (E2,F2[a]) for each a∈(0,1] by Theorem 24. By Theorem 37, f is a feasibility preserving mapping from (E1,δ(F1)[a]) to (E2,δ(F2)[a]) for each a∈(0,1]. By Corollary 35, f is a fuzzifying feasibility preserving mapping from (E1,δ(F1)) to (E2,δ(F2)).Theorem 41.
(1) If(E,F) is a fuzzifying greedoid, then δ∘σ(F)=F.
(2) If(E,F) is a closed and perfect I-greedoid, then σ∘δ(F)=F.Proof.
(1) By Theorem37, (E,σ(F)) is a closed and perfect I-greedoid. Then δ∘σ(F)[a]=σ(F)[a]=F[a] for all a∈(0,1] by Theorems 37 and 39. Hence δ∘σ(F)=F.
(2) By Theorems37 and 39, (E,σ∘δ(F)) is a closed and perfect I-greedoid. Then σ∘δ(F)={A∈IE:∀a∈(0,1],A[a]∈δ(F)[a]}. Since (E,F) is a closed and perfect I-greedoid, δ(F)[a]=F[a] for all a∈(0,1] by Theorem 39. Therefore σ∘δ(F)={A∈IE:∀a∈(0,1],A[a]∈F[a]}=F since (E,F) is a closed and perfect I-greedoid.By Theorems37–41, we have the following.Theorem 42.
F
Y
G is isomorphic to CPIG.Theorem 43.
Let(E,F) be an I-greedoid with the fundamental sequence 0=a0<a1<⋯<ar-1<ar=1. ∀a∈(0,1], define F~a=F[ai-1+ai/2], where a∈(ai-1,ai]. Let F~={A∈IE:∀a∈(0,1],A[a]∈F~a}. Then(1)
(E,F~) is an I-greedoid;(2)
F~[a]=F~a for all a∈(0,1];(3)
(E,F~) is a closed and perfect I-greedoid.Proof.
(1) It is easy to see thatF~ satisfies (IG1). Now we prove that F~ satisfies (IG2). Suppose that A,B∈F~ and |B|(n)≥b>|A|(n) for some n∈N. Then |B|[b]>|A|[b]. We know that |B[b]|>|A[b]|. Since A[b],B[b]∈F~b and (E,F~b) is a greedoid, there exists e∈B[b]-A[b] such that A[b]∪{e}∈F~b. In this case, e∈F(A,B). It is obvious that ((b∧A[b])∪eb)[a]=A[b]∪{e}∈F~b⊆F~a for every a≤b and ((b∧A[b])∪eb)[a]=∅∈F~a for every a>b. This implies that (b∧A[b])∪eb∈F~.
(2) Suppose thatA∈F~[a]. Then there exists A~∈F~ such that A=A~[a]∈F~[a] and A~[b]∈F~b for each b∈(0,1] by the definition of F~. This implies that F~[a]⊆F~a. Conversely, assume that A∈F~a. Then there exists A~∈F such that A~[a]=A and a∧A~[a]∈F. We have (a∧A~[a])[b]=A[a]∈F~a⊆F~b for every a≥b and (a∧A[a])[b]=∅∈F~b for every b>a. This implies that a∧A~[a]∈F~. Hence A=A~[a]=(a∧A[a])[a]∈F~[a]. We have F~a⊆F~[a]. Therefore F~[a]=F~a for all a∈(0,1].
(3) By (1) and (2),(E,F~) is a closed I-greedoid. By (2) and the definition of F~, F~={A∈IE:∀a∈(0,1],A[a]∈F~a}={A∈IE:∀a∈(0,1],A[a]∈F~[a]}. Hence (E,F~) is a perfect I-greedoid.Theorem 44.
If(E,F) is a closed and perfect I-greedoid, then F~=F.Proof.
Since(E,F) is a closed I-greedoid, by Theorem 43, F~[a]=F[a] for all a∈(0,1]. By Theorem 43, (E,F~) is a perfect I-greedoid. Since (E,F) is a perfect I-greedoid, then F~={A∈IE:∀a∈(0,1],A[a]∈F~[a]}={A∈IE:∀a∈(0,1],A[a]∈F[a]}=F.Theorem 45.
Let(Ei,Fi)(i=1,2) be I-greedoids. If f:E1→E2 is an I-feasibility preserving mapping from (E1,F1) to (E2,F2), then f is an I-feasibility preserving mapping from (E1,F~1) to (E2,F~2).Proof.
Sincef:E1→E2 is an I-feasibility preserving mapping from (E1,F1) to (E2,F2), f is a feasibility preserving mapping from (E1,F1[a]) to (E2,F2[a]) for each a∈(0,1] by Theorem 24. Let 0=a0<a1<⋯<an-1<an=1 and 0=b0<b1<⋯<bm-1<bm=1 be the fundamental sequences for (E1,F1) and (E2,F2), respectively. ∀a∈(0,1], there exist i∈{1,2,…,n} and j∈{1,2,…,m} such that a∈(ai-1,ai]∩(bj-1,bj]. Let c=1/2min⁡{a-ai-1,a-bj-1}. Then a-c∈(ai-1,ai]∩(bj-1,bj]. It is easy to verify that F~1[a]=F1[a-c] and F~2[a]=F2[a-c]. Thus f is an I-feasibility preserving mapping from (E1,F~1[a]) to (E2,F~2[a]) for all a∈(0,1]. By Theorem 43, (E1,F~1) is a perfect I-greedoid. By Theorem 24, f is an I-feasibility preserving mapping from (E1,F~1) to (E2,F~2).Therefore, there is a functor fromIG to CPIG sending every I-greedoid (E,F) to (E,F~), in symbols s.By Theorems43–45, we have the following.Theorem 46.
Leti:CPIG→IG be the inclusion functor. Then(1)
i∘s(F)⊇F for any I-greedoid (E,F);(2)
s∘i(F)=F for any closed and perfect I-greedoid (E,F).By Theorem46, we have the following.Theorem 47.
C
P
I
G is a coreflective full subcategory of IG.By Theorems47 and 42, we have the following.Corollary 48.
F
Y
G can be regarded as a coreflective full subcategory of IG.


## 6.G as a Subcategory of FYG and IG as a Subcategory of IIFG

In the following, we will study the relation betweenI-greedoids and (I,I)-fuzzy greedoids and the relation between greedoids and fuzzifying greedoids from the viewpoint of category theory.Let(E,F) be an I-greedoid. Then (E,χF) is an (I,I)-fuzzy greedoid. Therefore, we define the inclusion mapping i:IG→IIFG by i(E,F)=(E,χF).By Theorem30, Corollary 31, Theorem 34, and Corollary 35, we will define two functors from IIFG to IG in the following theorem.Theorem 49.
(1)F:IIFG→IG, (E,F)↦(E,F[1]) is a functor.
(2)G:IIFG→IG, (E,F)↦(E,F(0)) is a functor.Theorem 50.
(1) For anyI-greedoid (E,F), F∘i(F)=G∘i(F)=F.
(2) For any(I,I)-fuzzy greedoid (E,F), i∘F(F)≤F and i∘G(F)≥F.Proof.
The proof is trivial and straightforward.Since bothIG and IIFG are concrete categories, we have the following.Theorem 51.
Both(F,i) and (i,G) are Galois correspondences between IG and IIFG, and i is the right inverse of both F and G. Hence IG can be embedded in IIFG as a simultaneously reflective and coreflective full subcategory.Corollary 52.
G is a simultaneously reflective and coreflective full subcategory of FYG.


## 7.G as a Subcategory of IG and FYG as a Subcategory of IIFG

In this section, we will study the relation between fuzzifying greedoids and(I,I)-fuzzy greedoids and the relation between greedoids and I-greedoids from the viewpoint of category theory.Theorem 53.
Let(E,F) be a fuzzifying greedoid. Define ωI(F):IE→I by (12)ωIFA=⋀a∈0,1FAa.Then (E,ωI(F)) is an (I,I)-fuzzy greedoid.Proof.
It is easy to see thatωI(F) satisfies (IIFG1). Now we prove that ωI(F) satisfies (IIFG2). Suppose that A,B∈[0,1]E, and |B|(n)≥b>|A|(n) for some n∈N. Then |B|[b]>|A|[b]. We know that |B[b]|>|A[b]|. This implies ⋁e∈Bb-AbF(A[b]∪{e})≥F(A[b])∧F(B[b]), since (E,F) is a fuzzifying greedoid. It is obvious that ((b∧A[b])∪eb)[a]=A[b]∪{e} for every a≤b and ((b∧A[b])∪eb)[a]=∅ for every a>b. This implies (13)⋁e∈FA,BωIFb∧Ab∪eb≥⋁e∈Bb-AbωIFb∧Ab∪eb≥⋁e∈Bb-Ab⋀a∈0,1Fb∧Ab∪eba=⋁e∈Bb-AbFAb∪e∧F∅≥FAb∧FBb≥ωIFAb∧ωIFBb,where F(A,B)={e∈E:B(e)≥b>A(e)}. Therefore (E,ωI(F)) is an (I,I)-fuzzy greedoid.Corollary 54.
Let(E,F) be a greedoid. Define ω(F) by ω(F)={A∈IE:A[a]∈F,∀a∈(0,1]}. Then (E,ω(F)) is an I-greedoid.Theorem 55.
Let(Ei,Fi)(i=1,2) be fuzzifying greedoids. If f:E1→E2 is a fuzzifying feasibility preserving mapping from (E1,F1) to (E2,F2), then f is an (I,I)-fuzzy feasibility preserving mapping from (E1,ωI(F1)) to (E2,ωI(F2)).Proof.
∀
A
∈
I
E, A[a]∈2E for all a∈(0,1]. Since f:E1→E2 is a fuzzifying feasibility preserving mapping from (E1,F1) to (E2,F2), F1(f-1(A[a]))≥F2(A[a]) for all a∈(0,1]. By the definition of ωI(F1) and ωI(F2), we have(14)ωIF1fI←A=⋀a∈0,1F1fI←Aa=⋀a∈0,1F1f-1Aa≥⋀a∈0,1F2Aa=ωIF2A.This implies that f is an (I,I)-fuzzy feasibility preserving mapping from (E1,ωI(F1)) to (E2,ωI(F2)).Corollary 56.
Let(Ei,Fi)(i=1,2) be greedoids. If f:E1→E2 is a feasibility preserving mapping from (E1,F1) to (E2,F2), then f is an I-feasibility preserving mapping from (E1,ω(F1)) to (E2,ω(F2)).Theorem 57.
Let(E,F) be an (I,I)-fuzzy greedoid. Define ιI(F):2E→I by (15)ιIFA=⋁a∈0,1FA∧a.Then (E,ιI(F)) is a fuzzifying greedoid.Proof.
It is easy to see thatιI(F) satisfies (FYG1). Now we prove that ιI(F) satisfies (FYG2). Suppose that A,B∈2E and |A|<|B|. Then a∧A, a∧B∈IE, and |a∧B|(|B|)=a>0=|a∧A|(|B|) for each a∈(0,1]. Since (E,F) is an (I,I)-fuzzy greedoid, (16)⋁e∈Fa∧A,a∧BFa∧A∧aa∨ea≥FA∧a∧FB∧a;that is, (17)⋁e∈B-AFa∧A∪e≥FA∧a∧FB∧a.Hence(18)⋁e∈B-AιIFa∧A∪e=⋁e∈B-A⋁a∈0,1Fa∧A∪e≥⋁a∈0,1FA∧a∧⋁a∈0,1FB∧a=ιIFA∧ιIFB.This implies that (FYG2) holds. Therefore (E,ιI(F)) is a fuzzifying greedoid.Corollary 58.
Let(E,F) be an I-greedoid. Define ι(F) by ι(F)={A∈2E:A∧a∈F for some a∈(0,1]}. Then (E,F) is a greedoid.Theorem 59.
Let(Ei,Fi)(i=1,2) be (I,I)-fuzzy greedoids. If f:E1→E2 is an (I,I)-fuzzy feasibility preserving mapping from (E1,F1) to (E2,F2), then f is a fuzzifying feasibility preserving mapping from (E1,ιI(F1)) to (E2,ιI(F2)).Proof.
For eachA∈2E, by the definition of ιI(F) and f:E1→E2 being an (I,I)-fuzzy feasibility preserving mapping from (E1,F1) to (E2,F2), we have (19)ιIF1f-1A=⋁a∈0,1F1f-1A∧a=⋁a∈0,1F1fI←A∧a≥⋁a∈0,1F2A∧a=ιIF2A.This implies that f is a fuzzifying feasibility preserving mapping from (E1,ιI(F1)) to (E2,ιI(F2)).Corollary 60.
Let(Ei,Fi)(i=1,2) be fuzzy greedoids. If f:E1→E2 is an I-feasibility preserving mapping from (E1,F1) to (E2,F2), then f is a feasibility preserving mapping from (E1,ι(F1)) to (E2,ι(F2)).Theorem 61.
(1) If(E,F) is an (I,I)-fuzzy greedoid, then ωI∘ιI(F)≥F.
(2) If(E,F) is a fuzzifying greedoid, then ιI∘ωI(F)=F.Proof.
(1) For eachA∈IE, by the definitions of ιI and ωI, we have(20)ωI∘ιIFA=⋀a∈0,1ιIFAa=⋀a∈0,1⋁b∈0,1Fb∧Aa≥⋀a∈0,1Fa∧Aa≥FA.This implies that ωI∘ιI(F)≥F.
(2) For eachA∈2E, by the definitions of ιI and ωI, we have (21)ιI∘ωIFA=⋁a∈0,1ωIFa∧A=⋁a∈0,1⋀b∈0,1Fa∧Ab=⋁a∈0,1FA=FA.This implies that ιI∘ωI(F)=F.Corollary 62.
(1) If(E,F) is an I-greedoid, then ω∘ι(F)⊇F.
(2) If(E,F) is a greedoid, then ι∘ω(F)=F.Based on the theorems and corollaries in this section, we have the following.Theorem 63.
(1)FYG is a coreflective full subcategory of  IIFG.
(2)G is a coreflective full subcategory of IG.


## 8. Conclusion

In this paper, we introduce the concepts ofI-greedoids, fuzzifying greedoids, and (I,I)-fuzzy greedoids as different approaches of the fuzzification of greedoids and study the relations among greedoids, fuzzy greedoids, fuzzifying greedoids, and (I,I)-fuzzy greedoids from a categorical point of view. The main results in this paper are in the following diagram, where r, c mean, respectively, reflective and coreflective: Such facts will be useful to help further investigations and it is possible that the fuzzification of greedoids would be applied to some combinatorial optimization problems in the future.



---

*Source: 543247-2015-11-10.xml*