T 代数上の上半束のイデアル完備化
Ideal Completion of Join Semilattice over T-algebra
西澤

弘毅・古澤

仁

NISHIZAWA Koki，FURUSAWA Hitoshi

鳥取環境大学紀要
第９号・第10号合併号

2012．３抜刷

Reprinted ftom
BULLETIN OF TOTTORI UNIVERSITY OF ENVIRONMENTAL STUDIES
Volumes 9 & 10

Mar. 2012

鳥取環境大学紀要
第９号・第10号合併号（2012. ３）pp.91‑103

T 代数上の上半束のイデアル完備化
Ideal Completion of Join Semilattice over T-algebra
西澤

弘毅＊・古澤仁†

NISHIZAWA Koki ＊，FURUSAWA Hitoshi†
和文要旨：この論文は、クウォンテールの圏からべき等半環の圏への忘却関手の左随伴を明示的に構成する方法を二つ与える。一つの方法は、イデアル完備化が、完備上半束の圏から上半束の圏への忘却関手の左随伴を与えることを示す方法である。この方法に対して、上半束から T 代数上の上半束へ一般化すると、例として、クウォンテールの圏からべき等半環の圏への忘却関手の左随伴を扱えるようになる。もう一つの方法は、べき等半環のイデアル完備化が忘却関手の左随伴を与えることを、直接的に証明する方法である。
【キーワード】べき等半環、クウォンテール、イデアル完備化、分配律
Abstract：This paper provides an explicit construction of the left adjoint to the forgetful functorfrom the category of quantales to the category of idempotent semirings in two ways. The ﬁrst way
shows that an ideal completion gives the left adjoint to the forgetful functor from the category ofcomplete join semilattices to the category of join semilattices. Generalizing join semilattices to join
semilattices over T-algebras, the left adjoint to the forgetful functor from the category of quantales tothe category of idempotent semirings is given as an example. The second way is to directly provethat the ideal completion of idempotent semirings gives the left adjoint.
【Keywords】idempotent semiring, quantale, ideal completion, distributive law
１

Introduction

This paper provides an explicit construction of the left adjoint to the forgetful functor from the category of complete join semilattices to the category of join semilattices. Similarly, one can construct the left adjoint to the forgetful functor from the category of quantales to the category of idempotent semirings. A quantale is a complete join
semilattice together with a monoid structure whose associative multiplication distributes over arbitrary joins. An
idempotent semiring is a join semilattice together with a monoid structure whose associative multiplication distributes over ﬁnite joins. Both of these left adjoints are deﬁned by an ideal completion. In order to show why bothof these left adjoints are deﬁned by the ideal completion, we generalize quantales and idempotent semirings tocomplete join semilattices over T-algebras and join semilattices over T-algebras, respectively. By generalization,
the left adjoint to the forgetful functor from the category of quantales to the category of idempotent semirings is
given as an example. We also give a direct proof for the case of the category of quantales and the category of
idempotent semirings.
This paper is organized as follows: Section 2 deﬁnes monads for join semilattices. Section 3 shows that a left ad-＊

Department of Information Systems, Faculty of Environmental and Information Studies, Tottori University of Environmental Studies.
koki@kankyo-u.ac.jp

Department of Mathematics and Computer Science, Graduate School of Science and Engineering, Kagoshima University. furusawa@sci.kagoshima-u.ac.jp― 91 ―

鳥取環境大学紀要

第９号・第10号合併号

joint between categories of algebras is deﬁned by absolute coequalizer construction. Section 4 shows that the ideal
completion gives the absolute coequalizer for join semilattices. Section 5 generalizes results in Section 3 formonads combined by distributive laws. Section 6 directly proves that the ideal completion gives the left adjoint to
the forgetful functor from the category of quantales to the category of idempotent semirings without notions ofmonads and distributive laws. Section 7 summarizes this work and discusses future work.
２

Monads for Join Semilattices

Deﬁnition 2.1. A join semilattice is a tuple（S, ≤,㱹）with a partially ordered set（S, ≤）and the join or the least upper bound 㱹 A for a ﬁnite subset A of S.
A join semilattice S must have the least element 0 since the empty set

is a ﬁnite subset of S and 㱹 ＝0.

SLat denotes the category whose objects are join semilattices and whose arrows are homomorphisms between
them. SLat is equivalent to the Eilenberg-Moore category ℘f -Alg of the ﬁnite powerset monad ℘f , whose endofunctor sends a set X to the set of ﬁnite subsets ℘（X）={A ⊆ X | | A|<ω}, whose unit sends an element x in X to {x} inf℘（X）, and whose multiplication sends a subset family α in ℘（℘（X））to its union ∪α={ x | ∃X∈α, x∈X } in ℘（X）
.
f
f
f
f
The forgetful functor from ℘f-Alg to Set has the left adjoint which sends a set X to（℘（X）, ∪: ℘（℘（X））→ ℘（X））.
f
f
f
f
The counit for ℘f -algebra（S, 㱹）is 㱹:（℘（S）, ∪）→（S, ∨）.
fDeﬁnition 2.2. A complete join semilattice is a tuple（S, ≤, ∨）with a partially ordered set（S, ≤）and the join or the
least upper bound 㱹 A for a subset A of S.
We write CSLat for the category whose objects are complete join semilattices and whose arrows are homomorphisms between them. CSLat is equivalent to the Eilenberg-Moore category ℘-Alg of the powerset monad ℘,whose endofunctor sends a set X to the set of all subsets ℘（X）={ A | A ⊆ X }, whose unit sends an element x in X to{x} in ℘（X）, and whose multiplication sends a subset family α in ℘（℘（X））to its union ∪α={ x | ∃X∈α, x∈X } in ℘（X）
. The forgetful functor from ℘-Alg to Set has the left adjoint which sends a set X to（℘（X）,∪: ℘（℘（X））→ ℘（X））
. The counit for ℘-algebra（S, ∨）is ∨:（℘（S）,∪）→（S, 㱹）.
P

P

P'

P'

（P', μ , η ）be monads on C. A monad map ι from P to P' is a natural
Deﬁnition 2.3. Let P =（P, μ , η ）and P’=transformation from P to P' satisfying the following diagrams.
P
ηP

ι

P

P

PP

Pι

PP′

ιP

PP

μP

μP

η

P

Id
P

P

ι

P

P'

P'

Lemma 2.4. Let P=（P, μ , η ）and P'=（P', μ , η ）be monads on C. If ι is a monad map from P to P', then, the following G is afunctor from P'-Alg to P-Alg.
・For a P'-algebra（c, p'）,G（c, p'）=（c, p'◦ιc）.
・For a P'-algebra homomorphism f:（c1, p'1）→（c2 , p'2）,Gf=f.
Proof. G（c, p ）is a P-algebra by the following equations.
p'◦ιc◦ηPc=p'◦ηP'c=Idp'◦ιc◦μPc=p'◦μPc'◦ιP’c◦Pιc=p'◦P'p ◦ιP‘c◦Pιc=p'◦ιc◦Pp'◦Pιc
Gf is a P-algebra homomorphism by the following equation.
f ◦ p'1◦ ιc1=p'2◦ P'f ◦ ιc1=p'2◦ ιc2◦ Pf□
We write −◦ι for the above functor G.
Example 2.5. Let P be the ﬁnite powerset monad ℘f. Let P' be the powerset monad ℘. Let ιX be the inclusion from℘（X）
to ℘（X）.Then, ι is a monad map from ℘f to ℘. The functor −◦ι is the forgetful functor from CSLat to SLat.
f― 92 ―

NISHIZAWA

3FURUSAWA

Ideal Completion of Join Semilattice over T-algebra

Left Adjoint by Absolute Coequalizers
The next theorem is a corollary of the Theorem 2（b）of Section 3.7 of the book［2］.

Theorem 3.1. Let C, D, D' be categories and G, U, U' be functors satisfying the following conditions.
・G: D' → D is a functor.
・A functor U: D → C has a left adjoint F（call its unit η and its counit ε）.
.
・A functor U': D' → C has a left adjoint F'（call its unit η' and its counit ε'）・U◦G is natural isomorphic to U'.
・U is monadic.
・For an object d in D, the parallel pairF'UFUdandF’UFUd

F'Uεd

F'Ud

F'UFη'Ud

F'UFU'F'Ud

㲓◦F'UεGF'Ud◦㲓

F'U'F'Ud

ε'F'UdF'Ud

has a coequalizer in D'.
Then, G has a left adjoint which sends an object d in D to the codomain of the above coequalizer.
Theorem 3.2（Corollary of Beckʼs theorem［6］）. If a functor U' : D' → C is monadic, then U' creates coequalizers of thoseparallel pairs f,g in D' for which U'f, U'g has an absolute coequalizer in C.
Example 3.3. The forgetful functor U' from CSLat to Set is monadic. Therefore, it creates coequalizers of thoseparallel pairs f, g in CSLat for which U'f, U'g has an absolute coequalizer in Set.
P

P

P'

P'

Theorem 3.4. Let P=（P, μ , η ）and P'=（P', μ , η ）be monads on C. Let ι be a monad map from P to P'. For a P-algebra（c,P'p）（c, p）be an absolute coequalizer of P'p and μc ◦ P'ιc in C.
, let e（c, p）: P'c → E

P'Pc

P'p
P'
c

μ◦P'ιcP'ce（c,p）

E（c,p）

Then, the functor−◦ ι: P'-Alg → P-Alg has a left adjoint L, where L（c, p）is the P'-algebra on E（c, p）created by the forgetful
functor from P'-Alg to C.
Proof. Let D=P-Alg and D'=P'-Alg in Theorem 3.1. Let U be the forgetful functor from P-Alg to C. Let U' be theforgetful functor from P'-Alg to C. The composition of U and−◦ι is natural isomorphic to U'. For a P-algebra（c, p）,
U' sends the parallel pair in Theorem 3.1 to
U' F' Uε（c, p）=U' F' Up=U' F' p=P'pandU'ε'F’U（c, p）◦ U'F'Uε（−◦ι）F’U（c, p）◦U'F'UFη'U（c, p）=U’ε'F'U（c, p）◦ U'F'Uε（P'c, μP'c◦ι P'c）◦U'F'UFη'U（c, p）
P'P'=μ c◦P'（μ c ◦ ιP'c）◦P'Pη'c
P'
c

P'
c

P'

=μ ◦P'μ ◦ P'P'η c◦P'ιcP'=μ c◦P'ιc.
These pairs have an absolute coequalizer e（c, p）. Since U' is monadic, −◦ι has the left adjoint L by Theorem 3.2
and Theorem 3.1.

□

Theorem 3.5. If the assumptions of Theorem 3.4 hold and for all P-algebra（c,p）,e（c, p） has a right inverse r（c, p）,
E（c, p）

r（c, p）

Id

Pce（c, p）
E（c, p）― 93 ―

鳥取環境大学紀要

第９号・第10号合併号

then L（c, p）is the pair of E（c, p）and the following P'-structure map.
P'r（c,p）
μP'ce（c,p）
P' E
P'P'c
P'c
E
（c,p）
（c, p）P'
Proof. There exist a unique object（E（c, p）, p'）in P'-Alg satisfying（c, p）, p'）and a unique arrow f :（P'c, μ c ）→（E

U' f =e（c, p） by Theorem 3.4. Since f is e（c, p） itself and it is a P'-algebra homomorphism, the following diagram commutes.
P E（c, p）
Id

P r（c, p）
PPc

P e（c, p）

P E（c, p）

P′

p

μc

Pc

e（c, p）

E（c, p）□
By Theorem 3.4, the forgetful functor ―◦ ι from CSLat to SLat has a left adjoint if Set has an absolute coequalizer of ℘（∨）: ℘（℘（S））→ ℘（S）and ∪ : ℘（℘（S））→ ℘（S）for a join semilattice（S, ≤, ∨）.
f
f
４

Ideal Completion as Absolute Coequalizer
This section shows that Set has an absolute coequalizer of ℘（㱹）and ∪ for a join semilattice（S, ≤, 㱹）.

Deﬁnition 4.1. Let S be a join semilattice. An ideal is a subset A of S such that
・A is closed under ﬁnite join operation 㱹,
・A is closed downward under ≤.
Since an ideal A is closed under ﬁnite join, A must contain the least element 㱹 ＝0. Thus, ideals are not empty.
The set of ideals of a join semilattice S is denoted by （S）. For a subset A of a join semilattice S, we write〈A〉
for{a∈S | ∃X∈℘（S）. X⊆A, a ≤∨X}.
f
is an ideal of S andLemma 4.2. For a subset A and an ideal I of a join semilattice S,〈A〉〈A〉⊆ I iff A⊆I. In other words, for asubset A of a join semilattice S,
is the smallest ideal containing A.
〈A〉
Proof. For a ﬁnite subset Y ⊆〈A〉and y∈Y, there exists a ﬁnite set Xy satisfying Xy⊆A and y≤∨Xy. We have ∨Y∈〈A〉, since ∪{Xy | y∈Y} is a ﬁnite subset of S satisfying ∪{Xy | y ∈ Y}⊆A and ∨Y≤∨∪{Xy | y∈Y}.〈A〉is closed downward under ≤, trivially. Therefore,〈A〉
is an ideal.
For all a ∈ A, {a} is a ﬁnite subset satisfying {a}⊆A and a≤ ∨{a}. Therefore,〈A〉contains A.
Let I be an ideal containing A. For a∈S and X∈℘（S）, if X⊆A and a≤∨X, then we have X⊆I, ∨X∈I, and a∈I.
f
Therefore, we have
〈A〉
⊆ I.

□

The function〈̲〉: ℘（S）→ （S）which sends A to〈A〉is called an ideal completion. The inclusion function r: （S）→ ℘（S）is a right inverse of〈̲〉
.
r

（S）

Id

℘（S）
〈̲〉
（S）

― 94 ―

NISHIZAWA

FURUSAWA

Ideal Completion of Join Semilattice over T-algebra

Theorem 4.3. For a join semilattice S,〈̲〉: ℘（S）→ （S）is an absolute coequalizer of ℘（㱹）and ∪ in Set.
℘
（∨）
〈̲〉
℘
℘（S）
（℘（S）
（S）
）
f
∪
Proof. Let α be an element of ℘（℘（S））. We have〈℘（㱹）（α）〉⊆〈∪α〉as follows.
f
〈℘（㱹）
（α）
〉
⊆
〈∪α〉
⇔℘
（㱹）
（α）
⊆
〈∪α〉

（by Lemma 4.2）

⇔㱹X ∈
〈∪α〉

（∀X∈α）⇔ X⊆〈∪α〉（∀X∈α） （since an ideal is closed under ﬁnite join）

⇔∪α⊆
〈∪α〉
⇔
〈∪α〉
⊆
〈∪α〉

（by Lemma 4.2）

Conversely, we have〈∪α〉
⊆
〈℘
（㱹）
（α）
〉as follows.
〈∪α〉⊆
〈℘（㱹）
（α）
〉
⇔∪α⊆
〈℘
（㱹）
（α）
〉

（by Lemma 4.2）

⇔ X⊆
〈℘
（㱹）
（α）
〉 （∀X∈α）
⇔∨X∈
〈℘
（㱹）
（α）
〉 （∀X∈α） （since an ideal is closed downward）
⇔℘
（㱹）
（α）
⊆
〈℘（㱹）
（α）
〉
⇔
〈℘
（㱹）
（α）
〉
⊆
〈℘
（㱹）
（α）
〉

（by Lemma 4.2）

Therefore, for each α∈℘（℘（S））,〈℘（㱹）（α）
〉=〈∪α〉.
f
We deﬁne ℘f : ℘（S）→℘（℘（S）
）and down: ℘（S）→℘（℘（S））as follows.
ff℘（A）={X∈℘（S）| X⊆A}ff
down（A）={{a,b} | a∈S, b∈A, a≤b}
These functions satisfy the following diagrams, where r is the inclusion function from （S）to ℘（S）.
℘（S）

℘f

℘（℘（S）
）
f

℘（S）

∪

Id

down

℘（∨）

Id

℘（S）

℘（S）

℘f

℘（℘（S））
f℘（℘（S）
）
f

℘（S）

℘（∨）

℘（S）

〈̲〉

down

℘（℘（S）
）
f
∪

（S）

℘（S）

r

Let Z∈Set and f: ℘（S）
→ Z be satisfying f◦℘（㱹）=f ◦ 㱮. We show that there exists a unique arrow h: （S）→Z
satisfying h◦
〈̲〉
=f.
℘（∨）
〈̲〉
℘（℘（S）
）
℘（S）
f
∪

（S）
h

f
Z

― 95 ―

鳥取環境大学紀要

第９号・第10号合併号

The arrow h is deﬁned by f◦r. We have h◦〈̲〉=f as follows:h◦〈̲〉= f◦r◦〈̲〉= f◦∪◦down◦℘
（㱹）
◦℘f
= f◦℘
（㱹）
◦down◦℘（㱹）
◦℘f
= f◦℘
（㱹）
◦℘f
= f◦∪◦℘f=f
Moreover, if an arrow g: （S）→ Z satisﬁes g◦〈̲〉=f, then h=f ◦ r=g◦〈̲〉◦r=g. So, h: （S）→ Z is a unique arrowsatisfying h◦〈̲〉=f.
Therefore,〈̲〉:℘（S）→ （S）is a coequalizer of ℘（㱹）and ∪ in Set. The above diagrams are preserved by any
functor from Set to another category. Therefore,〈̲〉: ℘（S）→ （S）is an absolute coequalizer of ℘（㱹）and 㱮 in Set.
□
Example 4.4. By Theorem 4.3, Theorem 3.4, and Theorem 3.5, the forgetful functor from CSLat to SLat has a left
adjoint, which sends a join semilattice S to（ （S）, ⊆, 㱹）satisfying 㱹α=〈∪α〉.
５Left Adjoint between Categories of Algebras by Absolute Coequalizers
This section extends Theorem 3.4 to the theorem for quantales and idempotent semirings.

Deﬁnition 5.1. An idempotent semiring, abbreviated as I-semiring is a tuple（S, +, ・, 0,1）with a set S, two binary operations + and ・, and 0,1∈S satisfying the following properties:
・（S, +, 0）is an idempotent commutative monoid.
・（S,・, 1）is a monoid.
・For all a, b, c ∈ S,
a・c + b・c =（a+b）
・c
a・b + a・c = a・（b+c）
0・a = 0a・0 = 0where the natural order ≤ is given by a≤b iﬀ a+b=b.
We often abbreviate a・b to ab.
The natural order ≤ on an I-semiring is a join semilattice, where its join operation is given by 㱹 ＝0 and, for aﬁnite subset A ⊆ S containing a, ∨ A＝a+
（㱹A╲{a}）.
Example 5.2. Let Σ be a ﬁnite set and Σ＊ the set of ﬁnite words（strings）over Σ. Then, the ﬁnite power set ℘f（Σ＊）of Σ＊ forms an I-semiring together with the union, concatenation, empty set, and the singleton set of theempty word.
IS denotes the category whose objects are I-semirings and whose arrows are homomorphisms between them.
Deﬁnition 5.3. A quantale S is an I-semiring satisfying the following properties: For each A⊆S and a∈S,・the least upper bound ∨ A of A exists in S,・（∨ A）a = ∨ {xa | x∈A}, and・a（∨ A）= ∨ {ax | x∈A}.
So, a quantale is a complete I-semiring or an S-algebra［3］. Homomorphisms between quantales are semiring
homomorphisms preserving arbitrary joins.
Example 5.4. Let Σ be a ﬁnite set and Σ＊ the set of ﬁnite words（strings）over Σ. Then, the power set ℘（Σ＊）of
Σ＊ forms a quantale together with the union, concatenation, empty set, and the singleton set of the empty word.
Qt denotes the category whose objects are quantales and whose arrows are homomorphisms between them.
＊Remark 5.5. I-semirings need not be quantales. For example, an I-semiring ℘（Σ
）is not a quantale since it is notfclosed under arbitrary unions.

― 96 ―

NISHIZAWAT

FURUSAWA

T

P

Ideal Completion of Join Semilattice over T-algebraP

Deﬁnition 5.6（distributive law［7］）. Let T =（T, μ , η ）and P =（P, μ , η ）be monads on a category C. A distributive
law θ of P over T is a natural transformation from TP to PT satisfying the following diagrams.
TTP

Tθ

TPT

θT

PTT

T

TP

θ
θP

PTP

Pθ

ηP

P

PPT

TP

P

P

μT

PT

PηT

PT

Tμ

θ

T

PμT

μP

TPP

TP

θ

TηP

PT

P

ηT

TP

PT
T
θ
Deﬁnition 5.7. Let T, T', P, P' be monads on C. Let θ be a distributive law of P over T. Let θ' be a distributive lawof P' over T'. A morphism（τ, π）: θ → θ' of distributive laws consists of monad maps τ: T → T' and π : P → P' satisfying
the following diagram.
TP

θ

PT

τP

πT

TP

PT

Tπ
TP

Pτ

θ

PT

Deﬁnition 5.8. Let P and T be monads on a category C. Let θ be a distributive law of P over T. A P◦θ T-algebra is atuple（c, t, p）such that・c is an object in C ,・The pair of c and t: Tc → c is a T-algebra,
・The pair of c and p: Pc → c is a P-algebra, and・p◦Pt◦θc = t◦Tp.
TPc

θc

PTc

Pt

Pc

Tp
Tc

p

t

c

P ◦ θ T-Alg denotes the category whose objects are P◦ θ T-algebras and whose arrows are simultaneous T- andP-homomorphisms.
Lemma 5.9. Let T, P, P' be monads on C. Let θ be a distributive law of P over T. Let θ' be a distributive law of P' over T. Let ι bea monad map such that（Id, ι）is a morphism（Id, ι）: θ → θ' of distributive laws. The following G is a functor from P'◦θ' T-Alg
to P◦θ T-Alg.
・For a P'◦θ’ T-algebra（c, t, p'）,G（c, t, p'）=（c, t, p'◦ιc）.

― 97 ―

鳥取環境大学紀要

第９号・第10号合併号

・For a P'◦θ’ T-algebra homomorphism f, Gf = f.
We write −◦ ι for the above functor G.
Example 5.10. Let T=（̲）＊ be the monad for ﬁnite sequences on Set. Then, T-Alg is equivalent to the category
Mon whose objects are monoids and whose arrows are homomorphisms between them.
Let ℘f be the ﬁnite powerset monad（℘f , 㱮, {̲}）on Set. Let ℘ be the powerset monad（℘, 㱮, {̲}）on Set. Thereexists a distributive law θ of T over ℘f, and there exists a distributive law θ' of T over ℘ as follows.
θ（SX
1・S2……Sn）= {x1・x2……xn | x1∈S1, x2∈S2, . . . , xn∈Sn}
θ'（SX
1 · S2……Sn）= {x1・x2……xn | x1∈S1, x2∈S2, . . . , xn∈Sn}
Then, ℘f◦θ T-Alg is equivalent to the category IS and ℘◦θ' T-Alg is equivalent to the category Qt. Let ιX be the inclusion function from ℘（X）
to ℘（X）.（Id, ι）
: θ → θ' is a morphism of distributive laws.
fLemma 5.11. The forgetful functor from P◦θ T-Alg to C is monadic.
Example 5.12. The forgetful functor from Mon to Set, the forgetful functor from IS to Set, and the forgetful functor from Qt to Set are monadic.
Lemma 5.13. The forgetful functor from P◦θ T-Alg to T-Alg is monadic. The left adjoint to this forgetful functor sends a T-algebra（c, t）to（Pc, Pt◦θc, μPc）and a T-homomorphism f to Pf. The unit for a T-algebra（c, t）is ηPc:（c, t）→（Pc, Pt◦θc）. The
counit for a P◦θ T-algebra（c, t, p）is p:（Pc, Pt ◦ θc, μPc）→（c, t, p）.
Example 5.14. The forgetful functor from IS to Mon and the forgetful functor from Qt to Mon are monadic.
T

T

P

P

P'

P'

Theorem 5.15. Let T=（T, μ , η ）, P=（P, μ , η ）, and P'=（P', μ , η ）be monads on C. Let θ be a distributive law of P over T.
Let θ' be a distributive law of P' over T. Let ι be a monad map such that（Id, ι）is a morphism（Id, ι）:θ → θ' of distributive laws.
P'
For a P◦θ T-algebra（c, t, p）, let e（c, p）: P'c → E（c, p）be an absolute coequalizer of P'p and μ c ◦ P'ιc in C.

P'Pc

P'p
'
μPc◦
P'ιc

P'c

e（c,p）

E（c,p）

Then, the functor−◦ ι: P'◦θ' T-Alg → P◦θ T-Alg has a left adjoint L, where L（c, t, p）is the P'◦θ' T-algebra on E（c, p）created by
the forgetful functor from P'◦θ' T-Alg to C.
Proof. Let D=P◦θ T-Alg and D'=P'◦θ' T-Alg in Theorem 3.1. Let U be the forgetful functor from P◦θ T-Alg to T-Alg.
Let U' be the forgetful functor from P'◦θ' T-Alg to T-Alg. The composition of U and −◦ ι is natural isomorphic to U'.
For a P◦θ T-algebra（c, t, p）, the forgetful functor U' sends the parallel pair in Theorem 3.1 to
U'F'Uε（c, t, p）=U'F'Up=U'F'p=P'pandU'ε'F'U（c, t, p）◦U'F'Uε（−◦ι）F'U（c, t, p）◦ U'F'UFη'U（c, t, p）=U'ε'F'U（c, t, p）◦U'F'Uε（P'c, P't◦θ' , μ ◦ι ）◦U'F'UFη’U（c, t, p）
c

P'
c

P'
c

P'c

P'
c

=μ ◦P'（μ ◦ιP'c）◦P'Pη'cP'P'P'=μ c ◦P'μ c◦P'P'η c◦P'ιcP'c=μ ◦P'ιcMoreover, the forgetful functor from T-Alg to C sends these pairs to the same arrows. They have an absolute coequalizer. The monadic forgetful functor from P'◦θ’ T-Alg to C is monadic. Therefore, −◦ι has the left adjoint L by
Theorem 3.1 and Theorem 3.2.

□

Theorem 5.16. If the assumptions of Theorem 5.15 hold and for all P◦θ T-algebra（c, t, p）,e（c, p） has a right inverse r（c, p）,
r（c, p）
E（c, p）
Pc

Ide（c, p）
E（c, p）― 98 ―

NISHIZAWA

FURUSAWA

Ideal Completion of Join Semilattice over T-algebrathen L（c, p）is the tuple of E（c, p）and the following P'◦θ' T-structure map.
Tr（c, p）
TE（c, p）
TP'c

θ'c

P'Tc

P't

P'c

e（c, p）

E（c, p）P'

μ ce（c, p）
Pr（c, p）
P'E
P'P'c
P'c
E
（c, p）（c, p）P'
Proof. There exist a unique object（E（c, p）,t', p'）in P'θ' T-Alg（c, p）, t', p'）and a unique arrow f :（P'c, P't◦θ'c, μ c ）→（Esatisfying U'f = e（c, p） by Theorem 5.15. Since f is e（c, p） itself and it is simultaneous a T-homomorphism and a P'-homomorphism, both of the following diagrams commute.
TE（c, p）
Tr（c, p）
TP c

Id

Te（c, p）

PE（c, p）
TE（c, p）

PPc

θc
P Tc

t

Pt
Pc

P e（c, p）

PE（c, p）

P

p′

μc

Pc

e（c, p）

Id

P r（c, p）

e（c, p）

E（c, p）

E（c, p）□
Example 5.17. By Theorem 5.15, Theorem 5.16, and Theorem 4.3, the forgetful functor from Qt to IS has a left adjoint, which sends an idempotent semiring（S, +,・, 0, 1）to（ （S）,⊆, 㱹I,・I, 1I）satisfying
α=〈{a・b | a∈J, b∈K}〉, 1I =〈{1}〉.
〈㱮 α〉, J・I K=∨
I
6

Direct Proof of Left Adjoint by Ideal Completion
In this section, we directly prove that the ideal completion gives the left adjoint to the forgetful functor from Qt

to IS.
Deﬁnition 6.1（cf. Deﬁnition 4.1）
. Let S be an I-semiring. An ideal is a subset A of S such that A is an ideal of theunderlying join semilattice（S, ≤, ∨）.
The set of ideals of an I-semiring S is denoted by （S）. Note that （S）is closed under arbitrary intersection.
Also note that A∈ （S）iﬀ A is nonempty, closed under +, and closed downward under ≤.
We say that a subset A of an I-semiring S generates an ideal I if I is the smallest ideal containing A. By Lemma
4.2,〈A〉={a∈S | ∃X ∈℘（S）. X⊆A, a ≤ ∨X} is the ideal generated by A⊆S. Note that〈̲〉is monotone and idempof
tent, i. e. A⊆B implies〈A〉⊆〈B〉and〈〈A〉〉=〈A〉for any subsets A, B⊆S. If A is a singleton {a}, we often abbreviate〈{a}〉to〈a〉. Such an ideal is called principal.
Lemma 6.2. Let S be an I-semiring. For a subset α of ℘（S）,〈㱮α〉=〈㱮〈A〉{| A∈α}〉.
Proof. The inclusion ⊆ follows from monotonicity of〈̲〉.Again, by monotonicity of〈̲〉,〈A〉⊆〈㱮 α〉for each A∈α.
{
| A∈α}⊆〈㱮 α〉{| A∈α}〉⊆〈㱮 α〉by monotonicity and idempotency of〈̲〉Thus, 㱮〈A〉
. So, we have〈㱮〈A〉.
Let S be an I-semiring. For subsets A, B ⊆ S, deﬁneA⊕B={a+b | a∈A, b∈B}
A⊙B={a・b | a∈A, b∈B}
A↓={ y | ∃x∈A. y ≤ x}.
Note that― 99 ―□

鳥取環境大学紀要

第９号・第10号合併号（A⊕B）⊙C ⊆
（A⊙C）
⊕
（B⊙C）
C⊙（A⊕B）
⊆
（C⊙A）
⊕
（C⊙B）
A⊙（B↓）
⊆
（A⊙B）
↓
（A↓）
⊙B⊆
（A⊙B）
↓.
Also note that for principal ideals,〈a〉={a}↓.
Though Lemma 3 in［4］, corresponding property will appear as Lemma 6.5 in this paper, is shown by transﬁnite induction, we are going to show Lemma 6.5 without using transﬁnite induction.
For subsets A, B, X of an I-semiring S, deﬁnex∈A−1X ⇔ ∀a∈A. ax∈Xx∈XB−1 ⇔ ∀b∈B. xb∈X.
Note that B⊆A− 1X iﬀ A⊙B⊆X iﬀ A⊆XB−1. Then, since A−1X ⊆ A−1X and XB− 1⊆XB− 1, we have A⊙A− 1X⊆X and
XB−1⊙B⊆X. Also, if X⊆Y, A⊆A', B⊆B', it holds that A'−1X ⊆ A−1Y and XB'−1⊆ YB−1.
Lemma 6.3. The following holds for subsets X, Y, A and B of an I-semiring S.
1．A−1X⊕A−1Y⊆A−1（X⊕Y）.
2．XB−1⊕YB−1⊆
B−1.
（X⊕Y）
3．（A−1X）
（X↓）
.
↓⊆A−1
4．（XB−1）
B−1.
↓⊆（X↓）
Proof. 1 follows from A⊙（A−1X⊕A−1Y）⊆（A⊙A−1X）⊕（A⊙A−1Y）⊆X⊕Y. The other inclusions are shown similarly
to 1.

□

Lemma 6.4. Let S be an I-semiring. The following holds for an ideal I and subsets A, B ⊆ S.
1．A−1I is an ideal.
2．IB−1 is an ideal.
Proof. 1. Since A⊙{0}={0}⊆I, {0} ⊆ A−1I. Thus, A−1I is nonempty. Also, we have
A−1I ⊕ A−1I ⊆ A−1（I⊕I）（by 1 of Lemma 6.3）
⊆ A−1I,↓⊆ A−1（I↓）（by 3 of Lemma 6.3）
（A−1I）⊆ A−1I.
Therefore A I is an ideal. 2 is proved similarly to 1.
−1□

Lemma 6.5. Let S be an I-semiring. Then,〈A⊙B〉=〈〈A〉⊙〈B〉〉holds for any subsets A, B⊆S.
Proof. The inclusion ⊆ follows from monotonicity of〈̲〉. Next, we show the reverse inclusion. Since A⊙B⊆〈A⊙B〉,
B−1. By Lemma 6.4 and monotonicity of〈̲〉, it holds that〈A〉⊆〈A⊙B〉B−1. Thus,〈A〉⊙B⊆
we have A ⊆〈A⊙B〉−1〈A⊙B〉holds. Moreover, this inclusion implies B⊆〈A〉〈A⊙B〉.Again, by Lemma 6.4 and monotonicity of〈̲〉,〈B〉
−1
⊆〈A〉
〈A⊙B〉
. Thus,〈A〉⊙〈B〉⊆〈A⊙B〉holds. Therefore, by monotonicity of〈̲〉,the reverse inclusion holds.

□

In general, the natural ordering on an I-semiring is a join semilattice but not complete as we have seen in Remark 5.5. Next, we provide a completion of I-semirings.
Let S be an I-semiring and consider the poset（ （S）,⊆）. Since〈0〉={0},〈0〉is the least element of （S）. For
each subset α⊆ （S）, an ideal〈㱮 α〉is the least upper bound of α. Obviously, the least upper bound of ⊆ （S）is〈0〉. Also, since〈a〉={a}↓,a≤b ⇔〈a〉⊆〈b〉
holds for any a, b∈S. Thus,（ （S）, ⊆）is an ideal completion of（S, ≤）with an embedding〈̲〉: S → （S）. ∨α denotes the least upper bound of α⊆ （S）. For any I, J ∈ （S）,we write I+J for∨{I, J }, and deﬁne I・J=〈I⊙J〉.
In the rest of this section, a functor from IS to Qt which is a left adjoint to the forgetful functor is provided. G:
Qt → IS
Proposition 6.6. Let S be an I-semiring. For any H, I, J ∈ （S）and α ⊆ （S）,the following holds.

― 100 ―

NISHIZAWA

FURUSAWA

Ideal Completion of Join Semilattice over T-algebra

1．〈0〉
・I=
〈0〉
=I・
〈0〉
.
2．〈1〉
・I=I=I・
〈1〉
.
3．
（H・I）
・J=H・
（I・J）
.
4．
（∨ α）
・I= ∨ {J・I | J∈α}.
5．I・
（∨α）
= ∨{I・J | J∈α}.
Proof. 1 follows from deﬁnition of ⊙. 2 and 3 follow from deﬁnition of ⊙ and Lemma 6.5. 4 follows from
・I=
〈
（∨α）
⊙I〉
（∨α）
=
〈
〈∪α〉
⊙I〉
⊙I〉
=
〈
（∪α）

（by Lemma 6.5）=〈∪{J⊙I | J∈α}〉=〈∪〈J⊙I〉{| J∈α}〉（by Lemma 6.2）=〈∪{J・I | J∈α}〉=∨{J・I | J∈α}.
5 is proved similarly to 4.

□

Therefore, （S）forms a quantale.
Let S be an I-semiring. Using〈x〉={x}↓, it is veriﬁed that the mapping
x 〈x〉
from S to （S）is one-to-one and preserves +, ・, 0, and 1. Thus, this mapping is an arrow from S to （S）in IS.
We have omitted a transﬁnitely inductive construction of an ideal, which has been adopted in［4］.Thus, it is impossible to beneﬁt from the proof of Lemma 4 in［4］,which depends on the transﬁnitely inductive construction.
Let S and S' be I-semirings. Given a homomorphism f from S to S', we deﬁneff［A］={f（a）| a∈A} and f −1［A'］={a | （a）
∈A' }f
for each A ⊆ S and A' ⊆ S', respectively. Note that ［A］⊆A' iﬀ A ⊆ f −1
［A'］.Also, note that
f
f
［A⊙B］
= ［A］⊙f
［B］
f
f
f
［A⊕B］
= ［A］
⊕ ［B］
f
f
［A↓］
⊆ ［A］
↓
for all A, B⊆S.
Lemma 6.7. Let S and S' be I-semirings and f: S → S' a homomorphism. Then the following holds for any A', B'⊆S'.
1．f −1［A'］⊙f −1［B'］⊆ f −1［A'⊙B'］.
2．f −1［A'］⊕ f −1［B'］⊆ f −1［A'⊕B'］.
3．f −1［A'］↓⊆ f −1［A'↓］.
4．If A' ∈ （S'）, then f −1
［A'］
∈ （S）
.
Proof. The ﬁrst inclusion is equivalent to ［f f −1［A'］⊙f −1［B'］］⊆A'⊙B'. Also, it holds thatf f −1
［
［A'］
⊙f −1
［B'］
］
=f［f −1［A'］］⊙f［f −1［B'］］.
f −1
f −1［B'］
Since ［f［A'］］
⊆A' and ［f］⊆B', 1 holds. 2 is proved similarly to 1. The third inclusion is equivalent to f
f f −1［A'］f −1［ f −1［A'］↓］⊆ A'↓. Since ［↓］⊆ f［ f −1［A'］］↓ and ［f［A'］］⊆A', 3 holds. It is suﬃcient for 4 to check nonf
emptiness of f −1
［A'］since the others are induced by 2 and 3. Suppose that A' is an ideal. Then, 0∈A'. So, ［{0}］={0}⊆A'. Thus {0}⊆f −1［A'］. Therefore, f −1［A'］is nonempty.
Lemma 6.8. Let S and S' be I-semirings and f : S → S' a homomorphism. For each subset A ⊆ S, the following holds.
f 〈A〉］ ⊆
［
〈f［A］
〉
f 〈A〉
f
〈［
］
〉
=
〈［A］
〉
Proof. The ﬁrst inclusion follows from
f
f
［
〈f［A］
〉
］
［A］
⊆
〈［A］
〉
⇔ A ⊆ f −1⇒
〈A〉
⊆ f −1［〈 f［A］〉］（by 4 of Lemma 6.7）
f 〈A〉
⇔［
］
⊆
〈 f［A］〉.

― 101 ―□

鳥取環境大学紀要

第９号・第10号合併号

The inclusion〈 f［
〈A〉
］
〉
⊆
〈 f［A］〉follows from the ﬁrst, and the reverse inclusion follows from the monotonicity off and〈̲〉.

□Let S be an I-semiring, Q a quantale, and g: S → G（Q）a homomorphism. By Lemma 6.8, g［I］and g［A］generate
the same ideal if I ∈ （S）is generated by A⊆S. For I ∈ （S）, the least upper bound of g［I］exists in Q, which isdenoted by ∨g［I］, since the least upper bound of any subset of Q exists in Q.
Lemma 6.9. Let S be an I-semiring, Q a quantale, and g: S → G（Q）a homomorphism. If I ∈ （S）, ∨g［I］= ∨g［A］for any
generating set A of I.
Proof. By Lemma 6.8,〈g
［I］
〉
=
〈g
［
〈A〉
］
〉
=
〈g
［A］
〉
for any generating set A of I. Then, ∨g［A］is an upper bound of
g［I］since〈g
［A］
〉
=
（∨g
［A］
）
↓. By g［A］⊆ g［I］, ∨g［A］≤ ∨g［I］. Thus, ∨g［A］= ∨g［I］since
［I］
〉
=
〈g
［A］
〉
⊆
〈∨g

∨g［I］is the least upper bound of g［I］.

□

Let S be an I-semiring and Q a quantale. Deﬁne the map ĝ: （S）→ Q by
ĝ
（I）
= ∨g
［I］
for a homomorphism g: S →G
（Q）.
Proposition 6.10. The map ĝ preserves ∨, ・, 0 and 1.
Proof. For I, J ∈ （S）,
ĝ（I・J ）
［I・J］
=∨g
= ∨g
［
〈I ⊙J〉］= ∨g［I ⊙J］（by Lemma 6.9）

= ∨g［I ］⊙g［J］
［I ］
）
・
（∨g
［J］
）
=
（∨g
=ĝ
（I ）
・ĝ
（J ）
.
Also, we have ĝ
（
〈1〉
）
= 㱹g
［
〈1〉
］
= 㱹g
［{1}］
=1 and ĝ（〈0〉）= 㱹g［〈0〉］= 㱹g［{0}］=0. Note that 㱹（㱮 β）= 㱹 { 㱹 B |B∈β } for a subset β of the powerset ℘（Q）
. Then, for nonempty subset α⊆ （S）,
ĝ（㱹α）
= 㱹g
［㱹α］
= 㱹g
［
〈㱮 α〉
］
= 㱹g
［㱮 α］

（by Lemma 6.9）

［I］| I∈α}）= 㱹（㱮 {g= 㱹{ 㱹g［I］| I∈α}［I］| I∈α}.
= 㱹{ĝThe equation holds even in the case of α =since 㱹α=〈0〉and it has been shown that ĝ preserves 0.

□

Theorem 6.11. Let S be an I-semiring and Q a quantale. For a homomorphism g: S → G（Q）, ĝ is a unique completely joinpreserving homomorphism from （S）to Q such that g=ĝ◦〈̲〉.
Proof. For each a∈S, we have ĝ（〈a〉）= 㱹g［〈a〉］=∨g［{a}］=g（a）by Lemma 6.9. Assume that a completely joinpreserving homomorphism f from （S）to Q satisﬁes g = f◦〈̲〉.Then, it holds that
ĝ
（I）
=∨g
［I ］
（α）| α∈I }
=∨{g
f〈α〉
=∨{ （
）| α∈I}（by assumption）
=f
（∨〈α〉
{
| α∈I }）=f（I ）for each I ∈ （S）. Thus, ĝ = f.

□

For an I-semiring S and a homomorphism h: S → S', we deﬁne
F（S）= （S）and F
（h）
=
〈̲〉
◦h,
respectively. Then, F is a functor from IS to Qt. It is immediate from Theorem 6.11 that the following holds.
Corollary 6.12. The functor F: IS → Qt is a left adjoint to the forgetful functor G: Qt → IS.

― 102 ―

NISHIZAWA

７FURUSAWA

Ideal Completion of Join Semilattice over T-algebra

Conclusion and Future Work
We provided the suﬃcient condition for the functor from P'◦θ'T-Alg to P◦θ T-Alg to have a left adjoint. This result

includes the cases of the forgetful functor from CSLat to SLat and the forgetful functor from Qt to IS. For the second case, a proof being independent from the suﬃcient condition was also provided.
In both cases, left adjoints are given by an ideal completion. The authors plan to search for other examples thanideal completion provided.
Acknowledgements
This work was supported in part by Grants-in-Aid for Scientiﬁc Research（C）22500016 from Japan Society for
the Promotion of Science（JSPS）.
References［1］ Barr M., Wells, C.: Category Theory for Computing Science, Third Edition Les Publications（1999）.
［2］ Barr, M., Wells, C.: Toposes, Triples and Theories Volume 278 of Grundlagen der Mathematischen Wissenschaften. Springer-Verlag, Berlin（1985）.
［3］ Conway, J.H.: Regular Algebra and Finite Machines Chapman and Hall（1971）.
［4］ Kozen, D.: On Kleene Algebras and Closed Semirings In: Rovan, B.（ed.）MFCS 1990. LNCS, vol. 452, pp. 2647. Springer（1990）.
［5］ Kozen, D.: A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events Information andComputation, 110: 366-390（1994）.
［6］ Mac Lane, S.: Categories for the Working Mathematician, Second Edition Springer（1998）.
［7］ Manes, E., and Mulry, P.: Monad compositions I: general constructions and recursive distributive laws. Theory and Applications of Categories 18: 172-208（2007）.
［8］ Mulvey, C.J.: “&”, Supplemento ai Rendiconti del Circolo Matematico di Palermo, Serie II no. 12, pp. 99-104（1986）.
（受付日2011年11月15日― 103 ―

受理日2011年11月30日）