1621 LABEL:LastPageSep. 17, 2018Apr. 01, 2020

# An Integrated First-Order Theory of Points and Intervals over Linear Orders
(Part II)

Willem Conradiea  aSchool of Mathematics, University of Witwatersrand
Johannesburg, South Africa<EMAIL_ADDRESS>,  Salih Durhanb  bD4C
Research and Development
Istanbul, Turkey<EMAIL_ADDRESS>and  Guido Sciaviccoc  cDepartment of
Mathematics and Computer Science
University of Ferrara
Ferrara, Italy<EMAIL_ADDRESS>
###### Abstract.

There are two natural and well-studied approaches to temporal ontology and
reasoning: point-based and interval-based. Usually, interval-based temporal
reasoning deals with points as a particular case of duration-less intervals. A
recent result by Balbiani, Goranko, and Sciavicco presented an explicit two-
sorted point-interval temporal framework in which time instants (points) and
time periods (intervals) are considered on a par, allowing the perspective to
shift between these within the formal discourse. We consider here two-sorted
first-order languages based on the same principle, and therefore including
relations, as first studied by Reich, among others, between points, between
intervals, and inter-sort. We give complete classifications of its sub-
languages in terms of relative expressive power, thus determining how many,
and which, are the intrinsically different extensions of two-sorted first-
order logic with one or more such relations. This approach roots out the
classical problem of whether or not points should be included in a interval-
based semantics. In this Part II, we deal with the cases of all dense and the
case of all unbounded linearly ordered sets.

###### Key words and phrases:

Interval based temporal logics; expressivity; Allen’s relations

###### 1991 Mathematics Subject Classification:

[Theory of computation]: Logic — Modal and temporal logics; [Computing
methodologies]: Artificial intelligence — Knowledge representation and
reasoning — Temporal reasoning

The research of the first author was partially supported by grant number 81309
of the South African National Research Foundation.

We would like to thank Dr. Davide Bresolin, of the University of Padova, for
his help. This paper is the second part of a 2-parts paper.

##  1\. Introduction

The relevance of temporal logics in many theoretical and applied areas of
computer science and AI, such as theories of action and change, natural
language analysis and processing, and constraint satisfaction problems, is
widely recognized. While the predominant approach in the study of temporal
reasoning and logics has been based on the assumption that time points
(instants) are the primary temporal ontological entities, there has also been
significant activity in the study of interval-based temporal reasoning and
logics over the past two decades. The variety of binary relations between
intervals in linear orders was first studied systematically by Allen [AH87,
All83, AF94], who explored their use in systems for time management and
planning. Allen’s work and much that follows from it is based on the
assumption that time can be represented as a dense line, and that points are
excluded from the semantics. At the modal level, Halpern and Shoham [HS91]
introduced the multi-modal logic HS that comprises modal operators for all
possible relations (known as Allen’s relations [All83]) between two intervals
in a linear order, and it has been followed by a series of publications
studying the expressiveness and decidability/undecidability and complexity of
the fragments of HS, e.g., [BMM+14, BMG+14]. Many studies on interval logics
have considered the so-called ‘non-strict’ interval semantics, allowing point-
intervals (with coinciding endpoints) along with proper ones, and thus
encompassing the instant-based approach, too; more recent ones, instead,
started to treat pure intervals only. Yet, little has been done so far on the
formal treatment of both temporal primitives, points and intervals, in a
unified two-sorted framework. A detailed philosophical study of both
approaches, point-based and interval-based, can be found in [vB91] (see also
[CM00]). A similar mixed approach has been studied in [AH89]. [MH06] contains
a study of the two sorts and the relations between them in dense linear
orders. More recently, a modal logic that includes different operators for
points and interval has been presented in [BGS11].

The present paper provides a systematic treatment of point and interval
relations (including equality between points and between intervals treated on
the same footing as the other relations) at the first-order level. Our work is
motivated, among other observations, by the fact that natural languages
incorporate both ontologies on a par, without assuming the primacy of one over
the other, and have the capacity to shift the perspective smoothly from
instants to intervals and vice versa within the same discourse, e.g.: when the
alarm goes on, it stays on until the code is entered, which contains two
instantaneous events and a non-instantaneous one. Moreover, there are various
temporal scenarios which neither of the two ontologies alone can grasp
properly since neither the treatment of intervals as the sets of their
internal points, nor the treatment of points as ‘instantaneous’ intervals, is
really adequate. The technical identification of intervals with sets of their
internal points, or of points as instantaneous intervals leads also to
conceptual problems like the confusion of events and fluents. Instantaneous
events are represented by time intervals and should be distinguished from
instantaneous holding of fluents, which are evaluated at time points:
therefore, the point $a$ should be distinguished from the interval $[a,a]$,
and the truths in these should not necessarily imply each other. Finally, we
note that, while differences in expressiveness have been found between the
strict and non-strict semantics for some interval logics (see [MGMS11], for
example), so far, no distinction in the decidability of the satisfiability has
been found. Therefore, we believe that an attempt to systemize the role of
points, intervals, and their interaction, would make good sense not only from
a purely ontological point of view, but also from algorithmic and
computational perspectives.

Previous Work and Motivations. As presented in the early work of van Benthem
[vB91] and Allen and Hayes [AH85], interval temporal reasoning can be
formalized as an extension of first-order logic with equality with one or more
relations, and the properties of the resulting language can be studied;
obviously, the same applies when relations between points are considered too.
In this paper we ask the question: interpreted over linear orders, how many
and which expressively different languages can be obtained by enriching first-
order logic with relations between intervals, between points, and between
intervals and points? Since, as we shall see, there are 26 different relations
(including equality of both sorts) between points, intervals, and points and
intervals, $2^{26}$ is an upper bound on this number. (It is worth noticing
that in [MH06] the authors distinguish 30 relations, instead of 26; this is
due to the fact that the concepts of the point $a$ starting the interval
$[a,b]$ and meeting it are considered to be different.) However, since certain
relations are definable in terms of other ones, the actual number is less and
in fact, as we shall show, much less. The answer also depends on our choices
of certain semantic parameters, specifically, the class of linear orders over
which we construct our interval structures. In this paper, in Part I [CDS18],
we consider the classification problem relative to:

  1. _(i)_

the class of all linear orders;

  2. _(ii)_

the class of all weakly discrete linear orders (i.e., orders in which every
point with a successor/predecessor has an immediate one).

In Part II of this paper we consider:

  1. _(iii)_

the class of all dense linear orders;

  2. _(iv)_

the class of all unbounded linear orders;

Apart from the intrinsic interest and naturalness of this classification
problem, its outcome has some important repercussions, principally in the
reduction of the number of cases that need to be considered in other problems
relating to these languages. For example, it reduces the number of
representation theorems that are needed: given the dual nature of time
intervals (i.e., they can be abstract first-order individuals with specific
characteristics, or they can be defined as ordered pairs over a linear order),
one of the most important problems that arises is the existence or not of a
representation theorem. Consider any class of linear orders: given a specific
extension of first-order logic with a set of interval relations (such as, for
example, meets and during), does there exist a set of axioms in this language
which would constrain (abstract) models of this signature to be isomorphic to
concrete ones? Various representation theorems exist in the literature for
languages that include interval relations only: van Benthem [vB91], over
rationals and with the interval relations during and before, Allen and Hayes
[AH85], for the dense unbounded case without point intervals and for the
relation meets, Ladkin [Lad78], for point-based structures with a quaternary
relation that encodes meeting of two intervals, Venema [Ven91], for structures
with the relations starts and finishes, Goranko, Montanari, and Sciavicco
[GMS03], for linear structures with meets and met-by, Bochman [Boc90], for
point-interval structures, and Coetzee [Coe09] for dense structure with
overlaps and meets. Clearly, if two sets of relations give rise to
expressively equivalent languages, two separate representations theorems for
them are not needed. In which cases are representation theorems still
outstanding? Preliminary works that provide similar classifications appeared
in [CS11] for first-order languages with equality and only interval-interval
relations, and in [CDS12] for points and intervals (with equality between
intervals treated on a par with the other relations) but only over the class
of all linear orders. Finally, a complete study of first-order interval
temporal logics enables a deeper understanding of their modal counterparts
based on their shared relational semantics.

Structure of the paper. This paper is structured as follows. Section 2
provides the necessary preliminaries, along with an overview of the general
methodology used in this paper. Part I of this paper dealt with definability
and undefinability in the classes $\mathsf{Lin}$ and $\mathsf{Dis}$, from
which we start in order to tackle, in Section 3, the study the expressive
power of the language by analyzing the definability properties of each basic
relation in the class $\mathsf{Den}$, and in Section 4 the corresponding
undefinability results in this case. Then, in Section 5 and Section 6,
respectively, we present the same analysis in the unbounded case, before
concluding. It is worth reminding that most of the results presented here are
a consequence of those presented in Part I, to which we shall refer whenever
necessary.

##  2\. Basics

###  2.1. Syntax and semantics

$(\mbox{{\em
meets,m}})\,\,[a,b]~{}{\mathpzc{3}\mathpzc{4}}_{ii}~{}[c,d]\Leftrightarrow
b=c$$(\mbox{{\em
before,b}})\,\,[a,b]~{}{\mathpzc{4}\mathpzc{4}}_{ii}~{}[c,d]\Leftrightarrow
b<c$$(\mbox{{\em
starts,s}})\,\,[c,d]~{}{\mathpzc{1}\mathpzc{4}}_{ii}~{}[a,b]\Leftrightarrow
a=c,d<b$$(\mbox{{\em
finishes,f}})\,\,[c,d]~{}{\mathpzc{0}\mathpzc{3}}_{ii}~{}[a,b]\Leftrightarrow
b=d,a<c$$(\mbox{{\em
during,d}})\,\,[c,d]~{}{\mathpzc{0}\mathpzc{4}}_{ii}~{}[a,b]\Leftrightarrow
a<c,d<b$$(\mbox{{\em
overlaps,o}})\,\,[a,b]~{}{\mathpzc{2}\mathpzc{4}}_{ii}~{}[c,d]\Leftrightarrow
a<c<b<d$$a$$b$$c$$d$$c$$d$$c$$d$$c$$d$$c$$d$$c$$d$ Table 1. Interval-interval
relations, a.k.a. Allen’s relations. The equality relation is not depicted.

Given a linear order $\mathbb{D}=\langle D,<\rangle$, we call the elements of
$D$ _points_ (denoted by $a,b,\ldots$) and define an interval as an ordered
pair $[a,b]$ of points in $D$, where $a<b$. Abstract intervals will be denoted
by $I,J,\ldots,$ and so on. Now, as we have mentioned above, there are 13
possible relations, including equality, between any two intervals. From now
on, we call these interval-interval relations. Besides equality, there are 2
different relations that may hold between any two points (before and after),
called hereafter point-point relations, and 5 different relations that may
hold between a point and an interval and vice-versa: we call those interval-
point and point-interval relations, respectively, and we use the term mixed
relations to refer to them indistinctly. Interval-interval relations are
exactly Allen’s relations [All83]; point-point relations are the classical
relations on a linear order, and mixed relations will be explained below.
Traditionally, interval relations are represented by the initial letter of the
description of the relation, like $m$ for meets. However, when one considers
more relations (like point-point and point-interval relations) this notation
becomes confusing, and even more so in the presence of more relations, e.g.
when one wants to consider interval relations over a partial order111This
paper is focused on linear orders only; nevertheless, it is our intention to
complete this study to include the treatment of partial orders also, and, at
this stage, we want to make sure that we will be able to keep the notation
consistent.. We introduce the following notation to resolve this issue: an
interval $[a,b]$ induces a partition of $\mathbb{D}$ into five regions (see
[Lig91]): region 0 which contains all points less than $a$, region 1 which
contains $a$ only, region 2 which contains all the points strictly between $a$
and $b$, region 3 which contains only $b$ and region 4 which contains the
points greater than $b$. Likewise, a point $c$ induces a partition of
$\mathbb{D}$ into 3 pieces: region 0 contains all the points less than $c$,
region 2 contains only $c$, and region 4 contains all the points greater than
$c$. Interval-interval relations will be denoted by
$I{\mathpzc{k}\mathpzc{k^{\prime}}}_{ii}J$ (where the subscript ii refers to
interval-interval relations), where $k,k^{\prime}\in\\{0,1,2,3,4\\}$, and $k$
represent the region of the partition induced by $I$ in which the left
endpoint of $J$ falls, while $k^{\prime}$ is the region of the same partition
in which the right endpoint of $J$ falls; for example,
$I{\mathpzc{3}\mathpzc{4}}_{ii}J$ is exactly Allen’s relation meets.
Similarly, interval-point relations will be denoted by
$I{\mathpzc{k\,}}_{ip}a$ (where the subscript ip stands for interval-point
relations), where $k$ represents the position of $a$ with respect to $I$; for
example, $I{\mathpzc{4}}_{ip}a$ is the relation before. Analogously, point-
point relations will be denoted by the symbol ${\mathpzc{k\,}}_{pp}$, and
point-interval relations by the symbol
${\mathpzc{k}\mathpzc{k^{\prime}}}_{pi}$. For point-point relations it is more
convenient to use $<$ instead of ${\mathpzc{4}}_{pp}$, and $>$ instead of
${\mathpzc{0}}_{pp}$. In Tab. 1 we show six of the interval-interval
relations, along with its original nomenclature and symbology, and in Tab. 2
we show the interval-point relations. Finally, we consider one equality per
sort, using $=_{i}$ to denote ${\mathpzc{1}\mathpzc{3}}_{ii}$ (equality
between intervals), and $=_{p}$ to denote ${\mathpzc{2}}_{pp}$ (the equality
between points). Now, given any of the mentioned relations $r$, its inverse,
generically denoted by $\bar{r}$, can be obtained by inverting the roles of
the objects in the case of non-mixed relations; for example, the inverse of
the relation ${\mathpzc{2}\mathpzc{2}}_{ii}$ (Allen’s relation contains) is
the relation ${\mathpzc{0}\mathpzc{4}}_{ii}$ (Allen’s relation during). On the
other hand, mixed relations present a different situation: the inverse of a
point-interval relation is an interval-point relation; thus, for example, the
inverse of ${\mathpzc{3}}_{ip}$ is ${\mathpzc{0}\mathpzc{2}}_{pi}$. Finally,
notice that some combinations are forbidden: for instance, the relation
${\mathpzc{2}\mathpzc{2}}_{pi}$ makes no sense, as all intervals have a non-
zero extension.

######  Definition .

We shall denote by: $\mathfrak{R}$ the set of all above described relations;
$\mathfrak{I}\subset\mathfrak{R}$ the subset of all 13 interval-interval
relations (Allen’s relations) including the relation $=_{i}$;
$\mathfrak{M}\subset\mathfrak{R}$ the subset of all mixed relations;
$\mathfrak{P}\subset\mathfrak{R}$ the subset of all point-point relations
including the relation $=_{p}$. Clearly,
$\mathfrak{R}=\mathfrak{I}\bigcup\mathfrak{M}\bigcup\mathfrak{P}$.

$a$$b$$[a,b]~{}{\mathpzc{3}}_{ip}~{}c\Leftrightarrow
b=c$$\cdot$$c$$[a,b]~{}{\mathpzc{4}}_{ip}~{}c\Leftrightarrow
b<c$$\cdot$$c$$[a,b]~{}{\mathpzc{2}}_{ip}~{}c\Leftrightarrow
a<c<b$$\cdot$$c$$[a,b]~{}{\mathpzc{1}}_{ip}~{}c\Leftrightarrow
a=c$$\cdot$$c$$[a,b]~{}{\mathpzc{0}}_{ip}~{}c\Leftrightarrow c<a$$\cdot$$c$
Table 2. Interval-point relations.

######  Definition .

In the following, we denote by:

  1. _(i)_

$\mathsf{Lin}$ the class of all linear orders;

  2. _(ii)_

$\mathsf{Den}$ the class of all dense linear orders, that is, the class of all
linear orders where there exists a point in between any two distinct points;

  3. _(iii)_

$\mathsf{Dis}$ the class of all weakly discrete linear orders, that is, the
class of all linear orders where each point, other than the least (resp.,
greatest) point, if there is one, has a direct predecessor (resp., successor)
– by a direct predecessor of $a$ we of course mean a point $b$ such that $b<a$
and for all points $c$, if $c<a$ then $c\leq b$, and the notion of a direct
successor is defined dually;

  4. _(iv)_

$\mathsf{Unb}$ the class of all unbounded linear orders, that is, the class of
all linear order such that for every point $a$ there exists a point $b>a$ and
a point $c<a$.

######  Definition .

Given a linear order $\mathbb{D}$, and given the set
$\mathbb{I}(\mathbb{D})=\\{[a,b]\mid a,b\in\mathbb{D},a<b\\}$ of all intervals
built on $\mathbb{D}$:

  * •

a _concrete interval structure of signature $S$_ is a relational structure
$\mathcal{F}=\langle\mathbb{I}(\mathbb{D}),r_{1},$
$r_{2},\ldots,r_{n}\rangle$, where
$S=\\{r_{1},\ldots,r_{n}\\}\subseteq\mathfrak{I}$, and

  * •

a _concrete point-interval structure of signature $S$_ is a two-sorted
relational structure
$\mathcal{F}=\langle\mathbb{D},\mathbb{I}(\mathbb{D}),r_{1},r_{2},\ldots,$
$r_{n}\rangle$, where $S=\\{r_{1},\ldots,r_{n}\\}\subseteq\mathfrak{R}$.

Since all relations between intervals, points, and all mixed relations are
already implicit in $\mathbb{I}(\mathbb{D})$, we shall often simply write
$\langle\mathbb{I}(\mathbb{D})\rangle$ for a concrete interval structure
$\langle\mathbb{I}(\mathbb{D}),r_{1},r_{2},\ldots,r_{n}\rangle$, and
$\langle\mathbb{D},\mathbb{I}(\mathbb{D})\rangle$ for a concrete point-
interval structure
$\langle\mathbb{D},\mathbb{I}(\mathbb{D}),r_{1},r_{2},\ldots,r_{n}\rangle$;
this is in accordance with the standard usage in much of the literature on
interval temporal logics. Moreover, we denote by $FO+S$ the language of first-
order logic without equality and relation symbols corresponding to the
relations in $S$. Finally, $\mathcal{F}$ is further said to be _of the class
$\mathrm{C}$_
($\mathrm{C}\in\\{\mathsf{Lin},\mathsf{Den},\mathsf{Dis},\mathsf{Unb}\\}$)
when $\mathbb{D}$ belongs to the specific class of linear orders $\mathrm{C}$.

###  2.2. (Un)definability and Truth Preserving Relations

We describe here the most important tools that we use to classify the
expressive power of our (sub-)languages.

######  Definition .

Let $S\subseteq\mathfrak{R}$, and $\mathrm{C}$ a class of linear orders. We
say that $FO+S$ defines $r\in\mathfrak{R}$ over $\mathrm{C}$, denoted by
$FO+S\rightarrow_{\mathrm{C}}r$, if there exists an $FO+S$-formula
$\varphi(x,y)$ such that $\varphi(x,y)\leftrightarrow r(x,y)$ is valid on the
class of concrete point-interval structures of signature $(S\cup\\{r\\})$
based on $\mathrm{C}$.

By $FO+S\rightarrow r$ we denote the fact that
$FO+S\rightarrow_{\mathsf{Lin}}r$ (and hence $FO+S\rightarrow_{\mathrm{C}}r$
for every
$\mathrm{C}\in\\{\mathsf{Lin},\mathsf{Den},\mathsf{Dis},\mathsf{Unb}\\}$).
Obviously, $FO+S\rightarrow r$ for all $r\in S$.

######  Definition .

Let $S,S^{\prime}\subseteq\mathfrak{R}$ and $\mathrm{C}$ a class of linear
orders. We say that $S$ is:

  * •

$S^{\prime}$-complete over $\mathrm{C}$ (resp., $S^{\prime}$-incomplete over
$\mathrm{C}$) if and only if $FO+S\rightarrow_{\mathrm{C}}r$ for all $r\in
S^{\prime}$ (resp., $FO+S\not\rightarrow_{\mathrm{C}}r$ for some $r\in
S^{\prime}$), and

  * •

minimally $S^{\prime}$-complete over $\mathrm{C}$ (resp., maximally
$S^{\prime}$-incomplete over $\mathrm{C}$) if and only if it is
$S^{\prime}$-complete (resp., $S^{\prime}$-incomplete) over $\mathrm{C}$, and
every proper subset (resp., every proper superset) of $S$ is
$S^{\prime}$-incomplete (resp., $S^{\prime}$-complete) over the same class.

The notion of (minimally) $r$-completeness and (maximally) $r$-incompleteness
over $\mathrm{C}$ is immediately deduced from the above one, by taking
$S^{\prime}=\\{r\\}$ and denoting the latter simply by $r$. Moreover, one can
project the above definitions over some interesting subsets of $\mathfrak{R}$,
such as $\mathfrak{I},\mathfrak{M}$ or $\mathfrak{P}$, obtaining relative
completeness and incompleteness.

Let $C^{\prime}\subseteq C$ be two classes of linear orders. Notice that if
$FO+S\rightarrow_{\mathrm{C}}r$ then $FO+S\rightarrow_{\mathrm{C}^{\prime}}r$
and, contrapositively, that if $FO+S\not\rightarrow_{\mathrm{C}^{\prime}}r$
then $FO+S\not\rightarrow_{\mathrm{C}}r$. So specifically, if $S$ is
$S^{\prime}$-complete over $\mathrm{C}$, then it is also $S^{\prime}$-complete
over $\mathrm{C}^{\prime}$. Also, if $S$ is $S^{\prime}$-incomplete over
$\mathrm{C}^{\prime}$, then it is also $S^{\prime}$-incomplete over
$\mathrm{C}$. Notice however, that minimality and maximality of complete and
incomplete sets does not necessarily transfer between super and subclasses in
a similar way. In what follows, in order to prove that
$FO+S\not\rightarrow_{\mathrm{C}}r$ for some $r$ and some class $\mathrm{C}$,
we shall repeatedly apply the following definition and (rather standard)
procedure.

######  Definition .

Let $\mathcal{F}=\langle\mathbb{D},\mathbb{I}(\mathbb{D}),S\rangle$ and
$\mathcal{F}^{\prime}=\langle\mathbb{D}^{\prime},\mathbb{I}(\mathbb{D}^{\prime}),S\rangle$
be concrete structures where $S\subseteq\mathfrak{R}$. A binary relation
$\zeta\subseteq(\mathbb{D}\cup\mathbb{I}(\mathbb{D}))\times(\mathbb{D}^{\prime}\cup\mathbb{I}(\mathbb{D}^{\prime}))$
is called a _surjective $S$-truth preserving relation_ if and only if:

  1. _(i)_

$\zeta$ respects sorts, i.e., $\zeta=\zeta_{p}\cup\zeta_{i}$, where
$\zeta_{p}\subseteq\mathbb{D}\times\mathbb{D}^{\prime}$ and
$\zeta_{i}\subseteq\mathbb{I}(\mathbb{D})\times\mathbb{I}(\mathbb{D}^{\prime})$;

  2. _(ii)_

$\zeta$ respects the relations in $S$, i.e., if
$(a,a^{\prime}),(b,b^{\prime})\in\zeta_{p}$ and
$(I,I^{\prime}),(J,J^{\prime})\in\zeta_{i}$, then:

    1. (a)

$r(a,b)$ if and only if $r(a^{\prime},b^{\prime})$ for every point-point
relation $r\in S$;

    2. (b)

$r(I,a)$ if and only if $r(I^{\prime},a^{\prime})$ for every interval-point
relation $r\in S$;

    3. (c)

$r(I,J)$ if and only if $r(I^{\prime},J^{\prime})$ for every interval-interval
relation $r\in S$;

  3. _(iii)_

$\zeta$ is total and surjective, i.e.:

    1. (a)

for every $a\in\mathbb{D}$ (resp., $I\in\mathbb{I}(\mathbb{D})$), there exist
$a^{\prime}\in\mathbb{D}^{\prime}$ (resp.,
$I^{\prime}\in\mathbb{I}(\mathbb{D}^{\prime})$) such that
$(a,a^{\prime})\in\zeta_{p}$ (resp., $(I,I^{\prime})\in\zeta_{i}$);

    2. (b)

for every $a^{\prime}\in\mathbb{D}^{\prime}$ (resp.,
$I^{\prime}\in\mathbb{I}(\mathbb{D}^{\prime})$), there exist $a\in\mathbb{D}$
(resp., $I\in\mathbb{I}(\mathbb{D})$) such that $(a,a^{\prime})\in\zeta_{p}$
(resp., $(I,I^{\prime})\in\zeta_{i}$).

If we add to Definition 2.2 the requirement that that $\zeta$ should be
functional, we obtain nothing but the definition of an isomorphism between
two-sorted first-order structures or, equivalently, an isomorphism between
single sorted first-order structures with predicates added for ‘point’ and
‘interval’ (see e.g. [Hod93]). As one would expect, surjective $S$-truth
preserving relations preserve the truth of all first-order formulas in
signature $S$. This is stated in Theorem 2.2, below. The reason why we
consider only interval-point relations instead of all mixed relations is that,
as we shall explain, we can limit ourselves to work without inverse relations,
and point-interval relations are the inverse of interval-point ones.

######  Definition .

If $\zeta$ is a surjective $S$-truth preserving relation, we say that $\zeta$
breaks $r\not\in S$ if and only if there are:

  1. _(i)_

$(a,a^{\prime}),(b,b^{\prime})\in\zeta_{p}$ such that $r(a,b)$ but $\neg
r(a^{\prime},b^{\prime})$, if $r$ is point-point, or

  2. _(ii)_

$(a,a^{\prime})\in\zeta_{p}$ and $(I,I^{\prime})\in\zeta_{i}$ such that
$r(I,a)$ but $\neg r(I^{\prime},a^{\prime})$, if $r$ is interval-point, or

  3. _(iii)_

$(I,I^{\prime}),(J,J^{\prime})\in\zeta_{i}$ such that $r(I,J)$ but $\neg
r(I^{\prime},J^{\prime})$, if $r$ is interval-interval.

The following result is, as already mentioned, a straightforward
generalization of the classical result on the preservation of truth under
isomorphism between first-order structures, and it is proved by an easy
induction on formulas, using clause (ii) of Definition 2.2 to establish the
base case for atomic formulas and clause (iii) for the inductive step for the
quantifiers.

######  Theorem .

If $\zeta=\zeta_{p}\cup\zeta_{i}$ is a surjective $S$-truth preserving
relation between
$\mathcal{F}=\langle\mathbb{D},\mathbb{I}(\mathbb{D}),S\rangle$ and
$\mathcal{F}^{\prime}=\langle\mathbb{D}^{\prime},\mathbb{I}(\mathbb{D}^{\prime}),S\rangle$,
and $a_{1},\ldots,a_{k}\in\mathbb{D}$,
$a^{\prime}_{1},\ldots,a^{\prime}_{k}\in\mathbb{D}$,
$I_{1},\ldots,I_{l}\in\mathbb{I}(\mathbb{D})$, and
$I^{\prime}_{1},\ldots,I^{\prime}_{l}\in\mathbb{I}(\mathbb{D}^{\prime})$ are
such that $(a_{j},a_{j}^{\prime})\in\zeta_{p}$ for $1\leq j\leq k$, and
$(I_{j},I^{\prime}_{j})\in\zeta_{i}$ for $1\leq j\leq l$, then for every
$FO+S$ formulas
$\varphi(x_{p}^{1},\ldots,x_{p}^{k},y_{i}^{1},\ldots,y_{i}^{l})$ with free
variables $x_{p}^{1},\ldots x_{p}^{k},y_{i}^{1},\ldots y_{i}^{l}$, we have
that

$\mathcal{F}\models\varphi(a_{1},\ldots,a_{k},I_{1},\ldots,I_{l})\text{ \ if
and only if \ }\mathcal{F}^{\prime}\models\varphi(a^{\prime}_{1},\ldots
a^{\prime}_{k},I^{\prime}_{1},\ldots,I^{\prime}_{l}).$

Thus, to show that $FO+S\not\rightarrow r$ for a given $r\in\mathfrak{R}$, it
is sufficient to find two concrete point-interval structures $\mathcal{F}$ and
$\mathcal{F}^{\prime}$ and a surjective $S$-truth preserving relation $\zeta$
between $\mathcal{F}$ and $\mathcal{F}^{\prime}$ which breaks $r$. For the
readers’ convenience, let us refer to surjective $S$-truth preserving
relations as simply $S$-relations.

Although there are other constructions that could be used to show that
relations are not definable in $FO+S$, e.g. elementary embedding or
Ehrenfeucht-Fraïssé games, we have found $S$-relations sufficient for our
purposes in this paper.

###  2.3. Strategy

The main objective of this paper is to establish all expressively different
subsets of $\mathfrak{R}$ (and, then, of $\mathfrak{I},\mathfrak{M}$ or
$\mathfrak{P}$) over the mentioned classes of linear orders. To this end, for
each $r\in\mathfrak{R}$ we compute all expressively different minimally
$r$-complete and all maximally $r$-incomplete subsets of $\mathfrak{R}$, from
which we can easily deduce all expressively different minimally $r$-complete
and maximally $r$-incomplete subsets of $\mathfrak{I},\mathfrak{M}$ and
$\mathfrak{P}$; minimally $\mathfrak{R}$\- (resp.,
$\mathfrak{I}-,\mathfrak{M}-,\mathfrak{P}-$) complete and maximally incomplete
subsets are, then, deduced as a consequence of the above results. The set
$\mathfrak{R}$ contains, as we have mentioned, 26 different relations. This
means that there are $2^{26}$ potentially different extensions of first-order
logic to be studied. Clearly, unless we design a precise strategy that allows
us to reduce the number of results to be proved, the task becomes cumbersome.

As a first simplification principle observe that, since we are working within
first-order logic, all inverses of relations are explicitly definable, and
hence we only need to assume as primitive a set which contains all relation up
to inverses, which implies that point-interval relations can be omitted if we
consider all interval-point ones. Accordingly, let $\mathfrak{I}^{+}$ be the
set of interval-interval relations given in Tab. 1 together with $=_{i}$,
$\mathfrak{M}^{+}$ be the set of interval-point relations given in Tab. 2, and
let $\mathfrak{P}^{+}=\\{<,=_{p}\\}$. Lastly let
$\mathfrak{R}^{+}=\mathfrak{I}^{+}\bigcup\mathfrak{M}^{+}\bigcup\mathfrak{P}^{+}$.

In order to further reduce the number of results to be presented, consider
what follows. The order dual of a structure
$\mathcal{F}=\langle\mathbb{D},\mathbb{I}(\mathbb{D})\rangle$ is the structure
$\mathcal{F}^{\partial}=\langle\mathbb{D}^{\partial},\mathbb{I}(\mathbb{D}^{\partial})\rangle$
based on the order dual $\mathbb{D}^{\partial}$ (obtained by reversing the
order) of the underlying linear order $\mathbb{D}$. All classes considered in
this paper are closed under taking order duals.

######  Definition .

The _reversible relations_ are exactly the members of the set
$\\{{\mathpzc{0}}_{ip},{\mathpzc{1}}_{ip},$
${\mathpzc{3}}_{ip},{\mathpzc{4}}_{ip},$
${\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$. The
relations belonging to the complement
$\mathfrak{R}^{+}\setminus\\{{\mathpzc{0}}_{ip},{\mathpzc{1}}_{ip},$
${\mathpzc{3}}_{ip},{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
are called _symmetric_ ; if, in addition, $r={\mathpzc{2}}_{ip}$ or
$r={\mathpzc{0}\mathpzc{4}}_{ii}$, then $r$ is said self-symmetric. If
$r={\mathpzc{0}}_{ip}$ (resp.,
$r={\mathpzc{1}}_{ip},r={\mathpzc{1}\mathpzc{4}}_{ii}$), its reverse is
$r={\mathpzc{4}}_{ip}$ (resp.,
$r={\mathpzc{3}}_{ip},r={\mathpzc{0}\mathpzc{3}}_{ii}$), and the other way
around. Finally, the symmetric $S^{\prime}$ of a subset
$S\subseteq\mathfrak{R}^{+}$ is obtained by replacing every reversible
relation in $S$ with its reverse. We shall use the notation $S\sim S^{\prime}$
to indicate that sets $S$ and $S^{\prime}$ are symmetric.

 $\begin{array}[]{@{\hspace*{1ex}}lr@{}}\hskip
3.01389pt\lx@intercol\mbox{proc
}\mbox{{Undef}}\left(r\in\mathfrak{R}^{+},def\\_rules\right)\\\ \hskip
3.01389pt\lx@intercol\BEGIN\FORALL\ S\subset\mathfrak{R}^{+}\\\ \hskip
3.01389pt\lx@intercol\BEGIN S=Closure(S,def\\_rules);\\\ \hskip
3.01389pt\lx@intercol\IF((r\notin S)\and(S\ is\ maximal))\THEN list\ S\END\\\
\hskip 3.01389pt\lx@intercol\END\\\ \end{array}$
$\begin{array}[]{@{\hspace*{1ex}}lr@{}}\hskip 3.01389pt\lx@intercol\mbox{proc
}\mbox{{Closure}}\left(S,def\\_rules\right)\\\ \hskip
3.01389pt\lx@intercol\BEGIN\WHILE(S\ changes)\\\ \hskip
3.01389pt\lx@intercol\BEGIN\FORALL 1\leq i\leq size(def\\_rules)\\\ \hskip
3.01389pt\lx@intercol\BEGIN\IF(def\\_rules[i]\ applies)\THEN
S=Apply(S,def\\_rule[i])\\\ \hskip 3.01389pt\lx@intercol\END\\\ \hskip
3.01389pt\lx@intercol\END\\\ \hskip 3.01389pt\lx@intercol\mbox{return}\
S\END\\\ \end{array}$

Figure 1. Pseudo-code to identify maximally $r$-incomplete sets.

This definition is motivated by the following easily verifiable facts. Let
$r\in\mathfrak{R}^{+}$, $\mathcal{F}$ be a structure, and $x$ and $y$ be
elements of $\mathcal{F}$ of the appropriate sorts for $r$; then:

  1. _(i)_

if $r$ is a reversible relation, with reverse $r^{\prime}$, then
$\mathcal{F}\models r(x,y)$ if and only if $\mathcal{F}^{\partial}\models
r^{\prime}(x,y)$;

  2. _(ii)_

if $r$ is self-symmetric, then $\mathcal{F}\models r(x,y)$ if and only if
$\mathcal{F}^{\partial}\models r(x,y)$;

  3. _(iii)_

if $r$ is a symmetric, but not self-symmetric, relation, then
$\mathcal{F}\models r(x,y)$ if and only if $\mathcal{F}^{\partial}\models
r(y,x)$.

$\mathbb{D},\mathbb{D}^{\prime},\ldots$ |  (generic) linearly ordered sets
---|---
$x_{p},y_{p},\ldots$ |  first-order variables for points
$x_{i},y_{i},\ldots$ |  first-order variables for intervals
$x,y,\ldots$ |  first-order variables of any sort
before,… |  relations in text are emphasized
$\mathcal{F},\mathcal{F}^{\prime},\ldots$ |  (generic) concrete (point-)interval structures
$S,S^{\prime},\ldots$ |  (generic) subsets of $\mathfrak{R}$-relations
$\zeta~{}(\zeta_{p},\zeta_{i})$ |  surjective relation (for points, for intervals)
$Id_{p}(Id_{i})$ |  ‘identity’ relation over points (intervals)
$\mathrm{C},\mathrm{C}^{\prime}$ |  (generic) class of linearly ordered sets
$FO+S\rightarrow_{\mathrm{C}}r$ |  $S$ defines $r$ (w.r.t. the class $C$)
$S\sim S^{\prime}$ |  $S$ and $S^{\prime}$ are symmetric
$a\in\mathbb{D}$ |  $a$ is a point of $D$, where $\mathbb{D}=(D,<)$
$\underline{S}$ |  in the text, a new proof case is underlined
$r$ |  generic relation
$\mathsf{mcs}$ ($\mathsf{mcs}(r)$) |  minimally complete set (minimally $r$-complete set)
$\mathsf{MIS}$ ($\mathsf{MIS}(r)$) |  maximally incomplete set (maximally $r$-incomplete set)
Table 3. Notational conventions used in this paper. $=_{p}$ | $=_{i}$ | $<$ | ${\mathpzc{0}}_{ip}$ | ${\mathpzc{1}}_{ip}$ | ${\mathpzc{2}}_{ip}$
---|---|---|---|---|---
$\\{<\\}$ | $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ | $\\{{\mathpzc{0}}_{ip},{\mathpzc{1}}_{ip}\\}$ | $\\{{\mathpzc{1}}_{ip},<\\}$ | $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ | $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$
$\\{{\mathpzc{1}}_{ip}\\}$ | $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ | $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ | $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$
$\\{{\mathpzc{3}}_{ip}\\}$ | $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ | $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip},<\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
| $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ | $\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},<\\}$ | $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$
| $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ | $\\{{\mathpzc{3}}_{ip},{\mathpzc{4}}_{ip}\\}$ | $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ | $\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}$ | $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$
| $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ | $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ | $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii},<\\}$ | $\\{{\mathpzc{0}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii},<\\}$
| $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ | $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ | $\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},<\\}$ | $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{0}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii},<\\}$
| $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ | $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}$ | $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ | $\\{{\mathpzc{0}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii},<\\}$
| $\\{{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{3}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}$
| $\\{{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ | $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},<\\}$ | $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii},<\\}$
| $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{3}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$
|  | $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii},=_{i}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},<\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$
|  | $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},=_{i}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$
|  | $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},=_{i}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},=_{i}\\}$ | $\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii},<\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$
|  | $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii},=_{i}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii},=_{i}\\}$ | $\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii},<\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$
|  | $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},=_{i}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},=_{i}\\}$ | $\\{{\mathpzc{4}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii},<\\}$ | $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
|  | $\\{{\mathpzc{3}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},=_{i}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  | $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$
|  | $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  | $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$
|  | $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii},<\\}$ |  | $\\{{\mathpzc{3}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$
|  | $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{3}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  | $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},<\\}$
|  | $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ | $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  | $\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}$
|  | $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  | $\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii},<\\}$
|  | $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ | $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  | $\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii},<\\}$
|  |  | $\\{{\mathpzc{4}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii},<\\}$ |  |
|  |  | $\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}$ |  |
|  |  | $\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii},<\\}$ |  |
|  |  | $\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii},<\\}$ |  |
Table 4. The spectrum of the $\mathsf{mcs}(r)$, for each
$r\in\mathfrak{M}^{+}\cup\\{=_{p},=_{i},<\\}$. - Class: $\mathsf{Lin}$
(review).

The following crucial lemma capitalizes on these facts.

######  Lemma .

Let $S,S^{\prime}\subset\mathfrak{R}^{+}$ be such that $S\sim S^{\prime}$. If
$r$ is a symmetric relation, then $FO+S\rightarrow r$ if and only if
$FO+S^{\prime}\rightarrow r$. Moreover, if $r$ is a reversible relation with
reverse $r^{\prime}$, then $FO+S\rightarrow r$ if and only if
$FO+S^{\prime}\rightarrow r^{\prime}$.

###### Proof.

Let $S,S^{\prime}\subset\mathfrak{R}^{+}$ such that $S\sim S^{\prime}$. For
any $FO+S$ formula $\varphi$ that defines a given relation (and, therefore,
with exactly two free variables), let $\varphi^{\prime}$ denote the formula
obtained from $\varphi$ by replacing every occurrence of a reversible relation
with its reverse, and by swapping the arguments of every symmetric, but not
self-symmetric, relation (occurrences of every self-symmetric relation are
left unchanged). Induction on formulas then shows that
$\mathcal{F}\models\varphi(x,y)$ (after substituting $x,y$ with elements of
the appropriate sorts) if and only if
$\mathcal{F}^{\partial}\models\varphi^{\prime}(x,y)$, for any structure
$\mathcal{F}$. The base case of the induction is taken care of by the three
observations preceding this lemma. Now, suppose that a $FO+S$ formula
$\varphi(x,y)$ defines a symmetric relation $r$. We claim that
$\varphi^{\prime}$ also defines $r$. Let $\mathcal{F}$ be an arbitrary
structure of signature $S\cup\\{r\\}$. Then
$\mathcal{F}^{\partial}\models\varphi(x,y)\leftrightarrow r(x,y)$, and hence
$\mathcal{F}\models\varphi^{\prime}(x,y)\leftrightarrow r(y,x)$ if $r$ is not
self-symmetric, and $\mathcal{F}\models\varphi^{\prime}(x,y)\leftrightarrow
r(x,y)$ otherwise. Next, suppose that the $FO+S$ formula $\varphi(x,y)$
defines a reversible relation $r$. We claim that $\varphi^{\prime}$ defines
its reverse $r^{\prime}$. Let $\mathcal{F}$ be an arbitrary structure of
signature $S\cup\\{r\\}$. Then
$\mathcal{F}^{\partial}\models\varphi(x,y)\leftrightarrow r(x,y)$, and, hence,
$\mathcal{F}\models\varphi^{\prime}(x,y)\leftrightarrow r^{\prime}(x,y)$. ∎

In conclusion, we can limit our attention to 14 out of 26 relations by
disregarding the inverses of relations in $\mathfrak{R}^{+}$, and we do not
need to explicitly analyze complete and incomplete sets for
${\mathpzc{3}}_{ip}$, ${\mathpzc{4}}_{ip}$, and
${\mathpzc{0}\mathpzc{3}}_{ii}$ as those correspond exactly to symmetric of
complete and incomplete sets for ${\mathpzc{0}}_{ip}$, ${\mathpzc{1}}_{ip}$,
and ${\mathpzc{1}\mathpzc{4}}_{ii}$, respectively. This means that only 11
relations are to be analyzed (which we can refer to as explicit relations).

Even under the mentioned simplifications, there is a huge number of results to
be presented and displayed. Let $r$ be anyone of the explicit relations. In
order to correctly identifying all minimally $r$-complete sets
($\mathsf{mcs}(r)$), we need to know all maximally $r$-incomplete sets
($\mathsf{MIS}(r)$) over the same class, and the other way around. To this
end, we proceed in the following way:

  1. (1)

fixed a class of linearly ordered sets and an explicit relation $r$, we first
guess the $r$-complete subsets of $\mathfrak{R}^{+}$, obtaining a first
approximation of the definability rules for $r$ (here, denoted by
$def\\_rules$);

  2. (2)

then, we apply the algorithm in Fig. 1, which uses the set of $r$-complete
subsets of $\mathfrak{R}^{+}$ (the parameter $def\\_rules$) to obtain a first
approximation of the maximally $r$-incomplete sets (the procedure $Closure()$
returns the transitive closure of a set of relations, obtained by
systematically applying the definition rules contained in $def\\_rules$ \-
function $Apply()$);

  3. (3)

after that, we prove that every $R_{1},R_{2},\ldots,R_{k}$ listed as a
maximally $r$-incomplete set is actually $r$-incomplete, and, if not, we
repeat from step 1, using the acquired knowledge to update the set of
$r$-complete subsets of $\mathfrak{R}^{+}$;

  4. (4)

at this point, the sets $S_{1},S_{2},\ldots,S_{k^{\prime}}$ listed at step 1
are, actually, all minimally $r$-complete. To see this, observe that, for each
$i$, $S_{i}$ is $r$-complete by definition, and if there was a $r$-complete
set $S\subset S_{i}$, then for some $R_{j}$ listed as maximally $r$-incomplete
set we could not prove its $r$-incompleteness. Therefore,
$S_{1},S_{2},\ldots,S_{k^{\prime}}$ are, in fact, all minimally $r$-complete,
and, as a consequence, $R_{1},R_{2},\ldots,R_{k}$ are all maximally
$r$-incomplete.

For example, suppose that we are interested in minimal $=_{i}$-complete
(resp., maximal $=_{i}$-incomplete) sets of relations. First, we guess that
having the relations ${\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip},$ and
${\mathpzc{3}}_{ip}$ is sufficient to define equality between intervals,
because we can easily define the latter by asserting that two intervals are
the same if they start with the same point, end with the same point, and
contain the same points; so,
$S=\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ is our
first guess. Now, by computing all possible subsets, we find that if $S$ were
minimal, then $\mathfrak{R}^{+}\setminus S$ should be maximally
$=_{i}$-incomplete. Since we cannot find a proof of the latter, we realize
that, in fact, $S^{\prime}=\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ is
sufficient to define $=_{i}$. This back-and-forth procedure continues until it
stabilizes; clearly, one cannot find one minimal $r$-complete subset without
finding, at the same time, all maximal $r$-incomplete subsets, and the other
way around. In the following, for each completeness result, its minimality is
left unproven; after the corresponding undefinability results are proven,
then, by observing that our sets are systematically computed, their respective
minimality and maximality will be a consequence.

The most common notational conventions used in the paper are listed in Tab. 3.

##  3\. Completeness Results in the Class $\mathsf{Den}$

${\mathpzc{3}\mathpzc{4}}_{ii}$ |  ${\mathpzc{1}\mathpzc{4}}_{ii}$ |  ${\mathpzc{2}\mathpzc{4}}_{ii}$ |  ${\mathpzc{0}\mathpzc{4}}_{ii}$ |  ${\mathpzc{4}\mathpzc{4}}_{ii}$
---|---|---|---|---
$\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},<\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$
$\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$
$\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$
$\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$
$\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
$\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$
$\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$
$\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$
$\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
$\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$
$\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$
$\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$
$\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},<\\}$ |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
$\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$
|  |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
|  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$
|  |  $\\{{\mathpzc{0}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$
|  |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |
|  |  |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |
Table 5. The spectrum of the $\mathsf{mcs}(r)$, for each
$r\in\mathfrak{I}^{+}\setminus\\{=_{i}\\}$. - Class: $\mathsf{Lin}$ (review).

As it turns out, only a few of the results that appear in Tab. 4 and Tab. 5
are to be refined to obtain all minimally complete sets under the assumption
of density. In the following, we show in boldface those complete sets that are
stricter than some complete set for a given relation, or completely new, and
we prove them explicitly modulo symmetry.

###  3.1. Definability in $\mathfrak{I}^{+}$ and in $\mathfrak{M}^{+}$.

We begin our study of definability over the Class $\mathsf{Den}$ by
considering minimal definability of $\mathfrak{I}^{+}$ relations by sets of
$\mathfrak{I}^{+}$ relations, and then of $\mathfrak{M}^{+}$ relations by sets
of $\mathfrak{M}^{+}$ relations.

${\mathpzc{3}\mathpzc{4}}_{ii}$ |  ${\mathpzc{1}\mathpzc{4}}_{ii}$ |  ${\mathpzc{2}\mathpzc{4}}_{ii}$ |  ${\mathpzc{0}\mathpzc{4}}_{ii}$ |  ${\mathpzc{4}\mathpzc{4}}_{ii}$ |  $=_{i}$
---|---|---|---|---|---
$\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$
$\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  ${\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii}\\}$
$\bm{\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\bm{\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
$\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |
$\bm{\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |

Table 6. The spectrum of the $\mathsf{mcs}(r)$, for each
$r\in\mathfrak{I}^{+}$. - Class: $\mathsf{Den}$.

(Lemma 3.1)

######  Lemma .

Tab. 6 is correct.

###### Proof.

We begin by proving that $\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ is
${\mathpzc{3}\mathpzc{4}}_{ii}$-complete. In Part I that we proved that on
linear domains the relation
${\mathpzc{3}\mathpzc{4}}_{ii}\vee{\mathpzc{4}\mathpzc{4}}_{ii}$ is
${\mathpzc{3}\mathpzc{4}}_{ii}$-complete. It is therefore sufficient to show
that $\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ is
$({\mathpzc{3}\mathpzc{4}}_{ii}\vee{\mathpzc{4}\mathpzc{4}}_{ii})$-complete
over dense structures. To this end, consider the following definition:

$\begin{array}[]{llll}x_{i}{\mathpzc{3}\mathpzc{4}}_{ii}\vee{\mathpzc{4}\mathpzc{4}}_{ii}y_{i}&\leftrightarrow&\neg(x_{i}{\mathpzc{2}\mathpzc{4}}_{ii}y_{i})\wedge\exists
z_{i}(x_{i}{\mathpzc{2}\mathpzc{4}}_{ii}z_{i}\wedge
z_{i}{\mathpzc{2}\mathpzc{4}}_{ii}y_{i}).&\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}\end{array}$

If $\mathcal{F}\models\varphi([a,b],[c,d])$, there must be some interval
$z_{i}$ overlapped by $x_{i}$ and overlapping $y_{i}$, which implies $a<c$ and
$b<d$ and since $x_{i}$ cannot overlap $y_{i}$, we obtain $b\leq c$ as
required. Conversely, assume that
$[a,b]{\mathpzc{3}\mathpzc{4}}_{ii}\vee{\mathpzc{4}\mathpzc{4}}_{ii}[c,d]$.
Then using the density assumption we can take $z_{i}=[e,f]$, where $a<e<b$ and
$c<f<d$, to witness $\varphi$. Next, we prove that
$\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ is
${\mathpzc{1}\mathpzc{4}}_{ii}$-complete. Consider the following definition:

$\begin{array}[]{llll}x_{i}{\mathpzc{1}\mathpzc{4}}_{ii}y_{i}&\leftrightarrow&\forall
z_{i}(z_{i}{\mathpzc{4}\mathpzc{4}}_{ii}x_{i}\leftrightarrow
z_{i}{\mathpzc{4}\mathpzc{4}}_{ii}y_{i})\wedge\exists
z_{i}(x_{i}{\mathpzc{4}\mathpzc{4}}_{ii}z_{i}\wedge\neg(y_{i}{\mathpzc{4}\mathpzc{4}}_{ii}z_{i})).&\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}\end{array}$

First suppose that $\mathcal{F}\models\varphi([a,b],[c,d])$. If $a<c$, then we
can find a point $e$ with $a<e<c$ and the first conjunct of $\varphi$ fails,
witnessed by the interval $z_{i}=[a,e]$. Similarly $a>c$ also gives a
contradiction, so we obtain $a=c$. The second conjunct of $\varphi$ gives an
interval $z_{i}=[e,f]$ such that $b<e$ and $e\leq d$, and so we have $b<d$. On
the other hand, if we assume that $a=c<b<d$, since the underlying linear order
is dense, there exists $e$ such that $b<e<d$; by taking $z_{i}=[e,d]$, we
witness the second conjunct of $\varphi$, while the first conjunct is
satisfied trivially. The ${\mathpzc{3}\mathpzc{4}}_{ii}$-completeness of
$\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ now follows from the just-proved
${\mathpzc{1}\mathpzc{4}}_{ii}$-completeness of
$\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ and the
${\mathpzc{3}\mathpzc{4}}_{ii}$-completeness of
$\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ over all
linear orders (see Table 5). Having established this, all the remaining new
completeness results listed in Table 6 follows via the completeness of
$\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ with respect to every
$\mathfrak{I}^{+}$-relation. ∎

${\mathpzc{0}}_{ip}$ | ${\mathpzc{1}}_{ip}$ | ${\mathpzc{2}}_{ip}$
---|---|---
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ | $\bm{\\{{\mathpzc{0}}_{ip}\\}}$ | $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ | $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ | $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ | $\bm{\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}}$ | $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  | $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  |

Table 7. The spectrum of the $\mathsf{mcs}(r)$, for each
$r\in\mathfrak{M}^{+}$. - Class: $\mathsf{Den}$.

(Lemma 3.1)

The next two lemmas involve both interval-interval and interval-point
relations, and therefore contrasts with the other results of the present
subsection that all concern definability purely among interval-interval
relations and purely among interval-point relations. However, anticipating
these particular results here, which do not refer to any table in particular,
will be very useful in order to simplify some definitions and chains of
deduction further on.

######  Lemma .

The set $\\{{\mathpzc{0}}_{ip}\\}$ is $<$-complete over dense linear orders.

###### Proof.

Consider the following definition:

$x_{p}<y_{p}\leftrightarrow\begin{array}[]{llll}(\neg\exists
x_{i}(x_{i}{\mathpzc{0}}_{ip}y_{p})\wedge\exists
y_{i}(y_{i}{\mathpzc{0}}_{ip}x_{p}))\vee\exists
x_{i}(x_{i}{\mathpzc{0}}_{ip}x_{p}\wedge\neg(x_{i}{\mathpzc{0}}_{ip}y_{p}))&\\{{\mathpzc{0}}_{ip}\\}\\\
\end{array}$

Suppose that $\mathcal{F}\models\varphi(x_{p},y_{p})$. If the first disjunct
of $\varphi$ holds then $y_{p}$ is the greatest point of the model, while
$x_{p}$ is not, which gives $x_{p}<y_{p}$. Assume the second disjunct of
$\varphi$ holds. Then the interval $x_{i}=[a,b]$ is such that $x_{p}=c<a$, but
$y_{p}\geq a$, that is $x_{p}<y_{p}$. Conversely, suppose that
$x_{p}=a,y_{p}=b$, and that $a<b$. As the structure is dense, if $b$ is the
last point of the model, we have no interval starting at $b$ but infinitely
many intervals $x_{i}$ such that $x_{i}{\mathpzc{0}}_{ip}a$, and if $b$ is not
the last point of the model, then every $x_{i}$ starting at $b$ satisfies the
second part of the definition. ∎

######  Lemma .

The sets $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ are
${\mathpzc{3}\mathpzc{4}}_{ii}$-complete over dense linear orders..

###### Proof.

We will show that both sets
$\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ define
${\mathpzc{0}\mathpzc{3}}_{ii}$ in the dense case; then, since
$\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ defines
${\mathpzc{3}\mathpzc{4}}_{ii}$ in the general case, we have the result.
Indeed, consider the following definitions:

$x_{i}{\mathpzc{0}\mathpzc{3}}_{ii}y_{i}\leftrightarrow\left\\{\begin{array}[]{ll}\exists
z_{p}(x_{i}{\mathpzc{3}}_{ip}z_{p}\wedge
y_{i}{\mathpzc{3}}_{ip}z_{p})\wedge\exists
z_{i}(z_{i}{\mathpzc{0}\mathpzc{4}}_{ii}y_{i}\wedge\neg(z_{i}{\mathpzc{0}\mathpzc{4}}_{ii}x_{i})).&\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}\\\
&\\\ \forall z_{p}(x_{i}{\mathpzc{4}}_{ip}z_{p}\leftrightarrow
y_{i}{\mathpzc{4}}_{ip}z_{p})\wedge\exists
z_{i}(z_{i}{\mathpzc{0}\mathpzc{4}}_{ii}y_{i}\wedge\neg(z_{i}{\mathpzc{0}\mathpzc{4}}_{ii}x_{i})).&\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}\\\
\end{array}\right.$

Let us consider $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$,
first. If $[a,b]{\mathpzc{0}\mathpzc{3}}_{ii}[c,d]$ then $c<a$ and $b=d$, so,
taking $z_{p}$ equal to $b$ satisfies the first conjunct. By density there is
a point $e$ such that $c<e<a$, and therefore taking $z_{i}$ equal to $[e,a]$
satisfies the second conjunct. Conversely, suppose that
$\varphi([a,b],[c,d])$. The first conjunct of $\varphi$ ensures that $b=d$. If
it were the case that $a\leq c$, every interval contained in $[a,b]$ would be
contained in $[c,d]$, violating the second conjunct, so it can only be the
case that $c<a$. We therefore have that
$[a,b]{\mathpzc{0}\mathpzc{3}}_{ii}[c,d]$, as desired. The argument for
$\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ is similar, using the
fact that $\forall z_{p}(x_{i}{\mathpzc{4}}_{ip}z_{p}\leftrightarrow
y_{i}{\mathpzc{4}}_{ip}z_{p})$ is true if and only if the intervals assigned
$x_{i}$ and $y_{i}$ have the same end point. ∎

######  Lemma .

Tab. 7 is correct.

###### Proof.

First, we show that $\\{{\mathpzc{0}}_{ip}\\}$ is
${\mathpzc{1}}_{ip}$-complete. From Lemma 3.1 we know that
$\\{{\mathpzc{0}}_{ip}\\}$ defines ${<}$ in the dense case, so we may consider
the following definition:

$\begin{array}[]{llll}x_{i}{\mathpzc{1}}_{ip}y_{p}&\leftrightarrow&\forall
z_{p}(x_{i}{\mathpzc{0}}_{ip}z_{p}\leftrightarrow
z_{p}<y_{p}).&\\{{\mathpzc{0}}_{ip}\\}\end{array}$

If $[a,b]{\mathpzc{1}}_{ip}c$, then $a=c$, and hence $\varphi([a,b],c)$.
Conversely, suppose that $\varphi([a,b],c)$. So, if $c<a$, then
$[a,b]{\mathpzc{0}}_{ip}c$ by definition of ${\mathpzc{0}}_{ip}$ and so, by
$\varphi([a,b],c)$ we obtain the contradiction $c<c$. Now, if $a<c$ then, by
density, there is a point $d$ such that $a<d<c$. Hence
$\neg[a,b]{\mathpzc{0}}_{ip}d$ by the definition of ${\mathpzc{0}}_{ip}$, but
then $d\not<c$ by $\varphi([a,b],c)$ — a contradiction. The only possible case
is therefore that $a=c$, i.e., that $[a,b]{\mathpzc{1}}_{ip}c$. To see that
$\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ is
${\mathpzc{1}}_{ip}$-complete, it suffices to note that
$\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ defines ${\mathpzc{0}}_{ip}$ in
the general case, and then appeal to the just proven fact that
$\\{{\mathpzc{0}}_{ip}\\}$ defines ${\mathpzc{1}}_{ip}$. ∎

###  3.2. Definability for the Relations $=_{p},=_{i},<$ in $\mathsf{Den}$

$=_{p}$ |  $=_{i}$ |  $<$
---|---|---
$\\{<\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\bm{\\{{\mathpzc{0}}_{ip}\\}}$
$\bm{\\{{\mathpzc{0}}_{ip}\\}}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$
$\\{{\mathpzc{1}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$
$\\{{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$
$\bm{\\{{\mathpzc{4}}_{ip}\\}}$ |  $\bm{\\{{\mathpzc{2}}_{ip}\\}}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$
|  $\\{{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$
|  $\\{{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
|  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$
|  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$
|  $\bm{\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$
|  $\bm{\\{{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$
|  $\bm{\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$
|  |  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$
|  |  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$
|  |  $\bm{\\{{\mathpzc{4}}_{ip}\\}}$
Table 8. The spectrum of the $\mathsf{mcs}(r)$, for each
$r\in\\{=_{p},=_{i},<\\}$. - Class: $\mathsf{Den}$.

######  Lemma .

Tab. 8 is correct.

###### Proof.

We begin by showing that $\\{{\mathpzc{0}}_{ip}\\}$ is $=_{p}$-compete.
Consider the following definition:

$\begin{array}[]{llll}x_{p}=_{p}y_{p}&\leftrightarrow&\forall
x_{i}(x_{i}{\mathpzc{0}}_{ip}x_{p}\leftrightarrow
x_{i}{\mathpzc{0}}_{ip}y_{p})&\\{{\mathpzc{0}}_{ip}\\}\end{array}$

Suppose, first, that $x_{p}=_{p}y_{p}$; we have that, either there exists no
interval in the model, in which case the right-hand side of the definition is
vacuously true, or there are infinitely many intervals (as the underlying
linear order is dense), and every interval $x_{i}$ clearly has both $x_{p}$
and $y_{p}$ in relation ${\mathpzc{0}}_{ip}$ with it or none of them, again
satisfying the right-hand side. If, on the other hand, $\varphi(x_{p},y_{p})$
is satisfied, then, if there is no interval, then $x_{p}$ and $y_{p}$
coincide, and if there are infinitely many intervals, the only way to
guarantee that the intervals that see both $x_{p}$ and $y_{p}$ via
${\mathpzc{0}}_{ip}$ are exactly the same is to assign the same point to
$x_{p}$ and $y_{p}$, as we wanted to prove. The $=_{p}$-completeness of
$\\{{\mathpzc{4}}_{ip}\\}$ follows by symmetry (see Lemma 2.3). Now, consider
$=_{i}$-completeness, and the following definitions:

$x_{i}=_{i}y_{i}\leftrightarrow\left\\{\begin{array}[]{ll}\forall
x_{p}(x_{i}{\mathpzc{2}}_{ip}x_{p}\leftrightarrow
y_{i}{\mathpzc{2}}_{ip}x_{p})&\\{{\mathpzc{2}}_{ip}\\}\\\ &\\\ \forall
z_{i}(x_{i}{\mathpzc{2}\mathpzc{4}}_{ii}z_{i}\leftrightarrow
y_{i}{\mathpzc{2}\mathpzc{4}}_{ii}z_{i})\wedge\forall
z_{i}(z_{i}{\mathpzc{2}\mathpzc{4}}_{ii}x_{i}\leftrightarrow
z_{i}{\mathpzc{2}\mathpzc{4}}_{ii}y_{i})&\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}\\\
&\\\ \forall z_{i}(x_{i}{\mathpzc{0}\mathpzc{4}}_{ii}z_{i}\leftrightarrow
y_{i}{\mathpzc{0}\mathpzc{4}}_{ii}z_{i})\wedge\forall
z_{i}(z_{i}{\mathpzc{0}\mathpzc{4}}_{ii}x_{i}\leftrightarrow
z_{i}{\mathpzc{0}\mathpzc{4}}_{ii}y_{i})&\\{{\mathpzc{0}\mathpzc{4}}_{ii}\\}\\\
&\\\ \forall z_{i}(x_{i}{\mathpzc{4}\mathpzc{4}}_{ii}z_{i}\leftrightarrow
y_{i}{\mathpzc{4}\mathpzc{4}}_{ii}z_{i})\wedge\forall
z_{i}(z_{i}{\mathpzc{4}\mathpzc{4}}_{ii}x_{i}\leftrightarrow
z_{i}{\mathpzc{4}\mathpzc{4}}_{ii}y_{i}).&\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}\\\
\end{array}\right.$

As for $\underline{\\{{\mathpzc{2}}_{ip}\\}}$, observe that two intervals over
a dense linear order are equal if and only if they have the same internal
points. Consider, now, the set $\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}$. It is
clear that if $x_{i}=_{i}y_{i}$ then $\varphi(x_{i},y_{i})$ holds. For the
converse, suppose that $[a,b]\neq[c,d]$. Then either $[a,b]$ has an internal
point which is not an internal point of $[c,d]$ or $[c,d]$ has an internal
point which is not an internal point of $[a,b]$. In both cases either the
first or the second conjunct of $\varphi$ does not hold. The remaining cases
are treated with similar arguments. Let us now focus on the relation $<$ and
the corresponding definitions:

$x_{p}<y_{p}\leftrightarrow\begin{array}[]{llll}\exists
x_{i}(x_{i}{\mathpzc{0}}_{ip}x_{p}\wedge\neg(x_{i}{\mathpzc{0}}_{ip}y_{p}))&\\{{\mathpzc{0}}_{ip}\\}\\\
\end{array}$

Consider the set $\\{{\mathpzc{0}}_{ip}\\}$. Suppose that
$\mathcal{F}\models\varphi(x_{p},y_{p})$. Then, there must be an interval that
starts after $x_{p}$ but not after $y_{p}$; if $x_{p}\geq y_{p}$, then it is
impossible to find such an interval, so $x_{p}<y_{p}$. Conversely, suppose
that $x_{p}=a,y_{p}=b$, and that $a<b$. As the structure is dense, there
exists a point $c$ such that $a<c<b$, and therefore the interval $[c,b]$ can
be used as a witness of $x_{i}$. All other new definitions follow directly
from the results for the class $\mathsf{Lin}$ combined with the density
hypothesis. In particular, to see that
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ is $<$-complete, note
that $\\{{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ defines $=_{i}$ in the dense case
and that $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii},=_{i}\\}$
defines $<$ in the general one. The case for
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ follows since
$\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ defines $=_{i}$ in the dense case and
since $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},=_{i}\\}$ defines
$<$. The case $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ follows
since $\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ defines $=_{i}$ in the dense case
and $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},=_{i}\\}$ defines
$<$. The case $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ follows
since, in the dense case, we have that $\\{{\mathpzc{0}\mathpzc{4}}_{ii}\\}$
defines $=_{i}$ and that
$\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii},=_{i}\\}$ defines $<$.
The case $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ follows
since, under the density hypothesis, we have that
$\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ defines $=_{i}$ and
$\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},=_{i}\\}$ defines $<$.
The case $\\{{\mathpzc{3}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ follows
since $\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ defines $=_{i}$ in the dense case
and since we already know that
$\\{{\mathpzc{3}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},=_{i}\\}$ defines $<$.
Lastly, the fact that $\\{{\mathpzc{4}}_{ip}\\}$ is $<$-complete follows from
$\\{{\mathpzc{0}}_{ip}\\}$ being able to define $<$ and from Lemma 2.3. ∎

###  3.3. Definability for $\mathfrak{M}^{+}$-Relations in $\mathsf{Den}$

To continue studying how the density hypothesis influences the ability of the
sub-languages to express our relations, we focus now on mixed relations.

${\mathpzc{0}}_{ip}$ |  ${\mathpzc{1}}_{ip}$ |  ${\mathpzc{2}}_{ip}$
---|---|---
$\\{{\mathpzc{1}}_{ip},<\\}$ |  $\bm{\\{{\mathpzc{0}}_{ip}\\}}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$
$\bm{\\{{\mathpzc{2}}_{ip},<\\}}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\bm{\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}}$ |  $\bm{\\{{\mathpzc{0}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\bm{\\{{\mathpzc{2}}_{ip},<\\}}$ |  $\bm{\\{{\mathpzc{0}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\bm{\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}}$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{0}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}}$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$
$\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$
$\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$
$\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$
$\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},\\}}$ |  $\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$
$\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$
$\\{{\mathpzc{3}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$
$\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ |  |  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$
$\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  |  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$
$\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$
$\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}}$ |  |  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$
$\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ |  |  $\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}}$
$\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  |  $\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$
$\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  |  $\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$
|  |  $\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}}$
|  |  $\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$
Table 9. The spectrum of the $\mathsf{mcs}(r)$, for each
$r\in\mathfrak{M}^{+}$. - Class: $\mathsf{Den}$.

######  Lemma .

Tab. 9 is correct.

###### Proof.

As for the $\\{{\mathpzc{0}}_{ip}\\}$-completeness, only one new definition is
necessary:

$\begin{array}[]{llll}x_{i}{\mathpzc{0}}_{ip}y_{p}&\leftrightarrow&\exists
k_{p}(\forall z_{p}(x_{i}{\mathpzc{2}}_{ip}z_{p}\rightarrow k_{p}<z_{p})\wedge
y_{p}<k_{p})&\\{{\mathpzc{2}}_{ip},<\\}\end{array}$

Let us prove that the set $\\{{\mathpzc{2}}_{ip},<\\}$ is
${\mathpzc{0}}_{ip}$-complete. If $\mathcal{F}\models\varphi(x_{i},y_{p})$,
then there exists a point $k_{p}$ smaller than every point contained in
$x_{i}$ (there are infinitely many such points because we are in a dense
structure); and $y_{p}$ is smaller than $k_{p}$, so it must be before $x_{i}$.
If, on the other hand $x_{i}=[a,b]$ and $y_{p}=c<a$, we take $k_{p}=a$ to
satisfy all requirements. The ${\mathpzc{0}}_{ip}$-completeness of the
remaining new sets is now a consequence of the
${\mathpzc{0}}_{ip}$-completeness and previously established results. We will
give the details of the deductions chains involved. For
$\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$, note that
$\\{{\mathpzc{4}}_{ip}\\}\rightarrow_{\mathsf{Den}}\><$ (Table 8) and that
$\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},<\\}\rightarrow_{\mathsf{Lin}}{\mathpzc{0}}_{ip}$
(Table 4). For the cases
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$,
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$, we note that
$\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}$, $\\{{\mathpzc{0}\mathpzc{4}}_{ii}\\}$
and $\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ all define $=_{i}$ over
$\mathsf{Den}$ (Table 8), and then that
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},=_{i}\\}$,
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii},=_{i}\\}$ and
$\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},=_{i}\\}$ all define
${\mathpzc{0}}_{ip}$ over $\mathsf{Lin}$ (Table 4). The cases for
$\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$,
$\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{3}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ follow similarly,
using that $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},=_{i}\\}$,
$\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii},=_{i}\\}$ and
$\\{{\mathpzc{3}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},=_{i}\\}$ all define
${\mathpzc{0}}_{ip}$ over $\mathsf{Lin}$ (Table 4). Considering the
${\mathpzc{0}}_{ip}$-completeness of
$\\{{\mathpzc{4}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$, we again use the
fact that $\\{{\mathpzc{4}}_{ip}\\}\rightarrow_{\mathsf{Den}}\><$ (Table 8)
and that
$\\{{\mathpzc{4}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii},<\\}\rightarrow_{\mathsf{Lin}}{\mathpzc{0}}_{ip}$
(Table 4). In the case of
$\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ the chain of
deductions goes as follows:
$\\{{\mathpzc{4}}_{ip}\\}\rightarrow_{\mathsf{Den}}\><$ (Table 8),
$\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}\rightarrow_{\mathsf{Den}}\>{\mathpzc{1}\mathpzc{4}}_{ii}$
(Table 6) and hence, by Lemma 2.3,
$\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}\rightarrow_{\mathsf{Den}}\>{\mathpzc{0}\mathpzc{3}}_{ii}$,
and lastly
$\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}\rightarrow_{\mathsf{Lin}}{\mathpzc{0}}_{ip}$
(Table 4). In the case of
$\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$, recall that
$\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}\rightarrow_{\mathsf{Den}}{\mathpzc{3}\mathpzc{4}}_{ii}$
(Lemma 3.1), and then appeal to the just proved
${\mathpzc{0}}_{ip}$-completeness of
$\\{{\mathpzc{4}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$. In the case of
$\\{{\mathpzc{4}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ we use the fact that
$\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}\rightarrow_{\mathsf{Den}}{\mathpzc{3}\mathpzc{4}}_{ii}$
and again appeal to the case for
$\\{{\mathpzc{4}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$. As for proving that
$\\{{\mathpzc{0}}_{ip}\\}$ is ${\mathpzc{1}}_{ip}$-complete, observe that by
the previous lemma this set defines $<$, and consider the following simple
definition:

$\begin{array}[]{llll}x_{i}{\mathpzc{1}}_{ip}y_{p}&\leftrightarrow&\forall
z_{p}(x_{i}{\mathpzc{0}}_{ip}z_{p}\leftrightarrow
z_{p}<y_{p})&\\{{\mathpzc{0}}_{ip}\\}\\\ \end{array}$

The left to right direction of the above definition is immediate. For the
right to left direction, suppose, on the contrary, that the formula holds and
it is not the case that $x_{i}{\mathpzc{1}}_{ip}y_{p}$. Then, assume that
$x_{i}=[a,b]$: if $y_{p}<a$, then, since the underlying linear order is dense,
we could find $c$ such that $y_{p}<c<a$, and contradict the right-side by
instantiating $z_{p}$ with $c$, and if $a<y_{p}$, then since the underlying
linear order is dense, we could find $c$ such that $a<c<y_{p}$, and, again,
contradict the right-side by instantiating $z_{p}$ with $c$. Now, the
remaining new definitions for the relation ${\mathpzc{1}}_{ip}$ all follow
straightforwardly by noting that these sets all define ${\mathpzc{0}}_{ip}$.
Finally, we prove that
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ is
${\mathpzc{2}}_{ip}$-complete by means of the following definability equation:

$\begin{array}[]{llll}x_{i}{\mathpzc{2}}_{ip}y_{p}&\leftrightarrow&\exists
z_{i}(z_{i}{\mathpzc{1}}_{ip}y_{p}\wedge
z_{i}{\mathpzc{0}\mathpzc{4}}_{ii}x_{i}).&\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}\end{array}$

The ${\mathpzc{2}}_{ip}$-completeness of
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ is extremely simple.
Assuming $\mathcal{F}\models\varphi([a,b],c)$, there must be an interval
$z_{i}=[c,d]$ contained in $[a,b]$, which implies $a<c<b$, as we wanted.
Conversely, if $a<c<b$, since the structure is dense, we can find $d$ such
that $a<c<d<b$, and $z_{i}=[c,d]$ is a witness for $\varphi$. For the
${\mathpzc{2}}_{ip}$-completeness of
$\\{{\mathpzc{0}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$,
$\\{{\mathpzc{0}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{0}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ we note that facts
that $\\{{\mathpzc{0}}_{ip}\\}\rightarrow_{\mathsf{Den}}{\mathpzc{1}}_{ip}$,
that $\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}$,
$\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ each define
${\mathpzc{0}\mathpzc{4}}_{ii}$ over $\mathsf{Den}$, and the just proved
${\mathpzc{2}}_{ip}$-completeness of
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$. For
$\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ we note that
$\\{{\mathpzc{0}}_{ip}\\}\rightarrow_{\mathsf{Den}}\><$ and that
$\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}\rightarrow_{\mathsf{Lin}}{\mathpzc{2}}_{ip}$.
For $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ we again use the fact
that $\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ each define
${\mathpzc{0}\mathpzc{4}}_{ii}$ over $\mathsf{Den}$ and that
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}\rightarrow_{\mathsf{Den}}{\mathpzc{0}\mathpzc{2}}_{ii}$
as proved above. For $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$
and $\\{{\mathpzc{3}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ we use the facts
that $\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ each defines
${\mathpzc{1}\mathpzc{4}}_{ii}$ over $\mathsf{Den}$ and that
$\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}\rightarrow_{\mathsf{Lin}}{\mathpzc{2}}_{ip}$.
In the case of $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ we use
the facts that
$\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}\rightarrow_{\mathsf{Den}}{\mathpzc{3}\mathpzc{4}}_{ii}$
(Lemma 3.1) and that
$\\{{\mathpzc{3}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}\rightarrow_{\mathsf{Lin}}{\mathpzc{2}}_{ip}$.
For $\\{{\mathpzc{4}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ we use the
previously proven facts that
$\\{{\mathpzc{4}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}\rightarrow_{\mathsf{Den}}{\mathpzc{1}}_{ip}$
and
$\\{{\mathpzc{1}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}\rightarrow_{\mathsf{Lin}}{\mathpzc{2}}_{ip}$.
From this the cases for
$\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$,
$\\{{\mathpzc{4}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ now respectively
follow since
$\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}\rightarrow_{\mathsf{Den}}{\mathpzc{3}\mathpzc{4}}_{ii}$,
$\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}\rightarrow_{\mathsf{Den}}{\mathpzc{3}\mathpzc{4}}_{ii}$
and
$\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}\rightarrow_{\mathsf{Den}}{\mathpzc{3}\mathpzc{4}}_{ii}$
(Lemma 3.1). Lastly the ${\mathpzc{2}}_{ip}$-completeness of
$\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ follows by noting
that $\\{{\mathpzc{4}}_{ip}\\}\rightarrow_{\mathsf{Den}}\><$ and that
$\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},<\\}\rightarrow_{\mathsf{Lin}}{\mathpzc{2}}_{ip}$.
∎

###  3.4. Definability for Relations in $\mathfrak{I}^{+}\setminus\\{=_{i}\\}$
in $\mathsf{Den}$

${\mathpzc{1}\mathpzc{4}}_{ii}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$ |  ${\mathpzc{2}\mathpzc{4}}_{ii}$ |  ${\mathpzc{0}\mathpzc{4}}_{ii}$ |  ${\mathpzc{4}\mathpzc{4}}_{ii}$
---|---|---|---|---
$\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$
$\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$
$\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$
$\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
$\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\bm{\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\bm{\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\bm{\\{{\mathpzc{2}}_{ip}\\}}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
$\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\bm{\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\bm{\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$
$\bm{\\{{\mathpzc{2}}_{ip},<\\}}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
$\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{2}}_{ip},<\\}}$ |  $\\{{\mathpzc{2}}_{ip},<\\}$ |  |  $\bm{\\{{\mathpzc{2}}_{ip},<\\}}$
$\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$
$\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  |  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$
$\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$
$\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  |  $\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$
$\bm{\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
|  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$
|  $\bm{\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  |  $\bm{\\{{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$
|  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$
|  $\bm{\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$
|  |  |  |  $\bm{\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$
Table 10. The spectrum of the $\mathsf{mcs}(r)$, for each
$r\in\mathfrak{I}^{+}\setminus\\{=_{i}\\}$. - Class: $\mathsf{Den}$.

To conclude this analysis of dense linear orders, we prove that Tab. 10 is
correct.

######  Lemma .

Tab. 10 is correct.

###### Proof.

All new definitions involving only interval-interval relations have already
been treated in Lemma 3.1. All new
${\mathpzc{1}\mathpzc{4}}_{ii}$-completeness results follow from previously
proven facts, and we will give the deduction chains. For
$\\{{\mathpzc{2}}_{ip},<\\}$, we have that $\\{{\mathpzc{2}}_{ip},<\\}$
defines ${\mathpzc{0}}_{ip}$ in the dense case and that
$\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ defines
${\mathpzc{1}\mathpzc{4}}_{ii}$. The cases for
$\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ follow from Lemma 3.1
and the fact that $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ define
${\mathpzc{1}\mathpzc{4}}_{ii}$. The new
${\mathpzc{3}\mathpzc{4}}_{ii}$-completeness results are based on the
following arguments. For
$\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$, we have that
$\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ defines
${\mathpzc{2}}_{ip}$ in the dense case and that
$\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ defines
${\mathpzc{3}\mathpzc{4}}_{ii}$. For
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$, we know that
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ defines
${\mathpzc{2}}_{ip}$ in the dense case and that
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ defines
${\mathpzc{3}\mathpzc{4}}_{ii}$. For $\\{{\mathpzc{2}}_{ip},<\\}$, we have
that $\\{{\mathpzc{2}}_{ip},<\\}$ defines ${\mathpzc{0}}_{ip}$ in the dense
case and that $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ is
${\mathpzc{3}\mathpzc{4}}_{ii}$-complete. The cases for
$\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ were proven in Lemma
3.1. The ${\mathpzc{2}\mathpzc{4}}_{ii}$-completeness of the sets
$\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$,
$\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ follow from their
already proven ${\mathpzc{3}\mathpzc{4}}_{ii}$-completeness over
$\mathsf{Den}$ and the ${\mathpzc{2}\mathpzc{4}}_{ii}$-completeness of
${\mathpzc{3}\mathpzc{4}}_{ii}$ over $\mathsf{Lin}$. For the
${\mathpzc{0}\mathpzc{4}}_{ii}$-completeness of $\\{{\mathpzc{2}}_{ip}\\}$,
assuming density, recall that $\\{{\mathpzc{2}}_{ip}\\}$ is $=_{i}$-complete
in the dense case, and consider the following definition:

$\begin{array}[]{lllll}x_{i}{\mathpzc{0}\mathpzc{4}}_{ii}y_{i}&\leftrightarrow&&\forall
z_{p}(x_{i}{\mathpzc{2}}_{ip}z_{p}\rightarrow
y_{i}{\mathpzc{2}}_{ip}z_{p})\wedge\exists
z_{p}(y_{i}{\mathpzc{2}}_{ip}z_{p}\wedge\neg(x_{i}{\mathpzc{2}}_{ip}z_{p}))&\\{{\mathpzc{2}}_{ip}\\}\\\
&&\wedge&\exists z_{i}\exists z^{\prime}_{i}\left[\begin{array}[]{llll}&\neg
z_{i}=_{i}z^{\prime}_{i}\\\ \wedge&\forall
u_{p}[(z_{i}{\mathpzc{2}}_{ip}u_{p}\vee
z^{\prime}_{i}{\mathpzc{2}}_{ip}u_{p})\rightarrow(y_{i}{\mathpzc{2}}_{ip}u_{p}\wedge\neg
x_{i}{\mathpzc{2}}_{ip}u_{p})]\\\ \wedge&\forall
v_{i}\left[\begin{array}[]{lll}&(\forall
u_{p}(z_{i}{\mathpzc{2}}_{ip}u_{p}\vee
z^{\prime}_{i}{\mathpzc{2}}_{ip}u_{p}\rightarrow
v_{i}{\mathpzc{2}}_{ip}u_{p}))\\\ \rightarrow&\exists
t_{p}(x_{i}{\mathpzc{2}}_{ip}t_{p}\wedge
v_{i}{\mathpzc{2}}_{ip}t_{p})\end{array}\right]\end{array}\right]\end{array}$

First suppose that $\mathcal{F}\models\varphi([a,b],$ $[c,d])$. Then $[c,d]$
must contain every point contained by $[a,b]$, and there must be some point
contained in $[c,d]$ which is not contained in $[a,b]$. So we have $c\leq a$,
$b\leq d$ and $[a,b]\neq[c,d]$. (Note that here we are using the fact, which
follows from the density of the order, that $[a,b]$ contain at least one
point. If this were not the case, the first conjunct of $\phi$ would be
vacuously satisfied.) We need to show that $a\neq c$ and $d\neq b$. Suppose,
to the contrary, that $a=c$. Then we must have that $b<d$. Let $\psi$ denote
the third main conjunct of $\varphi$ and let $z_{i}=[e,f]$ and
$z^{\prime}_{i}=[g,h]$ be two intervals satisfying $\psi$. Then
$[e,f]\neq[g,h]$ by the first conjunct of $\psi$, while $b\leq e<f\leq d$ and
$b\leq g<h\leq d$. However now, taking $v_{i}=[b,d]$ falsifies the third
conjunct of $\psi$, as $[b,d]$ contains all points contained in either $[e,f]$
or $[g,h]$ while not containing any point contained in $x_{i}=[a,b]$. This is
a contradiction. Conversely, if $[a,b]{\mathpzc{0}\mathpzc{4}}_{ii}[c,d]$, the
the first conjunct of $\varphi$ holds trivially, while any point $e$ such that
$c<e<a$ or $b<e<d$ (which exists because the structure is dense) witnesses the
$z_{p}$ of the second conjunct. Taking $z_{i}=[c,a]$ and
$z^{\prime}_{i}=[b,d]$ witnesses the third conjunct. All that remains to be
proved is the ${\mathpzc{4}\mathpzc{4}}_{ii}$-completeness of the sets
$\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$,
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$,
$\\{{\mathpzc{2}}_{ip},<\\}$,
$\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$. But all of these
sets have already been shown to define ${\mathpzc{3}\mathpzc{4}}_{ii}$ over
$\mathsf{Den}$, and we know that $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ defines
${\mathpzc{4}\mathpzc{4}}_{ii}$ over $\mathsf{Lin}$. ∎

##  4\. Incompleteness Results in The Class $\mathsf{Den}$

We can now turn our attention to the maximal incomplete sets for relations in
$\mathfrak{R}^{+}$. Notice that for some $r\in\mathfrak{R}^{+}$ some
$r$-incomplete set in the class $\mathsf{Lin}$ is also maximally
$r$-incomplete in the class $\mathsf{Den}$; nevertheless, all proofs in Part I
must be revisited here, as they were designed to work not only in
$\mathsf{Lin}$ but also in $\mathsf{Dis}$, and therefore are not valid in
$\mathsf{Den}$.

Proved |  $=_{p}$ |  $=_{i}$ |  $<$ |  ${\mathpzc{0}}_{ip}$ |  ${\mathpzc{1}}_{ip}$ |  ${\mathpzc{2}}_{ip}$ |  ${\mathpzc{3}}_{ip}$ |  ${\mathpzc{4}}_{ip}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$ |  ${\mathpzc{1}\mathpzc{4}}_{ii}$ |  ${\mathpzc{0}\mathpzc{3}}_{ii}$ |  ${\mathpzc{2}\mathpzc{4}}_{ii}$ |  ${\mathpzc{0}\mathpzc{4}}_{ii}$ |  ${\mathpzc{4}\mathpzc{4}}_{ii}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$\\{{\mathpzc{2}}_{ip}\\}\cup\mathfrak{I}^{+}$ |  $\bullet$ |  |  |  |  |  |  |  |  |  |  |  |  |
$\\{=_{p},<,{\mathpzc{0}}_{ip},{\mathpzc{1}}_{ip}\\}$ |  |  $\bullet$ |  |  |  |  |  |  |  |  |  |  |  |
$\\{=_{p},=_{i},{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  |  |  $\bullet$ |  $\bullet$ |  |  |  |  |  |  |  |  |  |
$\\{=_{p},{\mathpzc{2}}_{ip}\\}\cup\mathfrak{I}^{+}$ |  |  |  $\bullet$ |  $\bullet$ |  $\bullet$ |  |  $\bullet$ |  $\bullet$ |  |  |  |  |  |
$\\{=_{p},=_{i},<,{\mathpzc{3}}_{ip},{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  |  |  |  $\bullet$ |  $\bullet$ |  $\bullet$ |  |  |  $\bullet$ |  $\bullet$ |  |  $\bullet$ |  $\bullet$ |  $\bullet$
$\\{=_{p},<\\}\cup\mathfrak{I}^{+}$ |  |  |  |  $\bullet$ |  $\bullet$ |  $\bullet$ |  $\bullet$ |  $\bullet$ |  |  |  |  |  |
$\\{=_{p},=_{i},<,{\mathpzc{0}}_{ip},{\mathpzc{1}}_{ip}\\}$ |  |  |  |  |  |  |  |  |  |  $\bullet$ |  |  |  |
$\\{=_{p},=_{i},{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  |  |  |  |  |  |  |  |  $\bullet$ |  $\bullet$ |  $\bullet$ |  $\bullet$ |  |  $\bullet$
$\\{=_{p},=_{i},<,{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  |  |  |  |  |  |  |  |  $\bullet$ |  $\bullet$ |  $\bullet$ |  $\bullet$ |  |  $\bullet$
Symmetric |  $=_{p}$ |  $=_{i}$ |  $<$ |  ${\mathpzc{0}}_{ip}$ |  ${\mathpzc{1}}_{ip}$ |  ${\mathpzc{2}}_{ip}$ |  ${\mathpzc{3}}_{ip}$ |  ${\mathpzc{4}}_{ip}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$ |  ${\mathpzc{1}\mathpzc{4}}_{ii}$ |  ${\mathpzc{0}\mathpzc{3}}_{ii}$ |  ${\mathpzc{2}\mathpzc{4}}_{ii}$ |  ${\mathpzc{0}\mathpzc{4}}_{ii}$ |  ${\mathpzc{4}\mathpzc{4}}_{ii}$
$\\{=_{p},<,{\mathpzc{3}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  |  $\bullet$ |  |  |  |  |  |  |  |  |  |  |  |
$\\{=_{p},=_{i},{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  |  |  $\bullet$ |  |  |  |  |  $\bullet$ |  |  |  |  |  |
$\\{=_{p},=_{i},<,{\mathpzc{0}}_{ip},{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  |  |  |  |  |  $\bullet$ |  $\bullet$ |  $\bullet$ |  $\bullet$ |  |  $\bullet$ |  $\bullet$ |  $\bullet$ |  $\bullet$
$\\{=_{p},=_{i},<,{\mathpzc{3}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  |  |  |  |  |  |  |  |  |  |  $\bullet$ |  |  |
Table 11. $\mathsf{MIS}(r)$, for each $r\in\mathfrak{R}^{+}$; upper part: sets
for which we give an explicit construction; lower part: symmetric ones. -
Class: $\mathsf{Den}$.

######  Lemma .

Tab. 11 is correct.

###### Proof.

Let $S$ be $\\{{\mathpzc{2}}_{ip}\\}\cup\mathfrak{I}^{+}$: proving that it is
$=_{p}$-incomplete is almost immediate. Indeed, it suffices to take
$\mathbb{D}$ and $\mathbb{D}^{\prime}$ both equal to the subset of
$\mathbb{Q}$ of all points between $0$ and $1$, $\zeta=(\zeta_{p},\zeta_{i})$,
where $\zeta_{i}=Id_{i}$ (the identical relation on intervals),
$\zeta_{p}=\\{(0,1^{\prime})\\}$ plus the identical relation on points to have
a surjective truth-preserving relation that breaks $=_{p}$. Proving that
$\\{=_{p},<,{\mathpzc{0}}_{ip},{\mathpzc{1}}_{ip}\\}$ is $=_{i}$-incomplete is
equally easy: it suffices to take $\mathbb{D}=\mathbb{D}^{\prime}=\mathbb{Q}$,
$\zeta_{p}=Id_{p}$, and $\zeta_{i}=Id_{i}$ plus
$\zeta_{i}([0,2],[0^{\prime},1^{\prime}])$. Assume, now, $S$ to be
$\\{=_{p},=_{i},{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$; we need
to prove its $<,{\mathpzc{0}}_{ip}$-incompleteness in the dense case. Let
$\mathbb{D}=\mathbb{D}^{\prime}=\mathbb{Q}$, and define
$\zeta=\zeta_{p}\cup\zeta_{i}$ as follows: $(a,-a^{\prime})\in\zeta_{p}$ for
every $a\in\mathbb{Q}$, and
$([a,b],[-a^{\prime},-a^{\prime}+|b^{\prime}-a^{\prime}|])\in\zeta_{i}$ for
every $[a,b]\in\mathbb{I}(\mathbb{Q})$, so that the length of every interval
is preserved while their beginning point are reflected over 0; as this
relation breaks both $<$ and ${\mathpzc{0}}_{ip}$, the latter cannot be
expressed in this language. Let now $S$ be
$\\{=_{p},{\mathpzc{2}}_{ip}\\}\cup\mathfrak{I}^{+}$: we can prove that it is
$<,{\mathpzc{0}}_{ip},{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip},{\mathpzc{4}}_{ip}$-incomplete.
To this end, it suffices to take, once again, $\mathbb{D}$ and
$\mathbb{D}^{\prime}$ both equal to the subset of $\mathbb{Q}$ of all points
between $0$ and $1$, $\zeta=(\zeta_{p},\zeta_{i})$, where $\zeta_{i}=Id_{i}$
(the identical relation on intervals),
$\zeta_{p}=\\{(0,1^{\prime}),(1,0^{\prime})\\}$ plus the identical relation on
every other point to have a surjective truth-preserving relation that breaks
the relations under analysis. As for
S=$\\{=_{p},=_{i},<,{\mathpzc{3}}_{ip},{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$,
we can prove its
${\mathpzc{0}}_{ip},{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip},i$-incompleteness,
where
$i\in\mathfrak{I}^{+}\setminus\\{=_{i},\linebreak{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
by defining two $\mathbb{Q}$-based structures and a relation between them
defined as the identity between points and as
$\zeta_{i}([a,b])=[a^{\prime}-|b^{\prime}-a^{\prime}|,b^{\prime}]$, obtaining
(as we did for the same set of relations on $\mathsf{Lin}$, using, in that
case, a pseudo-discrete structure) a relation that maps every interval to the
interval with the same ending point but twice the length. In this way, all
relations in $S$ are respected. The $m$-incompleteness of
$\\{=_{p},<\\}\cup\mathfrak{I}^{+}$ for each $m\in\mathfrak{M}^{+}$ can be
proved by taking again $\mathbb{D}=\mathbb{D}^{\prime}=\mathbb{Q}$,
$\zeta=(\zeta_{p},\zeta_{i})$, where $\zeta_{i}=Id_{i}$ and
$\zeta_{p}(a)=a^{\prime}+1$ for every $a\in\mathbb{Q}$, which clearly respects
all interval-interval relations, and both equality and relative ordering
between points, but breaks every relation between points and intervals. When
$S$ is $\\{=_{p},=_{i},<,{\mathpzc{0}}_{ip},{\mathpzc{1}}_{ip}\\}$, we have to
prove that it is ${\mathpzc{1}\mathpzc{4}}_{ii}$-incomplete. Consider two
structures based on $\mathbb{Q}$, and let $\zeta=(\zeta_{p},\zeta_{i})$ be
defined as $\zeta_{p}=Id_{p}$, and $\zeta_{i}=Id_{i}$ except for the interval
$[-1,0]$, which is mapped to $[-1,1]$. When $S$ is
$\\{=_{p},=_{i},{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$, we have
to prove that it is $r$-incomplete in the dense case for
$r\in\mathfrak{I}^{+}\setminus\\{{\mathpzc{0}\mathpzc{4}}_{ii},=_{i}\\}$.
Consider two structures based on $\mathbb{Q}$, and let
$\zeta=(\zeta_{p},\zeta_{i})$ be defined as $\zeta_{p}(a)=-a^{\prime}$ for
every point and $\zeta_{i}([a,b])=[-b^{\prime},-a^{\prime}]$ for every
interval. Clearly, containment is respected for both sorts; nevertheless, all
other interval-interval relations are broken. Finally, when $S$ is
$\\{=_{p},=_{i},<,{\mathpzc{0}\mathpzc{4}}_{ii}\\}$, we have to prove that it
is $r$-incomplete for
$r\in\mathfrak{I}^{+}\setminus\\{=_{i},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$.
Consider two structures based on $\mathbb{Q}$, and let
$\zeta=(\zeta_{p},\zeta_{i})$ be defined as $\zeta_{p}=Id_{p}$, and
$\zeta_{i}([a,b])=[-b,-a]$; again, we respect containment between intervals,
and the relative ordering between points is respected as well (since points
are not affected by the construction), and we break every other interval-
interval relation. ∎

##  5\. Completeness Results in the Class $\mathsf{Unb}$

The ability of fragments of our language to define relations when the
underlying linear order is unbounded (but not necessarily discrete or dense)
differs from the dense/discrete cases only slightly. Following the same
schema, we now focus on the definability part, again, pointing out the
differences with the linear case.

###  5.1. Definability in $\mathfrak{I}^{+}$ and in $\mathfrak{M}^{+}$.

We begin our study of definability over the Class $\mathsf{Unb}$ by
considering minimal definability of $\mathfrak{I}^{+}$ relations by sets of
$\mathfrak{I}^{+}$ relations, and then of $\mathfrak{M}^{+}$ relations by sets
of $\mathfrak{M}^{+}$ relations.

${\mathpzc{1}\mathpzc{4}}_{ii}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$ |  ${\mathpzc{2}\mathpzc{4}}_{ii}$ |  ${\mathpzc{0}\mathpzc{4}}_{ii}$ |  ${\mathpzc{4}\mathpzc{4}}_{ii}$
---|---|---|---|---
$\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$
$\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
$\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$
$\bm{\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
|  $\bm{\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$
|  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  |  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$
|  $\bm{\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  |  |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$
Table 12. The spectrum of the $\mathsf{mcs}(r)$, for each
$r\in\mathfrak{I}^{+}\setminus\\{=_{i}\\}$. - Class: $\mathsf{Unb}$.

######  Lemma .

Tab. 12 is correct.

###### Proof.

To prove that $\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ is
${\mathpzc{1}\mathpzc{4}}_{ii}$-complete we ue the same definition as was used
in the dense case in Lemma 3.1:

$\begin{array}[]{llll}x_{i}{\mathpzc{1}\mathpzc{4}}_{ii}y_{i}&\leftrightarrow&\forall
z_{i}(z_{i}{\mathpzc{4}\mathpzc{4}}_{ii}x_{i}\leftrightarrow
z_{i}{\mathpzc{4}\mathpzc{4}}_{ii}y_{i})\wedge\exists
z_{i}(x_{i}{\mathpzc{4}\mathpzc{4}}_{ii}z_{i}\wedge\neg(y_{i}{\mathpzc{4}\mathpzc{4}}_{ii}z_{i})).&\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}\end{array}$

The argument for the correctness of this definition is the same as in the
dense case except that, when arguing that
$[a,b]{\mathpzc{1}\mathpzc{4}}_{ii}[c,d]$ implies $\phi([a,b],[c,d])$, we
appeal to unboundedness rather than density to justify the existence of the
interval required by the second conjunct of the definition. As before, the
${\mathpzc{3}\mathpzc{4}}_{ii}$-completeness of
$\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ now follows via
${\mathpzc{3}\mathpzc{4}}_{ii}$-completeness of
$\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ over all
linear orders. Now, since ${\mathpzc{3}\mathpzc{4}}_{ii}$ defines all
interval-interval relations over all linear orders, it follows that
${\mathpzc{4}\mathpzc{4}}_{ii}$ is also complete with respect all other
interval-interval relations over unbounded orders. To compete the proof, it
suffices to show the ${\mathpzc{3}\mathpzc{4}}_{ii}$-completeness of
$\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$. We do so
by proving, as we did in Lemma 3.1 of Part I of this paper, that this set is
able to express the weaker relation
${\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii}$:

$\begin{array}[]{llll}x_{i}{\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii}y_{i}&\leftrightarrow&\exists
z_{i},k_{i}(x_{i}{\mathpzc{0}\mathpzc{4}}_{ii}z_{i}\wedge
y_{i}{\mathpzc{0}\mathpzc{4}}_{ii}k_{i}\wedge
z_{i}{\mathpzc{2}\mathpzc{4}}_{ii}k_{i})\wedge&\\{{\mathpzc{0}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}\\\
&&\exists
z_{i}(x_{i}{\mathpzc{0}\mathpzc{4}}_{ii}z_{i}\wedge\neg(y_{i}{\mathpzc{0}\mathpzc{4}}_{ii}z_{i}))\wedge\exists
k_{i}(y_{i}{\mathpzc{0}\mathpzc{4}}_{ii}k_{i}\wedge\neg(x_{i}{\mathpzc{0}\mathpzc{4}}_{ii}k_{i}))\wedge&\\\
&&\neg(x_{i}{\mathpzc{2}\mathpzc{4}}_{ii}y_{i})\wedge\neg(y_{i}{\mathpzc{2}\mathpzc{4}}_{ii}x_{i})\wedge\neg(x_{i}{\mathpzc{0}\mathpzc{4}}_{ii}y_{i})\wedge\neg(y_{i}{\mathpzc{0}\mathpzc{4}}_{ii}x_{i}).\end{array}$

If $\mathcal{F}\models\varphi([a,b],[c,d])$ over an unbounded structure, we
can eliminate all possibilities for the relationship between $[a,b]$ and
$[c,d]$ other than ${\mathpzc{3}\mathpzc{4}}_{ii}$ and
${\mathpzc{4}\mathpzc{4}}_{ii}$. Indeed, first observe that $x_{i}$ and
$y_{i}$ cannot overlap nor contain each other. Next, if $y_{i}$ ends before
$x_{i}$ or at its beginning point, it would be impossible to place $z_{i}$ and
$k_{i}$. Finally, if $x_{i}$ starts or finishes $y_{i}$, or the other way
around, we have a contradiction with the second or the third requirement of
$\varphi$. This implies that $x_{i}$ meets or is before $y_{i}$. Conversely,
if $[a,b]{\mathpzc{3}\mathpzc{4}}_{ii}\vee{\mathpzc{4}\mathpzc{4}}_{ii}[c,d]$,
then we can take $z_{i}=[e,d]$, where $e<a$, and $k_{i}=[a,f]$, where $d<f$,
and the existence of $e$ and $f$ is guaranteed by the assumption of
unboundedness. ∎

###  5.2. Definability for the Relations $=_{p},=_{i},<$ in $\mathsf{Unb}$

$=_{p}$ |  $=_{i}$ |  $<$
---|---|---
$\\{<\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\bm{\\{{\mathpzc{0}}_{ip}\\}}$
$\bm{\\{{\mathpzc{0}}_{ip}\\}}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$
$\bm{\\{{\mathpzc{2}}_{ip}\\}}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$
$\\{{\mathpzc{1}}_{ip}\\}$ |  $\bm{\\{{\mathpzc{0}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$
$\\{{\mathpzc{3}}_{ip}\\}$ |  $\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
$\bm{\\{{\mathpzc{4}}_{ip}\\}}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$
|  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$
|  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\bm{\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$
|  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$
|  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\bm{\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}}$
|  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{2}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$
|  $\bm{\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}}$
|  $\\{{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\bm{\\{{\mathpzc{2}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}}$
|  $\\{{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\bm{\\{{\mathpzc{2}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$
|  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$
|  $\bm{\\{{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ |  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$
|  $\bm{\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$
|  |  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$
|  |  $\bm{\\{{\mathpzc{3}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$
|  |  $\bm{\\{{\mathpzc{4}}_{ip}\\}}$
Table 13. The spectrum of the $\mathsf{mcs}(r)$, for each
$r\in\\{=_{p},=_{i},<\\}$. - Class: $\mathsf{Unb}$.

######  Lemma .

Tab. 13 is correct.

###### Proof.

Starting with $=_{p}$, we have now that every mixed relation is
$=_{p}$-complete, as follows:

$\begin{array}[]{llll}x_{p}=_{p}y_{p}&\leftrightarrow&\forall
x_{i}(x_{i}~{}m~{}x_{p}\leftrightarrow
x_{i}~{}m~{}y_{p}).&\\{m\\},~{}m\in\mathfrak{M}^{+}\end{array}$

Observe that this definition is the same that we have used in the dense case
for ${\mathpzc{0}}_{ip}$ and ${\mathpzc{4}}_{ip}$; the difference is that now,
because of the unboundedness hypothesis, the argument also works for
$\underline{\\{{\mathpzc{2}}_{ip}\\}}$, as we now prove. The left to right
direction if immediate. We argue contrapositively for the other implication.
Suppose that $x_{p}=a$ and $y_{p}=b$ are not equal. Without loss of generality
we can assume that $x_{p}<y_{p}$. Since the underlying domain is unbounded,
there must be a point $c<a$, and therefore, the interval $[c,b]$ is such that
$[c,b]{\mathpzc{2}}_{ip}a$ but it is not the case that
$[c,b]{\mathpzc{2}}_{ip}b$, falsifying the right-hand side. Notice that this
argument does not work on dense structures that are left/right bounded, such
as $[0,1]\subset\mathbb{Q}$. Now, consider the relation $=_{i}$, and the
following definitions:

$x_{i}=_{i}y_{i}\leftrightarrow\left\\{\begin{array}[]{ll}\forall
z_{p}(x_{i}{\mathpzc{0}}_{ip}z_{p}\leftrightarrow
y_{i}{\mathpzc{0}}_{ip}z_{p})\wedge\forall
u_{i}(x_{i}{\mathpzc{2}\mathpzc{4}}_{ii}u_{i}\leftrightarrow
y_{i}{\mathpzc{2}\mathpzc{4}}_{ii}u_{i})&\\{{\mathpzc{0}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}\\\
&\\\ \forall z_{p}(x_{i}{\mathpzc{1}}_{ip}z_{p}\leftrightarrow
y_{i}{\mathpzc{1}}_{ip}z_{p})\wedge\forall
u_{i}(x_{i}{\mathpzc{2}\mathpzc{4}}_{ii}u_{i}\leftrightarrow
y_{i}{\mathpzc{2}\mathpzc{4}}_{ii}u_{i})&\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}\\\
&\\\ \forall z_{i}(x_{i}{\mathpzc{0}\mathpzc{4}}_{ii}z_{i}\leftrightarrow
y_{i}{\mathpzc{0}\mathpzc{4}}_{ii}z_{i})\wedge\forall
z_{i}(z_{i}{\mathpzc{0}\mathpzc{4}}_{ii}x_{i}\leftrightarrow
z_{i}{\mathpzc{0}\mathpzc{4}}_{ii}y_{i})&\\{{\mathpzc{0}\mathpzc{4}}_{ii}\\}\\\
&\\\ \forall z_{i}(x_{i}{\mathpzc{4}\mathpzc{4}}_{ii}z_{i}\leftrightarrow
y_{i}{\mathpzc{4}\mathpzc{4}}_{ii}z_{i})\wedge\forall
z_{i}(z_{i}{\mathpzc{4}\mathpzc{4}}_{ii}x_{i}\leftrightarrow
z_{i}{\mathpzc{4}\mathpzc{4}}_{ii}y_{i}).&\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}\\\
\end{array}\right.$

First take the set
$\underline{\\{{\mathpzc{0}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$. If
$x_{i}=_{i}y_{i}$ we immediately have $\varphi(x_{i},y_{i})$. Conversely,
suppose $x_{i}=[a,b]\neq_{i}[c,d]=y_{i}$, so either $a\neq c$ or $b\neq d$. In
the first case the first conjunct of $\varphi$ is falsified. Assume therefore
that $a=c$ but that $b\neq d$ and, w.l.o.g., that $b<d$. Since the order is
unbounded, there is a point $e>d$. Then
$[c,d]{\mathpzc{2}\mathpzc{4}}_{ii}[b,e]$ but
$\neg([a,b]{\mathpzc{2}\mathpzc{4}}_{ii}[b,e])$, falsifying the second
conjunct. The argument in the case of
$\underline{\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ is
virtually identical. The $=_{i}$-completeness of
$\underline{\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ and
$\underline{\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$ follows
by symmetry (Lemma 2.3). Consider the set
$\\{{\mathpzc{0}\mathpzc{4}}_{ii}\\}$. If $x_{i}=_{i}y_{i}$ we immediately
have $\varphi(x_{i},y_{i})$. Conversely, suppose that $[a,b]\neq_{i}[c,d]$, so
either $a\neq c$ or $b\neq d$. Consider, w.l.o.g., the case $a\neq c$,
specifically $a<c$. We then choose a point $e>\max\\{b,d\\}$, which does exist
because the underlying domain is unbounded. Now, we have that
$[c,d]{\mathpzc{0}\mathpzc{4}}_{ii}[a,e]$, but it is not the case that
$[a,b]{\mathpzc{0}\mathpzc{4}}_{ii}[a,e]$, falsifying the right-hand side. The
other case is treated with a similar argument. Let us now focus on $<$. Five
new definitions are needed:

$x_{p}<y_{p}\leftrightarrow\left\\{\begin{array}[]{ll}\forall
x_{i}(x_{i}{\mathpzc{0}}_{ip}y_{p}\rightarrow
x_{i}{\mathpzc{0}}_{ip}x_{p})\wedge\exists
x_{i}(x_{i}{\mathpzc{0}}_{ip}x_{p}\wedge\neg(x_{i}{\mathpzc{0}}_{ip}y_{p}))&\\{{\mathpzc{0}}_{ip}\\}\\\
&\\\ \exists x_{i}y_{i}(x_{i}{\mathpzc{1}}_{ip}x_{p}\wedge
y_{i}{\mathpzc{1}}_{ip}y_{p}\wedge
x_{i}{\mathpzc{2}\mathpzc{4}}_{ii}y_{i})&\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}\\\
&\\\ \exists x_{i}y_{i}(x_{i}{\mathpzc{2}}_{ip}x_{p}\wedge
y_{i}{\mathpzc{2}}_{ip}y_{p}\wedge\neg(x_{i}{\mathpzc{2}}_{ip}y_{p})\wedge\neg(y_{i}{\mathpzc{2}}_{ip}x_{p})\wedge
x_{i}{\mathpzc{2}\mathpzc{4}}_{ii}y_{i})&\\{{\mathpzc{2}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}\\\
&\\\ \exists x_{i}y_{i}(x_{i}{\mathpzc{2}}_{ip}x_{p}\wedge
y_{i}{\mathpzc{2}}_{ip}y_{p}\wedge\neg(x_{i}{\mathpzc{2}}_{ip}y_{p})\wedge
x_{i}{\mathpzc{1}\mathpzc{4}}_{ii}y_{i})&\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}\\\
&\\\ \exists x_{i}y_{i}(x_{i}{\mathpzc{2}}_{ip}x_{p}\wedge
y_{i}{\mathpzc{2}}_{ip}y_{p}\wedge\neg(x_{i}{\mathpzc{2}}_{ip}y_{p})\wedge\neg(y_{i}{\mathpzc{2}}_{ip}x_{p})\wedge&\\{{\mathpzc{2}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}\\\
\hskip 25.6073pt\exists
z_{i},t_{i}(z_{i}{\mathpzc{4}\mathpzc{4}}_{ii}y_{i}\wedge\neg(z_{i}{\mathpzc{4}\mathpzc{4}}_{ii}x_{i})\wedge
x_{i}{\mathpzc{4}\mathpzc{4}}_{ii}t_{i}\wedge\neg(y_{i}{\mathpzc{4}\mathpzc{4}}_{ii}t_{i})))\\\
\end{array}\right.$

Consider, first the set $\\{{\mathpzc{0}}_{ip}\\}$. Suppose that
$\mathcal{F}\models\varphi(a,b)$, and, for the sake of contradiction, that
$a\geq b$. If $a=b$, then every interval $[c,d]$ such that
$[c,d]{\mathpzc{0}}_{ip}a$ must be such that $[c,d]{\mathpzc{0}}_{ip}b$ as
well, contradicting the second conjunct, and, if $b<a$ then, by unboundedness,
there exists an interval $[a,c]$ such that $[a,c]{\mathpzc{0}}_{ip}b$ but it
is not the case that $[a,c]{\mathpzc{0}}_{ip}a$, contradicting the first
conjunct. On the other hand, suppose that $x_{p}=a<b$. Then if
$[c,d]{\mathpzc{0}}_{ip}b$, we have $b<c$ and hence $a<c$, therefore
$[c,d]{\mathpzc{0}}_{ip}a$, satisfying the first conjunct. For the sake of the
second conjunct, consider any interval $[b,c]$: such an interval exists by
unboundedness and clearly $[b,c]{\mathpzc{0}}_{ip}a$ while it is not the case
that $[b,c]{\mathpzc{0}}_{ip}b$. Consider, now, the set
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$. If $x_{p}=a<b=y_{p}$
then, by unboundedness, we may choose points $c$ and $d$ such that $a<b<c<d$.
Then the intervals $x_{i}=[a,c]$ and $y_{i}=[b,d]$ witness $\varphi$.
Conversely, if $\mathcal{F}\models\varphi(a,b)$, then there must be intervals
$[a,c]$ and $[b,d]$ such that $[a,c]{\mathpzc{2}\mathpzc{4}}_{ii}[b,d]$, i.e.
such that $a<b<c<d$. So, in particular, $a<b$. As for
$\\{{\mathpzc{2}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$, suppose that
$\mathcal{F}\models\varphi(a,b)$, and, by contradiction, that $a\geq b$. If
$a=b$, then for any interval containing $a$ also contains $b$, and vice versa,
making the first three conjuncts not simultaneously satisfiable. If, on the
other hand, $b<a$, any interval containing $b$ must start before $a$, and
therefore no interval containing $a$ can overlap an interval containing $b$,
making $\varphi(a,b)$ false. Conversely, assume that $a<b$. By unboundedness
we can take two intervals $[c,b]$ such that $c<a$ and $[a,d]$ such that $b<d$
to witness $\varphi(a,b)$, as we wanted. As for
$\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$, suppose that
$\mathcal{F}\models\varphi(a,b)$, and, by contradiction, that $a\geq b$. If
$a=b$, then $a$ and $b$ are contained by the same intervals, making the first
three conjuncts not simultaneously satisfiable. If, on the other hand, $b<a$,
then any interval containing $a$ but not $b$ must start at $b$ or after, and
therefore it cannot start an interval containing $b$, falsifying
$\varphi(a,b)$. Conversely, suppose that $a<b$: then, the intervals $[a,b]$
and $[a,c]$ for some $c>b$ witness $\varphi(a,b)$, as we wanted. Finally, as
for $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$, suppose that
$\mathcal{F}\models\varphi(a,b)$, and, by contradiction, that $a\geq b$. If
$a=b$, then $a$ and $b$ are contained by the same intervals, making the first
four conjuncts not simultaneously satisfiable. If, on the other hand, $b<a$,
then any interval containing $a$ but not $b$ must start at $b$ or after it,
and every interval containing $b$ but not $a$ must end at $a$ or before it;
thus, $z_{i}$ and $t_{i}$ cannot be witnessed by any concrete interval, as
$z_{i}$ should end before $y_{i}$ starts but not before $x_{i}$ does, and,
symmetrically, $x_{i}$ should end before $t_{i}$ starts but not before $y_{i}$
does. Conversely, suppose that $a<b$: then, any interval of the type $[c,b]$
($c<a$) serves as witness of $x_{i}$, and any interval of the type $[a,d]$
($d>b$) serves as witness of $y_{i}$, while $z_{i}$ and $t_{i}$ are witnessed
by any intervals $[e,c]$ ($e<c$) and $[d,f]$ ($d<f$), respectively. Such
points $c$, $d$, $e$ and $f$ exist thanks to the unboundedness of the order.
Every other definition is now straightforward. The cases for
$\underline{\\{{\mathpzc{2}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}}$ follows
since $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ defines
${\mathpzc{1}\mathpzc{4}}_{ii}$ in the general case and the just-proved
$<$-completeness of $\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$.
The cases for
$\underline{\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$ and
$\underline{\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ follow
since both $\\{{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ define $=_{i}$ in the unbounded case and
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii},=_{i}\\}$ define $<$ in
the general case. The remaining cases, viz.
$\underline{\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}}$,
$\underline{\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}$,
$\underline{\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}}$,
$\underline{\\{{\mathpzc{3}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}}$ and
$\underline{\\{{\mathpzc{4}}_{ip}\\}}$, now follow by symmetry and Lemma 2.3
from the already-proved cases for
$\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$,
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$,
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$,
$\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{0}}_{ip}\\}$, respectively. ∎

###  5.3. Definability for $\mathfrak{M}^{+}$-Relations in $\mathsf{Unb}$

Because the relationship between definability of $\mathfrak{M}^{+}$ and
$\mathfrak{I}^{+}$ over unbounded orders is somewhat involved, the
corresponding results cannot be kept as neatly apart as e.g. in the dense
case. We therefore first present and prove two lemmas (Lemmas 5.3 and 5.3)
which collect some key definability results for $\mathfrak{M}^{+}$ and
$\mathfrak{I}^{+}$, respectively. These results are then used to prove the
full collection of minimal definability results for $\mathfrak{M}^{+}$ and
$\mathfrak{I}^{+}$ (Lemmas 5.3 and 5.4).

######  Lemma .

Over unbounded linear orders the sets
$\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii},<\\}$ and
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ are
${\mathpzc{0}}_{ip}$-complete, the set $\\{{\mathpzc{0}}_{ip}\\}$ is
${\mathpzc{1}}_{ip}$-complete, while the sets
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$,
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$,
$\\{{\mathpzc{0}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ and
$\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ are
${\mathpzc{2}}_{ip}$-complete.

###### Proof.

Consider the following definition of ${\mathpzc{0}}_{ip}$ in terms of
${\mathpzc{2}}_{ip}$,${\mathpzc{0}\mathpzc{4}}_{ii}$ and $<$:

$\begin{array}[]{llll}x_{i}{\mathpzc{0}}_{ip}y_{p}&\leftrightarrow&\exists
z_{i}(x_{i}{\mathpzc{0}\mathpzc{4}}_{ii}z_{i}\wedge\forall
k_{p}(z_{i}{\mathpzc{2}}_{ip}k_{p}\rightarrow
y_{p}<k_{p})).&\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii},<\\}\end{array}$

Proceeding as always, suppose that $\mathcal{F}\models\varphi([a,b],c)$. Let
$z_{i}=[d,e]$ the interval witnessing $\varphi$, so that $d<a<b<e$. Since
$z_{i}{\mathpzc{2}}_{ip}a$ by definition it follows that $c<a$, i.e. that
$[a,b]{\mathpzc{0}}_{ip}c$. Conversely, suppose that
$[a,b]{\mathpzc{0}}_{ip}c$. Since the underlying order is unbounded there is a
point $d$ such that $b<d$. Then the interval $[c,d]$ witnesses the definition.
As for ${\mathpzc{1}}_{ip}$, we show that $\\{{\mathpzc{0}}_{ip}\\}$ is
${\mathpzc{1}}_{ip}$-complete by noticing that $\\{{\mathpzc{0}}_{ip}\\}$ is
$<,=_{p}$-complete and by using the following, straightforward definition:

$\begin{array}[]{llll}x_{i}{\mathpzc{1}}_{ip}y_{p}&\leftrightarrow&\forall
z_{p}(x_{i}{\mathpzc{0}}_{ip}z_{p}\rightarrow z_{p}<y_{p})\wedge\forall
z_{p}(\neg(x_{i}{\mathpzc{0}}_{ip}z_{p})\rightarrow(y_{p}<z_{p}\vee
y_{p}=_{p}z_{p})).&\\{{\mathpzc{0}}_{ip}\\}\end{array}$

Finally, consider the following two new definitions for ${\mathpzc{2}}_{ip}$:

$x_{i}{\mathpzc{2}}_{ip}y_{p}\leftrightarrow\left\\{\begin{array}[]{ll}\exists
z_{i}(z_{i}{\mathpzc{1}}_{ip}y_{p}\wedge
x_{i}{\mathpzc{2}\mathpzc{4}}_{ii}z_{i})&\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}\\\
&\\\ \neg(x_{i}{\mathpzc{1}}_{ip}y_{p})\wedge\exists
z_{i}(z_{i}{\mathpzc{1}}_{ip}y_{p}\wedge\forall
k_{i}(x_{i}{\mathpzc{0}\mathpzc{4}}_{ii}k_{i}\rightarrow
z_{i}{\mathpzc{0}\mathpzc{4}}_{ii}k_{i})).&\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}\\\
\end{array}\right.$

The first one, namely
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$, is straightforward.
As for $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$, suppose first