()


@ Appl. Gen. Topol. 18, no. 2 (2017), 255-275doi:10.4995/agt.2017.5868
c© AGT, UPV, 2017

Oriented components and their separations

Bärbel M. R. Stadler a and Peter F. Stadler a−d

a
Max Planck Institute for Mathematics in the Sciences, Inselstraße 22, D-04103 Leipzig, Ger-

many. (baer@bioinf.uni-leipzig.de)
b
Bioinformatics Group, Department of Computer Science; Interdisciplinary Center for Bioinfor-

matics; German Centre for Integrative Biodiversity Research (iDiv) Halle-Jena-Leipzig; Compe-

tence Center for Scalable Data Services and Solutions; and Leipzig Research Center for Civilization

Diseases, Leipzig University, Härtelstraße 16-18, D-04107 Leipzig, Germany.

(studla@bioinf.uni-leipzig.de)
c

Institute for Theoretical Chemistry, University of Vienna, Währingerstraße 17, A-1090 Wien,

Austria.
d
Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM 87501

Communicated by E. Induráin

Abstract

There is a tight connection between connectedness, connected com-

ponents, and certain types of separation spaces. Recently, axiom sys-

tems for oriented connectedness were proposed leading to the notion of

reaches. Here, we introduce production relations as a further genera-

lization of connectivity spaces and reaches and derive associated sys-

tems of oriented components that generalize connected components in

a natural manner. The main result is a characterization of generalized

reaches in terms of equivalent separation spaces.

2010 MSC: 54D05; 54E05.

Keywords: separation spaces; pre-proximities; generalized topological
spaces.

1. Introduction

Already in the 1940’s, A. D. Wallace asked whether topological concepts
can be axiomatized starting from a notion of connectivity or an associated

Received 02 June 2016 – Accepted 21 March 2017

http://dx.doi.org/10.4995/agt.2017.5868


concept of separation [29], the latter being the complement of a generalization
of proximity [24]. Ch. Ronse characterized the separations that are equivalent
to abstract connectivities [20]. These results were generalized further in [26].
Since connectedness is an intrinsically symmetric notion, the theory requires
that separations satisfy a symmetry axiom.

Tankyevych et al. [28] recently introduced so-called semi-connections as a
generalized model of connected components in directed graphs. Ronse explored
this concept in more detail [22] as a generalization of connectivity openings
[20, 23] and discussed some fundamental properties of the equivalent notion
of oriented components. The latter form a system of pairs (p, Q) with the
interpretation that “every point of Q is reachable from p within Q”. This con-
struction is insufficient, however, to capture the natural connectivity structure
of chemical reaction networks and directed hypergraphs in general. The key
point is that in a chemical reaction, the “output molecules” depend on a set
of “input molecules” rather than on a single input molecule. This suggests to
generalize the work of [28, 22] to pairs (P, Q) such that every point of Q can
be reached from the start set P within Q.

This formalization of reachability does not appear to be connected to con-
cepts familiar from topology in an obvious manner. On the other hand, reaches
are rather natural generalizations of connectivity structures, and the latter have
been shown to be equivalent to certain generalized proximities in [20, 26]. It
is the purpose of this contribution to show that there is also a 1-1 correspon-
dence of reachability structures general enough to encompass chemical reaction
networks, and thus directed hypergraphs, and a suitable class of generalized
separations or, equivalently, proximities.

To this end we consider two binary relations ≻− and | on 2X × 2X that we
interpret as follows: P ≻− Q means that P can produce Q, i.e., Q are the
points eventually reachable from P . Production relations capture the salient
structure of (directed) hypergraphs, which to our knowledge rarely have been
considered with regard of their topological properties [10]. On the other hand,
we think of A | B as “A is separated from B”. The negation of separation
relations are proximity relations, Aδ B, which are well studied in the literature
as a starting point for constructing topological theories [24, 13, 14, 18]. Before
we turn to establishing the formal connection between production relations and
separations, we briefly argue that production relations are an interesting notion
to study in their own right.

2. Production Relations in the Real World

The paradigmatic examples of production relations derive from chemical
reactions. Given a set X of molecular types, usually called compounds or
reactants, chemical reactions describe the transformation of subsets into each
other. An example is the burning of methane in oxygen, which produces carbon
dioxide and water CH4 + 2O2 → CO2+ 2H2O. An important property of sys-
tems of chemical reactions is that the products can undergo further reactions,
for instance with each other, e.g. CO2 + H2O → H2CO3, or with additional

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 256



Oriented components and their separations

reactants, say CO2 + H2 → CO + H2O. Chemical reactions thus can be con-
catenated into overall reactions such as CH4 + 2O2 → H2CO3 + H2O. As long
as we are only interested in which molecules can be transformed into each other,
we can neglect the multiplicities (called stoichiometric coefficients) and think
of reactions as a relation on 2X. In our example {CH4, O2} → {CO2, H2O},
and so on.

An important question in the analysis of reaction networks is to understand
which compounds can eventually be generated from which initial conditions.
In particular in the field of biochemistry, there are also large databases of the
chemical reactions that together describe the metabolic network of a cell [8].
In a more general setting rules that describe which reactions are possible and
which are not can be specified in the form of graph grammars. These can then
be used to computationally generate large chemical networks [1]. Reachability
in such a network amounts to asking whether, given a set Q of compounds
of interest and set P of starting molecules, it is possible to produce Q by a
sequence of consecutive reactions P ′ → Q′ where initially P ′ ⊆ P and always
Q′ ⊆ Q must hold. In subsequent steps we also allow the educts P ′ to be
contained in the union of the products of earlier steps. This construction
naturally leads to the notion of what we call here the production relation P ≻−
Q. Since chemical reactions may run in parallel, reachability must be “additive”
in the sense that Pi ≻− Qi for all i ∈ I should imply

⋃

i
Pi ≻−

⋃

Qi. The re-use
of products for consecutive reactions leads us to conclude that P ≻− Q and
S ≻− T for some S ⊆ Q must imply P ≻− Q ∪ T . In fact, we will be content with
essentially these two properties when we formally define production relations
in the next section.

A somewhat different motivation for the same formal construction comes
from evolutionary algorithms. Here, the problem is to optimize a cost function
f : X → R over some set X using a search operator that produces from a
set of parents A ⊆ X a set of offsprings c(A). The same framework of course
also models real evolution in biology [27, 25]. In the simplest case, mutations
transform individual genotypes into their mutant offsprings, thus imposing a
graph structure on X. In the usual setup of evolutionary strategies [19] and
genetic algorithms [11], however, recombinants of two parents are used, i.e., the
structure of the search space is determined implicitly by the relations of the
form {x, y} → Rxy. Such relations have been investigated extensively under
the name transit functions [16, 5], which serve as generalizations of betweenness
relations and abstract convexities. The cost function f : X → R together with
the topological structure on X implied by the search spaces give rise to “fitness
landscapes” [30], in which concepts such as local minima, saddle points, and
basins of attraction are well defined. These notions are inherently topological in
nature and require only the definition of connected sets on X [9, 12, 26]. Search
operators are not necessarily symmetric, however. Most recombination opera-
tors used in evolutionary computation tend to reduce diversity in the “search
population” and thus are inherently directional. It is of interest, therefore, to
consider reachability as a generalization of connectedness.

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 257



In general, production relations naturally appear in all types of generative
systems. When generation rules apply to individual elements, as in the case of
mutations of gene sequences, reaches in the sense of [28] and [22] are obtained.
Generative grammars and (term) rewriting systems could also be viewed in
this way. Alternatively, generation rules apply to sets or multisets of elements
rather than individual elements. A proper description then requires produc-
tion relations in the sense of this contribution. Within computer science this
pertains in particular to large classes of “chemistry-like” formal systems such
as Berry’s Chemical Abstract Machine [3]. Certain constructions in natural
languages, such the well known property of the German language to produce
new nouns by concatenations of nouns, or the self-assembly of macromolecular
complexes may serve as further examples.

3. Separations, Productions, and Oriented Components

3.1. Galois Correspondence. To relate the production relation ≻− and a se-
paration relation | with each other, we introduce another relation ≬ on (2X ×
2X) × (2X × 2X) that expresses when a pair (A, B) splits a pair (P, Q):

(3.1) (A, B) ≬ (P, Q) ⇐⇒ P ∪ Q ⊆ A ∪ B, P ⊆ B, and Q ∩ A 6= ∅

The negation of ≬ will be written as ≬−. Thus we have (A, B) ≬− (P, Q) if and
only if P ∪ Q 6⊆ A ∪ B, or P /∈ B, or A ∩ Q = ∅. The relation ≬− is a very
natural way of connecting ≻− and |: If P ≻− Q there is no A | B that splits P
from Q, and A | B means that there is no P ≻− Q that “reaches” from B to A.
Fig. 1 illustrates the interesting case.

p p

Q Q
B

A

B

A

(A, B) ≬ ({p}, Q) (A, B) ≬− ({p}, Q)

Figure 1. Illustration of the splitting relation ≬ between two
pairs of subsets.

More formally, we have the Galois connection comprising the two maps

φ : 22
X
×2X → 22

X
×2X , {(P, Q)|P ≻− Q} 7→ {(A, B)|A |̇ B}

θ : 22
X
×2X → 22

X
×2X , {(A, B)|A | B} 7→ {(P, Q)|A ≻̇− B}.

(3.2)

where the induced relations |̇ and ≻̇−, resp., are defined by

A |̇ B ⇐⇒ (A, B) ≬− (P, Q) ∀(P, Q) ∈ 2X with P ≻− Q

P ≻̇− Q ⇐⇒ (A, B) ≬− (P, Q) ∀(A, B) ∈ 2X with A | B
(3.3)

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 258



Oriented components and their separations

The theory of Galois connections implies that θ(φ) and φ(θ) are closure oper-

ations on 22
X
×2X defining from a | and ≻− relations |̈ := φ(≻̇−) = φ(θ(|)) and

≻̇−:= θ(|̇) = θ(φ(≻−)), resp., that are in 1-1 correspondence. In other words, θ
and φ induce a bijection between img θ and img φ. We are interested, therefore,
in the properties of relations | and ≻− that correspond to elements of img θ and
img φ, respectively.

3.2. Basic Properties. Throughout this section we write |̇:= φ(≻−) for the
separation relation induced by a given production relation ≻−; conversely ≻̇−:=
θ(|) denotes the production relation induced by a given separation relation |.
We start from an arbitrary production relation ≻− and strive to identify the

properties of |̇ that are necessary for membership in img φ.

Theorem 3.1. Given an arbitrary production relation ≻−, the corresponding

relation |̇ satisfies for all A, B ∈ 2X:

(S0) ∅ |̇ B for all B.

(S1) A′ ⊆ A, B′ ⊆ B, and A |̇ B implies A′ |̇ B′.

(SR1) A |̇ C and B |̇ A ∪ C implies A ∪ B |̇ C.

(SR2) Ai ∪ Bi = Z and Ai |̇ Bi for all i ∈ I implies
⋃

i∈I
Ai |̇

⋂

i∈I
Bi

Proof. (S0) follows immediately from the definition of ≬−.

(S1) Suppose A′ ⊆ A and B′ ⊆ B. From A |̇ B we know that for all P ≻− Q
with P ∪ Q ⊆ A ∪ B and P ⊆ B holds Q ∩ A = ∅. The pairs P ≻− Q satisfying
P ∪ Q ⊆ A′ ∪ B′ and P ⊆ B′ are a subset of the latter. Furthermore, they also

satisfy Q ∩ A′ = ∅. Thus A′ |̇ B′ holds.

(SR1) Suppose A |̇ C and B |̇ A ∪ C are satisfied but A ∪ B |̇ C does not
hold, i.e., there is a production P ≻− Q with P ⊆ C, Q ⊆ A ∪ B ∪ C, and

(A∪B)∩Q 6= ∅. Suppose first that Q∩B = ∅; then A |̇ C implies Q∩A = ∅.
The desired production therefore must satisfy Q∩B 6= ∅. Since P ⊆ C implies

P ⊆ A ∪ C we infer from B |̇ A ∪ C that Q ∩ B = ∅, a contradiction. Thus

A ∪ B |̇ C cannot be violated.

(SR2) Suppose Ai ∪ Bi = Z and Ai |̇ Bi holds for all i ∈ I. Consider all
P ≻− Q with P∪Q ⊆ Z and P ⊆ Bi for all i ∈ I, i.e., P ⊆

⋂

i
Bi. By assumption,

Q ∩ Ai = ∅ for all i and thus Q ∩
⋃

i
Ai = ∅. Therefore

⋃

i
Ai |̇

⋂

Bi. �

A space satisfying (S0) and (S1) can be seen as the most general form of a
separation space generalizing even further the setting of Wallace [29]. The ax-
ioms (SR1) and (SR2), on the other hand, appeared in Ronse’s characterization
of separation spaces that are defined by connectedness [20].

Now we take the converse point of view. Starting from an arbitrary “sepa-
ration” relation | we determine properties of the production relation ≻̇− that is
defined by the map θ to obtain necessary conditions for membership in img θ.

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 259



Lemma 3.2. Given an arbitrary separation relation |, the corresponding rela-
tion ≻̇− satisfies

(O) P ≻̇− ∅.
(U) If Pi ≻̇− Qi for all i ∈ I then

⋃

Pi ≻̇−
⋃

Qi. ( union property)
(T) If P ≻̇− Q, S ⊆ Q, and S ≻− T then P ≻− Q ∪ T . ( transitivity)

(T+) If P ≻̇− Q, S ⊆ Q ⊆ T and P ∪ S ≻− T then P ≻̇− T . ( source closure)

Proof. (O) Given any collection of A|B we always have A ∩ Q = ∅ if Q = ∅,
i.e, (A, B) ≬− (P, ∅) holds for all P ∈ 2X.

(U) Suppose Pi ≻̇− Qi for some family i ∈ I. Thus, for all A | B with Pi ⊆ B
and Pi ∪ Qi ⊆ A ∪ B holds A ∩ Qi = ∅. In particular, therefore, every A | B
satisfying

⋃

i∈I
Pi ∈ B and

⋃

i∈I
Pi ∪

⋃

i∈I
Qi ⊆ A ∪ B therefore also satisfies

⋃

i∈I
Qi ∩ A = ∅, and therefore

⋃

i∈I
Pi ≻̇−

⋃

i∈I
Qi holds.

(T) Suppose P ≻̇− Q, S ⊆ Q and S ≻̇− T . Suppose P ≻̇− Q ∪ T does not
hold, i.e., there is a separation A | B with P ∪ Q ∪ T ⊆ A ∪ B, P ⊆ B,
and (Q ∪ T ) ∩ A 6= ∅. We observe that Q ∩ A 6= ∅ contradicts P ≻̇− Q,
hence Q ∩ A = ∅, which implies Q ⊆ B and therefore also S ⊆ B. Therefore
A ∩ T 6= ∅ contradicts S ≻̇− T , i.e., no such separation A | B can exist, and
P ≻̇− Q ∪ T must be true.

(T+) Suppose P ≻̇− Q and P ∪ S ≻− T holds for S ⊆ Q ⊆ T . Note that
P ∪S ≻− T implies by (U) also P ∪S ≻− T ∪Q, hence we may choose T such that
Q ⊆ T . Now suppose for contradiction that P ≻̇− T does not hold. Then there
is a A | B with P ∪ T = A ∪ B such that P ⊆ B and T ∩ A 6= ∅. Since P ≻̇− Q
we have A ∩ Q = ∅ and thus Q ⊆ B, which further implies S ⊆ B. From
P ∪ S ≻̇− T we know that A′ ∩ T = ∅ holds for all A′ | B′ with S ∪ P ⊆ B′ and
A′ ∪ B′ = P ∪ Q. This is in particular also true for A | B, a contradiction. �

Axiom (U) generalizes the “union property” of [22]. It allows multiple pro-
duction to be “applied” at the same time. The transitivity axiom (T) encap-
sulates the idea that Q is an “attractor” that is reached eventually.

Lemma 3.3. If (O) and (U) holds, then (T+) implies (T).

Proof. Suppose P ≻− Q and S ⊆ Q and S ≻− T . By (U) also have P ∪S ≻− Q∪T .
Setting T ′ = Q ∪ T we have S ⊆ Q ⊆ T ′ and P ∪ S ≻− T ′. Now (T+) implies
P ≻− T ′, i.e., T ≻− Q ∪ T , and thus (T) holds. �

We next observe that it is sufficient to consider the relationship of ≻− and |
on a given subset Y ∈ 2X. To this end we define for a given separation relation
| and all pairs (P, Q) ∈ 2X × 2X the collections

(3.4) S(P, Q) :=
{

(A, B) ∈ 2X × 2X
∣

∣A ∪ B = P ∪ Q, P ⊆ B , and A | B
}

.

of separated pairs on Y = P ∪ Q. The production relation ≻̇− can be specified
completely by the sets S(P, Q) by virtue of the following simple condition:

Lemma 3.4. P ≻̇− Q if and only if Q ∩ A = ∅ for all (A, B) ∈ S(P, Q).

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 260



Oriented components and their separations

Proof. By definition, we have P ≻̇− Q if and only if (A, B) ≬− (P, Q) for all
(A, B) ∈ 2X with A | B. If P 6⊆ B or P ∪Q := Y 6⊆ A∪B then (A, B) ≬− (P, Q)
always holds, i.e., these pairs never impose a condition and therefore they can
be ignored. Now consider the remaining case P ⊆ B and Y ⊆ A ∪ B. Thus
(A, B) ≬− (P, Q) holds if and only if A∩Q = ∅. Set A′ = A∩Y and B′ = B ∩Y
and observe that P ⊆ B ∩ Y iff P ⊆ B′ and Q ∩ A = Q ∩ (A ∩ Y ) = Q ∩ A′.
Therefore, (A, B) ≬− (P, Q) if and only if (A′, B′) ≬− (P, Q) and A ∩ Q = ∅ if
and only if A′ ∩ Q = ∅. Since A | B implies A′ | B′ by (S1) we conclude that
P ≻̇− Q holds if and only if (A′, B′) ≬− (P, Q) and A′ | B′. The latter statement
is equivalent expressed as Q ∩ A′′ = ∅ for all (A′′, B′′) ∈ S(P, Q). �

Now let us fix Z and P ⊆ Z and suppose Q ∪ P = Z. As a consequence of
(SR2) there is a unique “extremal” separation A∗|B∗ with A∗ ∪ B∗ = Z and
P ⊆ B∗, which is defined by

(3.5) A∗ =
⋃

(A,B)∈S(P,Q)

A and B∗ =
⋂

(A,B)∈S(P,Q)

B

since A ∩ Q = ∅ and P ⊆ B for all (A, B) ∈ S(P, Q).

Corollary 3.5. Suppose A∗ | B∗ as defined by S(P, Q) as in equ.(3.5). Then
we have P ≻̇− Q if and only if Q ∩ A∗ = ∅.

Proof. By lemma 3.4, P ≻̇− Q if and only if Q∩A = ∅ for all (A, B) ∈ S(P, Q).
By equ.(3.5) this is equivalent to A∗ ∩ Q = ∅. �

The key observation here is that A∗|B∗ depends only on P and Z but not
on the exact choice of Q as long as Z \ P ⊆ Q ⊆ Z. Thus P ≻̇− Q implies
A∗ ⊆ P \ Q. Furthermore, Q ∩ A∗ = ∅ implies the same condition also for all
subsets Q′ of Q. Since the corollary holds as long as Q′ ∪ P = Q ∪ P = Z, we
have in particular the following implication:

(A) P ≻̇− Q implies P ≻̇− Q′ for all Q′ satisfying Q \ P ⊆ Q′ ⊆ Q.

We will give a more intuitive interpretation of property (A) in the following
section.

3.3. Oriented Components. For every pair (P, Q) ∈ 2X × 2X we define the
set

(3.6) Q[P ] =
⋃

{

Q′ ∈ 2X
∣

∣ Q′ ⊆ Q, P ′ ⊆ P and P ′ ≻− Q′
}

The map γ : 2X × 2X → 2X : (P, Q) 7→ Q[P ] generalizes the openings that
play a central role e.g. in topological approaches to image analysis [23, 20, 15].
The sets Q[P ] will be referred to as (generalized) oriented components.

Lemma 3.6. Suppose ≻− is a production relation satisfying (U). Then

(o1) Q[P ] ⊆ Q. (contraction)
(o2) P ′ ⊆ P and Q′ ⊆ Q implies Q′[P ′] ⊆ Q[P ]. (isotony)
(o3) (Q[P ])[P ] = Q[P ]. (idempotency)

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 261



Proof. Property (o1) is an immediate consequence of the definition.
If P shrinks in equ.(3.6) then the union runs over fewer productions, and thus
Q[P ] cannot increase, i.e., P ′ ⊆ P implies Q[P ′] ⊆ Q[P ]. The same argument
can be applied if Q is reduced, hence Q′ ⊆ Q implies Q′[P ] ⊆ Q[P ]. Now (o2)
follows by combining the two inclusions.
Fix P and Q. By definition every Q′ ⊆ Q with P ′ ⊆ P and P ′ ≻− Q′ implies
Q′ ⊆ Q[P ]. Thus replacing Q in the r.h.s. of equ.(3.6) by Q[P ] does not change
the collection of sets. Since this substitution turns the definition of Q[P ] into
the definition of (Q[P ])[P ], property (o3) holds. �

We call a map 2X × 2X → 2X : (P, Q) 7→ Q[P ] that satisfies (o1), (o2), and
(o3) a generalized opening. It defines a production relation by means of

(3.7) P ≻− Q if and only if Q[P ] = Q.

An immediate consequene is the following

Fact 3.7. If ≻− satisfies (O) and (U) then P ≻− Q[P ] for all P, Q ∈ 2X.

Lemma 3.8. If (P, Q) 7→ Q[P ] is a generalized opening, then the corresponding
production relation ≻− satisfies (O) and (U).

Proof. Setting Q = ∅ we have ∅[P ] = ∅, i.e., P ≻− Q.
Suppose Q[P ] = Q and P ⊆ P ′. Then isotony w.r.t. P implies Q = Q[P ] ⊆
Q[P ′] ⊆ Q, and thus Q[P ′] = Q. Now consider an arbitrary family F of
pairs (P, Q) satisfying Q[P ] = Q and let P ∗ =

⋃

{P |(P, Q) ∈ F}. We have
Q[P ] = Q[P ∗] for all (P, Q) ∈ F. Isotony w.r.t. to Q and condition (o1) now
imply

⋃

Q:(P,Q)∈F

Q =
⋃

Q:(P,Q)∈F

Q[P ∗] ⊆





⋃

Q:(P,Q)∈F

Q



 [P ∗] ⊆
⋃

Q:(P,Q)∈F

Q .

With the abbreviation Q∗ :=
⋃

(P,Q)∈F Q we therefore have Q
∗[P ∗] = Q∗. In

other words, P ≻− Q for all (P, Q) ∈ F implies P ∗ ≻− Q∗, i.e., (U) holds. �

Theorem 3.9. Eqns.(3.6) and (3.7) define a bijection between relations ≻−
satisfying (O) and (U) on 2X and maps 2X × 2X → 2X satisfying (o1), (o2),
and (o3).

Proof. It is shown e.g. in [22] that there is a bijection between the openings γP :
(P, Q) 7→ Q[P ] and the set systems with the union property FP := {Q|P ≻− Q}
for fixed P . The theorem now follows directly from lemma 3.6 and lemma 3.8,
whose proofs also establish the correspondence P ≻− Q =⇒ P ′ ≻− Q for all
P ⊆ P ′ and Q[P ] = Q =⇒ Q[P ′] = Q for all P ⊆ P ′ �

Let us now turn to additional properties of production relations that derive
from separations. Property (T) translates into a simple transitivity condition
for generalized openings. The following lemma parallels Prop. 2 of [22]:

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 262



Oriented components and their separations

Lemma 3.10. Let ≻− be a production relation satisfying (O) and (U) and let
(Q, P) 7→ Q[P ] be the corresponding generalized opening. Then axiom (T) is
equivalent to

(o4) S ⊆ Q[P ] implies Q[S] ⊆ Q[P ].

Proof. Suppose (T) holds. From P ≻− Q[P ], S ≻− Q[S], and S ⊆ Q[P ] we
conclude P ≻− Q[P ] ∪ Q[S] ⊆ Q. By maximality of the oriented connected
components we therefore have Q[P ] ∪ Q[S] ⊆ Q[P ], i.e., Q[S] ⊆ Q[P ], i.e., (o4)
holds.

Conversely suppose (o4) is satisfied. Assume P ≻− Q, S ≻− T and S ⊆ Q.
Thus we have Q[P ] = Q and T [S] = T and further Q[P ] ⊆ (Q ∪ T )[P ],
S ⊆ (Q∪T )[P ], and T ⊆ (Q∪T )[S]. Now (o4) implies (Q∪T )[S] ⊆ (Q∪T )[P ]
and therefore T ⊆ (Q∪T )[P ]. Taken together we have Q∪T ⊆ (Q∪T )[P ] and
thus Q ∪ T = (Q ∪ T )[P ]. This translates to P ≻− Q ∪ T , i.e., (T) holds. �

Property (T+) becomes a transitivity condition in the arguments:

Lemma 3.11. If ≻− satisfies (O) and (U) and (Q, P) 7→ Q[P ] is the corre-
sponding generalized opening, then (T+) is equivalent to

(t+) If R ⊆ Q[P ] then Q[P ∪ R] = Q[P ].

Proof. Suppose (T+) holds. Substituting Q by Q[P ] and T by T [P ∪ S]
transforms (T+) to: S ⊆ Q[P ] ⊆ T [P ∪ S] and P ∪ S ≻− T [P ∪ S] implies
P ≻− T [P ∪ S]. For the first precondition observe that Q[P ] ⊆ T [P ∪ S]
implies Q[P ] = (Q[P ])[P ] ⊆ (T [P ∪ S])[P ] ⊆ T [P ], and hence in particular
S ⊆ Q[P ] ⊆ T [P ]. The second precondition is always true and thus can be
omitted. The definition of generalized oriented components, finally, implies
T [P ∪ S] ⊆ T [P ] because T [P ∪ S] ⊆ T . On the other hand T [P ] ⊆ T [P ∪ S]
by isotony. Thus S ⊆ T [P ] implies T [P ] = T [P ∪ S].

Conversely, assume P ≻− Q, S ⊆ Q ⊆ T , and P ∪ S ≻− T . Therefore
Q = Q[P ] ⊆ T [P ] and thus S ⊆ T [P ] and T [P ∪ S] = T . By (t+) we therefore
have T [P ∪S] = T [P ]. By definition P ≻− T [P ], and thus T = T [P ], i.e., P ≻− T ,
i.e., (T+) holds. �

In analogy to Lemma 3.3 we have the following

Fact 3.12. If (o2) holds, then (t+) implies (o4).

Proof. Assume (t+) and suppose S ∈ Q[P ]. Then Q[S] ⊆ Q[P ∪ S] = Q[P ],
i.e., (o4) holds �

Condition (A) is also easily translated to the language of generalized oriented
components:

Lemma 3.13. If ≻− satisfies (O) and (U) and (Q, P) 7→ Q[P ] is the corre-
sponding generalized opening, then (A) is equivalent to

(a) Q[P ] = (P ∪ Q)[P ] ∩ Q.

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 263



Proof. Suppose ≻− satisfies (A). The set Z[P ] is uniquely defined and by (o2)
Q[P ] ⊆ Z[P ] for all Q ⊆ Z and by (o1) we have Q[P ] ⊆ Z[P ], and thus
Q[P ] ⊆ Z[P ] ∩ Q. If Q ∪ P = Z then (A) implies P ≻− Z[P ] ∩ Q which in turn
guarantees Z[P ] ∩ Q ⊆ Q[P ]; hence Q[P ] = Z[P ] ∩ Q whenever P ∪ Q = Z.
Substituting Z = P ∪ Q establishes (a).

To see the converse set Z = P ∪Q and assume (a), i.e., Q[P ] = Z[P ]∩Q for
all Q satisfying Z \ P ⊆ Q ⊆ Z. By construction of the generalized oriented
components we have P ≻̇− Q[P ] and thus P ≻̇− Z[P ] ∩ Q for Z \ P ⊆ Q ⊆ Z. In
particular for Q ⊆ Z[P ] this implies P ≻̇− Q. On the other hand, P ≻̇− Q and
Q ⊆ Z implies Q ⊆ Z[P ]. Therefore P ≻− Q implies P ≻− Q′ for all Q′ with
Z \ P ⊆ Q′ ⊆ Q ⊆ Z[P ], i.e., condition (A) holds. �

In this form, property (a) lends itself to a simple intuitive interpretation. It
states that the generalized opening is completely defined by the (Q∪P)[P ], i.e.,
the oriented components Q[P ] with P ⊆ Q. This matches, of course, with the
observation in the previous section that separations are defined by Z = P ∪ Q
and P independent of the exact choice of Q. For later reference we finally
record a simple consequence of property (a):

Lemma 3.14. If (P, Q) → Q[P ] satisfies (o1) through (o4) and (a) then P \
Q[P ] = P \ Q′[P ] for Q \ P ⊆ Q′ ⊆ Q ∪ P.

Proof. We set Z = P ∪ Q and hence Z \ P ⊆ Q ⊆ Z. By isotony we have
P \ Z[P ] ⊆ P \ Q[P ] ⊆ P \ (Z \ P)[P ]) = P \ (Z[P ] ∩ (Z \ P)) = P \ Z[P ] ∪ P \
(Z \ P) = P \ Z[P ]; here the first equality uses (a). Thus P \ Q′[P ] does not
depend on the choice of Q′ between Z \ P = Q \ P ⊆ Q′ ⊆ P ∪ Q. �

3.4. Bijection. In order to show that there is a bijection between the produc-
tion relations satisfying (O), (U), (T+), and (A) and the separation relations

satisfying (S0), (S1), (SR1), and (SR2) it suffices to show that |̈ = φ(θ(|)) =|
or ≻̈− = θ(φ(≻−)) =|.

Consider the map 2X × 2X → 2X : (P, Q) 7→ Q(P) such that

(3.8) Q(P) = Q \
{

A ∈ 2X
∣

∣(A, B) ∈ S(P, Q)
}

= Q \ A∗

Lemma 3.15. The map (P, Q) 7→ Q(P) satisfies (o1), (o2), (o3), (a), (t+),
and thus also (o4).

Proof. (o1). Q(P) ⊆ Q follows directly from the definition of Q(P).
(o2). Suppose P ′ ⊆ P , A ∪ B = P ∪ Q, P ⊆ B, and A | B. Thus (A, B) ∈

S(P, Q). Set Y ′ = P ′ ∪ Q. By isotony, A ∩ Y ′ | B ∩ Y ′ and thus (A ∩
Y ′, B ∩ Y ′) ∈ S(P ′, Q). Therefore Y ′ ∩ A∗ := Y ′ ∩

⋃

{A|(A, B) ∈ S(P, Q)} =
⋃

{Y ′ ∩A|(A, B) ∈ S(P, Q)} ⊆
⋃

{Y ′ ∩A|(A∩Y ′, B∩Y ′) ∈ S(P ′, Q) =: Y ′ ∩Ã.
By definition, Q(P) = Q \ A∗ = Q \ (Q ∩ A∗) = Q \ (Y ′ ∩ A∗) where we have

used Q ⊆ Y ′. Analogously we have Q(P ′) = Q \ Ã = Q \ (Y ′ ∩ Ã). Therefore
Q(P ′) ⊆ Q(P).

Next consider Q′ ⊆ Q and set Y ′ = P ∪ Q′. From A ∪ B = P ∪ Q
and P ⊆ B we infer (A ∩ Y ′) ∪ B = P ∪ Q′ and A ∩ Q′ | B. There-
fore Q′ ∩ {A|(A, B) ∈ S(P, Q)} ⊆ {A ∩ Y ′|(A ∩ Y ′, B) ∈ S(P, Q′)} = Q′ ∩

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 264



Oriented components and their separations

{A|(A ∩ Y ′, B) ∈ S(P, Q′)} = Q′ ∩ {A|(A, B) ∈ S(P, Q′)}, which in turn
implies Q′(P) ⊆ Q(P). Therefore (o2) holds.

(a). We have Q(P) := Q \ A∗ = (Z \ A∗) ∩ Q = Z(P) ∩ Q = (P ∪ Q)(P)
because Z(P) = Z \ A∗, Q ⊆ Z and P ∪ Q = Z, and thus (a) is satisfied.

Before we proceed, we show that the sets Q(P) are separated from their
complements in Q. From A∗ | B∗, Z \ A∗ ⊆ B∗ and P ⊂ B∗ we obtain
P ∪Z \A∗ ⊆ B∗, which by isotony implies A∗ | P ∪Z \A∗. From Z(P) = Z \A∗

we have A∗ = Z \ Z(P) and thus Z \ Z(P) | Z(P) ∪ P . Isotony immediately
yields Q ∩ (Z \ Z(P)) | (Q ∩ Z(P)) ∪ P , which by (a) reduces to

(3.9) Q \ Q(P) | Q(P) ∪ P for all P, Q ∈ 2X.

(t+) Let R ⊆ Q(P) and set A := Q\Q(P) and B := Q(P)∪P . By equ.(3.9),
A | B is a separation with R ∪ P ⊆ B. Therefore Q(R ∪ P) ⊆ Q \ A = Q(P).
By (o2) we have Q(P) ⊆ Q(R ∪ P); therefore Q(R ∪ P) = Q(P).

(o3) Suppose that there is a separation A | C with A ∪ C = Z(P) ∪ P
and P ⊆ C. With B := Z \ Z(P) we have B | A ∪ C and thus by (SR1) also
A∪B | C, i.e., A∪(Z\Z(P)) | C. Since this separation by definition is contained
in S(P, Q), we have A∪(Z \Z(P)) ⊆ A∗ = Z \Z(P), i.e., A ⊆ Z \Z(P). Thus
A∩Z(P) = ∅. We conclude: (*) All separations A | B with A∪B = Z(P)∪P
and P ⊆ B satisfy A ∩ Z(P) = ∅.

The definition of (Z(P))(P) and (*) together imply Z(P) ⊆ (Z(P))(P).
Thus (o1) implies (Z(P))(P) = Z(P). Now consider Q(P) with P ∪ Q =
Z. From (a) we have Q(P) = Q ∩ Z(P) ⊆ Z(P) and thus Q(P) ∪ P = Z.
Now (a) implies with Q′(P) = Q′ ∩ Z(P) in particular also for Q′ = Q(P),
i.e., (Q(P))(P) = Q(P) ∩ Z(P). Since Q(P) ⊆ Z(P) by (o2), we arrive at
(Q(P))(P) = Q(P).

(o4). Property (t+) with R = Q(P) implies Q(Q(P) ∪ P) ⊆ Q(P) and thus
by isotony of Q( . ) we have Q(Q(P)) ⊆ Q(Q(P) ∪ P) ⊆ Q(P). Thus for any
S ⊆ Q(P), isotony also implies Q(S) ⊆ Q(Q(P)) ⊆ Q(P). �

Lemma 3.16. Let | satisfy (S0), (S1), (SR1), and (SR2), let ≻̇− be the derived
production relation with generalized oriented connected components (P, Q) 7→
Q[P ] and let (P, Q) 7→ Q(P) be the map defined in equ.(3.8). Then for all
P, Q ∈ 2X holds Q(P) = Q[P ].

Proof. By definition of Q(P) we have Q(P) = Q if and only if A∗ = ∅, i.e., iff
there is no separation A | B with P ∈ B and A 6= ∅, i.e., if and only if P ≻̇− Q.
By Thm. 3.9 (P, Q) 7→ Q(P) bijectively maps to a unique production relation,
which we have just seen is the same as P ≻̇− Q. The bijection between the
production relation ≻̇− and the generalized opening (P, Q) 7→ Q[P ] completes
the proof. �

Theorem 3.17. There is a bijection between production relations ≻− satisfying
(O), (U), (T+), and (A) and separation relations satisfying (S0), (S1), (SR1),
and (SR2).

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 265



Proof. It suffices to show that A |̈ B if and only if A | B. The fact that | and
≻̇− are related by the Galois connection defined in equ.(3.3) then immediately
implies the theorem.

Suppose A |̈ B. For A = ∅ we trivially have A | B. Thus assume A 6= ∅ and

set Y = A ∪ B. From A |̈ B we know that P ≻̇− Q with P ⊆ B and P ∪ Q ⊆ Y
must satisfy Q ∩ A = ∅. In particular, the corresponding generalized oriented
components satisfy Q(P) ∩ A = ∅ for all P ⊆ B and Q ⊆ Y in particular
Y (B) ∩ A = ∅. By equ.(3.9) we have Y \ Y (B) | Y (B) ∪ B. From A ⊆ Y and
Y (B) ∩ A = ∅ we conclude A ⊆ Y \ Y (B) and thus, by (S1) A | Y (B) ∪ B and
finally A | B.

Conversely, assume A | B. Lemma 3.16 implies that the generalized con-

nected components w.r.t. ≻̇− are given by equ.(3.8). Now suppose A |̈ B does not
hold. Then there is a P ≻̇− Q with P ∪Q ⊆ A∪B, P ⊆ B, and Q∩A 6= ∅. This
is impossible, however, since by construction A ∩ Y (B) = ∅ and Q ⊆ Y (B).

Thus A |̈ B. �

We recall, finally, that axiom (A) means that (P, Q) → Q[P ] and hence the
relation ≻− is uniquely defined by the P ≻− Q or Q[P ] with P ⊆ Q. In other
words, we might want to restrict the definition of production relations ≻− and
of generalized oriented components Q[P ] to the domain {(P, Q)|P ⊆ Q ⊆ X}.
In this condition axiom (A) becomes void and thus can be omitted.

4. Properties of Separation and Production Relations

Throughout this section we assume | and ≻− are connected by their natural
bijection (3.3) and that the Q[P ] are the equivalent generalized oriented com-
ponents. In particular, | satisfies (S0), (S1), (SR1), and (SR2), ≻− satisfies (O),
(U), (A), (T+), and (P, Q) 7→ Q[P ] satisfies (o1), (o2), (o3), (t+), and (a).
Recall that axioms (o4) and (T), resp., also hold by Lemma 3.3 and Fact 3.12.

4.1. The Membership Property.

Theorem 4.1. The following three conditions are equivalent

(SR0) A | B implies A ∪ B | A ∩ B.
(m) If P ⊆ Q then P ′ ⊆ P \ Q[P ] implies Q[P ′] = ∅.
(M) P ≻− Q, P ′ ≻− Q′, P ′ ⊆ P \ Q, and Q′ ⊆ Q implies Q′ = ∅.

Proof. Suppose (SR0) holds, A | B and Z = A ∪ B. We have B ≻− Z[B] and
thus Z[B]∩A = ∅, i.e., Z[B] ⊆ B \ A = Z \ A. Furthermore, let {Ai|i ∈ I|} be

the family of sets with Ai ∪ B = Z and Ai | B and set  =
⋃

i∈I
Ai. By (SR2)

we have  | B. From Z[B] ∩ Ai = ∅ for all I and Z \ Z[B] | Z[B], which is a

special case of equ.(3.9), we conclude  = Z \ Z[B]. By (SR0) A ∪ B | A ∩ B,
i.e., for every P ′ ⊆ A∩B holds Z[P ′]∩(A∪B) = Z[P ′]∩Z = ∅, i.e., Z[P ′] = ∅.

This is true in particular also for all P ′ ⊆ Â ∩ B = B ∩ (Z \ Z[B]) = B \ Z[B].
By lemma 3.14 we have B \ Z[B] = B \ Q[B], i.e., P ′ ∈ B \ Q[B] implies
Q[P ′] = Z[P ′] = ∅.

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 266



Oriented components and their separations

Conversely, suppose (m) holds but there is a pair A | B such that A ∪ B |
A∩B does not hold, i.e., there is a point y ∈ A∪B = Z and a P ′ ∈ A∩B with
y ∈ Q[P ′] for some Q ⊆ Z. From A | B we have Q[B] ⊆ B \ A. Since A | B we
have A ⊆ Z \ Z[B] and thus P ′ ⊆ A ∩ B ⊆ B ∩ (Z \ Z[B]) = B ⊆ Z[B]. Now
property (m) implies Z[P ′] = ∅. Since Q[P ′] ⊆ Z[P ′] we arrive at the desired
contradiction.

Suppose (m) holds, P ≻− Q, P ′ ≻− Q′, P ′ ⊆ P \ Q[P ], and Q ⊆ Q′. Then by
definition, Q = Q[P ] and Q′ = Q′[P ′]. Isotony implies Q′[P ′] ⊆ Q[P ′]. By (m)
Q[P ′] = ∅ and thus Q′ = ∅, i.e., (M) holds.

Finally, suppose (M) holds. Consider P ′ ⊆ P \ Q[P ] and suppose P ′ ≻− Q′

for some Q′ ⊆ Q. By definition of generalized connected components, Q′ ⊆
Q[P ′] ⊆ Q. From P ≻− Q[P ′] and (M) we conclude Q[P ′] = ∅, i.e., (m)
holds. �

We shall see below that (m) corresponds to the “membership condition”
employed in [22] in the context of oriented components: “p /∈ Q[{p}] implies
Q[{p}] = ∅” for p ∈ Q. Property (SR0), on the other hand, appeared in [26]
as a condition for the existence of a bijection between connected components
and symmetric separations.

4.2. The Point Source Property. Ronse’s [22] work on oriented components
can be embedded into the current framework by assuming that reachability
from individual points completely specifies the production map. This property,
which we call here the point source property is most easily expressed in terms
of generalized oriented components as Q[P ] =

⋃

p∈P
Q[{p}].

Theorem 4.2. The following three conditions are equivalent

(SR2+) Let Ai ∪ Bi = Z and Ai | Bi for all i ∈ I. Then
⋂

Ai |
⋃

Bi.
(D) If P ≻− Q and Q is maximal in P ∪ Q then there are {p} ≻− Qp for

p ∈ P such that
⋃

p∈P
Qp = Q.

(d) If P ⊆ Q then Q[P ] =
⋃

p∈P
Q[{p}].

Proof. (d)=⇒(SR2+). Suppose (d) holds, Ai ∪ Bi = Z and Ai | Bi for all
i ∈ I. From Ai | Bi we known that for every P ⊆ Bi we have, for every
Q ⊆ Z, Q[P ] ∩ Ai = ∅ and thus in particular also Q[{p}] ∩ Ai = ∅. For
every p ∈

⋃

i∈I
Bi we therefore have Q[{p}] ∩

⋂

i∈I
Ai = ∅ and thus by (d)

Z[P ]∩
⋂

i∈I
Ai = ∅ and therefore also Q[P ]∩

⋂

i∈I
Ai = ∅ for all P ⊆

⋃

i∈I
Bi,

and thus
⋂

i∈I
Ai |

⋃

i∈I
Bi.

(SR2+)=⇒(d). Fix Z and P ⊆ Z. Choose I so that Bi = {p} and Ai =
Z\Z[{p}] for some p ∈ P . We have shown in the proof of Lemma (3.15) that Z\
Z[P ] | Z[P ]∪P . Therefore Ai | Bi holds, and hence by (SR2+), also

⋂

p∈P
(Z \

Z[P ]) |
⋃

p∈P
Z[{p}], i.e., Z \

⋃

p∈P
Z[{p}] |

⋃

p∈P
Z[{p}]. Furthermore we

know that P ≻−
⋃

p∈P Z[{p}] by (U). By equ.(3.9) we have Z \
⋃

p∈P Z[p] |

P ∪
⋃

p∈P
Z[{p}]. Now P ≻− Z[P ] implies Z[P ] ∩ Z \

⋃

p∈P
Z[{p}] = ∅, i.e.,

Z[P ] ⊆
⋃

p∈P
Z[{p}], i.e., Z[P ] =

⋃

p∈P
Z[{p}]. Since Z = Q for P ⊆ Q, (d)

follows.

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 267



(D)=⇒(d). Suppose P ≻− Z and assume that Z is maximal in P ∪ Z. Thus
Z = (P ∪ Z)[P ]. Set Q = P ∪ Z. By construction Z = Q[P ]. Property (D)
implies that there are Qp with {p} ≻− Qp and Qp ⊆ Q such that

⋃

p∈P
Qp =

Q[p]. We have Qp ⊆ Q[{p}] ⊆ Q and thus Q[P ] =
⋃

p∈P
Qp ⊆

⋃

p∈P
Q[p] ⊆

Q[P ], and hence Q[P ] =
⋃

p∈P
Q[p] whenever P ⊆ Q, i.e., (d) holds.

(d)=⇒(D) We may assume P ⊆ Q, thus Q[P ] is the maximal set in Q∪P = Q
satisfying P ≻− Q. We simply choose Qp = Q[{p}]. By construction {p} ≻− Qp
and Q[P ] =

⋃

p∈P
Q[{p}] =

⋃

p∈P
Qp. �

Property (a) now implies Q[P ] =
⋃

p∈P
(Q ∪ P)[{p}] ∩ Q whenever P 6⊆ Q.

In general we only have

(4.1)
⋃

p∈P

Q[{p}] ⊆ Q[P ]

Equality is guaranteed only if P ⊆ Q.

Lemma 4.3. The following three axioms are equivalent for separation rela-
tions, production relations and generalized connected components satisfying the
conditions of Thm. 3.17.

(S0+) A | ∅ for all A ∈ 2X.
(G) ∅ ≻− Q implies Q = ∅.
(g) Q[∅] = ∅.

Proof. Suppose (S0+) holds, i.e., A ∩ Q = ∅ for all A ∈ 2X and all Q such
that ∅ ≻− Q. Thus Q = ∅, i.e. (G) follows. Conversely suppose G holds. Then
A | ∅ follows since A ∩ Q = ∅ for Q = ∅. �

Fact 4.4. Axiom (d) implies axiom (g).

Proof. Q[∅] =
⋃

p∈∅
Q[{p}] = ∅. �

Lemma 4.5. If (d) holds, then (t) implies (t+).

Proof. Suppose R ∈ Q[P ]. Then
Q[P ∪ R] =

⋃

p∈P ∪R
(P ∪ Q)[{p}] ∩ Q ⊆

⋃

p∈P
((P ∪ Q)[{p}] ∩ Q) ∪

⋃

r∈R ((P ∪ Q)[{r}] ∩ Q) = (P ∪ Q)[P ] ∩ Q = Q[P ] because, by (t),
(P ∪ Q)[{r}] ⊆ (P ∩ Q)[P ] for all r ∈ Q[P ]. Thus (t+) holds. �

4.3. Reaches. A reach [22] is a family R ⊆ 2X × X satisfying the following
three axioms:

(r1) Let F ⊆ 2X and (F, p) ∈ R for all F ∈ F. Then (
⋃

F ∈F
F, p) ∈ R.

(union property)
(r2) If (Q, p) ∈ R, s ∈ Q, and (T, s) ∈ R then (Q ∪ T, p) ∈ R. (transitivity)
(r3) If (p, F) ∈ R then F = ∅ or p ∈ F . (membership property)

As shown in [22] there is a bijection of set systems satisfying (r1) and systems
of point openings, that is, maps 2X × X → 2X, (F, p) 7→ F(p) satisfying the
following three axioms for all p ∈ X and all F, F ′ ∈ 2X:

(p1) F(p) ⊆ F ,

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 268



Oriented components and their separations

(p2) F ′ ⊆ F implies F ′(p) ⊆ F(p),
(p3) (F(p))(p) = F(p),

The bijection is established by virtue of

F(p) :=
⋃

{S|(S, p) ∈ R and S ⊆ F}

R = {(F, p)|F = F(p)} .
(4.2)

Now consider a production relation ≻− satisfying (O), (U), (D), and (A)
and the corresponding generalized opening. In this case Q[P ] is completely
determined by the Q[{p}] with p ∈ Q. We can think of the Q[{p}] as a point
opening. Axiom (a) specializes to

(pa) If p /∈ F then F(p) = (F ∪ {p})(p) \ {p}.

and uniquely defines the sets F(p) whenever p /∈ F . An equivalent condition is

(ra) If p ∈ F and (F, p) ∈ R then (F \ {p}, p) ∈ R.

We call a set system R ⊆ 2X × X a pre-reach if it satisfies (r1) and (ra).
We note here that this construction differs from the definition in [22], where

F(p) = ∅ is stipulated for p /∈ F . In either case, however, (F, p) 7→ F(p)
is uniquely determined by the subset {(F, p)|p ∈ F} on which [22] and our
definition does agree. Therefore there is an obvious 1-1 correspondence.

Lemma 4.6. There is a bijection between pre-reaches, i.e., set systems R on
2X × X satisfying (r1) and (ra) and production relations ≻− on 2X satisfying
(O), (U), (A), and (D), by virtue of (F, p) ∈ R if and only if {p} ≻− F.

Proof. It is easier to argue in terms of the openings F(p) and the generalized
oriented components Q[P ], respectively. First we recall that Q[P ] is uniquely
determined by (Q ∪ P)[P ] through property (a), i.e., the Q[P ] with P 6⊆ Q
are determined by those with P ⊆ Q. For the latter, however, property (d)
implies that they are uniquely determined by the Q[{p}] with p ∈ Q. If p /∈ Q,
property (a) again determines Q[{p}]. Since (a) coincides with (ra) for |P | = 1,
it extends to equality F(p) = F [{p}] to all p ∈ X. It follows that F(p) = F [{p}]
induces a bijection between openings satisfying (ra) and generalized openings
satisfying (a) and (d). Indeed (o1), (o2), and (o3) trivially specialize to (p1),
(p2), and (p3).

It remains to show that (p1), (p2), and (p3) together with (d) implies (o1),
(o2), and (o3). For P ⊆ Q we have Q[P ] =

⋃

p∈P
Q[{p}] ⊆ Q and otherwise

Q[P ] = (Q ∪ P)[P ] ∩ Q ⊆ Q, i.e., (o1) holds.
Next suppose P ′ ⊆ P and Q′ ⊆ Q. By (ii) we have (Q′ ∪ P ′)[p] ⊆ (Q ∪ P)[p].
Therefore Q′[P ′] = (Q′ ∪P ′)[P ′]∩Q′ = Q′ ∩

⋃

p∈P ′
(Q′ ∪P ′)[p] ⊆ Q∩

⋃

p∈P
(Q∪

P)[p] = Q ∩ (Q ∪ P)[P ] = Q[P ], i.e. (o2) holds.
In particular, we have (Q[{p}])[{p}] ⊆ (Q[P ])[{p}] ⊆ (Q[P ])[P ] for all p ∈ P
and therefore also

⋃

p∈P
(Q[p])[{p}] ⊆ (Q[P ])[P ]. Now suppose P ⊆ Q. Then

(d) implies Q[P ] =
⋃

p∈P
Q[{p}] and (p3) implies Q[P ] =

⋃

p∈P
(Q[{p}])[{p}]

and therefore Q[P ] ⊆ (Q[P ])[P ]. Now (o2) implies the desired equality Q[P ] =
(Q[P ])[P ]. Finally, if P 6⊆ Q we have (Q[P ])[P ] = (Q[P ] ∪ P)[P ] ∩ Q[P ] =

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 269



((Q∪P)[P ]∩Q)[P ]∩Q[P ] By (o2) ((Q∪P)[P ])[P ]∩Q[P ] ⊆ ((Q∪P)[P ]∩Q)[P ].
On the other hand ((Q ∪ P)[P ])[P ] ∩ Q[P ] = (Q ∪ P)[P ] ∩ Q[P ] = Q[P ], and
thus Q[P ] ⊆ (Q[P ])[P ]. Thus (o3) holds. �

A family R ⊆ 2X × X is transitive if

(rt) (F, p) ∈ R, q ∈ F and (G, q) ∈ R implies (F ∪ G, p) ∈ R.

It is shown in [22] that if R satisfies (r1), then (rt) is equivalent to

(pt) q ∈ F(p) implies F(q) ⊆ F(p)

for the corresponding system of point openings. In our setting we have the
following, analogous result:

Lemma 4.7. Let ≻− be a production relation satisfying (O), (U), and (D) and
let R be the corresponding pre-reach. Then (r2) is equivalent to (T) and (T+).

Proof. Specializing (T) to single point sources yields {p} ≻− Q, s ∈ Q, and
{s} ≻− T implies {p} ≻− Q ∪ T , which translates to (Q, p) ∈ R, s ∈ Q, and
(T, s) ∈ R implies (Q ∪ T, p) ∈ R, i.e, (r2). Now suppose {p} ≻− Qp for all
p ∈ P , S ⊆ Q = ∪p∈P Qp and s ≻− Ts for s ∈ S. Then P ≻− Q, and for
every s ∈ S there is p such that s ∈ Qp and therefore {p} ≻− Qp ∪ Ts. Using
T =

⋃

s∈S
Ts and thus by (U) S ≻− T , and applying (U) again yields P ≻− Q,

S ⊆ Q and S ≻− T implies P → Q ∪ T , i.e., (T) holds. Finally, by Lemma 4.5
(D) and (T) imply (T+). �

In the presence of (r1), it is shown in [22] that (r3) is equivalent to p ∈ Q(p)
or Q(p) = ∅. This condition obviously clashes with (pa). The reason is
that for p /∈ Q, [22] stipulates Q(p) = ∅, while we have made another choice
with condition (pa), which in turn is motivated by (A). Instead, we use the
specialization of (m) to singleton sets P :

(pm) If p ∈ Q then p ∈ Q(p) or Q(p) = ∅

To see that (pm) is the proper specialization of (m) we simply note that for
P ′ = P = {p} we have P ′ ⊆ P \ Q[P ] = {p} ⊆ {p} \ Q[{p}] which translates to
p /∈ Q[{p}].

Lemma 4.8. Let ≻− be a production relation satisfying (O), (U), (A) and (D)
and let R be the corresponding pre-reach. Then (M) and (pm) are equivalent.

Proof. We first show that (m) reduces to (pm) for P = {p}. Assume p ∈ Q. If
p ∈ Q[{p}] then P ′ = ∅; otherwise P ′ = {p} = P and thus p /∈ Q[{p}]. Now
(m) implies Q[P ′] = Q[{p}] = ∅, and hence (pm) follows.

Conversely, suppose (pm) holds and suppose P ⊆ Q. Then by (d) Q[P ] =
⋃

p∈P
Q[{p}]. Let P̄ = P \ Q[P ]. Then for p′ ∈ P̄ holds p′ /∈ Q[P ] and thus

also p′ /∈ Q[{p′}], hence (pm) implies Q[{p′}] = ∅. By (d) we have Q[P̄] =
⋃

p′∈P̄
Q[{p′}] = ∅. Isotony now implies Q[P ′] = ∅ for all P ′ ⊆ P \ Q[P ], i.e.,

(m) holds. �

We can summarize this discussion in this section in the following form:

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 270



Oriented components and their separations

Corollary 4.9. There is a bijection between the generalized oriented compo-
nents satisfying (o1), (o2), (o3), (o4), (m), (a), and (d) and the system of
point openings satisfying (p1), (p2), (p3), (pt), (pm), and (pa). The latter co-
incides for p ∈ Q with the system of point openings that is equivalent to reaches
in the sense of Ronse [22].

Proof. The first statement is a direct consequence of Lemmas 4.6, 4.7, and 4.8.
By virtue of (pa) and the choice made in [22] to set Q(p) = ∅ whenever p /∈ Q,
the system of point openings is completely defined by (Q, p) 7→ Q(p) for p ∈ Q.
Here Q(p) = Q[{p}], i.e., the bijection is just the identity on this subset. �

Finally, we can relate reaches to separation spaces:

Corollary 4.10. There is a bijection between the generalized oriented compo-
nents satisfying (o1), (o2), (o3), (o4), (m), (a), and (d) and separation spaces
satisfying (S0), (S0+), (S1), (SR0), (SR1), (SR2), and (SR2+). The same is
true for the reaches as defined in [22].

This result directly generalizes the 1-1 correspondence between connectivity
spaces and symmetric separations satisfying the same axioms [26]. We will
return to this point in section 4.5.

4.4. Disjunctiveness. Consider the following properties:

(S3) A | B implies A ∩ B = ∅.
(P) P ≻− P for all P ∈ 2X.
(p) P ⊆ Q implies P ⊆ Q[P ].

Lemma 4.11. Suppose | and ≻− are corresponding separation and production
relations, and let {Q[P ]} be the corresponding system of generalized oriented
components. Then (S3), (P), and (p) are equivalent.

Proof. Suppose A | B. By assumption, we have in particular B ≻− B. It follows
immediately that B ∩ A = ∅.

Conversely, assume A | B implies A ∩ B = ∅ and suppose P ≻− P does not
hold for some P ∈ 2X. Then there is A | B such that P ⊆ B and P ∩ A 6= ∅,
whence A ∩ B 6= ∅, a contradiction.

Suppose P ⊆ Q. From P ≻− P we immediately conclude P ⊆ Q[P ]. Con-
versely, consider P ⊆ P [P ]. By isotony we have P [P ] ⊆ P and therefore
P = P [P ] and thus P ≻− P . �

Lemma 4.12. Suppose (p) holds. Then (m) is equivalent to (g) and, equiva-
lently, (SR0) reduces to (S0+).

Proof. Since P ⊆ Q[P ] for all P ⊆ Q, we have P ′ = P \ Q[P ] = ∅. Thus
(m) reduces to Q[∅] = ∅, i.e., axiom (g). Analogously, we can argue that (S3)
simplifies (SR0) to A | B implies A ∪ B | ∅. By (S0) we have ∅ | B and thus
B | ∅ for all B ∈ 2X. �

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 271



4.5. Symmetry Axioms. The natural symmetry axiom for separations is

(S2) A | B implies B | A.

Lemma 4.13. Suppose | satisfies (S2). Then (S0) and (S0+), (SR2) and
(SR2+) are equivalent. Furthermore, (S2) and (SR2) implies (SR0).

Proof. ∅ | A implies A | ∅ for all A ∈ 2X and vice versa.
Suppose Ai | Bi for all ∈ I and (SR2) holds. Then by (S2) Bi | Ai. (SR2)

ensures
⋃

i∈I
Bi |

⋂

i∈I
Ai. Using (S2) again we also have

⋂

i∈I
Ai |

⋃

i∈I
Bi,

i.e., (SR2+) holds. The implication in the other direction is shown analogously.
Finally, if A | B then by (S2) also B | A. Applying (SR2) with Z = A ∪ B,

A1 = A, B1 = B, A2 = B, and B2 = A results in A ∩ B | B ∩ A, i.e., (SR0)
holds. �

As shown in [26], there is a bijection between the “partial connections” of
[21] and separation spaces satisfying (S0), (S1), (S2), (SR0), (SR1), and (SR2).
Equivalent constructions have been considered e.g. in [23, 7, 4, 17, 6], see [26]
for a detailed overview. Lemma 4.13 above shows that the (SR0) axiom thus
is redundant in [26] and can simply be omitted. The (S2) axiom, via (SR0)
and (SR2+) implies both the membership property (M) and point definedness
(D) for the corresponding production relation and the generalized oriented
components, i.e., the (S2) axiom takes us automatically to the reaches of [22].
The symmetry condition for the corresponding oriented components can be
paraphrased in our notation as

(s) If p ∈ Q and r ∈ Q[{p}] then Q[{p}] ⊆ Q[{r}].

By (o4) we have Q[{r}] ⊆ Q[{p}] for r ∈ Q[{p}], and thus under our general
assumptions axiom (s) is equivalent to Q[{p}] = Q[{r}].

Lemma 4.14. (S2) is equivalent to (m), (d), and (s).

Proof. Suppose (S2) holds. By lemma 4.13 we have (SR2+) and (SR0), and
thus (m) and (d). In particular either x ∈ Q[{x}] or Q[{x}] = ∅ for all x ∈ X.
Suppose p ∈ Q and r ∈ Q[{p}]; by (o4) this implies Q[{r}] ⊆ Q[{p}]. Now
there are two cases to consider.
(1) If p ∈ Q[{r}] then (o4) implies Q[{p}] ⊆ Q[{r}], and thus Q[{r}] = Q[{p}].
(2) Otherwise p /∈ Q[{r}]. By equ.(3.9) we have Q \ Q[{r}] | Q[{r}] and by
(S2) also Q[{r}] | Q \ Q[{r}]. Since p ∈ Q \ Q[{r}], the correspondence of
separation and generalized oriented components implies Q[{p}] ∩ Q[{r}] = ∅.
The assumption r ∈ Q[{p}] thus implies r /∈ Q[{r}] and thus by (m) Q[{r}] = ∅
and therefore Q | {r}. Using (S2) again implies {r} | Q and thus p ∈ Q implies
Q[{p}] ∩ {r} = ∅, i.e., r /∈ Q[{p}], a contradiction. Thus r ∈ Q[{p}] implies
p ∈ Q[{r}].

Conversely, suppose (m), (d), and (s) hold. Suppose (S2) does not hold, i.e.,
there is A | B with A ∪ B = Q but B | A does not hold. Then for all p ∈ B
holds Q[{p}] ∩ A = ∅ and there is some y ∈ A such that Q[{y}] ∩ B 6= ∅.
Consider x ∈ B ∩ Q[{y}]. From x ∈ B we infer Q[{x}] ∩ A = ∅. On the other
hand, axiom (s) implies Q[{x}] = Q[{y}] and thus Q[{y}] ∩ A = ∅, whence

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 272



Oriented components and their separations

y /∈ Q[{y}]. Now (m) implies Q[{y}] = ∅, a contradiction. Thus (S2) must
hold. �

The axiom for production relations corresponding to (s) is

(S) If {p} ≻− S then q ≻− S for all q ∈ S.

If ≻− corresponds to a reach, i.e., in addition to (O), (U), (T), and (A) we also
have (D) and (M), then (S) is equivalent to (s) for the corresponding system
of generalized oriented components [22].

Concluding Remarks

We have shown here that production relations are in 1-1 correspondence with
a class of proximity spaces satisfying simple, rather natural axioms. This estab-
lishes a natural topological interpretation of directed hypergraphs in general
and chemical reaction networks in particular. The usefulness of this corre-
spondence is further supported by the equivalence of simple properties in both
axiom systems.

Many open questions remain for future research. The natural morphisms
between proximity spaces, proximal maps f : (X, δ ) → (Y, δ ), preserve
proximity, i.e., A δ B implies f(A) δ f(B). It will be interesting to investigate
the properties of the corresponding maps for production relations. These should
be related to the “catenous functions” introduced in [17]. On this basis one can
hope to investigate the natural product structures. This might be interesting
for production relations defined on Cartesian products such as the sequence
spaces (Hamming graphs) typically used to model molecular evolution.

The Wallace closure w : 2X → 2X associated with a proximity is usually
defined as x ∈ w(B) iff {x} δ B. The Wallace closure can be viewed as a
generalization of Kuratowski’s closure function for topologies. We will explore
this connection to generalized topologies in forthcoming work. Such closure
functions have been used as an alternative way of associating a topological
structure with chemical reaction networks [2]. Exactly how this approach is
connected with the production relations used here remains to be explored in
the future.

Acknowledgements. BMRS gratefully acknowledges the hospitality of the

Santa Fe Institute, where much of this work has been performed.

References

[1] J. L. Andersen, C. Flamm, D. Merkle and P. F. Stadler, Generic strategies for chemical
space exploration, Int. J. Comp. Biol. Drug Design 7 (2014), 225–258.

[2] G. Benkö, F. Centler, P. Dittrich, C. Flamm, B. M. R. Stadler and P. F. Stadler, A
topological approach to chemical organizations, Alife 15 (2009), 71–88.

[3] G. Berry, The chemical abstract machine, Theor. Comp. Sci. 96 (1992), 217–248.

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 273



[4] R. Börger, Connectivity spaces and component categories, in: H. L. Bentley, H. Herrlich,
M. Rajagopalan, H. Wolff (Eds.), Categorical topology, Vol. 5 of Sigma Ser. Pure Math.,
Heldermann, Berlin, 1983, pp. 71–89, Proceedings of the International Conference held
at the University of Toledo, Ohio, U.S.A., August 1–5, 1983.

[5] M. Changat and J. Mathew, Induced path transit function, monotone and Peano axioms,
Discrete Math. 286 (2004), 185–194.

[6] S. Dugowson, Les frontières dialectiques, Math. Social Sci. 177 (2007), 87–152.
[7] M. Erné and R. Vainio, Connectivity in lattice-ordered spaces, Math. Nachr. 147 (1990),

13–28.
[8] L. G. Fearnley, M. J. Davis, M. A. Ragan and L. K. Nielsen, Extracting reaction networks

from databases – opening Pandora’s box, Brief Bioinform. 15 (2014), 973–983.
[9] C. Flamm, B. M. R. Stadler and P. F. Stadler, Saddles and barrier in landscapes of

generalized search operators, in: C. R. Stephens, M. Toussaint, D. Whitley, P. F. Stadler
(Eds.), Foundations of Genetic Algortithms IX, Vol. 4436 of Lecture Notes Comp. Sci.,
Springer, Berlin, Heidelberg, 2007, pp. 194–212, 9th International Workshop, FOGA
2007, Mexico City, Mexico, January 8-11, 2007.

[10] C. Flamm, B. M. R. Stadler and P. F. Stadler, Generalized topologies: hypergraphs,
chemical reactions, and biological evolution, in: S. C. Basak, G. Restrepo, J. L. Villave-
ces (Eds.), Advances in Mathematical Chemistry: With applications to chemoinformat-

ics, bioinformatics, drug discovery, and Predictive toxicology, Vol. 2, Bentham, Sharjah,
UAE, 2013, pp. 300–327.

[11] J. H. Holland, Adaptation in natural and artificial systems, University of Michigan Press,
Ann Arbor, MI, 1975.

[12] K. Klemm, J. Qin and P. F. Stadler, Geometry and coarse-grained representations of
landscapes, in: A. Engelbrecht, H. Richter (Eds.), Recent advances in the theory and
application of fitness landscapes, Vol. 6 of Emergence, Complexity, and Computation,
Springer-Verlag, Berlin, 2014, pp. 153–176.

[13] S. Leader, Local proximity spaces, Math. Annalen 169 (1957), 275–281.
[14] M. W. Lodato, On topologically induced generalized proximity relations, Proc. Amer.

Math. Soc. 15 (1964), 417–422.
[15] L. Mazo, N. Passat, M. Couprie and C. Ronse, Digital imaging: a unified topological

framework, J. Math. Imaging Vision 44 (2012), 19–37.
[16] H. M. Mulder, The Interval Function of a Graph, Vol. 132 of Math. Centre Tracts, Math.

Centre, Amsterdam, NL, 1980.
[17] J. Muscat and D. Buhagiar, Connective spaces, Mem. Fac. Sci. Eng. Shimane Univ.

Series B: Math. Sci. 39 (2006), 1–13.
[18] W. J. Pervin, On separation and proximity spaces, Amer. Math. Monthly 71 (1964),

158–161.
[19] I. Rechenberg, Evolutionstrategie: Optimierung Technischer Systeme nach Prinzipien

des Biologischen Evolution, Frommann-Holzboog Verlag, Stuttgart, 1973.
[20] C. Ronse, Set-theoretical algebraic approaches to connectivity in continuous or digital

spaces, J. Math. Imaging Vision 8 (1998), 41–58.
[21] C. Ronse, Partial partitions, partial connections and connective segmentation, J. Math.

Imaging Vis. 32 (2008), 97–125.
[22] C. Ronse, Axiomatics for oriented connectivity, Pattern Recognition Lett. 47 (2014),

120–128.
[23] J. Serra, Mathematical morphology for boolean lattices, in: J. Serra (Ed.), Image Anal-

ysis and Mathematical Morphology, Theoretical Advances, Vol. 2, Academic Press, Lon-
don, 1988, pp. 37–58.

[24] J. M. Smirnov, On proximity spaces, Mat. Sb. 31 (1952), 543–574.
[25] B. M. R. Stadler and P. F. Stadler, Generalized topological spaces in evolutionary theory

and combinatorial chemistry, J. Chem. Inf. Comput. Sci. 42 (2002), 577–585.
[26] B. M. R. Stadler and P. F. Stadler, Connectivity spaces, Math. Comp. Sci 9 (2015),

409–436.

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 274



Oriented components and their separations

[27] B. M. R. Stadler, P. F. Stadler, G. Wagner and W. Fontana, The topology of the possible:
Formal spaces underlying patterns of evolutionary change, J. Theor. Biol. 213 (2001),
241–274.

[28] O. Tankyevych, H. Talbot, N. Passat, Semi-connections and hierarchies, in: C. L. Lu-
engo Hendriks, G. Borgefors, R. Strand (Eds.), Mathematical Morphology and Its Ap-
plications to Signal and Image Processing, Vol. 7883 of Lect. Notes Comp. Sci., Springer,
Berlin, 2013, pp. 159–170.

[29] A. D. Wallace, Separation spaces, Ann. Math. 42 (1941), 687–697.
[30] S. Wright, The roles of mutation, inbreeding, crossbreeeding and selection in evolution,

in: D. F. Jones (Ed.), Proceedings of the Sixth International Congress on Genetics,
Vol. 1, 1932, pp. 356–366.

c© AGT, UPV, 2017 Appl. Gen. Topol. 18, no. 2 275