The free product of M -fuzzifying matroids 1

Abstract

In this paper, motivated by the free product of crisp matroids, the free product of M-fuzzifying matroids is defined when M is a finite Boolean algebra and a number of fundamental properties of the operation are derived. Parallel to crisp matroids, the minors of M-fuzzifying matroids are described in terms of the M-fuzzifying truncation operator and its dual, the M-fuzzifying Higgs lift operator.

1 Introduction

Matroids were introduced by Whitney [38] to produce an abstract notion that would capture the main features of the structure of a set of vectors in a vector space. As an abstract theory of dependence originated in linear algebra and graph theory, matroids have a wide range of applications. For example, a number of problems in combinatorial optimization can be formulated on matroids and thus algorithmic matroid theory has been developed [8 , 23]. As far back as 1976, Greene [12] re-derived the MacWilliams identities [18], which related the weight enumerator of a code with the Tutte polynomial of a related matroid, and hence showed a connection between codes and matroids. In the past three decades, there has been a flurry of new applications of this theory. For example, ideas of matroids arise naturally in the study of ideal secret-sharing schemes [1 , 34] and in network coding theory [5 –7].

A characteristic of matroids is that they can be defined in terms of different concepts, such as rank, independence, bases, circuits, etc. In matroid theory, various operations as ways of constructing new matroids from given sets of matroids— such as direct sum and union— are useful tools for simplifying some well-known results and in dealing with some problems [22, 36]. As a relatively new operation, the free product of two matroids was first introduced by Crapo and Schmitt in [2], where the authors used it to prove the conjecture of Welsh [37] that f (n + m) ≥ f (n) f (m) , where f (n) is the number of non-isomorphic matroids on an n-element set. In their paper [3], a systematic study of the free product showed many attractive properties and rich algebraic structure of the operation.

In 1988, matroids were generalized to fuzzy fields by Goetschel and Voxman [10]. In [31], based on the idea of a fuzzifying topology [44], Shi introduced a new approach to fuzzification of matroids, which led to the concept of M-fuzzifying matroids. An M-fuzzifying matroid is a pair of a finite set E and an M-fuzzy family of independent sets on E (i.e., a mapping $I$ from 2^E to M satisfying certain axioms) in which each subset A of E can be regarded as an independent set with degree $I (A) .$ Since then, axioms of bases and circuits of [0, 1]-fuzzifying matroids,M-fuzzy family of bases, M-fuzzifying rank function, M-fuzzifying closure operator, M-fuzzifying nullity, etc., have been established and studied [16 , 43].

More recently, the dual and minors for M-fuzzifying matroids were introduced in terms of M-fuzzifying rank functions and a kind of subtraction of M-fuzzy natural numbers [16]. Since every matroid can be regard as an M-fuzzifying matroid with M = {⊥ , ⊤} , and since there is a nice theory of dual for M-fuzzifying matroids when M is a finite Boolean algebra, we therefore consider the free product of M-fuzzifying matroids when M is a finite Boolean algebra in this paper. After recalling some basic notions and properties of matroids, lattices and the subtraction of M-fuzzy natural numbers in the following section, we give the definition of the free product of M-fuzzifying matroids when M is a finite Boolean algebra. Then analogous to the free product for crisp matroids, some fundamental properties of the operation are derived. In section 4, the minors of M-fuzzifying matroids are described in terms of the M-fuzzifying truncation operator and its dual, the M-fuzzifying Higgs lift operator. Finally, conclusions and discussions are made.

2 Preliminaries

Given a non-empty finite set E, we denote the set of all subsets of E by 2^E, and for any A ⊆ E, we denote by |A| the cardinality of A .

In this section, unless otherwise mentioned, M denotes a completely distributive lattice, and the smallest element and the largest element in M are denoted by ⊥ and ⊤, respectively. An element a in M is called a (meet-)prime element if a ≥ b ∧ c implies a ≥ b or a ≥ c . a in M is called co-prime or join-prime if a ≤ b ∨ c implies a ≤ b or a ≤ c . The set of non-unit prime elements in M is denoted by P (M) . The set of non-zero join-prime elements in M is denoted by J (M) . From [9] we know that in a completely distributive lattice, each element is the sup of a set of join-prime elements and the inf of a set of meet-prime elements. The pseudocomplement [11] of a relative to b (a, b ∈ M) is an element a ∗ b of M satisfying a ∧ x ≤ b if and only if x ≤ a ∗ b, that is, a ∗ b = ⋁ {x ∈ M : a ∧ x ≤ b} .

Definition 2.1. [22] Let E be a finite set and $I \subseteq 2^{E} .$ Then the ordered pair $(E, I)$ is called a matroid if it has the following three properties:

(I1) $\emptyset \in I .$

(I2) If $A \in I, B \in 2^{E}$ and B ⊆ A, then $B \in I .$ (I3) If $A, B \in I$ and |A| < |B|, then there exists x ∈ B - A such that $A \cup {x} \in I .$

Definition 2.2. [31] Denote the set of all M-fuzzy sets on X by M^X . Let A ∈ M^X and a ∈ M . Define

A_[a] = {x ∈ X : A (x) ≥ a} ,

A^(a) = {x ∈ X : A (x) nleqa} .

Some properties of these cut sets can be found in [13 , 33].

For a ∈ M and D ⊆ X, we define a ∨ D as follows:

$(a \lor D) (x) = \{\begin{array}{c} ⊤, & if x \in D, \\ a, & if x \notin D . \end{array}$

Then for any M-fuzzy set A ∈ M^X, we have [13, 27] $A = ⋀_{a \in P (M)} (a \lor A^{(a)}) .$ (1)

Definition 2.3. [31] Let $ℕ$ be the set of all natural numbers. An M-fuzzy natural number is an antitone mapping $λ : ℕ \to M$ satisfying $λ (0) = ⊤, ⋀_{n \in ℕ} λ (n) = ⊥ .$

The set of all M-fuzzy natural numbers is denoted by $ℕ (M) .$ For $λ, μ \in ℕ (M),$ we write μ ≤ λ (or λ ≥ μ) if and only if μ (n) ≤ λ (n) for all $n \in ℕ .$ And μ < λ means μ ≤ λ but μ ≠ λ .

Definition 2.4. [24, 31] For any $λ, μ \in ℕ (M),$ the addition λ + μ of λ and μ is defined as follows: for any $n \in ℕ,$ $(λ + μ) (n) = ⋁_{k + l = n} (λ (k) \land μ (l)) .$

Also, the meet λ ∧ μ and join λ ∨ μ of λ and μ are defined by (λ ∧ μ) (n) = λ (n) ∧ μ (n) and (λ ∨ μ) (n) = λ (n) ∨ μ (n) , for all $n \in ℕ,$ respectively.

Remark 2.5. [31] For any $n \in ℕ,$ define $\underline{n} \in ℕ (M)$ such that

$\underline{n} (t) = \{\begin{array}{c} ⊤, & if t \leq n, \\ ⊥, & if t \geq n + 1. \end{array}$

Then $ℕ$ can be regarded naturally as a subset of $ℕ (M) .$ In the sequel, we shall not distinguish the set {0, 1, ⋯ , n} , n and $\underline{n}$ (see Remark 17 in [31]).

Theorem 2.6. [31, 40] Let $λ, μ \in ℕ (M) .$ Then

(i) for any a∈ P (M) , (λ + μ) ^(a) = λ^(a) + μ^(a) ;

(ii) for any a ∈ J (M) , (λ + μ) _[a] = λ_[a] + μ_[a] .

Let x ∧ y = min {x, y} , x ∨ y = max {x, y} for real numbers x and y . Then the following proposition holds.

Proposition 2.7. Let $λ, μ \in ℕ (M) .$ Then (i) for any a∈ P (M) , (λ ∧ μ) ^(a) = λ^(a) ∧ μ^(a) ;

(ii) for any a ∈ M ∖ {⊤} , (λ ∨ μ) ^(a) = λ^(a) ∨ μ^(a) .

Proposition 2.8. [16] Let $α, β, γ, δ, μ \in ℕ (M) .$ Then (i) (α ∨ β) + γ = (α + γ) ∨ (β + γ) ,

(α∧ β) + γ = (α + γ) ∧ (β + γ) ;

(ii) if α ≥ δ ∨ γ, δ ∧ γ ≥ β and α + β ≤ δ + γ, then (α ∧ μ) + (β ∧ μ) ≤ (δ ∧ μ) + (γ ∧ μ) .

Proposition 2.9. Let $α, β, γ, δ, α^{'}, β^{'}, γ^{'}, δ^{'} \in ℕ (M) .$ Then

(i) α+ β = (α ∧ β) + (α ∨ β) ;

(ii) (α+ β) ∧ γ = (α ∧ γ + β) ∧ γ ;

(iii) if α ≥ δ ∨ γ, δ ∧ γ ≥ β, β′ ≥ δ′ ∨ γ′, δ′ ∧ γ′ ≥ α′, α + β ≥ δ + γ and α′ + β′ ≥ δ′ + γ′, then (α ∨ α′) + (β ∨ β′) ≥ (δ ∨ δ′) + (γ ∨ γ′) .

Proof. (i) By Theorem 2.6 and Proposition 2.7, for any a ∈ P (M) , ((α ∧ β) + (α ∨ β)) ^(a) = (α^(a) ∧ β^(a)) + (α^(a) ∨ β^(a)) = α^(a) + β^(a) = (α + β) ^(a) . It follows from Proposition 3.6 that α + β = (α ∧ β) + (α ∨ β) .

(ii) Note that for any a ∈ P (M) , (α^(a) + β^(a)) ∧ γ^(a) ≤ α^(a) ∧ γ^(a) + β^(a) . Then by Proposition 3.6, (α + β) ∧ γ ≤ (α ∧ γ + β) and thus (α + β) ∧ γ ≤ (α ∧ γ + β) ∧ γ . Conversely, (α + β) ∧ γ ≥ (α ∧ γ + β) ∧ γ is obvious.

(iii) It follows easily from the conditions that α + β′ ≥ α′ + β . Thus by the first equality of Proposition 2.8(i), we have $\begin{matrix} (α \lor α^{'}) + (β \lor β^{'}) \\ = [(α \lor α^{'}) + β] \lor [(α \lor α^{'}) + β^{'}] \\ = [(α + β) \lor (α^{'} + β)] \lor [(α + β^{'}) \lor (α^{'} + β^{'})] \\ = (α + β) \lor (α + β^{'}) \lor (α^{'} + β^{'}) \\ \geq (δ + γ) \lor (δ^{'} + γ) \lor (δ + γ^{'}) \lor (δ^{'} + γ^{'}) \\ = (δ \lor δ^{'}) + (γ \lor γ^{'}) . □ \end{matrix}$

Definition 2.10. [16] Let $λ, μ \in ℕ (M)$ and λ ≥ μ . The subtraction λ - μ of λ and μ is defined by $(λ - μ) (n) = ⋀_{k \in ℕ} (μ (k) * λ (k + n)),$ for all $n \in ℕ .$

Proposition 2.11. [16] Let M be a finite Booleanalgebra and $α, δ, λ, μ \in ℕ (M) .$ Then

(i) if λ ≥ μ, then δ+ (λ - μ) = (δ + λ) - μ ;

(ii) α + μ = λ if and only if α = λ - μ ;

(iii) for any a∈ J (M) , (λ - μ) _[a] = λ_[a] - μ_[a] ;

(iv) for any a∈ P (M) , (λ - μ) ^(a) = λ^(a) - μ^(a) ;

(v) if δ + μ ≥ λ ≥ μ, then δ - (λ - μ) = (δ + μ) - λ .

Note that Proposition 2.11(ii) implies that when M is a finite Boolean algebra the subtraction is the inverse of the addition. Due to this fact, the subtraction has further properties. Particularly, we need the following proposition.

Proposition 2.12. Let M be a finite Boolean algebra and $α, β, δ, λ, μ \in ℕ (M) .$ Then

$\begin{matrix} (i) (λ \land μ) - δ = (λ - δ) \land (μ - δ); \\ (ii) (α \land μ) + (β + α - α \land μ) \land δ \\ = β \land δ + α \land (μ + δ - β \land δ) . \end{matrix}$ (2)In particular, taking $β = \underline{0}$ in (2) yields $(α \land μ) + (α - α \land μ) \land δ = α \land (μ + δ) .$ (3)

Proof. (i) By Propositions 2.8(i) and 2.11, δ + (λ - δ) ∧ (μ - δ) = λ ∧ μ . Therefore, the result follows from Proposition 2.11(ii).

(ii) By Propositions 2.8(i), 2.9(ii) and 2.11, we have

$\begin{matrix} (α \land μ) + (β + α - α \land μ) \land δ \\ = [(β + α - α \land μ) + α \land μ] \land (α \land μ + δ) \\ = (β + α) \land [(α + δ) \land (μ + δ)] \\ = [(β + α) \land (α + δ)] \land (μ + δ) \\ = [β \land δ + α] \land (μ + δ) \\ = β \land δ + α \land (μ + δ - β \land δ) . □ \end{matrix}$

Remark 2.13. Note that in general Proposition 2.12(ii) does not hold. For instance, let M = [0, 1] , α = (1, 0.8, 0.5, 0.3, 0, ⋯) , μ = (1, 0.6, 0.2, 0, ⋯) and $δ = \underline{1}$ in (3). Then (α ∧ μ) + (α - α ∧ μ) ∧ δ = (1, 0.6, 0.5, 0.2, 0, ⋯) < (1, 0.8, 0.5, 0.2, 0, ⋯) = α ∧ (μ + δ) .

Definition 2.14. [32] Let E be a finite set. A mapping $I : 2^{E} \to M$ is called an M-fuzzy family of independent sets on E if it satisfies the following three conditions:

(FI1) $I (\emptyset) = ⊤ .$

(FI2) If A, B ∈ 2^E and A ⊆ B, then $I (A) \geq I (B) .$

(FI3) If A, B ∈ 2^E and |A| < |B|, then $⋁_{e \in B - A} I (A \cup {e}) \geq I (A) \land 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.

Definition 2.15. [31] Let $(E, I)$ be an M-fuzzifying matroid. The mapping $R : 2^{E} \to ℕ (M)$ defined by $R_{I} (A) (n) = ⋁ {I (B) : B \subseteq A, | B | \geq n},$ is called the M-fuzzifying rank function for $(E, I) .$

Theorem 2.16. [31] Let $(E, I)$ be an M-fuzzifying matroid. Then the M-fuzzifying rank function $R_{I}$ for $(E, I)$ has the following properties:

(FR1) For any $A \in 2^{E}, \underline{0} \leq R_{I} (A) \leq \underline{| A |} .$

(FR2) If A, B ∈ 2^E and A ⊆ B, then $R_{I} (A) \leq R_{I} (B) .$

(FR3) For any $A, B \in 2^{E}, R_{I} (A) + R_{I} (B) \geq R_{I} (A \cap B) + R_{I} (A \cup B) .$

It was proved in [31] that whenever a mapping $R : 2^{E} \to ℕ (M)$ satisfies (FR1) – (FR3) , there is an M-fuzzifying matroid $(E, I_{R}),$ in which $I_{R} : 2^{E} \to M$ is determined by $I_{R} (X) = R (X) (| X |), \forall X \subseteq E .$ (4)

And as expected, R is the M-fuzzifying rank function for $(E, I_{R}) .$

In what follows, we always denote by $R_{I}$ theM-fuzzifying rank function for a given M-fuzzifying matroid $(E, I) .$ A mapping $R : 2^{E} \to ℕ (M)$ is called an M-fuzzifying rank function provided it satisfies (FR1) – (FR3) . And we call the M-fuzzifying matroid determined by (4) the M-fuzzifying matroid corresponding to R .

Theorem 2.17. [16] Let $(E, I)$ be an M-fuzzifying matroid and $I^{*}, I / T$ be its dual and restriction, respectively. Then $R_{I^{*}} (X) = [\underline{| X |} + R_{I} (\bar{X})] - R_{I} (E), \forall X \subseteq E,$ (5)and $R_{I / T} (X) = R_{I} (X \cup T) - R_{I} (T), \forall X \subseteq E - T .$

Let M be a finite Boolean algebra. Then the following propositions hold.

Proposition 2.18. [16] Let $(E, I)$ be an M-fuzzifying matroid and T₁, T₂ disjoint subsets of E . Then

(i) $(I ∖ T_{1}) ∖ T_{2} = I ∖ (T_{1} \cup T_{2}) = (I ∖ T_{2}) ∖ T_{1};$

(ii) $(I ∖ T_{1}) / T_{2} = (I / T_{2}) ∖ T_{1};$

(iii) $(I / T_{1}) / T_{2} = I / (T_{1} \cup T_{2}) = (I / T_{2}) / T_{1} .$

Proposition 2.19. [16] Let $(E, I)$ be an M-fuzzifying matroid and T ⊆ E . Then

(i) $(I^{*})^{*} = I;$

(ii) $(I / T)^{*} = I^{*} ∖ T .$

Proposition 2.20. [16] Let $(E, I)$ be an M-fuzzifying matroid and T₁, T₂ disjoint subsets of E . Then

(i) $R_{I} (E) + R_{I^{*}} (E) = \underline{| E |};$

(ii) for any a ∈ P (M) , ${I^{*}}^{(a)} = (I^{(a)})^{*};$

(iii) for any a ∈ J (M) , $\underset{[a]}{I^{*}} = (I_{[a]})^{*};$

(iv) for any a ∈ P (M) , $((I / T_{1}) ∖ T_{2})^{(a)} = (I^{(a)} / T_{1}) ∖ T_{2};$

(v) for any a ∈ J (M) , $((I / T_{1}) ∖ T_{2})_{[a]} = (I_{[a]} / T_{1}) ∖ T_{2} .$

Definition 2.21. [16] Let M be [0, 1] or a finite Boolean algebra and let $(E, I)$ be an M-fuzzifying matroid. The mapping $ν_{I} : 2^{E} \to ℕ (M)$ defined, for all A ⊆ E, by $ν_{I} (A) = \underline{| A |} - R_{I} (A)$ is called the M-fuzzifyingnullity for $(E, I) .$

Theorem 2.22. [16] Let M be [0, 1] or a finite Boolean algebra and let $(E, I)$ be an M-fuzzifying matroid. Then $ν_{I}$ has the following properties:

(FN1) For any $A \in 2^{E}, \underline{0} \leq ν_{I} (A) \leq \underline{| A |} .$

(FN2) If A, B ∈ 2^E and A ⊆ B, then $\underline{| B |} - \underline{| A |} \geq ν_{I} (B) - ν_{I} (A) .$

(FN3) For any $A, B \in 2^{E}, ν_{I} (A \cap B) + ν_{I} (A \cup B) \geq ν_{I} (A) + ν_{I} (B) .$

Remark 2.23. It is not difficult to show that if A ⊆ B ⊆ E, then $ν_{I} (A) \leq ν_{I} (B) .$

3 The free product of M-fuzzifying matroids

In the following, M is assumed to be a finite Boolean algebra for all the M-fuzzifying matroids considered. For an M-fuzzifying matroid $(E, I)$ and A ⊆ B ⊆ E, we denote the minor $(I | B) / A = (I / A) | (B ∖ A)$ by $I (A, B) .$ Following [3], we denote the disjoint union of sets S and T by S + T, and the intersection X ∩ Y by either X_Y or Y_X . We denote by $λ_{I}$ the M-fuzzifying rank-lack function for $(E, I),$ given by $λ_{I} (A) = R_{I} (E) - R_{I} (A),$ for all A ⊆ E . Clearly, if A ⊆ B ⊆ E then $λ_{I} (A) \geq λ_{I} (B) .$

Theorem 3.1. [3] Let M = M (S) and N = N (T) be matroids on disjoint sets S and T, respectively. Then the rank function of the free product L = M (S) □ N (T) is given by

$\begin{matrix} r_{L} (A) & = & r_{M} (A_{S}) + r_{N} (A_{T}) \\ + min {r_{M} (S) - r_{M} (A_{S}), | A_{T} | - r_{N} (A_{T})}, \end{matrix}$ for all A ⊆ S + T, where r_M and r_N are the rank functions of the matroids M and N, respectively.

Proposition 3.2. Let $(S, M)$ and $(T, N)$ be M-fuzzifying matroids on disjoint sets S and T, respectively. Define $R_{M □ N} : 2^{S + T} \to ℕ (M)$ by $\begin{matrix} R_{M □ N} (A) & = & R_{M} (A_{S}) + R_{N} (A_{T}) \\ + λ_{M} (A_{S}) \land ν_{N} (A_{T}), \end{matrix}$ (6)for all A ⊆ S + T . Then $R_{M □ N}$ is an M-fuzzifying rank function.

Proof. By Propositions 2.9(i) and 2.11, we have

$\begin{matrix} R_{M □ N} (A) & = & [R_{M} (S) + R_{N} (A_{T})] \\ \land [\underline{| A_{T} |} + R_{M} (A_{S})] . \end{matrix}$ (7)

It follows easily from (7) that $R_{M □ N}$ satisfies (FR1) and (FR2) . To prove (FR3) , noting that by Propositions 2.9(ii) and 2.12(i), we can rewrite $R_{M □ N}$ as

$\begin{matrix} R_{M □ N} (A) \\ = R_{M} (A_{S}) + R_{N} (A_{T}) \\ + [λ_{M} (A_{S}) + ν_{N} (A_{T}) - λ_{M} (A_{S}) \lor ν_{N} (A_{T})] \\ = R_{M} (S) + \underline{| A_{T} |} - λ_{M} (A_{S}) \lor ν_{N} (A_{T}) . \end{matrix}$

Now, let $β = λ_{M} (A_{S} \cup B_{S}), α = λ_{M} (A_{S} \cap B_{S}), δ = λ_{M} (A_{S}), γ = λ_{M} (B_{S})$ and let $β^{'} = ν_{N} (A_{T} \cup B_{T}), α^{'} = ν_{N} (A_{T} \cap B_{T}), δ^{'} = ν_{N} (A_{T}), γ^{'} = ν_{N} (B_{T}) .$ By Remark 2.23 and the submodularity of $R_{M}$ and $R_{N},$ one can show that the conditions of Proposition 2.9(iii) are satisfied. Thus $\begin{matrix} R_{M □ N} (A) + R_{M □ N} (B) \\ = [R_{M} (S) + \underline{| A_{T} |} - δ \lor δ^{'}] + [R_{M} (S) + \underline{| B_{T} |} \\ - γ \lor γ^{'}] \\ = [R_{M} (S) + R_{M} (S) + \underline{| A_{T} |} + \underline{| B_{T} |}] - [δ \lor δ^{'} \\ + γ \lor γ^{'}] \\ \geq [R_{M} (S) + R_{M} (S) + \underline{| A_{T} \cap B_{T} |} + \underline{| A_{T} \cup B_{T} |}] \\ - [α \lor α^{'} + β \lor β^{'}] \\ = [R_{M} (S) + \underline{| A_{T} \cap B_{T} |} - α \lor α^{'}] \\ + [R_{M} (S) + \underline{| A_{T} \cup B_{T} |} - β \lor β^{'}] \\ = R_{M □ N} (A \cap B) + R_{M □ N} (A \cup B) . \end{matrix}$

Hence $R_{M □ N}$ is an M-fuzzifying rank function.□

Based on Theorem 3.1 and Proposition 3.2, we can give the following definition.

Definition 3.3. Under the conditions of Proposition 3.2, the M-fuzzifying matroid $(S + T, M □ N)$ is called the free product of $(S, M)$ and $(T, N),$ where $M □ N : 2^{S + T} \to M$ is defined by $M □ N (X) = R_{M □ N} (X) (| X |),$ for all X ⊆ S + T .

It follows immediately that the M-fuzzifying rank-lack function for $(S + T, M □ N)$ is given by

$\begin{matrix} λ_{M □ N} (A) & = & λ_{M} (A_{S}) + λ_{N} (A_{T}) \\ - λ_{M} (A_{S}) \land ν_{N} (A_{T}), \end{matrix}$ (8)for all A ⊆ S + T, and similarly the M-fuzzifyingnullity

$\begin{matrix} ν_{M □ N} (A) & = & ν_{M} (A_{S}) + ν_{N} (A_{T}) \\ - λ_{M} (A_{S}) \land ν_{N} (A_{T}), \end{matrix}$ (9)for all A ⊆ S + T .

Definition 3.4. [43] Two M-fuzzifying matroids $(E_{1}, I_{1})$ and $(E_{2}, I_{2})$ are isomorphic, written $(E_{1}, I_{1})$ $≅ (E_{2}, I_{2}),$ if there is a bijection f : E₁ → E₂ such that $I_{1} (A) = I_{2} (f (A))$ for all A ⊆ E₁ . We call such a bijection f an isomorphism from $(E_{1}, I_{1})$ to $(E_{2}, I_{2}) .$

Theorem 3.5. Let $(S_{1}, M_{1}) ≅ (S_{2}, M_{2})$ and $(T_{1}, N_{1})$ $≅ (T_{2}, N_{2}) .$ Then $(S_{1} + T_{1}, M_{1} □ N_{1}) ≅ (S_{2} + T_{2}, M_{2} □ N_{2}) .$

Proof. Let φ be an isomorphism from $(S_{1}, M_{1})$ to $(S_{2}, M_{2})$ and let ψ be an isomorphism from $(T_{1}, N_{1})$ to $(T_{2}, N_{2}) .$ Define f : S₁ + T₁ → S₂ + T₂ by

$f (x) = \{\begin{array}{c} φ (x), & if x \in S_{1}, \\ ψ (x), & if x \in T_{1} . \end{array}$

Then it is not difficult to show that f is an isomorphism from $(S_{1} + T_{1}, M_{1} □ N_{1})$ to $(S_{2} + T_{2}, M_{2} □ N_{2}) .$ □

Recall that the direct sum of two M-fuzzifying matroids $(E_{i}, I_{i}) (i = 1, 2)$ is defined in [39] as $(E_{1} + E_{2}, I_{1} \oplus I_{2}),$ where $(I_{1} \oplus I_{2}) (A) = I_{1} (A_{E_{1}}) \land I_{2} (A_{E_{2}})$ for all A ⊆ E₁ + E₂ . Clearly, $I_{1} \oplus I_{2} = I_{2} \oplus I_{1}$ and $R_{I_{1} \oplus I_{2}} (A) = R_{I_{1}} (A_{E_{1}}) + R_{I_{2}} (A_{E_{2}}),$ while the M-fuzzifying matroids $I_{1} □ I_{2}$ and $I_{2} □ I_{1}$ are almost never equal. More precisely, we have

Proposition 3.6. Let $(E_{i}, I_{i}) (i = 1, 2)$ be M-fuzzifying matroids on disjoint sets E_i . Then $I_{1} □ I_{2} = I_{2} □ I_{1}$ if and only if $R_{I_{1}} (E_{1}) \land ν_{I_{2}} (E_{2}) = R_{I_{2}} (E_{2}) \land ν_{I_{1}} (E_{1}) = \underline{0} .$

Proof. The sufficiency of the condition is obvious. To see the necessity, note first that $I_{1} □ I_{2} = I_{2} □ I_{1}$ means $R_{I_{1} □ I_{2}} = R_{I_{2} □ I_{1}},$ i.e.,

$\begin{matrix} R_{I_{1}} (A_{E_{1}}) + R_{I_{2}} (A_{E_{2}}) + λ_{I_{1}} (A_{E_{1}}) \land ν_{I_{2}} (A_{E_{2}}) \\ = & R_{I_{2}} (A_{E_{2}}) + R_{I_{1}} (A_{E_{1}}) + λ_{I_{2}} (A_{E_{2}}) \land ν_{I_{1}} (A_{E_{1}}), \end{matrix}$ for any A ⊆ E₁ + E₂ . By taking A = E₂ and A = E₁, respectively, we obtain $R_{I_{1}} (E_{1}) \land ν_{I_{2}} (E_{2}) = R_{I_{2}} (E_{2}) \land ν_{I_{1}} (E_{1}) = \underline{0}$ as required.□ It follows from Proposition 3.6 that if $I_{1} □ I_{2} = I_{2} □ I_{1},$ then $I_{1} □ I_{2} = I_{1} \oplus I_{2} .$

The next proposition shows that the free product of M-fuzzifying matroids is associative and commutes with the dual operator in a nice way.

Proposition 3.7. Let $(E_{i}, I_{i}) (i = 1, 2, 3)$ be M-fuzzifying matroids on disjoint sets E_i . Then

(i) $(I_{1} □ I_{2}) | E_{1} = I_{1}, (I_{1} □ I_{2}) / E_{1} = I_{2};$

(ii) $(I_{1} □ I_{2})^{*} = I_{2}^{*} □ I_{1}^{*};$ (iii) $(I_{1} □ I_{2}) □ I_{3} = I_{1} □ (I_{2} □ I_{3}) .$

Proof. (i) The proof is immediate from the definitions.

(ii) We show that $(I_{1} □ I_{2})^{*}$ and $I_{2}^{*} □ I_{1}^{*}$ have the same M-fuzzifying rank function. Note that by (5),

$\begin{matrix} λ_{I} (\bar{X}) & = & R_{I} (E) - R_{I} (\bar{X}) \\ = & \underline{| X |} - R_{I^{*}} (X) \\ = & ν_{I^{*}} (X), \end{matrix}$ for any X ⊆ E . Thus, for any A ⊆ E₁ + E₂, we have

$\begin{matrix} R_{(I_{1} □ I_{2})^{*}} (A) \\ = [\underline{| A |} + R_{I_{1} □ I_{2}} (\bar{A})] - R_{I_{1} □ I_{2}} (E_{1} + E_{2}) \\ = [\underline{| A_{E_{1}} + A_{E_{2}} |} + R_{I_{1}} ({\bar{A}}_{E_{1}}) + R_{I_{2}} ({\bar{A}}_{E_{2}}) \\ + λ_{I_{1}} ({\bar{A}}_{E_{1}}) \land ν_{I_{2}} ({\bar{A}}_{E_{2}})] - [R_{I_{1}} (E_{1}) + R_{I_{2}} (E_{2})] \\ = [\underline{| A_{E_{1}} |} + \underline{| A_{E_{2}} |} + R_{I_{1}} ({\bar{A}}_{E_{1}}) + R_{I_{2}} ({\bar{A}}_{E_{2}}) \\ + ν_{I_{1}^{*}} (A_{E_{1}}) \land λ_{I_{2}^{*}} (A_{E_{2}})] - [R_{I_{1}} (E_{1}) + R_{I_{2}} (E_{2})] \\ = [\underline{| A_{E_{1}} |} + R_{I_{1}} ({\bar{A}}_{E_{1}}) - R_{I_{1}} (E_{1})] + [\underline{| A_{E_{2}} |} \\ + R_{I_{2}} ({\bar{A}}_{E_{2}}) - R_{I_{2}} (E_{2})] + ν_{I_{1}^{*}} (A_{E_{1}}) \land λ_{I_{2}^{*}} (A_{E_{2}}) \\ = R_{I_{1}^{*}} (A_{E_{1}}) + R_{I_{2}^{*}} (A_{E_{2}}) + λ_{I_{2}^{*}} (A_{E_{2}}) \land ν_{I_{1}^{*}} (A_{E_{1}}) \\ = R_{I_{2}^{*} □ I_{1}^{*}} (A) . \end{matrix}$ (iii) Again we show that both sides have the same M-fuzzifying rank function. For any A ⊆ E₁ + E₂ + E₃, by (6) and (8), we have $\begin{matrix} R_{(I_{1} □ I_{2}) □ I_{3}} (A) \\ = R_{(I_{1} □ I_{2})} (A_{(E_{1} + E_{2})}) + R_{I_{3}} (A_{E_{3}}) \\ + λ_{I_{1} □ I_{2}} (A_{(E_{1} + E_{2})}) \land ν_{I_{3}} (A_{E_{3}}) \\ = R_{I_{1}} (A_{E_{1}}) + R_{I_{2}} (A_{E_{2}}) + λ_{I_{1}} (A_{E_{1}}) \land ν_{I_{2}} (A_{E_{2}}) \\ + R_{I_{3}} (A_{E_{3}}) + [λ_{I_{1}} (A_{E_{1}}) + λ_{I_{2}} (A_{E_{2}}) - λ_{I_{1}} (A_{E_{1}}) \\ \land ν_{I_{2}} (A_{E_{2}})] \land ν_{I_{3}} (A_{E_{3}}) \\ = R_{I_{1}} (A_{E_{1}}) + R_{I_{2}} (A_{E_{2}}) + R_{I_{3}} (A_{E_{3}}) + λ_{I_{1}} (A_{E_{1}}) \\ \land ν_{I_{2}} (A_{E_{2}}) + [λ_{I_{1}} (A_{E_{1}}) + λ_{I_{2}} (A_{E_{2}}) \\ - λ_{I_{1}} (A_{E_{1}}) \land ν_{I_{2}} (A_{E_{2}})] \land ν_{I_{3}} (A_{E_{3}}) . \end{matrix}$

Similarly, by (6) and (9) we have $\begin{matrix} R_{I_{1} □ (I_{2} □ I_{3})} (A) \\ = R_{I_{1}} (A_{E_{1}}) + R_{I_{2} □ I_{3}} (A_{(E_{2} + E_{3})}) + λ_{I_{1}} (A_{E_{1}}) \\ \land ν_{I_{2} □ I_{3}} (A_{(E_{2} + E_{3})}) \\ = R_{I_{1}} (A_{E_{1}}) + R_{I_{2}} (A_{E_{2}}) + R_{I_{3}} (A_{E_{3}}) + λ_{I_{2}} (A_{E_{2}}) \\ \land ν_{I_{3}} (A_{E_{3}}) + λ_{I_{1}} (A_{E_{1}}) \land [ν_{I_{2}} (A_{E_{2}}) + ν_{I_{3}} (A_{E_{3}}) \\ - λ_{I_{2}} (A_{E_{2}}) \land ν_{I_{3}} (A_{E_{3}})] . \end{matrix}$ Now, it follows immediately from equality (2) that $R_{(I_{1} □ I_{2}) □ I_{3}} (A) = R_{I_{1} □ (I_{2} □ I_{3})} (A) .$ □

Theorem 3.8. Let $(S, M), (T, N)$ and $(S + T, I)$ be M-fuzzifying matroids. Then the following statements are equivalent.

(i) $(S + T, I) = (S, M) □ (T, N) .$

(ii) For each $a \in P (M), I^{(a)} = M^{(a)} □ N^{(a)} .$

(iii) For each $a \in J (M), I_{[a]} = M_{[a]} □ N_{[a]} .$

Proof. (i)⇒(ii). For any a ∈ P (M) and A ⊆ S + T, we have

$\begin{matrix} R_{I^{(a)}} (A) \\ = R_{(M □ N)^{(a)}} (A) \\ = [R_{M} (A_{S}) + R_{N} (A_{T}) + λ_{M} (A_{S}) \land ν_{N} (A_{T})]^{(a)} \\ = R_{M} (A_{S})^{(a)} + R_{N} (A_{T})^{(a)} + λ_{M} (A_{S})^{(a)} \\ \land ν_{N} (A_{T})^{(a)} \\ = R_{M^{(a)}} (A_{S}) + R_{N^{(a)}} (A_{T}) + λ_{M^{(a)}} (A_{S}) \\ \land ν_{N^{(a)}} (A_{T}) \\ = R_{M^{(a)} □ N^{(a)}} (A) . \end{matrix}$

(ii)⇒(i). By conversing the order of the above calculation, we know $R_{I^{(a)}} (A) = R_{M^{(a)} □ N^{(a)}} (A) = R_{(M □ N)^{(a)}} (A),$ for each a ∈ P (M) . Thus by Proposition 3.6,

$\begin{matrix} R_{I} (A) & = & ⋀_{a \in P (M)} {a \lor R_{I^{(a)}} (A)} \\ = & ⋀_{a \in P (M)} {a \lor R_{(M □ N)^{(a)}} (A)} \\ = & R_{(M □ N)} (A), \end{matrix}$ and hence $(S + T, I) = (S, M) □ (T, N) .$

(ii)⇔(iii). Note that if M is a finite Boolean algebra (B ; ∨ , ∧ , ^′, 0, 1) and A ∈ M^X, then A^(a) = A_[a′] for all a ∈ P (M) , and A_[a] = A^(a′) for all a ∈ J (M) . It follows easily that (ii)⇔(iii). □

Example 3.9. Let S = {x, y} , T = {z} and let M = {⊥ , a, b, ⊤} , where a, b are incomparable. Define $M : 2^{S} \to M$ and $N : 2^{T} \to M$ by

$ℳ (A) = \{\begin{array}{c} ⊤, & if A \in {\emptyset, {x}}, \\ a, & if A = {y}, \\ ⊥, & if A = {x, y} \end{array}$

and

$N (A) = \{\begin{array}{c} ⊤, & if A = \emptyset, \\ b, & if A = {z}, \end{array}$

respectively. Then $(S, M)$ and $(T, N)$ are both M-fuzzifying matroids. Clearly, $M_{[a]} = {\emptyset, {x}, {y}},$ $M_{[b]} = {\emptyset, {x}},$ and $N_{[a]} = {\emptyset}, N_{[b]} = {\emptyset, {z}} .$ Let $(S, M) □ (T, N) = (S + T, I) .$ Then $I : 2^{S + T} \to M$ is given by

$ℐ (A) = \{\begin{array}{c} ⊤, & if A \in {\emptyset, {x}, {z}}, \\ a, & if A = {y}, \\ b, & if A = {x, z}, \\ ⊥, & if A \in {{x, y}, {y, z}, {x, y, z}} . \end{array}$

Hence $I_{[a]} = {\emptyset, {x}, {y}, {z}}, I_{[b]} = {\emptyset, {x}, {z},$ {x, z}} . Now one can check $I_{[a]} = M_{[a]} □ N_{[a]}$ and $I_{[b]} = M_{[b]} □ N_{[b]}$ as Theorem 3.8 claimed.

Definition 3.10. A nonempty M-fuzzifying matroid $(E, I)$ is called irreducible if any factorization of $(E, I)$ as a free product of M-fuzzifying matroids contains $(E, I)$ as a factor.

Example 3.11. Let E = {x, y} and M = {⊥ , a, b, ⊤} as be given in Example 3.9. Define $I : 2^{E} \to M$ by

$ℐ (A) = \{\begin{array}{c} ⊤, & if A = \emptyset, \\ a, & if A = {x}, \\ b, & if A = {y}, \\ ⊥, & if A = E . \end{array}$

Then the M-fuzzifying matroid $(E, I)$ is irreducible.

Remark 3.12.From [3] we know that no crisp matroid of size two is irreducible. So Example 3.11 shows that the finite Boolean algebra M plays an essential role when the irreducibility of M-fuzzifying matroids is considered.

Theorem 3.13. Let $(S + T, I)$ be an M-fuzzifying matroid. Then $I | S \oplus I / S \leq I \leq I | S □ I / S .$

Proof. It suffices to show that for any A ⊆ S + T, $R_{I | S \oplus I / S} (A) \leq R_{I} (A) \leq R_{I | S □ I / S} (A) .$

Since A_T ∪ S = A ∪ S, we have

$\begin{matrix} R_{I | S \oplus I / S} (A) \\ = R_{I | S} (A_{S}) + R_{I / S} (A_{T}) \\ = R_{I} (A_{S}) + [R_{I} (A_{T} \cup S) - R_{I} (S)] \\ = [R_{I} (A \cap S) + R_{I} (A \cup S)] - R_{I} (S) \\ \leq [R_{I} (A) + R_{I} (S)] - R_{I} (S) \\ = R_{I} (A) . \end{matrix}$

Moreover, by equality (7), we have

$\begin{matrix} R_{I | S □ I / S} (A) \\ = [R_{I | S} (S) + R_{I / S} (A_{T})] \land [\underline{| A_{T} |} + R_{I | S} (A_{S})] \\ = {R_{I} (S) + [R_{I} (A \cup S) - R_{I} (S)]} \land [\underline{| A_{T} |} \\ + R_{I} (A_{S})] \\ = R_{I} (A \cup S) \land [\underline{| A_{T} |} + R_{I} (A_{S})] \\ \geq R_{I} (A) . \end{matrix}$ This completes the proof. □

Remark 3.14. Theorem 3.13 shows that the identity map on S + T is an M-fuzzifying weak mapping [42] both from $(S + T, I)$ to $(S + T, I | S \oplus I / S)$ and from $(S + T, I | S □ I / S)$ to $(S + T, I) .$

4 Minors of free products

Since the minors of the free product of two crisp matroids can be described in terms of the matroid truncation operator and its dual, the Higgs lift operator [3], in this section we investigate the analogous notions for M-fuzzifying matroids.

Proposition 4.1. Let $(E, I)$ be an M-fuzzifying matroid and $α \in ℕ (M) .$ Define $R_{T^{α} I}$ and $R_{L^{α} I} : 2^{E} \to M$ by $R_{T^{α} I} (X) = R_{I} (X) \land [R_{I} (E) - R_{I} (E) \land α]$ (10)and $R_{L^{α} I} (X) = \underline{| X |} \land [R_{I} (X) + α],$ (11)for all X ⊆ E, respectively. Then both $R_{T^{α} I}$ and $R_{L^{α} I}$ are M-fuzzifying rank functions.

Proof. In both cases, (FR1) and (FR2) are evidently satisfied. The submodularity of $R_{T^{α} I}$ follows easily from Proposition 2.8(ii). To prove the submodularity of $R_{L^{α} I},$ let $μ = ν_{I} (E) - ν_{I} (E) \land α .$ Then

$\begin{matrix} R_{L^{α} I} (X) \\ = \underline{| X |} \land [R_{I} (X) + α] \\ = R_{I} (X) + ν_{I} (X) \land α \\ = R_{I} (X) + ν_{I} (X) \land ν_{I} (E) \land α \\ = \underline{| X |} \land [R_{I} (X) + ν_{I} (E) \land α] \\ = [\underline{| X |} + μ] \land [R_{I} (X) + ν_{I} (E)] - μ \\ = [\underline{| X |} + μ] \land [R_{I} (X) + (\underline{| X |} + \underline{| \bar{X} |} - R_{I} (E))] - μ \\ = [\underline{| X |} + μ \land R_{I^{*}} (\bar{X})] - μ . \end{matrix}$

Again the result follows from Proposition 2.8(ii) and the submodularity of $R_{I^{*}} .$ □

Based on Proposition 4.1, we can give the following definitions.

Definition 4.2. The M-fuzzifying matroids $(E, T^{α} I)$ corresponding to $R_{T^{α} I}$ is called the M-fuzzifying truncation of $(E, I) .$ That is, $T^{α} I$ is given by $T^{α} I (X) = R_{T^{α} I} (X) (| X |),$ (12)for all X ⊆ E .

Definition 4.3. The M-fuzzifying matroids $(E, L^{α} I)$ corresponding to $R_{L^{α} I}$ is called the M-fuzzifying Higgs lift of $(E, I) .$ That is, $L^{α} I$ is given by $L^{α} I (X) = R_{L^{α} I} (X) (| X |),$ (13)for all X ⊆ E .

Some basic properties of the M-fuzzifying truncation operator and the M-fuzzifying Higgs lift operator are given in the following proposition.

Proposition 4.4. Let $(E, I)$ be an M-fuzzifying matroid and U ⊆ E . Then for any $α \in ℕ (M),$

(i) $(T^{α} I)^{*} = L^{α} (I^{*});$

(ii) for any a ∈ P (M) , $(T^{α} I)^{(a)} = T^{α^{(a)}} (I^{(a)})$ and $(L^{α} I)^{(a)} = L^{α^{(a)}} (I^{(a)});$

(iii) $(T^{α} I) / U = T^{α} (I / U), (L^{α} I) | U = L^{α} (I | U);$

(iv) $T^{α} (I | U) = (T^{α + λ} I) | U, L^{α} (I / U) = (L^{α + ν} I) / U,$ where $λ = λ_{I} (U)$ and $ν = ν_{I} (U) .$

Proof. (i) For any X ⊆ E, we have

$\begin{matrix} R_{(T^{α} I)^{*}} (X) \\ = [\underline{| X |} + R_{T^{α} I} (\bar{X})] - R_{T^{α} I} (E) \\ = {\underline{| X |} + R_{I} (\bar{X}) \land [R_{I} (E) - R_{I} (E) \land α]} \\ - [R_{I} (E) - R_{I} (E) \land α] \\ = [\underline{| X |} + R_{I} (\bar{X})] \land [\underline{| X |} + R_{I} (E) - R_{I} (E) \land α] \\ - [R_{I} (E) - R_{I} (E) \land α] \\ = {\underline{| X |} + R_{I} (\bar{X}) - [R_{I} (E) - R_{I} (E) \land α]} \land \underline{| X |} \\ = {[\underline{| X |} + R_{I} (\bar{X}) + R_{I} (E) \land α] - R_{I} (E)} \land \underline{| X |} \\ = [R_{I} (E) \land α + R_{I^{*}} (X)] \land \underline{| X |} \\ = [R_{I} (E) + R_{I^{*}} (X)] \land [α + R_{I^{*}} (X)] \land \underline{| X |} \\ = [\underline{| X |} + R_{I} (\bar{X})] \land [α + R_{I^{*}} (X)] \land \underline{| X |} \\ = [α + R_{I^{*}} (X)] \land \underline{| X |} \\ = R_{L^{α} (I^{*})} (X) . \end{matrix}$ Since X is arbitrary, we have $(T^{α} I)^{*} = L^{α} (I^{*}) .$

(ii) We prove the first equality.

For any a ∈ P (M) and X ⊆ E, we have

$\begin{matrix} R_{(T^{α} I)^{(a)}} (X) \\ = {R_{I} (X) \land [R_{I} (E) - R_{I} (E) \land α]}^{(a)} \\ = R_{I} (X)^{(a)} \land [R_{I} (E) - R_{I} (E) \land α]^{(a)} \\ = R_{I^{(a)}} (X) \land [R_{I} (E)^{(a)} - R_{I} (E)^{(a)} \land α^{(a)}] \\ = R_{I^{(a)}} (X) \land [R_{I^{(a)}} (E) - R_{I^{(a)}} (E) \land α^{(a)}] \\ = R_{T^{α^{(a)}} (I^{(a)})} (X) . \end{matrix}$

(iii) We show $(T^{α} I) / U = T^{α} (I / U) .$

For any X ⊆ E - U, by (3), we have

$\begin{matrix} R_{(T^{α} I) / U} (X) \\ = R_{T^{α} I} (X \cup U) - R_{T^{α} I} (U) \\ = R_{I} (X \cup U) \land [R_{I} (E) - R_{I} (E) \land α] \\ - R_{I} (U) \land [R_{I} (E) - R_{I} (E) \land α] \\ = {R_{I} (E) \land [R_{I} (X \cup U) + α] - R_{I} (E) \land α} \end{matrix}$

$\begin{matrix} - {R_{I} (E) \land [R_{I} (U) + α] - R_{I} (E) \land α} \\ = R_{I} (E) \land [R_{I} (X \cup U) + α] - R_{I} (E) \\ \land [R_{I} (U) + α] \\ = R_{I} (E) \land [R_{I} (X \cup U) + α] - {R_{I} (U) \\ + [R_{I} (E) - R_{I} (U)] \land α} \\ = {R_{I} (E) \land [R_{I} (X \cup U) + α] - R_{I} (U)} \\ - [R_{I} (E) - R_{I} (U)] \land α \\ = {[R_{I} (E) - R_{I} (U)] \land [R_{I} (X \cup U) + α \\ - R_{I} (U)]} - [R_{I} (E) - R_{I} (U)] \land α \\ = [R_{I} (X \cup U) - R_{I} (U)] \land {R_{I} (E) - R_{I} (U) \\ - [R_{I} (E) - R_{I} (U)] \land α} \\ = R_{I / U} (X) \land [R_{I / U} (E - U) - R_{I / U} (E - U) \land α] \\ = R_{T^{α} (I / U)} (X) . \end{matrix}$

(iv) Again we prove the first equality.

By Proposition 2.8, we have

$\begin{matrix} R_{I} (E) + R_{I} (U) \land α \\ = [R_{I} (E) + R_{I} (U)] \land [R_{I} (E) + α] \\ = R_{I} (U) + R_{I} (E) \land [R_{I} (E) + α - R_{I} (U)] . \end{matrix}$ It follows that

$\begin{matrix} R_{I} (U) - R_{I} (U) \land α \\ = R_{I} (E) - R_{I} (E) \land [R_{I} (E) + α - R_{I} (U)] . \end{matrix}$

Thus, for any X ⊆ U, we have

$\begin{matrix} R_{T^{α} (I | U)} (X) \\ = R_{I | U} (X) \land [R_{I | U} (U) - R_{I | U} (U) \land α] \\ = R_{I} (X) \land [R_{I} (U) - R_{I} (U) \land α] \\ = R_{I} (X) \land {R_{I} (E) - R_{I} (E) \land [R_{I} (E) \\ + α - R_{I} (U)]} \\ = R_{I} (X) \land [R_{I} (E) - R_{I} (E) \land (α + λ)] \\ = R_{(T^{α + λ} I) | U} (X) . \end{matrix}$

So we conclude that $T^{α} (I | U) = (T^{α + λ} I) | U .$ □

Remark 4.5. By Proposition 4.4(iii), we can drop the parentheses in expressions $(T^{α} I) / U$ and $(L^{α} I) | U$ without introducing any ambiguity.

Proposition 4.6. If $I = M (S) □ N (T)$ and U ⊆ S + T, then $I | U = (M | U_{S}) □ (L^{λ} N | U_{T})$ and $I / U = (T^{ν} M / U_{S}) □ (N / U_{T}),$ where $λ = λ_{M} (U_{S})$ and $ν = ν_{N} (U_{T}) .$

Proof. Let us first consider the first equality. Note that for any X ⊆ U = U_S + U_T, X_S = X ∩ U_S and X_T = X ∩ U_T . By (7), we have

$\begin{matrix} R_{(M | U_{S}) □ (L^{λ} N | U_{T})} (X) \\ = [R_{M | U_{S}} (U_{S}) + R_{L^{λ} N | U_{T}} (X_{T})] \\ \land [\underline{| X_{T} |} + R_{M | U_{S}} (X_{S})] \\ = {R_{M} (U_{S}) + \underline{| X_{T} |} \land [R_{N | U_{T}} (X_{T}) + λ]} \\ \land [\underline{| X_{T} |} + R_{M} (X_{S})] \\ = {[R_{M} (U_{S}) + \underline{| X_{T} |}] \land [R_{N} (X_{T}) + R_{M} (U_{S}) \\ + λ]} \land [\underline{| X_{T} |} + R_{M} (X_{S})] \\ = [R_{N} (X_{T}) + R_{M} (S)] \land [\underline{| X_{T} |} + R_{M} (X_{S})] \\ = R_{I | U} (X) . \end{matrix}$

Thus we obtain the first equality.

Now, using the duality between the deletion and contraction operators (Proposition 2.19(ii)) and the duality between the M-fuzzifying truncation and M-fuzzifying Higgs lift operators (Proposition 4.4(i)), it follows from the first equality that

$\begin{matrix} I / U & = & (I^{*} | \bar{U})^{*} \\ = & [(N^{*} □ M^{*}) | \bar{U}]^{*} \\ = & [N^{*} | (T - U_{T}) □ (L^{α} M^{*}) | (S - U_{S})]^{*} \\ = & [(L^{α} M^{*}) | (S - U_{S})]^{*} □ [N^{*} | (T - U_{T})]^{*} \\ = & (T^{α} M / U_{S}) □ (N / U_{T}), \end{matrix}$ where $α = λ_{N^{*}} (T - U_{T}) = ν_{N} (U_{T}) = ν .$ □

Theorem 4.7. Let $I = M (S) □ N (T)$ and U ⊆ V ⊆ S + T . If $λ = λ_{M} (V_{S})$ and $ν = ν_{N} (U_{T})$ are comparable, then $I (U, V) = (T^{ν} M) (U_{S}, V_{S}) □ (L^{λ} N) (U_{T}, V_{T}) .$

Proof. Using Proposition 4.6 twice, we have

$\begin{matrix} I (U, V) & = & (I | V) / U \\ = & ((M | V_{S}) □ (L^{λ} N | V_{T})) / U \\ = & (T^{μ} (M | V_{S}) / U_{S}) □ ((L^{λ} N | V_{T}) / U_{T}) \\ = & (T^{μ} (M | V_{S}) / U_{S}) □ ((L^{λ} N) (U_{T}, V_{T})) \end{matrix}$ where $λ = λ_{M} (V_{S})$ and $μ = ν_{L^{λ} N | V_{T}} (U_{T}) .$

Now if λ ≤ ν, then $λ + R_{N} (U_{T}) \leq \underline{| U_{T} |} .$ Therefore, by Proposition 4.4(iv), $T^{μ} (M | V_{S}) = (T^{μ + λ} M) | V_{S},$ where $μ + λ = \underline{| U_{T} |} - \underline{| U_{T} |} \land [R_{N} (U_{T}) + λ] + λ = ν .$ Thus we obtain the desired expression for $I (U, V) .$ Otherwise, λ > ν, hence, $λ + R_{N} (U_{T}) > \underline{| U_{T} |}$ and $R_{M} (S) - ν > R_{M} (V_{S}) .$ Thus $μ = \underline{0},$ and for any X ⊆ V_S,

$\begin{matrix} R_{(T^{ν} M) | V_{S}} (X) \\ = R_{M} (X) \land [R_{M} (S) - R_{M} (S) \land ν] \\ = R_{M} (X) \land [R_{M} (S) - ν] \\ = R_{M} (X) . \end{matrix}$

This means that $(T^{ν} M) | V_{S} = M | V_{S} = T^{μ} (M | V_{S}) .$ Again we obtain the desired expression for $I (U, V) .$ □

As a special case of Theorem 4.7, for all A ⊆ S and B ⊆ T, we have $I (A, A \cup T) = L^{λ} N and I (B, B \cup S) = T^{ν} M,$ where $λ = λ_{M} (A)$ and $ν = ν_{N} (B) .$

More particularly, we have $I | T = I (\emptyset, T) = L^{R_{M} (S)} N$ and $I / T = I (T, T \cup S) = T^{\underline{| T |} - R_{N} (T)} M .$

The following theorem describes how the M-fuzzifying truncation and M-fuzzifying lift operators interact with the free product.

Theorem 4.8. Let $(S, M)$ and $(T, N)$ be M-fuzzifying matroids and let $α \in ℕ (M) .$ Then

$T^{α} (ℳ □ N) = \{\begin{array}{c} ℳ □ T^{α} N, & α \leq ρ, \\ T^{α - ρ} ℳ □ T^{ρ} N, & α > ρ \end{array}$

and

$L^{α} (ℳ □ N) = \{\begin{array}{c} L^{α} ℳ □ N, & α \leq ν, \\ L^{ν} ℳ □ L^{α - ν} N, & α > ν, \end{array} n$

where $ρ = R_{N} (T)$ and $ν = ν_{M} (S) .$

Proof. The proof is straightforward.□

5 Conclusions and discussions

There are several remarkable points to note about the free product of M-fuzzifying matroids. First, one can check the results obtained are degenerated to that for crisp matroids when M = {⊥ , ⊤} and are therefore reasonable generalizations. However, the free product of M-fuzzifying matroids seems more complicate (see Remark 3.12). Second, it was proved in [3] that crisp matroids, which are irreducible with respect to free product are characterized in terms of cyclic flats, and more importantly, a unique factorization theorem (Theorem 6.17 in [3]) was proved. We do not know whether there exist similar results for M-fuzzifying matroids. Finally, according to Schmitt and Crapo [4, 25], more algebra structures associated with M-fuzzifying matroids such as Hopf algebra structure can be considered.

References

Brickell

E.F.

and Davenport

D.M.

, On the classification of ideal secret sharing schemes, Journal of Cryptology 4 (1991), 123–134.

Crapo

and Schmitt

, The free product of matroids, European Journal of Combinatorics 26 (2005), 1060–1065.

Crapo

and Schmitt

, A unique factorization theorem for matroids, Journal of Combinatorial Theory, Series A 112 (2005), 222–249.

Crapo

and Schmitt

, A free subalgebra of the algebra of matroids, European Journal of Combinatorics 26 (2005), 1066–1085.

Dougherty

, Freiling

and Zeger

, Networks, matroids, and non-Shannon information inequalities, IEEE Transactions on Information Theory 53 (2007), 1949–1969.

Dougherty

, Freiling

and Zeger

, Network coding and matroid theory, Proceedings of the IEEE 99 (2011), 388–405.

El Rouayheb

, Sprintson

and Georghiades

, On the index coding problem and its relation to network coding and matroid theory, IEEE Transactions on information theory 56 (2010), 3187–3195.

Gale

, Optimal assignments in an ordered set: An application of matroid theory, Journal of Combinatorial Theory 4 (1968), 176–180.

Gierz

et al., A Compendium of Continuous Lattices, Springer-Verlag, Berlin, 1980.

10.

Goetschel

and Voxman

, Fuzzy matroids, Fuzzy Sets and Systems 27 (1988), 291–302.

11.

Grätzer

, Lattice Theory: Foundation, Springer, Basel, 2011.

12.

Greene

, Weight enumeration and the geometry of linear codes, Studies in Applied Mathematics 55 (1976), 119–128.

13.

Huang

H.L.

and Shi

F.G.

, L-fuzzy numbers and their properties, Information Sciences 178 (2008), 1141–1151.

14.

Kasperski

and Zieliński

, On combinatorial optimization problems on matroids with uncertain weights, European Journal of Operational Research 177 (2007), 851–864.

15.

Lee

and Ryan

, Matroid applications and algorithms, ORSA Journal on Computing 4 (1992), 70–98.

16.

E.Q.

and Shi

F.G.

, Minors of M-fuzzifying matroids, Journal of Intelligent & Fuzzy Systems 28 (2015), 1213–1224.

17.

Lian

and Xin

, The nullities for M-fuzzifying matroids, Applied Mathematics Letters 25 (2012), 279–286.

18.

MacWilliams

F.J.

, A theorem on the distribution of weights in a systematic code, Bell System Technology Journal 42 (1963), 79–94.

19.

Martí-Farré

and Padró

, On secret sharing schemes, matroids and polymatroids, Fourth IACR Theory of Cryptography Conference TCC 2007, Lecture Notes in Computer Science 4392 (2007), 273–290.

20.

Matúš

, Matroid representations by partitions, Discrete Mathematics 203 (1999), 169–194.

21.

Negoita

C.V.

, Ralescu

D.A.

, Applications of Fuzzy Sets to Systems Analysis, Interdisciplinary Systems Research Series, Vol. 11, Birkhauser, Basel, Stuttgart and Halsted Press, New York, 1975.

22.

Oxley

J.G.

, Matroid Theory, Second edition, Oxford University Press, New York, 2011.

23.

Rado

, Note on independence functions, Proceedings of the London Mathematical Society 7 (1957), 300–320.

24.

Rocacher

and Bosc

, The set of fuzzy rational numbers and flexible querying, Fuzzy Sets and Systems 155 (2005), 317–339.

25.

Schmitt

, Incidence Hopf algebras, Journal of Pure and Applied Algebra 96 (1994), 299–330.

26.

Seymour

P.D.

, On secret-sharing matroids, Journal of Combinatorial Theory, Series B 56 (1992), 69–73.

27.

Shi

F.G.

, Theory of L_β-nested sets and L_α-nested sets and its applications, Fuzzy Systems and Mathematics 9 (1995), 65–72. (in Chinese).

28.

Shi

F.G.

, L-fuzzy sets and prime element nested sets, J Mathematical Research and Exposition 16 (1996), 398–402. (in Chinese).

29.

Shi

F.G.

, Theory of molecular nested sets and its applications, J Yantai Teachers University (Natural Science) 12 (1996), 33–36. (in Chinese).

30.

Shi

F.G.

, L-fuzzy relation and L-fuzzy subgroup, Journal of Fuzzy Mathematics 8 (2000), 491–499.

31.

Shi

F.G.

, A new approach to the fuzzification of matroids, Fuzzy Sets and Systems 160 (2009), 696–705.

32.

Shi

F.G.

, (L, M)-fuzzy matroids, Fuzzy Sets and Systems 160 (2009), 2387–2400.

33.

Shi

F.G.

and Wang

, Characterizations and applications of M-fuzzifying matroids, Journal of Intelligent & Fuzzy Systems 25 (2013), 919–930.

34.

Simons

and Ashikhmin

, Almost affine codes, Designs, Codes and Cryptography 14 (1998), 179–197.

35.

Wang

and Shi

F.G.

, Characterization of M-fuzzifying matroids by M-fuzzifying closure operators, Iranian Journal of Fuzzy Systems 7 (2010), 47–58.

36.

Welsh

D.J.A.

, Matroid Theory, Academic Press Inc. LTD., London, 1976.

37.

Welsh

D.J.A.

, A bound for the number of matroids, Journal of Combinatorial Theory 6 (1969), 313–316.

38.

Whitney

, On the abstract properties of linear dependence, American Journal of Mathematics 57 (1935), 509–533.

39.

Xin

, Categorical properties of (L, M)-fuzzy matroids, Beijing: Beijing Institute of Technology, 2010.

40.

Xin

and Shi

F.G.

, M-fuzzifying bases, Proyecciones Journal of Mathematics 28 (2009), 271–283.

41.

Xin

and Shi

F.G.

, M-fuzzifying derived operators and difference derived operators, Iranian Journal of Fuzzy Systems 7 (2010), 71–81.

42.

Xin

and Shi

F.G.

, Categories of bi-fuzzy pre-matroids, Computers and Mathematics with Applications 59 (2010), 1548–1558.

43.

Yao

and Shi

F.G.

, Bases axioms and circuits axioms for fuzzifying matroids, Fuzzy Sets and Systems 161 (2010), 3155–3165.

44.

Ying

M.S.

, A new approach for fuzzy topology(I), Fuzzy Sets and Systems 39 (1991), 303–321.