# A Note on Isomorphism Theorems for Semigroups of Order-Preserving Transformations with Restricted Range

Authors: Phichet Jitjankarn; Thitarie Rungratgasame
Journal: International Journal of Mathematics and Mathematical Sciences
 (2015)

---

## Abstract

Finding necessary and sufficient conditions for isomorphism between two semigroups of order-preserving transformations over an infinite domain with restricted range was an open problem. In this paper, we show a proof strategy to answer that question.


---

## Body

## 1. Introduction

For a nonempty setX, let T(X) be the full transformation semigroup under composition of all maps from X to X. When X is a partially ordered set (poset), a mapping α in T(X) is calledorder-preserving if x≤y implies xα≤yα for all x,y∈X, and α isregressive if xα≤x for all x∈X. We denote by TOP(X) and TRE(X) the subsemigroups of T(X) of all order-preserving maps and all regressive maps on X, respectively. The semigroups of order-preserving maps were first introduced by Howie in [1].Forα∈T(X), let ranα denote the range of α. In 1975, Symons [2] introduced and studied the subsemigroup T(X,X′) where ∅≠X′⊆X of T(X) consisting of α∈T(X) with ranα⊆X′. Subsemigroups of transformations (with restricted range) of T(X) of this type have been studied extensively, including our work which we will mention later on. Regarding the semigroups of regressive type, in 1996, Umar proved that for any chains X and Y, TRE(X)≅TRE(Y) if and only if X and Y are order-isomorphic (see in [3]). Later in [4], Saitô et al. generalized this result to partially ordered sets. They introduced the adjusted partially ordered set A(X) of a poset X and proved that the order-isomorphism between A(X) and A(Y) is a necessary and sufficient condition for the two semigroups to be isomorphic.In this paper, we are also interested in studying the isomorphisms of subsemigroups of transformations with restricted range. Now, let us introduce the subsemigroups which will be of particular interest to us in this paper.For a partially ordered setX and a subset X′ of X, we let
(1)TOPX,X′:=TOP(X)∩TX,X′,TREX,X′:=TREX∩TX,X′.
Then both of these are subsemigroups of TX,X′.In 2012, Udomkavanich and Jitjankarn proved in [5] that TREX,X′≅TREY,Y′ if and only if two adjusted chains A(X,X′) and A(Y,Y′) are order-structural isomorphic. This result leads us to study the isomorphism theorems for the semigroups of order-preserving type. It is known (e.g., [6], pages 222-223) that, for posets X and Y, TOP(X)≅TOP(Y) if and only if X and Y are either order-isomorphic or order-anti-isomorphic. These necessary and sufficient conditions also hold for the isomorphisms on the semigroups of partial order-preserving transformations (see in [7]). In 2014, Fernandes et al. [8] show that these conditions apply for TOP(X,X′) and TOP(Y,Y′) to be isomorphic when X and Y are finite as well. In this paper, we study the case when X and Y are infinite chains. Since TOP(X,X′) is trivial when |X′|=1, we omit this case.Throughout the paper, we assume thatX and Y are chains, |X′|>1, and |Y′|>1. The following statement is known.If there is an order-(anti)-isomorphismθ:X→Y such that
(2)X′θ=Y′forsomeX′⊆X,Y′⊆Y,
then TOP(X,X′)≅TOP(Y,Y′).It is natural to ask whether the converse of the above result holds. Nevertheless, our work shows that it may not be the case if|X′|=2. To be precise, we derive that the converse of the statement (2) holds when |X′|≥3.To prove the statements, we apply in a similar fashion to [5] the idea of using adjusted chains. To do so, we will first introduce some notation and definitions that will be useful in Section 2. In Section 3, some homomorphism properties which are preserved under isomorphism will be given. Lastly, the isomorphism theorems for the semigroups of the type TOPX,X′ when X is an infinite chain are determined in Section 4.


## 2. Basic Notations and Results

LetC′ be a subchain of a chain C. Let {C∖C′} denote the set of all equivalence classes of C∖C′ such that each class contains all elements in C∖C′ with no elements in C′ lying between them. Then we consider C∖C′∪C′ as a chain under the partial order induced by the chain C in the natural way. This chain is an adjusted chain, denoted by A{C,C′}.For eacha,b∈C with a<b, the intervals (a,b), [a,b), (a,b], [a,b] in C are defined naturally and we define the following intervals:
(3)←a:=z∈C:z≤a,a→:=z∈C:z≥a,←a:=z∈C:z<a,a→:=z∈C:z>a.For a nonempty subsetV of a chain C, V is said to beconvex if for x,y,z∈C such that x≤z≤y, x,y∈V implies z∈V; V is called anupper(lower)-convex subset of C if x<y (x>y) for all x∈C∖V and y∈V.For a convex subsetV of C, we define
(4)←V:=z∈C∖V:zisalowerboundofVinC,V→:=z∈C∖V:zisanupperboundofVinC.For convenience, ifa∈C, let Ca be the element of T(C) whose range is {a}.Given[k]∈{C∖C′}, k∈C∖C′. We will define some order-preserving maps of T(C,C′) as follows.(i)
For a convex subsetA of [k] and a,b,c∈C′ such that a≤b<[k]<c (or a<[k]<b≤c), we write
(5)ωa:Ab:c:=(←A)A(A→)abc,whereran(ωa:Ab:c)={a,b,c} and b(ωa:Ab:c)-1=A if a≠b.(ii)
When[k]=min⁡A{X∖X′}, for a lower-convex subset L of [k] and a,b∈C′ such that [k]<a<b, we write
(6)ωLa:b:=L(L→)ab,whereran(ωLa:b)={a,b} and a(ωLa:b)-1=L.(iii)
When[k]=max⁡A{X∖X′}, for an upper-convex subset U of [k] and a,b∈C′ such that a<b<[k], we write
(7)ωa:Ub:=(←U)Uab,whereran(ωa:Ub)={a,b} and b(ωa:Ub)-1=U.Forα∈T(C), we denote Fix⁡(α)={x∈C:xα=x}.Forα∈T(C,C′), we definethe partial graph of transformationα, denoted by Γα:=(C′,ranα,Eα), in the following way: C′ is the set of upper vertices, ranα is the set of lower vertices such that all vertices are placed in order, and Eα is the set of (directed) edges which each element is in the form xαy, where xα=y for x,y∈C′. Notice that the number of components in each partial graph is equal to the number of elements in its range. Furthermore, the components, considered from left to right, are placed in the same order as their related elements in the range.Example 1.
For the transformationα∈T({1,2,…,9},{1,3,5,7,9}) defined by
(8)α=123456789151955535,
the set of upper vertices is {1,3,5,7,9}, the set of lower vertices is {1,3,5,9}, and Eα={1α1,3α1,5α5,7α5,9α5}. Then the graph Γα has the form shown in Figure 1.
The partial graphΓα has four components placed in order from left to right.Figure 1Theorem 2.
IfTOP(X,X′)≅TOP(Y,Y′), then X′ and Y′ are either order-isomorphic or order-anti-isomorphic.Proof.
Letφ:TOP(X,X′)→TOP(Y,Y′) be an isomorphism. For each a∈X′, there is an element a¯∈Y′ such that (Xa)φ=Ya¯ by idempotent and right zero properties of Xa and Ya¯. The map a↦a¯ becomes a bijective map from X′ onto Y′. It remains to show that this map is either order-preserving or order-anti-preserving. Let a,b,s,t∈X′ be such that a<b and s<t. Since Y′ is a chain and the map is one-to-one, it must be that a¯<b¯ or a¯>b¯ and s¯<t¯ or s¯>t¯. Now, we have (←a](a→)st∈TOP(X,X′) such that
(9)Xa←aa→st=Xs,Xb←aa→st=Xt.
Then
(10)Ya¯←aa→stφ=Ys¯,Yb¯←aa→stφ=Yt¯.
Consequently,
(11)a¯←aa→stφ=s¯,b¯←aa→stφ=t¯.
Since(←a](a→)stφ∈TOP(Y,Y′), it follows that a¯<b¯ implies s¯<t¯ and a¯>b¯ implies s¯>t¯. This proves that X′ and Y′ are either order-isomorphic or order-anti-isomorphic.From now on, letφ denote an isomorphism from TOP(X,X′) and TOP(Y,Y′). The order-(anti)-isomorphism from X′ onto Y′, defined in the proof of Theorem 2, is denoted by θφ. It is easy to see that the order-(anti)-isomorphism θφ-1 from Y′ onto X′, induced by the isomorphism φ-1, is the inverse function of θφ. That is,
(12)θφ-1=θφ-1.
Notice that, by considering φ-1 and θφ-1 instead of φ and θφ, respectively, all results that hold for φ also hold for φ-1.


## 3. Some Homomorphism Properties

In this section, we study some properties of transformations which will be preserved under a homomorphism. First, we will study the structure ofα and αφ through θφ when α∈TOP(X,X′). Then we derive that two graphs of Γα and Γ(α)φ are isomorphic. Moreover, the order of components (in the sense of partial graph) is also preserved.Without loss of generality, we assume thatθφ is order-preserving from now on. The other case that θφ is order-anti-preserving can be done by the same process.Lemma 3.
For eachα∈TOP(X,X′), the following statements hold. (i)
(Fix⁡(α))θφ=Fix⁡(αφ).(ii)
Fora∈ranα such that aα-1∩X′≠∅,
(13)a¯∈ranαφ,a¯αφ-1∩Y′=aα-1∩X′θφ.In particular, if α is an idempotent, then (ranα)θφ=ran(αφ).Proof.
(i) Leta∈Fix⁡(α). Then aα=a. Since Ya¯(αφ)=(Xaφ)(αφ)=(Xaα)φ=Xaφ=Ya¯, it follows that a¯(αφ)=a¯=aθφ∈Fix⁡(αφ). Similarly, if s¯∈Fix⁡(αφ), then Xsα=(Ys¯φ-1)α=(Ys¯(αφ))φ-1=(Ys¯)φ-1=Xs; that is, sα=s. Then s¯=sθφ∈(Fix⁡(α))θφ.
(ii) Fora∈ranα such that aα-1∩X′≠∅, let x∈aα-1∩X′. Then a∈Fix⁡Xxα, by (i), a¯∈Fix⁡(Xxφ)(αφ). That is, a¯∈ran(αφ). Since x¯(αφ)=a¯(Xxφ)(αφ)=a¯, it follows that x¯∈a¯(αφ)-1∩Y′. Then (aα-1∩X′)θφ⊆a¯(αφ)-1∩Y′. Similarly, by considering φ-1 instead of φ, a¯(αφ)-1∩Y′⊆(aα-1∩X′)θφ. Thus the equality is obtained.Lemma 4.
For eachα∈TOP(X,X′), if b∈ranα and bα-1∩X′=∅, then b¯∈ran(αφ).Proof.
Letb∈ranα and bα-1∩X′=∅. Assume that b is neither maximum nor minimum in X′. Choose a,c∈X′ such that a<b<c and let ϵb=(←b)b(b→)abc. Then ϵb is an idempotent with b(ϵb)-1∩X′={b}. By Lemma 3, b¯(ϵbφ)-1∩Y′={b¯}. Suppose in the contrary that b¯∉ran(αφ). Then we have b¯∉ran((αφ)(ϵbφ)). Since |ran(αφ)(ϵbφ)| is finite, this guarantees the existence of an idempotent μ in TOP(Y,Y′) with ranμ=ran(αφ)(ϵbφ). Then μφ-1 is an idempotent in TOP(X,X′), by Lemma 3, b∉ran(μφ-1). However,
(14)αϵbμφ-1=αφϵbφμφ-1=αφϵbφφ-1=αϵb,
which is a contradiction. If b is either maximum or minimum, it can be proved in the same way by defining ϵb as before and choosing a=b if b is minimum, and c=b if b is maximum.By Lemmas3 and 4, the following proposition is directly obtained.Proposition 5.
For eachα∈TOP(X,X′), we have the following.(i)
(ranα)θφ=ran(αφ).(ii)
For anya∈ranα, a¯(αφ)-1∩Y′=(aα-1∩X′)θφ.This proposition leads us to define an interesting equivalence relation on the semigroup of full transformations with restricted range.Given a transformationα:X→X′, the α-structure is the partial graph Γα which its components will be placed in the same order as their related elements in the range. Here we define an equivalence relation K on T(X,X′) by
(15)αKβiffα-structureandβ-structurearethesame.
Indeed, it is equivalent to α|X′=β|X′ and ranα=ranβ. The K-class containing α is denoted by Kα. It is very clear that when X′=X, T(X,X′) is K-trivial. By Proposition 5, we have that Kα and (Kα)φ=Kαφ have the same structure for all α∈TOP(X,X′).Next, we will construct an extension ofθφ to be an order-isomorphism on the adjusted chains.Lemma 6.
Suppose that two classes[k1] and [k2] are the minimum and the maximum of A{X,X′}, respectively. Let a,b∈X′ be such that a<b, and A⊆[k1] and B⊆[k2] as a lower-convex subset and an upper-convex subset of [k1] and [k2], respectively. Then
(16)ωAa:bφ=ωCa¯:b¯,ωa:Bbφ=ωa¯:Db¯
for some lower-convex C and upper-convex D of the minimum and the maximum of {Y∖Y′}, respectively.Proposition 7.
For each[k]∈{X∖X′}, there is a corresponding [tk]∈{Y∖Y′} such that the extended map of θφ from X′∪{[k]} onto Y′∪{[tk]} is an order-isomorphism. Moreover, |[k]|=|[tk]|.Proof.
Let[k]∈{X∖X′} be such that a<[k]<b for some a,b∈X′. We choose ωa:Aa:b as an idempotent in TOP(X,X′) whose range is {a,b}. Since two partial graphs of transformations Γωa:Aa:b and Γ(ωa:Aa:b)φ have the same structure, by Proposition 5, it follows that (Kωa:Aa:b)φ=K(ωa:Aa:b)φ. Due to the structure of Γωa:Aa:b, the cardinality of Kωa:Aa:b is depending only on [k]. Indeed, |Kωa:Aa:b|=|[k]|. This implies the existence of [tk]∈{Y∖Y′} with a¯<[tk]<b¯ and |K(ωa:Aa:b)φ|=|[tk]|.
Suppose[k] is maximum (or minimum) in A{X,X′}. For any a,b∈X′ such that a<b, we consider ωa:[k]b (or ω[k]a:b). By Lemma 6 and using the same argument, our proof is finished.From Proposition7, the union of all these extensions form an order-isomorphism, denoted by θφ^ (with respect to θφ), from A{X,X′} onto A{Y,Y′} such that
(17)x⟼x¯,k⟼tk
for x∈X′ and [k]∈{X∖X′}. We notice that θφ^ is an order-structural isomorphism (as defined in [5]). This conclusion results in the isomorphism theorems between the two semigroups for an infinite discrete chain.Theorem 8.
LetX and Y be infinite discrete chains. Then TOP(X,X′)≅TOP(Y,Y′) if and only if there is an order-(anti)-isomorphism θ:X→Y such that (X′)θ=Y′.Nevertheless, the property that|[k]|=|[tk]|=|([k])θφ^| is not sufficient to determine the isomorphism for an uncountable chain. As a result, we study more of homomorphism properties associated with a class of {X∖X′}.Lemma 9.
Let[k]∈{X∖X′} be such that a<b<[k]<c (or a<[k]<b<c) for some a,b,c∈X′. Then for each convex subset A of [k],
(18)ωa:Ab:cφ=ωa¯:Bb¯:c¯
for some convex subset B of [tk]∈{Y∖Y′} with a¯<b¯<[tk]<c¯ (or a¯<[tk]<b¯<c¯).Proof.
By Proposition5, it follows that ran((ωa:Ab:c)φ)={a¯,b¯,c¯}. Since (aωa:Ab:c-1∪cωa:Ab:c-1)∩X′=X′, by Lemma 3, we have that (a¯((ωa:Ab:c)φ)-1∪c¯((ωa:Ab:c)φ)-1)∩Y′=Y′. As ((ωa:Ab:c)φ) is order-preserving such that b¯ is in its range, there exists the unique class in {Y∖Y′}, namely [tk], containing a convex subset b¯((ωa:Ab:c)φ)-1.Proposition 10.
Let[k]∈{X∖X′} be such that a<b<[k]<c (or a<[k]<b<c) for some a,b,c∈X′. Then for each x∈[k],
(19)ωa:{x}b:cφ=ωa¯:{y}b¯:c¯
for some y∈[tk].Proof.
Letf and g stand for two idempotents in TOP(X,X′) such that ranf=rang={a,c} with {b,c}⊆cf-1 and {a,b}⊆ag-1. Let B be a convex subset of [k] such that |B|>1. By Lemma 9, we obtain that (ωa:Bb:c)φ=ωa¯:Mb¯:c¯ for some convex subset M of [tk]. Suppose in the contrary that M={y}. We choose L and U as two convex subsets of B which form a partition of B, and L is a lower bound of U. Since ωa:Ub:cg=ωa:Bb:cg, it follows that
(20)ωa:Ub:cφgφ=ωa:Bb:cφgφ=ωa¯:{y}b¯:c¯gφ.
Then b¯(ωa:Ub:cφ)-1 is an upper-convex subset of (←y]. Since ωa:Lb:cf=ωa:Bb:cf, we have
(21)ωa:Lb:cφfφ=ωa:Bb:cφfφ=ωa¯:{y}b¯:c¯fφ.
Then b¯(ωa:Lb:cφ)-1 is a lower-convex subset of [y→). It can be seen that ωa:Lb:cg=ωa:Ub:cf. Then (ωa:Lb:cφ)(gφ)=(ωa:Ub:cφ)(fφ) which contradicts to
(22)a¯=b¯gφ=yωa:Lb:cφgφ=yωa:Ub:cφfφa¯=b¯fφ=c¯.Proposition 11.
Fora,b,c∈X′ with a<b<c, the following statements hold. (i)
If[k]=max⁡A{X∖X′}, then, for x∈[k],
(23)ωa:[x→)cφ=ωa¯:[y→)c¯forsomey∈tk.(ii)
If[k]=min⁡A{X∖X′}, then, for x∈[k],
(24)ω(←x]a:cφ=ω(←y]a¯:c¯forsomey∈tk.Proof.
(i) Suppose[k]=max⁡A{X∖X′}. Let x∈[k]. Suppose that (x→)≠∅. We let α=(←x)x(x→)abc and β=(←b)[b→)ac. Clearly, αβ=ωa:[x→)c. Then (αφ)(βφ)=(ωa:[x→)c)φ. By applying the same process as in the proof of Proposition 10, we obtain that |b¯(αφ)-1|=1. It is clear that c¯(ωa:[x→)cφ)-1=b¯(αφ)-1∪˙c¯(βφ)-1 where b¯(αφ)-1 is a lower-convex subset of c¯(ωa:[x→)cφ)-1. These imply that c¯(ωa:[x→)cφ)-1=[y→) for some y∈[tk].
(ii) can be proved similarly to (i).


## 4. Isomorphism Theorems

In the last section, we take care of the case|X′|=2. For convenience, we here denote TOP(X,X′) by O[M11M22M3] where M1,M2, and M3 are three classes in {X∖X′}. We observe that there are only 5 classes in O[M11M22M3]/K whose partial graph of transformations is one of the forms shown in Figure 2.Figure 2The following results are directly derived.Lemma 12.
ForKλi∈O[M11M22M3]/K, (i=1,…,5), we have that(i)
Kλ1 and Kλ2 are trivial,(ii)
|Kλ3|=|M2|+1,(iii)
|Kλ4|=|M3| and |Kλ5|=|M1|.Proof.
Since there are only two constant maps, (i) is proved. To show (ii), it is easy to see that each element inM2 determines the consequent map in Kλ3 and vice versa. Hence the bijection between the two sets is constructed. The same idea can also be applied to show |Kλ4|=|M3| and |Kλ5|=|M1|.Theorem 13.
O
[
M
1
1
M
2
2
M
3
]
≅
O
[
N
1
1
¯
N
2
2
¯
N
3
] if and only if |Mi|=|Ni| for all i=1,2,3.Proof.
Suppose that, fori=1,…,5, λi and γi are two representations of order-preserving maps having the same partial graph in O[M11M22M3] and O[N11¯N22¯N3], respectively. By Lemma 12, we let fi be a bijection from Kλi onto Kγi for i=1,…,5. To show that φ:=f1∪f2∪⋯∪f5:O[M11M22M3]→O[N11¯N22¯N3] is an isomorphism, we let α∈O[M11M22M3]. It is easy to see that the pairwise composition of five graph structures can be one of the following maps: for β∈O[M11M22M3], either αβ=λ1, αβ=λ2 or αβ=α:
(25)λ1λ2λ3λ4λ5λ1λ1λ2λ1λ1λ2λ2λ1λ2λ2λ1λ2λ3λ1λ2λ3λ1λ2λ4λ1λ2λ4λ1λ2λ5λ1λ2λ5λ1λ2
Suppose αβ=λ1. One of the following statements hold: (i)
β=λ1,(ii)
β∈Kλ4,(iii)
β∈Kλ3 and α=λ1. It is clear that (αφ)(βφ)=γ1=(λ1)φ.
For the rest, it can be proved directly.Example 14.
LetX=R, X′={1,2}, Y=[2,5), Y′={3,4}. Theorem 13 tells us that O[(-∞,1)1(1,2)2(2,∞)]≅O[[2,3)3(3,4)4(4,5)], yet it is clear that R and [2,5) are not order or order-anti-isomorphic.
Next, we will prove that when|X′|≥3, the converse of (2) holds.Theorem 15.
Suppose that|X′|≥3. Then TOP(X,X′)≅TOP(Y,Y′) if and only if there is an order-(anti)-isomorphism θ from X onto Y such that X′θ=Y′.Proof.
It remains to show that, for each[k]∈{X∖X′}, [k] and [tk] are order-isomorphic. Let [k] be a class in {X∖X′}. We will consider in two cases.
Case  1. Consider [k]=max⁡A{X∖X′} or min⁡A{X∖X′}.
Without loss of generality we can assume that[k]=max⁡A{X∖X′}. We choose a,b,c∈X′ with a<b<c. For any x,x′∈[k] with x<x′. Consider ωa:[x→)c and ωa:[x′→)c. By Proposition 11, we have (ωa:[x→)c)φ=ωa¯:[y→)c¯ and (ωa:[x′→)c)φ=ωa¯:[y′→)c¯. Let γ=(←x)[x,x′)[x′→)abc. Then
(26)γ←bb→ac=ωa:[x→)c,γ←bb→ac=ωa:[x′→)c.
It follows that
(27)γφ←bb→acφ=ωa:[x→)cφ=ωa¯:[y→)c¯,γφ←bb→acφ=ωa:[x′→)cφ=ωa¯:[y′→)c¯.
Since [y→)=c¯(ωa¯:[y→)c¯)-1=b¯(γφ)-1∪˙c¯(γφ)-1 and y′→=c¯ωa¯:y′→c¯-1=c¯γφ-1, these imply that y<y′.
Case  2. [k] is neither max⁡A{X∖X′} nor min⁡A{X∖X′}.
Then there area,b,c∈X′ such that a<b<[k]<c or a<[k]<b<c.
By using Proposition10 and following the same proof as in Case1, we derive the result.



---

*Source: 187026-2015-02-19.xml*