[a]

# Isolated Suborders and their Application to Counting Closure Operators

Roland Glück0000-0001-7909-1942  Deutsches Zentrum für Luft- und Raumfahrt,
D-86159 Augsburg, Germany<EMAIL_ADDRESS>
###### Abstract.

In this paper, we investigate the interplay between isolated suborders and
closures. Isolated suborders are a special kind of suborders and can be used
to diminish the number of elements of an ordered set by means of a quotient
construction. The decisive point is that there are simple formulae
establishing relationships between the number of closures in the original
ordered set and the quotient thereof induced by isolated suborders. We show
how these connections can be used to derive a recursive algorithm for counting
closures, provided the ordered set under consideration contains suitable
isolated suborders.

###### Key words and phrases:

hull, closure, counting, isolated suborder

##  1\. Introduction

A widespread and common concept in various areas of mathematics and computer
science are hull or closure operators, i.e., idempotent, isotone and extensive
endofunctions on some ordered set. The best-known examples include the
topological closure in traditional analysis, the (reflexive) transitive
closure of a relation or a graph, and the Kleene closure in language theory.
There are also more complicated and sophisticated appearances as for example
in automated reasoning (see e.g. [EBJ+14]), data base theory (as in [DHLM92]),
or the algebraic analysis of connected components (as demonstrated in
[Glü17]). Most of this work uses hulls or closures mainly as a tool for
specific purposes but does not investigate the properties of these operators.

If we take a look at the work dealing with actual properties of closures, then
we see that most of this work is concerned with closures on powerset lattices
which falls also under the term “Moore family” (here [CM03] gives a survey;
for more recent results see e.g. [BD18]). Some other work deals with closures
on lattices although closures can also be defined on general ordered sets. The
appoach from [DHLM92] does not rely on lattice properties (it is not
explicitly stated whether a lattice structure is required); however, if one
tries to extend the ideas from one single database table to several tables,
then a nearby approach (using tuples of choice functions) leads to an order
lacking at least a binary supremum operator.

In recent years, counting structures of interest has become a rising area of
research in order theory and related topics. For example, [AJS21] gives
numbers of so-called $d\ell$-structures of various kinds, [QRRV20] counts
join-endomorphisms in lattices, [BPBV18] generates and counts a certain kind
of bisemilattices whereas the topic of [BBW21] are topological spaces, and
different kinds of posets are counted in [FJST20]. However, to our best
knowledge, there is no work dealing with the number of closures on general
lattices or orders. The only results we are aware of concern the power set
lattice $(\mathcal{P}(S),\subseteq)$. For this special structure, the exact
number of closure operators is known only up to $|S|=7$ (for curiosity, there
are 14.087.648.235.707.352.472 of them, as shown in [CIR10] only in 2010).

The present work introduces a heuristic method for structuring ordered sets in
a way that eases under certain circumstances the computation of the number of
closure operators. The key idea are so called isolated suborders which are
intuitively speaking suborders which have contact with the rest of the ordered
set only via their least and greatest element. By means of quotient orders, we
can reduce the number of elements of the ordered set under consideration and
obtain an ordered set with a certain structure for which there are closed
formulae for the number of closure operators available. Similar ideas were
used already in the predecessor work of [Glü21]. There, however, the area of
application was restricted to lattices whereas the present work generalizes
the results to general ordered sets. We stress that this generalization does
not lead to the common loss of strength of claims associated with
generalization. In particular, the specialization of the results in the
present paper to lattices leads exactly to the results obtained in [Glü21] for
lattices. This holds also for the main result of the paper, Algorithm 2, which
retains the same structure as in the predecessor paper. Additionally to this
generalization, the present work contains also thoughts about the computation
of isolated suborders.

Of course, heuristic approaches defy often precise analysis, however,
heuristics are an established tool if one has to deal with computationally
hard problems. One of the oldest example is the $\text{A}^{*}$ algorithm,
first described 1968 in [HNR68]. More recent examples are algorithms based on
tree decomposition as in [Bod88], outerplanarity as in [Kam07], or the vast
field of genetic algorithms, see e.g. [Gol89] for a first introduction. All of
these approaches have in common that a rigorous analysis is hard or even
impossible; consequently, we will also give only a rough analysis of our
algorithm in Section 7.

The remainder of this work is organized as follows: in Section 2, we introduce
some notation we will use in the sequel (on other places, we introduce
notation ad hoc to spare the reader annoying look-ups). Section 3 introduces
the main topic of the present work, closures, and shows important relations
between different characterizations of closures. The main tool of the present
work, isolated suborders, are the topic of Section 4 whereas Section 5 studies
the interplay between closures and isolated suborders. Because we look at
isolated suborders not only as an object of study but will use them as tool in
an algorithm, we investigate in Section 6 how to compute isolated suborders.
In Section 7, we put all our results together to obtain an algorithm for
counting closures which can make use of favorable structures of an ordered set
under consideration. Finally, the concluding Section 8 gives a short
retrospect of the work, raises some open issues, and sketches ways of further
research.

##  2\. Basic Notions and Properties

In this paper, we presuppose general knowledge of order and lattice theory,
and refer e.g. to [DP02, Grä11, Rom08] for the basics and e.g. to [Bir67,
JR92] for more advanced topics. We will, however, recapitulate some topics in
order to clarify matters and to obtain a consistent notion.

The symbol $\leq$ and derived variants thereof (by indexes or primes) denote
always an order whose carrier set is usually denoted by $S$ and variants
thereof. Given an order $\leq$, we use the symbol $\nleq$ for the relation
$\nleq\Leftrightarrow_{def}\neg(x\leq y)$. The associated strict order,
reverse order, and strict reverse order are denoted by $<$, $\geq$, and $>$,
respectively. In the case of existence, $\bot$ and $\top$ (also possibly
indexed) stand for the least and greatest element of an order. The sets of
maximal and minimal and least elements of a subset $S^{\prime}\subseteq S$ are
denoted by $\max{(S^{\prime})}$ and $\min{(S^{\prime})}$ , respectively,
whereas ${\sf lst}(S^{\prime})$ denotes the (possibly empty) set of least
elements of $S^{\prime}$. An element $x$ is said to _majorize_ an element $y$
if $x\geq y$ holds, and we extend this concept to sets by ${\sf
maj}(x,S^{\prime})=_{def}\\{y\in S^{\prime}\,|\,y\geq x\\}$. Two elements $x$
and $y$ are called _comparable_ , written $x\lessgtr y$, if $x\leq y$ or
$y\leq x$ holds. Consequently, we call $x$ and $y$ _incomparable_ if they are
not comparable, and denote this by $x\not\lessgtr y$. As usual, a _chain_ is a
set of elements which are pairwise comparable. A subset $S^{\prime}\subseteq
S$ of an ordered set $(S,\leq)$ is called _convex_ if for all $x,y\in
S^{\prime}$ and all $z\in S$ the implication $x\leq z\leq y\Rightarrow z\in
S^{\prime}$ holds. For intervals, we use the common notations
$[a,b]=_{def}\\{x\,|\,a\leq x\wedge x\leq b\\}$ and
$]a,b]=_{def}[a,b]\backslash\\{a\\}$. For a relation $R\subseteq S\times S$
and a subset $S^{\prime}\subseteq S$, we define the _restriction_ of $R$ to
$S^{\prime}$ routinely by $R|_{S^{\prime}}=_{def}\\{(s^{\prime},t^{\prime})\in
R\,|\,(s^{\prime},t^{\prime})\in S^{\prime}\times S^{\prime}\\}$.

Given an equivalence relation $E\subseteq S\times S$, we denote the
equivalence class of an element $s\in S$ under $E$ by $[s]_{E}$. For the set
of equivalence classes of such an equivalence relation $E\subseteq S\times S$
we use the notation $S/E$. For an arbitrary relation $R\subseteq S\times S$
and an equivalence relation $E\subseteq S\times S$ we define the _quotient_
$R/E\subseteq S/E\times S/E$ by $([x]_{E},[y]_{E})\in
R/E\Leftrightarrow_{def}$ $\exists x^{\prime}\in[x]_{E}\exists
y^{\prime}\in[y]_{E}:(x^{\prime},y^{\prime})\in R$. If $(S,\leq)$ is an
ordered set and $E\subseteq S\times S$ is an equivalence relation such that
$(S/E,\leq/E)$ is an ordered set, then we say that $E$ is _order generating_.
In this case, we may write also $\leq_{E}$ instead of $\leq/E$. Clearly, if
under these circumstances both $[x]_{E}$ and $[y]_{E}$ are singleton sets,
then we have the equivalence $x\leq y\iff[x]_{E}\leq_{E}[y]_{E}$ to which we
will often refer as _homomorphism properties_. Trivial examples of order
generating equivalences are the identity and the universal relation. However,
as counterexample, the relation $\sim$ on the ordered set $(\mathop{\rm\hskip
3.00003ptZZ\hskip 3.50006pt}\nolimits,\leq)$ (where $\leq$ denotes the usual
ordering of the integers), defined by $x\sim y\Leftrightarrow_{def}x\cdot
y\neq 0\vee x=y=0$, is obviously not order generating.

Since we will often have to consider the union of the sets of a set system
$\mathbf{C}$ (i.e., $\mathbf{C}$ is a set of sets), we use the abbreviation
$\bigcup\mathbf{C}=_{def}\bigcup\limits_{C\in\mathbf{C}}C$ to make the text
easier to read. Conversely, dealing with a set $C$, we use
$C^{\\{\\}}=_{def}\\{\\{c\\}\,|\,c\in C\\}$ to denote the set of singleton
sets consisting of the elements of $C$.

##  3\. Closures

The main topic of this work, closures, can be characterized in two different
ways, namely as endofunctions on ordered sets or as subsets of ordered sets.
At the end of this section we will see that these characterizations are
cryptomorphic; we start with the functional definition:

Given an ordered set $(S,\leq)$, an endofunction $c$ on $S$ is called a
_closure operator_ if it fulfills the following properties for all $x,y\in S$:

  1. (1)

$x\leq c(x)$ (extensitivity)

  2. (2)

$x\leq y\Rightarrow c(x)\leq c(y)$ (isotony)

  3. (3)

$c(c(x))=c(x)$ (idempotence)

A useful easy consequence of this definition is the following corollary:

######  Corollary 1.

Let $c$ be a closure function and $x,y\in S$ elements such that $y\geq c(x)$
($y=c(x)$) holds. Then $x\leq y$ holds.

######  Proof 3.1.

This follows simply from $x\leq c(x)$ and transitivity of $\leq$.

The next definition is a characterization of closures as subsets of ordered
sets:

Given an ordered set $(S,\leq)$ a subset $C\subseteq S$ is called a _closure
system_ if for every $s\in S$ the set ${\sf maj}(s,C)$ has a least element.

The set of all closure systems of an ordered set $(S,\leq)$ is denoted by
$\mathcal{C}(S)$ (here we assume that the order on $S$ is clear from context).

######  Remark 2.

In the literature, e.g. [Grä11] one finds a more complicated version of
Definition 3 which imposes also the requirement that a closure system is
closed under binary infima. However, a reviewer of [Glü21] pointed out that
this requirement is redundant. This observation lead in the consequence to the
generalization of [Glü21] from lattices to the present form handling general
ordered sets. This is a rare case where generalization leads also to
simplification due to the more concise formulation of Definition 3.

It turns out that closure functions generate closure systems:

######  Lemma 3.

For every closure function $c$ the set ${\sf fix}(c)$ of fixpoints of $c$ is a
closure system.

######  Proof 3.2.

Let $s\in S$ be an arbitrary element. Clearly, $c(s)\in{\sf fix}(c)$ holds,
and due to extensitivity of $c$ we have $c(s)\in{\sf maj}(s,{\sf fix}(c))$.
Let us now pick an arbitrary $f\in{\sf fix}(c)$ with the property $s\leq f$.
Now isotony of $c$ and $f\in{\sf fix}(c)$ imply $c(s)\leq f$ which completes
the proof.

Also, closure systems determine closure functions in a unique way:

######  Lemma 4.

Let $C$ be a closure system. Then there exists exactly one closure function
$c$ with ${\sf fix}(c)=C$.

######  Proof 3.3.

We define the function $c$ by $c(s)=_{def}{\sf lst}({\sf maj}(s,C))$ (note
that this is well-defined due to the properties of a closure system according
to Definition 3). Let us first check that $c$ is indeed a closure function:

  * $\bullet$

Extensivity: this is obvious since every element is mapped to a majorizing
one.

  * $\bullet$

Isotony: under the assumption $s\leq t$ we have ${\sf maj}(s,C)\supseteq{\sf
maj}(t,C)$ and hence $c(s)={\sf lst}({\sf maj}(s,C))\leq{\sf lst}({\sf
maj}(t,C))=c(t)$.

  * $\bullet$

Idempotence: by already shown extensivity we have $s\leq c(s)$ and hence ${\sf
maj}(s,C)\supseteq{\sf maj}(c(s),C)$. Let us now pick an arbitrary
$s^{\prime}\in{\sf maj}(s,C)$. Because $c(s)$ is the least element of ${\sf
maj}(s,C)$ we have $c(s)\leq s^{\prime}$, hence $s^{\prime}\in{\sf
maj}(c(s),C)$, implying ${\sf maj}(s,C)={\sf maj}(c(s),C)$. Now $c(s)=c(c(s))$
follows from this set equality and definition of $c$.

Let us now assume that there is another closure function $c^{\prime}$ with
${\sf fix}(c^{\prime})=C$, and pick an arbitrary $s\in S$. Because
$c^{\prime}$ is idempotent, we have $c^{\prime}(s)\in C$ and hence
$c(c^{\prime}(s))=c(s)$ from where we conclude that $c^{\prime}(s)\leq c(s)$
holds (this is due to Corollary 1). Symmetrically, we obtain $c(s)\leq
c^{\prime}(s)$ and hence $c(s)=c^{\prime}(s)$ which shows uniqueness of $c$.

Lemmata 3 and 4 establish a cryptomorphic one-to-one correspondence between
closure functions and closure systems on an ordered set. Since the main
contribution of this work deals with counting of closures (both functions and
systems), it is sufficient to use the more convenient characterization. In
this case, closure systems are much easier to handle than closure functions.

##  4\. Isolated Suborders

The main tool for structuring ordered sets we will use is the subject of the
following definition:

Let $(S,\leq)$ be an ordered set. A subset $S^{\prime}\subseteq S$ is called
an _isolated suborder_ if it fulfills the following properties:

  1. (1)

$S^{\prime}$ has a greatest element $\top_{S^{\prime}}$ and least element
$\bot_{S^{\prime}}$.

  2. (2)

$\forall x\notin S^{\prime}\forall y^{\prime}\in S^{\prime}:y^{\prime}\leq
x\Rightarrow\top_{S^{\prime}}\leq x$

  3. (3)

$\forall x\notin S^{\prime}\forall y^{\prime}\in S^{\prime}:x\leq
y^{\prime}\Rightarrow x\leq\bot_{S^{\prime}}$

Intuitively, an isolated suborder $S^{\prime}$ can be “entered from below”
only via $\bot_{S^{\prime}}$ and “left upwards” only via $\top_{S^{\prime}}$.
We call an isolated suborder _nontrivial_ if $S^{\prime}$ does not equal $S$.
A _summit isolated suborder_ is a suborder $S^{\prime}$ such that
$\top_{S^{\prime}}\in\max{(S)}$ holds. If $|S^{\prime}|>1$ holds we call an
isolated suborder _nonsingleton_ , and a _useful_ isolated suborder is a
nontrivial non-singleton isolated suborder.

Another property we will need to make our ideas work is that an order does not
“branch upwards” at an element under consideration (in our case at its top
element):

Given an ordered set $(S,\leq)$ we call an element $b\in S$ a _bottleneck_ of
an element $x\in S$ if the following conditions are fulfilled:

  1. (1)

$b>x$,

  2. (2)

$[x,b]$ is a chain, and

  3. (3)

$y>x\Rightarrow(y\in[x,b]\vee y>b)$ holds for all $y\in S$.

Consequently, an _isolated suborder with bottleneck_ is an isolated suborder
$S^{\prime}$ such that $\top_{S^{\prime}}$ has a bottleneck. Obviously, given
an element $x$ with a bottleneck $b$, every element in $]x,b]$ is also a
bottleneck of $x$.

Figure 1 illustrates these definitions. At the left, an isolated suborder with
bottleneck is shown. In the middle, we find an isolated suborder without
bottleneck, and at the right, a summit isolated suborder is given. Note that
neither the overall order nor the isolated suborder with bottleneck are
lattices (in contrast, the other two isolated suborders are indeed lattices).

Figure 1. Various Kinds of Isolated Suborders

We will use isolated suborders to derive quotients of an order. To this end,
we define for an isolated suborder $S^{\prime}\subseteq S$ an equivalence
relation $\sim_{S^{\prime}}$ by $x\sim_{S^{\prime}}y\Leftrightarrow_{def}(x\in
S^{\prime}\,\Leftrightarrow\,y\in S^{\prime})$. Clearly, for an element
$x\notin S^{\prime}$, the equivalence class $[x]_{\sim_{S^{\prime}}}$ is the
singleton set $\\{x\\}$, and for all elements $x\in S^{\prime}$ the
equivalence class $[x]_{\sim_{S^{\prime}}}$ coincides with $S^{\prime}$. A
crucial point is that $\sim_{S^{\prime}}$ is even order generating:

######  Lemma 5.

Let $S^{\prime}$ be an isolated suborder of an ordered set $(S,\leq)$. Then
$\sim_{S^{\prime}}$ is order generating.

######  Proof 4.1.

It is easy to see that $\leq/\sim_{S^{\prime}}$ (we use this notation since we
do not know yet whether $\sim_{S^{\prime}}$ is order generating) is both
reflexive and transitive so it remains to show that it is also antisymmetric.
To this end, we pick two arbitrary
$[s]_{\sim_{S^{\prime}}},[t]_{\sim_{S^{\prime}}}\in S/\sim_{S^{\prime}}$ such
that both
$[s]_{\sim_{S^{\prime}}}\leq/\sim_{S^{\prime}}[t]_{\sim_{S^{\prime}}}$ and
$[t]_{\sim_{S^{\prime}}}\leq/\sim_{S^{\prime}}[s]_{\sim_{S^{\prime}}}$ hold.
In the case $s,t\notin S^{\prime}$, we have $[s]_{\sim_{S^{\prime}}}=\\{s\\}$
and $[t]_{\sim_{S^{\prime}}}=\\{t\\}$, and hence both $s\leq t$ and $t\leq s$
by homomorphism properties. Now
$[s]_{\sim_{S^{\prime}}}=[t]_{\sim_{S^{\prime}}}$ is an easy consequence of
the antisymmetry of $\leq$. If $s,t\in S^{\prime}$ holds, then we have
$[s]_{\sim_{S^{\prime}}}=[t]_{\sim_{S^{\prime}}}$ by construction of
$\sim_{S^{\prime}}$. For the last case we assume w.l.o.g. that $s\in
S^{\prime}$ and $t\notin S^{\prime}$ hold. From
$[s]_{\sim_{S^{\prime}}}\leq/\sim_{S^{\prime}}[t]_{\sim_{S^{\prime}}}$ we
conclude that there is an $s_{1}\in S^{\prime}$ with $s_{1}\leq t$ (note that
$[t]_{\sim_{S^{\prime}}}$ is the singleton set $\\{t\\}$). By definition of an
isolated suborder, this implies $\top_{S^{\prime}}\leq t$, and symmetrically
we obtain $t\leq\bot_{S^{\prime}}$. This leads to the chain
$t\leq\bot_{S^{\prime}}\leq\top_{S^{\prime}}\leq t$, implying among other
things $t=\bot_{S^{\prime}}$ and hence $t\in S^{\prime}$, contradicting the
choice of $t$. This finishes the proof since it shows that the last case can
not occur.

This lemma justifies the writing $\leq_{\sim_{S^{\prime}}}$ which we will use
from now on.

An important property of isolated suborders is their convexity:

######  Lemma 6.

Let $S^{\prime}$ be an isolated suborder of an ordered set $(S,\leq)$. Then
$S^{\prime}$ is convex.

######  Proof 4.2.

Let $s,t\in S^{\prime}$ be arbitrary elements of $S^{\prime}$ with $s\leq t$,
and assume that there is an $u\notin S^{\prime}$ such that $s\leq u\leq t$
holds. By $\bot_{S^{\prime}}\leq s\leq u$, we have $\bot_{S^{\prime}}\leq u$.
On the other hand, from $u\leq t$ and $u\notin S^{\prime}$ we obtain
$u\leq\bot_{S^{\prime}}$ by definition of an isolated suborder; so altogether
we have $u=\bot_{S^{\prime}}$. However, this is a contradiction to the
assumption $u\notin S^{\prime}$.

In particular, this means that an isolated suborder $S^{\prime}$ is the same
as the interval $[\bot_{S^{\prime}},\top_{S^{\prime}}]$. However, not every
interval is an isolated suborder: consider as counterexample the interval
$[\emptyset,\\{1\\}]$ in the ordered set $(\mathcal{P}(\\{1,2\\}),\subseteq)$.
In this setting, we have $\emptyset\subseteq\\{2\\}$ but not
$\\{1\\}\subseteq\\{2\\}$, so the second part of Definition 4 is not
fulfilled.

The next lemma states intuitively spoken that isolated suborders with common
elements can not lie side by side:

######  Lemma 7.

Let $S_{1}$ and $S_{2}$ be two isolated suborders with $S_{1}\cap
S_{2}\neq\emptyset$. Then the set
$\\{\bot_{S_{1}},\bot_{S_{2}},\top_{S_{1}},\top_{S_{2}}\\}$ is a chain.

######  Proof 4.3.

Let us pick an arbitrary $s_{12}\in S_{1}\cap S_{2}$. In the case
$\top_{S_{1}}\in S_{2}$, the inequality $\top_{S_{1}}\leq\top_{S_{2}}$ is easy
to see. If $\top_{S_{1}}$ is not an element of $S_{2}$, then we can conclude
$\top_{S_{2}}\leq\top_{S_{1}}$ from $s_{12}\in S_{2}$,
$s_{12}\leq\top_{S_{1}}$ and the properties of an isolated suborder.
Symmetrically, we can show that $\bot_{S_{1}}$ and $\bot_{S_{2}}$ are
comparable. Now the rest is an easy consequence of
$\bot_{S_{1}},\bot_{S_{2}}\leq s_{12}\leq\top_{S_{1}},\top_{S_{2}}$.

Now we see that two isolated suborders with a common element can be merged
into one isolated suborder:

######  Lemma 8.

Let $S_{1}$ and $S_{2}$ be two isolated suborders with $S_{1}\cap
S_{2}\neq\emptyset$. Then $S_{12}=_{def}S_{1}\cup S_{2}$ is an isolated
suborder, too.

######  Proof 4.4.

Because $\\{\bot_{S_{1}},\bot_{S_{2}},\top_{S_{1}},\top_{S_{2}}\\}$ is a chain
due to Lemma 7, we can assume w.l.o.g. that $\bot_{S_{1}}\leq\bot_{S_{2}}$
holds. If $\top_{S_{2}}\leq\top_{S_{1}}$ holds, then we have
$[\bot_{S_{2}},\top_{S_{2}}]\subseteq[\bot_{S_{1}},\top_{S_{1}}]$, and we
obtain the claim immediately because isolated suborders are intervals. We do
not have to consider the case $\top_{S_{1}}<\bot_{S_{2}}$ because of
$S_{1}\cap S_{2}\neq\emptyset$, so we only have to look only at
$\bot_{S_{1}}\leq\bot_{S_{2}}\leq\top_{S_{1}}\leq\top_{S_{2}}$ as last case.

To show that $S_{12}$ is indeed an isolated suborder we pick arbitrary
$s_{12}\in S_{12}$ and $x\notin S_{12}$ such that $s_{12}\leq x$ holds. In the
case $s_{12}\in S_{2}$ we obtain $x\geq\top_{S_{2}}=\top_{S_{12}}$ because
$S_{2}$ is an isolated suborder, so let us now assume that $s_{12}\in S_{1}$
holds. Due to the properties of $S_{1}$, we have here $x\geq\top_{S_{1}}$.
Knowing this, we can deduce $x\geq\top_{S_{2}}$ from $\top_{S_{1}}\in S_{2}$
and $x\notin S_{2}$. The case $x\leq s_{12}$ can be treated by a symmetric
argumentation.

An easy observation is now that $S_{1}\cup S_{2}$ is an isolated suborder with
bottleneck provided that $S_{1}$ and $S_{2}$ are isolated suborders with
bottlenecks. Moreover, if $S_{1}$ and $S_{2}$ are nontrivial summit isolated
suborders with $\top_{S_{1}}=\top_{S_{2}}$ then $S_{1}\cup S_{2}$ is also a
nontrivial summit isolated suborder with greatest element $\top_{S_{1}}$ (or,
equivalently, greatest element $\top_{S_{2}}$). This shows the following
theorem together with Lemma 8:

######  Theorem 9.

Let $(S,\leq)$ be an ordered set.

  1. 1.

Two distinct inclusion-maximal isolated suborders with bottleneck of
$(S,\leq)$ are disjoint.

  2. 2.

For every $s\in\max{(S)}$, there is at most one nontrivial inclusion-maximal
summit isolated suborder with $s$ as greatest element.

The next lemma establishes a connection between isolated suborders in an
ordered set and a quotient of this order, induced by an isolated suborder.

######  Lemma 10.

Let $S^{\prime}$ be an isolated suborder of an ordered set $(S,\leq)$, and let
$S_{S^{\prime}}$ be an isolated suborder of $S/\sim_{S^{\prime}}$. Then
$S^{\prime\prime}=_{def}\bigcup S_{S^{\prime}}$ is an isolated suborder of
$S$.

######  Proof 4.5.

Clearly, $\bot_{S^{\prime\prime}}=\bot_{S^{\prime}}$ holds, provided
$\bot_{S_{S^{\prime}}}=S^{\prime}$, and also $\bot_{S^{\prime\prime}}=s$,
provided $\bot_{S_{S^{\prime}}}=\\{s\\}$. Analogous equalities hold also for
$\top_{S^{\prime\prime}}$ instead of $\bot_{S_{S^{\prime}}}$.

To show the remaining properties of Definition 4, we pick arbitrary $s\in
S^{\prime\prime}$ and $t\notin S^{\prime\prime}$ with $s\leq t$. The
construction of $S^{\prime\prime}$ yields both $[s]_{\sim_{S^{\prime}}}\in
S_{S^{\prime}}$ and $[t]_{\sim_{S^{\prime}}}\notin S_{S^{\prime}}$, and
homomorphism properties lead to
$[s]_{\sim_{S^{\prime}}}\leq_{\sim_{S^{\prime}}}[t]_{\sim_{S^{\prime}}}$.
Because $S_{S^{\prime}}$ is an isolated suborder, we can therefrom deduce that
$\top_{S_{S^{\prime}}}$ $\leq_{\sim_{S^{\prime}}}[t]_{\sim_{S^{\prime}}}$ has
to hold. We note that $[t]_{\sim_{S^{\prime}}}$ and $\top_{S_{S^{\prime}}}$
are disjoint and consider first the case that $\top_{S_{S^{\prime}}}$ is a
singleton set. In this case, the equality
$\top_{S_{S^{\prime}}}=\\{\top_{S^{\prime\prime}}\\}$ holds which implies
$\top_{S^{\prime\prime}}\leq t$. Otherwise, i.e., if $\top_{S_{S^{\prime}}}$
has more than one element, we have $\top_{S_{S^{\prime}}}=S^{\prime}$,
implying $\top_{S^{\prime\prime}}=\top_{S^{\prime}}$. Here too, we have
$\top_{S^{\prime\prime}}\leq t$ by homomorphism properties and due to
disjointness of $[t]_{\sim_{S^{\prime}}}$ and $\top_{S_{S^{\prime}}}$. A
symmetric argumentation applies to the case $s\geq t$, hence
$S^{\prime\prime}$ is an isolated suborder according to Definition 4.

Next we extend this claim to isolated suborders with bottleneck:

######  Lemma 11.

Let $S^{\prime}$ be an isolated suborder of an ordered set $(S,\leq)$, and let
$S_{S^{\prime}}$ be an isolated suborder with bottleneck of
$S/\sim_{S^{\prime}}$. Then $S^{\prime\prime}=_{def}\bigcup S_{S^{\prime}}$ is
an isolated suborder with bottleneck of $S$.

######  Proof 4.6.

$S^{\prime\prime}$ is an isolated suborder by Lemma 10, and by assumption we
can choose an arbitrary bottleneck $B\in S/\sim_{S^{\prime}}$ of
$S_{S^{\prime}}$. Now we have the following three possibilities:

  * 1.

$\top_{S_{S^{\prime}}}=S^{\prime}$: In this case, we have
$\top_{S^{\prime\prime}}=\top_{S^{\prime}}$ and $B=\\{b\\}$ for some $b\in S$.
Hence $b$ is a bottleneck according to Definition 4 by homomorphism properties
because all elements of the (nonempty) interval $]S^{\prime},B]$ are singleton
sets.

  * 2.

$B=S^{\prime}$: Here $\top_{S_{S^{\prime}}}=\\{\top_{S^{\prime\prime}}\\}$
holds, and our goal is to show that $\bot_{S^{\prime}}$ is a bottleneck of
$S^{\prime\prime}$. By assumption,
$[\\{\top_{S^{\prime\prime}}\\},S^{\prime}]$ is a chain in
$S/\sim_{S^{\prime}}$, hence $[\top_{S^{\prime\prime}},\bot_{S^{\prime}}]$ is
a chain in $S$ due to the fact that $S/\sim_{S^{\prime}}$ consists only of
singleton sets except possibly $S^{\prime}$. Now it is easy to check the
remaining properties of Definition 4.

  * 3.

$\top_{S_{S^{\prime}}}\neq S^{\prime}\wedge B\neq S^{\prime}$: Here, we first
investigate the case $S^{\prime}\in[\top_{S_{S^{\prime}}},B]$. Under this
condition, $B$ is also a bottleneck of $S_{S^{\prime}}$, and the argumentation
can be carried out analogously to the previous case. If
$S^{\prime}\notin[\top_{S_{S^{\prime}}},B]$ holds, $S/\sim_{S^{\prime}}$
consists of singleton sets only, and the properties of Definition 4 follow
easily from homomorphism properties.

An analogous lemma holds also for summit isolated suborders:

######  Lemma 12.

Let $S^{\prime}$ be an isolated suborder of an ordered set $(S,\leq)$, and let
$S_{S^{\prime}}$ be a summit isolated suborder of $S/\sim_{S^{\prime}}$. Then
$S^{\prime\prime}=_{def}\bigcup S_{S^{\prime}}$ is a summit isolated suborder
of $S$.

######  Proof 4.7.

By Lemma 10, we know that $S^{\prime\prime}$ is an isolated suborder. If
$\top_{S_{S^{\prime}}}=\\{s\\}$ holds for some $s\in S$, then $s$ is a maximal
element in $(S,\leq)$ by homomorphism properties. Moreover, also by
homomorphism properties, $s$ is the greatest element of $S^{\prime\prime}$ so
$S^{\prime\prime}$ is a summit isolated suborder in this case. Let us now
assume that $\top_{S_{S^{\prime}}}=S^{\prime}$ holds. In this case,
$S^{\prime}$ is a maximal element of
$(S/\sim_{S^{\prime}},\leq_{\sim_{S^{\prime}}})$, hence $\top_{S^{\prime}}$ is
a maximal element of $(S,\leq)$. By construction and homomorphism properties,
$\top_{S^{\prime}}$ is the greatest element of $S^{\prime\prime}$.

In our algorithm we may make use of consecutive quotients induced by various
isolated suborders. A (possibly infinite) sequence $S_{0},S_{1},S_{2},\ldots$
of ordered sets is called a _quotient sequence_ if for all $i$ the ordered set
$S_{i+1}$ can be written as the quotient $S_{i+1}=S_{i}/\sim_{S^{\prime}_{i}}$
for some isolated suborder $S^{\prime}_{i}$ of $S_{i}$. Consecutive quotient
formation leads to ordered sets whose carrier sets have an increasing depth of
set nesting. To be type correct, we introduce the notation
$\bigcup^{n}\mathbf{C}$ inductively by
$\bigcup^{0}\mathbf{C}=_{def}\mathbf{C}$ and
$\bigcup^{n+1}\mathbf{C}=_{def}\bigcup(\bigcup^{n}\mathbf{C})$. Intuitively
spoken, this operation removes $n$ set brackets from the elements of
$\mathbf{C}$ and joins them all.

In a quotient sequence, an inclusion-maximal summit isolated suborder
containing a fixed maximal element can appear as most once as a factor (if we
abstract from set parentheses):

######  Lemma 13.

Let $S_{0},S_{1},S_{2},\ldots$ be a quotient sequence, and assume that there
exists an index $i$ such that $S_{i+1}=S_{i}/\sim_{S^{\prime}_{i}}$ holds for
an inclusion-maximal useful summit isolated suborder $S^{\prime}_{i}$ with
greatest element $\top_{S^{\prime}_{i}}$. Then there is no $S_{j}$ with $j>i$
containing a useful summit isolated suborder $S^{\prime}_{j}$ with
$\top_{S^{\prime}_{i}}\in\bigcup^{j-i}S^{\prime}_{j}$.

######  Proof 4.8.

Assume that some $S_{j}$ with $j>i$ contains a useful summit isolated suborder
$S^{\prime}_{j}$. Then we could construct an inclusion-maximal summit isolated
suborder $S^{\prime\prime}_{i}\supsetneq S^{\prime}_{i}$ of $S_{i}$ from
$S^{\prime}_{j}$ backwards along the lines of Lemmata 10 and 12, contradicting
the inclusion-maximality of $S^{\prime}_{i}$.

In the next lemma, we show that if we ignore set brackets, an element can
appear in at most one inclusion-maximal isolated suborders in a quotient
sequence.

######  Lemma 14.

Let $S_{0},S_{1},S_{2},\ldots$ be a quotient sequence such that
$S_{i+1}=S_{i}/\sim_{S^{\prime}_{i}}$ holds for an inclusion-maximal useful
isolated suborder with bottleneck $S^{\prime}_{i}$ for all $i\geq 0$. Then
$S^{\prime}_{i}$ and $\bigcup^{j-i}S^{\prime}_{j}$ are disjoint for all $i,j$
with $j>i$.

######  Proof 4.9.

By the first part of Theorem 9 and Lemma 11, it is obvious that
$S^{\prime}_{i}$ and $\bigcup S^{\prime}_{i+1}$ are disjoint for all $i$. Now
the claim follows by straightforward induction.

##  5\. Isolated Suborders and Closure Systems

After investigating isolated suborders and their properties, we now turn our
attention to the interplay between isolated suborders and closure systems.
First we show how closure systems on an ordered set give rise to closure
systems of a quotient:

######  Lemma 15.

Let $(S,\leq)$ be an ordered set, $S^{\prime}$ an isolated suborder of
$(S,\leq)$, and consider a closure system $C$ of $(S,\leq)$.

  1. (1)

If $C\cap S^{\prime}=\emptyset$, then $C^{\\{\\}}$ is a closure system of
$S/\sim_{S^{\prime}}$.

  2. (2)

If $C\cap S^{\prime}\neq\emptyset$, then $(C\backslash
S^{\prime})^{\\{\\}}\cup\\{S^{\prime}\\}$ is a closure system of
$S/\sim_{S^{\prime}}$.

######  Proof 5.1.

Because $\sim_{S^{\prime}}$ is order generating, $S/\sim_{S^{\prime}}$ is a
homomorphic image of $(S,\leq)$. Deploying this fact, Definition 3 can now be
verified easily on $S/\sim_{S^{\prime}}$ for the two cases of the Lemma.

By the nature of things, homomorphisms work in general only in one direction,
so we expect to have a harder task to show how closure systems of a quotient
can induce closure systems of the original ordered set. First we introduce a
notion for “almost” closure systems:

Let $(S,\leq)$ be an ordered set with greatest element $\top$. A subset
$C\subseteq S$ is called a _preclosure system_ of $(S,\leq)$ if
$C\cup\\{\top\\}$ is a closure system of $(S,\leq)$. The set of all preclosure
systems of $(S,\leq)$ is denoted by $\mathcal{PC}(S)$.

Clearly, every closure system on an ordered set with greatest element is also
a preclosure system, and the empty set is a preclosure system on ordered sets
with a greatest element. An important observation for the algorithm we will
develop is that $|\mathcal{PC}(S)|=2\cdot|\mathcal{C}(S)|$ holds if
$\mathcal{C}(S)$ is finite and has a greatest element (note that this is a
precondition to make $\mathcal{PC}(S)$ well-defined). Another crucial fact in
the further course is that a nonempty preclosure system contains a least
element majorizing $\bot$ (if the order under consideration has a least
element at all):

######  Lemma 16.

Let $C$ be a nonempty preclosure system of an ordered set $(S,\leq)$ with
least element $\bot_{S}$ and greatest element $\top_{S}$. Then there is a
least element $c\in C$ majorizing $\bot_{S}$.

######  Proof 5.2.

In the case $\top_{S}\in C$, $C$ is even a closure system, and Definition 3
entails the claim obviously. Otherwise, we define the closure system
$C^{\prime}$ by $C^{\prime}=_{def}C\dot{\cup}\\{\top_{S}\\}$, and by
definition of a closure system there is a least $c^{\prime}\in C^{\prime}$
majorizing $\bot_{S}$. This element $c^{\prime}$ can not be $\top_{S}$ since
$C^{\prime}$ contains at least one element except $\top_{S}$ (recall the $C$
was supposed to be nonempty), so we conclude $c^{\prime}\in C$.

Now we can use preclosure systems to describe the intersection of an isolated
suborder and a closure system:

######  Lemma 17.

Let $C$ be a closure system on an ordered set $(S,\leq)$, and let $S^{\prime}$
be an isolated suborder of $S$ with greatest element $\top_{S^{\prime}}$ and
least element $\bot_{S^{\prime}}$. Then $C^{\prime}=_{def}C\cap S^{\prime}$ is
a preclosure system of $S^{\prime}$. Moreover, if $S^{\prime}$ is a summit
isolated suborder, then $C^{\prime}$ is a closure system of $S^{\prime}$.

######  Proof 5.3.

Let $S^{\prime}$ be an arbitrary isolated suborder and consider an arbitrary
$s^{\prime}\in S^{\prime}$. Because $C$ is a closure system, it contains a
least $c$ which majorizes $s^{\prime}$. If $c\in S^{\prime}$ holds, then $c$
is by construction also an element of $C^{\prime}$. In the other case $c\notin
S^{\prime}$ we have $\top_{S^{\prime}}\leq c$ by definition of an isolated
suborder. Now it is obvious that $\top_{S^{\prime}}$ is a smallest element of
$C^{\prime}$ majorizing $s^{\prime}$. This shows the first claim, so let us
now assume that $S^{\prime}$ is even a summit isolated suborder. Then
$\top_{S^{\prime}}\in\max{(S)}$ holds by definition, hence $C$ has to contain
also $\top_{S^{\prime}}$ wherefrom the second claim follows immediately.

The next lemma is in some sense a “reverse” of Lemma 15 in the case of
isolated suborders with bottleneck:

######  Lemma 18.

Let $(S,\leq)$ be an ordered set and $S^{\prime}$ an isolated suborder of $S$
such that $\top_{S^{\prime}}$ has a least bottleneck $b$. Assume that
$C_{S^{\prime}}$ is a preclosure system of $S^{\prime}$, and let $C^{\prime}$
be a closure system of $S/\sim_{S^{\prime}}$ with $S^{\prime}\in C^{\prime}$.
Then $C=_{def}\bigcup(C^{\prime}\backslash\\{S^{\prime}\\})\cup
C_{S^{\prime}}$ is a closure system of $(S,\leq)$.

######  Proof 5.4.

Let us pick an arbitrary $s\in S$ with the goal to show that there is a least
$c\in C$ with $s\leq c$ in order to fulfill Definition 3. To this end, we have
several cases to consider:

  * 1.

$s\notin S^{\prime}$: In this case, we have $[s]_{\sim_{S^{\prime}}}=\\{s\\}$,
and by assumption there is a least $c^{\prime}\in C^{\prime}$ with
$\\{s\\}\leq_{\sim_{S^{\prime}}}c^{\prime}$. Now we have the following
possibilities:

    * a)

$c^{\prime}\neq S^{\prime}$: then we have $c^{\prime}=\\{c^{\prime\prime}\\}$
for some $c^{\prime\prime}\in S$. By homomorphism properties,
$c^{\prime\prime}$ majorizes $s$ in $(S,\leq)$, so let us pick an arbitrary
$\hat{c}\in C$ with $s\leq\hat{c}$. If
$[\hat{c}]_{\sim_{S^{\prime}}}=\\{\hat{c}\\}$ holds we have
$c^{\prime}\leq_{\sim_{S^{\prime}}}\\{\hat{c}\\}$ since $C^{\prime}$ is a
closure system (note that by construction of $C$, $\\{\hat{c}\\}$ has to be an
element of $C^{\prime}$). Otherwise, we have
$[\hat{c}]_{\sim_{S^{\prime}}}=S^{\prime}$, and because $C^{\prime}$ is a
closure system, we have $c^{\prime}\leq_{\sim_{S^{\prime}}}S^{\prime}$. In
both cases we have $c^{\prime\prime}\leq\hat{c}$ by homomorphism properties.

    * b)

$c^{\prime}=S^{\prime}$: here we distinguish the following cases:

      * i)

$C_{S^{\prime}}\neq\emptyset$: by Lemma 16, there is a least
$c^{\prime\prime}\in C_{S^{\prime}}$ majorizing $\bot_{S^{\prime}}$. By
homomorphism properties and the assumption
$\\{s\\}\leq_{\sim_{S^{\prime}}}S^{\prime}$ we have $s\leq\bot_{S^{\prime}}$,
and by transitivity we get $s\leq c^{\prime\prime}$. Let us now consider an
arbitrary $\hat{c}\in C$ with $s\leq\hat{c}$. If $\hat{c}\in S^{\prime}$, then
we get $\hat{c}\in C_{S^{\prime}}$ by construction of $C$. Because
$c^{\prime\prime}$ is the least element of $C_{S^{\prime}}$, we obtain
$c^{\prime\prime}\leq\hat{c}$ immediately. In the case $\hat{c}\notin
S^{\prime}$ we have $\\{\hat{c}\\}\in C^{\prime}$ by construction of $C$, and
as above we get $\\{s\\}\leq_{\sim_{S^{\prime}}}\\{\hat{c}\\}$. Because
$C^{\prime}$ is a closure system, we obtain
$S^{\prime}\leq_{\sim_{S^{\prime}}}\\{\hat{c}\\}$ and hence
$c^{\prime\prime}\leq\hat{c}$.

      * ii)

$C_{S^{\prime}}=\emptyset$: because of $b\notin S^{\prime}$ we have
$[b]_{\sim_{S^{\prime}}}=\\{b\\}$, and because $C^{\prime}$ is a closure
system, there is a least $b^{\prime}\in C^{\prime}$ majorizing $\\{b\\}$.
Moreover, $b^{\prime}=\\{c^{\prime\prime}\\}$ has to hold for some
$c^{\prime\prime}\in S$ (note that we have
$S^{\prime}<_{\sim_{S^{\prime}}}\\{b\\}\leq_{\sim_{S^{\prime}}}b^{\prime}$),
and by homomorphism properties and transitivity we obtain $s\leq
c^{\prime\prime}$. As usual we pick an arbitrary $\hat{c}\in C$ with
$s\leq\hat{c}$ and observe that $[\hat{c}]_{\sim_{S^{\prime}}}=\\{\hat{c}\\}$
holds (note that we assume here $C_{S^{\prime}}=\emptyset$). From
$s\leq\hat{c}$ we derive $\\{s\\}\leq_{\sim_{S^{\prime}}}\\{\hat{c}\\}$ and
hence $S^{\prime}\leq_{\sim_{S^{\prime}}}\\{\hat{c}\\}$ (recall
$c^{\prime}=S^{\prime}$ and the properties of $c^{\prime}$). However, due to
$C_{S^{\prime}}=\emptyset$ and construction of $C$, we obtain $\hat{c}\notin
S^{\prime}$, and by order theory and homomorphism this leads to
$\\{b\\}\leq_{\sim_{S^{\prime}}}\\{\hat{c}\\}$ from where we conclude that
$b^{\prime}\leq_{\sim_{S^{\prime}}}\\{\hat{c}\\}$ and eventually
$c^{\prime\prime}\leq\hat{c}$ hold.

  * 2.

$s\in S^{\prime}$: clearly, $S^{\prime}$ is the least element of $C^{\prime}$
majorizing $[s]_{\sim_{S^{\prime}}}$ since
$[s]_{\sim_{S^{\prime}}}=S^{\prime}$ and $S^{\prime}\in C^{\prime}$ hold. We
have two cases:

    * a)

$C_{S^{\prime}}$ contains an element $s^{\prime}$ majorizing $s$: then
$C_{S^{\prime}}$ contains also a minimal element $c^{\prime\prime}$ majorizing
$s$, and let $\hat{c}$ be an arbitrary element of $C$ such that $s\leq\hat{c}$
holds. In the case $\hat{c}\in C_{S^{\prime}}$ we get
$c^{\prime\prime}\leq\hat{c}$ immediately by the choice of $c^{\prime\prime}$,
so let us assume that $\hat{c}\notin S^{\prime}$ holds. However, here we have
$\top_{S^{\prime}}\leq\hat{c}$ by properties of an isolated suborder, implying
$c^{\prime\prime}\leq\hat{c}$.

    * b)

$C_{S^{\prime}}$ contains no element majorizing $s$: as above, there is a
least $b^{\prime}=\\{c^{\prime\prime}\\}\in C^{\prime}$ majorizing $\\{b\\}$.
Clearly, $c^{\prime\prime}$ majorizes $s$ in $(S,\leq)$ so we pick an
arbitrary $\hat{c}\in C$ with $s\leq\hat{c}$. By properties of an isolated
suborder we have $\top_{S^{\prime}}\leq\hat{c}$, and because $C_{S^{\prime}}$
does not contain $\top_{S^{\prime}}$ (otherwise $\top_{S^{\prime}}$ would be
an element of $C_{S^{\prime}}$ majorizing $s$), we can deduce even
$b\leq\hat{c}$. Now it is clear that $c^{\prime\prime}\leq\hat{c}$ holds due
to $\\{b\\}\leq_{\sim_{S^{\prime}}}\\{\hat{c}\\}$ and closure properties of
$C^{\prime}$.

In all cases, we constructed in the form of $c^{\prime\prime}$ a least element
of $C$ majorizing $s$.

######  Remark 19.

It is necessary for the correctness of Lemma 18 to require that
$\top_{S^{\prime}}$ has a bottleneck. This can be seen in Figure 2. At the
left, a preclosure system, indicated by encircled elements, on an isolated
suborder without bottleneck of its top element, indicated by an ellipse, is
shown. In the middle of the figure, we see a closure system on the associated
quotient order, indicated by circles. However, executing the construction from
Lemma 18 leads to the set of encircled elements in the right picture which
does not contain a least element majorizing the middle element (the only
unencircled element), and hence is no closure system. This shows one effect of
a bottleneck: it releases the top element of an isolated suborder from the
responsibility of being the least element being majorized by two elements
above it. Moreover, it it necessary to require that $\top_{S^{\prime}}$ has
even a least bottleneck: consider the ordered set $S=([0,1],\leq)$ (where
$\leq$ denotes the usual order on the reals) and the isolated suborder
$S^{\prime}=(\\{0\\},\leq)$. We choose the empty set as preclosure
$C_{S^{\prime}}$ of $S^{\prime}$ and $[0,1]^{\\{\\}}$ as closure system
$C^{\prime}$. Then the construction from above yields for $C$ the set $]0,1]$
which is no closure system since it contains no least element majorizing $0$.

Figure 2. A preclosure system on an isolated suborder (left), a closure system
on a quotient (middle) and no closure system on the original order (right)

The next lemma is a variant of the previous lemma for summit isolated
suborders:

######  Lemma 20.

Let $(S,\leq)$ be an ordered set, and let $S^{\prime}$ be a summit isolated
suborder of $(S,\leq)$. Assume that $C_{S^{\prime}}$ is a closure system of
$S^{\prime}$, and let $C^{\prime}$ be a closure system of
$S/\sim_{S^{\prime}}$. Then
$C=_{def}\bigcup(C^{\prime}\backslash\\{S^{\prime}\\})\cup C_{S^{\prime}}$ is
a closure system of $(S,\leq)$.

######  Proof 5.5.

As in the proof of Lemma 18, we pick an arbitrary $s\in S$ and show the
existence of a least element of $C$ majorizing $s$. We distinguish the
following cases:

  * 1.

$s\notin S^{\prime}$: analogously to Lemma 18 we have
$[s]_{\sim_{S^{\prime}}}=\\{s\\}$, and by assumption there is a least
$c^{\prime}\in C^{\prime}$ with $\\{s\\}\leq_{\sim_{S^{\prime}}}c^{\prime}$.
Now we have the following possibilities:

    * a)

$c^{\prime}\neq S^{\prime}$: this case can be handled exactly like the same
case in the proof of Lemma 18.

    * b)

$c^{\prime}=S^{\prime}$: here we have the following cases:

      * i)

$C_{S^{\prime}}\neq\emptyset$: also this case can be handled along the lines
of Lemma 18 (note that $C_{S^{\prime}}$ as closure system is also a preclosure
system).

      * ii)

$C_{S^{\prime}}=\emptyset$: in this case we can not resort to the proof of
Lemma 18 because the argument there uses properties of a smallest bottleneck.
However, $C_{S^{\prime}}$ can not be empty because it has to contain the
greatest element of $S^{\prime}$.

  * 2.

$s\in S^{\prime}$: by properties of a closure system, $C_{S^{\prime}}$
contains a least element $c^{\prime}$ majorizing $s$. However, By construction
of $C$ and because $S^{\prime}$ is a summit isolated suborder, all elements of
$C\backslash C_{S^{\prime}}$ majorizing $s$ are contained in $C_{S^{\prime}}$

In all cases, we deduced the existence of a least element of $C$ majorizing
$s$.

Finally, we consider the case that an isolated suborder with bottleneck does
not appear in a closure system of the quotient:

######  Lemma 21.

Let $(S,\leq)$ be an ordered set, and let $S^{\prime}$ be an isolated suborder
with bottleneck of $(S,\leq)$. Assume that $C^{\prime}$ is a closure system on
$S/\sim_{S^{\prime}}$ such that $S^{\prime}\notin C^{\prime}$. Then
$C=_{def}\bigcup C^{\prime}$ is a closure system on $S$.

######  Proof 5.6.

Routinely, we pick an arbitrary $s\in S$ with the obligation to show the
existence of a least element of $C$ majorizing $s$. Then the case $s\notin
S^{\prime}$ is analogous to case 1.a) of the proof of Lemma 18 (note that
$S^{\prime}\notin C^{\prime}$ was assumed). Similarly, the case $s\in
S^{\prime}$ can be handled along the lines of case 2.b) of the proof of Lemma
18.

Now we are ready to state our main results about the relationships between
closure systems on ordered sets and quotients thereof in the following two
theorems:

######  Theorem 22.

Let $S^{\prime}$ be an isolated suborder with bottleneck of an ordered set
$(S,\leq)$, and consider a subset $C\subseteq S$.

  1. (1)

Assume that $C^{\prime}=_{def}C\cap S^{\prime}\neq\emptyset$ holds. Then $C$
is a closure system of $S$ iff $C^{\prime}$ is a nonempty preclosure system of
$S^{\prime}$ and $(C\backslash S^{\prime})^{\\{\\}}\cup\\{S^{\prime}\\}$ is a
closure system of $S/\sim_{S^{\prime}}$.

  2. (2)

Assume that $C\cap S^{\prime}=\emptyset$ holds. Then $C$ is a closure system
of $S$ iff $C^{\\{\\}}$ is a closure system of $S/\sim_{S^{\prime}}$.

######  Proof 5.7.

This follows now easily from Lemmata 15, 17, 18 and 21

######  Theorem 23.

Let $S^{\prime}$ be a summit isolated suborder of an ordered set $(S,\leq)$,
and consider a subset $C\subseteq S$. Then $C$ is a closure system of $S$ iff
$C\cap S^{\prime}$ is a closure system of $S^{\prime}$ and $(C\backslash
S^{\prime})^{\\{\\}}\cup\\{S^{\prime}\\}$ is a closure system of
$S/\sim_{S^{\prime}}$.

######  Proof 5.8.

This follows simply from Lemmata 15, 17 and 20.

##  6\. Computing Isolated Suborders

The previous results concerned isolated suborders and their relation to
closure systems. In this section, we will become more concrete and deal with
the computation of isolated suborders. As representation for an ordered set,
we assume that an ordered set is given by its Hasse diagram as a directed
graph $G=(S,E)$ where the edges point “upwards”, i.e., $(s,t)\in E$ implies
$s<t$. Given a path $p=s_{1}s_{2}\ldots s_{n}$, we write $s\in p$ if $s=s_{i}$
holds for some $i\in[1,n]$ and say that $p$ _contains_ $s$. We call a node $u$
an $(s,t)$_-separator_ if every path from $s$ to $t$ contains $u$. Routinely,
we add an element $\bot$ to $S$ and consider the graph
$G_{\bot}=_{def}(S_{\bot},E_{\bot})$ with $S_{\bot}=S\dot{\cup}\\{\bot\\}$ and
$E_{\bot}=E\dot{\cup}\\{(\bot,m)\,|\,m\in\min{(S)}\\}$. Intuitively, this adds
a least element to the ordered set. Additionally, we may add yet another
element $\top$ to $S_{\bot}$ to obtain the set
$S_{\bot,\top}=_{def}S_{\bot}\dot{\cup}\\{\top\\}$ and define the graph
$G_{\bot,\top}=(S_{\bot,\top},E_{\bot,\top})$ by
$E_{\bot,\top}=_{def}E_{\bot}\dot{\cup}\\{(m,\top)\,|\,m\in\max{(S)}\\}$.
Analogously to the construction of $G_{\bot}$, this adds a greatest element to
the ordered set under consideration. All algorithms considered in this section
have polynomial running time so these constructions do not affect their
asymptotic complexity.

###  6.1. Isolated Suborders and Separators

In the sequel, we will establish a connection between isolated suborders and
separators in finite graphs. In the following two lemmata which form the basis
for Theorem 26, finiteness is a crucial point in order to argue about finite
paths.

######  Lemma 24.

Let $(S,\leq)$ be a finite ordered set with Hasse diagram $G=(S,E)$, and let
$[s_{1},s_{2}]$ be an isolated suborder. Then $s_{1}$ is a
$(\bot,s_{2})$-separator in $G_{\bot,\top}$, and $s_{2}$ is an
$(s_{1},\top)$-separator in $G_{\bot,\top}$.

######  Proof 6.1.

We first show the claim that $s_{1}$ is a $(\bot,s_{2})$-separator. To this
end, let $p=p_{1}p_{2}\ldots p_{n}$ with $p_{1}=\bot$ and $p_{n}=s_{2}$ be a
path in $G_{\bot,\top}$ from $\bot$ to $s_{2}$. Then there is an index
$i\in[1,n-1]$ with $p_{i}\notin[s_{1},s_{2}]$ and $p_{i+1}\in[s_{1},s_{2}]$,
and we claim that $p_{i+1}=s_{1}$ holds. Let us therefore assume that
$p_{i+1}\neq s_{1}$ holds.

First we rule out the case $i=1$: if $p_{2}\in[s_{1},s_{2}]$ and $p_{2}\neq
s_{1}$ hold, then we have $s_{1}<p_{2}$. However, this contradicts minimality
of $p_{2}$ in $(S,\leq)$ which follows from the construction of
$G_{\bot,\top}$. The crucial point is now that all elements of $p$ under
consideration are vertices of $G$ (or, equivalently, elements of $S$).

Now we have $s_{1}<p_{i+1}$ due to $p_{i+1}\in[s_{1},s_{2}]$ and $p_{i+1}\neq
s_{1}$. Furthermore, we have $p_{i}<p_{i+1}$ by construction of $p$, and now
$p_{i}\notin[s_{1},s_{2}]$, $p_{i+1}\in[s_{1},s_{2}]$, and the properties of
an isolated suborder imply $p_{i}<s_{1}$. Alltogether, this means
$p_{i}<s_{1}<p_{i+1}$, contradicting the fact that $(p_{i},p_{i+1})$ is an
edge of a Hasse diagram.

######  Lemma 25.

Let $(S,\leq)$ be a finite ordered set with Hasse diagram $G=(S,E)$, and let
$[s_{1},s_{2}]$ be a nonempty interval. Assume that both $s_{1}$ is a
$(\bot,s_{2})$-separator in $G_{\bot,\top}$ and $s_{2}$ is an
$(s_{1},\top)$-separator in $G_{\bot,\top}$. Then $[s_{1},s_{2}]$ is an
isolated suborder.

######  Proof 6.2.

We only show that for all $s^{\prime}\notin[s_{1},s_{2}]$ and
$s^{\prime\prime}\in[s_{1},s_{2}]$ with $s^{\prime}\leq s^{\prime\prime}$
(note that this can be strengthened $s^{\prime}<s^{\prime\prime}$) the
inequality $s^{\prime}\leq s_{1}$ holds. By construction, there is a path
$p^{\prime}=p_{1}^{\prime}p_{2}^{\prime}\ldots p_{n^{\prime}}^{\prime}$ in
$G_{\bot,\top}$ with $p_{1}^{\prime}=\bot$ and
$p_{n^{\prime}}^{\prime}=s^{\prime}$. Note that $s_{1}$ can not be an element
of $p^{\prime}$: assume there is an index $i^{\prime}$ with
$p_{i}^{\prime}=s_{1}$. By construction, $i^{\prime}<n^{\prime}$ has to hold
which implies $s_{1}\leq s^{\prime}$. Together with $s^{\prime}\leq
s^{\prime\prime}$ and $s^{\prime\prime}\in[s_{1},s_{2}]$, this implies
$s^{\prime}\in[s_{1},s_{2}]$, contradicting the choice of $s^{\prime}$.

Next, there is a path
$p^{\prime\prime}=p_{1}^{\prime\prime}p_{2}^{\prime\prime}\ldots
p_{n^{\prime\prime}}^{\prime\prime}$ in $G_{\bot,\top}$ with
$p_{1}^{\prime\prime}=s^{\prime}$ and
$p_{n^{\prime\prime}}^{\prime\prime}=s^{\prime\prime}$ (this is due to the
fact $s^{\prime}<s^{\prime\prime}$). Finally, because of
$s^{\prime\prime}\in[s_{1},s_{2}]$, there is a path
$\hat{p}=\hat{p}_{1}\hat{p}_{2}\ldots\hat{p}_{\hat{n}}$ in $G_{\bot,\top}$
with $\hat{p}_{1}=s^{\prime\prime}$ and $\hat{p}_{\hat{n}}=s_{2}$. The
concatenation of these three paths yields a path $p=p_{1}p_{2}\ldots p_{n}$
which has to contain $s_{1}$ because $s_{1}$ is a $(\bot,s_{2})$-separator.
However, the discussion about $p^{\prime}$ shows that $s^{\prime}$ appears in
$p$ before $s_{1}$, hence we have $s^{\prime}\leq s_{1}$.

Clearly, $[s_{1},s_{2}]$ has a least and a greatest element, and the remaining
property of Definition 4 can be shown symmetrically to above.

From the previous two lemmata, the next theorem follows immediately:

######  Theorem 26.

Let $(S,\leq)$ be a finite ordered set with Hasse diagram $G=(S,E)$. Then, an
interval $[s_{1},s_{2}]$ is an isolated suborder iff $[s_{1},s_{2}]$ is
nonempty, $s_{1}$ is a $(\bot,s_{2})$-separator in $G_{\bot,\top}$, and
$s_{2}$ is an $(s_{1},\top)$-separator in $G_{\bot,\top}$.

###  6.2. Computing Isolated Suborders

The result from Theorem 26 can be used to determine all useful isolated
sublattices with bottleneck in polynomial time. To this end, we note that it
is possible to decide in $\mathcal{O}(|V|+|E|)$ time whether a node $s$ is a
$(v_{1},v_{2})$-separator in a graph $G=(V,E)$: we simply remove $s$ and its
adjacent edges from $G$ and test whether in the resulting graph $v_{2}$ is
reachable from $v_{1}$. Algorithm 1 shows now how to compute useful isolated
suborders with bottleneck.

Algorithm 1 Computing Maximal Useful Isolated Suborders with Bottleneck

1:function Useful Maximal Isolated Suborders with Bottleneck(Hasse diagram
$G=(V,E)$)

2: $G_{t}\leftarrow$ transitive hull of $G$

3:  _bottlenecks_ $\leftarrow$ topologically ordered list of all nodes of $G$
with outdegree 1

4:  _candidates_ $\leftarrow$ empty list of type $V\times V$

5:  _maximalIsos_ $\leftarrow$ empty list of type $V\times V$

6: for all $v\in V$ do

7: for all $b\in$ _bottlenecks_ with $v\neq b$ do

8: if $(v,b)$ is an edge in $G_{t}$ then

9: if $v$ is a $(\bot,b)$-separator in $G_{\bot,\top}$ and $b$ is a
$(v,\top)$-separator in $G_{\bot,\top}$ then

10: append $(v,b)$ to _candidates_

11: end if

12: end if

13: end for

14: end for

15: for all $v\in V$ do

16: append the last occurence of the form $(v,b)$ in _candidates_ to
_maximalIsos_

17: end for

18: return _maximalIsos_

19:end function

First, we compute the order associated with $G$ which can be done in
$\mathcal{O}(|V^{3}|)$ time using the Floyd-Warshall algorithm. An algorithm
running in $\mathcal{O}(|V|^{2.371552})$ given in [AW21], however, this
algorithm is not useable in practice. Next, we collect all possible top
elements of an isolated suborder with bottleneck in the list _bottlenecks_ in
topological order. Using standard methods, this can be carried out in
$\mathcal{O}(|V|+|E|)$ time. Subsequently, we initialize two lists of type
$V\times V$ to collect intermediate results and for the final return result.

The centerpiece of the algorithm are lines 6 to 14: here we loop over all
tuples $(v,b)$ such that $[v,b]$ is an interval with at least two elements,
and test whether such an interval fulfills the conditions of Theorem 26. If
so, than the respective interval is added to the _candidates list_. There are
at most $\mathcal{O}(|V|^{2})$ tuples of the form $(v,b)$, and the computation
in lines 9 and 10 takes $\mathcal{O}(|V|+|E|)$ time, so lines 6 to 14 can be
carried out in $\mathcal{O}(|V|^{2}(|V|+|E|))$ time. We assume that in line 7
the elements of _bottlenecks_ are processed in their topological order so line
16 ensures that only inclusion-maximal suborders are added to the returned
_maximalIsos_ list. Here, the loop from line 15 to line 17 is executed $|V|$
times, and since the _candidates_ list can contain $\mathcal{O}(|V|^{2})$
elements, the running time of this loop is bounded by $\mathcal{O}(|V|^{3})$.
Alltogether, the dominating is given by lines 6 to 14, so the overall running
time is in $\mathcal{O}(|V|^{2}(|V|+|E|))$.

This algorithm is rather simple and can be optimized in many ways. For
example, once we find an isolated suborder $[v,b]$ with bottleneck in lines 9
and 10, we have to look in line 7 only at elements $b^{\prime}$ with
$b<b^{\prime}$ and can skip elemets $v^{\prime}$ with $v<v^{\prime}$ in line 6
due to Lemma 7. Moreover, ideas from [CCMP20] or [ILS12] can be used for the
computation of separators and to replace the rather primitive computation in
line 9. Note also that this algorithm returns all useful maximal isolated
suborders with bottleneck and hence has a priori a running time in
$\Omega(|V|^{2})$. The restriction to finding only a one arbitrary useful
isolated suborder with bottleneck could also lead to a better running time.

Note that this algorithm can easily be modified for the computation of useful
isolated summit suborders: instead of _bottlenecks_ , we simply use a list
_maxElements_ containing all maximal elements of $G$. Clearly, this list can
be computed in $\mathcal{O}(|V|)$ time because we put simply all nodes with
outdegree 0 into it. A topological ordering is not necessary; however, the
running time is again dominated by lines 6 to 14 and is amounts hence to
$\mathcal{O}(|V|^{2}(|V|+|E|))$.

##  7\. Counting Closure Operators

In this section we will apply our previous results to counting closure
systems. First, we consider come special cases in Subsection 7.1 and give
afterward a recursive algorithm based on isolated suborders in Subsection 7.2.

###  7.1. Special Cases

General orders may consist of several distinct connected components; however,
we will see that for counting purposes it suffices to concentrate on orders
consisting of one connected component. The following lemma shows a splitting
property for closure systems on ordered sets with two or more connected
components.

######  Lemma 27.

Let $(S_{1},\leq_{1})$ and $(S_{2},\leq_{2})$ be ordered sets with $S_{1}\cap
S_{2}=\emptyset$, and let $C_{1}\subseteq S_{1}$ and $C_{2}\subseteq S_{2}$ be
closures systems of $S_{1}$ and $S_{2}$, resp. Then $C_{1}\cup C_{2}$ is a
closure system of $(S_{12},\leq_{12})=_{def}(S_{1}\cup
S_{2},\leq_{1}\cup\leq_{2})$.

######  Proof 7.1.

Let $s\in S_{12}$ be arbitrary, and assume w.l.o.g. that $s\in S_{1}$ holds.
Then there is a least (in $C_{1}$) element $c\in C_{1}$ majorizing $s$ (wrt.
$\leq_{1}$). However, elements from $S_{1}$ and $S_{2}$ (and hence from
$C_{1}$ and $C_{2}$) are incomparable wrt. $\leq_{12}$ by construction, so $c$
is also a least element (wrt. $\leq_{12}$) majorizing $s$ (wrt. $\leq_{12}$).

This observation entails the following corollary:

######  Corollary 28.

Let $(S,\leq)$ be an ordered set such that there is a partition of
$S=S_{1}\dot{\cup}S_{2}$ into disjoint nonempty finite subsets $S_{1}$ and
$S_{2}$ such that for all $s_{1}\in S_{1}$ and $s_{2}\in S_{2}$ the elements
$s_{1}$ and $s_{2}$ are incomparable. Then the equality
$|\mathcal{C}(S,\leq)|=|\mathcal{C}(S_{1},\leq|_{S_{1}})|\cdot|\mathcal{C}(S_{2},\leq|_{S_{2}})|$
holds.

Of course, the results of Lemma 27 and Corollary 28 can be extended to ordered
sets with more than two connected components by means of induction.

Next, we will derive closed formulae for the number of closure system on some
special kinds of ordered sets which may serve as termination case in the
algorithm from the following Subsection 7.2. However, we are not only
interested in the overall number of closure systems but also in the number of
closure systems containing a given subset of the ordered set under
consideration. To deal with this situation, we introduce the notations
$\mathcal{C}(S)_{T}=_{def}\\{C\in\mathcal{C}(S)\,|\,T\subseteq C\\}$,
$\mathcal{C}(S)^{-S}_{T}\,=_{\it df}\,\\{C\in\mathcal{C}(S)_{T}\,|\,S\cap
C=\emptyset\\}$, and $\mathcal{C}(S)^{S}_{T}\,=_{\it
df}\,\\{C\in\mathcal{C}(S)_{T}\,|\,S\cap C\neq\emptyset\\}$ for subsets
$T\subseteq S$ of an ordered set $(S,\leq)$. With this notation, we have the
trivial equalities $\mathcal{C}(S)=\mathcal{C}(S)_{\emptyset}$ (the empty set
imposes no constraints) and
$\mathcal{C}(S)_{T}=\mathcal{C}(S)_{T\backslash\\{m\\}}=\mathcal{C}(S)_{T\cup\\{m\\}}$
for each $m\in\max{(S)}$ (every closure system has to contain every maximal
element). Moreover, since $\mathcal{C}(S)_{T}$ is the disjoint union of
$\mathcal{C}(S)_{T\cup\\{s\\}}$ and $\mathcal{C}(S)^{-\\{s\\}}_{T}$, we have
the equality
$|\mathcal{C}(S)_{T}|=|\mathcal{C}(S)_{T\cup\\{s\\}}|+|\mathcal{C}(S)^{-\\{s\\}}_{T}|$.
In particular, this means that we do not need explicit formulae for
$\mathcal{C}(S)^{-\\{s\\}}_{T}$.

The first special case is that of a chain:

######  Lemma 29.

Let $(S,\leq)$ be a chain with $n$ elements and consider an arbitrary
$T\subseteq S$. Then we have
$|\mathcal{C}(S)_{T}|=2^{n-1-|T\backslash\\{\top_{S}\\}|}$.

######  Proof 7.2.

It is straightforward to see that for a finite chain $(S,\leq)$ a set
$C\subseteq S$ is a closure system according to Definition 3 iff it contains
$\top_{S}$. The claim follows now from the formula for the cardinality of
power sets.

Next, we consider orders with only one layer of elements between the bottom
and top element:

An ordered set $(S,\leq)$ is called a _diamond of width $n$_ if its carrier
set $S=\\{\bot_{S},\top_{S},b_{1},\dots,b_{n}\\}$ consists of $n+2$ pairwise
different elements and $b_{i}\not\lessgtr b_{j}$ holds for all $i\neq j$. The
elements $(b_{i})_{1\leq i\leq n}$ are called the _belt elements_ of
$(S,\leq)$.

######  Lemma 30.

Let $(S,\leq)$ be a diamond of width $n$ and let $B$ be the set of its belt
elements. Then the following holds:

  1. 1.

$\bot_{S}\in
T\Rightarrow|\mathcal{C}(S)_{T}|=2^{n-|T\backslash\\{\top_{S}\\}|}$

  2. 2.

$\bot_{S}\notin T\wedge|T\cap
B|>1\Rightarrow|\mathcal{C}(S)_{T}|=2^{n-|T\backslash\\{\top\\}|}$

  3. 3.

$\bot_{S}\notin T\wedge T\cap
B=\\{b_{i}\\}\Rightarrow|\mathcal{C}(S)_{T}|=2^{n-1}+1$

  4. 4.

$\bot_{S}\notin T\wedge T\cap
B=\emptyset\Rightarrow|\mathcal{C}(S)_{T}|=2^{n}+n+1$

######  Proof 7.3.

1\. Here, all elements of $\mathcal{C}(S)_{T}$ have the form
$\\{\bot_{S},\top_{S}\\}\cup T\cup B^{\prime}$ for some $B^{\prime}\subseteq
B\backslash T$. However, $T$ occupies already $|T\backslash\\{\top_{S}\\}|$
places in $B$ so the claim follows again from the cardinality formula for
power sets.

2\. Because closures have to contain a least element majorizing every element,
$|T\cap B|>1$ implies $\bot\in C$ for every $C\in\mathcal{C}(S)_{T}$ which
reduces this case to the previous one.

3\. Consider a closures system $C\in\mathcal{C}(S)_{T}$. If $\bot\notin C$
holds then $b_{j}\notin C$ has to hold for all $b_{i}\neq b_{j}\in B$ since
$C$ has to contain a least element majorizing any element. Hence, the only
possibility in this case is $C=\\{\bot_{S},b_{i},\top_{S}\\}$. The case
$\bot\in C$ can be treated analogously to the first case and the result
follows from summing up.

4\. We have $2^{n}$ closure systems of the form $\\{\bot_{S},\top_{S}\\}\cup
B^{\prime}$ with $B^{\prime}\subseteq B$, $n$ of the form
$\\{b_{i},\top_{S}\\}$ and the trivial closure system $\\{\top_{S}\\}$.

A concept similar to diamonds are bottomless diamonds:

An ordered set $(S,\leq)$ is called a _bottomless diamond of width $n$_ if its
carrier set $S=\\{\top_{S},b_{1},\dots,b_{n}\\}$ consists of $n+1$ pairwise
different elements and $b_{i}\not\lessgtr b_{j}$ holds for all $i\neq j$. The
elements $(b_{i})_{1\leq i\leq n}$ are called the _belt elements_ of
$(S,\leq)$.

######  Lemma 31.

Let $(S,\leq)$ be a bottomless diamond of width $n$ and let $B$ be the set of
its belt elements. Then
$|\mathcal{C}(S)_{T}|=2^{n-|T\backslash\\{\top_{S}\\}|+1}$.

######  Proof 7.4.

Clearly, every $C\subseteq S$ is a closure system iff $\top_{S}\in C$ holds so
the claim follows by elementary combinatorics.

###  7.2. Counting Closures using Isolated Suborders

From now on we assume on that every ordered set under consideration is finite
because we are interested in developing an algorithm for counting the number
of closure systems. The algorithm we are going to introduce in subsection 7.2
will make recursive calls computing the number of (pre)closure systems
containing already processed elements.

Let $(S,\leq)$ be an ordered set and consider an isolated suborder with
bottleneck $S^{\prime}\subseteq S$ of $S$ and a subset $T\subseteq S$ with
$T\cap S^{\prime}=\emptyset$. Then we can partition the set
$\mathcal{C}(S)_{T}$ into the two disjoint sets
$\mathcal{C}(S)_{T}^{S^{\prime}}$ and $\mathcal{C}(S)_{T}^{-S^{\prime}}$
(where the first one consists of all elements from $\mathcal{C}(S)_{T}$
containing an element from $S^{\prime}$ and the second one consists of all
elements from $\mathcal{C}(S)_{T}$ containing no element from $S^{\prime}$).
By the first part of Theorem 22, we obtain the following equation (we have to
subtract $1$ in order not to count the empty preclosure twice):

$|\mathcal{C}(S)_{T}^{S^{\prime}}|=|\mathcal{C}(S/\sim_{S^{\prime}})_{T^{\\{\\}}\cup\\{S^{\prime}\\}}|\cdot(|\mathcal{PC}(S^{\prime})|-1).$
(1)

By an analogous argumentation we obtain the following equation by means of the
second part of Theorem 22:

$|\mathcal{C}(S)_{T}^{-S^{\prime}}|=|\mathcal{C}(S/\sim_{S^{\prime}})_{-\\{S^{\prime}\\},T^{\\{\\}}}|.$
(2)

Now the equalities
$|\mathcal{C}(S/\sim_{S^{\prime}})_{T^{\\{\\}}}|=|\mathcal{C}(S/\sim_{S^{\prime}})_{T^{\\{\\}}\cup\\{S^{\prime}\\}}|+|\mathcal{C}(S/\sim_{S^{\prime}})_{-\\{S^{\prime}\\},T^{\\{\\}}}|$
and $|\mathcal{PC}(S^{\prime})|=2\cdot|\mathcal{C}(S^{\prime})|$, together
with
$|\mathcal{C}(S)_{T}|=|\mathcal{C}(S)_{T}^{S^{\prime}}|+|\mathcal{C}(S)_{T}^{-S^{\prime}}|$
lead to

Now we can argue as follows:

$|\mathcal{C}(S)_{T}|=$
$\\{$
$\mathcal{C}(S)_{T}=\mathcal{C}(S)_{T}^{S^{\prime}}\dot{\cup}\mathcal{C}(S)_{T}^{-S^{\prime}}$
$\\}$
$|\mathcal{C}(S)_{T}^{S^{\prime}}|+|\mathcal{C}(S)_{T}^{-S^{\prime}}|=$
$\\{$ Equation 1 $\\}$
$|\mathcal{C}(S/\sim_{S^{\prime}})_{T^{\\{\\}}\cup\\{S^{\prime}\\}}|\cdot(|\mathcal{PC}(S^{\prime})|-1)+|\mathcal{C}(S)_{T}^{-S^{\prime}}|=$
$\\{$ $|\mathcal{PC}(S^{\prime})|=2\cdot|\mathcal{C}(S^{\prime})|$ $\\}$
$|\mathcal{C}(S/\sim_{S^{\prime}})_{T^{\\{\\}}\cup\\{S^{\prime}\\}}|\cdot(2\cdot|\mathcal{C}(S^{\prime})|-1)+|\mathcal{C}(S)_{T}^{-S^{\prime}}|=$
$\\{$
$|\mathcal{C}(S/\sim_{S^{\prime}})_{T^{\\{\\}}}|=|\mathcal{C}(S/\sim_{S^{\prime}})_{T^{\\{\\}}\cup\\{S^{\prime}\\}}|+|\mathcal{C}(S/\sim_{S^{\prime}})^{-\\{S^{\prime}\\}}_{T^{\\{\\}}}|$
$\\}$
$|\mathcal{C}(S/\sim_{S^{\prime}})_{T^{\\{\\}}\cup\\{S^{\prime}\\}}|\cdot(2\cdot|\mathcal{C}(S^{\prime})|-1)+|\mathcal{C}(S/\sim_{S^{\prime}})_{T^{\\{\\}}}|-|\mathcal{C}(S/\sim_{S^{\prime}})_{T^{\\{\\}}\cup\\{S^{\prime}\\}}|=$
$\\{$ elementary calculus $\\}$
$|\mathcal{C}(S/\sim_{S^{\prime}})_{T^{\\{\\}}\cup\\{S^{\prime}\\}}|\cdot
2(|\mathcal{C}(S^{\prime})|-1)+|\mathcal{C}(S/\sim_{S^{\prime}})_{T^{\\{\\}}}|$

Alltogether, we obtain the following equation:

$|\mathcal{C}(S)_{T}|=|\mathcal{C}(S/\sim_{S^{\prime}})_{T^{\\{\\}}\cup\\{S^{\prime}\\}}|\cdot
2(|\mathcal{C}(S^{\prime})|-1)+|\mathcal{C}(S/\sim_{S^{\prime}})_{T^{\\{\\}}}|$
(3)

Analogous considerations for a summit isolated suborder $S^{\prime}$ guide us
to the following formula by means of Theorem 23:

$|\mathcal{C}(S)_{T}|=|\mathcal{C}(S/\sim_{S^{\prime}})_{T^{\\{\\}}}|\cdot|\mathcal{C}(S^{\prime})|$
(4)

Clearly, $|\mathcal{C}(S)|=|\mathcal{C}(S)_{\emptyset}|$ holds, so we can use
Equations (3) and (4) for a recursive algorithm if the ordered set under
consideration contains a useful summit isolated suborder or a useful isolated
suborder with bottleneck. However, this is only feasible if the isolated
suborder $S^{\prime}$ and the set $T$ are disjoint. Fortunately, we can ensure
this due to Lemmata 13 and 14 by choosing first - if possible - an inclusion-
maximal nontrivial suborder followed by the choice of inclusion maximal
isolated suborders with bottleneck. A formal description of this idea is given
in Algorithm 2. Of course, if the ordered set under consideration does not
contain some kind of useful isolated suborder or does not have a special
structure for which a closed formula is available, then we have to resort to
some kind of brute force.

Let us now take a look at the functioning of this algorithm. First (lines 2 to
4), it is tested whether th ordered set under consideration is of a special
structure. For the examples given here, it is easy to see that this can be
done in linear time. In every recursive call of #CLOSURES the cardinality of
the ordered sets in the first arguments is strictly smaller than the
cardinality of the ordered set from the first argument of the function call.
The first reason for this is that every isolated suborder with bottleneck or
every nontrivial summit isolated suborder $S^{\prime}$ is a strict subset of
$S$. Moreover, we consider only useful isolated suborders $S^{\prime}$, hence
$S/\sim_{S^{\prime}}$ contains strictly less element than $S$. This enforces
termination in the sense that either an ordered set with a special structure
(for which a closed formula is known) is obtained or some brute force method
is applied.

Algorithm 2 Counting Closure Operators

1:function #closures(ordered set $S$, set $T$)

2: if some special case from Subsection 7.1 is applicable then

3: return the respective number

4: end if

5: if $S$ has a useful summit isolated suborder then

6: $S^{\prime}\leftarrow$ an inclusion maximal useful summit suborder

7: return
#closures($S/\sim_{S^{\prime}}$,$T^{\\{\\}}$)$\cdot$#closures($S^{\prime}$,
$\emptyset$)

8: end if

9: if $S$ has a useful isolated suborder with bottleneck then

10: $S^{\prime}\leftarrow$ an inclusion maximal useful isolated suborder with
bottleneck

11: return #closures($S/\sim_{S^{\prime}}$,
$T^{\\{\\}}\cup\\{S^{\prime\\{\\}}\\}$)$\cdot$2(#closures($S^{\prime}$,
$\emptyset$)-1)+#closures($S/\sim_{S^{\prime}}$,${T^{\\{\\}}}$)

12: end if

13: compute and return $|\mathcal{C}(S)_{T}|$ by some brute force algorithm

14:end function

As described in Algorithm 1 and the following discussion, isolated suborders
of interest can be computed in polynomial time. Hence, we can assume that the
test whether an order has a certain structure (lines 2 to 4) and the
computation of isolated sublattices in the algorithm are bounded by a
polynomial $p$. Let us now assume that a brute force algorithm takes $c^{|S|}$
time for some $c>1$ to compute the number of all closure systems. Furthermore,
let us consider a sequence $(S_{1},\leq_{1})$, $(S_{2},\leq_{2})$, $\ldots$ of
finite ordered sets with $|S_{i}|<|S_{i+1}|$ such that no $S_{i}$ has a useful
isolated suborder (e.g., choose for $(S_{i},\leq_{i})$ the power set lattice
of $[1,\ldots n]$). Furthermore, let $(S^{\prime}_{i},\leq^{\prime}_{i})$ be
an isomorphic copy of $(S_{i},\leq_{i})$, and define the ordered set
$(T_{i},\leq_{T_{i}})$ by $T_{i}=_{def}S_{i}\dot{\cup}S_{i+1}$ and
$\leq_{T_{i}}=_{def}\leq_{i}\dot{\cup}\leq^{\prime}_{i}\dot{\cup}S_{i}\times
S^{\prime}_{i}$. Then $T_{i}$ contains exactly one useful summit isolated
suborder (namely $S^{\prime}_{i}$). An immediate application of a brute force
algorithm to $T_{i}$ would now take $\mathcal{O}{|T_{i}|^{c}}$ time. However,
Algorithm 2 will make two recursive calls (note that the condition in line 5
is true) on instances of sizes $\frac{|T_{i}|}{2}$ and $\frac{|T_{i}|}{2}+1$.
Hence, the running time in this case will amount to
$\mathcal{O}(p(|T_{i}|)+p(\frac{|T_{i}|}{2})+c^{\frac{|T_{i}|}{2}}+p(\frac{|T_{i}|}{2}+1)+c^{\frac{|T_{i}|}{2}+1})\in$
$\mathcal{O}{c^{\frac{|T_{i}|}{2}+1}}$. Asymptotically, this running time is
dominated strictly by $\mathcal{O}(T_{i}^{c})$, so Algorithm 1 will lead to a
speed up.

Another argument in favor of Algorithm 2 can be given by means of the master
theorem. Assume that we have an order which allows recursive decomposition by
means of isolated suborders with half the size of the starting order down to
orders of a constant size (dismantable lattices as in [BM96] are a class of
orders with a similar property). Then, the running time fulfills the recursion
equation $T(|S|\leq 3T(\frac{|S|}{2}+1)+p(|S|)$. The critical exponent in this
case is $\text{log}_{2}(3)<1.6$ which is less than the degree of $p$ according
to the analysis of Algorithm 1. Hence, under these (admittedly artificial and
favorable) circumstances, Algorithm 1 runs in $\mathcal{O}(p)$ time.

##  8\. Conclusion and Outlook

As main result, we introduced Algorithm 2 which can simplify counting of
closures if the ordered set under consideration contains certain kinds of
isolated suborders. Naturally, the question arises whether more general or
other structures than isolated suborders can be used with the same purpose.
Concepts which come to mind are bisimulations which are used also for
simplification (in the sense of reducing the number of states) in model
checking in [BK08] or model refinement in [GMS10]. Also, it would be of
interest to search for more special cases than the ones from Subsection 7.1
wherefrom the Algorithm would clearly benefit. Lastly, the algorithm is still
awaiting being implementated. Part of such an implementation would also be an
optimal (i.e., linear time) algorithm for the computation of isolated
suborders along the lines sketched at the end of Subsection 6.2. A combination
of classical programming and specific system like Mace4 (see [Mac]) or RelView
(see [Rel]) seems to be an interesting and promising approach. Alas, for
computing the number of closure systems on a powerset, the approach presented
here will be of no help: it is easy to see that a powerset lattice contains no
useful isolated suborders.

## References

  * [AJS21] N. Alpay, P. Jipsen, and M. Sugimoto.  Unary-determined distributive $\ell$-magmas and bunched implication algebras.  In U. Fahrenberg, M. Gehrke, L. Santocanale, and M. Winter, editors, Relational and Algebraic Methods in Computer Science - 19th International Conference, RAMiCS 2021, Marseille, France, November 2-5, 2021, Proceedings, volume 13027 of Lecture Notes in Computer Science, pages 19–36. Springer, 2021.  doi:10.1007/978-3-030-88701-8\\_2.
  * [AW21] J. Alman and V. V. Williams.  A refined laser method and faster matrix multiplication.  In D. Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 522–539. SIAM, 2021.  doi:10.1137/1.9781611976465.32.
  * [BBW21] R. Berghammer, S. Börm, and M. Winter.  Algorithmic counting of zero-dimensional finite topological spaces with respect to the covering dimension.  Appl. Math. Comput., 389:125523, 2021.
  * [BD18] G. Brinkmann and R. Deklerck.  Generation of union-closed sets and moore families.  Journal of Integer Sequences, 21(1):18.1.7, 2018.  URL: https://cs.uwaterloo.ca/journals/JIS/VOL21/Brinkmann/brink6.html.
  * [Bir67] G. Birkhoff.  Lattice Theory.  Amer. Math. Soc., 3rd edition, 1967.
  * [BK08] C. Baier and J-P. Katoen.  Principles of Model Checking.  MIT Press, 2008.
  * [BM96] G. Bordalo and B. Monjardet.  Reducible classes of finite lattices.  Order, 13(4):379–390, 1996.
  * [Bod88] H. Bodlaender.  Dynamic programming on graphs with bounded treewidth.  In T. Lepistö and A. Salomaa, editors, Automata, Languages and Programming, 15th International Colloquium, ICALP88, Tampere, Finland, July 11-15, 1988, Proceedings, volume 317 of Lecture Notes in Computer Science, pages 105–118. Springer, 1988.  doi:10.1007/3-540-19488-6\\_110.
  * [BPBV18] S. Bonzio, M. Pra Baldi, and D. Valota.  Counting finite linearly ordered involutive bisemilattices.  In J. Desharnais, W. Guttmann, and S. Joosten, editors, Relational and Algebraic Methods in Computer Science - 17th International Conference, RAMiCS 2018, Groningen, The Netherlands, October 29 - November 1, 2018, Proceedings, volume 11194 of Lecture Notes in Computer Science, pages 166–183. Springer, 2018.
  * [CCMP20] A. Conte, P. Crescenzi, A. Marino, and G. Punzi.  Enumeration of s-d separators in dags with application to reliability analysis in temporal graphs.  In J. Esparza and D. Král’, editors, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, volume 170 of LIPIcs, pages 25:1–25:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020\.  doi:10.4230/LIPIcs.MFCS.2020.25.
  * [CIR10] P. Colomb, A. Irlande, and O. Raynaud.  Counting of moore families for n=7.  In L. Kwuida and B. Sertkaya, editors, Formal Concept Analysis, 8th International Conference, ICFCA 2010, Agadir, Morocco, March 15-18, 2010\. Proceedings, volume 5986 of Lecture Notes in Computer Science, pages 72–87. Springer, 2010.
  * [CM03] N. Caspard and B. Monjardet.  The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey.  Discrete Applied Mathematics, 127(2):241–269, 2003.
  * [DHLM92] J. Demetrovics, G. Hencsey, L. Libkin, and I. B. Muchnik.  On the interaction between closure operations and choice functions with applications to relational database.  Acta Cybern., 10(3):129–139, 1992.  URL: https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3401.
  * [DP02] B. A. Davey and H. A. Priestley.  Introduction to Lattices and Order, Second Edition.  Cambridge University Press, 2002.
  * [EBJ+14] S. Elloumi, B. Boulifa, A. Jaoua, M. Saleh, J. Al Otaibi, and M. F. Frias.  Inference engine based on closure and join operators over truth table binary relations.  J. Log. Algebraic Methods Program., 83(2):180–193, 2014.
  * [FJST20] U. Fahrenberg, C. Johansen, G. Struth, and R.B. Thapa.  Generating posets beyond N.  In U. Fahrenberg, P. Jipsen, and M. Winter, editors, Relational and Algebraic Methods in Computer Science - 18th International Conference, RAMiCS 2020, Palaiseau, France, April 8-11, 2020, Proceedings [postponed], volume 12062 of Lecture Notes in Computer Science, pages 82–99. Springer, 2020.  doi:10.1007/978-3-030-43520-2\\_6.
  * [Glü17] R. Glück.  Algebraic investigation of connected components.  In P. Höfner, D. Pous, and G. Struth, editors, Relational and Algebraic Methods in Computer Science - 16th International Conference, RAMiCS 2017, Lyon, France, May 15-18, 2017, Proceedings, volume 10226 of Lecture Notes in Computer Science, pages 109–126, 2017.
  * [Glü21] R. Glück.  Isolated sublattices and their application to counting closure operators.  In U. Fahrenberg, M. Gehrke, L. Santocanale, and M. Winter, editors, Relational and Algebraic Methods in Computer Science - 19th International Conference, RAMiCS 2021, Marseille, France, November 2-5, 2021, Proceedings, volume 13027 of Lecture Notes in Computer Science, pages 192–208. Springer, 2021.  doi:10.1007/978-3-030-88701-8\\_12.
  * [GMS10] R. Glück, B. Möller, and M. Sintzoff.  Model refinement using bisimulation quotients.  In M. Johnson and D. Pavlovic, editors, Algebraic Methodology and Software Technology - 13th International Conference, AMAST 2010, Lac-Beauport, QC, Canada, June 23-25, 2010. Revised Selected Papers, volume 6486 of Lecture Notes in Computer Science, pages 76–91. Springer, 2010\.
  * [Gol89] D. E. Goldberg.  Genetic Algorithms in Search Optimization and Machine Learning.  Addison-Wesley, 1989.
  * [Grä11] G. Grätzer.  Lattice theory: Foundation.  Springer Basel, 2011.
  * [HNR68] P. E. Hart, N. J. Nilsson, and B. Raphael.  A formal basis for the heuristic determination of minimum cost paths.  IEEE Trans. Syst. Sci. Cybern., 4(2):100–107, 1968.  URL: https://doi.org/10.1109/TSSC.1968.300136.
  * [ILS12] G. F. Italiano, L. Laura, and F. Santaroni.  Finding strong bridges and strong articulation points in linear time.  Theor. Comput. Sci., 447:74–84, 2012.  doi:10.1016/j.tcs.2011.11.011.
  * [JR92] P. Jipsen and H. Rose.  Varieties of Lattices.  Springer, 1st edition, 1992.
  * [Kam07] F. Kammer.  Determining the smallest _k_ such that _G_ is _k_ -outerplanar.  In L. Arge, M. Hoffmann, and E. Welzl, editors, Algorithms - ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings, volume 4698 of Lecture Notes in Computer Science, pages 359–370. Springer, 2007.  doi:10.1007/978-3-540-75520-3\\_33.
  * [Mac] Mace4.  https://www.cs.unm.edu/~mccune/mace4/.  [Online; accessed 23-February-2023].
  * [QRRV20] S. Quintero, S. Ramírez, C. Rueda, and F. Valencia.  Counting and computing join-endomorphisms in lattices.  In U. Fahrenberg, P. Jipsen, and W. Winter, editors, Relational and Algebraic Methods in Computer Science - 18th International Conference, RAMiCS 2020, Palaiseau, France, April 8-11, 2020, Proceedings [postponed], volume 12062 of Lecture Notes in Computer Science, pages 253–269. Springer, 2020.
  * [Rel] RelView.  https://www.informatik.uni-kiel.de/~progsys/relview/.  [Online; accessed 23-February-2023].
  * [Rom08] S. Roman.  Lattices and Ordered Sets.  Springer, 1st edition, 2008.