2022–292

December 27, 2022 CDS-Library The COMPASS Collaboration The COMPASS
Collaboration

A set of measurements of azimuthal asymmetries in the production of pairs of
identified hadrons in deep-inelastic scattering of muons on transversely
polarised 6LiD (deuteron) and NH3 (proton) targets is presented. All available
data collected in the years 2002–2004 and 2007/2010 with the COMPASS
spectrometer using a muon beam of $160\,\,\mbox{GeV}/c$ at the CERN SPS were
analysed. The asymmetries provide access to the transversity distribution
functions via a fragmentation function that in principle may be independently
obtained from $e^{+}e^{-}$ annihilation data. Results are presented, discussed
and compared to existing measurements as well as to model predictions.
Asymmetries of $\pi^{+}\pi^{-}$ pairs measured with the proton target as a
function of the Bjorken scaling variable are sizeable in the range $x>0.032$,
indicating non-vanishing transversity distribution and di-hadron interference
fragmentation functions. As already pointed out by several authors, the small
asymmetries of $\pi^{+}\pi^{-}$ measured on the 6LiD target can be interpreted
as indication for a cancellation of $u$ and $d$-quark transversity
distributions.

(to be submitted to Phys. Lett. B)

##  1 Introduction

The description of the nucleon spin structure remains one of the main
challenges in hadron physics. For a polarised nucleon, a leading-twist
description comprises eight transverse-momentum-dependent (TMD) parton
distribution functions (PDFs), describing the distributions of longitudinal
and transverse momenta of partons and their correlations with nucleon and
quark polarisations [1]. After integration over quark intrinsic transverse
momentum $k_{T}$, three PDFs fully describe the nucleon, i.e. the momentum
distribution function $f_{1}^{q}(x)$, the helicity distribution function
$g_{1}^{q}(x)$ and the transversity distribution function $h_{1}^{q}(x)$,
where $x$ denotes the Bjorken scaling variable. For simplicity, the latter
will be referred to as ”transversity” throughout this paper. While the
momentum and the helicity distribution functions have been measured with good
accuracy, the knowledge on transversity is inferior but steadily increasing.
Unlike $f_{1}^{q}$ and $g_{1}^{q}$, transversity is not accessible at leading
twist in inclusive deep-inelastic scattering (DIS) because it is related to
soft processes correlating quarks with opposite chirality, making it a chiral-
odd function. Transversity can be accessed through observables that conserve
chirality, i.e. when it is coupled to a chiral-odd partner. In this regard,
measuring semi-inclusive deep-inelastic scattering (SIDIS) is advantageous as
transversity is coupled to the chiral-odd fragmentation functions (FFs) that
describe the hadronisation of a transversely polarised quark $q$ into
unpolarised final-state hadrons.

The major source of information on transversity has been measurements of
transverse-spin-dependent asymmetries (TSAs) in single-hadron production in
SIDIS ($\ell N^{\uparrow}\rightarrow\ell^{\prime}hX$), where transversity is
coupled to the Collins FF [2]. Transverse-spin asymmetries define the size of
the transverse-target-spin-dependent azimuthal modulations of the SIDIS cross
section. The first measurement of the Collins asymmetries was performed by the
HERMES Collaboration [3] using a transversely polarised hydrogen target.
Sizeable asymmetries were observed, suggesting non-zero transversity and
Collins FFs. The COMPASS Collaboration has the highest statistics data in this
field, e.g. 28 M pion pairs taken with the NH3 (proton) target and 4 M pion
pairs taken with the 6LiD (deuteron) target. The COMPASS collaboration has
delivered a full set of measurements, i.e. both TSAs for unidentified charged
hadrons [4] as well as pions and kaons [5] using the transversely polarised
deuteron target, and TSAs for unidentified charged hadrons [6, 7] as well as
pions and kaons [8] using the transversely polarised proton target. The TSAs
measured with the polarised proton target showed a non-zero signal for Collins
asymmetries with high statistics and a wide kinematic coverage. The TSAs
measured with the polarised deuteron target are compatible with zero
indicating a possible cancellation between up and down quark contributions to
transversity. Despite the lower accuracy of these data, they were shown to
play a key role in the extraction of flavour-dependent transversity
distribution functions and remain the only SIDIS measurement ever performed
using a transversely polarised deuteron target. In order to complete the
COMPASS programme [9], a new high statistics measurement of TSAs using a
transversely polarised deuteron target was performed in the last data taking
campaign, in 2022.

A promising alternative approach to access transversity is the measurement of
TSAs in semi-inclusive production of pairs of hadrons of opposite charge
($\ell\ N^{\uparrow}\rightarrow\ell^{\prime}h^{+}h^{-}X$). Following this
approach, in this work $\pi^{+}\pi^{-}$ and $K^{+}K^{-}$ as well as
$\pi^{+}K^{-}$ and $K^{+}\pi^{-}$ pairs will be studied. In this case,
transversity is coupled to the chiral-odd interference fragmentation function
(IFF) $H_{1}^{\sphericalangle}$ [10, 11, 12], which describes the
hadronisation of a transversely polarised quark into a pair of unpolarised
hadrons. At leading twist, and after integration over total transverse
momentum, the differential cross section on a transversely polarised target
comprises two terms and can be written as [13]

$\begin{split}\frac{\mathop{}\mathopen{}\mathrm{d}^{7}\sigma}{\mathop{}\mathopen{}\mathrm{d}\cos\theta\mathop{}\mathopen{}\mathrm{d}M_{\rm{hh}}\mathop{}\mathopen{}\mathrm{d}\phi_{\rm{R}}\mathop{}\mathopen{}\mathrm{d}z\mathop{}\mathopen{}\mathrm{d}x\mathop{}\mathopen{}\mathrm{d}y\mathop{}\mathopen{}\mathrm{d}\phi_{\rm{S}}}=&\frac{\alpha^{2}}{2\pi
Q^{2}y}\left((1-y+\frac{y^{2}}{2})\sum_{q}e_{q}^{2}~{}f_{1}^{q}(x)~{}D_{1,q}(z,M_{\rm{hh}}^{2},\cos\theta)\right.\\\
&\quad\left.+S_{\perp}(1-y)\sum_{q}e_{q}^{2}\frac{|\textbf{p}_{1}-\textbf{p}_{2}|}{2M_{\rm{hh}}}\sin\theta~{}\sin\phi_{\rm{RS}}~{}h_{1}^{q}(x)~{}H_{1,q}^{\sphericalangle}(z,M_{\rm{hh}}^{2},\cos\theta)\right).\end{split}$
(1)

Here $\alpha$ is the fine-structure constant,
$D_{1,q}(z,M_{\rm{hh}}^{2},\cos\theta)$ is the spin-independent dihadron
fragmentation function (DiFF), $y$ is the fraction of the lepton energy in the
laboratory frame transferred to the exchanged virtual-photon and $Q^{2}$ the
negative square of the four-momentum transfer. Here, $z$ is the fraction of
the virtual-photon energy carried by the hadron pair, $M_{\rm{hh}}$ its
invariant mass and $\theta$ the polar angle of the positive hadron with
respect to the two-hadron boost axis in the two-hadron rest frame. The symbol
$S_{\perp}$ denotes the component of the target spin vector $\bf{S}$
perpendicular to the virtual-photon direction, with $\phi_{\rm{S}}$ the
azimuthal angle of the initial nucleon spin, $\phi_{S^{\prime}}$ the azimuthal
angle of the spin vector of the fragmenting quark and
$\phi_{\rm{RS}}=\phi_{\rm{R}}-\phi_{S^{\prime}}=\phi_{\rm{R}}+\phi_{\rm{S}}-\pi$.
The azimuthal angle $\phi_{\rm{R}}$ is given as

$\phi_{\rm{R}}=\frac{(\bf{q}\times\bf{l})\cdot\bf{R}}{|(\bf{q}\times\bf{l})\cdot\bf{R}|}\,\arccos\frac{(\bf{q}\times\bf{l})\cdot(\textbf{q}\times\bf{R})}{|\bf{q}\times\bf{l}|\,|\textbf{q}\times\bf{R}|},$
(2)

where $\bf{l}$ is the incoming lepton momentum, q the virtual-photon momentum
and R the relative hadron momentum defined as
$\textbf{R}=(z_{2}\textbf{p}_{1}-z_{1}\textbf{p}_{2})/(z_{1}+z_{2})$. The TSAs
are experimentally accessible through the measured number of hadron pairs
written as

$N_{\rm{hh}}(x,y,z,M_{\rm{hh}}^{2},\cos\theta,\phi_{\rm{RS}})\propto\sigma_{\rm{UU}}(1+f(x,y)P_{\rm{T}}D_{\rm{nn}}(y)A_{\rm{UT}}^{\phi_{\rm{RS}}}\sin\theta\sin\phi_{\rm{RS}}),$
(3)

where $f(x,y)$ is the target polarisation dilution factor, $P_{\rm{T}}$ is the
transverse polarisation of the target nucleons and $D_{\rm{nn}}$ the
transverse-spin transfer coefficient. A more detailed discussion about the
theoretical framework can be found in Ref. [14]. As shown in Ref. [14], the
asymmetry

$A_{\rm UT}^{\sin\phi_{\rm
RS}}=\frac{|\textbf{p}_{1}-\textbf{p}_{2}|}{2M_{\rm{hh}}}\frac{\sum_{q}\,e_{q}^{2}~{}h_{1}^{q}(x)~{}H_{1,q}^{\sphericalangle}(z,M_{\rm{hh}}^{2},\cos\theta)}{\sum_{q}e_{q}^{2}~{}f_{1}^{q}(x)~{}D_{1,q}(z,M_{\rm{hh}}^{2},\cos\theta)}$
(4)

is proportional to the product of the transversity distribution function
$h_{1}^{q}(x)$ and the polarised two-hadron interference fragmentation
function $H_{1,q}^{\sphericalangle}(z,M_{\rm{hh}}^{2},\cos\theta)$, summed
over the quark flavours $q$ with charge $e_{q}$.

Transverse-spin-dependent asymmetries of hadron pairs were first measured by
the HERMES Collaboration [15] for pion pairs using a transversely polarised
hydrogen target. A sizeable signal was seen as a function of $x$, indicating a
sizeable $u$-quark transversity and non-vanishing interference fragmentation
functions. The COMPASS collaboration has published measurements of transverse
spin asymmetries for pairs of unidentified hadrons produced on polarised
deuterons [14] and polarised protons [16]. The COMPASS results obtained with
the proton target showed significantly sizeable asymmetries and a clear slope
in their $x$-dependence thanks to the high accuracy of the proton data set,
while those extracted from deuteron-target data were found to be compatible
with zero. An intriguing similarity between Collins-like single-hadron
asymmetries for the positive and negative hadrons extracted from the SIDIS
hadron-pair data and the standard Collins asymmetries is observed as a
function of $x$, suggesting that both single hadron and hadron-pair
transverse-spin dependent fragmentation functions are generated by the same
elementary mechanism, as presented and discussed in Ref. [17].

In this paper, we present a new measurement of TSAs for identified hadron-
pairs using the full data set collected by the COMPASS Collaboration on
transversely polarised deuteron (2002-2004) and proton (2007 and 2010)
targets. The paper is organised as follows. Only a brief description of the
experimental setup and data analysis are given in Sec. 3, as the same setup
and methods of data cleaning, selection and extraction of TSAs as in previous
COMPASS analyses [14, 16] are used. The measured asymmetries are presented in
Sec. 3 and discussed in Sec. 4.

##  2 Experimental data and analysis

The analysis presented in this paper is based on data collected in the years
2002-2004 and 2007/2010 using the COMPASS spectrometer [18] by scattering the
naturally polarised $\mu^{+}$ beam of 160 GeV/$c$ delivered by the CERN SPS
off transversely polarised 6LiD and NH3 targets, respectively. For 6LiD, the
average dilution factor calculated for semi-inclusive reactions is
$\langle{f}\rangle\sim 0.38$ and the average polarisation is $\langle{P_{\rm
T}}\rangle\sim 0.47$, while for NH3 the corresponding values are
$\langle{f}\rangle\sim 0.15$ and $\langle{P}_{\textrm{T}}\rangle\sim 0.83$,
respectively. The target consisted of two or three cylindrical cells assembled
in a row, which can be independently polarised. In 2002–2004, two cells were
used, each 60 cm long and 3 cm in diameter, separated by a 10 cm gap. In 2007
and 2010, the target consisted of three cells of 4 cm diameter, with gaps of 5
cm in between. The middle cell was 60 cm long and the two outer ones 30 cm
long each. From 2006 on, a new solenoidal magnet was used to polarise the
target with a polar angle acceptance of 180 mrad as seen from the upstream end
of the target, while in the earlier measurements with the 6LiD target the
polar angle acceptance was 70 mrad. For the measurement of transverse spin
effects, the target material was polarised along the vertical direction. In
order to reduce systematic effects, neighbouring cells were polarised in
opposite directions allowing for simultaneous data taking with both target
spin directions to reduce flux-dependent systematic uncertainties.
Furthermore, the polarisation was destroyed and built up in reversed direction
every four to five days, in order to cancel residual acceptance effects
associated with the longitudinal position of the target cells (i.e. position
along the beam line). For the data collected using a proton target, in the
analysis, the central cell is divided into two parts, providing four data
samples with two different orientations of polarisation. Note that for the
measurements in 2007 and in 2010 a similar spectrometer configuration was
used.

In the analysis, events with incoming and outgoing muons and at least two
reconstructed charged hadrons originating from the interaction vertex inside
the target cells are selected. Equal flux through the whole target is obtained
by requiring that the extrapolated beam tracks pass through all three cells.
In order to select events in the DIS regime, requirements are applied on the
squared four-momentum transfer, $Q^{2}>1$ (GeV/$c)^{2}$, and on the invariant
mass of the final hadronic state, $W>5~{}\mbox{GeV}/c^{2}$. Furthermore, the
fractional energy transfer to the virtual photon is required to be $y>0.1$ and
$y<0.9$ to remove events with poorly reconstructed virtual-photon energy and
events with large radiative corrections, respectively.

For a selected DIS event, all reconstructed hadrons originating from the
interaction vertex are considered. Only hadrons produced in the current
fragmentation region are selected by requiring $z>0.1$ for the fractional
energy and $x_{F}>0.1$ for the Feynmann-$x$ variable. The two-hadron sample
consists of all combinations of oppositely charged hadrons built from the same
DIS event. Exclusive dihadron production is suppressed by requiring the
missing energy for each hadron pair to be greater than 3 GeV. As the azimuthal
angle $\phi_{\rm{R}}$ is only defined for non-collinear vectors R and q, a
minimum value is required on the component of R perpendicular to q, i.e.
$R_{\perp}>0.07$ GeV/$c$. After the application of all requirements, 0.56
$\times\,10^{7}$ h+h- combinations remain for the deuteron data and 3.5
$\times\,10^{7}$ h+h- pairs for the proton data.

Table 1: Final statistics for unidentified and identified charged-hadron pairs in deuteron (2002-2004) and proton (2007 and 2010) data. Year | Number of pairs ($\times 10^{6}$) [tb]
---|---
| h+h- | $\pi^{+}\pi^{-}$ | $\pi^{+}K^{-}$ | $K^{+}\pi^{-}$ |  $K^{+}K^{-}$ [tb]
2002-2004 (deuteron) | 5.65 | 3.97 | 0.26 | 0.30 | 0.10
2007 (proton) | 10.91 | 7.41 | 0.38 | 0.53 | 0.22
2010 (proton) | 34.56 | 20.60 | 1.10 | 1.53 | 0.60

Figure 1: Distributions of invariant mass $M_{\rm{hh}}$ for $2002$-$2004$
deuteron data (top row) and combined $2007$/$2010$ proton data (bottom row):
$\pi^{+}\pi^{-}$ pairs ($1^{\text{st}}$ column) , $K^{+}K^{-}$ pairs
($2^{\text{nd}}$ column), $\pi^{+}K^{-}$ and $K^{+}\pi^{-}$ pairs
($3^{\text{rd}}$ column).

The RICH detector information is used to identify charged hadrons as pions or
kaons in the momentum range between the Cherenkov threshold (about 2.6 GeV/$c$
and 9 GeV/$c$, respectively) and 50 GeV/$c$. The detector set-up after the
upgrade of 2005 and the particle identification (PID) procedure are fully
described in Ref. [19], while details on the likelihood PID method and the
purity of identified samples are explained in Ref. [5] and Ref. [8] for
deuteron and proton targets, respectively. In the kinematic domain of the
COMPASS experiment, about $67\,\%$ of the final-state charged hadrons are
identified as pions and about $10\,\%$ as kaons. The remaining particles are
either protons, electrons or not clearly identified. About $60\,\%$ are pion
pairs ($\pi^{+}\pi^{-}$), about $2\,\%$ are kaon pairs ($K^{+}K^{-}$) and
about $8\,\%$ are mixed pairs ($\pi^{+}K^{-},~{}K^{+}\pi^{-}$). The missing
fraction refers to cases where at least one of the two hadrons cannot be
accurately identified. The resulting statistics for unidentified and
identified hadron pairs after applying all requirements are shown in Table 1.

The invariant-mass distributions for the four opposite-charge combinations
that can be formed using identified charged pions and kaons ($\pi^{+}\pi^{-}$,
$K^{+}K^{-}$, $\pi^{+}K^{-}$, $K^{+}\pi^{-}$) are shown in Fig.1 for deuteron
and proton targets. In the $\pi^{+}\pi^{-}$ spectrum, the mass signatures of
some mesons decays, such as $K^{0}$ around $500\,\mbox{MeV}/c^{2}$, $\rho^{0}$
around $770\,\mbox{MeV}/c^{2}$, $f_{0}$ around $980\,\mbox{MeV}/c^{2}$ and
$f_{2}$ around $1270\,\mbox{MeV}/c^{2}$, respectively, are clearly visible in
both deuteron and proton data as expected from Ref. [20]. Other decays with
more than two hadrons in the final state (like the decays of $\omega$, $\eta$
and $\eta^{\prime}$) generate broader peaks and contribute less to the overall
pion-pair invariant-mass spectra [20]. The $K^{+}K^{-}$ invariant-mass
distribution shows a very pronounced signal of the $\phi(1020)$ resonance
close to its production threshold. The $\phi$ meson can also contribute to the
pion pair spectra via the two-step decay
$\phi(1020)\rightarrow\rho\pi\rightarrow\pi^{+}\pi^{-}\pi^{0}$. The invariant-
mass distribution of $K^{+}K^{-}$ pairs in the proton data shows indications
of further broad peaks around $1300\,\mbox{MeV}/c^{2}$ and
$1500\,\mbox{MeV}/c^{2}$, which might be caused by $f_{2}(1270)$ and
$f_{2}^{\prime}(1525)$. The invariant-mass distributions of $\pi^{+}K^{-}$ and
$K^{+}\pi^{-}$ also show in each case one dominant channel caused by the
decays of $K^{*}(892)$. Further possible candidates for peaks in the
$M_{\rm{hh}}$ spectra of the $\pi^{+}K^{-}$ and $K^{+}\pi^{-}$ pairs are
$K^{*}(1430)$ and $K_{4}^{*}(2045)$.

##  3 Results

The asymmetries extracted from 6LiD and NH3 targets are presented in Figs. 2
and 3, respectively. They were evaluated in bins of $x$, $z$ and $M_{\rm{hh}}$
as given in Table 2. For 6LiD, no significant asymmetry is observed in any
variable for all pair combinations. For $\mathrm{NH_{3}}$, large negative
asymmetries up to $-0.07$ are obtained for $\pi^{+}\pi^{-}$ pairs in the
region $x>0.03$, which implies that both transversity distributions and
polarised two-hadron interference fragmentation functions do not vanish, as
already observed in Refs. [15, 16]. For $x<0.03$, these asymmetries are
compatible with zero.

Figure 2: Hadron-pair transverse-spin-dependent asymmetries as a function of $x$, $z$ and $M_{\rm{hh}}$, extracted from the full data set collected with the 6LiD (deuteron) target. Systematic uncertainties are shown by the gray bands. Table 2: Bin limits of the variables $x$, $z$ and $M_{\rm{hh}}$ (in units of $\,\mbox{GeV}/c^{2}$) for the four types of pairs. |  $x$ bin limits [tb]
---|---
$\pi\pi$ | 0.003 | 0.008 | 0.013 | 0.020 | 0.032 | 0.050 | 0.080 | 0.130 | 0.210 | 1.000 |
$\pi K/K\pi$ | 0.003 | 0.013 | 0.020 | 0.032 | 0.050 | 0.080 | 0.130 | 1.000 |  |  |
$KK$ | 0.003 | 0.008 | 0.013 | 0.020 | 0.032 | 0.080 | 1.000 |  |  |  |
|  $z$ bin limits [tb]
$\pi\pi$ | 0.20 | 0.25 | 0.30 | 0.35 | 0.40 | 0.50 | 0.65 | 0.80 | 1.00 |  |
$\pi K/K\pi$ | 0.20 | 0.30 | 0.35 | 0.40 | 0.50 | 0.65 | 1.00 |  |  |  |
$KK$ | 0.20 | 0.40 | 0.50 | 0.65 | 0.80 | 1.00 |  |  |  |  |
|  $M_{\rm{hh}}$ bin limits [tb]
$\pi\pi$ | 0.0 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0 | 1.2 | 1.6 | 100
$\pi K/K\pi$ | 0.0 | 0.8 | 0.9 | 1.0 | 1.2 | 100 |  |  |  |  |
$KK$ | 0.9 | 1.05 | 1.15 | 1.30 | 1.50 | 100 |  |  |  |  |

The asymmetry measured with the 6LiD target is compatible with zero within
uncertainties over the whole $x$ range. For both targets, no clear dependence
on $z$ can be observed, and for the NH3 target the asymmetry is observed to be
negative in the whole range. For both targets, the $M_{\rm hh}$-dependence
shows negative asymmetry values in the region of the $\rho^{0}$ mass.

Figure 3: Hadron-pair transverse-spin-dependent asymmetries as a function of
$x$, $z$ and $M_{\rm{hh}}$, extracted from the full data set collected with
the NH3 (proton) target. Systematic uncertainties are shown by the gray bands.

For $K^{+}K^{-}$ pairs, the proton data show negative asymmetries in all three
variables, while the deuteron data show indications for a positive signal. In
particular the $M_{\rm{hh}}$-dependence shows opposite signs for the
asymmetries measured with the NH3 and 6LiD target, with an indication of a
mirror-symmetric shape. In the case of $\pi^{+}K^{-}$ and $K^{+}\pi^{-}$
pairs, the deuteron data show asymmetries compatible with zero, while the
proton data show slightly negative asymmetries.

The HERMES Collaboration measured TSAs for $\pi^{+}\pi^{-}$ pairs using
electron-proton scattering [15]. Given the wider kinematic coverage by
COMPASS, the $\pi^{+}\pi^{-}$ COMPASS asymmetry was re-evaluated in the region
$x>0.032$ to allow for a direct comparison. The comparison is shown in Fig. 4.
The results are in very good agreement within statistical uncertainties.

Figure 4: Comparison of $\pi^{+}\pi^{-}$ pair asymmetries measured by the
HERMES Collaboration [15] (blue open squares) with the results of the COMPASS
Collaboration re-evaluated in the $x>0.032$ region (black dots).

##  4 Interpretation of the results

The dihadron fragmentation functions entering the SIDIS cross section in Eq.
(1) are non-perturbative objects. As such, they can not be calculated from
first principles. Two classes of models have been proposed to describe them.
In spectator-jet type models a mechanism different from that of the Collins FF
is invoked to produce a non-vanishing $H_{1}^{\sphericalangle}$ function. Such
a mechanism involves the interference between the amplitudes of two competing
channels for the production of the hadron pair, e.g. either the amplitude for
direct production and the amplitude for resonance production [21, 20], or the
two amplitudes for the production of two different resonances [11]. A
different approach is followed by the recursive string+${}^{3}P_{0}$ model of
polarised quark fragmentation [22]. It is implemented in the StringSpinner
package [23] for the simulation of the Collins effect for pseudoscalar mesons
produced in the fragmentation of transversely polarised quarks in SIDIS with
the PYTHIA 8 event generator [24].

Figure 5: The string+${}^{3}P_{0}$ mechanism of polarised quark fragmentation
[25]. The closed (open) circles represent quark (antiquarks) at the string
ends. The circular arrows above quarks show the orientation of their spins
whereas the arrows at each string breaking $L_{2},L_{3}\dots$ represent the
orientation of the relative orbital angular momenta of the $q\bar{q}$ pairs.
The straight arrows indicate the quark transverse momenta.

The classical string+${}^{3}P_{0}$ model for the fragmentation of a
transversely polarised quark $q_{A}$ is illustrated in Fig. 5. The string is
stretched between the scattered quark $q_{A}$ and the target remnants along
the quark direction and the string fragmentation occurs via tunneling of
quark-antiquark pairs in the ${}^{3}P_{0}$ state, i.e. with spin $S=1$ and
relative orbital angular momentum $L=1$, such that the total angular momentum
$J$ is zero. Given the polarisation of $q_{A}$, taken here along the normal to
the figure plane, at the string breakings the spin and the transverse momentum
of the quark and antiquark, as well as the transverse momentum of the produced
hadron are fixed. The rank $r$ indicates how far the hadron $h_{r}$ is
produced from the fragmenting quark $q_{A}$, with $h_{1}$ being the hadron
which contains $q_{A}$. For odd (even) $r$ the hadron $h_{r}$ is emitted to
the left (right) with respect to the plane spanned by the momentum and
polarisation vectors of the fragmenting quark. As an example, if the flavor of
the fragmenting quark is $q_{A}=u$ and $h_{1}=\pi^{+}$, it can be
$h_{2}=\pi^{-}$ and opposite Collins asymmetries for oppositely charged
hadrons are generated. Also, a dihadron asymmetry with the same sign as for
positive hadrons is produced. StringSpinner uses the quantum mechanical
formulation of this model, in which the spin effects depend on a complex
parameter, tuned as in Ref. [23]. The initial quark polarisation is given by a
parametrisation of the transversity PDF for valence $u$ and $d$ quarks. For
this work we have used the default parametrisations, which were tuned to
reproduce the $\pi^{+}$ and $\pi^{-}$ Collins asymmetries measured by COMPASS
on an NH3 target. The simulations were performed neglecting the intrinsic
transverse momentum of the quarks, but it was checked that the dihadron
asymmetries are not affected [25].

Figure 6: Comparison between $\pi^{+}\pi^{-}$, $\pi^{+}K^{-}$, $K^{+}\pi^{-}$
and $K^{+}K^{-}$ asymmetries for proton data (closed points) and results from
simulations using StringSpinner (open points).

In Fig. 6 the measured dihadron asymmetries (closed points) are compared to
the simulated asymmetries (open points) for proton data. As can be seen, the
simulation describes the data particularly well for $\pi^{+}\pi^{-}$ and
$K^{+}K^{-}$ pairs, in all kinematic variables. The trend of the asymmetries
as a function of $x$ is mainly driven by the $x$-shape of the implemented
transversity PDFs. While the $z$ and $M_{\rm hh}$ dependences are predictions
of the model. The large signal for $\pi^{+}\pi^{-}$ and $K^{+}K^{-}$ pairs can
be understood in the approximation of $u$-quark dominance considering the fact
that $\pi^{+}$ or $K^{+}$ are most likely produced at rank one, whereas
$\pi^{-}$ or $K^{-}$ are produced at rank two. Regarding the $\pi^{+}K^{-}$
and $K^{+}\pi^{-}$ pairs, the simulated asymmetries are small and compatible
with the data within uncertainties. This is expected considering the fact
that, e.g., the $\pi^{+}$ and the $K^{-}$ of a $\pi^{+}K^{-}$ pair are most
likely produced at rank one and three separated by a rank two neutral kaon.
Thus the $\pi^{+}$ and the $K^{-}$ are most likely emitted on the same side
producing a small dihadron asymmetry.

In corresponding simulations for deuteron data, dihadron asymmetries
compatible with zero were found for all types of hadron pairs. This is in
agreement with the data and is expected from the fact that the transversity
PDFs for valence $u$ and $d$-quarks have almost the same size but opposite
sign.

##  5 Conclusions

In this paper we present the results of a new measurement of transverse-spin-
dependent asymmetries in hadron pair production in DIS of 160 $\rm{GeV}/c$
muons off transversely polarised deuteron (6LiD) and proton (NH3) targets. The
measurement covers all possible combinations of oppositely charged pions and
kaons observed in the COMPASS kinematic range.

The deuteron data used in the analysis were collected during $2002$ and
$2004$, while the proton data include two separate parts collected in 2007 and
2010. Both data sets were already used earlier to extract the Collins and
Sivers asymmetries for semi-inclusively measured single hadrons, with separate
publications for charged hadrons as well for identified pions and kaons. These
two data sets are the largest ones available on this process, including e.g.
28M (4M) pion pairs in the proton (deuteron) data, and they provide important
input for global analyses.

The proton data show significant non-zero asymmetries. For $\pi^{+}\pi^{-}$
pairs, values reach $-7\%$ in the region $x>0.032$ and $-2.5\%$ in the
invarinat-mass region around the $\rho^{0}$-meson mass. Slightly negative
asymmetries are observed for $K^{+}K^{-}$ and $K^{+}\pi^{-}$ pairs. The
deuteron data show for all hadron combinations asymmetries compatible with
zero, within statistical uncertainties.

## Acknowledgements

This work was made possible thanks to the financial support of our funding
agencies. We also acknowledge the support of the CERN management and staff, as
well as the skills and efforts of the technicians of the collaborating
institutes.

## References

  * [1] M. Anselmino, A. Mukherjee and A. Vossen, Prog. Part. Nucl. Phys. 114 (2020) 103806, arXiv:2001.05415 [hep-ph].
  * [2] J. C. Collins Nucl. Phys. B 396 (1993) 161–182, arXiv:hep-ph/9208213.
  * [3] HERMES Collaboration, A. Airapetian et al., Phys. Rev. Lett. 94 (2005) 012002, arXiv:hep-ex/0408013.
  * [4] COMPASS Collaboration, V. Alexakhin et al., Phys. Rev. Lett. 94 (2005) 202002, arXiv:hep-ex/0503002.
  * [5] COMPASS Collaboration, M. Alekseev et al., Phys. Lett. B 673 (2009) 127–135, arXiv:0802.2160 [hep-ex].
  * [6] COMPASS Collaboration, M. Alekseev et al., Phys. Lett. B 692 (2010) 240–246, arXiv:1005.5609 [hep-ex].
  * [7] COMPASS Collaboration, C. Adolph et al., Phys. Lett. B 717 (2012) 376–382, arXiv:1205.5121 [hep-ex].
  * [8] COMPASS Collaboration, C. Adolph et al., Phys. Lett. B 744 (2015) 250–259, arXiv:1408.4405 [hep-ex].
  * [9] COMPASS Collaboration CERN-SPSC:2017034 [SPSC-P-340-ADD-1].
  * [10] J. C. Collins, S. F. Heppelmann and G. A. Ladinsky, Nucl. Phys. B 420 (1994) 565–582, arXiv:hep-ph/9305309.
  * [11] R. L. Jaffe, X.-m. Jin and J. Tang, Phys. Rev. Lett. 80 (1998) 1166–1169, arXiv:hep-ph/9709322.
  * [12] A. Bianconi, S. Boffi, R. Jakob and M. Radici, Phys. Rev. D 62 (2000) 034008, arXiv:hep-ph/9907475.
  * [13] A. Bacchetta and M. Radici, Phys. Rev. D 67 (2003) 094002, arXiv:hep-ph/0212300.
  * [14] COMPASS Collaboration, C. Adolph et al., Phys. Lett. B713 (2012) 10–16, arXiv:1202.6150 [hep-ex].
  * [15] HERMES Collaboration, A. Airapetian et al., JHEP 06 (2008) 017, arXiv:0803.2367 [hep-ex].
  * [16] COMPASS Collaboration, C. Adolph et al., Phys. Lett. B 736 (2014) 124–131, arXiv:1401.7873 [hep-ex].
  * [17] COMPASS Collaboration, C. Adolph et al., Phys. Lett. B 753 (2016) 406–411, arXiv:1507.07593 [hep-ex].
  * [18] COMPASS Collaboration, P. Abbon et al., Nucl. Instrum. Meth. A 577 (2007) 455–518, arXiv:hep-ex/0703049.
  * [19] P. Abbon et al., Nucl. Instrum. and Meth. A631 (2011) no. 1, 26 – 39. http://www.sciencedirect.com/science/article/pii/S0168900210026422.
  * [20] A. Bacchetta and M. Radici, Phys. Rev. D 74 (2006) 114007, arXiv:hep-ph/0608037.
  * [21] J. C. Collins and G. A. Ladinsky, arXiv:hep-ph/9411444.
  * [22] A. Kerbizi, X. Artru, Z. Belghobsi and A. Martin, Phys. Rev. D100 (2019) no. 1, 014003, arXiv:1903.01736 [hep-ph].
  * [23] A. Kerbizi and L. Lönnblad, Comput. Phys. Commun. 272 (2022) 108234, arXiv:2105.09730 [hep-ph].
  * [24] T. Sjostrand, S. Mrenna and P. Z. Skands, JHEP05 (2006) 026, Comput. Phys. Commun. 178 (2008) 852–867, arXiv:0710.3820 [hep-ph].
  * [25] A. Kerbizi, X. Artru, Z. Belghobsi, F. Bradamante and A. Martin, Phys. Rev. D 97 (2018) no. 7, 074010, arXiv:1802.00962 [hep-ph].


# A syntactic approach to the MacNeille completion of $\Lambda^{\ast}$, the
free monoid over an ordered alphabet $\Lambda$.

Hans-Jürgen Bandelt  Fachbereich Mathematik, Universität Hamburg, Bundesstr.
55, D-20146 Hamburg, Germany<EMAIL_ADDRESS>and  Maurice Pouzet
Univ. Lyon, Université Claude Bernard Lyon 1, CNRS UMR 5208, Institut Camille
Jordan, 43 blvd. du 11 novembre 1918, F-69622 Villeurbanne cedex, France, and
Mathematics & Statistics Department, University of Calgary, Calgary, Alberta,
Canada T2N 1N4<EMAIL_ADDRESS>
###### Abstract.

Let $\Lambda^{\ast}$ be the free monoid of (finite) words over a not
necessarily finite alphabet $\Lambda$, which is equipped with some (partial)
order. This ordering lifts to $\Lambda^{\ast}$, where it extends the
divisibility ordering of words. The MacNeille completion of $\Lambda^{\ast}$
constitutes a complete lattice ordered monoid and is realized by the system of
”closed” lower sets in $\Lambda^{*}$ (ordered by inclusion) or its isomorphic
copy formed of the ”closed” upper sets (ordered by reverse inclusion). Under
some additional hypothesis on $\Lambda$, one can easily identify the closed
lower sets as the finitely generated ones, whereas it is more complicated to
determine the closed upper sets. For a fairly large class of ordered sets
$\Lambda$ (including complete lattices as well as antichains) one can generate
the closure of any upper set of words by means of binary operations (
”syntactic rules”) thus obtaining an efficient procedure to test closedness.
Closed upper set of words are involved in an embedding theorem for valuated
oriented graphs. In fact, generalized paths (so-called ”zigzags”) are encoded
by words over an alphabet $\Lambda$. Then the valuated oriented graphs which
are ”isometrically” embeddable in a product of zigzags have the characteristic
property that the words corresponding to the zigzags between any pair of
vertices form a closed upper set in $\Lambda^{*}$.

###### Key words and phrases:

Free monoid, MacNeille completion, syntactic rules, well-quasi-order, graph
distance, isometric embedding, zig-zag

###### 2010 Mathematics Subject Classification:

06A07,06A15,06D20,08B20, 68Q45

##  1\. Introduction

Our motivation for studying the MacNeille completion stems from distance-
preserving embeddings of graphs into products of path-like graphs. Here is an
outline of the embedding question. For undirected graphs there is a universal
embedding theorem, due independently to Quilliot [13, 14] and Nowakowski and
Rival [11]:

Every undirected graph $G$ isometrically embeds in a product of paths.

”Isometry” and ”product” certainly need a word of explanation. Isometry
requires preservation of the shortest path distance, that is, any two vertices
of $G$ are sent to two vertices at the same distance in the product. The
product in question is the _strong product_ , which is the canonical product
in the category of undirected graphs with loops; namely, two vertices in such
a product are adjacent if and only if all pairs of their corresponding
coordinates form edges (which may be loops). Now, for directed graphs (binary
relations with loops) the embedding question is more intricate. The strong
product one considers here is, of course, the direct product for reflexive
relations, but the potential factors are not just those directed graphs whose
symmetric closures constitute undirected paths (see Kabil and Pouzet [7]).
Distance and thus isometry have a natural meaning here, too – but one needs to
measure distances by sets of words over a two or three lettter alphabet rather
than numbers. The approriate notion of distance for directed graphs was
introduced by Quilliot [13] and is subsumed in the general approach taken by
Jawhari, Misane and Pouzet [5] and further developped by Pouzet and Rosenberg
[12]. Let us focus on the case of oriented graphs (with loops), i.e.,
reflexive antisymmetric binary relations as in this case a two letter alphabet
(distinguishing ’forward’ and ’backward’) will do: an oriented graph is a
directed graph in which every pair of vertices is linked by at most one arc.
The oriented analogues of undirected complete graphs, for instance, are the
tournaments. The oriented versions of undirected paths are called zigzags, see
Figure 1.

$a$$b$ Figure 1. A zigzag from $a$ to $b$

The distance from the initial to the terminal vertex of a zigzag is not just a
number (counting the edges) as in the undirected case but rather the isomorphy
class of its homomorphic zigzag pre-images, thus a subset of what we call the
ordered monoid of zigzags; this set consists of all zigzags (up to
isomorphism) ordered as follows: $P\leq Q$ if and only if there is an arc-
preserving mapping from the zigzag $Q$ onto the zigzag $P$ (which may collapse
vertices because of the ubiquity of loops). The multiplication is simply the
concatenation of zigzags. The singleton zigzag, i.e. the loop, is the least
element as well as the neutral element. Coding forward arcs by $"+"$ and
backward arcs by $"-"$ we can identify zigzags with words (i.e., finite
sequences) over the alphabet $\\{+,-\\}$. For example, the zigzag from $a$ to
$b$ shown in Figure 1 receives the code $+++--+--$ and the reverse zigzag from
$b$ to $a$ is coded by $++-++---$.

Hence the ordered monoid of zigzags is nothing else but the $2$-generated free
monoid $\\{+,-\\}^{\ast}.$ The ordering of $\\{+,-\\}^{\ast}$ is the subword
or divisibility ordering. Now, the distance $d(a,b)$ from vertex $a$ to vertex
$b$ in any oriented graph $G$ is the ”upper” subset of $\\{+,-\\}^{\ast}$
consisting of all words coding zigzags which map homomorphically to a
subzigzag of $G$ from $a$ to $b$. Every upper set $Z$ of $\\{+,-\\}^{\ast}$
(such that every word above some element of $Z$ belongs to $Z$) may occur as a
distance in some oriented graph except the set of all nonempty words. This
exception simply reflects the hypothesis of antisymmetry, for, if $+$ as well
as $-$ belong to $d(a,b)$, then we would get a double arc between $a$ and $b$
unless $a=b$. The set of all words (being the upper set generated by the empty
word) then constitutes the ”zero” distance.

An isometry (or isometric embedding) of $G$ into another oriented graph $H$ is
a mapping $f$ from $G$ to $H$ preserving distances, i.e.
$d(f(a),f(b))=d(a,b)$, and is necessarily injective and preserves arcs. The
isometric embedding in products of zigzags is governed by the Galois
connection induced by the ordering between zigzags (or words), viz., the
MacNeille completion of $\\{+,-\\}^{\ast}$. First observe that the ”lower
cone” $d(a,b)^{\nabla}$ formed by the words below all words in a distance
$d(a,b)$ of $G$ has an obvious interpretation: it consists of the words coding
zigzags $P$ for which there are arc-preserving mappings from $G$ onto $P$
sending $a$ and $b$ to the initial and terminal vertices of $P$, respectively.
So, if $a:=(a_{i})$ and $b:=(b_{i})$ are vertices in a product of zigzags,
then the words coding the zigzags from the $a_{i}^{\prime}s$ to the
$b_{i}^{\prime}s$ in the factors are exactly the members of the lower cone of
the distance from $a$ to $b$. This merely rephrases the universal property of
products in our category. Hence the distance from $a$ to $b$ in a product is a
”closed” upper set, and therefore every oriented graph $G$ which isometrically
embeds in such a product has MacNeille closed distances.

That the converse is also true, is affirmed by a (more general) result of
Jawhari, Misane and Pouzet [5], Proposition IV-4.1. This characterization is,
however, not yet completely satisfactory because of its partially extrinsic
nature: how would we check that a distance is closed other than by computing
the lower cone, which consists of the words coding potential zigzag factors?
Fortunately, there is an intrinsic way to verify closedness: assume $y+z$ and
$y-z$ are any two words in a distance $d(a,b)$ with common circumfix $y\ldots
z$ but different infix letters; then the common subword $yz$ must belong to
$d(a,b)$ whenever this distance is closed. We refer to this checking procedure
as the ”cancellation rule”. To give an example, assume that a closed upper set
$Z$ of words contains $+++$ and $---$. Then, as $Z$ is an upper set, we have
both $+-+-+$ and $--+-+$ in $Z$, whence $-+-+$ belongs to $Z$ by the
cancellation rule. Further, as $++-+$ is in $Z$, the rule applied to the
latter two words returns $+-+$, and since also $+++$ is in $Z$, so must be the
common subword $++$. Interchanging the roles of $+$ and $-$ we infer that $Z$
contains $--$. Repeating essentially the same argument for the words $++$ and
$--$ proves that $+$ and $-$ are words in $Z$, whence $Z$ contains the empty
word and thus is all of $\\{+,-\\}^{\ast}.$

The category of oriented graphs is not the only one where embeddability in
products of certain paths or zigzags can be characterized by closedness of
distances. Suitable coding schemes are then necessary in order to capture the
kind of adjacency relation for pairs of vertices. Consider, for instance,
undirected multigraphs (with loops of unbounded multiplicity) and mappings
that do not decrease the multiplicity of edges. Adjacency is coded by the
multiplicity of the corresponding edges, and thus the alphabet $\Lambda$ is
linearly ordered here (as the negative integers). If we want to deal with
arbitrary directed graphs (with loops), then the appropriate alphabet consists
of three letters $+,-,\sharp$ coding for backward, forward, and two-way arcs,
respectively. This alphabet is necessarily ordered so that the letter $\sharp$
is below $+$ and $-$, which exactly expresses the fact that a two-way arc
entails a forward and a backward arc; see Figure 2.

Figure 2. Ordered alphabets for undirected multigraphs and directed graphs,
respectively

This motivates the use of ordered alphabets. The ordering of letters extends
(freely) to an ordering of words, viz., the Higman ordering of
$\Lambda^{\ast}$ (refining the divisibility ordering). Then, with the right
notions of product and path/zigzag, we obtain analogous embedding theorems for
multigraphs and directed graphs.

The next section provides the necessary details on the free ordered monoid
$\Lambda^{\ast}$ (over an ordered alphabet $\Lambda$) and its MacNeille
completion. Under some additional assumption on $\Lambda$ the closed lower
sets of $\Lambda^{\ast}$ other than $\Lambda^{\ast}$ are exactly the lower
sets generated by finitely many words, see Section 3. A syntactical
description of the upper closure (in the MacNeille completion of
$\Lambda^{\ast}$) is established for particular classes of ordered sets
$\Lambda$ in Section 4 (see Theorem 4.4). This applies to the ordered
alphabets coding arcs in oriented graphs or multigraphs with bounded
multiplicity of edges, respectively, but not to the ordered alphabets
displayed in Figure 2.

##  2\. The free ordered monoid and its completion

An _alphabet_ is a not necessarily finite, ordered set $\Lambda$. Its elements
are _letters_ and denoted by small Greek letters
$\alpha,\beta,\gamma,\delta,\lambda$ etc. A finite sequence
$(\alpha_{1},\ldots,\alpha_{m})$ of letters is a _word_ of length $m$ and is
written as $\alpha_{1}\alpha_{2}\ldots\alpha_{m}$. The word of length $0$ is
the _empty_ word, denoted by $\Box$. The words of length $1$ are identified
with the corresponding letters. The concatenation of two words
$x:=\alpha_{1}\alpha_{2}\ldots\alpha_{m}$ and
$y:=\beta_{1}\beta_{2}\ldots\beta_{n}$ is the word $xy$ given by

$xy:=\alpha_{1}\alpha_{2}\ldots\alpha_{m}\beta_{1}\beta_{2}\ldots\beta_{n}.$

For each $i$ with $1\leq i\leq m$, the word $\alpha_{1}\ldots\alpha_{i}$ is a
prefix of $x=\alpha_{1}\ldots\alpha_{m}$ while the word
$\alpha_{i}\ldots\alpha_{m}$ is a _suffix_ of $x$.

The set $\Lambda^{\ast}$ of all words is a _monoid_ with respect to
concatenation, where the empty word is the neutral element. The order relation
of $\Lambda$, denoted by $\leq$, extends to $\Lambda^{*}$ in the following
way:

$x=\alpha_{1}\alpha_{2}\ldots\alpha_{m}\leq
y=\beta_{1}\beta_{2}\ldots\beta_{n}$

if and only if

$\alpha_{j}\leq\beta_{i_{j}}\ {\rm for\ all}\ j=1,\ldots m\;\text{with
some}\;1\leq i_{1}<\dots i_{m}\leq n.$

That is, $x$ is below $y$ in $\Lambda^{*}$ exactly when there exists a subword
$\beta_{i_{1}}\beta_{i_{2}}\ldots\beta_{i_{m}}$ of $y$ which is letter-wise
above $x$ (in the ordering of $\Lambda^{*}$). Then $\Lambda^{*}$ becomes an
ordered monoid (i.e., $x\leq y$ implies $xz\leq yz$ and $zx\leq zy$) in which
the empty word is the least element. The ordered monoid $\Lambda^{*}$ is
freely generated by the ordered set $\Lambda$, see [2], that is, $\Lambda^{*}$
is the free object in the category of ordered monoids (whose neutral elements
are also the least elements) and order-preserving homomorphisms.

The ordered monoid $\Lambda^{*}$ can be extended to a complete lattice ordered
monoid by applying the MacNeille completion. The necessary notation (cf.
Skornjakow [15]) is introduced next. Let $X$ be a subset of $\Lambda^{\ast}$;
then

$\uparrow X:=\\{y\in\Lambda^{\ast}:x\leq y\;\text{for some}\;x\in X\\}$

is the upper set generated by $X$ and

$\downarrow X:=\\{x\in\Lambda^{\ast}:x\leq y\;\text{for some}\;y\in X\\}$

is the lower set generated by $X$. Upper sets and lower sets are _finitely
generated_ if they are of the form $\uparrow X$, resp. $\downarrow X$ for some
finite set $X$. For a singleton $X=\\{x\\}$, we omit the set brackets and call
$\uparrow x$ and $\downarrow x$ a _principal upper set_ and a _principal lower
set_ , respectively. Then

$X^{\Delta}:=\bigcap_{x\in X}\uparrow x$

and

$X^{\nabla}:=\bigcap_{x\in X}\downarrow x$

are the upper cone and the lower cone respectively, generated by $X$.

The pair $(\Delta,\nabla)$ of mappings on $\powerset(\Lambda^{*})$, the power
set lattice of $\Lambda^{*}$, constitutes a Galois connection, yieldings the
_MacNeille completion_ of $\Lambda^{*}$. This completion is realized as the
complete lattice

$\\{W\subseteq\Lambda^{\ast}:W=W^{\Delta\nabla}\\}$

ordered by inclusion or its isomorphic copy

$\\{Y\subseteq\Lambda^{\ast}:Y=Y^{\nabla\Delta}\\}$

ordered by reverse inclusion. The members of those two sets are said to be
(MacNeille) _closed_. The set $\Lambda^{\ast}$ embeds into the former set via
$x\mapsto\downarrow x$ and into the latter via $x\mapsto\uparrow x$
($x\in\Lambda^{*}$).

To give an example, consider the alphabet $\Lambda:=\\{+,-\\}$ where $+$ and
$-$ are incomparable letters. Then:

$\\{-+-+-,+-+-+,+--+-\\}^{\nabla}=\;\downarrow\\{--+,+-+-\\}$

and

$\\{-\;-+,+-+-\\}^{\Delta}=\;\uparrow\\{-+-+-,+-+-+,+-\;-+-\\},$

showing that the latter upper set $\uparrow\\{-+-+-,+-+-+,+--+-\\}$ is closed.
In contrast, $\uparrow\\{+,-\\}$ is not closed since
$\\{+,-\\}^{\nabla\Delta}=\Lambda^{\ast}.$

The completion of $\Lambda^{*}$ inherits its monoid structure from the power
set, where the muliplication is given by

$XY:=\\{xy:x\in X,y\in Y\\}$

for any subsets $X$ and $Y$ of $\Lambda^{*}$. The cone operators preserve this
multiplication as the following lemma confirms.

######  Lemma 2.1.

For any subsets $X,Y$ of $\Lambda^{*}$,

$(XY)^{\nabla}=X^{\nabla}Y^{\nabla},\ {\rm and}\
(XY)^{\Delta}=X^{\Delta}Y^{\Delta}\;\text{if}\;X,Y\not=\emptyset,$

whence

$(XY)^{\nabla\Delta}=X^{\nabla\Delta}Y^{\nabla\Delta}\ {\rm and}\
(XY)^{\Delta\nabla}=X^{\Delta\nabla}Y^{\Delta\nabla}$

Proof.  First, observe that
$\emptyset^{\nabla}=\emptyset^{\Delta}=\Lambda^{*}$ and
$\Lambda^{*\Delta}=\emptyset$, while $\Lambda^{*\nabla}$ consists of the empty
word. Further, $\emptyset Z=Z\emptyset=\emptyset$ for every subset $Z$ of
$\Lambda^{*}$. The inclusions $X^{\nabla}Y^{\nabla}\subseteq(XY)^{\nabla}$ and
$X^{\Delta}Y^{\Delta}\subseteq(XY)^{\Delta}$ are then immediate.

Suppose that there exists a word $w$ in $(XY)^{\nabla}$ that does not belong
to $X^{\nabla}Y^{\nabla}$. Then let $u$ be the longest prefix of $w$ from
$X^{\nabla}$, and let $v$ be the longest suffix of $w$ from $Y^{\nabla}$ so
that $w$ is of the form

$w=u{\alpha_{1}}\ldots\alpha_{k}v$

for some letters $\alpha_{1},\ldots,\alpha_{k}$, where $k\geq 1$. By the
choice of $u$ and $v$, there are words $x\in X$ and $y\in Y$ such that

$u\alpha_{1}\not\leq x\ {\rm and}\ \alpha_{k}v\not\leq y.$

This, however, is in conflict with

$w=u\alpha_{1}\ldots\alpha_{k}v\leq xy.$

Therefore $(XY)^{\nabla}$ equals $X^{\nabla}Y^{\nabla}.$ Finally, suppose $z$
is a word in $(XY)^{\Delta}$ which does not belong to $X^{\Delta}Y^{\Delta}$,
where $X$ and $Y$ are nonempty. Then the shortest prefix of $z$ from
$X^{\Delta}$ and the shortest suffix of $z$ from $Y^{\Delta}$ intersect in a
nonempty subword

$w:=\alpha_{1}\ldots\alpha_{k}$

so that $z$ can be written as

$z=uwv\ {\rm with}\ uw\in X^{\Delta}\ {\rm and}\ wv\in Y^{\Delta}.$

By the choice of the words $u$ and $v$, we can find words $x\in X$ and $y\in
Y$ with

$x\not\leq u\alpha_{1}\ldots\alpha_{k-1}\ {\rm and}\ y\not\leq v.$

This contradicts the hypothesis that

$xy\leq z=u{\alpha_{1}}\ldots\alpha_{k-1}\alpha_{k}v.$

We conclude that $(XY)^{\Delta}=X^{\Delta}Y^{\Delta}$, completing the proof.

The completion of $\Lambda^{*}$, realized by the upper closed sets, is a
complete lattice in which suprema are set-theoretic intersections, whereas
infima are the closures of set-theoretic unions. The _closed union_ of a
family $Z_{i}\;(i\in I)$ of upper sets in $\Lambda^{*}$ is given by:

$\bigsqcup_{i\in I}Z_{i}=(\bigcup_{i\in I}Z_{i})^{\nabla\Delta}.$

The following result entails that the completion of $\Lambda^{*}$ is a
complete latttice ordered monoid (in the sense of Birkhoff [1]).

######  Proposition 2.2.

For any ordered alphabet $\Lambda$, the collection of all closed upper sets of
words over $\Lambda$ is a monoid and complete lattice such that the
multiplication distributes over intersection and closed unions, that is

$Y(\bigcap_{i\in I}Z_{i})=\bigcap_{i\in I}YZ_{i}\ {\rm and}\ (\bigcap_{i\in
I}Z_{i})Y=\bigcap_{i\in I}Z_{i}Y,$ $Y(\bigsqcup_{i\in I}Z_{i})=\bigsqcup_{i\in
I}YZ_{i}\ {\rm and}\ (\bigsqcup_{i\in I}Z_{i})Y=\bigsqcup_{i\in I}Z_{i}Y$

for any index set $I$ and all closed upper sets $Y,Z_{i}\;(i\in I).$

Proof.  Since $Y$ and all $Z_{i}$ are closed and $(\Delta,\nabla)$ is a Galois
connection, we have $Y=Y^{\nabla\Delta}$ and $\bigsqcup_{i\in
I}Z_{i}=(\bigcup_{i\in I}Z_{i})^{\nabla\Delta}=(\bigcap_{i\in
I}Z_{i}^{\nabla})^{\Delta}$. Analogous formulae hold for $Y^{\nabla}$ and
$Z_{i}^{\nabla}\;(i\in I)$. Hence by Lemma 2.1

$Y(\bigsqcup_{i\in I}Z_{i})=Y^{\nabla\Delta}(\bigcup_{i\in
I}Z_{i})^{\nabla\Delta}=[Y(\bigcup_{i\in I}Z_{i})]^{\nabla\Delta}=$
$=(\bigcup_{i\in I}YZ_{i})^{\nabla\Delta}=\bigsqcup_{i\in
I}(YZ_{i})^{\nabla\Delta}=\bigsqcup_{i\in
I}Y^{\nabla\Delta}Z_{i}^{\nabla\Delta}=\bigsqcup_{i\in I}YZ_{i}.$

Further

$Y(\bigcap_{i\in I}Z_{i})=Y^{\nabla\Delta}(\bigcap_{i\in
I}Z_{i})^{\nabla\Delta}=(Y^{\nabla}\bigcup_{i\in
I}Z_{i}^{\nabla})^{\Delta}=(\bigcup_{i\in
I}Y_{i}^{\nabla}Z_{i}^{\nabla})^{\Delta}=\bigcap_{i\in
I}Y^{\nabla\Delta}Z_{i}^{\nabla\Delta}=\bigcap_{i\in I}YZ_{i}.$

This settles left distributivity; the proof of right distributivity is
analogous.

Note that the collection of all closed upper sets of words over $\Lambda$ is
in fact a free monoid, see [8].

##  3\. Closed lower sets

In this section, we describe the closed lower sets. The characterization of
the closed upper sets is more involved and shall occupy us for the rest of the
next section.

Finiteness assumptions on the alphabet $\Lambda$ allow to argue by induction
or to obtain finite generation. $\Lambda$ is said to be well-founded (or to
satisfy the _descending chain condition_ , DCC for short, [1]) if $\Lambda$
does not contain any infinite decreasing chain
$\lambda_{0}>\lambda_{1}>\ldots.$ Then $\Lambda$ is called well-quasi-ordered
if $\Lambda$ is well-founded and has no infinite antichain (that is, contains
no infinite subset of pairwise incomparable elements). We recall a fundamental
result.

######  Theorem 3.1.

(Higman [3]) If $\Lambda$ is well-quasi-ordered then $\Lambda^{\ast}$ is well-
quasi-ordered too, whence the complete lattice of all lower sets of
$\Lambda^{\ast}$ is well-founded, which means that every upper set in
$\Lambda^{\ast}$ is finitely generated.

For a proof see also Nash-Williams [10] or Cohn [2]. For more information on
well-quasi-ordered sets, see the survey paper of Milner [9]. If $\Lambda$ is
well-quasi-ordered, then by virtue of Higman’s Theorem the MacNeille
completion of $\Lambda^{\ast}$ as realized within the complete lattice of all
lower sets is necessarily well-founded. However, this completion can be well-
founded even when $\Lambda$ contains infinite antichains. Well-founded dual
forests constitute pertinent examples, as will be seen next.

An ordered set $\Lambda$ is called an ordered tree if every principal lower
set of $\Lambda$ is a chain and $\Lambda$ is down-directed (that is, any two
elements of $\Lambda$ are bounded below). An ordered forest is a disjoint
union of ordered trees. The dual (alias _opposite_) of an ordered set is
obtained by reversing the order relation. Observe that the dual of an ordered
forest (a _dual forest_ , for short) is just an ordered set in which any two
incomparable elements are incompatible, i.e., not bounded below (Figure 3).

Figure 3. A (finite) dual forest

Consider an ordered set $\Lambda$ that is well-quasi-ordered and the dual of
an ordered forest. Since $\Lambda$ is well-founded, every element is above
some minimal element. Let $K$ be the subset of $\Lambda$ consisting of all
existing joins of minimal elements. Then, as $\Lambda$ has no infinite
antichain, $K$ is a dual finite forest. It is not difficult to see that
$\Lambda$ is the lexicographic sum of a family of ordinals indexed by $K$.
Note that adding a least element to $\Lambda$ (if necessary) results in a
complete lattice.

It will turn out (see Theorem 3.4 below) that the finitely generated lower
sets of $\Lambda^{\ast}$ together with $\Lambda^{\ast}$ are exactly the closed
lower sets in any well-founded dual forest $\Lambda$. Two lemmas are needed to
establish this.

######  Lemma 3.2.

Let $\Lambda$ be an ordered set. Then all (MacNeille) closed lower sets of
$\Lambda^{\ast}$ different from $\Lambda^{\ast}$ are finitely generated lower
sets if and only if $\Lambda$ is well-founded and the intersection of any two
principal lower sets of $\Lambda$ is a finitely generated lower set. Hence, in
this case, the MacNeille completion of $\Lambda^{\ast}$ is necessarily well-
founded.

Proof.  $\Lambda$ can be regarded as a lower set of
$\Lambda^{\ast}\setminus\\{\Box\\}$. Therefore, if $\Lambda^{\ast}$ is well-
founded, so is $\Lambda$. The intersection of any two principal lower sets in
$\Lambda$ is closed, whence this is a finitely generated lower set under the
asssumption that all closed lower sets in $\Lambda^{\ast}$ other than
$\Lambda^{\ast}$ be finitely generated. Restricting this intersection to
$\Lambda$ amounts to removing the empty word. This establishes necessity of
the conditions on $\Lambda$.

To prove the converse, assume that $\Lambda$ is well-founded such that any two
principal lower sets of $\Lambda$ intersect in a finitely generated lower set.
We extend the original alphabet $\Lambda$ to the set
$\overline{\Lambda}:=\Lambda\cup\\{\Box\\}$, where $\Box$ becomes the least
element of the extended alphabet. The set ${\overline{\Lambda}}^{\ast}$ of
words over $\overline{\Lambda}$ is the union of $\overline{\Lambda}^{n}$ for
all $n\geq 0$ (here the empty word is distinct from $\Box$). There is a
canonical map $\varphi$ from $\overline{\Lambda}^{\ast}$ onto $\Lambda^{\ast}$
which ”forgets” the empty letter $\Box$, viz., $\varphi$ maps the empty tuple
to ${\Box}$ and a nonempty tuple $x$ from $\overline{\Lambda}^{n}$( $n>0$) to
the concatenation of its coordinates with respect to the indexing order. For
instance, both tuples $(\Box,+,\Box,-)$ and $(+,-,\Box)$ from
$\overline{\\{+,-\\}}^{\ast}$ are mapped to $+-$ under $\varphi$. Thus, the
pre-images under $\varphi$ of a fixed word differ only in the number and
positions of the empty letter $\Box$. The map $\varphi$ obviously is a monoid
homomorphism such that for any two words $w$ and $x$ in $\Lambda^{\ast}$ we
have $w<x$ exactly when for each tuple $x^{\prime}$ in the pre-image of $x$
under $\varphi$ there exist a tuple $w^{\prime}$ in the pre-image of $w$ such
that $w^{\prime}<x^{\prime}$.

First, we claim that $\Lambda^{\ast}$ is well-founded because $\Lambda$ is.
Trivially, $\overline{\Lambda}$ is well-founded and hence so any of its finite
Cartesian powers $\overline{\Lambda}^{n}$ ($n>0$) by virtue of the pigeonhole
principle. If there was an infinite descending chain $x_{0}>x_{1}>x_{2}>\dots$
in $\Lambda^{\ast}$ starting with some word $x_{0}$ of length $n$, then we
could lift this chain to $\overline{\Lambda}^{n}$ by selecting
$x^{\prime}_{0}=x_{0}$ and successively choosing tuples in
$\overline{\Lambda}^{n}$ with
$x^{\prime}_{1}<x^{\prime}_{0},x^{\prime}_{2}<x^{\prime}_{1}$, etc., contrary
to the observation that $\overline{\Lambda}^{n}$ is well-founded.

Second, we assert that any two principal lower sets $\downarrow\\!\\!w$ and
$\downarrow\\!\\!x$ of $\Lambda^{\ast}$ intersect in a finitely generated
lower set. This is true in the particular case that $w$ and $x$ belong to
$\overline{\Lambda}$ because of the corresponding property assumed for the
alphabet $\Lambda$. If $w^{\prime}:=(w_{1},\dots,w_{n})$ and
$x^{\prime}:=(x_{1},\dots,x_{n})$ belong to $\overline{\Lambda}^{n}(n>0)$,
then $\downarrow\\!\\!w^{\prime}\;\cap\downarrow\\!\\!x^{\prime}$ is simply
the Cartesian product of $\downarrow\\!\\!w_{i}\;\cap\downarrow x_{i}$ for
$i=1,...n$, whence as a product of finitely generated lower sets of
$\overline{\Lambda}$ it is a finitely generated lower set of
$\overline{\Lambda}^{n}$. Now, if $w$ and $x$ are words of length at most $n$,
then we can take corresponding tuples $w^{\prime}$ and $x^{\prime}$ in
$\overline{\Lambda}^{n}$ which are mapped to $w$ and $x$ by $\varphi$. Since
$\varphi$ maps lower sets onto lower sets, we infer that $\downarrow
w\;\cap\downarrow x$ is a finitely generated lower set of $\Lambda^{\ast}$.

Third, we claim that for every finite subset $Z$ of
$\overline{\Lambda}^{\ast}$, the lower cone $Z^{\nabla}$ is a finitely
generated lower set. If $Z$ has cardinality at most $2$, this has just been
established. Now, by an induction hypothesis, for any $y$ in $Z$, there is a
finite antichain $X$ in $\Lambda^{\ast}$ such that
$(Z\setminus\\{y\\})^{\nabla}=\;\downarrow X$. Then
$\downarrow\\!X\;\cap\downarrow\\!\\!y$ equals the union of all
$\downarrow\\!\\!x\;\cap\downarrow\\!\\!y$ for $x$ from $X$ and thus is a
finitely generated lower set, as required.

Fourth, a result of Birkhoff [1], Theorem 2, p. 182, states that the set of
finitely generated lower sets of any well-founded ordered set $P$ is well-
founded. Hence, the set of finitely generated initial segments of
$\Lambda^{\ast}$ is well-founded. From this and the well foundedness of
$\Lambda^{\ast}$ we derive that every closed lower set $X$ other than
$\Lambda^{\ast}$ is finitely generated. Consider the collection of all lower
cones of the form $Z^{\nabla}$ where $Z$ is a finite subset of the upper cone
$X^{\Delta}$ (so that $X\subseteq Z^{\nabla}$). This collection is nonempty
because $X\neq\Lambda^{\ast}$, and it contains some minimal member
$Y^{\nabla}.$ Suppose we could find $w\in Y^{\nabla}\setminus X$. Then
$w\not\leq z$ for some $z\in X^{\Delta}$ because $X$ is closed. Now, by
minimality of $Y^{\nabla}$ we have

$w\in Y^{\nabla}=(Y\cup\\{z\\})^{\nabla}\subseteq\downarrow z,$

giving a contradiction. This completes the proof.

Note that every closed upper set of $\Lambda^{\ast}$ is of the form
$Y^{\nabla\Delta}$ for some finite subset $Y$ whenever the MacNeille
completion of $\Lambda^{\ast}$ is well-founded. Observe that
$Y^{\nabla\Delta}$ need not be a finitely generated upper set. Lemma 3.2
applies, in particular, to a well-founded conditional lattice $\Lambda$ (such
as a well-founded dual forest), yielding the finiteness conditions for the
MacNeille completion of $\Lambda^{\ast}$. Here we say that an ordered set
$\Lambda$ is a conditional lattice if it is obtained from a bounded lattice by
removing the bounds. In other words, $\Lambda$ is a conditional lattice if and
only if every pair of elements bounded below has a meet and every pair of
element bounded above has a join.

######  Lemma 3.3.

Let $\Lambda$ be an ordered set. Then every finitely generated lower set in
$\Lambda^{\ast}$ is (MacNeille) closed if and only if each pair of letters
from $\Lambda$ that is bounded below is also bounded above.

Proof.  Let $\alpha,\beta,\lambda$ be letters such that
$\lambda<\alpha,\lambda<\beta,$ but $\alpha,\beta$ do not have an upper bound.
Consider the lower set $W:=\downarrow\\{\alpha,\beta\\}$ in $\Lambda^{\ast}$.
Since $\\{\alpha,\beta\\}$ is not bounded above, every word above $\alpha$ and
$\beta$ is above $\alpha\beta$ or $\beta\alpha$. Hence
$W^{\Delta}=\uparrow\\{\alpha\beta,\beta\alpha\\}.$ Then the word
$\lambda\lambda$ belongs to $W^{\Delta\nabla}$ but not to $W$, showing that
$W$ is not closed.

Conversely assume that $\Lambda$ satisfies the condition of the lemma. Let
$w,x,y$ be words in $\Lambda^{\ast}$ such that $w$ does not belong to
$\downarrow\\{x,y\\}$, that is,

$w\not\leq x\ {\rm and}\ w\not\leq y.$

We claim that $w\not\in\\{x,y\\}^{\Delta\nabla}$, that is, there exists a word
$z$ such that

$x\leq z,y\leq z,{\rm and}\ w\not\leq z.$

Assume that $w=\alpha_{1}\ldots\alpha_{n}$ with $\alpha_{i}\in\Lambda$. Let
$x_{n}$ be the (possibly empty) largest suffix of $x$ consisting only of
letters not above $\alpha_{n}$. If $\alpha_{n}\not\leq x,$ then $x_{n}=x.$
Otherwise, there exists some $\beta_{n}\in\Lambda$ such that
$\alpha_{n}\leq\beta_{n}$ and $x$ is of the form $x=u\beta_{n}x_{n}$ for some
(possibly empty) word $u$. Then $n\geq 2$ and
$\alpha_{1}\ldots\alpha_{n-1}\not\leq u$. We continue as before, so that we
eventually obtain a representation of $x$ as

$x=x_{i}\beta_{i+1}x_{i+1}\ldots x_{n-1}\beta_{n}x_{n},$

where $1\leq i\leq n$, and

$\alpha_{k}\not\leq x_{k}\ {\rm for}\ i\leq k\leq n,$
$\alpha_{k}\leq\beta_{k}\ {\rm for}\ i<k\leq n.$

Then $\alpha_{i+1}\ldots\alpha_{n}$ is the largest suffix of $w$ that is below
some subword $\beta_{i+1}\ldots\beta_{n}$ of $x$, where in addition
$\beta_{i+1}\ldots\beta_{n}$ is the right-most subword of $x$ with this
property. Similarly, we have a representation

$y=y_{j}\gamma_{j+1}y_{j+1}\ldots y_{n-1}\gamma_{n}y_{n},$

where $1\leq j\leq n$, and

$\alpha_{k}\not\leq y_{k}\ {\rm for}\ j\leq k\leq n,$
$\alpha_{k}\leq\gamma_{k}\ {\rm for}\ j<k\leq n.$

We may assume that $i\leq j$. Now, by the condition on $\Lambda$, we can find
a letter $\lambda_{k}$ such that

$\beta_{k}\leq\lambda_{k}\ {\rm and}\ \gamma_{k}\leq\lambda_{k}\ {\rm
whenever}\ j\leq k\leq n.$

Put

$z=x_{i}\beta_{i+1}\ldots x_{j-1}\beta_{j}x_{j}y_{j}\lambda_{j+1}\ldots
x_{n-1}y_{n-1}\lambda_{n}x_{n}y_{n}.$

Then $x\leq z$ and $y\leq z$, but $w\not\leq z$ by the choice of the $x_{k}$
and $y_{k}.$ This proves the claim. Now, by a trivial induction we get that
for any words $w,x_{1},\ldots,x_{m}$ with $w\not\leq x_{k}$ for all $k$ there
exists a word $z$ such that $w\not\leq z$ and $x_{k}\leq z$ for all $k$. So,
if $X=\downarrow\\{x_{1},\ldots,x_{m}\\}$ is some finitely generated set and
$w\in\Lambda^{\ast}\setminus X$, then there exists $z\in\\{x_{1},\ldots
x_{m}\\}^{\Delta}$ such that $w\not\in\downarrow z$, that is, $w\not\in
X^{\Delta\nabla}.$ This proves that $X^{\Delta\nabla}\subseteq X$, whence $X$
is closed.

The preceding lemma covers the result of Jullien [4] for unordered finite
alphabets (i.e., in the case that $\Lambda$ is a finite antichain); see also
Kabil and Pouzet [6], Proposition 2.2.

Recall that a pair of elements $\alpha,\beta\in\Lambda$ is _compatible_ if
these elements have a common lower bound.

######  Theorem 3.4.

Let $\Lambda$ be an ordered set. Then the (MacNeille) closed lower sets of
$\Lambda^{\ast}$ form a well-founded lattice which exactly comprises
$\Lambda^{\ast}$ and all finitely generated lower sets if and only if
$\Lambda$ is well-founded and every compatible pair of (incomparable) elements
$\alpha,\beta\in\Lambda$ is bounded above and the common lower bounds of
$\alpha,\beta$ form a finitely generated lower set. In particular, the ordered
set $\Lambda$ obtained from some disjoint union of well-founded lattices by
removing the antichain of minimal elements is of this kind.

Proof.  From Lemma 3.2 we infer that every closed lower set
$W\neq\Lambda^{\ast}$ in $\Lambda^{\ast}$ is finitely generated. Conversely, a
finitely generated lower set of $\Lambda^{\ast}$ is closed by Lemma 3.3 since
$\Lambda$ satisfies the hypothesis of this Lemma.

##  4\. Closed upper sets

Given a set $Y$ of words over an ordered set $\Lambda$, we wish to build up
its closure $Y^{\nabla\Delta}$ by successively applying a few (partial) binary
operations and taking upper sets (which, of course, is governed by a family of
unary operations indexed by $\Lambda^{\ast}$). Certainly, one cannot
circumvent some finiteness condition on $Y$ as the MacNeille completion is
inherently infinitary. Since we reserve the name ”closed upper set” for
members of this completion, we say that $Z\subseteq\Lambda^{\ast}$ is stable
with respect to a partial operation $f$ defined on
$D(f)\subseteq\Lambda^{\ast}\times\Lambda^{\ast}$ if

$(x,x^{\prime})\in D(f)\bigcap(Z\times Z)\ {\rm implies}\ f(x,x^{\prime})\in
Z.$

######  Lemma 4.1.

Let $\Lambda$ be an ordered set. Then every closed upper set $Z$ in
$\Lambda^{\ast}$ is stable with respect to the four partial binary operations
”cancellation”, ”reduction”, ”permutation”, and ”meet”:

(cancellation rule) if $y\alpha z\in Z$ and $y\beta z\in Z$ where
$\alpha,\beta$ are incompatible letters (that is, not bounded below) and
$y,z\in\Lambda^{\ast}$, then $yz\in Z;$

(reduction rule) if $y\alpha\alpha z\in Z$ and $y\gamma z\in Z$ for
$\alpha<\gamma$ in $\Lambda$ and $y,z\in\Lambda$, then $y\alpha z\in Z;$

(permutation rule) if $y\alpha\beta z\in Z$ and $y\gamma z\in Z$ where
$\alpha,\beta,\gamma\in\Lambda$ and $y,z\in\Lambda^{\ast}$ such that
$\alpha,\beta$ are incomparable and below $\gamma$, then $y\beta\alpha z\in
Z;$

(meet rule) if $y\alpha z\in Z$ and $y\beta z\in Z$ such that
$\alpha,\beta\in\Lambda$ are incomparable letters with meet
$\alpha\wedge\beta$ in $\Lambda$ and $y,z\in\Lambda^{\ast}$, then
$y(\alpha\wedge\beta)z\in Z.$

Proof.  Let $u,v,y,z\in\Lambda^{\ast}$ such that $yuz,yvz\in Z.$ Then,
according to Lemma 2.1, we obtain

$\\{yuz,yvz\\}^{\nabla}=(y\\{u,v\\}z)^{\nabla}=(\downarrow
y)\\{u,v\\}^{\nabla}(\downarrow z)$

and hence

$\\{yuz,yvz\\}^{\nabla\Delta}=(\uparrow y)\\{u,v\\}^{\nabla\Delta}(\uparrow
z).$

Since $Z$ is a closed upper set, the preceding upper cone in included in $Z$,
that is,

$ywz\in Z\;\text{ for all}\;w\in\\{u,v\\}^{\nabla\Delta}.$

This applies to each of the four asserted rules. In each case the closure of
$\\{u,v\\}$ is readily determined: if $\alpha$ and $\beta$ are incompatible,
then $\\{\alpha,\beta\\}^{\nabla\Delta}=\Lambda^{\ast}$; and if
$\alpha\wedge\beta$ exists then
$\\{\alpha,\beta\\}^{\nabla\Delta}=\uparrow(\alpha\wedge\beta).$ For
$\alpha<\beta$ we get
$\\{\alpha\alpha,\beta\\}^{\nabla\Delta}=\uparrow\alpha.$ Finally, if $\alpha$
and $\beta$ are incomparable such that $\alpha,\beta<\gamma$, then

$\\{\alpha\beta,\gamma\\}^{\nabla\Delta}=(\downarrow\alpha\;\cup\downarrow\beta)^{\Delta}=\\{\alpha,\beta\\}^{\Delta}=(\uparrow\alpha\;\cap\uparrow\beta\cap\Lambda)\;\cup\uparrow\\{\alpha\beta,\beta\alpha\\},$

which equals $\uparrow\\{\alpha\beta,\beta\alpha,\alpha\vee\beta\\}$ whenever
the join $\alpha\vee\beta$ exists. This completes the proof of the lemma.

The final argument in the preceding proof actually yields an extension of the
permutation rule that also entails the reduction rule, viz.

(permuto-reduction rule) if $y\alpha\beta z\in Z$ and $y\gamma z\in Z$ where
$\alpha,\beta,\gamma\in\Lambda$ and $y,z\in\Lambda^{\ast}$ such that
$\alpha,\beta$ are incomparable and below $\gamma$, then $y\beta\alpha z\in Z$
and $y\delta z\in Z$ for all $\delta\in\Lambda$ with $\alpha,\beta<\delta.$

One can also derive the second assertion in this rule from the reduction rule:
if $\alpha,\beta<\delta<\gamma$ such that $y\alpha\beta z\in Z$ and $y\gamma
z\in Z$ then $y\delta\delta z\in Z$ and hence $y\delta z\in Z$ by the
reduction rule.

The cancellation rule and the meet-rule can be regarded as a single rule with
respect to the meet in $\Lambda^{\ast}$:

(extended meet rule) if $y\alpha z\in Z$ and $y\beta z\in Z$ such that
$\alpha,\beta\in\Lambda$ are incomparable letters such that their meet $w$ in
$\Lambda^{\ast}$ exists, then $ywz\in Z.$

In fact, this meet exists exactly when $\alpha$ and $\beta$ either are
incompatible (so that $w=\Box$) or have a meet $w=\alpha\wedge\beta$ in
$\Lambda$. Hence, any two incomparable letters have a meet in $\Lambda^{\ast}$
if and only if $\Lambda$ is a conditional meet-semilattice, that is, every
pair of compatible elements (i.e., bounded below) has a meet.

######  Lemma 4.2.

Let $\Lambda$ be a conditional meet-semilattice. An upper set $Z$ in
$\Lambda^{\ast}$ is stable with respect to cancellation, reduction,
permutation, and meet precisely when $Z$ obeys the following ”compound” rule :
if $y\alpha_{1}\ldots\alpha_{n}z\in Z(n\geq 1)$ and $y\beta z\in Z$ such that
$y,z\in\Lambda^{\ast}$ and $\alpha_{i},\beta\in\Lambda$ with
$\beta\not\leq\alpha_{i}$ for all $i$, then $ytz\in Z$ where $t$ is a word
(possibly empty) formed by the maximal elements of
$\\{\alpha_{i}\wedge\beta\;:i=1,\ldots,n\;\text{such that
}\;\alpha_{i}\wedge\beta\;\text{exists}\\}$ in any order.

Proof.  Evidently the rules described in Lemma 4.1 are particular instances of
the compound rule. To prove the converse, assume first that there is some
letter $\alpha_{i}$ incompatible with $\beta$. Then, as $Z$ is an upper set
containing $y\beta z$, the word
$y\alpha_{1}\ldots\alpha_{i-1}\beta\alpha_{i+1}\ldots\alpha_{n}z$ belongs to
$Z$, whence so does
$y\alpha_{1}\ldots\alpha_{i-1}\alpha_{i+1}\ldots\alpha_{n}z$ by virtue of the
cancellation rule. Continuing this way we can eliminate all letters
$\alpha_{i}$ from the subword $\alpha_{1}\ldots\alpha_{n}$ in
$y\alpha_{1}\ldots\alpha_{n}z$ that are incompatible with $\beta$, thus
resulting in $y\lambda_{1}\ldots\lambda_{k}z\in Z$ where
$\lambda_{1}\ldots\lambda_{k}$ is a subword of $\alpha_{1}\ldots\alpha_{n}.$
Since $y\lambda_{1}\ldots\lambda_{k-1}\beta z\in Z$, the meet rule gives
$y\lambda_{1}\ldots\lambda_{k-1}(\lambda_{k}\wedge\beta)z\in Z.$ Iterating
this argument yields $y\mu_{1}\ldots\mu_{k}z\in Z$ with
$\mu_{i}=\lambda_{i}\wedge\beta$ for all $i$. In a similar way we successively
apply the reduction and permutation rules: as every permutation of a word is
the composition of transpositions interchanging two consecutive letters, it
suffices to manipulate the letters $\mu_{i},\mu_{i+1}$ for $i=1,\ldots,k-1.$
If $\mu_{i}\leq\mu_{i+1}$, then both
$y\mu_{1}\ldots\mu_{i-1}\mu_{i+1}\mu_{i+1}\ldots\mu_{k}z$ and
$y\mu_{1}\ldots\mu_{i-1}\beta\mu_{i+2}\ldots\mu_{k}z$ belong to $Z$, whence
$y\mu_{1}\ldots\mu_{i-1}\mu_{i+1}\ldots\mu_{k}z$ by the reduction rule. If
$\mu_{i}\not\leq\mu_{i+1},$ then the permutation rule guarantees
$y\mu_{1}\ldots\mu_{i-1}\mu_{i+1}\mu_{i}\mu_{i+2}\ldots\mu_{k}z\in Z.$ This
finally, shows that $ytz$ is in $Z.$

The next lemma we need is the analogue of Lemma 2.1 for stable sets.

######  Lemma 4.3.

If $U$ and $V$ are two upper sets that are stable with respect to
cancellation, reduction, permutation, and meet, then the concatenation $UV$ is
stable as well.

Proof.  Let $s,y,z\in\Lambda^{\ast}$ and $\lambda\in\Lambda$ such that $ysz$
and $y\lambda z$ are words for which the compound rule, say, would return the
word $ytz$. Assume $ysz,y\lambda z\in UV.$ We wish to show that $ytz\in UV.$
Since $U,V$ are upper sets, we infer from $y\lambda z\in UV$ either $y\in U$
or $z\in V$; say, the latter holds. If $y\in U$, then $yt\in U$ and hence
$ytz\in UV.$ So assume that $y$ does not belong to $U.$ Let $v$ be the
shortest suffix of $z$ belonging to $V$ such that $z$ is of the form $xv$ with
$y\lambda x\in U$. Then, by the minimal choice of $v$, the word $ysx$ belongs
to $U$ as well (because $U$ is an upper set) and hence $ytx\in U$ as $U$ is
stable. We conclude that $ytz=ytxv\in UV$, as required.

We are now in position to prove the main theorem. For every subset $Y$ of
$\Lambda^{\ast}$ let $[Y]$ denote the smallest upper set of words which
contains $Y$ and is stable with respect to cancellation, reduction,
permutation, and meet (as described in Lemma 4.1). Then by this lemma we have
$[Y]\subseteq Y^{\nabla\Delta}.$

######  Theorem 4.4.

Let $\Lambda$ be an ordered set in which any two elements bounded below have a
meet and an upper bound. Then for every finite nonempty subset $Y$ of
$\Lambda^{\ast}$ the smallest closed upper set and the smallest stable upper
set containing $Y$ coincide: $Y^{\nabla\Delta}=[Y].$ If, in addition,
$\Lambda$ is well-founded, then the closed upper sets of $\Lambda^{\ast}$ are
exactly the stable upper sets.

Proof. We will show that $[Y]$ is closed for all finite nonempty sets
$Y\subseteq\Lambda^{\ast}$ by induction. To this end, define the total lenght
$\parallel\\!\\!Y\\!\\!\parallel$ of $Y$ as the sum of the lengths of the
words in $Y$. If $\parallel\\!\\!Y\\!\\!\parallel=0$, that is, $Y$ consists
only of the empty word, then we get $[Y]=\Lambda^{\ast}$. So let
$n=\parallel\\!\\!Y\\!\\!\parallel\;\geq 1$, and assume that $[X]$ is closed
for all nonempty sets $X\subseteq\Lambda^{\ast}$ with
$\parallel\\!\\!X\\!\\!\parallel\;<n.$ If $Y$ is not an antichain, then
$\uparrow Y=\;\uparrow X$ for some proper subset $X$ of $Y$ (giving
$\parallel\\!\\!X\\!\\!\parallel<\parallel\\!\\!Y\\!\\!\parallel$), whence
$[Y]=[X]$ is closed by the induction hypothesis. Therefore we can assume that
$Y$ is an antichain. We aim at representing $Z:=[Y]$ as an intersection of
concatenations of stable upper sets to which the induction hypothesis applies.

Consider the set $K$ of front letters (i.e., prefixes of length $1$) of the
words in $Y$. For $\delta\in K$ and any $W\subseteq\Lambda^{\ast}$ let
$W_{\delta}$ be the set of words obtained from $W$ by cancelling all front
letters $\delta$, that is, $x\in W_{\delta}$ if and only if either $\delta
x\in W$, or $x\in W$ and $\delta$ is not a prefix of $x$. In case that $W$ is
an upper set we simply have $W_{\delta}=\\{x\in\Lambda^{\ast}:\delta x\in
W\\}.$ It is easy to see (by putting $\delta$ in front of all words in
question) that each $W_{\delta}$ is a stable upper set whenever $W$ is a
stable upper set. In particular, $Z_{\delta}$ is a stable upper set containing
$Y_{\delta}$ (for $\delta\in K$). Therefore, as $Z$ is an upper set and
$\uparrow Y\subseteq\;\uparrow Y_{\delta}$ holds, we obtain the following
inclusions

$(\uparrow\delta)Z_{\delta}\subseteq Z=[Y]\subseteq[Y_{\delta}]\subseteq
Z_{\delta}\;\text{for all}\;\delta\in K.$

Furthermore,
$\parallel\\!\\!Y_{\delta}\\!\\!\parallel<\parallel\\!\\!Y\\!\\!\parallel$,
and consequently $[Y_{\delta}]$ is closed by virtue of the induction
hypothesis. These facts will be used in each of the subsequent cases (without
explicit mention).

Case 1. $K$ is a singleton $\\{\delta\\}.$
This means that all words in $Y$ have the letter $\delta$ in front, that is,
$Y=\delta Y_{\delta}$. Since the concatenation of stable upper sets is a
stable upper set by Lemma 4.3, it follows

$(\uparrow\delta)Z_{\delta}\subseteq Z=[\delta
Y_{\delta}]\subseteq(\uparrow\delta)[Y_{\delta}]\subseteq(\uparrow\delta)Z_{\delta},$

and thus equality holds throughout. Then $Z=(\uparrow\delta)[Y_{\delta}]$ is
closed by Lemma 2.1.

Case 2.  $K$ is not bounded below in $\Lambda.$
Let $\lambda$ be the meet of a maximal subset of $K$. Then there is a letter
$\mu$ in $K$ incompatible with $\lambda$. Now if
$x\in\displaystyle\bigcap_{\delta\in K}Z_{\delta}$, then $\delta x\in Z$ for
all $\delta\in K.$ Applying the meet rule several times, we eventually get
$\lambda x\in Z.$ Since $\mu x\in Z$, the cancellation rule returns $x\in Z$,
thus proving that $Z$ contains the intersection of all $Z_{\delta}$
($\delta\in K$). On the other hand, we already know that

$Z\subseteq\displaystyle\bigcap_{\delta\in
K}[Y_{\delta}]\subseteq\displaystyle\bigcap_{\delta\in K}Z_{\delta}.$

Therefore $Z$ equals the intersection of all $[Y_{\delta}](\delta\in K)$ and
hence is closed.

Case 3.  $K$ is not a singleton, but bounded below.
Then the meet $\alpha$ of $K$ in $\Lambda$ exists, and the hypothesis on
$\Lambda$ guarantees an upper bound $\beta$ of $K$. Necessarily,
$\alpha<\beta.$ Remove the front letters from all words in $Y$, which results
in the set

$Y_{K}=\\{x\in\Lambda^{\ast}:\delta x\in Y\;\text{for some}\;\delta\in
K\\}=\bigcup_{\delta\in K}Y_{\delta}.$

Since
$\parallel\\!\\!Y_{\delta}\\!\\!\parallel<\parallel\\!\\!Y\\!\\!\parallel$,
the stable set $[Y_{K}]$ must be closed. Note that

$Y\subseteq(\uparrow\alpha)Y_{K}\ {\rm and}\ Y_{K}\subseteq Z_{\beta}$

as $\alpha\leq\delta\leq\beta$ for all $\delta\in K.$ Hence, by Lemma 4.3,

$Z\subseteq[(\uparrow\alpha)Y_{K}]\subseteq(\uparrow\alpha)[Y_{K}]\subseteq(\uparrow\alpha)Z_{\beta}.$

Now, applying the meet rule successively, we get $\alpha x\in Z$ whenever
$\delta x\in Z$ for all $\delta\in K$ (where $x\in\Lambda^{\ast}$). Therefore

$Z\subseteq\displaystyle\bigcap_{\delta\in\Lambda}[Y_{\delta}]\subseteq\displaystyle\bigcap_{\delta\in\Lambda}Z_{\delta}\subseteq
Z_{\alpha}.$

Combining both chains of inclusions yields

$Z\subseteq\displaystyle\bigcap_{\delta\in
K}[Y_{\delta}]\cap((\uparrow\alpha)[Y_{K}])\subseteq
Z_{\alpha}\cap((\uparrow\alpha)Z_{\beta}).$

To prove the converse inclusion, assume $x\in
Z_{\alpha}\cap((\uparrow\alpha)Z_{\beta}).$ Then $\alpha x\in Z$ and $x=wy$
for some word $w\geq\alpha$ and $y\in Z_{\beta}$. If $w\geq\beta$, then $x\in
Z$ follows immediately. So, let $\beta\not\leq w$. Writing $w=u\gamma v$ with
$u,v\in\Lambda^{\ast}$ and a letter $\gamma\geq\alpha$, we have $\alpha
u\gamma vy\in Z$ and $\beta y\in Z.$ Now we can apply the compound rule
(according to Lemma 4.2) and thus obtain
$u^{\prime}(\beta\wedge\gamma)v^{\prime}y\in Z$, where $u^{\prime}$ and
$v^{\prime}$ are some words below $u$ resp. $v$ (and only comprising letters
below $\beta$) and $\alpha$ got removed because $\alpha\leq\beta\wedge\gamma$.
Hence $x=u\gamma vy\in Z$, as required. Hence $Z$ is equal to the intersection
of all $[Y_{\delta}]$ with $(\uparrow\alpha)[Y_{K}].$ Since the latter set is
closed by Lemma 4.3, so is $Z$.

This completes the induction and thus establishes the equality of $[Y]$ and
$Y^{\nabla\Delta}$ for all finite nonempty sets of words. These sets
$Y^{\nabla\Delta}$ exhaust all closed upper sets when $\Lambda$ is well-
founded. Indeed, in that case, the MacNeille completion of $\Lambda^{*}$ is
well-founded by Lemma 3.2.

Some of the four rules for generating the smallest stable upper set may become
redundant in the case of particular alphabets. Specifically, we have the
following consequence of Theorem 4.4.

######  Corollary 4.5.

Let $\Lambda$ be a well-founded ordered set in which every (finite) subset
bounded below has its meet and join in $\Lambda$. Then

  1. (a)

$\Lambda$ is a lattice,

  2. (b)

$\Lambda$ is a dual forest,

  3. (c)

$\Lambda$ is a disjoint union of chains,

  4. (d)

$\Lambda$ is a chain, or

  5. (e)

$\Lambda$ is an antichain, respectively,

if and only if the closed upper sets of $\Lambda^{\ast}$ are exactly the upper
sets obeying the

  1. (a)

reduction, permutation, and meet rules,

  2. (b)

cancellation, reduction, and permutation rules,

  3. (c)

cancellation and reduction rules,

  4. (d)

reduction rule, or

  5. (e)

cancellation rule, respectively.

Proof.  Necessity is clear. As to sufficiency, consider sets of the form

$(a)$ $\uparrow\\{\alpha,\beta\\}$ where $\alpha,\beta$ are incompatible,

$(b)$ $\uparrow\\{\alpha,\beta\\}$ where $\alpha,\beta$ are incomparable, but
bounded,

$(c)$ $\uparrow\\{\alpha\vee\beta,\alpha\beta\\}$ where $\alpha,\beta$ are
incomparable,

$(e)$ $\uparrow\\{\alpha\alpha,\beta\\}$ for $\alpha<\beta$, respectively.

In each case, the upper set as described is not closed, but obeys the
corresponding subset of rules. Finally, (d) follows from (a) and (c).

######  Conjecture 4.6.

Let $\Lambda$ be a well-founded conditional lattice. Then an upper set $Z$ of
$\Lambda^{\ast}$ is closed if and only if it satisfies the four rules.

We do not even have a proof of this assertion in the simplest case of a
$3$-letter alphabet $\Lambda=\\{\lambda,\mu,\nu\\}$ with $\nu<\lambda$ and
$\nu<\mu$ ($\lambda,\mu$ being incomparable) so that $\nu=\lambda\wedge\mu.$

Theorem 4.4 does not apply to the ordered alphabets displayed in Figure 2. So,
we have not yet achieved a thorough understanding of the MacNeille completion
of all free ordered monoids. It would also be interesting to characterize the
closed upper sets of $\Lambda^{\ast}$ without imposing any condition on
$\Lambda$; then, of course, finitary rules are no longer sufficient:

######  Problem 4.7.

Characterize the closed upper sets of $\Lambda^{\ast}$ for an arbitrary
ordered set $\Lambda.$

##  5\. Final remark

Originally, the main motivation for the description of upper sets belonging to
the MacNeille completion by means of syntactic rules was to characterize
absolute retracts among oriented graphs. The difficulty of a characterization
is due to the fact that, in general, not every oriented graph (e.g., an
oriented cycle) is isometrically embeddable in an absolute retract in the
category of oriented graphs (that is, a graph which is a retract of all its
isometric extensions). Our main result, Theorem 4.4, entails that on a two-
letter alphabet $\Lambda:=\\{+,-\\}$, closed sets are characterized by the
satisfaction of the cancellation rule. This allows to characterize among
oriented graphs those which are absolute retracts in the category of oriented
graphs. Indeed, it turns out that these graphs are simply the retracts of
products of oriented zigzags. This result, as well as others in the same vein,
obtained in collaboration with F. Saïdane, will be developped in a forthcoming
paper.

## Acknowledgement

The second author thanks the members of the Mathematical Department of the
University of Hamburg for their hospitality in February 2016, and the first
author is grateful to the Camille Jordan Institute for a visit in August 2017.

The authors are pleased to thank the referee for his very careful reading.

## References

  * [1] G. Birkhoff: Lattice theory. Corrected reprint of the 1967 third edition. American Mathematical Society Colloquium Publications, 25. American Mathematical Society, Providence, R.I., 1979. vi+418 pp.
  * [2] P.M. Cohn: Universal algebra. Second edition. Mathematics and its Applications, 6. D. Reidel Publishing Co., Dordrecht-Boston, Mass., 1981. xv+412.
  * [3] G. Higman: Ordering by divisibility in abstract algebra, Proc. London Math. Soc (3) 2 (1952), 326-336.
  * [4] P. Jullien: Sur un théorème d’extension dans la théorie des mots, C. R. Acad. Sci. Paris Sér. A-B 266 (1968) A851-A854.
  * [5] E. Jawhari, D. Misane, M. Pouzet: Retracts: graphs and ordered sets from the metric point of view, (I.Rival, ed.) Contemporary Mathematics, Vol 57 (1986), 175-226.
  * [6] M. Kabil, M. Pouzet: Une extension d’un théorème de P.Jullien sur les âges de mots, Theoretical Informatics and Applications. Vol 26, n∘5, (1992), 449-482.
  * [7] M. Kabil, M. Pouzet: Injective envelope of graphs and transition systems, Discrete Math. 192 (1998), no. 1-3, 145-186.
  * [8] M. Kabil, M. Pouzet, I.G. Rosenberg: Free monoids and generalized metric spaces, Europ. J. Combinatorics, (2018), https://doi.org/10.1016/j.ejc.2018.02.008.
  * [9] E.C. Milner: Basic wqo- and bqo-theory, in Graphs and order (Banff, Alta., 1984), pp. 487-502, Reidel, Dordrecht, 1985.
  * [10] C.St.J.A. Nash-Williams: On well-quasi-ordering finite trees.  Proc. Cambridge Philos. Soc. 59 (1963), 833-835, .
  * [11] R. Nowakowski, I. Rival: The smallest graph variety containing all paths, Discrete Math. 43 (1983), 185-198.
  * [12] M. Pouzet, I.G. Rosenberg: General metrics and contracting operations, Discrete Math. 130 (1994), 103-169.
  * [13] A. Quilliot: Homomorphismes, points fixes, rétractions et jeux de poursuite dans les graphes, les ensembles ordonnés et les espaces métriques, Thèse de doctorat d’Etat, Univ. Paris VI (1983).
  * [14] A. Quilliot: An application of the Helly property to the partially ordered sets, J. Combin. Theory, Series A, 35 (1983), 185-198.
  * [15] L.A. Skornjakow: Elemente der Verbandstheorie, 1973, Akademie-Verlag, Berlin.