2 Biordered Sets and Bimorphisms

denote a family of partial transformation of

E

such that for each

e \in E

τ^{r} (e)

and

τ^{l} (e)

are idempotent mappings of

ω^{r} (e)

and

ω^{l} (e)

respectively onto

ω (e)

. Then

(E, ω^{r}, ω^{l}, τ)

is a biordered set if

ω^{r}

ω^{l}

and

τ

satisfy the following axioms.

In a biordered set

(E, ω^{r}, ω^{l}, τ)

, we call the quasi-order

ω^{r} (ω^{l})

the right (left) quasi-order, the partial transformations

τ^{r} (e) (τ^{l} (e))

e \in E

, the partial right (left) translation (or

r (l)

-translation) corresponding to

e

and the set

S (e, f)

, the sandwich set for

e

and

f

When there is no confusion we denote the biordered set

(E, ω^{r}, ω^{l}, τ)

E

. Also if

E

and

E'

are two biordered sets, for convenience we denote quasi-orders, translations etc. by the same symbols if the context makes the meaning clear. Thus

e ω^{r} f

means

e

and

f

are

ω^{r}

-related in

E

e, f \in E

and they are so related (under this order) in

E'

e, f \in E'

. We adopt the same convention to translations, sandwich sets etc.

As observed earlier, axioms for biordered sets include

(B_{i}), i = 1, 2, 3, 4, 5

as well as their duals. The dual

{(B_{i})}^{*}

(B_{i})

can be obtained by interchanging

r

and

l

(B_{i})

. It may be noted that axiom

(B_{5})

is essentially self dual.

Equality of two partial transformations

α

and

β

E

is to be understood in the sense of equality of the associated subsets of

E \times E

. Since this idea is used frequently in this work, we state the necessary and sufficient condition for this equality explicitly as follows.

Example 2.1: Let $E = {e, f_{1}, f_{2}, f_{3})$ . Define $ω^{r} = (E \times {e}) \cup {(E')}^{2}$ and $ω^{l} = {(f_{2}, e), (f_{3}, e)} \cup I_{E}$ where $E' = {f_{1}, f_{2}, f_{3}}$ . Then $ω^{r}$ and $ω^{l}$ are quasi-orders on $E$ such that $ω^{l} \subseteq ω^{r}$ and

ω^{r} \cap {(ω^{l})}^{- 1} = {(ω^{r})}^{- 1} \cap ω^{l} = I_{E},

where $E' = {f_{1}, f_{2}, f_{3}}$ . Then $ω^{r}$ and $ω^{l}$ are quasi-orders on $E$ such that $ω^{l} \subseteq ω^{r}$ and

ω^{r} \cap {(ω^{l})}^{- 1} = {(ω^{r})}^{- 1} \cap ω^{l} = I_{E} .

It is clear that

ω^{r} (e) = E, ω^{r} (f_{i}) = E' (i = 1, 2, 3)

ω^{l} (e) = ω (e) = {e, f_{2}, f_{3}}

and

ω^{l} (f_{i}) = ω (f_{i}) = {f_{i}} (i = 1, 2, 3)

. Let

τ^{r} (e)

denote the idempotent mappings of

E

onto

ω (e)

such that

f, τ^{r} (e) = f_{2}

. Define

τ^{r} (f_{i})

f_{j} τ^{r} (f_{i}) = f_{i}

for

i, j = 1, 2, 3

. Further let

τ^{l} (x)

denote identify map on

ω^{l} (x) = ω (x)

. If

then

(E, ω^{r}, ω^{l}, τ)

is a biordered set. Further if

τ_{1}^{r} (e)

denotes another idempotent mapping of

E

onto

ω (e)

such that

f, τ^{r} (e) = f_{3}

and if

then

(E, ω^{r}, ω^{l}, τ_{1})

is also a biordered set. These two differ only with respect to translations.

Remark 2.2: Let $(E, ω)$ be a semilattice. If

I = {I_{ω (e)} | e \in E},

(where each $I_{ω (e)}$ denotes identity map on the $ω$ -ideal $ω (e)$ of $E$ ), then $(E, ω, ω, I)$ is a biordered set. Since for each $e \in E$ , $τ^{r} (e)$ and $τ^{l} (e)$ are identity maps, axioms $(B_{1}), (B_{2}), (B_{3})$ and their duals are obviously satisfied. Axiom $(B_{4})$ (and ${(B_{4})}^{*}$ ) is satsified with $S (e, f) = {e f}$ where $e f$ denotes the product of $e$ and $f$ in $(E, ω)$ and $(B_{5})$ is satsified with $g_{2} = g'_{2} = g_{2}^{''}$ .

then

τ

must coincide with

I

defined above. For

e, f \in E

h \in S (e, f)

, implies that

and

h

is the greatest member of

ω (e) \cap ω (f)

. Thus

(E, ω)

is a semilattice.

We say that the biordered set satisfying the condition (2.7) is a semilattice. In the following we do not distinguish between the biordered set

(E, ω, ω, I)

and the semilattice

(E, ω)

It may be noted that in a biordered set

(E, ω^{r}, ω^{l}, τ)

one or more of the quasi-ordered sets

(E, ω^{r})

(E, ω^{l})

(E, ω)

(but not all) may be semilattices without the biordered set satisfying condition (2.7). This is shown by an example given below. Clearly if

(E, ω^{r}) ((E, ω^{l}))

is a semilattice,

ω^{r} = ω (ω^{l} = ω)

Example 2.2: Let $(E, ω^{r}, ω^{l}, τ)$ be a biordered set and let 1 denote a symbol not representing any element of $E$ . Let $E^{1} = E \cup {1}$ . Extend $ω^{r}$ and $ω^{l}$ to $E^{1}$ by defining

e ω 1

for every $e \in E$ , and $τ$ by defining

τ^{r} (1) = τ^{l} (1) = I_{E'} .

With these extended quasi-orders and translations, $E^{1}$ becomes a biordered set.

We say that

e \in E

is the identity (the zero) of the biordered set

E

if and only if for every

f \in E

Let

E^{1}

stands for

E

E

has identity, and it denotes the biordered set constructed above if

E

has no identity. Similarly

E^{0}

stands for

E

E

has a zero. If not, it denotes the biordered set obtained by adjoining

0

E

, where

0 ω e

0 τ^{r} (e) = 0 τ^{l} (e) = 0

for every

e \in E \cup {0}

Example 2.3: Let $(E, \leq)$ be a semilattice and $X, Y$ denote arbitrary non-null sets. Let $E^{'} = X \times E \times Y$ and define $ω^{r}$ and $ω^{l}$ in $E$ as follows.

\begin{array}{rcl} (x, e, y) ω^{r} (x^{'}, e^{'}, y^{'}) & \Leftrightarrow & e^{'} \leq e, y = y^{'}; \\ (x, e, y) ω^{l} (x^{'}, e^{'}, y^{'}) & \Leftrightarrow & x = x^{'}, e^{'} \leq e . \end{array}

Then it is clear that

τ^{r} (x, e, y)

and

τ^{l} (x, e, y)

are idempotent mappings of

ω^{r} (x, e, y)

and

ω^{l} (x, e, y)

respectively onto

ω (x, e, y)

. Let

Hence for any

(x^{'}, g, y^{'}) \in ω^{l} (x, e, y) \cap ω^{r} (x_{1}, e_{1}, y_{1})

we have

x^{'} = x, g \leq e e_{1}, y^{'} = y_{1}

(x, g, y_{1}) \in S ((x, e, y), (x_{1}, e_{1}, y_{1}))

, then from the fact that

((x, g, y), (x_{1}, g, y_{1}))

and

((x, e e_{1}, y), (x_{1}, e e_{1}, y_{1}))

are universally maximal in

M ((x, e, y), (x_{1}, e_{1}, y_{1}))

, we have

g = e e_{1}

, and

From this axiom

(B_{4})

follows, Axiom

{(B_{4})}^{*}

may be verified similarly.

(x, g_{1}, y_{1}), (x, g_{2}, y_{1}) \in ω^{l} (x, e, y) \cup ω^{r} (x_{1}, e_{1}, y_{1})

then hypothesis of

(B_{5})

implies that

and hence axiom

(B_{5})

is satisfied. (In this case,

g_{2}, g_{2}^{'}, g_{2}^{''}

of axiom

(B_{5})

coincide.)

Note: In this example

S ((x, e, y), (x_{1}, e_{1}, y_{1})) = {(x, e e_{1}, y_{1})}

and

S ((x_{1}, e_{1}, y_{1}), (x, e, y)) = {(x_{1}, e e_{1}, y)} .

Hence unless $x = x_{1}$ and $y = y_{1}$

S ((x, e, y), (x_{1}, e_{1}, y_{1})) \neq S ((x_{1}, e_{1}, y_{1}), (x, e, y)) .

Thus in a biordered set, in general, $S (e, f) \neq S (f, e)$ .

Example 2.4: Let $E^{'}$ denote the biordered set constructed in 2.3. Then if both $X$ and $Y$ contain more than one element, $ω^{r} \neq ω^{l} \neq ω$ and if $X (Y)$ contains only one element, $ω^{r} \subseteq ω^{l} (ω^{l} \subseteq ω^{r})$ .

Let ${(E^{'})}^{0}$ denote the biordered set obtained by adjoining $0$ to $E^{'}$ . Then $({(E^{'})}^{0}, ω)$ is a semilattice.

When both $X$ and $Y$ contain more than one element, this gives an example of a biordered set $E$ such that $ω^{r} \neq ω^{l} \neq ω$ and $(E, ω)$ is a semilattice.

Following are certain consequence of the definition of biordered sets. (

E

stands for a biordered set,

e

f

etc. are its elements.)

Proof. If $f τ^{r} (e) = e, e \overset{r}{\approx} f$ by $(B_{1})$ . Conversely if $e \overset{r}{\approx} f$ , $f τ^{r} (e) \in ω (e)$ and by $(B_{1})$ $f τ^{r} (e) \overset{r}{\approx} f \overset{r}{\approx} e$ . Hence by (2.1)

(f τ^{r} (e), e) \in ω \cap (\overset{r}{\approx}) \subseteq ω^{l} \cap {(ω^{r})}^{- 1} = I_{E} .

□

Proof. Let $h \in S (e, f)$ . Then by $(B_{4})$ and Lemma 2.3* we have

e = g τ^{l} (e) ω^{r} h τ^{l} (e) ω e,

and thus, $h \overset{l}{\approx} g$ . Dually we can show that $h \overset{r}{\approx} g$ . □

Proof. In the first case, if $h \in S (e, f)$

e = e τ^{l} (e) ω^{r} h τ^{l} (e) ω e

so that $e \overset{l}{\approx} h$ . Since $e, h \in ω^{r} (f)$ , by $(B_{3})$ , $e τ^{r} (f) \overset{l}{\approx} h τ^{r} (f)$ . Hence

((e τ^{l} (e))), (e τ^{r} (f)) (\overset{r}{\approx} \times \overset{l}{\approx}), (h τ^{l} (e)), (h τ^{r} (f))

and therefore $(e τ^{l} (e), e τ^{r} (f))$ is universally maximal in $M (e, f)$ .

In the second case, we have by ${(B_{2})}^{*}$ that $(e τ^{l} (f)) τ^{l} (e) = e$ and hence

(e τ^{l} (f)) τ^{l} (e) = e ω^{r} h τ^{l} (e) ω e .

Thus $(e τ^{l} (f)) τ^{l} (e) = h τ^{l} (e)$ and by $(B_{3})$ , $(e τ^{l} (f)) τ^{r} (f) \overset{l}{\approx} h τ^{r} (f)$ . It now follows that $((e τ^{l} (f)) τ^{l} (e), (e τ^{l} (f)) τ^{r} (f))$ is universally maximal in $M (e, f)$ . □

Lemma 2.6. Let $e \overset{l}{\approx} e^{'}$ and $f \overset{r}{\approx} f^{'}$ . For $g \in ω^{l} (e) \cap ω^{r} (f)$ , define

(g τ^{l} (e), g τ^{r} (f)) m (e^{'}, g^{'}) = (g τ^{l} (e^{'}), g τ^{r} (f^{'})) .

(2.8)

Then $m (e^{'}, f^{'})$ is an order isomorphism of $M (e, f)$ on to $M (e^{'}, f^{'})$ . In particular

S (e, f) = S (e^{'}, f^{'}) .

Proof. For $g \in ω^{l} (e) \cap ω^{r} f$ , by axioms $(B_{2})$ and ${(B_{2})}^{*}$ ,

(g τ^{l} (e), g τ^{r} (f)) m (e^{'}, f^{'}) = ((g τ^{l} (e)) τ^{l} (e^{'}), (g τ^{r} (f)) τ^{r} (f^{'})) .

(g τ^{l} (e^{'}), g τ^{r} (f^{'})) m (e, f) = (g τ^{l} (e), g τ^{r} (f)),

then

m (e^{'}, f^{'}) \circ m (e, f) = I_{M (e, f)}

and

m (e, f) \circ m (e^{'}, f^{'}) = I_{M (e^{'}, f^{'})} .

Cosequently $m (e^{'}, f^{'})$ is a bijection of $M (e, f)$ onto $M (e^{'}, f^{'})$ and

m (e, f) = {(m (e^{'}, f^{'}))}^{- 1} .

Now let

(g_{1} τ^{l} (e), g_{1} τ^{r} (f)) (ω^{r} \times ω^{l}) (g_{2} τ^{l} (e), g_{2} τ^{r} (f)) .

Then $g_{1} τ^{l} (e) ω^{r} g_{2} τ^{l} (e) \in ω^{l} (e^{'})$ and hence by ${(B_{3})}^{*}$

g_{1} τ^{l} (e^{'}) = (g_{1} τ^{l} (e)) τ^{l} (e^{'}) ω^{r} (g_{2} τ^{l} (e)) τ^{l} (e^{'}) = g_{2} τ^{l} (e^{'}) .

Dually we also have $g_{1} τ^{r} (f^{'}) ω^{l} g_{2} τ^{r} (f^{'})$ . Thus $m (e^{'}, f^{'})$ is order preserving and so also is $m (e, f)$ . Consequently $m (e^{'}, f^{'})$ is an order isomorphism.

The equality $S (e, f) = S (e^{'}, f^{'})$ follows from the fact that order isomorphisms preserve universally maximal elements. □

Lemma 2.7. Let $e, f, g_{1}, g_{2}, g_{2}^{'}, g_{2}^{''}$ be as in $(B_{5})$ . Then we have the following:

If $g_{1}^{'} = g_{2}^{'} τ^{r} (g_{1})$ , then $g_{1}^{'} = g_{2}^{''} τ^{l} (g_{1})$ .
$g_{2} \overset{l}{\approx} g_{2}^{'} \overset{r}{\approx} g_{1}^{'} \overset{l}{\approx} g_{2}^{''} \overset{r}{\approx} g_{2}$ .
1. $g_{2} τ^{l} (e) = g_{2}^{'} τ^{l} (e) \overset{r}{\approx} g_{1}^{'} τ^{l} (e) = g_{2}^{''} τ^{l} (e),$
2. $g_{2} τ^{r} (f) = g_{2}^{''} τ^{r} (f) \overset{l}{\approx} g_{1}^{'} τ^{r} (f) = g_{2}^{'} τ^{r} (f)$ .

Furthermore,

$g_{1}^{'} = g_{1} \Leftrightarrow g_{2} τ^{l} (e) \overset{r}{\approx} g_{1} τ^{l} (e)$ (or $g_{2} τ^{r} (f) \overset{l}{\approx} g_{1} τ^{r} (f)$ ).

In particular if $h_{1}, h_{2} \in S (e, f)$ , there exist $h_{2}^{'}$ and $h_{2}^{''}$ in $S (e, f)$ such that

$h_{2} \overset{l}{\approx} h_{2}^{'} \overset{r}{\approx} h_{1} \overset{l}{\approx} h_{2}^{''} \overset{r}{\approx} h_{2}$ .

Proof. Statement (a) follows from (a) and (c) of $(B_{5})$ and statement (b) from (a) of this lemma and (a) of $(B_{5})$ . From statement (b) of this lemma, $(B_{1})$ , $(B_{3})$ and $(B_{5})$ we have

g_{2}^{'} τ^{l} (e) \overset{r}{\approx} g_{1}^{'} τ^{l} (e) \overset{l}{\approx} g_{2}^{''} τ^{l} (e),

and

g_{1}^{'} τ^{l} (e) \overset{r}{\approx} g_{2}^{'} τ^{l} (e) = g_{2} τ^{l} (e) \overset{r}{\approx} g_{2}^{''} τ^{l} (e) .

We now obtain from (b) of $(B_{5})$ , the statement (c)(i). The second relation in (c) can be proved dually.

(d) If $g_{1}^{'} = g_{1}$ , clearly, $g_{2} τ^{l} (e) \overset{r}{\approx} g_{1} τ^{l} (e)$ and $g_{2} τ^{r} (f) \overset{l}{\approx} g_{1} τ^{r} (f)$ . Conversely assume that $g_{2} τ^{l} (e) \overset{r}{\approx} g_{1} τ^{l} (e)$ . The fact that $g_{1}^{'} τ^{l} (e) \overset{r}{\approx} g_{1} τ^{l} (e)$ and $g_{1}^{'} \in ω (g_{1})$ together give $g_{1}^{'} τ^{l} (e) = g_{1} τ^{l} (e)$ . In other words $g_{1}^{'} \overset{l}{\approx} g_{1}$ and consequently $g_{1}^{'} = g_{1}$ .

If we assume that $g_{2} τ^{r} (f) \overset{l}{\approx} g_{1} τ^{r} (f)$ , we arrive at the same conclusion.

(e) If $h_{1}, h_{2} \in S (e, f)$

(h_{1} τ^{l} (e), h_{1} τ^{r} (f)) (\overset{r}{\approx} \times \overset{l}{\approx}) (h_{2} τ^{l} (e), h_{2} τ^{r} (f)) .

Thus $h_{1}$ and $h_{2}$ satisfy the hypothesis of $(B_{5})$ , and therefore there exist $h_{2}^{'}$ and $h_{2}^{''}$ in $E$ such that

h_{2} \overset{l}{\approx} h_{2}^{'} \overset{r}{\approx} h_{1}^{'} \overset{l}{\approx} h_{2}^{''} \overset{r}{\approx} h_{2},

where $h_{1}^{'} = h_{2}^{''} τ^{l} (h_{1})$ . By statement (c) of this lemma, we see that $h_{2}^{'}, h_{2}^{''} \in S (e, f)$ and since by (d), $h_{2} τ^{l} (e) \overset{r}{\approx} h_{1} τ^{l} (e), h_{1}^{'} = h$ ; which proves (e). □

Definition 2.2. A mapping $θ : E \to E^{'}$ of a biordered set $E$ into biordered set $E^{'}$ is a bimorphism if it satisfies the following axioms and their duals.

Let $e_{1}, e_{2} \in E$ and $e_{1} ω^{r} e_{2}$ . Then $e_{1} θ ω^{r} e_{2} θ$ and $(e_{1} τ^{r} (e_{2})) θ = e_{1} θ τ^{r} (e_{2} θ)$ .
$e_{1}, e_{2} \in E \Rightarrow S (e_{1}, e_{2}) θ \subseteq S (e_{1} θ, e_{2} θ)$ .

A bimorphism $θ$ of $E$ in to $E^{'}$ is a retraction (co-retraction) if it satisfies the following axiom.

There exists a bimorphism $θ^{'} : E^{'} \to E$ such that $θ^{'} \circ θ (θ \circ θ^{'})$ is identity on $E^{'} (E)$ .

$θ$ is an isomorphism if and only if $θ$ is both a retraction and a co-retraction. (The fact that $θ$ is an isomorphism of $E$ onto $E^{'}$ may be expressed by writing $θ : E \approx E^{'}$ .)

Identity map

I_{E}

E

is evidently an isomorphism. Also all retractions (co-retractions) are surjections (injections) and therefore isomorphisms are bijections. Axiom

(m_{3})

gives that if

θ

is a retraction (co-retraction), the bimorphism

θ^{'}

associated with

θ

is a co-retraction (retraction). If

θ

is a one-to-one retraction (onto co-retraction), we can see that

θ \circ θ^{'} = I_{E} (θ^{'} \circ θ = I_{E^{'}})

so that

θ^{'} = θ^{- 1}

. Hence in this case both

θ

and

θ^{- 1}

are isomorphisms and clearly this holds for all isomorphisms.

Thus

θ \circ θ^{'}

satisfy

(m_{1}) \cdot {(m_{1})}^{*}

is verified dually.

Now let

h \in S (e_{1}, e_{2})

. Thus by

(m_{2})

h θ \in S (e_{1} θ, e_{2} θ)

and

(h θ) θ^{'} \in S ((e_{1}, θ) θ^{'}, (e_{2}, θ) θ^{'})

. That is

(h) θ \circ θ^{'} \in S ((e_{1}) θ \circ θ^{'}, (e_{2}) θ \circ θ^{'})

. Thus

θ \circ θ^{'}

satisfies

(m_{2})

also.

Definition 2.3. Let $E$ be a biordered set and $E^{'} \subset E$ . Define

\begin{matrix} ω_{1}^{r} = ω^{r} \cap {(E^{'})}^{2}, ω_{1}^{l} = ω^{l} \cap {(E^{'})}^{2} and \\ τ_{1} = \{τ^{r} (e) | E^{'} | e \in E^{'}\} \cup {τ^{l} (e) | E^{'} | e \in E^{'}} . \end{matrix}

(2.9)

Then $(E^{'}, ω_{1}^{r}, ω_{1}^{l}, τ_{1})$ is a biordered subset of $E$ if the following conditions are satisfied.

$E^{'} = (E^{'}, ω_{1}^{r}, ω_{1}^{l}, τ_{1})$ is a bordered set.
If $e, f \in E^{'}$ and if $S_{1} (e, f)$ and $S (e, f)$ denote sandwich sets of $e$ and $f$ in $E^{'}$ and $E$ respectively, then
$S_{1} (e, f) \subseteq S (e, f) .$

Clearly

E

is a biordered subset of itself. Axiom (

{B S}_{1}

) implies in particular that for each

e \in E^{'}

τ^{r} (e) | E^{'}

and

τ^{l} (e) | E^{'}

are partial transformations of

E'

so that

and that

S_{1} (e, f) \neq \emptyset (e, f \in E^{'})

. Clearly

S_{1} (e, f) \subseteq E^{'}

. Hence by (

{B S}_{2}

S_{1} (e, f) \subseteq S (e, f) \cap E^{'}

. If

M_{1} (e, f)

and

M (e, f)

denote the sets defined by (2.4) for

E^{'}

and

E

respectively, then by (2.10),

M_{1} (e, f) \subseteq M (e, f)

. If

h \in S (e, f) \cap E^{'}, h τ^{l} (e)

and

h τ^{r} (f)

are members of

E^{'}

and therefore

Since

(h τ^{l} (e), h τ^{r} (f))

is universally maximal in

M (e, f)

it must be universally maximal in

M_{1} (e, f)

also. Thus

h \in S_{1} (e, f)

This, together with (2.5) (of axiom (

B_{4}

)), shows that for all

e_{1}, e_{2}

E^{'}

such that

e_{1}, e_{2} \in ω^{r} (e)

Lemma 2.8. Let $E^{'} \subseteq E$ , where $E$ is a biordered set. Let $ω_{1}^{r}$ and $ω_{1}^{l}$ be defined by (2.9) and let $τ_{1}$ be a family of partial transformations of $E^{'}$ such that $E^{'} = (E, ω_{1}^{r}, ω_{1}^{l}, τ_{1})$ is a biordered set. Then $E'$ is a biordered subset of $E$ if and only if the identity mapping $I_{E^{'}}$ of $E^{'}$ into $E$ is a bimorphism.

If $E^{'}$ is biordered subset of $E$ and if $θ : E \to E_{1}$ is a bimorphism, then $θ | E^{'}$ is bimorphism of $E^{'}$ into $E_{1}$ . Further, if $E^{''}$ is a biordered subset of $E^{'}$ it is also a biordered subset of $E$ .

Proof. Let $E^{'}$ be a biordered subset of $E$ . Then definitions of $ω_{1}^{r}$ , $ω_{1}^{l}$ , $τ_{1}$ and axiom $({B S}_{1})$ together imply that the mapping $I_{E^{'}}$ of $E^{'}$ into $E$ satisfies axiom $(m_{1})$ of Definition 2.2. Axiom ( ${B S}_{2}$ ) is the same as axiom $(m_{2})$ with $I_{E^{'}}$ in plane of $θ$ . Hence $I_{E^{'}}$ is a bimorphism.

On the other hand if $E^{'} = (E^{'}, ω_{1}^{r}, ω_{1}^{l}, τ_{1})$ is a biordered set such that $ω_{1}^{r}$ and $ω_{1}^{l}$ are quasi-orders defined by (2.9) and $I_{E^{'}}$ is a bimorphism, then axiom $(m_{1})$ shows that for every $f \in E^{'}$ , $e \in ω_{1}^{r} (f)$ and $e^{'} \in ω_{1}^{l} (f)$

e τ_{1}^{r} (f) = e τ^{r} (f) and e^{'} τ_{1}^{l} (f) = e^{'} τ^{l} (f) .

Hence $τ_{1}$ is the same as the family defined by (2.9) and as a consequence $E^{'}$ satisfies $({B S}_{1})$ . Statement $({B S}_{2})$ follows from axiom $(m_{2})$ . Therefore $E^{'}$ is a biordered subset of $E$ .

The remaining statements of Lemma 2.8 are consequences of the fact that if $θ_{1} : E_{1} \to E_{2}$ and $θ_{2} : E_{2} \to E_{3}$ are bimorphism, then $θ_{1} \circ θ_{2}$ is a bimorphism of $E_{1}$ into $E_{3}$ . □

Lemma 2.9. Let $E^{'}$ be a subset of a biordered set $E$ . Then $E^{'}$ is a biordered subset if and only if the following conditions and their duals are satisfied.

For every $e \in E^{'}$
$(E^{'} \cap ω^{r} (e)) τ^{r} (e) \subseteq E^{'} .$
$e_{1}, e_{2} \in E^{'} \Rightarrow S (e_{1}, e_{2}) \cap E^{'} \neq \emptyset$
$e \in E^{'}$ and $e_{1}, e_{2} \in ω^{r} (e) \cap E^{'}$ imply that $(S (e_{1}, e_{2}) \cap E^{'}) τ^{r} (e) = S (e_{1}, e_{2}) τ^{r} (e) \cap E^{'} .$

Proof. If $E^{'}$ is biordered subset, (a) and (c) are the same as (2.10) and (2.12). (b) follows from (2.11).

Now suppose $E^{'}$ satisfied (a), (b) and (c). Define $ω_{1}^{r}, ω_{1}^{l}$ and $τ_{1}$ by (2.9). Then by (a), $τ_{1}$ is a family of partial transformations of $E^{'}$ . The fact that $(E^{'}, ω_{1}^{r}, ω_{1}^{l}, τ_{1})$ are satisfied axioms $(B_{1})$ , $(B_{2})$ , $(B_{3})$ and their duals follows from the definitions of $ω_{1}^{r}, ω_{1}^{l}$ and $τ_{1}$ . For $e, f \in E^{'}$ , let $M (e, f)$ and $M_{1} (e, f)$ denote quasi-ordered sets (Definition 2.4) of $E$ and $E^{'}$ respectively. Then $M_{1} (e, f) \subseteq M (e, f)$ and by (b), at least one universally maximal member of $M (e, f)$ belongs to $M_{1} (e, f)$ . Since the quasi-order of $M_{1} (e, f)$ is the restriction of $ω^{r} \times ω^{l}$ to the subset $M_{1} (e, f)$ of $M (e, f)$ the set of universally maximal members of $M_{1} (e, f)$ is non-empty and these members are universally maximal in $M (e, f)$ also. Thus $(h τ_{1}^{l} (e), h τ_{1}^{r} (f))$ is universally maximal in $M_{1} (e, f)$ if and only if $h \in S (e, f) \cap E^{'} = S_{1} (e, f)$ . Now if $e \in E^{'}$ and $e_{1}, e_{2} \in ω_{1}^{r} (e)$ then $e_{1}, e_{2} \in ω^{r} (e) \cap E^{'}$ and therefore

\begin{array}{rcl} S_{1} (e_{1}, e_{2}) τ_{1}^{r} (e) & = & (S (e_{1}, e_{2}) \cap E^{'}) τ^{r} (e) \\ = & S (e_{1}, e_{2}) τ^{r} (e) \cap E^{'} \\ = & S (e_{1} τ^{r} (e), e_{2} τ^{r} (e)) \cap E^{'} \\ = & S_{1} (e_{1} τ_{1}^{r} (e), e_{2} τ_{1}^{r} (e)) . \end{array}

□

Dual statement of (2.5) can be verified similarly. Hence

E^{'}

satisfies axioms

(B_{4})

and

{(B_{4})}^{*}

. To assert that

E^{'}

satisfies

({B S}_{1})

, we have to show that

E^{'}

satisfies axioms

(B_{5})

also. Let

g_{1}, g_{2} \in ω_{1}^{r} (e) \cap ω_{1}^{r} (f)

where

e, f \in E^{'}

and

Then

g_{1}

and

g_{2}

satisfy this condition in

E

also and therefore by

(B_{5})

there exist

g_{2}^{'}

and

g_{2}^{''}

E

satisfying (a), (b) and (c) of

(B_{5})

. Now it is enough to establish that

g_{2}^{'}, g_{2}^{''} \in E^{'}

Since

g_{1}, g_{2} \in E^{'}

S_{1} (g_{2}, g_{1}) \neq \emptyset

. Choose

h \in S_{1} (g_{2}, g_{1})

and suppose that

h_{1} = h τ^{r} (g_{1}) = h τ^{r} (g_{1})

. Then by (a),

h_{1} \in E^{'}

and as a consequence of Lemmass 2.5 and 2.6,

Hence

h, g_{2}^{'} \in S (g_{2}, g_{1})

and therefore

h_{1} \overset{l}{\approx} g_{2}^{'} τ^{r} (g_{1}) = g_{1}^{'}

. By Lemma 2.7(a)

g_{1}^{'} = g_{2}^{''} τ^{l} (g_{1})

and we can prove similarly that there exists

h_{2} \in E^{'}

such that

h_{2} \overset{r}{\approx} g_{1}^{'}

. But since

h_{1}, h_{2} \in E^{'}

, statement (b) implies that

and consequently

g' \in E^{'}

. Thus

g_{2}, g_{1}^{'} \in E^{'}

and

S_{1} (g_{2}, g_{1}^{'}) = S (g_{2}, g_{1}^{'}) \cap E^{'} = {g_{2}^{'}} \cap E^{'} \neq \emptyset

. This leads to the conclusion that

g_{2}^{'} \in E^{'}

. Dually we can show that

g_{2}^{''} \in E^{'}

. Thus we observe that

(E^{'}, ω_{1}^{r}, ω_{1}^{l}, τ_{1})

is a biordered set and that it satisfies

({B S}_{1})

. For

e, f \in E^{'}

S_{1} (e, f) = S (e, f) \cap E^{'}

is the sandwich set of

e

and

f

E^{'}

and therefore

({B S}_{2})

is also satisfied.

Proof. Given $e \in E$ , for all $g \in ω^{r} (e)$ , $ω^{r} (g) \subseteq ω^{r} (e)$ . Further given $g, g^{'} \in ω^{r} (e)$ , if $g^{'} ω^{l} g$ , then $g^{'} τ^{l} (g) ω g ω^{r} e$ . Hence condition (a) of Lemma 2.9 is satisfied. If $g_{1}, g_{2} \in ω^{r} (e)$ and $h \in S (g_{1}, g_{2})$ then $h ω^{r} g_{2}$ and consequently $h \in ω^{r} (g_{2}) \subseteq ω^{r} (e)$ . Thus $S (g_{1}, g_{2}) \subseteq ω^{r} (e)$ . Hence $ω^{r} (e)$ satisfies (b) of Lemma 2.9 also. Statement (c) is obvious, since for $g_{1}, g_{2} \in ω^{r} (g) \cap ω^{r} (e)$ where $g \in ω^{r} (e)$ , $S (g_{1}, g_{2}) \subseteq ω^{r} (g) \subseteq ω^{r} (e)$ . This proves that $ω^{r} (e)$ is a biordered subset. □

Similarly using Lemma 2.9 we can prove that

ω^{l} (e)

and

ω (e)

are also biordered subsets of

E

Proof. Let $e \in E$ . Then axioms $(B_{1})$ and $(B_{2})$ show that $τ^{r} (e)$ preserves $ω^{r}$ and $ω^{l}$ . Let $e, ω^{r} e_{2} ω^{r} e$ . Then $e_{1} ω^{r} e_{2} τ^{r} (e) ω e$ and hence by $(B_{2})$ .

\begin{array}{rcl} (e_{1} τ^{r} (e)) τ^{r} (e_{2} τ^{r} (e)) & = & e_{1} τ^{r} (e_{2} τ^{r} (e)) \\ = & (e_{1} τ^{r} (e_{2})) τ^{r} (e_{2} τ^{r} (e)) . & (2.14) \end{array}

Also $e_{1} τ^{r} (e) \overset{r}{\approx} e_{1} \overset{r}{\approx} e_{1} τ^{r} (e_{2}) ω e_{2} \overset{r}{\approx} e_{2} τ^{r} (e)$ and therefore $(e_{1} τ^{r} (e_{2})) τ^{r} (e) ω e_{2} τ^{r} (e)$ . Hence by axiom $(B_{2})$ we get

\begin{array}{rcl} (e_{1} τ^{r} (e_{2})) τ^{r} (e_{2} τ^{r} (e)) & = & ((e_{1} τ^{r} (e_{2})) τ^{r} (e)) τ^{r} (e_{2} τ^{r} (e)) \\ = & (e_{1} τ^{r} (e_{2})) τ^{r} (e) . & (2.15) \end{array}

From (2.14) and (2.15) we get

(e_{1} τ^{r} (e_{2})) τ^{r} (e) = (e_{1} τ^{r} (e)) τ^{r} (e_{2} τ^{r} (e)),

and hence $τ^{r} (e)$ satisfies axiom $(m_{1})$ of Definition 2.2. Axiom ${(m_{1})}^{*}$ follows from axiom $(B_{3})$ and axiom $(m_{2})$ follows from (2.5).

If $e^{'} \overset{r}{\approx} e$ , it can be similarly proved that $τ^{r} (e, e^{'})$ is a bimoprhism of $ω (e)$ into $ω (e^{'})$ and $τ^{r} (e^{'}, e)$ is a bimorphism of $ω (e^{'})$ into $ω (e)$ . But for $e^{''} \in ω (e)$ by axiom $(B_{2})$ ,

(e^{''}) τ^{r} (e, e^{'}) \circ τ^{r} (e^{'}, e) = (e^{''} τ^{r} (e^{'})) τ^{r} (e) = e^{''},

and similarly we can prove that

τ^{r} (e^{'}, e) \circ τ^{r} (e, e^{'}) = I_{ω (e^{'})} .

Hence by the definition of isomorphism, $τ^{r} (e, e^{'})$ is an isomorphism of $ω (e)$ onto $ω (e^{'})$ . □

NOTE. clearly

τ^{r} (e, e)

is identity map

I_{ω (e)}

. Also we get by axiom

(B_{2})

that for all

e \overset{r}{\approx} e^{'} \overset{r}{\approx} e^{''}

Dually

τ^{l} (e, e)

is also

I_{ω (e)}

and the two symbols

τ^{r} (e, e)

and

τ^{l} (e, e)

may be used according to convenience.

Remark 2.12: We have already observed that (Remark 2.2) the concept of a biordered set is a generalisation of the concept of a semilattice. It can be verified without difficulty that a subset $E^{'}$ of a semilattice $E$ is a subsemilattice of $E$ if and only if it is a biordered subset of $E$ . Further a mapping $θ$ of semilattice $E_{1}$ into semilattice $E_{2}$ is a homomorphism of $E_{1}$ into $E_{2}$ (i.e. a mapping such that $(e_{1}, e_{2}) θ = e_{1} θ \cdot e_{2} θ$ for all $e_{1}, e_{2} \in E_{1}$ ) if and only if it is a bimorphism of $E_{1}$ into $E_{2}$ .

Chapter 2Biordered Sets and Bimorphisms

Chapter 2
Biordered Sets and Bimorphisms