Natural Partial Orders on Transformation Semigroups with Fixed Sets

Abstract

Let X be a nonempty set. For a fixed subset Y of X , let F i x ( X , Y ) be the set of all self-maps on X which fix all elements in Y . Then F i x ( X , Y ) is a regular monoid under the composition of maps. In this paper, we characterize the natural partial order on F i x ( X , Y ) and this result extends the result due to Kowol and Mitsch. Further, we find elements which are compatible and describe minimal and maximal elements.

[ProQuest: [...] denotes non US-ASCII text; see PDF]

Academic Editor:Pentti Haukkanen

Department of Mathematics, Chiang Mai University, Chiang Mai 50200, Thailand

Received 20 April 2016; Revised 1 July 2016; Accepted 5 July 2016

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

For any semigroup S , the natural partial order on E ( S ) , the set of all idempotents on S , is defined by [figure omitted; refer to PDF]

In 1980, Hartwig [1] and Nambooripad [2] proved that if S is a regular semigroup, then the relation [figure omitted; refer to PDF] is a partial order on S which extends the usual ordering of the set E ( S ) .

Later in 1986, the natural partial order on a regular semigroup was further extended to any semigroup S by Mitsch [3] as follows: [figure omitted; refer to PDF]

Let X be a set and B ( X ) denote the semigroup of binary relations on the set X under the composition of relations. A partial transformation semigroup is the collection of functions from a subset of X into X with composition which is denoted by P ( X ) . Let T ( X ) be the set of all transformations from X into itself and it is called the full transformation semigroup on X . Then P ( X ) and T ( X ) are subsemigroups of B ( X ) . It is well known that P ( X ) and T ( X ) are regular semigroups.

In 1986, Kowol and Mitsch [4] characterized the natural partial order on T ( X ) in terms of images and kernels. They also proved that an element α ∈ T ( X ) is maximal with respect to the natural order if and only if α is surjective or injective; α is minimal if and only if α is a constant map. Moreover, they described lower and upper bounds for two transformations and gave necessary and sufficient conditions for their existence.

Later in 2006, Namnak and Preechasilp [5] studied two natural partial orders on B ( X ) and characterized when two elements of B ( X ) are related under these orders. They also described the minimality, maximality, left compatibility, and right compatibility of elements with respect to each order.

Let Y be a subset of X . Recently, Fernandes and Sanwong [6] defined [figure omitted; refer to PDF] where X α denotes the image of α . Moreover, they defined I ( X , Y ) to be the set of all injective transformations in P T ( X , Y ) . Hence P T ( X , Y ) and I ( X , Y ) are subsemigroups of P ( X ) .

In [7], Sangkhanan and Sanwong described natural partial order <= on P T ( X , Y ) and I ( X , Y ) in terms of domains, images, and kernels. They also compared <= with the subset order and characterized the meet and join of these two orders. Furthermore, they found elements of P T ( X , Y ) and I ( X , Y ) which are compatible and determined the minimal and maximal elements.

Let Y be a fixed subset of X and [figure omitted; refer to PDF] In 2013, Honyam and Sanwong [8] proved that F i x ( X , Y ) is a regular semigroup and they also determined its Green's relations and ideals. Moreover, they proved that F i x ( X , Y ) is never isomorphic to T ( Z ) for any set Z when ∅ ≠ Y [subset of not =] X , and every semigroup S is isomorphic to a subsemigroup of F i x ( ^{X [variant prime]} , ^{Y [variant prime]} ) for some appropriate sets ^{X [variant prime]} and ^{Y [variant prime]} with ^{Y [variant prime]} ⊆ ^{X [variant prime]} . Note that this also follows trivially from the fact that T ( X ) embeds in F i x ( X ∪ Z , Z ) for any set Z with X ∩ Z = ∅ . Recently, the authors in [9] proved that there are only three types of maximal subsemigroups of F i x ( X , Y ) and these maximal subsemigroups coincide with the maximal regular subsemigroups when X \ Y is a finite set with | X \ Y | ≥ 2 . They also gave necessary and sufficient conditions for F i x ( X , Y ) to be factorizable, unit-regular, and directly finite.

In this paper, we characterize the natural partial order on F i x ( X , Y ) and find elements which are compatible under this order in Section 3. In Section 4, we describe the minimal elements, the maximal elements, and the covering elements. Moreover, we find the number of upper covers of minimal elements and the number of lower covers of maximal elements.

2. Preliminaries and Notations

In [8], the authors proved that F i x ( X , Y ) is a regular subsemigroup of T ( X ) . Note that F i x ( X , Y ) contains _{1 X} , the identity map on X . If Y = ∅ , then F i x ( X , Y ) = T ( X ) ; and if | X | = 1 or X = Y , then F i x ( X , Y ) consists of one element, _{1 X} . So, throughout this paper we will consider the case Y [subset of not =] X and | X | > 1 .

For any α ∈ T ( X ) , the symbol _{π α} denotes the partition of X induced by the map α , namely, [figure omitted; refer to PDF] For α , β ∈ T ( X ) , A ⊆ _{π α} , and B ⊆ _{π β} , we say that A refines B if for each A ∈ A there exists B ∈ B such that A ⊆ B .

Throughout this paper, unless otherwise stated, let Y = { _{y i} : i ∈ I } .

For each α ∈ F i x ( X , Y ) , we have _{y i} α = _{y i} for all i ∈ I . So Y = Y α ⊆ X α . If α ∈ F i x ( X , Y ) , then we write [figure omitted; refer to PDF] and take as understood that the subscripts i and j belong to the index sets I and J , respectively, such that X α = { _{y i} : i ∈ I } ∪ { _{b j} : j ∈ J } , _{y i} ^{α - 1} = _{A i} , and _{b j} ^{α - 1} = _{B j} . Thus _{A i} ∩ Y = { _{y i} } for all i ∈ I , _{B j} ⊆ X \ Y for all j ∈ J and { _{b j} : j ∈ J } ⊆ X \ Y . Here J can be an empty set.

An idempotent e in a semigroup S is said to be minimal if e has the property f ∈ E ( S ) and f <= e implies f = e .

In [8] the authors showed that [figure omitted; refer to PDF] is the set of all minimal idempotents in F i x ( X , Y ) and it is an ideal of F i x ( X , Y ) . We note that _{E m} is simply the set { α ∈ F i x ( X , Y ) : X α = Y } and α is an idempotent in F i x ( X , Y ) if and only if x α = x for all x ∈ X α \ Y .

3. Natural Partial Order on Fix [...] ( X , Y )

Kowol and Mitsch [4] gave a characterization of the natural partial order on T ( X ) . Later in 1994, Higgins [10] showed that if T is a regular subsemigroup of a semigroup S , then the natural partial order on T is the restriction to T of the natural partial order on S . Here we describe the natural partial order on F i x ( X , Y ) which is a regular subsemigroup of T ( X ) without making use of Higgins' result and when we take Y = ∅ , we recapture the result above by Kowol and Mitsch.

We note that if α , β ∈ F i x ( X , Y ) and α = β γ for some γ ∈ F i x ( X , Y ) , then _{π β} refines _{π α} .

Since F i x ( X , Y ) is regular, we use ( [low *] ) to study the natural partial order on this semigroup.

Theorem 1.

Let α , β ∈ F i x ( X , Y ) . Then α <= β if and only if the following statements hold:

(1) X α ⊆ X β ;

(2) _{π β} refines _{π α} ;

(3) if x β ∈ X α , then x β = x α .

Proof.

Suppose that α <= β . Then, by ( [low *] ) , we have [figure omitted; refer to PDF] for some λ , γ ∈ E ( F i x ( X , Y ) ) . Thus X α = ( X λ ) β ⊆ X β . Since α = β γ , we get that _{π β} refines _{π α} . Now, let x β ∈ X α . Then x β = ^{x [variant prime]} α for some ^{x [variant prime]} ∈ X and thus x β = ^{x [variant prime]} α = ^{x [variant prime]} β γ = ( ^{x [variant prime]} β ) γ . Hence x β ∈ X γ and then x α = x β γ = x β since γ is an idempotent.

Conversely, assume that conditions (1)-(3) hold. By condition ( 1 ) , we can write [figure omitted; refer to PDF] where _{y i} ∈ _{A i} ∩ ^{A i [variant prime]} , _{b j} , _{b k} ∈ X \ Y , and _{B j} , _{C j} , _{C k} ⊆ X \ Y . Since _{y i} ∈ _{A i} ∩ ^{A i [variant prime]} and _{π β} refines _{π α} , we obtain ^{A i [variant prime]} ⊆ _{A i} for all i ∈ I . If J = ∅ , then define λ = α and thus α = λ β . If J ≠ ∅ , then, for each j ∈ J , let _{c j} ∈ _{C j} . So _{c j} β = _{b j} ∈ X α . By condition ( 3 ) , _{c j} α = _{c j} β = _{b j} ; that is, _{c j} ∈ _{B j} and hence _{C j} ⊆ _{B j} . Define [figure omitted; refer to PDF] We get λ ∈ E ( F i x ( X , Y ) ) and α = λ β .

If K = ∅ , then α = β _{1 X} . If K ≠ ∅ , then, for each k ∈ K , we choose _{c k} ∈ _{C k} .

Case 1 . Consider X β = X . Then X \ X α = { _{b k} : k ∈ K } . We define γ ∈ F i x ( X , Y ) by [figure omitted; refer to PDF] To prove that α = β γ , let x ∈ X . If x ∈ ^{A i [variant prime]} for some i or x ∈ _{C j} for some j , then it is clear that x α = x β γ . Now, if x ∈ _{C k} for some k , then x β = _{c k} β and thus x α = _{c k} α since _{π β} refines _{π α} . So ( x β ) γ = _{b k} γ = _{c k} α = x α . Hence α = β γ . It remains to show that γ is an idempotent. Let x γ ∈ X γ \ X α . Then x γ = _{c k} α for some k . Thus ( x γ ) γ = ( _{c k} α ) γ = _{c k} α = x γ since _{c k} α ∈ X α .

Case 2 . Consider X β [subset of not =] X . We choose _{c 0} ∈ X \ X β and define ^{γ [variant prime]} ∈ F i x ( X , Y ) by [figure omitted; refer to PDF] By the same prove as given in Case 1, we get α = β ^{γ [variant prime]} and ( x ^{γ [variant prime]} ) ^{γ [variant prime]} = x ^{γ [variant prime]} for all x ^{γ [variant prime]} ∈ X β . If x ^{γ [variant prime]} = _{c 0} , then ( x ^{γ [variant prime]} ) ^{γ [variant prime]} = _{c 0} ^{γ [variant prime]} = _{c 0} = x ^{γ [variant prime]} . So ^{γ [variant prime]} is an idempotent. Therefore, α <= β by ( [low *] ) .

Remark 2.

If Y = ∅ , then F i x ( X , Y ) = T ( X ) , and we have the characterization of <= on T ( X ) which first appeared in [4, Proposition 2.3].

As a direct consequence of Theorem 1, we get the following corollary.

Corollary 3.

Let α , β ∈ F i x ( X , Y ) with α <= β . If X α \ Y = X β \ Y , then α = β .

Let S be a semigroup. An element a ∈ S is said to be left (right) compatible with respect to the partial order <= if a b <= a c ( b a <= c a ) whenever b <= c .

The following results describe all the left compatible and right compatible elements in F i x ( X , Y ) when ∅ ≠ Y [subset of not =] X . We also write α < β instead of α <= β and α ≠ β for α , β ∈ F i x ( X , Y ) .

Theorem 4.

Assume that ∅ ≠ Y [subset of not =] X and let λ ∈ F i x ( X , Y ) . Then λ is left compatible if and only if λ is a minimal idempotent or λ is surjective.

Proof.

Suppose that λ is left compatible. Assume by contrary that λ is not a minimal idempotent and λ is not surjective. So there are a ∈ X λ \ Y and b ∈ X \ X λ . Define [figure omitted; refer to PDF] Then α , β ∈ F i x ( X , Y ) with α < β and thus λ α <= λ β since λ is left compatible. However, X λ α [neither a subset of nor =] X λ β since a ∈ X λ α but a ∉ X λ β , a contradiction.

Conversely, let α <= β . If λ is a minimal idempotent, then λ α = λ = λ β . Now, assume that λ is surjective. So X λ α = X α ⊆ X β = X λ β . Let A ∈ _{π λ β} . So A = ^{x ( λ β ) - 1} = ( ^{x β - 1} ) ^{λ - 1} for some x ∈ X λ β . Since α <= β , we have that _{π β} refines _{π α} and hence ^{x β - 1} ⊆ ^{x [variant prime] α - 1} for some ^{x [variant prime]} ∈ X α . Since ^{x [variant prime]} ∈ X α , we get ^{x [variant prime]} = u α for some u ∈ X and u = v λ for some v ∈ X because λ is surjective. Hence v λ α = u α = ^{x [variant prime]} ; that is, ^{x [variant prime]} ∈ X λ α . Further, A = ( ^{x β - 1} ) ^{λ - 1} ⊆ ( ^{x [variant prime] α - 1} ) λ ^{- 1} = ^{x [variant prime] ( λ α ) - 1} ∈ _{π λ α} , thus _{π λ β} refines _{π λ α} . Let a λ β ∈ X λ α . So ( a λ ) β ∈ X α and then a λ β = a λ α . By Theorem 1, we have λ α <= λ β which implies that λ is left compatible.

Theorem 5.

The following statements hold.

(1) If | Y | = 1 , then λ ∈ F i x ( X , Y ) is right compatible if and only if λ is a minimal idempotent or λ is injective.

(2) If | Y | ≥ 2 , then λ ∈ F i x ( X , Y ) is right compatible if and only if λ is injective.

Proof.

( 1 ) Assume that Y = { y } and λ is right compatible. Suppose in the contrary that λ is not a minimal idempotent and λ is not injective. So we can write [figure omitted; refer to PDF] where y ∈ A and J ≠ ∅ . Since λ is not injective, two cases arise.

Case 1 . Consider | A | ≥ 2 . Choose a ∈ A \ { y } and c ∈ _{B j 0} for some _{j 0} ∈ J . Let X \ { a , c } = { _{x k} : k ∈ K } and define α ∈ F i x ( X , Y ) by [figure omitted; refer to PDF] we get α < _{1 X} . Moreover, we have a ( _{1 X} λ ) = a λ = y = y ( _{1 X} λ ) , hence there is B ∈ _{π 1 X λ} such that { a , y } ⊆ B . However, { a , y } [neither a subset of nor =] C for all C ∈ _{π α λ} since a ( α λ ) = c λ = _{b j 0} ≠ y = y ( α λ ) . This means that _{π 1 X λ} does not refine _{π α λ} . By Theorem 1, we get α λ [neither < nor =] _{1 X} λ , a contradiction.

Case 2 . Consider | _{B j 0} | ≥ 2 for some _{j 0} ∈ J . Choose a , b ∈ _{B j 0} such that a ≠ b . Let X \ { a , b , y } = { _{x k} : k ∈ K } . Define α , β ∈ F i x ( X , Y ) by [figure omitted; refer to PDF] we get α < β . Since a ( β λ ) = b λ = a λ = b ( β λ ) , there is B ∈ _{π β λ} such that { a , b } ⊆ B . However, { a , b } [neither a subset of nor =] C for all C ∈ _{π α λ} since a ( α λ ) = y λ = y ≠ _{b j 0} = a λ = b ( α λ ) . So _{π β λ} does not refine _{π α λ} . By Theorem 1, we get α λ [neither < nor =] β λ , a contradiction.

Conversely, let α , β ∈ F i x ( X , Y ) be such that α <= β . If λ is a minimal idempotent, then λ = ( X y ) and α λ = λ = β λ ; that is, λ is right compatible. Now, assume that λ is injective. Since X α ⊆ X β , we get X α λ ⊆ X β λ . Let A ∈ _{π β λ} . So A = ^{x ( β λ ) - 1} = ( ^{x λ - 1} ) β ^{- 1} for some x ∈ X β λ and hence ( ^{x λ - 1} ) ^{β - 1} ⊆ ^{x [variant prime] α - 1} for some ^{x [variant prime]} ∈ X α . So ^{x [variant prime]} = u α for some u ∈ X . Since λ is injective, { ^{x [variant prime]} } = ^{v λ - 1} for some v ∈ X λ and u α λ = ^{x [variant prime]} λ = v ; that is, v ∈ X α λ . Thus ^{x [variant prime] α - 1} = ( ^{v λ - 1} ) ^{α - 1} = ^{v ( α λ ) - 1} ∈ _{π α λ} which implies that _{π β λ} refines _{π α λ} . Let a β λ ∈ X α λ . So a β λ = b α λ for some b ∈ X . Since λ is injective, a β = b α and then a β ∈ X α . Thus a β = a α since α <= β and that a β λ = a α λ . Therefore, α λ <= β λ , and we conclude that λ is right compatible.

( 2 ) Suppose that λ is right compatible and λ is not injective. Write [figure omitted; refer to PDF] where _{y i} ∈ _{A i} and | I | ≥ 2 . Since λ is not injective, two cases arise.

Case 1 . | _{A i 0} | ≥ 2 for some _{i 0} ∈ I . Choose a ∈ _{A i 0} \ { _{y i 0} } and _{y i 1} ∈ Y \ { _{y i 0} } . Let X \ { _{y i 1} , a } = { _{x k} : k ∈ K } and define [figure omitted; refer to PDF] Then α < _{1 X} and hence α λ <= _{1 X} λ . We can see that { _{y i 0} , a } ⊆ _{A i 0} ∈ _{π λ} = _{π 1 X λ} , but { _{y i 0} , a } [neither a subset of nor =] B for all B ∈ _{π α λ} since a α λ = _{y i 1} λ = _{y i 1} ≠ _{y i 0} = _{y i 0} α λ . This means that _{π 1 X λ} does not refine _{π α λ} , a contradiction.

Case 2 . | _{B j 0} | ≥ 2 for some _{j 0} ∈ J . This is virtually identical to Case 2 of ( 1 ) above.

4. Minimal and Maximal Elements

Let S be a semigroup together with the partial order <= . S is said to be directed downward if every pair of elements has a lower bound. In other words, for any a and b in S , there exists c in S with c <= a and c <= b . A directed upward semigroup is defined dually.

If Y = ∅ , then F i x ( X , Y ) = T ( X ) and it has neither minimum nor maximum elements under the natural order (see [4]). So, in Lemmas 6 and 7 we assume that ∅ ≠ Y [subset of not =] X .

Lemma 6.

Assume that ∅ ≠ Y [subset of not =] X . Then the following statements are equivalent.

(1) F i x ( X , Y ) has a minimum element.

(2) F i x ( X , Y ) is directed downward.

(3) | Y | = 1 .

Proof.

(1)[implies](2) This is clear.

(2)[implies](3) Assume that F i x ( X , Y ) is directed downward. Let _{y i 1} , _{y i 2} ∈ Y and J = I \ { _{i 1} , _{i 2} } . Consider [figure omitted; refer to PDF] We have α , β ∈ F i x ( X , Y ) and there is γ ∈ F i x ( X , Y ) such that γ <= α and γ <= β . By Theorem 1, _{π α} refines _{π γ} and _{π β} refines _{π γ} . Then there is A ∈ _{π γ} such that ( X \ Y ) ∪ { _{y i 1} } ⊆ A and ( X \ Y ) ∪ { _{y i 2} } ⊆ A . Thus _{y i 1} , _{y i 2} ∈ A and hence _{y i 1} = _{y i 2} . Since _{y i 1} , _{y i 2} are arbitrary elements in Y , we obtain that | Y | = 1 .

(3)[implies](1) Assume that Y = { y } . It is easy to see that θ = ( X y ) is the minimum element in F i x ( X , Y ) .

Lemma 7.

Assume that ∅ ≠ Y [subset of not =] X . Then the following statements are equivalent.

(1) F i x ( X , Y ) has a maximum element.

(2) F i x ( X , Y ) is directed upward.

(3) | X \ Y | = 1 .

Proof.

(1)[implies](2) This is clear.

(2)[implies](3) Assume that F i x ( X , Y ) is directed upward. Let a , b ∈ X \ Y and X \ { a , b } = { _{x k} : k ∈ K } . Define [figure omitted; refer to PDF] Then there is γ ∈ F i x ( X , Y ) such that α <= γ and _{1 X} <= γ . Since α and _{1 X} are bijective, γ is also bijective and thus b γ ∈ ( X α \ Y ) ∩ ( X _{1 X} \ Y ) . So a = b α = b γ = b _{1 X} = b . Since a , b are arbitrary elements in X \ Y , we get | X \ Y | = 1 .

(3)[implies](1) Assume that | X \ Y | = 1 . It is easy to see that _{1 X} is the maximum element in F i x ( X , Y ) .

We now describe minimal and maximal elements in F i x ( X , Y ) when ∅ ≠ Y [subset of not =] X . If | Y | = 1 , then F i x ( X , Y ) has a minimum element by Lemma 6 and it is minimal. In the same way, if | X \ Y | = 1 , then F i x ( X , Y ) has a maximum element by Lemma 7 and it is maximal.

Theorem 8.

Assume that ∅ ≠ Y [subset of not =] X and let α ∈ F i x ( X , Y ) . Then α is minimal if and only if α is a minimal idempotent.

Proof.

Assume that α is minimal but α is not a minimal idempotent. So we can write [figure omitted; refer to PDF] where J ≠ ∅ . Choose _{i 0} ∈ I and _{j 0} ∈ J . Let ^{I [variant prime]} = I \ { _{i 0} } , ^{J [variant prime]} = J \ { _{j 0} } and define β ∈ F i x ( X , Y ) by [figure omitted; refer to PDF] Hence β < α , which contradicts the minimality of α .

Conversely, assume that α is a minimal idempotent and β <= α . Since Y ⊆ X β ⊆ X α = Y , we get X β = X α and hence X β \ Y ⊆ X α \ Y . By Corollary 3, we obtain β = α .

Theorem 9.

Assume that ∅ ≠ Y [subset of not =] X and let α ∈ F i x ( X , Y ) . Then α is maximal if and only if α is injective or α is surjective.

Proof.

Let α be maximal. Assume that α is not injective and surjective. So there are a , b , c ∈ X such that a α = b α with a ≠ b and c ∈ X \ X α . Write [figure omitted; refer to PDF]

Case 1. a , b ∈ _{A i 0} for some _{i 0} ∈ I . We may assume that a ≠ _{y i 0} . Let ^{I [variant prime]} = I \ { _{i 0} } and define [figure omitted; refer to PDF] Then β ∈ F i x ( X , Y ) and α < β which contradicts the maximality of α .

Case 2 . a , b ∈ _{B j 0} for some _{j 0} ∈ J . Then we let ^{J [variant prime]} = J \ { _{j 0} } and define [figure omitted; refer to PDF] Then γ ∈ F i x ( X , Y ) and α < γ which contradicts the maximality of α .

Conversely, assume that α is injective or α is surjective and α <= β for some β ∈ F i x ( X , Y ) . Then X α ⊆ X β and X α \ Y ⊆ X β \ Y . Consider the case where α is injective, by letting z ∈ X β \ Y . Then z = x β for some x ∈ X \ Y and x α ∈ X α \ Y ⊆ X β \ Y ; that is, x α = ^{x [variant prime]} β for some ^{x [variant prime]} ∈ X \ Y . So ^{x [variant prime]} β ∈ X α and ^{x [variant prime]} β = ^{x [variant prime]} α by Theorem 1. Since α is injective, we get x = ^{x [variant prime]} and thus z = x β = ^{x [variant prime]} β = x α ∈ X α \ Y , whence X β \ Y ⊆ X α \ Y . Hence, in this case, X α \ Y = X β \ Y and by Corollary 3 we obtain α = β . In the case α is surjective, we get X \ Y = X α \ Y ⊆ X β \ Y ⊆ X \ Y ; that is, X α \ Y = X β \ Y . Again by Corollary 3, we have that α = β . Therefore, α is maximal.

Figure 1 shows the diagram of F i x ( X , Y ) when X = { 1,2 , 3,4 } and Y = { 1,2 } . The notation ( a b c d ) for α ∈ F i x ( X , Y ) means that 1 α = a , 2 α = b , 3 α = c , and 4 α = d .

Figure 1: [figure omitted; refer to PDF]

An element β ∈ F i x ( X , Y ) is called an upper cover for α ∈ F i x ( X , Y ) if α < β and there is no γ ∈ F i x ( X , Y ) such that α < γ < β ; lower covers are defined dually.

Lemma 10.

Assume that ∅ ≠ Y [subset of not =] X and let α ∈ F i x ( X , Y ) . Then the following statements hold.

(1) If α is not minimal in F i x ( X , Y ) , then there is some lower cover of α in F i x ( X , Y ) .

(2) If α is not maximal in F i x ( X , Y ) , then there is some upper cover of α in F i x ( X , Y ) .

Proof.

( 1 ) Let α ∈ F i x ( X , Y ) be not minimal. By Theorem 8, α is not a minimal idempotent. So we can write [figure omitted; refer to PDF] where J ≠ ∅ . Define β as in the proof of Theorem 8, we get β < α . Suppose that there is λ ∈ F i x ( X , Y ) such that β <= λ <= α . Then by Theorem 1, X β ⊆ X λ ⊆ X α and thus X β \ Y ⊆ X λ \ Y ⊆ X α \ Y . Since X α \ Y = ( X β \ Y ) ∪ { _{b j 0} } which implies X λ \ Y = X β \ Y or X λ \ Y = X α \ Y , thus λ = β or λ = α by Corollary 3. Therefore, β is a lower cover of α .

( 2 ) The proof is similar to ( 1 ) , using β or γ from the proof of Theorem 9 as appropriate.

Now, we aim to find the number of upper covers of minimal elements and the number of lower covers of maximal elements when X is a finite set. The following lemma is needed in finding such numbers.

Lemma 11.

Assume that ∅ ≠ Y [subset of not =] X and let α , β ∈ F i x ( X , Y ) with α < β . Then β is an upper cover of α if and only if | X β \ X α | = 1 .

Proof.

Write [figure omitted; refer to PDF] Since α < β , we can write [figure omitted; refer to PDF] where _{y i} ∈ ^{A i [variant prime]} ⊆ _{A i} , _{C j} ⊆ _{B j} , and _{C k} is contained in either _{A i} for some i or _{B j} for some j . We get | K | = | X β \ X α | .

Assume that β is an upper cover of α . If | X β \ X α | = 0 , then X β = X α which implies that β = α , a contradiction. For the case | X β \ X α | > 1 , we choose _{k 0} ∈ K and hence _{C k 0} ⊆ _{A i 0} for some _{i 0} ∈ I or _{C k 0} ⊆ _{B j 0} for some _{j 0} ∈ J . Assume that _{C k 0} ⊆ _{A i 0} (the other case being similar). Let ^{I [variant prime]} = I \ { _{i 0} } and ^{K [variant prime]} = K \ { _{k 0} } . Define [figure omitted; refer to PDF] Since ^{K [variant prime]} ≠ ∅ , we get α < γ < β , a contradiction. Therefore, | X β \ X α | = 1 .

The converse is proved in similar fashion to Lemma 10 (1).

Let X be a finite set with n elements and Y a nonempty proper subset of X with r elements. If | Y | = 1 , then F i x ( X , Y ) has unique minimal element, say α = ( X y ) . By Lemma 11, each of upper covers of α is of the form ( X \ B B y b ) , where ∅ ≠ B ⊆ X \ { y } and b ∈ X \ Y . Since there are ( ^{2 n - 1} - 1 ) ways to choose B and n - 1 choice of b , in this case there are in total ( ^{2 n - 1} - 1 ) ( n - 1 ) upper covers of α .

If | X \ Y | = 1 , then F i x ( X , Y ) has unique maximal element, the identity map. Let I = { 1,2 , ... , n - 1 } , Y = { _{y i} : i ∈ I } , and X \ Y = { b } . Then each of lower covers of _{1 X} is of the form ( { _{y i 0} , b } _{y ^{i [variant prime]} y i 0 y ^{i [variant prime]}} ) , where ^{I [variant prime]} = I \ { _{i 0} } . Since _{i 0} can be chosen from I , there are in total n - 1 lower covers of _{1 X} .

Theorem 12.

Assume that ∅ ≠ Y [subset of not =] X and let α ∈ F i x ( X , Y ) . Then the following statements hold.

(1) If α = ( _{A i y i} ) is minimal, then there are [figure omitted; refer to PDF]

: upper covers of α .

(2) If α is maximal, then there are ( n - r ) ( n - 1 ) lower covers of α .

Proof.

Since Y is a finite set with r elements, Y = { _{y 1} , ... , _{y r} } and I = { 1 , ... , r } .

( 1 ) Let α = ( _{A i y i} ) be minimal in F i x ( X , Y ) and β an upper cover of α . Then | X β \ X α | = 1 by Lemma 11; that is, X β = Y ∪ { b } for some b ∈ X \ Y . Since _{π β} must refine _{π α} , we can write [figure omitted; refer to PDF] where ^{A i [variant prime]} ⊆ _{A i} and ∅ ≠ B ⊆ _{A i 0} \ { _{y i 0} } for some _{i 0} ∈ I . We claim that ^{A i [variant prime]} = _{A i} for all i ∈ I \ { _{i 0} } . Assume by contrary that there is _{i 1} ∈ I \ { _{i 0} } such that ^{A _{i 1} [variant prime]} [subset of not =] _{A i 1} . Let _{B 1} = _{A i 1} \ ^{A _{i 1} [variant prime]} . So ∅ ≠ _{B 1} ∩ ^{A i [variant prime]} ⊆ _{A i} for some i ≠ _{i 1} , but _{B 1} ⊆ _{A i 1} ; that is _{A i} ∩ _{A i 1} ≠ ∅ , a contradiction. So we can write [figure omitted; refer to PDF] where ^{I [variant prime]} = I \ { _{i 0} } . Since there are ^{2 | _{A i 0} | - 1} - 1 ways to choose B and n - r choices of b , in this case β can have ( ^{2 | _{A i 0} | - 1} - 1 ) ( n - r ) forms, but _{i 0} can be chosen from I = { 1 , ... , r } , so that there are in total ^{∑ i = 1 r} ( ^{2 | _{A i} | - 1} - 1 ) ( n - r ) upper covers of α .

( 2 ) Assume that α is maximal. Then α is a bijection and we can write [figure omitted; refer to PDF] where J = { 1 , ... , n - r } and { _{b j} : j ∈ J } = X \ Y = { _{c j} : j ∈ J } . Let β be a lower cover of α . Then | X α \ X β | = 1 ; that is, X β = X α \ { _{c j 0} } for some _{j 0} ∈ J . Let ^{J [variant prime]} = J \ { _{j 0} } and _{b ^{j [variant prime]}} ∈ { _{b j} : j ∈ ^{J [variant prime]} } . So _{b ^{j [variant prime]}} α = _{c ^{j [variant prime]}} ∈ X β \ Y , then _{b ^{j [variant prime]}} α = _{b ^{j [variant prime]}} β since β < α . Hence x α = x β for all x ∈ X \ { _{b j 0} } and _{b j 0} β = _{y i 0} for some _{i 0} ∈ I or _{b j 0} β = _{b j 1} β = _{c j 1} for some _{j 1} ∈ ^{J [variant prime]} . Thus [figure omitted; refer to PDF] where ^{I [variant prime]} = I \ { _{i 0} } , or [figure omitted; refer to PDF] where K = J \ { _{j 0} , _{j 1} } . For the first form and the second form, the numbers of ways of placing _{b j 0} is r and n - r - 1 , respectively. So the total number of ways of placing _{b j 0} is n - 1 . But _{j 0} varies in the index set J ; hence there are in total ( n - 1 ) ( n - r ) lower covers of α .

Acknowledgments

This research was supported by Chiang Mai University.

References

[1] R. Hartwig, "How to partially order regular elements," Mathematica Japonica , vol. 35, pp. 1-13, 1980.

[2] K. S. Nambooripad, "The natural partial order on a regular semigroup," Proceedings of the Edinburgh Mathematical Society (Series 2) , vol. 23, no. 3, pp. 249-260, 1980.

[3] H. Mitsch, "A natural partial order for semigroups," Proceedings of the American Mathematical Society , vol. 97, no. 3, pp. 384-388, 1986.

[4] G. Kowol, H. Mitsch, "Naturally ordered transformation semigroups," Monatshefte f\"ur Mathematik , vol. 102, no. 2, pp. 115-138, 1986.

[5] C. Namnak, P. Preechasilp, "Natural partial orders on the semigroup of binary relations," Thai Journal of Mathematics , vol. 4, no. 3, pp. 39-50, 2006.

[6] V. H. Fernandes, J. Sanwong, "On the ranks of semigroups of transformations on a finite set with restricted range," Algebra Colloquium , vol. 21, no. 3, pp. 497-510, 2014.

[7] K. Sangkhanan, J. Sanwong, "Partial orders on semigroups of partial transformations with restricted range," Bulletin of the Australian Mathematical Society , vol. 86, no. 1, pp. 100-118, 2012.

[8] P. Honyam, J. Sanwong, "Semigroups of transformations with fixed sets," Quaestiones Mathematicae. Journal of the South African Mathematical Society , vol. 36, no. 1, pp. 79-92, 2013.

[9] Y. Chaiya, P. Honyam, J. Sanwong, "Maximal subsemigroups and finiteness conditions on transformation semigroups with fixed sets," In press Turkish Journal of Mathematics

[10] P. M. Higgins, "The Mitsch order on a semigroup," Semigroup Forum , vol. 49, no. 2, pp. 261-266, 1994.