Notes on subsemigroups of Nm
0(+)
BARBORA BATÍKOVÁ
Faculty of Engineering
Czech University of Life Sciences
Kamýcká 129 165 21 Praha 6 - Suchdol
CZECH REPUBLIC
ANTONÍN JANČAŘÍK
Faculty of Education
Charles University
M. Rettigove 4 116 39 Praha 1
CZECH REPUBLIC
PETR NĚMEC
Faculty of Engineering
Czech University of Life Sciences
Kamýcká 129 165 21 Praha 6 - Suchdol
CZECH REPUBLIC
TOMÁŠ KEPKA
Faculty of Education
Charles University
M. Rettigove 4 116 39 Praha 1
CZECH REPUBLIC
Abstract: The paper summarizes and extends the knowledge of various subsemigroups of Nm
0(+) (=N0(+)m).
It creates a theoretical basis for further study in this area and applications in other areas, such as the investigation
of context-free languages. The last chapter introduces the notion of pure subsemigroups and presents one con-
struction of a pure subsemigroup to a chosen semisubgroup of Nm
0(+).
Key-Words: integer, semigroup, pure, Nm
0(+), subsemigroups, pure subsemigroups
Introduction
This note presents some results on various subsemi-
groups of Nm
0(+) (=N0(+)m). The results show-
cased in this article may encompass both new find-
ings and components of previously published results.
However, consolidating them into a singular output is
a theoretical basis for further research.
The motivation for investigating such problems
stems from several parts of mathematics. Holes in
subsemigroups of Nm
0(+) (if Ais a subsemigroup
of Nm
0(+) then an element hof the pure subsemi-
group generated by Ais said to be a hole in Aif
h/∈A) were applied to transportation problems in
[1]. There also is a close connection with the the-
ory of semirings. For example, the problem whether
every commutative parasemifield (i.e., an algebraic
structure with two commutative and associative bi-
nary operations such that the multiplication is a group
and distributes over addition) finitely generated as a
semiring is additively idempotent was in [2] affirma-
tively answered in 2-generated case by transferring
the problem to subsemigroups of N0m(+) with special
properties; this method was further developed in [3],
[4]. It also seems that the investigation of finitely
generated cones could be useful in the investigation
of context-free languages (see e.g. [5], [6], [7]).
2 Preliminaries (a)
The following notation will be used throughout the
note:
Received: June 5, 2023. Revised: September 4, 2023. Accepted: October 2, 2023. Published: October 20, 2023.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.85
Barbora Batíková, Antonín Jančařík, Petr Němec, Tomáš Kepka
E-ISSN: 2224-2880
773
Volume 22, 2023
N... the semiring of positive integers;
N0... the semiring of non-negative integers;
Z... the ring of integers;
Q+... the parasemifield of positive rationals;
Q+
0... the semifield of non-negative rationals;
R+
0... the semifield of non-negative reals.
Throughout this section, let m∈Nand let Abe a
subset of Qm(the ring of ordered m-tuples of ratio-
nals, where the operations of addition and multipli-
cation are defined componentwise), where we denote
0 = (0, . . . , 0) ∈Qm(no confusion can arise). We
put
conv(A) =
=Pn
i=1 qiai
n∈N, ai∈A, qi∈Q+,Pqi= 1
and cone(A) = Pn
i=1qiai
n∈N,ai∈A,qi∈Q+
0.
Lemma 1.1. (i) A⊆conv(A).
(ii) conv(conv(A)) = conv(A).
(iii) If A⊆(Q+
0)mthen conv(A)⊆(Q+
0)mand,
moreover, 0∈conv(A)if and only if 0∈A.
(iv) If A⊆(Q+)mthen conv(A)⊆(Q+)mand
0 /∈conv(A).
Proof. The assertions (i), (iii) and (iv) are quite easy.
As concerns (ii), take a∈conv(conv(A)). Then
a=Pn
i=1 qiai,n∈N,ai∈conv(A),qi∈Q+and
Piqi= 1. Furthermore, ai=Pki
j=1 qij aij ,ki∈N,
aij ∈A,qij ∈Q+and Pjqij = 1, and hence
a=PiPjqiqij aij . However, PiPjqiqij =
Pi(qiPjqij ) = Piqi= 1. Thus a∈conv(A).
Lemma 1.2. (i) A⊆conv(A)⊆cone(A) =
conv(B), where B={qa |a∈A, q ∈Q+
0}.
(ii) If A6=∅then 0∈cone(A).
(iii) cone(cone(A)) = conv(cone(A)) =
cone(conv(A)) = cone(A).
(iv) If A⊆(Q+
0)mthen cone(A)⊆(Q+
0)m.
Proof. It is easy.
Lemma 1.3. cone(A) = Aif and only if conv(A) =
Aand qA ⊆Afor every q∈Q+
0.
Proof. It is easy.
Lemma 1.4. If A6=∅then cone(A)is just the sub-
semimodule of the Q+
0-semimodule Qmgenerated by
the set A.
Proof. It is easy.
Lemma 1.5. cone(A) = Aif and only if either A=∅
or Ais a subsemimodule of the Q+
0-semimodule Qm.
Proof. See 1.3 and 1.4.
Lemma 1.6. Let n∈N,n≥m+2,q1, . . . , qn∈Q+
0,
a1, . . . , an∈Qmand a=Pqiai. Then there are
r1, . . . , rn∈Q+
0such that a=Priaiand ri1= 0
for at least one i1,1≤i1≤n.
Proof. Clearly, there are s1, . . . , sn−1∈Qsuch that
Pn−1
i=1 si(ai−an) = 0 and si06= 0 for at least one
i0,1≤i0≤n−1. Then Pn
i=1 siai= 0, where
sn=−s1− · · · − sn−1, and we have Psi= 0.
Consequently, the set J={j|sj>0}is a non-
empty subset of the set {1, . . . , n}and we find j0∈
Jsuch that t=qj0/sj0≤qj/sjfor every j∈J.
Clearly, t∈Q+
0. Now, put ri=qi−tsifor all
i= 1, . . . , n. Then ri∈Q+
0and rj0= 0. Finally,
Priai=a.
Lemma 1.7. cone(A) = Scone(B),B⊆A,|B| ≤
m+ 1.
Proof. Let a=Pn
i=1 qiai,n∈N,qi∈Q+
0,ai∈A.
If nis the smallest possible number with this property
then n≤m+ 1 by 1.6. The rest is clear.
Lemma 1.8. cone(A) = {Pm+1
i=1qiai|ai∈A,qi∈
Q+
0}.
Proof. See 1.7.
Lemma 1.9. Assume that Ais a subsemigroup of
Qm(+) that is generated by a non-empty set B. Then
cone(A) = cone(B).
Proof. Since B⊆A, we have cone(B)⊆cone(A).
On the other hand, cone(B)is a subsemigroup of
Qm(+) by 1.4, and hence A⊆cone(B). Conse-
quently, cone(A)⊆cone(cone(B)) = cone(B)by
1.2(iii).
Lemma 1.10. Assume that Ais a subsemigroup of
Qm(+). Then:
(i) For every a∈cone(A),a6= 0, there is k∈Nwith
ka ∈A(⊆conv(A)).
(ii) Either 0 /∈Aand cone(A) = {0} ∪ Sk∈NA/kor
0∈Aand cone(A) = Sk∈NA/k.
Proof. We have a=Pn
i=1 qiai,n∈N,ai∈A,
qi∈Q+. If k∈Nis such that kqi∈Nfor every i
then ka =Pkqiai∈A.
Lemma 1.11. If Ais a subsemigroup of Qm(+) then
cone(A) = {0} ∪ Sk∈Nconv(A/k).
Proof. See 1.10.
Lemma 1.12. Assume that Ais a subsemimodule of
the Q+-semimodule Qm. Then:
(i) If 0∈Athen conv(A) = cone(A) = A.
(ii) If 0 /∈Athen conv(A) = Aand cone(A) = A∪
{0}.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.85
Barbora Batíková, Antonín Jančařík, Petr Němec, Tomáš Kepka
E-ISSN: 2224-2880
774
Volume 22, 2023
Proof. It is easy.
Lemma 1.13. If cone(A) = Qmthen 0∈conv(A).
Proof. There are n∈N,ai∈Aand qi, ri∈Q+
0
such that (−1,0, . . . , 0) = Pqiai,(1,0, . . . , 0) =
Priai,q=Pqi∈Q+and r=Pri∈Q+. Now,
0 = P(qi+ri)ai, and so Pqi+ri
q+rai= 0 as well. But
Pqi+ri
q+r= 1 and it follows easily that 0∈conv(A).
Lemma 1.14. Let Abe a subsemigroup of Qm(+)
and let a∈A,b∈Qmand k, l ∈N0,k+l≥1,
be such that kb −la ∈A(A∪ {0}, resp.). Then
(k−1)a+kb ∈A(A∪ {0}, resp.).
Proof. We have (k−1)a+kb = (kb −la)+(k+
l−1)a∈A.
Lemma 1.15. Let a1, . . . , an∈conv(A),n∈N.
Then (a1+· · · +an)/n∈conv(A).
Proof. It is easy.
3Preliminaries (b)
For a= (q1, . . . , qn)∈Qm, we put ||a|| =pPq2
i∈
R+
0.
Remark 2.1. Let ε={e1, . . . , em}be a basis of
the vector Q-space Qm. For every a∈Qmthere
are uniquely determined πi(a)∈Qsuch that a=
Pπi(a)ei. Then πi:Qm→Qare projections of
the vector Q-spaces and these projections are continu-
ous. Consequently, for every q∈Q+there is t∈Q+
such that |πi(a)|< q for all i= 1, . . . , m, whenever
a∈Qmis such that ||a|| < t.
Lemma 2.2. Let a0, . . . , am∈Qmbe such that
the elements a1−a0, . . . , am−a0are linearly Q
independent (then they form a basis of Qm). Take
q0, . . . , qm∈Q+such that Pm
j=0 qj= 1 and put
a=Pjqjaj. Then there is t∈Q+such that
a+b∈conv({a0, . . . , am})for every b∈Qmwith
||b|| < t.
Proof. Put q=min({qj/m|j= 0,1, . . . , m })∈
Q+. By 2.1, where ε={a1−a0, a2−a0, . . . , am−
a0}, there is t∈Q+such that |πi(b)|< q for all
i= 1, . . . , m, whenever b∈Qmis such that ||b|| <
t. Moreover, if we put π0(b) = −Pm
i=1 πi(b)then
b=Pm
j=0 πj(b)aj,|π0(b)|< q,Pm
j=0 πj(b)=0,
Pm
j=0(qi+πj(b)) = 1 and qj+πj(b)>0for every
j= 0,1, . . . , m. Thus a+b=Pm
j=0(qj+πj(b))ai∈
conv({a0, . . . , am}).
Lemma 2.3. Let a1, . . . , am∈Qmbe linearly in-
dependent elements (then they form a basis of Qm).
Take q1, . . . , qm∈Q+and put a=Pm
i=1 qiai. Then
there is t∈Q+such that a+b∈cone({a1, . . . , am})
for every b∈Qmwith ||b|| < t.
Proof. First, find r∈Q+such that rq < 1, where
q=Pm
i=1 qi∈Q+, and put a0
0= 0,a0
i=ai/rand
q0
i=rqifor i= 1, . . . , m. If q0
0= 1 −rq then q0
j∈
Q+for every j= 0,1, . . . , m,Pm
j=0 q0
j= 1 and a=
Pm
j=0 q0
ja0
j. Now, by 2.2, there is t∈Q+such that
a+b∈conv({a0
0,a0
1, . . . , a0
m})⊆cone({a1, . . . , am})
for every b∈Qmwith ||b|| < t.
Lemma 2.4. Let a1, . . . , am∈Qmbe linearly in-
dependent and let a=Pm
i=1 qiai,qi∈Q+. Then,
for every b∈Qm, there is n∈Nwith na +b∈
cone({a1, . . . , an}).
Proof. By 2.3, there is t∈Q+such that a+
c∈cone({a1, . . . , am})whenever ||c|| < t. Now,
||b/n|| < t for some n∈N, and hence a+
b/n∈cone({a1, . . . , am}). Then na +b∈
cone({a1, . . . , am}).
Lemma 2.5. Let a1, . . . , am∈Qmbe linearly inde-
pendent and let a=Pm
i=1 qiai,qi∈Q+. Then, for
every b∈Qm, there are r, s ∈Q+with ra +sb ∈
conv({a1, . . . , am}).
Proof. By 2.4, na+b∈cone({a1, . . . , am})for some
n∈N. Our result is clear for na +b6= 0. If
na +b= 0 6=athen 06= (n+ 1)a+b∈
cone({a1, . . . , am}). Finally, if a=0=na +b
then b= 0,0∈conv({a1, . . . , am})and we can put
r= 1 = s.
4Preliminaries (c)
In this section, the structure of these subsets is de-
scribed in more detail. Attention is paid to the case
when Ais a subsemigroup of Qm(+).
Let Abe a subset of Qm,m∈N. We put
α(A) = {a∈Qm|(∃b∈Qm)(∀r, s ∈Q+)
ra +sb /∈cone(A)}, β(A) = α(A)∩cone(A),
γ(A) = α(A)∩conv(A)and δ(A) = α(A)∩A.
Lemma 3.1. The following conditions are equivalent
for a∈Qm:
(i) a∈α(A).
(ii) There is at least one c∈Zmsuch that ra +sc /∈
cone(A)for all r, s ∈Q+.
(iii) There is at least one d∈Qmsuch that ra +sd /∈
conv(A)for all r, s ∈Q+.
(iv) There is at least one e∈Zmsuch that ra +se /∈
conv(A)for all r, s ∈Q+.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.85
Barbora Batíková, Antonín Jančařík, Petr Němec, Tomáš Kepka
E-ISSN: 2224-2880
775
Volume 22, 2023
Proof. Clearly, the conditions (i) and (ii) are equiva-
lent, the conditions (iii) and (iv) are equivalent and (i)
implies (iii). It remains to show that (iii) implies (i).
Assume first that ra+sd ∈cone(A)and ra+sd 6= 0.
Then there are n∈N,ai∈Aand qi∈Q+such
that ra +sd =Pn
i=1 qiaiand Pqi=q∈Q+.
Now, (r/q)a+ (s/q)d=P(qi/q)ai,Pqi/q= 1
and (r/q)a+(s/q)d∈conv(A), a contradiction with
(iii). Consequently, if ra +sd 6= 0 for all r, s ∈Q+
then ra +sb /∈cone(A)and a∈α(A).
Next, assume that r1a+s1d= 0 for some r1, s1∈
Q+. Then 0 /∈conv(A),d= (−r1/s1)aand ra +
sd = (r−((r1s/s1))a/∈conv(A)for all r, s ∈Q+.
If a∈cone(A),a6= 0, then r2a∈conv(A)for suit-
able r2∈Q+and, setting r=r2+ (r1s/s1), we get
ra +sd =r2a∈conv(A), a contradiction. It follows
that a∈(Qm\cone(A)) ∪ {0}.
If a/∈cone(A)then, setting b= 0, we get ra +
sb =ra /∈cone(A)for all r, s ∈Q+and a∈α(A).
Finally, if a= 0 then, choosing b∈Qm\cone(A)
(see 1.13), we get ra +sb =sb /∈cone(A)for all
r, s ∈Q+. Again, we obtain a∈α(A).
Lemma 3.2. (i) qα(A)⊆α(A)and qβ(A)⊆β(A)
for every q∈Q+.
(ii) For every a∈β(A),a6= 0, there is r∈Q+with
ra ∈γ(A).
Proof. It is easy.
Lemma 3.3. The following conditions are equiva-
lent:
(i) 0∈α(A).
(ii) 0∈β(A).
(iii) β(A)6=∅.
(iv) α(A)6=∅.
(v) cone(A)6=Qm.
Proof. Clearly, (i) implies (ii), (ii) implies (iii), (iii)
implies (iv) and (iv) implies (v). If b/∈cone(A)then
r0 + sb =sb /∈cone(A)for all r, s ∈Q+. Thus
0∈α(A)and (v) implies (i).
Lemma 3.4. If A⊆(Q+)mthen 0∈β(A).
Proof. We have cone(A)⊆(Q+
0)mand 0∈β(A)by
3.3.
Lemma 3.5. α(A) = (Qm\cone(A)) ∪β(A).
Proof. If a/∈cone(A)then ra /∈cone(A)for every
r∈Q+, and hence a∈α(A).
Lemma 3.6. Let a1, . . . , am∈Qmbe linearly in-
dependent and let a=Pm
i=1 qiai,qi∈Q+. Then
a/∈α(A).
Proof. See 2.4 (or 2.5).
Lemma 3.7. (i) α(cone(A)) = α(A).
(ii) β(cone(A)) = γ(cone(A)) = δ(cone(A)) =
β(A).
Proof. The equalities follow easily from the defini-
tions of the sets involved and from 1.2(iii).
Lemma 3.8. Assume that Ais a subsemigroup of
Qm(+). Then for every a∈β(A),a6= 0, there is
k∈Nwith ka ∈δ(A).
Proof. We have a=Piqiaifor some ai∈A,qi∈
Q+,i= 1, . . . , n,n∈N. Choosing k∈Nsuch that
kqi∈Nfor every i, we get ka ∈A. But ka ∈β(A)
by 3.2(i), and hence ka ∈δ(A).
Corollary 3.9. If Ais a subsemigroup of Qm(+)
then β(A) = Sk∈Nδ(A)/kor β(A) = {0} ∪
Sk∈Nδ(A)/k.
Lemma 3.10. Assume that Ais a subset of (Q+
0)m.
Then Qm\(Q+
0)m⊆α(A).
Proof. We have cone(A)⊆(Q+
0)m, and hence Qm\
(Q+
0)m⊆α(A)by 3.5. On the other hand, if a=
(q1. . . , qm)∈(Q+
0)m\(Q+)mthen qi= 0 for at least
one iand, setting b= (0, . . . , 0,−1,0, . . . , 0) where
−1is the i-th coordinate, we have ra +sb /∈(Q+
0)m
for all r, s ∈Q+. Thus a∈α(A).
Lemma 3.11. Let a1, . . . , am∈Qmbe linearly in-
dependent and let a=Pm
i=1 qiai,qi∈Q+. Then
a/∈α({a1, . . . , am}).
Proof. See 2.5.
Lemma 3.12. The following conditions are equiva-
lent for a∈Qm:
(i) a/∈α(A).
(ii) For every b∈Qmthere are k, l ∈Nwith ka +
lb ∈cone(A).
Moreover, if Ais a subsemigroup of Qm(+) with 0∈
Athen these two conditions are equivalent to
(iii) For every b∈Qmthere are k1, l1∈Nwith
k1a+l1b∈A.
Proof. Clearly, (iii) implies (ii) and (ii) implies (i). If
a/∈α(A)then ra+sb ∈cone(A)for some r, s ∈Q+
and we have tra +tsb ∈cone(A), where t∈Nis
such that tr, ts ∈N. Finally, if Ais a subsemigroup
of Qm(+) and 0∈Athen (ii) implies (iii) by 1.10(i).
Lemma 3.13. If b∈Qm\α(A),a∈Aand q∈Q+
0
then qa +b/∈α(A).
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.85
Barbora Batíková, Antonín Jančařík, Petr Němec, Tomáš Kepka
E-ISSN: 2224-2880
776
Volume 22, 2023
Proof. The result follows easily from 3.12(ii).
Lemma 3.14. Assume that Ais a subsemigroup of
Qm(+). Then either δ(A) = Aor A\α(A)is a
subsemigroup of Qm(+).
Proof. If δ(A)6=Athen A*α(A)and B=A\
α(A)6=∅. Now, the fact that Bis a subsemigroup of
Qm(+) follows from 3.13.
Lemma 3.15. Assume that Ais a subsemigroup of
Qm(+). Then, for all a∈Aand b∈Qm\α(A),
there is n∈Nwith (n−1)a+nb ∈A.
Proof. By 3.12(iii), k1b−l1a∈A∪ {0}for some
k1, l1∈N(notice that cone(A) = cone(A∪{0})) and
α(A) = α(A∪ {0}). Now, by 1.14, (n−1)a+nb ∈
A∪ {0}for some n∈N. If (n−1)a+nb = 0 then
(2n−1)a+ 2nb =a∈A.
5Subsemigroups of Nm
0(+) (a)
In this section, let Abe a subsemigroup of Nm
0(+).
We denote by ε(A)the set of the elements a∈Asuch
that b−a∈A, whenever b∈Aand b−a∈Nm
0.
Equivalently, ε(A) = {a∈A|A+a= (Nm
0+a)∩
A}.
Lemma 4.1. The following conditions are equiva-
lent:
(i) 0∈A.
(ii) 0∈ε(A).
(iii) ε(A)6=∅.
Proof. Clearly, (i) implies (ii) and (ii) implies (iii). It
remains to show that (iii) implies (i). If a∈ε(A)then
a=a+ 0, and so a∈(Nm
0+a)∩A=A+a. Then
a=b+afor some b∈Aand, of course, b= 0.
Lemma 4.2. Either 0 /∈Aand ε(A) = ∅or 0∈
ε(A)⊆Aand ε(A)is a subsemigroup of A.
Proof. It is easy (use 4.1).
In the rest of the section, we will assume that 0∈
A(see 4.1 and 4.2).
Lemma 4.3. (i) If b, a ∈ε(A)are such that b−a∈
Nm
0then b−a∈ε(A).
(ii) (ε(A)−ε(A)) ∩Nm
0=ε(A).
(iii) ε(ε(A)) = ε(A).
Proof. (i) Since a∈ε(A)and b∈A, we have b−a∈
A. Now, if c∈Ais such that c−(b−a) = (c+a)−b∈
Nm
0then c+a∈Aand c−(b−a)∈A, since b∈ε(A).
Thus b−a∈ε(A).
(ii) and (iii). Use (i).
Lemma 4.4. ε(A)−ε(A)⊆Zmand ε(A)−ε(A)is
just the difference (sub)group of the (sub)semigroup
ε(A).
Proof. It is easy.
Lemma 4.5. If A+a∈ε(A)for at least one a∈Nm
0
then ε(A) = A.
Proof. First, a= 0 + a∈a+A⊆ε(A), and so
a∈ε(A). Now, A= ((A+a)−a)∩Nm
0⊆(ε(A)−
ε(A)) ∩Nm
0=ε(A)by 4.3(ii). Thus ε(A) = A.
Corollary 4.6. If ε(A)6=Athen for every a∈Nm
0
there is at least one b∈Asuch that a+b/∈ε(A).
For every a∈A, put ϕ(A, a) = {b∈Nm
0|a+
b∈A},ψ(A, a) = {c∈Nm
0|(n−1)a+nc ∈
Afor some n∈N}and ξ(A, a) = ϕ(A, a)∩
ψ(A, a).
Lemma 4.7. (i) A∪ {0} ⊆ ξ(A, a).
(ii) Nm
0\α(A)⊆ψ(A, a).
(iii) Nm
0∩Qa⊆ψ(A, a).
Proof. (i) It is obvious.
(ii) This is ensured by 3.15.
(iii) We can assume that a6= 0. Take b∈Nm
0∩Qa,
b6= 0. We have b=ra/bfor some r∈Z,s∈N,
and hence sb =ra and we conclude easily that r∈
N. Now, sb −ra = 0 and (s−1)a+sb ∈A(see
1.14).
Lemma 4.8. If a∈ε(A)then both ϕ(A, a)and
ξ(A, a)are subsemigroups of Nm
0(+).
Proof. First, if a+b1∈Aand a+b2∈Afor some
b1, b2∈Nm
0then 2a+b1+b2∈Aand a+b1+
b2∈Nm
0. Since a∈ε(A), we get a+b1+b2∈A.
Similarly, if c1, c2∈ξ(A, a)then (n−1)a+nci∈A
for some n∈N,n≥3,(2n−2)a+n(c1+c2)∈A
and, since a∈ε(A), we conclude that (n−1)a+
n(c1+c2)∈A.
6Subsemigroups of Nm
0(+) (b)
Define a relation ≤on Nm
0by a≤bif and only if
b−a∈Nm
0. Clearly, the relation ≤is reflexive, anti-
symmetric and transitive, and hence it is an ordering.
This ordering is stable under both addition and multi-
plication. Notice that it satisfies the descending chain
condition, but not the ascending one.
Lemma 5.1. There is no infinite set of pair-wise in-
comparable m-tuples in Nm
0.
Proof. The assertion is clear for m= 1 and we pro-
ceed by induction for m≥2.
Let Abe a set of pair-wise incomparable elements
from Nm
0. For k∈N0, put Bk={b∈Nm−1
0|a≤
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.85
Barbora Batíková, Antonín Jančařík, Petr Němec, Tomáš Kepka
E-ISSN: 2224-2880
777
Volume 22, 2023
(b, k)for at least one a∈A}. Then B0⊆B1⊆
B2⊆. . . and all the sets Bkare filters of the ordered
set Nm−1
0. Then B=SBkis a filter and we denote
by Cthe set of minimal elements of B. The elements
of Care pair-wise incomparable, and hence Cis a
finite set by induction. Consequently, C⊆Bk0for
some k0and it follows that Bk0=Bk0+1 =· · · =
B. Now, if a= (b1, k1)∈A,b1∈Nm−1
0,k1∈
N0, then b1∈Bk1⊆B=Bk0, and therefore a1≤
(b1, k0)for some a1∈A. If k0≤k1then a1≤
a, and hence a1=aand k1=k0. It means that
k1≤k0anyway. Furthermore, if Cidenotes the set
of minimal elements from Bi,i= 0,1, . . . , k0, then
Ciis a finite set (and Ck0=C). Since b1∈Bk1, there
is c1∈Ck1with c1≤b1and (c1, k1)≤a. According
to the definition of Bk1, we can find a2∈Asuch that
a2≤(c1, k1). Then a2≤a, and therefore a2=aand
b1=c1. We have proved that A⊆Sk0
i=0(Ci× {i})
and it follows immediately that Ais finite.
Example 5.2. Put m= 2. Then An=
{(0, n),(1, n −1), . . . , (n−1,1),(n, 0)}(⊆N2
0),
n∈N0, is a set of incomparable elements and |An|=
n+ 1.
Proposition 5.3. Let A1be a non-empty finite subset
of Nm
0and let Abe a subsemigroup of Nm
0(+) such
that A1⊆A⊆cone(A1). Then Ais a finitely gener-
ated semigroup.
Proof. Let A1={a1, . . . , an},n∈N, and B=
{Pn
i=1 qiai|qi∈Q+
0, qi≤1} ∩ Nm
0. Clearly, A1⊆
A⊆cone(A1)∩Nm
0and Bis a finite subset of Nm
0.
If a∈Athen a=Priai,ri∈Q+
0, and we have
ri=li+sifor suitable li∈N0and si∈Q+
0,si≤1.
From this, a=b1+Pliai, where b1=Psiai.
Since a∈Nm
0and Pliai∈Nm
0, we get b1∈B.
Moreover, either Pliai= 0 or Pliai∈A.
For every b∈B, put Nb={(k1, . . . , kn)∈
Nn
0|b+Pkiai∈A}. Then Nbis a filter of the or-
dered set Nm
0(see 5.1 and its proof) and the set Mbof
minimal elements from Nbis finite. Of course, Nb=
{d∈Nm
0|c≤dfor some c∈Mb}and the set
C={a1, . . . , an} ∪ Sb∈B{b+kiai|(k1, . . . , kn)∈
Mb}is a finite subset of A. Taking into account the
preceding steps, one sees easily that the semigroup A
is generated by the finite subset C.
Theorem 5.4. The following conditions are equiva-
lent for a subsemigroup Aof Nm
0(+):
(i) Ais a finitely generated semigroup.
(ii) cone(A) = cone(A1)for a non-empty finite sub-
set A1of A.
(iii) cone(A) = cone(A2)for a non-empty finite sub-
set A2of (Q+
0)m.
Proof. (i) implies (ii) by 1.9, (ii) implies (iii) trivially
and (ii) implies (i) by 5.3. It remains to show that (iii)
implies (ii).
Since A2is a finite subset of cone(A), there is
a finite subset A1of Asuch that A2⊆cone(A1).
Then cone(A) = cone(A2)⊆cone(cone(A1)) =
cone(A1)⊆cone(A). Thus cone(A) =
cone(A1).
Corollary 5.5. Let Abe a finitely generated subsemi-
group of Nm
0(+). Then every subsemigroup A0of
Nm
0(+) such that A⊆A0⊆cone(A)is finitely gen-
erated. In particular, cone(A)∩Nm
0is a finitely gen-
erated subsemigroup of Nm
0(+).
Remark 5.6. It is easy to see that 5.4 remains true for
subsemigroups of (Q+
0)m(+). Indeed, let Bbe such a
subsemigroup and assume that cone(B) = cone(B1)
for a non-empty finite subset B1of B. We have B1=
{k1/l1, . . . , kn/ln}for some n∈N,ki∈N0and
li∈N. If l=l1· · · lnthen A=lB is a subsemigroup
of Nm
0(+) and cone(A) = cone(B) = cone(B1) =
cone(A1), where A1=lB1. By 5.4, Ais a finitely
generated semigroup and the same is true for B, since
the mapping a7→ a/l,a∈A, is an isomorphism of
Aonto B.
7Pure subsemigroups of Nm
0(+)
In this section, let Abe a subsemigroup of Nm
0(+).
Lemma 6.1. The following conditions are equiva-
lent:
(i) nA =A∩nNm
0for every n∈N.
(ii) If a∈Nm
0and n∈Nare such that na ∈Athen
a∈A.
(iii) If a∈Nm
0and q∈Q+are such that qa ∈A
then a∈A.
Proof. It is easy.
If these equivalent conditions are satisfied then A
is called pure subsemigroup of Nm
0(+). In the re-
maining part of this section(except for 6.12), we will
assume that Ais a pure subsemigroup.
Lemma 6.2. A∪ {0}is a pure subsemigroup of
Nm
0(+).
Proof. It is easy.
Lemma 6.3. If 0∈Athen ε(A)is a pure subsemi-
group of Nm
0(+).
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.85
Barbora Batíková, Antonín Jančařík, Petr Němec, Tomáš Kepka
E-ISSN: 2224-2880
778
Volume 22, 2023
Proof. By 4.2, ε(A)is a subsemigroup of A. Let a=
nb, where n∈N,a∈ε(A)and b∈Nm
0. Since Ais
pure, we have b∈A. Moreover, if c∈Ais such that
c−b∈Nm
0then nc −a=n(c−b)∈Nm
0, and so
n(c−b)∈A, since a∈ε(A). Using again the fact
that Ais pure, we get c−b∈A. Thus b∈ε(A)and
ε(A)is pure.
Lemma 6.4. Let n∈N,a1, . . . , an∈Aand
q1, . . . , qn∈Q+be such that a=Pqiai∈Nm
0.
Then a∈A.
Proof. We have qi=ri/sifor some ri, si∈N. If
s=s1· · · snthen sqi∈N,bi=sqiai∈Aand
sa =Pbi∈A. Now, a∈Aby 6.1.
Lemma 6.5. If a∈Nm
0and a/∈α(A)then a∈A.
Proof. By 3.3, a6= 0. If b∈Athen there are
r, s ∈Q+with ra −sb ∈cone(A)and we get ra ∈
cone(A) + sb ⊆cone(A). Thus a∈cone(A)∩Nm
0
and a∈Aby 6.4.
Proposition 6.6. (i) cone(A)∩Nm
0=A∪ {0}.
(ii) If 0∈Athen A=cone(A)∩Nm
0.
(iii) If cone(A) = (Q+
0)mthen A∪ {0}=Nm
0.
(iv) α(A)∩Nm
0= (Nm
0\A)∪δ(A).
(v) Nm
0= (α(A)∩Nm
0)∪A.
(vi) ξ(A, a) = ψ(A, a)for every a∈A.
Proof. (i), (ii) and (iii). Use 6.4.
(iv) and (v). Use 6.5.
(vi) If (n−1)a+nc ∈Athen n(a+c)∈Aand
a+c∈A. Thus ψ(A, a)⊆ϕ(A, a)and ξ(A, a) =
ψ(A, a).
Remark 6.7. Let k∈Nand a, b1, . . . , bk∈Nm
0be
such that a+bi∈Afor every i= 1, . . . , k (e.g.,
a∈Aand bi∈ϕ(A, a)). Furthermore, assume that
there are ni∈Nsuch that (ni−1)a+nibi∈Afor
every i(e.g., a∈Aand bi∈ψ(A, a)). If n∈N,
n≥max(ni)then (n−1)a+nbi∈Afor all i.
In particular, if ti∈N0are such that t=Pti≥
max(ni)then (t−1)a+tbi∈Aand (t−1)a+
Ptibi=P((ti/t)((t−1)a+tbi),(t−1)a+Ptibi∈
Nm
0. Now, by 6.4, we get (t−1)a+Ptibi∈A.
Lemma 6.8. If a∈Aand b∈Nm
0are such that
a+b/∈α(A)then a+b∈Aand b∈ξ(A, a).
Proof. Since a+b/∈α(A),a+b∈Aby 6.6(v) and
there are r, s ∈Q+such that r(a+b)−sa ∈cone(A).
We have r=k/n,s=l/nfor suitable k, l, n ∈N
and c/n=r(a+b)−sa ∈cone(A), where c= (k−
l)a+kb. Then c∈Zm∩cone(A) = Zm∩(Q+
0)m∩
cone(A) = Nm
0∩cone(A) = A∪ {0}(see 6.6(i)), so
that c∈A∪{0}and d= (k−1)a+kb =c+(l−1)a∈
A∪ {0}. If d6= 0 then d∈Aand b∈ξ(A, a)(see
6.6(vi)). If d= 0 then b= 0 ∈ξ(A, a).
Lemma 6.9. Let a∈Abe such that b∈ψ(A, a)for
every b∈Nm
0with a+b∈δ(A)(then b∈α(A)).
Then ϕ(A, a) = ψ(A, a) = ξ(A, a).
Proof. We have ψ(A, a) = ξ(A, a)⊆ϕ(A, a)by
6.6(vi). If b∈ϕ(A, a)then a+b∈Aand if a+b/∈
α(A)then b∈ξ(A, a)by 6.8. On the other hand, if
a+b∈α(A)then a+b∈α(A)∩A=δ(A)and
b∈ψ(A, a)by assumption.
Lemma 6.10. Let a∈Abe such that δ(A)⊆Qa.
Then ϕ(A, a) = ψ(A, a) = ξ(A, a).
Proof. In view of 6.9, if b∈Nm
0is such that a+b∈
δ(A)then a+b∈Qa,b∈Qaand b∈ψ(A, a)by
4.7(iii).
Lemma 6.11. The following conditions are equiva-
lent for all a∈Aand b∈Nm
0:
(i) b∈ψ(A, a)(b∈ξ(A, a), resp.).
(ii) r(a+b)−sa =Pk
i=1 qiaifor some r, s ∈Q,
k∈N,ai∈Aand qi∈Q+.
Proof. See the proof of 6.8.
Construction 6.12. Let Abe a subsemigroup of
Nm
0(+). Put p(A) = Nm
0∩Sn∈NA/n. It is
easy to check that p(A)is a pure subsemigroup of
Nm
0(+). It is the smallest pure subsemigroup con-
taining A. Clearly, A⊆p(A)⊆cone(A), and so
cone(p(A)) = cone(A). Now, according to 5.4, p(A)
is finitely generated if and only if Ais so. Finally, no-
tice that Nm
0∩Sn∈Nε(A)/n⊆ε(p(A)). In partic-
ular, ε(A)⊆ε(p(A)), and so ε(p(A)) 6=∅, provided
that ε(A)6=∅.
8Conclusion
In this paper, the properties of subsemigroups and
pure subsemigroups of Nm
0(+) (=N0(+)m) are in-
vestigated. A theoretical and reference basis for fur-
ther research in this area has been established. It
can be used for further research of finitely gener-
ated cones, e.g. in connection with the investigation
of context-free languages. Our further research will
be directed to a deeper description of pure subsemi-
groups of Nm
0for a finite m, in particular m= 2.
References:
[1] R. Hemmecke, A. Takemura, R. Yoshida, Com-
puting holes in semigroups and its application to
transportation problems, Contribution to Discrete
Mathematics America Vol. 1, No. 4, 2009
[2] J. Ježek, V. Kala, T. Kepka, Finitely generated
algebraic structures with various divisibility con-
ditions, Forum Mathematicum, Vol. 24, 2012, pp.
379–397.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.85
Barbora Batíková, Antonín Jančařík, Petr Němec, Tomáš Kepka
E-ISSN: 2224-2880
779
Volume 22, 2023
[3] J. Ježek, T. Kepka, Finitely generated commu-
tative division semirings, Acta Univ. Carolinae
Math. Phys., Vol. 51, 2010, pp. 3–27.
[4] V. Kala, T. Kepka, M. Korbelář, Notes on com-
mutative parasemifields, Comment. Math. Univ.
Carolinae. Vol. 50, 2009, pp. 321–533.
[5] J. Beauquier, M. Blattner, M. Latteux, On com-
mutative context/free languages, J. Comput. Sys-
tems Sci. 35 (1987), pp. 311–320.
[6] M. Latteux, Cônes rationnels commutatifs, J.
Comput. Systems Sci.. Vol. 18, 1979, pp.
307–333.
[7] T. Kepka, J. Kortelainen, M. Latteux, On
face-structure of convex polyhedrons induced
by simple commutative context-free languages,
(preprint)
Contribution of individual authors to
the creation of a scientific article
(ghostwriting policy)
B. Batíková – formal analysis and investigation.
A. Jančařík – validation and writing - review &
editing.
P. Němec – investigation, writing - original draft,
validation.
T. Kepka – supervision, validation and methodology.
Sources of Funding for Research Presented in a
Scientific Article or Scientific Article Itself
No funding was received for conducting this study.
Conflict of Interest
The authors have no conflicts of interest to declare
that are relevant to the content of this article.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en
_US
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.85
Barbora Batíková, Antonín Jančařík, Petr Němec, Tomáš Kepka
E-ISSN: 2224-2880
780
Volume 22, 2023
