3 Partially Transitive Set of Partial ω-isomorphisms

Chapter 3
Partially Transitive Set of Partial $ω$ -isomorphisms

Let $E$ be a biordered set and let

δ_{0} = {(\overset{r}{\approx} \cup \overset{l}{\approx})}^{t}

(3.1)

where ${(\overset{r}{\approx} \cup \overset{l}{\approx})}^{t}$ denotes the transitive closure of $\overset{r}{\approx} \cup \overset{l}{\approx}$ . Since $\overset{r}{\approx}$ and $\overset{l}{\approx}$ are equivalence relations, so is $δ_{0}$ . By the definition of transitive closure, (cf. [2], p. 14), $(e, f) \in δ_{0}$ if and only if there exists a finite ordered subset $(e_{0}, e_{1}, \dots, e_{n})$ of $E$ such that $e_{0} = e, e_{n} = f$ and either $e_{i} \overset{r}{\approx} e_{i + 1}$ or $e_{i} \overset{l}{\approx} e_{i + 1}$ for $i = 0, 1, \dots, n - 1$ . A subset $c$ of $E$ satisfying this property will be called a $δ_{0}$ -chain connecting $e$ and $f$ (or $e_{0}$ and $e_{n}$ ). If $c = (e_{0} \dots e_{n})$ is a $δ_{0}$ -chain, then $c^{- 1} = (e_{n}, e_{n - 1}, \dots, e_{0})$ is also a $δ_{0}$ -chain, which will be called the inverse of $c$ . Further if $c_{1} = (e_{0}, \dots, e_{n})$ and $c_{2} = (e_{0}^{'}, \dots, e_{m}^{'})$ are $δ_{0}$ -chains and if $e_{n} = e_{0}^{'}$ then $c^{1} = (e_{0}, \dots, e_{n}, e_{1}^{'}, \dots e_{m}^{'})$ is also a $δ_{0}$ -chain. $c^{'}$ will be called the composite of $c_{1}$ and $c_{2}$ ; and $c_{1}$ and $c_{2}$ the factors of $c^{'}$ . We may denote $c^{'}$ by $c_{1} \cdot c_{2}$ . Given two arbitrary $δ_{0}$ -chains $c_{1}$ and $c_{2}$ their composite $c_{1} \cdot c_{2}$ is defined if and only if the extremity of $c_{1}$ (the last member of the ordered set $c_{1}$ ) is the same as the origin of $c_{2}$ (the first member of $c_{2}$ ). This definition of composite can be extended to more than two $δ_{0}$ -chains and this operation is associative whenever it is defined.

By the definitions of $δ_{0}$ -chain, it is clear that $(e, f)$ is a $δ_{0}$ -chain whenever $e \overset{r}{\approx} f$ or $e \overset{l}{\approx} f$ . We call the chain $(e, f)$ an elementary chain. If $e = f$ . $(e, f)$ is trivially a chain. If $c = (e_{0}, e_{1}, \dots, e_{n})$ is a $δ_{0}$ -chain, then $(e_{i}, e_{i + 1})$ is an elementary chain for every $i$ such that $i = 0, 1, \dots, n - 1$ and $(e_{1}, e_{i + 1})$ is a factor of $c$ . Thus we have

c = (e_{0}, e_{1}) \cdot (e_{1}, e_{2}) \dots (e_{n - 1}, e_{n}) .

(3.2)

Also if $c_{1}$ and $c_{2}$ are $δ_{0}$ -chains such that $c_{1} \cdot c_{2}$ is defined, then $c_{2}^{- 1} \cdot c_{1}^{- 1}$ is also defined and

{(c_{1} \cdot c_{2})}^{- 1} = c_{2}^{- 1} \cdot c_{1}^{- 1} .

(3.3)

If $(e, f)$ is an elementary $δ_{0}$ -chain, define

ϵ (e, f) = \{\begin{matrix} I_{ω (e)} & if e = f \\ τ^{r} (e, f) & if e \overset{r}{\approx} f \\ τ^{l} (e, f) & if e \overset{l}{\approx} f . \end{matrix}

(3.4)

We call $ϵ (e, f)$ the elementary transformation associated with the elementary chain $(e, f)$ . If $c = (e_{0}, \dots, e_{n})$ is any $δ_{0}$ -chain, the chain transformation associated with $c$ is defined by

ϵ (c) = ϵ (e_{0}, e_{1}) \circ ϵ (e_{1}, e_{2}) \circ \dots \circ ϵ (e_{n - 1}, e_{n}) .

(3.5)

Thus

ϵ (c_{1} \cdot c_{2}) = ϵ (c_{1}) \circ ϵ (c_{2})

(3.6)

whenver $c_{1} \cdot c_{2}$ is meanigful.

By (Theorems Remark 2.11 and Remark 2.11*) it is clear that if $c$ is a $δ_{0}$ -chain connecting $e_{0}$ to $e_{n}$ , then $ϵ (c)$ is an isomorphism of the biordered subset $ω (e_{0})$ onto $ω (e_{n})$ . Also if $(e, f)$ is an elementary chain, the transformation $ϵ (f, e)$ is the inverse of $ϵ (e, f)$ (and vice versa) and consequently

ϵ (c^{- 1}) = {(ϵ (c))}^{- 1} .

(3.7)

Let $c = (e_{0}, \dots, e_{n})$ be a $δ_{0}$ -chain. Then for $h ω^{r} e_{0}$ we define a $δ_{0}$ -chain $h c$ by

h c = (h, e_{0}^{'}, e_{1}^{'}, \dots, e_{n}^{'})

(3.8)

where $e_{0}^{'} = h τ^{r} (e_{0})$ and $e_{i}^{'} = e_{i - 1}^{'} ϵ (e_{i - 1}, e_{i}), i = 1, 2, \dots, n$ .

By axiom $(B_{1})$ , $e_{0}^{'} \overset{r}{\approx} h$ and by $(β_{1})$ and ${(β_{1})}^{*}$ , $e_{i - 1}^{'} \overset{r}{\approx} e_{i}^{'}$ or $e_{i - 1}^{'} \overset{l}{\approx} e_{i}^{'}$ according as $e_{i - 1} \overset{r}{\approx} e_{i}$ or $e_{i - 1} \overset{l}{\approx} e_{i}$ . Therefore $h c$ is a $δ_{0}$ -chain and the factor $(e_{i - 1}^{'}, e_{i}^{'})$ of $h c$ is either trivial or of the same type as $(e_{i - 1}, e_{i})$ . If $c_{1} = (e_{0}, \dots, e_{i}), i = 1, 2, \dots, n$ then it follows by induction that

e_{i}^{'} = e_{0}^{'} ϵ (c_{i}) and e_{i}^{'} ω e_{i}^{'} .

Similarly if $k ω^{l} e_{n}$ , we define the $δ_{0}$ -chain $c k$ by

c k = (e_{0}^{''}, \dots, e_{n}^{''}, k)

(3.9)

where $e_{n}^{''} = k τ^{l} (e_{n})$ and for $i = 1, 2, \dots n, e_{n - i}^{''} = e_{n - i + 1}^{''} = ϵ (e_{n - i + 1}, e_{n - i})$ .

As before it can be shown that $c k$ is a $δ_{0}$ -chain in which $e_{i}^{''} ω e_{i}$ such that the factor $(e_{i - 1}^{''}, e_{i}^{''})$ is either trivial or of the same type as $(e_{i - 1}, e_{i})$ . Since $e_{n}^{''} ω e_{n}$ we can define $e_{n}^{''} c^{- 1}$ by (3.8) and then $e_{n}^{''} c^{- 1} = (e_{n}^{''}, e_{n - 1}^{''}, \dots e_{0}^{''})$ . Therefore

c k = {((k, e_{n}^{''}) \cdot e_{n} c^{- 1})}^{- 1}

(3.10)

and $h c$ may be expressed in terms of chains of the form $c k$ in a similar way.

Lemma 3.1. Let $c = (e_{0}, \dots, e_{n})$ be a $δ_{0}$ -chain in $E$ . Then if $h ω^{r} e_{0}$ and $k ω^{l} e_{n}$ , we have

ϵ (h c) = τ^{r} (h, e_{0}^{'}) \circ ϵ (c) and ϵ (c k) = ϵ (c) \circ T^{l} (e_{n}, k) .

(3.11)

Proof. Let $f \in ω (h)$ and $f_{0} = f τ^{r} (h, e_{0}) = f τ^{r} (e_{0}) .$ Then by (3.5) and (3.8)

f ϵ (h c) = (f_{0}) ϵ (e_{0}^{'}, e_{1}^{'}), \circ \dots \circ ϵ (e_{n - 1}^{'}, e_{n}^{'}) .

Now if $e_{0} \overset{r}{\approx} e_{1}$ , then $e_{0}^{'} \overset{r}{\approx} e_{1}^{'}$ and by Theorem 2.11,

\begin{array}{rcl} (f_{0}) ϵ (e_{0}^{'}, e_{1}^{'}) & = & (f_{0}) τ^{r} (e_{1}^{'}) \\ = & ((f_{0}) τ^{r} (e_{1})) τ^{r} (e_{0}^{'} τ^{r} (e_{1})) \\ = & ((f_{0}) τ^{r} (e_{0}^{'})) τ^{r} (e_{1}) = (f_{0}) τ^{r} (e_{0}, e_{1}) . \end{array}

If $e_{0} \overset{l}{\approx} e_{1}$ , then $(f_{0}) ϵ (e_{0}^{'}, e_{1}^{'}) = f_{0} τ (e_{0}, e_{1})$ and therefore in either case

f_{0} ϵ (e_{0}^{'}, e_{1}^{'}) = f_{0} ϵ (e_{0}, e_{1}) .

Inductively,

\begin{matrix} (f_{0}) ϵ (e_{0}^{'}, e_{1}^{'}) \circ ϵ (e_{1}^{'}, e_{2}^{'}), \dots, ϵ (e_{i - 1}^{'}, e_{1}^{'}) = (f_{0}) ϵ (e_{0}, e_{1}) \circ \dots \circ ϵ (e_{i - 1}, e_{i}) . \end{matrix}

Hence

\begin{array}{rcl} (f) ϵ (h c) & = & (f_{0}) ϵ (e_{0}, e_{1}) \circ ϵ (e_{1}, e_{2}) \circ \dots \circ ϵ (e_{n - 1}, e_{n}) \\ = & (f_{0}) ϵ (c) \\ = & (f) τ^{r} (h, e_{0}) \circ ϵ (c) . \end{array}

This proves the first equality in (3.11). The second can be proved similarly or may be deduced from the first using (3.3), (3.6), (3.7) and (3.10). □

Corollary 3.2. Let $c$ be a $δ_{0}$ -chain in $E$ and $h ω e_{0} (k ω e_{n})$ . Then $ϵ (h c) (ϵ (c k))$ is the domain resriction of $ϵ (c)$ (range restriction of $ϵ (c)$ ) to $ω (h) (ω (k))$

Proof. Since $h ω e_{0}$ , $e_{0}^{'} = h τ^{r} (e_{0}) = h$ and it follows that $τ^{r} (h, e_{0}^{'}) = τ^{r} (h, h)$ . Clearly $τ^{r} (h, h) \circ ϵ (c)$ is the domain restriction of $ϵ (c)$ to $ω (h)$ . The bracketed statement can be proved dually. □

Theorem 3.3. Let $E$ be a biordered set and let $Ẽ_{0}$ denote the set of all chain transformations of $E$ . Then we have the following.

Each $ϵ \in Ẽ_{0}$ is a partial isomorphism.
If $ϵ \in Ẽ_{0}$ then $ϵ^{- 1} \in Ẽ_{0}$
Let $ϵ, ϵ^{'} \in Ẽ_{0}$ , $r a n g e (ϵ) = ω (e)$ and $d o m (ϵ^{'}) = ω (f)$ . Then if either $e ω f$ or $f ω e$ , $ϵ \circ ϵ^{'} \in Ẽ_{0}$
For $e, f \in E, e δ_{0} f$ if and only if there exists $ϵ \in Ẽ_{0}$ such that $d o m (ϵ) = ω (e)$ and $r a n g e (ϵ) = ω (f)$ .

Proof. Statements (a) and (b) follow from the definition of chain transformation and Theorem 2.11. Statement (d) follows from (a) and the definition of $δ_{0}$ .

To prove (c) let $ϵ, ϵ^{'} \in Ẽ_{0}$ . Then there exist $δ_{0}$ -chains $c_{1}$ and $c_{2}$ such that

ϵ = ϵ (c_{1}) and ϵ^{'} = ϵ (c_{2}) .

Let range $(ϵ) = ω (e)$ and $d o m (ϵ^{'}) = ω (f)$ . Then $e$ is the extremity of $c_{1}$ and $f$ is the origin of $c_{2}$ . If $e ω f$ by Lemma 3.1 we have,

\begin{array}{rcl} ϵ \circ ϵ^{'} & = & ϵ \circ (T^{l} (e, e) \circ ϵ^{'}) \\ = & ϵ (c_{1}) \circ (τ^{l} (e, e) \circ ϵ (c_{2})) \\ = & ϵ (c_{1}) \circ ϵ (e c_{2}) \end{array}

where $e c_{2}$ is defined by (3.8). Now $c_{1} \cdot e c_{2}$ is defined according to the definition of compositions of $δ_{0}$ -chains and hence by (3.6)

ϵ \circ ϵ^{'} = ϵ (c \cdot e c_{2}) .

Thus $ϵ \circ ϵ^{'} \in Ẽ_{0}$ . When $f ω e$ we can similarly prove that $ϵ \circ ϵ^{'} \in Ẽ_{0}$ .□

An isomorphism of $ω$ -ideals $ω (e)$ and $ω (f)$ of a biordered set $E$ wiil be called a partial $ω$ -isomorphism (or $ω$ -isomorphism when no confusion is likely) of $E$ . If $α$ is an $ω$ -isomorphism of $E$ we define $e_{α}$ anf $f_{α}$ respectively by

d o m α = ω (e_{α}), r a n g e α = ω (f_{α}) .

(3.12)

We also denote by $Ẽ_{1}$ the set of all $ω$ -isomorphisms of $E$ . Clearly every chain transformation is an $ω$ -isomorphisms.

Hence

Ẽ_{0} \subseteq Ẽ_{1} .

Also, if $α \in Ẽ_{1}$ , and if $g \in ω (e_{α})$ , it is clear that

α | w (g) = τ^{r} (g, g) \circ α

is also an $ω$ -isomorphism. Similarly if $g^{'} \in ω (f_{α})$ . the range restriction of $α$ to $ω (g^{'})$ (which is $α \circ τ^{l} (g^{'}, g^{'})$ ) is an $ω$ -isomorphism. Hence if $α, β \in Ẽ_{1}$ and if $f_{α} ω e_{β}$ (or $e_{β} ω f_{α}$ ) then

\begin{matrix} α \circ β = α \circ (τ^{r} (f_{α}, f_{α}) \circ β) \in Ẽ_{1} \\ (α \circ β = (α \circ τ^{l} (e_{β}, e_{β})) \circ β \in Ẽ_{1}) . \end{matrix}

Definition 3.1. Let $E$ be a biordered set and $T \subseteq Ẽ_{1}$ . Then $T$ will be called a partially transitive set of $ω$ -isomorphisms of $E$ (or a partially transitive set on $E$ ) if and only if $T$ satisfies the following axioms.

$Ẽ_{0} \subseteq T$
$α \in T \Rightarrow α^{- 1} \in T$
If $α, β \in T$ and if either $f_{α} ω e_{β}$ or $e_{β} w f_{α}$ then $α \circ β \in T$ .

If $T$ is a partially transitive set on $E$ , then we call the relation

\begin{array}{rcl} δ (T) = {(e, f) \in E^{2} ∕ e_{α} = e and f_{α} = f for some α \in T} & (3.13) \end{array}

the transitivity relation of $T$ , $T$ a transitive set on $E$ if $δ (T) = E^{2}$ and $E$ a uniform biordered set if there exists a transitive set on $E$ . A relation $δ$ on $E$ is said to be regular if there exists a partially transitive set $T$ on $E$ such that $δ (T) = δ$ .

Associated with a biordered set $E$ , we have the following sets.

\begin{array}{rcl} P T (E) & = & {T | T is a partially transitive set on E} & (3.14) \\ R_{e} (E) & = & {δ : for some T \in P T (E), δ (T) = δ} & (3.15) \\ T (E, δ) & = & {α \in Ẽ_{1} | α \subseteq δ} & (3.16) \\ P T (E, δ) & = & {T \in P T (E) | δ (T) = δ} & (3.17) \end{array}

where $δ$ is a given relation on $E$ . These sets are ordered by inclusion.

Theorem 3.3 and the discussion preceding Definition 3.1 give,

Ẽ_{0}, Ẽ_{1} \in P T (E) .

(3.18)

By Theorem 3.3, $δ_{0} = δ (Ẽ_{0})$ and if

δ_{1} = δ (Ẽ_{1})

we have

δ_{0}, δ_{1} \in R_{e} (E) .

(3.19)

Lemma 3.4. Let $E$ be a biordered set. Then we have the following.

$P T (E)$ is a partially ordered set containing a greatest and a least member that is,
$T \in P T (E) \Rightarrow Ẽ_{0} \subseteq T \subseteq Ẽ_{1} .$
$T \in P T (E) \Rightarrow T \subseteq T (E, δ (T))$
For δ ∈ Re(E).
1. $δ$ is an equivalence relation
2. $δ_{0} \subseteq δ$ .
3. $(e, f) \in δ$ if and only if for some $α \in \tilde{E_{1}}$ , $e_{α} = e, f_{α} = f$ and $α \subseteq δ$ .
Conversely if $δ$ is a relation on $E$ satisfying (c1), (c2), and (c3), then
$T (E, δ) \in P T (E) and δ (T (E, δ)) = δ .$ (3.20)

The mapping

δ : T \mapsto δ (T)

is an order preserving mapping of $P T (E)$ onto $R_{e} (E)$ .

Proof. Statement (a) follows from definition (3.1) and (3.18).

Let $α \in T$ . In order to obtain (b), by (3.16), it is enough to prove that $α \subseteq δ (T)$ . Let $(g, h) \in α$ so that $g α = h$ . Then by $(T_{1})$ , $τ^{r} (g, g) \in T$ and since $g \in ω (e_{α})$ by $(T_{3})$ , $τ^{r} (g, g) \circ α \in T$ . But if $α^{'} = τ^{r} (g, g) \circ α$ , then $e_{α^{'}} = g$ and $f_{α^{'}} = (g) α' = g α = h$ . Hence $(g, h) \in δ (T)$ .

To prove (c) suppose that $δ \in R_{e} (E)$ . Then there exists $T \in P T (E)$ such that $δ (T) = δ$ . For every $e \in E, τ^{r} (e, e) \in \tilde{E_{0}} \subseteq T$ by $(T_{1})$ and hence by (3.13). $δ$ is reflexive. Axiom $(T_{2})$ implies that $δ$ is symmetric and the transitivity of $δ$ follows from $(T_{3})$ . Thus (c1) is obtained. Results (c2) and (c3) follow from (a), (b) and (3.13).

Now suppose that $δ$ satisfies (c1), (c2) and (c3). Then if $ϵ \in \tilde{E_{0}}$ , by (b) and (c2), $ϵ \subseteq δ_{0} \subseteq δ$ so that by (3.16) $ϵ \in T (E, δ)$ . Hence $T (E, δ)$ satisfies $(T_{1})$ . If $α \in T (E, δ), α \subseteq δ$ and hence $α^{- 1} \subseteq δ^{- 1} = δ$ (since $δ$ is an equivalence relation). Similarly if $α, β \in T (E, δ)$ and $f_{α} ω e_{β}$ (or $e_{β} ω f_{α}$ ) then $τ^{r} (f_{α}, f_{α}) \circ β \subseteq δ (α_{0} τ^{l} (e_{β}, e_{β}) \subseteq δ)$ . Therefore

\begin{array}{rcl} α \circ β & = & α \circ (τ^{r} (f_{α}, f_{α}) \circ β) \subseteq δ \circ δ = δ, \\ α \circ β & = & (α \circ (τ^{l} (e_{β}, e_{β})) \circ β \subseteq δ \circ δ = δ) . \end{array}

Hence $T (E, δ) \in P T (E)$ . Now suppose that $(e, f) \in δ$ . Then by (c3) there exists $α \in Ẽ$ , such that $e_{α} = e, f_{α} = f$ and $α \subseteq δ$ . Then by (3.16), $α \in T (E, δ)$ . Hence $(e, f) \in δ (T (E, δ))$ by (3.13). On the other hand if $(e, f) \in δ (T (E, δ))$ , there exists $α \in T (E, δ)$ such that $e_{α} = e, f_{α} = f$ . Then from the fact that $α \subseteq δ$ we get $(e, f) \in δ$ . Hence $δ (T (E, δ)) = δ$ . The statement (d) is evident from (3.13) and the definition of regular relations. □

Let $M \subseteq P T (E)$ . Define

\land M = \cap {T | T \in M}, \lor M = \cap {T | T^{'} \in M \Rightarrow T^{'} \subseteq T} .

(3.21)

Similarly define $\land$ and $\lor$ on $R_{e} (E)$ as follows. If $D \subseteq R_{e} (E)$

\begin{matrix} \land D & = & {[\cup {δ \in R_{e} (E) ∣ δ^{'} \in D \Rightarrow δ \subseteq δ^{'}}]}^{t}, \\ \lor D & = & {[\cup {δ ∣ δ \in D}]}^{t} . \end{matrix}

(3.22)

Theorem 3.5. Let $E$ be a biordered set. Then the sets $P T (E)$ and $R_{e} (E)$ are complete lattices under lattice operations defined by (3.21) and (3.22) respectively.

Proof. Let $M$ be an arbitrary subset of $P T (E)$ . Then, if

T_{M} = \cap {T | T \in M}

it can be seen that $T_{M} \in P T (E)$ and it is also the greatest partially transitive set contained in every member of $M$ . Consequently $T_{M}$ is the lattice product of $M$ in $P T (E)$ . Also for any subset $M$ of $P T (E)$ ,

Ẽ_{1} \in {T | T^{'} \in M \Rightarrow T^{'} \subseteq T}

so that this latter subset of $P T (E)$ is not empty and its lattice product is the lattice sum of $M$ . Thus $P T (E)$ is a complete lattice.

To prove that $R_{e} (E)$ is a complete lattice we first show that for any $D \subseteq R_{e} (E)$

δ_{D} = {[{δ ∣ δ \in D}]}^{t} \in R_{e} (E) .

Evidently $δ_{D}$ satisfies (c1) and (c2) of Lemma 3.4. Suppose that $(e, f) \in δ_{D}$ . Then there exists a finite subset ${δ_{i} ∣ i = 1, 2, \dots, n}$ of $D$ and ${e_{i} ∣ i = 0, 1, \dots, n}$ of $E$ such that $e_{0} = e, e_{n} = f$ and $e_{i - 1} δ_{i} e_{i}, i = 1, 2, \dots, n$ . Then by (c3), there exists $α_{i} \in \bar{E_{1}}$ such that $e_{α i} = e_{i - 1} f_{α i} = e_{i}$ and $α_{i} \subseteq δ_{i} \subseteq δ_{D}$ . Then

α = α_{1} \circ α_{2} \circ \dots \circ α_{n} \subseteq δ_{D}^{n} = δ_{D^{'}}

$e_{α} = e$ and $f_{α} = f$ . Hence $δ_{D}$ satisfies (c3) also. Thus $δ_{D} \in R_{e} (E)$ . Since $δ_{D}$ is the lattice sum in the lattice of all equivalence relations on $E$ , it is the lattice sum in $R_{e} (E)$ . Then as before it can be shown that $\land D$ exists and is in $R_{e} (E)$ . Hence $R_{e} (E)$ is also a complete lattice. □

Theorem 3.6. Let $E$ be a biordered set. Then

δ : T \to δ (T) and T : δ \to T (E, δ)

are order preserving and join preserving, and order preserving and meet preserving mappings of $P T (E)$ onto $R_{e} (E)$ and $R_{e} (E)$ into $P T (E)$ respectively such that

T \circ δ = I_{R_{e} (E)} .

Proof. We have already proved that $δ$ is an order preserving mapping of $P T (E)$ onto $R_{e} (E)$ and by (3.16), it is clear that $T$ is an order preserving mapping of $R_{e} (E)$ into $P T (E)$ . The equality $T \circ δ = J_{R_{e} (E)}$ follows from the fact that $δ (T (E, δ)) = δ$ for every $δ \in R_{e} (E)$ . Hence it remains to prove that $δ$ is join preserving and $T$ is meet preserving. Therefore if $M \subseteq P T (E)$ and $D \subseteq R_{e} (E)$ we need show that

δ (\lor M) = \lor δ (M) and \land T (D) = T (E, \land D)

(3.23)

where $δ (M) = {δ (T) | T \in M}$ and $T (D) = {T (E, δ) ∣ δ \in R_{e} (E)}$ .

For convenience, we call a finite ordered subset $c = (α_{1}, \dots, α_{n})$ of $\tilde{E_{1}}$ , a composable chain if $f_{α i} = e_{α i + 1}$ for all $i = 1, 2, \dots, n - 1$ . Every singleton set can also be regarded as a composable chain (in this case the condition stated above is satisfied vacuously). If $c = (α_{1}, \dots, α_{n})$ is any composable chain, we call

α (c) = α_{1} \circ \dots \circ α_{n}

the composite of $c$ and if $c$ is a singleton, the composite of $c$ is the unique element of $c$ . Let

\cup M = \cup {T ∣ T \in M}

and

\bar{M} = \{α (c) ∣ c is a composable chain in \cup M\} .

(3.24)

Then if $α \in \bar{M}$ , there exists a composable chain $c$ such that $α (c) = α$ . If $c = (α_{1}, \dots, α_{n})$ is a composable chain in $U M$ and if

c^{- 1} = (α_{n}^{- 1}, α_{n - 1}^{- 1}, \dots, α_{1}^{- 1})

it is clear that $c^{- 1}$ is also a composable chain in $\cup M$ and that

α (c^{- 1}) = {(α (c))}^{- 1} .

Hence $\bar{M}$ satisfies axiom $(T_{2})$ of definition (3.1). Since $\tilde{E_{0}} \subseteq \cup M \subseteq \bar{M}$ , it satisfies $(T_{1})$ also.

Now let $c = (α_{0}, α_{1}, \dots, α_{n})$ be a composable chain in $\cup M$ . Then

e_{α (c)} = e_{α_{0}} and f_{α (c)} = f_{α_{n}} .

For $e^{'} \in ω (e_{α_{0}})$ , define

\begin{array}{rcl} e'_{0} & = & e' \\ e'_{i} & = & (e'_{i - 1}) α_{i - 1}, i = 1, 2, \dots, n \end{array}

and

α'_{i} = τ^{n} (e'_{i}, e'_{i}) \circ α_{i}, i = 0, 1, \dots, n .

Then for $i = 1, 2, \dots, n, f_{α^{'} i - 1} = e_{i}^{'} = e_{α^{'} i}$ , and hence $c^{'} = (α_{0}^{'}, \dots, α_{n}^{'})$ is also a composable chain in $\cup M$ . Further

α (c^{'}) = τ^{r} (e^{'}, e^{'}) \circ α (c) = α (c) ∣ ω (e^{'}) .

Thus the domain restriction of the composite of a chain is again the composite of another chain. Similarly we can show that the range restriction of the composite of a chain is again the composite of a chain. These results are trivial when $c$ is a singleton.

If $c_{1} = (α_{0}, α_{1}, \dots, α_{n})$ , $c_{2} = (α_{0}^{'}, \dots, α_{m}^{'})$ are composable chains, and if $f_{α_{n}} = e_{α_{0}}^{'}$ then

c_{1} \cdot c_{2} = (α_{0}, \dots, α_{n}, α_{0}^{'}, \dots, α_{m}^{'})

is evidently a composable chain and

α (c_{1} \cdot c_{2}) = α (c_{1}) \circ α (c_{2}) .

Hence if $α (c_{1}) \circ α (c_{2}) \in \bar{M}$ and if $f_{α (c_{1})} ω e_{α (c_{2})}$ then

α (c_{1}) \circ α (c_{2}) = α (c_{1}) \circ τ^{r} (f_{α (c)}, f_{α (c_{1})}) \circ α (c_{2}) \in \bar{M} .

In the case when $e_{α (c_{2}^{'})} ω f_{α} (c_{1})$ , we see by similar arguments that $α (c_{1}) \circ α (c_{2}) \in \bar{M}$ . Thus $\bar{M}$ satisfies $(T_{3})$ also and $\bar{M} \in P T (E)$ .

Since $\cup M \subseteq \bar{M}$ by the definition of lattice sum we have $\lor M \subseteq \bar{M}$ . On the other hand if $c$ is a composable chain in $\cup M$ , axiom $(T_{3})$ implies that $α (c) \in \lor M$ and so $\bar{M} \subseteq \lor M$ . Thus

\lor M = \bar{M} .

(3.25)

We can now prove that $δ (\lor M) = \lor δ (M)$ . Since $δ$ is order preserving, the fact that $\lor δ (M)$ is the lattice sum of equivalence relations in $δ (M)$ implies that

\lor δ (M) \subseteq δ (\lor M) .

On the other hand if $(e, f) \in δ (\lor M)$ , there exists $α \in \lor M$ such that $e_{α} = e, f_{α} = f$ and $α \subseteq δ (\lor M)$ . Now by (2.25), there exists a composable chain $c = (α_{0}, \dots, α_{n})$ in $\cup M$ such that $α (c) = α$ . Since for all $i, α_{i} \in \cup M$ there exists $T_{i} \in M$ such that $α_{i} \in T_{i}$ . Hence $e_{α i} δ (T_{i}) f_{α i}$ , where $e_{α_{0}} = e$ and $f_{α_{n}} = f$ . Therefore

(e, f) \in δ (T_{0}) \circ δ (T_{1}) \circ \dots \circ δ (T_{n}) \subseteq \lor δ (M) .

This proves the required equality.

It remains to prove that $\land T (D) = T (E, \land D)$ .

Let $\bar{δ} = δ (\land T (D))$ . Since the mapping $δ$ is order preserving, $\bar{δ} \subseteq δ$ for all $δ \in D$ and since $T$ is also order preserving, $T (E, \bar{δ}) \subseteq T (E, δ)$ . Thus

T (E, \bar{δ}) \subseteq {T (E, δ) ∣ δ \in D} = \land T (D) .

But by Lemma 3.4(b), $\land T (D) \subseteq T (E, \bar{δ})$ and therefore $T (E, δ) = \land T (D)$ . For all $δ \in D$ since $\bar{δ} \subseteq δ$ , we have by the definition of lattice products $\bar{δ} \subseteq \land D$ . Hence $T (E, \bar{δ}) \subseteq T (E, \land D)$ . On the other hand, if $α \in T (E, \land D), α \subseteq δ$ for all $δ \in D$ and hence $α \in T (E, δ)$ for all $δ \in D$ . This implies that $α \in \land T (D)$ .

This completes the proof. □

Before concluding this section, we prove three lemmas needed in Chapter Lemma 5.

Lemma 3.7. Let $e \in E$ . If $e_{1}, e_{2} \in ω^{l} (e)$ and $e_{1} \overset{r}{\approx} e_{α}$ then

τ^{r} (e_{1}, e_{2}) \circ τ^{l} (e_{2}, e_{2} τ_{(2)}^{l}) = τ^{l} (e_{1}, e_{1} τ_{(2)}^{l}) \circ τ^{r} (e_{1} τ^{l} (e), e_{2} τ^{l} (e)) .

Proof. Let $h \in ω (e_{1})$ . Then $h \in ω^{r} (e_{2})$ and $(h) τ^{r} (e_{1}, e_{2}) \circ τ^{l} (e_{2}, e_{2} τ^{l} (e)) = ((h) τ^{r} (e_{2})) τ^{l} (e_{2} τ^{l} (e))$ . Now $h τ^{r} (e_{2}) ω^{l} e_{2} τ^{l} (e) ω e$ and hence by $(B_{2}^{*})$ ,

\begin{array}{rcl} (h τ^{r} (e_{2})) τ^{l} (e_{2} τ^{l} (e)) & = & ((h τ^{r} (e_{2})) τ^{l} (e)) τ^{l} (e_{2} τ^{l} (e)) \\ = & ((h τ^{r} (e_{2})) τ^{l} (e_{2})) τ^{l} (e) \end{array}

since $τ^{l} (e)$ is a bimorphism. Hence

(h) τ^{r} (e_{1}, e_{2}) \circ τ^{l} (e_{2}, e_{2} τ^{l} (e)) = (h τ^{l} (e)) τ^{r} (e_{2} τ^{l} (e)) .

But $h τ^{l} (e) ω e_{1} τ^{l} (e)$ and hence by ${(B_{2})}^{*}$

h τ^{r} (e) = (h τ^{l} (e)) τ^{l} (e_{1} τ^{l} (e)) = h τ^{l} (e_{1} τ^{l} (e)) .

Therefore

\begin{array}{rcl} (h) τ^{r} (e_{1}, e_{2}) \circ τ^{l} (e_{2}, e_{2} τ^{l} (e)) & = & (h τ^{l} (e)) τ^{r} (e_{2} τ^{l} (e)) \\ = & (h) τ^{l} (e_{1}, e_{1} τ^{l} (e)) \circ τ^{r} (e_{1} τ^{l} (e), e_{2} τ^{l} (e)) \end{array}

which is the required equality. □

Lemma 3.8. Let $e, f, g_{1}$ and $g_{2}$ satisfy the conditions of axiom $(B_{5})$ . Then

\begin{matrix} α^{l} (g_{2}, e) \circ α^{r} (g_{2} τ^{l} (e), g_{1}, τ^{l} (e)) \circ α^{l} {(g_{1}, e)}^{- 1} \\ = α^{r} (g_{2}, f) \circ α^{l} (g_{2} τ^{l} (f), g_{1}, τ^{r} (f)) \circ α^{r} {(g, f)}^{- 1} . \end{matrix}

where, for $e_{1} ω^{r} e_{2} (e_{1} ω^{l} e_{2})$

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

(3.26)

and $α^{r} {(e_{1}, e_{2})}^{- 1}$ denotes the inverse of $α_{r} (e_{1}, e_{2})$ .

Proof. Since $e, f, g_{1}$ and $g_{2}$ satisfy conditions of axiom $(B_{5})$ , there exist $g_{2}^{'}, g_{2}^{''}$ and $g_{1}^{'}$ such that statements (a), (b) and (c) of Lemma 2.7 are satisfied. □

Hence

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

Therefore by (3.26) and by (c) of Lemma 2.7, we have

\begin{array}{rcl} (e^{''}) α^{l} (g_{2}, e) \circ α^{r} (g_{2} τ^{l} (e), g_{1} τ^{l} (e) \circ α^{l} {(g, e)}^{- 1}) \\ = (e^{''} τ^{l} (g_{2}^{'} τ^{l} (e)) τ^{r} (g_{1}^{'} τ^{l} (e)) τ^{l} (g_{1})) \end{array}

for every $e^{''} \in ω (g_{2})$ . Since $τ^{l} (e)$ is a bimorphism, by axiom ${(B_{2})}^{*}$ we have

\begin{array}{rcl} (e^{''}) τ^{l} (g_{2}^{'} τ^{l} (e)) & = & (e^{''} τ^{l} (e)) τ^{l} (g_{2}^{'} τ^{l} (e)) \\ = & (e^{''} τ^{l} (g_{2}^{'})) τ^{l} (e) \end{array}

and

\begin{array}{rcl} ((e^{''}) τ^{l} (g_{2}^{'} τ^{l} (e)) τ^{r} (g_{1}^{'} τ^{l} (e)) & = & ((e^{''} τ^{l} (g_{2}^{'})) τ^{l} (e)) τ^{r} (g_{1}^{'} τ^{l} (e)) \\ = & ((e^{''} τ^{l} (g_{2}^{'})) τ^{r} (g_{1}^{'})) τ^{l} (e) . \end{array}

Hence

\begin{array}{rcl} (e^{''}) α^{l} (g_{2}, e) \circ α^{r} (g_{2} τ^{l} (e), g_{1} τ^{l} (e)) \circ α^{l} {(g_{1}, e)}^{- 1} & = & (((e^{''}) τ^{l} (g_{2}^{'})) τ^{r} (g_{1}^{'})) τ^{l} (e) τ^{r} (g_{1})) \\ = & ((e^{''} τ^{l} (g_{2}^{'})) τ^{r} (g_{1})) τ^{r} (g_{2}^{'} τ^{r} (g_{1})) \\ = & ((e^{''} τ^{l} (g_{2}^{'})) τ^{r} (g_{2}^{'})) τ^{r} (g_{1}) \\ = & (e^{''} τ^{l} (g')) τ^{r} (g_{1}) \\ = & (e^{''}) τ^{l} (g_{2}, g_{2}^{'}) \circ τ^{r} (g_{1}) . \end{array}

We can prove dually that

\begin{array}{rcl} (e^{''}) α^{r} (g_{2}, f) \circ α^{l} (g_{2} τ^{r} (f), g, τ^{r} (f)) \circ α^{r} {(g_{1}, f)}^{- 1} = (e^{''}) τ^{r} (g_{2}, g_{2}^{''}) \circ τ^{l} (g_{1}) . \end{array}

The lemma now follows from axiom $(B_{5})$ .

Lemma 3.9. Let $α \in Ẽ$ . Then for every $e, g \in E, h_{1} \in S (e, e_{α})$ and $h_{2} \in S (f_{α}, g)$ , there exist $h \in S (e_{1}, (h_{2} τ^{l} (e_{α})) α^{- 1})$ and $h^{'} \in S ((h_{1} τ^{r} (e_{α})) α, g)$ such that

\begin{array}{rcl} (h τ^{r} (e_{α})) α = h^{'} τ^{l} (f_{α}) . \end{array}

Proof. Let $h_{1}^{'} = (h_{1} τ^{r} (e_{α})) α$ and $h_{2}^{'} = (h_{2} τ^{l} (f_{α})) α^{- 1}$ . We first prove that

\begin{array}{rcl} S (h_{1}, h_{2}^{'}) \subseteq S (e, h_{2}^{'}), S (h_{1}^{'}, h_{2}) \subseteq S (h_{1}^{'}, g) . & (3.27) \end{array}

Suppose that $h \in S (h_{1}, h_{2}^{'})$ and $h^{'} \in S (e, h_{2}^{'})$ . By the definition of $h_{2}^{'}$ , $h_{2}^{'} \in ω (e_{α})$ and hence

\begin{array}{rcl} h^{'} \in ω^{l} (e) \cap ω^{r} (e_{α}) . \end{array}

Therefore,

\begin{array}{rcl} (h^{'} τ^{l} (e), h^{'} τ^{r} (e_{α})) ω^{r} \times ω^{l} (h τ^{l} (e), h τ^{r} (e_{α})) . \end{array}

Thus by axiom $(B_{5})$ , there exists $h^{''} \in E$ such that

\begin{array}{rcl} h^{'} \overset{r}{\approx} h^{''} ω^{l} h_{1}, h^{'} τ^{r} (e_{α}) = h^{''} τ^{r} (e_{α}) and h^{'} τ^{l} (e) \overset{r}{\approx} h^{''} τ^{l} (e) . \end{array}

Further, by axiom $(B_{2})$ , we have

\begin{array}{rcl} h^{'} τ^{r} (h_{2}^{'}) = (h^{'} τ^{r} (e_{2})) τ^{r} (h_{2}^{'}) = (h^{''} τ^{r} (e_{α})) τ^{r} (h_{2}^{'}) = h^{''} τ^{r} (h_{2}^{'}) . \end{array}

Hence $h^{''} \in S (e, h_{2}^{'}) \cap ω^{l} (h_{1})$ and therefore

\begin{array}{rcl} h, h^{''} \in ω^{l} (h_{1}) \cap ω^{r} (h_{2}^{'}) . \end{array}

Since $h \in S (h, h_{2}^{'})$ and $h^{''} \in S (e, h_{2}^{'})$ we have

\begin{array}{rcl} h^{''} τ^{r} (h_{2}^{'}) = h τ^{r} (h_{2}^{'}), \\ h^{''} τ^{l} (h_{1}) ω^{r} h τ^{l} (h_{1}) and h τ^{l} (e) ω^{r} h^{''} τ^{l} (e) . \end{array}

Then

\begin{array}{rcl} h τ^{l} (h_{1}) = (h τ^{l} (e)) τ^{l} (h_{1}) ω^{r} (h^{''} τ^{l} (e) τ^{l} (h_{1})) = h^{''} τ^{l} (h_{1}), \end{array}

which implies that $h^{''} \in S (h_{1}, h_{2}^{'})$ .

From the facts that $h^{''} \in S (e, h'), h \in ω^{l} (e) \cap ω^{r} (h')$ and by axiom $(B_{5})$ we obtain that there exists $h^{'''}$ such that

\begin{array}{rcl} h \overset{l}{\approx} h^{'''} ω^{r} h^{''} \\ h τ^{l} (e) = h^{'''} τ^{l} (e) and h τ^{r} (h_{2}^{'}) \overset{l}{\approx} h^{'''} τ^{r} (h_{2}^{'}) . \end{array}

Since $h τ^{r} (h') \overset{l}{\approx} h^{''} τ^{r} (h_{2}^{'}), h^{'''} ω^{r} h^{''}$ we have

\begin{array}{rcl} h^{'''} τ^{r} (h_{2}^{'}) \overset{l}{\approx} h^{''} τ^{r} (h_{2}^{'}) and h^{'''} τ^{r} (h_{2}^{'}) ω^{r} h^{''} τ^{r} (h_{2}^{'}) . \end{array}

Thus

\begin{array}{rcl} h^{'''} τ^{r} (h_{2}^{'}) & = & h^{''} τ^{r} (h_{2}^{'}) \Rightarrow h^{'''} \overset{r}{\approx} h^{''} \\ \Rightarrow & h^{''} τ^{l} (e) \overset{r}{\approx} h^{'''} τ^{l} (e) = h τ^{l} (e) \\ \Rightarrow & h \in S (e, h_{2}^{'}) . \end{array}

Consequently $S (h, h_{2}^{'}) \subseteq S (e, h_{2}^{'})$ . The other inclusion relation in (3.27) can be proved dually. Now to prove the lemma, choose $h \in S (h_{1}, h_{2}^{'})$ . Then by (2.5)

\begin{array}{rcl} h τ^{r} (e_{α}) \in (S (h_{1}, h_{2}^{'}) \cap τ^{r} (e_{α})) \subseteq S (h_{1} τ^{r} (e_{α}), h_{2}^{'}) . \end{array}

Since $α$ is a partial $ω$ -isomorphism, we have

\begin{array}{rcl} (h τ^{r} (e_{α})) α \in S ((h, τ^{r} (e_{α})) α, h_{2}^{'} α) = S (h_{1}^{'}, h_{2} τ^{l} (f_{α})) . \end{array}

But $S (h_{1}^{'}, h_{2} τ^{l} (f α)) = S (h_{1}^{'}, h_{2}) τ^{l} (f α)$ and hence there exists $h^{'} \in S (h_{1}^{'}, h_{2})$ such that

\begin{array}{rcl} (h τ^{r} (e_{α})) α = h^{'} τ^{l} (f α) \end{array}

and hence the lemma. □

ptail

top

Chapter 3Partially Transitive Set of Partial ω-isomorphisms

Chapter 3
Partially Transitive Set of Partial $ω$ -isomorphisms