key: cord-0060785-v1xdkjw9
authors: Nishizawa, Koki; Yasuda, Koji; Furusawa, Hitoshi
title: Preorders, Partial Semigroups, and Quantales
date: 2020-04-01
journal: Relational and Algebraic Methods in Computer Science
DOI: 10.1007/978-3-030-43520-2_15
sha: 08328c5c5e3b6e5bd3260d02c188a2a971d04220
doc_id: 60785
cord_uid: v1xdkjw9

It is known that each powerset quantale is embeddable into some relational unital quantale whose underlying set is the powerset of some preorder. An aim of this paper is to understand the relational embedding as a relationship between quantales and preorders. For that, this paper introduces the notion of weak preorders, a functor from the category of weak preorders to the category of partial semigroups, and a functor from the category of partial semigroups to the category of quantales and lax homomorphisms. By using these two functors, this paper shows a correspondence among four classes of weak preorders (including the class of ordinary preorders), four classes of partial semigroups, and four classes of quantales. As a corollary of the correspondence, we can understand the relational embedding map as a natural transformation between functors onto certain category of quantales.

A unital quantale is defined to be a complete join semilattice together with a monoid structure satisfying the distributive laws. It was introduced by Conway under the name S-algebras [1] . A relational example of unital quantale is a powerset ℘(A × A), which is the set of all binary relations on a set A and whose monoid structure is given by relational composition and the identity relation. We call it a relational quantale. A relational quantales play an important role in computer science, for example, it is a model for the semantics of non-deterministic while-programs [2, 3] .

In the paper [4] , the relational representation theorem for powerset quantales is shown, where a powerset quantale is defined to be a unital quantale whose complete join semilattice part is isomorphic to the powerset of some set. The relational representation is given as an embedding (i.e., injective unital homomorphism) η from a powerset quantale ℘(A) to some relational quantale ℘(A × A). The paper [5] includes this embedding η in the special case where A is a free monoid.

( In general, the representation theorem helps to understand the algebra, not only that, but it is meaningful in the field of computer science, because it suggests the possibility of representing infinite entities with finite data. Embedding from power set quantale into binary relations also shows the possibility that infinite entities can be represented by finite data. For example, as an application example of the above η : ℘(N) → ℘ (N × N) , the finite set {2} is representing η({2}), i.e., the infinite binary relation (or the infinite directed graph) {(m, m+2) | m ∈ N}. In addition, the multiplication in the quantale can replace the relational composition operation. This shows the same effect as the correspondence between linear mapping and its matrix representation. Analyzing quantales' representation theorem is meaningful in the field of computer science.

The definition of relational quantale is extendable for the powerset ℘(≤) of each preorder ≤, where a preorder is regarded as a subset of A × A satisfying reflexivity and transitivity. An aim of this paper is to understand the relational embedding η as a relationship between quantales and preorders.

Since direct construction of a relationship between quantales and preorders is not very obvious, this paper introduces the notion of weak preorder and partial semigroup as a relaxation of preorder and semigroup, respectively. We also introduce the notion of lax homomorphism between (not unital) quantales as a relaxation of ordinary homomorphism between quantales. And, we give a functor comp from the category WPreOrd of weak preorders to the category PSG of partial semigroups, and a contravariant functor ℘ from PSG to the category Qt lax of quantales and lax homomorphisms. Moreover, we also define three categories (including the category UQt of unital quantales and unital homomorphisms) as restrictions of Qt lax , in a step-by-step manner. By proving the following six pullbacks in Cat, we show the relationship among orders, semigroups, and quantales.

Recall that a pullback of F :

By using these functors, we understand the relational embedding map η as a natural transformation. This paper is organized as follows. Section 2 defines the notions of weak preorder, partial semigroup, and lax homomorphism between quantales. In Sect. 3, we restrict arrows between quantales to ordinary homomorphisms and give the corresponding classes of arrows between weak preorders or partial semigroups. Section 4 extends quantales to unital quantales and give the corresponding extension of weak preorders or partial semigroups. In Sect. 5, we introduce sufficient classes to induce the relational embedding. Section 6 summarizes this work and discusses about future work.

In this section, we define the notions of weak preorder, partial semigroup, and lax homomorphism between quantales. By using the three notions, we give three categories and two functors among them.

First, we recall the definition of quantale [6] [7] [8] and define the notion of lax homomorphism between quantales.

A quantale is defined to be a tuple (Q, ≤, , ) such that 1. (Q, ) is a semigroup (i.e., a binary function on Q that is associative), 2. (Q, ≤, ) is a complete join semilattice (i.e., a partially ordered set (Q, ≤) has the least upper bound S for arbitrary subset S of Q), 3. ( S) q = {s q|s ∈ S} for each element q and each subset S of Q, and 4. q ( S) = {q s|s ∈ S} for each element q and each subset S of Q.

For two quantales (Q, ≤, , ), (Q , ≤ , , ), a lax homomorphism from (Q, ≤, , ) to (Q , ≤ , , ) is defined to be a map f : Q → Q such that

Lax homomorphisms between quantales are closed under composition as maps. The identity map is a lax homomorphism on a quantale. Therefore, we can define the category whose objects are quantales and whose arrows are lax homomorphisms between them and we write Qt lax for it.

As the sufficient structure to construct in the powerset case Q = ℘(X), we define the notion of partial semigroup. Definition 2 (partial semigroup and homomorphism). A partial semigroup is defined to be a tuple (X, ·) such that 1. X is a set, 2. · is a partial binary function on X (i.e., x · y may be undefined), 3. x · y and (x · y) · z are defined if and only if y · z and x · (y · z) are defined for

x, y, z ∈ X, and 4. (x · y) · z = x · (y · z) if they are defined.

For partial semigroups (X, ·), (X , · ), a homomorphism from (X, ·) to (X , · ) is defined to be a map f : X → X such that

Homomorphisms between partial semigroups are closed under composition as maps. The identity map is a homomorphism on a partial semigroup. We write PSG for the category whose objects are partial semigroups and whose arrows are homomorphisms between them. Next, we present the construction of a powerset (not unital) quantale from a partial semigroup. Here, we denote by the binary map 

Proof. Take an arrow f : (X, ·) → (X , · ) in PSG. ℘(f ) preserves . Take

] ℘(f )(S 2 ). There are s 1 , s 2 ∈ X satisfying f (s 1 ) ∈ S 1 , f (s 2 ) ∈ S 2 , and x = s 1 · s 2 . They satisfy

. ℘ preserves composition and identities.

A transitive relation R on a set X forms a partial semigroup (R, ; ) with the same ; as Example 2. However, we define weak preorders, as a stronger notion than transitive relations and a weaker notion than preorders.

A binary relation R ⊆ X ×X on X is called a weak preorder on X, if R is transitive and R satisfies ∀x ∈ X.∃y ∈ X.(x, y) ∈ R or (y, x) ∈ R. A weak preordered set is defined to be a tuple (X, R) of a set X and a weak preorder R on X.

Example 3. Let N be the set of all natural numbers (including 0). We write m < N n when m is less than n as natural numbers and write m ≤ N n when m < N n or m = n. We also regard < N as the set of (m, n) satisfying m < N n and regard ≤ N as the set of (m, n) satisfying m ≤ N n.

≤ N is a preorder on N. On the other hand, < N is not a preorder, but a weak preorder on N.

Monotone maps between weak preordered sets are closed under composition as maps. The identity map is a monotone map on a weak preordered set. Therefore, weak preordered sets and monotone maps between them form a category. We write WPreOrd for it.

Next, we present the construction of a partial semigroup from a weak preordered set.

The following data form a functor comp : WPreOrd → PSG.

Proof. Take an arrow f :

. comp preserves composition and identities. 

In this section, we recall the category of quantales and ordinary homomorphisms of quantales. It is a subcategory of Qt lax in Sect. 2. We study which maps between partial semigroups correspond to homomorphisms between quantales, and which maps between weak preorders correspond to those maps between partial semigroups.

We write Qt for the subcategory of Qt lax , whose arrows are homomorphisms.

Next, we introduce the additional condition for homomorphisms between partial semigroups which corresponds to homomorphisms between quantales. We call it the dividing condition.

Dividing maps between partial semigroups are closed under composition as maps. The identity map is dividing. We write PSG div for the subcategory of PSG, whose arrows are only dividing maps.

Next, we show that dividing maps between partial semigroups correspond to homomorphisms between quantales.

For an arrow f : (X, ·) → (X , · ) in PSG, the following statements are equivalent. in Cat (Fig. 1) .

Next, we introduce the additional condition for monotone maps between weak preorders which corresponds to dividing maps between partial semigroups. The condition is the intermediate value property.

Monotone maps satisfying the intermediate value property between weak preordered sets are closed under composition as maps. The identity map on a weak preordered set satisfies the intermediate value property. We write WPreOrd int for the subcategory of WPreOrd, whose arrows are only arrows satisfying the intermediate value property.

Next, we show that monotone maps satisfying the intermediate value property correspond to dividing maps between partial semigroups.

Theorem 4. For f : (X, R) → (X , R ) in WPreOrd, the following statements are equivalent.

Corollary 2. Let comp : WPreOrd int → PSG div be the restriction of comp : WPreOrd → PSG. The forgetful functor forget : WPreOrd int → WPreOrd and comp : WPreOrd int → PSG div is a pullback of comp : WPreOrd → PSG and the forgetful functor forget : PSG div → PSG in Cat (Fig. 1) . Example 5. In WPreOrd int , the map plus1(n) def = n + 1 is an arrow from (N, < N ) to (N, < N ), but not to (N, ≤ N ), since 1 ≤ N 1 ≤ N 2 but not 0 < N 0.

For the same reason, the map comp(plus1)(m, n) = (m + 1, n + 1) is a dividing map from (< N , ; ) to (< N , ; ), but not to (≤ N , ; ) .

Similarly, the map ℘(comp (plus1) 

In this section, we recall the definition of unital quantale. We show which weak preorders and which partial semigroups correspond to unital quantales. We also study the correspondence among their maps.

A unital quantale is defined to be a tuple (Q, ≤, , , 1) such that 1. (Q, ≤, , ) is a quantale, and 2. 1 ∈ Q satisfies for each q ∈ Q, 1 q = q = q 1 (1 is called the unit of ).

For unital quantales (Q, ≤, , , 1), (Q , ≤ , , , 1 ) , a unital homomorphism from (Q, ≤, , , 1) to (Q , ≤ , , , 1 ) is defined to be a homomorphism from

Unital homomorphisms between unital quantales are closed under composition as maps. The identity map is a unital homomorphism on a unital quantale. We write UQt for the category whose objects are unital quantales and whose arrows are unital homomorphisms between them.

Next, we introduce the additional structure for a partial semigroup which corresponds to the unit of the multiplication of a quantale. We call the structure a unital subset.

A unital subset of a partial semigroup (X, ·) is defined to be a subset U ⊆ X such that

for any x ∈ X, there exists u ∈ U such that u · x is defined, and 4. for any x ∈ X, there exists u ∈ U such that x · u is defined.

For each partial semigroup (X, ·), if U and U are unital subsets of (X, ·), then U = U .

Proof. Assume that (X, ·) is a partial semigroup and that U and U are unital subsets of (X, ·). Take an element u of U . Since U is a unital subset of (X, ·), there exists u ∈ U such that u · u is defined and u · u = u. Since U is also a unital subset of (X, ·) and u ∈ U , u · u is equal to u ∈ U . Therefore, U ⊆ U . The converse is proven, similarly.

A unital partial semigroup is defined to be a tuple (X, ·, U) such that 1. (X, ·) is a partial semigroup, and 2. U is the unital subset of (X, ·).

For unital partial semigroups (X, ·, U), (X , · , U ), a dividing map from (X, ·, U) to (X , · , U ) is defined to be an arrow f : (X, ·) → (X , · ) ∈ PSG div such that for any x ∈ X, it satisfies x ∈ U if and only if f (x) ∈ U .

Note that a unital partial semigroup is not equal to a partial monoid, which is a base structure of an effect algebra [9] , since the unital subset of a unital partial semigroup is not always singleton.

Dividing maps between unital partial semigroups are closed under composition as maps. The identity map is dividing on a unital partial semigroup. We write UPSG div whose objects are unital partial semigroups and whose arrows are dividing maps between them. Example 6. The set of all arrows of a small category forms the unital partial semigroup whose partial binary operator is the composition of arrows and whose unital subset is the set of identities. On the other hand, a unital partial semigroup is not always regarded as the set of arrows. For example, ({0, 1}, ·, {1}) is a unital partial semigroup, when 0 · 1 = 1 · 0 = 0, 1 · 1 = 1 and 0 · 0 is undefined. To regard {1} as the set of all identities, however, the category can have only one object, and then 0 · 0 must be defined. Therefore, a unital partial semigroup is not equal to a poloid [10] . If x · y and y · z are defined in a poloid, then (x · y) · z must be defined. In this unital partial semigroup ({0, 1}, ·, {1}), however, 0 · 1 and 1 · 0 are defined, but (0 · 1) · 0 is undefined.

Next, we show that a unital partial semigroup corresponds to a unital quantale.

Theorem 5. For a partial semigroup (X, ·) and U ⊆ X, the following statements are equivalent. 

For any x ∈ X, there exists u ∈ U such that x · u is defined, since {x} ⊆ {x} [[·]] U . Therefore, U is the unital subset of (X, ·).

Next, we show that a dividing map between unital partial semigroups corresponds to a unital homomorphism between unital quantales. Theorem 6. For unital partial semigroups (X, ·, U), (X , · , U ) and f : (X, ·) → (X , · ) in PSG div , the following statements are equivalent. (Fig. 1) .

Next, we show that a preordered set which corresponds to a unital partial semigroup. A preordered set is defined to be a tuple (X, ≤) of a set X and a preorder ≤ on X, that is to say, ≤ is reflexive and transitive. We write x ≤ y for (x, y) ∈≤.

is defined, then x = y and (x, x); (y, z) = (y, z). For any x ≤ y, (x, x); (x, y) is defined and (x, x) ∈ X . The remaining condition is proven similarly.

(⇐=) Take x ∈ X. There is y ∈ X such that (x, y) ∈ R or (y, x) ∈ R. When (x, y) ∈ R, there is (u, u ) ∈ X such that (u, u ); (x, y) is defined and equal to (x, y). Then, u = x = u . When (y, x) ∈ R, there is (u, u ) ∈ X such that (y, x); (u, u ) is defined and equal to (y, x). Then, u = x = u . In both cases, (x, x) is equal to (u, u ) ∈ X ⊆ R. Therefore, R is reflexive.

Next, we introduce the condition for maps between preordered sets corresponds to dividing maps between unital partial semigroups. The condition is monotone, satisfying the intermediate value property, and Id-reflecting.

Id-reflecting maps satisfying the intermediate value property between preordered sets are closed under composition as maps. The identity map on a preordered set is an Id-reflecting map satisfying the intermediate value property. Therefore, we write PreOrd int,idref for the category whose objects are preordered sets and whose arrows are Id-reflecting maps satisfying the intermediate value property between them.

Next, we show that Id-reflecting maps satisfying the intermediate value property correspond to dividing maps between unital partial semigroups. f(y) ) ∈ X , then x = y and (x, y) ∈ X , since f (x) = f (y) and f is Id-reflecting. Therefore, we have (x, y) ∈ X if and only if

Since f is a dividing maps between unital partial semigroups, x, y satisfy (x, y) ∈ X and x = y. Therefore, f is Idreflecting.

Let comp : PreOrd int,idref → UPSG div be the extension of comp : WPreOrd int → PSG div by comp(X, ≤) = (≤, ; , X ). The forgetful functor forget : PreOrd int,idref → WPreOrd int and comp : PreOrd int,idref → UPSG div is a pullback of comp : WPreOrd int → PSG div and the forgetful functor forget : UPSG div → PSG div in Cat (Fig. 1 ). Example 7. (N, < N ) is an object of WPreOrd int , but not of PreOrd int,idref , since < N is not reflexive. For the same reason, comp(N, < N ) = (< N , ; ) has no unital subset.

The map plus1(n) def = n + 1 is Id-reflecting on (N, ≤ N ) in PreOrd int,idref , since m ≤ n and m + 1 = n + 1 imply m = n. For the same reason, the map comp(plus1)(m, n) = (m + 1, n + 1) is a dividing map on (≤ N , ; , N ) in UPSG div .

On the other hand, the map zero(n) def = 0 is not Id-reflecting on (N, ≤ N ) in PreOrd int,idref , since 0 ≤ 1 and zero(0) = zero(1) but not 0 = 1. For the same reason, the map comp(zero)(m, n) = (0, 0) is not a dividing map on (≤ N , ; , N ) in UPSG div .

In this section, we define a subcategory of UPSG div and the corresponding subcategory of PreOrd int,idref . Between them, we give a functor suff in the converse direction of comp. Moreover, we give the natural transformation− : comp •suff → Id which induces the relational embedding maps mentioned in Sect. 1.

A unital partial semigroup (X, ·, U) is called diagonal, if (X, ·) is diagonal. We write DUPSG div for the subcategory of UPSG div whose objects are only diagonal unital partial semigroups.

Definition 13 (interval-total preorder). A preorder ≤ on X is called interval-total, if x ≤ y ≤ z and x ≤ y ≤ z imply y ≤ y or y ≤ y for each x, y, y , z ∈ X. A preordered set (X, ≤) is called an interval-totally preordered set, if ≤ is interval-total. We write ITPreOrd int,idref for the subcategory of PreOrd int,idref whose objects are only interval-totally preordered sets. Proof. (=⇒) (1) Assume that w, x, y, z ∈≤ satisfy w; x = y; z. There exists a, b, b , c ∈ X such that w = (a, b), x = (b, c), y = (a, b ), and z = (b , c), that is to say,

(2) Assume that w, x, y ∈≤ satisfy w; x = w; y. There exists a, b, c ∈ X such that w = (a, b), x = (b, c), and y = (b, c) . Therefore, x = y.

(⇐=) Assume that (≤, ; , X ) is diagonal. Assume that x, y, y , z ∈ X satisfy x ≤ y ≤ z and x ≤ y ≤ z. Then, we have that (x, y); (y, z) = (x, z) = (x, y ); (y , z). Since (≤, ; , X ) is diagonal, there exists v ≤ w such that (x, y ) ; (v, w) = (x, y) or (x, y); (v, w) = (x, y ). If (x, y ); (v, w) = (x, y), then y = v ≤ w = y. On the other hand, if (x, y); (v, w) = (x, y ), then y = v ≤ w = y . Therefore, ≤ is interval-total. Corollary 5. Let comp : ITPreOrd int,idref → DUPSG div be the restriction of comp : PreOrd int,idref → UPSG div . The forgetful functor forget : ITPreOrd int,idref → PreOrd int,idref and comp : ITPreOrd int,idref → DUPSG div is a pullback of comp : PreOrd int,idref → UPSG div and the forgetful functor forget : DUPSG div → UPSG div in Cat (Fig. 1) .

Next, we give a functor suff in the converse direction of comp. Theorem 10. The following data form a functor suff from DUPSG div to ITPreOrd int,idref .

-For an object (X, ·, U), suff (X, ·, U)

-For an arrow f : (X, ·, U) → (X , · , U ), suff (f ): (X, ≤ · ) → (X , ≤ · ) is f . Proof. (object part) Assume that (X, ·, U) is a diagonal unital partial semigroup. Since (X, ·, U) is a unital partial semigroup, ≤ · is transitive and reflexive. If x ≤ · y ≤ · z and x ≤ · y ≤ · z, then there exist v, w such that y · v = z = y · w. Since (X, ·, U) is diagonal, there exists u such that y = y · u or y = y · u, that is to say, y ≤ · y or y ≤ · y . Therefore, ≤ · is interval-total.

(arrow part) Take f :

We show that suff (f ) = f is Id-reflecting. Assume that x ≤ · y and f (x) = f (y). There exist z ∈ X such that x · z = y. Therefore,

Since f is a dividing map between unital partial semigroups, f (z) = u ∈ U implies z ∈ U and x = x · z = y. Therefore, f is Id-reflecting.

We show that f satisfies the intermediate value property. Assume that x ≤ · y, f (x) ≤ · z , and z ≤ · f (y). There exist u ∈ X, v , w ∈ X such that x · u = y, f (x) · v = z , and z · w = f (y). Since f is dividing, there exist w, z ∈ X such that f (w) = w , f (z) = z , and z · w = y. Therefore, z ≤ · y. Since f is dividing and

suff (f ) preserves composition and identities.

We call the following operation− the partial subtraction on a diagonal unital partial semigroup. Theorem 11. The following data form a natural transformation− : comp • suff → Id : DUPSG div → DUPSG div .

-For an object (X, ·, U), its component− :

Proof. (well-definedness) For y ≤ · x, there exists z ∈ X such that y · z = x.

(homomorphism of PSG) Assume that (z, y); (x, w) is defined, z ≤ · y, and x ≤ · w. Then, z ≤ · y = x and w is representable as w = x · (w−x) = (z · (x−z)) · (w−x). Therefore, (x−z) · (w−x) and z · ((x−z) · (w−x)) are also defined and

(dividing) Assume that x ≤ · w and w−x = z · y. Then, x · (w−x) is defined and equal to w. Therefore, x · (z · y), x · z, and (x · z) · y are also defined. Since (x · z) · y = x · (z · y) = x · (w−x) = w, they satisfy x · z ≤ · w and w−(x · z) = y. Since x · z is defined, obviously x ≤ · x · z and (x · z)−x = z. (x, x · z); (x · z, w) is defined and equal to (x, w).

(unital) For y ≤ · x, we show (y, x) ∈ X ⇐⇒ x−y ∈ U . Assume (y, x) ∈ X . Then, x = y. There exists u ∈ U satisfying x · u = x. Since (X, ·, U) is diagonal and x·(x−x) = x = x·u, they satisfy x−y = x−x = u ∈ U . Conversely, assume x−y ∈ U . y · (x−y) is defined and equal to x. By the definition of unital subset, y · (x−y) = y. Therefore, x = y · (x−y) = y and (x, y) ∈ X .

(naturality) Assume f is an arrow f : (X, ·, U) → (X , · , U ) in DUPSG div .

Example 8. (N, +, 0) is a diagonal unital partial semigroup. Then, the intervaltotally preordered set suff (N, +, 0) is equal to (N, ≤ N ) , since x ≤ N y ⇔ ∃z ∈ N.x + z = y. Therefore, comp(suff (N, +, 0)) = (≤ N , ; ) is also a diagonal unital partial semigroup. The partial subtraction− : (≤ N , ; ) → (N, +, 0) sends x ≤ N y to y − x. We define the subcategory DPQt of UQt, whose object is a diagonal powerset quantale.

Theorem 12. For a unital partial semigroup (X, ·, U), the following statements are equivalent. The forgetful functor forget : DUPSG div → UPSG div and ℘ : DUPSG div → DPQt op is a pullback of ℘ : UPSG div → UQt op and the forgetful functor forget : DPQt op → UQt op in Cat (Fig. 1) . For any S 1 , S 2 ⊆ X, the distributivity of also implies S 1 S 2 = {{x} {y} | x ∈ S 1 , y ∈ S 2 } = {x · y | x ∈ S 1 , y ∈ S 2 is defined} = S 1 [[·]] S 2 . Therefore, (X, ·) is the partial semigroup satisfying ℘(X, ·) = (℘(X), ⊆, , ). By Theorem 5, (X, ·, 1) is the unital partial semigroup satisfying ℘(X, ·, 1) = (Q, ≤, , , 1). By Theorem 12, (X, ·, 1) is diagonal, since (℘(X), ⊆, , [[·]], 1) is a diagonal powerset quantale. 

This paper has introduced the notions of weak preorder, partial semigroup, lax homomorphism between quantales. And, we have shown three correspondences by proving the six pullbacks in Fig. 1. 1. The correspondence among a monotone map satisfying the intermediate value property between weak preordered sets, a dividing map between partial semigroups, and a homomorphism between quantales 2. The correspondence among a preordered set, a unital partial semigroup, and a unital quantales (including the correspondence among maps for them) 3. The correspondence among an interval-totally preordered set, a diagonal unital partial semigroup, and a diagonal powerset quantale (including the correspondence among maps for them)

We also have shown that each diagonal powerset quantale has the relational embedding which is the image of partial subtraction− by the functor ℘. It is a future work to generalize our result for any (possibly not diagonal) powerset quantale and to extend it to a Stone duality [11] .

Regular Algebra and Finite Machines

Weakest prespecification

Topology via Logic

Relational representation theorem for powerset quantales

Dynamic algebras and the nature of induction

Second Topology Conference. Rendiconti del Circolo Matematico di Palermo

Quantales and Their Applications

Semigroups in Complete Lattices: Quantales, Modules and Related Topics

Effect algebras and unsharp quantum logics

Poloids from the points of view of partial transformations and category theory

Stone Spaces

The authors thank Izumi Takeuti, Takeshi Tsukada, Soichiro Fujii, Mitsuhiko Fujio, and Hiroyuki Miyoshi for valuable discussion about partial semigroups.