H−,R−and L−cross-sections of the infinite symmetric inverse semigroup ISX
All H−,R− and L−cross-sections of the infinite symmetric inverse semigroup ISX are described.
Gespeichert in:
| Datum: | 2005 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2005
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/156604 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | H−,R−and L−cross-sections of the infinite symmetric inverse semigroup ISX / V. Pyekhtyeryev // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 1. — С. 92–104. — Бібліогр.: 6 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-156604 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1566042019-06-19T01:28:21Z H−,R−and L−cross-sections of the infinite symmetric inverse semigroup ISX Pyekhtyeryev, V. All H−,R− and L−cross-sections of the infinite symmetric inverse semigroup ISX are described. 2005 Article H−,R−and L−cross-sections of the infinite symmetric inverse semigroup ISX / V. Pyekhtyeryev // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 1. — С. 92–104. — Бібліогр.: 6 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 20M20, 20M10. http://dspace.nbuv.gov.ua/handle/123456789/156604 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
All H−,R− and L−cross-sections of the infinite
symmetric inverse semigroup ISX are described. |
| format |
Article |
| author |
Pyekhtyeryev, V. |
| spellingShingle |
Pyekhtyeryev, V. H−,R−and L−cross-sections of the infinite symmetric inverse semigroup ISX Algebra and Discrete Mathematics |
| author_facet |
Pyekhtyeryev, V. |
| author_sort |
Pyekhtyeryev, V. |
| title |
H−,R−and L−cross-sections of the infinite symmetric inverse semigroup ISX |
| title_short |
H−,R−and L−cross-sections of the infinite symmetric inverse semigroup ISX |
| title_full |
H−,R−and L−cross-sections of the infinite symmetric inverse semigroup ISX |
| title_fullStr |
H−,R−and L−cross-sections of the infinite symmetric inverse semigroup ISX |
| title_full_unstemmed |
H−,R−and L−cross-sections of the infinite symmetric inverse semigroup ISX |
| title_sort |
h−,r−and l−cross-sections of the infinite symmetric inverse semigroup isx |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2005 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/156604 |
| citation_txt |
H−,R−and L−cross-sections of the infinite symmetric inverse semigroup ISX / V. Pyekhtyeryev // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 1. — С. 92–104. — Бібліогр.: 6 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT pyekhtyeryevv hrandlcrosssectionsoftheinfinitesymmetricinversesemigroupisx |
| first_indexed |
2025-07-14T08:59:54Z |
| last_indexed |
2025-07-14T08:59:54Z |
| _version_ |
1837612238054096896 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 1. (2005). pp. 92 – 104
c© Journal “Algebra and Discrete Mathematics”
H−,R− and L−cross-sections of the infinite
symmetric inverse semigroup ISX
Vasyl Pyekhtyeryev
Communicated by V. V. Kirichenko
Dedicated to Yu.A. Drozd on the occasion of his 60th birthday
Abstract. All H−,R− and L−cross-sections of the infinite
symmetric inverse semigroup ISX are described.
Introduction
Let ρ be an equivalence relation on a semigroup S. The subsemigroup
T ⊂ S is called a cross-section with respect to ρ if T contains exactly 1
element from every equivalence class. Clearly, the most interesting are
the cross-sections with respect to the equivalence relations connected with
the semigroup structure on S. The first candidates for such relations are
congruences and the Green relations.
The Green relations L,R,H,D and J on semigroup S are defined
as binary relations in the following way: aLb if and only if S1a = S1b;
aRb if and only if aS1 = bS1; aJ b if and only if S1aS1 = S1bS1 for any
a, b ∈ S and H = L ∧R, D = L ∨R.
Cross-sections with respect to the H− (L−,R−,D−,J−) Green re-
lations are called H− (L−,R−,D−,J−) cross-sections in the sequel.
The study of cross-sections with respect to Green relations for some
classical semigroups was initiated a few years ago. For the semigroup
ISn all H−cross-sections were classified in [CR] and all L− and R−cross-
sections were classified in [GM1]. For the full transformation semigroup
2000 Mathematics Subject Classification: 20M20, 20M10.
Key words and phrases: Symmetric inverse semigroup, Green relations, cross-
sections.
V. Pyekhtyeryev 93
TX all H− and R−cross-sections were described in [P1] and [P2], and for
the Brauer semigroup all H−,L− and R−cross-sections were classified
in [KMM].
In the present paper all H−,R− and L− cross-sections of the infinite
symmetric inverse semigroup ISX are described. The paper is organized
as follows. We collect all necessary preliminaries in Section 1. Section 2 is
dedicated to the construction and classification of all H−cross-sections of
ISX . Also we prove that every two H−cross-sections are isomorphic. In
Section 3 we describe all R− and L−cross-sections in ISX . Since infinity
of the set X is not used in the proof, we see that from this description one
immediately gets the well-known(see [GM1]) description of the R−(L−)
cross-sections for the finite symmetric inverse semigroup ISn. Finally, in
Section 4 we determine, which R− (L−) cross-sections are isomorphic.
1. Preliminaries
Let X be an arbitrary infinite set.
The symmetric inverse semigroup on X is the semigroup of all one-
to-one partial transformations on X under composition. It is denoted
by ISX . For a ∈ ISX by dom(a) and im(a) we denote the domain and
the image of the element a respectively. The cardinal number rk(a) =
|dom(a)| = |im(a)| is called the rank of a.
It is well-known (see for example [GM2]) that the Green relations on
ISX can be described as follows:
aRb if and only if dom(a) = dom(b);
aLb if and only if im(a) = im(b);
aHb if and only if dom(a) = dom(b) and im(a) = im(b);
aDb if and only if rk(a) = rk(b).
In particular, Green’s D−classes are Dk = { a ∈ ISX | rk(a) = k}, 1 ≤
k ≤ |X|.
Recall that a binary relation < on X is a well order if it is reflexive,
antisymmetric, transitive and satisfies the following properties: (i) for all
x, y ∈ X, either x < y or y < x; (ii) every non-empty subset Y ⊆ X has
the smallest element.
If the set X is equipped with a well order, then denote by ξ(X)
the order-type of this ordered set. Denote by W (α) the set of all ordinal
numbers less than α. If ξ(X) = α, then there exists a unique isomorphism
f : X → W (α). Denote by xβ := f−1(β) for every β ∈ W (α). Then
X =
⋃
β<α{xβ}, moreover, xβ < xγ iff β < γ. For every η ≤ α denote by
X(η) the set {xβ ∈ X|β < η} .
Let ω be the order-type of the natural numbers in their usual order.
94 H−,R− and L−cross-sections of ISX
2. Description of H− cross-sections
From the structure of Green relation H on the semigroup ISX it follows
that each H−class of this semigroup is uniquely determined by two sets
A, B ⊆ X with |A| = |B|. Denote by H(A, B) the H−class determined
by these sets.
Theorem 1. Let X be an countable set and < be an arbitrary well order
of type ω on the set X. Then
I(X, <) = {a ∈ ISX | x < y implies a(x) < a(y) for all x, y ∈ dom(a)}
is an H−cross-section of ISX .
Moreover, if <1 6=<2, then I(X, <1) 6= I(X, <2).
Proof. It is obvious, that I(X, <) is closed under multiplication. Also,
since ω is the smallest transfinite number, we see that for every H−class
H the intersection H ∩ I(X, <) contains exactly one element. This com-
pletes the proof of the first part of our theorem.
Let x′
1 <1 x′
2 <1 x′
3 <1 . . . and x′′
1 <2 x′′
2 <2 x′′
3 <2 . . . be two
different well orders of the type ω on the set X. By k denote the smallest
number such that x′
k 6= x′′
k. We consider the following two cases:
1) k = 1. Let x′′
m = x′
1 = x, x′
n = x′′
1 = y. Then the set Y :=
{x ∈ X|x >1 x′
n, x >2 x′′
m} is not empty. By z denote an arbitrary
element of Y . Then x <1 y <1 z and y <2 x <2 z. Therefore in this
case, we have
(
x y
y z
)
∈ I(X, <1) and also
(
x y
y z
)
/∈ I(X, <2). Hence,
I(X, <1) 6= I(X, <2).
2) k > 1. Let x′
1 = x, x′
k = y, x′′
k = z. Then x <1 y <1 z and
x <2 z <2 y. Arguing as above, we see that I(X, <1) 6= I(X, <2).
Theorem 2. Suppose X is an arbitrary infinite set.
a) The semigroup ISX contains H−cross-sections if and only if the
set X is countable.
b) If X is countable, then every H−cross-section of ISX has the form
I(X, <) for some well order < of the type ω on the set X. Moreover,
every two H−cross-sections are isomorphic.
Proof. a) Sufficiency follows from Theorem 1.
Necessity. Let T be an H−cross-section of ISX . Let K denote the
complete graph on X. We orient the edges E of K as follows:
For any x, y ∈ X, let ax,y be a unique element of T such that
ax,y({1, 2}) = {x, y}. Note that ax,y = ay,x. Define
(x, y) ∈ E if ax,y(1) = x, ax,y(2) = y
(y, x) ∈ E if ax,y(1) = y, ax,y(2) = x.
V. Pyekhtyeryev 95
Clearly this provides an orientation of the edges.
We proceed by a sequence of lemmas.
Lemma 1. Let a be an arbitrary element of T and x, y ∈ dom(a). If
(x, y) ∈ E, then (a(x), a(y)) ∈ E.
Proof. The proof is analogous to one of Lemma 3.3 in [CR].
Lemma 2. K has no cycles.
Proof. The proof is analogous to one of Lemma 3.4 in [CR].
Lemma 3. K does not contain two infinite paths such that one of them
possesses an initial vertex and the other possesses a terminal vertex.
Proof. Assume the converse. Let (x1, x2, · · · ) and (· · · , y−1, y0) be two
such paths. Suppose a is a unique element of the set T ∩ H({xi|i ∈
N}, {yi|i ∈ Z\N}). Let yk = a(x1) and xl = a−1(yk−1). Then by Lemma
1, we obtain (xl, x0) ∈ E. This contradicts Lemma 2 and the lemma is
proved.
From the previous Lemma it follows that K does not contain two-
sided infinite paths.
We define the graph K ′ = (X, E′) as follows:
K ′ = K, if every infinite path of K possesses an initial vertex,
K ′ = Kc, if every infinite path of K possesses a terminal vertex,
where Kc has the same vertex set as K and an arrow is in Kc if and only
if its converse is in K. Then every infinite path of the graph K ′ possesses
an initial vertex and also Lemmas 1-3 hold true for this graph.
For arbitrary x ∈ X denote by Px the set {y ∈ X|(y, x) ∈ E′}.
Lemma 4. If |Px| > 0, then there exists a unique element xp ∈ Px such
that (y, xp) ∈ E′ for all y ∈ Px\{xp}.
Proof. Consider an element x1 of Px. Let us move along the arrows of
K ′ the end of which also belongs to Px. Assume this process is infinite.
Then since K ′ has no cycles, we obtain an infinite path (x1, x2, x3, · · · ).
Moreover, xi ∈ Px for all i ∈ N. Suppose a is a unique element of the set
T ∩ H({xi|i ∈ N} ∪ {x}, {xi|i ∈ N}). Let xk = a(x) and xl = a−1(xk+1).
Then by Lemma 1, we have (x, xl) ∈ E′. This contradicts xl ∈ Px.
This implies that there exists a finite path (x1, x2, . . . , xn) which it is
impossible to prolong. Thus there is no arrow with the beginning xn and
the end in Px. Hence xn satisfies lemma’s conditions. Now assume there
96 H−,R− and L−cross-sections of ISX
exists an element y with the above property. Then (xn, y) ∈ E′,(y, xn) ∈
E′ and by Lemma 2 y = xn. This completes the proof of the lemma.
Lemma 5. For any non-empty subset Y ⊆ X there exists a unique ele-
ment z ∈ Y such that (z, y) ∈ E′ for all y ∈ Y \{z}.
Proof. Assume there is no such an element. Since K ′ has no cycles, we
see that starting at any element of the set Y we can move opposite the
direction of the arrows infinitely long and thus construct an infinite path
without an initial vertex. This contradicts the definition of the graph K ′.
Now assume there exist two different elements x and z with the above
property. Then (x, z) ∈ E′ and (z, x) ∈ E′. This contradicts Lemma 2
and the statement is proved.
Define x < y ⇐⇒ (either x = y or (x, y) ∈ E′).
Lemma 6. The relation < is a linear order.
Proof. From the definition of the graph K ′ it follows that either x < y or
y < x for all x, y ∈ X. Now let x < y and y < z. Assume that z < x; then
the graph K ′ contains the cycle x − y − z − x. This contradicts Lemma
2 and so x < z. Thus < is transitive. Since the proof of reflexivity and
anti-symmetry of the relation are trivial, the lemma is proved.
Lemma 7. The relation < is a well order of type ω.
Proof. From Lemma 5 and Lemma 6 it follows that the order < is a well
order. Also we have that for any x ∈ X such that |Px| > 0 there exists a
predecessor by Lemma 4. This completes the proof of the lemma.
By Lemma 7 the set X is countable.
b) Suppose X is an arbitrary countable set, T is an H−cross-section
of ISX , and < is the well order of the type ω on X defined in the proof of
item a). Let S = I(X, <). From Lemma 1, we see that T ⊆ S. Since T
and S contain exactly one element from every H−class of ISX , we obtain
T = S.
Now let S1 = I(X, <1) and S2 = I(X, <2) be two H−cross-sections
of ISX determined by the orders
x′
1 <1 x′
2 <1 x′
3 <1 . . .
x′′
1 <2 x′′
2 <2 x′′
3 <2 . . .
Let θ denote the permutation of X such that x′
i 7→ x′′
i (i ∈ N). Then the
mapping
V. Pyekhtyeryev 97
Θ : α 7→ θ−1αθ (α ∈ S1)
is an isomorphism of S1 onto S2.
3. Description of R− and L− cross-sections
Since for a, b ∈ ISX the condition aRb is equivalent to the condition
dom(a) = dom(b), the equalities a = b and dom(a) = dom(b) are equiva-
lent for elements a, b from arbitrary R−cross-section T of ISX . We will
frequently use this fact in the paper.
>From the structure of Green relation R on the semigroup ISX it
follows that each R−class of this semigroup is uniquely determined by a
set A ⊆ X. Denote by R(A) the R−class determined by this set.
Let a well order < on the set X be fixed and ξ(X) = α.
Now construct the set R(X, <) in the following way: an element a ∈
R(A) with ξ(A) = η ≤ α belongs to R(X, <) if and only if the map a is
an isomorphism of the well-ordered sets A and X(η). Then it is obvious,
that R(X, <) contains exactly one element from every R−class.
Lemma 8. For every well order < on the set X the set R(X, <) is closed
under multiplication.
Proof. Let a, b ∈ R(X, <) be arbitrary elements. Then there exist two
R−classes R(A), R(B) such that a ∈ R(A), b ∈ R(B). Let us give some
notation.
ηA := ξ(A), ηB := ξ(B), C := X(ηA) ∩ B, ηC := ξ(C) = ξ(b|C).
Then dom(ab) = a−1(C) and ξ(dom(ab)) = ηC . To complete the proof
it is now enough to show that b|C = X(ηC). First suppose X(ηC) * b|C .
Let xγ be the smallest element of the set X(ηC)\b|C . Since γ < ηC ,
there exists δ > γ such that xδ ∈ b|C , because otherwise b|C ⊂ X(γ) and
this implies ηC = ξ(b|C) ≤ γ. Moreover, from γ < ηC it follows that
γ < ηB and xγ ∈ im(b). Let xǫ := b−1(xγ). Since xǫ /∈ C, we have xǫ ≥
xα > b−1(xδ). This contradicts to the fact that b is an isomorphism of
well-ordered sets. Thus our assumption is wrong. Therefore X(ηC) ⊆ b|C .
Now the equality b|C = X(ηC) immediately follows from ξ(b|C) = ηC .
Lemma 9. For every well order < on the set X the set R(X, <) is an
R−cross-section in ISX .
Proof. By Lemma 8 this set is closed under multiplication. Hence R(X, <
) is a subsemigroup of ISX . But from the construction of this set it also
follows that R(X, <) contains exactly one element from every R−class
and the statement is proved.
98 H−,R− and L−cross-sections of ISX
Let now X =
⋃
i∈I Xi be an arbitrary decomposition of X into a
disjoint union of non-empty blocks, where the order of blocks is not im-
portant. Assume that a well order <i is fixed on the elements of the
block Xi for all i ∈ I. The decomposition X =
⋃
i∈I Xi together with a
fixed well order on every block will be denoted by {
⋃
i∈I(Xi, <i)}. The
notation {
⋃
i∈I(Xi, <i)} 6= {
⋃
j∈J(Xj , <j)} then means that either the
decompositions X =
⋃
i∈I Xi and X =
⋃
j∈J Xj are different or there
exists a block on which the fixed well orders are different.
Let αi be the order-type of the set Xi. Now construct the set
R({
⋃
i∈I(Xi, <i)}) in the following way: an element a ∈ R(A) belongs
to R({
⋃
i∈I(Xi, <i)}) if and only if the map a|A∩Xi
is an isomorphism of
A ∩ Xi and Xi(ηi), where ηi = ξ(A ∩ Xi) ≤ αi for all i ∈ I.
Theorem 3. a) For an arbitrary decomposition X =
⋃
i∈I Xi and arbi-
trary well orders on the elements of every block of this decomposition the
set R({
⋃
i∈I(Xi, <i)}) is an R−cross-section of ISX .
b) If {
⋃
i∈I(Xi, <i)} 6= {
⋃
j∈J(Xj , <j)} then one has that
R({
⋃
i∈I(Xi, <i)}) 6= R({
⋃
j∈J(Xj , <j)}).
c) Moreover, every R−cross-section of ISX has the form
R({
⋃
i∈I(Xi, <i)}) for some decomposition X =
⋃
i∈I Xi and some well
orders <i on the elements of every block.
Proof. a) We can regard elements of R({
⋃
i∈I(Xi, <i)}) as all possible col-
lections (ai ∈ R(Xi, <i))i∈I with component-wise multiplication. There-
fore, the item a) follows from Lemma 9.
b) Obvious.
c) Now let T be an R−cross-section of ISX . By I denote the set {x ∈
X| id{x} ∈ T}. By definition, put Xi = {a−1(i)| a ∈ T and im(a) = {i}}.
We consider the following two cases:
Case 1. |I| = 1. Let I = {x0}. Denote by P the set {im(a)|a ∈ T}.
To prove the theorem, we need several lemmas.
Lemma 10. For all A, B ∈ P we have either A ⊆ B or B ⊆ A.
Proof. Assume the converse. Then there exist A, B ∈ P such that B\A 6=
∅ and A\B 6= ∅. Let y ∈ B\A, z ∈ A\B. Choose an element a ∈ T such
that im(a) = A and an element b ∈ T such that im(b) = B. Denote by c
a unique element of the set T ∩ R({y, z}). Then im(ac) = {c(z)}. Since
ac ∈ D1, we have im(ac) = {x0}. Thus c(z) = x0. One can similarly
prove that c(y) = x0. This contradicts the injectivity of c and completes
the proof.
Lemma 11. Let k ∈ N and a, b ∈ Dk ∩ T . Then im(a) = im(b).
V. Pyekhtyeryev 99
Proof. Follows from the previous lemma.
For any natural number k by Mk denote the set im(Dk ∩ T ). It
follows from Lemma 10 that Mk ⊂ Mk+1 for all k ∈ N. Therefore,
|Mk+1\Mk| = 1. Denote by xk a unique element of the set Mk+1\Mk.
Then Mk = {x0, x1, . . . , xk−1}.
We construct the relation < as follows:
Define x < x for all x ∈ X. For any x, y ∈ X such that x 6= y, let
ax,y be a unique element of the set T ∩ R({x, y}). Note that ax,y = ay,x
and im(ax,y) = {x0, x1}. Define
x < y if ax,y(x) = x0, ax,y(y) = x1
y < x if ax,y(y) = x0, ax,y(x) = x1.
Lemma 12. Let a be an arbitrary element of T and x, y ∈ dom(a). If
x < y, then a(x) < a(y).
Proof. Let x′ = a(x), y′ = a(y) and b = ax′,y′ . Since dom(ab) = {x, y} =
dom(ax,y), we have ab = ax,y. This implies (ab)(x) = ax,y(x). Also, since
x < y, we obtain b(x′) = b(a(x)) = (ab)(x) = ax,y(x) = x0. Finally, from
the definition of < it follows that x′ < y′, that is, a(x) < a(y).
Lemma 13. The relation < is a linear order.
Proof. From the definition of < it follows that for all different x, y ∈ X we
have either x < y or y < x. Reflexivity and anti-symmetry of the relation
are obvious. Therefore, to complete the proof it is now enough to prove
the transitivity. Considering the product baxk,xl
, where b ∈ T ∩ Dk+1,
we obtain xk < xl for all natural numbers k < l. Suppose x, y, z are
three different elements of the set X such that x < y and y < z. Let
T ∩ R({x, y, z}) = {c}. Then from Lemma 12 it follows that c(x) < c(y)
and c(y) < c(z). Since {c(x), c(y), c(z)} = im(c) = M3 = {x0, x1, x2},
we have c(x) = x0, c(y) = x1, c(z) = x2. Finally, using Lemma 12 and
x0 < x2, we get x < z.
Lemma 14. The element x0 is the smallest element of the set X, that
is, the inequality x0 < x for all x ∈ X holds true.
Proof. It is enough to consider the product id{x0}ax0,x.
Lemma 15. The relation < is a well order, that is, every non-empty
subset Y ⊆ X has the smallest element.
100 H−,R− and L−cross-sections of ISX
Proof. Let a be a unique element of the set T ∩ R(Y ). From Lemma 10
it follows that x0 ∈ im(a). Let y = a−1(x0). Then from Lemmas 12 and
14 it follows that y is the smallest element of the set Y .
By α denote the order-type of the set (X, <).
Lemma 16. For all A, B ∈ P such that ξ(A) = ξ(B), we have A = B.
Proof. Let A, B ∈ P be the sets from the formulation. Then by Lemma
10 we have either A ⊆ B or B ⊆ A. Without loss of generality we can
assume that A ⊆ B. Consider an element a of T such that im(a) = A.
Assume A 6= B, then there exists z ∈ B\A. By g denote an isomorphism
of the well-ordered sets B and A. Since g is bijective, we see that all
elements of the sequence {g(n)(z), n ≥ 0} are different and the set C :=
{g(n)(z), n ≥ 0} is countable. Consider the pair (z, g(z)). If z > g(z),
then g(n)(z) > g(n+1)(z) for all n ≥ 0. This implies that the set C does
not possess the smallest element. This contradicts Lemma 15. Thus
z < g(z) and z is the smallest element of C. Let b be a unique element
of the set T ∩ R(C). Then b(z) = x0. Since ab ∈ T , we see that there
exists a unique number k ≥ 1 such that b(g(k)(z)) = x0. This contradicts
the injectivity of the map b and completes the proof of the lemma.
Lemma 17. For any ordinal number β ≤ α the transformation idX(β)
belongs to the cross-section T .
Proof. The proof is by transfinitary induction on β. Since 0 ∈ T , the
basis of induction holds true. Assume the statement holds for all ordinal
numbers less than β and denote by a a unique element of the set T ∩
R(X(β)). Let us consider two cases.
1) β is nonlimiting ordinal. Then the set X(β) has the greatest
element xβ′ and β = β′ + 1. By the inductive hypothesis, idX(β′) ∈ T .
Now let b = idX(β′)a, then dom(b) = X(β′) and b = idX(β′). This implies
that a|X(β′) = idX(β′). To complete the proof it is now enough to show
that a(xβ′) = xβ′ . Assume the converse. Then a(xβ′) = xδ > xβ′ .
Further, suppose c is a unique element of the set T ∩ R(xδ, xβ′). Then
since rk(ac) = 1, we obtain c(xδ) = x0 and c(xβ′) = x1. This contradicts
Lemma 12 and so a(xβ′) = xβ′ .
2) β is limiting ordinal. In this case, for all ordinal numbers γ such
that γ < β, we have γ + 1 < β. Then by the inductive hypothesis,
idX(γ+1) ∈ T . In addition, let b = idX(γ+1)a. Then dom(b) = X(γ + 1)
and b = idX(γ+1). This implies a|X(γ+1) = idX(γ+1). In particular,
a(xγ) = xγ . Therefore a = idX(β). This completes the proof of the
lemma.
V. Pyekhtyeryev 101
By Lemma 12, Lemma 16 and Lemma 17, T ⊆ R(X, <). But T and
R(X, <) contain a unique element from each R−class of ISX and so we
must have T = R(X, <).
Case 2. |I| > 1.
Lemma 18. If a ∈ T , then a(Xi) ⊆ Xi for all i ∈ I.
Proof. Assume the converse. Then there exist elements i ∈ I and x ∈ Xi
such that a(x) /∈ Xi. Let b be a unique element of the set T ∩R({a(x)});
then we obviously have b(a(x)) = j 6= i. Since dom(ab) = {x} and
(ab)(x) = j, we obtain x ∈ Xj and so x /∈ Xi. This contradiction
completes the proof of the lemma.
For any i ∈ I consider the set Ti = {a ∈ T | dom(a) ⊆ Xi} and denote
Ri := {a|Xi
: a ∈ Ti}. Clearly, the set Ri is an R−cross-section in ISXi
and also it satisfies the condition of case 1. Hence Ri = R(Xi, <i) for
some well order <i on the elements of Xi.
Lemma 19. Let a be an arbitrary element of T and x, y ∈ dom(a)∩Xi.
If x <i y, then a(x) <i a(y).
Proof. The proof is analogous to one of Lemma 12.
For any i ∈ I by Pi denote the set {a(dom(a) ∩ Xi)| a ∈ T}.
Lemma 20. For any i ∈ I and for all A, B ∈ Pi we have either A ⊆ B
or B ⊆ A.
Proof. The proof is analogous to one of Lemma 10.
Lemma 21. For any i ∈ I and for all A, B ∈ P such that ξ(A) = ξ(B),
we have A = B.
Proof. The proof is analogous to one of Lemma 16.
Lemma 22. For all a ∈ T , we have a(dom(a) ∩ Xi) = Xi(ξ(dom(a) ∩
Xi)).
Proof. Consider an element b of T such that dom(b) = dom(a) ∩ Xi.
From Lemma 19 it follows that ξ(a(dom(a) ∩ Xi)) = ξ(im(b)). Also,
since b ∈ Ti, we obtain a(dom(a) ∩ Xi) = im(b) = Xi(ξ(dom(a) ∩ Xi))
by Lemma 21.
Now by Lemma 22, T ⊆ R({
⋃
i∈I(Xi, <i)}). But both T and
R({
⋃
i∈I(Xi, <i)}) contain a unique element from each R−class of ISX
and so we must have T = R({
⋃
i∈I(Xi, <i)}).
102 H−,R− and L−cross-sections of ISX
The anti-involution a 7→ a−1 interchanges R− and L−classes in ev-
ery inverse semigroup. Clearly, this anti-involution also maps L−cross-
sections to R−cross-section and vice versa. Hence, dualizing Theorem 3,
one immediately gets the description of the L−cross-sections in ISX . To
formulate this theorem it is convenient to introduce the following nota-
tion.
Let αi be the order-type of the set Xi. Now construct the set
L({
⋃
i∈I(Xi, <i)}) in the following way: an element a ∈ L(A) belongs
to L({
⋃
i∈I(Xi, <i)}) if and only if the map a|Xi(ηi) is an isomorphism of
Xi(ηi) and A ∩ Xi, where ηi = ξ(A ∩ Xi) ≤ αi for all i ∈ I.
Theorem 4. a) For an arbitrary decomposition X =
⋃
i∈I Xi and arbi-
trary well orders on the elements of every block of this decomposition the
set L({
⋃
i∈I(Xi, <i)}) is an L−cross-section of ISX .
b) If {
⋃
i∈I(Xi, <i)} 6= {
⋃
j∈J(Xj , <j)} then one has that
L({
⋃
i∈I(Xi, <i)}) 6= L({
⋃
j∈J(Xj , <j)}).
c) Moreover, every L−cross-section of ISX has the form
L({
⋃
i∈I(Xi, <i)}) for some decomposition X =
⋃
i∈I Xi and some well
orders <i on the elements of every block.
4. Classification of R− (L−) cross-sections up
to isomorphism
By ωα+1 denote the smallest ordinal number of cardinality ℵα+1. Let
R = R({
⋃
i∈I(Xi, <i)}) be an R−cross-section of ISX , where |X| = ℵα.
The map fR : W (ωα+1) → [0,ℵα], η 7→ |{i ∈ I|ξ(Xi) = η}|, will be called
the type of R. Analogously one defines the type of an L−cross-section.
Theorem 5. Two R− (L−) cross-sections in ISX are isomorphic if and
only if they have the same type.
Proof. Clearly, it is enough to prove the statement for, say R−cross-
sections. Let R1 = R({
⋃
i∈I(Xi, <i)}) and R2 = R({
⋃
j∈J(Xj , <j)}) be
two arbitrary R−cross-sections of types fR1
and fR2
respectively.
Necessity. Assume first that R1 ≃ R2 and f is an arbitrary isomor-
phism of these cross-sections. Since every idempotent of the cross-sections
has the form idA for some subset A ⊆ X, we have f(idA) = idB. Con-
sider the equation idA · x = x in the semigroup R1. Its solutions form
the set {x ∈ R1| dom(x) ∈ A}. Since R1 is a cross-section, this equation
has exactly 2|A| solutions. Also, since corresponding equations have the
same quantity of solutions under the isomorphism, we obtain 2|A| = 2|B|.
Thus if |A| = n < ∞, then |B| = n. This implies that there exists
a bijection between idempotents of the finite rank n. In particular, for
V. Pyekhtyeryev 103
n = 1, there exists a bijection f̃ between the set I and the set J given
by the rule f̃(i) = j iff f(id{i}) = id{j}. For any i ∈ I and x ∈ Xi
by ax denote a unique element of R1 ∩ R({x}). Further, for any i ∈ I
define the map fi : Xi → Y
f̃(i)
by the rule x 7→ dom(f(ax)). Since f(ax)
satisfies the equation y · id
{f̃(i)}
= y, we see that this map is well defined.
Also, since f is isomorphism, we see that fi is bijection. To complete
the proof it is now enough to show that fi is an isomorphism of the well-
ordered sets Xi and Y
f̃(i)
for all i ∈ I. Since for all a ∈ R1 such that
rk(a) = n < ∞, we have a · idim(a) = a, where rk(idim(a)) = n, we obtain
that in the semigroup R2 the equality f(a) · idB = f(a) holds true, where
rk(idB) = n. This implies rk(f(a)) ≤ n = rk(a). Similarly, we can show
that rk(a) ≤ rk(f(a)) and so for all a ∈ R1 such that rk(a) = n < ∞,
we have rk(a) = rk(f(a)).
Let an element i of the set I be fixed. If |Xi| = 1, then it is obvious,
that fi is an isomorphism of the well-ordered sets. If |Xi| > 1, then
by i′ denote the successor of i in the well-ordered set (Xi, <i). Let j :=
fi(i) = f̃(i), j′ := fi(i
′), ai = id{i} and bj = id{j}. Suppose ai′ is a unique
element of R1∩R({i′}) and bj′ is a unique element of R2∩R({j′}). Then
f(ai) = bj and f(ai′) = bj′ . Since id{i,i′} ∈ R1, we see that in R1 the
equalities id{i,i′} · ai = ai, id{i,i′} · ai′ = ai′ hold true. Therefore in R2
the equalities f(id{i,i′}) · bj = bj , f(id{i,i′}) · bj′ = bj′ hold true. This
implies j, j′ ∈ dom(f(id{i,i′})) and f(id{i,i′})|{j,j′} = id{j,j′}. But since
rk(f(id{i,i′})) = 2, we obtain f(id{i,i′}) = id{j,j′}. Hence id{j,j′} ∈ R2.
This means that j′ is the successor of j in the well-ordered set (Yj , <j).
Let x1 and x2 be two different elements of Xi such that x1 <i x2.
Then the element α =
(
x1 x2
i i′
)
belongs to R1. Let y1 := fi(x1), y2 :=
fi(x2). Defining elements ax1
, ax2
, by1
, by2
similarly, we can show that(
y1 y2
j j′
)
= f(α) ∈ R2. This means y1 <j y2. Therefore fi is an iso-
morphism of the well-ordered sets (Xi, <i) and (Yj , <j) and the statement
is proved.
Sufficiency. Obvious.
Acknowledgements
I would like to thank Prof. O. G. Ganyushkin for fruitful discussions.
References
[CR] Cowan D., Reilly N., Partial cross-sections of symmetric inverse semigroups
International J. Algebra and Comput. 5 (1995), no. 3, 259-287.
104 H−,R− and L−cross-sections of ISX
[GM1] Ganyushkin O., Mazorchuk V., L− and R−cross-sections in ISn Com. in
Algebra 31 (2003), no. 9, 4507-4523.
[GM2] Ganyushkin O., Mazorchuk V., The full finite Inverse symmetric semigroup
ISn, Preprint 2001:31, Chalmers University of Technology and Goteborg Univer-
sity, Goteborg, 2001.
[KMM] Kudryavtseva G., Maltsev V., Mazorchuk V., L− and R−cross-sections in
the Brauer semigroup, U.U.D.M. Report 2004:43, Uppsala University, 2004.
[P1] Pyekhtyeryev V., H− and R−cross-sections of the full finite semigroup Tn. J.
Algebra and Discrete Mathematics no. 3 (2003), 82-88.
[P2] Pyekhtyeryev V., R−cross-sections of TX Mathematical studio, 21 (2004), 133-
139. [ukrainian]
Contact information
Pyekhtyeryev V. Department of Mechanics and Mathematics,
Kiyv Taras Shevchenko University, 64,
Volodymyrska st., 01033, Kiyv, UKRAINE
E-Mail: vasiliy@univ.kiev.ua
Received by the editors: 29.12.2004
and in final form 21.03.2005.
|