$A\cdot w=B\cdot v\ \Rightarrow\ A\cdot w^{+}=B\cdot v^{+}\qquad\text{for all
$A,B\in{\mathcal{P}}_{X}$ and $w,v\in X^{*}$}$

from the expansions $A\cdot w=(A\cup w^{\downarrow},w)$, $A\cdot w^{+}=(A\cup
w^{\downarrow},\iota)$, and so on.

It also follows from (7.5) that the associated map
${X^{*}\to{\mathcal{P}}_{X}:w\mapsto w^{+}}$ from Proposition 4.7 is given by
${w^{+}=w^{\downarrow}\equiv(w^{\downarrow},\iota)}$. This is of course just
the restriction to $X^{*}$ of the + operation on $\mathcal{L}_{X}$.

######  Remark 7.6.

It follows from Lemma 4.15(ii) that the pair $({\mathcal{P}}_{X},X^{*})$ is
not strong, as $w^{\downarrow}\not=\\{\iota\\}$ when $w\in X^{*}$ is non-
empty. Hence, the left-uniqueness property (SA2) does not hold. In contrast to
this, it follows immediately from (7.1) that the pair
$({\mathcal{P}}_{X},X^{*})$ has the _right-uniqueness_ property:

$A\cdot w=B\cdot v\ \Rightarrow\ w=v\qquad\text{for all
$A,B\in{\mathcal{P}}_{X}$ and $w,v\in X^{*}$.}$

One important consequence of this is that the congruence
$\sigma=\sigma({\mathcal{P}}_{X},X^{*})$ on $X^{*}$ from Definition 5.21 is
trivial: i.e., $\sigma=\Delta_{X^{*}}$. Together with Lemma 5.37 (and
$P=U={\mathcal{P}}_{X}$), it follows immediately from this that the pair
$({\mathcal{P}}_{X},X^{*})$ is proper. Consequently,
$\mathcal{L}_{X}={\mathcal{P}}_{X}\cdot X^{*}$ is
$({\mathcal{P}}_{X},X^{*})$-proper.

######  Remark 7.7.

It does not follow from Remark 7.6 that $\mathcal{L}_{X}$ is a proper left
restriction monoid in the sense of Definition 5.7, although this does turn out
to be the case. (To the best of our knowledge, this fact has not been
explicitly stated in the literature, but it follows quickly from known
results; see for example [52, Proposition 3.3].) To demonstrate this we could
show that the pair $({\mathcal{P}}_{X},\mathcal{L}_{X})$ is proper, and then
apply Proposition 5.29. But this is no easier than directly using Definition
5.7. To use this, we need to understand the congruence
$\sigma=\sigma_{\mathcal{L}_{X}}(=\sigma({\mathcal{P}}_{X},\mathcal{L}_{X}))$
on $\mathcal{L}_{X}$, and it is easy to see that for any elements $(A,w)$ and
$(B,v)$ of $\mathcal{L}_{X}$,

$(A,w)\mathrel{\sigma}(B,v)\ \Leftrightarrow\ w=v.$ (7.8)

Indeed, the forwards implication is clear, while if $w=v$, then
$(B,\iota)\cdot(A,w)=(A,\iota)\cdot(B,v)$. We then have

$\displaystyle(A,w)=(B,v)\quad\ \Leftrightarrow\ \quad A=B\text{ and
}w=v\quad\ \Leftrightarrow\ \quad(A,w)^{+}=(B,v)^{+}\text{ and
}(A,w)\mathrel{\sigma}(B,v).$

######  Remark 7.9.

Consider again the pair $({\mathcal{P}}_{X},X^{*})$. It follows from
Proposition 4.46 that $\mathcal{L}_{X}$ is a homomorphic image of the
semidirect product

${\mathcal{P}}_{X}\rtimes X^{*}=\big{\\{}{(A,w)}:{A\in{\mathcal{P}}_{X},\ w\in
X^{*}}\big{\\}}\qquad\text{with
operation}\qquad(A,w)\cdot(B,v)=(A\cup{}^{w}\\!B,wv),$

where the action is given in (7.4). Explicitly, the surmorphism
$\pi:{\mathcal{P}}_{X}\rtimes X^{*}\to\mathcal{L}_{X}$ from Proposition 4.46
is given by

$(A,w)\pi=A\cdot w=(A\cup w^{\downarrow},w).$

Note that ${\mathcal{P}}_{X}\rtimes X^{*}$ is not a monoid, even though
${\mathcal{P}}_{X}$ and $X^{*}$ both are. This is because the action of
$X^{*}$ on ${\mathcal{P}}_{X}$ is not by monoid morphisms (cf. (7.5)), even
though it is of course monoidal; cf. Lemma 3.11. On the other hand, it follows
immediately from its definition that $\mathcal{L}_{X}$ is also the
_subsemigroup_ of ${\mathcal{P}}_{X}\rtimes X^{*}$ consisting of all pairs
$(A,w)$ with $w\in A$. (For this, note that when $w\in A$, we have
${A\cup{}^{w}\\!B=A\cup wB}$.)

This is of course reminiscent of the embedding theorems from Chapter 5.
Indeed, Theorem 5.60 tells us that $\mathcal{L}_{X}={\mathcal{P}}_{X}\cdot
X^{*}$ embeds in a semidirect product $\mathcal{U}\rtimes X^{*}$ for some
semigroup $\mathcal{U}$ containing ${\mathcal{P}}_{X}$. (For this we also need
to remember that $\sigma({\mathcal{P}}_{X},X^{*})=\Delta_{X^{*}}$; cf Remark
7.6.) As noted in the previous paragraph, we can in fact take $\mathcal{U}$ to
be ${\mathcal{P}}_{X}$ itself.

Alternatively, we could apply Theorem 5.60 to the pair
$({\mathcal{P}}_{X},\mathcal{L}_{X})$, or even apply Theorem 5.12 to
$\mathcal{L}_{X}$ itself. In either case, the relevant theorem tells us that
$\mathcal{L}_{X}(={\mathcal{P}}_{X}\cdot\mathcal{L}_{X})$ embeds in a
semidirect product $\mathcal{U}\rtimes(\mathcal{L}_{X}/\sigma)$ for some
semigroup $\mathcal{U}$ containing ${\mathcal{P}}_{X}$, where
$\sigma=\sigma_{\mathcal{L}_{X}}=\sigma({\mathcal{P}}_{X},\mathcal{L}_{X})$.
It is easy to see from (7.8) that $\mathcal{L}_{X}/\sigma\cong X^{*}$, as has
also been shown in [10, Theorem 5.1(iii)].

######  Remark 7.10.

Finally, we consider the covering Theorem 5.39 in the context of
$\mathcal{L}_{X}$. Since $\mathcal{L}_{X}$ is proper, it is trivially covered
by itself, and it turns out that this is precisely what we recover from our
proof of Theorem 5.39. Indeed, the $(\underline{U},\overline{S})$ construction
applied to the pair ${(U,S)=({\mathcal{P}}_{X},X^{*})}$ leads to the (monoid)
subsemigroups

$\underline{{\mathcal{P}}_{X}}=\big{\\{}{(A,\iota)}:{A\in{\mathcal{P}}_{X}}\big{\\}}\equiv{\mathcal{P}}_{X}\qquad\text{and}\qquad\overline{X^{*}}=\big{\\{}{(w^{\downarrow},w)}:{w\in
X^{*}}\big{\\}}\equiv X^{*}$

of the semidirect product $U\rtimes S(=U^{1}\rtimes
S^{1})={\mathcal{P}}_{X}\rtimes X^{*}$. The proper monoid

$\underline{U}\cdot\overline{S}=\big{\\{}{(u,s)\in U\rtimes
S}:{u=us^{+}}\big{\\}}=\big{\\{}{(A,w)\in{\mathcal{P}}_{X}\rtimes
X^{*}}:{A=A\cup w^{+}}\big{\\}}$

is then precisely $\mathcal{L}_{X}$ itself, since

$A=A\cup w^{+}\ \Leftrightarrow\ A=A\cup w^{\downarrow}\ \Leftrightarrow\ w\in
A\qquad\text{for all $A\in{\mathcal{P}}_{X}$ and $w\in X^{*}$.}$

####  7.2 Presentations

Our goal now is to give a monoid presentation for the free left restriction
monoid $\mathcal{L}_{X}$ over an arbitrary set $X$. We keep the notation from
the previous section. In particular, $\mathcal{L}_{X}={\mathcal{P}}_{X}\cdot
X^{*}$ arises from the action pair $({\mathcal{P}}_{X},X^{*})$, where
${\mathcal{P}}_{X}$ and $X^{*}$ are identified with submonoids of
$\mathcal{L}_{X}$, as explained above. We _could_ apply Theorem 6.12 to this
pair, but it actually follows from Remark 7.10 that Theorem 6.29 applies, and
this will lead us to a slightly quicker derivation. In any case, we need
presentations for ${\mathcal{P}}_{X}$ and $X^{*}$; with the latter of course
being trivial, we turn to the former.

The next result gives a monoid generating set for ${\mathcal{P}}_{X}$. Recall
that an _atom_ of a semigroup $S$ is an element $a$ such that $a=xy\
\Rightarrow\ a\in\\{x,y\\}$ for all $x,y\in S$. It is easy to see that any
generating set for a semigroup must contain all atoms.

######  Proposition 7.11.

For any set $X$, $\Gamma_{X}=\\{{w^{\downarrow}}:{w\in X^{+}}\\}$ is the
(unique) minimum monoid generating set for ${\mathcal{P}}_{X}$.

###### Proof.

If $A\in{\mathcal{P}}_{X}$, then

$A=A^{\downarrow}=\bigcup_{w\in
A\setminus\\{\iota\\}}w^{\downarrow}\in\langle\Gamma_{X}\rangle,$

keeping $|A|<\aleph_{0}$ in mind. This shows that
${\mathcal{P}}_{X}=\langle\Gamma_{X}\rangle$.

To complete the proof, it suffices to show that every element of $\Gamma_{X}$
is an atom. So let $w\in X^{+}$, and suppose $w^{\downarrow}=A\cup B$ for some
$A,B\in{\mathcal{P}}_{X}$. Then $A,B\subseteq w^{\downarrow}$. Since $w\in
w^{\downarrow}=A\cup B$, we may assume by symmetry that $w\in A$, and then
$w^{\downarrow}\subseteq A^{\downarrow}=A$, so that $A=w^{\downarrow}$. ∎

We now wish to give a presentation for ${\mathcal{P}}_{X}$ in terms of the
generating set $\Gamma_{X}$. With this in mind, we define an alphabet

$A_{X}=\\{{a_{w}}:{w\in X^{+}}\\}$

in one-one correspondence with $\Gamma_{X}$. By Proposition 7.11, we have a
surmorphism

$\phi_{X}:A_{X}^{*}\to{\mathcal{P}}_{X}:a_{w}\mapsto w^{\downarrow}.$

We then define $R_{X}=R_{X}^{1}\cup R_{X}^{2}$, where

$R_{X}^{1}=\big{\\{}{(a_{w}a_{v},a_{v}a_{w})}:{w,v\in
X^{+}}\big{\\}}\qquad\text{and}\qquad
R_{X}^{2}=\big{\\{}{(a_{wv}a_{w},a_{wv})}:{w\in X^{+},\ v\in X^{*}}\big{\\}}.$

Note that we have the alternative description

$R_{X}^{2}=\big{\\{}{(a_{w}a_{v},a_{w})}:{w,v\in X^{+},\ v\text{ is a prefix
of }w}\big{\\}}.$

######  Theorem 7.12.

For any set $X$, ${\mathcal{P}}_{X}$ has presentation
$\textup{{Mon}}\langle{A_{X}}:{R_{X}}\rangle$ via $\phi_{X}$.

###### Proof.

We have already noted that $\phi_{X}$ is a surmorphism, and it is clear that
${R_{X}\subseteq\ker(\phi_{X})}$. Indeed, we have
$R_{X}^{1}\subseteq\ker(\phi_{X})$ because ${\mathcal{P}}_{X}$ is commutative,
and $R_{X}^{2}\subseteq\ker(\phi_{X})$ follows from the observation that

$(wv)^{\downarrow}\cup w^{\downarrow}=(wv)^{\downarrow}\qquad\text{for all
$w,v\in X^{*}$.}$

It therefore remains to show that $\ker(\phi_{X})\subseteq{\sim}$, where
${\sim}=R_{X}^{\sharp}$. So suppose $(p,q)\in\ker(\phi_{X})$, and write

$p=a_{w_{1}}\cdots a_{w_{k}}\qquad\text{and}\qquad q=a_{v_{1}}\cdots
a_{v_{l}}\qquad\text{where}\qquad w_{1},\ldots,w_{k},v_{1},\ldots,v_{l}\in
X^{+}.$

For any $1\leq i\leq l$, we have

$v_{i}\in v_{i}^{\downarrow}\subseteq v_{1}^{\downarrow}\cup\cdots\cup
v_{l}^{\downarrow}=q\phi_{X}=p\phi_{X}=w_{1}^{\downarrow}\cup\cdots\cup
w_{k}^{\downarrow}.$

It follows from this that $v_{i}\in w_{j}^{\downarrow}$ for some $1\leq j\leq
k$, which means that $v_{i}$ is a prefix of $w_{j}$. But then $R_{X}^{2}$
contains the relation $(a_{w_{j}}a_{v_{i}},a_{w_{j}})$. Combining this with
$R_{X}^{1}$, it follows that $p\sim pa_{v_{i}}$. Since this is true for all
$1\leq i\leq l$, it follows that $p\sim pa_{v_{1}}\cdots a_{v_{l}}=pq$. By
symmetry we also have $q\sim qp$. Since $pq\sim qp$ by $R_{X}^{1}$, it follows
that $p\sim q$, as required. ∎

We now apply Theorem 6.29 to obtain a (monoid) presentation for
$\mathcal{L}_{X}$.

######  Theorem 7.13.

For any set $X$, the free left restriction monoid $\mathcal{L}_{X}$ has
presentation

$\textup{{Mon}}\langle{A_{X}\cup X}:{R_{X}\cup R_{1}\cup R_{2}}\rangle$

via

$\Phi_{X}:(A_{X}\cup X)^{*}\to\mathcal{L}_{X}:\begin{cases}a_{w}\mapsto
w^{\downarrow}\equiv(w^{\downarrow},\iota)&\text{for $w\in X^{+}$,}\\\
x\mapsto x\equiv(x^{\downarrow},x)&\text{for $x\in X$,}\end{cases}$

where

$R_{1}=\big{\\{}{(xa_{w},a_{xw}x)}:{x\in X,\ w\in
X^{+}}\big{\\}}\qquad\text{and}\qquad R_{2}=\big{\\{}{(x,a_{x}x)}:{x\in
X}\big{\\}}.$

###### Proof.

We begin with the presentation $\textup{{Mon}}\langle{A_{X}}:{R_{X}}\rangle$
for ${\mathcal{P}}_{X}$ from Theorem 7.12, and the canonical presentation
$\textup{{Mon}}\langle{X}:{\varnothing}\rangle$ for $X^{*}$ (via the identity
map $X^{*}\to X^{*}$). Theorem 6.29 then tells us that
$\mathcal{L}_{X}=\big{\\{}{(A,w)\in{\mathcal{P}}_{X}\rtimes X^{*}}:{A=A\cup
w^{+}}\big{\\}}$ has presentation

$\textup{{Mon}}\langle{A_{X}\cup X}:{R_{X}\cup R_{1}\cup R_{2}}\rangle$

via $\Phi_{X}$, where

$R_{1}=\big{\\{}{(xa_{w},{}^{x}(a_{w})\cdot x)}:{x\in X,\ w\in
X^{+}}\big{\\}}\qquad\text{and}\qquad R_{2}=\big{\\{}{(x,x^{+}x)}:{x\in
X}\big{\\}}.$

(The second set of relations was denoted $R_{3}$ in Theorem 6.29.) In $R_{1}$,
${}^{x}(a_{w})$ is a word mapping to
${}^{x}(w^{\downarrow})=(xw)^{\downarrow}$, so of course we can take
${}^{x}(a_{w})=a_{xw}$. Similarly, we can take $x^{+}=a_{x}$ in $R_{2}$. ∎

######  Remark 7.14.

The presentation in Theorem 7.13 involves the generating set $\Gamma_{X}\cup
X$ for $\mathcal{L}_{X}$. It is easy to see (using Proposition 7.11) that this
is the unique minimum generating set.

###  8 Independence algebras

In this chapter we apply the theory developed so far to a number of monoids
and semigroups of partial endomorphisms of independence algebras. In Sections
8.1 and 8.2 we recall the necessary definitions, and prove some preliminary
results on independence algebras, and the partial endomorphism monoid
$\operatorname{PEnd}(A)$ of such an algebra $A$. A key point is that
$\operatorname{PEnd}(A)$ is a left restriction monoid. Section 8.3 contains a
number of results concerning maximal subalgebras, and Section 8.4 treats
subalgebras of arbitrary finite codimension; the main result here is Theorem
8.40, which gives a presentation for the $\cap$-semilattice
$\operatorname{Sub}^{\operatorname{f}}(A)$ of all finite-codimensional
subalgebras of a strong independence algebra $A$. Section 8.5 provides natural
generating sets for the automorphism groups $\operatorname{Aut}(A)$ in the
case that $A$ is finite-dimensional, and also for the group
$\operatorname{Aut}^{\operatorname{f}}(A)$ of finitary automorphisms of an
arbitrary strong independence algebra. In Section 8.6 we identify six strong
action pairs $(E,S)$ in $M=\operatorname{PEnd}(A)$, each leading in the usual
way to a naturally occurring subsemigroup $ES$ of $\operatorname{PEnd}(A)$,
the elements of which we also characterise. We then look, in Section 8.7, at
the various ‘congruence conditions’ from Section 4.5 and Chapter 6, as they
apply to each of our pairs. Finally, we discuss presentations for the
semigroups $ES$ in Section 8.8. Presentations for $S$ are not known in general
(even for relatively simple classes of the algebra $A$), so it is not possible
to give explicit presentations for $ES$ in full generality. However, a
presentation for $E$ can be deduced from Theorem 8.40 in the case that $A$ is
finite-dimensional and strong, as $E$ is then isomorphic to
$\operatorname{Sub}(A)=\operatorname{Sub}^{\operatorname{f}}(A)$. We conclude
by explaining how the presentation for $E$ can be extended to a presentation
for $ES$ modulo an appropriate presentation for $S$. For background on
universal algebra, see [12].

####  8.1 Preliminaries

Let $A$ be a (universal) algebra. We typically identify $A$ with its
underlying set, and as usual we identify any nullary operation on $A$ with a
constant: i.e., the unique element in the image of the operation. If
$X\subseteq A$ then $\langle X\rangle$ denotes the subalgebra generated by
$X$. The least subalgebra of $A$ will be denoted

$\mathcal{C}(A)=\langle\varnothing\rangle.$

Note that $\mathcal{C}(A)=\varnothing$ if and only if $A$ has no constants. We
write $B\leq A$ ($B<A$) to indicate that $B$ is a (proper) subalgebra of $A$,
and we write $\operatorname{Sub}(A)=\\{{B}:{B\leq A}\\}$ for the lattice of
all subalgebras. The meet and join of $B,C\in\operatorname{Sub}(A)$ are $B\cap
C$ and $B\vee C=\langle B\cup C\rangle$, respectively.

A subset $X\subseteq A$ is _independent_ if for any $x\in X$ we have
$x\notin\langle X\setminus x\rangle$. (Here and elsewhere in this chapter, we
avoid clutter by identifying one-element subsets of $A$ with their unique
element, so $X\setminus x$ stands for $X\setminus\\{x\\}$, and so on.) A
_basis_ is an independent generating set for $A$. Note that a singleton subset
$\\{x\\}$ is independent if and only if $x\not\in\mathcal{C}(A)$.

######  Definition 8.1.

Let $A$ be a (universal) algebra. Then $A$ is an _independence algebra_ if it
satisfies the _exchange property_ and the _free basis property_ :

  1. (EP)

For all $X\subseteq A$ and $x,y\in A$, if $x\in\langle X\cup y\rangle$ and
$x\notin\langle X\rangle$, then $y\in\langle X\cup x\rangle$.

  1. (FBP)

If $X$ is basis for $A$, then any map $X\rightarrow A$ can be extended
(uniquely) to an endomorphism of $A$.

Archetypal examples of independence algebras include:

  * •

vector spaces over division rings, where we have a binary operation
(addition), a unary operation (negation), a nullary operation (the zero), and
an additional unary operation for each element of the ground ring (scalar
multiplication),

  * •

sets, regarded as algebras with no operations, and

  * •

free group-acts, including the special case of sets when the group is trivial;
see Example 9.9.

As noted in [54], independence algebras were first studied under the name of
_$v^{*}$ -algebras_. They appear first in an article of Narkiewicz [96], and
were inspired by Marczewski’s study of notions of independence, initiated in
[80]. A classification into five families, together with one finite exception,
was given by Urbanik in [117].

The next (well known) result is a simple consequence of (EP).

######  Lemma 8.2.

If $X$ is an independent subset of an independence algebra $A$, then $X\cup y$
is independent for any $y\in A\setminus\langle X\rangle$. ∎

The next result follows from [54, Lemma 3.7], and will typically be used
without explicit reference.

######  Lemma 8.3.

If $X$ and $Y$ are bases of an independence algebra $A$, then any endomorphism
of $A$ extending a bijection $X\to Y$ is an automorphism. ∎

The following facts concerning an arbitrary independence algebra $A$ are well
known; see for example [54, Section 3].

  * •

Every independent subset of $A$ is contained in a maximal independent subset.
Since $\varnothing$ is independent, maximal independent subsets exist. Any
maximal independent subset generates $A$, and is hence a basis. So any
independent set can be extended to a basis.

  * •

All bases for $A$ have the same cardinality, which we call the _dimension_ of
$A$, and denote $\dim(A)$. This coincides with the usual meaning of dimension
when $A$ is a vector space; when $A$ is a set (with no operations),
$\dim(A)=|A|$. Note that the dimension of $A$ is also called the _rank_ of $A$
in the literature, and denoted $\operatorname{rank}(A)$.

  * •

Any subalgebra $B\leq A$ is also an independence algebra, and any basis of $B$
may be extended to a basis for $A$. Thus, $\dim(B)$ exists and
$\dim(B)\leq\dim(A)$.

  * •

If $\dim(A)=n<\aleph_{0}$, then $A$ is the unique subalgebra of dimension $n$,
and the maximal (proper) subalgebras are precisely those of dimension $n-1$.
(Recall that $B\leq A$ is maximal if $B<C\leq A\ \Rightarrow\ C=A$.) When
$\dim(A)\geq\aleph_{0}$ we require the notion of _codimension_ to describe the
maximal subalgebras; see Definition 8.6 and Proposition 8.22.

  * •

If $X\subseteq A$ is any independent set, then any map $X\to A$ can be
extended to an endomorphism of $A$. (First extend $X$ to a basis $X\sqcup Y$
of $A$, and extend the given map $X\to A$ arbitrarily to $X\sqcup Y\to A$; by
(FBP), the latter extends to an endomorphism.)

Here and elsewhere, $\sqcup$ denotes disjoint union.

The notion of _codimension_ of subalgebras was used in [48], and goes back to
ideas from Jones [67]. The following definition is a special case of that
given in [67], which involved more general _closure operators_ on arbitrary
sets.

######  Definition 8.4.

Let $B$ be a subalgebra of an independence algebra $A$. A subset $X$ of $A$ is
_$B$ -independent_ if $x\not\in\big{\langle}B\cup(X\setminus x)\big{\rangle}$
for all $x\in X$. The set $X$ is then called a _$B$ -basis_ for $\langle B\cup
X\rangle$.

Clearly any $B$-independent set is disjoint from $B$. Note that independent
sets are precisely the $\mathcal{C}(A)$-independent sets in the sense of
Definition 8.4, where as usual $\mathcal{C}(A)=\langle\varnothing\rangle$. The
next result is a special case of the main theorem of [67]:

######  Lemma 8.5.

For any subalgebra $B$ of an independence algebra $A$, all $B$-bases for $A$
have the same cardinality. ∎

We may therefore make the following definition:

######  Definition 8.6.

Given a subalgebra $B$ of an independence algebra $A$, the _codimension of $B$
in $A$_, denoted $\operatorname{codim}(B)$, is defined to be the cardinality
of any $B$-basis of $A$.

Strictly speaking, one should perhaps use notation such as
$\operatorname{codim}_{A}(B)$, to explicitly indicate the over-algebra $A$.
But since the context should always be clear, we simply write
$\operatorname{codim}(B)$ to avoid clutter.

We will also need the following basic facts.

######  Lemma 8.7.

If $B$ is a subalgebra of an independence algebra $A$, then $X\cup Y$ is a
basis of $A$ for any basis $X$ of $B$, and any $B$-basis $Y$ of $A$.

###### Proof.

Since $A=\langle B\cup Y\rangle=\langle\langle X\rangle\cup Y\rangle=\langle
X\cup Y\rangle$, it remains to show that $X\cup Y$ is independent. For this,
and aiming for a contradiction, suppose $z\in\big{\langle}(X\cup Y)\setminus
z\big{\rangle}$ for some $z\in X\cup Y$.

Case 1. If $z\in Y$, then $z\in\big{\langle}X\cup(Y\setminus
z)\big{\rangle}=\big{\langle}B\cup(Y\setminus z)\big{\rangle}$, contradicting
$B$-independence of $Y$.

Case 2. Now suppose $z\in X$, so that $z\in\big{\langle}(X\setminus z)\cup
Y\big{\rangle}$. Choose finite subsets $X^{\prime}\subseteq X\setminus z$ and
$Y^{\prime}\subseteq Y$ such that $z\in\langle X^{\prime}\cup
Y^{\prime}\rangle$, and suppose $|X^{\prime}|+|Y^{\prime}|$ is minimal among
all such $X^{\prime},Y^{\prime}$. Since $X$ is a basis of $B$, it follows from
independence that $z\not\in\langle X^{\prime}\rangle$, and so
$Y^{\prime}\not=\varnothing$. Then for any $y\in Y^{\prime}$, and with
$Z=(X^{\prime}\cup Y^{\prime})\setminus y$, we have

$z\in\langle X^{\prime}\cup Y^{\prime}\rangle=\langle Z\cup
y\rangle\qquad\text{and}\qquad z\not\in\langle Z\rangle,$

using minimality of $|X^{\prime}|+|Y^{\prime}|$ for the latter. It then
follows from (EP) that

$y\in\langle Z\cup z\rangle\subseteq\big{\langle}(X\cup Y)\setminus
y\big{\rangle}.$

Since $y\in Y^{\prime}\subseteq Y$, we have therefore reduced to Case 1. ∎

It follows that $\dim(B)+\operatorname{codim}(B)=\dim(A)$ for all $B\leq A$.
In particular, if $\dim(A)=n<\aleph_{0}$, then
$\operatorname{codim}(B)=n-\dim(B)$ for all $B\leq A$. We will also use the
following converse of Lemma 8.7, often without reference.

######  Lemma 8.8.

If $B$ is a subalgebra of an independence algebra $A$, and if $X\sqcup Y$ is
independent for some basis $X$ of $B$, then $Y$ is $B$-independent.

###### Proof.

Aiming to prove the contrapositive, suppose $Y$ is not $B$-independent, so
${y\in\big{\langle}B\cup(Y\setminus y)\big{\rangle}}$ for some $y\in Y$. But
$B=\langle X\rangle$, so $y\in\big{\langle}B\cup(Y\setminus
y)\big{\rangle}=\big{\langle}X\cup(Y\setminus
y)\big{\rangle}=\big{\langle}(X\cup Y)\setminus y\big{\rangle}$, where we used
the fact that $X$ and $Y$ are disjoint in the last equality. This shows that
$X\cup Y$ is not independent. ∎

The first part of the next result is [48, Lemma 1.3].

######  Lemma 8.9.

Let $A$ be an independence algebra.

  1. (i)

If $B\leq C\leq A$, then $\operatorname{codim}(B)\geq\operatorname{codim}(C)$.

  2. (ii)

If $B\leq C\leq A$ and
$\operatorname{codim}(B)=\operatorname{codim}(C)<\aleph_{0}$, then $B=C$.

###### Proof.

Let $X$ be a basis of $B$, and extend this to bases $X\sqcup Y$ and $X\sqcup
Y\sqcup Z$ of $C$ and $A$, respectively. By Lemma 8.8, $Y\sqcup Z$ is a
$B$-basis of $A$, and $Z$ is a $C$-basis of $A$, so

$\operatorname{codim}(B)=|Y\sqcup
Z|\qquad\text{and}\qquad\operatorname{codim}(C)=|Z|.$

Part (i) immediately follows. For (ii), we have

$\operatorname{codim}(B)=\operatorname{codim}(C)<\aleph_{0}\ \Rightarrow\
|Y\sqcup Z|=|Z|<\aleph_{0}\ \Rightarrow\ Y=\varnothing\ \Rightarrow\ B=\langle
X\rangle=\langle X\sqcup Y\rangle=C.\qed$

Some of the results in Chapter 8 apply only to so-called _strong_ independence
algebras:

######  Definition 8.10.

An independence algebra $A$ is _strong_ if it satisfies the _strong property_
:

  1. (SP)

For independent subsets $X,Y\subseteq A$, if $\langle X\rangle\cap\langle
Y\rangle=\mathcal{C}(A)$, then $X\cup Y$ is independent.

######  Remark 8.11.

Sets, vector spaces and free group-acts are all strong independence algebras.
It is also easy to show that every independence algebra of dimension $\leq 2$
is strong.

A specific example of a three-dimensional non-strong independence algebra is
given in [48, Example 1.5], and it will be convenient to recall the
construction here. Let $A=\\{a_{1},a_{2},a_{3},a_{4}\\}$, with a ternary
operation $f$ defined by

$\displaystyle f(a_{i},a_{i},a_{i})$ $\displaystyle=a_{i}$ for all $i$
$\displaystyle f(a_{i},a_{i},a_{j})=f(a_{i},a_{j},a_{i})=f(a_{j},a_{i},a_{i})$
$\displaystyle=a_{j}$ if $i,j$ are distinct $\displaystyle
f(a_{i},a_{j},a_{k})$ $\displaystyle=a_{l}$ if $i,j,k,l$ are distinct.

All proper subsets of $A$ are independent, but $A$ is not itself independent,
and (SP) fails (for example) for $X=\\{a_{1},a_{2}\\}$ and
$Y=\\{a_{3},a_{4}\\}$.

Of crucial importance to us is the following result, which is [48, Lemma 1.6].
In fact, the property in the lemma can be taken as an equivalent definition of
strong independence algebras.

######  Lemma 8.12.

Let $A$ be a strong independence algebra, and let $B,C\leq A$. Let $X$ be a
basis for $B\cap C$, and extend $X$ to bases $X\sqcup Y$ and $X\sqcup Z$ for
$B$ and $C$, respectively. Then $X\sqcup Y\sqcup Z$ is a basis for $B\vee C$.
∎

We will also need the following simple result, which is a generalisation of
the inclusion-exclusion formula for sets.

######  Lemma 8.13.

If $B$ and $C$ are subalgebras of a strong independence algebra $A$, then

  1. (i)

$\dim(B\vee C)+\dim(B\cap C)=\dim(B)+\dim(C)$,

  2. (ii)

$\operatorname{codim}(B\vee C)+\operatorname{codim}(B\cap
C)=\operatorname{codim}(B)+\operatorname{codim}(C)$.

###### Proof.

Let $X$ be a basis for $B\cap C$, and extend this to bases $X\sqcup Y$ and
$X\sqcup Z$ for $B$ and $C$. By Lemma 8.12, $X\sqcup Y\sqcup Z$ is a basis for
$B\vee C$, and we extend this to a basis $X\sqcup Y\sqcup Z\sqcup W$ for $A$.
Both parts follow quickly upon writing down expressions for the various
(co)dimensions in terms of the cardinalities of $X$, $Y$, $Z$ and $W$. ∎

######  Remark 8.14.

The assumption that $A$ is strong cannot be removed from Lemma 8.13. For
example, let $A$ be the algebra from [48] discussed in Remark 8.11. Then for
the subalgebras $B=\\{a_{1},a_{2}\\}$ and $C=\\{a_{3},a_{4}\\}$, we have

$\dim(B)=\dim(C)=2,\qquad\dim(B\cap C)=0\qquad\text{and}\qquad\dim(B\vee
C)=\dim(A)=3,$

which witnesses the failure of the first identity from Lemma 8.13 in $A$. (The
same (sub)algebras work to demonstrate the failure of the second identity.)

####  8.2 (Partial) endomorphisms

A _partial endomorphism_ of an algebra $A$ is a morphism $B\to A$ for some
subalgebra $B\leq A$; if this morphism is injective, it is a _partial
automorphism_ , and it is then an isomorphism from its domain onto its image.
We also have _endomorphisms_ and _automorphisms_ , with their usual meaning.
We write

$\operatorname{PEnd}(A),\qquad\operatorname{End}(A),\qquad\operatorname{PAut}(A)\qquad\text{and}\qquad\operatorname{Aut}(A)$
(8.15)

for the sets of all partial endomorphisms, endomorphisms, partial
automorphisms and automorphisms of $A$, respectively. These are all monoids
under composition, with identity element $\mathrm{id}_{A}$. Note that for
$\alpha,\beta\in\operatorname{PEnd}(A)$, we have

$\operatorname{dom}(\alpha\beta)=(\operatorname{im}(\alpha)\cap\operatorname{dom}(\beta))\alpha^{-1}\qquad\text{and}\qquad\operatorname{im}(\alpha\beta)=(\operatorname{im}(\alpha)\cap\operatorname{dom}(\beta))\beta,$

both of which are subalgebras of $A$ by standard facts from universal algebra.

The inclusions among the monoids listed in (8.15) are indicated as follows:

$\operatorname{PEnd}(A)$$\operatorname{End}(A)$$\operatorname{PAut}(A)$$\operatorname{Aut}(A)$

Moreover, $\operatorname{PAut}(A)$ is an inverse monoid, and
$\operatorname{Aut}(A)$ is the group of units of all of the above monoids. If
$A$ is an independence algebra, then we also have
$\operatorname{End}(A)\vee\operatorname{PAut}(A)=\operatorname{PEnd}(A)$, as
follows from Theorem 8.56(i) below. On the other hand,
$\operatorname{End}(A)\cap\operatorname{PAut}(A)$ consists of all injective
endomorphisms of $A$; this is equal to $\operatorname{Aut}(A)$ if and only if
$\dim(A)<\aleph_{0}$. When $A$ is simply a set (an algebra with no
operations), the monoids listed in (8.15) are $\mathcal{P}\mathcal{T}_{A}$,
$\mathcal{T}_{A}$, $\mathcal{I}_{A}$ and $\mathcal{G}_{A}$, respectively.
These monoids of (partial) transformations were introduced in Section 2.2.

The next result is of fundamental importance. It is well known, and follows
immediately from the fact that left restriction monoids form a variety.
Specifically, $\mathcal{P}\mathcal{T}_{A}$ is a left restriction monoid under
$\alpha^{+}=\mathrm{id}_{\operatorname{dom}(\alpha)}$, and the submonoid
${\operatorname{PEnd}(A)\leq\mathcal{P}\mathcal{T}_{A}}$ is closed under +.

######  Proposition 8.16.

For any algebra $A$, the partial endomorphism monoid $\operatorname{PEnd}(A)$
is a left restriction monoid under the unary operation
$\alpha^{+}=\mathrm{id}_{\operatorname{dom}(\alpha)}$. ∎

Recall from Section 4.3 that for any left restriction monoid $M$ we have a
number of important submonoids, such as $P(M)=\\{{s^{+}}:{s\in M}\\}$ and
$T(M)=\\{{s\in M}:{s^{+}=1}\\}$. For any algebra $A$, we denote the
semilattice of projections of $\operatorname{PEnd}(A)$ by

$\mathcal{E}_{A}=P(\operatorname{PEnd}(A))=\\{{\alpha^{+}}:{\alpha\in\operatorname{PEnd}(A)}\\}=\\{{\mathrm{id}_{B}}:{B\leq
A}\\}.$ (8.17)

So $\mathcal{E}_{A}$ is precisely the semilattice of _partial identities_ of
$A$: i.e., all identity maps on subalgebras of $A$. Since

$\mathrm{id}_{B}\cdot\mathrm{id}_{C}=\mathrm{id}_{B\cap
C}\qquad\text{and}\qquad\mathrm{id}_{B}=\mathrm{id}_{C}\ \Leftrightarrow\
B=C\qquad\text{for all $B,C\leq A$,}$

it follows that $\mathcal{E}_{A}$ is in fact isomorphic to
$\operatorname{Sub}(A)=\\{{B}:{B\leq A}\\}$, considered as an
$\cap$-semilattice.

It is also worth noting that for any algebra $A$,

$T(\operatorname{PEnd}(A))=\\{{\alpha\in\operatorname{PEnd}(A)}:{\alpha^{+}=\mathrm{id}_{A}}\\}=\\{{\alpha\in\operatorname{PEnd}(A)}:{\operatorname{dom}(\alpha)=A}\\}=\operatorname{End}(A).$
(8.18)

For an independence algebra $A$, we also define the subsets

$\displaystyle\operatorname{Sing}(\operatorname{PEnd}(A))$
$\displaystyle=\operatorname{PEnd}(A)\setminus\operatorname{Aut}(A),$
$\displaystyle\operatorname{Sing}(\operatorname{End}(A))$
$\displaystyle=\operatorname{End}(A)\setminus\operatorname{Aut}(A),$
$\displaystyle\operatorname{Sing}(\operatorname{PAut}(A))$
$\displaystyle=\operatorname{PAut}(A)\setminus\operatorname{Aut}(A),$ and we
refer to the elements of these sets as _singular_. These are subsemigroups
(indeed, two-sided ideals) of $\operatorname{PEnd}(A)$,
$\operatorname{End}(A)$ and $\operatorname{PAut}(A)$, respectively, if and
only if $\dim(A)<\aleph_{0}$. On the other hand,
$\displaystyle\operatorname{PEnd}(A)\setminus\operatorname{End}(A)$
$\displaystyle=\\{{\alpha\in\operatorname{PEnd}(A)}:{\operatorname{dom}(\alpha)<A}\\}$
is a subsemigroup (indeed, right ideal) of $\operatorname{PEnd}(A)$,
consisting of all _strictly_ partial endomorphisms, for any algebra $A$.
However, $\displaystyle\operatorname{PEnd}(A)\setminus\operatorname{PAut}(A)$
$\displaystyle=\\{{\alpha\in\operatorname{PEnd}(A)}:{\alpha\text{ is not
injective}}\\}$

is not a subsemigroup if $\dim(A)\geq 3$. For example, let
$\\{x,y,z\\}\subseteq A$ be independent, let $B=\langle x,y\rangle$ and
$C=\langle y,z\rangle$, and consider $\alpha:B\to A$ and $\beta:C\to A$
defined by $x\alpha=y\alpha=x$ and $y\beta=z\beta=y$; then
$\alpha,\beta\in\operatorname{PEnd}(A)\setminus\operatorname{PAut}(A)$, yet
$\alpha\beta=\mathrm{id}_{\mathcal{C}(A)}\in\operatorname{PAut}(A)$.

Now suppose $A$ is an independence algebra. If
$\alpha\in\operatorname{PEnd}(A)$, then the dimension of the subalgebra
$\operatorname{im}(\alpha)\leq A$ is taken as the definition of the _rank_ of
$\alpha$:

$\operatorname{rank}(\alpha)=\dim(\operatorname{im}(\alpha)).$

Note that $0\leq\operatorname{rank}(\alpha)\leq\dim(A)$. We also have

$\operatorname{rank}(\alpha\beta)\leq\min(\operatorname{rank}(\alpha),\operatorname{rank}(\beta))\qquad\text{for
all $\alpha,\beta\in\operatorname{PEnd}(A)$.}$ (8.19)

Indeed, this was proved for $\alpha,\beta\in\operatorname{End}(A)$ in [54,
Lemma 4.1], and the argument there works unmodified for partial endomorphisms.
At times it will also be convenient to speak of the _corank_ of
$\alpha\in\operatorname{PEnd}(A)$, defined by

$\operatorname{corank}(\alpha)=\operatorname{codim}(\operatorname{im}(\alpha)).$

When $\dim(A)=n<\aleph_{0}$, we have

$\displaystyle\operatorname{Aut}(A)$
$\displaystyle=\\{{\alpha\in\operatorname{PEnd}(A)}:{\operatorname{rank}(\alpha)=n}\\}$
$\displaystyle=\\{{\alpha\in\operatorname{End}(A)}:{\operatorname{rank}(\alpha)=n}\\}$
$\displaystyle=\\{{\alpha\in\operatorname{PAut}(A)}:{\operatorname{rank}(\alpha)=n}\\},$

so that
$\operatorname{Sing}(\operatorname{PEnd}(A))=\\{{\alpha\in\operatorname{PEnd}(A)}:{\operatorname{rank}(\alpha)<n}\\}$,
with similar statements for $\operatorname{Sing}(\operatorname{End}(A))$ and
$\operatorname{Sing}(\operatorname{PAut}(A))$.

At this point it is worth recording some observations concerning small ranks
and dimensions.

######  Remark 8.20.

For the duration of this remark, we write
$C=\mathcal{C}(A)=\langle\varnothing\rangle$ for the unique subalgebra of $A$
of dimension $0$. We have already noted that $C$ is non-empty if and only if
$A$ has constants (nullary operations).

  1. (i)

Since every subalgebra of $A$ contains $C$, and since every (partial)
endomorphism fixes each constant, every (partial) endomorphism fixes $C$
pointwise.

  2. (ii)

A (partial) endomorphism has rank $0$ if and only if its image is $C$. It
follows that if $A$ has no constants, then $A$ has no rank-$0$ endomorphisms
(unless $A$ is itself empty). On the other hand, $\mathrm{id}_{C}$ is always a
rank-$0$ _partial_ endomorphism.

  3. (iii)

If $A$ has constants, then any function from a basis of $A$ into $C$ can be
extended to an endomorphism of rank $0$.

  4. (iv)

By (8.19), the sets

$I_{0}=\\{{\alpha\in\operatorname{End}(A)}:{\operatorname{rank}(\alpha)=0}\\}\qquad\text{and}\qquad
J_{0}=\\{{\alpha\in\operatorname{PEnd}(A)}:{\operatorname{rank}(\alpha)=0}\\}$

are ideals of $\operatorname{End}(A)$ and $\operatorname{PEnd}(A)$. As above
$I_{0}=\varnothing$ if $A$ is non-empty and has no constants; in this case we
also have $J_{0}=\\{\mathrm{id}_{C}=\mathrm{id}_{\varnothing}=\varnothing\\}$.

  5. (v)

If $\alpha\in J_{0}$ and $\beta\in\operatorname{PEnd}(A)$, then since $\beta$
fixes $C=\operatorname{im}(\alpha)$ pointwise, $\alpha\beta=\alpha$. That is,
each element of $J_{0}$ is a left zero for $\operatorname{PEnd}(A)$.
Consequently, the ideals $I_{0}$ and $J_{0}$ are left zero semigroups.

  6. (vi)

If $\dim(A)=0$, then $A=C$ and
$\operatorname{PEnd}(A)=\operatorname{End}(A)=\operatorname{PAut}(A)=\operatorname{Aut}(A)=\\{\mathrm{id}_{A}\\}$.

  7. (vii)

If $\dim(A)=1$, then

$\displaystyle\operatorname{End}(A)$ $\displaystyle=\operatorname{Aut}(A)\cup
I_{0},$ $\displaystyle\operatorname{PEnd}(A)$
$\displaystyle=\operatorname{Aut}(A)\cup
J_{0}=\operatorname{End}(A)\cup\\{\mathrm{id}_{C}\\},$
$\displaystyle\operatorname{PAut}(A)$
$\displaystyle=\operatorname{Aut}(A)\cup\\{\mathrm{id}_{C}\\}.$

In particular, if $\dim(A)=1$ and $A$ has no constants, then $C=\varnothing$,
$I_{0}=\varnothing$ and

$\operatorname{End}(A)=\operatorname{Aut}(A)\qquad\text{and}\qquad\operatorname{PEnd}(A)=\operatorname{PAut}(A)=\operatorname{Aut}(A)\cup\\{\varnothing\\}.$

It will also be convenient to prove the following:

######  Lemma 8.21.

For any independence algebra $A$, the following are equivalent:

  1. (i)

$\operatorname{End}(A)=\operatorname{Aut}(A)$,

  2. (ii)

$\operatorname{Sing}(\operatorname{End}(A))=\varnothing$,

  3. (iii)

$\dim(A)=0$ or $[\dim(A)=1$ and $A$ has no constants$]$.

###### Proof.

Clearly (i) and (ii) are equivalent.

(iii)$\ \Rightarrow\ $(i). This implication was covered in items (vi) and
(vii) of Remark 8.20.

(i)$\ \Rightarrow\ $(iii). Aiming to prove the contrapositive, suppose (iii)
does not hold, so that either $\dim(A)\geq 2$ or else $\dim(A)=1$ and $A$ has
constants. In either case, there exists $x\in A$ such that $\langle
x\rangle<A$. It follows that for any basis $X$ of $A$, the endomorphism
$\alpha$ extending the constant map $X\to\\{x\\}$ is not an automorphism. ∎

####  8.3 Maximal subalgebras

In this section we prove a number of results concerning maximal (proper)
subalgebras of an independence algebra $A$. These will be used in a number of
places in the remainder of Chapter 8. We denote the set of all maximal
subalgebras of $A$ by $\operatorname{Max}(A)$.

######  Proposition 8.22.

For a proper subalgebra $B$ of an independence algebra $A$, the following are
equivalent:

  1. (i)

$A=\langle B\sqcup x\rangle$ for some $x\in A\setminus B$,

  2. (ii)

$A=\langle B\sqcup x\rangle$ for all $x\in A\setminus B$ (i.e., $B$ is
maximal),

  3. (iii)

$\operatorname{codim}(B)=1$.

Consequently, $\operatorname{Max}(A)=\\{{B\leq
A}:{\operatorname{codim}(A)=1}\\}$.

###### Proof.

(i)$\ \Rightarrow\ $(ii). Suppose $A=\langle B\sqcup x\rangle$ for some $x\in
A\setminus B$, and let $y\in A\setminus B$ be arbitrary; we must show that
$A=\langle B\sqcup y\rangle$. But $y\in A\setminus B=\langle B\sqcup
x\rangle\setminus\langle B\rangle$, so (EP) gives $x\in\langle B\sqcup
y\rangle$. It then follows that $A=\langle B\sqcup x\rangle\subseteq\langle
B\sqcup y\rangle$.

(ii)$\ \Rightarrow\ $(iii). Since $B<A$, we have $\operatorname{codim}(B)\geq
1$. It follows directly from (ii) that $\operatorname{codim}(B)\leq 1$.

(iii)$\ \Rightarrow\ $(i). This is clear. ∎

In particular, if $\dim(A)=n<\aleph_{0}$, then
$\operatorname{Max}(A)=\\{{B\leq A}:{\dim(B)=n-1}\\}$, as observed in Section
8.1. Our next result shows that every finite-codimensional subalgebra of $A$
is a finite intersection of maximal subalgebras. In the statement, the
expression $C_{1}\cap\cdots\cap C_{k}$ is understood to represent $A$ if
$k=0$: i.e., if the list $C_{1},\ldots,C_{k}$ is empty.

######  Lemma 8.23.

Let $A$ be an independence algebra, and let $B\leq A$ with
$\operatorname{codim}(B)=k<\aleph_{0}$. Then $B=C_{1}\cap\cdots\cap C_{k}$ for
some $C_{1},\ldots,C_{k}\in\operatorname{Max}(A)$.

###### Proof.

Let $X$ be a basis of $B$, and $\\{y_{1},\ldots,y_{k}\\}$ a $B$-basis of $A$,
so that $Y=X\sqcup\\{y_{1},\ldots,y_{k}\\}$ is a basis of $A$ by Lemma 8.7.
For each $1\leq i\leq k$, let $C_{i}=\langle Y\setminus y_{i}\rangle$; it
follows from Proposition 8.22 that each $C_{i}$ is maximal. We will show by
induction on $k$ that $B=C_{1}\cap\cdots\cap C_{k}$. This is vacuously true
for $k=0$, so we assume that $k\geq 1$.

Let $X^{\prime}=X\sqcup y_{k}$, and put $B^{\prime}=\langle
X^{\prime}\rangle$, so that $\operatorname{codim}(B^{\prime})=k-1$, and
$Y=X^{\prime}\sqcup\\{y_{1},\ldots,y_{k-1}\\}$. It follows inductively that
$B^{\prime}=C_{1}\cap\cdots\cap C_{k-1}$, so it remains to show that
$B=B^{\prime}\cap C_{k}$. From $X\subseteq X^{\prime}$ and $X\subseteq
Y\setminus y_{k}$, we have $B\subseteq B^{\prime}$ and $B\subseteq C_{k}$, so
that $B\leq B^{\prime}\cap C_{k}\leq B^{\prime}$. Since $B^{\prime}=\langle
B\sqcup y_{k}\rangle$, it follows from Proposition 8.22 that $B$ is maximal in
$B^{\prime}$, so we can complete the proof that $B=B^{\prime}\cap C_{k}$ by
showing that $B^{\prime}\cap C_{k}<B^{\prime}$. But this is clear: we
obviously have $y_{k}\in B^{\prime}$, yet $y_{k}\not\in\langle Y\setminus
y_{k}\rangle=C_{k}$, as $Y$ is independent. ∎

######  Remark 8.24.

In the case that $\dim(A)<\aleph_{0}$, it follows from Lemma 8.23 that
$\operatorname{Sub}(A)$ is generated (as an $\cap$-monoid) by the set
$\operatorname{Max}(A)$. We will see in Proposition 8.39 that
$\operatorname{Max}(A)$ is in fact the unique minimum generating set.
Actually, Proposition 8.39 also treats the case that $A$ is infinite-
dimensional and strong, but with $\operatorname{Sub}(A)$ replaced by the
lattice of finite-codimensional subalgebras.

For subalgebras of arbitrary codimension we have the following:

######  Lemma 8.25.

If $A$ is an independence algebra, and if $B\leq A$, then

$B=\bigcap_{C\in\Sigma}C\qquad\text{where}\qquad\Sigma=\\{{C\in\operatorname{Max}(A)}:{B\leq
C}\\}.$

###### Proof.

Write $D=\bigcap_{C\in\Sigma}C$. Since $B\leq C$ for each $C\in\Sigma$,
certainly $B\leq D$.

To show that $D\leq B$, it suffices to show that $A\setminus B\subseteq
A\setminus D$, so fix some $y\in A\setminus B$. We will show that $y\not\in D$
by finding $C\in\Sigma$ such that $y\not\in C$. Fix a basis $X$ of $B$, so
that $X\sqcup y$ is independent, by Lemma 8.2. Extend $X\sqcup y$ to a basis
$X\sqcup y\sqcup Z$ of $A$, and define $C=\langle X\sqcup Z\rangle$. By
Proposition 8.22, $C$ is maximal, and certainly $B=\langle X\rangle\subseteq
C$, so that $C\in\Sigma$. Since $X\sqcup y\sqcup Z$ is independent,
$y\not\in\langle X\sqcup Z\rangle=C$. ∎

The next result concerns the situation in which $A$ has subalgebras missing
only one element, and shows that this is an extremely restrictive property.
Since every subalgebra contains $\mathcal{C}(A)$, we could only possibly have
$A\setminus x\leq A$ if $x\not\in\mathcal{C}(A)$. Such an element $x$ could
only exist if $A\not=\mathcal{C}(A)$: i.e., if $\dim(A)\not=0$.

######  Proposition 8.26.

Let $A$ be an independence algebra with $\dim(A)\not=0$, and write
$C=\mathcal{C}(A)$ and $X=A\setminus C$. Then the following are equivalent:

  1. (i)

$A\setminus x\leq A$ for some $x\in X$,

  2. (ii)

$A\setminus x\leq A$ for all $x\in X$,

  3. (iii)

$X$ is independent,

  4. (iv)

$X$ is the unique basis of $A$,

  5. (v)

$\operatorname{Sub}(A)=\\{{B}:{C\subseteq B\subseteq A}\\}$,

  6. (vi)

$\operatorname{Max}(A)=\\{{A\setminus x}:{x\in X}\\}$.

###### Proof.

(i)$\ \Rightarrow\ $(ii). Suppose $A\setminus x\leq A$ for some $x\in X$, and
let $y\in X$ be arbitrary; we must show that $A\setminus y\leq A$. Since
$x,y\not\in C$, we may extend $x$ and $y$ to bases $U\sqcup x$ and $V\sqcup y$
for $A$, noting that $|U|=|V|$. We then let $\alpha$ be the endomorphism of
$A$ extending any bijection $U\sqcup x\to V\sqcup y$ that maps $x\mapsto y$.
Then $\alpha$ is an automorphism (as it maps a basis bijectively to a basis),
and since $A\setminus x\leq A$, it follows that $A\setminus y=(A\setminus
x)\alpha\leq A$.

(ii)$\ \Rightarrow\ $(iii). If we had $x\in\langle X\setminus x\rangle$ for
some $x\in X$, then since $A\setminus x\leq A$, it would follow that
$x\in\langle X\setminus x\rangle\subseteq\langle A\setminus
x\rangle=A\setminus x$, a contradiction.

(iii)$\ \Rightarrow\ $(iv). If $X$ is independent, then it is clearly the
maximum independent subset of $A$.

(iv)$\ \Rightarrow\ $(v). Since every subalgebra contains $C$, it suffices to
show that $B\leq A$ for any $C\subseteq B\subseteq A$, so fix some such $B$.
To show that $B\leq A$, it suffices to show that no element of $A\setminus B$
belongs to $\langle B\rangle$. But for any $x\in A\setminus B$, we have
$(B\setminus C)\sqcup x\subseteq A\setminus C=X$. Since $X$ is independent, so
too is $(B\setminus C)\sqcup x$. Thus, $x\not\in\langle B\setminus
C\rangle=\langle B\rangle$.

(v)$\ \Rightarrow\ $(vi) and (vi)$\ \Rightarrow\ $(i). These are both clear. ∎

Consider an independence algebra $A$, and again write $C=\mathcal{C}(A)$ and
$X=A\setminus C$. Any automorphism of $A$ fixes $C$ pointwise, and is
therefore of the form $\mathrm{id}_{C}\cup\alpha$ for some permutation
$\alpha\in\mathcal{G}_{X}$. It follows that $\operatorname{Aut}(A)$ is a
subgroup of $\\{{\mathrm{id}_{C}\cup\alpha}:{\alpha\in\mathcal{G}_{X}}\\}$,
and the latter is of course isomorphic to $\mathcal{G}_{X}$. It turns out that
the conditions of Proposition 8.26 lead to the greatest ‘freedom’ in
automorphisms, in the sense that $\operatorname{Aut}(A)$ is precisely this
copy of $\mathcal{G}_{X}$. Indeed, if $X$ is a basis for $A$, then any
permutation $\alpha\in\mathcal{G}_{X}$ extends to an automorphism (cf. Lemma
8.3), which must be $\mathrm{id}_{C}\cup\alpha$. However, it turns out that
$X$ being independent is not (quite) necessary for this ‘maximum freedom’ to
occur, and the next result characterises the algebras for which it does.

######  Proposition 8.27.

Let $A$ be an independence algebra with $\dim(A)\not=0$, and write
$C=\mathcal{C}(A)$ and $X=A\setminus C$. Then the following are equivalent:

  1. (i)

$X\setminus x$ is independent for some $x\in X$,

  2. (ii)

$X\setminus x$ is independent for all $x\in X$,

  3. (iii)

$\operatorname{Aut}(A)=\\{{\mathrm{id}_{C}\cup\alpha}:{\alpha\in\mathcal{G}_{X}}\\}$.

When the above conditions hold, we have
$\operatorname{Aut}(A)\cong\mathcal{G}_{X}$.

###### Proof.

If $X$ is independent, then all three conditions hold, so we assume otherwise
for the rest of the proof. In particular, it follows from Proposition 8.26
that $A\setminus x\not\leq A$ for all $x\in A$.

(i)$\ \Rightarrow\ $(ii). Suppose $X\setminus x$ is independent for some $x\in
X$, and let $y\in X$ be arbitrary; we must show that $X\setminus y$ is
independent. This is clear if $x=y$, so suppose otherwise, and write
$U=X\setminus\\{x,y\\}$. Since $U\sqcup y=X\setminus x$ is independent we have
$y\not\in\langle U\rangle$.

Next we claim that $x\not\in\langle U\rangle$. To prove this, suppose to the
contrary that $x\in\langle U\rangle$. Then $\langle U\rangle=\langle U\sqcup
x\rangle=\langle C\sqcup U\sqcup x\rangle=\langle A\setminus y\rangle=A$,
since $A\setminus y\not\leq A$. It follows that $y\in A=\langle U\rangle$, a
contradiction. Now that the claim has been proved, it follows from Lemma 8.2
(and the fact that $U$ is independent) that $U\sqcup x$ is independent. But
$U\sqcup x=X\setminus y$, so we are done.

(ii)$\ \Rightarrow\ $(iii). It suffices to show that
$\mathrm{id}_{C}\cup\alpha$ is an automorphism for any
$\alpha\in\mathcal{G}_{X}$. To do so, fix some such $\alpha$, and let
$Y=X\setminus x$ for any $x\in X$. Since $Y$ is independent, and $X$ is not,
it follows that $Y$ is a basis of $A$. Since $\alpha\in\mathcal{G}_{X}$, we
have $Y\alpha=X\setminus x\alpha$, and again this is a basis. It follows from
Lemma 8.3 that the unique endomorphism $\gamma$ of $A$ extending
$\alpha\mathord{\restriction}_{Y}$ is an automorphism. But
$\gamma\mathord{\restriction}_{C}=\mathrm{id}_{C}$ and
$\gamma\mathord{\restriction}_{Y}=\alpha\mathord{\restriction}_{Y}$, so
$\gamma$ and $\mathrm{id}_{C}\cup\alpha$ agree on $C\cup Y=A\setminus x$.
Since $\gamma$ and $\mathrm{id}_{C}\cup\alpha$ agree on the basis $Y$ of $A$,
it follows that $\gamma=\mathrm{id}_{C}\cup\alpha$. This completes the proof
that $\mathrm{id}_{C}\cup\alpha$ is an automorphism.

(iii)$\ \Rightarrow\ $(i). Aiming to prove the contrapositive, we assume that
(i) does not hold; we must show that
$\mathrm{id}_{C}\cup\alpha\not\in\operatorname{Aut}(A)$ for some
$\alpha\in\mathcal{G}_{X}$. Fix a basis $Y$ of $A$. So $Y\subseteq X$, and by
assumption $|X\setminus Y|\geq 2$. The only automorphism extending
$\mathrm{id}_{Y}$ is $\mathrm{id}_{A}=\mathrm{id}_{C}\cup\mathrm{id}_{X}$. So
we may take $\alpha\in\mathcal{G}_{X}$ to be any permutation that maps $Y$
identically, but permutes $X\setminus Y$ non-trivially. ∎

######  Remark 8.28.

One may wonder how the conditions of Proposition 8.27 relate to the monoids
$\operatorname{End}(A)$, $\operatorname{PEnd}(A)$ and
$\operatorname{PAut}(A)$, and to what extent these have the same ‘freedom’ as
$\operatorname{Aut}(A)$, as discussed above. We will treat
$\operatorname{PAut}(A)$ in the next result. The situation for the other two
monoids is a little more complex, as (partial) endomorphisms can map elements
of $X$ into $C$, in the above notation. But, for example, when $X$ is
independent (so the conditions of Proposition 8.26 are satisfied), a
transformation $\alpha$ of $A$ belongs to $\operatorname{End}(A)$ if and only
if $\alpha$ fixes $C$ pointwise, so that

$\operatorname{End}(A)=\\{{\alpha\in\mathcal{T}_{A}}:{\alpha\mathord{\restriction}_{C}=\mathrm{id}_{C}}\\}.$

These submonoids of $\mathcal{T}_{A}$ have been studied extensively, and are
typically denoted $\operatorname{Fix}(A,C)$; see for example [63]. In the case
that $C=\varnothing$ we of course have
$\operatorname{End}(A)=\mathcal{T}_{A}$. If $|C|=1$, say with $C=\\{c\\}$,
then $\operatorname{End}(A)\cong\mathcal{P}\mathcal{T}_{X}$, via the standard
trick of identifying a partial transformation $\alpha$ of $X$ with the
transformation of $A=X\sqcup c$ mapping as $\alpha$ on
$\operatorname{dom}(\alpha)$, and sending all elements of
$A\setminus\operatorname{dom}(\alpha)$ to $c$.

Here is the promised version of Proposition 8.27, concerning ‘maximum freedom’
for _partial_ automorphisms.

######  Proposition 8.29.

Let $A$ be an independence algebra, and write $C=\mathcal{C}(A)$ and
$X=A\setminus C$. Then the following are equivalent:

  1. (i)

$X$ is independent,

  2. (ii)

$\operatorname{PAut}(A)=\\{{\mathrm{id}_{C}\cup\alpha}:{\alpha\in\mathcal{I}_{X}}\\}$.

When the above conditions hold, we have
$\operatorname{PAut}(A)\cong\mathcal{I}_{X}$.

###### Proof.

The result is trivial if $\dim(A)=0$, as then $X=\varnothing$, so we assume
that $\dim(A)\not=0$.

(i)$\ \Rightarrow\ $(ii). Since any element of $\operatorname{PAut}(A)$ is
injective and maps $C$ identically, the forwards containment always holds.
Conversely, let $\alpha\in\mathcal{I}_{X}$, and write
$B=\operatorname{dom}(\alpha)$ and $D=\operatorname{im}(\alpha)$. We must show
that $\mathrm{id}_{C}\cup\alpha\in\operatorname{PAut}(A)$; in fact, since
$\mathrm{id}_{C}\cup\alpha$ is obviously injective, it is enough to check that
it is a morphism $C\cup B\to C\cup D$. Now, $C\cup B,C\cup D\leq A$ by
Proposition 8.26. Since $B$ is independent (as $X$ is), it is a basis for
$C\cup B$, so there is therefore a unique morphism $C\cup B\to C\cup D$
extending $\alpha:B\to D$, and this is of course $\mathrm{id}_{C}\cup\alpha$.

(ii)$\ \Rightarrow\ $(i). By Proposition 8.26 it suffices to show that $B\leq
A$ for any $C\subseteq B\subseteq A$. But for any such $B$ we have
$\mathrm{id}_{B}=\mathrm{id}_{C}\cup\mathrm{id}_{B\setminus
C}\in\operatorname{PAut}(A)$, so that
$B=\operatorname{dom}(\mathrm{id}_{B})\leq A$. ∎

We have already noted that the conditions in Proposition 8.26 imply those in
Proposition 8.27. The next result concerns algebras that satisfy the latter
but not the former. An example of such an algebra is the two-dimensional
vector space over the two-element field; another example is the one from [48]
discussed in Remark 8.11; see also Proposition 8.32 below.

######  Proposition 8.30.

Let $A$ be an independence algebra with $\dim(A)\not=0$, write
$C=\mathcal{C}(A)$ and $X=A\setminus C$, and suppose $A$ does not satisfy the
conditions of Proposition 8.26. Then the following are equivalent:

  1. (i)

$X\setminus x$ is independent for some $x\in X$,

  2. (ii)

$X\setminus x$ is independent for all $x\in X$,

  3. (iii)

$A\setminus\\{x,y\\}\leq A$ for all $x,y\in X$ with $x\not=y$,

  4. (iv)

$\operatorname{Sub}(A)=\\{{B}:{C\subseteq B\subseteq A,\ |A\setminus
B|\not=1}\\}$,

  5. (v)

$\operatorname{Max}(A)=\\{{A\setminus\\{x,y\\}}:{x,y\in X,\ x\not=y}\\}$.

###### Proof.

(i)$\ \Leftrightarrow\ $(ii). This was proved in Proposition 8.27.

(ii)$\ \Rightarrow\ $(iv). Since $A$ does not satisfy the conditions of
Proposition 8.26, it has no subalgebras missing just one element. This gives
the forwards containment.

Conversely, suppose $C\subseteq B\subseteq A$ is such that $|A\setminus
B|\not=1$; we must show that $B\leq A$. If $|A\setminus B|=0$ then $B=A\leq
A$, so suppose instead that $|A\setminus B|\geq 2$. Aiming for a
contradiction, suppose $B\not\leq A$, so that $x\in\langle B\rangle$ for some
$x\in A\setminus B$. Since $|A\setminus B|\geq 2$, we may fix another element
$y\in A\setminus B$. Since $x,y\not\in B$ and $C\subseteq B$, we have $x,y\in
X$. Then $x\in\langle B\rangle=\langle B\setminus
C\rangle\subseteq\big{\langle}X\setminus\\{x,y\\}\big{\rangle}$; but this
implies that $X\setminus y$ is not independent, and contradicts (ii).

(iv)$\ \Rightarrow\ $(v) and (v)$\ \Rightarrow\ $(iii). These are clear.

(iii)$\ \Rightarrow\ $(ii). Aiming to prove the contrapositive, suppose
$X\setminus x$ is not independent for some $x\in X$, so that
$y\in\big{\langle}X\setminus\\{x,y\\}\big{\rangle}$ for some $y\in X\setminus
x$. But then
$y\in\big{\langle}X\setminus\\{x,y\\}\big{\rangle}\subseteq\big{\langle}A\setminus\\{x,y\\}\big{\rangle}$,
so that $A\setminus\\{x,y\\}\not\leq A$. ∎

######  Remark 8.31.

Comparing Propositions 8.26 and 8.30, one might wonder why the following
condition was not listed in the latter:

  * •

$A\setminus\\{x,y\\}\leq A$ for _some_ $x,y\in X$ with $x\not=y$.

The reason is that this is strictly weaker than condition (iii) of Proposition
8.30 in general.

For example, let $A=\\{a,b,c,d\\}$ with a single unary operation mapping
$a\leftrightarrow b$ and $c\leftrightarrow d$. Then $A$ is an independence
algebra (it is term-equivalent to the free two-dimensional
$\mathcal{G}_{2}$-act, as in Example 9.9), and it is easy to see that the
lattice $\operatorname{Sub}(A)$ is as follows:

$A$$\\{a,b\\}$$\\{c,d\\}$$\varnothing$

In particular, $\\{a,b\\}$ and $\\{c,d\\}$ are the only two-element
subalgebras of $A$. This means that condition (iii) of Proposition 8.30 fails,
even though the above weaker condition holds. The conditions of Propositions
8.26 and 8.27 also fail for $A$.

Because of this, it follows from Proposition 8.27 that $\operatorname{Aut}(A)$
is a proper subgroup of $\mathcal{G}_{A}$ (note that
$X=A\setminus\mathcal{C}(A)=A$ since $A$ has no nullary operations), and we
can also see this by direct computation. Indeed, any basis of $A$ contains one
element each from $\\{a,b\\}$ and $\\{c,d\\}$, and it follows that
$\operatorname{Aut}(A)$ consists precisely of the following permutations,
which are specified in two ways, by indicating the action on the basis
$\\{a,c\\}$, and in standard cycle notation:

$\displaystyle\mathrm{id}_{A}=\left(\begin{smallmatrix}a&c\\\
a&c\end{smallmatrix}\right),$ $\displaystyle\alpha_{1}$
$\displaystyle=\left(\begin{smallmatrix}a&c\\\
b&c\end{smallmatrix}\right)=(a,b),$ $\displaystyle\beta_{1}$
$\displaystyle=\left(\begin{smallmatrix}a&c\\\
c&a\end{smallmatrix}\right)=(a,c)(b,d),$ $\displaystyle\alpha_{2}$
$\displaystyle=\left(\begin{smallmatrix}a&c\\\
a&d\end{smallmatrix}\right)=(c,d),$ $\displaystyle\beta_{2}$
$\displaystyle=\left(\begin{smallmatrix}a&c\\\
c&b\end{smallmatrix}\right)=(a,c,b,d),$ $\displaystyle\alpha_{3}$
$\displaystyle=\left(\begin{smallmatrix}a&c\\\
b&d\end{smallmatrix}\right)=(a,b)(c,d),$ $\displaystyle\beta_{3}$
$\displaystyle=\left(\begin{smallmatrix}a&c\\\
d&b\end{smallmatrix}\right)=(a,d)(b,c),$ $\displaystyle\beta_{4}$
$\displaystyle=\left(\begin{smallmatrix}a&c\\\
d&a\end{smallmatrix}\right)=(a,d,b,c).$

Consequently, $\operatorname{Aut}(A)$ is dihedral of order $8$, or
equivalently a wreath product $\mathcal{G}_{2}\wr\mathcal{G}_{2}$ (see Chapter
9).

We have already noted that the two-dimensional vector space over the two-
element field satisfies the conditions of Proposition 8.27 but not those of
Proposition 8.26. The next result shows that this is unusual among such
examples, as it is strong; note that $|X|=3$ for this example.

######  Proposition 8.32.

Let $A$ be an independence algebra, write $C=\mathcal{C}(A)$ and $X=A\setminus
C$, and suppose $|X|\geq 4$. If $A$ satisfies the conditions of Proposition
8.27 but not those of Proposition 8.26, then $A$ is not strong.

###### Proof.

Fix a partition $X=Y\sqcup Z$ where $|Y|,|Z|\geq 2$. Then $Y$ and $Z$ are both
independent (as $X\setminus x$ is independent for all $x\in X$). By
Proposition 8.30, $C\cup Y=A\setminus Z\leq A$, so $\langle Y\rangle=\langle
C\cup Y\rangle=C\cup Y$, and similarly $\langle Z\rangle=C\cup Z$. Certainly
then $\langle Y\rangle\cap\langle Z\rangle=C$, yet $Y\cup Z=X$ is not
independent. ∎

######  Remark 8.33.

By contrast, if $A$ satisfies the conditions of Proposition 8.26, then $A$ is
trivially strong, for then the independent sets are just the subsets of
$X=A\setminus\mathcal{C}(A)$.

If the conditions of Proposition 8.26 hold for an independence algebra $A$,
then it quickly follows that $A$ is equal to the union of any two distinct
maximal subalgebras. In Section 8.5 we will be concerned with the case in
which this never happens. In fact, we only need a weaker assumption, but the
next result shows that these are equivalent when $A$ is strong.

######  Lemma 8.34.

Let $A$ be an independence algebra, and consider the following two conditions:

  1. (i)

for any $B,C\in\operatorname{Max}(A)$, we have $B\cup C\not=A$,

  2. (ii)

for any basis $X$ of $A$, and for any $x,y\in X$, we have $\langle X\setminus
x\rangle\cup\langle X\setminus y\rangle\not=A$.

Then (i)$\ \Rightarrow\ $(ii). If $A$ is strong, then (i)$\ \Leftrightarrow\
$(ii)

###### Proof.

By Proposition 8.22, $\langle X\setminus x\rangle$ is maximal for any basis
$X$ of $A$ and any $x\in X$, so it is clear that (i)$\ \Rightarrow\ $(ii).

We now assume that $A$ is strong, and that (ii) holds. Let
$B,C\in\operatorname{Max}(A)$ be arbitrary; we must show that $B\cup C\not=A$.
This is clear if $B=C$, so suppose $B\not=C$. Together with maximality it
follows that $B\not\subseteq C$ and $C\not\subseteq B$, and also that $B\vee
C=A$. From the latter, we have $\operatorname{codim}(B\vee C)=0$, so it
follows from Lemma 8.13(ii) and Proposition 8.22 that
$\operatorname{codim}(B\cap C)=2$.

Fix a basis $U$ for $B\cap C$, and extend this to bases $U\sqcup Y$ and
$U\sqcup Z$ for $B$ and $C$, respectively. Since $B\not=C$ we have $|Y|\geq 1$
and $|Z|\geq 1$. By Lemma 8.12, $U\sqcup Y\sqcup Z$ is a basis of $B\vee C=A$.
But then $|Y|+|Z|=\operatorname{codim}(B\cap C)=2$, so in fact $|Y|=|Z|=1$,
and we may write $Y=\\{y\\}$ and $Z=\\{z\\}$. This all shows that
$X=U\sqcup\\{y,z\\}$ is a basis of $A$. We also have $B=\langle U\sqcup
y\rangle=\langle X\setminus z\rangle$, and similarly $C=\langle X\setminus
y\rangle$. It then follows from (ii) that $B\cup C=\langle X\setminus
z\rangle\cup\langle X\setminus y\rangle\not=A$. ∎

######  Remark 8.35.

The algebra $A$ from [48] discussed in Remark 8.11 satisfies condition (ii) of
Lemma 8.34, but not (i). Indeed, each two-element subalgebra is maximal, and
for example ${A=\\{a_{1},a_{2}\\}\cup\\{a_{3},a_{4}\\}}$. However, any basis
has the form $X=\\{a_{i},a_{j},a_{k}\\}$ for distinct $i,j,k$, and $\langle
X\setminus x\rangle\cup\langle X\setminus y\rangle=(X\setminus
x)\cup(X\setminus y)\subseteq X\not=A$ for any $x,y\in X$.

######  Remark 8.36.

We have already noted that the conditions in Proposition 8.26 and Lemma 8.34
are mutually exclusive. They are not, however, exhaustive. For example, let
$A$ be the four-element algebra from Remark 8.31. We have already observed
that $A$ does not satisfy the conditions in Proposition 8.26. On the other
hand, the maximal subalgebras of $A$ are precisely $B=\\{a,b\\}$ and
$C=\\{c,d\\}$, and of course $B\cup C=A$. In fact, $B=\langle X\setminus
c\rangle$ and $C=\langle X\setminus a\rangle$ for the basis $X=\\{a,c\\}$.
Thus, $A$ does not satisfy either of the conditions of Lemma 8.34. (This
extends to arbitrary free $G$-acts of dimension $\geq 2$ for non-trivial $G$.)

######  Remark 8.37.

Any vector space $A$ of dimension $\geq 2$ satisfies the conditions of Lemma
8.34. Indeed, if $X$ is a basis, and if $x,y\in X$ are distinct, then
$x+y\not\in\langle X\setminus x\rangle\cup\langle X\setminus y\rangle$. (To
see this, note that if $x+y\in\langle X\setminus x\rangle$, then since also
$y\in X\setminus x$, we would have $x=(x+y)-y\in\langle X\setminus x\rangle$,
contradicting independence of $X$.)

It follows that such a vector space $A$ cannot satisfy the conditions of
Proposition 8.26. The only such $A$ satisfying the conditions of Proposition
8.27 is two-dimensional over the two-element field, which we have already
discussed.

####  8.4 Finite-codimensional subalgebras

The previous section concerned maximal subalgebras of an independence algebra
$A$: i.e., subalgebras of codimension $1$; cf. Proposition 8.22. We now
consider the more general case of subalgebras of arbitrary finite codimension,
the set of which we denote by

$\operatorname{Sub}^{\operatorname{f}}(A)=\\{{B\leq
A}:{\operatorname{codim}(B)<\aleph_{0}}\\}.$

Our first result shows that $\operatorname{Sub}^{\operatorname{f}}(A)$ is a
sublattice of $\operatorname{Sub}(A)$ in the case that $A$ is finite-
dimensional or strong, and Theorem 8.40 gives a presentation for
$\operatorname{Sub}^{\operatorname{f}}(A)$ in this case, considered as an
$\cap$-semilattice.

######  Lemma 8.38.

Let $A$ be an independence algebra, and let
$B,C\in\operatorname{Sub}^{\operatorname{f}}(A)$. Then

  1. (i)

$B\vee C\in\operatorname{Sub}^{\operatorname{f}}(A)$,

  2. (ii)

$B\cap C\in\operatorname{Sub}^{\operatorname{f}}(A)$ if $A$ is finite-
dimensional or strong.

###### Proof.

(i). This follows immediately from Lemma 8.9(i), as $B\leq B\vee C\leq A$ and
$\operatorname{codim}(B)<\aleph_{0}$.

(ii). Since $\operatorname{Sub}^{\operatorname{f}}(A)=\operatorname{Sub}(A)$
when $\dim(A)<\aleph_{0}$, we only need to consider the case that $A$ is
strong. But here Lemma 8.13(ii) gives $\operatorname{codim}(B\cap
C)\leq\operatorname{codim}(B)+\operatorname{codim}(C)<\aleph_{0}$. ∎

Recall that $\operatorname{Max}(A)=\\{{B\leq
A}:{\operatorname{codim}(B)=1}\\}$ is the set of maximal subalgebras of $A$.

######  Proposition 8.39.

If $A$ is a finite-dimensional or strong independence algebra, then
$\operatorname{Max}(A)$ is the (unique) minimum monoid generating set for
$\operatorname{Sub}^{\operatorname{f}}(A)$, considered as an
$\cap$-semilattice.

###### Proof.

It follows immediately from Lemma 8.23 that $\operatorname{Max}(A)$ is a
generating set.

It remains to show that any generating set for
$\operatorname{Sub}^{\operatorname{f}}(A)$ contains $\operatorname{Max}(A)$,
and for this it suffices to show that every element of $\operatorname{Max}(A)$
is an atom. To do so, suppose $B=C\cap D$, with $B\in\operatorname{Max}(A)$
and $C,D\in\operatorname{Sub}^{\operatorname{f}}(A)$; we must show that
$B\in\\{C,D\\}$. If $C=A$, then $B=A\cap D=D$. Otherwise, $B=C\cap D\leq C<A$,
so $B=C$ by maximality. ∎

Now that we know $\operatorname{Sub}^{\operatorname{f}}(A)$ contains a unique
minimum generating set (when $A$ is finite-dimensional or strong), this is of
course the generating set we wish to use in constructing a presentation. We
can do this in the case that $A$ is assumed to be strong. We begin by defining
an alphabet

$X_{E}=\big{\\{}{x_{B}}:{B\in\operatorname{Max}(A)}\big{\\}}$

in one-one correspondence with $\operatorname{Max}(A)$. (The reason for
choosing the $E$ subscript will become clear in later sections.) By
Proposition 8.39 we have a surmorphism

$\Phi_{E}:X_{E}^{*}\to\operatorname{Sub}^{\operatorname{f}}(A):x_{B}\mapsto
B.$

We define the set of relations $R_{E}=R_{E}^{1}\cup R_{E}^{2}\cup R_{E}^{3}$,
where

$\displaystyle R_{E}^{1}$
$\displaystyle=\big{\\{}{(x_{B}^{2},x_{B})}:{B\in\operatorname{Max}(A)}\big{\\}},$
$\displaystyle R_{E}^{2}$
$\displaystyle=\big{\\{}{(x_{B}x_{C},x_{C}x_{B})}:{B,C\in\operatorname{Max}(A)}\big{\\}},$
$\displaystyle R_{E}^{3}$
$\displaystyle=\big{\\{}{(x_{B}x_{C},x_{B}x_{D})}:{B,C,D\in\operatorname{Max}(A),\
B\cap C=B\cap D}\big{\\}}.$

It is clear that $R_{E}\subseteq\ker(\Phi_{E})$.

######  Theorem 8.40.

If $A$ is a strong independence algebra, then with the above notation,
$\operatorname{Sub}^{\operatorname{f}}(A)$ has presentation
$\textup{{Mon}}\langle{X_{E}}:{R_{E}}\rangle$ via $\Phi_{E}$.

###### Proof.

We begin with three technical lemmas, the first of which is rather simple. The
second may appear to be _exceedingly_ technical, but it turns out to be
exactly what we need in the proof of the third, which leads to a swift
conclusion to the proof of the theorem.

######  Lemma 8.41.

If $B\leq A$ and $C\in\operatorname{Max}(A)$, then
$\operatorname{codim}(B)\leq\operatorname{codim}(B\cap
C)\leq\operatorname{codim}(B)+1$.

###### Proof.

By Lemma 8.13(ii) and Proposition 8.22, we have

$\operatorname{codim}(B\vee C)+\operatorname{codim}(B\cap
C)=\operatorname{codim}(B)+1.$

Since $C\leq B\vee C\leq A$, Lemma 8.9(i) gives
$0\leq\operatorname{codim}(B\vee C)\leq 1$, and the result follows. ∎

######  Lemma 8.42.

If $B,C\in\operatorname{Max}(A)$ and
$D\in\operatorname{Sub}^{\operatorname{f}}(A)$ are such that $B\not=C$,
$D\not\subseteq B$ and $D\cap C\subseteq B$, then there exists
$B^{\prime}\in\operatorname{Max}(A)$ such that $D\subseteq B^{\prime}$ and
$C\cap B=C\cap B^{\prime}$.

###### Proof.

We first claim that $D\cap B=D\cap C$. To prove this, first note that $D\cap
C\not=D$ (as $D\not\subseteq B$ but $D\cap C\subseteq B$), so Lemma 8.41 gives
$\operatorname{codim}(D\cap C)=\operatorname{codim}(D)+1$. Since also $D\cap
B\not=D$ (as $D\not\subseteq B$), Lemma 8.41 gives $\operatorname{codim}(D\cap
B)=\operatorname{codim}(D)+1$ as well. In particular,
$\operatorname{codim}(D\cap C)=\operatorname{codim}(D\cap B)<\aleph_{0}$ (as
$D\in\operatorname{Sub}^{\operatorname{f}}(A)$). By assumption we have $D\cap
C\subseteq B$, so of course $D\cap C\subseteq D\cap B$. It then follows from
Lemma 8.9(ii) that $D\cap C=D\cap B$, as claimed.

We now fix a basis $X$ of $D\cap B(=D\cap C)$, and extend this to a basis
$X\sqcup Y$ for $B\cap C$. Since
$\operatorname{codim}(B)=\operatorname{codim}(C)=1$ and $B\not=C$, Lemma 8.41
gives $\operatorname{codim}(B\cap C)=2$. Since $D\not\subseteq B$, we may also
fix some $z\in D\setminus B(=D\setminus C)$. Since $z\not\in B$, certainly
$z\not\in B\cap C=\langle X\sqcup Y\rangle$, so it follows from Lemma 8.2 that
$X\sqcup Y\sqcup z$ is independent. Let $B^{\prime}=\langle X\sqcup Y\sqcup
z\rangle$. Since $B\cap C=\langle X\sqcup Y\rangle$ and
$\operatorname{codim}(B\cap C)=2$, we have $B^{\prime}<A$ and so
$\operatorname{codim}(B^{\prime})\geq 1$. Since $B\cap C\subseteq B^{\prime}$,
we have $\operatorname{codim}(B^{\prime})\leq\operatorname{codim}(B\cap C)=2$.
If $\operatorname{codim}(B^{\prime})=2$, then Lemma 8.9(ii) would give
$B^{\prime}=B\cap C$, contradicting $z\not\in B\cap C$. So it follows that
$\operatorname{codim}(B^{\prime})=1$, so that
$B^{\prime}\in\operatorname{Max}(A)$.

Next let $D^{\prime}=\langle X\sqcup z\rangle$. Since $D\cap C=\langle
X\rangle$, and since $X\sqcup z\subseteq D$, we have

$D\cap C\subseteq D^{\prime}\subseteq D.$ (8.43)

Combined with $\operatorname{codim}(D\cap C)=\operatorname{codim}(D)+1$ (shown
above), it follows that

$\operatorname{codim}(D)+1\geq\operatorname{codim}(D^{\prime})\geq\operatorname{codim}(D),$

and this of course implies that

$\operatorname{codim}(D^{\prime})=\operatorname{codim}(D)\qquad\text{or}\qquad\operatorname{codim}(D^{\prime})=\operatorname{codim}(D)+1=\operatorname{codim}(D\cap
C).$

In these two cases, and since $\operatorname{codim}(D)<\aleph_{0}$, Lemma
8.9(ii) and (8.43) give $D^{\prime}=D$ or ${D^{\prime}=D\cap C}$,
respectively. But the latter is impossible, since $D\cap C=\langle X\rangle$
and $D^{\prime}=\langle X\sqcup z\rangle$, and since $X(\sqcup Y)\sqcup z$ is
independent. Thus, $D=D^{\prime}$, and it follows that $D=\langle X\sqcup
z\rangle\subseteq\langle X\sqcup Y\sqcup z\rangle=B^{\prime}$.

It remains to show that $C\cap B=C\cap B^{\prime}$, and for this it is enough
to show that

$C\cap B\subseteq B^{\prime}\qquad\text{and}\qquad C\cap B^{\prime}\subseteq
B.$

For the first, we have $C\cap B=\langle X\sqcup Y\rangle\subseteq B^{\prime}$.
For the second, suppose to the contrary that there exists $w\in(C\cap
B^{\prime})\setminus B$. In particular we have $w\in B^{\prime}=\langle
X\sqcup Y\sqcup z\rangle$. On the other hand, since $w\not\in B$, certainly
$w\not\in B\cap C=\langle X\sqcup Y\rangle$. It then follows from (EP) that
$z\in\langle X\sqcup Y\sqcup w\rangle\subseteq C$ (as $X\sqcup Y\subseteq
B\cap C\subseteq C$ and $w\in C\cap B^{\prime}\subseteq C$), and this
contradicts $z\in D\setminus C$. ∎

For the rest of the proof (of the theorem) we write ${\sim}=R_{E}^{\sharp}$.

######  Lemma 8.44.

If $w\in X_{E}^{*}$, and if $B\in\operatorname{Max}(A)$ is such that
$w\Phi_{E}\subseteq B$, then $w\sim wx_{B}$.

###### Proof.

Given the relations in $R_{E}^{1}\cup R_{E}^{2}$, it suffices to show that $w$
is $\sim$-equivalent to some word that involves the letter $x_{B}$.

Write $w=x_{C_{1}}\cdots x_{C_{k}}$, where each
$C_{i}\in\operatorname{Max}(A)$, and note that $w\Phi_{E}=C_{1}\cap\cdots\cap
C_{k}$. Since $w\Phi_{E}\subseteq B<A$, we must have $k\geq 1$. We now proceed
by induction on $k$. If $k=1$, then $C_{1}=w\Phi_{E}\subseteq B$, and it
follows by maximality that $C_{1}=B$; thus, $w=x_{B}$ in this case.

Now suppose $k\geq 2$, and let $u=x_{C_{1}}\cdots x_{C_{k-1}}$ and
$D=u\Phi_{E}=C_{1}\cap\cdots\cap
C_{k-1}\in\operatorname{Sub}^{\operatorname{f}}(A)$. If $D\subseteq B$, then
by induction we have $u\sim ux_{B}$, and so $w=ux_{C_{k}}\sim
ux_{B}x_{C_{k}}$, and we are done. So now we assume that $D\not\subseteq B$,
and we also write $C=C_{k}$. If $B=C$, then $w=ux_{B}$, and again we are done,
so we also assume that $B\not=C$. Since also $D\cap C=w\Phi_{E}\subseteq B$,
the conditions of Lemma 8.42 are all satisfied, so by that lemma there exists
$B^{\prime}\in\operatorname{Max}(A)$ such that $D\subseteq B^{\prime}$ and
$C\cap B=C\cap B^{\prime}$. By the latter, $R_{E}^{3}$ contains the relation
$(x_{C}x_{B},x_{C}x_{B^{\prime}})$. Since $u$ has length $k-1$, and since
$u\Phi_{E}=D\subseteq B^{\prime}$, it follows by induction that $u\sim
ux_{B^{\prime}}$. But then

$w=ux_{C}\sim ux_{B^{\prime}}x_{C}\sim ux_{C}x_{B^{\prime}}\sim ux_{C}x_{B},$

and the proof is complete. ∎

We now return to the main proof. We have already observed that $\Phi_{E}$ is
surjective, and that $R_{E}\subseteq\ker(\Phi_{E})$, so it remains to show
that $\ker(\Phi_{E})\subseteq R_{E}^{\sharp}$. So suppose
$(u,v)\in\ker(\Phi_{E})$; we must show that $u\sim v$. For $w\in X_{E}^{*}$,
we have $w\Phi_{E}=A\ \Leftrightarrow\ w=\iota$ (the empty word), so it
suffices to assume that $u$ and $v$ are both non-empty. Let $x_{B}\in X_{E}$
be any letter appearing in $v$, so that $v\sim vx_{B}$ (by $R_{E}^{1}\cup
R_{E}^{2}$). Then $u\Phi_{E}=v\Phi_{E}=(vx_{B})\Phi_{E}=v\Phi_{E}\cap
B\subseteq B$, so it follows from Lemma 8.44 that $u\sim ux_{B}$. Since this
is the case for every letter appearing in $v$, it follows that $u\sim uv$. By
symmetry we also have $v\sim vu$, and since $uv\sim vu$ (by $R_{E}^{2}$), it
follows that $u\sim v$. ∎

######  Remark 8.45.

Lemma 8.41 can fail for non-strong independence algebras. Indeed, consider the
example from [48] discussed in Remark 8.11. Then with $B=\\{a_{1},a_{2}\\}$
and $C=\\{a_{3},a_{4}\\}$, both maximal, we have $\operatorname{codim}(B)=1$,
yet $\operatorname{codim}(B\cap C)=3$.

Theorem 8.40 also does not (quite) hold for this algebra $A$. According to GAP
[50, 91], ${\textup{{Mon}}\langle{X_{E}}:{R_{E}}\rangle}$ has size $15$ in
this case, while $\operatorname{Sub}(A)$ has size $12$; it contains all
subsets of size ${\not=3}$. We do, however, obtain a presentation for this
$\operatorname{Sub}(A)$ by enlarging $R_{E}^{3}$ to

$\big{\\{}{(x_{B}x_{C},x_{B^{\prime}}x_{C^{\prime}})}:{B,C,B^{\prime},C^{\prime}\in\operatorname{Max}(A),\
B\cap C=B^{\prime}\cap C^{\prime}}\big{\\}},$

as again confirmed by GAP. We leave it as an open problem to determine whether
a similar presentation exists for $\operatorname{Sub}^{\operatorname{f}}(A)$
for an arbitrary (non-strong) independence algebra $A$.

####  8.5 Generating (finitary) automorphisms

The main purpose of this section is to prove results concerning (monoid)
generating sets for the automorphism group of a finite-dimensional
independence algebra; in fact, we prove more general results concerning
_finitary_ automorphisms, which we define below.

Let $A$ be an independence algebra. As usual, the _fix set_ of a partial
endomorphism ${\alpha\in\operatorname{PEnd}(A)}$ is the subalgebra

$\operatorname{Fix}(\alpha)=\\{{x\in\operatorname{dom}(\alpha)}:{x\alpha=x}\\}.$

We also write

$\operatorname{fix}(\alpha)=\dim(\operatorname{Fix}(\alpha))\qquad\text{and}\qquad\operatorname{cofix}(\alpha)=\operatorname{codim}(\operatorname{Fix}(\alpha)).$

Note that $\operatorname{cofix}(\alpha)$ is called the _shift_ of $\alpha$ in
[48], and denoted $s(\alpha)$. We say $\alpha\in\operatorname{PEnd}(A)$ is
_finitary_ if $\operatorname{cofix}(\alpha)<\aleph_{0}$, and we write

$\operatorname{PEnd}^{\operatorname{f}}(A)=\\{{\alpha\in\operatorname{PEnd}(A)}:{\operatorname{cofix}(\alpha)<\aleph_{0}}\\}$

for the set of all finitary partial endomorphisms of $A$, and similarly for
$\operatorname{End}^{\operatorname{f}}(A)$,
$\operatorname{PAut}^{\operatorname{f}}(A)$ and
$\operatorname{Aut}^{\operatorname{f}}(A)$. Of course we have

$\operatorname{PEnd}^{\operatorname{f}}(A)=\operatorname{PEnd}(A)\
\Leftrightarrow\ \dim(A)<\aleph_{0},$

and similarly with $\operatorname{End}^{\operatorname{f}}(A)$ and so on. When
$A$ is simply a set (with no operations),
${\operatorname{Aut}^{\operatorname{f}}(A)=\mathcal{G}^{\operatorname{f}}_{A}}$
is the _finitary symmetric group over $A$_, consisting of all finitary
permutations of $A$: i.e., the permutations that move only finitely many
elements of $A$.

######  Lemma 8.46.

If $A$ is a finite-dimensional or strong independence algebra, then
$\operatorname{PEnd}^{\operatorname{f}}(A)$ is a submonoid of
$\operatorname{PEnd}(A)$.

###### Proof.

The result is clear for $\dim(A)<\aleph_{0}$. When $A$ is strong it follows
from the identity

$\operatorname{cofix}(\alpha\beta)\leq\operatorname{cofix}(\alpha)+\operatorname{cofix}(\beta)\qquad\text{for
$\alpha,\beta\in\operatorname{PEnd}(A)$.}$

This was proved in [48, Lemma 2.7] for (full) endomorphisms, and the proof
there works unchanged for partial endomorphisms. ∎

For any cardinal $\kappa$, we define the set

$\Gamma_{\kappa}=\\{{\alpha\in\operatorname{Aut}(A)}:{\operatorname{cofix}(\alpha)=\kappa}\\}.$

For example, $\Gamma_{0}=\\{\mathrm{id}_{A}\\}$. If $\kappa>\dim(A)$ then
$\Gamma_{\kappa}=\varnothing$.

######  Theorem 8.47.

Let $A$ be an independence algebra, and let $\Gamma=\Gamma_{1}\cup\Gamma_{2}$.
Then for any ${\alpha\in\operatorname{Aut}^{\operatorname{f}}(A)}$, we have
$\alpha=\beta_{1}\cdots\beta_{k}$ for some
$\beta_{1},\ldots,\beta_{k}\in\Gamma$ with
${\operatorname{Fix}(\alpha)\subseteq\operatorname{Fix}(\beta_{i})}$ for each
$i$. Consequently,
$\operatorname{Aut}^{\operatorname{f}}(A)\subseteq\langle\Gamma\rangle$, with
equality if $A$ is finite-dimensional or strong.

###### Proof.

It suffices to prove the first claim, and for this we use induction on
$d=\operatorname{cofix}(\alpha)$. If $d=0$ then $\alpha=\mathrm{id}_{A}$, and
we take $k=0$. If $d=1$, then $\alpha\in\Gamma$, and we take $k=1$ and
$\beta_{1}=\alpha$. (We could include $d=2$ in the base case(s), but we prefer
not to, as it allows us to only use certain elements of $\Gamma_{2}$, which
will then be used in the next proof.)

We now assume that $d\geq 2$. We will show that there exists $\beta\in\Gamma$
such that

$\operatorname{cofix}(\alpha\beta^{-1})\leq
d-1\qquad\text{and}\qquad\operatorname{Fix}(\alpha)\subseteq\operatorname{Fix}(\beta).$
(8.48)

It follows from the latter that
$\operatorname{Fix}(\alpha)\subseteq\operatorname{Fix}(\alpha\beta^{-1})$. By
induction, it follows from the former that
$\alpha\beta^{-1}=\gamma_{1}\cdots\gamma_{l}$ for some
$\gamma_{1},\ldots,\gamma_{l}\in\Gamma$ such that each
$\operatorname{Fix}(\gamma_{i})\supseteq\operatorname{Fix}(\alpha\beta^{-1})\supseteq\operatorname{Fix}(\alpha)$.
Since $\alpha=\gamma_{1}\cdots\gamma_{l}\cdot\beta$, the inductive step will
be complete.

For the rest of the proof, we fix a basis $X$ for
$\operatorname{Fix}(\alpha)$. Since $d>0$ we may also fix some $y\in
A\setminus\operatorname{Fix}(\alpha)$. Since
$y\not\in\operatorname{Fix}(\alpha)=\langle X\rangle$, and since $X$ is
independent, it follows from Lemma 8.2 that $X\sqcup y$ is independent.

Case 1. Suppose first that $y\alpha\in\langle X\sqcup y\rangle$. Note also
that $y\alpha\not\in\operatorname{Fix}(\alpha)=\langle X\rangle$. (Otherwise,
$(y\alpha)\alpha=y\alpha$ would imply $y\alpha=y$, contradicting
$y\not\in\operatorname{Fix}(\alpha)$.) It then follows from (EP) that
$y\in\langle X\sqcup y\alpha\rangle$. Consequently, $\langle X\sqcup
y\rangle=\langle X\sqcup y\alpha\rangle$. Since $X\sqcup y$ is independent, we
may extend it to a basis $X\sqcup y\sqcup Z$ of $A$, and we note that
$|y\sqcup Z|=\operatorname{cofix}(\alpha)=d$. So $Z$ is a $B$-basis of $A$,
where $B=\langle X\sqcup y\rangle=\langle X\sqcup y\alpha\rangle$. It then
follows from Lemma 8.7 that $X\sqcup y\alpha\sqcup Z$ is also a basis of $A$.
Now let $\beta$ be the endomorphism of $A$ satisfying

$x\beta=x,\qquad y\beta=y\alpha\qquad\text{and}\qquad z\beta=z\qquad\text{for
all $x\in X$ and $z\in Z$.}$

Since $\beta$ maps a basis bijectively to a basis, it is an automorphism. And
moreover, the maximal subalgebra $\langle X\sqcup Z\rangle$ is contained in
$\operatorname{Fix}(\beta)$, so it follows that
$\operatorname{cofix}(\beta)\leq 1$. Since ${y\beta=y\alpha\not=y}$, we cannot
have $\operatorname{cofix}(\beta)=0$, so in fact
$\beta\in\Gamma_{1}\subseteq\Gamma$. Certainly
${\operatorname{Fix}(\alpha)=\langle
X\rangle\subseteq\operatorname{Fix}(\beta)}$, and since $X\sqcup
y\subseteq\operatorname{Fix}(\alpha\beta^{-1})$, we also have
$\operatorname{cofix}(\alpha\beta^{-1})\leq|Z|=d-1$. This completes the proof
that (8.48) holds in this case.

Case 2. Now suppose $y\alpha\not\in\langle X\sqcup y\rangle$, and for
convenience write $y^{\prime}=y\alpha$. It follows from Lemma 8.2 that
$X\sqcup\\{y,y^{\prime}\\}$ is independent, so we may extend it to a basis
$X\sqcup\\{y,y^{\prime}\\}\sqcup Z$ of $A$. This time we have
$\big{|}\\{y,y^{\prime}\\}\sqcup Z\big{|}=\operatorname{cofix}(\alpha)=d$, and
we define $\beta\in\operatorname{Aut}(A)$ by

$x\beta=x,\qquad y\beta=y^{\prime},\qquad
y^{\prime}\beta=y\qquad\text{and}\qquad z\beta=z\qquad\text{for all $x\in X$
and $z\in Z$.}$

Since $X\sqcup Z\subseteq\operatorname{Fix}(\beta)$ but
$y\not\in\operatorname{Fix}(\beta)$, we have
$1\leq\operatorname{cofix}(\beta)\leq 2$, so $\beta\in\Gamma$, and again we
have $\operatorname{Fix}(\alpha)\subseteq\operatorname{Fix}(\beta)$. Also,
since $X\sqcup y\subseteq\operatorname{Fix}(\alpha\beta^{-1})$ we have
$\operatorname{cofix}(\alpha\beta^{-1})\leq|Z\sqcup y^{\prime}|=d-1$, and
again (8.48) holds. ∎

######  Remark 8.49.

In the above proof, we noted that the automorphism $\beta$ constructed during
Case 2 satisfied $\operatorname{cofix}(\beta)\leq 2$. It is actually possible
that $\operatorname{cofix}(\beta)=1$, so that in fact $\beta\in\Gamma_{1}$.
For example, if $A$ is a vector space, then $X\sqcup\\{y,y+y^{\prime}\\}\sqcup
Z$ is also a basis of $A$, and $(y+y^{\prime})\beta=y+y^{\prime}$. It follows
that $\operatorname{Aut}^{\operatorname{f}}(A)=\langle\Gamma_{1}\rangle$ if
$A$ is a vector space.

Among other things, the next result shows that the situation just described is
true of a wider class of algebras:

######  Theorem 8.50.

Let $A$ be an independence algebra.

  1. (i)

If $A$ satisfies the conditions of Proposition 8.26, then Theorem 8.47 holds
with $\Gamma_{1}\cup\Gamma_{2}$ replaced by $\Gamma_{2}$.

  2. (ii)

If $A$ satisfies the conditions of Proposition 8.27, but not those of
Proposition 8.26, then Theorem 8.47 holds with ${\Gamma_{1}\cup\Gamma_{2}}$
replaced by $\Gamma_{1}$.

  3. (iii)

If $A$ satisfies either of the conditions of Lemma 8.34, then Theorem 8.47
holds with ${\Gamma_{1}\cup\Gamma_{2}}$ replaced by $\Gamma_{1}$.

###### Proof.

(i). In this case, the subalgebras of codimension $1$ are of the form
$A\setminus x$, and if an automorphism fixes $A\setminus x$ pointwise, it must
also fix $x$. So $\Gamma_{1}=\varnothing$, and the claim follows.

For later reference, it is worth discussing an alternative proof of this part.
We know from Proposition 8.27 that
${\operatorname{Aut}(A)=\\{{\mathrm{id}_{C}\cup\alpha}:{\alpha\in\mathcal{G}_{X}}\\}}$,
where again we write $X=A\setminus\mathcal{C}(A)$, and of course it follows
that

$\operatorname{Aut}^{\operatorname{f}}(A)=\\{{\mathrm{id}_{C}\cup\alpha}:{\alpha\in\mathcal{G}^{\operatorname{f}}_{X}}\\}.$

It is well known that finite symmetric groups are generated by transpositions.
So too therefore is the finitary symmetric group
$\mathcal{G}^{\operatorname{f}}_{X}$, and so
$\operatorname{Aut}^{\operatorname{f}}(A)$ is generated by automorphisms of
the form $\beta=\mathrm{id}_{C}\cup(x,y)$ for distinct $x,y\in X$ (again using
standard cycle notation). But for this $\beta$ we have
$\operatorname{Fix}(\beta)=A\setminus\\{x,y\\}=\big{\langle}X\setminus\\{x,y\\}\big{\rangle}$.
Since $X$ is independent, so too is $X\setminus\\{x,y\\}$, so
$\operatorname{Fix}(\beta)$ has codimension $2$.

(ii). This is similar to the second proof of (i). Again we have
${\operatorname{Aut}^{\operatorname{f}}(A)=\\{{\mathrm{id}_{C}\cup\alpha}:{\alpha\in\mathcal{G}^{\operatorname{f}}_{X}}\\}}$,
where $X=A\setminus\mathcal{C}(A)$. So
$\operatorname{Aut}^{\operatorname{f}}(A)$ is generated by automorphisms of
the form $\beta=\mathrm{id}_{C}\cup(x,y)$ for distinct $x,y\in X$, and we
still have
$\operatorname{Fix}(\beta)=A\setminus\\{x,y\\}=\big{\langle}X\setminus\\{x,y\\}\big{\rangle}$.
Since $X$ is not independent, but $X\setminus x$ and $X\setminus y$ both are,
it follows that $\operatorname{Fix}(\beta)$ is maximal, and hence has
codimension $1$.

(iii). Looking at the proof of Theorem 8.47, it suffices to show that the
automorphism $\beta$ constructed during Case 2 can be expressed as
$\beta=\gamma_{1}\gamma_{2}\gamma_{3}$, where each $\gamma_{i}\in\Gamma_{1}$
satisfies $\operatorname{Fix}(\alpha)\subseteq\operatorname{Fix}(\gamma_{i})$.
To do so, we keep the notation of that part of the proof, and it will be
convenient to write $U=X\sqcup Z$. So $U\sqcup\\{y,y^{\prime}\\}$ is a basis
of $A$, and $\beta\in\operatorname{Aut}(A)$ acts via

$u\beta=u,\qquad y\beta=y^{\prime}\qquad\text{and}\qquad
y^{\prime}\beta=y\qquad\text{for all $u\in U$.}$

By Lemma 8.34(ii), we may choose some $w\in A$ such that $w\not\in\langle
U\sqcup y\rangle\cup\langle U\sqcup y^{\prime}\rangle$. It follows quickly
that $U\sqcup\\{y,w\\}$ and $U\sqcup\\{y^{\prime},w\\}$ are both bases of $A$.
We then define $\gamma_{1},\gamma_{2},\gamma_{3}\in\Gamma_{1}$ by their action
on the various bases by

$\displaystyle u\gamma_{1}$ $\displaystyle=u,$ $\displaystyle u\gamma_{2}$
$\displaystyle=u,$ $\displaystyle u\gamma_{3}$ $\displaystyle=u,$
$\displaystyle y\gamma_{1}$ $\displaystyle=y,$ $\displaystyle y\gamma_{2}$
$\displaystyle=y^{\prime},$ $\displaystyle y^{\prime}\gamma_{3}$
$\displaystyle=y^{\prime},$ $\displaystyle y^{\prime}\gamma_{1}$
$\displaystyle=w,$ $\displaystyle w\gamma_{2}$ $\displaystyle=w,$
$\displaystyle w\gamma_{3}$ $\displaystyle=y,$

for each $u\in U$. Verification that $\beta=\gamma_{1}\gamma_{2}\gamma_{3}$ is
straightforward, and we have $\operatorname{Fix}(\alpha)=\langle X\rangle$,
and $X\subseteq U$. ∎

######  Remark 8.51.

As we observed in the proof, parts (i) and (ii) of Theorem 8.50 boil down to
the fact that finite symmetric groups are generated by transpositions. The
standard Coxeter presentation for a finite symmetric group involves (simple)
transpositions [92]; this is stated in Theorem 9.55 below. We believe it would
be interesting to look for presentations for
$\operatorname{Aut}^{\operatorname{f}}(A)$ in the cases that $A$ does not
satisfy the conditions of Propositions 8.26 or 8.27, but this is beyond the
scope of the current work. To our knowledge, such presentations are not even
known in the case that $A$ is a finite-dimensional vector space.

For infinite $\dim(A)$, generating sets for the full automorphism group
$\operatorname{Aut}(A)$ can be very complicated, even when $A$ is simply a set
(since $\mathcal{G}_{A}$ is uncountable).

######  Remark 8.52.

Since vector spaces of dimension $2\leq n<\aleph_{0}$ satisfy the conditions
of Lemma 8.34 (cf. Remark 8.37), Theorem 8.50(iii) implies the well-known fact
that general linear groups are generated by matrices whose fix spaces have
codimension $1$. Indeed, it is a basic fact of linear algebra that every
invertible matrix is a product of ‘elementary row operation’ matrices, and one
can easily see that the fix space of each such matrix has codimension $1$.
This is clear for row operations of the form $R_{i}\to\lambda R_{i}$ or
$R_{i}\to R_{i}+R_{j}$; for a row swap $R_{i}\leftrightarrow R_{j}$, we use
the argument in Remark 8.49, with $y$ and $y^{\prime}$ the $i$th and $j$th
standard basis vectors.

######  Remark 8.53.

Consider again the algebra $A=\\{a,b,c,d\\}$ from Remark 8.31. Using the
notation of that remark, we have

$\Gamma_{0}=\\{\mathrm{id}_{A}\\},\qquad\Gamma_{1}=\\{\alpha_{1},\alpha_{2}\\}\qquad\text{and}\qquad\Gamma_{2}=\\{\alpha_{3},\beta_{1},\beta_{2},\beta_{3},\beta_{4}\\}.$

Then $A$ satisfies none of the conditions of Proposition 8.26, Proposition
8.27 or Lemma 8.34, and one can check that

$\operatorname{Aut}(A)=\langle\Gamma_{2}\rangle\qquad\text{but}\qquad\langle\Gamma_{1}\rangle=\\{\mathrm{id}_{A},\alpha_{1},\alpha_{2},\alpha_{3}\rangle\not=\operatorname{Aut}(A).$

####  8.6 Action pairs and subsemigroups

Consider a partial endomorphism $\alpha:B\to A$, where $A$ is an independence
algebra. Since any basis for $B$ can be extended to a basis of $A$, it follows
from (FBP) that $\alpha$ can be extended to an endomorphism $\beta:A\to A$.
Note then that
$\alpha=\beta\mathord{\restriction}_{B}=\mathrm{id}_{B}\cdot\beta$, so that
every partial endomorphism is a restriction of an endomorphism. This and more
can be expressed in terms of (strong) action pairs, as we explore in this
section.

In what follows, we continue to write

$\mathcal{E}_{A}=\\{{\mathrm{id}_{B}}:{B\leq A}\\}$

for the semilattice of all partial identities of $A$. We observed in Section
8.2 that $\mathcal{E}_{A}$ is isomorphic to the $\cap$-semilattice
$\operatorname{Sub}(A)$. We also write

$\operatorname{Sing}(\mathcal{E}_{A})=\mathcal{E}_{A}\setminus\\{\mathrm{id}_{A}\\}=\\{{\mathrm{id}_{B}}:{B<A}\\},$

and we note that $\operatorname{Sing}(\mathcal{E}_{A})$ is a subsemilattice of
$\mathcal{E}_{A}$, regardless of the dimension of $A$. We have
$\operatorname{Sing}(\mathcal{E}_{A})=\varnothing$ if $\dim(A)=0$.

######  Proposition 8.54.

For any independence algebra $A$, the following are all strong action pairs in
$\operatorname{PEnd}(A)$_:_

  1. (i)

$(\mathcal{E}_{A},\operatorname{End}(A))$,

  2. (ii)

$(\operatorname{Sing}(\mathcal{E}_{A}),\operatorname{End}(A))$,

  3. (iii)

$(\mathcal{E}_{A},\operatorname{Sing}(\operatorname{End}(A)))$ if
$\dim(A)<\aleph_{0}$,

  4. (iv)

$(\operatorname{Sing}(\mathcal{E}_{A}),\operatorname{Sing}(\operatorname{End}(A)))$
if $\dim(A)<\aleph_{0}$,

  5. (v)

$(\mathcal{E}_{A},\operatorname{Aut}(A))$,

  6. (vi)

$(\operatorname{Sing}(\mathcal{E}_{A}),\operatorname{Aut}(A))$.

###### Proof.

This follows from Propositions 4.44 and 8.16, given (8.17) and (8.18). ∎

######  Remark 8.55.

In fact the previous result holds for an arbitrary algebra $A$ (with the same
proof), but note that parts (iii) and (iv) hold precisely when
$\operatorname{Sing}(\operatorname{End}(A))$ is a subsemigroup of
$\operatorname{End}(A)$. (When $A$ is not an independence algebra, there might
not be a meaningful notion of dimension.)

Each of the pairs $(E,S)$ listed in Proposition 8.54 leads as usual to the
subsemigroup $ES$ of ${M=\operatorname{PEnd}(A)}$. The next result identifies
the set $ES$ for each pair. Note that we do not assume $\dim(A)<\aleph_{0}$ in
the third and fourth parts; even though the stated equality still holds when
$\dim(A)\geq\aleph_{0}$, the subsets $S$ and $ES$ are not semigroups in this
case.

######  Theorem 8.56.

For any independence algebra $A$, we have:

  1. (i)

$\mathcal{E}_{A}\cdot\operatorname{End}(A)=\operatorname{PEnd}(A)$,

  2. (ii)

$\operatorname{Sing}(\mathcal{E}_{A})\cdot\operatorname{End}(A)=\operatorname{PEnd}(A)\setminus\operatorname{End}(A)$,

  3. (iii)

$\mathcal{E}_{A}\cdot\operatorname{Sing}(\operatorname{End}(A))\subseteq\operatorname{Sing}(\operatorname{PEnd}(A))$,
with equality unless $\dim(A)=1$ and $A$ has no constants,

  4. (iv)

$\operatorname{Sing}(\mathcal{E}_{A})\cdot\operatorname{Sing}(\operatorname{End}(A))\subseteq\operatorname{PEnd}(A)\setminus\operatorname{End}(A)$,
with equality unless $\dim(A)=1$ and $A$ has no constants,

  5. (v)

$\mathcal{E}_{A}\cdot\operatorname{Aut}(A)\subseteq\operatorname{PAut}(A)$,
with equality if and only if $\dim(A)<\aleph_{0}$,

  6. (vi)

$\operatorname{Sing}(\mathcal{E}_{A})\cdot\operatorname{Aut}(A)\subseteq\operatorname{Sing}(\operatorname{PAut}(A))$,
with equality if and only if $\dim(A)<\aleph_{0}$.

###### Proof.

The forwards inclusions are straightforward in each case (and trivial for
(i)), given that

$\mathrm{id}_{B}\cdot\alpha=\alpha\mathord{\restriction}_{B}\qquad\text{for
all $\alpha\in\operatorname{End}(A)$ and $B\leq A$.}$

For cases (ii)–(vi), we additionally rely on (combinations of) the following
simple observations:

  * •

If $B\not=A$ (i.e., $\mathrm{id}_{B}\in\operatorname{Sing}(\mathcal{E}_{A})$),
then $\alpha\mathord{\restriction}_{B}$ is not an endomorphism (and of course
not an automorphism).

  * •

If $\alpha$ is not an automorphism (i.e.,
$\alpha\in\operatorname{Sing}(\operatorname{End}(A))$), then neither is
$\alpha\mathord{\restriction}_{B}$. (Indeed, this is clear if $B=A$, and
follows from the previous point if $B<A$.)

  * •

If $\alpha$ is injective, then so too is $\alpha\mathord{\restriction}_{B}$.

We now work towards the reverse inclusions. For this, we fix some
${\alpha\in\operatorname{PEnd}(A)}$, and write $B=\operatorname{dom}(\alpha)$.
Let $X$ be a basis of $B$, and extend this to a basis $X\sqcup Y$ of $A$. Let
$f:Y\to A$ be an arbitrary function, so that
$\alpha\mathord{\restriction}_{X}\sqcup f:X\sqcup Y\to A$ extends to an
endomorphism $\beta:A\to A$. For any $x\in X$, we have $x\beta=x\alpha$, so
since $X$ is a basis it follows that $b\beta=b\alpha$ for all $b\in B$.
Consequently, we have

$\alpha=\beta\mathord{\restriction}_{B}=\mathrm{id}_{B}\cdot\beta\qquad\text{with
$\mathrm{id}_{B}\in\mathcal{E}_{A}$ and $\beta\in\operatorname{End}(A)$.}$

This completes the proof of part (i). For the other parts, we need to ensure
that the additional constraints on $\alpha$ (by virtue of belonging to the
appropriate right-hand set) allow us to define $f$ in such a way that the
appropriate conditions on $\beta$ (and $\mathrm{id}_{B}$) hold, or else
explain why the backwards inclusions do not hold in the relevant cases.

(ii). If $\alpha\in\operatorname{PEnd}(A)\setminus\operatorname{End}(A)$, then
$B\not=A$, so $\mathrm{id}_{B}\in\operatorname{Sing}(\mathcal{E}_{A})$.

(iii). First suppose $\dim(A)=1$ and $A$ has no constants. Then by Remark
8.20(vii), we have

$\mathcal{E}_{A}\cdot\operatorname{Sing}(\operatorname{End}(A))=\operatorname{Sing}(\mathcal{E}_{A})\cdot\operatorname{Sing}(\operatorname{End}(A))=\varnothing$
(8.57)

and

$\operatorname{Sing}(\operatorname{PEnd}(A))=\operatorname{PEnd}(A)\setminus\operatorname{End}(A)=\\{\varnothing\\},$
(8.58)

so we have strict inclusion in this case.

We now assume that $\dim(A)\not=1$ and/or $A$ has constants.

Suppose $\alpha\in\operatorname{Sing}(\operatorname{PEnd}(A))$. We must show
that $\beta$ can be chosen so that
$\beta\in\operatorname{Sing}(\operatorname{End}(A))$. First, if
$\alpha\in\operatorname{End}(A)$, then
$\alpha\in\operatorname{Sing}(\operatorname{End}(A))$ and $B=A$, so that
$\beta=\alpha\in\operatorname{Sing}(\operatorname{End}(A))$. So now suppose
$\alpha\not\in\operatorname{End}(A)$. In particular, $B<A$, which implies
$Y\not=\varnothing$, and so $\dim(A)\geq 1$. Since we have also assumed that
$\dim(A)\not=1$ and/or $A$ has constants, it then follows from Lemma 8.21 that
$\operatorname{Sing}(\operatorname{End}(A))\not=\varnothing$.

If $X\not=\varnothing$, then we fix some $x\in X$, and simply ensure that
$yf=x\alpha$ for all $y\in Y$; in this case,
$\alpha\mathord{\restriction}_{X}\sqcup f$ is not injective, and so
$\beta\in\operatorname{Sing}(\operatorname{End}(A))$.

If $X=\varnothing$, then $B=\mathcal{C}(A)$ and $\alpha=\mathrm{id}_{B}$
(since every partial endomorphism fixes $\mathcal{C}(A)$ pointwise). So in
fact, $\alpha=\mathrm{id}_{B}\cdot\beta$ for _any_
$\beta\in\operatorname{End}(A)$. In particular, we can take $\beta$ to be any
element of $\operatorname{Sing}(\operatorname{End}(A))$, which we noted above
is non-empty.

(iv). If $\dim(A)=1$ and $A$ has no constants, then strict inclusion again
follows from (8.57) and (8.58). So now suppose $\dim(A)\not=1$ and/or $A$ has
constants, and let
${\alpha\in\operatorname{PEnd}(A)\setminus\operatorname{End}(A)}$. As in (ii),
we have $\mathrm{id}_{B}\in\operatorname{Sing}(\mathcal{E}_{A})$. As in (iii),
we can choose $\beta$ so that
$\beta\in\operatorname{Sing}(\operatorname{End}(A))$.

(v). First suppose $\dim(A)\geq\aleph_{0}$, and fix any basis $Z$ for $A$. Let
$z\in Z$, and let $\beta$ be an endomorphism extending some bijection $Z\to
Z\setminus z$. Then in fact
$\beta\in\operatorname{Sing}(\operatorname{PAut}(A))$. But if
$\beta=\mathrm{id}_{B}\cdot\gamma$ for some $B\leq A$ and
$\gamma\in\operatorname{Aut}(A)$, then from
$\beta=\gamma\mathord{\restriction}_{B}$ it follows that
$B=\operatorname{dom}(\beta)=A$, and so
$\beta=\gamma\in\operatorname{Aut}(A)$, a contradiction.

Now suppose $\dim(A)<\aleph_{0}$. Since $\alpha\in\operatorname{PAut}(A)$, it
follows that $X\alpha$ is a basis for $\operatorname{im}(\alpha)$ and
$|X\alpha|=|X|$. We then extend $X\alpha$ to a basis $X\alpha\sqcup W$ for
$A$, noting that $|W|=|Y|$, and let $f:Y\to W$ be any bijection. Clearly then
$\beta\in\operatorname{Aut}(A)$.

(vi). The proof is essentially the same as (v). The same
$\beta\in\operatorname{Sing}(\operatorname{PAut}(A))$ deals with the case
$\dim(A)\geq\aleph_{0}$. When $\dim(A)<\aleph_{0}$, we define $f$ as above,
and note that $\alpha\not\in\operatorname{Aut}(A)$ implies $B<A$. ∎

######  Remark 8.59.

One might wonder if any of the pairs $(E,S)$ in Proposition 8.54 are proper,
in the sense of Definition 5.25. By Proposition 5.29 this is equivalent to the
left restriction semigroup $ES$ being proper, in the sense of Definition 5.7.
But it is easy to see that this is never the case (apart from trivially small
exceptions). Indeed, $\mathrm{id}_{C}$ is a left zero element of
$\operatorname{PEnd}(A)$, where $C=\mathcal{C}(A)$, and we have
$\mathrm{id}_{C}\in E=P(ES)$ for each of the pairs $(E,S)$ listed in the
proposition. It follows immediately that $\sigma=\sigma_{ES}=\nabla_{S}$ (the
universal relation) in each case. The equivalence (5.8) becomes

$\alpha=\beta\ \Leftrightarrow\
\operatorname{dom}(\alpha)=\operatorname{dom}(\beta)\qquad\text{for all
$\alpha,\beta\in ES$,}$

and this clearly does not hold (apart from trivially small exceptions).

On the other hand, it follows from Theorem 5.39 (cf. Theorem 5.11) that the
left restriction semigroup $ES$ is covered by the proper left restriction
semigroup

$\big{\\{}{(\mathrm{id}_{B},\alpha)\in E\rtimes
S}:{\mathrm{id}_{B}=\mathrm{id}_{B}\cdot\alpha^{+}}\big{\\}}=\big{\\{}{(\mathrm{id}_{B},\alpha)\in
E\rtimes S}:{B\subseteq\operatorname{dom}(\alpha)}\big{\\}}.$

######  Remark 8.60.

Part (ii) of Theorem 8.56 is a special case of the right ideal
$P^{\flat}T=M\setminus T$ discussed in Remark 4.45; cf. (8.17) and (8.18).

By Proposition 8.54, $(\mathcal{E}_{A},\operatorname{Aut}(A))$ and
$(\operatorname{Sing}(\mathcal{E}_{A}),\operatorname{Aut}(A))$ are strong
action pairs in $\operatorname{PEnd}(A)$, for arbitrary $A$. Theorem 8.56
characterises the resulting subsemigroups
$\mathcal{E}_{A}\cdot\operatorname{Aut}(A)$ and
$\operatorname{Sing}(\mathcal{E}_{A})\cdot\operatorname{Aut}(A)$ in the case
that $\dim(A)$ is finite. For the infinite case, we need the notion of
_codimension_ from Definition 8.6:

######  Theorem 8.61.

For any independence algebra $A$, we have

  1. (i)

$\mathcal{E}_{A}\cdot\operatorname{Aut}(A)=\big{\\{}{\alpha\in\operatorname{PAut}(A)}:{\operatorname{codim}(\operatorname{dom}(\alpha))=\operatorname{codim}(\operatorname{im}(\alpha))}\big{\\}}$,

  2. (ii)

$\operatorname{Sing}(\mathcal{E}_{A})\cdot\operatorname{Aut}(A)=\big{\\{}{\alpha\in\operatorname{PAut}(A)}:{\operatorname{codim}(\operatorname{dom}(\alpha))=\operatorname{codim}(\operatorname{im}(\alpha))\geq
1}\big{\\}}$.

###### Proof.

Since

$\mathcal{E}_{A}\cdot\operatorname{Aut}(A)=\big{(}{\operatorname{Sing}}(\mathcal{E}_{A})\cdot\operatorname{Aut}(A)\big{)}\sqcup\operatorname{Aut}(A),$

and since

$\operatorname{Aut}(A)=\\{{\alpha\in\operatorname{PAut}(A)}:{\operatorname{codim}(\operatorname{dom}(\alpha))=\operatorname{codim}(\operatorname{im}(\alpha))=0}\\},$

it suffices to prove (i).

Beginning with the forwards inclusion, let
$\alpha\in\mathcal{E}_{A}\cdot\operatorname{Aut}(A)$, so that
$\alpha=\mathrm{id}_{B}\cdot\beta=\beta\mathord{\restriction}_{B}$ for some
$B\leq A$ and $\beta\in\operatorname{Aut}(A)$. Fix some $B$-basis $X$ of $A$,
and also write $C=\operatorname{im}(\alpha)=B\beta$ and $Y=X\beta$. We first
claim that $Y$ is a $C$-basis of $A$. To see this, first note that since
$\beta$ is an automorphism, we have $A=\langle B\cup X\rangle=\langle(B\cup
X)\beta\rangle=\langle C\cup Y\rangle$. It remains (for the claim) to show
that $Y$ is $C$-independent, and this is also straightforward. If
$y\in\big{\langle}C\cup(Y\setminus y)\big{\rangle}$ for some $y\in Y$, then
applying the automorphism $\beta^{-1}$, we have
$y\beta^{-1}\in\big{\langle}B\cup(X\setminus y\beta^{-1})\big{\rangle}$, with
$y\beta^{-1}\in X$, contradicting $B$-independence of $X$. With the claim
established, and since $\beta$ is injective, we then have

$\operatorname{codim}(\operatorname{dom}(\alpha))=\operatorname{codim}(B)=|X|=|X\beta|=|Y|=\operatorname{codim}(C)=\operatorname{codim}(\operatorname{im}(\alpha)).$

Conversely, suppose $\alpha\in\operatorname{PAut}(A)$ is such that
$\operatorname{codim}(B)=\operatorname{codim}(C)$, where we have written
$B=\operatorname{dom}(\alpha)$ and $C=\operatorname{im}(\alpha)$. Let $X$ be a
basis for $B$, and let $Y$ and $Z$ be $B$\- and $C$-bases for $A$,
respectively. Since $\alpha:B\to C$ is an isomorphism, $X\alpha$ is a basis of
$C$, and it follows from Lemma 8.7 that $X\cup Y$ and $X\alpha\cup Z$ are
bases for $A$. Since
${|Y|=\operatorname{codim}(B)=\operatorname{codim}(C)=|Z|}$, we may fix a
bijection $\phi:Y\to Z$. Since $X\cup Y$ is a basis of $A$, we may define
$\beta\in\operatorname{End}(A)$ to be the endomorphism extending
$\alpha\mathord{\restriction}_{X}\cup\phi:X\cup Y\to X\alpha\cup Z$. Since
$\alpha\mathord{\restriction}_{X}\cup\phi$ is a bijection between bases, it
follows that $\beta\in\operatorname{Aut}(A)$. For any $x\in X$ we have
$x\beta=x\alpha$, so since $B=\langle X\rangle$ it follows that
$b\beta=b\alpha$ for all $b\in B$. We then have
$\alpha=\beta\mathord{\restriction}_{B}=\mathrm{id}_{B}\cdot\beta\in\mathcal{E}_{A}\cdot\operatorname{Aut}(A)$.
∎

######  Remark 8.62.

Theorem 8.61 holds for arbitrary $\dim(A)$. When $\dim(A)<\aleph_{0}$, we have

$\dim(B)=\dim(C)\ \Rightarrow\
\operatorname{codim}(B)=\operatorname{codim}(C)\qquad\text{for $B,C\leq A$},$

so parts (v) and (vi) of Theorem 8.56 follow from Theorem 8.61.

######  Remark 8.63.

Note that $\mathcal{E}_{A}$ and $\operatorname{Aut}(A)$ respectively consist
of all idempotents and units of the inverse monoid $\operatorname{PAut}(A)$.
It follows that $\mathcal{E}_{A}\cdot\operatorname{Aut}(A)$ is the largest
factorisable inverse submonoid of $\operatorname{PAut}(A)$. Theorem 8.61(i) is
therefore a generalisation of the main result of [14], which concerns the case
that $A$ is a set, and says that the largest factorisable inverse submonoid of
the symmetric inverse monoid $\mathcal{I}_{A}$ is

$\mathcal{F}_{A}=\big{\\{}{\alpha\in\mathcal{I}_{A}}:{|A\setminus{\operatorname{dom}(\alpha)}|=|A\setminus{\operatorname{im}(\alpha)}|}\big{\\}}.$

(In this case, an arbitrary subset $B\subseteq A$ is a subalgebra, and
$\operatorname{codim}(B)=|A\setminus B|$.)

######  Remark 8.64.

It is worth considering Proposition 8.54 and Theorems 8.56 and 8.61 in the
special case that $A=X$ is simply a set with no operations. As explained
above, we then have ${\operatorname{PEnd}(A)=\mathcal{P}\mathcal{T}_{X}}$, and
so on. We then obtain the following strong action pairs in
$M=\mathcal{P}\mathcal{T}_{X}$:

  1. (i)

$(\mathcal{E}_{X},\mathcal{T}_{X})$,

  2. (ii)

$(\operatorname{Sing}(\mathcal{E}_{X}),\mathcal{T}_{X})$,

  3. (iii)

$(\mathcal{E}_{X},\operatorname{Sing}(\mathcal{T}_{X}))$ if $|X|<\aleph_{0}$,

  4. (iv)

$(\operatorname{Sing}(\mathcal{E}_{X}),\operatorname{Sing}(\mathcal{T}_{X}))$
if $|X|<\aleph_{0}$,

  5. (v)

$(\mathcal{E}_{X},\mathcal{G}_{X})$,

  6. (vi)

$(\operatorname{Sing}(\mathcal{E}_{X}),\mathcal{G}_{X})$.

These action pairs give rise, respectively, to the following product
semigroups:

  1. (i)

$\mathcal{E}_{X}\cdot\mathcal{T}_{X}=\mathcal{P}\mathcal{T}_{X}$,

  2. (ii)

$\operatorname{Sing}(\mathcal{E}_{X})\cdot\mathcal{T}_{X}=\mathcal{P}\mathcal{T}_{X}\setminus\mathcal{T}_{X}$,

  3. (iii)

$\mathcal{E}_{X}\cdot\operatorname{Sing}(\mathcal{T}_{X})=\operatorname{Sing}(\mathcal{P}\mathcal{T}_{X})$
if $1\not=|X|<\aleph_{0}$,

  4. (iv)

$\operatorname{Sing}(\mathcal{E}_{X})\cdot\operatorname{Sing}(\mathcal{T}_{X})=\mathcal{P}\mathcal{T}_{X}\setminus\mathcal{T}_{X}$
if $1\not=|X|<\aleph_{0}$,

  5. (v)

$\mathcal{E}_{X}\cdot\mathcal{G}_{X}=\mathcal{F}_{X}$,

  6. (vi)

$\operatorname{Sing}(\mathcal{E}_{X})\cdot\mathcal{G}_{X}=\operatorname{Sing}(\mathcal{F}_{X})$.

The results of the current chapter all have interpretations for these
subsemigroups of $\mathcal{P}\mathcal{T}_{X}$. We will not explicitly state
these, however, as they are more readily deduced as special cases of the
results of Chapter 9.

####  8.7 Congruence conditions

The action pairs $(E,S)$ listed in Proposition 8.54 lead to the subsemigroups
$ES$ of ${M=\operatorname{PEnd}(A)}$, which are characterised in Theorems 8.56
and 8.61. In each case we have $ES\cong(E\rtimes S)/\theta$, as in Proposition
4.46. Section 4.5 gave a number of conditions under which relatively small
generating sets exist for the congruence $\theta$; such conditions also
featured in a number of results of Chapter 6 concerning presentations for
$ES$. The purpose of the current section is to identify which of these
conditions hold for the pairs in Proposition 8.54.

######  Lemma 8.65.

Let $(E,S)$ be one of the (strong) action pairs in $\operatorname{PEnd}(A)$
listed in Proposition 8.54, with the exception of
$(E,S)=(\operatorname{Sing}(\mathcal{E}_{A}),\operatorname{End}(A))$ in the
case that $\dim(A)\geq\aleph_{0}$. Then $(E,S)$ satisfies at least one of the
conditions listed in Lemma 4.61.

###### Proof.

The pairs in parts (i), (iii) or (v) of Proposition 8.54 satisfy _all_ the
conditions of Lemma 4.61, since $\mathcal{E}_{A}$ is a submonoid of
$\operatorname{PEnd}(A)$; cf. Remark 4.62.

The other pairs (not including the stated exception) satisfy condition (viii),
and hence also (x). To prove this, we need to show that every element of $ES$
has a right identity from $E$. So let $\alpha\in ES$, and put
$B=\operatorname{im}(\alpha)$. Since we clearly have
$\alpha=\alpha\cdot\mathrm{id}_{B}$, it remains to show that $B\not=A$. For
this, we consider the three cases (as listed in Proposition 8.54) separately.

(ii). Here Theorem 8.56 gives
$ES=\operatorname{PEnd}(A)\setminus\operatorname{End}(A)$, and $\dim(A)$ is
finite (because the infinite case is excluded in the lemma). Since $\alpha$ is
therefore not an endomorphism, $\operatorname{dom}(\alpha)$ is a proper
subalgebra of $A$, and hence $\dim(\operatorname{dom}(\alpha))<\dim(A)$, as
the latter is finite. It follows that
$\dim(B)=\dim(\operatorname{im}(\alpha))\leq\dim(\operatorname{dom}(\alpha))<\dim(A)$,
and so $B\not=A$.

(iv). The proof is essentially the same as for (ii), except that finiteness of
$\dim(A)$ is built into the assumption of this case in Proposition 8.54.

(vi). Here we use Theorem 8.61(ii), which tells us that
$\operatorname{codim}(B)\geq 1$, whence $B\not=A$. ∎

######  Remark 8.66.

When $\dim(A)\geq\aleph_{0}$,
$(E,S)=(\operatorname{Sing}(\mathcal{E}_{A}),\operatorname{End}(A))$ does not
satisfy any of the conditions of Lemma 4.61. Indeed, in this case Theorem
8.56(ii) gives $ES=\operatorname{PEnd}(A)\setminus\operatorname{End}(A)$, and
if $\alpha$ is any partial endomorphism with
$\operatorname{dom}(\alpha)\not=A=\operatorname{im}(\alpha)$, then no element
of ${E=\operatorname{Sing}(\mathcal{E}_{A})}$ is a right identity for
$\alpha$. This shows that condition (viii) of Lemma 4.61 does not hold, and
hence neither do any of the other conditions. (No such $\alpha$ exists if
$\dim(A)<\aleph_{0}$.)

######  Remark 8.67.

In the above proof we showed that condition (viii) of Lemma 4.61 was satisfied
for the cases in which $E=\operatorname{Sing}(\mathcal{E}_{A})$, apart from
the excluded case; condition (x) therefore holds as well. On the other hand,
condition (vii) is never satisfied (in these cases), apart from trivially
small exceptions. Examining the flow of implications in Lemma 4.61, it follows
that none of (i), (iii)–(vii) or (ix) hold. Condition (ii) is satisfied for
${(E,S)=(\operatorname{Sing}(\mathcal{E}_{A}),\operatorname{Sing}(\operatorname{End}(A))}$
with $\dim(A)<\aleph_{0}$, but not for the other two pairs.

It follows from Lemma 8.65 that Lemma 4.65 applies to each of the action pairs
listed in Proposition 8.54, with the exception of
$(\operatorname{Sing}(\mathcal{E}_{A}),\operatorname{End}(A))$ in the case
that $\dim(A)\geq\aleph_{0}$. More powerful results from Section 4.5—such as
Lemmas 4.71, 4.73 and 4.74, and also Theorems 6.27 and 6.43 from Chapter
6—involve pairs $(E,S)$ with $E$ a (commutative) monoid, satisfying various
conditions on joins of the right congruences $\theta_{e}$ (or $\Theta_{e}$) or
sub(semi)groups $S_{e}$, for $e\in E$. The pairs $(E,S)$ from Proposition 8.54
with $E=\operatorname{Sing}(\mathcal{E}_{A})$ are therefore excluded. Thus,
the remainder of Section 8.7 concerns pairs $(E,S)$ where:

  * •

$E=\mathcal{E}_{A}=\\{{\mathrm{id}_{B}}:{B\leq A}\\}$, and

  * •

$S$ is one of $\operatorname{End}(A)$,
$\operatorname{Sing}(\operatorname{End}(A))$ or $\operatorname{Aut}(A)$, where
we must additionally assume that ${\dim(A)<\aleph_{0}}$ in the second case.

Our main goal here is to determine which of the above-mentioned conditions
hold for these pairs.

Recall that for $B\leq A$, we have the right congruence
$\theta_{\mathrm{id}_{B}}$ on $S$, defined by

$\theta_{\mathrm{id}_{B}}=\big{\\{}{(\alpha,\beta)\in S\times
S}:{\mathrm{id}_{B}\cdot\alpha=\mathrm{id}_{B}\cdot\beta}\big{\\}}=\big{\\{}{(\alpha,\beta)\in
S\times
S}:{\alpha\mathord{\restriction}_{B}=\beta\mathord{\restriction}_{B}}\big{\\}}.$
(8.68)

(Since this depends on $S$, we will be careful to specify which of the above
choices of $S$ statements apply to.) To simplify notation, we write
$\theta_{B}$ for $\theta_{\mathrm{id}_{B}}$. It is clear that (for any $S$)

$B\subseteq C\ \Rightarrow\ \theta_{B}\supseteq\theta_{C}\qquad\text{for all
$B,C\leq A$.}$ (8.69)

It is also worth noting that
$\alpha\mathord{\restriction}_{B}=\beta\mathord{\restriction}_{B}$ (i.e.,
$(\alpha,\beta)\in\theta_{B}$) if and only if $\alpha$ and $\beta$ agree on a
basis of $B$.

The next two results apply to _strong_ independence algebras (cf. Definition
8.10). The first shows that Lemma 4.71(ii) applies to the pair
$(\mathcal{E}_{A},\operatorname{End}(A))$ for strong $A$:

######  Proposition 8.70.

If $S=\operatorname{End}(A)$ for a strong independence algebra $A$, then
$\theta_{B}\vee\theta_{C}=\theta_{B\cap C}$ for all $B,C\leq A$.

###### Proof.

By (8.69), we have $\theta_{B},\theta_{C}\subseteq\theta_{B\cap C}$, and hence
$\theta_{B}\vee\theta_{C}\subseteq\theta_{B\cap C}$. Thus, it remains to show
that ${\theta_{B\cap C}\subseteq\theta_{B}\vee\theta_{C}}$. To do so, fix some
$(\alpha,\beta)\in\theta_{B\cap C}$, meaning that

$\alpha,\beta\in\operatorname{End}(A)\qquad\text{and}\qquad\alpha\mathord{\restriction}_{B\cap
C}=\beta\mathord{\restriction}_{B\cap C}.$

Fix a basis $X$ for $B\cap C$, and extend this to bases $X\sqcup Y$ and
$X\sqcup Z$ for $B$ and $C$, respectively. By Lemma 8.12, $X\sqcup Y\sqcup Z$
is independent, so there exists an endomorphism
$\gamma\in\operatorname{End}(A)$ extending the map

$X\sqcup Y\sqcup Z\to A:\begin{cases}x\mapsto x\alpha=x\beta&\text{for $x\in
X$,}\\\ y\mapsto y\alpha&\text{for $y\in Y$,}\\\ z\mapsto z\beta&\text{for
$z\in Z$.}\end{cases}$

Since $\gamma$ agrees with $\alpha$ on the basis $X\sqcup Y$ of $B$ we have
$(\alpha,\gamma)\in\theta_{B}$. Similarly, $(\gamma,\beta)\in\theta_{C}$, so
it follows that $(\alpha,\beta)\in\theta_{B}\vee\theta_{C}$, as required. ∎

The situation for the pair
$(\mathcal{E}_{A},\operatorname{Sing}(\operatorname{End}(A)))$ is almost the
same as for $(\mathcal{E}_{A},\operatorname{End}(A))$, with one exception
(when $\dim(A)=2$ and $A$ has no constants). The next result concerns the
right congruences $\Theta_{B}=\Theta_{\mathrm{id}_{B}}$ on
$\operatorname{Sing}(\operatorname{End}(A))\cup\\{\mathrm{id}_{A}\\}$, defined
in (6.34). It is again clear that $B\subseteq C\ \Rightarrow\
\Theta_{B}\supseteq\Theta_{C}$ for all $B,C\leq A$; cf. (8.69).

######  Proposition 8.71.

If $S=\operatorname{Sing}(\operatorname{End}(A))$ for a finite-dimensional
strong independence algebra $A$, and if $[\dim(A)\not=2$ or $A$ has
constants$]$, then $\Theta_{B}\vee\Theta_{C}=\Theta_{B\cap C}$ for all
$B,C\leq A$.

###### Proof.

Again we must show that ${\Theta_{B\cap C}\subseteq\Theta_{B}\vee\Theta_{C}}$.
This is clear if $B$ and $C$ are comparable in the inclusion order, so suppose
instead that $B$ and $C$ are incomparable, and let
$(\alpha,\beta)\in\Theta_{B\cap C}$. Fix a basis $X$ for $B\cap C$, and extend
this to bases $X\sqcup Y$ and $X\sqcup Z$ for $B$ and $C$, respectively. So
again $X\sqcup Y\sqcup Z$ is independent. While it is possible for $X$ to be
empty, both $Y$ and $Z$ are non-empty (by incomparability). We now consider
separate cases. In each one, we define three singular endomorphisms
$\gamma_{1},\gamma_{2},\gamma_{3}\in\operatorname{Sing}(\operatorname{End}(A))$
such that

$\alpha\mathrel{\Theta}_{B}\gamma_{1}\mathrel{\Theta}_{C}\gamma_{2}\mathrel{\Theta}_{B}\gamma_{3}\mathrel{\Theta}_{C}\beta,$
(8.72)

which leads to $(\alpha,\beta)\in\Theta_{B}\vee\Theta_{C}$. The verification
that $\gamma_{1},\gamma_{2},\gamma_{3}$ are indeed singular, and that (8.72)
holds, is left to the reader.

Case 1. If $X\not=\varnothing$, then we fix some $x_{0}\in X$, and we let
$\gamma_{1},\gamma_{2},\gamma_{3}$ be any endomorphisms such that for $x\in
X$, $y\in Y$ and $z\in Z$,

$\displaystyle x\gamma_{1}$ $\displaystyle=x\alpha=x\beta,$ $\displaystyle
x\gamma_{2}$ $\displaystyle=x\alpha=x\beta,$ $\displaystyle x\gamma_{3}$
$\displaystyle=x\alpha=x\beta,$ $\displaystyle y\gamma_{1}$
$\displaystyle=y\alpha,$ $\displaystyle y\gamma_{2}$
$\displaystyle=x_{0}\alpha,$ $\displaystyle y\gamma_{3}$
$\displaystyle=x_{0}\alpha,$ $\displaystyle z\gamma_{1}$
$\displaystyle=x_{0}\alpha,$ $\displaystyle z\gamma_{2}$
$\displaystyle=x_{0}\alpha,$ $\displaystyle z\gamma_{3}$
$\displaystyle=z\beta.$

Case 2. If $X=\varnothing$ and $A$ has a constant $c$, then we let
$\gamma_{1},\gamma_{2},\gamma_{3}$ be any endomorphisms such that for $y\in Y$
and $z\in Z$,

$\displaystyle y\gamma_{1}$ $\displaystyle=y\alpha,$ $\displaystyle
y\gamma_{2}$ $\displaystyle=c,$ $\displaystyle y\gamma_{3}$ $\displaystyle=c,$
$\displaystyle z\gamma_{1}$ $\displaystyle=c,$ $\displaystyle z\gamma_{2}$
$\displaystyle=c,$ $\displaystyle z\gamma_{3}$ $\displaystyle=z\beta.$

Case 3. Finally, suppose $X=\varnothing$ and $A$ has no constants. By the
assumption in the statement of the lemma, we have $\dim(A)\not=2$, and so
since $\dim(A)\geq|Y|+|Z|\geq 2$, we must have $\dim(A)\geq 3$. By symmetry we
may assume that $|Y|\geq|Z|$, and we fix some $y_{0}\in Y$. We also extend
$Y\sqcup Z$ to a basis $Y\sqcup Z\sqcup W$ for $A$, noting that $W$ could be
empty. We then let $\gamma_{1},\gamma_{2},\gamma_{3}$ be any endomorphisms
such that for $y\in Y$, $z\in Z$ and $w\in W$,

$\displaystyle y\gamma_{1}$ $\displaystyle=y\alpha,$ $\displaystyle
y\gamma_{2}$ $\displaystyle=y_{0}\alpha,$ $\displaystyle y\gamma_{3}$
$\displaystyle=y_{0}\alpha,$ $\displaystyle z\gamma_{1}$
$\displaystyle=y_{0}\alpha,$ $\displaystyle z\gamma_{2}$
$\displaystyle=y_{0}\alpha,$ $\displaystyle z\gamma_{3}$
$\displaystyle=z\beta,$ $\displaystyle w\gamma_{1}$
$\displaystyle=y_{0}\alpha,$ $\displaystyle w\gamma_{2}$
$\displaystyle=y_{0}\alpha,$ $\displaystyle w\gamma_{3}$
$\displaystyle=y_{0}\alpha.$

(Singularity of $\gamma_{1}$ and $\gamma_{2}$ is clear, and also of
$\gamma_{3}$ when $W\not=\varnothing$. If $W=\varnothing$, then
${3\leq\dim(A)=|Y|+|Z|}$ and $|Y|\geq|Z|$ force $|Y|\geq 2$, and singularity
of $\gamma_{3}$ quickly follows.) ∎

Proposition 8.71 excluded the case in which $\dim(A)=2$ and $A$ has no
constants. We will soon show, in Proposition 8.74, that a weaker (but equally
powerful) condition holds in this case; cf. Remark 8.75. We begin with a
lemma.

######  Lemma 8.73.

Suppose $A$ is a two-dimensional independence algebra with no constants. Then
for any
$\alpha\in\operatorname{Sing}(\operatorname{End}(A))\cup\\{\mathrm{id}_{A}\\}$
we have $(\alpha,\mathrm{id}_{A})\in\Theta_{B}\vee\Theta_{C}$ for some
$B,C\in\operatorname{Max}(A)$.

###### Proof.

Only the case $\alpha\not=\mathrm{id}_{A}$ needs proof. Fix a basis
$\\{x,y\\}$ for $A$, and write $u=x\alpha$ and $v=y\alpha$. Since $\alpha$ is
singular, and since $A$ has no constants, we have
$\operatorname{rank}(\alpha)=1$, and it quickly follows that
$\operatorname{im}(\alpha)=\langle u\rangle=\langle v\rangle$. Let
$B_{1}=\langle x\rangle$, $B_{2}=\langle y\rangle$ and $C=\langle
u\rangle=\langle v\rangle$; each is maximal, by Proposition 8.22. Since
$C\not=A=\langle x,y\rangle$, we may assume by symmetry that $x\not\in
C=\langle u\rangle$. It follows from Lemma 8.2 that $\\{x,u\\}$ is
independent, and hence a basis for $A$. In this case we define
$\beta\in\operatorname{Sing}(\operatorname{End}(A))$ with $x\beta=u\beta=u$.
Then $\alpha\mathrel{\Theta}_{B_{1}}\beta\mathrel{\Theta}_{C}\mathrm{id}_{A}$,
so that $(\alpha,\mathrm{id}_{A})\in\theta_{B_{1}}\vee\theta_{C}$. ∎

######  Proposition 8.74.

If $S=\operatorname{Sing}(\operatorname{End}(A))$ for a two-dimensional
independence algebra $A$ with no constants, then for any $B<A$ we have

$\Theta_{B}=\bigvee_{C\in\operatorname{Max}(A),\atop B\subseteq C}\Theta_{C}.$

###### Proof.

Fix $B<A$, and write $\Sigma=\\{{C\in\operatorname{Max}(A)}:{B\subseteq
C}\\}$. By the assumptions on $A$, either $B=\varnothing(=\mathcal{C}(A))$ or
else $B\in\operatorname{Max}(A)$. In the latter case we have $\Sigma=\\{B\\}$,
and the result is trivial. So now we assume that $B=\varnothing$, and here we
have $\Sigma=\operatorname{Max}(A)$. Since
$\Theta_{B}=\Theta_{\varnothing}=\nabla_{S^{1}}$, we must show that
$\bigvee_{C\in\operatorname{Max}(A)}\Theta_{C}=\nabla_{S^{1}}$. For this it
suffices to show that any $\alpha\in
S=\operatorname{Sing}(\operatorname{End}(A))$ is $\sigma$-related to
$\mathrm{id}_{A}$, where
$\sigma=\bigvee_{C\in\operatorname{Max}(A)}\Theta_{C}$, and this follows
immediately from Lemma 8.73. ∎

######  Remark 8.75.

Proposition 8.71 feeds into Theorem 6.43(ii), and shows that (in the notation
of Theorems 6.35 and 6.43) relations $R_{2}$ may be replaced by
$R_{2}^{\prime\prime}$ for the pair
$(U,S)=(\mathcal{E}_{A},\operatorname{Sing}(\operatorname{End}(A)))$. Note
that $R_{2}^{\prime\prime}$ is defined with respect to a fixed generating set
$V=X_{U}\phi_{U}$ for $U=\mathcal{E}_{A}$, coming from a presentation
$U\cong\textup{{Mon}}\langle{X_{U}}:{R_{U}}\rangle$. When $A$ is finite-
dimensional, Proposition 8.22 (cf. Theorem 8.40) tells us that the most
obvious generating set $V$ for
${U=\mathcal{E}_{A}\cong(\operatorname{Sub}(A),\cap)}$ is

$V=\big{\\{}{\mathrm{id}_{B}}:{B\in\operatorname{Max}(A)}\big{\\}}.$

Proposition 8.71 excluded the case in which $A$ is two-dimensional and has no
constants. However, Proposition 8.74 shows that Theorem 6.43(i) applies in
this case with respect to the same set
$V=\\{{\mathrm{id}_{B}}:{B\in\operatorname{Max}(A)}\\}$, so that relations
$R_{2}$ may be replaced by $R_{2}^{\prime}$ in the notation of that theorem.
It follows that in fact $R_{2}^{\prime}=R_{2}^{\prime\prime}$ in this case.

######  Remark 8.76.

Even though Proposition 8.71 excluded the case in which $\dim(A)=2$ and $A$
has no constants, the conclusion of the proposition may still hold in this
case. For example, suppose $A=\\{1,2\\}$ with no operations, so that
$S=\operatorname{Sing}(\operatorname{End}(A))=\operatorname{Sing}(\mathcal{T}_{2})=\\{\alpha,\beta\\}$,
where $\alpha=\left(\begin{smallmatrix}1&2\\\ 1&1\end{smallmatrix}\right)$ and
$\beta=\left(\begin{smallmatrix}1&2\\\ 2&2\end{smallmatrix}\right)$. Recall
that Proposition 8.71 only needs proof when $B$ and $C$ are incomparable, and
up to symmetry this is only the case when $B=\\{1\\}$ and $C=\\{2\\}$. But
here we have $\alpha\mathrel{\Theta}_{B}\mathrm{id}_{A}$ and
$\beta\mathrel{\Theta}_{C}\mathrm{id}_{A}$, and it quickly follows that
$\Theta_{B}\vee\Theta_{C}=\nabla_{S^{1}}=\Theta_{\varnothing}=\Theta_{B\cap
C}$.

Keeping Remark 8.75 in mind, in order to give presentations for
$\operatorname{PEnd}(A)$ and $\operatorname{Sing}(\operatorname{PEnd}(A))$, we
will need to have generating sets for the right congruences $\theta_{B}$ and
$\Theta_{B}$ for $B\in\operatorname{Max}(A)$. It turns out that these are
extremely simple:

######  Lemma 8.77.

Let $A$ be an independence algebra with $\dim(A)\geq 1$, and additionally
assume that $\dim(A)\geq 2$ if $A$ has no constants. Then for any
${B\in\operatorname{Max}(A)}$, the right congruence $\theta_{B}$ on
$\operatorname{End}(A)$ is generated by the pair $(\alpha,\mathrm{id}_{A})$
for any idempotent $\alpha\in\operatorname{End}(A)$ with
$\operatorname{im}(\alpha)=B$.

###### Proof.

Throughout the proof we write $\sigma$ for the right congruence on
$\operatorname{End}(A)$ generated by $(\alpha,\mathrm{id}_{A})$.

Since $\alpha$ maps $\operatorname{im}(\alpha)=B$ identically (as it is an
idempotent), we have
$\mathrm{id}_{B}\cdot\alpha=\mathrm{id}_{B}=\mathrm{id}_{B}\cdot\mathrm{id}_{A}$.
This shows that $(\alpha,\mathrm{id}_{A})\in\theta_{B}$, and so
$\sigma\subseteq\theta_{B}$.

For the reverse inclusion, fix some $(\beta,\gamma)\in\theta_{B}$. For any
$x\in A$ we have $x\alpha\in B$ (as $\operatorname{im}(\alpha)=B$), so since
$\beta\mathord{\restriction}_{B}=\gamma\mathord{\restriction}_{B}$ it follows
that $x(\alpha\beta)=(x\alpha)\beta=(x\alpha)\gamma=x(\alpha\gamma)$, so that
$\alpha\beta=\alpha\gamma$. But also, since
$\mathrm{id}_{A}\mathrel{\sigma}\alpha$, and since $\sigma$ is a right
congruence, we have
$\beta=\mathrm{id}_{A}\cdot\beta\mathrel{\sigma}\alpha\beta=\alpha\gamma\mathrel{\sigma}\mathrm{id}_{A}\cdot\gamma=\gamma$.
∎

The next result has essentially the same proof:

######  Lemma 8.78.

Let $A$ be an independence algebra with $\dim(A)\geq 1$, and additionally
assume that $\dim(A)\geq 2$ if $A$ has no constants. Then for any
${B\in\operatorname{Max}(A)}$, the right congruence $\Theta_{B}$ on
$\operatorname{Sing}(\operatorname{End}(A))\cup\\{\mathrm{id}_{A}\\}$ is
generated by the pair $(\alpha,\mathrm{id}_{A})$ for any idempotent
$\alpha\in\operatorname{End}(A)$ with $\operatorname{im}(\alpha)=B$. ∎

######  Remark 8.79.

Lemmas 8.77 and 8.78 excluded the case in which $\dim(A)=1$ and $A$ has no
constants. But in this case
$\operatorname{PEnd}(A)=\operatorname{Aut}(A)\cup\\{\varnothing\\}$ and
$\operatorname{Sing}(\operatorname{PEnd}(A))=\\{\varnothing\\}$, as in Remark
8.20(vii). So it is trivial to derive a presentation for
$\operatorname{PEnd}(A)$ from a presentation for $\operatorname{Aut}(A)$, and
of course a presentation for $\operatorname{Sing}(\operatorname{PEnd}(A))$ is
trivial.

We now move on to the pair $(\mathcal{E}_{A},\operatorname{Aut}(A))$, and here
we do not need to assume $A$ is strong. Since $\operatorname{Aut}(A)$ is a
group, Lemma 4.73 applies, and shows that a generating set for the congruence
$\theta$ may be constructed using (generating sets for) the subgroups

$S_{\mathrm{id}_{B}}=\\{{\alpha\in\operatorname{Aut}(A)}:{\mathrm{id}_{B}=\mathrm{id}_{B}\cdot\alpha}\\}=\\{{\alpha\in\operatorname{Aut}(A)}:{\alpha\mathord{\restriction}_{B}=\mathrm{id}_{B}}\\}\qquad\text{for
$B\leq A$.}$ (8.80)

For simplicity again, we will abbreviate $S_{\mathrm{id}_{B}}$ to $S_{B}$.
Note that we have the alternative formulation in terms of fix sets:

$S_{B}=\big{\\{}{\alpha\in\operatorname{Aut}(A)}:{B\subseteq\operatorname{Fix}(\alpha)}\big{\\}}\qquad\text{for
$B\leq A$.}$

Lemma 4.74 gives conditions on these subgroups under which the generating set
for $\theta$ from Lemma 4.73 can be reduced further. The simpler of the two
conditions is in Lemma 4.74(ii), and says (in this case) that ${S_{B}\vee
S_{C}=S_{B\cap C}}$ for all $B,C\leq A$. Unfortunately, this does not hold in
general, even in the simple case that $A$ is a set of size $\geq 2$ (with no
operations), where $\operatorname{Aut}(A)$ is the symmetric group
$\mathcal{G}_{A}$. For example, if $A=B\sqcup C$, with $B$ and $C$ both non-
empty, then each element of $S_{B}$ and $S_{C}$ fixes $B$ and $C$ setwise; so
too therefore does each element of $S_{B}\vee S_{C}$. However, $S_{B\cap
C}=S_{\varnothing}$ is all of $\mathcal{G}_{A}$. Despite this, we will now
show that the weaker assumption of Lemma 4.74(i) does hold for the pair
$(\mathcal{E}_{A},\operatorname{Aut}(A))$ when $\dim(A)=n<\aleph_{0}$, with
respect to the set

$V=\\{{\mathrm{id}_{B}}:{B\leq A,\ n-2\leq\dim(B)\leq n-1}\\}.$

######  Proposition 8.81.

Let $A$ be an independence algebra with $\dim(A)=n<\aleph_{0}$, and let

$Q=\\{{B\leq A}:{n-2\leq\dim(B)\leq n-1}\\}.$

Then for any $B<A$ we have

$S_{B}=\bigvee_{C\in Q,\atop B\subseteq C}S_{C}.$

###### Proof.

As explained in Remark 4.75, we only need to demonstrate the forwards
inclusion. So let $\alpha\in S_{B}$, and fix a factorisation
$\alpha=\beta_{1}\cdots\beta_{k}$, for
$\beta_{1},\ldots,\beta_{k}\in\Gamma_{1}\cup\Gamma_{2}$, as in Theorem 8.47.
Also write $C_{i}=\operatorname{Fix}(\beta_{i})\in Q$ for each $i$, so that
each $C_{i}\supseteq\operatorname{Fix}(\alpha)\supseteq B$. But then

$\alpha=\beta_{1}\cdots\beta_{k}\in S_{C_{1}}\vee\cdots\vee
S_{C_{k}}\subseteq\bigvee_{C\in Q,\atop B\subseteq C}S_{C}.\qed$

######  Remark 8.82.

As in Theorem 8.50, the set $Q$ in Proposition 8.81 can be replaced by

$\\{{B\leq A}:{\dim(B)=n-2}\\}\qquad\text{or}\qquad\\{{B\leq
A}:{\dim(B)=n-1}\\},$

as appropriate, if the various conditions of Propositions 8.26 and 8.27, or
Lemma 8.34 hold.

####  8.8 Presentations

We conclude Chapter 8 by discussing presentations for the semigroups

$T_{1}=\operatorname{PEnd}(A),\qquad
T_{2}=\operatorname{Sing}(\operatorname{PEnd}(A))\qquad\text{and}\qquad
T_{3}=\operatorname{PAut}(A),$

where $A$ is a finite-dimensional strong independence algebra. As we have
seen, each arises as a product $T_{i}=ES_{i}$, where $E=\mathcal{E}_{A}$ and

$S_{1}=\operatorname{End}(A),\qquad
S_{2}=\operatorname{Sing}(\operatorname{End}(A))\qquad\text{and}\qquad
S_{3}=\operatorname{Aut}(A).$

We have already noted that presentations are not known for the $S_{i}$ in
general. However, it is possible to describe presentations for each $T_{i}$
modulo a presentation for the corresponding $S_{i}$.

For example, suppose $S=\operatorname{End}(A)$ has presentation
$\textup{{Mon}}\langle{X_{S}}:{R_{S}}\rangle$ via
$\phi_{S}:X_{S}^{*}\to\operatorname{End}(A)$. We know from Theorem 8.40 that
$E=\mathcal{E}_{A}(\cong\operatorname{Sub}(A)=\operatorname{Sub}^{\operatorname{f}}(A))$
has presentation $\textup{{Mon}}\langle{X_{E}}:{R_{E}}\rangle$ via
$\phi_{E}:X_{E}^{*}\to E:x_{B}\mapsto\mathrm{id}_{B}$. It then follows from
Theorem 6.4 that $ES=\operatorname{PEnd}(A)$ has presentation

$\textup{{Mon}}\langle{X_{E}\cup X_{S}}:{R_{E}\cup R_{S}\cup R_{1}\cup
R_{\Omega}}\rangle,$

where the additional sets of relations $R_{1}$ and $R_{\Omega}$ are as
follows. For the former (and making the respective notational substitutions
$z$ and $x_{B}$ for the letters $x\in X_{S}$ and $y\in X_{E}(=X_{U})$ in the
original definition of $R_{1}$ in (6.3)), we have

$R_{1}=\big{\\{}{(zx_{B},{}^{z}x_{B}\cdot z)}:{z\in X_{S},\
B\in\operatorname{Max}(A)}\big{\\}},$

where ${}^{z}x_{B}$ is some word over $X_{E}$ mapping to
${}^{z\phi_{S}}\mathrm{id}_{B}=\mathrm{id}_{B(z\phi_{S})^{-1}}$. As explained
in Remark 6.5 (see (6.8), by Proposition 8.70 and Lemma 8.77 (and excluding
trivial small cases), we can take

$R_{\Omega}=\big{\\{}{(x_{B},x_{B}N_{S}(\alpha_{B}))}:{B\in\operatorname{Max}(A)}\big{\\}},$

where for each $B\in\operatorname{Max}(A)$,
$\alpha_{B}\in\operatorname{End}(A)$ is some fixed idempotent with image $B$,
and where ${N_{S}:\operatorname{End}(A)\to X_{S}^{*}}$ is a normal form
function.

The situation for $S=\operatorname{Sing}(\operatorname{End}(A))$ is very
similar. We first note that $(E,S)$ satisfies Assumption 6.32, with $E$
commutative. We may therefore apply Theorem 6.43, Propositions 8.71 and 8.74,
and Remark 8.75. The latter explains whether to use part (i) or (ii) of
Theorem 6.43, but in either case the resulting presentation for
$\operatorname{Sing}(\operatorname{PEnd}(A))$ has the form

$\textup{{Sgp}}\langle{X_{E}\cup X_{S}}:{R_{E}\cup R_{S}\cup R_{1}\cup
R_{2}^{\prime\prime}}\rangle,$

where this time $\textup{{Sgp}}\langle{X_{S}}:{R_{S}}\rangle$ is a
presentation for $S=\operatorname{Sing}(\operatorname{End}(A))$. The sets
$R_{1}$ and $R_{2}^{\prime\prime}$ here have the same form as $R_{1}$ and
$R_{\Omega}$ above (for $S=\operatorname{End}(A)$). Note that ${}^{z}x_{B}\in
X_{E}^{*}$ might be empty, but $N_{S}(\alpha_{B})\in X_{S}^{+}$ is always non-
empty.

In the case that $S=\operatorname{Aut}(A)$, Theorem 6.4 and Remark 6.5 apply,
drawing from Lemma 4.74(i) and Proposition 8.81. These yield the presentation

$\textup{{Mon}}\langle{X_{E}\cup X_{S}}:{R_{E}\cup R_{S}\cup R_{1}\cup
R_{\Omega}}\rangle,$

where $R_{1}$ is yet again as above, and

$\displaystyle R_{\Omega}$ $\displaystyle=\big{\\{}{(x_{B},x_{B}\cdot
N_{S}(\alpha))}:{B\in\operatorname{Max}(A),\ \alpha\in\Gamma_{B}}\big{\\}}$
$\displaystyle\quad\cup\big{\\{}{(x_{B}x_{C},x_{B}x_{C}\cdot
N_{S}(\alpha))}:{B,C\in\operatorname{Max}(A),\ B\not=C,\
\alpha\in\Gamma_{B\cap C}}\big{\\}},$ (8.83)

where each $\Gamma_{B}$ is a generating set for $S_{B}=S_{\mathrm{id}_{B}}$.
Such generating sets can be deduced from Theorems 8.47 and 8.50. As in Remark
8.82, we only need one of the two sets in the union (8.83) if any of the
conditions of Theorem 8.50 hold.

###  9 Wreath products and free acts

This final chapter concerns a number of (transformational) wreath products
$M\wr S$, where $M$ is an arbitrary monoid, and $S$ is a subsemigroup of some
partial transformation semigroup $\mathcal{P}\mathcal{T}_{X}$. The standard
way to define the wreath product $M\wr\mathcal{T}_{X}$ is as a semidirect
product $M^{X}\rtimes\mathcal{T}_{X}$, where $M^{X}$ is the direct product of
$|X|$ copies of $M$, and where $\mathcal{T}_{X}$ acts on the coordinates of
tuples from $M^{X}$; the full definitions are given below. (This distinguishes
the _transformational_ wreath products from the _unrestricted_ wreath products