HTML reading edition · 84 source pages · Open the source PDF

Semiframes: the algebra of semitopologies and actionable coalitions

Murdoch J. Gabbay

arXiv:2310.00956v3 [cs.LO] 11 Oct 2025

MACS, Heriot-Watt University Edinburgh, UK www.gabbay.org.uk

Abstract

We introduce semiframes (an algebraic structure) and investigate their duality with semitopologies (a topological one). Both semitopologies and semiframes are relatively recent developments, arising from a novel application of topological ideas to study decentralised computing systems. Semitopologies generalise topology by removing the condition that intersections of open sets are necessarily open. The motivation comes from identifying the notion of an actionable coalition in a distributed system — a set of participants with sufficient resources for its members to collaborate to take some action — with open set; since just because two sets are actionable (have the resources to act) does not necessarily mean that their intersection is.

We define notions of category and morphism and prove a categorical duality between (sober) semiframes and (spatial) semitopologies, and we investigate how key well-behavedness properties that are relevant to understanding decentralised systems, transfer (or do not transfer) across the duality.

Keywords: Semitopology; Semiframes; Decentralised systems; Actionable coalitions; Categorical Duality

1. Introduction

This paper is about a duality between semiframes (an algebraic structure) and semitopologies (a topological one). We will define semiframes, study their duality with semitopologies, and also motivate and define relevant well-behavedness conditions on semitopologies and investigate how these conditions dualise to algebraic conditions on semiframes.

Both semitopologies and semiframes are relatively recent developments, arising from a novel application of topological ideas to study decentralised computing systems. So while this paper is about pure mathematics, and it can be read as mathematics for its own sake, it would be nice to understand the motivation for why we looked at these structures in the first place.

1.1 The challenge of decentralised systems

Consider a computing system whose operation is distributed over many collaborating participants, like a blockchain. At a high level, how can we design algorithms that participants can run such that the overall system will act coherently in some appropriate sense?

We could just assume a central controller; a dictator participant. In this case, ‘collaborating’ just means doing as the dictator instructs, and ‘truth’ just means whatever the dictator says.

This is indeed how many distributed systems actually work, but it introduces tradeoffs of latency, scalability, availability, and trust which may or may not be acceptable depending on the use case. Do we trust the dictator? What if it crashes, or gets hacked? What if the network is slow? What if it is just busy? Sometimes, we need participants to be able, to a greater or lesser extent, to collaborate independently of central control.

This is the topic of decentralised systems, which are distributed systems that do not adopt a central controller. Decentralised systems are hard to design and implement, because control itself is spread out,1 but often this is the only architecture that is practical at scale and speed.

While blockchains are an example of decentralised systems,2 these design issues arise repeatedly: e.g. if we want to manage a system of drones, or satellites, or low-power devices. An ant colony is an interesting example of a (semi-)decentralised system in nature: while a queen ant exists, she does not dictate every action of every ant; for much of the time, individual ants work autonomously, yet they still manage to do so coherently and for the good of the colony. The human brain is another important example of a decentralised system. These systems are all inherently decentralised: they maintain some clear notion of global coherence (e.g. there is an identifiable thing called ‘an ant colony’ or ‘my sense of self’) all while their parts collaborate to perform significant actions independently of any explicit central control.

This leads us to consider the concept of what in [18, 17] is called an actionable coalition: a set of participants in a decentralised system with sufficient resources to act (if the participants in the coalition choose to do so), without the involvement — i.e. without the help, the permission, or even the knowledge — of any other participants.3

Let us return to our ant colony and consider a column of foraging ants: what are the actionable coalitions here, where the ants’ task is to bring food back to the colony? When the column discovers some food, a relevant notion of actionable coalition is any collection of ants with the physical strength to heave the food back to the hive. Note that the ants do not need anybody to organise them into a group, or to tell them what to do: they swarm over the food until some group of them manage to move the food — aha; an actionable coalition has assembled and agreed on their action! — and then that coalition gets on with heaving while the rest of the ants move on.

When we describe an actionable coalition as “a group of participants with the resources to act”, note that — this being a decentralised system — the action concerns just participants in that coalition and not the entire set of participants. Contrast with e.g. a national voting system, which is distributed but still centralised in the sense that the winning candidate wins for everybody, not just for the people who voted for that candidate.4

A union of actionable coalitions is an actionable coalition.5 This makes the set of all actionable coalitions look a bit like a topology, except that an intersection of actionable coalitions need not be actionable (just because sets S and S′ are each collectively strong enough to act, does not mean that S ∩ S′ is; e.g. S ∩ S′ may consist of just a single ant).

This brings us to a mathematical abstraction: point-set semitopology, which generalises point-set topology by removing the condition that intersections of open sets are necessarily open:

1.2 Point-set semitopologies

Notation 1.2.1

Suppose P is a set. Write pow(P) for the powerset of P (the set of subsets of P).

Definition 1.2.2

A semitopological space, or semitopology for short, consists of a pair (P, Open(P)) of a (possibly empty) set P of points, and a set Open(P) ⊆ pow(P) of open sets, such that:

(1) ∅∈ Open(P) and P ∈ Open(P).

(2) If X ⊆ Open(P) then ⋃ X ∈ Open(P).6

We may write Open(P) just as Open, if P is irrelevant or understood, and we may write Open≠∅ for the set of nonempty open sets.

Remark 1.2.3 (Justification for semitopologies).

A classic text [52] justifies topology as follows:

(1) Logically, open sets model affirmations:7 an open set O corresponds to an affirmation (of O) [52, page 10].

(2) Computationally, open sets model semidecidable properties. See the first page of the preface in [52].

We can justify semitopologies in similar style as follows:

(1) Logically, open sets model actionable affirmations: an open set O corresponds to an outcome that is agreed on and can be actioned within O.

(2) Computationally, open sets model actionable outcomes.

So the distinction between topology and semitopology is this: topology is about things that can be positively said; whereas semitopology is about things that can be positively done.

Identifying actionable coalitions as a topological concept is new; but as is often the case for key concepts, with hindsight we can see them everywhere. The notion corresponds that of a quorum in the classic distributed systems literature [26]. Social choice theorists have a similar notion called a winning coalition [44, Item 5, page 40]. In blockchains, the XRP Ledger [48] and Stellar network [30] have explicit notions of actionable coalition, in the sense that a participant must specify information about their desired actionable coalitions when they sign up to the system. In Ethereum and other proof-of-stake blockchains, an actionable coalition is (roughly speaking) any group of participants with more than half of the voting power of the system.

1.3 Well-behavedness conditions on semitopologies

It turns out that we can understand a surprising amount about a decentralised system, just by analysing its actionable coalitions; i.e. by viewing it as a semitopology. And when we do, the most relevant and interesting semitopologies turn out to be ill-behaved from the usual topological viewpoint, because they are almost never Hausdorff; indeed the most well-behaved semitopologies satisfy an anti-Hausdorff property of being intertwined, that all of their open sets intersect.

This is because if all actionable coalitions intersect, then any two actions that are taken must be compatible, in the sense that there must exist at least one participant who was able to take both actions. This implies a practically useful form of coherence for the overall system: while it is not the case that participants must act in synchrony (since that would not be decentralised), any actions that are taken must be compatible on some nonempty overlap; we make this formal in Theorem 3.2.3 and Corollary 3.2.4. In practice, it turns out that this property is often enough to derive important coherence properties for the overall system.

Notions of transitive open set (topen) and regular point become central to the theory, where topens are sets of pairwise intertwined participants (all their open neighbourhoods intersect), and points are called ‘regular’ when they have a topen neighbourhood. Briefly and in a nutshell: ‘good’ semitopologies have lots of regular points, and the best ones consist entirely of regular points.

The question we should then as is: what are semitopologies, and what are well-behavedness properties like having topens and being regular?

One answer is that things are what the definitions define them to be — e.g. semitopologies are Definition 1.2.2 — but the reader may know that we can use algebra to give better answers. In particular, looking at Definition 1.2.2 it might appear that semitopologies are just complete join-semilattices in sets. Well, this is not quite true, as we shall see:

1.4 Semiframes: the algebraic dual to semitopologies

There is well-known recipe for understanding sets-based structures: we dualise them. That is: we decide what the morphisms should be (answer: continuous functions), we build a dual category of semiframes, and we study that.

It will turn out that a semiframe is a compatible complete semilattice. What ‘compatibility’ means is given in Definition 7.3.1 and it has to do with an algebraic abstraction of nonempty intersection of open sets. What we can observe here is that the devil will be in the details (as always): the definition ‘compatible complete semilattice’ is not immediately obvious, and the proofs require work, and the duals to the well-behavedness conditions on semitopologies translate to algebraic structure in the world of semiframes.

Studying the dualities between semitopologies and semiframes, and how well-behavedness properties on points translate (or do not translate!) to their algebraic duals, is the topic of the paper.

Remark 1.4.1 (Semitopologies are compatible complete join-semilattices in sets).

Something interesting will happen when we dualise semitopologies: we will find ourselves obliged to introduce the notion of a compatibility relation ∗ (Definition 7.2.1). This arises naturally twice:

• as a key technicality in our duality result, and also

• as an algebraic analogue of the intertwinedness property ≬ which we need to express well-behavedness properties such as regularity (Section 4).

It is interesting that ∗/≬ appears for two reasons that on the face of things have quite distinct origins: algebraically in the duality; and as a pragmatically motivated well-behavedness conditions on sets.

So a message of our study of duality is to corroborate that intertwinedness is both mathematically fundamental and practically useful, and that (as noted above) semitopologies are not just complete join semilattices in sets, but something a bit richer; namely compatible complete join-semilattices in sets.

1.5 Map of the paper

(1) Section 1 is the Introduction. You Are Here.

(2) In Section 2 we show how continuity corresponds to local agreement (Definition 1.2.2 and Lemma 2.2.4).

(3) In Section 3 we discuss transitive sets, topens, and intertwined points. These are all anti-separation well-behavedness properties; e.g. Transitive and topen sets are guaranteed to be in agreement, in a sense made precise in Theorem 3.2.3 and Corollary 3.2.4.

(4) In Section 4 we classify points in more detail, introducing notions of regular, weakly regular, and quasiregular points (Definition 4.1.4).8 Regular points are points contained in a topen set, and as per Theorem 3.2.3 they display good behaviour.

(5) In Section 5 we characterise regularity as regular = weakly regular + unconflicted: see Theorem 5.3.4.

(6) In Section 6 we characterise regularity as regular = quasiregular + hypertransitive: see Theorem 6.3.3. This completes our treatment of point-set semitopologies, and next we dualise, as follows:

(7) In Section 7 we introduce semiframes. These are the algebraic version of semitopologies, and they are to semitopologies as frames are to topologies. We discover that semiframes are not just join-semilattices; semiframes are compatible semilattices, which include a compatibility relation ∗ to abstract the property of sets intersection ≬ (see Remark 1.4.1).

(8) In Section 8 we introduce semifilters. These play a similar role as filters do in topologies, except that semifilters have a compatibility condition instead of closure under finite meets. We develop the notion of abstract points (completely prime semifilters), and show how to build a semitopology out of the abstract points of a semiframe.

(9) In Section 9 we introduce sober semitopologies and spatial semiframes. The reader familiar with categorical duality may be familiar with these conditions, though some details are significantly different from the topological case (see for instance the discussion in Subsection 9.3.2).

(10) In Section 10 we consider the duality between suitable categories of (sober) semitopologies and (spatial) semiframes.

(11) In Section 11 we dualise the well-behavedness conditions from Section 3 to algebraic versions. The correspondence is good (Proposition 11.6.2) but also imperfect in some interesting ways (Remark 11.8.11).

(12) In Section 12 we conclude and discuss related and future work.

1.6 Comments on the context of this research

Remark 1.6.1 (Algebraic topology ≠ semitopology and semiframes).

Algebraic topology has been applied to the solvability of distributed-computing tasks in computational models (e.g. the impossibility of k-set consensus and the Asynchronous Computability Theorem [22, 3, 47]; see [21] for a survey).

This paper is not that! Algebra and topology are versatile tools: this paper is algebraic and topological, but in different senses and to different ends.

Remark 1.6.2 (Where the interesting properties are).

Topology often studies spaces with strong separability properties between points, like Hausdorff separability. For our applications, the well-behavedness properties of semitopologies, and corresponding properties in semiframes, centre on clusters of points that cannot be separated.

For example, we state and discuss an ‘anti-Hausdorff’ anti-separation property which we call being intertwined (see Definition 3.5.1 and Remark 3.5.7). Within an intertwined set, continuity implies agreement in a particularly strong sense (see Corollary 3.5.6). This leads us to study classes of semitopologies and semiframes with various anti-separation well-behavedness conditions; see most notably regularity (Sections 4 and 11).

Remark 1.6.3

As the reader may know, frames and locales are the same thing: the category of locales is just the categorical opposite of the category of frames. So every time we write ‘semiframe’, the reader can safely read ‘semilocale’; these are two names for essentially the same structure up to reversing arrows.

The literature on frames and locales is huge, as indeed is the literature on topology. Classic texts are [24, 33]. More recent and very readable presentations are in [39, 40]. This literature is a rich source of ideas for things to do with semiframes, with respect to which we cannot possibly be comprehensive in this single paper: there are many things of interest that we simply have not done yet, or perhaps have not even (yet) realised could be done, and this is a feature, not a bug, since it reflects a wide scope for possible future research.

A partial list of possible future work is in Subsection 12.3; and lists of properties and non-properties of semiframes/semitopologies vs. frames/topologies are in Subsections 8.2.1, 8.2.2, 9.3.2, and 12.1.

Remark 1.6.4

This paper expands on selected material from a technical monograph [17], and it continues where a journal paper on point-set topologies [18] left off.

For this document to be meaningful and self-contained, we include some material on point-set semitopologies — just as a treatment of frames would define point-set topologies. The material has been organised, edited, and streamlined specifically to provide a direct route to semiframes and their duality.

Our goal for this paper is to offer an accessible, dedicated, and self-contained journal exposition on what is currently understood about semiframes and their relation to point-set semitopologies, in the context of current developments in decentralised systems.

Remark 1.6.5 (Who should read this paper?).

This work is aimed at the advanced researcher interested in a new kind of point-free topology, albeit one that is grounded in the practical needs of modern decentralised systems, and at the advanced practitioner interested in seeing what they may already be doing in a new (and more abstract) mathematical light.

I hope this paper will stimulate interest in compatible complete join-semilattices, and related structures, as an elegant abstraction of decentralised systems.

2. Semitopology

2.1 Definition and examples

2.1.1 Semitopologies are not topologies

Recall from Definition 1.2.2 the definition of a semitopology. As a sets structure, a semitopology on P is like a topology on P, but without the condition that the intersection of two open sets be an open set. This gives semitopologies their own distinct character, and we can see this before we have even developed much of the theory, as we discuss in Remark 2.1.1 and Lemma 2.1.2:

Remark 2.1.1

Every semitopology (P, Open) gives rise to a topology just by closing opens under intersections. But semitopologies are far more than just subbases for a corresponding topology:

(1) Completing a semitopology to a topology by closing under intersections, loses information. For example: the ‘many’, ‘all-but-one’, and ‘more-than-one’ semitopologies in Example 2.1.4 express three distinct notions of quorum, yet all three yield the discrete semitopology (Definition 2.1.3) if we close under intersections and P is infinite. See also the overview in Subsection 12.1.

(2) We are explicitly interested in situations where intersections of open sets need not be open, due to our motivating interpretation of open sets as actionable coalitions (as discussed in Section 1).

Much of the difference in flavour between topologies and semitopologies comes down to this:

Lemma 2.1.2

(1) In topologies, if a point p has a minimal open neighbourhood then it is least (= unique minimal).

(2) In semitopologies, a point may have multiple distinct minimal open neighbourhoods.

1 20
Figure 1. An example of a point with two minimal open neighbourhoods (Lemma 2.1.2)
Proof

To see that in a topology every minimal open neighbourhood is least, just note that if p ∈ A and p ∈ B then p ∈ A ∩ B. So if A and B are two minimal open neighbourhoods then A ∩ B is contained in both and by minimality is equal to both.

To see that in a semitopology a minimal open neighbourhood need not be least, it suffices to provide an example. Consider (P, Open) defined as follows, as illustrated in Figure 1:

• P = {0, 1, 2}

• Open ={ ∅, {0, 1}, {1, 2}, {0, 1, 2}}

Note that 1 has two minimal open neighbourhoods: {0, 1} and {1, 2}.End of proof

2.1.2 Examples

As standard, we can make any set Val into a semitopology (indeed, it is also a topology) just by letting open sets be the powerset:

Definition 2.1.3

(1) Call (P, pow(P)) the discrete semitopology on P.
We may call a set with the discrete semitopology a semitopology of values, and when we do we will usually call it Val. We may identify Val-the-set and Val-the-discrete-semitopology; meaning will always be clear.

(2) When (P, Open) is a semitopology and Val is a semitopology of values, we may call a function f : P → Val a value assignment.
Note that a value just assigns values to points, and in particular we do not assume a priori that it is continuous, where continuity is defined just as for topologies (see Definition 2.2.1).

Example 2.1.4

We consider further examples of semitopologies:

(1) Every topology is also a semitopology; intersections of open sets are allowed to be open in a semitopology, they are just not constrained to be open. In particular, the discrete topology is also a discrete semitopology (Definition 2.1.3(1)).

(2) The initial semitopology (∅, {∅}) and the final semitopology ({∗}, {∅, {∗}}) are semitopologies.

(3) An important discrete semitopological space is

B = {⊥, ⊤} with the discrete semitopology Open(B) = {∅, {⊥}, {⊤}, {⊥, ⊤}}.

We may silently treat B as a (discrete) semitopological space henceforth.

(4) Take P to be any nonempty set. Let the trivial semitopology (this is also a topology) on P have

Open = {∅, P}.

So (as usual) there are only two open sets: the one containing nothing, and the one containing every point.9 The only nonempty open is P itself, reflecting a notion of actionable coalition that requires unanimous agreement.

(5) Suppose P is a set and F ⊆ pow(P) is nonempty and up-closed (so if P ∈ F and P ⊆ P′ ⊆ P then P′ ∈ F , then (P, F ) is a semitopology. This is not necessarily a topology, because we do not insist that F is a filter (i.e. is closed under intersections). We give four sub-examples for different choices of P ⊆ pow(P):

a. Take P to be any finite nonempty set. Let the supermajority semitopology have

Open = {∅} ∪{O ⊆P | cardinality(O) ≥2/3 ∗cardinality(P)}.

So O is open when it contains at least two-thirds of the points.

Two-thirds is a typical threshold used for making progress in consensus algorithms.

b. Take P to be any nonempty set. Let the many semitopology have

Open = {∅} ∪{O ⊆P | cardinality(O) = cardinality(P)}.

For example, if P = N then open sets include evens = {2 ∗ n | n ∈N} and odds = {2 ∗ n+1 | n ∈N}.

Its notion of open set captures an idea that an actionable coalition is a set that may not be all of P, but does at least biject with it.

c. Take P to be any nonempty set. Let the all-but-one semitopology have

Open = {∅, P} ∪{P\{p} | p ∈P}.

This semitopology is not a topology.

The notion of actionable coalition here is that there may be at most one objector (but not two).

d. Take P to be any set with cardinality at least 2. Let the more-than-one semitopology have

Open = {∅} ∪{O ⊆P | cardinality(O) ≥2}.

This semitopology is not a topology. This notion of actionable coalition reflects a security principle in banking and accounting (and elsewhere) of separation of duties, that functional responsibilities be separated such that at least two people are required to complete an action — so that errors (or worse) cannot be made without being discovered by another person.

(6) Take P = R (the set of real numbers) and let open sets be generated by intervals of the form [0, r) or (-r, 0] for any strictly positive real number r > 0. This semitopology is not a topology, since (for example) (1, 0] and [0, 1) are open, but their intersection {0} is not open.

(7) In [37] a notion of quorum system is discussed, defined as any collection of pairwise intersecting sets. Quorum systems are key to the theory and practical implementation of consensus algorithms. Every quorum system gives rise naturally to the least semitopology that contains it, just by closing under arbitrary unions.
To give one specific example of a quorum system from [37], consider n × n grid of cells with quorums being sets consisting of any full row and a full column; note that any two quorums must intersect in at least two points. We obtain a semitopology just by closing under arbitrary unions.

2.2 Continuity, and its interpretation as agreement

Definition 2.2.1

We import standard topological notions of inverse image and continuity:

(1) Suppose P and P′ are any sets and f : P → P′ is a function. Suppose O′ ⊆ P′. Then write f -1(O′) for the inverse image or preimage of O′, defined by

f-1(O′) = {p∈P | f(p) ∈O′}.

(2) Suppose (P, Open) and (P′, Open′) are semitopological spaces (Definition 1.2.2). Call a function f : P → P′ continuous when the inverse image of an open set is open. In symbols:

∀O′ ∈Open′.f-1(O′) ∈Open.

(3) Call a function f : P → P′ continuous at p ∈ P when

∀O′∈Open′.f(p) ∈O′ =⟹∃Op,O′∈Open.p ∈Op,O′ ∧Op,O′ ⊆f-1(O′).

In words: f is continuous at p when the inverse image of every open neighbourhood of f(p) contains an open neighbourhood of p.

(4) Call a function f : P → P′ continuous on P ⊆ P when f is continuous at every p ∈ P.

Lemma 2.2.2

Suppose (P, Open) and (P′, Open′) are semitopological spaces (Definition 1.2.2) and suppose f : P → P′ is a function. Then the following are equivalent:

(1) f is continuous (Definition 2.2.1(2)).

(2) f is continuous at every p ∈ P (Definition 2.2.1(3)).

Proof

The top-down implication is immediate, taking O = f -1(O′).

For the bottom-up implication, given p and an open neighbourhood O′ ∋ f(p), we write

O =⋃ {Op,O′ ∈Open | p ∈P, f(p) ∈O′}.

Above, Op,O′ is the open neighbourhood of p in the preimage of O′, which we know exists by Definition 2.2.1(3).

It is routine to check that O = f -1(O′), and since this is a union of open sets, it is open.End of proof

Definition 2.2.3

Suppose that:

• (P, Open) is a semitopology and

• Val is a semitopology of values (Definition 2.1.3(1)) and

• f : P → Val is a value assignment (Definition 2.1.3(2); an assignment of a value to each element in P).

Then:

(1) Call f locally constant at p ∈ P when there exists p ∈ Op ∈ Open such that

∀p′∈Op.f(p) = f(p′).

So f is locally constant at p when it is constant on some open neighbourhood Op of p.

(2) Call f locally constant when it is locally constant at every p ∈ P.

Lemma 2.2.4

Suppose (P, Open) is a semitopology and Val is a semitopology of values and f : P → Val is a value assignment. Then the following are equivalent:

• f is locally constant / locally constant at p ∈ P (Definition 2.2.3).

• f is continuous / continuous at p ∈ P (Definition 2.2.1).

Proof

This is just by pushing around definitions, but we spell it out:

• Suppose f is continuous, consider p ∈ P, and write v = f(p). By our assumptions we know that f -1(v) is open, and p ∈ f -1(v). This is an open neighbourhood Op on which f is constant, so we are done.

• Suppose f is locally constant, consider p ∈ P, and write v = f(p). By assumption we can find p ∈ Op ∈ Open on which f is constant, so that Op ⊆ f -1(v).End of proof

Remark 2.2.5 (Continuity = agreement).

Lemma 2.2.4 tells us that we can view the problem of obtaining agreement across an actionable coalition (as discussed in Section 1) as being the same as obtaining a value assignment that is continuous (at least) on that coalition.

2.3 Neighbourhoods of a point

Definition 2.3.1 is standard from topology, and Lemma 2.3.2 is a (standard) characterisation of openness, which will be useful later:

Definition 2.3.1

Suppose (P, Open) is a semitopology and p ∈ P and O ∈ Open. Then:

(1) call O an open neighbourhood of p when p ∈ O.

(2) Define nbhd(p) ⊆ Open the neighbourhood system of p by

nbhd(p) = {O ∈Open | p ∈Open}.
Lemma 2.3.2

Suppose (P, Open) is a semitopology and suppose P ⊆ P is any set of points. Then the following are equivalent:

• P ∈ Open.

• Every point p in P has an open neighbourhood in P.

In symbols we can write:

∀p∈P.∃O∈Open.(p ∈O ∧O ⊆P) if and only if P ∈Open
Proof

If P is open then P itself is an open neighbourhood for every point that it contains.

Conversely, if every p ∈ P contains some open neighbourhood p ∈ Op ⊆ P then P = ⋃{Op | p ∈ P} and this is open by condition 2 of Definition 1.2.2.End of proof

Remark 2.3.3

An initial inspiration for modelling collaborative action using semitopologies, came from noting that the standard topological property described above in Lemma 2.3.2, corresponds to the quorum sharing property in [31, Property 1]; the connection to topological ideas had not been noticed in [31].

3. Transitive sets & topens

3.1 Some background on sets intersection

Some notation will be convenient:

Notation 3.1.1

Suppose X, Y, and Z are sets.

(1) Write

X ≬Y when X ∩Y ≠ ∅.

When X ≬ Y holds then we say (as standard) that X and Y intersect.

(2) We may chain the ≬ notation, writing for example

X ≬Y ≬Z for X ≬Y ∧Y ≬Z

(3) We may write X ≬̸Y for ¬(X ≬ Y), thus X ≬̸Y when X ∩ Y = ∅.

Remark 3.1.2

Note on design in Notation 3.1.1: It is uncontroversial that if X ≠ ∅ and Y ≠ ∅ then X ≬ Y should hold precisely when X ∩ Y ≠ ∅ — but there is an edge case! What truth-value should X ≬ Y return when X or Y is empty?

(1) It might be nice if X ⊆ Y would imply X ≬ Y. This argues for setting

(X = ∅∨Y = ∅) =⟹X ≬Y.

(2) It might be nice if X ≬ Y were monotone on both arguments (i.e. if X ≬ Y and X ⊆ X′ then X′ ≬ Y). This argues for setting

(X = ∅∨Y = ∅) =⟹X ≬̸Y.

(3) It might be nice if X ≬ X always — after all, should a set not intersect itself? — and this argues for setting

∅≬∅,

even if we also set ∅≬̸Y for nonempty Y.

All three choices are defensible, and they are consistent with the following nice property:

X ≬Y =⟹(X ≬X ∨Y ≬Y).

We choose the second — if X or Y is empty then X ≬̸Y — because it gives the simplest definition that X ≬ Y precisely when X ∩ Y ≠ ∅.

We list some elementary properties of ≬ from Notation 3.1.1(1):

Lemma 3.1.3

(1) X ≬ X if and only if X ≠ ∅.

(2) X ≬ Y if and only if Y ≬ X.

(3) X ≬ (Y ∪ Z) if and only if (X ≬ Y) ∨ (X ≬ Z).

(4) If X ⊆ X′ and X ≠ ∅ then X ≬ X′.

(5) Suppose X ≬ Y. Then X ⊆ X′ implies X′ ≬ Y, and Y ⊆ Y′ implies X ≬ Y′.

(6) If X ≬ Y then X ≠ ∅ and Y ≠ ∅.

Proof

By facts of sets intersection.End of proof

3.2 Transitive open sets and value assignments

Remark 3.2.1 (Taking stock of topens).

Transitive sets are of interest because values of continuous functions are strongly correlated on them. This is Theorem 3.2.3, especially part 2 of Theorem 3.2.3.

A transitive open set — a topen — is even more important, because an open set corresponds in our semitopological model to a quorum (a collection of participants that can make progress), so a transitive open set is a collection of participants that can make progress and are guaranteed to do so in consensus, where algorithms succeed.

For this and other reasons, we very much care about finding topens and understanding when points are associated with topen sets (e.g. by having topen neighbourhoods). As we develop the maths, this will then lead us on to consider various regularity properties (Definition 4.1.4). But first, we start with transitive sets and topens:

Definition 3.2.2

Suppose (P, Open) is a semitopology. Suppose T ⊆ P is any set of points.

(1) Call T transitive when

∀O, O′∈Open.O ≬T ≬O′ =⟹O ≬O′.

(2) Call T topen when T is nonempty transitive and open.10 We may write

Topen = {T ∈ Open≠∅| T is transitive}.

(3) Call S a maximal topen when S is a topen that is not a subset of any strictly larger topen.11

Theorem 3.2.3 clarifies why transitivity is interesting: continuous value assignments are constant — if we think of points as participants, ‘constant function’ here means ‘in agreement’ — across transitive sets.

Theorem 3.2.3

Suppose that:

• (P, Open) is a semitopology.

• Val is a semitopology of values (a nonempty set with the discrete semitopology; see Definition 2.1.3(1)).

• f : P → Val is a value assignment (Definition 2.1.3(2)).

• T ⊆ P is a transitive set (Definition 3.2.2) — in particular this will hold if T is topen — and p, p′ ∈ T.

Then:

(1) If f is continuous at p and p′ then f (p) = f (p′).

(2) As a corollary, if f is continuous on T, then f is constant on T.

In words we can say:

Continuous value assignments are constant across transitive sets.

Proof

Part 2 follows from part 1 since if f (p) = f (p′) for any p, p′ ∈ T, then by definition f is constant on T. So we now just need to prove part 1 of this result.

Consider p, p′ ∈ T. By continuity on T, there exist open neighbourhoods p ∈ O ⊆ f -1( f (p)) and p′ ∈ O′ ⊆ f -1( f (p′)). By construction O ≬ T ≬ O′ (because p ∈ O ∩ T and p′ ∈ T ∩ O′). By transitivity of T it follows that O ≬ O′. Thus, there exists p′′ ∈ O ∩ O′, and by construction f (p) = f (p′′) = f (p′).End of proof

Corollary 3.2.4 is an easy and useful consequence of Theorem 3.2.3:

Corollary 3.2.4

Suppose that:

• (P, Open) is a semitopology.

• f : P → Val is a value assignment to some set of values Val (Definition 2.1.3).

• f is continuous on topen sets T, T′ ∈ Topen.

Then

T ≬T ′implies ∀p ∈T, p′ ∈T ′.f(p) = f(p′).
Proof

By Theorem 3.2.3 f is constant on T and T′. We assumed that T and T′ intersect, and the result follows.End of proof

A converse to Theorem 3.2.3 also holds:

Proposition 3.2.5

Suppose that:

• (P, Open) is a semitopology.

• Val is a semitopology of values with at least two elements (to exclude a degenerate case that no functions exist, or they exist but there is only one because there is only one value to map to).

• T ⊆ P is any set.

Then

• if for every p, p′ ∈ T and every value assignment f : P → Val, f continuous at p and p′ implies f (p) = f (p′),

• then T is transitive.

Proof

We prove the contrapositive. Suppose T is not transitive, so there exist O, O′ ∈ Open such that O ≬ T ≬ O′ and yet O ∩ O′ = ∅. We choose two distinct values v ≠ v′ ∈ Val and define f to map any point in O to v and any point in P\O to v′.

Choose some p ∈ O and p′ ∈ O′. It does not matter which, and some such p and p′ exist, because O and O′ are nonempty by Lemma 3.1.3(6), since O ≬ T and O′ ≬ T).

We note that f (p) = v and f (p′) = v′ and f is continuous at p ∈ O and p′ ∈ O′ ⊆ P\O, yet f (p) ≠ f (p′).End of proof

We can sum up what Theorem 3.2.3 and Proposition 3.2.5 mean, as follows:

Remark 3.2.6

Suppose (P, Open) is a semitopology and Val is a semitopology of values with at least two elements. Say that a value assignment f : P → Val splits a set T ⊆ P when there exist p, p′ ∈ T such that f is continuous at p and p′ and f (p) ≠ f (p′). Then Theorem 3.2.3 and Proposition 3.2.5 together say in words that:

T ⊆ P is transitive if and only if it cannot be split by a value assignment that is continuous on T.

Intuitively, transitive sets characterise areas of guaranteed agreement.

3.3 Examples and discussion of transitive sets and topens

We may routinely order sets by subset inclusion; including open sets, topens, closed sets, and so on, and we may talk about maximal, minimal, greatest, and least elements. We include the (standard) definition for reference:

Notation 3.3.1

Suppose (P, ≤) is a poset. Then:

(1) Call p ∈ P maximal when ∀p′.p≤p′ =⟹ p′ = p and minimal when ∀p′.p′≤p =⟹ p′ = p.

(2) Call p ∈ P greatest when ∀p.p′ ≤ p and least when ∀p′.p ≤ p′.

Example 3.3.2 (Examples of transitive sets).

(1) {p} is transitive, for any single point p ∈ P.

(2) The empty set ∅ is (trivially) transitive. It is not topen because we insist in Definition 3.2.2(2) that topens are nonempty.

(3) Call a set P ⊆ P topologically indistinguishable when (using Notation 3.1.1) for every open set O,

P ≬O ⟺⇒P ⊆O.

It is easy to check that if P is topologically indistinguishable, then it is transitive.

Example 3.3.3 (Examples of topens).

(1) Take P = {0, 1, 2}, with open sets ∅, P, {0}, and {2}. This has two maximal topens {0} and {2} as illustrated in Figure 2 (top-left diagram).

(2) Take P = {0, 1, 2}, with open sets ∅, P, {0}, {0, 1}, {2}, {1, 2}, and {0, 2}. This has two maximal topens {0} and {2}, as illustrated in Figure 2 (top-right diagram).

(3) Take P = {0, 1, 2, 3, 4}, with open sets generated by {0, 1}, {1}, {3}, and {3, 4}. This has two maximal topens {0, 1} and {3, 4}, as illustrated in Figure 2 (lower-left diagram).

(4) Take P = {0, 1, 2, ∗}, with open sets generated by {0}, {1}, {2}, {0, 1, ∗}, and {1, 2, ∗}. This has three maximal topens {0}, {1}, and {2}, as illustrated in Figure 2 (lower-right diagram).

(5) Take the all-but-one semitopology from Example 2.1.4(5c) on N: so P = N with opens ∅, N, and N\{x} for every x ∈N. This has a single maximal topen N.

(6) The semitopology in Figure 3 has no topen sets at all (∅ is transitive and open, but by definition in Definition 3.2.2(2) topens have to be nonempty).

3.4 Closure properties of transitive sets and topens

Remark 3.4.1

Transitive sets have some nice closure properties which we treat in this Subsection — here we mean ‘closure’ in the sense of “the set of transitive sets is closed under various operations”, and not in the topological sense of ‘closed sets’. Topens — nonempty transitive open sets — have even better closure properties, which emanate from the requirement in Lemma 3.4.3 that at least one of the transitive sets T or T′ is open.

Lemma 3.4.2

Suppose (P, Open) is a semitopology and T ⊆ P. Then:

(1) If T is transitive and T′ ⊆ T, then T′ is transitive.

(2) If T is topen and ∅≠ T′ ⊆ T is nonempty and open, then T′ is topen.

Proof

(1) By Definition 3.2.2 it suffices to consider open sets O and O′ such that O ≬ T′ ≬ O′, and prove that O ≬ O′. But this is simple: by Lemma 3.1.3(5) O ≬ T ≬ O′, so O ≬ O′ follows by transitivity of T.

(2) Direct from part 1 of this result and Definition 3.2.2(2).End of proof

1 20 1 20*0 1 20 21

Here and elsewhere, we might omit open sets that are unions of open sets that are illustrated. For example, we explicitly draw the universal open set in the left-hand diagrams above, but not in the right-hand and bottom diagrams above. Meaning is clear and we get cleaner diagrams.

Figure 2. Examples of topens (Example 3.3.3)

Lemma 3.4.3

Suppose (P, Open) is a semitopology and T, T′ ⊆ P are transitive, and suppose that at least one of T and T′ is open. Then

∀O, O′ ∈Open.O ≬T ≬T ′ ≬O′ =⟹O ≬O′.
Proof

We simplify using Definition 3.2.2 and our assumption that one of T and T′ is open. We consider the case that T′ is open:

O ≬T ≬T ′ ≬O′ =⟹O ≬T ′ ≬O′T transitive, T ′ open=⟹O ≬O′T ′ transitive.

The argument for when T is open, is precisely similar.End of proof

Proposition 3.4.4

Suppose (P, Open) is a semitopology. Then if T is a set of pairwise intersecting topens, then ⋃ T is topen.

Proof

⋃ T is open by Definition 1.2.2(2). Also, if O ≬⋃ T ≬ O′ then there exist T, T′ ∈ T such that O ≬ T and T′ ≬ O′. We assumed T ≬ T′, so by Lemma 3.4.3 (since T and T′ are open) we have O ≬ O′ as required.End of proof

Corollary 3.4.5

Suppose (P, Open) is a semitopology. Then every topen T is contained in a unique maximal topen.

Proof

Consider T = {T ∪ T′ | T′ topen ∧ T ≬ T′}. By Proposition 3.4.4 this is a set of topens. By construction they all contain T, so by our assumption that T ≠ ∅, they pairwise intersect, and by Proposition 3.4.4 again ⋃ T is topen. It is easy to check that this is the unique maximal topen that contains T.End of proof

3.5 Intertwined points

3.5.1 The basic definition

Definition 3.5.1

Suppose (P, Open) is a semitopology and p, p′ ∈ P.

(1) Call p and p′ intertwined when {p, p′} is transitive. Unpacking Definition 3.2.2 this means:

∀O, O′∈Open.(p ∈O ∧p′ ∈O′) =⟹O ≬O′.

By a mild abuse of notation, write

p ≬ p′ when p and p′ are intertwined.

(2) Define p≬ (read ‘intertwined of p’) to be the set of points intertwined with p. In symbols:

p≬= {p′ ∈P | p ≬p′}.
Example 3.5.2

We return to the examples in Example 3.3.3. There we note that:

(1) 1≬= {0, 1, 2} and 0≬= {0, 1} and 2≬= {1, 2}.

(2) 1≬= {1} and 0≬= {0} and 2≬= {2}.

(3) x≬= P for every x.

Lemma 3.5.3

Suppose (P, Open) is a semitopology. Then the ‘is intertwined’ relation ≬ is not necessarily transitive. That is: p ≬ p′ ≬ p′′ does not necessarily imply p ≬ p′′.

Proof

It suffices to provide a counterexample. The semitopology from Example 3.3.3(1) (illustrated in Figure 2, top-left diagram) will do. So take P = {0, 1, 2} and Open = {∅, P, {0}, {2}}. Then

0 ≬ 1 and 1 ≬ 2, but ¬(0 ≬ 2).End of proof

3.5.2 Pointwise characterisation of transitive sets

Lemma 3.5.4

Suppose (P, Open) is a semitopology and T ⊆ P. Then the following are equivalent:

(1) T is transitive.

(2) p ≬ p′ (meaning by Definition 3.5.1 that {p, p′} is transitive) for every p, p′ ∈ T.

Proof

Suppose T is transitive. Then by Lemma 3.4.2(1), {p, p′} is transitive for every p, p′ ∈ T.

Suppose {p, p′} is transitive for every p, p′ ∈ T. Consider open sets O and O′ such that O ≬ T ≬ O′. Choose p ∈ O ∩ T and p′ ∈ O ∩ T′. By construction {p, p′} ⊆ T so this is transitive. It follows that O ≬ O′ as required.End of proof

Theorem 3.5.5

Suppose (P, Open) is a semitopology and T ⊆ P. Then the following are equivalent:

(1) T is topen.

(2) T ∈ Open≠∅ and ∀p, p′∈T.p ≬ p′.

In words we can say:

A topen is a nonempty open set of intertwined points.

Proof

By Definition 3.2.2(2), T is topen when it is nonempty, open, and transitive. By Lemma 3.5.4 this last condition is equivalent to p ≬ p′ for every p, p′ ∈ T.End of proof

A value assignment is constant on a pair of intertwined points, where it is continuous:

Corollary 3.5.6

Suppose Val is a semitopology of values and f : P → Val is a value assignment (Definition 2.1.3) and p, p′ ∈ P and p ≬ p′. Then if f continuous at p and p′ then f (p) = f (p′).

Proof

{p, p′} is transitive by Theorem 3.5.5; we use Theorem 3.2.3.End of proof

Remark 3.5.7 (Intertwined as ‘non-Hausdorff’).

Recall that we call a topological space (P, Open) Hausdorff (or T2) when any two points can be separated by pairwise disjoint open sets. Using the ≬ symbol from Notation 3.1.1, we rephrase the Hausdorff condition as

∀p, p′.p ≠ p′ =⟹∃O, O′.(p ∈O ∧p′ ∈O′ ∧¬(O ≬O′)),

we can simplify to

∀p, p′.p ≠ p′ =⟹p≬̸p′,

and thus we simplify the Hausdorff condition just to

∀p.p≬= {p}. (1)

Note how distinct p and p′ being intertwined is the opposite of being Hausdorff: p ≬ p′ when p′ ∈ p≬, and they cannot be separated by pairwise disjoint open sets. Thus the assertion p ≬ p′ in Theorem 3.5.5 is a negation to the Hausdorff property: ∃p.p≬≠ {p}.

4. Interiors, communities & regular points

4.1 Community of a (regular) point

Definition 4.1.1 is standard:

Definition 4.1.1 (Open interior).

Suppose (P, Open) is a semitopology and P ⊆ P. Define interior(P) the (open) interior of P by

interior(P) =⋃ {O ∈Open | O ⊆P}.
Lemma 4.1.2

Suppose (P, Open) is a semitopology and P ⊆ P. Then interior(P) from Definition 4.1.1 is the greatest open subset of P.

Proof

Routine by the construction in Definition 4.1.1 and closure of open sets under unions (Definition 1.2.2(2)).End of proof

Corollary 4.1.3

Suppose (P, Open) is a semitopology and P, P′ ⊆ P. Then if P ⊆ P′ then interior(P) ⊆ interior(P′).

Proof

Routine using Lemma 4.1.2.End of proof

Definition 4.1.4 (Community of a point, and regularity).

Suppose (P, Open) is a semitopology and p ∈ P. Then:

(1) Define K(p) the community of p by

K(p) = interior(p≬).

The community of p is always an open set by Lemma 4.1.2.

(2) Extend K to subsets P ⊆ P by taking a sets union:

K(P) =⋃ {K(p) | p ∈P}.

(3) Call p a regular point when its community is a topen neighbourhood of p. In symbols:

p is regular when p ∈ K(p) ∈ Topen.

(4) Call p a weakly regular point when its community is an open (but not necessarily topen) neighbourhood of p. In symbols:

p is weakly regular when p ∈ K(p) ∈ Open.

(5) Call p a quasiregular point when its community is nonempty. In symbols:

p is quasiregular when ∅≠ K(p) ∈ Open.

(6) If p is not regular then we may call it an irregular point, or just say that it is not regular.

(7) If P ⊆ P and every p ∈ P is regular/weakly regular/quasiregular/irregular then we may call P a regular/weakly regular/quasiregular/irregular set respectively (see also Definition 5.3.1(2)).

Remark 4.1.5

The notion of regular point in Definition 4.1.4 is a key well-behavedness property. Let’s remember why it matters:

A topen set is a transitive open set. We care about transitivity because it implies agreement, as per Theorem 3.2.3 (continuous value assignments are constant on transitive sets). We care about being open, because we understand this as ‘being actionable’. Thus, a regular point is interesting because it is a participant in a topen and thus is capable of safely making progress in algorithms we write on top of the underlying semitopology. For convenient reference, the semiframe characterisation of regularity is in Subsection 11.5.

Lemma 4.1.6 gives an initial overview of the relationships between the properties in Definition 4.1.4. A more detailed treatment follows, which repeats these main points and expands on them and puts them in a detailed context.

Lemma 4.1.6

Suppose (P, Open) is a semitopology and p ∈ P. Then:

(1) If p is regular, then p is weakly regular.

(2) If p is weakly regular, then p is quasiregular.

(3) The converse implications need not hold.

(4) Furthermore, it is possible for a point p to not be quasiregular.

Proof

We consider each part in turn:

(1) If p is regular then by Definition 4.1.4(3) p ∈ K(p) ∈ Topen, so certainly p ∈ K(p) and by Definition 4.1.4(4) p is weakly regular.

(2) If p is weakly regular then by Definition 4.1.4(4) p ∈ K(p) ∈ Open, so certainly K(p) ≠ ∅ and by Definition 4.1.4(5) p is quasiregular.

(3) To see that the converse implications need not hold, note that:

– Point 1 in Example 4.1.7(2) (illustrated in Figure 2, top-left diagram) is weakly regular (K(1) = {0, 1, 2}) but not regular (K(1) is open but not topen).

– Point ∗ in Example 4.1.7(3) (illustrated in Figure 2, lower-right diagram) is quasiregular (K(∗) = {1} is nonempty but does not contain ∗).

(4) To see that p may not even be quasiregular, take P = R (real numbers), with its usual topology (which is also a semitopology). Then x≬= {x} and K(x) = ∅ for every x ∈R.End of proof

Example 4.1.7

(1) In Figure 2 (bottom diagram), 0, 1, and 2 are three intertwined points and the entire space {0, 1, 2} consists of a single topen set. It follows that 0, 1, and 2 are all regular and their community is {0, 1, 2}.

(2) In Figure 2 (top-left diagram), 0 and 2 are regular and 1 is weakly regular but not regular (1 ∈ K(1) = {0, 1, 2} but {0, 1, 2} is not topen).

(3) In Figure 2 (lower-right diagram), 0, 1, and 2 are regular and ∗ is quasiregular (K(∗) = {1}).

(4) In Figure 2 (top-right diagram), 0 and 2 are regular and 1 is neither regular, weakly regular, nor quasiregular (K(1) = ∅).

(5) In a semitopology of values (Val, pow(Val)) (Definition 2.1.3) every value v ∈ Val is regular, weakly regular, and unconflicted.

(6) In R with its usual topology (which is also a semitopology), every point is unconflicted because the topology is Hausdorff and by Equation 1 in Remark 3.5.7 this means precisely that p≬= {p} so p is intertwined just with itself. Furthermore p is not (quasi/weakly)regular, because K(p) = interior(p≬) = ∅.

4.2 Further exploration of (quasi-/weak) regularity and topen sets

Remark 4.2.1

Recall three common separation axioms from topology:

(1) T0: if p1 ≠ p2 then there exists some O ∈ Open such that (p1 ∈ O) xor (p2 ∈ O), where xor denotes exclusive or.

(2) T1: if p1 ≠ p2 then there exist O1, O2 ∈ Open such that pi ∈ Oj ⟺⇒ i = j for i, j ∈{1, 2}.

(3) T2, or the Hausdorff condition: if p1 ≠ p2 then there exist O1, O2 ∈ Open such that pi ∈ Oj ⟺⇒ i = j for i, j ∈{1, 2}, and O1 ∩ O2 = ∅. Cf. the discussion in Remark 3.5.7.

Even the weakest of the well-behavedness property for semitopologies that we consider in Definition 4.1.4 — quasiregularity — is in some sense strongly opposed to the space being Hausdorff/T2 (though not to being T1), as Lemma 4.2.2 makes formal.

Lemma 4.2.2

(1) Every quasiregular Hausdorff semitopology is discrete. In more detail: if (P, Open) is a semitopology that is quasiregular (Definition 4.1.4(5)) and Hausdorff (equation 1 in Remark 3.5.7), then Open = pow(P).

(2) There exists a (quasi)regular T1 semitopology that is not discrete.

Proof

We consider each part in turn:

(1) By the Hausdorff property, p≬= {p}. By the quasiregularity property, K(p) ≠ ∅. It follows that K(p) = {p}. But by construction in Definition 4.1.4(1), K(p) is an open interior. Thus {p} ∈ Open. The result follows.

(2) It suffices to provide an example. We use the bottom semitopology in Figure 2. Thus P = {0, 1, 2} and Open is generated by {0, 1}, {1, 2}, and {2, 0}. The reader can check that this is regular (since all three points are intertwined) and T1.End of proof

So what is K(p)? We start by characterising K(p) as the greatest topen neighbourhood of p, if this exists:

Lemma 4.2.3

Suppose (P, Open) is a semitopology and recall from Definition 4.1.4(3) that p is regular when K(p) is a topen neighbourhood of p.

(1) If K(p) is a topen neighbourhood of p (i.e. if p is regular) then K(p) is a maximal topen.

(2) If p ∈ T ∈ Topen is a maximal topen neighbourhood of p then T = K(p).

Proof

(1) Since p is regular, by definition, K(p) is topen and is a neighbourhood of p. It remains to show that K(p) is a maximal topen. Suppose T is a topen neighbourhood of p; we wish to prove T ⊆ K(p) = interior(p≬). Since T is open it would suffice to show that T ⊆ p≬. By Theorem 3.5.5 p ≬ p′ for every p′ ∈ T, and it follows immediately that T ⊆ p≬.

(2) Suppose T is a maximal topen neighbourhood of p. First, note that T is open, and by Theorem 3.5.5 T ⊆ p≬, so T ⊆ K(p). Now consider any open O ⊆ p≬. Note that T ∪ O is an open subset of p≬, so by Theorem 3.5.5 T ∪ O is topen, and by maximality T ∪ O ⊆ T and thus O ⊆ T. It follows that K(p) ⊆ T.End of proof

Remark 4.2.4

We can use Lemma 4.2.3 to characterise regularity in five equivalent ways: see Theorem 4.2.5 and Corollary 4.2.6.

Theorem 4.2.5

Suppose (P, Open) is a semitopology and p ∈ P. Then the following are equivalent:

(1) p is regular, or in full: p ∈ K(p) ∈ Topen.

(2) K(p) is the greatest topen neighbourhood of p.

(3) K(p) is a maximal topen neighbourhood of p.

(4) p has a maximal topen neighbourhood.

(5) p has some topen neighbourhood.

Proof

We prove a cycle of implications:

(1) If K(p) is a topen neighbourhood of p then it is maximal by Lemma 4.2.3(1). Furthermore this maximal topen neighbourhood of p is necessarily greatest, since if we have two maximal topen neighbourhoods of p then their union is a larger topen neighbourhood of p by Proposition 3.4.4.

(2) If p≬ is the greatest topen neighbourhood of p, then certainly it is maximal.

(3) If p≬ is a maximal topen neighbourhood of p, then certainly p has a maximal topen neighbourhood.

(4) If p has a maximal topen neighbourhood then certainly p has a topen neighbourhood.

(5) Suppose p has a topen neighbourhood T. By Corollary 3.4.5 we may assume without loss of generality that T is a maximal topen. We use Lemma 4.2.3(2).End of proof

Corollary 4.2.6

Suppose (P, Open) is a semitopology and p ∈ P. Then the following are equivalent:

(1) p is regular.

(2) p is weakly regular and K(p) = K(p′) for every p′ ∈ K(p).

It might be useful to look at Example 3.3.3(2) and Figure 2 (top-right diagram). In that example the point 1 is not regular, and its community {0, 1, 2} is not a community for 0 or 2.

Proof

We prove two implications, using Theorem 4.2.5:

• Suppose p is regular. By Lemma 4.1.6(1) p is weakly regular. Now consider p′ ∈ K(p). By Theorem 4.2.5 K(p) is topen, so it is a topen neighbourhood of p′. By Theorem 4.2.5 K(p′) is a greatest topen neighbourhood of p′. But by Theorem 4.2.5 K(p) is also a greatest topen neighbourhood of p, and K(p) ≬ K(p′) since they both contain p′. By Proposition 3.4.4 and maximality, they are equal.

• Suppose p is weakly regular and suppose K(p) = K(p′) for every p′ ∈ K(p), and consider p′, p′′ ∈ K(p). Then p′ ≬ p′′ holds, since p′′ ∈ K(p′) = K(p). By Theorem 3.5.5 K(p) is topen, and by weak regularity p ∈ K(p), so by Theorem 4.2.5 p is regular as required.End of proof

Corollary 4.2.7

Suppose (P, Open) is a semitopology and p, p′ ∈ P. Then if p is regular and p′ ∈ K(p) then p′ is regular and has the same community.

Proof

Suppose p is regular — so by Definition 4.1.4(3) p ∈ K(p) ∈ Topen — and suppose p′ ∈ K(p). Then by Corollary 4.2.6 K(p) = K(p′), so p′ ∈ K(p′) ∈ Topen and by Theorem 4.2.5 p′ is regular.End of proof

4.3 Intersection and partition properties of regular spaces

Proposition 4.3.1 is useful for consensus in practice. Suppose we are a regular point q and we have reached consensus with some topen neighbourhood O ∋ q. Suppose further that our topen neighbourhood O intersects with the maximal topen neighbourhood K(p) of some other regular point p. Then Proposition 4.3.1 tells us that we were inside K(p) all along.

Proposition 4.3.1

Suppose (P, Open) is a semitopology and p ∈ P is regular and O ∈ Topen is topen. Then

O ≬K(p) if and only if O ⊆K(p).
Proof

The right-to-left implication is immediate from Notation 3.1.1(1), given that topens are nonempty by Definition 3.2.2(2).

For the left-to-right implication, suppose O ≬ K(p). By Theorem 4.2.5 K(p) is a maximal topen, and by Proposition 3.4.4 O ∪ K(p) is topen. Then O ⊆ K(p) follows by maximality.End of proof

Proposition 4.3.2

Suppose (P, Open) is a semitopology and suppose p, p′ ∈ P are regular. Then

K(p) ≬K(p′) ⟺⇒ K(p) = K(p′)
Proof

We prove two implications.

• Suppose there exists p′′ ∈ K(p) ∩ K(p′). By Corollary 4.2.7 (p′′ is regular and) K(p) = K(p′′) = K(p′).

• Suppose K(p) = K(p′). By assumption p ∈ K(p), so p ∈ K(p′). Thus p ∈ K(p) ∩ K(p′).End of proof

Corollary 4.3.3 is a simple characterisation of regular semitopological spaces:

Corollary 4.3.3

Suppose (P, Open) is a semitopology. Then the following are equivalent:

(1) (P, Open) is regular.

(2) P partitions into topen sets: there exists some set of topen sets T such that T ≬̸ T′ for every T, T′ ∈ T and P = ⋃ T .

(3) Every X ⊆ P has a cover of topen sets: there exists some set of topen sets T such that X ⊆⋃ T .

Proof

The proof is routine from the machinery that we already have. We prove equivalence of parts 1 and 2:

(1) Suppose (P, Open) is regular, meaning by Definition 4.1.4(7&3) that p ∈ K(p) ∈ Topen for every p ∈ P. We set T = {K(p) | p ∈ P}. By assumption this covers P in topens, and by Proposition 4.3.2 the cover is a partition.

(2) Suppose T is a topen partition of P. By definition for every point p there exists T ∈ T such that p ∈ T and so p has a topen neighbourhood. By Theorem 4.2.5(5&1) p is regular.

We prove equivalence of parts 2 and 3:

(1) Suppose T is a topen partition of P, and suppose X ⊆ P. Then trivially X ⊆⋃ T .

(2) Suppose every X ⊆ P has a cover of topen sets. Then P has a cover of topen sets; write it T . By Corollary 3.4.5 we may assume without loss of generality that T is a partition, and we are done.End of proof

Notation 4.3.4

Call a semitopology (P, Open) singular when it contains a single maximal topen subset.

Remark 4.3.5

The moral we take from the results and examples above (and those to follow) is that the world we are entering has rather different well-behavedness criteria than those familiar from the study of typical Hausdorff topologies like R:

(1) ‘Bad’ spaces are spaces that are not regular. R with its usual topology (which is also a semitopology) is an example of a ‘bad’ semitopology; it is not even quasiregular.

(2) ‘Good’ spaces are spaces that are regular. The supermajority and all-but-one semitopologies from Example 2.1.4(5a&5c) are typical examples of ‘good’ semitopologies; both are singular regular spaces.

(3) Corollary 4.3.3 shows that the ‘good’ spaces are just the (disjoint, possibly infinite) unions of singular regular spaces.

So to sum this up: modulo disjoint unions, the study of consensus behaviour is the study of semitopological spaces that consist of a single topen set of points that are all intertwined with one another.

5. Regular = weakly regular + unconflicted

5.1 Closed sets

In Subsection 5.1 we check that some familiar properties of closures carry over from topologies to semitopologies. There are no technical surprises, but this in itself is a mathematical result that needs checked. Then, we will use this to study the relation between closures and sets of intertwined points.

Definition 5.1.1

Suppose (P, Open) is a semitopology and suppose p ∈ P and P ⊆ P. Then:

(1) Define |P| ⊆ P the closure of P to be the set of points p such that every open neighbourhood of p intersects P. In symbols using Notation 3.1.1:

|P| = {p′ ∈P | ∀O∈Open.p′ ∈O =⟹P ≬O}.

(2) As is standard, we may write |p| for |{p}|. Unpacking definitions for reference:

|p| = {p′ ∈P | ∀O∈Open.p′ ∈O =⟹p ∈O}.
Lemma 5.1.2

Suppose (P, Open) is a semitopology and suppose P, P′ ⊆ P. Then taking the closure of a set is:

(1) Monotone: If P ⊆ P′ then |P| ⊆|P′|.

(2) Increasing: P ⊆|P|.

(3) Idempotent: |P| = ||P||.

Proof

By routine calculations from Definition 5.1.1.End of proof

Lemma 5.1.3

Suppose (P, Open) is a semitopology and P ⊆ P and O ∈ Open. Then

P ≬ O if and only if |P| ≬ O.

Proof

Suppose P ≬ O. Then |P| ≬ O using Lemma 5.1.2(2).

Suppose |P| ≬ O. Pick p ∈|P| ∩ O. By construction of |P| in Definition 5.1.1 p ∈ O =⟹ P ≬ O. It follows that P ≬ O as required.End of proof

Definition 5.1.4

Suppose (P, Open) is a semitopology and suppose C ⊆ P.

(1) Call C a closed set when C = |C|.

(2) Call C a clopen set when C is closed and open.

(3) Write Closed for the set of closed sets (as we wrote Open for the open sets; the ambient semitopology will always be clear or understood).

Lemma 5.1.5

Suppose (P, Open) is a semitopology and suppose P ⊆ P. Then |P| is closed and contains P. In symbols:

P ⊆|P| ∈Closed.
Proof

From Definition 5.1.4(1) and Lemma 5.1.2(2 & 3).End of proof

Example 5.1.6

(1) Take P = {0, 1} and Open = {∅, {0}, {0, 1}}. Then the reader can verify that:

– {0} is open.

– The closure of {1} is {1} and {1} is closed.

– The closure of {0} is {0, 1}.

– ∅ and {0, 1} are the only clopen sets.

(2) Now take P = {0, 1} and Open = {∅, {0}, {1}, {0, 1}}.12 Then the reader can verify that:

– Every set is clopen.

– The closure of every set is itself.

Remark 5.1.7

There are two standard definitions for when a set is closed: when it is equal to its closure (as per Definition 5.1.4(1)), and when it is the complement of an open set. In topology these are equivalent. We do need to check that the same holds in semitopology, but as it turns out the proof is routine:

Lemma 5.1.8

Suppose (P, Open) is a semitopology. Then:

(1) Suppose C ∈ Closed is closed (by Definition 5.1.4: C = |C|). Then P\C is open.

(2) Suppose O ∈ Open is open. Then P\O is closed (by Definition 5.1.4: |P\O| = P\O).

Proof

(1) Suppose p ∈ P\C. Since C = |C|, we have p ∈ P\|C|. Unpacking Definition 5.1.1, this means precisely that there exists Op ∈ Open with p ∈ Op ≬̸C. We use Lemma 2.3.2.

(2) Suppose O ∈ Open. Combining Lemma 2.3.2 with Definition 5.1.1 it follows that O ≬̸|P\O| so that |P\O| ⊆ P\O. Furthermore, by Lemma 5.1.2(2) P\O ⊆|P\O|.End of proof

The usual duality between forming closures and interiors, remains valid in semitopologies:

Lemma 5.1.9

Suppose (P, Open) is a semitopology and O ∈ Open and C ∈ Closed. Then:

(1) O ⊆ interior(|O|). The inclusion may be strict.

(2) |interior(C)| ⊆ C. The inclusion may be strict.

(3) interior(P\O) = P\|O|.

(4) |P\C| = P\interior(C).

Proof

The reasoning is just as for topologies, but we spell out the details:

(1) By Lemma 5.1.2(2) O ⊆|O|. By Corollary 4.1.3 interior(O) ⊆ interior(|O|). By Lemma 4.1.2 O = interior(O), so we are done. For an example of the strict inclusion, consider R with the usual topology (which is also a semitopology) and take O = (0, 1) ∪ (1, 2). Then O ⊊ interior(|O|) = (0, 2).

(2) By Lemma 4.1.2 interior(C) ⊆ C. By Lemma 5.1.2(1) |interior(C)| ⊆|C|. By Definition 5.1.4(1) (since we assumed C ∈ Closed) |C| = C, so we are done. For an example of the strict inclusion, consider R with the usual topology and take C = {0}.

Then |interior(C)| = ∅⊊C.

(3) Consider some p′ ∈ P. By Definition 4.1.1 p′ ∈ interior(P\O) when there exists some O′ ∈ Open such that p′ ∈ O′ ≬̸ O. By definition in Definition 5.1.1(1) this happens precisely when p′ /∈|O|.

(4) By Definition 5.1.1(1), p′ /∈|P\C| precisely when there exists some O′ ∈ Open such that p′ ∈ O′ ≬̸ P\C. By facts of sets this means precisely that p′ ∈ O′ ⊆ C. By Definition 4.1.1 this means precisely that p′ ∈ interior(C).End of proof

5.2 Closed neighbourhoods and intertwined points

Definition 5.2.1

Suppose (P, Open) is a semitopology. We generalise Definition 2.3.1 as follows:

(1) Call P ⊆ P a neighbourhood when it contains an open set (i.e. when interior(P) ≠ ∅), and call P a neighbourhood of p when p ∈ P and P contains an open neighbourhood of p (i.e. when p ∈ interior(P)). In particular:

(2) C ⊆ P is a closed neighbourhood of p ∈ P when C is closed and p ∈ interior(C).

(3) C ⊆ P is a closed neighbourhood when C is closed and interior(C) ≠ ∅.

Remark 5.2.2

(1) If C is a closed neighbourhood of p in the sense of Definition 5.2.1(2) then C is a closed neighbourhood in the sense of Definition 5.2.1(3), just because if p ∈ interior(C) then interior(C) ≠ ∅.

(2) p ∈ C is not enough for C to be a closed neighbourhood of p; we require the stronger condition p ∈ interior(C). For instance, consider the Sierpiński space

Sk = ({0, 1}, {∅, {1}, {0, 1}}).

is a topology and so also a semitopology (cf. Remark 12.3.2), and consider p = 0 and C = {0}. Then p ∈ C but p ∉ interior(C) = ∅, so that C is not a closed neighbourhood of p.

Remark 5.2.3

Recall the definitions of p≬ and |p|:

• The set |p| is the closure of p. By Definition 5.1.1 this is the set of p′ such that every open neighbourhood O′ ∋ p′ intersects with {p}.

• The set p≬ is the set of points intertwined with p. By Definition 3.5.1(2) this is the set of p′ such that every open neighbourhood O′ ∋ p′ intersects with every open neighbourhood O ∋ p.

Lemma 5.2.4 rephrases Remark 5.2.3 more precisely by looking at it through sets complements. We will use it in Lemma 11.4.4(2):

Lemma 5.2.4

Suppose (P, Open) is a semitopology and p ∈ P. Then:

(1) P\|p| = ⋃{O ∈ Open | p /∈ O} ∈ Open.

(2) P\ p≬= ⋃{O′ ∈ Open | ∃O∈Open.p ∈ O ∧ O′ ≬̸ O} ∈ Open.

(3) P\ p≬= ⋃{O ∈ Open | p /∈|O|} ∈ Open.

In words, we can say: P\|p| is the union of the open sets such that p avoids them, and P\ p≬ is the union of the open sets such that p avoids their closures.

Proof

(1) Immediate from Definitions 3.5.1 and 5.1.1. Openness is from Definition 1.2.2(2).

(2) By a routine argument direct from Definition 3.5.1. Openness is from Definition 1.2.2(2).

(3) Rephrasing part 2 of this result using Definition 5.1.1(1).End of proof

Remark 5.2.5

We can relate Lemma 5.2.4 to a concept from topology. Following standard terminology ([4, Definition 2, page 69] or [14, page 52]), a cluster point p ∈ P of O ⊆ Open is one such that every open neighbourhood of p intersects every O ∈ O. Then Lemma 5.2.4(2) identifies p≬ as the set of cluster points of nbhd(p) ⊆ Open from Definition 2.3.1.

5.3 Regular = weakly regular + unconflicted

In Lemma 3.5.3 we asked whether the ‘is intertwined with’ relation ≬ from Definition 3.5.1(1) is transitive — answer: not necessarily.

Transitivity of ≬ is a natural condition. We now have enough machinery to study it in more detail, and this will help us gain a deeper understanding of the properties of not-necessarily-regular points.

Definition 5.3.1

Suppose (P, Open) is a semitopology.

(1) Call a point p conflicted when there exist p′ and p′′ such that p′ ≬ p and p ≬ p′′ yet ¬(p′ ≬ p′′).

(2) If p′ ≬ p ≬ p′′ implies p′ ≬ p′′ always, then call p unconflicted.

(3) Continuing Definition 4.1.4(7), if P ⊆ P and every p ∈ P is conflicted/unconflicted, then we may call P conflicted/unconflicted respectively.

3102ACBD
Figure 3. An unconflicted, irregular space (Proposition 5.3.3) in which every point is intertwined only with itself (Example 5.3.2)
Example 5.3.2

We consider some examples:

(1) In Figure 2 top-left diagram, 0 and 2 are unconflicted and intertwined with themselves, and 1 is conflicted (being intertwined with 0, 1, and 2). If the reader wants to know what a conflicted point looks like: it looks like 1.

(2) In Figure 2 top-right diagram, 0 and 2 are unconflicted and intertwined with themselves, and 1 is conflicted (being intertwined with 0, 1, and 2).

(3) In Figure 2 lower-left diagram, 0 and 1 are unconflicted and intertwined with themselves, and 3 and 4 are unconflicted and intertwined with themselves, and 2 is conflicted (being intertwined with 0, 1, 2, 3, and 4).

(4) In Figure 2 lower-right diagram, all points are unconflicted, and 0 and 2 are intertwined just with themselves, and 1 and ∗ are intertwined with one another.

(5) In Figure 3, all points are unconflicted and intertwined only with themselves. (This semitopology is useful for counterexamples and we will use it again.)

Proposition 5.3.3

Suppose (P, Open) is a semitopology and p ∈ P. Then:

(1) If p is regular then it is unconflicted. Equivalently by the contrapositive: if p is conflicted then it is not regular.

(2) p may be unconflicted and neither quasiregular, weakly regular, nor regular.

Proof

We consider each part in turn:

(1) So consider q ≬ p ≬ q′. We must show that q ≬ q′, so consider open neighbourhoods Q ∋ q and Q′ ∋ q′. By assumption p is regular, so unpacking Definition 4.1.4(3) K(p) is a topen (transitive and open) neighbourhood of p. By assumption Q ≬ K(p) ≬ Q′, and by transitivity of K(p) (Definition 3.2.2(1)) we have Q ≬ Q′ as required.

(2) Consider the semitopology illustrated in Figure 3. Note that the point 0 is not conflicted (because it is not intertwined with any other point), but it is also neither quasiregular, weakly regular, nor regular, because its community is the empty set.End of proof

We can combine Proposition 5.3.3 with a previous result Lemma 4.1.6 to get a precise and attractive relation between being

• regular (Definition 4.1.4(3)),

• weakly regular (Definition 4.1.4(4)), and

• unconflicted (Definition 5.3.1),

as follows:

Theorem 5.3.4

Suppose (P, Open) is a semitopology and p ∈ P. Then the following are equivalent:

• p is regular.

• p is weakly regular and unconflicted.

More succinctly we can write: regular = weakly regular + unconflicted.13

Proof

We prove two implications:

• If p is regular then it is weakly regular by Lemma 4.1.6 and unconflicted by Proposition 5.3.3(1).

• Suppose p is weakly regular and unconflicted. By Definition 4.1.4(4) p ∈ K(p) and by Lemma 3.5.4 it would suffice to show that q ≬ q′ for any q, q′ ∈ K(p). So consider q, q′ ∈ K(p). Now by Definition 4.1.4(1) K(p) = interior(p≬) so in particular q, q′ ∈ p≬. Thus q ≬ p ≬ q′, and since p is unconflicted q ≬ q′ as required.End of proof

6. Regular = quasiregular + hypertransitive

6.1 Regular open/closed sets

We recall some simple results:

Definition 6.1.1

Suppose (P, Open) is a semitopology. Recall some standard terminology from topology [56, Exercise 3D, page 29]:

(1) We call an open set O ∈ Open a regular open set when O = interior(|O|).

(2) We call a closed set C ∈ Closed a regular closed set when C = |interior(C)|.

(3) Write Openreg and Closedreg for the sets of regular open and regular closed sets respectively.

Lemma 6.1.2

Suppose (P, Open) is a semitopology and O ∈ Open and C ∈ Closed. Then:

(1) |O| = |interior(|O|)|.

(2) interior(C) = interior(|interior(C)|).

Proof

We use Lemma 5.1.9(1&3) along with Lemma 5.1.2(1) and Corollary 4.1.3:

|O|L5.1.9(1)&L5.1.2(1)⊆ |interior(|O|)|L5.1.9(2)⊆ interior(|O|)interior(C)L5.1.9(1)⊆ interior(|interior(C)|)L5.1.9(2)&C4.1.3⊆ interior(C)End of proof

The terminology ‘regular open/closed set’ is from the topological literature. It is not directly related to terminology ‘regular point’ from Definition 4.1.4(3), which comes from semitopologies. However, it turns out that a mathematical connection does exist between these two notions:

Corollary 6.1.3

Suppose (P, Open) is a semitopology and O ∈ Open and C ∈ Closed. Then:

(1) interior(C) is a regular open set.

(2) |O| is a regular closed set.

Proof

Direct from Definition 6.1.1 and Lemma 6.1.2.End of proof

An elementary observation about open sets will be useful:

Lemma 6.1.4

Suppose (P, Open) is a semitopology and O, O′ ∈ Open. Then the following are equivalent:

(1) O ≬ O′.

(2) O ≬ interior(|O′|).

(3) interior(|O|) ≬ interior(|O′|).

Proof

First we prove the equivalence of parts 1 and 2:

(1) Suppose O ≬ O′. By Lemma 5.1.9(1) O ≬ interior(|O′|).

(2) Suppose there is some p ∈ O ∩ interior(|O′|). Then O is an open neighbourhood of p and p ∈|O′|, so by Definition 5.1.1(1) O ≬ O′ as required.14

Equivalence of parts 1 and 3 then follows easily by two applications of the equivalence of parts 1 and 2.End of proof

Remark 6.1.5

Lemma 6.1.4 is true in topologies as well, but it is not prominent in the literature. Two standard reference works [14, 56] do not seem to mention it. It appears as equation 10 in Theorem 1.37 of [25], and as a lemma in π-base [38] (thanks to the mathematics StackExchange community for the pointers). Interestingly, this result is as true in topologies as it is in semitopologies, but somehow, it matters more in the latter than the former.

6.2 Hypertransitivity

We are now ready to define hypertransitivity.

Notation 6.2.1

Suppose (P, Open) is a semitopology and O′ ∈ Open and O ⊆ Open.

(1) Write O′ ≬ O, or equivalently O ≬ O′, when O′ ≬ O for every O ∈ O. In symbols:

O′ ≬O when ∀O∈O.O′ ≬O.

(2) As a special case of part 1 above taking O = nbhd(p) (Definition 2.3.1), if p ∈ P then write O′ ≬ nbhd(p), or equivalently nbhd(p) ≬ O′, when O′ ≬ O for every O ∈ Open such that p ∈ O.

Lemma 6.2.2

Suppose (P, Open) is a semitopology and p ∈ P and O′ ∈ Open. Then

p ∈|O′| if and only if O′ ≬nbhd(p).
Proof

This just rephrases Definition 5.1.1(1).End of proof

Definition 6.2.3

Suppose (P, Open) is a semitopology. Call p ∈ P a hypertransitive point when for every O′, O′′ ∈ Open,

O′ ≬ nbhd(p) ≬ O′′ implies O′ ≬ O′′.

Call (P, Open) a hypertransitive semitopology when every p ∈ P is hypertransitive.

Lemma 6.2.4 notes some equivalent formulations of hypertransitivity:

Lemma 6.2.4

Suppose (P, Open) is a semitopology and p ∈ P. Then the following are equivalent:

(1) p is hypertransitive.

(2) For every pair of open sets O′, O′′ ∈ Open, p ∈|O′| ∩|O′′| implies O′ ≬ O′′.

(3) For every pair of regular open sets O′, O′′ ∈ Openreg, p ∈|O′| ∩|O′′| implies O′ ≬ O′′.

Proof

For the equivalence of parts 1 and 2 we reason as follows:

• Suppose p is hypertransitive and suppose p ∈|O′| and p ∈|O′′|. By Lemma 6.2.2 it follows that O′ ≬ nbhd(p) ≬ O′′. By hypertransitivity, O′ ≬ O′′ as required.

• Suppose for every O, O′ ∈ Open, p ∈|O| ∩|O′| implies O′ ≬ O′′, and suppose O′ ≬ nbhd(p) ≬ O′′. By Lemma 6.2.2 p ∈|O| ∩|O′| and therefore O′ ≬ O′′.

For the equivalence of parts 2 and 3 we reason as follows:

• Part 2 implies part 3 follows since every open regular set is also an open set.

• To show part 3 implies part 2, suppose for every pair of regular opens O′, O′′ ∈ Openreg, p ∈|O′| ∩|O′′| implies O′ ≬ O′′, and suppose O′, O′′ ∈ Open are two open sets that are not necessarily regular, and suppose p ∈|O′| ∩|O′′|. We must show that O′ ≬ O′′.
Write P′ = interior(|O′|) and P′′ = interior(|O′′|) and note by Corollary 6.1.3 and Lemma 5.1.5 that P′ and P′′ are regular open sets and |P′| = |O′| and |P′′| = |O′′|. Then |P′| ≬|P′′|, so P′ ≬ P′′, and O′ ≬ O′′ follows from Lemma 6.1.4
End of proof

6.3 Regular = quasiregular + hypertransitive

Lemma 6.3.1

Suppose (P, Open) is a semitopology and p ∈ P. Then:

(1) If p is regular then it is hypertransitive.

(2) If p is hypertransitive then it is unconflicted.

(3) The reverse implication need not hold: it is possible for p to be unconflicted but not hypertransitive.

(4) It is possible for p to be hypertransitive (and unconflicted), but not quasiregular (and thus not weakly regular or regular).

Proof

We consider each part:

(1) Suppose p is regular and O, O′ ∈ Open and O ≬ nbhd(p) ≬ O′. By Definition 4.1.4(3) (since p is regular) K(p) is a topen (= open and transitive) neighbourhood of p. Therefore by transitivity O ≬ O′ as required.

(2) Suppose p is hypertransitive and suppose p′, p′′ ∈ P and p′ ≬ p ≬ p′′. Now consider p′ ∈ O′ ∈ Open and p′′ ∈ O′′ ∈ Open. By our intertwinedness assumptions we have that O′ ≬ nbhd(p) ≬ O′′. But p is hypertransitive, so O′ ≬ O′′ as required.

(3) It suffices to provide a counterexample. Consider the bottom right semitopology in Figure 2, and take p = ∗ and O′ = {1} and O′′ = {0, 2}. Note that:

– ∗ is unconflicted, since it is intertwined only with itself and 1.

– O′ and O′ intersect every open neighbourhood of ∗, but O′ ≬̸ O′′, so ∗ is not hypertransitive.

(4) It suffices to provide an example. Consider the semitopology illustrated in Figure 2, top-right diagram; so P = {0, 1, 2} and Open = {∅, {0}, {2}, {1, 2}, {0, 1}, {0, 1, 2}}. The reader can check that p = 1 is hypertransitive, but 1≬= {1} and K(1) = ∅ so p is not quasiregular.End of proof

(Yet) another characterisation of being quasiregular will be helpful:

Lemma 6.3.2

Suppose (P, Open) is a semitopology and p ∈ P. Then the following conditions are equivalent:

(1) p is quasiregular (meaning by Definition 4.1.4(5) that K(p) ≠ ∅).

(2) K(p) ≬ nbhd(p) (meaning by Notation 6.2.1(2) that K(p) ≬ O for every O ∈ nbhd(p)).

(3) p ∈|K(p)|.

Proof

Equivalence of parts 2 and 3 is immediate from Lemma 6.2.2.

For equivalence of parts 1 and 2, we prove two implications:

• Suppose p is quasiregular, meaning by Definition 4.1.4(5) that K(p) ≠ ∅. Pick some p′ ∈ K(p) (it does not matter which). It follows by construction in Definitions 3.5.1(2) and 4.1.4(1) and Lemma 4.1.2 that p′ ≬ p, so that p′ ∈ K(p). Using Definition 3.5.1(1) it follows that K(p) ≬ O for every O ∈ nbhd(p), as required.

• Suppose K(p) ≬ nbhd(p). Then in particular K(p) ≬ P (because p ∈ P ∈ Open), and by Notation 3.1.1(1) it follows that K(p) ≠ ∅.End of proof

Compare and contrast Theorem 6.3.3 with Theorem 5.3.4:

Theorem 6.3.3

Suppose (P, Open) is a semitopology and p ∈ P. Then the following are equivalent:

(1) p is regular.

(2) p is quasiregular and hypertransitive.

Proof

We consider two implications:

• Suppose p is regular. Then p is quasiregular by Lemma 4.1.6(1&2), and hypertransitive by Lemma 6.3.1(1).

• Suppose p is quasiregular and hypertransitive.
By Lemma 6.3.1(2) p is unconflicted. If we can prove that p is weakly regular (meaning by Definition 4.1.4(4) that p ∈ K(p)), then by Theorem 5.3.4 it would follow that p is regular as required. Thus, it would suffice to show that p ∈ K(p), thus that there is an open neighbourhood of points with which p is intertwined. Write O′′ = interior(P\K(p)). We have two subcases to consider:

– Suppose nbhd(p) ≬ O′′. By Lemma 6.3.2 (since p is quasiregular) we have that K(p) ≬ nbhd(p). Thus K(p) ≬ nbhd(p) ≬ O′′, and by hypertransitivity of p it follows that K(p) ≬ O′′. But this contradicts the construction of O′′ as being a subset of P\K(p), so this case is impossible.

– Suppose nbhd(p) ≬̸ O′′. Then there exists some O ∈ nbhd(p) such that O ≬̸ O′′, and it follows that O ⊆ K(p) so that p ∈ K(p) as required.

Thus p is weakly regular, as required.End of proof

Remark 6.3.4

Recall from Definition 4.1.4(3) the notion of a regular point, which in the theory of semitopologies is a canonical well-behavedness property because it ensures that the point is part of a community of other regular points; all in a single maximal intertwined actionable coalition (i.e. open set). We have obtained two nice characterisations of regularity:

(1) Regular = weakly regular + unconflicted, by Theorem 5.3.4.

(2) Regular = quasiregular + hypertransitive, by Theorem 6.3.3.

We are now ready to dualise everything — including semitopologies, regularity, weak regularity, quasiregularity, and being unconflicted and hypertransitive — and thus we will investigate the algebraic structures which correspond to the sets structures above:

7. Semiframes: compatible complete semilattices

7.1 Complete join-semilattices, and morphisms between them

We recall some (mostly standard) definitions and facts:

Definition 7.1.1

(1) A poset (X, ≤) is a set X of elements and a relation ≤⊆ X × X that is transitive, reflexive, and antisymmetric.

(2) A poset (X, ≤) is a complete join-semilattice when every X ⊆ X (X may be empty or equal to all of X) has a least upper bound — or join — ⋁ X ∈ X. All the semilattices we consider will be join (rather than meet) semilattices, so we may omit the word ‘join’ and just call this a complete semilattice henceforth.

(3) If (X, ≤) is a complete semilattice then we may write

⊥X =⋁∅.

By the least upper bound property, ⊥X ≤ x for every x ∈ X.

(4) If (X, ≤) is a complete semilattice then we may write

⊤X =⋁X.

By the least upper bound property, x ≤⊤X for every x ∈ X.

Definition 7.1.2

Suppose (X′, ≤′) and (X, ≤) are complete join-semilattices. Define a morphism g : (X′, ≤′) → (X, ≤) to be a function X′ → X that commutes with joins, and sends ⊤X′ to ⊤X. That is:

(1) If X′ ⊆ X′ then g(⋁ X′) = ⋁ x′∈X′ g(x′).

(2) g(⊤X′) = ⊤X.

Remark 7.1.3

In Definition 7.1.1(2) we insist that g(⊤X′) = ⊤X; i.e. we want our notion of morphism to preserve the top element.

This does not follow from Definition 7.1.1(1), because g need not be surjective onto X, so we need to add this as a separate condition. Contrast with g(⊥X) = ⊥X′, which does follow from Definition 7.1.1(1), because ⊥X is the least upper bound of ∅.

We want g(⊤X′) = ⊤X because our intended model is that (X, ≤) = (Open, ⊆) is the semilattice of open sets of a semitopology (P, Open), and similarly for (X′, ≤′), and g is equal to f -1 where f : (P, Open) → (P′, Open′) is a continuous function.

We recall a standard result:

Lemma 7.1.4

Suppose (X, ≤) is a complete join-semilattice. Then:

(1) If x1, x2 ∈ X then x1 ≤ x2 if and only if x1∨x2 = x2.

(2) If f : (X, ≤) → (X′, ≤′) is a semilattice morphism (Definition 7.1.2) then f is a monotone morphism: if x1 ≤ x2 then f (x1) ≤ f (x2), for every x1, x2 ∈ X.

Proof

We consider each part in turn:

(1) Suppose x1 ≤ x2. By the definition of a least upper bound, this means precisely that x2 is a least upper bound for {x1, x2}. It follows that x1∨x2 = x2. The converse implication follows just by reversing this reasoning.

(2) Suppose x1 ≤ x2. By part 1 of this result x1∨x2 = x2, so f (x1∨x2) = f (x2). By Definition 7.1.2 f (x1)∨ f (x2) = f (x2). By part 1 of this result f (x1) ≤ f (x2).End of proof

Remark 7.1.5

As the reader may know, frames and locales are the same thing: the category of locales is just the categorical opposite of the category of frames. So every time we write ‘semiframe’, the reader can safely read ‘semilocale’; these are two names for essentially the same structure up to reversing arrows. The literature on frames and locales is huge: the interested reader can consult two classic texts [24, 33]; more recent (and very readable) presentations include [39, 40].

7.2 The compatibility relation

Definition 7.2.1 is a simple idea, but so far as we are aware it is novel:

Definition 7.2.1

Suppose (X, ≤) is a complete semilattice. A compatibility relation ∗⊆ X × X is a relation on X such that:

(1) ∗ is symmetric, so if x, x′ ∈ X then

x ∗ x′ if and only if x′ ∗ x.

(2) ∗ is a properly reflexive relation,15 by which we mean

∀x ∈X\{⊥X}.x ∗x.

Note that it will follow from the axioms of a compatibility relation that x ∗ x ⟺⇒ x ≠ ⊥X; see Lemma 7.3.7(2).

(3) ∗ satisfies a distributive law, that if x ∈ X and X′ ⊆ X then

x ∗⋁X′ ⟺⇒∃x′∈X′.x ∗x′.

Thus we can say:

a compatibility relation ∗⊆ X × X is a symmetric properly reflexive completely distributive relation on X.

When x ∗ x′ holds, we may call x and x′ compatible elements.

Remark 7.2.2

The compatibility relation ∗ is what it is, but we take a moment to discuss some intuitions, and to put it in the context of some natural generalisations:

(1) We can think of ∗ as an abstract intersection.
It lets us observe whether x and x′ intersect — but without having to explicitly represent this intersection as a meet x∧x′ in the semilattice itself.
We call ∗ a compatibility relation following an intuition of x, x′ ∈ X as observations, and x ∗ x′ holds when there is some possible world at which it is possible to observe x and x′ together. More on this in Example 7.3.3.

(2) We can think of ∗ as a generalised intersection; so our notion of semiframe in Definition 7.3.1 is an instance of a frame with a generalised meet.
We will concentrate on the case where x ∗ x′ measures whether x and x′ intersect, but there are other possibilities. Here are some natural ways to proceed:

a. (X, ≤) is a complete join-semilattice and ∗ : (X × X) → X is any commutative distributive map. For concreteness, we can set x ∗ x′ ∈{⊥X, ⊤X} ⊆ X.

b. (X, ≤) is a complete join-semilattice and ∗ : (X × X) →N is any commutative distributive map. We think of x ∗ x′ as returning the size of the intersection of x and x′.

c. Any complete join-semilattice (X, ≤) is of course a (generalised) semiframe by taking

x ∗x′ = ⋁{x′′ | x′′ ≤x, x′′ ≤x′}.

d. We can generalise further, in more than one direction. We would take (X, ≤) and (X′, ≤′) to be complete join-semilattices and ∗ : (X × X) → X′ to be any commutative distributive map (which generalises the above). We could also take X to be a cocomplete symmetric monoidal category [32, Section VII]: a category with all colimits and with a (symmetric) monoid action ∗ that distributes over (commutes with) colimits.

e. The compatibility relation ∗ is binary: as noted in part 1 of this Remark it abstracts two open sets having a nonempty open intersection.

However, the literature on distributed systems is rich in well-behavedness conditions based on intersections of sets: e.g. ones corresponding to nonempty ternary intersections between open sets, and on intersections between open and closed sets, and on other types of intersections. These are not thought of in the literature in topological/algebraic terms — that way of looking at things is a contribution of this paper and the recent [18] — but they could be.

This suggests that ∗ may be a (canonical simplest) representative of a design space of ‘nonempty n-ary intersection’ operators, which remains to be explored.

More details, with some references, are in Remark 12.3.6.

Lemma 7.2.3

Suppose (X, ≤) is a complete semilattice and suppose ∗⊆ X × X is a compatibility relation on X. Then:

(1) ∗ is monotone on both arguments. That is: if x1 ∗ x2 and x1 ≤ x′ 1 and x2 ≤ x′ 2, then x′ 1 ∗ x′ 2.

(2) If x1, x2 ∈ X have a non-⊥ lower bound ⊥X ⪇ x ≤ x1, x2, then x1 ∗ x2. In words we can write: ∗ reflects non-⊥ lower bounds.

(3) The converse implication to part 2 need not hold: it may be that x1 ∗ x2 (x1 and x2 are compatible) but the greatest lower bound of {x1, x2} is ⊥.

Proof

We consider each part in turn:

(1) We argue much as for Lemma 7.1.4(1). Suppose x1 ∗ x2 and x1 ≤ x′ 1 and x2 ≤ x′ 2. By Lemma 7.1.4 x1∨x′ 1 = x′ 1 and x2∨x′ 2 = x′ 2. It follows using distributivity and commutativity (Definition 7.2.1(3&1)) that x1 ∗ x2 implies that (x1∨x′ 1) ∗ (x2 ∗ x′ 2), and thus that x′ 1 ∗ x′ 2 as required.

(2) Suppose ⊥X ≠ x ≤ x1, x2, so x is a non-⊥X lower bound. By assumption ∗ is properly reflexive (Definition 7.2.1(2)) so (since x ≠ ⊥X) x ∗ x. By part 1 of this result it follows that x1 ∗ x2 as required.

(3) It suffices to provide a counterexample. Define (X, ≤, ∗) by:

– X = {⊥, 0, 1, ⊤}.

– ⊥≤ 0, 1 ≤⊤ and ¬(0 ≤ 1) and ¬(1 ≤ 0).

– x ∗ x′ for every ⊥≠ x, x′ ∈ X.

We note that 0 ∗ 1 but the greatest lower bound of {0, 1} is ⊥. We will revisit a slightly more elaborate version of this counterexample in Figure 5.End of proof

7.3 The definition of a semiframe

Definition 7.3.1

A semiframe is a tuple (X, ≤, ∗) such that

(1) (X, ≤) is a complete semilattice (Definition 7.1.1), and

(2) ∗ is a compatibility relation on it (Definition 7.2.1).

Slightly abusing terminology, we can say that

semiframe = compatible complete semilattice.

Semiframes are new, so far as we know, but they are a natural idea. We consider some elementary ways to generate examples, starting with arguably the simplest possible instance:

Example 7.3.2 (The empty semiframe).

Suppose (X, ≤, ∗) is a semiframe.

(1) If X is a singleton set, so that X = {•} for some element •, then we call (X, ≤, ∗) the empty semiframe or singleton semiframe. Then necessarily • = ⊥X = ⊤X and • ≤• and ¬(• ∗•).

(2) If X has more than one element then we call (X, ≤, ∗) a nonempty semiframe. Then necessarily ⊥X ≠ ⊤X.

Thus, (X, ≤, ∗) is nonempty if and only if ⊥X ≠ ⊤X. We call a singleton semiframe empty, because this corresponds to the semiframe of open sets of the empty topology, which has no points and one open set, ∅.

Example 7.3.3 continues Remark 7.2.2:

Example 7.3.3

(1) Suppose (P, Open) is a semitopology. Then the reader can check that the semiframe of open sets (P, ⊆, ≬) is a semiframe. We will study this example in detail; see Definition 7.3.4 and Lemma 7.3.5.

(2) Suppose (X, ≤, ⊥, ⊤) is a frame (a complete lattice such that meets distribute over arbitrary joins). Then (X, ≤, ∗) is a semiframe, where x ∗ x′ when x∧x′ ≠ ⊥.16

(3) Take X = {⊥, 0, 1, ⊤} with ⊥≤ 0 ≤⊤ and ⊥≤ 1 ≤⊤ (so 0 and 1 are incomparable). There are two possible semiframe structures on this, characterised by choosing 0 ∗ 1 or ¬(0 ∗ 1).

(4) See also the semiframes used in Lemmas 8.2.7.

Definition 7.3.4 is just an example of semiframes for now, though we will see much more of it later:

Definition 7.3.4 (Semitopology → semiframe).

Suppose (P, Open) is a semitopology. Define the semiframe of open sets Fr(P, Open) (cf. Example 7.3.3(1)) by:

(1) Fr(P, Open) has elements open sets O ∈ Open.

(2) ≤ is subset inclusion.

(3) ∗ is ≬ (sets intersection).

We may write

(Open, ⊆, ≬) as a synonym for Fr(P, Open).

Lemma 7.3.5

Suppose (P, Open) is a semitopology. Then (Open, ⊆, ≬) is indeed a semiframe.

Proof

As per Definition 7.3.1 we must show that Open is a complete semilattice (Definition 7.1.1) and ≬ is a compatibility relation (Definition 7.2.1) — symmetric, properly reflexive, and distributive and satisfies a distributive law that if O ≬⋃ O′ then O ≬ O′ for some O′ ∈ O′. These are all facts of sets.End of proof

Remark 7.3.6

Definition 7.3.4 and Lemma 7.3.5 are the start of our development. Once we have built more machinery, we will have a pair of translations:

• Definition 7.3.4 and Lemma 7.3.5 go from semitopologies to semiframes.

• Definition 8.4.3 and Lemma 8.4.4 go from semiframes to semitopologies.

These translations are part of a dual pair of functors between categories of semitopologies and semiframes, as described in Definitions 10.1.1 and 10.2.1 and Proposition 10.3.7.

Semitopologies are (relatively) concrete: we have concrete points and open sets that are sets of points. Semiframes are more abstract: we have a join-complete semilattice, and a compatibility relation. The duality we are about to build will show how these two worlds interact and reflect each other.

We conclude with a simple technical lemma:

Lemma 7.3.7

Suppose (X, ≤, ∗) is a semiframe (a complete semilattice with a compatibility relation) and x ∈ X. Then:

(1) ¬(x ∗⊥X) and in particular ¬(⊥X ∗⊥X).

(2) x ∗ x if and only if x ≠ ⊥X.

(3) x ∗⊤X if and only if x ≠ ⊥X.

(4) ⊤X ∗⊤X holds precisely if X is nonempty (Example 7.3.2).

Proof

We consider each part in turn:

(1) Recall from Definition 7.1.1(3) that ⊥X = ⋁ ∅. By distributivity (Definition 7.2.1(3))

x ∗⊥X ⟺⇒∃x′ ∈∅.x ∗x′ ⟺⇒⊥.

(2) We just combine part 1 of this result with Definition 7.2.1(2).

(3) Suppose x ≠ ⊥X. Then ⊥X ⪇ x ≤ x ≤⊤X, and by Lemma 7.2.3(2) x ∗⊤X. Suppose x = ⊥X. Then ¬(x ∗⊤X) by combining commutativity of ∗ (Definition 7.2.1(1)) with part 1 of this result.

(4) If X is nonempty then by Example 7.3.2 ⊥X ≠ ⊤X and so ⊤X ∗⊤X holds by part 2 of this result. However, in the degenerate case that X has one element then ⊤X = ⊥X and ⊤X ∗⊤X does not hold.End of proof

Remark 7.3.8

Recall from [13, Definition 5.22, page 128] that if X is a lattice, then the pseudocomplement to x ∈ X is x∗= ⋁{x′ ∈ X | x′ ∧ x = ⊥}. A semiframe (X, ≤, ∗) naturally supports a notion of pseudocomplement for x ∈ X, given by

xc =⋁ {x′ ∈X | ¬(x′ ∗x)}.

It is easy to prove that ¬(xc ∗ x), arguing by contradiction: if xc ∗ x then ⋁{x′ | ¬(x′ ∗ x)} ∗ x, and by distributivity (Definition 7.2.1(3)) there exists x′ ∈ X such that x′ ∗ x and ¬(x′ ∗ x), a contradiction.

Note that it may be that (xc)c ⪇ x. For example, in the semiframe illustrated in Figure 5, 0c = ⋁{1, 2, 3} = ⊤ and (0c)c = ⊥⪇ 0 (this behaviour will be familiar to the reader who has seen, for example, double negation in intuitionistic logic).

xc and related constructions will be useful later, in Definition 11.4.2 and Lemma 11.4.4.

8. Semifilters & abstract points

8.1 The basic definition, and discussion

Definition 8.1.1

Suppose (X, ≤, ∗) is a semiframe and suppose F ⊆ X. Then:

(1) Call F prime when for every x, x′ ∈ X,

x∨x′ ∈F implies x ∈F ∨x′ ∈F.

(2) Call F completely prime when for every (possibly empty) X ⊆ X,

⋁X ∈F implies ∃x∈X.x ∈F.

(This condition is used in Lemma 8.3.2, which is needed for Lemma 8.4.2.)

(3) Call F up-closed when x ∈ F and x ≤ x′ implies x′ ∈ F.

(4) Call F compatible when its elements are pairwise compatible, by which we mean that x ∗ x′ for every x, x′ ∈ F.

(5) A semifilter is a nonempty, up-closed, compatible subset F ⊆ X.

(6) Call F ⊆ X a maximal semifilter when it is a semifilter and is contained in no strictly greater semifilter.

(7) An abstract point is a completely prime semifilter.

(8) Write

Points(X, ≤, ∗)

for the set of abstract points of (X, ≤, ∗).

Notation 8.1.2

We will generally write F ⊆ X for a subset of X that is intended to be a semifilter, or for which in most cases of interest F is a semifilter. We will generally write P ⊆ X when the subset is intended to be an abstract point, or when in most cases of interest P is an abstract point.

Remark 8.1.3

Note on design: The notion of semifilter from Definition 8.1.1 is, obviously, based on the standard notion of filter [24, I.2.2, page 12]. We just replace the closure under binary meets condition

‘if x, x′ ∈ F then x∧x′ ∈ F’

with a weaker compatibility condition

‘if x, x′ ∈ F then x ∗ x′’.

This is in keeping with our move from frames to semiframes, which weakens from ∧ to the compatibility relation ∗.

Note that a semifilter or abstract point need not be directed:

(1) Consider nbhd(0) in the (semiframes of open sets of the) semitopologies in the left-hand and middle examples in Figure 4. In both cases, {0, 1}, {0, 2} ∈ nbhd(0) but {0} /∈ nbhd(0) because {0} is not an open set.

(2) Consider {0, 1, 2} with the discrete semitopology (so every set is open). Then the set of all two- or three-element subsets {{0, 1}, {1, 2}, {2, 0}, {0, 1, 2}} is a semifilter, but it is not closed under sets intersections because it does not contain {0}, {1}, or {2}.

This second example is particularly interesting. As the reader may know, the intuition of a filter in topology is a set of approximations. But this example is clearly not approximating anything — after all, we are in the discrete semitopology and there is no need to approximate anything since we can just take a singleton set! This suggests that a better intuition for semiframe is a set of collaborations; in this case, of 0 with 1, 1 with 2, and 2 with 0.

Thus in particular, the standard result in frames that a proper finite filter17 has a non-⊥ least element (obtained as the finite meet of all the elements in the filter), does not hold for semifilters in semiframes. See also Remark 8.1.6 and Proposition 8.2.8(1).

Example 8.1.4

Suppose (X, ≤, ∗) is a semiframe. We recall some (standard) facts about abstract points, which carry over from topologies and frames:

(1) Suppose (P, Open) is a semitopology and (X, ≤, ∗) = (Open, ⊆, ≬). By Lemma 7.3.5, (X, ≤, ∗) is a semiframe.

If p ∈P thennbhd(p) = {O ∈Open | p ∈O}

from Definition 2.3.1 is an abstract point: see Proposition 9.2.2. Intuitively, nbhd(p) abstractly represents p as the set of all of its open approximations in Open.

(2) Suppose (P, Open) is a semitopology. Then (Open, ⊆, ≬) could contain an abstract point that is not the neighbourhood semifilter nbhd(p) of a point p ∈ P. Set X = {Q} ∪{(π-q, π+q) ⊆Q | q ∈Q≥0} (the set of all symmetric open intervals around π in the rational numbers Q), and set ≤= ⊆ and ∗= ≬. Set P = X\{∅} to be the set of all nonempty symmetric open intervals around π. Note that π /∈Q, but P is a set of open sets ‘approximating’ π.

(3) We mention one more (standard) example. Consider N with the final segment semitopology such that opens are either ∅ or sets n≥= {n′ ∈N | n′ ≥ n}. Then {n≥| n ∈N} is an abstract point. Intuitively, this approximates a point at infinity, which we can understand as ω.

Lemma 8.1.5

Suppose (X, ≤, ∗) is a semiframe and suppose F ⊆ X is compatible. Then ⊥X /∈ F.

Proof

By compatibility, x ∗ x for every x ∈ F. We use Lemma 7.3.7(1).End of proof

Remark 8.1.6

We continue Remark 8.1.3.

As the reader may know, a semiframe still has greatest lower bounds, because we can build them as x∧x′ = ⋁{x′′ | x′′ ≤ x, x′′ ≤ x′}. It is just that this greatest lower bound may be unhelpful. To see why, consider again the examples in Figure 4. In the left-hand and middle examples in Figure 4, the greatest lower bound of {0, 1} and {0, 2} exists in the semiframe of open sets: but it is ∅ the empty set in the left-hand and middle example, not {0}. In the right-hand example, the greatest lower bound of {0, ∗, 1} and {0, ∗, 2} is {0}, not {0, ∗}.

So the reader could ask whether perhaps we should add the following weakened meet-closure condition to the definition of semifilters (and thus to abstract points):

If x, x′ ∈ F and x∧x′ ≠ ⊥ then x∧x′ ∈ F.

Intuitively, this insists that semifilters are closed under non-⊥ greatest lower bounds. However, there are two problems with this:

• It would break our categorical duality proof in the construction of g◦ in Lemma 10.3.3; see the discussion in Remark 10.3.4. This technical difficulty may be superable, but ...

• ...the condition is probably not what we want anyway. It would mean that the set of open neighbourhoods of ∗ in the right-hand example of Figure 4, would not be a semifilter, because it contains {0, ∗, 1} and {0, ∗, 2} but not its (non-∅) greatest lower bound {0}.

0 120 21* 021
Figure 4. Examples of open neighbourhoods (Remarks 8.1.3 and 9.2.1)

8.2 Properties of semifilters

8.2.1 Things that are familiar from filters

Lemma 8.2.1

Suppose (X, ≤, ∗) is a semiframe and F ⊆ X is a semifilter. Then:

(1) ⊤X ∈ F.

(2) ⊥X /∈ F.

Proof

We consider each part in turn:

(1) By nonemptiness (Definition 8.1.1(7)) F is nonempty, so there exists some x ∈ F. By definition x ≤⊤X. By up-closure (Definition 8.1.1(3)) ⊤X ∈ F follows.

(2) By assumption in Definition 8.1.1(4) elements in F are pairwise compatible (so x ∗ x for every x ∈ F). We use Lemma 8.1.5.End of proof

Lemma 8.2.2

Suppose (X, ≤, ∗) is a semiframe. It is possible for a semifilter F ⊆ X to be completely prime but not maximal.

Proof

We give a standard example (which also works for frames and filters). Take P = {0, 1} and Open = {∅, {0}, {0, 1}}. Then P′ = {{0, 1}} is an abstract point, but it is not a maximal semifilter (it is not even a maximal abstract point) since P′ is contained in the strictly larger semifilter {{0}, {0, 1}} (which is itself also a strictly larger abstract point).End of proof

Lemma 8.2.3

If (X, ≤, ∗) is a finite semiframe (meaning that X is finite) then the properties of

• being a prime semifilter (Definition 8.1.1(1)) and

• being a completely prime semifilter (Definition 8.1.1(2)),

coincide.

Proof

This is almost trivial, except that if X = ∅ in the condition for being completely prime then we get that ⊥X /∈ P — but we know that anyway from Lemma 8.2.1(2), from the compatibility condition on semifilters.End of proof

Lemma 8.2.4

Suppose (X, ≤, ∗) is a semiframe. Then:

(1) The union of an ascending chain of semifilters in X, is a semifilter in X.

(2) As a corollary, every semifilter F ⊆ X is contained in some maximal semifilter F′ ⊆ X (assuming Zorn’s lemma).

Proof

We consider each part in turn:

(1) By a straightforward verification of the conditions of being a semifilter from Definition 8.1.1(5).

(2) Direct application of Zorn’s lemma.End of proof

Remark 8.2.5

(1) Lemma 8.2.1(2) has a small twist to it. In the theory of filters, it does not follow from the property of being nonempty, up-closed, and closed under finite meets, that ⊥X /∈ F; this must be added as a distinct condition if required. In contrast, we see in the proof of Lemma 8.2.1(2) that for semifilters, ⊥X /∈ F follows from the compatibility condition.

(2) Lemma 8.2.3 matters in particular to us here, because we are particularly interested in abstracting the behaviours of finite semitopologies, because our original motivation for looking at both of these structures comes from looking at real networks, which are finite.18

8.2.2 Things that are different from filters

Remark 8.2.6

Obviously, by definition semifilters are necessarily compatible but not necessarily closed under meets. But aside from this fact, we have so far seen semiframes and semifilters behave more-or-less like frames and filters, modulo small details like that mentioned in Remark 8.2.5(1).

But there are also differences, as we will now briefly explore. In the theory of (finite) frames, the following facts hold:

(1) Every proper filter F has a greatest lower bound x, and F = x≤= {x′ | x ≤ x′}. Just take x = ⋀ F the meet of all of its (finitely many) elements. This is not ⊥, by the filter’s finite intersection property.

(2) Every proper filter can be extended to a maximal filter.19 Just extend using Zorn’s lemma (as in Lemma 8.2.4).

(3) Every maximal filter is completely prime.

It is a fact of finite frames that a maximal filter is prime,20 and since we assume the frame is finite, it is also completely prime.

(4) Every non-⊥ element x ≠ ⊥X in a finite frame is contained in some abstract point. Just form {x′ | x ≤ x′}, observe it is a filter, form a maximal filter above it, and we get an abstract point.

(5) As a corollary, if the frame is nonempty (so ⊥≠ ⊤; see Example 7.3.2) then it has at least one abstract point.

In Lemma 8.2.7 and Proposition 8.2.8 we consider some corresponding non-properties of (finite) semiframes.

Lemma 8.2.7

Suppose (X, ≤, ∗) is a semiframe. It is possible for Points(X, ≤, ∗) to be empty, even if (X, ≤, ∗) is nonempty (Example 7.3.2(2)). This is possible even if X is finite, and even if X is infinite.

Proof

It suffices to provide an example. We define a semiframe as below, and as illustrated in Figure 5:

• X = {⊥, 0, 1, 2, 3, ⊤}.

• Let x ≤ x′ when x = x′ or x = ⊥ or x′ = ⊤.

• Let x ∗ x′ when x∧x′ ≠ ⊥.21

Then (X, ≤, ∗) has no abstract points.

For suppose P is one such. By Lemma 8.2.1 ⊤∈ P. Note that ⊤= 0∨1 = 2∨3. By assumption P is completely prime, we know that 0 ∈ P ∨ 1 ∈ P, and also 2 ∈ P ∨ 3 ∈ P. But this is impossible because 0, 1, 2, and 3 are not compatible.

For the infinite case, we just increase the width of the semiframe by taking X = {⊥} ∪N ∪ {⊤}.End of proof

Proposition 8.2.8

Suppose (X, ≤, ∗) is a semiframe and F ⊆ X is a semifilter. Then:

(1) It is not necessarily the case that F has a non-⊥ greatest lower bound (even if X is finite).

(2) Every semifilter can be extended to a maximal semifilter, but ...

(3) ...this maximal semifilter is not necessarily prime (even if X is finite).

(4) There may exist a non-⊥ element x ≠ ⊥X that is contained in no abstract point.

Proof

We consider each part in turn:

(1) Consider (pow({0, 1, 2}), ⊆, ≬) and take

F = {{0, 1}, {1, 2}, {0, 2}, {0, 1, 2}}.

The greatest lower bound of F is ∅.

(2) This is Lemma 8.2.4.

(3) F from part 1 of this result is maximal, and it cannot be extended to a point P ⊇ F. Figure 5 gives another counterexample, and in a rather interesting way: the semitopology has four maximal semifilters {i, ⊤} for i ∈{0, 1, 2, 3}, but by Lemma 8.2.7 it has no prime semifilters at all.22

(4) We just take x = 0 ∈ X from the example in Lemma 8.2.7 (see Figure 5). Since this semiframe has no abstract points at all, there is no abstract point that contains x.End of proof

⊤0 1 2 3⊥
Figure 5. A semiframe with no abstract points (Lemma 8.2.7)
Remark 8.2.9

For now, we will just read Proposition 8.2.8 as a caution not to assume that semiframes and semifilters behave like frames and filters. Sometimes they do, and sometimes they don’t; we have to check.

We now proceed to build our categorical duality, culminating with Theorem 10.4.2. Once that machinery is constructed, we will continue our study of the fine structure of semifilters in Section 11.

8.3 Sets of abstract points

Definition 8.3.1

Suppose (X, ≤, ∗) is a semiframe and recall Points(X, ≤, ∗) from Definition 8.1.1(7). Define a map Op : X → pow(Points(X, ≤, ∗)) by

Op(x) = {P ∈Points(X, ≤, ∗) | x ∈P}.
Lemma 8.3.2

Suppose (X, ≤, ∗) is a semiframe and X ⊆ X. Then

Op(⋁X) =⋃ x∈XOp(x).

In words: we can say that Op commutes with joins, and that Op commutes with taking least upper bounds.

Proof

Suppose P ∈ Points(X, ≤, ∗). We reason as follows:

P ∈Op(⋁ X) ⟺⇒⋁ X ∈P Definition 8.3.1⟺⇒∃x∈X.x ∈P Definition 8.1.1(2)⟺⇒P ∈⋃ x∈X Op(x) Definition 8.3.1End of proof
Proposition 8.3.3

Suppose (X, ≤, ∗) is a semiframe and x, x′ ∈ X. Then:

(1) If x ≤ x′ then Op(x) ⊆ Op(x′).

(2) If Op(x) ≬ Op(x′) then x ∗ x′.

(3) Op(⊤X) = Points(X, ≤, ∗) and Op(⊥X) = ∅.

(4) Op(⋁ X) = ⋃ x∈X Op(x) for X ⊆ X.

Proof

We consider each part in turn:

(1) We prove that x ≤ x′ implies Op(x) ⊆ Op(x′).

Suppose x ≤ x′, and consider some abstract point P ∈ Op(x). By Definition 8.3.1 x ∈ P, and by up-closure of P (Definition 8.1.1(3)) x′ ∈ P, so by Definition 8.3.1 P ∈ Op(x′). P was arbitrary, and it follows that Op(x) ⊆ Op(x′).

(2) We prove that Op(x) ≬ Op(x′) implies x ∗ x′. Suppose there exists an abstract point P ∈ Op(x) ∩ Op(x′). By Definition 8.3.1 x, x′ ∈ P, and by compatibility of P (Definition 8.1.1(4)) x ∗ x′.

(3) Unpacking Definition 8.3.1, it suffices to show that ⊤X ∈ P and ⊥X /∈ P, for every abstract point P ∈ Points(X, ≤, ∗). This is from Lemma 8.2.1(1).

(4) This is just Lemma 8.3.2.End of proof

Remark 8.3.4

Proposition 8.3.3 carries a clear suggestion that ({Op(x) | x ∈ X}, ⊆, ≬) is trying, in some sense, to be an isomorphic copy of (X, ≤, ∗). Lemma 8.3.5 notes that it may not quite manage this, because there may not be enough points (indeed, there may not be any abstract points at all). This will (just as for topologies and frames) lead us to the notion of a spatial semiframe in Definition 9.1.2 and Proposition 9.1.4.

Lemma 8.3.5

The converse implications in Proposition 8.3.3(1&2) need not hold. That is:

(1) There exists a semiframe (X, ≤, ∗) and x, x′ ∈ X such that Op(x) ⊆ Op(x′) yet x ≰ x′.

(2) There exists a semiframe (X, ≤, ∗) and x, x′ ∈ X such that x ∗ x′ yet Op(x) ≬̸ Op(x′).

Proof

The example from Lemma 8.2.7 (as illustrated in Figure 5) is a counterexample for both cases:

• Op(0) ⊆ Op(1) because both are equal to the empty set, yet 0 ≰ 1; and

• ⊤∗⊤ yet Op(⊤) ≬̸ Op(⊤).End of proof

8.4 The semitopology of abstract points

Recall from Definition 8.1.1(7) that an abstract point in a semiframe (X, ≤, ∗) is a nonempty up-closed compatible completely prime subset of X, and recall from Definition 8.3.1 that

Op(x) = {P ∈Points(X, ≤, ∗) | x ∈P},

or in words: Op(x) is the set of abstract points that contain x.

Definition 8.4.1

Suppose (X, ≤, ∗) is a semiframe. Then define Op(X, ≤, ∗) by

Op(X, ≤, ∗) = {Op(x) | x ∈X}.
Lemma 8.4.2

Suppose (X, ≤, ∗) is a semiframe. Then:

(1) Op(X, ≤, ∗) from Definition 8.4.1 is closed under arbitrary sets union.

(2) As a corollary, (Op(X, ≤, ∗), ⊆) (in words: Op(X, ≤, ∗) ordered by subset inclusion) is a complete join-semilattice.

Proof

Part 1 is just Lemma 8.3.2. The corollary part 2 is just a fact, since Op(X, ≤, ∗) ⊆ pow(Points(X, ≤, ∗)), and sets union is the join (least upper bound) in the powerset lattice.End of proof

Recall from Definition 7.3.4 and Lemma 7.3.5 that we showed how to go from a semitopology (P, Open) to a semiframe (Open, ⊆, ≬). We now show how to go in the other direction:

Definition 8.4.3 (Semiframe → semitopology).

Suppose (X, ≤, ∗) is a semiframe. Define the semitopology of abstract points St(X, ≤, ∗) by

St(X, ≤, ∗) =(Points(X, ≤, ∗), Op(X, ≤, ∗)).

Unpacking this a little:

(1) The set of points of St(X, ≤, ∗) is the set of abstract points Points(X, ≤, ∗) from Definition 8.1.1(7) — namely, the completely prime nonempty up-closed compatible subsets of X.23

(2) Open sets Opens(X, ≤, ∗) are the Op(x) from Definition 8.3.1:

Op(x) = {P ∈Points(X, ≤, ∗) | x ∈P}.
Lemma 8.4.4

Suppose (X, ≤, ∗) is a semiframe. Then St(X, ≤, ∗) from Definition 8.4.3 is indeed a semitopology.

Proof

From conditions 1 and 2 of Definition 1.2.2, we need to check that Op(X, ≤, ∗) contains ∅ and Points(X, ≤, ∗) and is closed under arbitrary unions. This is from Proposition 8.3.3(3&4).End of proof

Recall from Definitions 8.4.3 and 7.3.4 that St(X, ≤, ∗) is a semitopology, and Fr St(X, ≤, ∗) is a semiframe each of whose elements is the set of abstract points of (X, ≤, ∗) that contain some x ∈ X:

Lemma 8.4.5

Suppose (X, ≤, ∗) is a semiframe. Then Op : (X, ≤, ∗) → Fr St(X, ≤, ∗) is surjective.

Proof

Direct from Definition 8.4.3(2).End of proof

We conclude with Definition 8.4.6 and Proposition 8.4.7, which are standard properties of the construction in Definition 8.4.3.

Definition 8.4.6

Suppose (P, Open) is a semitopology and p, p′ ∈ P. Define p ˚= p′ by

p ˚= p′when ∀O ∈Open.p ∈O ⟺⇒p′ ∈O.

We recall some standard terminology from topology:

(1) Call p and p′ topologically indistinguishable when p ˚= p′.

(2) Call p and p′ topologically distinguishable when ¬(p ˚= p′) (so there exists some O ∈ Open such that p ∈ O ∧ p′ /∈ O or p /∈ O ∧ p′ ∈ O).

(3) Call (P, Open) a T0 space when points are topologically indistinguishable precisely when they are equal, or in symbols: ˚= = =.

Proposition 8.4.7

Suppose (X, ≤, ∗) is a semiframe. Then St(X, ≤, ∗) (Definition 8.4.3) is a T0 space.

Proof

Suppose P, P′ ∈ Points(X, ≤, ∗). Unpacking Definition 8.1.1(7), this means that P and P′ are completely prime nonempty up-closed compatible subsets of X.

It is immediate that P = P′ implies P ˚= P′.

Now suppose P ˚= P′ in St(X, ≤, ∗); to prove P = P′ it would suffice to show that x ∈ P ⟺⇒ x ∈ P′, for arbitrary x ∈ X. By Definition 8.4.3(2), every open set in St(X, ≤, ∗) has the form Op(x) for some x ∈ X. We reason as follows:

x ∈P ⟺⇒P ∈Op(x) Definition 8.3.1⟺⇒P′ ∈Op(x) P, P′ top. indisting.⟺⇒x ∈P′Definition 8.3.1

Since x was arbitrary and P, P′ ⊆ Open, it follows that P = P′ as required.End of proof

9. Spatial semiframes & sober semitopologies

9.1 Definition of spatial semiframes

Remark 9.1.1

We continue Remark 8.3.4. We saw in Example 8.1.4(2&3) that there may be more abstract points than there are concrete points, and in Remark 8.3.4 that there may also be fewer.

In the theory of frames, the condition of being spatial means that the abstract points and concrete points correspond. We imitate this terminology for a corresponding definition on semiframes:

Definition 9.1.2 (Spatial semiframe).

Call a semiframe (X, ≤, ∗) spatial when:

(1) Op(x) ⊆ Op(x′) implies x ≤ x′, for every x, x′ ∈ X.

(2) x ∗ x′ implies Op(x) ≬ Op(x′), for every x, x′ ∈ X.

Remark 9.1.3

Not every semiframe is spatial, just as not every frame is spatial. Lemma 8.2.7 gives an example of a semiframe that is not spatial because it has no points at all, as illustrated in Figure 5.

We check that the conditions in Definition 9.1.2 correctly strengthen the implications in Proposition 8.3.3 to become logical equivalences:

Proposition 9.1.4

Suppose (X, ≤, ∗) is a spatial semiframe and x, x′ ∈ X. Then:

(1) x ≤ x′ if and only if Op(x) ⊆ Op(x′).

(2) x ∗ x′ if and only if Op(x) ≬ Op(x′).

(3) x = x′ if and only if Op(x) = Op(x′).

(4) Op(⊤X) = Points(X, ≤, ∗) and Op(⊥X) = ∅.

(5) Op(⋁ X) = ⋃ x∈X Op(x) for X ⊆ X.

Proof

We consider each part in turn:

(1) We prove that x ≤ x′ if and only if Op(x) ⊆ Op(x′). The right-to-left implication is direct from Definition 9.1.2(1). The left-to-right implication is Proposition 8.3.3(1).

(2) We prove that x ∗ x′ if and only if Op(x) ≬ Op(x′). The left-to-right implication is direct from Definition 9.1.2(2). The right-to-left implication is Proposition 8.3.3(2).

(3) We prove that x = x′ if and only if Op(x) = Op(x′).
If x = x′ then Op(x) = Op(x′) is immediate. If Op(x) = Op(x′) then Op(x) ⊆ Op(x′) and Op(x′) ⊆ Op(x). By part 1 of this result (or direct from Definition 9.1.2(1)) x ≤ x′ and x′ ≤ x. By antisymmetry of ≤ it follows that x = x′.

(4) This is just Proposition 8.3.3(3)

(5) This is just Lemma 8.3.2.End of proof

Definition 9.1.5 will be useful in a moment:24

Definition 9.1.5

Suppose (X, ≤, ∗) and (X′, ≤′, ∗′) are semiframes. Then an isomorphism between them is a function g : X → X′ such that:

(1) g is a bijection between X and X′.

(2) x1 ≤ x2 if and only if g(x1) ≤ g(x2).

(3) x1 ∗ x2 if and only if g(x1) ∗ g(x2).

Lemma 9.1.6

Suppose (X, ≤, ∗) and (X′, ≤′, ∗′) are semiframes and g : X → X′ is an isomorphism between them. Then g(⊥X) = g(⊥X′) and g(⊤X) = ⊤X′.

Proof

By construction ⊥X ≤ x for every x ∈ X. It follows from Definition 9.1.5(2) that g(⊥X) ≤ g(x) for every x ∈ X; but g is a bijection, so g(⊥X) ≤ x′ for every x′ ∈ X′. It follows that g(⊥X) = ⊥X′.

By similar reasoning we conclude that g(⊤X) = ⊤X′.End of proof

Remark 9.1.7

Suppose (X, ≤, ∗) is a semiframe and recall from Definition 8.4.1 that Op(X, ≤ , ∗) = {Op(x) | x ∈ X}. Then the intuitive content of Proposition 9.1.4 is that a semiframe (X, ≤, ∗) is spatial when (X, ≤, ∗) is isomorphic (in the sense made formal by Definition 9.1.5) to (Op(X, ≤ , ∗), ⊆, ≬).

And, because Op(⊤X) = Points(X, ≤, ∗) we can write a slogan:

A semiframe is spatial when it is (up to isomorphism) generated by its abstract points.

We will go on to prove in Proposition 9.2.5 that every semitopology generates a spatial semiframe — and in Theorem 10.4.2 we will tighten and extend the slogan above to a full categorical duality.

9.2 The neighbourhood semifilter nbhd(p)

9.2.1 The definition and basic lemma

Recall from Definition 2.3.1 that we define nbhd(p) = {O ∈ Open | p ∈ O}.

Remark 9.2.1

If (P, Open) is a topology, then nbhd(p) is a filter (a nonempty up-closed down-directed set) and is often called the neighbourhood filter of p.

We are working with semitopologies, so Open is not necessarily closed under intersections, and nbhd(p) is not necessarily a filter (it is still a compatible set, because every O ∈ nbhd(p) contains p). Figure 4 illustrates examples of this: e.g. in the left-hand example {0, 1}, {0, 2} ∈ nbhd(0) but {0} ∉ nbhd(0) (because this is not an open set).

Recall from Definition 2.3.1 that nbhd(p) = {O ∈ Open | p ∈ O}.

Proposition 9.2.2

Suppose (P, Open) is a semitopology and p ∈ P and O ∈ Open. Then:

(1) nbhd(p) (Definition 2.3.1) is an abstract point (a completely prime semifilter) in the semiframe Fr(P, Open) (Definition 7.3.4). In symbols:

nbhd : P →Points(Fr(P, Open)).

(2) The following are equivalent:

nbhd(p) ∈Op(O) ⟺⇒ O ∈nbhd(p) ⟺⇒ p ∈O.

(3) We have an equality:

nbhd-1(Op(O)) = O.
Proof

We consider each part in turn:

(1) From Definition 8.1.1(7), we must check that nbhd(p) is a nonempty, completely prime, up-closed, and compatible subset of Open when considered as a semiframe as per Definition 7.3.4. All properties are by facts of sets; we give brief details:

– nbhd(p) is nonempty because p ∈ P ∈ Open.

– nbhd(p) is completely prime because it is a fact of sets that if P ⊆ Open and p ∈⋃ P then p ∈ O for some O ∈ P.

– nbhd(p) is up-closed because it is a fact of sets that if p ∈ O and O ⊆ O′ then p ∈ O′.

– nbhd(p) is compatible because if p ∈ O and p ∈ O′ then O ≬ O′.

(2) By Definition 8.3.1, Op(O) is precisely the set of abstract points P that contain O, and by part 1 of this result nbhd(p) is one of those points. By Definition 2.3.1, nbhd(p) is precisely the set of open sets that contain p. The equivalence follows.

(3) We reason as follows:

p ∈ nbhd-1(Op(O)) ⟺⇒ nbhd(p) ∈ Op(O) Fact of function inverse

⟺⇒p ∈O Part 2 of this resultEnd of proof
Corollary 9.2.3

Suppose (P, Open) is a semitopology and O, O′ ∈ Open. Then:

(1) Op(O) ⊆ Op(O′) if and only if O ⊆ O′.

(2) Op(O) ≬ Op(O′) if and only if O ≬ O′.

(3) As a corollary, nbhd-1(∅) = ∅ and nbhd-1(Points(Open, ⊆, ≬)) = P; i.e. nbhd-1 maps the bottom/top element to the bottom/top element.

Proof

We consider each part in turn:

(1) If Op(O) ⊆ Op(O′) then nbhd-1(Op(O)) ⊆ nbhd-1(Op(O′)) by facts of inverse images, and O ⊆ O′ follows by Proposition 9.2.2(3). If O ⊆ O′ then Op(O) ⊆ Op(O′) by Proposition 8.3.3(1).

(2) If O ≬ O′ then there exists some point p ∈ P with p ∈ O ∩ O′. By Proposition 9.2.2(1) nbhd(p) is an abstract point, and by Proposition 9.2.2(2) nbhd(p) ∈ Op(O) ∩ Op(O′); thus Op(O) ≬ Op(O′). If Op(O) ≬ Op(O′) then O ≬ O′ by Proposition 8.3.3(2).

(3) Routine from Proposition 8.3.3(3) (or from Lemma 9.1.6).End of proof

9.2.2 Application to semiframes of open sets

Proposition 9.2.4

Suppose (P, Open) is a semitopology. Then:

(1) nbhd-1 bijects open sets of St(Open, ⊆, ≬) (as defined in Definition 8.4.3(2)), with open sets of (P, Open), taking Op(O) to O.

(2) nbhd-1 is an isomorphism between the semiframe of open sets of St(Open, ⊆, ≬), and the semiframe of open sets of (P, Open) (Definition 9.1.5).

Proof

We consider each part in turn:

(1) Unpacking Definition 8.4.3(2), an open set in St Fr(P, Open) has the form Op(O) for some O ∈ Open. By Proposition 9.2.2(3) nbhd-1(Op(O)) = O, and so nbhd-1 is surjective and injective.

(2) Unpacking Definition 9.1.5 it suffices to check that:

– nbhd-1 is a bijection, and maps Op(O) to O.

– Op(O) ⊆ Op(O′) if and only if O ⊆ O′.

– Op(O) ≬ Op(O′) if and only if O ≬ O′.

The first condition is part 1 of this result; the second and third are from Corollary 9.2.3.End of proof

Proposition 9.2.5

Suppose (P, Open) is a semitopology. Then the semiframe Fr(P, Open) = (Open, ⊆, ≬) from Definition 7.3.4 is spatial.

Proof

The properties required by Definition 9.1.2 are that Op(O) ⊆ Op(O′) implies O ⊆ O′, and O ≬ O′ implies Op(O) ≬ Op(O′). Both of these are immediate from Proposition 9.2.4(2).End of proof

9.2.3 Application to characterise T0 spaces

Lemma 9.2.6

Suppose (P, Open) is a semitopology and p, p′ ∈ P. Then the following are equivalent:

(1) nbhd(p) = nbhd(p′) (cf. also Lemma 11.7.1)

(2) ∀O∈Open.p ∈ O ⟺⇒ p ∈ O′

(3) p ˚= p′ (Definition 8.4.6: p and p′ are topologically indistinguishable in (P, Open)).

(4) nbhd(p) ˚= nbhd(p′) (nbhd(p) and nbhd(p′) are topologically indistinguishable as — by Proposition 9.2.2(1) — abstract points in St Fr(P, Open)).

Proof

Equivalence of parts 1 and 2 is direct from Definition 2.3.1. Equivalence of parts 2 and 3 is just Definition 8.4.6(1). Equivalence of parts 4 and 1 is from Proposition 8.4.7.End of proof

Corollary 9.2.7

Suppose (P, Open) is a semitopology. Then the following are equivalent:

(1) (P, Open) is T0 (Definition 8.4.6(3)).

(2) nbhd : P → Points(Open, ⊆, ≬) is injective.

Proof

Suppose (P, Open) is T0, and suppose nbhd(p) = nbhd(p′). By Lemma 9.2.6(1&3) p ˚= p′. By Definition 8.4.6(2) p = p′. Since p and p′ were arbitrary, nbhd is injective.

Suppose nbhd is injective. Reversing the reasoning of the previous paragraph, we deduce that (P, Open) is T0.End of proof

9.3 Sober semitopologies

Recall from Proposition 9.2.5 that if we go from a semitopology (P, Open) to a semiframe (Open, ⊆, ≬), then the result is not just any old semiframe — it is a spatial one.

We now investigate what happens when we go from a semiframe to a semitopology using Definition 8.4.3.

9.3.1 The definition and a key result

Definition 9.3.1

Call a semitopology (P, Open) sober when every abstract point P of Fr(P, Open) — i.e. every completely prime nonempty up-closed compatible set of open sets — is equal to the neighbourhood semifilter nbhd(p) of some unique p ∈ P.

Equivalently, (P, Open) is sober when nbhd : P → Points(Fr(P, Open)) (Definition 8.1.1(7)) is a bijection.

Remark 9.3.2

A bijection is a map that is injective and a surjective. We noted in Corollary 9.2.7 that a space is T0 when nbhd is injective. So the sobriety condition can be thought of as having two parts:

• nbhd is injective and the space is T0, so it intuitively contains no ‘unnecessary’ duplicates of points;

• nbhd is surjective, so the space contains ‘enough’ points that there is (precisely) one concrete point for every abstract point.25

We start with a very simple example of sober semitopologies:

Lemma 9.3.3

Suppose P is any set. Then the discrete semitopology (P, pow(Open)) is sober.

Proof

Consider an abstract point P ⊆ Open (completely prime nonempty up-closed and compatible, as per Definition 8.1.1(7)). Then P ∈ P and P = ⋁{{p} | p ∈ P}. Since P is completely prime, {p} ∈ P for some p ∈ P. It follows easily that P = nbhd(p).End of proof

Example 9.3.4

We give some more examples of sober and non-sober semitopologies.

(1) Take P = {0, 1} and Open = {∅, {0, 1}}. This has one abstract point P = {{0, 1}} but two concrete points 0 and 1. It is therefore not sober.

(2) Take P = {0, 1} and Open = {∅, {1}, {0, 1}}. This has two abstract points

{{1}, {0, 1}} and {{0, 1}}

corresponding to two concrete points 0 and 1. It is sober.

(3) Take P = N with the final topology; so O ∈ Open when O = ∅ or O = n≥ for some n ∈N, where n≥= {n′ ∈N | n′ ≥ n}. Take P = {n≥| n ∈N}. The reader can check that this is an abstract point (up-closed, completely prime, compatible); however P is not the neighbourhood semifilter of any n ∈N. Thus this space is not sober.

(4) R with its usual topology (which is also a semitopology) is sober. This is a known result for topologies, but Remark 8.1.3 (and also the later Remark 9.3.11) caution us that we cannot take this for granted, so we sketch the proof. Suppose P is an abstract point; we wish to exhibit a unique p ∈R such that P = nbhd(p). We cover R with open intervals of radius 1 by writing R = ⋃{(r-0.5, r+0.5) | r ∈R}, and we use the completely prime property to find (at least one) such open interval that is in P; write it O1 ∈ P. We then cover O1 with open intervals of radius at most 1/2 by writing O1 = ⋃{O1 ∩ (r-0.25, r+0.25) | r ∈ O1}, and we iterate to obtain a sequence (Oi | i ∈N) ⊆ P. This converges to some unique p ∈R. We check that P = nbhd(p):

– Suppose O ∈ Open is such that p ∈ O. Because p ∈ O, there exists some ε such that (p-ε, p+ε) ⊆ O. It follows that for i > 1/ε we have Oi ⊆ O and thus O ∈ P by up-closedness.

– Suppose O′ ∈ Open is such that p /∈ O′. For a sufficiently large i we have Oi ≬̸ O′, so by compatibility it follows that O′ /∈ P.

(5) Q is sober. The argument is much as for R above. We have to work just a little harder because the p we obtain need not be rational, but the arguments on open intervals remain valid.

Proposition 9.3.5

Suppose (X, ≤, ∗) is a semiframe. Then St(X, ≤, ∗) from Definition 8.4.3 is a sober semitopology.

0 213102ACBD
Figure 6. Two counterexamples for sobriety: (a) finite T0 (and also T1) semitopology that is not sober (Lemma 9.3.8); (b) Hausdorff semitopology that is not sober (Lemma 9.3.10)
Proof

We know from Lemma 8.4.4 that St(X, ≤, ∗) is a semitopology. The issue is whether it is sober; thus by Definition 9.3.1 we wish to exhibit every abstract point P of Fr St(X, ≤, ∗) as a neighbourhood semifilter nbhd(p) for some unique abstract point p of (X, ≤, ∗). The calculations to do so are routine, but we give details.

Fix some abstract point P of Fr St(X, ≤, ∗). By Definition 8.1.1(7), P is a completely prime nonempty up-closed set of intersecting open sets in the semitopology St(X, ≤, ∗), and by Definition 8.4.3(2) each open set in St(X, ≤, ∗) has the form Op(x) = {p ∈ Points(X, ≤, ∗) | x ∈ p} for some x ∈ X.

We define p ⊆ X as follows:

p = {x ∈X | Op(x) ∈P} ⊆X.

By construction we have that x ∈ p if and only if Op(x) ∈ P, and so

nbhd(p) = {Op(x) | p ∈Op(x)} Definition 2.3.1= {Op(x) | x ∈p} Definition 8.3.1= {Op(x) | Op(x) ∈P} Construction of p= P Fact.

Now P is completely prime, nonempty, up-closed, and compatible and it follows by elementary calculations using Proposition 9.1.4 that p is also completely prime, nonempty, up-closed, and compatible — so p is an abstract point of (X, ≤, ∗).

So we have that

p ∈Point(X, ≤, ∗) and P = nbhd(p).

To prove uniqueness of p, suppose p′ is any other abstract point such that P = nbhd(p′). We follow the definitions: Op(x) ∈ nbhd(p′) ⟺⇒ Op(x) ∈ nbhd(p), and thus by Definition 2.3.1 p′ ∈ Op(x) ⟺⇒ p ∈ Op(x), and thus by Definition 8.3.1 x ∈ p′ ⟺⇒ x ∈ p, and thus p′ = p.End of proof

9.3.2 Sober topologies contrasted with sober semitopologies

We will need Notation 9.3.6 for Remark 9.3.7:

Notation 9.3.6

Call a closed set irreducible when it cannot be written as the union of two proper closed subsets.

Remark 9.3.7

Topology has a wealth of separation actions. Three of them are: T0 (distinct points have distinct neighbourhood (semi)filters); T1 (distinct points have distinct open neighbourhoods); and T2, also known as the Hausdorff condition (distinct points have disjoint open neighbourhoods) — see Remark 4.2.1 for formal statements. For topologies, the following is known of sobriety:

(1) Every finite T0 (and thus every finite T1) topological space is sober.

(2) Every T2/Hausdorff space (including infinite ones) is sober [33, page 475, Theorem 3].

(3) A topological space is sober if and only if every nonempty irreducible closed set is the closure of a unique point [33, page 475].

The situation for semitopologies is different, as we explore in the rest of this Subsection.

0 21••••BAC3102ACBD• •• •
Figure 7. Soberifications of the examples in Figure 6 (Remark 9.3.12)
Lemma 9.3.8

(1) It is not necessarily the case that a finite T0 semitopology (or even a finite T1 semitopology) is sober (Definition 9.3.1).

(2) It is not necessarily the case that if every nonempty irreducible closed set is the closure of a unique point, then a semitopology is sober.

These non-implications hold even if the semitopology is regular (so p ∈ K(p) ∈ Topen for every p; see Definition 4.1.4(3)).

Proof

We provide a semitopology that is a counterexample for both parts.

Consider the left-hand semitopology illustrated in Figure 6, so that:

• P = {0, 1, 2}, and

• Open = {∅, {0, 1}, {1, 2}, {0, 2}, {0, 1, 2}}.

We note that:

• (P, Open) is T0 and T1.

• (P, Open) is regular because all points are intertwined, so that K(p) = P for every p ∈ P.

• The nonempty irreducible closed sets are {0} (which is the complement of {1, 2}), {1}, and {2}. Since these are singleton sets, they are certainly the closures of unique points.

So (P, Open) is T0, regular, and irreducible closed sets are the closures of unique points.

We take as our semifilter P = Open\{∅}. The reader can check that P is completely prime (Definition 8.1.1(2)), nonempty, up-closed, and compatible (P is also the greatest semifilter); but, P is not the neighbourhood semifilter of 0, 1, or 2 in P. Thus, (P, Open) is not sober.End of proof

Remark 9.3.9

The counterexample used in Lemma 9.3.8 generalises, as follows: the reader can check that the all-but-one semitopology from Example 2.1.4(5c) on three or more points (so open sets are generated by P\{p} for every p ∈ P) has similar behaviour.

In topology, every Hausdorff space is sober. In semitopologies, this implication does not hold, and in a rather strong sense:

Lemma 9.3.10

(1) It is not necessarily the case that if a semitopology is Hausdorff, then it is sober.

(2) Every quasiregular Hausdorff semitopology is (discrete and therefore) sober.

Proof

We consider each part in turn:

(1) It suffices to give a counterexample. Consider the right-hand semitopology illustrated in Figure 6 (which we also used, for different purposes, in Figure 3), so that:

– P = {0, 1, 2, 3}, and

– Open is generated by X = {{3, 0}, {0, 1}, {1, 2}, {2, 3}}.

This is Hausdorff, but it is not sober: the reader can check that the up-closure {3, 0}≤⊆ Open is nonempty, up-closed, compatible, and completely prime, but it is not the neighbourhood filter of any p ∈ P.

(2) From Lemmas 4.2.2 (quasiregular Hausdorff is discrete) and 9.3.3 (discrete is sober).End of proof

Remark 9.3.11

A bit more discussion of Lemma 9.3.10.

(1) The space used in the counterexample for part 1 is Hausdorff, T1, and unconflicted (Definition 5.3.1(2)). It is not quasiregular (Definition 4.1.4(5)) because the community of every point is empty; see Proposition 5.3.3.

(2) The implication holds if we add quasiregularity as a condition: every quasiregular Hausdorff space is sober. But, this holds for very bad reasons, because by Lemma 4.2.2 every quasiregular Hausdorff space is discrete.

(3) Thus, the non-implication discussed in Lemma 9.3.10 is informative and tells us something interesting about semitopological sobriety. Semitopological sobriety is not just a weak form of topological sobriety, and it has its own distinct personality.

Remark 9.3.12

We can inject the examples illustrated in Figure 6 (used in Lemmas 9.3.8 and 9.3.10) into soberified versions of the spaces that are sober and have an isomorphic lattice of open sets, as illustrated in Figure 7:

(1) The left-hand semitopology has abstract points (completely prime semifilters; see Definition 8.1.1(2)) generated as the ⊆-up-closures of the following sets: {A}, {B}, {C}, {A, B}, {B, C}, {C, A}, and {A, B, C}. Of these, {A, B}⊆= nbhd(0), {B, C}⊆= nbhd(1), and {C, A}⊆= nbhd(2). The other completely prime semifilters are not generated as the neighbourhood semifilters of any point in the original space, so we add points as illustrated using • in the left-hand diagram in Figure 7. This semitopology is sober, and has the same semiframe of open sets.

(2) For the right-hand example, we again add a • point for every abstract point in the original space that is not already the neighbourhood semifilter of a point in the original space. These abstract points are generated as the ⊆-up-closures of {A}, {B}, {C}, and {D}.
There is no need to add a • for the abstract point generated as the ⊆-up-closure of {A, B}, because {A, B}⊆= nbhd(0). Similarly {B, C}⊆= nbhd(1), {C, D}⊆= nbhd(2), and {D, A}⊆= nbhd(3). Note that {A, B, C} does not generate an abstract point because it is not compatible: A ≬̸ C. Similarly for {B, C, D}, {C, D, A}, {D, A, C}, and {A, B, C, D}.

These soberified spaces are instances of a general construction described in Theorem 10.1.4. And, continuing the observation made in Remark 9.3.11, note that neither of these spaces, with their extra points, are Hausdorff.

10. Four categories & functors between them

10.1 The categories SemiTop/Sober of semitopologies/sober semitopologies

Definition 10.1.1

(1) Suppose (P, Open) and (P′, Open′) are semitopologies and f : P → P′ is any function. Then call f a morphism of semitopologies when f is continuous, by which we mean (as standard) that

O′ ∈Open′implies f-1(O′) ∈Open.

(2) Define SemiTop the category of semitopologies such that:

– objects are semitopologies, and

– arrows are morphisms of semitopologies (continuous maps on points).26

(3) Write Sober for the category of sober semitopologies and continuous functions between them. By construction, Sober is the full subcategory of SemiTop, on its sober semitopologies.

Remark 10.1.2

For convenience reading Theorem 10.1.4 we recall some facts:

(1) The semiframe

Fr(P, Open) = (Open, ⊆, ≬)

from Definition 7.3.4 has elements open sets O ∈ Open, preordered by subset inclusion and with a compatibility relation given by sets intersection. It is spatial, by Proposition 9.2.5.

(2) An abstract point P in Points(Fr(P, Open)) is a completely prime nonempty up-closed compatible subset of Open.

(3) St Fr(P, Open) is by Definition 8.4.3 a semitopology such that:

a. Its set of points is Points(Fr(P, Open)); the set of abstract points in Fr(P, Open) = (Open, ⊆, ≬), the semilattice of open sets of (P, Open), and

b. Its open sets are given by the Op(O), for O ∈ Open.

It is sober, by Proposition 9.3.5.

Continuing Remark 10.1.2, a notation will be useful:

Notation 10.1.3

Suppose (P, Open) is a semitopology. Then define

Soberify(P, Open) = St Fr(P, Open).

We may use Soberify(P, Open) and St Fr(P, Open) interchangeably, depending on whether we want to emphasise “this is a sober semitopology obtained from (P, Open)” or “this is St acting on Fr(P, Open) = (Open, ⊆, ≬)”.

Theorem 10.1.4

Suppose (P, Open) is a semitopology. Then

(1) nbhd : P → Points(Fr(P, Open)) is a morphism of semitopologies from (P, Open) to St Fr(P, Open) = Soberify(P, Open)

(2) taking (P, Open) to a sober semitopology Soberify(P, Open), such that

(3) nbhd-1 induces a bijection on open sets by mapping Op(O) to O, and furthermore this is an isomorphism of the semiframes of open sets, in the sense of Definition 9.1.5.

Proof

We consider each part in turn:

(1) Following Definition 10.1.1 we must show that nbhd is continuous (inverse images of open sets are open) from (P, Open) to Soberify(P, Open). So following Definition 8.4.3(2), consider Op(O) ∈ Open(Soberify(P, Open)). By Proposition 9.2.2(3)

nbhd-1(Op(O)) = O ∈Open.

Continuity follows.

(2) Soberify(P, Open) is sober by Proposition 9.3.5.

(3) This is Proposition 9.2.4.End of proof

Remark 10.1.5

We can summarise Theorem 10.1.4 as follows:

(1) By construction, the kernel of the nbhd function (the relation determined by which points it maps to equal elements) is topological indistinguishability ˚=.

(2) We can think of St Fr(P, Open) as being obtained from (P, Open) by

a. quotienting topologically equivalent points to obtain a T0 space, and then

b. adding extra points to make it sober.

See also the discussion in Remark 9.3.2 about what it means to have ‘enough’ points.

(3) This is done without affecting the semiframe of open sets (up to isomorphism), with the semiframe bijection given by nbhd-1.

In this sense, we can view St Fr(P, Open) as a soberification of (P, Open).

10.2 The categories SemiFrame/Spatial of semiframes/spatial semiframes

Definition 10.2.1

(1) Suppose (X, ≤, ∗) and (X′, ≤′, ∗′) are semiframes (Definition 7.3.1) and g : X → X′ is any function. Then call g a morphism of semiframes when:

a. g is a morphism of complete semilattices (Definition 7.1.2).

b. g is compatible, by which we mean that g(x′) ∗ g(x′′) implies x′ ∗ x′′ for every x′, x′′ ∈ X′.

(2) We define SemiFrame the category of semiframes such that:

– objects are semiframes, and

– arrows are morphisms of semiframes.

(3) Write Spatial for the category of spatial semiframes and semiframe morphisms between them. By construction, Spatial is the full subcategory of SemiFrame, on its spatial semiframes (Definition 9.1.2).

Lemma 10.2.2

Suppose (X, ≤, ∗) is a semiframe. Then Op : (X, ≤, ∗) → Fr St(X, ≤, ∗) is a morphism of semiframes and is surjective on underlying sets.

Proof

Following Definition 10.2.1(1) we must show that

• Op is a semilattice morphism (Definition 7.1.2) — commutes with joins and maps ⊤X to Points(X, ≤, ∗)) — and

• is compatible with the compatibility relation ∗, and

• we must show that Op is surjective.

We consider each property in turn:

• Op is a semilattice morphism. Op(⋁ X) = ⋁ x∈X Op(x) by Lemma 8.3.2, and Op(⊤X) = Points(X, ≤, ∗) by Proposition 8.3.3(3).

• Op is compatible with ∗. Unpacking Definition 10.2.1(1b), we must show that Op(x) ≬ Op(x′) implies x ∗ x′. We use Proposition 8.3.3(2).

• Op is surjective ... by Lemma 8.4.5.End of proof

10.3 Functoriality of the maps

Definition 10.3.1

Suppose g : (X′, ≤′, ∗′) → (X, ≤, ∗) ∈ SemiFrame. Define a mapping g◦ : St(X, ≤, ∗) → St(X′, ≤′, ∗′) by

g◦: Points(X, ≤, ∗) −⟶ Points(X′, ≤′, ∗′)P⟼ −→ P′ = {x′ ∈X′ | g(x′) ∈P}.
Remark 10.3.2

We will show that g◦ from Definition 10.3.1 is an arrow in SemiTop. We will need to prove the following:

• If P ∈ Points(X, ≤, ∗) then g◦(P) ∈ Points(X′, ≤′, ∗′).

• g◦ is a morphism of semitopologies.

We do this in Lemmas 10.3.3 and 10.3.6 respectively.

Lemma 10.3.3 (g◦ well-defined).

Suppose g : (X′, ≤′, ∗′) → (X, ≤, ∗) ∈ SemiFrame and suppose P ∈ Points(X, ≤, ∗). Then g◦(P) from Definition 10.3.1 is indeed in Points(X′, ≤′, ∗′) — and thus g◦ is well-defined function from Points(X, ≤, ∗) to Points(X′, ≤′, ∗′).

Proof

For brevity write

P′ = {x′ ∈X′ | g(x′) ∈P}.

We must check that P′ is a completely prime nonempty up-closed compatible subset of X′. We consider each property in turn:

(1) P′ is completely prime. Consider some X′ ⊆ P′ and suppose g(⋁ X′) ∈ P. By Definition 10.2.1(1a) g is a semilattice homomorphism, so by Definition 7.1.1(2) g(⋁ X′) = ⋁ x′∈X′ g(x′). Thus ⋁ x′∈X′ g(x′) ∈ P. By assumption P is completely prime, so g(x′) ∈ P for some x′ ∈ X′. Thus x′ ∈ P′ for that x′. Since X′ was arbitrary, it follows that P′ is completely prime.

(2) P′ is nonempty. By assumption g is an arrow in SemiFrame (i.e. a semiframe morphism) and unpacking Definition 10.2.1(1a) it follows that it is a semilattice homomorphism. In particular by Definition 7.1.1(2) g(⊤X′) = ⊤X, and by Lemma 8.2.1(1) ⊤X ∈ P. Thus ⊤X′ ∈ P′, so P′ is nonempty.

(3) P′ is up-closed.
Suppose x′ ∈ P′ and x′ ≤ x′′. By construction g(x′) ∈ P. By Lemma 7.1.4 (because g is a semilattice morphism by Definition 10.2.1(1a)) g is monotone, so g(x′) ≤ g(x′′). By

assumption in Definition 8.1.1(3) P is up-closed, so that g(x′′) ∈ P and thus x′′ ∈ P′ as required.

(4) P′ is compatible. Suppose x′, x′′ ∈ P′. Thus g(x′), g(x′′) ∈ P. By assumption in Definition 8.1.1(4) P is compatible, so g(x′) ∗ g(x′′). By compatibility of g (Definition 10.2.1(1b)) it follows that x′ ∗ x′′. Thus P′ is compatible.End of proof

Remark 10.3.4

Note on design: If we want to impose further conditions on being an abstract point (such as those discussed in Remark 8.1.6) then Lemma 10.3.3 would need to be extended to show that these further conditions are preserved by the g◦ operation, so that for P ∈ Points(X, ≤, ∗) an abstract point in (X, ≤, ∗), g◦(P) = {x′ ∈ X′ | g(x′) ∈ P} is an abstract point in (X′, ≤′, ∗′).

For example: consider what would happen if we add the extra condition on semifilters from Remark 8.1.6. Then the P′ defined in the proof of Lemma 10.3.3 above might not be closed under this additional condition (it will be if g is surjective). This could be mended by closing P′ under greatest lower bounds that are not ⊥, but that in turn might compromise the property of being completely prime. These comments are not a proof that the problems would be insuperable; but they suggest that complexity would be added. For now, we prefer to keep things simple!

Lemma 10.3.5

Suppose g : (X′, ≤′, ∗′) → (X, ≤, ∗) ∈ SemiFrame, and suppose x′ ∈ X′. Then

(g◦)-1(Op(x′)) = Op(g(x′)).
Proof

Consider an abstract point P ∈ Point(Gr(X′, ≤′, ∗′)). We just chase definitions:

p57-four-row-derivationP ∈(g◦)-1(Op(x′)) ⟺⇒g◦(P) ∈Op(x′) Fact of inverse image⟺⇒x′ ∈g◦(P) Definition 8.3.1⟺⇒g(x′) ∈P Definition 10.3.1⟺⇒P ∈Op(g(x′)). Definition 8.3.1

The choice of P was arbitrary, so (g◦)-1(Op(x′)) = Op(g(x′)) as required.End of proof

Lemma 10.3.6 (g◦ continuous).

Suppose g : (X′, ≤′, ∗′) → (X, ≤, ∗) ∈ SemiFrame. Then g◦ : St(X, ≤, ∗) → St(X′, ≤′, ∗′) is continuous:

(g◦)-1(O′) ∈Open(St(X, ≤, ∗))

for every O′ ∈ Open(St(X′, ≤′, ∗′)).

Proof

By Definition 8.4.3, O′ = Op(x′) for some x′ ∈ X′. By Lemma 10.3.5 (g◦)-1(Op(x′)) = Op(g(x′)). By Definition 8.4.3(2) Op(g(x′)) ∈ Open(St(X, ≤, ∗)).End of proof

Proposition 10.3.7 (Functoriality).

(1) Suppose f : (P, Open) → (P′, Open′) ∈ SemiTop (so f is a continuous map on underlying points). Then f -1 is an arrow Fr(P′, Open′) → Fr(P, Open) in SemiFrame.

(2) Suppose g : (X′, ≤′, ∗′) → (X, ≤, ∗) ∈ SemiFrame. Then g◦ from Definition 10.3.1 is an arrow St(X, ≤, ∗) → St(X′, ≤′, ∗′) in SemiTop.

(3) The assignments f ↦→ f -1 and g ↦→ g◦ are functorial — they map identity maps to identity maps, and commute with function composition.

Proof

We consider each part in turn:

(1) Following Definition 10.2.1, we must check that f -1 is a morphism of semiframes. We just unpack what this means and see that the required properties are just facts of taking inverse images:

– f -1 commutes with joins, i.e. with ⋃. This is a fact of inverse images.

– f -1 maps ⊤Fr(P′,Open′) = P′ to ⊤Fr(P,Open) = P. This is a fact of inverse images.

– f -1 is compatible, meaning that f -1(O′) ≬ f -1(O′′) implies O′ ≬ O′′. This is a fact of inverse images.

(2) We must check that g◦ is continuous. This is Lemma 10.3.6.

(3) Checking functoriality is routine, but we sketch the reasoning anyway:

– Consider the identity function id on some semitopology (P, Open). Then id-1 should be the identity function on (Open, ⊆, ≬). It is.

– Consider f : (P, Open) → (P′, Open′) and f′: (P′, Open′) → (P′′, Open′′). Then ( f′ ◦ f )-1 should be equal to f -1 ◦ ( f′)-1. It is.

– Consider the identity function id on (X, ≤, ∗). Then id◦ should be the identity function on Points(X, ≤, ∗). We look at Definition 10.3.1 and see that this amounts to checking that P = {x ∈ X | id(x) ∈ P}. It is.

– Consider g : (X, ≤, ∗) → (X′, ≤′, ∗′) and g′: (X′, ≤′, ∗′) → (X′′, ≤′′, ∗′′) and consider some P′′ ∈ Points(X′′, ≤′′, ∗′′). Then (g′ ◦ g)◦(P′′) should be equal to (g◦◦ (g′)◦)(P′′). We look at Definition 10.3.1 and see that this amounts to checking that {x ∈ X | g′(g(x)) ∈ P′′} = {x ∈ X | g(x) ∈ P′} where P′ = {x′ ∈ X′ | g′(x′) ∈ P′′}. Unpacking these definitions, we see that the equality does indeed hold.End of proof

10.4 Sober semitopologies are dual to spatial semiframes

Remark 10.4.1

A categorical duality between two categories C and D is a categorical equivalence between C and Dop. See [32, IV.4] or [43, Subsection 1.5 & Exercise 4.2.i].27 It suffices to provide an adjoint pair of functors whose unit and counit are natural isomorphisms.28

There are many duality results in the literature. The duality between topologies and frames is described (for example) in [33, page 479, Corollary 4]. A duality between distributive lattices and coherent spaces is in [24, page 66]. There is the classic duality by Stone between Boolean algebras and compact Hausdorff spaces with a basis of clopen sets [50, 24]. An encyclopedic treatment is in [9], with a rather good overview in Example 2.9 on page 17.

Theorem 10.4.2 states a duality result between Sober and Spatial, thus appending another item to this extensive canon.

It also constructively moves us forward in studying semitopologies, because it gives us an algebraic treatment of semitopologies, and a formal framework for studying morphisms between semitopologies. For instance: taking morphisms to be continuous functions is sensible not just because this is also how things work for topologies, but also because this is what is categorically dual to the ≤/∗-homomorphisms between semiframes (Definition 10.2.1). And of course, if we become interested in different notions of semitopology morphism (a flavour of these is in Remark 12.3.1) then the algebraic framework gives us a distinct mathematical light with which to inspect and evaluate them.

Theorem 10.4.2

The maps St (Definition 8.4.3) and Fr (Definition 7.3.4), with actions on arrows as described in Proposition 10.3.7, form a categorical duality between the categories

• Sober of sober semitopologies (Definition 9.3.1) and continuous compatible morphisms between them; and

• Spatial of spatial semiframes and morphisms between them (Definition 10.2.1(3)).

Proof

There are various things to check:

• Proposition 9.3.5 shows that St maps spatial semiframes to sober semitopologies.

• Proposition 9.2.5 shows that Fr maps sober semitopologies to spatial semiframes.

• By Proposition 10.3.7 the maps f ↦→ f -1 (inverse image) and g ↦→ g◦ (Definition 10.3.1) are functorial.

• The equivalence morphisms are given by the bijections Op and nbhd:

– Op is from Definition 8.3.1. By Lemma 10.2.2 Op is a morphism (X, ≤, ∗) → Fr St(X, ≤, ∗) in Spatial that is surjective on underlying sets. Injectivity is from Proposition 9.1.4(3).

– nbhd is from Definition 2.3.1. By Theorem 10.1.4 nbhd is a morphism (P, Open) → St Fr(P, Open) in Sober. It is a bijection on underlying sets by the sobriety condition in Definition 9.3.1.

Finally, we must check naturality of Op and nbhd, which means (as standard) checking commutativity of the following diagrams:

p59-commuting-squares(P, Open) St Fr(P, Open)(P′, Open′) St Fr(P′, Open′)nbhdf(f-1)◦nbhd(X, ≤, ∗) Fr St(X, ≤, ∗)(X′, ≤′, ∗′) Fr St(X′, ≤′, ∗′)Opg(g◦)-1Op

We proceed as follows:

• Suppose g : (X′, ≤′, ∗′) → (X, ≤, ∗) in Spatial, so that g◦ : St(X, ≤, ∗) → St(X′, ≤′, ∗′) in Sober and (g◦)-1 : Fr St(X′, ≤′, ∗′) → Fr St(X, ≤, ∗) in Spatial. To prove naturality we must check that

(g◦)-1(Op(x)) = Op(g(x))

for every x ∈ X. This is just Lemma 10.3.5.

• Suppose f : (P, Open) → (P′, Open′) in SemiTop, so that f -1 : Fr(P′, Open′) → Fr(P, Open) in Spatial and ( f -1)◦ : St Fr(P, Open) → St Fr(P′, Open′) in SemiTop. To prove naturality we must check that

(f-1)◦(nbhd(p)) = nbhd(f(p)).

We just chase definitions, for an open set O′ ∈ Open′:

O′ ∈(f-1)◦(nbhd(p)) ⟺⇒f-1(O′) ∈nbhd(p) Definition 10.3.1⟺⇒p ∈f-1(O′) Definition 2.3.1⟺⇒f(p) ∈O′Inverse image⟺⇒O′ ∈nbhd(f(p)) Definition 2.3.1.End of proof
Remark 10.4.3

We review the background to Theorem 10.4.2:

(1) A semitopology (P, Open) is a set of points P and a set of open sets Open ⊆ pow(P) that contains P and is closed under arbitrary (possibly empty) unions (Definition 1.2.2).

(2) A morphism between semitopologies is a continuous function, just as for topologies (Definition 10.1.1(1)).

(3) A semiframe (X, ≤, ∗) is a complete join-semilattice (X, ≤) with a properly reflexive distributive compatibility relation ∗ (Definition 7.3.1).

(4) A morphism between semiframes is a morphism of complete join-semilattices with ⊤ that is compatible with the compatibility relation (Definition 10.2.1(1)).

(5) An abstract point of a semitopology (P, Open) is a completely prime nonempty up-closed compatible subset P ⊆ Open (Definition 8.1.1(7)).

(6) A semitopology is sober when the neighbourhood semifilter map p ∈ P ↦→ nbhd(p) = {O ∈ Open | p ∈ O} is injective and surjective between the points of P and the abstract points of P (Definition 9.3.1).

(7) By Theorem 10.1.4, and as discussed in Remark 10.1.5, every (possibly non-sober) semitopology (P, Open) maps into its soberification St Fr(P, Open), which has an isomorphic semiframe of open sets. So even if our semitopology (P, Open) is not sober, there is a standard recipe to make it so.

(8) A semiframe is spatial when x ∈ X ↦→ Op(x) = {P ∈ Point | x ∈ P} respects ≤ and ∗ in senses make formal in Definition 9.1.2 and Proposition 9.1.4.

(9) Sober semitopologies and continuous functions between them, and spatial semiframes and semiframe morphisms between them, are categorically dual (Theorem 10.4.2).

Remark 10.4.4

Note what Theorem 10.4.2 does not do: it does not give a duality between all semitopologies and all semiframes; it gives a duality between sober semitopologies and spatial semiframes. This in itself is nothing new — the topological duality is just the same — but what is interesting is that our motivation for studying semitopologies comes from practical network systems. These tend to be (finite) non-sober semitopologies — non-sober, because a guarantee of sobriety cannot be enforced, and anyway it is precisely the point of the exercise to achieve coordination, without explicitly requiring every possible constellation of cooperating agents to be explicitly represented by a point.

It is true that by Theorem 10.1.4 every non-sober T0 semitopology can be embedded into a sober one without affecting the semiframe of open sets, but this makes the system to which it corresponds larger, by adding points. Thus the duality in Theorem 10.4.2 is a mathematical statement, but not necessarily a practical one — and this is as expected, because we knew that this is an abstract result. nbhd maps a point to a set of (open) sets; and Op maps an (open) set of points to a set of sets of (open) sets. Of course these might not be computationally optimal.

11. Well-behavedness conditions, dually

We now study how properties of semifilters and abstract points correspond to the well-behavedness properties which we found useful in studying semitopologies — for example topens, regularity, and being unconflicted (Definitions 3.2.2, 4.1.4 and 5.3.1).

11.1 (Maximal) semifilters and transitive elements

Remark 11.1.1 (Semifilters are not filters).

We know that semifilters do not necessarily behave like filters. For instance:

(1) It is possible for a finite semifilter to have more than one minimal element, because the closure under binary meets condition of filters is replaced by a weaker compatibility condition (see also Remarks 8.1.3 and 8.1.6).

(2) There are more semifilters than proper filters — even if the underlying space is a topology. For example, the discrete semitopology on {0, 1, 2} (whose open sets are all subsets of the space) is a topology. Every proper filter in this space is a semifilter, but it also has a semifilter { {0, 1}, {1, 2}, {2, 0}, {0, 1, 2}} (see the top-left diagram in Figure 6) and this is not a filter.

More on this in Subsection 8.2.2.

In summary: semifilters are different and we cannot necessarily take their behaviour for granted without checking it. We now examine them in more detail.

We start with some easy definitions and results:

Notation 11.1.2

Suppose (X, ≤, ∗) is a semiframe and X, Y ⊆ X and x ∈ X. Then we generalise x ∗ y to x ∗ Y, X ∗ y, and X ∗ Y as follows:

(1) Write x ∗ Y for ∀y∈Y.x ∗ y.

(2) Write X ∗ y for ∀x∈X.x ∗ y.

(3) Write X ∗ Y for ∀x∈X.∀y∈Y.x ∗ y.

We read x ∗ Y as ‘x is compatible with Y’, and similarly for X ∗ y and X ∗ Y.

Remark 11.1.3

We will see later on in Lemma 11.7.1 that X ∗ X′ generalises p ≬ p′, in the sense that if X = nbhd(p) and X′ = nbhd(p′), then p ≬ p′ if and only if nbhd(p) ∗ nbhd(p′).

Lemma 11.1.4 (Characterisation of maximal semifilters).

Suppose (X, ≤, ∗) is a semiframe and F ⊆ X is a semifilter. Then the following conditions are equivalent:

(1) F is maximal.

(2) For every x ∈ X, x ∗ F if and only if x ∈ F.

Proof

We prove two implications:

• Suppose F is a maximal semifilter. Suppose x ∈ F. Then x ∗ F is immediate from Notation 11.1.2(1) and semifilter compatibility (Definition 8.1.1(4)). Suppose x ∗ F; thus by Notation 11.1.2(1) x is compatible with (every element of) F. We note that the ≤-up-closure of {x} ∪ F is a semifilter (nonempty, up-closed, compatible). By maximality, x ∈ F.

• Suppose x ∗ F if and only if x ∈ F, for every x ∈ X. Suppose F′ is a semifilter and F ⊆ F′. Consider x′ ∈ F′. Then x ∗ F by compatibility of F′, and so x ∈ F. Thus, F′ ⊆ F.End of proof

Definition 11.1.5

Suppose (X, ≤, ∗) is a semiframe and x ∈ X. Call x transitive when:

(1) x ≠ ⊥X.

(2) x′ ∗ x ∗ x′′ implies x′ ∗ x′′, for every x′, x′′ ∈ X.

‘Being topen’ in semitopologies (Definition 3.2.2(2)) corresponds to ‘being transitive’ in semiframes (Definition 11.1.5):

Lemma 11.1.6 (Characterisation of topen sets).

Suppose (P, Open) is a semitopology and O ∈ Open. Then the following are equivalent:

(1) O is topen in (P, Open) in the sense of Definition 3.2.2(2).

(2) O is transitive in (Open, ⊆, ≬) in the sense of Definition 11.1.5.29

Proof

We unpack the definitions and note that the condition for being topen — being a nonempty open set that is transitive for ≬ — is identical to the condition for being transitive in (Open, ⊆, ≬) — being a non-⊥Open element that is transitive for ∗= ≬.End of proof

11.2 The compatibility system x∗

Definition 11.2.1

Suppose (X, ≤, ∗) is a semiframe and x ∈ X. Then define x∗ the compatibility system of x by

x∗= {x′ ∈X | x′ ∗x}.
Lemma 11.2.2

Suppose (X, ≤, ∗) is a semiframe and X ⊆ X. Then (⋁ X)∗= ⋃ x∈X x∗.

Proof

We just follow the definitions:

y ∈(⋁ X)∗⟺⇒y ∗⋁ X Definition 11.2.1⟺⇒∃x∈X.y ∗x Definition 7.2.1(3)⟺⇒∃x∈X.y ∈x∗Definition 11.2.1⟺⇒y ∈⋃ x∈X x∗Fact of setsEnd of proof
Lemma 11.2.3

Suppose (X, ≤, ∗) is a semiframe and x ∈ X is transitive. Then the following are equivalent for every y ∈ X:

y ∗x ⟺⇒ y ∈x∗⟺⇒ y ∗x∗.
Proof

We prove a cycle of implications:

• Suppose y ∗ x. Then y ∈ x∗ is direct from Definition 11.2.1.

• Suppose y ∈ x∗. Then y ∗ x∗ — meaning by Notation 11.1.2(1) that y ∗ x′ for every x′ ∈ x∗ — follows by transitivity of x.

• Suppose y ∗ x∗. By proper reflexivity of ∗ (Definition 7.2.1(2); since x ≠ ⊥X) x ∈ x∗, and y ∗ x follows.End of proof

Proposition 11.2.4

Suppose (X, ≤, ∗) is a semiframe and suppose ⊥X ≠ x ∈ X. Then the following are equivalent:

(1) x is transitive.

(2) x∗ is a completely prime semifilter (i.e. an abstract point).

(3) x∗ is a semifilter.

(4) x∗ is compatible.

(5) x∗ is a maximal semifilter.

Proof

We first prove a cycle of implications between parts 1, 2, 3, and 4:

(1) Suppose x is transitive. We need to check that x∗ is nonempty, up-closed, compatible, and completely prime. We consider each property in turn:

– x ∗ x by proper reflexivity of ∗ (Definition 7.2.1(2); since x ≠ ⊥X), so x ∈ x∗.

– It follows from monotonicity of ∗ (Lemma 7.2.3(1)) that if x′ ≤ x′′ and x ∗ x′ then x ∗ x′′.

– Suppose x′ ∗ x ∗ x′′. By transitivity of x (Definition 11.1.5), x′ ∗ x′′.

– Suppose x ∗⋁ X′; then by distributivity of ∗ (Definition 7.2.1(3)) x ∗ x′ for some x′ ∈ X′.

(2) If x∗ is a completely prime semifilter, then it is certainly a semifilter.

(3) If x∗ is a semifilter, then it is compatible (Definition 8.1.1(5)&4).

(4) Suppose x∗ is compatible (Definition 8.1.1(4)) and suppose x′ ∗ x ∗ x′′. By Lemma 11.2.3 x′, x′′ ∈ x∗, and by compatibility of x∗ we have x′ ∗ x′′. Thus, x is transitive.

To conclude, we prove two implications between parts 4 and 5:

• Suppose x∗ is a semifilter. By equivalence of parts 3 and 1 of this result, x is transitive, and so using Lemma 11.2.3 x′ ∗ x∗ if and only if x′ ∈ x∗. By Lemma 11.1.4, x∗ is maximal.

• Clearly, if x∗ is a maximal semifilter then it is a semifilter.End of proof

11.3 The compatibility system F∗

11.3.1 Basic definitions and results

Definition 11.3.1

Suppose (X, ≤, ∗) is a semiframe and suppose F ⊆ X (F may be a semifilter, but the definition does not depend on this). Define F∗ the compatibility system of F by

F∗= {x′ ∈X | x′ ∗F}

Unpacking Notation 11.1.2(1), and combining with Definition 11.2.1, we can write:

F∗= {x′ ∈X | x′ ∗F} = {x′ ∈X | ∀x∈F.x′ ∗x} =⋂ {x∗| x ∈F}.

Lemma 11.3.2 presents one easy and useful example of Definition 11.3.1:

Lemma 11.3.2

Suppose (P, Open) is a semitopology and suppose p ∈ P and O′ ∈ Open. Then:

O′ ∈nbhd(p)∗⟺⇒∀O∈Open.p ∈O =⟹O′ ≬O O′ /∈nbhd(p)∗⟺⇒∃O∈Open.p ∈O ∧O′ ≬̸O.
Proof

We just unpack Definitions 2.3.1 and 11.3.1.End of proof

Lemma 11.3.3

Suppose (X, ≤, ∗) is a semiframe and F ⊆ X. Then F∗ is up-closed.

Proof

This is just from Definition 11.3.1 and monotonicity of ∗ (Lemma 7.2.3(1)).End of proof

Lemma 11.3.4

Suppose (X, ≤, ∗) is a semiframe and F ⊆ X is a semifilter. Then:

(1) If x ∈ F then F ⊆ x∗.

(2) As a corollary, F ⊆ F∗.

Proof

Suppose x ∈ F. By compatibility of F (Definition 8.1.1(4)), x′ ∗ x for every x′ ∈ F. It follows from Definition 11.2.1 that F ⊆ x∗. The corollary is immediate from Definition 11.3.1.End of proof

We can use Lemma 11.3.4 and Definition 11.3.1 to give a more succinct rendering of Lemma 11.1.4:

Corollary 11.3.5

Suppose (X, ≤, ∗) is a semiframe and F ⊆ X is a semifilter. Then the following are equivalent:

(1) F is maximal.

(2) F∗= F.

(3) F∗⊆ F.

Proof

Equivalence of parts 1 and 2 just repeats Lemma 11.1.4 using Definition 11.3.1. To prove equivalence of parts 2 and 3 we use use Lemma 11.3.4(2).End of proof

11.3.2 Strong compatibility: when F∗ is a semifilter

Proposition 11.2.4 relates good properties of x (transitivity) to good properties of its compatibility system x∗ (e.g. being compatible). It will be helpful to ask similar questions of F∗. What good properties are of interest for F∗, and what conditions can we impose on F to guarantee them?

Definition 11.3.6

Suppose (X, ≤, ∗) is a semiframe. Then:

(1) Call F ⊆ X strongly compatible when F∗ is nonempty and compatible.

(2) Call (X, ≤, ∗) strongly compatible when every abstract point (completely prime semifilter) P ⊆ X is strongly compatible.

Remark 11.3.7

For the reader’s convenience we unpack Definition 11.3.6.

(1) By Definition 8.1.1(4), F∗ is compatible when x ∗ x′ for every x, x′ ∈ F∗. Combining this with Definition 11.3.1 and Notation 11.1.2, F∗ is compatible when x ∗ F ∗ x′ implies x ∗ x′, for every x, x′ ∈ X. Thus, F is strongly compatible when

∀x, x′∈X. x ∗F ∗x′ =⟹x ∗x′.

(2) (X, ≤, ∗) is strongly compatible when every abstract point P ∈ Point(X, ≤, ∗) is strongly compatible in the sense just given above.

Lemma 11.3.8

Suppose (P, Open) is a semitopology and p ∈ P. Recall from Definition 7.3.4(3) and Lemma 7.3.5 that (Open, ⊆, ≬) is a semiframe. Then the following are equivalent:

(1) The point p ∈ P is hypertransitive in the sense of Definition 6.2.3.

(2) The semifilter nbhd(p) ⊆ Open is strongly compatible in the sense of Definition 11.3.6.

Proof

Remark 11.3.7 notes that the condition in Definition 6.2.3 is precisely the condition for nbhd(p) to be strongly compatible.End of proof

Remark 11.3.9

Given Lemma 11.3.8, the reader might ask why we do not just call a strongly compatible semifilter ‘hypertransitive’.

There is a case for doing so, but caution is required: strong compatibility of semiframes is not quite the same thing as hypertransitivity of points. Every point p generates a semifilter nbhd(p), but there may be more semifilters than there are points, and this makes the strong compatibility condition subtly different from the hypertransitivity condition. We shall see the effects of this in Lemma 11.5.3(2), and in Theorem 11.5.4 (see Remark 11.5.5 for a brief discussion), and then again in Definition 11.8.8 where we define a notion of strongly compatible semitopology (essentially: all of its semifilters are strongly compatible), which is not the same thing as the space being hypertransitive (essentially: all of its points are hypertransitive).

Therefore, we maintain a terminological distinction: points are hypertransitive, semiframes are strongly compatible. The notions are related, but not quite the same thing.

Lemma 11.3.10

Suppose (X, ≤, ∗) is a semiframe and suppose F ⊆ X is nonempty. Then the following are equivalent:

(1) F∗ is a semifilter.

(2) F∗ is compatible.

(3) F is strongly compatible.

-1 1-2 0 2A B
Figure 8. Strongly compatible filter that contains no transitive element
Proof

Equivalence of parts 2 and 3 is just Definition 11.3.6. For equivalence of parts 1 and 2 we prove two implications:

• Suppose F∗ is a semifilter. Then F∗ is compatible by assumption in Definition 8.1.1(5).

• Suppose F∗ is compatible. Then F∗ is up-closed by Lemma 11.3.3, and nonempty by Lemma 11.3.4(2) (since F is nonempty). Thus, by Definition 8.1.1(5) F∗ is a semifilter.End of proof

Lemma 11.3.11

Suppose (X, ≤, ∗) is a semiframe and suppose F ⊆ X. Then it is not necessarily the case that F∗ is a semifilter.

This non-implication holds even in strong well-behavedness conditions: that (X, ≤, ∗) is spatial and F is an abstract point (a completely prime semifilter).

Proof

It suffices to provide a counterexample. Let (P, Open) = ({0, 1, 2}, {∅, {0}, {2}, P}), as illustrated in the top-left semitopology in Figure 2. Take (X, ≤, ∗) = (Open, ⊆, ≬) (which is spatial by Proposition 9.2.5) and set F = nbhd(1) = {0, 1, 2}. Then nbhd(1)∗= {{0}, {2}, {0, 1, 2}}, and this is not compatible because {0}≬̸{2}.30End of proof

Remark 11.3.12

Lemma 11.3.11 gives an example of a semifilter F that is not strongly compatible (i.e. such that F∗ is not a semifilter). Note that in this example both the space and F are well-behaved. This raises the question of finding sufficient (though perhaps not necessary) criteria for strong compatibility. We conclude with Proposition 11.3.13 which provides one such criterion; it will be useful later in Lemma 11.5.3 and Theorem 11.8.10.

Proposition 11.3.13 bears a family resemblance to Theorem 4.2.5 (if a point has a topen neighbourhood then it is regular):

Proposition 11.3.13

Suppose (X, ≤, ∗) is a semiframe and F ⊆ X is a semifilter. Then:

(1) If F contains a transitive element then F is strongly compatible.

(2) The converse implication need not hold: it may be that F is strongly compatible yet F contains no transitive element.

Proof

We consider each part in turn:

(1) Suppose x ∈ F is transitive. By Lemma 11.3.10 it would suffice to show that F∗ is compatible (Definition 8.1.1(4)). So consider y ∗ F ∗ y′. Then y ∗ x ∗ y′ and by transitivity y ∗ y′. Thus F∗ is compatible.

(2) It suffices to provide a counterexample. We take, as illustrated in Figure 8,

– P = {-2, -1, 0, 1, 2} and

– we let Open be generated by {i, i+1} for -2 ≤ i ≤ 1 (unordered pairs of adjacent numbers).

Write A = {-1, 0} and B = {0, 1} and let F be the up-closure of {A, B}. Note that A and B are not transitive (i.e. not topen). The reader can check that F∗= F (e.g. {1, 2} /∈ F∗ because {1, 2}≬̸{-1, 0} ∈ F), but F contains no transitive element.End of proof

11.4 Semiframe characterisation of community

Remark 11.4.1

We saw the notion of K(p) the community of a point in Definition 4.1.4(1). In this Subsection we construct an analogue to it in semiframes. We will give two characterisations: one in Definition 11.4.5, and another in Proposition 11.4.7.

We will mostly be interested in Definition 11.4.2 when F is a semifilter, but the definition does not require this:

Definition 11.4.2

Suppose (X, ≤, ∗) is a semiframe and F ⊆ X and x ∈ X. Then define Fc ∈ X, F∗c ∈ X, and x∗c ∈ X by

Fc =⋁ {y ∈X | y /∈F}, F∗c = (F∗)c, and x∗c = (x∗)c.
Remark 11.4.3

We unpack the definitions of F∗c and x∗c:

F∗c = (F∗)cDefinition 11.4.2= ⋁{y ∈X | y /∈F∗} Definition 11.4.2= ⋁{y ∈X | ¬(y ∗F)} Definition 11.3.1
x∗c = (x∗)cDefinition 11.4.2= ⋁{y ∈X | y /∈x∗} Definition 11.4.2= ⋁{y ∈X | ¬(y ∗x)}. Definition 11.2.1

Lemma 11.4.4 will be useful, and gives some intuition for (-)c and (-)∗c by unpacking their concrete meaning in the special case of a semiframe of open sets of a semitopology:

Lemma 11.4.4

Suppose (P, Open) is a semitopology and p ∈ P and O ∈ Open. Then:

(1) nbhd(p)c = P\|p|.

(2) nbhd(p)∗c = P\ p≬.

(3) O∗c = P\|O| = interior(P\O).

Proof

We consider each part in turn:

(1) It is a fact of Definition 5.1.1 that P\|p| = ⋃{O′ ∈ Open | p /∈ O′}. By Proposition 9.2.2(2) p /∈ O′ if and only if O′ /∈ nbhd(p).

(2) It is a fact of Definition 3.5.1, which is spelled out in Lemma 5.2.4(2), that P\ p≬= ⋃{O′ ∈ Open | ∃O∈Open.p ∈ O ∧ O′ ≬̸ O}. By Lemma 11.3.2 ∃O∈Open.p ∈ O ∧ O′ ≬̸ O precisely when O′ /∈ nbhd(p)∗.

(3) By Definitions 11.4.2 and 11.3.1 we have

Oc = (O∗)∗c =⋃ {O′∈Open | O′ /∈O∗} =⋃ {O′∈Open | O′ ≬̸O}.

The result then follows by routine reasoning on closures (Definition 5.1.1).End of proof

Definition 11.4.5

Suppose (X, ≤, ∗) is a semiframe and F ⊆ X. Then define k(F) ∈ X the abstract community of F by

k(F) = (F∗c)∗c ∈X.

(For a more direct characterisation, see Proposition 11.4.7.)

Proposition 11.4.6

Suppose (P, Open) is a semitopology and p ∈ P. Then

k(nbhd(p)) = K(p).

In words: the abstract community of the abstract point nbhd(p) in (Open, ⊆, ≬), is identical to the community of p.

Proof

We reason as follows:

k(nbhd(p)) = (nbhd(p)∗c)∗cDefinition 11.4.5= (P\ p≬)∗cLemma 11.4.4(2)= interior(P\(P\ p≬)) Lemma 11.4.4(3)= interior(p≬) Fact of sets

= K(p) Definition 4.1.4(1) We can also give a more direct characterisation of the abstract community from Definition 11.4.5:End of proof

Proposition 11.4.7

Suppose (X, ≤, ∗) is a semiframe and F ⊆ X. Then

k(F) =⋁ {x ∈X | x∗⊆F∗},

and k(F) is the greatest element in X such that k(F)∗⊆ F∗.

Proof

We follow the definitions:

(F∗c)∗c = ⋁{x ∈X | ¬(x ∗F∗c)} Remark 11.4.3= ⋁{x ∈X | ¬(x ∗⋁{y | ¬(y ∗F)})} Remark 11.4.3= ⋁{x ∈X | ¬∃y∈X.(x ∗y ∧¬(y ∗F))} Definition 7.2.1(3)= ⋁{x ∈X | ∀y∈X.y ∗x =⟹y ∗F} Fact of logic= ⋁{x ∈X | x∗⊆F∗} Definitions 11.2.1 & 11.3.1

To see that k(F) is the greatest element such that k(F)∗⊆ F∗, we note from Lemma 11.2.2 that

k(F)∗=⋃ {x∗| x∈X, x∗⊆F∗}.End of proof

11.5 Semiframe characterisation of regularity

We now have enough to generalise the notions of quasiregularity, weak regularity, and regularity from semitopologies (Definition 4.1.4 parts 5, 4, and 3) to semiframes:

Definition 11.5.1

Suppose (X, ≤, ∗) is a semiframe and F ⊆ X is a semifilter.

(1) Call F quasiregular when k(F) ≠ ⊥X. Thus, there exists some x ∈ X such that x∗⊆ F∗.

(2) Call F weakly regular when k(F) ∈ F.

(3) Call F regular when k(F) ∈ F and k(F) is transitive.

Lemma 11.5.2 does for semiframes what Lemma 4.1.6 does for semitopologies:

Lemma 11.5.2

Suppose (X, ≤, ∗) is a semiframe and F ⊆ X is a semifilter. Then:

(1) If F is regular then it is weakly regular.

(2) If F is weakly regular then it is quasiregular.

(The converse implications need not hold, and it is possible for F to not be quasiregular: it is convenient to defer the proofs to Corollary 11.6.3.)

Proof

The proofs are easy: If k(F) ∈ F and k(F) is transitive, then certainly k(F) ∈ F. If k(F) ∈ F then by Lemma 8.2.1(2) k(F) ≠ ⊥X.End of proof

Lemma 11.5.3

Suppose (X, ≤, ∗) is a semiframe and F ⊆ X is a semifilter. Then:

(1) If F is quasiregular and strongly compatible then k(F) is transitive.

(2) The converse implication need not hold: it is possible for F to be quasiregular and k(F) to be transitive, yet F is not strongly compatible.

(3) If F is weakly regular and k(F) is transitive then F is strongly compatible.

(4) If F is weakly regular, then k(F) is transitive if and only if F is strongly compatible.

Proof

We consider each part in turn:

(1) Suppose F is quasiregular and strongly compatible. By quasiregularity ⊥X ≠ k(F). By Proposition 11.4.7 k(F)∗⊆ F∗. By strong compatibility F∗ is a semifilter and so in particular F∗ is compatible. It follows from Proposition 11.2.4(1&4) that k(F) is transitive, as required.

(2) It suffices to provide a counterexample. Let (R, Open) be the real numbers with their usual topology, and let (R, Open′) be the topology generated by Open ∪{{0}} — in words: we add {0} as an open set.
Let F be the semifilter of all Open-open neighbourhoods of 0. F∗ is the set of Open′-open sets that intersect every Open-open neighbourhood of 0. This is not compatible, because it contains (0,) (the set of numbers strictly less than 0) and (, 0) (the set of numbers strictly greater than 0), and these do not intersect. Using Proposition 11.4.7, we calculate that k(F) = {0}; this is transitive because it is a singleton set. So F is quasiregular, k(F) is transitive, yet F is not strongly compatible.

(3) Suppose k(F) is transitive and suppose F is weakly regular, so k(F) ∈ F. By Proposition 11.3.13 F is strongly compatible.

(4) From parts 1 and 3 of this result, noting from Lemma 11.5.2 that if F is weakly regular then it is quasiregular.End of proof

Theorem 11.5.4

Suppose (X, ≤, ∗) is a semiframe and F ⊆ X is a semifilter. Then F is regular if and only if F is weakly regular and strongly compatible. We can write this succinctly as follows:

Regular = weakly regular + strongly compatible.

(Compare this slogan with the version for semitopologies in Theorem 5.3.4.)

Proof

Suppose F is weakly regular and strongly compatible. By Lemma 11.5.3(4) k(F) is transitive, and by Definition 11.5.1(3) F is regular.

For the converse implication we just reverse the reasoning above.End of proof

Remark 11.5.5

In Theorem 6.3.3 we characterised regularity of points in terms of quasiregularity and being hypertransitive. In view of Lemma 11.3.8 we might expect Theorem 11.5.4 to read ‘regular = quasiregular + strongly compatible’. But this is false, as per the discussion in Remark 11.3.9 and the counterexample in Lemma 11.5.3(2). Thus, the semiframes results are subtly different from those governing point-set semitopologies.

11.6 Semiframe characterisation of (quasi/weak)regularity

The direct translation in Definition 11.5.1 of parts 5, 4, and 3 of Definition 4.1.4, along with the machinery we have now built, makes Lemma 11.6.1 easy to prove:

Lemma 11.6.1

Suppose (P, Open) is a semitopology and p ∈ P. Recall from Definition 2.3.1 and Proposition 9.2.2(1) that nbhd(p) = {O ∈ Open | p ∈ O} is a (completely prime) semifilter. Then:

(1) p is quasiregular in the sense of Definition 4.1.4(5) if and only if nbhd(p) is quasiregular in the sense of Definition 11.5.1(1).

(2) p is weakly regular in the sense of Definition 4.1.4(4) if and only if nbhd(p) is weakly regular in the sense of Definition 11.5.1(2).

(3) p is regular in the sense of Definition 4.1.4(3) if and only if nbhd(p) is regular in the sense of Definition 11.5.1(3).

Proof

We consider each part in turn:

(1) Suppose p is quasiregular. By Definition 4.1.4(5) K(p) ≠ ∅. By Proposition 11.4.6 k(nbhd(p)) ≠ ∅= ⊥Open. By Definition 11.5.1(1) nbhd(p) is quasiregular. The reverse implication follows just reversing the reasoning above.

(2) Suppose p is weakly regular. By Definition 4.1.4(4) p ∈ K(p). By Definition 2.3.1 K(p) ∈ nbhd(p). By Proposition 11.4.6 k(nbhd(p)) ∈ nbhd(p) as required. The reverse implication follows just reversing the reasoning above.

(3) Suppose p is regular. By Definition 4.1.4(3) p ∈ K(p) ∈ Topen. By Definition 2.3.1 and Proposition 11.4.6 k(nbhd(p)) ∈ nbhd(p). By Proposition 11.4.6 and Lemma 11.1.6 k(nbhd(p)) is transitive. The reverse implication follows just reversing the reasoning above.End of proof

Proposition 11.6.2

Suppose (P, Open) is a semitopology and p ∈ P. Then

• p is quasiregular / weakly regular / regular in (P, Open) in the sense of Definition 4.1.4 if and only if

• nbhd(p) is quasiregular / weakly regular / regular in Soberify(P, Open) in the sense of Definition 11.5.1.

Proof

We consider just the case of regularity; quasiregularity and weak regularity are no different.

Suppose p is regular. By Definition 4.1.4(3) p ∈ K(p) ∈ Topen. It follows from Lemma 11.1.6 that K(p) is transitive in (Open, ⊆, ≬), and from Proposition 9.2.2(2) that K(p) ∈ nbhd(p). It follows from Proposition 11.4.6 that nbhd(p) is regular in the sense of Definition 11.5.1(3).End of proof

Corollary 11.6.3

Suppose (X, ≤, ∗) is a semiframe and F ⊆ X is a semifilter. Then the converse implications in Lemma 11.5.2 need not hold: F may be quasiregular but not regular, and it may be weakly regular but not regular, and it may not even be quasiregular.

Proof

It suffices to provide counterexamples. We easily obtain these by using Proposition 11.6.2 to consider nbhd(p) for p ∈ P as used in Lemma 4.1.6.End of proof

11.7 Characterisation of being intertwined

This Subsection continues Remark 11.1.3.

The notion of points being intertwined from Definition 3.5.1(1) generalises in semiframes to the notion of semifilters being compatible:

Lemma 11.7.1

Suppose (P, Open) is a semitopology and p, p′ ∈ P. Then

p ≬p′⟺⇒ nbhd(p) ∗nbhd(p′) ⟺⇒ nbhd(p) ≬nbhd(p′).

For clarity and precision we unpack this. The following are equivalent:

(1) p ≬ p′ in the semitopology (P, Open) (Definition 3.5.1(1)). In words: the point p is intertwined with the point p′.

(2) nbhd(p) ∗ nbhd(p′) in the semiframe (Open, ⊆, ≬) (Notation 11.1.2(3)). In words: the abstract point nbhd(p) is compatible with the abstract point nbhd(p′).

(3) nbhd(p) ≬ nbhd(p′) in the semitopology St(Open, ⊆, ≬) (Definition 3.5.1(1)). In words: the point nbhd(p) is intertwined with the point nbhd(p′).

Proof

We unpack definitions:

• By Definition 3.5.1(1) p ≬ p′ when for every pair of open neighbourhoods p ∈ O and p′ ∈ O′ we have O ≬ O′.

• By Notation 11.1.2(3) nbhd(p) ∗ nbhd(p′) when for every O ∈ nbhd(p) and O′ ∈ nbhd(p′) we have O ∗ O′. By Proposition 9.2.2(2) we can simplify this to: p ∈ O and p′ ∈ O′ implies O ∗ O′.

• By Definition 3.5.1(1) and Theorem 10.1.4, nbhd(p) ≬ nbhd(p′) when: for every pair of open neighbourhoods nbhd(p) ∈ Op(O) and nbhd(p′) ∈ Op(O′) we have Op(O) ≬ Op(O′). By Proposition 9.2.2(2) we can simplify this to: p ∈ O and p′ ∈ O′ implies Op(O) ≬ Op(O′). By Proposition 8.3.3(2) we can simplify this further to: p ∈ O and p′ ∈ O′ implies O ∗ O′.

But by definition, the compatibility relation ∗ of (Open, ⊆, ≬) is ≬, so O ∗ O′ and O ≬ O′ are the same assertion. The equivalences follow.End of proof

The property of being intertwined is preserved and reflected when we use nbhd to map to the soberified space:

Corollary 11.7.2

Suppose (P, Open) is a semitopology and p, p′ ∈ P. Then p ≬ p′ in (P, Open) if and only if nbhd(p) ≬ nbhd(p′) in Soberify(P, Open).

Proof

This just reiterates the equivalence of parts 1 and 3 in Lemma 11.7.1.End of proof

Proposition 11.7.3

Suppose (P, Open) is a semitopology. Then:

(1) It may be that (P, Open) is unconflicted (meaning that it contains no conflicted points), but the semitopology Soberify(P, Open) contains a conflicted point.

(2) It may further be that (P, Open) is unconflicted and p ∈ P is such that nbhd(p) is conflicted in the semitopology Soberify(P, Open).

We can summarise the two assertions above as follows:

(1) Soberifying a space might introduce a conflicted point, even if none was originally present.

(2) Soberifying a space can make a point that was unconflicted, into a point that is conflicted.31

Proof

It suffices to provide counterexamples.

(1) Consider the right-hand semitopology in Figure 6; this is unconflicted because every point is intertwined only with itself. The soberification of this space is illustrated in the right-hand semitopology in Figure 7. Each of the extra points is intertwined with the two numbered points next to it; e.g. the extra point in the open set A — write it •A (in-between 3 and 0) — is intertwined with 0 and 3; so 3 ≬•A ≬ 0. However, the reader can check that 3 ≬̸ 0. Thus, •A is conflicted.

(2) We define (P, Open) by:

– P = (-1, 1) (real numbers between -1 and 1 exclusive).

– Open is generated by:

– All open intervals that do not contain 0; so this is open intervals (r1, r2) where -1 ≤ r1 < r2 ≤ 0 or 0 ≤ r1 < r2 ≤ 1.

– All of the open intervals (-1/n, 1/n), for n ≥ 2.

The reader can check that:

– Points in this semitopology are intertwined only with themselves.

– The soberification includes four additional points, corresponding to completely prime semifilters -1/0 generated by {(-1/n, 0) | n ≥ 2} and +1/0 generated by {(0, 1/n) | n ≥ 2}, and to the endpoints -1 and i+1.

– -1/0 and +1/0 are intertwined with 0, but are not intertwined with one another.

Thus, 0 is conflicted in Soberify(P, Open) but not in (P, Open).End of proof

Remark 11.7.4

Proposition 11.7.3 may seem surprising in view of Corollary 11.7.2, but the key observation is that the soberified space may add points to the original space. These points can add conflicting behaviour that is ‘hidden’ in the completely prime semifilters of the original space.

Thus, Proposition 11.7.3 shows that the property of ‘being unconflicted’ cannot be characterised purely in terms of the semiframe of open sets — if it could be, then soberification would make no difference, by Theorem 10.1.4(3).

There is nothing wrong with that, except that we are interested in well-behavedness conditions on semiframes. We can now look for some other condition — but one having to do purely with open sets — that might play a similar role in the theory of (weak/quasi)regularity of semiframes, as being unconflicted does in theory of (weak/quasi)regularity of semitopologies.

We already saw a candidate for this in Theorem 11.5.4: strong compatibility. We examine this next.

11.8 Strong compatibility in semitopologies

Remark 11.8.1

Note that:

(1) Theorem 11.5.4 characterises ‘regular’ for semiframes as ‘weakly regular + strongly compatible’.

(2) Theorem 5.3.4 characterises ‘regular’ for semitopologies as ‘weakly regular + unconflicted’.

We know from results like Lemma 11.6.1 and Corollary 11.7.2 that there are accurate correspondences between notions of regularity in semiframes and semitopologies. This is by design, e.g. in Definition 11.5.1; we designed the semiframe definitions so that semiframe regularity and semitopological regularity would match up closely.

Yet there are differences too, since Theorem 11.5.4 uses strong compatibility, and Theorem 5.3.4 uses being unconflicted. What is the difference here, and why does it arise?

One answer is given by Proposition 11.7.3, which illustrates that the condition of ‘unconflicted’ (which comes from semitopologies) does not sit comfortably with the ‘pointless’ semiframe definitions. This raises the question of how strong compatibility (which comes from semiframes) translates into the context of semitopologies; and how this relates to being (un)conflicted?

We look into this now; see Remark 11.8.11 for a summary.

We can translate the notion of strongly compatible filter (Definition 11.3.6(1)) to semitopologies in the natural way, just applying it to the neighbourhood semifilter nbhd(p) of a point (Definition 2.3.1):

Definition 11.8.2

Suppose (P, Open) is a semitopology. Then call p ∈ P strongly compatible when the (by Example 8.1.4(1)) abstract point nbhd(p) is strongly compatible (Definition 11.3.6) as a semifilter in (Open, ⊆, ≬).

We unpack what Definition 11.8.2 means concretely:

Lemma 11.8.3

Suppose (P, Open) is a semitopology and p ∈ P. Then the following are equivalent:

(1) p is hypertransitive (Definition 6.2.3).

(2) nbhd(p) is strongly compatible.

(3) nbhd(p)∗ is compatible.

(4) For every O′, O′′ ∈ Open, if O′ ∗ nbhd(p) ∗ O′′ then O′ ≬ O′′.

(Above, O′ ∗ nbhd(p) follows Notation 11.1.2(1) and means that O′ ≬ O for every p ∈ O ∈ Open, and similarly for nbhd(p) ∗ O′′.)

Proof

Equivalence of parts 1 and 2 is just Lemma 11.3.8. Equivalence of parts 2 and 3 is Definition 11.3.6(1). For the equivalence of parts 3 and 4, we just unpack what it means for nbhd(p)∗ to be compatible (see Remark 11.3.7).End of proof

‘p ∈ P is strongly compatible’ is a strictly stronger condition than ‘p ∈ P is unconflicted’:

Lemma 11.8.4

Suppose (P, Open) is a semitopology and p ∈ P. Then:

(1) If p is strongly compatible then it is unconflicted.

(2) If p is conflicted then: p is not strongly compatible, nbhd(p) is not strongly compatible, and nbhd(p)∗ is not compatible.

(3) The reverse implication need not hold, even if (P, Open) is sober:32 it is possible for p to be unconflicted but not strongly compatible.

Proof

We consider each part in turn:

(1) Suppose p is strongly compatible and suppose p′ ≬ p ≬ p′′; we must show that p′ ≬ p′′. Consider open neighbourhoods p′ ∈ O′ and p′′ ∈ O′′. By assumption p′ ≬ p and so by Lemma 11.7.1(1&2) nbhd(p′) ∗ nbhd(p). Since O′ ∈ nbhd(p′), it follows that O′ ∗ nbhd(p), and similarly it follows that nbhd(p) ∗ O′′. Then by strong compatibility, O′ ≬ O′′ as required.

(2) We take the contrapositive of part 1 of this result, and use Lemma 11.8.3.

(3) It suffices to provide a counterexample. Consider the bottom right semitopology in Figure 2, and take p = ∗ and O′ = {1} and O′′ = {0, 2}. Note that:

– ∗ is unconflicted, since it is intertwined only with itself and 1.

– O′ and O′ intersect every open neighbourhood of ∗, but O′ ≬̸ O′′, so ∗ is not strongly compatible.

This space is sober: the only completely prime filters are the neighbourhood semifilters of ∗, 0, 1, and 2.End of proof

Example 11.8.5

Continuing Lemma 11.8.4(3), it is possible for a point to be strongly compatible (Definition 11.8.2) but not regular, or even quasiregular (Definition 4.1.4(3, 5)). Consider the right-hand semitopology illustrated in Figure 6 and take p = 0. The reader can check that p is strongly compatible, but it is not quasiregular (i.e. K(p) = ∅) and thus also not regular.

Lemma 11.8.6 shows that the situation outlined in Proposition 11.7.3(2) cannot arise if we work with a strongly compatible point instead of an unconflicted one ...

Lemma 11.8.6

Suppose (P, Open) is a semitopology and p, p′ ∈ P. Then the following are equivalent:

(1) p is hypertransitive in (P, Open).

(2) nbhd(p) is hypertransitive in Soberify(P, Open) (Notation 10.1.3).

Proof

Note that from Lemma 11.8.3, p is hypertransitive in (P, Open) when

(∀O∈Open.p ∈O =⟹O′ ≬O ≬O′′) implies O′ ≬O′′

for every O′, O′′ ∈ Open. Also, from Definition 8.4.3(2) and Lemma 11.8.3, nbhd(p) is hypertransitive in Soberify(P, Open) when

(∀O∈Open.nbhd(p) ∈ Op(O) =⟹ Op(O′) ≬ Op(O) ≬ Op(O′′))

implies Op(O′) ≬ Op(O′′)

for every Op(O′), Op(O′′) ∈ Opens(Soberify(P, Open)).

Now by Proposition 9.2.2(2), nbhd(p) ∈ Op(O) if and only if p ∈ O, and by Corollary 9.2.3 Op(O′) ≬ Op(O) if and only if O′ ≬ O, and Op(O) ≬ Op(O′′) if and only if O ≬ O′′. The result follows.End of proof

...but, the situation outlined in Proposition 11.7.3(1) can arise, indeed we use the same counterexample:

Lemma 11.8.7

It may be that every point in (P, Open) is hypertransitive, yet Soberify(P, Open) contains a point that is not hypertransitive.

Proof

The same counterexample as used in Proposition 11.7.3(1) illustrates a space (P, Open) such that every point in (P, Open) is hypertransitive, but Soberify(P, Open) contains a point that is not hypertransitive. We note that •A (the extra point in-between 3 and 0) is not hypertransitive, because both B and D intersect with every open neighbourhood of •A, but B does not intersect with D.End of proof

The development above suggests that we define:

Definition 11.8.8

Call a semitopology (P, Open) strongly compatible when (Open, ⊆, ≬) is strongly compatible in the sense of Definition 11.3.6(2).

The proof of Proposition 11.8.9 is then very easy:

Proposition 11.8.9

Suppose (P, Open) is a semitopology. Then the following are equivalent:

(1) (P, Open) is strongly compatible in the sense of Definition 11.8.8.

(2) Soberify(P, Open) is strongly compatible in the sense of Definition 11.8.8.

(3) Soberify(P, Open) is strongly compatible in the sense of Definition 11.3.6(2).

(4) Soberify(P, Open) is hypertransitive in the sense of Definition 6.2.3.

Proof

We unpack Definition 11.8.8 and note that strong compatibility of (P, Open) is expressed purely as a property of its semiframe of open sets (Open, ⊆, ≬). By Theorem 10.1.4(3), the semiframe of open sets of Soberify(P, Open) is isomorphic to (Open, ⊆, ≬), via nbhd-1. Equivalence of parts 1 and 2 follows.

By Notation 10.1.3 and Remark 10.1.2(3), the points of Soberify(P, Open) are just abstract points of (Open, ⊆, ≬). Equivalence of parts 2 and 3 follows.

Equivalence of part 4 with the other parts follows using Lemmas 11.8.3 and 11.8.6.End of proof

Recall from Definition 4.1.4(7) that (P, Open) being (weakly) regular means that every point in (P, Open) is (weakly) regular. Recall from Definition 11.8.8 that (P, Open) being strongly compatible means that (Open, ⊆, ≬) = Fr(P, Open) is strongly compatible in the sense of Definition 11.3.6(2). We can now prove an analogue of Theorems 5.3.4 and 11.5.4:

Theorem 11.8.10

Suppose (P, Open) is a semitopology and p ∈ P. Then the following are equivalent:

(1) (P, Open) is regular.

(2) (P, Open) is weakly regular and strongly compatible.

Proof

Suppose (P, Open) is regular, meaning that every p ∈ P is regular.

By Theorems 5.3.4 and 6.3.3 every p ∈ P is weakly regular and hypertransitive. (So by Lemma 11.8.3 every nbhd(p) is strongly compatible, and by Lemma 11.8.6 also hypertransitive.) The definition of weak regularity for a space in Definition 4.1.4(7) is pointwise, so it follows immediately that (P, Open) is weakly regular.

But, the definition of strong compatibility for a space in Definition 11.8.8 is on its semiframe of open sets, which may include abstract points not only of the form nbhd(p). It therefore does not follow immediately that (P, Open) is strongly compatible; Lemma 11.8.7 contains a counterexample.

We can still prove that (P, Open) is strongly compatible — but we need to do a bit more work. Unpacking Definition 11.8.8, we must show that (Open, ⊆, ≬) is strongly compatible. Unpacking Definition 11.3.6(2), we must show that every abstract point in (Open, ⊆, ≬) is strongly compatible.

So consider an abstract point P ⊆ Open. By Corollary 4.3.3 P has a topen partition T , which means that: every T ∈ T is topen; the elements of T are disjoint; and ⋃ T = P.

Now ⋃ T = P ∈ T by Definition 8.1.1(7) and Lemma 8.2.1(1), so by Definition 8.1.1(2) there exists at least one (and in fact precisely one) T ∈ T such that T ∈ P. Now T is a transitive element in Open, so by Proposition 11.3.13 P ⊆ Open is strongly compatible as required.End of proof

Remark 11.8.11

We summarise what we have seen:

(1) The notions of (quasi/weak)regularity match up nicely between a semitopology, and its semiframe soberification (Proposition 11.6.2).

(2) We saw in Proposition 11.7.3 that the notions of (un)conflicted point and unconflicted space from Definition 5.3.1(2) are not robust under forming soberification (Notation 10.1.3). From the point of view of a pointless methodology in semitopologies — in which we seek to understand a semitopology (P, Open) starting from its semiframe structure (Open, ⊆, ≬) — this is a defect.

(3) A pointwise notion of strong compatibility exists; by Lemma 11.8.3 it is actually hypertransitivity from Definition 6.2.3. This is preserved pointwise by soberification (Lemma 11.8.6), but soberification can still introduce extra points, and it turns out that the property of a space being pointwise hypertransitive is still not robust under soberification because the extra points need not necessarily be hypertransitive; see Lemma 11.8.7.

(4) This motivates the notion of a strongly compatible semitopology from Definition 11.8.8; and then Proposition 11.8.9 becomes easy.

Our larger point (no pun intended) is that the Definition and its corresponding Proposition are natural, and also that the other design decisions are less natural, as noted above. Perhaps somewhat unexpectedly, ‘regular = weakly regular + strongly compatible’ then works pointwise and for the entire space; see Theorem 11.8.10. Thus Definition 11.8.8 has good properties and is natural from a pointless/semiframe/open sets perspective.

12. Conclusions and related and future work

12.1 Topology vs. semitopology

We briefly compare and contrast topology/frames and semitopology/semiframes. This list is not exhaustive but we hope it will give a feel for how the two differ:

(1) Topology: We are typically interested in spaces with separation axioms.33 Semitopology: We are interested in guaranteeing agreement between participants of a distributed system, and this is all about anti-separation properties of their actionable coalitions. Semifilters have a compatibility condition (Definition 8.1.1(4)); and regularity, being intertwined, and being unconflicted or strongly compatible are anti-separation properties (see Definitions 3.5.1, 4.1.4, 5.3.1, and 11.3.6, and Remark 3.5.7).34

(2) Topology: If a minimal open neighbourhood of a point exists then it is least, because we can intersect two minimal neighbourhoods to get a smaller one which by minimality is equal to both. A finite filter has a least element. Semitopology: A point may have multiple minimal open neighbourhoods — examples are very easy to generate, see e.g. the top-right example in Figure 2. A finite semifilter need not have a least element (see Remark 8.1.6).

(3) Topology: Every finite T0 topology is sober. A topology is sober if and only if every nonempty irreducible closed set is the closure of a unique point. Semitopology: Neither property holds. See Lemma 9.3.8.

(4) Semitopological questions such as ‘is this a topen set’ or ‘are these two points intertwined’ or ‘does this point have a topen neighbourhood’ — and many other definitions in this paper, such as our taxonomy of points into regular, weakly regular, quasiregular, conflicted, and strongly compatible are novel and/or play a larger role in the theory than they typically do in topology.

12.2 Related work

Dualities We discussed duality results in detail in Remark 10.4.1. The reader may know that there are a many such results, starting with Stone’s classic duality between Boolean algebras and compact Hausdorff spaces with a basis of clopen sets [50, 24]. The duality between frames and topologies is described in [33, page 479, Corollary 4]. See also the encyclopaedic treatment in [9], with an overview in Example 2.9 on page 17. Our duality between semiframes and semitopologies fits into this canon.

Union sets, closure spaces, and minimal structures There is a thread of research into union-closed families; these are subsets of a finite powerset closed under unions, so that a union-closed families is precisely just a finite semitopology. The motivation is to study the combinatorics of finite sub-semilattices of a powerset. Some progress has been made in this [41]; the canonical reference for the relevant combinatorial conjectures is the ‘problem session’ on page 525 (conjectures 1.9, 1.9’, and 1.9”) of [45]. See also recent progress in a conjecture about union-closed families.35 There is no direct connection to semitopologies, and certainly no consideration of duality results. Perhaps the duality in this paper may be of some interest in that community.

A closure space is a subset of a powerset that is closed under intersections [15, page 173]. Up to taking sets complements, a closure space is a semitopology, and likewise a finite closure space is, up to taking sets complements, a union-closed family. The motivation for closure spaces is to study closure operations in a topology-flavoured style, so closure spaces (unlike union-closed sets) share a topological flavour with semitopologies. However the applications are completely different, and algebra reveals how the underlying structures are also mathematically distinct, as is made clear by a lattice-based presentation of closure spaces and morphisms [15, Subsection 2.4], which uses a structure of ‘based lattices’ (essentially: lattices plus a generating basis): this differs from semitopologies with their semiframe presentation as compatible complete semilattices.36

A minimal structure on a set X is a subset of pow(X) that contains ∅ and X. Thus a semitopology is a minimal structure that is also closed under arbitrary unions. There is a thread of research into minimal structures, studying how notions familiar from topology (such as continuity) fare in weak (minimal) settings [42] and how this changes as axioms (such as closure under unions) are added or removed. An accessible discussion is in [51], and see the brief but comprehensive references in Remark 3.7 of that paper. Of course our focus is on properties of semitopologies which are not considered in that literature; but we share an observation with minimal structures that it is useful to study topology-like constructs, in the absence of closure under intersections.

Algebraic topology as applied to distributed computing tasks The reader may know that solvability results about distributed computing tasks have been obtained from algebraic topology, starting with the impossibility of k-set consensus and the Asynchronous Computability Theorem [22, 3, 47] in

1993. See [21] for numerous such results.

The basic observation is that states of a distributed algorithm form a simplicial complex, called its protocol complex, and topological properties of this complex, like connectivity, are constrained by the underlying communication and fault model. These topological properties in turn can determine what tasks are solvable. For example: every algorithm in the wait-free model with atomic read-write registers has a connected protocol complex, and because the consensus task’s output complex is disconnected, consensus in this model is not solvable [21, Chapter 4].

This paper is also topological, but in a different way: we use (semi)topologies to study consensus in and of itself, rather than the solvability of consensus or other tasks in particular computation models. Put another way: the papers cited above use topology to study the solvability of distributed tasks, but this paper shows how the very idea of ‘distribution’ can be viewed as having a semitopological foundation.

Of course we can imagine that these might be combined — that in future work we may find interesting and useful things to say about the topologies of distributed algorithms when viewed as algorithms on and in a semitopology.

Fail-prone systems and quorum systems Given a set of processes P, a fail-prone system [35] (or adversary structure [23]) is a set of fail-prone sets F = {F1, ..., Fn} where, for every 1 ≤ i ≤ n, Fi ⊆ P. F denotes the assumptions that the set of processes that will fail (potentially maliciously) is a subset of one of the fail-prone sets. A dissemination quorum system for F is a set {Q1, ..., Qm} of quorums where, for every 1 ≤ i ≤ m, Qi ⊆ P, and such that

• for every two quorums Q and Q′ and for every fail-prone set F, (Q ∩ Q′) \F ≠ /0 and

• for every fail-prone set F, there exists a quorum disjoint from F.

Several distributed algorithms, such as Bracha Broadcast [5] and PBFT [10], rely on a quorum system for a fail-prone system F in order to solve problems such as reliable broadcast and consensus assuming (at least) that the assumptions denoted by F are satisfied.

Several recent works generalise the fail-prone system model to heterogeneous systems. Under the failure assumptions of a traditional fail-prone system, Bezerra et al. [2] study reliable broadcast when participants each have their own set of quorums. Asymmetric Fail-Prone Systems [1] generalise fail-prone systems to allow participants to make different failure assumption and have different quorums. In Permissionless Fail-Prone Systems [8], participants not only make assumptions about failures, but also make assumptions about the assumptions of other processes; the resulting structure seems closely related to witness semitopologies, but the exact relationship still needs to be elucidated.

Federated Byzantine Agreement Systems [36] are an instance of semitopologies. García-Pérez and Gotsman [20] rigorously prove the correctness of broadcast abstractions in Stellar’s Federated Byzantine Agreement model and investigate the model’s relationship to dissemination quorum systems. The Personal Byzantine Quorum System model [31] is an abstraction of Stellar’s Federated Byzantine Agreement System model and accounts for the existence of disjoint consensus clusters (in the terminology of the paper) which can each stay in agreement internally but may disagree between each other. Consensus clusters are closely related to the notion of topen in Definition 3.2.2(2).

Sheff et al. study heterogeneous consensus in a model called Learner Graphs [49] and propose a consensus algorithm called Heterogeneous Paxos.

Cobalt, the Stellar Consensus Protocol, Heterogeneous Paxos, and the Ripple Consensus Algorithm [34, 36, 49, 48] are consensus algorithms that rely on heterogeneous quorums or variants thereof. The Stellar network [30] and the XRP Ledger [48] are two global payment networks that use heterogeneous quorums to achieve consensus among an open set of participants; the Stellar network is an instance of a witness semitopology.

The literature on fail-prone systems and quorum systems is most interested in synchronisation algorithms for distributed systems and has been less concerned with their deeper mathematical structure. Some work by the second author and others [31] gets as far as proving an analogue to Proposition 3.4.4 (though we think it is fair to say that the presentation in this paper is simpler and clearer), but it fails to notice the connection with topology and the subsequent results which we present in this paper, and there is no consideration of algebra as used in this paper.

(Semi)lattices with extra structure I am not aware of semiframes having been studied in the literature, but they are in excellent company, in the sense that things have been studied that are structurally similar. We mention two examples to give a flavour of this extensive literature:

(1) A quantale is a complete lattice (Q, ⋁) with an associative multiplication operation ∗ :

(Q × Q) →Q that distributes over ⋁ in both arguments [46]. A commutative quantale

whose multiplication is restricted to map to either the top or bottom element in Q is close being a semiframe.37 For reference, a pleasingly simple representation result for quantales is given in [6].

(2) An overlap algebra is a complete Heyting algebra X with an overlap relation >< ⊆ X × X whose intuition is that x><y when x∧y is inhabited. The motivation for this comes from constructive logic, in which ∃p.(p ∈ x ∧ p ∈ y) is a different and stronger statement than ¬∀p.¬(p ∈ x ∧ p ∈ y). Accordingly, overlap algebras are described as ‘a constructive look at Boolean algebras’ [11].
Overlap algebras are not semiframes, but they share an idea with semiframes in making a structural distinction between ‘intersect’ and ‘have a non-empty join’.

12.3 Future work

The list of future work below is not exhaustive, of course. If this list inspires, through some omission that is obvious to the reader, a new idea, then that is best of all: finding good questions is the first and arguably most important step in research.

Remark 12.3.1 (Other notions of morphism).

In Definition 10.1.1(1) we take a morphism of semitopologies f : (P, Open) → (P′, Open′) to be a continuous function f : P → P′. Correspondingly, in Definition 10.2.1(1) we take a morphism of semiframes g : (X′, ≤′, ∗′) → (X, ≤, ∗) to be a compatible morphism of complete semilattices.

The reader may be familiar with conditions on maps between topologies other than continuity, such as being open ( f maps open sets to open sets) and closed ( f maps closed sets to closed sets). These also make sense in semitopologies.

A further natural design space in the semitopological case is to include conditions on sets intersections and strict inclusions. We briefly list some conditions that we could impose on f : P → P′:

(1) If O ≬ O′ then f -1(O) ≬ f -1(O′) (it is automatic that if f -1(O) ≬ f -1(O′) then O ≬ O′, but the reverse implication is a distinct condition).

(2) If O ⊊ O′ then f -1(O) ⊊ f -1(O′).

(3) O ≬ O′ implies f -1(O) ⊆ f -1(O′) implies O ⊆ O′, or an equivalent contrapositive:

O ≬O′ implies O ⊈O′ implies f-1(O) ⊈f-1(O′).38
Remark 12.3.2 (Representations).

The Sierpiński space Sk = (P, Open) sets P = {0, 1} and Open = {∅, {1}, {0, 1}}. This is both a topology and a semitopology, and it is a classifying space for open sets, in the sense that Hom(-, Sk) : SemiTop → Set is naturally isomorphic to Opns : SemiTop → Set which maps (P, Open) to Open.

Sk does not classify semitopologies, because semiframes suggest that we should view the set of open sets Open of a semitopology as a semiframe structure, having a subset inclusion (of course) and also a generalised intersection ≬. A likely classifying space for this is the the top-left example in Figure 2, such that

• P = {0, 1, 2} and

• Open = {∅, {0}, {2}, {0, 2}, {0, 1, 2}}.

With Sk in mind, this space looks like two copies of Sk glued end-to-end — i.e. like two open sets — where the 1 ∈ P represents where they might intersect. Call this space 3.

3 suggests that a logic for semiframes might be naturally three-valued, with values t, f, and also b for ‘is in the intersection’, and that the spaces Hom(-, 3) of continuous mappings to 3 might play a useful role. This might also have some impact on suitable notions of exponential space (see Remark 12.3.3). Current research [19] considers applying three-valued modal logics based on semitopologies to reason explicitly about decentralised algorithms, like Paxos [27].

Remark 12.3.3 (Exponential spaces).

It remains to check whether the category SemiFrame of semiframes is closed [32, page 180, Section VII.7], or Cartesian.39

It remains to look into the Vietoris (also called the exponential) semitopologies [14, Exercise 2.7.20, page 120], though in view of Remark 12.3.2 it is also an open question what the most suitable notion of exponential would be — we speculate that exponentials over 3 would be suitable.

More generally, it remains to study functors of the from Hom(-, B) and Hom(A, -), for different values of A and B.

Remark 12.3.4 (Finiteness and compactness).

The relation of semitopologies to finiteness is interesting. On the one hand, our motivating examples — distributed networks — are finite because they exist in the real world. On the other hand, in distributed networks, precisely because they are distributed, participants may not be able to depend on an exhaustive search of the full network being practical (or even permitted — this could be interpreted as a waste of resources or even as hostile or dangerous).

This requires mathematical models and algorithms that make sense on at least countably infinitely many points.40

In fact, arguably even ‘countably large’ is not quite right. The natural cardinality for semitopologies may be uncountable, since network latency means that we cannot even enumerate the network: no matter how carefully we count, we could always in principle discover new participants who have joined in the past (but we just had not heard of them yet).

This motivates future work in which we consider algebraic conditions on a semiframe (X, ≤ , ∗) that mimic some of the properties of open sets of finite semitopologies (without necessarily insisting on finiteness itself). For instance:

(1) We could insist that a ≤-descending chain of non-⊥X elements in X have a non-⊥X greatest lower bound in X.

(2) We could insist that a ≤-descending chain of elements strictly ≤-greater than some x ∈ X have a greatest lower bound that is strictly ≤-greater than x.

(3) We could insist that if (xi | i ≥ 0) and (yi | i ≥ 0) are two ≤-descending chains of elements, and xi ∗ yi for every i ≥ 0 — in words: xi is compatible with yi — then the greatest lower bounds of the two chains are compatible.

The reader may notice how these conditions are reminiscent of compactness conditions from topology: e.g. a metric space is compact if and only if every descending chain of open sets has a nonempty intersection. This is no coincidence, since one of the uses of compactness in topology is precisely to recover some of the characteristics of finite topologies.

Considering semiframes (and indeed semitopologies) with compactness/finiteness flavoured conditions, is future work.

Remark 12.3.5 (Computational/logical behaviour).

The original motivation for semiframes comes from semitopologies, which are motivated by blockchains and other decentralised systems, which are often real software artefacts that do real computation. It might therefore be useful to think about ‘computable’ semiframes, whatever this should mean. In [17] we consider witness semitopologies as a model of computably tractable semitopologies (being a witness semitopology is a concrete condition on sets), and we propose an algebraic abstraction of these as (strongly) chain-complete semitopologies; a semitopology is (strongly) chain-complete when any infinite descending chain of (nonempty) open sets has a (nonempty) open intersection. we argue that being chain-complete is an appropriate generalisation of the familiar Alexandrov condition on topologies.

This observation, along with Remark 12.3.4, suggests that it would be interesting to look at semiframes with additional conditions having to do with limits of possibly infinite descending chains.

Remark 12.3.6 (Generalising ∗).

In Remark 7.2.2 we mentioned that we can think of semitopologies not as ‘topologies without intersections’ so much as ‘topologies with a generalised intersection’. In this paper we have studied a relation called ≬ (for point-set semitopologies) and ∗ (for semiframes), which intuitively measure whether two elements intersect. But really, this is just a notion of generalised meet, which suggests:

• We would take (X, ≤) and (X′, ≤′) to be complete join-semilattices and the generalised meet ∗ : (X × X) → X′ is any commutative distributive map.

• We could generalise in a different direction and consider (for example) cocomplete symmetric monoidal categories: ∗ becomes the (symmetric) monoid action.

• We could generalise from binary intersections to n-ary intersections. This generalisation deserves its own brief discussion:

The literature on decentralised systems is rich in intersection conditions. A Q2 property from [12, Theorem 1] asserts (in semitopological language) that all pairs of nonempty open sets intersect — but there is more, e.g. a Q3 property [1, Definition 2] asserts that all triples of nonempty open sets intersect. Other unpublished work considers situations where up to five nonempty open sets should intersect. From the point of view of this paper, it suggests a sequence of n-ary generalisations of ≬ and ∗.

Furthermore, a B3 condition [12, Theorem 2][1, Definition 5], considers a situation of even greater generality (and worse behaviour!), where open neighbourhoods are local to points in the sense that if O ∈ nbhd(p) and p′ ∈ O then it does not necessarily follow that O ∈ nbhd(p′). This suggests ‘heterogeneous’ generalisations of semitopology and semiframe whose mathematical behaviour is at time of writing unexplored.

Remark 12.3.7 (Homotopy and convergence).

We have not looked in any detail at notions of path and convergence in semitopologies and semiframes. Preliminary considerations suggest that, in the finite case, a path converging to a point can be identified with a minimal open set containing that point. In the topological case this is trivial, since minimal open sets are least; in the semitopological case it is not, since there may be many minimal open sets (Lemma 2.1.2). Thus, even in a semitopology with no ‘holes’, it can be possible to approach a single point from multiple directions. Developing this part of the theory is future work.

Remark 12.3.8 (Constructive mathematics).

We have not considered what semiframes would look like in a constructive setting. Much of the interest in frames and locales (versus point-set topologies) comes from working in a constructive setting; e.g. in the topos of sheaves over a base space, locales give a good fibrewise topology of bundles. To what extent similar structures might be built using semiframes, or what other structures might emerge instead, are currently entirely open questions.

Remark 12.3.9 (Semiframes, logic, and analysis of real systems).

A natural application of semiframes is to help build logics for consensus, and in particular logics for consensus algorithms (like Paxos [27]). A declarative approach to specifying consensus algorithmms, based on

the semitopological ideas in this paper, is current research recently submitted for publication [19]. In separate work current at the time of writing, these techniques have helped find errors in a real consensus algorithm; details to be published in due course.

That work illustrates how the ideas in this paper can be made actionable to analyse properties of real consensus algorithms.

12.4 Final comments

Innovation in decentralised systems design is currently very active, and in particular there is much work on notions of consensus and quorum [1, 49, 8, 28, 2, 20, 30, 31, 16, 29], and many new systems [34, 36, 49, 48] (and this is just a sample of an active literature). This explosion of practical design is also an explosion of suggestions to the theory community, of new structures to consider. One way to do this is to apply a classic technique which has been usefully applied many times before: topologise, then dualise.

Of course, practitioners are also invited to learn more topology and algebra and consider phrasing some aspects of their systems in these terms.41 If there is one thing holding back practical progress in decentralised algorithm design, it is that it is exceptionally hard. If (semi)topology, algebra, and logic can help, then that will be a useful contribution.

References

[1] Orestis Alpos, Christian Cachin, Björn Tackmann, and Luca Zanolini. Asymmetric distributed trust. Distributed Computing, 37(3):247–277, 2024, Springer-Verlag. https://doi.org/10.1007/s00446-024-00469-1.

[2] João Paulo Bezerra, Petr Kuznetsov, and Alice Koroleva. Relaxed reliable broadcast for decentralized trust. In Mohammed-Amine Koulali and Mira Mezini, editors, Networked Systems, Lecture Notes in Computer Science, pages 104–118. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-17436-0_8.

[3] Elizabeth Borowsky and Eli Gafni. Generalized FLP Impossibility Result for T-resilient Asynchronous Computations. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC ’93, pages 91–100, New York, NY, USA, 1993. ACM.

[4] Nicolas Bourbaki. General Topology: Chapters 1-4. Elements of mathematics. Springer-Verlag, Berlin, 1998.

[5] Gabriel Bracha. Asynchronous Byzantine agreement protocols. Information and Computation, 75(2):130–143, November 1987, Elsevier. https://doi.org/10.1016/0890-5401(87)90054-X.

[6] Carolyn Brown and Doug Gurr. A representation theorem for quantales. Journal of Pure and Applied Algebra, 85(1):27–42, 1993, Elsevier. https://doi.org/10.1016/0022-4049(93)90169-T.

[7] Christian Cachin, Rachid Guerraoui, and Luís E. T. Rodrigues. Introduction to Reliable and Secure Distributed Programming (2. ed.). Springer, 2011. https://doi.org/10.1007/978-3-642-15260-3.

[8] Christian Cachin, Giuliano Losa, and Luca Zanolini. Quorum systems in permissionless networks. In Eshcar Hillel, Roberto Palmieri, and Etienne Rivière, editors, 26th International Conference on Principles of Distributed Systems (OPODIS 2022), volume 253 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.OPODIS.2022.17.

[9] Olivia Caramello. A topos-theoretic approach to Stone-type dualities, 2011. https://doi.org/10.48550/arXiv.1103.3493.

[10] Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems (TOCS), 20(4):398–461, 2002, ACM, New York, USA. http://dl.acm.org/citation.cfm?id=571640.

[11] Francesco Ciraulo and Michele Contente. Overlap Algebras: a Constructive Look at Complete Boolean Algebras. Logical Methods in Computer Science, 16, February 2020. https://doi.org/10.23638/LMCS-16(1:13)2020.

[12] Ivan Damgård, Yvo Desmedt, Matthias Fitzi, and Jesper Buus Nielsen. Secure protocols with asymmetric trust. In Kaoru Kurosawa, editor, Advances in Cryptology - ASIACRYPT 2007, 13th International Conference on the Theory and Application of Cryptology and Information Security, Kuching, Malaysia, December 2-6, 2007, Proceedings, volume 4833 of Lecture Notes in Computer Science, pages 357–375. Springer, 2007.

[13] B. A. Davey and Hilary A. Priestley. Introduction to Lattices and Order. Cambridge University Press, Cambridge, UK, 2 edition, 2002.

[14] Ryszard Engelking. General Topology. Sigma Series in Pure Mathematics. Heldermann Verlag, Berlin, 1989.

[15] Marcel Erné. Closure. In Beyond topology, volume 486, pages 163–238. American Mathematical Society, Rhode Island, USA, 2009.

[16] Martin Florian, Sebastian Henningsen, Charmaine Ndolo, and Björn Scheuermann. The sum of its parts: Analysis of federated byzantine agreement systems. Distributed Computing, 35(5):399–417, 10 2022, Springer-Verlag. https://doi.org/10.1007/s00446-022-00430-0.

[17] Murdoch J. Gabbay. Semitopology: decentralised collaborative action via topology, algebra, and logic. College Publications, London, UK, August 2024. https://www.collegepublications.co.uk/logic/?00056.

[18] Murdoch J Gabbay. Semitopology: a topological approach to decentralized collaborative action. Journal of Logic and Computation, 35(5), January 2025, Oxford University Press, Oxford, UK. https://doi.org/10.1093/logcom/exae050.

[19] Murdoch J. Gabbay and Luca Zanolini. A declarative approach to specifying distributed algorithms using three-valued modal logic, 2025. (Submitted for publication.) https://arxiv.org/abs/2502.00892.

[20] Álvaro García-Pérez and Alexey Gotsman. Federated byzantine quorum systems. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Germany, 2018. https://doi.org/10.4230/LIPIcs.OPODIS.2018.17.

[21] Maurice Herlihy, Dmitry Kozlov, and Sergio Rajsbaum. Distributed computing through combinatorial topology. Morgan Kaufmann, Burlington, Massachusetts, USA, 2013. https://doi.org/10.1016/C2011-0-07032-1.

[22] Maurice Herlihy and Nir Shavit. The asynchronous computability theorem for t-resilient tasks. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 111–120. Springer, Berlin, Heidelberg, 1993. https://doi.org/10.1007/978-3-662-53426-7_31.

[23] Martin Hirt and Ueli Maurer. Player Simulation and General Adversary Structures in Perfect Multiparty Computation. Journal of Cryptology, 13(1):31–60, January 2000, Springer, Berlin. https://doi.org/10.1007/s001459910003.

[24] Peter T. Johnstone. Stone spaces, volume 3. Cambridge University Press, 1986.

[25] Sabine Koppelberg. Handbook of Boolean algebras, volume 1. North-Holland, Amsterdam, 1989. Series editors Robert Bonnet and James Donald Monk.

[26] Leslie Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133–169, 05 1998, ACM, New York, NY, USA. http://doi.acm.org/10.1145/279227.279229.

[27] Leslie Lamport. Paxos made simple. ACM SIGACT News (Distributed Computing Column), 32(4):51–58, 2001, ACM. http://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/past/03F/notes/paxos-simple.pdf. Permalink: https://web.archive.org/web/20250320162715/https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/past/03F/notes/paxos-simple.pdf.

[28] Xiao Li, Eric Chan, and Mohsen Lesani. Quorum Subsumption for Heterogeneous Quorum Systems. In Rotem Oshman, editor, 37th International Symposium on Distributed Computing (DISC 2023), volume 281 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:19, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2023.28.

[29] Xiao Li and Mohsen Lesani. Open Heterogeneous Quorum Systems, April 2023. https://arxiv.org/abs/2304.02156v1.

[30] Marta Lokhava, Giuliano Losa, David Mazières, Graydon Hoare, Nicolas Barry, Eli Gafni, Jonathan Jove, Rafał Malinowsky, and Jed McCaleb. Fast and secure global payments with Stellar. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, SOSP ’19, page 80–96, New York, NY, USA, 2019. Association for Computing Machinery.

[31] Giuliano Losa, Eli Gafni, and David Mazières. Stellar consensus by instantiation. In Jukka Suomela, editor, 33rd International Symposium on Distributed Computing (DISC 2019), volume 146 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.

[32] Saunders Mac Lane. Categories for the Working Mathematician, volume 5 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1971. https://doi.org/10.1007/978-1-4757-4721-8.

[33] Saunders Mac Lane and Ieke Moerdijk. Sheaves in Geometry and Logic: A First Introduction to Topos Theory. Universitext. Springer-Verlag, New York, 1992. https://doi.org/10.1007/978-1-4612-0927-0.

[34] Ethan MacBrough. Cobalt: BFT Governance in Open Networks. 2 2018. Available online at https://doi.org/10.48550/arXiv.1802.07240.

[35] Dahlia Malkhi and Michael Reiter. Byzantine quorum systems. Distributed computing, 11(4):203–213, 10 1998, Springer-Verlag. https://doi.org/10.1007/s004460050050.

[36] David Mazières. The Stellar consensus protocol: a federated model for Internet-level consensus. Technical report, Stellar Development Foundation, 2015. https://www.stellar.org/papers/stellar-consensus-protocol.pdf. Permalink: https://web.archive.org/web/20240629063518/https://stellar.org/learn/stellar-consensus-protocol.

[37] Moni Naor and Avishai Wool. The load, capacity and availability of quorum systems. In Proceedings 35th Annual Symposium on Foundations of Computer Science, volume 27, pages 214–225. IEEE, New York, USA, 1994. https://doi.org/10.1109/SFCS.1994.365692.

[38] π-Base. https://topology.pi-base.org/theorems/T000420. A community database of topological counterexamples. Permalink: https://web.archive.org/web/20240108192930/https://topology.pi-base.org/theorems/T000420.

[39] Jorge Picado and Aleš Pultr. Frames and Locales: Topology Without Points. Frontiers in Mathematics. Birkhäuser, Basel Switzerland, 1st edition, 2012. https://doi.org/10.1007/978-3-0348-0154-6.

[40] Jorge Picado and Aleš Pultr. Separation in Point-Free Topology. Birkhäuser, Basel Switzerland, 1st edition, 2021. https://doi.org/10.1007/978-3-030-53479-0.

[41] Bjorn Poonen. Union-closed families. Journal of Combinatorial Theory, Series A, 59(2):253–268, 1992, Elsevier. https://doi.org/10.1016/0097-3165(92)90068-6.

[42] Valeriu Popa and Takashi Noiri. On the definitions of some generalized forms of continuity under minimal conditions. Memoirs of the Faculty of Science. Series A. Mathematics, 22:9–18, 01 2001, Kyushu University, Fukuoka, Japan.

[43] Emily Riehl. Category theory in context. Modern Math Originals. Dover, 2016. Available online at https://emilyriehl.github.io/files/context.pdf. Permalink: https://web.archive.org/web/20250115022343/https://emilyriehl.github.io/files/context.pdf.

[44] William H. Riker. The Theory of Political Coalitions. Yale University Press, 1962.

[45] Ivan Rival, editor. Graphs and Order. The Role of Graphs in the Theory of Ordered Sets and its Applications, volume 147 of Proceedings of NATO ASI, Series C (ASIC) in Banff, Canada. Springer, Dordrecht, 1985. https://doi.org/10.1007/978-94-009-5315-4.

[46] Kimmo I. Rosenthal. Quantales and their applications. Number 234 in Pitman Research Notes in Mathematics. Longman Scientific & Technical, UK, 1990.

[47] Michael Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, volume 29, pages 1449–1483, Philadelphia, USA, 2000. https://doi.org/10.1137/S0097539796307698.

[48] David Schwartz, Noah Youngs, and Arthur Britto. The Ripple Protocol Consensus Algorithm. Ripple Labs Inc White Paper, 5(8):151, 2014.

[49] Isaac Sheff, Xinwen Wang, Robbert van Renesse, and Andrew C. Myers. Heterogeneous Paxos. In Quentin Bramas, Rotem Oshman, and Paolo Romano, editors, 24th International Conference on Principles of Distributed Systems (OPODIS 2020), volume 184 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:17, Dagstuhl, Germany, 2021. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2020.5.

[50] Marshall H. Stone. The theory of representation for boolean algebras. Transactions of the American Mathematical Society, 40(1):37–111, July 1936, American Mathematical Society, Rhode Island, USA. https://doi.org/10.2307/1989664.

[51] Árpád Száz. Minimal structures, generalized topologies, and ascending systems should not be studied without generalized uniformities. Filomat (Nis), 21(1):87–97, 2007, University of Nis, Faculty of Sciences and Mathematics, Serbia. http://www.jstor.org/stable/26194889.

[52] Steven Vickers. Topology via Logic. Cambridge University Press, USA, 1989.

[53] Wikipedia. Equivalence of categories. http://en.wikipedia.org/w/index.php?title=Equivalence%20of%20categories&oldid=1227082771, 2024. Permalink: https://web.archive.org/web/20230316075107/https://en.wikipedia.org/wiki/Equivalence_of_categories.

[54] Wikipedia. Ideal (order theory); maximal ideals. http://en.wikipedia.org/w/index.php?title=Ideal%20(order%20theory)&oldid=1200832357, 2024. Permalink: https://web.archive.org/web/20230724184908/https://en.wikipedia.org/wiki/Ideal_(order_theory)#Maximal_ideals.

[55] Wikipedia. Separation axiom; main definitions. https://en.wikipedia.org/w/index.php?title=Separation%20axiom&oldid=1230514922#Main_definitions, 2024. Permalink: https://web.archive.org/web/20221103233631/https://en.wikipedia.org/wiki/Separation_axiom#Main_definitions.

[56] Stephen Willard. General Topology. Addison-Wesley, 1970. Reprinted by Dover Publications, New York, USA.

Acknowledgements

I dedicate this paper to the memory of Phil Scott: colleague, mentor, gentleman, friend, and inspiration to us all.

I am extremely grateful to the anonymous referees for feedback on this work. Thanks to Giuliano Losa and the Stellar Development Foundation for their generous support and funding in pursuing this research.

Notes

1It is actually much worse than this: we may also have to worry about messages being lost or delayed, and about some participants being faulty, and not following algorithms and protocols correctly. But even in the ideal case where communication is reliable and all participants are correct, decentralised algorithms are still hard. ↩

2Pedant point: some blockchains have a central control, but this is a special case: most are fully decentralised. ↩

3The empty set has no resources but is still an actionable coalition because it has no members, so all of those members can act as they like. ↩

4How to design an algorithm that can run on a decentralised system and get coherent and sensible behaviour from the overall system, even though any actionable coalition can (within the rules of the algorithm) potentially agree on some action and carry it out, without waiting for participants not in that coalition to participate, approve, or even necessarily know that an action has been taken — is the challenge of designing decentralised algorithms. It is not easy! Explaining the magic of practical decentralised algorithms is out of scope for this paper; but it can be done, and notions of actionable coalition are often key to such algorithms. The interested reader can find more information in [27, 7]. ↩

5Our ants, being mathematical idealisations, are massless and occupy zero volume. However, even if the ants had mass and volume, some of them could just stand around drinking the ant equivalent of tea and encouraging the ones who are actually doing the heavy lifting; the mathematics of actionable coalitions makes no practical judgments about which participants are doing useful work in the actual implementation. ↩

6There is a little overlap between this clause and the first one: if X = ∅ then by convention ⋃ X = ∅. Thus, ∅∈ Open(P) follows from both clause 1 and clause 2. If desired, the reader can just remove the condition ∅∈ Open(P) from clause 1, and no harm would come of it. ↩

7Affirmation: Something declared to be true; a positive statement or judgment (https://www.wordnik.com/words/ affirmation, permalink: https://web.archive.org/web/20230608073651/https://www.wordnik.com/words/ affirmation). ↩

8The other main classification is conflicted points, in Definition 5.3.1. These properties are connected by an equation: regular = weakly regular + conflicted; see Theorem 5.3.4. ↩

9According to Wikipedia, this space is also called indiscrete, anti-discrete, concrete, and codiscrete (https://en.wikipedia.org/wiki/Trivial_topology). ↩

10The empty set is trivially transitive and open, so it would make sense to admit it as a (degenerate) topen. However, it turns out that we mostly need the notion of ‘topen’ to refer to certain kinds of neighbourhoods of points (we will call them communities; see Definition 4.1.4). It is therefore convenient to exclude the empty set from being topen, because while it is the neighbourhood of every point that it contains, it is not a neighbourhood of any point. ↩

11‘Transitive open’ → ‘topen’, like ‘closed and open’ → ‘clopen’. ↩

12Following Definition 2.1.3 and Example 2.1.4(3), this is just {0, 1} with the discrete semitopology. ↩

13See also Theorem 11.5.4, which does something similar for semiframes. ↩

14Lemma 6.2.2 packages this argument up nicely with some slick notation, which we have not yet set up. ↩

15‘Properly reflexive’ is a loose riff on terminologies like ‘proper subset of’ or ‘proper ideal of a ring’. We might also call this ‘non-⊥ reflexive’, which is descriptive, but perhaps a bit of a mouthful. ↩ ↩

16Just being a complete lattice is not enough; it has to be distributive as well. Consider ω+1 = N ∪{ω} with its usual ordering, augmented with an element d such that 0 ≤ d ≤ ω. Then ω = ⋁ N and d ∗ ω, but ¬(d ∗ n) for every n ∈N. ↩

17Recall that a proper filter is a filter that does not contain ⊥. ↩

18This is carefully worded. We care about abstracting properties of finite semitopologies, but we should not restrict to considering only semitopologies and semiframes that are actually finite! See Remark 12.3.4. ↩

19A proper filter is a filter that does not contain ⊥. A maximal filter is a filter that is maximal amongst proper filters. ↩

20A succinct proof is in Wikipedia [54]. ↩

21Unpacking what that means, we obtain this: x ≠ ⊥∧ x = x′ or x ≠ ⊥∧ x′ = ⊤ or x′ ≠ ⊥∧ x = ⊤. This definition for ∗ is what we need for our counterexample, but other choices for ∗ also yield valid semiframes. For example, we can set x ∗ x′ when x, x′ ≠ ⊥. ↩

22See also a discussion of the design of the notion of semifilter in Remarks 8.1.6 and 10.3.4. ↩

23There are no guarantees in general about how many abstract points exist; e.g. Lemma 8.2.7 gives an example of a semiframe that has no abstract points at all and so maps to the empty semitopology. Later on in Definition 9.1.2 we consider conditions to ensure the existence of abstract points. ↩

24More on this topic later on in Definition 10.2.1, when we build the category of semiframes. ↩

25‘Unnecessary’ and ‘enough’ are in scare quotes here because these are subjective terms. For example, if points represent computer servers on a network then we might consider it a feature to not be T0 by having multiple points that are topologically indistinguishable — e.g. for backup, or to reduce latency — and likewise, we might consider it a feature to not have one concrete point for every abstract point, if this avoids redundancies. There is no contradiction here: a computer network based on a small non-sober space with multiple backups of what it has, may be a more efficient and reliable system than one based on a larger non-sober space that does not back up its servers but is full of redundant points. And, this smaller non-sober space may present itself to the user abstractly as the larger, sober space. Users may even forget about the computation that goes on under the hood of this abstraction, as illustrated by the following true story: I had a paper presenting an efficient algorithm rejected because it ‘lacked motivation’. Why? Because the algorithm was unnecessary: the reviewer claimed, apparently with a straight face, that guessing the answer until you got it right was computationally equivalent. ↩

26A discussion of possible alternatives, for future work, is in Remark 12.3.1. See also Remarks 8.1.3 and 8.1.6. ↩

27The Wikipedia page is also exceptionally clear [53]. ↩

28This is not a necessary condition; non-adjoint equivalences are possible. But the duality in this paper comes from an adjoint equivalence. ↩

29Confusing terminology alert: Definition 3.2.2(1) also has a notion of transitive set. The notion of transitive set is well-defined for a set that may not be open. In the world of semiframes, we just have elements of the semiframe (which correspond, intuitively, to open sets). Thus transitive semiframe elements correspond to (nonempty) transitive open sets of a semitopology, which are called topens. ↩

301 is also a conflicted point; see Example 5.3.2(1). This is no accident: by Lemma 6.3.1(2) if p is conflicted then it is not hypertransitive, and by Lemma 11.3.8 it follows that nbhd(p)∗ is not compatible. ↩

31If we stretch the English language, we might say that soberifying a space can conflictify one of its points. ↩

32...meaning that every abstract point in (Open, ⊆, ≬) is the neighbourhood semifilter of a unique concrete point in P. ↩

33The Wikipedia page on separation axioms [55] includes an excellent overview with over a dozen separation axioms. No anti-separation axioms are discussed. ↩

34An extra word on this: Our theory of semitopologies admits spaces whose points partition into distinct communities. Surely it must be bad if not all points need be in consensus in a final state? Not at all: for example, most blockchains have a mainnet and several testnets and it is understood that each should be coherent within itself, but different nets need not be in consensus with one another — indeed, if the mainnet had to agree with a testnet then this would likely be a bug, not a feature. So the idea of a single space with multiple partitions of consensus is not a new idea; it is an old idea, which we frame in a new, fruitful, and more general way. ↩

35https://web.archive.org/web/20230330170701/https://en.wikipedia.org/wiki/Union-closed_sets_ conjecture#Partial_results. ↩

36There are other differences too. For example: in a semitopology, the closure of the empty set is empty; in a closure space it need not be. This is because the ‘closure’ in a closure space is intended in a subtly different sense, which is intended to model things that include ‘deductive closure of’, and the deductive closure of the empty set is the set of tautologies, which might be nonempty. ↩

37But not quite! We also need proper reflexivity (Definition 7.2.1(2)), and quantale morphisms do not necessarily map the top element to the top element like semiframe morphisms should (Definitions 7.1.2 and 10.2.1(1)). ↩

38This condition is motivated by a study of graph representations of semitopologies. See [17, Chapter 17]. ↩

39It would be surprising if it were not Cartesian. The category of semitopologies is Cartesian. ↩

40This is no different than a programming language including a datatype of arbitrary precision integers: the program must eventually terminate, but because we do not know when, we need the idea of an infinity in the language. ↩

41A start on this is in [19]. True story: I attended a talk on a novel distributed consensus algorithm which featured an interesting five-way quorum intersection condition. I said to the speaker after the talk “So consider each quorum as a proposition: what are the five properties that your algorithm needs to guarantee, in the sense that they are always true at some point?” — a natural question, given my background in logic. The speaker, who is no fool and is expert in practical systems, had not thought of things in this way and did not know to answer. I suggested that until this question was answered, he didn’t really understood his algorithm. Of course I tried to be polite, tactful and constructive when I said this, but it’s true. ↩