OPTIMAL NATURAL DUALITIES FOR SOME

QUASIVARIETIES OF DISTRIBUTIVE DOUBLE p–ALGEBRAS

M. J. SARAMAGO

Abstract. Quasivarieties of distributive doublep-algebras generated by an ordinal
sumM of two Boolean lattices are considered. Globally minimal failsets within
S(M^{2}) are completely determined; from them all the optimal dualities for these
quasivarieties are obtained.

1. Introduction

This paper concerns natural duality theory, as developed in [3] and [1]. The objective of this theory is to find a concrete representation, as a set of functions, of each algebra in a given quasivarietyA=ISP(M), whereMis a finite algebra. Such representations have been obtained for a considerable number of quasivarieties, in particular of varieties of algebras having a lattice reduct, and it is of interest, and of practical importance to the study of such varieties, to find workable dualities.

Given a quasivarietyA=ISP(M) of algebras generated by a finite algebraM,
let R be a set of algebraic relations onM, i.e., a set of relations on M such
that each of them is the underlying set of a subalgebra of a power of M. Define
M∼ := (M;R, τ) to be the topological relational structure on the underlying set
M of M in which τ is the discrete topology. Given M∼, we define the category
X :=IS_{c}P(M∼) in which objects are all isomorphic copies of closed substructures
of powers ofM∼ and in which morphisms are the continuousR-preserving maps. Let
D and E be the natural hom functors A(−, M):A → X and X(−, M∼):X → A
respectively. The setR yields a duality onA ifA is isomorphic to its second
dual ED(A), for every A ∈ A (see [6], [3], [1] for further details). Even when
the dualising setR is finite there are cases where Ris extremely large. This can
occurs, for example, when R can be taken to be S(M^{2}) as it is the case of M
having a lattice reduct. In these cases it would be useful to know whether such a

Received September 7, 1997; revised June 6, 1998.

1980Mathematics Subject Classification(1991Revision). Primary 06D15, 08C15.

Key words and phrases. Distributive double p-algebra, failset, natural duality, optimal duality.

This work was supported by a grant from JNICT. The author is a member of Centro de Algebra da Universidade de Lisboa and of Projecto Praxis nr. Praxis/2/2.1/MAT/73/94 and´ would also like to thank the Mathematical Institute, University of Oxford, for its hospitality.

duality isoptimalin the sense that no proper subset ofRyields a duality. In [5]

B. A. Davey and H. A. Priestley present a general theory of optimal dualities. For a given finite dualising set Ω of finitary algebraic relations onM, they prove that the subsetsR of Ω which yield optimal dualities are precisely the transversals of the globally minimal failsets in Ω, as defined at the beginning of Section 4. By a failsetwe mean a set of the form

Failr(u) :={s∈Ω|udoes not preserves};

herer ranges over Ω and u over the set of maps from D(r) to M which do not preserver. Theglobally minimal failsetsare those failsets which are minimal with respect to set inclusion.

Here we have a dual motivation. Our first aim is to obtain optimal dualities for the varieties under consideration. The second, and potentially the more important, is to use these varieties to explore the structure of globally minimal failsets in a non-trivial case, and so to gain a better understanding of the general theory. At the same time we present some techniques which can be used to determine failsets.

In our examples Ω = S(M^{2}), and so Ω includes in particular the graphs of the
(non-extendable) partial endomorphisms ofM. In general, failsets which do not
contain partial endomorphisms are easier to analyse than those that do. We are
able in our examples to describe certain globally minimal failsets containing as
minimal elements non-extendable partial endomorphisms ofM. In this work we
apply the theory to certain quasivarieties of distributive doublep-algebras. These
algebras have as reducts a pseudocomplemented distributive lattice and a dual
pseudocomplemented distributive lattice. In [5], B. A. Davey and H. A. Priestley
have already applied the theory to the quasivarietiesB_{n} of pseudocomplemented
distributive lattices.

For this work we have used some of the Pascal programs that B. A. Davey and H. A. Priestley have used for studying optimality in [5], and which have as a basis the backtracking algorithm presented in [8].

The author would like to thank to her supervisor, Dr. Hilary Priestley, for her help and encouragement.

2. Preliminaries

An algebra A = (A;∨,∧,^{∗},0,1) of type (2,2,1,0,0) is a distributive
p-algebraif (A;∨,∧,0,1) is a bounded distributive lattice and^{∗}is a unary oper-
ation defined by

x∧a= 0 if and only ifx6a^{∗},
i.e.,x^{∗} is the pseudocomplement ofx.

An algebraA= (A;∨,∧,^{∗},^{+},0,1) of type (2,2,1,1,0,0) is adistributive dou-
ble p-algebraif (A;∨,∧,^{∗},0,1) is a distributivep-algebra and (A;∨,∧,^{+},0,1) is
a dual distributivep-algebra.

Form, n>1, letB_{m} and B_{n} be respectively the m-atom Boolean lattice and
then-atom Boolean lattice. Define P_{m,n} to be the distributive doublep-algebra
given by the ordinal sumBm⊕Bn. The unary operations^{∗} and^{+} are defined as
follows,

x^{∗}=

1 ifx= 0,

x^{0}_{B}_{m} ifx∈Bm, x6= 0,
0 ifx∈Bn

and x^{+}=

1 ifx∈Bm,
x^{0}_{B}_{n} ifx∈Bn, x6= 1,
0 ifx= 1,

wherex^{0}_{B}_{i} is the complement of x∈Bi, withi∈ {m, n}.

We denote byd1 andd2respectively the maximum ofB_{m}and the minimum of
B_{n} . Letπi,i∈ {1,2}, be the natural projection maps fromP^{2}_{m,n}toP_{m,n}. For a
given subalgebrarwe denoteπir byρi.

Let m, n >1 and letA =ISP(P_{m,n}) be the quasivariety generated byP_{m,n}.
Let Ω =S(P^{2}_{m,n}) be the set of all binary algebraic relations on P_{m,n}. For a given
subalgebrar ofP^{2}_{m,n}, we writer⊆P_{m,n}^{2} when we wish to think of ras a binary
relation andr6P^{2}_{m,n}when it is regarded as a subalgebra ofP^{2}_{m,n}.

In Section 3 we will need some elementary facts on the algebrasP_{m,n}which we
next collect together for future reference.

Proposition 2.1. Letr6P^{2}_{m,n}. Then one of the following cases must occur:

(a) (0,1),(1,0)∈r and thenris a product of subalgebras ofP_{m,n}.

(b) (0,1),(1,0)∈/ r and then r\{(d1, d2),(d2, d1)} is the graph of some one-
to-one homomorphismh:N 6P_{m,n}→P_{m,n}.

Proof. Note that (0,1)∈rif and only if (1,0)∈r. So either (1,0),(0,1)∈ror (1,0),(0,1)∈/r.

Suppose that (0,1),(1,0)∈r. For everya∈ρ1(r) andb∈ρ2(r), letc, d∈Pm,n

be such that (a, d),(c, b)∈r. Then we have that (a,1) = (a, d)∨(0,1) ∈ rand (1, b) = (c, b)∨(1,0) ∈ r, and consequently (a, b) = (a,1)∧(1, b)∈ r. Thus (a) holds.

Now consider (b). We claim that we only have (a,0)∈ r fora= 0. Suppose
that (a,0)∈r, witha6= 0. Since (a^{∗},1)∈rand (0,1)∈/r, we must have a < d1.
But then (d1,1) = (a,0)∨(a^{∗},1) ∈ r and so (1,0) = (d^{+}_{1},1^{+}) ∈ r, contrary to
hypothesis. By using the same argument we also prove that (0, a)∈rif and only
ifa= 0. Analogously, we prove that (a,1)∈r⇔a= 1 and (1, a)∈r⇔a= 1.

Let (a, b),(a, c) ∈ r. We have that (0, b^{∗}∧c),(0, b∧c^{∗}) ∈ r which implies that
b^{∗}∧c = 0 =b∧c^{∗} and consequentlyb^{∗} =c^{∗}. But thenb =c or d1 6b, c. We
also have that (1, b^{+}∨c),(1, b∨c^{+}) ∈r which implies b^{+} =c^{+}. Thus b = c or
b, c 6 d2. If b or c is in {d1, d2} then (a^{∗},0),(a^{+},1) ∈ r, and so a ∈ {d1, d2}
because a^{∗} = 0 and a^{+} = 1. We prove in a similar way that (b, a),(c, a) ∈ r
implies that (b =c or a, b, c ∈ {d1, d2}). At last observe that if (a, b) ∈ r then

(d1, d1)∈ r whenever 0 < a < d1, and (d2, d2)∈ r whenever d2 < a <1. Now
it follows that r\{(d1, d2),(d2, d1)} is a subalgebra of P^{2}_{m,n} and finally we have
that r\{(d1, d2),(d2, d1)} is the graph of a one-to-one (partial) endomorphism

ofP_{m,n}.

From this proposition it follows immediately the following result.

Corollary 2.2. The endomorphisms of P_{m,n} are exactly the automorphisms
of P_{m,n}.

Proposition 2.3.

(a) There exists a group isomorphism between AutP_{m,n} and Sm×Sn, the
direct product of the symmetric groupsSm andSn.

(b) Iff ∈AutP_{m,n}\{id}then there exists a maximal subgroupHofAutP_{m,n}
such thatf /∈H.

Proof. First observe that the group of automorphisms of a k-atom Boolean
lattice is isomorphic to the symmetric group Sk. Since the restrictions of the
automorphisms ofP_{m,n}to Bmand to Bn are respectively automorphisms ofB_{m}
andB_{n}, every automorphim ofP_{m,n}is uniquely determined by a permutation on
its atoms and by a permutation on its coatoms. Also, each automorphism ofBm

and each automorphism ofBn define an automorphismgofP_{m,n}. Now the claim
regarding (a) follows easily.

For (b) take the subgroupH ={g∈AutP_{m,n}|g(a) =a}of AutP_{m,n}, where
a ∈ P_{m,n} is such that f(a) 6= a and a is either an atom or a coatom of P_{m,n}.
Suppose without less of generality thatais an atom ofP_{m,n}and takea1, . . . , am

to be the atoms ofP_{m,n}such thata=a1. Then{σ∈Sm|σ(1) = 1} ×Sn is the
subgroup ofSm×Snthat corresponds toH. Since it is a maximal proper subgroup
ofSm×Sn, we have thatH is a maximal proper subgroup of AutP_{m,n}.
Leta∈P_{m,n}. A subalgebra N ofP_{m,n}is called avalueofP_{m,n} ataif N is
maximal with respect to not containinga. Denote by N_{d}_{1} andN_{d}_{2} the values of
P_{m,n}atd1andd2respectively. Observe thatNd1 is{0} ⊕BnandNd2 isBm⊕ {1}.
Given a partial endomorphism h of P_{m,n}, we have that h(di) ∈ {d1, d2}, for
di ∈domh, and sincehis one-to-one on domh\{d1, d2}, by Proposition 2.1, we
also have that h(domh∩Ndi) ⊆ Ndi whenever domh∩Ndi * {0, dj,1}, with
j ∈ {1,2}, j 6=i. Then we may observe easily that if the codomain of his Nd_{i},
fori∈ {1,2}, its domain is eitherNdi orNdi∪ {d1, d2}. Now the following result
follows immediately.

Proposition 2.4. Let i ∈ {1,2}. ThenD(N_{d}_{i}) is the set of automorphisms
of N_{d}_{i}.

For every subalgebraN ofP_{m,n}, we denote the set of atoms ofN and the set
of coatoms ofN by AtN and CoatN respectively.

Lemma 2.5. Let h be a partial endomorphism of P_{m,n} with d1, d2 ∈ domh
andh(d1) =d1,h(d2) =d2. Then his extendable if and only if

there is an atoma ofdomhsuch that neithera norh(a)is an atom ofP_{m,n},
or

there is a coatomc ofdomhsuch that neither c norh(c)is a coatom of P_{m,n}.
Proof. LetN = domh. Ifhis extendable then takeh^{0}:N^{0}6P_{m,n}→P_{m,n}to
be an extension ofh. As N is a proper subalgebra of N^{0} there exists a^{0} ∈AtN^{0}
such thata^{0}< a, for somea∈AtN, or there existsc^{0}∈CoatN^{0} such thatc < c^{0},
for some c ∈ CoatN. Suppose without loss of generality that there is such an
atom a^{0}. Since h^{0} is one-to-one, by Proposition 2.1, 0< h^{0}(a^{0})< h(a). But then
a ∈ AtN and a, h(a) ∈/ AtP_{m,n}. Conversely suppose without loss of generality
thata∈AtN and thata, h(a)∈/AtP_{m,n}. Then there area1, a2∈AtP_{m,n} such
thata1< aanda2< h(a). For everyx∈N, we havea16x⇔a6x⇔a26h(x)
becausea∈AtN andhis one-to-one. Take

s= graph(h)∪ {(a1, a2)∨(x, h(x)) | x∈N} ∪ {(a1∗

, a2∗

)∧(x, h(x)) | x∈N}.
It is not difficult to verify that s is the universe of a subalgebra ofP^{2}_{m,n}. Then
s= graph(h) for some one-to-one partial endomorphism hof P_{m,n}. But thenh

extendsh.

Lemma 2.6. Let N and Q be two maximal proper subalgebras of P_{m,n}. If
N and Qare isomorphic then there exists an automorphismg of P_{m,n} such that
g(N) =Q.

Proof. SinceN is a maximal proper subalgebra ofP_{m,n},N must contain either
Nd1 orNd2. Suppose without loss of generality thatNd1 ⊆N. Then bothN and
Qare isomorphic toPm−1,n. Leta1, . . . , ambe the atoms ofPm,n. Ifm= 2 then
N =Nd_{1}∪ {d1}=Q. If m >2 then there exist ai_{1}, ai_{2}, aj_{1}, aj_{2} ∈AtP_{m,n} such
thatai1 ∨ai2 and aj1∨aj2 are respectively the atoms of N and Q that are not
atoms ofP_{m,n}. Take ((i1j1)◦(i2j2),id)∈Sm×Sn and letgbe the corresponding
automorphism ofP_{m,n}. Then we have thatg(N) =Q.

Proposition 2.7. Let h: N → P_{m,n} be a non-extendable partial endomor-
phism. If either Nd1 ⊆N andN has m−1atoms, withm >2, or Nd2 ⊆N and
N has n−1coatoms, withn >2, then

(a) there existsg∈AutP_{m,n} such that h◦g◦his extendable;

(b) for every non-extendable partial endomorphism f: Q → P_{m,n} of P_{m,n},
whereQ is isomorphic toN, there exist g1, g2∈AutP_{m,n} such thatf =
g1◦h◦g2N.

Proof. Suppose thatNd1 ⊆N andN hasm−1 atoms, withm >2. We may assume that AtN ={a1, . . . , am−2, am−1∨am}, wherea1, . . . , am are the atoms

ofP_{m,n}. Sincehis one-to-one, by Proposition 2.1, andhis non-extendable, there
areai, aj, ai1, ai2 ∈AtP_{m,n}such thath(ai) =ai1∨ai2 andh(am−1∨am) =aj, by
applying Lemma 2.5. There existsσ∈Smsuch thatσ(i1) =m−1,σ(i2) =mand
σ(j) =i. Now (a) holds by taking the automorphismg of AutP_{m,n}determined
by (σ,id)∈Sm×Sn.

By Lemma 2.6, we only need to prove (b) for the caseQ=N. Letf:N→P_{m,n}
be a non-extendable partial endomorphism of P_{m,n}. By Lemma 2.5, there are
ai, aj ∈ N such that ai, aj ∈ AtP_{m,n} and, for some ai1, ai2, aj1, aj2 ∈ AtP_{m,n},
f(aj) =aj1 ∨aj2 andh(ai) =ai1∨ai2. Takeg2to be the automorphism of P_{m,n}
determined by ((i j),id)∈Sm×Sn. Letf^{0} =f ◦g2−1◦h^{−}^{1}, whereh^{−}^{1} denotes
the inverse of the isomorphism from N to h(N) given by h. Since h(ai) is the
only atom of h(N) which is not an atom of P_{m,n} and f^{0}(h(ai)) = f(aj), f^{0} is
extendable. Letg1∈AutP_{m,n} be an extension off^{0}. We haveg1◦h◦g2N=f.

In caseNd_{2} ⊆N andN hasn−1 coatoms, withn >2, the proof of the claim

is dual to this we have just done.

Recall that a subsetRof Ωentailsa relationr(in symbols,R`r) if, for every A ∈ A, every continuos mapϕ:D(A)→Pm,n which preserves every relation in R also preserves r. The map R 7→R :={r ∈Ω| R ` r}is a closure operator, referred as entailment closure (see [4] and [5] for further details). There are different ways of building relations from a subsetRof Ω in order that those new relations are entailed byR. In [4] the authors present a list of constructs sufficient to describe entailment. Next we present some of those constructs which we will need in Section 3.

Permutation. From a binary relation r, construct r^{`} = {(c, d) ∈ Pm,n^{2} |
(d, c)∈r}.

Intersection. From binary relationsrands, constructr∩s.

Domains. From a partial endomorphisme:N→P_{m,n}, construct the domain,
dome, ofe.

Joint kernels. From (partial) endomorphismse1:N_{1}→P_{m,n}ande2:N_{2}→
P_{m,n}, withN_{1}, N_{2}≤P_{m,n}, construct ker(e1, e2) :={(c1, c2)∈N1×N2|e1(c1) =
e2(c2)}.

Composition. From (partial) endomorphismse1:N_{1}→P_{m,n}ande2:N_{2}→
P_{m,n}, with N_{1}, N_{2} ≤ P_{m,n}, construct the composite (partial) endomorphism
e2◦e1with domain {c∈dome1|e1(c)∈dome2}.

Action by (partial) endomorphisms. From r ⊆ P^{2}_{m,n} and a (partial)
endomorphisme:N →P_{m,n}ofP_{m,n}, constructe·r:={(c, d)∈P_{m,n}^{2} |c∈Nand
(e(c), d)∈r}.

Letr∈Ω and let u:D(r)→Pm,n be any map. Define U = Failr(u) :={s∈Ω|ufails to preserves};

U is called a failset of r(within Ω) if it contains r. We say that U is afailset whenever it is a failset of some r ∈ U. Let u: D(r) → Pm,n is a map and x, y ∈D(r). Then we say that (x, y)witnessess∈Failr(u) if (x, y)∈sD(r) but (u(x), u(y))∈/s.

Proposition 2.8. For any mapu: D(r)→Pm,n, the complement ofFailr(u) inΩ is a closed set for entailment closure.

Proof. This follows from the definitions.

A failset U is said to be aminimal failset of r ifU is a minimal element of the set of all failsets of r ordered by inclusion. If U is minimal in the set of all failsets ordered by inclusion thenU is called aglobally minimal failset.

The following two results are Corollary 3.6 and part of Theorem 3.14 of [5].

Proposition 2.9. Lets∈Ω. LetU = Failr(u)be a failset containings. Then there is a minimal failsetUs of swithUs⊆U.

Theorem 2.10. Let∅ 6=U ⊆Ω. Then the following are equivalent:

(a) U is a globally minimal failset;

(b) U is a minimal failset ofr for allr∈U.

3. Globally Minimal Failsets inS(P^{2}_{m,n})

As in the preceding section, let Ω be S(P^{2}_{m,n}). It is known that Ω yields a
duality on A = ISP(P_{m,n}), once P_{m,n} has a lattice reduct (see [3] and [6]).

For a given (partial) endomorphism h of Pm,n, we refer to r = graph(h) as h
whenever this causes no confusion. Note that each x∈ D(r) may be identified
with the homomorphism x◦f, where f: domh→ r is the isomorphism defined
by f(a) = (a, h(a)), and hence we may identify D(r) with D(domh). In case
domh=P_{m,n},D(r) is identified with AutP_{m,n}.

Observe that any map u: D(N) → Pm,n that fails to preserve a homomor-
phism h: N → P_{m,n} also fails to preserve either idN or every extension of h.

Consequently a globally minimal failsetU in Ω which contains a partial endomor-
phism ofP_{m,n}either contains every non-extendable extension of it or contains the
identity map on some value ofP_{m,n}. This is the case for the two globally minimal
failsets in Ω which contain the identity maps idNd1 and idNd2 respectively, as we
show next.

Lemma 3.1. For i ∈ {1,2}, let ud_{i}:D(N_{d}_{i}) → Pm,n be the constant map
with value di. Then Failid_{Ndi}(udi) is the unique minimal failset of idN_{di} and its
elements are the following (and no others):

(i) the partial endomorphisms ofP_{m,n}with codomain Ndi and their converses;

(ii) the productsQ×Ndi andNdi×Q, whereN_{d}_{i}6Q6P_{m,n}.
Moreover Failid_{Ndi}(ud_{i}) = ΦN_{di}, whereΦN_{di} :={r∈Ω|r`idN_{di}}.

Proof. Firstly, note that idN_{di} ∈ Failid_{Ndi}(udi) is witnessed by (idN_{di},idN_{di}).

Suppose that Failid_{Ndi}(v) is a failset of idN_{di} and that (h, h) witnesses idN_{di} ∈
Failid_{Ndi}(v). We claim that Failid_{Ndi}(udi)⊆Failid_{Ndi}(v). Letr∈ Failid_{Ndi}(udi).

If r is a product of two subalgebras of P_{m,n}, then the identity map on one of
them must belong to Failid_{Ndi}(udi). Since idN_{di} is the only identity map in
Failid_{Ndi}(udi), r must be either Q×Ndi or Ndi×Q, for some Q 6P_{m,n}. But
then r ∈ Failid_{Ndi}(v). Thus, by Lemma 2.1, we only need to consider r when
r\{(d1, d2),(d2, d1)}is the graph of a one-to-one partial endomorphism of P_{m,n}.
Leth^{0}be such a partial endomorphism. Sincercontains the graph of an automor-
phism ofN_{d}_{i} and it does not contain (di, di),h^{0}must be an automorphism ofN_{d}_{i}
and there isj∈ {1,2}such thatdi∈/ρj(r). Consequentlyr is a partial endomor-
phism ofP_{m,n}with codomainN_{d}_{i} or the converse of its graph. Suppose without
loss of generality thatj = 1. Then (h, h^{0}◦h)∈rand v(h)∈/Nd_{i} =ρ1(r). Thus
(h, h^{0}◦h) witnessesr∈Failid_{Ndi}(v). We have just proved that Failid_{Ndi}(udi) is the
unique minimal failset of idN_{di} and that its elements are between those of (i) and
(ii), which belong to ΦN_{di}. Finally it is immediate that ΦN_{di} ⊆Failid_{Ndi}(udi).

Proposition 3.2. The minimal failsets ΦNd1 and ΦNd2 are globally minimal failsets.

Proof. Letr6P^{2}_{m,n}and letv:D(r)→Pm,nbe such thatr∈Failr(v)⊆ΦN_{di},
withi∈ {1,2}. Suppose that idN_{di} ∈/Failr(v) or otherwise ΦN_{di} ⊆Failr(v). Since
idN_{di} is the only identity map in ΦN_{di} we have that Q×Ndi, Ndi×Q /∈Failr(v),
for every N_{d}_{i} 6 Q 6 P_{m,n}. But then, by Lemma 3.1, we may assume that r
is the graph of some partial endomorphism hof P_{m,n} with codomain Ndi. Let
x, y ∈D(r) such that (x, y)∈rbut (v(x), v(y))∈/r. We have that (v(x), v(y))∈
domh×Nd_{i}. Taker^{0} =r∪ {(di, di)}. It is easy to verify thatr^{0} 6P^{2}_{m,n}. Since
v(y)6=di we have (v(x), v(y))∈/r^{0} and thenr^{0} ∈Failr(v). Thusr^{0} ∈ΦN_{di} and so

(di, di)∈/r^{0}.

TakeU to be a failset such thatU contains an automorphism ofP_{m,n}. The set
of the automorphisms ofP_{m,n}which are not inU forms a subgroup of AutP_{m,n}.
The smaller U is, the bigger this subgroup will be. So we may ask if globally
minimal failsets in Ω containing automorphisms are “associated” with maximal
subgroups of AutP_{m,n}. The following results give us the answer.

Let g be a (partial) endomorphism of P_{m,n} and let r be a binary algebraic
relation onP_{m,n}, with (d1, d1),(d2, d2)∈ r. We denote by g^{6} and r the binary
relations graph(g)∪{(d1, d2)}andr∪{(d1, d2),(d2, d1)}respectively. Observe that
both these relations are algebraic.

Lemma 3.3. Let H be a maximal proper subgroup of AutP_{m,n} and K =
AutP_{m,n}\H. Then

WH :=K∪ {g^{6} | g∈K} ∪ {(g^{6})^{`} | g∈K}
is a minimal failset of eachg∈K.

Proof. Letg∈Kand define a mapu: AutP_{m,n}→Pm,nas follows:

u(x) =

d1 ifx∈K, d2 otherwise.

We have that g ∈Failg(u) is witnessed by (id, g). Lets∈ Failg(u). There exist
x, y ∈AutP_{m,n} such that (x, y)∈sand (u(x), u(y))∈/ s. Thenρ1(s) = ρ2(s) =
Pm,nands6=P_{m,n}^{2} . Hence, by Lemma 2.1,s= graph(f) ors=f^{6}or (f^{6})^{`}, for
somef ∈K. Conversely supposef ∈K. Then (id, f) witnessesf, f^{6} ∈Failg(u).

Thus Failg(u) = WH is a failset of g. Now let v: AutP_{m,n} → Pm,n be a map
such thatg∈Failg(v)⊆Failg(u). There existsx∈AutP_{m,n}such thatv(g◦x)6=
g(v(x)). We claim that ∀y∈AutP_{m,n},v(y)∈ {d1, d2}. Ifv(x) orv(g◦x) is not
in{d1, d2}, then (x, g◦x) witnesses r∈Failg(v), where r = graph(g), and then
r∈WH. Hencev(x), v(g◦x)∈ {d1, d2}. Lety ∈AutP_{m,n}. Ifv(y)6=d1, d2 then
(x, y) witnesses graph(y◦x^{−}^{1}) ∈ Failg(v). Thus graph(y◦x^{−}^{1}) ∈ Failg(u) and
this is false. LetK^{0}={f ∈AutP_{m,n}|f ∈Failg(v)}and letH^{0}= AutP_{m,n}\K^{0}.
Then H^{0} is a proper subgroup of AutP_{m,n}. By the maximality of H, H^{0} = H
and henceK^{0} =K. Now it suffices to prove thatf ∈Failg(v) implies thatf^{6} ∈
Failg(v) in order to conclude thatWH⊆Failg(v). Suppose thatf ∈Failg(v). Let
x∈AutP_{m,n}such thatv(f◦x)6=f(v(x)). Iff^{6}∈/Failg(v) then (v(x), v(f◦x)) =
(d1, d2) andv(f^{k}◦x) =v(f◦x) =d2, for everyk>1 (note that (f^{k}^{−}^{1}◦x, f^{k}◦x)∈
f^{6}). But thenv(x) =v(f^{−}^{1}◦f◦x) =d2. Thusf^{6} ∈Failg(v).

Proposition 3.4. Let H be a maximal proper subgroup of AutP_{m,n}. Then
WH is a globally minimal failset.

Proof. By Theorem 2.10 and Lemma 3.3, it suffices to prove that WH is a
minimal failset of each g^{6}, with g ∈ K. Fix g ∈ K and let s = g^{6}. Suppose
s∈Fails(v)⊆WH, for some mapv:D(s)→Pm,n. SinceWH is a minimal failset
ofgand, by Proposition 2.9, every failset that containsg must contain a minimal
failset ofg, we only need to prove thatg∈Fails(v). Observe thats=g·id^{6}. Since
s∈Fails(v) andid^{6} ∈/Fails(v) becauseid^{6}∈/WH, we must haveg∈Fails(v).

Proposition 3.5. LetU be a globally minimal failset. IfU intersectsAutP_{m,n}
thenU is WH for some maximal proper subgroupH of AutP_{m,n}.

Proof. LetK=U∩AutP_{m,n}and let H = AutP_{m,n}\K. ThenH is a proper
subgroup of AutP_{m,n}. Take H^{0} to be a maximal subgroup of AutP_{m,n} con-
taining H. Let K^{0} = AutP_{m,n}\H^{0} ⊆ K and let g ∈ K^{0}. Since g ∈ U we

may take x ∈ AutP_{m,n} and a map u: AutP_{m,n} → Pm,n such that (x, g◦x)
witnesses g ∈ U = Failg(u). If g^{6} ∈/ U then u(x) = d1, u(g◦x) = d2 and
u(g^{2}◦x) =u(g◦x) =d2(note that (g◦x, g^{2}◦x)∈g^{6}). Moreoveru(g^{k}◦x) =d2,
fork>1. But thenu(g^{−}^{1}◦g◦x) =d2, i.e. u(x) =d2. ThusWH^{0} ⊆U.
It follows from Lemma 2.1 that for everyg∈AutP_{m,n}, the subalgebrar, with
r=g^{6}, is maximal with respect to not containing (d2, d1), that is what we call a
value ofP^{2}_{m,n}at (d2, d1). The next result gives us a globally minimal failset whose
elements are exactly the relationsg^{6} and their converses, withg∈AutP_{m,n}.

Proposition 3.6. The set {g^{6},(g^{6})^{`} | g ∈AutP_{m,n}}is a globally minimal
failset.

Proof. Let f ∈ AutP_{m,n} and r = f^{6}. Let u: D(r) → Pm,n be defined as
follows:

u(x) =

d2 ifx(d1, d2) =d1, d1 ifx(d1, d2) =d2. Observe that

(i) for everyg∈AutP_{m,n}we have

u(g◦ρi) =u(ρi) and g^{6}={(a, g◦f^{−}^{1}(b))|(a, b)∈f^{6}},
which implies that

(ρ1, g◦f^{−}^{1}◦ρ2)∈g^{6} and (u(ρ1), u(g◦f^{−}^{1}◦ρ2)) = (d2, d1)∈/g^{6} ;
(ii) for everyx∈D(r),xgraph(f)is identified with an automorphism ofP_{m,n}

and thenx(r) =Pm,n. Therefore ifs∈Failr(u) thenρ1(s) =ρ2(s) =Pm,n

and (d1, d1),(d2, d2) ∈ s. Hence, by Lemma 2.1, s must be one of the
relations graph(g), g^{6} or (g^{6})^{`}, for someg∈AutP_{m,n};

(iii) for every g ∈ AutP_{m,n} and x ∈ D(r), u(g◦x) = g(u(x)) and so g /∈
Failr(u).

Thus Failr(u) ={g^{6},(g^{6})^{`}|g∈AutP_{m,n}}.

We claim that {g^{6},(g^{6})^{`} |g ∈AutP_{m,n}}is a minimal failset ofr. Suppose
thatr∈Failr(v)⊆Failr(u), for some mapv: D(r)→Pm,n. Letx, y∈D(r) such
that (x, y)∈rand (v(x), v(y))∈/r. If (v(x), v(y))6= (d2, d1) then (x, y) witnesses
r∈Failr(v). But thenr∈Failr(u) and this is false. Thus (v(x), v(y)) = (d2, d1).

Now takeg ∈AutP_{m,n}. Sinceg◦f^{−}^{1}∈/Failr(v) we must havev(g◦f^{−}^{1}◦y) =
g◦f^{−}^{1}(v(y)) = v(y). But then (x, g◦f^{−}^{1}◦y) witnesses g^{6} ∈ Failr(v). Thus
Failr(v) = Failr(u). Finally we apply Theorem 2.10 and we get that{g^{6},(g^{6})^{`}|
g∈AutP_{m,n}}is a globally minimal failset because it is a minimal failset of each

one of its elements.

Proposition 3.7. Let U be a globally minimal failset. If U intersects the
globally minimal failset {g^{6},(g^{6})^{`} | g ∈ AutP_{m,n}} but U does not intersect
AutP_{m,n}thenU ={g^{6},(g^{6})^{`}|g∈AutP_{m,n}}.

Proof. Letg ∈ AutP_{m,n} and suppose that g^{6} ∈U. Take g^{0} ∈AutP_{m,n} and
letf =g^{0−1}◦g. Note thatg^{6} =f·g^{0}^{6}. Sincef /∈U andg^{6} ∈U we must have

g^{0}^{6}∈U.

Denote by g the algebraic relation graph(g); the subalgebrar, wherer=g, is
a value ofP^{2}_{m,n}at (0,1) and thenris uniquely covered byP^{2}_{m,n}. Also now we get
a globally minimal failset whose elements are the relationsg, withg∈AutP_{m,n}.

Proposition 3.8. The set {g|g∈AutPm,n}is a globally minimal failset.

Proof. Letf ∈AutP_{m,n} andr=f. Letu:D(r)→Pm,nbe defined by
u(x) =

0 ifx(d1, d2) =d1, 1 otherwise.

Note that

(i)∀g∈AutP_{m,n}, (ρ1, g◦f^{−}^{1}◦ρ2)∈gand (u(ρ1), u(g◦f^{−}^{1}◦ρ2)) = (0,1)∈/g;

(ii) ifs∈Failr(u) then smust be one of the relations graph(g), g^{6}, (g^{6})^{`} or
g, for someg∈AutP_{m,n}, by applying Lemma 2.1;

(iii)∀x∈D(r),x(d1, d2)6=x(d2, d1) sinced1=x(d1, d1) =x(d1, d2)∧x(d2, d1) andd2=x(d2, d2) =x(d1, d2)∨x(d2, d1). Ifx, y ∈D(r) such that (x, y)∈sand u(x)6=u(y), then (d1, d2),(d2, d1)∈s.

Thus {g | g ∈ AutP_{m,n}} = Failr(u) is a failset of r. Let U be a failset of r
contained in Failr(u). For everyg ∈ AutP_{m,n}, we have r = (g^{−}^{1}◦f)·g. Since
g^{−}^{1}◦f /∈Failr(u), and consequentlyg^{−}^{1}◦f /∈U, we must haveg∈U or otherwise
r /∈U. ThusU = Failr(u) and Failr(u) is a minimal failset ofr. Finally we apply
Theorem 2.10 and we have that{g|g∈AutP_{m,n}}is a globally minimal failset.

Proposition 3.9. Let U be a globally minimal failset. If U intersects the
globally minimal failset {g | g ∈ AutP_{m,n}} but U does not intersect AutP_{m,n}
thenU ={g|g∈AutP_{m,n}}.

Proof. Use a similar argument to that in the proof of Proposition 3.7.

The following result gives us two globally minimal failsets that contain non-
extendable partial endomorphisms of P_{m,n}. Later on we will see that they are
the unique globally minimal failsets, within Ω, containing non-extendable partial
endomorphisms ofP_{m,n} and containing no identity maps.

We denote by End^{i}P_{m,n} the set of non-extendable partial endomorphisms of
P_{m,n}having as its domain a maximal proper subalgebra ofP_{m,n}containingNdi.

Proposition 3.10.

(a) Ifm >2then the setWd1 ={h, h^{6},(h^{6})^{`}: h∈End^{1}P_{m,n}}is a globally
minimal failset.

(b) Ifn >2then the setWd2={h, h^{6},(h^{6})^{`}:h∈End^{2}P_{m,n}}is a globally
minimal failset.

Proof. Next we prove the claim regarding (a). By Theorem 2.10, it is enough
to prove thatWd1 is a minimal failset of each of its elements. Takeh:N→P_{m,n}
to be a homomorphism in End^{1}P_{m,n}. HenceN is isomorphic to P_{m}−1,n. Define
a mapu:D(N)→Pm,n by

u(x) =

d1 ifxis non-extendable, d2 otherwise.

We claim that Wd1 = Failh(u). Let f: Q → P_{m,n} be a homomorphism in
End^{1}P_{m,n}. By Lemma 2.6, there is g ∈ AutP_{m,n} such thatg(N) = Q. Con-
sequently (gN, f◦gN) witnessesf, f^{6} ∈ Failh(u). Conversely let s∈Failh(u).

Then one of the pairs (d1, d2),(d2, d1) is not in s. By applying Lemma 2.1,
s= graph(f) ors=f^{6}ors= (f^{6})^{`}for some one-to-one partial endomorphismf
ofP_{m,n}. Letx, y ∈D(N) be such that (x, y) witnessess∈Failh(u). Then either
x is non-extendable or y is non-extendable. Since (x, y) ∈ s\{(d1, d2),(d2, d1)}
which is either graphf or (graphf)^{`}, andy◦x^{−}^{1}is non-extendable, we must have
thatf is either y◦x^{−}^{1} orx◦y^{−}^{1}. Hencef is non-extendable and its domain is
isomorphic toP_{m}−1,n.

Next we prove that Failh(u) is a minimal failset of h. Let v:D(N) → Pm,n

be a map such that h∈ Failh(v) ⊆ Failh(u). For every f ∈ Failh(u), there are
g1, g2 ∈ AutP_{m,n} such that h = g1◦f ◦g2N, by Lemma 2.7. Consequently
Failh(v) contains every f ∈ Failh(u) because it contains no automorphisms of
P_{m,n}. Suppose that Failh(v)6= Failh(u). Then there existsf ∈Failh(u) such that
f^{6} ∈/ Failh(v). We claim that h^{0}^{6} ∈/ Failh(v), for everyh^{0} ∈Failh(v). Let h^{0} ∈
Failh(v) and suppose that (x, y) witnessesh^{0}^{6} ∈Failh(v), for some x, y∈D(N).

Then (x, y) also witnessesh^{0} ∈Failh(v). We apply Lemma 2.7 again and we have
thath^{0}=g_{1}^{0} ◦f◦g_{2}^{0}x(N), for someg_{1}^{0}, g^{0}_{2}∈AutP_{m,n}. Since

g_{1}^{0}(v(f◦g_{2}^{0} ◦x) =v(h^{0}◦x)6=h^{0}(v(x)) =g^{0}_{1}◦f(v(g^{0}_{2}◦x))

and (g_{2}^{0}◦x, f◦g_{2}^{0}◦x)∈f^{6}we must havev(g^{0}_{2}◦x) =d1andv(f◦g_{2}^{0}◦x) =d2. But
then (d1, d2) = ((v(x), v(h^{0} ◦x)) = (v(x), v(y))∈/h^{0}^{6} and this is absurd. Denote
by h^{−}^{1} the partial endomorphism from h(N) into P_{m,n} given by the inverse of
the isomorphism from N to h(N) given byh. Ash, h^{−}^{1}∈Failh(v) we have that
h^{6},(h^{−}^{1})^{6}∈/Failh(v). Thereforeh=h^{6}∩((h^{−}^{1})^{6})^{`}∈/Failh(v). HenceWd1 is a
minimal failset ofh.

In order to finish our proof we only need to see that Wd1 is a minimal failset
ofs=h^{6}. Suppose that s∈Fails(v)⊆Failh(u), for some map v:D(s)→Pm,n.
Observe that s = h·id^{6}. Since id^{6} ∈/ Fails(v), h must be in Fails(v). By the
minimality of Failh(u) as a failset ofhwe have that Fails(v) =Wd1.

The proof of (b) is done by using the same kind of arguments as those used to

prove (a).

Proposition 3.11. Let U be a globally minimal failset. If there is a non-
extendable partial endomorphismhof P_{m,n} such that domhis a maximal proper
subalgebra of P_{m,n} and h ∈ U, then either U = ΦN_{di} or U = Wdi, for some
i∈ {1,2}.

Proof. Leth: N →P_{m,n} be a non-extendable partial endomorphism ofP_{m,n},
where N is a maximal proper subalgebra ofP_{m,n}. Then N must contain either
Nd_{1} orNd_{2}, so that eitherh∈End^{1}P_{m,n}orh∈End^{2}P_{m,n}. Suppose thath∈U
and suppose without loss of generality that h∈End^{1}P_{m,n}. By Proposition 3.5,
U does not intersect AutP_{m,n}.

Firstly consider the case m = 2. Then N = Nd_{1} ∪ {d1} and h(d1) = d2.
Take f ∈ AutN_{d}_{1} to be hN_{d}_{1}. Observe that graphh= (f^{−}^{1}·(id^{6})^{`})^{`} and so
f^{−}^{1}·(id^{6})^{`} ∈U. Consequently eitherf^{−}^{1}∈U or id^{6}∈U. SinceU∩{g^{6},(g^{6})^{`}|
g ∈ AutP_{m,n}}=∅, by Proposition 3.7, we have that id^{6} ∈/ U. Hence we must
have thatf^{−}^{1}∈U. Letg∈AutP_{m,n}be given bygNd1 =f^{−}^{1}andgNd2 = idN_{d}_{2}.
We have that g /∈ U and consequently idNd1 ∈U because graphf^{−}^{1} =g·M^{N}d1.
FinallyU = ΦN_{d}_{1} by Theorem 2.10 and Lemma 3.1.

Now consider the casem >2. We claim thatU =Wd1. Letu: D(N)→Pm,nbe
a map andx, y ∈D(N) such that (x, y) witnessesh∈U = Failh(u). Let f∈Wd_{1}

be a non-extendable partial endomorphism of P_{m,n}. We apply Lemma 2.7 and
we get that there exist g1, g2 ∈ AutP_{m,n} such that h = g1◦f ◦g2N. Since
g1, g2 ∈/ U and h ∈ U, f must be in U. We still need to prove that f^{6} ∈ U.
Observe that h^{6} = (g_{1}^{−}^{1} ·(g2·f^{6})^{`})^{`}. Therefore if h^{6} ∈ U then f^{6} ∈ U
because g1, g2 ∈/U. Hence it only remains to prove thath^{6} ∈ U. Suppose that
(u(x), u(y)) = (d1, d2). Let h^{−}^{1} ∈ Wd1 be the partial endomorphism of P_{m,n}
corresponding to the inverse of the isomorphism N → h(N) given by h. Once
again there areg^{0}_{1}, g_{2}^{0} ∈AutP_{m,n}such that h=g^{0}_{1}◦h^{−}^{1}◦g^{0}_{2}. Sincey=h◦xwe
have that u(h^{−}^{1}◦g^{0}_{2}◦x) =g^{0}_{1}^{−}^{1}(u(y)) =d2 andu(g^{0}_{2}◦x) = g^{0}_{2}(u(x)) =d1. But
then (h^{−}^{1}◦g^{0}_{2}◦x, g^{0}_{2}◦x) witnessesh^{6}∈U.
Our next step is to find out if there are any other globally minimal failsets
containing proper partial endomorphisms ofP_{m,n}.

Lemma 3.12. LetU be a failset and suppose thatid{0,1} ∈U. ThenΦNd1 ⊆U
orΦN_{d}_{2} ⊆U.

Proof. This is a consequence of the equalityMNd1 ∩MNd2=M^{{}0,1}and of Propo-

sition 2.9 and Lemma 3.1.

Lemma 3.13. LetU be a failset. For every subalgebra Q of P_{m,n} such that
Nd1 ⊆ Q, Nd2 ∩Q * {0, d1,1} and idQ ∈ U, there exists a maximal proper
subalgebra N ofP_{m,n} such thatQ⊆N andidN ∈U.

Proof. We prove the result by induction onm−k, where k is the number of atoms ofQ.

For m−k = 1, Q has m−1 atoms and therefore Q is a maximal proper
subalgebra of P_{m,n} since Nd1 ⊆ Q. Now suppose that the result is valid for
subalgebras of P_{m,n} containingNd_{1} and havingk atoms. LetQbe a subalgebra
ofP_{m,n}containingNd1 and leta1, . . . , ak−1 be the atoms ofQ. There existsi∈
{1, . . . , k−1}such thatai∈/AtP_{m,n}. We may assume thati=k−1. Thenak−1

is of the formai1∨ai2∨afor someai1, ai2 ∈AtP_{m,n}and somea∈Pm,nsuch that
ai1 a∨ai2andai2a∨ai1. Now we takeQ_{1}, Q_{2}6P_{m,n}such thatNd1 ⊆Q1, Q2

and AtQ_{1} ={a1, . . . , ak−2, a∨ai1, ai2} and AtQ_{2} ={a1, . . . , ak−2, a∨ai2, ai1}.
Note that Q=Q1∩Q2. Since idQ ∈U one of the two identity maps idQ1,idQ2

must be in U. Then by our inductive hypothesis there exists a maximal proper
subalgebraN ofP_{m,n} such thatQ⊆N and idN ∈U.

By using a similar argument we also have the following result:

Lemma 3.14. LetU be a failset. For every subalgebra Q of P_{m,n} such that
Nd2 ⊆ Q, Nd1 ∩Q * {0, d2,1} and idQ ∈ U, there exists a maximal proper
subalgebra N ofPm,n such thatQ⊆N andidN ∈U.

Lemma 3.15. LetU be a failset and suppose thatU contains neitheridN_{d}_{1} nor
idNd2 and thatU does not intersectAutP_{m,n}. LetQbe a subalgebra ofP_{m,n}such
that Q6={0,1}. IfidQ ∈U then U contains the identity map on some maximal
proper subalgebra of P_{m,n}.

Proof. Let Q1 = Nd1 ∪Q and Q2 = Nd2 ∪Q. Observe that Q1 and Q2 are
universes of two subalgebras Q_{1} and Q_{2} of P_{m,n}. Since idQ ∈U andQ=Q_{1}∩
Q_{2} one of the identity maps idQ1, idQ2 must be in U. Suppose without loss of
generality that idQ1 ∈ U. By hypothesis, idNd1 ∈/ U and therefore Q1 6= Nd1.
If Q1∩Nd_{2} * {0, d1,1}then, by applying Lemma 3.13, there exists a maximal
proper subalgebraN ofP_{m,n} satifyingQ1 ⊆N and idN ∈U. Now suppose that
Q1∩Nd2 ⊆,{0, d1,1}and so Q1=Nd1∪ {d1}. There exists a mapu:D(Q_{1})→
Pm,n such that idQ1 ∈FailidQ1(u) ⊆ U. Let x ∈D(Q_{1}) such that x∈ Q1 and
u(x)∈/Q1. Hence 0< u(x)< d1and then there exist distinct atomsa, bof P_{m,n}
such that a 6 u(x) and b u(x). Now we take N to be the maximal proper
subalgebra ofP_{m,n}, containingNd1, whose atoms are a∨b and all the atoms of
P_{m,n}different fromaandb. Observe thatx∈N andu(x)∈/N. Thus idN ∈U.

Proposition 3.16. LetU be a globally minimal failset. Suppose thatU con-
tains neitheridN_{d}_{1} noridN_{d}_{2} and suppose thatU does not intersectAutP_{m,n}. For
every subalgebraQ ofP_{m,n},idQ∈/U.

Proof. Let Q be a subalgebra ofP_{m,n}. If Q ={0,1}then idNd1, idNd2 ∈/ U
implies idQ ∈/U by Lemma 3.12. Now considerQ6={0,1}. Suppose that idQ∈U.
By Proposition 3.15, there exists a maximal proper subalgebra N of P_{m,n} such
that idN ∈U. Leth be a non-extendable partial endomorphism ofP_{m,n}having
N as its domain. We have that idN ∈U impliesh∈U and from Proposition 3.10
and Proposition 3.11 we getU =Wdi, for somei∈ {1,2}, and idN ∈/Wdi. Thus

idQ∈/U.

Lemma 3.17. LetU be a failset and suppose thatU contains no identity maps.

For every one-to-one non-extendable partial endomorphismh:N →P_{m,n}ofP_{m,n},
if Nd_{i}⊆N, for somei∈ {1,2}, and h∈U thenU intersects End^{i}P_{m,n}.

Proof. Leth:N →P_{m,n}be a one-to-one non-extendable partial endomorphism
such that Ndi ⊆ N, for some i ∈ {1,2}, and h ∈ U. Suppose without loss of
generality thati= 1. Note thatd1∈domhbecausehis non-extendable. Sinceh
is one-to-one andh(d1), h(d2)∈ {d1, d2}we must haveh(d1) =d1andh(d2) =d2.
Thus Nd_{2} ∩N 6= {0, d1,1} or otherwise h would be extendable. Let k be the
number of atoms ofN. We will prove the result by induction on m−k.

Ifm−k= 1 thenN has m-1 atoms. HenceN is a maximal proper subalgebra
ofP_{m,n}and there is nothing more to prove.

Now suppose the result is valid for partial endomorphisms whose domains have
at least k atoms. Let h:N → P_{m,n} be a one-to-one non-extendable partial en-
domorphism of P_{m,n} such that h ∈ U, Nd1 ⊆N and N has k−1 atoms. Let
a1, . . . , ak−1 be the atoms ofN. Sincehis non-extendable andk−1< m, there
exists aj ∈AtN such thataj ∈/AtP_{m,n} buth(aj)∈AtP_{m,n}. Suppose without
loss of generality thatj=k−1 and letb be the atomh(aj) ofP_{m,n}. Thenak−1

must be of the formak1∨ak2∨afor some distinct atomsak1, ak2 ofP_{m,n}and for
somea∈P_{m,n}(eventually 0), witha < d1. The one-to-one non-extendability ofh
also implies the existence of somelin{1, . . . , k−2}such thatal∈AtN∩AtP_{m,n},
buth(al) ∈/ AtPm,n, and so h(al) is of the formal1∨al2∨a^{0} for some distinct
atoms al_{1}, al_{2} of P_{m,n} and some a^{0} ∈ P_{m,n} with a^{0} < d1. Now two cases may
occur:

Case 1: there exists al ∈ AtP_{m,n} for which h(al) = al1 ∨al2 ∨a^{0}, for some
distinct atomsal_{1}, al_{2} ofP_{m,n}and some 0< a^{0}< d1 such thatal_{1}, al_{2} a^{0};

Case 2: for everyal∈AtN∩AtP_{m,n},h(al) is either an atom ofP_{m,n}or is the
join of two atoms ofP_{m,n}.

Observe that the subalgebras ofP_{m,n}are completely determined by their atoms
and their coatoms, and every one-to-one partial endomorphism of P_{m,n} is com-
pletely determined by the following conditions:

(i) The bijection from the set of the atoms of the domain, if non empty, into the set of the atoms of the codomain;

(ii) The bijection from the set of the coatoms of the domain, if non empty, into the set of the coatoms of the codomain.

We begin with case 1. Let N_{1} and N_{2} be the subalgebras of P_{m,n} such that
Nd1 ⊆N1, N2 and

AtN_{1}={a1, . . . , ak−2, ak1, ak2∨a}
and

AtN_{2}={al_{1}, al_{2}∨a^{0}} ∪Ath(N)\{h(al)}.

Let h1: N_{1} → P_{m,n} be the one-to-one partial endomorphism determined by
h1Nd1 =hNd1 and

h1(x) =

al2∨a^{0} ifx=al,
b ifx=ak1,
al1 ifx=ak2∨a,
h(x) otherwise

for every x∈AtN_{1}. Observe that the non-extendability ofh implies thath1 is
also non-extendable. Leth2:N_{2}→P_{m,n}be the one-to-one partial endomorphism
determined byh2N_{d}_{1} =idN_{d}_{1} and

h2(x) =

al_{2} ifx=al_{1},
a^{0} ifx=al_{2}∨a^{0},
al_{1}∨b ifx=b,

x otherwise

for everyx∈AtN_{2}. We claim thatker(h1, h2) = graph(h). Note thatker(h1, h2)

= (N_{d}^{2}_{1}∩ker(h1, h2))∪(N_{d}^{2}_{2}∩ker(h1, h2)). Sinceh1N_{d}_{1} =hN_{d}_{1} andh2N_{d}_{1} =
idNd1 we haveN_{d}^{2}_{1}∩ker(h1, h2) =N_{d}^{2}_{1}∩graphh. Let x, y∈Nd_{2}. We are going
to prove that (x, y) ∈ ker(h1, h2) only for x∈ N. Suppose (x, y) ∈ ker(h1, h2)
withx∈N1\N. Then one and only one of the atomsak1, ak2∨aofN_{1} is less or
equal tox.

If ak_{1} 6 x then b = h1(ak_{1}) 6 h1(x) = h2(y). But then al_{1} ∨b 6 h2(y).

Thus h1(ak2 ∨a) = al1 6 h1(x) and this is false because h1(x)∧h1(ak2∨a) =
h1(x∧(ak_{2}∨a)) = 0.

Ifak2∨a6xthenal1=h1(ak2∨a)6h1(x) =h2(y). But thenal1∨b6h2(y).

Thush1(ak_{1}) =b6h1(x) and this is false because h1(x∧ak_{1}) = 0.

Now let x∈N. We are going to consider three different possibilities in order to prove that (x, y)∈ker(h1, h2) if and only if (x, y)∈graph(h).