Correspondence functors and duality

Serge Bouc, Jacques Thévenaz

► To cite this version:

Serge Bouc, Jacques Thévenaz. Correspondence functors and duality. Journal of Algebra, 2023, 617, pp.425-475. 10.1016/j.jalgebra.2022.10.028. hal-04020769

HAL Id: hal-04020769

https://u-picardie.hal.science/hal-04020769v1

Submitted on 10 Sep 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Correspondence functors and duality

<figure><img src="image_2.png" /></figure>

Serge Bouc<sup>a</sup>, Jacques Thévenaz<sup>b,*</sup>

<sup>a</sup> CNRS-LAMFA, Université de Picardie - Jules Verne, 33, rue St Leu, F-80039
Amiens Cedex 1, France

<sup>b</sup> Institut de mathématiques, EPFL, Station 8, CH-1015 Lausanne, Switzerland

## ARTICLE INFO

*Article history:* Received 5 November 2021 Available online 15 November 2022 Communicated by Markus Linckelmann

*MSC:*

06B05
06B15
06D05
06D50
16B50
18B05
18B10
18B35
18E05

*Keywords:*

Finite set
Correspondence
Functor category
Simple functor
Poset
Lattice

## ABSTRACT

A correspondence functor is a functor from the category of finite sets and correspondences to the category of *k*-modules, where *k* is a commutative ring. By means of a suitably defined duality, new correspondence functors are constructed, having remarkable properties. In particular, their evaluation at any finite set is always a free *k*-module and an explicit formula is obtained for its rank. The results use some subtle new ingredients from the theory of finite lattices.

© 2022 The Authors. Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

<footnote>* Corresponding author.</footnote>

<footnote>E-mail addresses: serge.bouc@u-picardie.fr (S. Bouc), jacques.thevenaz@epfl.ch (J. Thévenaz).</footnote>
# 1. Introduction

Over the last few decades, the representation theory of small categories has played an increasingly important role in algebra, see for instance [1,8,9,11,13,14]. In the special case of the category with finite sets as objects and correspondences as morphisms, this theory turns out to be very rich and has been developed in [3–7]. A correspondence functor is a functor from the category of finite sets and correspondences to the category of $k$-modules, where $k$ is a commutative ring. In particular, simple functors have been classified and a $k$-basis has been obtained for their evaluation at any finite set, with an explicit formula for the rank. The key for such results is the construction of some special functors $S_{E,R}$, which we called fundamental functors, depending on a finite set $E$ and a partial order relation $R$ on $E$. The purpose of the present paper is to obtain a vast generalisation of this construction.

For any finite lattice $T$, we studied in [4] a correspondence functor $F_T$ whose evaluation $F_T(X)$ at a finite set $X$ is equal to the free $k$-module on the set $T^X$ of all maps from $X$ to $T$. Associated with any join-morphism $\alpha : T \to T^{\text{lop}}$ of finite lattices, we introduce here a suitable pairing of functors $F_T \times F_{T'} \to k$ and, by passing to the quotient by the left kernel $K_\alpha$ of this pairing, we obtain a correspondence functor $S_\alpha = F_T/K_\alpha$ which only depends on the given morphism $\alpha$. The opposite of $T'$ appears for reasons explained in the construction. One of our main results produces a $k$-basis for the evaluation $S_\alpha(X)$ at a finite set $X$, with an explicit formula for the rank. The fundamental functors $S_{E,R}$ mentioned above are just a very special case.

After a preliminary section on correspondence functors, we carry out in Section 3 the construction of $S_\alpha$. For any given join-morphism $\alpha : T \to T^{\text{lop}}$ of finite lattices, this construction uses a certain subset $\Phi_\alpha$ of the set $\text{Irr}(T)$ of all join-irreducible elements of the lattice $T$.

Finite lattices played a central role throughout our work in [4,5] and this is again the case here. Actually, several new structural results on the lattice $T$ can be brought out from the mere presence of the join-morphism $\alpha$. This lattice-theoretic part is developed in Section 4 and is a cornerstone for what comes next.

In Section 5, we produce a set of generators for $S_\alpha(X)$, where $X$ is any finite set, and we then prove in Section 6 that this generating set is a $k$-basis of $S_\alpha(X)$. The key ingredient is a subset $G_\alpha$ of $T$ containing $\Phi_\alpha$, defined using the lattice-theoretic developments of Section 4. The main result takes the following form:

**1.1. Theorem.** Let $\alpha : T \to T^{\text{lop}}$ be a join-morphism of finite lattices. Then for any finite set $X$, the set $\{\varphi \in T^X \mid \Phi_\alpha \subseteq \varphi(X) \subseteq G_\alpha\}$ maps bijectively to a $k$-basis of $S_\alpha(X) = F_T(X)/K_\alpha(X)$.

As mentioned above, this result generalises the theorem obtained in [5] for fundamental functors and the methods are inspired by those used there, but the actual proofs are
new and more involved. The mere fact that the theorem proved in [5] is a special case is not obvious and needs to be established. We do so in Section 7.

In Section 8, we mention the more specific case when $\alpha$ is injective and in Section 9 we give an explicit description of the minimal nonzero evaluation $S_\alpha(\Phi_\alpha)$. Finally, in Sections 10 and 11, two rather intricate results are proved, which will be used in a future paper but are also of independent interest.

## 2. Preliminaries

Finite lattices are essential tools in [4–7] and they continue to play a crucial role in the present work. If $T$ is a finite lattice, we write $\leq$ for its (partial) order relation, $\lor$ for its join, $\land$ for its meet, $\hat{0}_T$, or simply $\hat{0}$, for its minimal element and $\hat{1}_T$, or simply $\hat{1}$, for its maximal element. For any $s, t \in T$ with $s \leq t$, intervals are defined by

$$[s, t] = \{a \in T \mid s \leq a \leq t\}, \quad ]s, t] = \{a \in T \mid s < a \leq t\}, \quad [s, t[ = \{a \in T \mid s \leq a < t\}.$$

We occasionally write $[s, t]_T = [s, t]$ when we need to emphasize that we work inside the ambient lattice $T$. An element of $T$ is called *irreducible* (or join-irreducible) if it cannot be written as the join of some subset of strictly smaller elements of $T$. In particular, $\hat{0}$ is not irreducible because it is an empty join. We write $\text{Irr}(T)$ for the set of irreducible elements of $T$, viewed as a full subposet of $T$. The opposite lattice $T^{op}$ of a finite lattice $T$ is obtained by reversing the partial order, swapping $\lor$ and $\land$ and also swapping $\hat{0}$ and $\hat{1}$.

We work with the category $\mathcal{L}$ having all finite lattices as objects and join-morphisms as morphisms. Recall that a map $\alpha : T \to T'$ between two finite lattices is a *join-morphism* if, for any (finite) subset $S$ of $T$, we have

$$\alpha(\bigvee_{s \in S} s) = \bigvee_{s \in S} \alpha(s)$$

and in particular $\alpha(\hat{0}) = \hat{0}$ by using an empty join. Equivalently, $\alpha$ is a join-morphism if and only if $\alpha(s \lor t) = \alpha(s) \lor \alpha(t)$ for all $s, t \in T$ and $\alpha(\hat{0}) = \hat{0}$. It would be natural to view $\mathcal{L}$ as the category of finite join-semilattices, but we do not do so, because a finite join-semilattice is in fact a lattice. Indeed, recall that the meet $s \land t$ is uniquely determined by the (finite) join

$$s \land t = \bigvee_{\substack{a \in T \\ a \leq s \\ a \leq t}} a.$$

We use only join-morphisms as morphisms between finite lattices. We emphasize that, in general, a join-morphism does not preserve meets. Consequently, the image $\text{Im}(\alpha)$ of a join-morphism $\alpha : T \to T'$ may not be a sublattice of $T'$. More precisely, $\text{Im}(\alpha)$ is only join-closed in $T'$ and the meet of $\text{Im}(\alpha)$ inherited by its join is in general different from the meet of $T'$.
Whenever $k$ is a commutative ring, we also need the $k$-linearization $k\mathcal{L}$ of the category $\mathcal{L}$. Its objects are again the finite lattices, the set of morphisms $\operatorname{Hom}_{k\mathcal{L}}(T, T')$ is the free $k$-module with basis $\operatorname{Hom}_{\mathcal{L}}(T, T')$, and the composition of morphisms is the $k$-bilinear extension of the composition in $\mathcal{L}$.

If $\alpha : T \to T'$ is a join-morphism, then $\alpha^{op} : T'^{op} \to T^{op}$ is the map defined by

$$ \alpha^{op}(t') = \bigvee_{\substack{t \in T \\ \alpha(t) \le t'}} t. $$

In other words, $\alpha^{op}(t')$ is the greatest element of $\alpha^{-1}(\langle \hat{0}, t' \rangle)$. This definition goes back to E.H. Spanier and J.H.C. Whitehead [12,15], who introduced this functorial duality in the category of join-homomorphisms of finite lattices but used it only for their main interest, namely CW-complexes and CW-lattices. It is proved in Section 4 of [12], or in Lemma 8.1 of [4], that $\alpha^{op}$ is a join-morphism from $T'^{op}$ to $T^{op}$ and that $(\alpha^{op})^{op} = \alpha$.

Now we move to representation theory, as developed in [3–5]. We recall that a correspondence $R$ from a finite set $X$ to a finite set $Y$ is just a subset of $Y \times X$ and that $R^{op} \subseteq X \times Y$ is defined by $(x, y) \in R^{op}$ if and only if $(y, x) \in R$. Moreover, correspondences can be composed in the usual way: if $S \subseteq Z \times Y$ and $R \subseteq Y \times X$, then

$$ SR = \{(z, x) \in Z \times X \mid \exists y \in Y \text{ such that } (z, y) \in S \text{ and } (y, x) \in R\}. $$

If $k$ is a commutative ring, a correspondence functor (over $k$) is a functor from the category of finite sets and correspondences to the category of $k$-modules. We let $\mathcal{F}_k$ be the category of all correspondence functors over $k$, with natural transformations as morphisms. This is an abelian category. If $F$ is a correspondence functor and $R \subseteq Y \times X$ is a correspondence, we use a left action of $R$ for the $k$-linear map $F(R) : F(X) \to F(Y)$, namely we set, for any $v \in F(X)$,

$$ R \cdot v = F(R)(v) \in F(Y), $$

and we often omit the dot and write simply $Rv$.

A main example is the correspondence functor $F_T$ associated with a finite lattice $T$, introduced in [4]. Its evaluation at a finite set $X$ is the free $k$-module with basis $T^X$, where $T^X$ denotes the set of all maps $X \to T$. For any $\varphi \in T^X$, the left action $R\varphi$ of a correspondence $R \subseteq Y \times X$ is the map $Y \to T$ defined by

$$ (R\varphi)(y) = \bigvee_{\substack{x \in X \\ (y,x) \in R}} \varphi(x). $$

It is very easy to check that $F_T$ is a correspondence functor. Any join-morphism $\alpha : T \to T'$ induces a $k$-linear map $F_\alpha : F_T \to F_{T'}$ defined on the $k$-basis by $F_\alpha(\varphi) = \alpha \circ \varphi$, for any $\varphi \in T^X$. The following main result is Theorem 4.8 in [4].
**2.1. Theorem.** The assignment sending a finite lattice $T$ to $F_T$, and a join-morphism $\alpha : T \to T'$ to the $k$-linear map $F_\alpha : F_T \to F_{T'}$, yields a $k$-linear functor

$$F_? : k\mathcal{L} \to \mathcal{F}_k$$

which is fully faithful.

We end this section with a discussion of duality, which is a main tool in this paper. Let $F$ be a correspondence functor over $k$. The dual $F^\dagger$ of $F$ is the correspondence functor defined by $F^\dagger(X) = \operatorname{Hom}_k(F(X), k)$ for any finite set $X$ and

$$(R \cdot g)(v) = g(R^{op} \cdot v)$$

for any $R \subseteq Y \times X$, $g \in F^\dagger(X)$ and $v \in F(Y)$. Whenever $F$ and $G$ are correspondence functors, a *functorial pairing* $F \times G \to k$ is a family of $k$-bilinear forms

$$(-, -)_X : F(X) \times G(X) \to k,$$

where $X$ runs through finite sets, satisfying

$$(Ru, v)_Y = (u, R^{op}v)_X$$

for all $u \in F(X)$, $v \in G(Y)$, and $R \subseteq Y \times X$. It is elementary to check that a functorial pairing $F \times G \to k$ induces a morphism of correspondence functors

$$\lambda : G \to F^\dagger$$

and that conversely any such $\lambda$ determines a functorial pairing $F \times G \to k$.

An important example is provided by the following construction. Whenever $T$ is a finite lattice, consider the family of $k$-bilinear forms

$$(-|-)_X : F_T(X) \times F_{T^{op}}(X) \to k$$

defined on the $k$-bases elements $\varphi \in T^X$ and $\psi \in (T^{op})^X$ by

$$(\varphi | \psi)_X = \begin{cases} 1 & \text{if } \varphi \le \psi, \text{ i.e. } \varphi(x) \le \psi(x), \forall x \in X, \\ 0 & \text{otherwise.} \end{cases}$$

This defines a functorial pairing $F_T \times F_{T^{op}} \to k$, by Lemma 8.6 in [4]. Our next result is Theorem 8.9 in [4].
## 2.2. Proposition.

(a) The basis $T^X$ of $F_T(X)$ has a dual basis, namely a basis $\{\psi^* | \psi \in T^X\}$ of $F_{T^{\text{op}}}$ given by

$$ \psi^* = \sum_{\substack{\rho \in T^X \\ \rho \le \psi}} \mu(\rho, \psi) \rho^o, $$

where $\rho^o$ is the map $\rho$, viewed as a map from $X$ to $T^{\text{op}}$, and where $\mu$ denotes the Möbius function of the poset $T^X$.

(b) The morphism $\lambda: F_{T^{\text{op}}} \to F_T^{\text{b}}$ induced by the functorial pairing above is an isomorphism (i.e. nondegeneracy in the strong sense).

# 3. The main constructions

Let $T$ and $T'$ be finite lattices. The main purpose of this section is to construct, by means of a suitably defined functorial pairing $F_T \times F_{T'} \to k$, a quotient functor of $F_T$ obtained by passing to the quotient by the left kernel of this pairing. This provides a way of constructing many new correspondence functors, which turn out to have remarkable properties. We will see later in Section 7 that the fundamental functors introduced in [4] are very special cases of the present general construction.

The main context for our constructions is the following. Let $\alpha: T \to T'$ and $\beta: T' \to T$ be maps such that

$$ \forall (t, t') \in T \times T', \quad t' \le \alpha(t) \iff t \le \beta(t'). \qquad (3.1) $$

## 3.2. Lemma. Let $T$ and $T'$ be finite lattices.

(a) If the maps $\alpha: T \to T'$ and $\beta: T' \to T$ satisfy Condition 3.1, then $\alpha$ is a join-morphism from $T$ to $T^{\text{op}}$ and $\beta$ is a join-morphism from $T'$ to $T^{\text{op}}$. In particular, the maps $\alpha: T \to T'$ and $\beta: T' \to T$ are order-reversing.

(b) $\beta$ is equal to $\alpha^{\text{op}}: (T^{\text{op}})^{\text{op}} = T' \to T^{\text{op}}$. In particular, $\beta$ is uniquely determined by $\alpha$.

(c) Conversely, if $\alpha: T \to T^{\prime \text{op}}$ is a join-morphism and if we set $\beta = \alpha^{\text{op}}$, then $\alpha$ and $\beta$ fulfil Condition 3.1.

**Proof.** (a) For any $t_1, t_2 \in T$ and for any $t' \in T'$, we have

$$ \begin{align*} t' \le \alpha(t_1 \vee t_2) &\iff t_1 \vee t_2 \le \beta(t') \\ &\iff t_1 \le \beta(t') \text{ and } t_2 \le \beta(t') \\ &\iff t' \le \alpha(t_1) \text{ and } t' \le \alpha(t_2) \end{align*} $$
$$ \iff t' \leq \alpha(t_1) \wedge \alpha(t_2). $$

It follows that $\alpha(t_1 \lor t_2) = \alpha(t_1) \wedge \alpha(t_2)$. Similarly $\beta(t'_1 \lor t'_2) = \beta(t'_1) \wedge \beta(t'_2)$ for any $t'_1, t'_2 \in T'$.

(b) It follows from Condition 3.1 that

$$ \forall t' \in T', \beta(t') = \bigvee_{\substack{t \in T \\ t \leq \beta(t')}} t = \bigvee_{\substack{t \in T \\ t' \leq \alpha(t)}} t. $$

In other words $\beta = \alpha^{op}$.

(c) The definition of $\beta = \alpha^{op}$ yields the above formula for $\beta(t')$. If $t' \leq \alpha(t)$, then $t$ is one of the terms in the join and therefore $t \leq \beta(t')$. For the reverse implication, use the fact that $\beta^{op} = \alpha$ and apply the same argument. $\square$

**3.3. Convention.** Lemma 3.2 shows that we only need a given join-morphism $\alpha : T \to T'^{op}$ to obtain an associated map $\beta$ satisfying Condition 3.1. For this reason, we shall always work with a fixed join-morphism $\alpha$ and use a notation which includes $\alpha$ if necessary. Moreover, for the sake of simplicity, we shall usually define $\beta = \alpha^{op}$.

**3.4. Lemma.** Let $T$ and $T'$ be finite lattices, let $\alpha : T \to T'^{op}$ be a join-morphism, and let $\beta = \alpha^{op}$.

(a) $t \leq \beta\alpha(t)$, for any $t \in T$, and $t' \leq \alpha\beta(t')$, for any $t' \in T'$.

(b) $\alpha\beta\alpha = \alpha$ and $\beta\alpha\beta = \beta$.

**Proof.** Both assertions follow from the fact that $\beta$ and $\alpha$ are adjoint contravariant functors between $T$ and $T'$, viewed as categories. In more elementary terms, for $t \in T$, Condition 3.1 applied to $t' = \alpha(t)$ implies that $t \leq \beta\alpha(t)$. Similarly $t' \leq \alpha\beta(t')$, for any $t' \in T'$. Taking $t' = \alpha(t)$ gives $\alpha(t) \leq \alpha\beta\alpha(t)$. On the other hand $\alpha(t) \geq \alpha\beta\alpha(t)$ because $t \leq \beta\alpha(t)$ and $\alpha$ is order-reversing. Therefore $\alpha\beta\alpha = \alpha$, and similarly $\beta\alpha\beta = \beta$. $\square$

It follows from Lemmas 3.2 and 3.4 that $\alpha$ and $\beta$ are inverse Galois connections of posets (see Chapter 3 of [10] for this standard notion). We can also view $\alpha$ and $\beta$ as adjoint contravariant functors if we consider the posets $T$ and $T'$ as categories in the usual way.

We now introduce the main ingredient for our constructions.

**3.5. Notation.** Given a join-morphism $\alpha : T \to T'^{op}$ and $\beta = \alpha^{op}$, we set

$$ \Phi_{\alpha} := \{f \in \mathrm{Irr}(T) \mid \alpha(f) \in \mathrm{Irr}(T'), \beta\alpha(f) = f\}, $$

$$ \Phi'_{\alpha} := \{f' \in \mathrm{Irr}(T') \mid \beta(f') \in \mathrm{Irr}(T), \alpha\beta(f') = f'\}. $$
We view $\Phi_{\alpha}$ and $\Phi'_{\alpha}$ as full subposets of $T$ and $T'$, respectively. Whenever there is no
possible confusion, we will also write $\Phi = \Phi_{\alpha}$ and $\Phi' = \Phi'_{\alpha}$. We observe that, if we switch
the roles of $T, T'$ and $\alpha, \beta$, we obtain $\Phi_{\beta} = \Phi'_{\alpha}$ and $\Phi'_{\beta} = \Phi_{\alpha}$.

We emphasize that the definition of $\Phi'_{\alpha}$ involves the irreducible elements of $T'$ and not those of $T'^{op}$, despite the fact that the target of $\alpha$ is $T'^{op}$. Our next lemma also uses implicitly this remark.

**3.6. Lemma.** The restriction of $\alpha$ to $\Phi_{\alpha}$ is a poset isomorphism $\Phi_{\alpha} \to \Phi_{\alpha}^{op}$. The inverse isomorphism $\Phi'_{\alpha} \to \Phi_{\alpha}^{op}$ is the restriction of $\beta$ to $\Phi'_{\alpha}$.

**Proof.** Since $\alpha$ and $\beta$ are both order-reversing maps, it suffices to prove that the restrictions of $\alpha$ to $\Phi = \Phi_\alpha$ and the restriction of $\beta$ to $\Phi' = \Phi'_\alpha$ are bijections, and inverse to one another. If $f \in \Phi$, then $f' = \alpha(f) \in \text{Irr}(T')$ by the definition of $\Phi$, and $f = \beta(f')$. Hence $\beta(f') \in \text{Irr}(T)$, and $\alpha\beta(f') = \alpha\beta\alpha(f) = \alpha(f) = f'$, by Lemma 3.4. It follows that $f' \in \Phi'$, so $\alpha(\Phi) \subseteq \Phi'$. The reverse inclusion also holds because $\alpha\beta(f') = f'$ for any $f' \in \Phi'$. Therefore $\alpha(\Phi) = \Phi'$, and similarly $\beta(\Phi') = \Phi$. $\square$

Our next lemma introduces the technical conditions which will be used for the defi-
nition of the functorial pairing we are aiming for. Recall that the notation $\varphi_1 \le \varphi_2$ for
$\varphi_1, \varphi_2 \in T^X$ means that $\varphi_1(x) \le \varphi_2(x)$ for all $x \in X$.

**3.7. Lemma.** Let $X$ be a finite set. For any maps $\varphi \in T^X$ and $\psi \in (T')^X$, the following conditions are equivalent:

(a) $\psi \le \alpha \circ \varphi$ and, for any $f \in \Phi_\alpha$, there exists $x \in X$ such that $\varphi(x) = f$ and $\psi(x) = \alpha(f)$.

(b) $\varphi \le \beta \circ \psi$ and, for any $f' \in \Phi'_{\alpha}$, there exists $x \in X$ such that $\psi(x) = f'$ and $\varphi(x) = \beta(f')$.

(c) $\psi\varphi^{-1}(t) \subseteq [0, \alpha(t)]$ for any $t \in T$, and $\alpha(f) \in \psi\varphi^{-1}(f)$ for any $f \in \Phi_\alpha$.

(d) $\varphi\psi^{-1}(t') \subseteq [0, \beta(t')]$ for any $t' \in T'$, and $\beta(f') \in \varphi\psi^{-1}(f')$ for any $f' \in \Phi'_{\alpha}$.

**Proof.** Clearly $\psi \le \alpha \circ \varphi$ if and only if $\varphi \le \beta \circ \psi$, by Condition 3.1. Assume that for any $f \in \Phi_\alpha$, there exists $x \in X$ are such that $\varphi(x) = f$ and $\psi(x) = \alpha(f)$. By Lemma 3.6, for any $f' \in \Phi'_\alpha$, the element $f = \beta(f')$ belongs to $\Phi_\alpha$, and $f' = \alpha(f)$. Hence there exists $x \in X$ such that $\varphi(x) = f = \beta(f')$, and $\psi(x) = \alpha(f) = f'$. So (a) implies (b). Switching $T, T'$ and $\alpha, \beta$, we get that (b) implies (a).

Now if (a) holds, then for $t \in T$ and $x \in \varphi^{-1}(t)$, we have $\psi(x) \le \alpha(t)$. Hence
$\psi\varphi^{-1}(t) \subseteq [0, \alpha(t)]$. Moreover, if $f \in \Phi_\alpha$, there exists $x \in \varphi^{-1}(f)$ such that $\psi(x) = \alpha(f)$,
hence $\alpha(f) \in \psi\varphi^{-1}(f)$. So (a) implies (c).

Conversely, if (c) holds, then for any $x \in X$, setting $t = \varphi(x)$, we have $x \in \varphi^{-1}(t)$,
hence $\psi(x) \in [0, \alpha(t)]$. Thus $\psi(x) \le \alpha\varphi(x)$ and so $\psi \le \alpha \circ \varphi$. Moreover, for any $f \in \Phi_\alpha$,
we have $\alpha(f) \in \psi\varphi^{-1}(f)$, so there exists $x \in \varphi^{-1}(f)$ such that $\alpha(f) = \psi(x)$. Thus $\varphi(x) = f$ and $\psi(x) = \alpha(f)$. Hence (c) implies (a).

Switching $T, T'$ and $\alpha, \beta$, we see that (b) is equivalent to (d) and this completes the proof. $\square$

**3.8. Notation.** Let $\varphi \in T^X$ and $\psi \in (T')^X$. If the equivalent conditions of Lemma 3.7 hold, we will write $\varphi \vdash_{\alpha} \psi$, or simply $\varphi \vdash \psi$ when there is no possible confusion.

For each finite set $X$, we define a $k$-bilinear form

$$ \langle -,- \rangle_{\alpha,X} : F_T(X) \times F_{T'}(X) \to k $$

by setting, for all maps $\varphi \in T^X$ and $\psi \in (T')^X$,

$$ \langle \varphi, \psi \rangle_{\alpha, X} = \begin{cases} 1 & \text{if } \varphi \vdash_{\alpha} \psi, \\ 0 & \text{otherwise.} \end{cases} $$

We also write $\langle -,- \rangle_X = \langle -,- \rangle_{\alpha,X}$ when there is no possible confusion. We observe that $\varphi \vdash_{\alpha} \psi$ if and only if $\psi \vdash_{\beta} \varphi$, by Lemma 3.7. Therefore $\langle \varphi, \psi \rangle_{\alpha,X} = \langle \psi, \varphi \rangle_{\beta,X}$.

**3.9. Proposition.** Let $\alpha : T \to T'^{op}$ be a join-morphism. The family of bilinear forms $\langle -,- \rangle_{\alpha,X}$ defines a functorial pairing

$$ \langle -,- \rangle_{\alpha} : F_T \times F_{T'} \to k. $$

**Proof.** We have to prove that $\langle S\varphi, \psi \rangle_{\alpha,Y} = \langle \varphi, S^{op}\psi \rangle_{\alpha,X}$, where $X$ and $Y$ are finite sets, $\varphi \in T^X$, $\psi \in (T')^Y$, and $S \subseteq Y \times X$ is a correspondence. First we claim that

$$ \psi \le \alpha \circ (S\varphi) \iff S^{op}\psi \le \alpha \circ \varphi. $$

Recall that $(S\varphi)(y) = \bigvee_{(y,x) \in S} \varphi(x)$ for any $y \in Y$, by the definition of $S\varphi$. Therefore, the condition $\psi \le \alpha \circ (S\varphi)$ is equivalent to

$$ \forall y \in Y, \psi(y) \le \alpha \left( \bigvee_{(y,x) \in S} \varphi(x) \right) = \bigwedge_{(y,x) \in S} \alpha \varphi(x), $$

that is,

$$ \forall (y,x) \in S, \psi(y) \le \alpha \varphi(x). $$

This in turn is equivalent to the condition

$$ \bigvee_{(x,y) \in S^{op}} \psi(y) \le \alpha \varphi(x), $$
that is,

$$ \forall x \in X, (S^{op}\psi)(x) \leq \alpha\varphi(x). $$

Thus we have obtained $S^{op}\psi \leq \alpha \circ \varphi$, proving the claim.

Assume now that $\langle S\varphi, \psi \rangle_{\alpha, Y} = 1$, that is, $S\varphi \vdash_{\alpha} \psi$. In particular $\psi \leq \alpha \circ (S\varphi)$, which is equivalent to $S^{op}\psi \leq \alpha \circ \varphi$, by the claim above. Moreover, for any $f \in \Phi_{\alpha}$, there exists an element $y \in Y$ such that $(S\varphi)(y) = f$ and $\psi(y) = \alpha(f)$. Then

$$ f = (S\varphi)(y) = \bigvee_{(y,x) \in S} \varphi(x) $$

and since $f$ is irreducible, there exists $x \in X$ with $(y, x) \in S$ such that $f = \varphi(x)$. Therefore

$$ \alpha(f) = \psi(y) \leq \bigvee_{(y',x) \in S} \psi(y') = \bigvee_{(x,y') \in S^{op}} \psi(y') = (S^{op}\psi)(x) \leq (\alpha \circ \varphi)(x) = \alpha(f), $$

and so we get an equality $(S^{op}\psi)(x) = \alpha(f)$. Thus for any $f \in \Phi_{\alpha}$, there exists an element $x \in X$ such that $\varphi(x) = f$ and $(S^{op}\psi)(x) = \alpha(f)$. Hence $\varphi \vdash_{\alpha} S^{op}\psi$ and $\langle \varphi, S^{op}\psi \rangle_{\alpha, X} = 1$.

Conversely, assume that $\langle \varphi, S^{op}\psi \rangle_{\alpha, X} = 1$, that is, $\varphi \vdash_{\alpha} S^{op}\psi$. Then in particular $S^{op}\psi \leq \alpha \circ \varphi$, which is equivalent to $\psi \leq \alpha \circ (S\varphi)$ by the claim above, hence also to $S\varphi \leq \beta \circ \psi$ by Condition 3.1. Moreover, for any $f \in \Phi_{\alpha}$, there exists $x \in X$ such that $\varphi(x) = f$ and $(S^{op}\psi)(x) = \alpha(f)$. Then

$$ \alpha(f) = (S^{op}\psi)(x) = \bigvee_{(x,y) \in S^{op}} \psi(y) = \bigvee_{(y,x) \in S} \psi(y), $$

and moreover $\alpha(f) \in \text{Irr}(T')$ by the definition of $\Phi_{\alpha}$. So there exists $y \in Y$ such that $(y, x) \in S$ and $\psi(y) = \alpha(f)$. Therefore

$$ f = \varphi(x) \leq \bigvee_{(y,x') \in S} \varphi(x') = (S\varphi)(y) \leq (\beta \circ \psi)(y) = \beta\alpha(f) = f, $$

where the latter equality comes from the definition of $\Phi_{\alpha}$. Thus we obtain an equality $(S\varphi)(y) = f$. So for any $f \in \Phi_{\alpha}$, there exists $y \in Y$ such that $(S\varphi)(y) = f$ and $\psi(y) = \alpha(f)$. This shows that $S\varphi \vdash_{\alpha} \psi$, hence $\langle S\varphi, \psi \rangle_{\alpha, Y} = 1$.

We have now shown that $\langle S\varphi, \psi \rangle_{\alpha, Y} = \langle \varphi, S^{op}\psi \rangle_{\alpha, X}$, completing the proof. $\square$

**3.10. Corollary.** Let $K_{\alpha}$ the left kernel of the pairing $\langle -, - \rangle_{\alpha} : F_{T} \times F_{T'} \to k$ of Proposition 3.9, and let $K'_{\alpha}$ be its right kernel. In other words, for any finite set $X$,

$$ K_{\alpha}(X) = \{u \in F_{T}(X) \mid \forall \psi \in (T')^{X}, \langle u, \psi \rangle_{\alpha, X} = 0\}, $$

$$ K'_{\alpha}(X) = \{u' \in F_{T'}(X) \mid \forall \varphi \in T^{X}, \langle \varphi, u' \rangle_{\alpha, X} = 0\}. $$
Then $K_\alpha$ is a subfunctor of $F_T$, and $K'_\alpha$ is a subfunctor of $F_{T'}$.

**Proof.** Let $u \in K_\alpha(X)$ and consider a correspondence $S \subseteq Y \times X$. Then, for all $\psi \in (T')^X$, we have

$$ \langle Su, \psi \rangle_{\alpha, Y} = \langle u, S^{op} \psi \rangle_{\alpha, X} = 0 $$

and this shows that $Su \in K_\alpha(Y)$, as required. The proof for $K'_\alpha$ is similar. $\square$

In view of Corollary 3.10, we can now introduce the correspondence functors which are our main object of study.

**3.11. Definition.** For any given join-morphism $\alpha : T \to T'^{op}$, we define

$$ S_\alpha = F_T/K_\alpha \quad \text{and} \quad S'_\alpha = F_{T'}/K'_\alpha. $$

For completeness, observe that $K_\beta = K'_\alpha$ and hence $S_\beta = S'_\alpha$, where $\beta = \alpha^{op}$ as usual.

**3.12. Remark.** The pairing $\langle-, -\rangle_\alpha : F_T \times F_{T'} \to k$ induces a pairing

$$ S_\alpha \times S'_\alpha \to k $$

which is nondegenerate in the weak sense, that is, it induces an *injective* morphism of functors

$$ i : S_\alpha \to (S'_\alpha)^{\natural}, $$

where $(S'_\alpha)^{\natural}$ denotes the $k$-dual of $S'_\alpha$. We will prove later in Proposition 6.9 that the pairing is actually nondegenerate in the strong sense, that is, the morphism $i$ is an isomorphism. When $k$ is a field, an argument about dimensions shows that there is no distinction to be made about nondegeneracy, so $i$ is obviously an isomorphism in that case.

There is another way of obtaining the correspondence functor $S_\alpha$, by dealing in a different way with the pairing $\langle-, -\rangle_\alpha : F_T \times F_{T'} \to k$. We know that it induces a morphism

$$ j_\alpha : F_T \to F_{T'}^{\natural} \cong F_{T'^{op}}, $$

where the latter isomorphism comes from Proposition 2.2. Clearly $K_\alpha$ is the kernel of $j_\alpha$ and so $S_\alpha$ is isomorphic to the image of the morphism $j_\alpha$. Since the functor

$$ F_? : k\mathcal{L} \to \mathcal{F}_k $$
is fully faithful by Theorem 2.1, $j_\alpha$ must be the image of a morphism

$$ \hat{\alpha} \in \operatorname{Hom}_{k\mathcal{L}}(T, T'^{\text{op}}) $$

in the category $k\mathcal{L}$, that is, $j_\alpha = F_{\hat{\alpha}} : F_T \to F_{T'^{\text{op}}}$. We are going to show that the morphism $\hat{\alpha}$ can be described explicitly.

**3.13. Definition.** If $T$ is a finite lattice, we let $r : T \to T$ be the map defined by

$$ r(t) = \bigvee_{\substack{s \in T \\ s < t}} s. $$

If $t \notin \operatorname{Irr}(T)$, then clearly $r(t) = t$, while if $t \in \operatorname{Irr}(T)$, then $r(t)$ is the unique maximal element strictly smaller than $t$.

**3.14. Proposition.** Let $\alpha : T \to T'^{\text{op}}$ be a join-morphism. For any subset $A$ of $\Phi_\alpha$, define $\alpha_A : T \to T'$ by

$$ \alpha_A(t) = \begin{cases} \alpha(t) & \text{if } t \in T - A \\ r\alpha(t) & \text{if } t \in A, \end{cases} $$

and define $\alpha_A^o$ to be the map $\alpha_A$, viewed as a map from $T$ to $T'^{\text{op}}$.

(a) For any subset $A$ of $\Phi_\alpha$, the map $\alpha_A^o$ is a join-morphism $T \to T'^{\text{op}}$ (hence $\alpha_A^o$ belongs to $\mathcal{L}$).

(b) The morphism $\hat{\alpha} \in \operatorname{Hom}_{k\mathcal{L}}(T, T'^{\text{op}})$ defined above is equal to

$$ \hat{\alpha} = \sum_{A \subseteq \Phi_{\alpha}} (-1)^{|A|} \alpha_A^o. $$

**Proof.** (a) follows from (b), because the expression for $\hat{\alpha}$ obtained in (b) forces the terms to be join-morphisms. Alternatively, this can also be proved directly from the definition of $\alpha_A^o$.

(b) By Proposition 2.2, the basis $(T')^X$ has a dual basis $\{\psi^* | \psi \in (T')^X\}$ of $F_{T'^{\text{op}}}$ given by

$$ \psi^* = \sum_{\substack{\rho \in (T')^X \\ \rho \le \psi}} \mu(\rho, \psi) \rho^o, $$

where $\rho^o$ is the map $\rho$, viewed as a map from $X$ to $T'^{\text{op}}$. By the definition of the morphism $j_{\alpha,X} : F_T(X) \to F_{T'^{\text{op}}}(X)$, it maps $\varphi \in T^X$ to the linear combination
$$j_{\alpha, X}(\varphi) = \sum_{\psi \in (T')^X} \langle \varphi, \psi \rangle_X \cdot \psi^* = \sum_{\substack{\psi \in (T')^X \\ \varphi \vdash_{\alpha} \psi}} \psi^*.$$

The way to recover the morphism $\hat{\alpha} \in \operatorname{Hom}_{k\mathcal{L}}(T, T'^{op})$ from its fully faithful image $j_\alpha$ is provided by the proof of part (c) of Theorem 4.8 in [4]. It consists of choosing $X = T$ and $\varphi = \mathrm{id}_T$, and define $\hat{\alpha}$ to be the image of $\mathrm{id}_T$ under $j_{\alpha,T}$. We obtain

$$\hat{\alpha} = \sum_{\substack{\psi \in (T')^T \\ \mathrm{id}_T \vdash_{\alpha} \psi}} \psi^* = \sum_{\substack{\psi \in (T')^T \\ \mathrm{id}_T \vdash_{\alpha} \psi}} \sum_{\substack{\rho \in (T')^X \\ \rho \le \psi}} \mu(\rho, \psi)\rho^o.$$

Now the condition $\mathrm{id}_T \vdash_{\alpha} \psi$ tells us that $\psi \le \alpha \circ \mathrm{id}_T$, i.e. $\psi \le \alpha$, and moreover

$$(C_{\psi}): \quad \psi(f) = \alpha(f), \quad \forall f \in \Phi_{\alpha}.$$

Therefore we get

$$\hat{\alpha} = \sum_{\substack{\psi \in (T')^T \\ \rho \le \alpha \\ (C_{\psi})}} \sum_{\substack{\rho \in (T')^X \\ \rho \le \psi}} \mu(\rho, \psi)\rho^o = \sum_{\substack{\rho \in (T')^X \\ \rho \le \alpha}} \left( \sum_{\substack{\psi \in (T')^T \\ \rho \le \psi \le \alpha \\ (C_{\psi})}} \mu(\rho, \psi) \right) \rho^o$$

We now fix $\rho$ and consider the coefficient of $\rho^o$. For every $\psi \in (T')^T$, we define

$$A_{\psi} = \{f \in \Phi_{\alpha} \mid \psi(f) < \alpha(f)\} = \{f \in \Phi_{\alpha} \mid \psi(f) \le r\alpha(f)\},$$

the second equality coming from the fact that $\alpha(f)$ is irreducible. Note that, for any given $\psi \le \alpha$, the requirement that $A_\psi = \emptyset$ corresponds exactly to the condition $(C_\psi)$. Now for any subset $A \subseteq \Phi_\alpha$, we have

$$A \subseteq A_{\psi} \iff \psi \le \alpha_{A},$$

where $\alpha_A$ is defined in the statement. Using the fact that $\sum_{\emptyset \subseteq A \subseteq A_\psi} (-1)^{|A|} = 0$ except if $A_\psi = \emptyset$, we see that the coefficient of $\rho^o$ is equal to

$$\begin{align*}
\sum_{\substack{\psi \in (T')^T \\ \rho \le \psi \le \alpha \\ (C_{\psi})}} \mu(\rho, \psi) &= \sum_{\substack{\psi \in (T')^T \\ \rho \le \psi \le \alpha \\ \bar{A}_{\psi} = \emptyset}} \mu(\rho, \psi) \\
&= \sum_{\substack{\psi \in (T')^T \\ \rho \le \psi \le \alpha}} \mu(\rho, \psi) \sum_{\emptyset \subseteq A \subseteq A_{\psi}} (-1)^{|A|} \\
&= \sum_{\emptyset \subseteq A \subseteq A_{\psi}} (-1)^{|A|} \sum_{\substack{\psi \in (T')^T \\ \rho \le \psi \le \alpha_A}} \mu(\rho, \psi) \\
&= \sum_{\emptyset \subseteq A \subseteq A_{\psi}} (-1)^{|A|} \delta_{\rho, \alpha_A}
\end{align*}$$
and this gives $(-1)^{|A|}$ if $\rho = \alpha_A$ for some $A$ and zero if $\rho \neq \alpha_A$ for all $A$. Thus the only functions $\rho \le \alpha$ which remain are the functions $\rho = \alpha_A$ for $A \subseteq \Phi_\alpha$ and we obtain

$$ \hat{\alpha} = \sum_{\emptyset \subseteq A \subseteq \Phi_{\alpha}} (-1)^{|A|} \alpha_A^o, $$

as required. $\square$

**3.15. Corollary.** The correspondence functor $S_\alpha$ is isomorphic to the image of the morphism

$$ j_{\alpha} = F_{\hat{\alpha}} : F_{T} \to F_{T^{\prime op}}, $$

$$ \text{where } \hat{\alpha} = \sum_{\emptyset \subseteq A \subseteq \Phi_{\alpha}} (-1)^{|A|} \alpha_{A}^{o}. $$

**Proof.** We have already noticed that $S_\alpha$ is isomorphic to the image of the morphism $j_\alpha$ and that $j_\alpha = F_{\hat{\alpha}}$. $\square$

**3.16. Remark.** For any given join-morphism $\alpha : T \to T'^{op}$, there is a more elementary way of defining bilinear forms without using $\Phi_\alpha$ and $\Phi'_\alpha$, but it turns out that it does not yield any new result. More precisely, if the definition of $\varphi \vdash_\alpha \psi$ given by Lemma 3.7 is modified by requiring the single condition $\psi \le \alpha \circ \varphi$ (or equivalently $\varphi \le \beta \circ \psi$ where $\beta = \alpha^{op}$), then the associated bilinear forms $\langle - , - \rangle_X$ induce again a functorial pairing

$$ \langle - , - \rangle : F_T \times F_{T'} \to k $$

and one can define $\tilde{S}_\alpha = F_T/\tilde{K}_\alpha$ and $\tilde{S}'_\alpha = F_{T'}/\tilde{K}'_\alpha$, where $\tilde{K}_\alpha$ and $\tilde{K}'_\alpha$ are the left and right kernels of the pairing. Now recall from Section 2 that there is another pairing

$$ (-|-)_X : F_T(X) \times F_{T^{op}}(X) \to k $$

which is nondegenerate (in the strong sense, see Proposition 2.2). It follows from the definitions that the bilinear form above can be expressed in terms of the nondegenerate pairing via $\langle \varphi, \psi \rangle_X = (\varphi | \beta \circ \psi)_X$. Therefore, for any given $v \in F_{T'}(X)$, we obtain equivalences

$$ v \in \tilde{K}'_\alpha(X) \iff \langle \varphi, v \rangle_X = 0, \forall \varphi \in T^X \iff (\varphi | \beta \circ v)_X = 0, \forall \varphi \in T^X $$

and this is equivalent to $\beta \circ v = 0$ by nondegeneracy. In other words,

$$ v \in \text{Ker}(F_{\beta,X} : F_{T'}(X) \to F_{T^{op}}(X)) $$

and this shows that $\tilde{K}'_\alpha = \text{Ker}(F_\beta)$. It follows that
$$ \tilde{S}'_{\alpha} = F_{T'}/\tilde{K}'_{\alpha} = F_{T'}/\mathrm{Ker}(F_{\beta}) \cong F_{\mathrm{Im}(\beta)}. $$

Similarly, $\tilde{S}_{\alpha} \cong F_{\mathrm{Im}(\alpha)}$. Therefore $\tilde{S}_{\alpha}$, respectively $\tilde{S}'_{\alpha}$, is simply (up to isomorphism) the correspondence functor associated with the lattice $\mathrm{Im}(\alpha)$, respectively $\mathrm{Im}(\beta)$. This shows why the more elementary way of defining a bilinear form does not yield any new correspondence functor. It does not yield any new pairing either, because $\alpha$ and $\beta$ actually induce isomorphisms between $\mathrm{Im}(\beta)$ and $\mathrm{Im}(\alpha)^{op}$ and the nondegenerate pairing

$$ F_{\mathrm{Im}(\alpha)}(X) \times F_{\mathrm{Im}(\alpha)^{op}}(X) \to k $$

induced by the given pairing $\langle - , - \rangle$ actually coincides with the general pairing of Proposition 2.2.

## 4. Lattice-theoretic constructions

For any given join-morphism $\alpha : T \to T'^{op}$, we introduce several lattice-theoretic constructions which will play an essential role. Using the map $r : T \to T$ defined in (3.13), we define inductively $r^k(t) = r(r^{k-1}(t))$ and $r^\infty(t) = r^n(t)$ if $n$ is such that $r^n(t) = r^{n+1}(t)$.

**4.1. Lemma.** Let $T$ be a finite lattice, let $t \in T$, and let $n \ge 0$ be the smallest integer such that $r^n(t) = r^\infty(t)$.

(a) $n \ge 0$ is the smallest integer such that $r^n(t) \notin \mathrm{Irr}(T)$.

(b) $r^\infty(t)$ is the unique greatest element of $T - \mathrm{Irr}(T)$ smaller than or equal to $t$.

(c) If $v \in T$ is such that $v \le t$, then either $v = r^i(t)$ for some $0 \le i \le n-1$ or $v \le r^\infty(t)$.

(d) $[r^\infty(t), t]$ is totally ordered and consists of the elements $r^i(t)$, for $0 \le i \le n$.

(e) All the elements of $[r^\infty(t), t]$ belong to $\mathrm{Irr}(T)$.

(f) The map $r : T \to T$ is order-preserving.

**Proof.** The proof is an easy consequence of the definitions. The result is completely trivial if $t \notin \mathrm{Irr}(T)$, while if $t$ is irreducible, then $r(t)$ is the unique maximal element of $[0, t]$ and $r^{i+1}(t)$ is the unique maximal element of $[0, r^i(t)]$ whenever $0 \le i \le n-1$. Details can be found in Lemma 2.5 of [5]. □

Instead of $\mathrm{Irr}(T)$, we need to work with the subset $\Phi_{\alpha}$ of $\mathrm{Irr}(T)$ defined in Notation 3.5. For simplicity, we write $\Phi = \Phi_{\alpha}$ and $\Phi' = \Phi'_{\alpha}$ throughout this section.

**4.2. Lemma.** Let $T$ be a finite lattice, let $t \in T$, let $m \ge 0$ be the smallest integer such that $r^m(t) \notin \Phi$, and set $\rho(t) = r^m(t)$.
(a) $\rho(t)$ is the unique greatest element of $T - \Phi$ smaller than or equal to $t$. In other words, $\rho(t) = \bigvee_{u \in T - \Phi \atop u \le t} u$.

(b) If $v \in T$ is such that $v \le t$, then either $v = r^i(t)$ for some $0 \le i \le m-1$ or $v \le \rho(t)$.

(c) $[\rho(t), t]$ is totally ordered and consists of the elements $r^i(t)$, for $0 \le i \le m$.

(d) All the elements of $[\rho(t), t]$ belong to $\Phi$.

(e) The map $\rho: T \to T$ is order-preserving.

**Proof.** We apply Lemma 4.1. Since $r^n(t) \notin \text{Irr}(T)$, we have $r^n(t) \notin \Phi$. Thus $m \le n$ and $r^\infty(t) \le r^m(t) \le t$.

Let $v \in T - \Phi$ with $v \le t$. Then $v$ cannot be equal to $r^i(t)$ for $0 \le i \le m-1$ by the definition of $m$, so $v \le r^m(t) = \rho(t)$, by part (c) of Lemma 4.1. The results follow easily. $\square$

**4.3. Notation.** We define

$$ \beta^{\sharp} = \rho\beta \quad \text{and} \quad \alpha^{\sharp} = \rho'\alpha, $$

$$ \text{where } \rho(t) = \bigvee_{u \in T - \Phi \atop u \le t} u \text{ and } \rho'(t') = \bigvee_{u' \in T' - \Phi' \atop u' \le t'} u'. $$

**4.4. Corollary.**

(a) $\alpha^{\sharp}(t) = r^l\alpha(t)$, where $l$ is the smallest non-negative integer such that $r^l\alpha(t) \notin \Phi'$.

(b) $\alpha^{\sharp}(t)$ is the greatest element of $T' - \Phi'$ smaller than or equal to $\alpha(t)$.

(c) If $t' \in T'$ is such that $t' \le \alpha(t)$, then either $t' = r^i\alpha(t)$ for some $0 \le i \le l-1$ or $t' \le \alpha^{\sharp}(t)$.

(d) The interval $[\alpha^{\sharp}(t), \alpha(t)]$ is totally ordered and consists of the elements $r^i\alpha(t)$, for $0 \le i \le l$.

(e) All the elements of $[\alpha^{\sharp}(t), \alpha(t)]$ belong to $\Phi'$.

(f) The map $\alpha^{\sharp}: T \to T'$ is order-reversing.

**Proof.** Everything follows from Lemma 4.2. $\square$

**4.5. Remark.** We can view the situation slightly differently. Since $\Phi \subseteq \text{Irr}(T)$, the subset $T - \Phi$ is closed under join and contains $\emptyset$. In other words $T - \Phi$ is a lattice (its join being the join of $T$, but its meet being in general different from the meet of $T$). The inclusion $i: T - \Phi \hookrightarrow T$ is a join-morphism and its opposite $i^{op}: T^{op} \to (T - \Phi)^{op}$ is defined by

$$ i^{op}(t) = \bigvee_{u \in T - \Phi \atop u \le t} u. $$
It follows that $\rho$ is equal to $i^{op}$ (provided we view $i^{op}$ as a map from $T$ to $T - \Phi$).
Consequently, $\beta^{\#} = \rho\beta = i^{op}\alpha^{op} = (\alpha i)^{op}$ and similarly $\alpha^{\#} = (\beta i')^{op}$ using the inclusion
$i' : T' - \Phi' \hookrightarrow T'$. In particular, by Lemma 3.4, $\beta^{\#}\alpha\beta^{\#} = \beta^{\#}(\alpha i)\beta^{\#} = \beta^{\#}$ and similarly
$\alpha^{\#}\beta\alpha^{\#} = \alpha^{\#}$.

Applying $\beta$ and $\beta^{\#}$ to the totally ordered interval $[\alpha^{\#}(t), \alpha(t)]$ yields canonically defined
elements of $T$ associated to $t$ and we want to investigate some structural information
about these elements. To this end we introduce some notation.

**4.6. Notation.** We set

$$ \omega = \beta\alpha^{\#} : T \to T \quad \text{and} \quad \omega' = \alpha\beta^{\#} : T' \to T', \\ \theta = \beta^{\#}\alpha^{\#} : T \to T \quad \text{and} \quad \theta' = \alpha^{\#}\beta^{\#} : T' \to T'. $$

Let us first discuss a few properties of $\omega$.

**4.7. Lemma.**

(a) The map $\omega : T \to T$ is order-preserving and idempotent.

(b) Let $t \in T$ and let $l \ge 0$ be the smallest integer such that $r^l\alpha(t) \notin \Phi'$, so that
$\alpha^{\#}(t) = r^l\alpha(t)$ and $\omega(t) = \beta r^l\alpha(t)$. For $0 \le i \le l-1$, write $v_i := \beta r^i\alpha(t)$. Then

$$ t \le v_0 < v_1 < \dots < v_{l-1} \le \omega(t), $$

and $v_i \in \Phi$, for $0 \le i \le l-1$. In particular, $t \le \omega(t)$.

(c) $[t, \omega(t)] \cap \Phi = \{v_0, v_1, \dots, v_{l-1}\}$. In particular, $\omega(t) \in \Phi$ if and only if $l \ge 1$ and
$v_{l-1} = \omega(t)$.

(d) $[t, \omega(t)] \cap \text{Im}(\beta) = \{v_0, v_1, \dots, v_{l-1}\}$.

**Proof.** (a) Since $\omega = \beta\alpha^{\#}$ is the composition of two order-reversing maps, it is an order-preserving map. Moreover, by Remark 4.5, we get $\omega^2 = \beta\alpha^{\#}\beta\alpha^{\#} = \beta\alpha^{\#} = \omega$.

(b) If $l=0$, then $\alpha(t) \notin \Phi'$, hence $\alpha(t) = \alpha^{\#}(t)$ and $t \le \beta\alpha(t) = \beta\alpha^{\#}(t) = \omega(t)$. If $l > 0$, Corollary 4.4 implies that there is a decreasing sequence

$$ \alpha(t) > r\alpha(t) > \dots > r^{l-1}\alpha(t) > r^l\alpha(t) = \alpha^{\#}(t), $$

and all the elements of this sequence, except $\alpha^{\#}(t)$, are in $\Phi'$. It follows from Lemma 3.6
that the sequence

$$ \beta\alpha(t) < \beta r\alpha(t) < \dots < \beta r^{l-1}\alpha(t) $$

is strictly increasing and consists of elements of $\Phi$. Moreover $t \le \beta\alpha(t) = v_0$ and $v_{l-1} = \beta r^{l-1}\alpha(t) \le \beta r^l\alpha(t) = \omega(t)$.
(c) Let $f \in [t, \omega(t)] \cap \Phi$. Then $\alpha(t) \ge \alpha(f) \ge \alpha\omega(t) = \alpha\beta\alpha^\sharp(t) \ge \alpha^\sharp(t)$ and therefore, by Corollary 4.4,

$$ \alpha(f) \in [\alpha^\sharp(t), \alpha(t)] \cap \Phi' = \{\alpha(t), r\alpha(t), \dots, r^{l-1}\alpha(t)\}. $$

It follows that $f = \beta\alpha(f) \in \{\beta\alpha(t), \beta r\alpha(t), \dots, \beta r^{l-1}\alpha(t)\}$. The other inclusion and the additional statement follow from (b).

(d) Let $t' \in T'$ such that $t \le \beta(t')$, so that $t' \le \alpha(t)$ by (3.1). By Corollary 4.4, either $t' \le \alpha^\sharp(t)$, and then $\beta(t') \ge \beta\alpha^\sharp(t) = \omega(t)$, or there exists an integer $j$ with $0 \le j < l$ such that $t' = r^j\alpha(t)$. In that case $\beta(t') = \beta r^j\alpha(t) = v_j$, as required. $\square$

We consider next some basic properties of $\theta$.

## 4.8. Lemma.

(a) The map $\theta: T \to T$ is order-preserving and idempotent.

(b) If $t \in T - \Phi$, then $t \le \theta(t)$ and $\alpha^\sharp\beta^\sharp\alpha^\sharp(t) = \alpha^\sharp(t)$.

(c) $\theta(t)$ is the greatest element of $T - \Phi$ smaller than or equal to $\omega(t)$.

(d) $[\theta(t), \omega(t)]$ is totally ordered and consists of elements of $\Phi$.

**Proof.** Since $\theta = \beta^\sharp\alpha^\sharp$ is the composition of two order-reversing maps, it is an order-preserving map. By Lemma 4.7, we have $t \le \omega(t) = \beta\alpha^\sharp(t)$, for any $t \in T$. If $t \in T - \Phi$, then $t \le \beta^\sharp\alpha^\sharp(t) \le \beta\alpha^\sharp(t)$ by the definition of $\beta^\sharp$, hence $t \le \theta(t)$. Moreover,

$$ \alpha(t) \ge \alpha\beta^\sharp\alpha^\sharp(t) \ge \alpha\beta\alpha^\sharp(t) \ge \alpha^\sharp(t). $$

Since $\alpha^\sharp(t)$ is the greatest element of $T' - \Phi'$ smaller than or equal to $\alpha(t)$, it is also the greatest element of $T' - \Phi'$ smaller than or equal to $\alpha\beta^\sharp\alpha^\sharp(t)$. Hence $\alpha^\sharp\beta^\sharp\alpha^\sharp(t) = \alpha^\sharp(t)$.

Swapping the roles of $T$ and $T'$, the same argument applies to any $t' \in T' - \Phi'$ and therefore $\beta^\sharp\alpha^\sharp\beta^\sharp(t') = \beta^\sharp(t')$. Taking in particular $t' = \alpha^\sharp(t)$ for any $t \in T$, we see that $\theta = \beta^\sharp\alpha^\sharp$ is idempotent.

Finally, (c) is an immediate consequence of the definition of $\beta^\sharp$, while (d) follows from Corollary 4.4 (applied to $\beta$ and $\beta^\sharp$ instead of $\alpha$ and $\alpha^\sharp$). $\square$

Some examples show that both conclusions in part (b) of Lemma 4.8 may fail if $t \in \Phi$ (see also Proposition 4.9).

We now examine in more detail the interval $[t, \omega(t)]$ and the position of $\theta(t)$. The elements $\theta(t)$ as well as the elements of $\Phi$ belonging to the interval $[t, \omega(t)]$ play a crucial role in the description of a $k$-basis of $S_\alpha(X)$, which is carried out in Sections 5 and 6.

As before, we let $l \ge 0$ be minimal such that $r^l\alpha(t) \notin \Phi'$, so that $\alpha^\sharp(t) = r^l\alpha(t)$. If $l \ge 1$, we let $0 \le h \le l$ be minimal such that $\theta(t) \le \beta r^h\alpha(t)$. Such an $h$ exists because $\theta(t) \le \omega(t) = \beta r^l\alpha(t)$.
**4.9. Proposition.** Let $t \in T$ and let $l$ and $h$ be as above. For $l \ge 1$ and $0 \le i \le l-1$, write $v_i := \beta r^i \alpha(t)$ and recall that $v_i \in \Phi$ (by Lemma 4.7).

(a) If $l=0$, then $t \notin \Phi$, $\alpha(t) \notin \Phi'$, $\theta(t) = \omega(t) = \beta\alpha(t) \notin \Phi$, and $[t, \omega(t)] \cap \Phi$ is empty. Moreover, $\alpha\theta(t) = \alpha(t)$.

(b) If $l \ge 1$ and $1 \le h \le l-1$, then $v_{h-1} < \theta(t) < v_h$. Hence

$$t \le v_0 < \dots < v_{h-1} < \theta(t) < v_h < \dots < v_{l-1} = \omega(t).$$

Moreover, $\alpha\theta(t) = r^h\alpha(t)$.

(c) If $l \ge 1$ and $h = l$, then $\theta(t) = \omega(t)$. Hence

$$t \le v_0 < \dots < v_{l-1} < \theta(t) = \omega(t).$$

Moreover, $\alpha\theta(t) = r^l\alpha(t)$.

(d) If $l \ge 1$ and $h = 0$ and if moreover $t \notin \Phi$, then $t \le \theta(t) < v_0$. Hence

$$t \le \theta(t) < v_0 < \dots < v_{l-1} = \omega(t).$$

Moreover, $\alpha\theta(t) = \alpha(t)$.

(e) If $l \ge 1$ and $h = 0$ and if moreover $t \in \Phi$, then $\theta(t) < t$. Hence

$$\theta(t) < t = v_0 < \dots < v_{l-1} = \omega(t).$$

Moreover, $\alpha\theta(t) \ge \alpha(t)$.

(f) If either $h \ge 1$ or $t \notin \Phi$, then $\alpha\theta(t) = r^h\alpha(t)$.

**Proof.** (a) If $l=0$, then $\alpha(t) \notin \Phi'$ by the definition of $l$. Then necessarily $t \notin \Phi$ by Lemma 3.6. By the definition of $\omega$, we have $\omega(t) = \beta\alpha(t)$ and this cannot be in $\Phi$, otherwise $\alpha(t) = \alpha\beta\alpha(t)$ would be in $\Phi'$. Finally $\theta(t) = \omega(t)$ because $\omega(t) \notin \Phi$ and $\alpha\theta(t) = \alpha\beta\alpha(t) = \alpha(t)$.

(b) By Lemma 4.7, the minimality of $h$ implies that $v_h$ is the least element of $[\theta(t), \omega(t)]$ belonging to $\Phi$. Moreover, since $h \le l-1$, and since $\theta(t) \notin \Phi$ by the definition of $\theta$, we must have $\theta(t) < v_{l-1} \le \omega(t)$, forcing $\omega(t) \in \Phi$, hence $v_{l-1} = \omega(t)$ by Lemma 4.7(c). By Lemma 4.8, the interval $[\theta(t), \omega(t)]$ is totally ordered and consists of the elements $r^i\omega(t)$ for $i \ge 0$, so we must have $\theta(t) = r(v_h)$. Consequently, $v_{h-1} \le \theta(t) < v_h$. The first inequality is strict because $v_{h-1} \in \Phi$ while $\theta(t) \notin \Phi$.

Applying $\alpha$ to the inequality $v_{h-1} = \beta r^{h-1}\alpha(t) < \theta(t) < v_h = \beta r^h\alpha(t)$ and using the fact that $v_h, v_{h-1} \in \Phi$, we obtain

$$r^{h-1}\alpha(t) \ge \alpha\theta(t) \ge r^h\alpha(t).$$
If the first inequality was an equality, applying $\beta$ would imply $\beta r^{h-1}\alpha(t) = \beta\alpha\theta(t)$, contrary to the relation $v_{h-1} < \theta(t) \le \beta\alpha\theta(t)$. Therefore $r^{h-1}\alpha(t) > \alpha\theta(t)$ and the definition of the operator $r$ yields $\alpha\theta(t) = r^h\alpha(t)$.

(c) If $h = l$, then $v_{l-1} = \beta r^{l-1}\alpha(t)$ cannot be equal to $\omega(t) = \beta r^l\alpha(t)$ by minimality of $h$, so that $v_{l-1} < \omega(t)$. By Lemma 4.7(c), it follows that $\omega(t) \notin \Phi$ and so $\theta(t) = \omega(t)$.

Applying $\alpha$ to the inequality $v_{l-1} = \beta r^{l-1}\alpha(t) < \omega(t) = \beta r^l\alpha(t)$ and using the fact that $r^{l-1}\alpha(t) \in \Phi$, we obtain

$$r^{l-1}\alpha(t) \ge \alpha\omega(t) = \alpha\beta r^l\alpha(t) \ge r^l\alpha(t).$$

If the first inequality was an equality, applying $\beta$ would imply

$$\beta r^{l-1}\alpha(t) = \beta\alpha\beta r^l\alpha(t) = \beta r^l\alpha(t) = \omega(t),$$

contrary to the relation $v_{l-1} < \omega(t)$. Therefore $r^{l-1}\alpha(t) > \alpha\omega(t) \ge r^l\alpha(t)$ and the definition of the operator $r$ yields $\alpha\omega(t) = r^l\alpha(t)$, that is, $\alpha\theta(t) = r^l\alpha(t)$.

(d) We have $t \le \theta(t)$ by Lemma 4.8(b) and the assumption $t \notin \Phi$. Moreover, $\theta(t) \le v_0 = \beta\alpha(t)$ because $h = 0$, and the inequality is strict because $v_0 \in \Phi$ while $\theta(t) \notin \Phi$.

Now since $t \le \theta(t) < v_0 = \beta\alpha(t)$, we have $\alpha(t) \ge \alpha\theta(t) \ge \alpha\beta\alpha(t) = \alpha(t)$, hence $\alpha\theta(t) = \alpha(t)$.

(e) Since $h = 0$, we have $\theta(t) \le \beta\alpha(t)$. But $\beta\alpha(t) = t$ because $t \in \Phi$, hence $\theta(t) \le t$. Moreover equality does not hold since $\theta(t) \notin \Phi$. Since $\alpha$ is order-reversing, we also get $\alpha\theta(t) \ge \alpha(t)$.

(f) If either $h \ge 1$ or $t \notin \Phi$, then we are in one of the cases (a)-(d) and we have found that $\alpha\theta(t) = r^h\alpha(t)$. $\square$

**4.10. Remark.** The property in (f) does not extend to the case (e). More precisely, in case (e), we may have an inequality $\alpha\theta(t) > \alpha(t)$. This occurs precisely when there is an element $f \in \Phi$ such that $\theta(t) < f < t = v_0$, for we then have $\alpha\theta(t) \ge \alpha(f) > \alpha(t)$ because $f < t$ are both in $\Phi$. In other words, since $]\theta(t), \omega(t)]$ is totally ordered and consists of elements of $\Phi$ by Lemma 4.8, we see that if $u \in ]\theta(t), \omega(t)]$ is not the minimal element of $]\theta(t), \omega(t)]$, then $\theta(u) = \theta(t)$ and $\alpha\theta(u) = \alpha\theta(t) > \alpha(u)$.

The property $\theta(u) < u$ only occurs in case (e) of Proposition 4.9 and this case is important in the sequel. It appears in particular when $u \in ]t, \omega(t)]$ for $t \in \text{Im}(\theta)$ and we now analyse this situation.

**4.11. Lemma.** Let $\alpha : T \to T'^{op}$ be a join-morphism and let $\beta = \alpha^{op}$.

(a) The restriction of $\alpha^\#$ is an anti-isomorphism of posets from $\text{Im}(\theta)$ to $\text{Im}(\theta')$, with inverse anti-isomorphism $\beta^\#$.
(b) If $t \in \text{Im}(\theta)$ and $t' = \alpha^{\sharp}(t)$, then $\alpha$ restricts to an order-reversing bijection from the totally ordered interval $]t, \omega(t)]$ to the totally ordered interval $]t', \omega'(t')]$. The inverse bijection is induced by $\beta$.

(c) Let $t \in \text{Im}(\theta)$ and $u \in [t, \omega(t)]$. Then $\rho(u) = t$, $\omega(u) = \omega(t)$, and $\theta(u) = \theta(t) = t$.

**Proof.** (a) Let $t \in \text{Im}(\theta)$, i.e. $t = \theta(t)$ by Lemma 4.8. Setting $t' = \alpha^{\sharp}(t)$, we get $t = \theta(t) = \beta^{\sharp}\alpha^{\sharp}(t) = \beta^{\sharp}(t')$. Moreover, $\theta'(t') = \alpha^{\sharp}\beta^{\sharp}(t') = \alpha^{\sharp}\beta^{\sharp}\alpha^{\sharp}(t) = \alpha^{\sharp}(t) = t'$, the third equality coming from Lemma 4.8 and the fact that $t \notin \Phi$, because $t = \theta(t)$. Therefore $t' \in \text{Im}(\theta')$. Since $\alpha^{\sharp}$ and $\beta^{\sharp}$ are order-reversing, the result follows.

(b) We set again $t' = \alpha^{\sharp}(t)$ and we also have $t = \beta^{\sharp}(t')$ as above. Moreover,

$$ \omega(t) = \beta\alpha^{\sharp}(t) = \beta(t') \quad \text{and} \quad \omega'(t') = \alpha\beta^{\sharp}(t') = \alpha(t). \qquad (4.12) $$

If $]t, \omega(t)]$ is empty, i.e. $t = \omega(t)$, then Proposition 4.9 shows that we must have $l = 0$, hence $\alpha^{\sharp}(t) = \alpha(t)$. Therefore $t' = \alpha(t) = \omega'(t')$ and the interval $]t', \omega'(t')]$ is also empty. Similarly, if $]t', \omega'(t')]$ is empty, then so is $]t, \omega(t)]$. Thus we can assume that both intervals are nonempty.

By Lemma 4.8, the interval $[t, \omega(t)]$ is totally ordered and $]t, \omega(t)] \subseteq \Phi$. In particular, $\omega(t) \in \Phi$, hence $\beta(t') \in \Phi$ by (4.12). Similarly $\omega'(t') = \alpha(t) \in \Phi'$. In particular, we have $\beta\alpha(t) \in \Phi$, hence $t < v := \beta\alpha(t)$ because $t \notin \Phi$. Note that $\alpha(t) = \alpha(v)$ because $\alpha\beta\alpha = \alpha$. If $s \in ]t, \omega(t)]$, then $s \in \Phi$, hence

$$ t < v = \beta\alpha(t) \leq \beta\alpha(s) = s \leq \omega(t). $$

Therefore $v$ is the least element of $]t, \omega(t)]$ and $]t, \omega(t)] = [v, \omega(t)] = [t, \omega(t)] \cap \Phi$. Similarly $t' < v' := \alpha\beta(t') \in \Phi', \beta(t') = \beta(v')$ and $v'$ is the least element of $]t', \omega'(t')]$.

Since $\alpha(v) = \alpha(t) = \omega'(t')$ and $\beta(v') = \beta(t') = \omega(t)$ by (4.12), and since $\alpha$ is order-reversing, we get

$$ \alpha([v, \omega(t)]) = [\alpha\omega(t), \alpha(v)] = [\alpha\beta(t'), \alpha(v)] = [v', \omega'(t')], $$

that is, $\alpha([t, \omega(t)]) = [t', \omega'(t')]$. Similarly $\beta([t', \omega'(t')]) = [t, \omega(t)]$. Therefore the maps $\alpha$ and $\beta$ restrict to anti-isomorphisms of posets between $]t, \omega(t)]$ and $]t', \omega'(t')]$.

(c) If $u \in [t, \omega(t)]$, then $t = \rho(t) \leq \rho(u) \leq \rho\omega(t) = \beta^{\sharp}\alpha^{\sharp}(t) = t$, so $\rho(u) = t$. Similarly $\omega(t) \leq \omega(u) \leq \omega^2(t) = \omega(t)$ by Lemma 4.7, so $\omega(u) = \omega(t)$. Finally, $\theta(u) = \rho\omega(u) = \rho\omega(t) = \theta(t)$ and $\theta(t) = t$ since $t \in \text{Im}(\theta)$. $\square$

To end this section we show that the image of $\beta$ can be described in terms of $\omega$ and $\theta$, and similarly for $\alpha$.
**4.13. Proposition.** Let $\alpha : T \to T'^{op}$ be a join-morphism and let $\beta = \alpha^{op}$.

$$ (a) \beta(T') = \Phi \sqcup \{t \in T \mid t = \omega(t) = \theta(t)\}. $$

$$ (b) \alpha(T) = \Phi' \sqcup \{t' \in T' \mid t' = \omega'(t') = \theta'(t')\}. $$

**Proof.** Since (b) is the dual statement, it suffices to prove (a). The union is disjoint because $\theta(t) \notin \Phi$, so $t = \theta(t)$ implies that $t \notin \Phi$. If $t \in \Phi$, then $t = \beta\alpha(t) \in \beta(T')$, while if $t$ satisfies $t = \omega(t)$, then also $t \in \beta(T')$. So we are left with the proof of the inclusion $\beta(T') \subseteq \Phi \sqcup \{t \in T \mid t = \omega(t) = \theta(t)\}$.

Let $t' \in T'$ and set $t = \beta(t')$. If $t \in \Phi$, we are done, so we assume that $t \notin \Phi$. Recall that $t = \beta(t') = \beta\alpha\beta(t') = \beta\alpha(t)$, by Lemma 3.4. Thus $\alpha(t) \notin \Phi'$, otherwise $t = \beta\alpha(t)$ would be in $\Phi$. Therefore $\alpha^\sharp(t) = \alpha(t)$, hence $\omega(t) = \beta\alpha^\sharp(t) = \beta\alpha(t) = t$. Now $t \notin \Phi$ and the property $t = \omega(t) \notin \Phi$ implies that $\theta(t) = \rho\omega(t) = \omega(t)$, by the definition of $\theta$. This shows that $t = \omega(t) = \theta(t)$, as required. $\square$

**5. Generating set for the evaluation**

Our main goal in this section is to describe a set of generators of the evaluation $S_\alpha(X)$ at a finite set $X$. To this end, we need the lattice-theoretic constructions of Section 4 and in particular the following notation:

**5.1. Notation.** Let $\alpha : T \to T'^{op}$ be a join-morphism of finite lattices. Using our previous Notation 3.5 and 4.6, we set

$$ G_{\alpha} = \Phi_{\alpha} \sqcup \mathrm{Im}(\theta) \quad \text{and} \quad G'_{\alpha} = \Phi'_{\alpha} \sqcup \mathrm{Im}(\theta'). $$

We also write $G = G_\alpha$ and $G' = G'_\alpha$ whenever there is no possible confusion. Note that $\mathrm{Im}(\theta)$ can also be described as the set of fixed points of $\theta$ because $\theta$ is idempotent. The union is disjoint because $\theta(t) \notin \Phi_\alpha$ by definition.

**5.2. Lemma.** $\beta(T') \subseteq G_\alpha$ and $\alpha(T) \subseteq G'_\alpha$.

**Proof.** We have $\beta(T') = \Phi_\alpha \sqcup \{t \in T \mid t = \omega(t) = \theta(t)\}$ by Proposition 4.13, while $G_\alpha = \Phi_\alpha \sqcup \{t \in T \mid t = \theta(t)\}$ by Notation 5.1. Thus the inclusion is clear. $\square$

The key for our main result is to describe sufficiently many elements of the kernel $K_\alpha(X)$ of the surjection $F_T(X) \to S_\alpha(X)$. They will later be used to modify arbitrary chosen elements of the basis $T^X$ via consecutive reductions. This motivates the following terminology:

**5.3. Definition.** Let $\alpha : T \to T'^{op}$ be a join-morphism. Let $a \in T - G_\alpha$ and $b = \theta(a)$. Using the notation of Proposition 4.9, we let $l \ge 0$ be minimal such that $r^l\alpha(a) \notin \Phi'_\alpha$, so that $\alpha^\sharp(a) = r^l\alpha(a)$, and if $l \ge 1$ we let $0 \le h \le l$ be minimal such that $b \le \beta r^h \alpha(a)$.
By Proposition 4.9, the elements of $\Phi_\alpha$ lying in the interval $[a, b]$ form a totally ordered set

$$v_0 < \dots < v_{h-1},$$

where $v_i = \beta r^i \alpha(a)$ for $0 \le i \le h-1$. If $h=0$, then this set is empty. The totally ordered set

$$\{a, b\} \sqcup ([a, b] \cap \Phi_{\alpha}) = \{a < v_0 < \dots < v_{h-1} < b\}$$

will be called the *reduction sequence* associated to $a$.

In this sequence, it will be convenient to set also $v_{-1} = a$, and $v_h = b$ (but note that $a, b \notin \Phi_\alpha$). If $h=0$, the reduction sequence only consists of $a < b$.

Now we come to our main technical lemma.

**5.4. Lemma.** Let $a \in T - G_\alpha$ and $b = \theta(a)$. Let $a < v_0 < \dots < v_{h-1} < b$ be the associated reduction sequence (with $h$ fixed as in Definition 5.3) and set also $v_h = b$. For any $0 \le k \le h$, let $[a, v_0, \dots, v_k] : T \to T$ be the map defined by

$$\forall t \in T, [a, v_0, \dots, v_k](t) = \begin{cases} v_0 & \text{if } t = a, \\ v_{i+1} & \text{if } t = v_i \text{ with } 0 \le i \le k-1, \\ t & \text{otherwise.} \end{cases}$$

For any function $\varphi \in T^X$ (where $X$ is a finite set), we set

$$\varphi_k = [a, v_0, \dots, v_k] \circ \varphi.$$

Then the linear combination

$$w = \varphi + \sum_{k=0}^{h} (-1)^{k+1} \varphi_k$$

belongs to $K_\alpha(X)$.

**Proof.** We have to show that $\langle w, \psi \rangle_X = 0$ for any $\psi : X \to T'$. To see this, we must know when $\varphi \vdash_\alpha \psi$ and when $\varphi_k \vdash_\alpha \psi$, for $0 \le k \le h$. For simplicity, we write $\varphi \vdash \psi$ instead of $\varphi \vdash_\alpha \psi$ and $\Phi = \Phi_\alpha$. Recall from Lemma 3.7 that

$$\varphi \vdash \psi \iff \psi \varphi^{-1}(t) \subseteq [\hat{0}, \alpha(t)], \forall t \in T, \text{ and } \alpha(f) \in \psi \varphi^{-1}(f), \forall f \in \Phi.$$

We first observe the following, for any $0 \le k \le h$ (including $k=h$ in which case $v_h = b$):
$$ \varphi_k^{-1}(t) = \varphi^{-1}(t), \quad \forall t \neq a, v_0, \dots, v_{h-1} $$

$$ \varphi_k^{-1}(a) = \emptyset $$

$$ \varphi_k^{-1}(v_i) = \varphi^{-1}(v_{i-1}), \quad \forall i \text{ with } 0 \le i \le k-1 $$

$$ \varphi_k^{-1}(v_k) = \varphi^{-1}(v_{k-1}) \sqcup \varphi^{-1}(v_k) $$

$$ \varphi_k^{-1}(v_i) = \varphi^{-1}(v_i), \quad \forall i \text{ with } k+1 \le i \le h-1 $$

The proof is straightforward. For the 4th equality, note that $\varphi_k(x) = v_k$ if and only if $\varphi(x) = v_{k-1}$ or $\varphi(x) = v_k$, because $v_{k-1}$ and $v_k$ are the only elements mapped to $v_k$ by the map $[a, v_0, \dots, v_k]$.

Now we introduce a list of conditions which we need for the description of the property $\varphi_k \vdash \psi$. The first conditions treat the case $k = -1$, where for convenience we set $\varphi_{-1} = \varphi$:

$$ (\text{A}): \quad \begin{cases} \psi\varphi^{-1}(t) \subseteq [\hat{0}, \alpha(t)], & \forall t \in T - \{v_0, \dots, v_{h-1}\} \text{ and} \\ \alpha(f) \in \psi\varphi^{-1}(f), & \forall f \in \Phi - \{v_0, \dots, v_{h-1}\} \end{cases} $$

$$ (\text{D}_{-1}): \quad \alpha(v_i) \in \psi\varphi^{-1}(v_i) \subseteq [\hat{0}, \alpha(v_i)], \quad \forall i \text{ with } 0 \le i \le h-1 $$

Since $\varphi_{-1} = \varphi$, it is obvious that

$$ \varphi_{-1} \vdash \psi \iff (\text{A}) \text{ and } (\text{D}_{-1}) \text{ hold.} $$

Next we consider conditions for $0 \le k \le h-1$:

$$ (\text{B}_k): \quad \alpha(v_i) \in \psi\varphi^{-1}(v_{i-1}) \subseteq [\hat{0}, \alpha(v_i)], \quad \forall i \text{ with } 0 \le i \le k-1 $$

$$ (\text{C}_k): \quad \alpha(v_k) \in \psi(\varphi^{-1}(v_{k-1}) \sqcup \varphi^{-1}(v_k)) \subseteq [\hat{0}, \alpha(v_k)] $$

$$ (\text{D}_k): \quad \alpha(v_i) \in \psi\varphi^{-1}(v_i) \subseteq [\hat{0}, \alpha(v_i)], \quad \forall i \text{ with } k+1 \le i \le h-1 $$

Here $(\text{B}_0)$ is empty because the condition $0 \le i \le k-1$ is empty if $k=0$. Similarly $(\text{D}_{h-1})$ is empty because the condition $k+1 \le i \le h-1$ is empty if $k=h-1$. In view of the previous observations about $\varphi_k^{-1}$, it is clear that, for $0 \le k \le h-1$,

$$ \varphi_k \vdash \psi \iff (\text{A}), (\text{B}_k), (\text{C}_k), \text{ and } (\text{D}_k) \text{ hold.} $$

Finally we consider conditions in the case $k = h$:

$$ (\text{B}_h): \quad \alpha(v_i) \in \psi\varphi^{-1}(v_{i-1}) \subseteq [\hat{0}, \alpha(v_i)], \quad \forall i \text{ with } 0 \le i \le h-1 $$

$$ (\text{C}_h^*): \quad \psi\varphi^{-1}(v_{h-1}) \subseteq [\hat{0}, \alpha(b)] $$

The notation $(C_h^*)$ suggests that the condition is not exactly a special case of $(C_k)$: the requirement $\psi\varphi^{-1}(v_h) \subseteq [\hat{0}, \alpha(v_h)]$ is not included in $(C_h^*)$ because $v_h = b$ and this
requirement is contained in (A). Note that $(D_h)$ does not appear because it would be empty. Again it is clear that

$$ \varphi_h \vdash \psi \iff (A), (B_h), (C_h^*) \text{ hold.} $$

**5.5. Claim.** Let $-1 \le k, k' \le h$. If both $\varphi_k \vdash \psi$ and $\varphi_{k'} \vdash \psi$ hold, then $|k' - k| \le 1$.

First let $-1 \le k < k' \le h$ such that $k' - k \ge 3$ and suppose that both $\varphi_k \vdash \psi$ and $\varphi_{k'} \vdash \psi$ hold. Since $\varphi_k \vdash \psi$ implies $(D_k)$, we obtain in particular, for $i = k + 1$,

$$ \alpha(v_{k+1}) \in \psi\varphi^{-1}(v_{k+1}). $$

Now $\varphi_{k'} \vdash \psi$ implies $(B_{k'})$ and in particular, for $i = k + 2 \le k' - 1$, we get

$$ \psi\varphi^{-1}(v_{k+1}) \subseteq [0, \alpha(v_{k+2})]. $$

It follows that $\alpha(v_{k+1}) \in [0, \alpha(v_{k+2})]$, that is, $\alpha(v_{k+1}) \le \alpha(v_{k+2})$. But $\alpha(v_{k+2}) < \alpha(v_{k+1})$ because $v_{k+2} > v_{k+1}$ both belong to $\Phi$, so their images under $\alpha$ remain distinct, by Lemma 3.6. This contradiction shows that $\varphi_k \vdash \psi$ is incompatible with $\varphi_{k'} \vdash \psi$ when $k' - k \ge 3$.

A similar argument holds if $k' - k = 2$. Again $\varphi_k \vdash \psi$ implies that

$$ \alpha(v_{k+1}) \in \psi\varphi^{-1}(v_{k+1}). $$

Now $\varphi_{k'} \vdash \psi$ implies $(C_{k'})$ if $k' \le h - 1$, respectively $(C_h^*)$ if $k' = h$. In either case, for $i = k' - 1 = k + 1$, we get in particular

$$ \psi\varphi^{-1}(v_{k+1}) \subseteq [0, \alpha(v_{k+2})]. $$

Therefore $\alpha(v_{k+1}) \le \alpha(v_{k+2})$, but again this contradicts the fact that $\alpha(v_{k+2}) < \alpha(v_{k+1})$, which follows from $v_{k+2} > v_{k+1}$. A special argument is needed here if $k + 2 = h$, because $v_h = b$ is not in $\Phi$. We have $v_h > v_{h-1}$, hence $\alpha(v_h) \le \alpha(v_{h-1})$ and we must show that the equality $\alpha(v_h) = \alpha(v_{h-1})$ cannot hold. If it did hold, then we would obtain

$$ \beta\alpha(v_h) \ge v_h > v_{h-1} = \beta\alpha(v_{h-1}) = \beta\alpha(v_h), $$

but this is impossible. Thus we also have $\alpha(v_{k+2}) < \alpha(v_{k+1})$ if $k' = k + 2 = h$. We have seen that this yields a contradiction, so $\varphi_k \vdash \psi$ is incompatible with $\varphi_{k'} \vdash \psi$ when $k' = k + 2$. Putting together the cases $k' - k \ge 3$ and $k' - k = 2$, we see $\varphi_k \vdash \psi$ is incompatible with $\varphi_{k'} \vdash \psi$ whenever $|k' - k| \ge 2$. This completes the proof of Claim 5.5.
**5.6. Claim.** Let $0 \le k \le h$.

(a) Suppose $0 \le k \le h-1$. If both $\varphi_k \vdash \psi$ and $\alpha(v_k) \in \psi\varphi^{-1}(v_k)$ hold, then $\varphi_{k-1} \vdash \psi$ holds.

(b) Suppose $k = h$. If $\varphi_h \vdash \psi$ holds, then $\varphi_{h-1} \vdash \psi$ holds.

In order to show that $\varphi_{k-1} \vdash \psi$ holds, we need to prove $(B_{k-1})$, $(C_{k-1})$ and $(D_{k-1})$. This is clear for $(B_{k-1})$ because $(B_k)$ implies $(B_{k-1})$ (with $(B_{-1})$ empty if $k=0$).

(a) Suppose first that $1 \le k \le h-1$. Since $(B_k)$ for $i=k-1$ implies that $\alpha(v_{k-1}) \in \psi\varphi^{-1}(v_{k-2}) \subseteq [\hat{0}, \alpha(v_{k-1})]$, while $(C_k)$ implies that $\psi\varphi^{-1}(v_{k-1}) \subseteq [\hat{0}, \alpha(v_k)] \subseteq [\hat{0}, \alpha(v_{k-1})]$, we obtain $(C_{k-1})$. Now $(D_k)$ is the part of $(D_{k-1})$ corresponding to $i \ge k+1$ and moreover $(C_k)$ implies that $\psi\varphi^{-1}(v_k) \subseteq [\hat{0}, \alpha(v_k)]$ while the extra condition $\alpha(v_k) \in \psi\varphi^{-1}(v_k)$ holds by assumption, so we obtain $(D_{k-1})$ for $i=k$ as well.

If $k=0$, then $(B_{-1})$ and $(C_{-1})$ are empty and the argument that $(D_{-1})$ holds is obtained in the same way as above.

(b) Assume now that $k=h$. Since $(B_h)$ implies $(B_{h-1})$ and since $(D_{h-1})$ is empty, we are left with the proof of $(C_{h-1})$. Condition $(B_h)$ for $i=h-1$ implies that $\alpha(v_{h-1}) \in \psi\varphi^{-1}(v_{h-2}) \subseteq [\hat{0}, \alpha(v_{h-1})]$, while $(C_h^*)$ asserts that $\psi\varphi^{-1}(v_{h-1}) \subseteq [\hat{0}, \alpha(b)] \subseteq [\hat{0}, \alpha(v_{h-1})]$, so we obtain $(C_{h-1})$.

This completes the proof of Claim 5.6.

**5.7. Claim.** Let $-1 \le k \le h-1$.

(a) Suppose $0 \le k \le h-1$. If $\varphi_k \vdash \psi$ holds and if both conditions $\alpha(v_k) \in \psi\varphi^{-1}(v_{k-1})$ and $\psi\varphi^{-1}(v_k) \subseteq [\hat{0}, \alpha(v_{k+1})]$ are satisfied, then $\varphi_{k+1} \vdash \psi$ holds.

(b) Suppose $k = -1$. If $\varphi_{-1} \vdash \psi$ holds, then $\varphi_0 \vdash \psi$ holds.

We need to prove $(B_{k+1})$, $(C_{k+1})$, and $(D_{k+1})$. This is clear for $(D_{k+1})$ because $(D_k)$ implies $(D_{k+1})$ (with $(D_h)$ empty if $k=h-1$).

(a) Suppose first that $0 \le k \le h-2$. Since $(D_k)$ for $i=k+1$ implies that $\alpha(v_{k+1}) \in \psi\varphi^{-1}(v_{k+1}) \subseteq [\hat{0}, \alpha(v_{k+1})]$, while $\psi\varphi^{-1}(v_k) \subseteq [\hat{0}, \alpha(v_{k+1})]$ by one of the assumptions, we obtain $(C_{k+1})$. Now $(B_k)$ is the part of $(B_{k+1})$ corresponding to $i \le k-1$ and moreover $(C_k)$ implies that $\psi\varphi^{-1}(v_k) \subseteq [\hat{0}, \alpha(v_k)]$ while the extra condition $\alpha(v_k) \in \psi\varphi^{-1}(v_k)$ holds by assumption, so we obtain $(B_{k+1})$ for $i=k$ as well.

If $k=h-1$, then the second additional assumption yields precisely $(C_h^*)$. The argument that $(B_h)$ holds is obtained in the same way as above.

(b) Assume now that $k=-1$. Since $(D_1)$ implies $(D_0)$ and since $(B_0)$ is empty, we are left with the proof of $(C_0)$. Condition $(D_{-1})$ for $i=0$ implies that $\alpha(v_0) \in \psi\varphi^{-1}(v_0) \subseteq [\hat{0}, \alpha(v_0)]$. Moreover, the inclusion $\psi\varphi^{-1}(v_{-1}) \subseteq [\hat{0}, \alpha(v_0)]$ is no longer an extra assumption because it is a consequence of (A). Indeed we have $v_{-1} = a$ and $\alpha(v_0) = \alpha(a)$, because $\alpha(v_0) = \alpha\beta\alpha(a) = \alpha(a)$. This proves $(C_0)$ and completes the proof of Claim 5.7.
Now we prove that $\langle w, \psi \rangle_X = 0$, where $w = \sum_{k=-1}^{h} (-1)^{k+1} \varphi_k$ and $\varphi_{-1} = \varphi$. Recall that

$$ \langle \varphi_k, \psi \rangle_X \neq 0 \iff \langle \varphi_k, \psi \rangle_X = 1 \iff \varphi_k \vdash \psi. $$

There is nothing to prove if $\varphi_k \nvdash \psi$ for all $-1 \le k \le h$ (where $\nvdash$ denotes of course the negation of $\vdash$). Excluding this case, our aim is to prove that $\varphi_k \vdash \psi$ for exactly two consecutive values of $k$. So let $s$ be minimal such that $\varphi_s \vdash \psi$ (where $-1 \le s \le h$). We cannot have $s = h$ by minimality of $s$, because $\varphi_h \vdash \psi$ implies $\varphi_{h-1} \vdash \psi$, by Claim 5.6(b). We want to prove that $\varphi_{s+1} \vdash \psi$. If $s = -1$, then we know that $\varphi_0 \vdash \psi$ also holds, by Claim 5.7(b). So we can assume that $0 \le s \le h - 1$.

By minimality of $s$, we have $\varphi_{s-1} \nvdash \psi$. Now $\varphi_s \vdash \psi$ and $\varphi_{s-1} \nvdash \psi$ imply, by Claim 5.6(a), that

$$ \alpha(v_s) \notin \psi\varphi^{-1}(v_s). \qquad (5.8) $$

By (C$_s$), we have $\alpha(v_s) \in \psi(\varphi^{-1}(v_{s-1}) \sqcup \varphi^{-1}(v_s))$, hence

$$ \alpha(v_s) \in \psi\varphi^{-1}(v_{s-1}). \qquad (5.9) $$

Now (C$_s$) also implies that

$$ \psi\varphi^{-1}(v_s) \subseteq [\hat{0}, \alpha(v_s)] = [\hat{0}, \alpha(v_{s+1})] \sqcup \{\alpha(v_s)\}, $$

the equality coming from the fact that

$$ r\alpha(v_s) = r\alpha\beta r^s \alpha(a) = r^{s+1}\alpha(a) = \alpha\beta r^{s+1}\alpha(a) = \alpha(v_{s+1}). $$

Using (5.8), it follows that

$$ \psi\varphi^{-1}(v_s) \subseteq [\hat{0}, \alpha(v_{s+1})]. \qquad (5.10) $$

Conditions 5.9 and 5.10 are precisely the two additional requirements appearing in Claim 5.7. Thus, together with the assumption $\varphi_s \vdash \psi$, we get $\varphi_{s+1} \vdash \psi$ by Claim 5.7, as required.

Whenever $|k - s| \ge 2$, we have $\varphi_k \nvdash \psi$ by Claim 5.5. Thus $s$ and $s + 1$ are the only two integers which come into play and we obtain

$$ \langle w, \psi \rangle_X = \pm (\langle \varphi_s, \psi \rangle_X - \langle \varphi_{s+1}, \psi \rangle_X) = \pm(1 - 1) = 0. $$

We have now proved that $\langle w, \psi \rangle_X = 0$ for any $\psi : X \to T'$. In other words, $w \in K_\alpha(X)$, completing the proof of Lemma 5.4. $\square$
**5.11. Notation.** For any finite set $X$, we let

$$ \mathcal{B}_{\alpha,X} = \{\varphi \in T^X \mid \Phi_\alpha \subseteq \varphi(X) \subseteq G_\alpha\}, $$

a subset of the basis $T^X$ of $F_T(X)$. Moreover, $k\mathcal{B}_{\alpha,X}$ denotes the $k$-linear span of $\mathcal{B}_{\alpha,X}$ inside $F_T(X)$.

We can finally prove the main result of this section.

**5.12. Theorem.** Let $\alpha : T \to T'^{\text{op}}$ be a join-morphism of finite lattices. For any finite set $X$, the image of $\mathcal{B}_{\alpha,X}$ in $\mathcal{S}_{\alpha}(X) = F_T(X)/K_{\alpha}(X)$ is a set of $k$-linear generators of $\mathcal{S}_{\alpha}(X)$. In other words, $F_T(X) = k\mathcal{B}_{\alpha,X} + K_{\alpha}(X)$.

**Proof.** We have to show that for any map $\varphi : X \to T$, there is a linear combination $u$ of elements of $\mathcal{B}_{\alpha,X}$ such that $\varphi - u \in K_{\alpha}(X)$. If $\varphi$ is such that $\Phi_{\alpha} \not\subseteq \varphi(X)$, then we can take $u = 0$ because the mere existence of a map $\psi : X \to T'$ such that $\varphi \vdash \psi$ implies that $\Phi_{\alpha} \subseteq \varphi(X)$, by the definition of the relation $\varphi \vdash \psi$. Thus if $\Phi_{\alpha} \not\subseteq \varphi(X)$, then $\varphi$ is forced to lie in the kernel $K_{\alpha}(X)$.

So we now assume that $\varphi : X \to T$ is such that $\Phi_{\alpha} \subseteq \varphi(X)$ and we proceed by induction on the cardinality $n_{\varphi}$ of the difference $\varphi(X) - G_{\alpha}$. If $n_{\varphi} = 0$, then $\varphi(X) \subseteq G_{\alpha}$, so $\varphi \in \mathcal{B}_{\alpha,X}$, and we can take $u = \varphi$. Assuming now that $n_{\varphi} > 0$, there exists an element $a \in \varphi(X) - G_{\alpha}$. We set $b = \theta(a)$, and we consider the reduction sequence

$$ a < v_0 < v_1 < \dots < v_{h-1} < b = \theta(a) $$

associated to $a$. Recall that we set $v_{-1} = a$ and $v_h = b$. Moreover, in the case $h = 0$, the reduction sequence is simply $a < b$.

By Lemma 5.4, the element

$$ w = \varphi + \sum_{k=0}^{h} (-1)^{k+1} \varphi_k $$

belongs to $K_{\alpha}(X)$. For each $0 \le k \le h$, the definition of the map $\varphi_k$ shows that $a \notin \varphi_k(X)$, while we had $a \in \varphi(X)$. Moreover, when $k = h$, we may have added the element $b$ to the image $\varphi_h(X)$, but $b \in G_{\alpha}$ because $b = \theta(a)$. Thus $a \notin G_{\alpha}$, $b \in G_{\alpha} - \Phi_{\alpha}$, and $v_0, \dots, v_{h-1} \in \Phi_{\alpha} \subseteq G_{\alpha}$, so that the cardinality $n_{\varphi_k}$ of the difference $\varphi_k(X) - G_{\alpha}$ is equal to $n_{\varphi} - 1$. By induction, $\varphi_k$ lies in the sum $k\mathcal{B}_{\alpha,X} + K_{\alpha}(X)$ and it follows that $\varphi = w + \sum_{k=0}^{h} (-1)^k \varphi_k$ also belongs to $k\mathcal{B}_{\alpha,X} + K_{\alpha}(X)$. Hence $F_T(X) = k\mathcal{B}_{\alpha,X} + K_{\alpha}(X)$, as required. $\square$

**6. Basis for the evaluation**

We continue our investigation of the evaluation $\mathcal{S}_{\alpha}(X)$ and show that the image of $\mathcal{B}_{\alpha,X}$ is a $k$-basis of $\mathcal{S}_{\alpha}(X)$.
**6.1. Theorem.** Let $\alpha : T \to T'^{\text{op}}$ be a join-morphism of finite lattices. Then for any finite set $X$, the set $\mathcal{B}_{\alpha,X} = \{\varphi \in T^X \mid \Phi_\alpha \subseteq \varphi(X) \subseteq G_\alpha\}$ maps injectively to a k-basis of $\mathbb{S}_\alpha(X) = F_T(X)/K_\alpha(X)$. In other words, $F_T(X) = k\mathcal{B}_{\alpha,X} \oplus K_\alpha(X)$.

As explained in Section 7, this result is a far-reaching generalization of Theorem 6.6 in [5], where we only consider the so-called fundamental functors. In spirit, the proof is essentially the same as the proof in [5], but as it has to be generalized and adapted to the new situation, we need to go through all the arguments again.

**Proof.** Throughout this proof, we write $G = G_\alpha$, $\Phi = \Phi_\alpha$, and $\mathcal{B}_X = \mathcal{B}_{\alpha,X}$, and we use $\vdash$ instead of $\vdash_\alpha$.

Since $\mathcal{B}_X$ generates $\mathbb{S}_\alpha(X)$ by Theorem 5.12, all we have to prove is that $\mathcal{B}_X$ maps injectively in $\mathbb{S}_\alpha(X)$ and that its image remains a linearly independent subset. To do this, for each $\varphi \in \mathcal{B}_X$, we consider the map $\zeta\varphi : X \to T'$, where $\zeta : T \to T'$ is defined by

$$ \forall t \in T, \zeta(t) = \begin{cases} \alpha(t) & \text{if } t \in \Phi, \\ \alpha^\sharp(t) & \text{otherwise.} \end{cases} $$

Inside the matrix of the pairing $\langle-, -\rangle_X$ of Proposition 3.9, we consider the square submatrix $M$, indexed by $\mathcal{B}_X \times \mathcal{B}_X$, defined by

$$ \forall (\varphi, \varphi') \in \mathcal{B}_X \times \mathcal{B}_X, \quad M(\varphi, \varphi') = \langle\varphi, \zeta\varphi'\rangle_X. $$

If this matrix is nonsingular, then $\mathcal{B}_X$ maps injectively in $F_T(X)/K_\alpha(X)$ and its image is a linearly independent set. We will actually prove more:

**6.2. Theorem.** The matrix $M$ is invertible (over $\mathbb{Z}$, hence over $k$).

**Proof.** By definition, we have

$$ \forall (\varphi, \varphi') \in \mathcal{B}_X \times \mathcal{B}_X, \quad M(\varphi, \varphi') = \begin{cases} 1 & \text{if } \varphi \vdash \zeta\varphi', \\ 0 & \text{otherwise.} \end{cases} $$

Now

$$ \varphi \vdash \zeta\varphi' \iff \begin{cases} \varphi \le \beta\zeta\varphi', \\ \forall f' \in \Phi', \exists x \in X, \varphi(x) = \beta(f') \text{ and } \zeta\varphi'(x) = f'. \end{cases} $$

We observe that the equality $\zeta\varphi'(x) = f'$ implies that $\varphi'(x) \in \Phi$, otherwise we would have $\zeta\varphi'(x) = \alpha^\sharp\varphi'(x) \notin \Phi'$, hence $\zeta\varphi'(x) \ne f'$. Moreover $\varphi'(x) \in \Phi$ implies that $\zeta\varphi'(x) = \alpha\varphi'(x)$. It follows that $\varphi'(x) = \beta\alpha\varphi'(x) = \beta\zeta\varphi'(x) = \beta(f')$. Therefore, by Lemma 3.6, the condition
$$ \forall f' \in \Phi', \exists x \in X, \varphi(x) = \beta(f') \text{ and } \zeta\varphi'(x) = f' \quad (6.3) $$

implies that

$$ \forall f \in \Phi, \exists x \in X, \varphi(x) = f = \varphi'(x). \quad (6.4) $$

Conversely, if (6.4) holds, then for any $f' \in \Phi'$, there exists $x \in X$ such that $\varphi(x) = \beta(f')$ and $\varphi'(x) = \beta(f')$. Then $\zeta\varphi'(x) = \alpha\beta(f') = f'$ and so (6.3) holds. Thus (6.3) and (6.4) are equivalent and we get

$$ \varphi \vdash \zeta\varphi' \iff \left\{ \begin{array}{l} \varphi \le \beta\zeta\varphi', \\ \forall f \in \Phi, \exists x \in X, \varphi(x) = f = \varphi'(x). \end{array} \right. $$

Now for any $x \in X$, we have $\beta\zeta\varphi'(x) = \beta\alpha\varphi'(x) = \varphi'(x)$ if $\varphi'(x) \in \Phi$, while $\beta\zeta\varphi'(x) = \beta\alpha^\sharp\varphi'(x) = \omega\varphi'(x)$ if $\varphi'(x) \notin \Phi$. Therefore

$$ \varphi \le \beta\zeta\varphi' \iff \forall x \in X, \left\{ \begin{array}{ll} \varphi(x) \le \varphi'(x) & \text{if } \varphi'(x) \in \Phi, \\ \varphi(x) \le \omega\varphi'(x) & \text{otherwise.} \end{array} \right. \quad (6.5) $$

Finally

$$ \varphi \vdash \zeta\varphi' \iff \left\{ \begin{array}{ll} \forall x \in X, & \left\{ \begin{array}{ll} \varphi(x) \le \varphi'(x) & \text{if } \varphi'(x) \in \Phi, \\ \varphi(x) \le \omega\varphi'(x) & \text{otherwise.} \end{array} \right. \\ \\ \forall f \in \Phi, \exists x \in X, \varphi(x) = f = \varphi'(x). \end{array} \right. $$

Suppose that $\varphi \vdash \zeta\varphi'$ holds. Then in particular $\omega\varphi(x) \le \omega\varphi'(x)$ for any $x \in X$, because $\omega$ is order-preserving and idempotent, by Lemma 4.7. By Lemma 4.2, we also deduce that $\rho\varphi(x) \le \rho\varphi'(x)$ if $\varphi'(x) \in \Phi$. Moroever, if $\varphi'(x) \notin \Phi$, then $\varphi'(x) \in G - \Phi$ (because $\varphi'(X) \subseteq G$ by the definition of $\mathcal{B}_X$) and we get

$$ \rho\varphi(x) \le \rho\omega\varphi'(x) = \rho\beta\alpha^\sharp\varphi'(x) = \beta^\sharp\alpha^\sharp\varphi'(x) = \theta\varphi'(x) = \varphi'(x) = \rho\varphi'(x), $$

using again that $\varphi'(x)$ lies in $G - \Phi = \text{Im}(\theta)$, hence is fixed under $\theta$ and $\rho$. We have now proved that

$$ \varphi \vdash \zeta\varphi' \implies \left\{ \begin{array}{l} \omega\varphi \le \omega\varphi' \text{ and} \\ \rho\varphi \le \rho\varphi'. \end{array} \right. $$

We denote by $\leq$ the preorder on the set $\mathcal{B}_X$ defined by the right hand side, that is, for all $\varphi, \varphi' \in \mathcal{B}_X$,

$$ \varphi \leq \varphi' \iff (\omega\varphi \leq \omega\varphi' \text{ and } \rho\varphi \leq \rho\varphi'). $$
It follows that the matrix $M$ is block triangular, with blocks indexed by the equivalence classes of the preorder $\leq$ on $\mathcal{B}_X$. We denote by $\leq\geq$ this equivalence relation, i.e.

$$ \varphi_{\leq\geq} \varphi' \iff (\varphi \leq \varphi' \text{ and } \varphi' \leq \varphi) \iff (\omega\varphi = \omega\varphi' \text{ and } \rho\varphi = \rho\varphi'). $$

Showing that $M$ is invertible now amounts to showing that its diagonal blocks are invertible. In other words, we must prove that, for each equivalence class $C$ of $\mathcal{B}_X$ for the relation $\leq\geq$, the matrix $M_C = (M(\varphi, \varphi'))_{\varphi', \varphi\in C}$ is invertible. Let $C$ be such a fixed equivalence class.

Let $t \in G - \Phi$. Then $t = \theta(t)$ and, for any $u \in [t, \omega(t)]$, we have $\rho(u) = t$ and $\omega(u) = \omega(t)$ by Lemma 4.11. It follows in particular that $t$ is uniquely determined by any element $u \in [t, \omega(t)]$, so that the sets $[t, \omega(t)]$, for $t \in G - \Phi$, are disjoint. We set

$$ \mathring{G} = \{t \in G - \Phi \mid t < \omega(t)\}. $$

Remember that, by Lemma 4.8, we have

$$ \forall t \in G - \Phi, \quad ]t, \omega(t)] \subseteq \Phi. \qquad (6.6) $$

This shows that $\mathring{G} = \{t \in G - \Phi \mid \omega(t) \in \Phi\}$. Moreover, we set

$$ \forall t \in \mathring{G}, \quad G_t = [t, \omega(t)] \quad \text{and} \quad G_* = G - \bigsqcup_{t \in \mathring{G}} G_t, $$

so that we get a partition

$$ G = \bigsqcup_{t \in \{\ast\} \sqcup \mathring{G}} G_t. $$

Notice that

$$ G_* - (G_* \cap \Phi) = \{t \in T \mid t = \theta(t) = \omega(t)\}. $$

This set is actually equal to $\beta(T') - \Phi$ by Proposition 4.13, but that does not play any role in the sequel.

**6.7. Lemma.** Let $\varphi', \varphi \in \mathcal{B}_X$. If $\varphi' \leq\geq \varphi$, then $\varphi'^{-1}(G_t) = \varphi^{-1}(G_t)$ for all $t \in \{\ast\} \sqcup \mathring{G}$.

**Proof.** Since $\varphi' \leq\geq \varphi'$, we have $\rho\varphi = \rho\varphi'$ and $\omega\varphi = \omega\varphi'$, by the above discussion. Let $t \in \mathring{G}$, and let $x \in \varphi^{-1}(G_t)$. Then $\varphi(x) \in [t, \omega(t)]$, so $\rho(t) = t = \rho(\varphi(x)) = \rho(\varphi'(x)) \leq \varphi'(x)$. Similarly $\omega(t) = \omega(\varphi(x)) = \omega(\varphi'(x)) \geq \varphi'(x)$, by Lemma 4.7. It follows that $t \leq \varphi'(x) \leq \omega(t)$, so $x \in \varphi'^{-1}(G_t)$. Hence $\varphi^{-1}(G_t) \subseteq \varphi'^{-1}(G_t)$. Exchanging the roles of $\varphi$ and $\varphi'$, we obtain that $\varphi^{-1}(G_t) = \varphi'^{-1}(G_t)$. Now $G_*$ is the complement of $\bigsqcup_{t \in \mathring{G}} G_t$
in $G$ and the functions $\varphi'$, $\varphi$ have their values in $G$ (by the definition of $\mathcal{B}_X$). So we must have also $\varphi'^{-1}(G_*) = \varphi^{-1}(G_*)$. This completes the proof of Lemma 6.7. $\square$

We choose an arbitrary element $\varphi_0$ of $C$ and, for every $t \in \{*\} \sqcup \mathring{G}$, we define

$$X_t = \varphi_0^{-1}(G_t).$$

It follows from Lemma 6.7 that this definition does not depend on the choice of $\varphi_0$. Therefore, the equivalence class $C$ yields a decomposition of $X$ as a disjoint union

$$X = \bigsqcup_{t \in \{*\} \sqcup \mathring{G}} X_t,$$

and every function $\varphi \in C$ decomposes as the disjoint union of the functions $\varphi_t$, where $\varphi_t : X_t \to G_t$ is the restriction of $\varphi$ to $X_t$.

For $t \in \mathring{G}$, define

$$\Phi_t = ]t, \omega(t)] .$$

By (6.6), we have $\Phi_t = \Phi \cap G_t$. Then we define $\Phi_* = \Phi - \bigsqcup_{t \in \mathring{G}} \Phi_t = \Phi \cap G_*$, so that we get a partition

$$\Phi = \bigsqcup_{t \in \{*\} \sqcup \mathring{G}} \Phi_t.$$

For every $t \in \{*\} \sqcup \mathring{G}$ and every $\varphi \in C$, the function $\varphi_t$ satisfies the condition $\Phi_t \subseteq \varphi_t(X_t) \subseteq G_t$, by the definition of $\mathcal{B}_X$. Moreover, if $\varphi'$, $\varphi \in C$, then

$$M(\varphi, \varphi') = 1 \iff \forall t \in \{*\} \sqcup \mathring{G}, \left\{ \begin{array}{ll} \forall x \in X_t, & \begin{cases} \varphi(x) \le \varphi'(x) & \text{if } \varphi'(x) \in \Phi_t, \\ \varphi(x) \le \omega\varphi'(x) & \text{otherwise,} \end{cases} \\ \\ \forall f \in \Phi_t, \exists x \in X_t, \varphi(x) = f = \varphi'(x). \end{array} \right.$$

It follows that the matrix $M_C$ is a tensor product of square matrices $M_{C,t}$, for $t \in \{*\} \sqcup \mathring{G}$, where $M_{C,t}$ is indexed by the set $A_t$ of functions $\varphi : X_t \to G_t$ such that $\Phi_t \subseteq \varphi(X_t)$. Thus $M_{C,t}$ satisfies

$$M_{C,t}(\varphi, \varphi') = 1 \iff \left\{ \begin{array}{ll} \forall x \in X_t, & \begin{cases} \varphi(x) \le \varphi'(x) & \text{if } \varphi'(x) \in \Phi_t, \\ \varphi(x) \le \omega\varphi'(x) & \text{otherwise,} \end{cases} \\ \\ \forall f \in \Phi_t, \exists x \in X_t, \varphi(x) = f = \varphi'(x). \end{array} \right.$$

In order to show that $M_C$ is invertible, we shall prove that each matrix $M_{C,t}$ is invertible.
If $x \in X_*$ and $\varphi' \in A_*$, then either $\varphi'(x) = \omega\varphi'(x)$ or $\varphi'(x) \in \Phi_*$, by the construction of $G_*$. Therefore, if $M_{C,\ast}(\varphi, \varphi') \neq 0$, then $\varphi(x) \leq \varphi'(x)$ for any $x \in X_*$. It follows that the matrix $M_{C,\ast}$ is triangular. Clearly $M_{C,\ast}(\varphi, \varphi) = 1$ for any $\varphi \in A_*$, so $M_{C,\ast}$ is unitriangular, hence invertible, as required.

We are left with the matrices $M_{C,t}$ for $t \in \hat{G}$. If $t \in \hat{G}$, then $G_t = [t, \omega(t)]$ is isomorphic to the totally ordered lattice $\underline{n} = \{0 < 1 < \dots < n\}$ for some $n \geq 1$ (note that $t < \omega(t)$). Moreover, $\Phi_t = [t, \omega(t)]$ is isomorphic to $[n] = \{1, \dots, n\}$. Composing the maps $\varphi_t: X_t \to G_t$ with this isomorphism, we obtain maps $X_t \to \underline{n}$. Changing notation for simplicity, we write $X$ for $X_t$ and we consider the set $A_n$ of all such maps $\varphi: X \to \underline{n}$ satisfying the condition $[n] \subseteq \varphi(X)$. The matrix $M_{C,t}$, which we write $M$ for simplicity, is now indexed by $A_n$ and we have

$$M(\varphi, \varphi') = 1 \iff \left\{ \begin{array}{ll} \forall x \in X, & \begin{cases} \varphi(x) \leq \varphi'(x) & \text{if } \varphi'(x) \in [n], \\ \varphi(x) \leq \omega\varphi'(x) & \text{if } \varphi'(x) = 0, \end{cases} \\ \\ \forall f \in [n], \exists x \in X, \varphi(x) = f = \varphi'(x). \end{array} \right.$$

We observe that the condition $\varphi(x) \leq \omega\varphi'(x)$ if $\varphi'(x) = 0$ is always fulfilled since $\omega(0) = n$. Hence

$$M(\varphi, \varphi') = 1 \iff \left\{ \begin{array}{ll} \forall x \in X, & \varphi(x) \leq \varphi'(x) \text{ if } \varphi'(x) \in [n], \\ \\ \forall f \in [n], \exists x \in X, & \varphi(x) = f = \varphi'(x). \end{array} \right.$$

This is exactly the matrix $M_{\varphi',\varphi}^n$ considered at the end of the proof of Theorem 6.1 in [5]. In fact, it is a reduction to the case of a totally ordered lattice because this matrix corresponds to the special case $T = \underline{n}$. It is proved on page 246 of [5] that this matrix is invertible. This completes the proof of Theorem 6.2, hence of Theorem 6.1. $\square$

**6.8. Corollary.** Let $\alpha: T \to T'^{\text{op}}$ be a join-morphism of finite lattices and let $S_\alpha$ be the associated correspondence functor. Then for any finite set $X$ the $k$-module $S_\alpha(X)$ is free of rank

$$\mathrm{rk}(S_\alpha(X)) = \sum_{i=0}^{|\Phi_\alpha|} (-1)^i \binom{|\Phi_\alpha|}{i} (|G_\alpha| - i)^{|X|}.$$

**Proof.** A well-known combinatorial formula (see Lemma 8.1 in [3]) shows that the right hand side in the statement gives the number of maps $\varphi: X \to T$ satisfying the condition $\Phi_\alpha \subseteq \varphi(X) \subseteq G_\alpha$. The result follows from Theorem 6.1. $\square$

We can now give an answer to the question left open in Remark 3.12 and prove that the pairing $S_\alpha \times S'_\alpha \to k$ is nondegenerate in the strong sense.
**6.9. Proposition.** Let $\alpha : T \to T'^{\text{op}}$ be a join-morphism of finite lattices and let $\langle - , - \rangle : F_T \times F_{T'} \to k$ be the associated pairing (see Proposition 3.9). Then the natural morphism

$$i : S_{\alpha} = F_T / K_{\alpha} \longrightarrow (S'_{\alpha})^{\natural} = (F_{T'} / K'_{\alpha})^{\natural}$$

is an isomorphism.

**Proof.** For the convenience of this proof, we pass to the dual and we aim to prove that the natural morphism $j : S'_{\alpha} \to S^{\natural}_{\alpha}$ is an isomorphism. By Lemma 6.2, we know that the matrix $M$ indexed by $\mathcal{B}_{\alpha,X} \times \mathcal{B}_{\alpha,X}$ defined by

$$\forall (\pi, \varphi) \in \mathcal{B}_{\alpha,X} \times \mathcal{B}_{\alpha,X}, \quad M(\pi, \varphi) = \langle \pi, \zeta \varphi \rangle_X$$

is invertible. Let $N = M^{-1}$. Then

$$\forall (\pi, \pi') \in \mathcal{B}_{\alpha,X} \times \mathcal{B}_{\alpha,X}, \quad \sum_{\varphi \in \mathcal{B}_{\alpha,X}} \langle \pi, \zeta \varphi \rangle_X N(\varphi, \pi') = \delta_{\pi, \pi'},$$

where $\delta_{\pi, \pi'}$ is the Kronecker symbol.

The natural morphism $j_X : F_{T'}(X)/K'_{\alpha}(X) \to (F_T(X)/K_{\alpha}(X))^{\natural}$ is injective, by the definition of $K'_{\alpha}$. Now $(F_T(X)/K_{\alpha}(X))^{\natural}$ is isomorphic to the submodule of $F_T(X)^{\natural}$ consisting of linear forms $F_T(X) \to k$ which vanish on $K_{\alpha}(X)$. Let $\lambda$ be such a form, and set

$$\hat{\lambda} = \sum_{\varphi, \pi' \in \mathcal{B}_{\alpha,X}} N(\varphi, \pi')\lambda(\pi')\zeta\varphi \in F_{T'}(X).$$

Then for any $\pi \in \mathcal{B}_{\alpha,X}$,

$$\langle \pi, \hat{\lambda} \rangle_X = \sum_{\varphi, \pi' \in \mathcal{B}_{\alpha,X}} N(\varphi, \pi')\lambda(\pi')\langle \pi, \zeta\varphi \rangle_X = \sum_{\pi' \in \mathcal{B}_{\alpha,X}} \delta_{\pi, \pi'}\lambda(\pi') = \lambda(\pi).$$

Moreover $\langle u, \hat{\lambda} \rangle_X = 0$ for any $u \in K_{\alpha}(X)$, by the definition of $K_{\alpha}$, and $\lambda(u) = 0$ also, by our assumption on $\lambda$. It follows that the linear forms $\lambda$ and $\langle - , \hat{\lambda} \rangle_X$ coincide on $k\mathcal{B}_{\alpha,X} + K_{\alpha}(X)$, which is the whole of $F_T(X)$ by Theorem 5.12. Hence $\lambda = \langle - , \hat{\lambda} \rangle_X$, so $\lambda$ lies in the image of the morphism $j_X$. It follows that $j_X$ is surjective, hence it is an isomorphism. $\square$

**7. The main example of fundamental functors**

Let $T$ be a finite lattice and let $(E, R)$ be the poset of irreducible elements of $T$, i.e. $E = \text{Irr}(T)$ and $R$ is the restriction to $E$ of the order relation of $T$. For clarity, we use a subscript $T$ for the interval $[s, t]_T$ in $T$, where $s \le t$ in $T$. Similarly, if $a \le b$ in $E$, then
$[a, b]_E = \{e \in E | a \le e \le b\}$. Recall that an upper subset in $E$ is a subset $A$ of $E$ such that, whenever $a \in A$ and $a \le b$ with $b \in E$, then $b \in A$. We let $I^\uparrow(E, R)$ be the set of all upper subsets in $E$, which is a lattice for the usual operations of union and intersection. We consider the map

$$ \alpha : T \to I^\uparrow(E, R)^{op}, \quad t \mapsto \alpha(t) := [t, \hat{1}]_T \cap E, $$

which is easily seen to be a join-morphism, because $[s \lor t, \hat{1}]_T = [s, \hat{1}]_T \cap [t, \hat{1}]_T$ and $\alpha(\hat{0}) = [\hat{0}, \hat{1}]_T \cap E = E = \hat{1}_{I^\uparrow(E,R)} = \hat{0}_{I^\uparrow(E,R)^{op}}$.

Our aim is to show that the corresponding functor $S_\alpha$ is isomorphic to the fundamental functor $S_{E,R^{op}}$ studied in [4,5] and that our description of a $k$-basis of $S_\alpha(X)$ is the same as the one obtained for $S_{E,R^{op}}(X)$ in [5]. In fact, our results in Sections 5 and 6 have been inspired by this very special case, already proved in [5].

**7.1. Lemma.** Let $\alpha : T \to I^\uparrow(E, R)^{op}$ be as above and let $\beta = \alpha^{op}$.

(a) For any $A \in I^\uparrow(E, R)$, we have $\beta(A) = \bigwedge_{a \in A} a$.

(b) $\Phi_\alpha = E$ and $\Phi'_\alpha = \{[e, \cdot|_E | e \in E]\}$, where $[e, \cdot|_E = \{f \in E | f \ge e\}$.

**Proof.** (a) We have

$$ \beta(A) = \bigvee_{\alpha(t) \subseteq_{\text{op}} A} t = \bigvee_{A \subseteq_{\alpha} t} t = \bigvee_{A \subseteq [t, \hat{1}]_T} t = \bigvee_{t \subseteq A} t = \bigwedge_{a \in A} a. $$

(b) For any $e \in E = \text{Irr}(T)$, we have $\alpha(e) = [e, \cdot|_E$ and this is an irreducible element of $I^\uparrow(E, R)$ (also called a principal upper subset). Moreover, by (a),

$$ \beta\alpha(e) = \bigwedge_{f \in [e, \cdot|_E} f = \bigwedge_{f \ge e} f = e. $$

The definition of $\Phi_\alpha$ (see Notation 3.5) yields $\Phi_\alpha = E$. Moreover, we have $\Phi'_\alpha = \alpha(\Phi_\alpha) = \{[e, \cdot|_E | e \in E]\}$. $\square$

**7.2. Proposition.** With the notation above, there is an isomorphism $S_\alpha \cong S_{E,R^{op}}$, where $S_{E,R^{op}}$ is the fundamental functor introduced in [4].

**Proof.** We don't go back to the definition of $S_{E,R^{op}}$ but use instead the following description. By Theorem 6.5 in [4], there is a canonical surjective morphism $\Theta_T : F_T \to S_{E,R^{op}}$. Next, Theorem 7.1 in [4] asserts that, on evaluation at a finite set $X$, the kernel of the map $\Theta_{T,X} : F_T(X) \to S_{E,R^{op}}(X)$ consists of all linear combinations $\sum_{\varphi \in T^X} \lambda_\varphi \varphi$ satisfying a system of linear equations $(E_\psi)$ indexed by all maps $\psi : X \to I^\uparrow(E, R)$. More explicitly,
$$ (E_{\psi}): \quad \sum_{\substack{\varphi \in T^X \\ \varphi \vdash_{E,R} \psi}} \lambda_{\varphi} = 0, $$

where the relation $\vdash_{E,R}$ is defined as follows (see Theorem 7.3 in [4] or Theorem 4.13 in [5]):

$$ \varphi \vdash_{E,R} \psi \iff \forall t \in T, \psi(\varphi^{-1}(t)) \subseteq [t, \hat{1}_{[T \cap E}] \text{ and } \forall e \in E, \psi(\varphi^{-1}(e)) = [e, \cdot_{[E}]], $$

with the abuse of notation which identifies $\psi(\varphi^{-1}(t))$ with the union of its elements in $I^{\uparrow}(E, R)$. The first condition can be rewritten as

$$ \forall t \in T, \psi(\varphi^{-1}(t)) \subseteq [\hat{0}, \alpha(t)]_{I^{\uparrow}(E,R)} $$

while the second becomes

$$ \forall e \in E, \alpha(e) \in \psi(\varphi^{-1}(e)). $$

Thus we find that $\varphi \vdash_{E,R} \psi$ is equivalent to $\varphi \vdash \psi$ (see Notation 3.8). It follows that the equation $(E_{\psi})$ can be rewritten as $\sum_{\varphi \vdash \psi} \lambda_{\varphi} = 0$. Since this must hold for every $\psi$, we obtain that $\sum_{\varphi \in T^X} \lambda_{\varphi} \varphi$ must belong to the left kernel of the pairing defined in Notation 3.8. In other words, $\text{Ker}(\Theta_{T,X}) = K_{\alpha}(X)$. This implies that

$$ \mathbb{S}_{\alpha}(X) = F_{T}(X)/K_{\alpha}(X) = F_{T}(X)/\text{Ker}(\Theta_{T,X}) \cong \mathbb{S}_{E,R^{op}}(X), $$

hence $\mathbb{S}_{\alpha} \cong \mathbb{S}_{E,R^{op}}$, as was to be shown. $\square$

By Theorem 6.1, we know that a $k$-basis of $\mathbb{S}_{\alpha}(X)$ is obtained by taking the image of the subset

$$ \mathcal{B}_{\alpha,X} = \{\varphi \in T^X \mid E \subseteq \varphi(X) \subseteq G_{\alpha}\} \subseteq F_{T}(X), $$

where $G_{\alpha}$ is defined in (5.1). Similarly, by Theorem 6.6 in [5], we know that a $k$-basis of $\mathbb{S}_{E,R^{op}}(X)$ is obtained by taking the image of the subset

$$ \mathcal{B}_{X} = \{\varphi \in T^X \mid E \subseteq \varphi(X) \subseteq G\} \subseteq F_{T}(X), $$

where $G$ is described as

$$ G = E \sqcup G^{\sharp}, \quad G^{\sharp} = \{a \in T \mid a = r^{\infty} \sigma^{\infty}(a)\}, \qquad (7.3) $$

as in Lemma 2.9 of [5]. Here $r : T \to T$ is defined by (3.13) and $\sigma : T \to T$ is defined by

$$ \sigma(t) = \bigwedge_{\substack{e \in \text{Irr}(T) \\ t < e}} e. $$
Now we can show that both approaches coincide and that the result of [5] is indeed a
special case of Theorem 6.1.

**7.4. Proposition.** With the notation above, $G_\alpha = G$, hence $\mathcal{B}_{\alpha,X} = \mathcal{B}_X$.

**Proof.** Since $\Phi_\alpha = E$ by Lemma 7.1, we get $G_\alpha = E \sqcup \mathrm{Im}(\theta)$, so we need to show that

$$t \in \mathrm{Im}(\theta) \iff t \in G^{\sharp}.$$

We can assume that $t \notin E$ because both subsets intersect $E$ trivially. Now $t \in \mathrm{Im}(\theta)$ if and only if

$$t = \theta(t) = \beta^{\sharp} \alpha^{\sharp}(t) = \rho \omega(t) = r^{\infty} \omega(t)$$

because we have $\rho = r^\infty$ by Lemma 4.2 and the fact that $\Phi_\alpha = E$. So we are left with the proof that $\omega(t) = \sigma^\infty(t)$ for any $t \in T$ with $t \notin E$.

Suppose first that $\alpha(t) \notin \Phi'_\alpha$. Then $\alpha^\sharp(t) = \alpha(t)$ and Lemma 7.1 implies that

$$\omega(t) = \beta\alpha(t) = \bigwedge_{a \in \alpha(t)} a = \bigwedge_{\substack{a \in E \\ a \ge t}} a = \bigwedge_{\substack{a \in E \\ a > t}} a$$

because $t \notin E$. Therefore $\omega(t) = \sigma(t)$. The same argument applies to $\omega(t)$ instead of $t$, because $\alpha(\omega(t)) = \alpha\beta\alpha(t) = \alpha(t) \notin \Phi'_\alpha$. Thus $\omega(\omega(t)) = \sigma(\omega(t))$ and therefore

$$\sigma^2(t) = \sigma\omega(t) = \omega(\omega(t)) = (\beta\alpha)^2(t) = \beta\alpha(t) = \sigma(t).$$

It follows that $\sigma^\infty(t) = \sigma(t) = \omega(t)$.

Suppose now that $\alpha(t) \in \Phi'_\alpha$. Let $l \ge 1$ be the smallest integer such that $\alpha^\sharp(t) = r^l\alpha(t) \notin \Phi'_\alpha$. By Lemma 4.7, we have $[t, \omega(t)] \cap E = \{u_0, \dots, u_{l-1}\}$, where $u_i = \beta r^i\alpha(t)$ for $0 \le i \le l-1$. For any $e \in E$ with $e > t$, we have $\alpha(e) \le \alpha(t)$ and Corollary 4.4 implies that either $\alpha(e) = r^i\alpha(t)$ for some $0 \le i \le l-1$ or $\alpha(e) \le \alpha^\sharp(t)$. Applying $\beta$ and using the equality $e = \beta\alpha(e)$ (because $e \in E = \Phi_\alpha$), we see that either $e = u_i$ for some $0 \le i \le l-1$ or $e \ge \beta\alpha^\sharp(t) = \omega(t)$. The definition of $\sigma$ and the fact that $t < u_0$ (because $t \notin E$) yield

$$\sigma(t) = u_0, \sigma(u_0) = u_1, \dots, \sigma(u_{l-2}) = u_{l-1}. \qquad (7.5)$$

It remains to determine $\sigma(u_{l-1})$.

Note first that, for any $f \in E$, we have $\alpha(f) = [f, 1[T \cap E = [f, \cdot]_{[E}$ and moreover

$$\sigma(f) = \bigwedge_{\substack{e \in E \\ e > f}} e = \bigwedge_{e \in [f, \cdot]_{[E}} e = \beta([f, \cdot]_{[E]}), \qquad (7.6)$$
by Lemma 7.1. Therefore

$$r^{l-1}\alpha(t) = \alpha\beta(r^{l-1}\alpha(t)) = \alpha(u_{l-1}) = [u_{l-1}, \cdot]_E$$

and hence

$$\alpha^{\#}(t) = r^{l}\alpha(t) = r[u_{l-1}, \cdot]_E = u_{l-1}, \cdot]_E,$$

so that

$$\omega(t) = \beta\alpha^{\#}(t) = \beta([u_{l-1}, \cdot]_E) = \sigma(u_{l-1}) = \sigma^{l+1}(t),$$

using (7.6) and (7.5).

There are now two cases. Suppose first that $\sigma(u_{l-1}) = u_{l-1}$. Then $\sigma^{l+1}(t) = \sigma(u_{l-1}) = u_{l-1}$, hence $\sigma^{\infty}(t) = u_{l-1} = \sigma(u_{l-1}) = \omega(t)$, as was to be shown. Suppose now that $\sigma(u_{l-1}) > u_{l-1}$, that is, $\omega(t) > u_{l-1}$. Then $\omega(t) \notin E$ by Lemma 4.7(c). The definition of $\sigma$ implies that, for any $e \in E$,

$$e > u_{l-1} \iff e \ge \sigma(u_{l-1}) \iff e \ge \omega(t) \iff e > \omega(t),$$

where the latter equivalence comes from the fact that $\omega(t) \notin E$. We deduce that $\sigma(u_{l-1}) = \sigma(\omega(t))$, hence $\omega(t) = \sigma(\omega(t))$. But since $\sigma^{l+1}(t) = \sigma(u_{l-1}) = \omega(t)$, we obtain $\sigma^{\infty}(t) = \omega(t)$.

This shows that $\sigma^{\infty}(t) = \omega(t)$ in all cases, completing the proof that $\mathrm{Im}(\theta) = G^{\#}$. The equality $B_{\alpha,X} = B_X$ follows. $\square$

## 8. The injective case

In this section, we study the case when our given join-morphism $\alpha : T \to T'^{\mathrm{op}}$ is injective. We first show that this injective case could also be called the surjective case.

**8.1. Lemma.** Let $\alpha : T \to T'^{\mathrm{op}}$ be a join-morphism of finite lattices and let $\beta = \alpha^{\mathrm{op}}$.

(a) If $\alpha$ is injective, then $\beta\alpha = \mathrm{id}_T$ and in particular $\beta$ is surjective.

(b) If $\beta$ is surjective, then $\beta\alpha = \mathrm{id}_T$ and in particular $\alpha$ is injective.

**Proof.** (a) Since $\alpha\beta\alpha = \alpha$ by Lemma 3.4, the injectivity of $\alpha$ implies that $\beta\alpha = \mathrm{id}_T$.

(b) Similarly, since $\beta\alpha\beta = \beta$ by Lemma 3.4, the surjectivity of $\alpha$ implies that $\beta\alpha = \mathrm{id}_T$. $\square$

Next we show that some important simplifications occur.

**8.2. Lemma.** Let $\alpha : T \to T'^{\mathrm{op}}$ be a join-morphism of finite lattices and suppose that $\alpha$ is injective.
(a) $\Phi_{\alpha} = \{f \in \text{Irr}(T) \mid \alpha(f) \in \text{Irr}(T')\}$.

(b) $G_{\alpha} = T$.

(c) $T = \Phi_{\alpha} \sqcup \{t \in T \mid t = \omega(t) = \theta(t)\}$.

**Proof.** (a) Let $\beta = \alpha^{op}$ as usual. The definition of $\Phi_{\alpha}$ contains the condition $\beta\alpha(f) = f$, but this condition is automatically satisfied when $\alpha$ is injective, by Lemma 8.1.

(b) By Lemma 5.2, we have $\beta(T') \subseteq G_{\alpha}$, hence $G_{\alpha} = T$ by surjectivity of $\beta$.

(c) By Proposition 4.13, we have $\beta(T') = \Phi_{\alpha} \sqcup \{t \in T \mid t = \omega(t) = \theta(t)\}$. $\square$

**8.3. Remark.** Let $t \in T$ and let $l$ be the smallest integer such that $r^l\alpha(t) \notin \Phi'_{\alpha}$, as in Section 4. Keeping the assumption that $\alpha$ is injective, it is easy to see that

$$t \in \Phi_{\alpha} \iff \alpha(t) \in \Phi'_{\alpha} \iff l \ge 1.$$

Moreover, if $t \in \Phi_{\alpha}$ and $v_i = \beta r^i \alpha(t)$, then either

$$\theta(t) < t = v_0 < \dots < v_{l-1} = \omega(t) \in \Phi_{\alpha},$$

or

$$t = v_0 < \dots < v_{l-1} < \theta(t) = \omega(t) \notin \Phi_{\alpha}.$$

Both situations occur in specific examples. Note also that if $t \notin \Phi_{\alpha}$, then $t = \omega(t) = \theta(t)$ by Lemma 8.2, so there are no reduction sequences.

**8.4. Example.** Let $\alpha : T \to T'^{op}$ be an injective join-morphism of finite lattices. Replace every $e \in \text{Irr}(T')$ by a lozenge

<figure><img src="image_3.png" /></figure>

and let $\overline{T}'$ be the resulting lattice, in which every such $e$ becomes reducible. Thus no irreducible element of $T'$ remains irreducible in $\overline{T}'$ under the inclusion $j : T' \to \overline{T}'$ (mapping $e \in \text{Irr}(T')$ to the top $e$ in the corresponding lozenge) and so no irreducible element of $T$ is mapped to an irreducible element of $\overline{T}'$ under the composite $\overline{\alpha} = j \circ \alpha : T \to \overline{T}'^{op}$. By Lemma 8.2 and injectivity of $\overline{\alpha}$, we get $\Phi_{\overline{\alpha}} = \emptyset$ and $G_{\overline{\alpha}} = T$. Therefore the condition $\Phi_{\overline{\alpha}} \subseteq \varphi(X) \subseteq G_{\overline{\alpha}}$ is satisfied by every map $\varphi : X \to T$. Consequently, by using either Theorem 6.1 or Remark 3.16, we obtain

$$S_{\overline{\alpha}} = F_T,$$
so our main construction of functors also covers the functors $F_T$. In this example, $T$ can be any finite lattice, since we can choose $T' = T^{op}$ and $\alpha = \text{id}$.

## 9. The minimal nonzero evaluation

As usual, $\alpha : T \to T'^{op}$ is a join-morphism of finite lattices, $\Phi_\alpha$ is the subset of Irr($T$) defined in Notation 3.5, and $S_\alpha = F_T/K_\alpha$. We have seen that the set $\Phi_\alpha$ plays a crucial role throughout the paper and it appears again here as a minimal set such that the evaluation $S_\alpha(\Phi_\alpha)$ is nonzero. Our purpose is to analyse the structure of $S_\alpha(\Phi_\alpha)$ as a module for the algebra of the monoid of all relations on $\Phi_\alpha$. Let us start with an easy observation.

### 9.1. Lemma.

(a) For any finite set $X$, let $\varphi \in T^X$ be such that $\Phi_\alpha \not\subseteq \varphi(X)$. Then $\varphi \in K_\alpha(X)$.

(b) For any finite set $X$ such that $|X| < |\Phi_\alpha|$, we have $S_\alpha(X) = \{0\}$.

(c) $S_\alpha(\Phi_\alpha) \neq \{0\}$.

**Proof.** (a) This was already observed at the beginning of the proof of Theorem 5.12.

(b) If $\varphi \in T^X$ satisfies $\Phi_\alpha \not\subseteq \varphi(X)$, the image of $\varphi$ in $S_\alpha(X) = F_T(X)/K_\alpha(X)$ is zero by (a). If $|X| < |\Phi_\alpha|$, then $|\varphi(X)| \le |X| < |\Phi_\alpha|$, so $\Phi_\alpha \not\subseteq \varphi(X)$. Since this holds for every $\varphi$, we obtain $S_\alpha(X) = \{0\}$.

(c) If $X = \Phi_\alpha$, the inclusion $j : \Phi_\alpha \to T$ does not lie in $K_\alpha(\Phi_\alpha)$ because $j' = \alpha \circ j$ satisfies $j \vdash_\alpha j'$, hence $\langle j, j' \rangle_{\alpha, \Phi_\alpha} \neq 0$. Thus the image of $j$ in $S_\alpha(\Phi_\alpha)$ is nonzero.

Alternatively, the $k$-basis $B_{\alpha,X}$ of $S_\alpha(X)$ is empty if $|X| < |\Phi_\alpha|$ and nonempty if $X = \Phi_\alpha$. However, this argument is much less elementary since it requires Theorem 6.1. $\square$

Given a finite set $E$, the set of relations on $E$ (i.e. all subsets of $E \times E$) forms a monoid which is a $k$-basis for a $k$-algebra $A_E$, the algebra of the monoid. For any partial order relation $R$ on $E$, there is a very special $A_E$-module $M_{E,R}$, called the *fundamental module* associated to the pair $(E, R)$ and described explicitly in the following way. First $M_{E,R}$ is a free $k$-module with a basis $\{m_\sigma | \sigma \in \Sigma_E\}$, where $\Sigma_E$ is the group of all permutations of the set $E$. Then the left $A_E$-module structure is described by specifying the action of every relation $Q$ on the $k$-basis:

$$ Q \cdot m_{\sigma} = \begin{cases} m_{\tau\sigma} & \text{if } \exists \tau \in \Sigma_E \text{ such that } \Delta \subseteq \Delta_{\tau^{-1}} Q \subseteq {}^{\sigma}R, \\ 0 & \text{otherwise.} \end{cases} \qquad (9.2) $$

Here, $\Delta_\tau = \{(\tau(e), e) | e \in E\} \subseteq E \times E$ and ${}^\sigma R = \Delta_\sigma R \Delta_{\sigma^{-1}}$, while $\Delta = \Delta_{\text{id}}$ is the diagonal subset of $E \times E$.

The module $M_{E,R}$ was introduced in Section 7 of [2] as a left ideal $P f_R$, where $P$ is some quotient algebra of $A_E$ and $f_R$ is a suitable idempotent in $P$. The action (9.2)
appears in Proposition 8.5 of [2]. The fundamental module $M_{E,R}$ was used in [4,5] for the definition of the fundamental functor $S_{E,R}$, already mentioned in Section 7 as a very special case of $S_\alpha$. This module can also be recovered as the evaluation $S_{E,R}(E) \cong M_{E,R}$.

We now show that the latter isomorphism is again a very special case of a property of $S_\alpha$. To make our notation precise, we note that $\Phi_\alpha$ is a (full) subposet of $T$ and we let $R_\alpha$ be the partial order relation on $\Phi_\alpha$ obtained by restriction from $T$.

**9.3. Theorem.** With the notation above, $S_\alpha(\Phi_\alpha)$ is isomorphic to $M_{\Phi_\alpha, R_\alpha^{op}}$ as a module over the algebra $A_{\Phi_\alpha}$.

**Proof.** Write $\Phi = \Phi_\alpha$ and $R = R_\alpha$. Let $\varphi \in T^\Phi$ be such that its image in $S_\alpha(\Phi)$ is nonzero. By Lemma 9.1(a), we must have $\Phi \subseteq \varphi(\Phi)$, hence $\Phi = \varphi(\Phi)$. Therefore, there exists a permutation $\tau \in \Sigma_\Phi$ such that $\varphi \circ \tau = j$, where $j : \Phi \to T$ denotes the inclusion map. Then, by the definition of the action of correspondences, we get, for any $f \in \Phi$,

$$ (\Delta_{\tau}j)(f) = \bigvee_{\substack{x \in \Phi \\ (f,x) \in \Delta_{\tau}}} j(x) = j(\tau^{-1}(f)) = \varphi(f), $$

hence $\varphi = j \circ \tau^{-1} = \Delta_\tau j$. Thus all functions $\varphi \in T^\Phi$ map to zero in $S_\alpha(\Phi)$ except the functions $j \circ \tau^{-1} = \Delta_\tau j$.

Suppose that $\sigma \in \Sigma_\Phi$ is such that the relation $\Delta_\sigma j \vdash_\alpha j'$ holds, where $j' = \alpha \circ j$. Then Lemma 3.7(a) implies that $\alpha \circ j = j' \le \alpha \circ \Delta_\sigma j$, hence $j \ge \Delta_\sigma j$ because $\alpha|_\Phi : \Phi \to \Phi'^{op}$ is a poset isomorphism (Lemma 3.6). By increasing induction in the poset $\Phi$, we deduce that $j = \Delta_\sigma j$, hence $f = \sigma^{-1}(f)$ for all $f \in \Phi$, in other words $\sigma = \text{id}$. Thus if $\langle \Delta_\sigma j, j' \rangle_{\alpha, \Phi} \ne 0$, then $\sigma = \text{id}$.

Now we can prove that the functions $\{\Delta_\sigma j | \sigma \in \Sigma_\Phi\}$ remain $k$-linearly independent in $S_\alpha(\Phi) = \mathbb{F}_T(\Phi)/K_\alpha(\Phi)$. Suppose that

$$ \sum_{\sigma \in \Sigma_{\Phi}} \lambda_{\sigma} \Delta_{\sigma} j \in K_{\alpha}(\Phi), $$

where $\lambda_\sigma \in k$. Then, for all $\tau \in \Sigma_\Phi$,

$$ 0 = \langle \sum_{\sigma \in \Sigma_{\Phi}} \lambda_{\sigma} \Delta_{\sigma} j, \Delta_{\tau} j' \rangle_{\alpha, \Phi} = \sum_{\sigma \in \Sigma_{\Phi}} \lambda_{\sigma} \langle \Delta_{\tau}^{op} \Delta_{\sigma} j, j' \rangle_{\alpha, \Phi}, $$

because this is a functorial pairing by Proposition 3.9. But since we have $\Delta_{\tau}^{op} \Delta_\sigma = \Delta_{\tau^{-1}} \Delta_\sigma = \Delta_{\tau^{-1} \sigma}$, we get a nonzero term only if $\tau^{-1}\sigma = \text{id}$. So we are left with $0 = \lambda_\sigma \langle j, j' \rangle_{\alpha, \Phi} = \lambda_\sigma$, proving the required linear independence. Moreover, the image in $S_\alpha(\Phi)$ of the set $\{\Delta_\sigma j | \sigma \in \Sigma_\Phi\}$ is a basis of $S_\alpha(\Phi)$ because all the other functions $\varphi \in T^\Phi$ map to zero.

Now we consider the action of a relation $Q \subseteq \Phi \times \Phi$ and we assume first that $Qj = j$. Then, for all $f \in \Phi$, we have
$$f = j(f) = (Qj)(f) = \bigvee_{\substack{x \in \Phi \\ (f,x) \in Q}} j(x).$$

Since $f$ is irreducible in $T$, one of the terms must be $f$ and $j(x) \le j(f)$ for all $x$ such that $(f, x) \in Q$. In other words, $(f, f) \in Q$ and moreover the property $(f, x) \in Q$ implies $x \le f$ inside $\Phi$, that is, $(f, x) \in R^{op}$. Thus if $Qj = j$, then $\Delta \subseteq Q \subseteq R^{op}$. Conversely, if $\Delta \subseteq Q \subseteq R^{op}$, then

$$(Qj)(f) = \bigvee_{\substack{x \in \Phi \\ (f,x) \in Q}} j(x).$$

Since one of the terms is $j(f)$ (because $\Delta \subseteq Q$) and since $(f, x) \in Q$ implies $j(x) \le j(f)$ (because $Q \subseteq R^{op}$), we are left with $(Qj)(f) = j(f)$, hence $Qj = j$. We have proved that

$$Qj = j \iff \Delta \subseteq Q \subseteq R^{op}. \qquad (9.4)$$

Finally we can compute the action of $Q$ on each element $\Delta_{\sigma}j$ (mapping to a basis element of $S_{\alpha}(\Phi)$, as proved above). If $Q\Delta_{\sigma}j$ is not of the form $\Delta_{\pi}j$ for some $\pi \in \Sigma_{\Phi}$, then its image is zero in $S_{\alpha}(\Phi)$ by the first paragraph of the proof. Otherwise, by (9.4) followed by conjugation by $\Delta_{\sigma}$, we obtain

$$\begin{align*}
Q\Delta_{\sigma}j = \Delta_{\pi}j &\iff \Delta_{\pi^{-1}}Q\Delta_{\sigma}j = j \\
&\iff \Delta \subseteq \Delta_{\pi^{-1}}Q\Delta_{\sigma} \subseteq R^{op} \\
&\iff \Delta \subseteq \Delta_{\sigma}\Delta_{\pi^{-1}}Q \subseteq \Delta_{\sigma}R^{op}\Delta_{\sigma^{-1}} \\
&\iff \Delta \subseteq \Delta_{\tau^{-1}}Q \subseteq {}^{\sigma}R^{op}
\end{align*}$$

where $\tau = \pi\sigma^{-1}$. Thus we recover exactly the action of the monoid of relations on the fundamental module $M_{\Phi, R^{op}}$, as described in (9.2). In other words, we have an isomorphism of $A_{\Phi_{\alpha}}$-modules $S_{\alpha}(\Phi) \cong M_{\Phi, R^{op}}$. $\square$

Given a finite poset $(\Phi, R)$, the fundamental functor $S_{\Phi, R^{op}}$ is a special case of a functor $S_{\alpha}$, by Proposition 7.2. By Theorem 9.3 and Lemma 9.1, its evaluation at $\Phi$ is isomorphic to $M_{\Phi, R^{op}}$ and $S_{\Phi, R^{op}}(X) = \{0\}$ whenever $|X| < |\Phi|$. Moreover, this property is shared by all correspondence functors $S_{\alpha}$ whose associated poset $(\Phi_{\alpha}, R_{\alpha})$ is isomorphic to $(\Phi, R)$. We now show that the relationship between $S_{\alpha}$ and $S_{\Phi, R^{op}}$ can be made more explicit by establishing that the fundamental functor $S_{\Phi, R^{op}}$ is minimal among all correspondence functors $S_{\alpha}$ whose associated poset $(\Phi_{\alpha}, R_{\alpha})$ is isomorphic to $(\Phi, R)$.

**9.5. Proposition.** With the notation above, the fundamental functor $S_{\Phi_{\alpha}, R_{\alpha}^{op}}$ is isomorphic to a subquotient of $S_{\alpha}$.
**Proof.** Write $\Phi = \Phi_\alpha$ and $R = R_\alpha$. In this proof, we need to go back to the definition of $S_{\Phi,R^{op}}$ given in Section 2 of [4]. First recall that evaluation at $\Phi$ has a left adjoint

$$ \mathcal{A}_{\Phi} - \mathrm{Mod} \longrightarrow \mathcal{F}_k, \quad W \mapsto L_{\Phi,W} $$

defined by $L_{\Phi,W} = k\mathcal{C}(-, \Phi) \otimes_{\mathcal{A}_{\Phi}} W$, where $\mathcal{C}(X, \Phi)$ denotes the set of all correspondences between $X$ and $\Phi$ and $k\mathcal{C}(X, \Phi)$ is the free $k$-module with basis $\mathcal{C}(X, \Phi)$. Moreover, $L_{\Phi,W}$ has a unique subfunctor $J_{\Phi,W}$ which is maximal with respect to the condition that it vanishes at $\Phi$. The fundamental functor $S_{\Phi,R^{op}}$ is defined by

$$ S_{\Phi,R^{op}} := L_{\Phi,M}/J_{\Phi,M}, $$

where $M := M_{\Phi,R^{op}}$ is the fundamental $\mathcal{A}_{\Phi}$-module defined by (9.2). We refer to Section 2 of [4] for more details.

By Theorem 9.3, there is an isomorphism $S_\alpha(\Phi) \cong M$ and the adjunction property implies that there is a corresponding morphism

$$ \pi : L_{\Phi,M} \longrightarrow S_{\alpha} $$

which is an isomorphism on evaluation at $\Phi$. Therefore $\mathrm{Ker}(\pi)$ vanishes at $\Phi$, so that $\mathrm{Ker}(\pi) \subseteq J_{\Phi,M}$ by the property of $J_{\Phi,M}$. It follows that there is a surjective morphism

$$ \mathrm{Im}(\pi) \cong L_{\Phi,M} / \mathrm{Ker}(\pi) \longrightarrow L_{\Phi,M} / J_{\Phi,M} = S_{\Phi,R^{op}}. $$

Since $\mathrm{Im}(\pi) \subseteq S_\alpha$, we see that $S_{\Phi,R^{op}}$ is isomorphic to a subquotient of $S_\alpha$. $\square$

In the proof above, the morphism $\pi$ is not necessarily surjective, so that $S_{\Phi,R^{op}}$ may not be a quotient of $S_\alpha$, but only a subquotient. This can be seen by taking the special case $S_\alpha = F_T$ and $\Phi = \emptyset$, as in Example 8.4. In that case, $L_{\Phi,M}$ is the constant functor with values $k$ and $\pi(L_{\Phi,M})$ is the unique constant subfunctor of $F_T$, which is not the whole of $F_T$ as soon as $|T| \ge 2$. However, this example is slightly misleading, because the constant functor does appear as a quotient of $F_T$, but in a different way.

## 10. A comparison theorem

Every functor $S_\alpha$ is a quotient of $F_T$ which is in turn of the form $S_{\bar{\alpha}}$ for a suitable $\bar{\alpha}$, by Example 8.4. It is a natural question to ask more generally if one can compare functors by means of a surjective morphism. We prove here that this is indeed the case under very simple assumptions. The result will be used in an essential way in a future paper, but it is also of independent interest.

**10.1. Theorem.** Let $\alpha_1 : T \to T_1^{\prime op}$ and $\alpha_2 : T \to T_2^{\prime op}$ be two join-morphisms of finite lattices. Suppose that $\Phi_{\alpha_1} = \Phi_{\alpha_2}$ and $G_{\alpha_1} \subseteq G_{\alpha_2}$. Then $K_{\alpha_2} \subseteq K_{\alpha_1}$, and this induces a surjective morphism $S_{\alpha_2} \longrightarrow S_{\alpha_1}$.
**Proof.** Let $X$ be a finite set. We set $\Phi = \Phi_{\alpha_1} = \Phi_{\alpha_2}$ and we introduce, as in Section 6,

$$ \mathcal{B}_{\alpha_1, X} = \{ \varphi \in T^X \mid \Phi \subseteq \varphi(X) \subseteq G_{\alpha_1} \}, $$

$$ \mathcal{B}_{\alpha_2, X} = \{ \varphi \in T^X \mid \Phi \subseteq \varphi(X) \subseteq G_{\alpha_2} \}. $$

We will show that $F_T(X) = k\mathcal{B}_{\alpha_2, X} + (K_{\alpha_1}(X) \cap K_{\alpha_2}(X))$ by a method similar to the proof of Theorem 6.1. For simplicity, we write

$$ V := k\mathcal{B}_{\alpha_2, X} + (K_{\alpha_1}(X) \cap K_{\alpha_2}(X)) $$

and we aim to prove that $V = F_T(X)$. We choose $\varphi : X \to T$, and we will prove that $\varphi \in V$ by induction on $n_\varphi = |\varphi(X) - G_{\alpha_2}|$.

If $\Phi \not\subseteq \varphi(X)$, then $\varphi \in K_{\alpha_1}(X)$ by Lemma 9.1, and similarly $\varphi \in K_{\alpha_2}(X)$, hence $\varphi \in V$. So we can assume that $\Phi \subseteq \varphi(X)$. If $n_\varphi = 0$, then $\varphi(X) \subseteq G_{\alpha_2}$, so $\varphi \in \mathcal{B}_{\alpha_2, X}$ and $\varphi \in V$. Thus we assume that $n_\varphi \ge 1$.

For $i = 1, 2$, let $\theta_i = \beta_i^\sharp \alpha_i^\sharp$, as in Notation 4.6. It follows from the assumption that $G_{\alpha_1} - \Phi \subseteq G_{\alpha_2} - \Phi$, in other words $\mathrm{Im}(\theta_1) \subseteq \mathrm{Im}(\theta_2)$ (see Notation 5.1). Then $\theta_2 \circ \theta_1 = \theta_1$, as $\theta_2$ acts as the identity on $\mathrm{Im}(\theta_2)$. For any $a \in T - G_{\alpha_2} \subseteq T - G_{\alpha_1}$, we have $a < \theta_1(a)$ by Lemma 4.8 and the fact that $\mathrm{Im}(\theta_1) \subseteq G_{\alpha_1}$. Similarly $a < \theta_2(a)$. Since $\theta_2$ is order preserving, we obtain $a < \theta_2(a) \le \theta_2\theta_1(a) = \theta_1(a)$. Applying $\theta_1$, it follows that $\theta_1(a) \le \theta_1\theta_2(a) \le \theta_1(a)$, hence $\theta_1\theta_2(a) = \theta_1(a)$.

Since $n_\varphi \ge 1$, we can choose an element $a \in \varphi(X) - G_{\alpha_2}$. We set $b = \theta_2(a)$ and $c = \theta_1(a)$, so that $a < b \le c$ and $\theta_1(b) = c$. We consider the reduction sequence

$$ a < u_0 < u_1 < \dots < u_{h-1} < b $$

associated to $a$ for the morphism $\alpha_2 : T \to T_2'^{\mathrm{op}}$ (see Definition 5.3). Recall that

$$ \{a < u_0 < u_1 < \dots < u_{h-1} < b\} = \{a, b\} \sqcup ([a, b] \cap \Phi), $$

by Proposition 4.9. Similarly, we have $a \notin G_{\alpha_1}$ and we can consider the reduction sequence

$$ \{a < v_0 < v_1 < \dots < v_{l-1} < c\} = \{a, c\} \sqcup ([a, c] \cap \Phi) $$

associated to $a$ for the morphism $\alpha_1 : T \to T_1'^{\mathrm{op}}$. If $b = c$, then both reduction sequences coincide. If $b < c$, then the obvious equality $([a, c] \cap \Phi) \cap [a, b] = [a, b] \cap \Phi$ implies that the set $\{a < u_0 < u_1 < \dots < u_{h-1}\}$ is equal to the intersection with $[a, b]$ of the second reduction sequence. Thus $h \le l$, and $u_i = v_i$ for $0 \le i \le h-1$.

Now we claim that $b < v_h$ (provided $h < l$, hence in particular $l \ge 1$). In the case $h > 0$, we have $v_{h-1} < v_h$ and both are in $\Phi$. Therefore

$$ \alpha_2(v_h) < \alpha_2(v_{h-1}) = \alpha_2\beta_2 r^{h-1} \alpha_2(a) = r^{h-1} \alpha_2(a), $$
hence $\alpha_2(v_h) \le rr^{h-1}\alpha_2(a) = r^h\alpha_2(a)$. The same inequality holds if $h=0$ because $a < v_0$ implies $\alpha_2(v_0) \le \alpha_2(a)$. For any $h$, recall that $\alpha_2(b) = r^h\alpha_2(a)$ by Proposition 4.9(f). Therefore $\alpha_2(v_h) \le \alpha_2(b)$, hence $b \le \beta_2\alpha_2(b) \le \beta_2\alpha_2(v_h) = v_h$. But $b \ne v_h$ because $b \notin \Phi$ and $v_h \in \Phi$, so we get $b < v_h$, as claimed.

We have now obtained

$$a < v_0 < v_1 < \dots < v_{h-1} < b < v_h < \dots < v_{l-1} < c.$$

Recall that we may have $h=0$ (and the first part of the sequence is just $a < b$) and we may also have $h=l$ (and the second part of the sequence is either $b < c$ or $b=c$).

First assume that $b \in G_{\alpha_1}$, or equivalently $b=c$ (hence in particular $h=l$). Then both reduction sequences coincide and we write $v_h=b$. By Lemma 5.4, the element

$$w = \varphi + \sum_{k=0}^{h} (-1)^{k+1} [a, v_0, \dots, v_k] \varphi$$

belongs to both $K_{\alpha_1}(X)$ and $K_{\alpha_2}(X)$, hence $w \in V$. Moreover each function $\varphi_k = [a, v_0, \dots, v_k]\varphi$ satisfies $n_{\varphi_k} = n_{\varphi} - 1$ for $0 \le k \le h$, because $a \in \text{Im}(\varphi)$ but $a \notin \text{Im}(\varphi_k)$. So $\varphi_k \in V$ by induction, hence $\varphi = w + \sum_{k=0}^{h} (-1)^k \varphi_k$ also belongs to $V$, as was to be shown.

From now on, we assume that $b \notin G_{\alpha_1}$, that is, $b < c$. With the notation of Lemma 5.4, we define

$$\varphi_k = [a, v_0, \dots, v_k]\varphi \quad (0 \le k \le l-1)$$

$$\varphi' = [a, v_0, \dots, v_{h-1}, b]\varphi$$

$$\varphi_l = [a, v_0, \dots, v_{l-1}, c]\varphi$$

Using the reduction sequence $a < v_0 < \dots < v_{h-1} < b$ for the morphism $\alpha_2$, we see that the element

$$w := \varphi + \sum_{k=0}^{h-1} (-1)^{k+1} \varphi_k + (-1)^{h+1} \varphi' \quad (10.2)$$

belongs to $K_{\alpha_2}(X)$, by Lemma 5.4. Our main goal is to prove that it also belongs to $K_{\alpha_1}(X)$.

Since $c = \theta_1(b)$, the sequence $b < v_h < \dots < v_{l-1} < c$ is a reduction sequence for the morphism $\alpha_1$ and we set $v_l=c$ for convenience. By Lemma 5.4, we see that

$$\text{for any map } \psi \in T^X, \quad \psi + \sum_{i=h}^{l} (-1)^{i-h+1} [b, v_h, \dots, v_i] \psi \in K_{\alpha_1}(X). \quad (10.3)$$

We first apply (10.3) to each function $\varphi_k$ and take the alternating sum over $k$, for $h \le k \le l$. We obtain that the expression
$$ \sum_{k=h}^{l} (-1)^k \varphi_k - \sum_{k=h}^{l} (-1)^k [b, v_h] \varphi_k + \sum_{k=h}^{l} \sum_{i=h+1}^{l} (-1)^{k+i-h+1} [b, v_h, \dots, v_i] \varphi_k \quad (10.4) $$

belongs to $K_{\alpha_1}(X)$. We separate the first two sums on purpose, because we need to analyse the remaining double sum. This double sum runs over the rectangle

$$ P = \{(k, i) \mid h \le k \le l, h + 1 \le i \le l\} $$

of size $m \times (m-1)$, where $m = l - h + 1$. We can decompose $P$ as the disjoint union of the two subsets

$$ P_+ = \{(k, i) \in P \mid k < i\} \quad \text{and} \quad P_- = \{(k, i) \in P \mid k \ge i\}. $$

It is elementary to check that the map $(k, i) \mapsto (i, k+1)$ is a bijection between $P_+$ and $P_-$ with inverse $(r, s) \mapsto (s-1, r)$. We now show that, for any $(k, i) \in P_+$, the map $[b, v_h, \dots, v_i] \varphi_k$, indexed by $(k, i)$, is equal to the map $[b, v_h, \dots, v_{k+1}] \varphi_i$, indexed by $(i, k+1)$. In view of the definition of $\varphi_k$, we must prove that

$$ [b, v_h, \dots, v_i][a, v_0, \dots, v_k] = [b, v_h, \dots, v_{k+1}][a, v_0, \dots, v_i]. $$

But this is easy since both maps have the following effect (setting $v_{-1} = a$ for convenience):

$$ \begin{array}{ll} v_r \mapsto v_{r+1} & \text{if } -1 \le r \le h-2 \\ v_r \mapsto v_{r+2} & \text{if } h-1 \le r \le k-1 \\ v_r \mapsto v_{r+1} & \text{if } k \le r \le i-1 \\ v_r \mapsto v_r & \text{if } i \le r \le l \\ b \mapsto v_h & \\ t \mapsto t & \text{otherwise.} \end{array} $$

In the double sum appearing in (10.4), opposite signs are assigned to the two maps, so the pair vanishes. This applies to all pairs and therefore the whole double sum is zero. It follows that (10.4) reduces to

$$ \sum_{k=h}^{l} (-1)^k \varphi_k - \sum_{k=h}^{l} (-1)^k [b, v_h] \varphi_k \in K_{\alpha_1}(X). \quad (10.5) $$

We now apply (10.3) to the function $\varphi' = [a, v_0, \dots, v_{h-1}, b] \varphi$ and we get

$$ \varphi' + \sum_{k=h}^{l} (-1)^{k-h+1} [b, v_h, \dots, v_k] [a, v_0, \dots, v_{h-1}, b] \varphi \in K_{\alpha_1}(X). \quad (10.6) $$
But it is elementary to check that

$$[b, v_h, \dots, v_k][a, v_0, \dots, v_{h-1}, b]\varphi = [b, v_h][a, v_0, \dots, v_k]\varphi = [b, v_h]\varphi_k.$$

So if we multiply (10.6) by $(-1)^{h-1}$ and add it to (10.5), all the functions $[b, v_h]\varphi_k$ cancel and we obtain

$$(-1)^{h-1}\varphi' + \sum_{k=h}^{l} (-1)^k \varphi_k \in K_{\alpha_1}(X). \qquad (10.7)$$

Next we use the long reduction sequence $a < v_0 < \dots < v_h < v_{h+1} < \dots < v_{l-1} < c$ for the morphism $\alpha_1$ and we set $v_l = c$ for convenience. By Lemma 5.4, we have

$$\varphi + \sum_{k=0}^{l} (-1)^{k+1} \varphi_k \in K_{\alpha_1}(X)$$

and if we add this to (10.7), all the terms with indices $k \ge h$ cancel and we are left with

$$w = \varphi + \sum_{k=0}^{h-1} (-1)^{k+1} \varphi_k + (-1)^{h-1} \varphi' \in K_{\alpha_1}(X).$$

But this is precisely the element $w$ defined in (10.2), which also belongs to $K_{\alpha_2}(X)$. Therefore $w \in K_{\alpha_1}(X) \cap K_{\alpha_2}(X)$, hence $w \in V$.

We then proceed as we did earlier in the case $b = c$. We have $n_{\varphi_k} = n_{\varphi} - 1$ for $0 \le k \le h-1$, and $n_{\varphi'} = n_{\varphi} - 1$ as well. So $\varphi_k, \varphi' \in V$ by induction, hence

$$\varphi = w + \sum_{k=0}^{h-1} (-1)^k \varphi_k + (-1)^h \varphi' \in V.$$

This completes the proof of the equality $F_T(X) = k\mathcal{B}_{\alpha_2, X} + (K_{\alpha_1}(X) \cap K_{\alpha_2}(X))$.

Finally, we can finish the proof of Theorem 10.1. We have

$$K_{\alpha_1}(X) \cap K_{\alpha_2}(X) \subseteq K_{\alpha_2}(X) \subseteq k\mathcal{B}_{\alpha_2, X} + (K_{\alpha_1}(X) \cap K_{\alpha_2}(X)).$$

It follows that

$$K_{\alpha_2}(X) = (K_{\alpha_1}(X) \cap K_{\alpha_2}(X)) + (k\mathcal{B}_{\alpha_2, X} \cap K_{\alpha_2}(X)),$$

hence $K_{\alpha_2}(X) = K_{\alpha_1}(X) \cap K_{\alpha_2}(X)$ since $k\mathcal{B}_{\alpha_2, X} \cap K_{\alpha_2}(X) = \{0\}$ by Theorem 6.1. Thus $K_{\alpha_2}(X) \subseteq K_{\alpha_1}(X)$ and the proof is complete. $\square$
## 11. The structure of the poset $G_\alpha$

Given a join-morphism $\alpha : T \to T'^{op}$ of finite lattices, we have defined the subset $G_\alpha \subseteq T$, which is used in Section 6 for the description of a basis of each evaluation $S_\alpha(X)$. Dually, $G'_\alpha$ is a subset of $T'$, used similarly for a description of a basis of each evaluation $S'_\alpha(X)$. Note that $S'_\alpha$ is isomorphic to the dual $S_\alpha^\sharp$, by Proposition 6.9, but this does not tell us directly how $G_\alpha$ and $G'_\alpha$ are related. The purpose of this section is to show that $G_\alpha$ and $G'_\alpha$, viewed as full subposets of $T$ and $T'$ respectively, are actually anti-isomorphic.

We know from Lemma 4.11(a) that $\alpha^\sharp$ restricts to an anti-isomorphism of posets from $\text{Im}(\theta)$ to $\text{Im}(\theta')$. Since $G_\alpha - \Phi_\alpha = \text{Im}(\theta)$, we see that we now have two poset anti-isomorphisms

$$ \alpha^{\sharp} : G_{\alpha} - \Phi_{\alpha} \to G'_{\alpha} - \Phi'_{\alpha} \quad \text{and} \quad \alpha : \Phi_{\alpha} \to \Phi'_{\alpha}. $$

The disjoint union of the two maps yields a bijection $G_\alpha \to G'_\alpha$, but unfortunately, this bijection is not an anti-isomorphism. Our final theorem shows that the correct anti-isomorphism is more subtle. We start with a lemma.

**11.1. Lemma.** Let $\alpha : T \to T'^{op}$ be a join-morphism of finite lattices, let $\beta = \alpha^{op}$, and let $Z_\alpha := \{u \in \Phi_\alpha | \rho(u) \in G_\alpha \text{ and } u \le \omega\rho(u)\}$. Then $Z_\alpha = \bigsqcup_{t \in \text{Im}(\theta)} ]t, \omega(t)]$. □

**Proof.** If $u \in Z_\alpha$, then $t = \rho(u) \in G_\alpha - \Phi_\alpha = \text{Im}(\theta)$, and $t < u \le \omega(t)$ by the definition of $Z_\alpha$. Thus $u \in ]t, \omega(t)]$. Conversely, if $u \in ]t, \omega(t)]$ for some $t \in \text{Im}(\theta)$, then $u \in \Phi_\alpha$ because $]t, \omega(t)] \subseteq \Phi_\alpha$ by Lemma 4.8. Moreover $t = \rho(u)$ and $\omega(t) = \omega(u)$ by Lemma 4.11. This shows that $u \in Z_\alpha$. Moreover, we see that $t$ and $\omega(t)$ are determined by $u$, so that the sets $]t, \omega(t)]$ are disjoint (possibly empty) when $t$ runs over $\text{Im}(\theta)$. □

Note that $]t, \omega(t)]$ is empty if $t = \omega(t)$, so the disjoint union actually runs over the subset $\hat{G} = \{t \in \text{Im}(\theta) | t < \omega(t)\}$, which already appeared in the proof of Theorem 6.1.

**11.2. Theorem.** Let $\alpha : T \to T'^{op}$ be a join-morphism of finite lattices, let $\beta = \alpha^{op}$, and let $Z_\alpha$ be as above. Let $\lambda_\alpha : G_\alpha \to T'$ be the map defined by

$$ \lambda_{\alpha}(u) = \begin{cases} \alpha(u) & \text{if } u \in G_{\alpha} - Z_{\alpha}, \\ r\alpha(u) & \text{if } u \in Z_{\alpha}. \end{cases} $$

Then $\lambda_\alpha(G_\alpha) = G'_\alpha$ and $\lambda_\alpha : G_\alpha \to G'_\alpha$ is an anti-isomorphism of posets, with inverse $\lambda_\beta : G_\beta = G'_\alpha \to G'_\beta = G_\alpha$.

**Proof.** We first prove that $\lambda_\alpha(G_\alpha) \subseteq G'_\alpha$. Let $u \in G_\alpha$. If $u \notin Z_\alpha$, then $\lambda_\alpha(u) = \alpha(u)$. But we know that $\alpha(T) \subseteq G'_\alpha$ by Lemma 5.2, so $\lambda_\alpha(u) \in G'_\alpha$ in this case. If $u \in Z_\alpha$,
we let $t = \rho(u) \in G_\alpha - \Phi_\alpha$, and $t' = \alpha^\sharp(t)$. In this case $\lambda_\alpha(u) = r\alpha(u)$. Moreover $t < u \le \omega(t)$ and, by Lemma 4.11, we deduce that $t' < \alpha(u) \le \alpha(t)$. If $r\alpha(u) \in \Phi'_\alpha$, then $r\alpha(u) \in G'_\alpha$, that is, $\lambda_\alpha(u) \in G'_\alpha$ and we are done. Otherwise $r\alpha(u) \notin \Phi'_\alpha$, hence $r\alpha(u) = \alpha^\sharp(u) = \alpha^\sharp(t) = t'$ by the definition of $\alpha^\sharp$. Then $\theta'(r\alpha(u)) = \alpha^\sharp\beta^\sharp\alpha^\sharp(t) = \alpha^\sharp(t)$ by Lemma 4.8, since $t \notin \Phi_\alpha$. Thus $\lambda_\alpha(u) = r\alpha(u) = \alpha^\sharp(t) \in \operatorname{Im}(\theta') \subseteq G'_\alpha$.

We show next that $\lambda_\alpha$ is order-reversing. For this, we consider elements $u < v$ in $G_\alpha$, and we want to show that $\lambda_\alpha(u) \ge \lambda_\alpha(v)$. The first 3 cases are easy:

* If $u \notin Z_\alpha$ and $v \notin Z_\alpha$, then $\lambda_\alpha(u) = \alpha(u) \ge \alpha(v) = \lambda_\alpha(v)$.

* If $u \notin Z_\alpha$ and $v \in Z_\alpha$, then $\lambda_\alpha(u) = \alpha(u) \ge \alpha(v) > r\alpha(v) = \lambda_\alpha(v)$.

* If $u \in Z_\alpha$ and $v \in Z_\alpha$, then $\lambda_\alpha(u) = r\alpha(u) \ge r\alpha(v) = \lambda_\alpha(v)$.

In the fourth case, we have $u \in Z_\alpha$ and $v \notin Z_\alpha$, hence $\lambda_\alpha(u) = r\alpha(u)$ and $\lambda_\alpha(v) = \alpha(v)$. We set $t = \rho(u)$ and observe that we still have $\alpha(u) \ge \alpha(v)$. Assume that $\alpha(u) = \alpha(v)$. If $v \in \Phi_\alpha$, then $u = v$ by Lemma 3.6, contradicting the assumption $u < v$. Thus $v \in G_\alpha - \Phi_\alpha = \operatorname{Im}(\theta)$. Since $u \in Z_\alpha$, Lemma 11.1 implies that $u \in ]t, \omega(t)]$ where $t = \rho(u) \in \operatorname{Im}(\theta)$. By Lemma 4.11, $\alpha$ induces an anti-isomorphism between $]t, \omega(t)]$ and $]t', \omega'(t')]$, where $t' = \alpha^\sharp(t)$ and $\omega'(t') = \alpha(t)$. We deduce that $\alpha(v) = \alpha(u) \in ]\alpha^\sharp(t), \alpha(t)]$, hence $\alpha^\sharp(v) = \alpha^\sharp(t)$ because $\alpha^\sharp(v) = \rho'\alpha(v) = t'$ by Lemma 4.11 again. Since $v, t \in \operatorname{Im}(\theta)$, they are fixed under $\theta$, by Lemma 4.8, and therefore

$$v = \theta(v) = \beta^{\sharp} \alpha^{\sharp}(v) = \beta^{\sharp} \alpha^{\sharp}(t) = \theta(t) = t,$$

hence $v = t < u$, contradicting the assumption $u < v$. This contradiction shows that $\alpha(u) \ne \alpha(v)$, hence $\alpha(u) > \alpha(v)$, and it follows that $\lambda_\alpha(u) = r\alpha(u) \ge \alpha(v) = \lambda_\alpha(v)$.

Our next step is to show that $\lambda_\beta\lambda_\alpha = \operatorname{id}_{G_\alpha}$. We have

$$G_\alpha = (G_\alpha - \Phi_\alpha) \sqcup (\Phi_\alpha - Z_\alpha) \sqcup Z_\alpha$$

and we consider successively an element in each of those 3 subsets. We start with $t \in G_\alpha - \Phi_\alpha$, that is, $t = \theta(t)$. Applying Proposition 4.9, we see that only cases (a) or (d) of that Proposition can occur, because either $t < \theta(t)$ or $\theta(t) < t$ holds in the other cases. In case (a), we have $t = \theta(t) = \beta\alpha(t) \notin \Phi_\alpha$ and $\alpha(t) \notin \Phi'_\alpha$, hence $t \notin Z_\alpha$ and $\alpha(t) \notin Z'_\alpha$, where

$$Z'_\alpha := \{u \in \Phi'_\alpha | \rho'(u) \in G'_\alpha \text{ and } u \le \omega'\rho'(u)\}.$$

Thus we get $\lambda_\beta\lambda_\alpha(t) = \lambda_\beta\alpha(t) = \beta\alpha(t) = t$. In case (d), we have $t \notin \Phi_\alpha$ and

$$t = \theta(t) < v_0 < \dots < v_{l-1} = \omega(t), \quad \text{where } v_i = \beta r^i \alpha(t) \in \Phi_\alpha,$$

and $l \ge 1$. By Lemma 4.11(c), $]t, \omega(t)]$ is anti-isomorphic to $]t', \omega'(t')]$, which is contained in $Z'_\alpha$ by Lemma 11.1. In particular $\alpha(t) = \omega'(t') \in Z'_\alpha$, while $t \notin Z_\alpha$, so we obtain
$$ \lambda_{\beta}\lambda_{\alpha}(t) = \lambda_{\beta}\alpha(t) = r\beta\alpha(t) = r(v_0) = t, $$

because $v_0$ is the least element of the totally ordered interval $]t, \omega(t)]$, by Lemma 4.8, and so $r(v_0) = t$.

We consider now our second subset and take $t \in \Phi_{\alpha} - Z_{\alpha}$. We claim that $\alpha(t) \notin Z'_{\alpha}$. If not, then, by Lemma 11.1, we would have $\alpha(t) \in ]s', \omega'(s')[$, where $s' = \rho'\alpha(t) = \alpha^{\sharp}(t)$ and $s' \in \text{Im}(\theta')$. By Lemma 4.11, $\beta$ induces an anti-isomorphism between $]s', \omega'(s')[$ and $]s, \omega(s)]$, where $s = \beta^{\sharp}(s') \in \text{Im}(\theta)$. Therefore we would obtain $\beta\alpha(t) \in ]s, \omega(s)]$, hence $\beta\alpha(t) \in Z_{\alpha}$. But $\beta\alpha(t) = t$ because $t \in \Phi_{\alpha}$. Since we have chosen $t \notin Z_{\alpha}$, this proves the claim. Now, the definition of $\lambda_{\beta}$ implies that $\lambda_{\beta}\lambda_{\alpha}(t) = \lambda_{\beta}\alpha(t) = \beta\alpha(t) = t$.

Finally, for our third subset, we take $u \in Z_{\alpha}$ and we let $t = \rho(u)$ and $t' = \alpha^{\sharp}(t)$, so that $u \in ]t, \omega(t)]$. By Lemma 4.11 again, $\alpha$ induces an anti-isomorphism $]t, \omega(t)] \to ]t', \omega'(t')[$. We have $\lambda_{\alpha}(u) = r\alpha(u) \in [t', \omega'(t')[$, and there are two cases. If $r\alpha(u) = t'$, then $r\alpha(u) \notin Z'_{\alpha}$ and so $\lambda_{\beta}\lambda_{\alpha}(u) = \beta r\alpha(u) = \beta(t') = \omega(t)$. But since $r\alpha(u) = t'$, the element $\alpha(u)$ is the smallest element of the totally ordered interval $]t', \omega'(t')[$, so that $u$ is the top element of $]t, \omega(t)]$, that is, $u = \omega(t)$. Hence $\lambda_{\beta}\lambda_{\alpha}(u) = u$ in this case. In the other case, we have $v := r\alpha(u) > t'$, hence $v \in ]t', \omega'(t')[$. Then $v$ and $\alpha(u)$ are adjacent in this totally ordered interval. Since the inverse anti-isomorphism $]t', \omega'(t')] \to ]t, \omega(t)]$ is induced by $\beta$, the elements $u$ and $\beta(v)$ are adjacent in the totally ordered interval $]t, \omega(t)]$, that is, $u = r\beta(v)$. It follows that

$$ \lambda_{\beta}\lambda_{\alpha}(u) = \lambda_{\beta}r\alpha(u) = \lambda_{\beta}(v) = r\beta(v) = u. $$

This completes the proof that $\lambda_{\beta}\lambda_{\alpha} = \text{id}_{G_{\alpha}}$. $\square$

## Data availability

No data was used for the research described in the article.

## References

[1] S. Bouc, Foncteurs d'ensembles munis d'une double action, J. Algebra 183 (1996) 664–736.

[2] S. Bouc, J. Thévenaz, The algebra of essential relations on a finite set, J. Reine Angew. Math. 712 (2016) 225–250.

[3] S. Bouc, J. Thévenaz, Correspondence functors and finiteness conditions, J. Algebra 495 (2018) 150–198.

[4] S. Bouc, J. Thévenaz, Correspondence functors and lattices, J. Algebra 518 (2019) 453–518.

[5] S. Bouc, J. Thévenaz, The algebra of Boolean matrices, correspondence functors, and simplicity, J. Comb. Algebra 4 (2020) 215–267.

[6] S. Bouc, J. Thévenaz, Tensor product of correspondence functors, J. Algebra 558 (2020) 146–175.

[7] S. Bouc, J. Thévenaz, Simple and projective correspondence functors, Represent. Theory 25 (2021) 224–264.

[8] V. Franjou, A. Touzé (Eds.), Lectures on Contractor Homology, Lectures from the Conference Held in Nantes, April 2012, Progress in Mathematics, vol. 311, Birkhäuser/Springer, Cham, 2015.

[9] R. Nagpal, S.V. Sam, A. Snowden, Regularity of FI-modules and local cohomology, Proc. Am. Math. Soc. 146 (2018) 4117–4126.

[10] S. Roman, Lattices and Ordered Sets, Springer, New York, 2008.
[11] S.V. Sam, A. Snowden, Gröbner methods for representations of combinatorial categories, J. Am. Math. Soc. 30 (2017) 159–203.

[12] E.H. Spanier, J.H.C. Whitehead, Duality in relative homotopy theory, Ann. Math. (2) 67 (1958) 203–238.

[13] P. Webb, An introduction to the representations and cohomology of categories, in: M. Geck, D. Testerman, J. Thévenaz (Eds.), Group Representation Theory, EPFL Press, Lausanne, 2007, pp. 149–173.

[14] P. Webb, Sets with a category action, Oberwolfach Rep. 7 (3) (2010) 1940–1945, https://doi.org/10.4171/OWR/2010/32.

[15] J.H.C. Whitehead, Duality between CW-lattices, in: Symposium Internacional de Topología Algebraica, Universidad Nacional Autónoma de México and UNESCO, Mexico City, 1958, pp. 248–258.