# Natural Partial Orders on Transformation Semigroups with Fixed Sets

Authors: Yanisa Chaiya; Preeyanuch Honyam; Jintana Sanwong
Journal: International Journal of Mathematics and Mathematical Sciences
 (2016)

---

## Abstract

LetX 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.


---

## Body

## 1. Introduction

For any semigroupS, the natural partial order on E
(
S
), the set of all idempotents on S, is defined by(1)
e
≤
f
iff
e
=
e
f
=
f
e
.In 1980, Hartwig [1] and Nambooripad [2] proved that if S is a regular semigroup, then the relation∗
a
≤
b
iff
a
=
e
b
=
b
f
for some
e
,
f
∈
E
Sis 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 semigroupS by Mitsch [3] as follows: (2)
a
≤
b
iff
a
=
x
b
=
b
y
,
x
a
=
a
for some
x
,
y
∈
S
1
.LetX be a set and B
(
X
) denote the semigroup of binary relations on the set X under the composition of relations. Apartial 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 thefull 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.LetY be a subset of X. Recently, Fernandes and Sanwong [6] defined (3)
P
T
X
,
Y
=
α
∈
P
X
:
X
α
⊆
Y
,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.LetY be a fixed subset of X and(4)
F
i
x
X
,
Y
=
α
∈
T
X
:
y
α
=
y
∀
y
∈
Y
.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
⊊
X, and every semigroup S is isomorphic to a subsemigroup of F
i
x
(
X
′
,
Y
′
) for some appropriate sets X
′ and Y
′ with Y
′
⊆
X
′. 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 onF
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
⊊
X and |
X
|
>
1.For anyα
∈
T
(
X
), the symbol π
α denotes the partition of X induced by the map α, namely, (5)
π
α
=
x
α
-
1
:
x
∈
X
α
.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, letY
=
{
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(6)
α
=
A
i
B
j
y
i
b
jand 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 idempotente 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 (7)
E
m
=
A
i
y
i
:
A
i
:
i
∈
I
is a partition of
X
with
y
i
∈
A
iis 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 onFix
⁡
(
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 π
α.SinceF
i
x
(
X
,
Y
) is regular, we use ∗ 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)
ifx
β
∈
X
α, then x
β
=
x
α.Proof.
Suppose thatα
≤
β. Then, by ∗, we have (8)
α
=
λ
β
=
β
γfor some λ
,
γ
∈
E
(
F
i
x
(
X
,
Y
)
). Thus X
α
=
(
X
λ
)
β
⊆
X
β. Since α
=
β
γ, we get that π
β refines π
α. Now, let x
β
∈
X
α. Then x
β
=
x
′
α for some x
′
∈
X and thus x
β
=
x
′
α
=
x
′
β
γ
=
(
x
′
β
)
γ. 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 (9)
α
=
A
i
B
j
y
i
b
j
,
β
=
A
i
′
C
j
C
k
y
i
b
j
b
k
,where y
i
∈
A
i
∩
A
i
′, b
j
,
b
k
∈
X
∖
Y, and B
j
,
C
j
,
C
k
⊆
X
∖
Y. Since y
i
∈
A
i
∩
A
i
′ and π
β refines π
α, we obtain A
i
′
⊆
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 (10)
λ
=
A
i
B
j
y
i
c
j
.We get λ
∈
E
(
F
i
x
(
X
,
Y
)
) and α
=
λ
β.
IfK
=
∅, 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(11)
x
γ
=
x
,
x
∈
X
α
,
c
k
α
,
x
=
b
k
∈
X
∖
X
α
.To prove that α
=
β
γ, let x
∈
X. If x
∈
A
i
′ 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
β
⊊
X
. We choose c
0
∈
X
∖
X
β and define γ
′
∈
F
i
x
(
X
,
Y
) by(12)
x
γ
′
=
x
,
x
∈
X
α
,
c
k
α
,
x
=
b
k
∈
X
β
∖
X
α
,
c
0
,
x
∈
X
∖
X
β
.By the same prove as given in Case  1, we get α
=
β
γ
′ and x
γ
′
γ
′
=
x
γ
′ for all x
γ
′
∈
X
β. If x
γ
′
=
c
0, then x
γ
′
γ
′
=
c
0
γ
′
=
c
0
=
x
γ
′. So γ
′ is an idempotent. Therefore, α
≤
β by ∗.Remark 2.
IfY
=
∅, 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 Theorem1, we get the following corollary.Corollary 3.
Letα
,
β
∈
F
i
x
(
X
,
Y
) with α
≤
β. If X
α
∖
Y
=
X
β
∖
Y, then α
=
β.LetS be a semigroup. An element a
∈
S is said to beleft (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 inF
i
x
(
X
,
Y
) when ∅
≠
Y
⊊
X. We also write α
<
β instead of α
≤
β and α
≠
β for α
,
β
∈
F
i
x
(
X
,
Y
).Theorem 4.
Assume that∅
≠
Y
⊊
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 (13)
α
=
y
i
X
∖
Y
y
i
a
,
β
=
y
i
b
X
∖
Y
∪
b
y
i
a
b
. Then α
,
β
∈
F
i
x
(
X
,
Y
) with α
<
β and thus λ
α
≤
λ
β since λ is left compatible. However, X
λ
α
⊈
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
′
α
-
1 for some x
′
∈
X
α. Since x
′
∈
X
α, we get x
′
=
u
α for some u
∈
X and u
=
v
λ for some v
∈
X because λ is surjective. Hence v
λ
α
=
u
α
=
x
′; that is, x
′
∈
X
λ
α. Further, A
=
(
x
β
-
1
)
λ
-
1
⊆
(
x
′
α
-
1
)
λ
-
1
=
x
′
(
λ
α
)
-
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 (14)
λ
=
A
B
j
y
b
j
,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 (15)
α
=
a
,
c
x
k
c
x
k
;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
}
⊈
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 α
λ
≰
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(16)
α
=
y
,
a
b
x
k
y
a
x
k
,
β
=
a
b
y
x
k
b
a
y
x
k
, we get α
<
β. Since a
(
β
λ
)
=
b
λ
=
a
λ
=
b
(
β
λ
), there is B
∈
π
β
λ such that {
a
,
b
}
⊆
B. However, {
a
,
b
}
⊈
C for all C
∈
π
α
λ since a
(
α
λ
)
=
y
λ
=
y
≠
b
j
0
=
a
λ
=
b
(
α
λ
). So π
β
λ does not refine π
α
λ. By Theorem 1, we get α
λ
≰
β
λ, 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
′
α
-
1 for some x
′
∈
X
α. So x
′
=
u
α for some u
∈
X. Since λ is injective, {
x
′
}
=
v
λ
-
1 for some v
∈
X
λ and u
α
λ
=
x
′
λ
=
v; that is, v
∈
X
α
λ. Thus x
′
α
-
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 (17)
λ
=
A
i
B
j
y
i
b
j
,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 (18)
α
=
y
i
1
,
a
x
k
y
i
1
x
k
.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
}
⊈
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

LetS be a semigroup together with the partial order ≤. S is said to bedirected 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.IfY
=
∅, 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
⊊
X.Lemma 6.
Assume that∅
≠
Y
⊊
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)⇒(2) This is clear.
(2)⇒(3) Assume thatF
i
x
(
X
,
Y
) is directed downward. Let y
i
1
,
y
i
2
∈
Y and J
=
I
∖
{
i
1
,
i
2
}. Consider (19)
α
=
y
j
y
i
2
X
∖
Y
∪
y
i
1
y
j
y
i
2
y
i
1
,
β
=
y
j
y
i
1
X
∖
Y
∪
y
i
2
y
j
y
i
1
y
i
2
.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)⇒(1) Assume thatY
=
{
y
}. It is easy to see that θ
=
X
y is the minimum element in F
i
x
(
X
,
Y
).Lemma 7.
Assume that∅
≠
Y
⊊
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)⇒(2) This is clear.
(2)⇒(3) Assume thatF
i
x
(
X
,
Y
) is directed upward. Let a
,
b
∈
X
∖
Y and X
∖
{
a
,
b
}
=
{
x
k
:
k
∈
K
}. Define (20)
α
=
a
b
x
k
b
a
x
k
∈
F
i
x
X
,
Y
.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)⇒(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 inF
i
x
(
X
,
Y
) when ∅
≠
Y
⊊
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
⊊
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 (21)
α
=
A
i
B
j
y
i
b
j
,where J
≠
∅. Choose i
0
∈
I and j
0
∈
J. Let I
′
=
I
∖
{
i
0
}, J
′
=
J
∖
{
j
0
} and define β
∈
F
i
x
(
X
,
Y
) by (22)
β
=
A
i
0
∪
B
j
0
A
i
′
B
j
′
y
i
0
y
i
′
b
j
′
.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
⊊
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 (23)
α
=
A
i
B
j
y
i
b
j
.
Case  1.
a
,
b
∈
A
i
0 for some i
0
∈
I
. We may assume that a
≠
y
i
0. Let I
′
=
I
∖
{
i
0
} and define(24)
β
=
A
i
0
∖
a
a
A
i
′
B
j
y
i
0
c
y
i
′
b
j
.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
′
=
J
∖
{
j
0
} and define (25)
γ
=
A
i
B
j
0
∖
a
a
B
j
′
y
i
b
j
0
c
b
j
′
.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
′
β for some x
′
∈
X
∖
Y. So x
′
β
∈
X
α and x
′
β
=
x
′
α by Theorem 1. Since α is injective, we get x
=
x
′ and thus z
=
x
β
=
x
′
β
=
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.Figure1 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 1An elementβ
∈
F
i
x
(
X
,
Y
) is called anupper 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
⊊
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 (26)
α
=
A
i
B
j
y
i
b
j
,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 whenX is a finite set. The following lemma is needed in finding such numbers.Lemma 11.
Assume that∅
≠
Y
⊊
X and let α
,
β
∈
F
i
x
(
X
,
Y
) with α
<
β. Then β is an upper cover of α if and only if |
X
β
∖
X
α
|
=
1.Proof.
Write(27)
α
=
A
i
B
j
y
i
b
j
.Since α
<
β, we can write (28)
β
=
A
i
′
C
j
C
k
y
i
b
j
b
k
,where y
i
∈
A
i
′
⊆
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
′
=
I
∖
{
i
0
} and K
′
=
K
∖
{
k
0
}
. Define(29)
γ
=
A
i
0
′
∪
C
k
0
A
i
′
′
C
j
C
k
′
y
i
0
y
i
′
b
j
b
k
′
∈
F
i
x
X
,
Y
.Since K
′
≠
∅, we get α
<
γ
<
β, a contradiction. Therefore, |
X
β
∖
X
α
|
=
1.
The converse is proved in similar fashion to Lemma10 (1).LetX 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
′
y
i
0
y
i
′, where I
′
=
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
⊊
X and let α
∈
F
i
x
(
X
,
Y
). Then the following statements hold.(1)
Ifα
=
A
i
y
i is minimal, then there are (30)
∑
i
=
1
r
2
A
i
-
1
-
1
n
-
r
upper covers ofα.
(2)
Ifα is maximal, then there are (
n
-
r
)
(
n
-
1
) lower covers of α.Proof.
SinceY 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 (31)
β
=
A
i
′
B
y
i
b
,where A
i
′
⊆
A
i and ∅
≠
B
⊆
A
i
0
∖
{
y
i
0
} for some i
0
∈
I. We claim that A
i
′
=
A
i for all i
∈
I
∖
{
i
0
}. Assume by contrary that there is i
1
∈
I
∖
{
i
0
} such that A
i
1
′
⊊
A
i
1. Let B
1
=
A
i
1
∖
A
i
1
′. So ∅
≠
B
1
∩
A
i
′
⊆
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(32)
β
=
A
i
′
A
i
0
∖
B
B
y
i
′
y
i
0
b
,where I
′
=
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 (33)
α
=
y
i
b
j
y
i
c
j
,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
′
=
J
∖
{
j
0
} and b
j
′
∈
{
b
j
:
j
∈
J
′
}. So b
j
′
α
=
c
j
′
∈
X
β
∖
Y, then b
j
′
α
=
b
j
′
β 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
′. Thus (34)
β
=
y
i
0
,
b
j
0
y
i
′
b
j
′
y
i
0
y
i
′
c
j
′
,where I
′
=
I
∖
{
i
0
}, or(35)
β
=
y
i
b
j
1
,
b
j
0
b
k
y
i
c
j
1
c
k
,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 α.



---

*Source: 2759090-2016-08-21.xml*