1–LABEL:LastPageFeb. 06, 2014Jun. 19, 2018

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

Willem Conradie  School of Mathematics, University of the Witwatersrand
Johannesburg, South Africa<EMAIL_ADDRESS>,  Salih Durhan  Nesin
Mathematics Village
Sirince, Turkey<EMAIL_ADDRESS>and  Guido Sciavicco  Department 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.

###### Key words and phrases:

Interval-based Temporal Logics; Expressiveness; 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

We would like to thank Dr. Davide Bresolin, of the University of Padova, for
his help. The research of the first author was supported by the National
Research Foundation of South Africa grant number 81309..

##  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, 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. (3)

the class of all dense linear orders;

  2. (4)

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. In Section 3 we study the expressive power of
the language by analyzing the definability properties of each basic relation
in the class $\mathsf{Lin}$. Section 4 deals with the ‘other half’ of the
picture, that is, undefinability results, and presenting all maximally
incomplete sets in this class (i.e., those subsets of relations that do not
allow one to define the remaining ones, and are maximal in this sense with
respect to the subset relation); we also deal with completeness and
incompleteness results for the class of all discrete linear orders in this
section. Section 5 presents an account of all our results in a structured way,
including the projections of these to natural sub-languages, before
concluding. The classes of all dense and the class of all unbounded linearly
ordered sets will be treated in Part II (forthcoming).

##  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 a 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.

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.

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$.

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},\mathsf{Fin}\\}$)
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.

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 $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},\mathsf{Fin}\\}$).
Obviously, $FO+S\rightarrow r$ for all $r\in S$.

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.

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 1, 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.

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 1.

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 embeddings 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.

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.

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)$.

The following crucial lemma capitalizes on these facts.

######  Lemma 2.

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 2.1.

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
$\mathbb{\mathcal{missing}}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)$. ∎

 $\begin{array}[]{@{\hspace*{1ex}}lr@{}}\hskip
3.01389pt\lx@intercol\mbox{proc
}\mbox{{Undef}}\left(r\in\mathfrak{R}^{+}\right)\\\ \hskip
3.01389pt\lx@intercol\BEGIN\FORALL\ S\subset\mathfrak{R}^{+}\\\ \hskip
3.01389pt\lx@intercol\BEGIN S=Closure(S);\\\ \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(set\ S,rules\ 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.

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$;

  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;

  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: 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 all minimally $r$-complete, and, as a
consequence, $R_{1},R_{2},\ldots,R_{k}$ are all maximally $r$-incomplete.

Once the above process is completed for every relation, we can then easily
deduce all minimally $\mathfrak{R}^{+}$-complete and all maximally
$\mathfrak{R}^{+}$-incomplete sets, to complete the picture. A similar
procedure works for $\mathfrak{I}^{+},\mathfrak{M}^{+}$, and
$\mathfrak{P}^{+}$.

$\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.

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

##  3\. Completeness Results in The Class $\mathsf{Lin}$

In this section, we start analyzing the inter-definability of relations in
$\mathfrak{R}^{+}$, and. In particular, we consider the case in which we do
not assume any particular property of the underlying linear order. It is
convenient to begin by focusing our attention to the sub-languages induced by
$\mathfrak{M}^{+}$ and $\mathfrak{I}^{+}$; notice, in this respect, that while
the semantic counterpart of the sub-language $FO+\mathfrak{I}^{+}$ is
essentially single-sorted (it is interpreted on interval structures), in the
case of $FO+\mathfrak{M}^{+}$ (interpreted on point-interval ones) both sorts
are necessary. The results for $\mathfrak{M}^{+}$ and $\mathfrak{I}^{+}$ can
also be found in [CDS12].

Throughout our analysis we shall make extensive use of the following schema
for the definability part: for every definability equation
$r(x,y)\leftrightarrow\varphi(x,y)$, we denote by $\varphi(x,y)$ the right-
hand part of the definition, indicating that $x,y$ are the only free variables
in it; we then take a generic point-interval structure
$\mathcal{F}=\langle\mathbb{D},\mathbb{I}(\mathbb{D})\rangle$, and show that
$\mathcal{F}\models\varphi(x,y)$ (where $x,y$ have been instantiated with
suitable constants of the right type) if and only if $r(x,y)$ (again, after
the due instantiation). We shall therefore omit the specification of these
symbols and their meaning, as it remains the same in every proof. In order to
make the text more readable, we shall present the results for each relation
$r$ by means a table with at most four columns under the following headings:

  1. (1)

Proved, which contains those $r$-complete sets for which we give an explicit
proof in the corresponding lemma;

  2. (2)

Symmetric, which contains, for each $r$-complete set listed in the Proved
column, its symmetric one (if $r$ is symmetric);

  3. (3)

Implied, which contains all $r$-complete sets that can be deduced from those
in the first two columns plus the definability results presented earlier in
the paper;

  4. (4)

Deduction Chain, which is not empty if Implied is not empty, and it makes the
chain of deductions explicit.

When all (explicit) relations have been treated, we shall present the result
of applying the algorithm in Fig. 1, and we shall prove the undefinability
results, completing the process and consequently proving the minimality of the
complete sets.

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

We now study the minimal definability of $\mathfrak{I}^{+}$ relations, first,
and, then, of $\mathfrak{M}^{+}$ relations.

Relation |  Proved |  Symmetric |  Implied |  Deduction Chain
---|---|---|---|---
${\mathpzc{3}\mathpzc{4}}_{ii}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  |
|  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  - |  |
|  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  |
|  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  |
${\mathpzc{1}\mathpzc{4}}_{ii}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$ |  - |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
${\mathpzc{2}\mathpzc{4}}_{ii}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$ |  - |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
${\mathpzc{0}\mathpzc{4}}_{ii}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$ |  - |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
${\mathpzc{4}\mathpzc{4}}_{ii}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$ |  - |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{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{3}\mathpzc{4}}_{ii}$
|  |  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
$=_{i}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$ |  - |  |
|  ${\mathpzc{1}\mathpzc{4}}_{ii}$ |  ${\mathpzc{0}\mathpzc{3}}_{ii}$ |  |

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

(Lemma 3)

######  Lemma 3.

Tab. 4 is correct.

######  Proof 3.1.

First, we prove the $\mathfrak{I}^{+}$-completeness of
$\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$, as well as the fact that every relation
in $\mathfrak{I}^{+}$ is $=_{i}$-complete, and, then, we prove that every
other subset is ${\mathpzc{3}\mathpzc{4}}_{ii}$-complete; completeness for the
remaining relations is a mere consequence, as it can be seen in the table. As
for the first step, we simply express every other interval-interval relation,
as follows:

$\begin{array}[]{lll}x_{i}{\mathpzc{4}\mathpzc{4}}_{ii}y_{i}&\leftrightarrow&\exists
z_{i}(x_{i}{\mathpzc{3}\mathpzc{4}}_{ii}z_{i}\wedge
z_{i}{\mathpzc{3}\mathpzc{4}}_{ii}y_{i})\\\
x_{i}{\mathpzc{1}\mathpzc{4}}_{ii}y_{i}&\leftrightarrow&\exists
z_{i}(x_{i}{\mathpzc{3}\mathpzc{4}}_{ii}z_{i}\wedge\forall
k_{i}((z_{i}{\mathpzc{3}\mathpzc{4}}_{ii}k_{i}\leftrightarrow
y_{i}{\mathpzc{3}\mathpzc{4}}_{ii}k_{i})\wedge(k_{i}{\mathpzc{3}\mathpzc{4}}_{ii}x_{i}\leftrightarrow
k_{i}{\mathpzc{3}\mathpzc{4}}_{ii}y_{i}))\\\
x_{i}{\mathpzc{0}\mathpzc{3}}_{ii}y_{i}&\leftrightarrow&\exists
z_{i}(z_{i}{\mathpzc{3}\mathpzc{4}}_{ii}x_{i}\wedge\forall
k_{i}((k_{i}{\mathpzc{3}\mathpzc{4}}_{ii}z_{i}\leftrightarrow
k_{i}{\mathpzc{3}\mathpzc{4}}_{ii}y_{i})\wedge(x_{i}{\mathpzc{3}\mathpzc{4}}_{ii}k_{i}\leftrightarrow
y_{i}{\mathpzc{3}\mathpzc{4}}_{ii}k_{i}))\\\
x_{i}{\mathpzc{0}\mathpzc{4}}_{ii}y_{i}&\leftrightarrow&\exists
z_{i}(x_{i}{\mathpzc{1}\mathpzc{4}}_{ii}z_{i}\wedge
z_{i}{\mathpzc{0}\mathpzc{3}}_{ii}y_{i})\\\
x_{i}{\mathpzc{2}\mathpzc{4}}_{ii}y_{i}&\leftrightarrow&\exists
z_{i}(z_{i}{\mathpzc{0}\mathpzc{3}}_{ii}x_{i}\wedge
z_{i}{\mathpzc{1}\mathpzc{4}}_{ii}y_{i})\\\
x_{i}=_{i}y_{i}&\leftrightarrow&\forall
z_{i}((x_{i}{\mathpzc{3}\mathpzc{4}}_{ii}z_{i}\leftrightarrow
y_{i}{\mathpzc{3}\mathpzc{4}}_{ii}z_{i})\wedge(z_{i}{\mathpzc{3}\mathpzc{4}}_{ii}x_{i}\leftrightarrow
z_{i}{\mathpzc{3}\mathpzc{4}}_{ii}y_{i}))\\\
x_{i}=_{i}y_{i}&\leftrightarrow&\forall
z_{i}((x_{i}{\mathpzc{1}\mathpzc{4}}_{ii}z_{i}\leftrightarrow
y_{i}{\mathpzc{1}\mathpzc{4}}_{ii}z_{i})\wedge(z_{i}{\mathpzc{1}\mathpzc{4}}_{ii}x_{i}\leftrightarrow
z_{i}{\mathpzc{1}\mathpzc{4}}_{ii}y_{i}))\\\ \end{array}$

All above equations but the last two are very simple, and do not require
further explanation. Moreover, the $\mathfrak{I}^{+}$-completeness of
$\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ is a known result (except for equality
between intervals): it has been formally proved in [AH85] assuming density and
unboundedness of the structure, but a closer look shows that those additional
hypothesis were not needed. As for the fact that $=_{i}$ can be expressed with
$\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$, assume that
$\mathcal{F}\models\varphi([a,b],[c,d])$. We wish to show that $a=c$ and
$b=d$. Suppose, by way of contradiction, that $a\neq c$. If $a<c$, then the
interval $[a,c]$ meets the interval $[c,d]$, but it does not meet $[a,b]$,
contradicting the second conjunct of $\varphi$; if $c<a$, a similar argument
shows that the second conjunct fails. Symmetrically, we can prove that $b\neq
d$ leads to a contradiction with the first conjunct of $\varphi$. Also, it is
obvious that if $[a,b]=[c,d]$, they meet and are met by exactly the same
intervals. The case of $\\{{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ is very similar.
The remaining cases are more difficult, and require some non-trivial
definitions. First, let us observe that having the weaker relation:

${\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii}$

is enough to get ${\mathpzc{3}\mathpzc{4}}_{ii}$, and viceversa: in fact,
$[a,b]$ meets $[b,c]$ if and only if
$[a,b]{\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii}[b,c]$ and
no other interval in between them has the same property. This is explicitly
expressed by the formula $x_{i}34y_{i}\leftrightarrow
x_{i}({\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii})y_{i}\wedge\neg\exists
z_{i}(x_{i}({\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii})z_{i}\wedge
z_{i}({\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii})y_{i})$.
We use this observation in the rest of this proof, as in the remaining cases
we are able to define precisely the relation
${\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii}$:

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

where:

$\varphi_{1}(x_{i},y_{i})\leftrightarrow
x_{i}{\mathpzc{1}\mathpzc{4}}_{ii}y_{i}\vee
y_{i}{\mathpzc{1}\mathpzc{4}}_{ii}x_{i}\vee\forall
z_{i}((z_{i}{\mathpzc{1}\mathpzc{4}}_{ii}x_{i}\leftrightarrow
z_{i}{\mathpzc{1}\mathpzc{4}}_{ii}y_{i})\wedge(x_{i}{\mathpzc{1}\mathpzc{4}}_{ii}z_{i}\leftrightarrow
y_{i}{\mathpzc{1}\mathpzc{4}}_{ii}z_{i}))$
$\varphi_{2}(x_{i},y_{i})\leftrightarrow\forall
z_{i}(x_{i}{\mathpzc{4}\mathpzc{4}}_{ii}z_{i}\leftrightarrow
y_{i}{\mathpzc{4}\mathpzc{4}}_{ii}z_{i})\wedge(\neg\exists
z_{i}(x_{i}{\mathpzc{1}\mathpzc{4}}_{ii}z_{i})\leftrightarrow\neg\exists
z_{i}(y_{i}{\mathpzc{1}\mathpzc{4}}_{ii}z_{i}))$

As for the case of
$\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$, assume
$\mathcal{F}\models\varphi([a,b],[c,d])$; we want to prove that $b\leq c$. It
is easy to see that the requirement excludes every other possibility. First,
observe that $[a,b]$ and $[c,d]$ cannot overlap each other, nor can start each
other, thanks to the first line. The point $b$ cannot be the last one of the
model as there must be an interval started by $x_{i}$ (second line), and since
such an interval cannot be started by $y_{i}$ (second line), $x_{i}$ and
$y_{i}$ cannot be equal. If $y_{i}$ was during $x_{i}$, there would be an
interval that is started by $y_{i}$ and overlapped by $x_{i}$, which is a
contradiction (third line). If $x_{i}$ was during $y_{i}$, there would be an
interval $z_{i}$ that starts $y_{i}$ and an interval $t_{i}$ started by
$x_{i}$, and $z_{i}$ would overlap $t_{i}$, which is, again, a contradiction
(fourth line). It is then easy to see that $x_{i}$ and $y_{i}$ cannot finish
each other (third and fifth line); finally we would have a contradiction if
$c\leq a$ (fifth line). Thus, the only remaining possibility is the correct
one. Conversely, if we assume that $b\leq c$, it is straightforward to see
that all requirements are respected. Let us now consider the case
$\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$, which is
slightly harder. Consider, first, the definition of $\varphi_{1}$: it is easy
to see that if $\mathcal{F}$ is concrete interval structure, then
$\mathcal{F}\models\varphi_{1}([a,b],[c,d])$ if and only if $a=c$. Let us now
analyze the definition of $\varphi_{2}$. Consider $[a,b],[c,d]\in\mathcal{F}$.
If $b=d$ then it is clear that $\mathcal{F}\models\varphi_{2}([a,b],[c,d])$.
Suppose that $\mathcal{F}\models\varphi_{2}([a,b],[c,d])$. We claim that
$b=d$. Suppose, by way of contradiction that $b\neq d$. As
$\varphi_{2}(x,y)\leftrightarrow\varphi_{2}(y,x)$ we may assume that $b<d$. If
$d$ is the greatest point of the linear order $\mathbb{D}$ then the last
conjunct of $\varphi_{2}$ does not hold. If there is a point $e$ which is
greater than $d$, then $[a,b]{\mathpzc{4}\mathpzc{4}}_{ii}[d,e]$ and
$\neg[c,d]{\mathpzc{4}\mathpzc{4}}_{ii}[d,e]$, which means that the first
conjunct of $\varphi_{2}$ does not hold. So we have that
$\mathcal{F}\models\varphi_{2}([a,b],[c,d])$ if and only if $b=d$. Finally, we
want to show that
$\mathcal{F}\models[a,b]{\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii}[c,d]$
if and only if $\mathcal{F}\models\varphi([a,b],[c,d])$ where $\varphi$
denotes the right-hand part of the last equivalence considered for this set.
Assume that $\mathcal{F}\models\varphi([a,b],[c,d])$. If $c<b$ then $z=[c,b]$
witnesses the failure of $\varphi([a,b],[c,d])$. So $b\leq c$ and hence
$\mathcal{F}\models[a,b]{\mathpzc{3}\mathpzc{4}}_{ii}\vee{\mathpzc{4}\mathpzc{4}}_{ii}[c,d]$.
Now assume that
$\mathcal{F}\models[a,b]{\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii}[c,d]$,
i.e., $b\leq c$. If $\mathcal{F}\models\varphi_{1}(z_{i},[c,d])$, then
$z_{i}=[c,e]$ with $c<e$ which implies $b<e$. So
$\mathcal{F}\models\neg\varphi_{2}(z_{i},[a,b])$. Therefore we have
$\mathcal{F}\models\varphi([a,b],[c,d])$. For the case
$\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$, assume
that $\mathcal{F}\models\varphi([a,b],[c,d])$. We wish to show that
$\mathcal{F}\models[a,b]{\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii}[c,d]$,
i.e., that $b\leq c$. Suppose, by way of contradiction, that $c<b$. By
assumption, there exists an interval $z_{i}=[e,f]$ such that $a=e<b<f$ and
$e<c<d=f$. Then $a<c<b<d$, hence $[c,b]{\mathpzc{0}\mathpzc{3}}_{ii}[a,b]$ and
$[c,b]{\mathpzc{1}\mathpzc{4}}_{ii}[c,d]$, contradicting
$\mathcal{F}\models\neg\exists
z_{i}((z_{i}{\mathpzc{0}\mathpzc{3}}_{ii}[a,b])\wedge(z_{i}{\mathpzc{1}\mathpzc{4}}_{ii}[c,d]))$.
Conversely, suppose that
$\mathcal{F}\models[a,b]{\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii}[c,d]$,
i.e., $a<b\leq c<d$. Then the interval $z_{i}=[a,d]$ witnesses the first
conjunct of the definition. Moreover, for any $z_{i}$, if
$z_{i}{\mathpzc{0}\mathpzc{3}}_{ii}[a,b]$ then $z_{i}=[a^{\prime},b]$. Then
$\neg(z_{i}{\mathpzc{1}\mathpzc{4}}_{ii}[c,d])$, as $b\leq c$, proving that
the second conjunct also holds. Finally, as for the set
$\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$, we can
easily see that it is ${\mathpzc{3}\mathpzc{4}}_{ii}$-complete by means of an
indirect definition, that is, by defining ${\mathpzc{2}\mathpzc{4}}_{ii}$:

$\begin{array}[]{lll}x_{i}{\mathpzc{2}\mathpzc{4}}_{ii}y_{i}&\leftrightarrow&\exists
z_{i}(x_{i}{\mathpzc{1}\mathpzc{4}}_{ii}z_{i}\wedge\neg(y_{i}{\mathpzc{0}\mathpzc{4}}_{ii}z_{i})\wedge\exists
t_{i}(t_{i}{\mathpzc{0}\mathpzc{4}}_{ii}z_{i}\wedge
t_{i}{\mathpzc{1}\mathpzc{4}}_{ii}y_{i}))\wedge\\\ &&\exists
t_{i}(t_{i}{\mathpzc{1}\mathpzc{4}}_{ii}y_{i}\wedge\forall
w_{i}(x_{i}{\mathpzc{0}\mathpzc{4}}_{ii}w_{i}\rightarrow
t_{i}{\mathpzc{0}\mathpzc{4}}_{ii}w_{i}))\end{array}$

whose correctness is immediate.

We now focus our attention to $\mathfrak{M}^{+}$. Recall that models here are
based on point-interval structures; we are therefore allowed to define
interval-interval relations whenever we need them.

Relation |  Proved |  Implied |  Deduction Chain
---|---|---|---
${\mathpzc{0}}_{ip}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{0}}_{ip}\cup{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}$
|  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{4}}_{ip}$
|  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{0}}_{ip}\cup{\mathpzc{3}}_{ip},{\mathpzc{1}}_{ip}$
${\mathpzc{1}}_{ip}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}$
${\mathpzc{2}}_{ip}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{1}}_{ip}$
|  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{0}}_{ip}$

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

(Lemma 4)

######  Lemma 4.

Tab. 5 is correct.

######  Proof 3.2.

Let us focus, first, on ${\mathpzc{0}}_{ip}$, and consider the following
definitions:

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

The two cases above, namely $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ and
$\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ are almost immediate to see.
Now, consider the case $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$. We can
prove that it defines ${\mathpzc{0}}_{ip}$ by exclusion. As a matter of fact,
we can see that:

$\begin{array}[]{lll}x_{i}{\mathpzc{0}}_{ip}\cup{\mathpzc{2}}_{ip}y_{p}&\leftrightarrow&\exists
z_{i}(\forall w_{p}(z_{i}{\mathpzc{4}}_{ip}w_{p}\leftrightarrow
x_{i}{\mathpzc{4}}_{ip}w_{p})\wedge
z_{i}{\mathpzc{1}}_{ip}z_{p})\wedge\neg(x_{i}{\mathpzc{1}}_{ip}y_{p})\end{array}$

In this way, we have that ${\mathpzc{3}}_{ip}$ is definable by difference:

$\begin{array}[]{lll}x_{i}{\mathpzc{3}}_{ip}y_{p}&\leftrightarrow&\neg(x_{i}{\mathpzc{1}}_{ip}y_{p}\vee
x_{i}{\mathpzc{4}}_{ip}y_{p}\vee
x_{i}{\mathpzc{0}}_{ip}\cup{\mathpzc{2}}_{ip}y_{p})\end{array}$

and, therefore, the set is ${\mathpzc{0}}_{ip}$-complete by using
$\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$. Let us now consider the case of
$\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$. To deal with it, we first
observe that this set is ${\mathpzc{4}}_{ip}$-complete, because
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ defines ${\mathpzc{0}}_{ip}$ and
we can then use Lemma 2. Now, we can directly define ${\mathpzc{0}}_{ip}$:

$\begin{array}[]{llll}x_{i}{\mathpzc{0}}_{ip}y_{p}&\leftrightarrow&\neg(x_{i}{\mathpzc{2}}_{ip}y_{p})\wedge\neg(x_{i}{\mathpzc{3}}_{ip}y_{p})\wedge\neg(x_{i}{\mathpzc{4}}_{ip}y_{p})\wedge&\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}\\\
&&\exists z_{i}(\forall w_{p}(z_{i}{\mathpzc{4}}_{ip}w_{p}\leftrightarrow
x_{i}{\mathpzc{4}}_{ip}w_{p})\wedge\forall
w_{p}(x_{i}{\mathpzc{2}}_{ip}w_{p}\rightarrow
z_{i}{\mathpzc{2}}_{ip}w_{p})\wedge\\\ &&\hskip 17.07182pt\exists
w_{p}(z_{i}{\mathpzc{2}}_{ip}w_{p}\wedge\neg(x_{i}{\mathpzc{2}}_{ip}w_{p}))\wedge\neg(z_{i}{\mathpzc{2}}_{ip}y_{p}))\\\
\end{array}$

As for the case $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$, we reason in a
similar way. By slightly modifying the above definition, we obtain a weaker
relation:

$\begin{array}[]{llll}x_{i}{\mathpzc{0}}_{ip}\cup{\mathpzc{3}}_{ip}y_{p}&\leftrightarrow&\neg(x_{i}{\mathpzc{2}}_{ip}y_{p})\wedge\neg(x_{i}{\mathpzc{4}}_{ip}y_{p})\wedge&\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}\\\
&&\forall z_{i}((\forall w_{p}(z_{i}{\mathpzc{4}}_{ip}w_{p}\leftrightarrow
x_{i}{\mathpzc{4}}_{ip}w_{p})\wedge\forall
w_{p}(x_{i}{\mathpzc{2}}_{ip}w_{p}\rightarrow
z_{i}{\mathpzc{2}}_{ip}w_{p})\wedge\\\ &&\hskip 22.76228pt\exists
w_{p}(z_{i}{\mathpzc{2}}_{ip}w_{p}\wedge\neg(x_{i}{\mathpzc{2}}_{ip}w_{p})))\rightarrow\neg(z_{i}{\mathpzc{2}}_{ip}y_{p}))\\\
\end{array}$

Then, ${\mathpzc{1}}_{ip}$ is defined by difference, and
${\mathpzc{0}}_{ip}$-completeness becomes a consequence of the
${\mathpzc{0}}_{ip}$-completeness of
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$, seen above. Let us consider the
${\mathpzc{1}}_{ip}$-completeness. First, as for
$\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ we have that:

$\begin{array}[]{llll}x_{i}{\mathpzc{1}}_{ip}y_{p}&\leftrightarrow&\neg(x_{i}{\mathpzc{0}}_{ip}y_{p})\wedge\neg(x_{i}{\mathpzc{3}}_{ip}y_{p})\wedge&\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}\\\
&&\neg\exists z_{i}(z_{i}{\mathpzc{3}}_{ip}y_{p}\wedge\forall
w_{p}(z_{i}{\mathpzc{0}}_{ip}w_{p}\leftrightarrow
x_{i}{\mathpzc{0}}_{ip}w_{p}))\end{array}$

Then, for the case of $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$, we
already know that this set is ${\mathpzc{0}}_{ip}$-complete, and therefore it
must be also ${\mathpzc{1}}_{ip}$-complete thanks to the above argument. We
end this proof by analyzing the ${\mathpzc{2}}_{ip}$-complete sets:

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

All of the above are easy to prove. Also, the correctness of the remaining two
sets is immediate: from $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ we
define ${\mathpzc{1}}_{ip}$ and, then, we use
$\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$, and from
$\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ we define ${\mathpzc{0}}_{ip}$,
and, then, we use $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$.

This concludes our preliminary analysis of the expressiveness of our languages
when we limit ourselves to relation in $\mathfrak{I}^{+}$ and
$\mathfrak{M}^{+}$. We shall use these results in the rest of this section,
dealing with the expressiveness within $\mathfrak{R}^{+}$.

###  3.2. Definability in $\mathfrak{R}^{+}$

Proved |  Symmetric
---|---
$\\{<\\}$ |  -
$\\{{\mathpzc{1}}_{ip}\\}$ |  $\\{{\mathpzc{3}}_{ip}\\}$

Proved |  Symmetric
---|---
$\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$
$\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$
$\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  -
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  -
$\\{{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii}\\}$
$\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  -

Table 6. The spectrum of the $\mathsf{mcs}(=_{p})$ (left) and of the
$\mathsf{mcs}(=_{i})$ (right). - Class: $\mathsf{Lin}$.

(Lemma 5 and Lemma 6)

In the rest of this section, we assume that the set of relations is
$\mathfrak{R}^{+}$; unlike the previous results, we shall treat the relations
one by one. We begin our study by considering those sets that define the
equality between points; then we move to the equality between intervals, which
is no more complicate than the previous one, although there are more ways to
define $=_{i}$ than to define $=_{p}$.

######  Lemma 5.

Tab. 6 (left) is correct.

######  Proof 3.3.

Consider the following definitions

$x_{p}=_{p}y_{p}\leftrightarrow\left\\{\begin{array}[]{ll}\neg(x_{p}<y_{p})\wedge\neg(y_{p}<x_{p})&\\{<\\}\\\
&\\\ \forall x_{i}(x_{i}{\mathpzc{1}}_{ip}x_{p}\leftrightarrow
x_{i}{\mathpzc{1}}_{ip}y_{p})&\\{{\mathpzc{1}}_{ip}\\}\end{array}\right.$

The case of $\\{<\\}$ is trivial. As for the case of
$\\{{\mathpzc{1}}_{ip}\\}$; suppose that $\mathcal{F}\models\varphi(a,b)$.
Clearly, it implies that $a$ is the starting point of an interval if and only
if $b$ is the starting point of that interval. Hence $a=b$. On the other hand
it is obvious that if $a=b$, then $\mathcal{F}\models\varphi(a,b)$.

######  Lemma 6.

Tab. 6 (right) is correct.

######  Proof 3.4.

Consider the following definition:

$\begin{array}[]{llll}x_{i}=_{i}y_{i}&\leftrightarrow&\forall
z_{p}(x_{i}{\mathpzc{r}}_{ip}z_{p}\leftrightarrow
y_{i}{\mathpzc{r}}_{ip}z_{p})\wedge\forall
z_{p}(x_{i}{\mathpzc{r^{\prime}}}_{ip}z_{p}\leftrightarrow
y_{i}{\mathpzc{r^{\prime}}}_{ip}z_{p})&\\{{\mathpzc{r}}_{ip},{\mathpzc{r}}_{ip}^{\prime}\\}\end{array}$

where $\\{{\mathpzc{r}}_{ip},{\mathpzc{r}}_{ip}^{\prime}\\}=S$, for any $S$ in
the left-hand part of the table with $S\subseteq\mathfrak{M}^{+}$. All such
cases are based on the same, simple observation: in order to constrain two
intervals to be the same interval, it suffices to fix the two endpoints. This
is to say that, for each side of the intervals, we can simply express the fact
that they have the same sets of points in a given point-interval relation with
it. So, for example, consider $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$.
Assume that $\mathcal{F}\models\varphi([a,b],[c,d])$: we obtain $a=c$ from the
first conjunct of $\varphi$, and $b=d$ from the second conjunct. On the other
hand, it is immediate to see that if $[a,b]=[c,d]$ then
$\mathcal{F}\models\varphi([a,b],[c,d])$. The basic idea is now clear: by
means of ${\mathpzc{0}}_{ip}$ we fix the left endpoints, and by means of
${\mathpzc{2}}_{ip}$ we fix the right endpoint (in this particular case,
${\mathpzc{2}}_{ip}$ serves the right side, but, for example, in the case of
$\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$, it would serve the left one).
Notice that the only pairs missing from the list (and the list of symmetric
sets) are $\\{{\mathpzc{0}}_{ip},{\mathpzc{1}}_{ip}\\}$ and its symmetric one,
for which this idea does not apply (they are, in fact, $=_{i}$-incomplete).
The remaining definitions are already included in Lemma 3.

The case of ‘less then’ between point is the first non-trivial case, as there
are already many possible different definitions.

######  Lemma 7.

Tab. 7 is correct.

######  Proof 3.5.

Consider, first, the following definitions:

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

Proved |  Symmetric |  Implied |  Deduction Chain
---|---|---|---
$\\{{\mathpzc{0}}_{ip},{\mathpzc{1}}_{ip}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  $=_{i}$ (Section 3.1)
$\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $=_{i}$ (Section 3.1)
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $=_{i}$ (Section 3.1)
$\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  - |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $=_{i}$ (Section 3.1)
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $=_{i}$ (Section 3.1)
$\\{{\mathpzc{1}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $=_{i}$ (Section 3.1)
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii},=_{i}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii},=_{i}\\}$ |  |
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},=_{i}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},=_{i}\\}$ |  |
$\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},=_{i}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},=_{i}\\}$ |  |

Table 7. The spectrum of the $\mathsf{mcs}(<)$. - Class: $\mathsf{Lin}$.

(Lemma 7)

The case of $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ is straightforward.
Consider the case of $\\{{\mathpzc{0}}_{ip},{\mathpzc{1}}_{ip}\\}$. Assume
that $\mathcal{F}\models\varphi(a,b)$. If the first disjunct of $\varphi$ is
satisfied then $b$ is the largest point of the linear order $\mathbb{D}$ and
$a$ is not the largest point of $\mathbb{D}$ which implies $a<b$ as required.
If the second disjunct of $\varphi$ holds, witnessed by the interval $[c,d]$,
then $a<c$ and $b=c$, again leading to $a<b$. On the other hand assume $a<b$.
If $b$ is the largest point of $\mathbb{D}$ then $a$ is not, and hence the
first disjunct of $\varphi$ holds. If $b$ is not the largest point of the the
linear order $\mathbb{D}$ then we can pick $c\in\mathbb{D}$ with $b<c$ and the
interval $[b,c]$ witnesses the second disjunct of $\varphi$. Now consider the
case $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$, and assume, first, that
$\mathcal{F}\models\varphi(a,b)$. So, some interval $z_{i}$ ends at $b$; if,
by contradiction, $a=b$, then $z_{i}$ also ends at $a$, contradicting the last
conjunct, and if $b<a$, then the interval $k_{i}$ that starts at the beginning
point of $z_{i}$ and ends at $a$ contradicts the second conjunct. If, on the
other hand, we assume $a<b$, we can take the interval $z_{i}=[a,b]$ to satisfy
$\varphi(a,b)$, and we make sure that $z_{i}$ does not end at $x_{p}$, nor any
interval ending at $x_{p}$ may possibly start together with $z_{i}$. Next,
consider the case $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$. Assume that
$\mathcal{F}\models\varphi(a,b)$. If the first disjunct of $\varphi$ holds
then, $b$ is the largest point of $\mathbb{D}$ and $a$ is not which leads to
$a<b$. If the second disjunct of $\varphi$ holds, witnessed by the interval
$x_{i}=[c,d]$, then $a=c$ and $c<b<d$ which again leads to $a<b$. On the other
hand, assume $a<b$, and let us prove that $\mathcal{F}\models\varphi(a,b)$. If
$b$ is the greatest point of $\mathbb{D}$, then the first disjunct of
$\varphi$ holds. If it is not, then, there is a $c\in\mathbb{D}$ such that
$c>b>a$ and the second disjunct of $\varphi$ holds, witnessed by the interval
$x_{i}=[a,c]$. Let us prove the $<$-completeness of
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$. Assume that
$\mathcal{F}\models\varphi(a,b)$. If the first disjunct of $\varphi$ holds
then $b$ is the largest point of $\mathbb{D}$ and $a$ is not, which implies
that $a<b$. Suppose that the second disjunct of $\varphi$ holds, witnessed by
the intervals $x_{i}=[c,d]$ and $y_{i}=[e,f]$. Then $a=c$, $b=e$ and
$c<e<f=d$, hence $a<b$. Now assume that $a<b$. If $b$ is the largest point of
$\mathbb{D}$ then the first disjunct of $\varphi$ holds. Otherwise the second
disjunct of $\varphi$ holds witnessed by the intervals $x_{i}=[a,c]$ and
$y_{i}=[b,c]$ where $b<c$. Now, let us focus on the following group of
definitions:

$x_{p}<y_{p}\leftrightarrow\left\\{\begin{array}[]{ll}(\exists
x_{i}(x_{i}{\mathpzc{1}}_{ip}x_{p})\wedge\neg\exists
x_{i}(x_{i}{\mathpzc{1}}_{ip}y_{p}))\vee&\\{{\mathpzc{1}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}\\\
\exists x_{i}y_{i}z_{i}(x_{i}{\mathpzc{1}}_{ip}x_{p}\wedge
y_{i}{\mathpzc{1}}_{ip}y_{p}\wedge
z_{i}{\mathpzc{3}\mathpzc{4}}_{ii}y_{i}\wedge\forall
t_{i}(t_{i}{\mathpzc{3}\mathpzc{4}}_{ii}x_{i}\leftrightarrow
t_{i}{\mathpzc{3}\mathpzc{4}}_{ii}z_{i}))&\\\ &\\\ \exists
x_{i}y_{i}(x_{i}{\mathpzc{1}}_{ip}x_{p}\wedge
y_{i}{\mathpzc{1}}_{ip}y_{p}\wedge
y_{i}{\mathpzc{0}\mathpzc{4}}_{ii}x_{i})\vee&\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii},=_{i}\\}\\\
(\exists x_{i}(x_{i}{\mathpzc{1}}_{ip}x_{p})\wedge\neg\exists
x_{i}(x_{i}{\mathpzc{1}}_{ip}y_{p}))\vee&\\\ (\exists
x_{i}y_{i}(x_{i}{\mathpzc{1}}_{ip}x_{p}\wedge
y_{i}{\mathpzc{1}}_{ip}x_{p}\wedge x_{i}\neq y_{i})\wedge&\\\ \neg\exists
x_{i}y_{i}(x_{i}{\mathpzc{1}}_{ip}y_{p}\wedge
y_{i}{\mathpzc{1}}_{ip}y_{p}\wedge x_{i}\neq y_{i}))&\\\ &\\\ \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})\vee&\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},=_{i}\\}\\\
(\exists x_{i}(x_{i}{\mathpzc{1}}_{ip}x_{p})\wedge\neg\exists
x_{i}(x_{i}{\mathpzc{1}}_{ip}y_{p}))\vee&\\\ (\exists
x_{i}y_{i}(x_{i}{\mathpzc{1}}_{ip}x_{p}\wedge
y_{i}{\mathpzc{1}}_{ip}x_{p}\wedge x_{i}\neq y_{i})\wedge&\\\ \neg\exists
x_{i}y_{i}(x_{i}{\mathpzc{1}}_{ip}y_{p}\wedge
y_{i}{\mathpzc{1}}_{ip}y_{p}\wedge x_{i}\neq y_{i}))&\\\ &\\\ \exists
x_{i}(x_{i}{\mathpzc{1}}_{ip}x_{p}\wedge\forall
y_{i}(y_{i}{\mathpzc{1}}_{ip}y_{p}\rightarrow\exists
z_{i}(x_{i}{\mathpzc{4}\mathpzc{4}}_{ii}z_{i}\wedge\neg(y_{i}{\mathpzc{4}\mathpzc{4}}_{ii}z_{i}))))\vee&\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},=_{i}\\}\\\
(\exists x_{i}(x_{i}{\mathpzc{1}}_{ip}x_{p})\wedge\neg\exists
x_{i}(x_{i}{\mathpzc{1}}_{ip}y_{p}))\vee&\\\ (\exists
x_{i}y_{i}(x_{i}{\mathpzc{1}}_{ip}x_{p}\wedge
y_{i}{\mathpzc{1}}_{ip}x_{p}\wedge x_{i}\neq y_{i})\wedge&\\\ \neg\exists
x_{i}y_{i}(x_{i}{\mathpzc{1}}_{ip}y_{p}\wedge
y_{i}{\mathpzc{1}}_{ip}y_{p}\wedge x_{i}\neq y_{i}))\end{array}\right.$

The case of $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ is very
similar to the previous one. Indeed, if we assume that
$\mathcal{F}\models\varphi(a,b)$, and that the second conjunct of $\varphi$
holds (if the first conjunct holds, then we reason as in the previous case),
then, if $x_{i}=[c,d]$ and $y_{i}=[e,f]$, we have that $a=c$, $b=e$, and the
interval $z_{i}=[a,b]$ must exist, so that it is met by exactly the same
intervals that meet $x_{i}$. Now, assume that $a<b$, where $b$ is not the
largest point of $\mathbb{D}$ (otherwise, the first disjunct of $\varphi$
holds). Then, the second disjunct of $\varphi$ holds witnessed by the
intervals $x_{i}=[a,c]$, $y_{i}=[b,c]$, and $z_{i}=[a,b]$ where $b<c$. Now
consider the case of
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii},=_{i}\\}$. Suppose that
$\mathcal{F}\models\varphi(a,b)$. If the first disjunct of $\varphi$ holds,
witnessed by the intervals $x_{i}=[c,d]$ and $y_{i}=[e,f]$, then $a=c$, $b=e$
and $c<e<f<d$ and we get $a<b$. If the second disjunct of $\varphi$ holds,
then $b$ is the largest point of $\mathbb{D}$ and $a$ is not, so $a<b$. If the
third disjunct of $\varphi$ holds, then there are at least two points in
$\mathbb{D}$ which are greater than $a$ and there is at most one point in
$\mathbb{D}$ greater than $b$ which again leads to $a<b$. Now, assume $a<b$;
we want to show that $\mathcal{F}\models\varphi(a,b)$. If $b$ is the largest
point of $\mathbb{D}$, then $a$ is not and therefore the second disjunct of
$\varphi$ holds. If there is exactly one point in $\mathbb{D}$ which is
greater than $b$, then there are at least two points in $\mathbb{D}$ greater
than $a$ and therefore the third disjunct of $\varphi$ holds. Now we may
assume that there are points $c,d\in\mathbb{D}$ with $a<b<c<d$. Then the first
disjunct of $\varphi$ holds witnessed by the intervals $x_{i}=[a,d]$ and
$y_{i}=[b,c]$. The case of
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},=_{i}\\}$ is similar to
the previous one. Lastly, we consider the case of
$\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},=_{i}\\}$. Suppose that
$\mathcal{F}\models\varphi(a,b)$ and that the first disjunct of $\varphi$
holds, witnessed by the interval $x_{i}=[a,c]$. Suppose, towards a
contradiction, that $b<c$. Then the interval $y_{i}=[b,c]$ satisfies
$y_{i}{\mathpzc{1}}_{ip}b$ and therefore there is an interval $z_{i}$ such
that $[a,c]{\mathpzc{4}\mathpzc{4}}_{ii}z_{i}$ and
$\neg([b,c]{\mathpzc{4}\mathpzc{4}}_{ii}z_{i})$ which is impossible. Therefore
$c\leq b$ and we obtain $a<b$. If the second or the third disjunct of
$\varphi$ holds then we again obtain $a<b$ precisely as in the previous case.
Now assume $a<b$; we want to show that $\mathcal{F}\models\varphi(a,b)$. If
$b$ is the greatest point of $\mathbb{D}$ then the second disjunct of
$\varphi$ holds and if there is exactly one point in $\mathbb{D}$ which is
greater than $b$ then the third disjunct of $\varphi$ holds. So we may assume
there are two points $c,d\in\mathbb{D}$ such that $b<c<d$. We claim that the
first disjunct of $\varphi$ holds, witnessed by the interval $x_{i}=[a,b]$.
Let $y_{i}=[b,e]$. We want to find an interval $z_{i}$ such that
$[a,b]{\mathpzc{4}\mathpzc{4}}_{ii}z_{i}$ and
$\neg[b,e]{\mathpzc{4}\mathpzc{4}}_{ii}z_{i}$. Let $f$ be the minimum of $c$
and $e$. Then the interval $z_{i}=[f,d]$ has the desired property, from which
we see that the first disjunct of $\varphi$ holds.

We are now moving to mixed relations, starting with ${\mathpzc{0}}_{ip}$.
Recall that ${\mathpzc{0}}_{ip}$ and ${\mathpzc{1}}_{ip}$ are reversible
relations: symmetric sets of complete ones are complete for their (respective)
reverse, and, thus, they do not appear in their tables.

######  Lemma 8.

Tab. 8 is correct.

Proved |  Implied |  Deduction Chain
---|---|---
$\\{{\mathpzc{1}}_{ip},<\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $<$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $<$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $<$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},<\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  $<$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $<$
$\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $<$
$\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},<\\}$ |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},=_{i}\\}$ |  $<$
|  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{4}}_{ii},=_{i}\\}$ |  $<$
|  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},=_{i}\\}$ |  $<$
|  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $<$
|  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $<$
|  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{0}\mathpzc{3}}_{ii}$ (Section 3.1)
|  $\\{{\mathpzc{3}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{1}\mathpzc{4}}_{ii}$ (Section 3.1)
|  $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$ (Section 3.1)
|  $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$ (Section 3.1)
|  $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$ (Section 3.1)
|  $\\{{\mathpzc{4}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{1}\mathpzc{4}}_{ii}$ (Section 3.1)
|  $\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$ (Section 3.1)
|  $\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$ (Section 3.1)
|  $\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$ (Section 3.1)

Table 8. The spectrum of the $\mathsf{mcs}({\mathpzc{0}}_{ip})$. - Class:
$\mathsf{Lin}$.

(Lemma 8)

######  Proof 3.6.

Consider the following definitions:

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

The case of $\\{{\mathpzc{1}}_{ip},<\\}$ is straightforward, and needs no
explanation. Consider, now, the case
$\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$. The fact that this set is
$<$-complete is proved above. So, assume first
$\mathcal{F}\models\varphi([a,b],c)$; there must be some $d$ which, thanks to
the first two conjuncts, can only be placed in such a way that $d\leq a$ or
$b<d$, and, thanks to the third conjunct, the possibility $b<d$ is eliminated:
in fact, if we had $b<d$, we could take $z_{i}=[a,d]$ and $k_{p}=b$ to
contradict the third conjunct. So, since $d\leq a$ and $c<d$, it must be that
$c<a$ as we wanted. Conversely, suppose that $c<a$: we take $z_{p}=a$, which
is not during $x_{i}$ nor does it end $x_{i}$, and it is such that no interval
ending at $z_{p}$ may possibly contain $b$. Moreover, $y_{p}=c<a$, and so
$\varphi([a,b],c)$. Now, focus on the following definitions:

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

Let us focus on the the case of
$\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},<\\}$. Suppose
$\mathcal{F}\models\varphi([a,b],c)$. So, there are two points $d,e$ such that
$c<d<e$. Now $d=z_{p}$ cannot be after $a$, for if it was we could find an
interval $z_{i}=[a,e]$, where $e>b$ (since $e$ and $d$ cannot be during
$x_{i}$) and such that $x_{i}$ starts $z_{i}$, which contradicts the last
conjunct. Then, $d\leq a$, which implies $c<a$ as we wanted. Suppose, on the
other hand, that $c<a$: to satisfy the requirements, it suffices to take
$z_{p}=a$ and $k_{p}=b$. The correctness of the case
$\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ is based on the fact that we
can, first, eliminate the possibility that $y_{p}$ is during or after $x_{i}$;
then, we eliminate the possibility that $y_{p}$ starts $x_{i}$ by stating that
there must be an interval finished by $x_{i}$ that does not have $y_{p}$
during it; finally, we eliminate the possibility that $y_{p}$ ends $x_{i}$ by
stipulating the existence of an interval (the one that starts at $y_{p}$)
which ends before the right endpoint of $x_{i}$ that does not have $y_{p}$
after it. Finally, consider the following definitions:

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

Proved |  Implied |  Deduction Chain
---|---|---
$\\{{\mathpzc{0}}_{ip},<\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $<$
|  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  $<,{\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip},<\\}$ |  ${\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}$ |  ${\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $<,{\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $<,{\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $<,{\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $<,{\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{3}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  $<,{\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}$ |  ${\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{4}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{0}}_{ip}$

Table 9. The spectrum of the $\mathsf{mcs}({\mathpzc{1}}_{ip})$. - Class:
$\mathsf{Lin}$.

(Lemma 9)

For the sake of the case
$\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}$, suppose that
$\mathcal{F}\models\varphi([a,b],c)$. So, there is a point $z_{p}$ such that
it is not during $x_{i}$, and since it must be during an interval
$z_{i}=[e,b]$, it can only be $d\leq a$. Since $c<d$ we have $c<a$. Suppose,
on the other hand, that $c<a$: to satisfy the requirements, it suffices to
take $z_{i}=[c,b]$ and $z_{p}=a$. As for the set
$\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$, first, recall its
$<$-completeness; then, we state the existence of a point for which we can
eliminate the possibility that $z_{p}$ ends $x_{i}$ by means of the first
conjunct, and, after that, we can eliminate the possibility that $z_{p}$ is
during or after $x_{i}$: if that were the case, there would be an interval
$z_{i}$ starting or started by $x_{i}$ such that $z_{p}$ is its right
endpoint. The only possibility left is therefore that $z_{p}$ is less than or
equal to the beginning point of $x_{i}$, and therefore the last conjunct
guarantees that $x_{i}{\mathpzc{0}}_{ip}y_{p}$. Finally, the case
$\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},<\\}$ is identical to the
previous one, with the only difference that $x_{i}{\mathpzc{3}}_{ip}y_{p}$ can
be expressed by asserting that $y_{p}<k_{p}$ and
$x_{i}{\mathpzc{4}}_{ip}k_{p}$ are equivalent. As for the implied definitions,
notice that in some cases we exploit the $\mathfrak{I}^{+}$-completeness
results from Section 3.1.

######  Lemma 9.

Tab. 9 is correct.

######  Proof 3.7.

Only one new definition is needed:

$\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}$

This definition is quite straightforward: $[a,b]{\mathpzc{1}}_{ip}a$ if, and
only if, the points $c$ less than $a$ are exactly the same points $c$ such
that $[a,b]{\mathpzc{0}}_{ip}c$.

Proved |  Symmetric |  Implied |  Deduction Chain
---|---|---|---
$\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  - |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{1}}_{ip}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  - |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{4}}_{ip}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{4}}_{ip}$
|  |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{4}}_{ip}$
|  |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}$ |  ${\mathpzc{1}}_{ip}$
|  |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{0}\mathpzc{3}}_{ii}$ (Section 3.1)
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{3}}_{ip}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}}_{ip}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}}_{ip}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}}_{ip}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{0}\mathpzc{3}}_{ii}$ (Section 3.1)
|  |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{1}}_{ip}$
|  |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{1}}_{ip}$
|  |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{1}}_{ip}$
|  |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{1}\mathpzc{4}}_{ii}$ (Section 3.1)
|  |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{3}}_{ip}$
|  |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}$ |  ${\mathpzc{1}}_{ip}$
|  |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{1}}_{ip}$
|  |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{1}}_{ip}$

Table 10. The spectrum of the $\mathsf{mcs}({\mathpzc{2}}_{ip})$. - Class:
$\mathsf{Lin}$.

(Lemma 10)

We complete this part by analyzing the definability for ${\mathpzc{2}}_{ip}$.
Notice that here we also take advantage of the results of Section 3.1.

######  Lemma 10.

Tab. 10 is correct.

######  Proof 3.8.

In this case, three new definitions are needed:

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

For the ${\mathpzc{2}}_{ip}$-completeness of
$\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$, we begin by assuming that
$\mathcal{F}\models\varphi([a,b],c)$. So, there must be two intervals
$z_{i},k_{i}$, the former starting at $a$, and the latter ending at $b$; the
point $c$ must, at the same time, end $z_{i}$ (meaning that $a<c$) and start
$k_{i}$ (implying that $c<b$), and we deduce $a<c<b$. If we assume $a<c<b$, it
is enough to take $z_{i}=[a,c]$ and $k_{i}=[c,b]$ to satisfy the conditions.
We move now to the ${\mathpzc{2}}_{ip}$-completeness of
$\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$, and let us assume, again, that
$\mathcal{F}\models\varphi([a,b],c)$. The interval $z_{i}$ must start at $a$,
and the interval $k_{i}$ must end at $b$. Moreover, the ending point of
$k_{i}$ cannot be after the beginning point of $z_{i}$ (third conjunct). Now,
in this situation, $y_{p}$ cannot be $a$ or before it (because of the fifth
conjunct), and it cannot be $b$ or after it (because of the fourth conjunct),
and the only possibility left out is $a<c<b$. If, conversely, we assume
$a<c<b$, it is enough to take $z_{i}=[a,c]$ and $k_{i}=[c,b]$ to satisfy the
entire set of conditions. Finally, the ${\mathpzc{2}}_{ip}$-completeness of
$\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ is very easy. If
$\mathcal{F}\models\varphi([a,b],c)$, then there exists an interval $z_{i}$
that finishes $[a,b]$, and for its starting point, that is, $y_{p}=c$, it must
hold that $a<c<b$. On the other hand, if $a<c<b$, we just take $z_{i}=[c,b]$
to satisfy $\varphi$.

We now focus on interval-interval relations other than equality, starting with
${\mathpzc{3}\mathpzc{4}}_{ii}$, which, being $\mathfrak{I}^{+}$-complete on
its own, plays a very special role. Most of the work has already been taken
care of in Section 3.1. As a matter of fact, we already know some subsets of
$\mathfrak{I}^{+}$ that are ${\mathpzc{3}\mathpzc{4}}_{ii}$-complete, and we
certainly have to define those subsets of
$\mathfrak{R}^{+}\setminus\mathfrak{I}^{+}$ which are. It remains to establish
whether other subsets of $\mathfrak{I}^{+}$, other than those seen in Section
3.1, become ${\mathpzc{3}\mathpzc{4}}_{ii}$-complete within the language of
$FO+\mathfrak{R}^{+}$: the fact that this is not the case will be a
consequence of the results shown in Section 4.

Proved |  Symmetric |  Implied |  Deduction Chain
---|---|---|---
$\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  - |  $\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  Section 3.1
$\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  Section 3.1
$\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  Section 3.1
$\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  Section 3.1
|  |  $\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  Section 3.1
|  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  Section 3.1
|  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  Section 3.1
|  |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{1}}_{ip}$
|  |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{2}}_{ip}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  ${\mathpzc{0}}_{ip}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{3}}_{ip}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{2}}_{ip}$
|  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{4}}_{ip}$
|  |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{2}}_{ip}$

Table 11. The spectrum of the $\mathsf{mcs}({\mathpzc{3}\mathpzc{4}}_{ii})$. -
Class: $\mathsf{Lin}$.

(Lemma 11)

######  Lemma 11.

Tab. 11 is correct.

######  Proof 3.9.

The fact that the set $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ is
${\mathpzc{3}\mathpzc{4}}_{ii}$-complete depends on the following easy
definition:

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

The second two sets in the leftmost column can be proven
${\mathpzc{3}\mathpzc{4}}_{ii}$-complete by means of defining, as in Section
3.1, the weaker relation
${\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii}$:

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

Proved |  Implied |  Deduction Chain
---|---|---
$\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{2}}_{ip}$
$\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii},<\\}$ |  ${\mathpzc{2}}_{ip}$
|  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  ${\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}$
|  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{0}}_{ip}$
|  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  Section 3.1
|  $\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  $\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  Section 3.1
|  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  Section 3.1
|  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  Section 3.1

Table 12. The spectrum of the $\mathsf{mcs}({\mathpzc{1}\mathpzc{4}}_{ii})$. -
Class: $\mathsf{Lin}$.

(Lemma 12.)

As for $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$, assume,
first, that $\mathcal{F}\models\varphi([a,b],[c,d])$. We wish to show that
$\mathcal{F}\models[a,b]{\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii}[c,d]$,
i.e., that $b\leq c$. Suppose, by way of contradiction, that $c<b$. The only
possible interval which satisfies the first conjunct is $[a,d]$. Specifically
we have $b<d$. Now the interval $[c,b]$ falsifies the second conjunct.
Conversely assume that
$\mathcal{F}\models[a,b]{\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii}[c,d]$,
i.e., $a<b\leq c<d$. Then the interval $z_{i}=[a,d]$ witnesses the first
conjunct of the definition, and, for any $z_{i}$, if $z_{i}$ starts $y_{i}$,
then it cannot end at $b$, proving that the second conjunct also holds. As for
$\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ assume, first, that
$\mathcal{F}\models\varphi([a,b],$ $[c,d])$. We wish to show that
$\mathcal{F}\models[a,b]{\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii}[c,d]$,
i.e., that $b\leq c$. Because of the first four conjuncts, there must be an
interval started by $x_{i}$, and $z_{p}$ must be placed as the ending point of
$[a,b]$, that is, $z_{p}=b$; then, $y_{i}$ must start at $z_{p}$ or after it,
otherwise it would happen that either $y_{i}{\mathpzc{2}}_{ip}z_{p}$ or some
$k_{i}$ started by $y_{i}$ is such that $k_{i}{\mathpzc{2}}_{ip}z_{p}$. On the
other hand, assume that
$\mathcal{F}\models[a,b]{\mathpzc{3}\mathpzc{4}}_{ii}\cup{\mathpzc{4}\mathpzc{4}}_{ii}[c,d]$,
i.e., that $b\leq c<d$. In this case, it suffices to take $z_{p}=b$ and
$z_{i}=[a,d]$ to satisfy all conjuncts. Finally, the
${\mathpzc{3}\mathpzc{4}}_{ii}$-completeness of
$\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ can be seen as follows:

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

which is immediate to prove, as we stipulate that $x_{i}$ starts $y_{i}$ if
and only if $x_{i}$ and $y_{i}$ have the same points before them and there
exists a point (the ending point of $x_{i}$) that it is during $y_{i}$ and not
during $x_{i}$, and which allows us to obtain the result via the set
$\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$.

The only non-symmetric interval-interval relation,
${\mathpzc{1}\mathpzc{4}}_{ii}$, does not present particularly difficult
problems.

######  Lemma 12.

Tab. 12 is correct.

######  Proof 3.10.

The fact that the set $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ is
${\mathpzc{1}\mathpzc{4}}_{ii}$-complete has already been proved as a
necessary step to delineate the $\mathsf{mcs}({\mathpzc{3}\mathpzc{4}}_{ii})$.
As for the set $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$, it is easily
verified that:

######  Lemma 13.

Tab. 13 is correct.

Proved |  Symmetric |  Implied |  Deduction Chain
---|---|---|---
$\\{{\mathpzc{2}}_{ip},<\\}$ |  - |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
$\\{{\mathpzc{0}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{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{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{0}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  Section 3.1

Table 13. The spectrum of the $\mathsf{mcs}({\mathpzc{2}\mathpzc{4}}_{ii})$. -
Class: $\mathsf{Lin}$.

(Lemma 13.)

######  Proof 3.11.

Consider the following definitions:

$x_{i}{\mathpzc{2}\mathpzc{4}}_{ii}y_{i}\leftrightarrow\left\\{\begin{array}[]{ll}\exists
z_{p}k_{p}(x_{i}{\mathpzc{2}}_{ip}z_{p}\wedge\forall
t_{p}(x_{i}{\mathpzc{2}}_{ip}t_{p}\rightarrow
t_{p}<k_{p})&\\{{\mathpzc{2}}_{ip},<\\}\\\ \hskip 28.45274pt{}\wedge\forall
s_{p}(\forall t_{p}(x_{i}{\mathpzc{2}}_{ip}t_{p}\rightarrow
t_{p}<s_{p})\rightarrow\neg(s_{p}<k_{p}))\\\ \hskip 28.45274pt{}\wedge
y_{i}{\mathpzc{2}}_{ip}k_{p}\wedge\neg(y_{i}{\mathpzc{2}}_{ip}z_{p}))&\\\ &\\\
\exists z_{i}t_{i}w_{i}(\forall
k_{p}(x_{i}{\mathpzc{0}}_{ip}k_{p}\leftrightarrow
z_{i}{\mathpzc{0}}_{ip}k_{p})\wedge\forall
k_{p}(y_{i}{\mathpzc{0}}_{ip}k_{p}\leftrightarrow
w_{i}{\mathpzc{0}}_{ip}k_{p})\wedge{}&\\{{\mathpzc{0}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}\\\
\hskip 19.91684ptz_{i}{\mathpzc{4}\mathpzc{4}}_{ii}t_{i}\wedge\exists
s_{i}(w_{i}{\mathpzc{0}\mathpzc{4}}_{ii}s_{i}\wedge\neg(y_{i}{\mathpzc{0}\mathpzc{4}}_{ii}s_{i}))\wedge{}\\\
\hskip 19.91684pt\neg\forall k_{p}(x_{i}{\mathpzc{0}}_{ip}k_{p}\leftrightarrow
y_{i}{\mathpzc{0}}_{ip}k_{p})\wedge{}\\\ \hskip
19.91684pt\displaystyle{\bigwedge_{\begin{subarray}{c}u_{i},v_{i}\in\\{w_{i},x_{i},y_{i},z_{i},t_{i}\\}\\\
\\{u_{i},v_{i}\\}\neq\\{z_{i},t_{i}\\}\end{subarray}}(\neg(u_{i}{\mathpzc{0}\mathpzc{4}}_{ii}v_{i})\wedge\neg(u_{i}{\mathpzc{4}\mathpzc{4}}_{ii}v_{i}))})&\\\
&\\\ \exists z_{i}t_{i}w_{i}(\exists k_{p}(x_{i}{\mathpzc{1}}_{ip}k_{p}\wedge
z_{i}{\mathpzc{1}}_{ip}k_{p})\wedge\exists
k_{p}(y_{i}{\mathpzc{1}}_{ip}k_{p}\wedge
w_{i}{\mathpzc{1}}_{ip}k_{p})\wedge{}&\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}\\\
\hskip 19.91684ptz_{i}{\mathpzc{4}\mathpzc{4}}_{ii}t_{i}\wedge\exists
s_{i}(w_{i}{\mathpzc{0}\mathpzc{4}}_{ii}s_{i}\wedge\neg(y_{i}{\mathpzc{0}\mathpzc{4}}_{ii}s_{i}))\wedge{}\\\
\hskip 19.91684pt\neg\exists k_{p}(x_{i}{\mathpzc{1}}_{ip}k_{p}\wedge
y_{i}{\mathpzc{1}}_{ip}k_{p})\wedge{}\\\ \hskip
19.91684pt\displaystyle{\bigwedge_{\begin{subarray}{c}u_{i},v_{i}\in\\{w_{i},x_{i},y_{i},z_{i},t_{i}\\}\\\
\\{u_{i},v_{i}\\}\neq\\{z_{i},t_{i}\\}\end{subarray}}(\neg(u_{i}{\mathpzc{0}\mathpzc{4}}_{ii}v_{i})\wedge\neg(u_{i}{\mathpzc{4}\mathpzc{4}}_{ii}v_{i}))})&\\\
\end{array}\right.$

Let us start proving the correctness of the case $\\{{\mathpzc{2}}_{ip},<\\}$.
Suppose that $\mathcal{F}\models[a,b]{\mathpzc{2}\mathpzc{4}}_{ii}[c,d]$.
Then, by definition, $a<c<b<d$; by setting $z_{p}=c$ and $k_{p}=b$ we satisfy
all requirements. Conversely, suppose that
$\mathcal{F}\models\varphi([a,b],[c,d])$. First, observe that $x_{i}=[a,b]$
must have and internal point $z_{p}$. Then, the only way to place $k_{p}$ is
by having that $k_{p}$ is the smallest point which is greater than every
internal point of $x_{i}$, that is, $k_{p}$ must end $x_{i}$. Now, $y_{i}$
must contain $k_{p}$ (so, it must end after it), but not $z_{p}$ (so, it must
start after $z_{p}$ or on it). Consider, now,
$\\{{\mathpzc{1}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$.
Suppose that $\mathcal{F}\models[a,b]{\mathpzc{2}\mathpzc{4}}_{ii}[c,d]$.
Then, by definition, $a<c<b<d$; by setting $z_{i}=[a,c]$, $w_{i}=[c,b]$,
$t_{i}=[b,d]$, and $s_{i}=[a,d]$, we satisfy all requirements. Suppose, now,
that $\mathcal{F}\models\varphi([a,b],[c,d])$. We prove that
$[a,b]{\mathpzc{2}\mathpzc{4}}_{ii}[c,d]$ by eliminating every other
possibility. First, observe that they cannot have their starting point in
common (third line), and they cannot contain each other nor can one of them be
after the other (fourth line). Thus, we eliminated
$=_{i},{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}$
among the possible relation between $x_{i}$ and $y_{i}$. Assume, by way of
contradiction, that $y_{i}{\mathpzc{3}\mathpzc{4}}_{ii}x_{i}$. The second and
fourth conjuncts together imply that
$w_{i}{\mathpzc{1}\mathpzc{4}}_{ii}y_{i}$, and since $w_{i}$ (resp., $z_{i}$)
has the same starting point as $y_{i}$ (resp., $x_{i}$), and since
$z_{i}{\mathpzc{4}\mathpzc{4}}_{ii}t_{i}$, obviously
$w_{i}{\mathpzc{4}\mathpzc{4}}_{ii}t_{i}$, which is in contradiction with the
fourth line. Assume now that $x_{i}{\mathpzc{3}\mathpzc{4}}_{ii}y_{i}$. First,
observe that $z_{i}$ cannot be shorter than $x_{i}$, otherwise it would be
$z_{i}{\mathpzc{4}\mathpzc{4}}_{ii}w_{i}$ (contradicting the fourth line); but
then, $z_{i}$ cannot be equal to $x_{i}$ or longer than it, as in that case
$x_{i}{\mathpzc{4}\mathpzc{4}}_{ii}t_{i}$ (contradicting, once again, the
requirement in the fourth line). Now, suppose that
$x_{i}{\mathpzc{0}\mathpzc{3}}_{ii}y_{i}$. Let $w_{i}=[e,f]$, where $e=c$.
Clearly, to comply with the fourth line, it cannot be that $f<a$ or that
$f>b(=d)$. If, on the other hand, $a\leq f\leq b$, then it is impossible to
place $z_{i}=[g,h]$ ($g=a$), as it must be that $h<f$ (since
$w_{i}{\mathpzc{4}\mathpzc{4}}_{ii}t_{i}$ leads to a contradiction), but,
then, $z_{i}{\mathpzc{0}\mathpzc{4}}_{ii}y_{i}$, in contradiction with the
fourth line. Therefore, we cannot place $w_{i}$, which means that we have a
contradiction. Next suppose that $y_{i}{\mathpzc{0}\mathpzc{3}}_{ii}x_{i}$.
Let $w_{i}=[e,f]$, where $e=c$; clearly, $f\geq d$, as, otherwise, we would
have that $x_{i}$ contains $w_{i}$ (forbidden by the fourth line); but, then,
it is impossible to find any $s_{i}$ that contains $w_{i}$ and not $y_{i}$
(second line), leading to a contradiction. Finally, if
$y_{i}{\mathpzc{2}\mathpzc{4}}_{ii}x_{i}$, it is impossible to place
$w_{i},z_{i}$ and $t_{i}$ in such a way that
$z_{i}{\mathpzc{4}\mathpzc{4}}_{ii}t_{i}$,
$\neg(z_{i}{\mathpzc{0}\mathpzc{4}}_{ii}w_{i})$, and
$\neg(w_{i}{\mathpzc{0}\mathpzc{4}}_{ii}t_{i})$. Having eliminated every other
possibility, it must be that $x_{i}{\mathpzc{2}\mathpzc{4}}_{ii}y_{i}$.
Finally, observe that he case
$\\{{\mathpzc{0}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$
can be dealt with the very same argument, only having ${\mathpzc{0}}_{ip}$
playing the same role as ${\mathpzc{1}}_{ip}$. The corresponding definition is
therefore almost identical to the one of the previous case.

######  Lemma 14.

Tab. 14 is correct.

######  Proof 3.12.

Consider the following definitions:

$x_{i}{\mathpzc{0}\mathpzc{4}}_{ii}y_{i}\leftrightarrow\left\\{\begin{array}[]{ll}\exists
z_{i}t_{i}z_{p}t_{p}x_{i}^{\prime}x_{i}^{\prime\prime}(y_{i}{\mathpzc{2}}_{ip}z_{p}\wedge
y_{i}{\mathpzc{2}}_{ip}t_{p}\wedge
z_{i}{\mathpzc{2}\mathpzc{4}}_{ii}t_{i}\wedge
x_{i}^{\prime}{\mathpzc{4}\mathpzc{4}}_{ii}x_{i}^{\prime\prime}\wedge
z_{i}{\mathpzc{2}}_{ip}z_{p}\wedge
t_{i}{\mathpzc{2}}_{ip}t_{p}\wedge&\\{{\mathpzc{2}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}\\\
\hskip
56.9055pt\neg(z_{i}{\mathpzc{2}}_{ip}t_{p})\wedge\neg(t_{i}{\mathpzc{2}}_{ip}z_{p})\wedge&\\\
\hskip
56.9055pt\bigwedge\limits_{s_{i}\in\\{x_{i},x_{i}^{\prime},x_{i}^{\prime\prime}\\}}(\neg(s_{i}{\mathpzc{2}}_{ip}z_{p})\wedge\neg(s_{i}{\mathpzc{2}}_{ip}t_{p}))\wedge&\\\
\hskip
56.9055pt\bigwedge\limits_{s_{i}\in\\{y_{i},x_{i},z_{i},t_{i}\\},r\in\\{{\mathpzc{4}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}(\neg(x_{i}^{\prime}~{}r~{}s_{i})\wedge\neg(s_{i}~{}r~{}x_{i}^{\prime}))\wedge&\\\
\hskip
56.9055pt\bigwedge\limits_{s_{i}\in\\{y_{i},x_{i}^{\prime},x_{i}^{\prime\prime},z_{i},t_{i}\\},r\in\\{{\mathpzc{4}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}(\neg(x_{i}~{}r~{}s_{i})\wedge\neg(s_{i}~{}r~{}x_{i}))\wedge&\\\
\hskip
56.9055pt\bigwedge\limits_{s_{i}\in\\{y_{i},x_{i},z_{i},t_{i}\\},r\in\\{{\mathpzc{4}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}}(\neg(x_{i}^{\prime\prime}~{}r~{}s_{i})\wedge\neg(s_{i}~{}r~{}x_{i}^{\prime\prime})))&\\\
&\\\ \exists z_{i}t_{i}(\forall
k_{p}(x_{i}{\mathpzc{0}}_{ip}k_{p}\leftrightarrow
z_{i}{\mathpzc{0}}_{ip}k_{p})\wedge\forall
k_{p}(y_{i}{\mathpzc{0}}_{ip}k_{p}\leftrightarrow
t_{i}{\mathpzc{0}}_{ip}k_{p})\wedge{}&\\{{\mathpzc{0}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}\\\
\hskip 22.76228pt\forall
w_{i}(y_{i}{\mathpzc{4}\mathpzc{4}}_{ii}w_{i}\leftrightarrow
z_{i}{\mathpzc{4}\mathpzc{4}}_{ii}w_{i})\wedge
t_{i}{\mathpzc{2}\mathpzc{4}}_{ii}z_{i}\wedge{}&\\\ \hskip
22.76228pt\neg\forall k_{p}(x_{i}{\mathpzc{0}}_{ip}k_{p}\leftrightarrow
y_{i}{\mathpzc{0}}_{ip}k_{p})\wedge&\\\ \hskip
22.76228pt\displaystyle{\bigwedge\limits_{\begin{subarray}{c}s_{i},w_{i}\in\\{x_{i},y_{i},z_{i},t_{i}\\}\\\
\\{s_{i},w_{i}\\}\neq\\{t_{i},z_{i}\\}\end{subarray}}(\neg(s_{i}{\mathpzc{2}\mathpzc{4}}_{ii}w_{i})\wedge\neg(s_{i}{\mathpzc{4}\mathpzc{4}}_{ii}w_{i}))})&\\\
&\\\ \exists z_{i}t_{i}(\forall
k_{p}(x_{i}{\mathpzc{1}}_{ip}k_{p}\leftrightarrow
z_{i}{\mathpzc{1}}_{ip}k_{p})\wedge\forall
k_{p}(y_{i}{\mathpzc{1}}_{ip}k_{p}\leftrightarrow
t_{i}{\mathpzc{1}}_{ip}k_{p})\wedge{}&\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}\\\
\hskip 22.76228pt\forall
w_{i}(y_{i}{\mathpzc{4}\mathpzc{4}}_{ii}w_{i}\leftrightarrow
z_{i}{\mathpzc{4}\mathpzc{4}}_{ii}w_{i})\wedge
t_{i}{\mathpzc{2}\mathpzc{4}}_{ii}z_{i}\wedge{}&\\\ \hskip
22.76228pt\neg\exists k_{p}(x_{i}{\mathpzc{1}}_{ip}k_{p}\wedge
y_{i}{\mathpzc{1}}_{ip}k_{p})\wedge&\\\ \hskip
22.76228pt\displaystyle{\bigwedge\limits_{\begin{subarray}{c}s_{i},w_{i}\in\\{x_{i},y_{i},z_{i},t_{i}\\}\\\
\\{s_{i},w_{i}\\}\neq\\{t_{i},z_{i}\\}\end{subarray}}(\neg(s_{i}{\mathpzc{2}\mathpzc{4}}_{ii}w_{i})\wedge\neg(s_{i}{\mathpzc{4}\mathpzc{4}}_{ii}w_{i}))})\end{array}\right.$

Let us start by
$\\{{\mathpzc{2}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$.
Suppose that $\mathcal{F}\models[c,d]{\mathpzc{0}\mathpzc{4}}_{ii}[a,b]$.
Then, by definition, $a<c<d<b$; to satisfy $\varphi$ we set:
$x_{i}^{\prime}=[a,c],x_{i}^{\prime\prime}=[d,b],z_{i}=[a,d],t_{i}=[c,b],z_{p}=c$,
and $t_{p}=d$. Suppose, now, that $\mathcal{F}\models\varphi([c,d],[a,b])$ and
that $z_{i}=[b_{z},e_{z}]$, $t_{i}=[b_{t},e_{t}]$,
$x^{\prime}=[b^{\prime},e^{\prime}]$ and
$x^{\prime\prime}=[b^{\prime\prime},e^{\prime\prime}]$. First, observe that
$y_{i}=[a,b]$ must have two internal points $z_{p}$ and $t_{p}$, and that
$z_{p}$ ($t_{p}$) must be contained in $z_{i}$ ($t_{i}$) and not in $t_{i}$
($z_{i}$). Since $z_{i}$ overlaps $t_{i}$ we must have $z_{p}<t_{p}$. We
deduce that $a<z_{p}\leq b_{t}<e_{z}\leq t_{p}<b$. The constraints on
$x^{\prime}$ and $x^{\prime\prime}$ in lines 1, 3, 4 and 6 of the definition
imply that we must have $e^{\prime}=b_{t}=z_{p}$ and
$b^{\prime\prime}=e_{z}=t_{p}$. This gives
$a<z_{p}=b_{t}=e^{\prime}<b^{\prime\prime}=e_{z}=t_{p}<b$. Now, the only way
to place $x_{i}=[c,d]$ without violating the third and fifth line of the
definition is that $e^{\prime}=c<d=b^{\prime\prime}$. Consequently $a<c<b<d$,
as desired. Consider, now,
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$.
Suppose that $\mathcal{F}\models[c,d]{\mathpzc{0}\mathpzc{4}}_{ii}[a,b]$.
Then, by definition, $a<c<d<b$; by setting $z_{i}=[c,b]$ and $t_{i}=[a,d]$, we
satisfy all requirements. Suppose, now, that
$\mathcal{F}\models\varphi([c,d],[a,b])$. Once more, we eliminate every
possible relation between $x_{i}$ and $y_{i}$, except for
$x_{i}{\mathpzc{0}\mathpzc{4}}_{ii}y_{i}$. As before,
${\mathpzc{1}\mathpzc{4}}_{ii}$, ${\mathpzc{2}\mathpzc{4}}_{ii}$, and
${\mathpzc{4}\mathpzc{4}}_{ii}$ are immediately eliminated (third and fourth
line). If $x_{i}{\mathpzc{3}\mathpzc{4}}_{ii}y_{i}$, then, since $z_{i}$
(resp., $t_{i}$) and $x_{i}$ (resp., $y_{i}$) have the same starting point
(first line), it is not possible to have
$t_{i}{\mathpzc{2}\mathpzc{4}}_{ii}z_{i}$, contradicting the second line.
Suppose, now, that $y_{i}{\mathpzc{3}\mathpzc{4}}_{ii}x_{i}$. First, observe
that $z_{i}$ (which starts at the same point as $x_{i}$) cannot start or be
equal to $x_{i}$, since in that case $t_{i}{\mathpzc{2}\mathpzc{4}}_{ii}x_{i}$
(contradicting the fourth line). But then, if $z_{i}$ is started by $x_{i}$,
there will be some interval that is after $y_{i}$ which is not after $z_{i}$
itself, contradicting the second line. Thus, ${\mathpzc{3}\mathpzc{4}}_{ii}$
is eliminated. Assume that $x_{i}{\mathpzc{0}\mathpzc{3}}_{ii}y_{i}$. As
before, $z_{i}$ cannot start or be equal to $x_{i}$, since in that case
$t_{i}{\mathpzc{2}\mathpzc{4}}_{ii}x_{i}$ (contradicting the fourth line).
Moreover, if $z_{i}$ is started by $x_{i}$, it would imply that
$y_{i}{\mathpzc{2}\mathpzc{4}}_{ii}z_{i}$, again, a contradiction with the
fourth line. If $y_{i}{\mathpzc{0}\mathpzc{3}}_{ii}x_{i}$, $y_{i}=_{i}x_{i}$,
or $y_{i}{\mathpzc{0}\mathpzc{4}}_{ii}x_{i}$, then it is impossible to
correctly place $z_{i}$ and $t_{i}$ in such a way that
$t_{i}{\mathpzc{2}\mathpzc{4}}_{ii}z_{i}$. Having eliminated in this case all
other possibilities, we conclude that
$x_{i}{\mathpzc{0}\mathpzc{4}}_{ii}y_{i}$. Once again, we can deal with
$\\{{\mathpzc{0}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$
with the exact same argument, where ${\mathpzc{0}}_{ip}$ plays the role of
${\mathpzc{1}}_{ip}$.

Proved |  Symmetric |  Implied |  Deduction Chain
---|---|---|---
$\\{{\mathpzc{0}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
$\\{{\mathpzc{2}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  - |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}\mathpzc{4}}_{ii},<\\}$ |  ${\mathpzc{2}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{4}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  Section 3.1

Table 14. The spectrum of the $\mathsf{mcs}({\mathpzc{0}\mathpzc{4}}_{ii})$. -
Class: $\mathsf{Lin}$.

(Lemma 14.)

######  Lemma 15.

Tab. 15 is correct.

######  Proof 3.13.

As always, we start with the definition:

$\begin{array}[]{llll}x_{i}{\mathpzc{4}\mathpzc{4}}_{ii}y_{i}&\leftrightarrow&\exists
z_{i}t_{i}\big{(}\exists k_{p}(x_{i}{\mathpzc{1}}_{ip}k_{p}\wedge
z_{i}{\mathpzc{1}}_{ip}k_{p})\wedge\neg\exists
k_{p}(x_{i}{\mathpzc{1}}_{ip}k_{p}\wedge
y_{i}{\mathpzc{1}}_{ip}k_{p})\wedge&\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}\\\
&&\hskip 22.76228pt\forall w_{i}(\forall
k_{p}(y_{i}{\mathpzc{1}}_{ip}k_{p}\rightarrow
w_{i}{\mathpzc{1}}_{ip}k_{p})\rightarrow\neg(z_{i}{\mathpzc{0}\mathpzc{4}}_{ii}w_{i}))\wedge{}&\\\
&&\hskip 22.76228pt\forall w_{i}(\forall
k_{p}(t_{i}{\mathpzc{1}}_{ip}k_{p}\rightarrow
w_{i}{\mathpzc{1}}_{ip}k_{p})\rightarrow\neg(w_{i}{\mathpzc{0}\mathpzc{4}}_{ii}x_{i}))\wedge{}&\\\
&&\hskip 22.76228pt\forall w_{i}(\forall
k_{p}(y_{i}{\mathpzc{1}}_{ip}k_{p}\rightarrow
w_{i}{\mathpzc{1}}_{ip}k_{p})\rightarrow\neg(z_{i}{\mathpzc{2}\mathpzc{4}}_{ii}w_{i}))\wedge{}&\\\
&&\hskip 22.76228pt\forall w_{i}(\forall
k_{p}(y_{i}{\mathpzc{1}}_{ip}k_{p}\rightarrow
w_{i}{\mathpzc{1}}_{ip}k_{p})\rightarrow\neg(x_{i}{\mathpzc{0}\mathpzc{4}}_{ii}w_{i}))\wedge{}&\\\
&&\hskip 22.76228pt\forall w_{i}(\forall
k_{p}(y_{i}{\mathpzc{1}}_{ip}k_{p}\rightarrow
w_{i}{\mathpzc{1}}_{ip}k_{p})\rightarrow\neg(w_{i}{\mathpzc{2}\mathpzc{4}}_{ii}z_{i}))\wedge{}&\\\
&&\hskip
22.76228ptz_{i}{\mathpzc{2}\mathpzc{4}}_{ii}t_{i}\wedge\displaystyle{\bigwedge\limits_{\begin{subarray}{c}s_{i},w_{i}\in\\{x_{i},y_{i},z_{i},t_{i}\\}\\\
\\{s_{i},w_{i}\\}\neq\\{z_{i},t_{i}\\}\end{subarray}}(\neg(s_{i}{\mathpzc{2}\mathpzc{4}}_{ii}w_{i})\wedge\neg(s_{i}{\mathpzc{0}\mathpzc{4}}_{ii}w_{i}))})\end{array}$

Proved |  Symmetric |  Implied |  Deduction Chain
---|---|---|---
$\\{{\mathpzc{0}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{0}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{2}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{3}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{4}}_{ip}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{2}}_{ip},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{3}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{4}}_{ip},{\mathpzc{1}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{1}\mathpzc{4}}_{ii},{\mathpzc{2}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{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{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{3}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{0}\mathpzc{3}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$ |  ${\mathpzc{3}\mathpzc{4}}_{ii}$
|  |  $\\{{\mathpzc{3}\mathpzc{4}}_{ii}\\}$ |  Section 3.1

Table 15. The spectrum of the $\mathsf{mcs}({\mathpzc{4}\mathpzc{4}}_{ii})$. -
Class: $\mathsf{Lin}$.

(Lemma 15.)

Following the same schema of the previous two relations, consider the case of
$\\{{\mathpzc{1}}_{ip},{\mathpzc{2}\mathpzc{4}}_{ii},{\mathpzc{0}\mathpzc{4}}_{ii}\\}$,
and suppose that $\mathcal{F}\models[a,b]{\mathpzc{4}\mathpzc{4}}_{ii}[c,d]$.
Then, by definition, $a<b<c<d$; by setting $z_{i}=[a,c]$ and $t_{i}=[b,d]$,
all requirements are satisfied. Suppose, now, that
$\mathcal{F}\models\varphi([a,b],[c,d])$. We prove that
$[a,b]{\mathpzc{4}\mathpzc{4}}_{ii}[c,d]$ by eliminating every other possible
relation that may hold between $x_{i}$ and $y_{i}$. The relations $=_{i}$,
${\mathpzc{1}\mathpzc{4}}_{ii}$, ${\mathpzc{2}\mathpzc{4}}_{ii}$ and
${\mathpzc{0}\mathpzc{4}}_{ii}$ are eliminated immediately thanks to the first
and last lines of the definition. Suppose, by way of contradiction, that
$x_{i}{\mathpzc{3}\mathpzc{4}}_{ii}y_{i}$. The interval $z_{i}$, which must
start at $a$ (first line), cannot end between $c$ and $d$ in order to comply
with the fact that it cannot overlap $y_{i}$ (last line). If $z_{i}$ ends at
$d$ then, since $z_{i}{\mathpzc{2}\mathpzc{4}}_{ii}t_{i}$, we must have (i)
$t_{i}$ beginning between $a$ and $b$ which causes it to contain $y_{i}$
contradicting the last line, or (ii) $t_{i}$ beginning at $b=c$ which causes a
contradiction with the fourth line, or (iii) $t_{i}$ beginning between at $c$
and $d$ causing $y_{i}$ to overlap $t_{i}$, contradicting the last line. If
$z_{i}$ ends after $d$, then $y_{i}$ is contained in $z_{i}$ contradicting the
last line. If $z_{i}$ ends at $c$ then $t_{i}$ overlaps $x_{i}$ contradicting
the last line. If $z_{i}$ ends between $a$ and $b$ the overlap between $z_{i}$
and $t_{i}$ begins with $t_{i}$ and is contained in $x_{i}$, contradicting the
third line. This eliminates all possibilities for the placement of $z_{i}$ and