Model-completeness for the lattice of finite unions of closed intervals of a dense linear order

$(1)\Rightarrow(2)$: If $A\neq\bot$ and $A\neq\mathbf{0}$ then it is immediate that $A\setminus\mathbf{0}$ is not $\bot$. This gives us that $\operatorname{s}_{A\cup\mathbf{0}}(0)$ is defined (i.e. $0\in\mathbb{I}$ has a successor in $\mathbf{0}\cup A$). Then $\operatorname{s}_{A\cup\mathbf{0}}(0)\in A$ which by definition gives us $\mathbf{0}\subseteq\mathfrak{s}^{-1}(A\cup\mathbf{0},A)$.

$(2)\Rightarrow(1)$: Suppose $A=\bot$. From this it follows immediately that $A\neq\mathbf{0}$. Moreover $\mathfrak{s}^{-1}(A\cup\mathbf{0},A)=\mathfrak{s}^{-1}(\mathbf{0},\bot)$ which is $\bot$, hence $\mathbf{0}\not\subseteq\mathfrak{s}^{-1}(A\cup\mathbf{0},A)$. ∎

First note that for each $A,B\in\mathcal{P}_{\operatorname{fin}}(\mathbb{I})$, $A\setminus B=C$ if and only if,

$$(A\cap B)\cup C=A\text{ and }B\cap C=\bot.$$

Therefore every positive existential $(\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}\cup\{\setminus\})$-formula is equivalent to a positive existential $\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}$-formula (working in $\operatorname{W}(\mathbb{I})$, with $\setminus$ a binary function symbol interpreted as relative complement). So it is enough to check that every quantifier-free $\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}$-formula is equivalent to a positive existential $(\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}\cup\{\setminus\})$-formula. It is enough to check that the negation of an atomic $(\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}\cup\{\setminus\})$-formula is equivalent to a positive existential $(\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}\cup\{\setminus\})$-formula in $\operatorname{W}(\mathbb{I})$. Atomic formulas are all of the form $q_{1}(\bar{X})=q_{2}(\bar{X})$ for $\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}$-terms $q_{1},q_{2}$. Let $\Delta(q_{1}(\bar{X}),q_{2}(\bar{X}))$ be shorthand for $(q_{1}(\bar{X})\setminus q_{2}(\bar{X}))\cup(q_{2}(\bar{X})\setminus q_{1}(\bar{X}))$, i.e. the symmetric difference of $q_{1}$ and $q_{2}$. The formula $\neg(q_{1}(\bar{X})=q_{2}(\bar{X}))$ is equivalent over $\operatorname{W}(\mathbb{I})$ to,

$$\exists Y(Y\neq\bot\wedge Y\subseteq\Delta(q_{1}(\bar{X}),q_{2}(\bar{X}))),$$

but using lemma 3.3 this in turn is equivalent over $\operatorname{W}(\mathbb{I})$ to,

$$\exists Y((Y=\mathbf{0}\vee\mathbf{0}\subseteq\mathfrak{s}^{-1}(Y\cup\mathbf{0},Y))\text{ and }Y\subseteq\Delta(q_{1}(\bar{X}),q_{2}(\bar{X}))),$$

which is positive existential as required. ∎

That $\operatorname{W}(\mathbb{I})$ is model-complete is proved in my thesis [Lin21] (see theorem 5.4.7 on page 141). The result then follows immediately from proposition 3.5. ∎

Under our interpretation, an element $A\in\mathcal{P}_{\operatorname{fci}}(\mathbb{I})$ is bounded if and only if $A=\bot$ or $\max(A)\neq\bot$. Conversely the unbounded elements are precisely those $A\in\mathcal{P}_{\operatorname{fci}}(\mathbb{I})$ for which $A\neq\bot$ and $\max(A)=\bot$.

Therefore $\operatorname{Bd}$ is in fact a quantifier-free definable set in $\operatorname{L}(\mathbb{I})$. ∎

The formula $l(X)=r(X)$ defines $\mathcal{P}_{\operatorname{fin}}(\mathbb{I})$ in $\operatorname{L}(\mathbb{I})$. ∎

First suppose that $\mathfrak{s}^{-1}(A,B)=C$, we will show that one of the two conditions must then hold. Let $E$ be the union of all of the open intervals of $\mathbb{I}$ of the form $(i,j)$ for some $i\in C$ and $j\in B$ such that $\operatorname{s}_{A}(i)=j$. Now take $D=\mathbb{I}\setminus E\in\mathcal{P}_{\operatorname{fci}}(\mathbb{I})$.

By definition we get that $C\subseteq A$. Then $A\subseteq D$ follows from the choice that $E$ be made up from intervals $(i,j)$ where $\operatorname{s}_{A}(i)=j$. For if $A\not\subseteq D$ then we get $k\in A$ such that for some $i,j$ with $\operatorname{s}_{A}(i)=j$ we have $i<k<j$, a contradiction.

For our choice of $E$, it is easy to check that $l(E)=C$ and $r(E)$ is either,

1. (i)

   $B\setminus\min(B)$ if $\min(A)\subseteq B$, or,

2. (ii)

   $B$ if $\min(A)\not\subseteq B$.

Taking the complement, we interchange left and right endpoints, and introduce $0$ as a left endpoint. This gives us precisely that $(1)$ or $(2)$ hold for our choice of $D$.

Now for the other direction, suppose that $D\in\mathcal{P}_{\operatorname{fci}}(\mathbb{I})$ exists such that $(2)$ holds. We want to show that $\mathfrak{s}^{-1}(A,B)=C$. Let $i\in\mathfrak{s}^{-1}(A,B)$, so $i\in A$ is such that $\operatorname{s}_{A}(i)\in B\subseteq l(D)$. Now $i\notin C=r(D)$ implies that $i\in A\setminus D$, contradicting our assumption that $A\subseteq D$. So we have established that $\mathfrak{s}^{-1}(A,B)\subseteq C$ follows from $(2)$. Let $i\in C$, so by $(2)$ we have $i\in r(D)$. Suppose towards a contradiction that $\operatorname{s}_{A}(i)\notin B$. Then moreover $\operatorname{s}_{i}(A)\notin B\cup\mathbf{0}=l(D)$. This again gives us that $i\in A\setminus D$, contradicting our assumption that $A\subseteq D$. Therefore we have shown that $\mathfrak{s}^{-1}(A,B)=C$ follows from $(2)$.

We leave the checking of details in showing that $\mathfrak{s}^{-1}(A,B)=C$ follows from $(1)$ to the reader. ∎

Suppose $(1)$ holds. Then we can rewrite $(2)$ as follows,

1. (2)

   $A_{l}\neq\bot$, $\min(A_{l}\cup A_{r})\subseteq A_{l}$, and one of the following holds,

   1. (a)

      $\max(A_{l}\cup A_{r})\subseteq A_{r}\text{ and }\mathfrak{s}^{-1}(A_{l}\cup A_{r},A_{r}\setminus A_{l})=A_{l}\setminus A_{r}$,

   2. (b)

      $\max(A_{l}\cup A_{r})\subseteq A_{l}\setminus A_{r}\text{ and }\mathfrak{s}^{-1}(A_{l}\cup A_{r},A_{r}\setminus A_{l})\cup\max(A_{l}\cup A_{r})=A_{l}\setminus A_{r}$.

Intuitively then, (2) first says that $A$ has at least one left endpoint, and that the smallest endpoint of $A$ is a left endpoint. Then both (a) and (b) simply say that the proper left endpoints and proper right endpoints appear in pairs, with proper right endpoints immediately preceded by proper left endpoints. An exception is needed simply for the case where $A$ is unbounded, in which case the largest endpoint is a proper left endpoint which is not the predecessor of a proper right endpoint (this is dealt with by (b)).

Conversely, suppose that $(2)$ holds. It is straightforward to construct $A\in\mathcal{P}_{\operatorname{fci}}(\mathbb{I})$ such that $A_{l}=B$ and $A_{r}=C$. ∎

We split into two cases, according to whether $A\in\mathcal{P}_{\operatorname{fci}}(\mathbb{I})$ is bounded or unbounded (see lemma 4.3). Let $\phi_{\operatorname{Bd}}(X_{l},X_{r},Z)$ be the $\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}$-formula,

$$\mathfrak{s}^{-1}(X^{\partial}\cup Z,Z)\subseteq X_{l}\setminus X_{r}\text{ and }\mathfrak{s}^{-1}(X^{\partial}\cup Z,X_{r}\setminus X_{l})\cap Z\neq\bot,$$

this ‘says’ that the predecessor of $Z$ is a proper left endpoint and that $Z$ is the predecessor of a right endpoint, Then let $\phi_{\neg\operatorname{Bd}}(X_{l},X_{r},Z)$ be the $\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}$-formula,

$$(\mathfrak{s}^{-1}(X^{\partial}\cup Z,Z)\subseteq X_{l}\setminus X_{r}\text{ and }\mathfrak{s}^{-1}(X^{\partial}\cup Z,X_{r}\setminus X_{l})\cap Z\neq\bot)\text{ or }Z=\max(X^{\partial}\cup Z),$$

this ‘says’ that the condition in $\phi_{\operatorname{Bd}}$ holds or that $Z$ is greater than or equal to all left and right endpoints. Then for each $i\in\mathbb{I}$ and $A\in\mathcal{P}_{\operatorname{fci}}(\mathbb{I})$ the following are equivalent,

1. (1)

   $i\in A$,

2. (2)

   $\operatorname{W}(\mathbb{I})\models A^{\partial}\neq\bot$ (so that $A\neq\bot$) and one of the following holds,

   1. (a)

      $\operatorname{W}(\mathbb{I})\models\{i\}\subseteq A^{\partial}$ or,

   2. (b)

      $\operatorname{W}(\mathbb{I})\models\operatorname{Bd}(A)$ and $\phi_{\operatorname{Bd}}(A_{l},A_{r},\{i\})$, or,

   3. (c)

      $\operatorname{W}(\mathbb{I})\models\neg\operatorname{Bd}(A)$ and $\phi_{\neg\operatorname{Bd}}(A_{l},A_{r},\{i\})$.

In other words $i\in A$ if and only if $A$ is nonempty and either $i$ is an endpoint of $A$, or $i$ sits between a left and right endpoint of $A$, or $A$ is unbounded and $i$ sits in the unbounded part of $A$. The latter we have shown is definable in $\operatorname{W}(\mathbb{I})$ by giving $\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}$-formulas, so $\phi_{\in}$ exists. ∎

Let $\operatorname{At}(Z)$ be the formula $Z\neq\bot\wedge Z=\min(Z)$. In $\operatorname{W}(\mathbb{I})$ this defines the collection of singletons. Therefore we can take for $\phi_{\subseteq}$ the $\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}$-formula,

$$\forall Z(\operatorname{At}(Z)\rightarrow(\phi_{\in}(X_{l},X_{r},Z)\rightarrow\phi_{\in}(Y_{l},Y_{r},Z))).$$

This says that every singleton contained in $X$ is contained in $Y$, as required. ∎

Let $\phi(\bar{X})$ be an $\mathscr{L}_{{\scriptscriptstyle\operatorname{L}(\mathbb{I})}}$-formula. We will show that over $\operatorname{L}(\mathbb{I})$ the formula $\phi$ is equivalent to an existential formula $\phi^{*}$.

Using our interpretation of $\operatorname{L}(\mathbb{I})$ in $\operatorname{W}(\mathbb{I})$ (in particular corollary 6.5), for each $\mathscr{L}_{{\scriptscriptstyle\operatorname{L}(\mathbb{I})}}$-formula $\phi(\bar{X})$ there is an $\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}$-formula $\psi(\bar{Y})$ such that for each $\bar{A}\in\mathcal{P}_{\operatorname{fci}}(\mathbb{I})$,

$$\operatorname{L}(\mathbb{I})\models\phi(\bar{A})\Longleftrightarrow\operatorname{W}(\mathbb{I})\models\psi(\bar{A_{l}},\bar{A_{r}}).$$

Without loss of generality we can take $\psi(\bar{Y})$ to be a positive existential $\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}$-formula. This is because theorem 3.6, the positive model-completeness of $\operatorname{W}(\mathbb{I})$, tells us precisely that every $\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}$-formula is equivalent to some positive existential $\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}$-formula over $\operatorname{W}(\mathbb{I})$.

Using our interpretation of $\operatorname{W}(\mathbb{I})$ in $\operatorname{L}(\mathbb{I})$ (in particular corollary 5.6), for each $\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}$-formula $\psi(\bar{Y})$ there is an $\mathscr{L}_{{\scriptscriptstyle\operatorname{L}(\mathbb{I})}}$-formula $\theta(\bar{Y})$ such that for each $\bar{B}\in\mathcal{P}_{\operatorname{fin}}(\mathbb{I})$,

$$\operatorname{W}(\mathbb{I})\models\psi(\bar{B})\Longleftrightarrow\operatorname{L}(\mathbb{I})\models\theta(\bar{B}),$$

and so in particular taking $\bar{B}=(\bar{A_{l}},\bar{A_{r}})$ we get,

$$\operatorname{W}(\mathbb{I})\models\psi(\bar{A_{l}},\bar{A_{r}})\Longleftrightarrow\operatorname{L}(\mathbb{I})\models\theta(\bar{A_{l}},\bar{A_{r}}).$$

Moreover, as $\psi(\bar{Y})$ is a positive existential $\mathscr{L}_{{\scriptscriptstyle\operatorname{W}(\mathbb{I})}}$-formula, corollary 5.6 tells us that $\theta(\bar{Y})$ can additionally be chosen to be an existential $\mathscr{L}_{{\scriptscriptstyle\operatorname{L}(\mathbb{I})}}$-formula. Note that without the positive model-completeness of $\operatorname{W}(\mathbb{I})$, we could not have taken $\psi(\bar{Y})$ positive existential, and therefore could not have taken $\theta$ to be existential.

Combining $\eqref{star}$ and $\eqref{dagger}$ we get that for each $\bar{A}\in\mathcal{P}_{\operatorname{fci}}(\mathbb{I})$,

$$\operatorname{L}(\mathbb{I})\models\phi(\bar{A})\Longleftrightarrow\operatorname{L}(\mathbb{I})\models\theta(\bar{A_{l}},\bar{A_{r}}).$$

Now, $l$ and $r$ are part of the signature $\mathscr{L}_{{\scriptscriptstyle\operatorname{L}(\mathbb{I})}}$, so we take $\phi^{*}(\bar{X})$ to be the formula $\theta(\bar{X_{l}},\bar{X_{r}})$. Our choice of $\phi^{*}$ is clearly existential, as $\theta$ is existential. Putting everything together, we get that,

$$\operatorname{L}(\mathbb{I})\models\forall\bar{X}(\phi(\bar{X})\leftrightarrow\phi^{*}(\bar{X})),$$

and hence $\operatorname{L}(\mathbb{I})$ is model-complete. ∎