subcaption basicstyle=, keywordstyle=, commentstyle=, stringstyle=

# Semitopology: a survey of a topological approach to distributed
collaborative action

Murdoch J. Gabbay Giuliano Losa  Heriot-Watt University, UK  Stellar
Development Foundation, USA

###### Abstract

We introduce _semitopologies_ , a generalisation of point-set topology that
removes the restriction that intersections of open sets need necessarily be
open.

The intuition is that points are participants in some distributed system, and
an open set is a collection of participants that can collaborate to update
their local state by taking a distributed collaborative action; we call this
an _actionable coalition_.

What constitutes an actionable coalition depends on what actions we want to
model. Intuitive examples include ‘a group of people that is collectively
strong enough to lift a rock’, where the state update is very simply ‘holding
rock low’ to ‘holding rock high’ and this update is common to all participants
in the actionable coalition. Or, consider ‘two people wishing to barter a can
of juice for a bar of chocolate’, in which case the coalition is any such pair
and the state updates differ between participants to flip them between
‘has/has no juice’ and ‘has/has no chocolate’.

A characteristic of these systems is that state updates are local to the
coalition, voluntary, may vary between participants, and are not assumed
subject to permission or synchronisation by a central authority. Peer-to-peer
computer networks, including filesharing and blockchain systems, provide
motivating examples from computing.

This paper presents an abstract mathematics that is inspired by these
considerations. The maths is interesting in and of itself, much like point-set
topology is; and it provides a conceptual framework within which to understand
a useful class of distributed systems.

###### keywords:

Topology, Semitopology

###### Contents

  1. 1 Introduction
    1. 1.1 What is a ‘distributed collaborative action’, and what is a semitopology?
    2. 1.2 Semitopology applied to distributed collaborative action
    3. 1.3 Map of the paper
  2. 2 Semitopology
    1. 2.1 Definitions, examples, and some discussion
      1. 2.1.1 Definitions
      2. 2.1.2 Examples
      3. 2.1.3 Some discussion
    2. 2.2 Continuity, and its interpretation
    3. 2.3 Neighbourhoods of a point
  3. 3 Transitive sets and topens
    1. 3.1 Some background on sets intersection
    2. 3.2 Transitive open sets and value assignments
    3. 3.3 Examples and discussion of transitive sets and topens
    4. 3.4 Closure properties of transitive sets
    5. 3.5 Closure properties of topens
    6. 3.6 Intertwined points
      1. 3.6.1 The basic definition, and some lemmas
      2. 3.6.2 Pointwise characterisation of transitive sets
    7. 3.7 Strong topens: topens that are also subspaces
      1. 3.7.1 Definition and main result
      2. 3.7.2 Connection to lattice theory
      3. 3.7.3 Topens in topologies
  4. 4 Open interiors, communities, and regular points
    1. 4.1 Community of a (regular) point
    2. 4.2 Further exploration of (quasi-/weak) regularity and topen sets
    3. 4.3 Intersection and partition properties of regular spaces
    4. 4.4 Examples of communities and (ir)regular points
  5. 5 Closed sets
    1. 5.1 Closed sets
    2. 5.2 Duality between closure and interior
    3. 5.3 Transitivity and closure
    4. 5.4 Closed neighbourhoods and intertwined points
      1. 5.4.1 Definition and basic properties
      2. 5.4.2 Application to characterise (quasi/weak) regularity
    5. 5.5 Intersections of communities with open sets
    6. 5.6 Regularity, maximal topens, and minimal closed neighbourhoods
    7. 5.7 More on minimal closed neighbourhoods
      1. 5.7.1 Regular open/closed sets
      2. 5.7.2 Intertwined points and regular open sets
      3. 5.7.3 Minimal nonempty regular closed sets are precisely the minimal closed neighbourhoods
    8. 5.8 How are $p_{\between}$ and $|p|$ related?
  6. 6 (Un)conflicted points: transitivity of $\mathrel{\between}$
    1. 6.1 The basic definition
    2. 6.2 A key result: regular = weakly regular + unconflicted
    3. 6.3 The boundary of $p_{\between}$
    4. 6.4 The intertwined preorder
      1. 6.4.1 Definition and properties
      2. 6.4.2 Application to quasiregular conflicted spaces
      3. 6.4.3 (Un)conflicted points and boundaries of closed sets
    5. 6.5 Regular = quasiregular + hypertransitive
      1. 6.5.1 Hypertransitivity
      2. 6.5.2 The corollary
  7. 7 The product semitopology
    1. 7.1 Basic definitions and results (shared with topologies)
    2. 7.2 Componentwise composition of semitopological properties
    3. 7.3 Minimal closed neighbourhoods, with an application to a counterexample
  8. 8 Computing semitopologies: witnessed sets and the witness semitopology
    1. 8.1 Discussion
    2. 8.2 The witness function and semitopology
    3. 8.3 Examples
    4. 8.4 Computing open and closed sets in witness semitopologies
      1. 8.4.1 Computing open sets: $X$ is open when $X\prec X$
      2. 8.4.2 Computing closed sets using limit points: $|P|=\mathit{lim}(P)$
    5. 8.5 Declarative content of witness semitopologies
      1. 8.5.1 Witnessed sets and Horn clause theories
      2. 8.5.2 Witnessed sets and topologies
  9. 9 (Strongly) chain-complete semitopologies
    1. 9.1 Definition and discussion
    2. 9.2 Elementary properties of the definition
    3. 9.3 Consequences of being strongly chain-complete
      1. 9.3.1 Strongly chain-complete implies $\mathrel{\between}$-complete
      2. 9.3.2 Indirectly regular points: inherent properties
      3. 9.3.3 Indirectly regular points in the context of other regularity properties
    4. 9.4 Witness semitopologies are chain-complete
    5. 9.5 Minimal sets: open covers and atoms
      1. 9.5.1 Open covers (minimal open neighbourhoods)
      2. 9.5.2 Atoms (minimal nonempty open sets)
      3. 9.5.3 Discussion
  10. 10 Kernels: the atoms in a community
    1. 10.1 Definition and examples
    2. 10.2 Characterisations of the kernel
    3. 10.3 Further properties of kernels
      1. 10.3.1 Intersections between the kernel of $p$ and its open neighbourhoods
      2. 10.3.2 Idempotence properties of the kernel and community
  11. 11 Dense subsets and continuous extensions
    1. 11.1 Definition and basic properties
    2. 11.2 Dense subsets of topen sets
    3. 11.3 Explaining kernels
    4. 11.4 Unifying is-transitive and is-strongly-dense-in
    5. 11.5 Towards a continuous extension result
    6. 11.6 Kernels determine values of continuous extensions
  12. 12 Conclusions
    1. 12.1 Topology vs. semitopology
    2. 12.2 Related work
    3. 12.3 Future work

##  1 Introduction

###  1.1 What is a ‘distributed collaborative action’, and what is a
semitopology?

Let $\bm{\mathsf{P}}$ be the set of all people, which we may call points (as
in point-set topology), and assume these come with a local state with just two
values: ‘exists’, or ‘will exist’. Suppose that for two distinct existing
people $\\{p_{him},p_{her}\\}\subseteq\bm{\mathsf{P}}$ there is some set of
$p_{child}$ people such that the former can (but are not obliged to)
collaborate to act together to change the state of $p_{child}$ from ‘will
exist’ to ‘exists’.

Extensive literatures exist to reflect and advise on the implementational
details of this scenario — but this being a maths paper, we work with an
idealised model. Even for this simple model, we can make some observations:

A notion of collaboration is built in to the fact that no single point can act
on its own. Indeed, at least three distinct points — a $p_{him}$, a $p_{her}$,
and a suitable $p_{child}$ — are required for the local state of the one point
$p_{child}$ to get updated.

No central authority exists to coordinate or authorise state updates.

The state updates that do occur are local; a set
$\\{p_{him},p_{her},p_{child}\\}$ can act to update the existence of
$p_{child}$, but this update is local to the participants involved in the
particular action.111In the real world, births are supposed to be registered;
but this is a _separate action_. People were making babies by distributed
collaborative action before central governments and a population census.

Actions may overlap, and (provided they are compatible) they need not be
identical: e.g. $\\{p_{him},p_{her},p_{child},p_{child}^{\prime}\\}$ could
collaborate to update the states of two children. Likewise for
$\\{p_{him},p_{her},p_{child},p_{him}^{\prime},p_{child}^{\prime}\\}$ or
$\\{p_{him},p_{her},p_{child},p_{her}^{\prime},p_{child}^{\prime}\\}$

There are many examples of similar distributed systems. A swarm of birds or
drones, groups of pedestrians, and crowds of sports or music fans can and do
communicate locally to make local updates to their speeds and directions. Note
that the updates need not be identical: e.g. if two pedestrians see that they
are about to collide, then they had better _not_ both dodge in the same
direction.

In computing, peer-to-peer filesharing systems locally exchange data (to be
fair, this may be mediated by so-called _tracker nodes_ , but these are also
usually distributed); the _Fediverse_ of the distributed social network
Mastodon works is in a similar spirit; and so on, and so forth.

Most modern blockchain systems also evolve their state by distributed
collaborative action in a similar spirit. The technical details vary, but a
typical example is a proof-of-stake system that makes progress such that a
group of participants can update their state if they held a majority of the
stake at some time in the past (e.g. two weeks ago) — the idea being that all
participants have reached agreement on, and learned, the state of the network
two weeks in the past, so this can be treated as immutable common knowledge
without undermining the distributed nature of the system in the present
[Goo14, Subsection 3.2.1, final paragraph]. In the XRP Ledger [SYB14] and
Stellar blockchain networks [LLM+19] (which are not proof-of-stake or proof-
of-work systems) a notion of ‘actionable coalition’ is represented explicitly
in the engineering architecture of the system.

Thus, the maths in this paper reflects and is motivated by simple and natural
intuitive examples as above, and also by the practical realities of more
complex systems that at time of writing are up and running and providing
services to their users by doing real things.

So at a very high level, what do the examples above have in common?

There is a notion of what we can call an _actionable coalition_ — soon, we
will just call this an _open set_. This is a set $O\subseteq\bm{\mathsf{P}}$
of participants with the capability, though not the obligation, to act
collaboratively to advance (= update / transition) the local state of the
elements in $O$, possibly but not necessarily in the same way for every $p\in
O$ (it depends on the context; we will discuss this).

$\varnothing$ is trivially an actionable coalition. Also we assume that
$\bm{\mathsf{P}}$ is actionable, since if it were not then literally nothing
could ever get done.

A sets union of actionable coalitions, is an actionable coalition. This leads
us to the definition of a semitopology.

######  Notation 1.1.1.

Suppose $\bm{\mathsf{P}}$ is a set. Write $\mathit{pow}(\bm{\mathsf{P}})$ for
the powerset of $\bm{\mathsf{P}}$ (the set of subsets of $\bm{\mathsf{P}}$);
there will be more on this in Notation 8.2.1.

######  Definition 1.1.2.

A semitopological space, or semitopology for short, consists of a pair
$(\bm{\mathsf{P}},\mathsf{Open}(\bm{\mathsf{P}}))$ of

a (possibly empty) set $\bm{\mathsf{P}}$ of points, and

a set $\mathsf{Open}(\bm{\mathsf{P}})\subseteq\mathit{pow}(\bm{\mathsf{P}})$
of open sets, such that:

$\varnothing\in\mathsf{Open}(\bm{\mathsf{P}})$ and
$\bm{\mathsf{P}}\in\mathsf{Open}(\bm{\mathsf{P}})$.

If $X\subseteq\mathsf{Open}(\bm{\mathsf{P}})$ then $\bigcup
X\in\mathsf{Open}(\bm{\mathsf{P}})$.222There is a little overlap between this
clause and the first one: if $X=\varnothing$ then by convention $\bigcup
X=\varnothing$. Thus, $\varnothing\in\mathsf{Open}(\bm{\mathsf{P}})$ follows
from both clause 1 and clause 2. If desired, the reader can just remove the
condition $\varnothing\in\mathsf{Open}(\bm{\mathsf{P}})$ from clause 1, and no
harm would come of it. We may write $\mathsf{Open}(\bm{\mathsf{P}})$ just as
$\mathsf{Open}$, if $\bm{\mathsf{P}}$ is irrelevant or understood, and we may
write $\mathsf{Open}_{\neq\varnothing}$ for the set of nonempty open sets.

The reader will recognise a semitopology as being like a _topology_ on
$\bm{\mathsf{P}}$, but without the condition that the intersection of two open
sets necessarily be an open set. This reflects the fact that the intersection
of two actionable coalitions need not itself be an actionable coalition.

Armed with this simple definition and bearing in mind its modern relevance as
noted above, this paper introduces and surveys point-set semitopologies and
their properties. There is an emphasis (though not an exclusive one) on
studying distributed collaborative actions, which (broadly speaking) amounts
to studying antiseparation properties of points, and how this interacts with
topological continuity of functions out of semitopologies. The details of what
this means are unpacked below.

######  Remark 1.1.3.

Traditional notions of consensus and voting can be understood in a
semitopological framework. For instance, a committee may make a decision by
two-thirds majority vote; the set of all 2/3 majorities of some
$\bm{\mathsf{P}}$ is a semitopology (note that it is not a topology). Also,
concrete algorithms to attain consensus often use a notion of _quorum_ [Lam98,
LSP82]; a set of participants whose unanimous adoption of a value guarantees
that other (typically all other) participants will eventually also adopt this
value. Social choice theorists have a similar notion called a _winning
coalition_ [Rik62, Item 5, page 40]. If the reader has a background in logic
then they may be reminded of a whole field of _generalised quantifiers_ (a
good survey is in [Wes11]).

The reader should just note that these examples have a synchronous,
centralised flavour.

For instance: a vote in the typical democratic sense is a synchronous, global
operation (unless the result is disputed): votes are cast, collected, and then
everyone gets together — e.g. in a vote counting hall — to count the votes and
agree on who won and so certify the outcome.333The first author has seen this
happen; votes being tallied up while under supervision by representatives of
all parties on the ballot. It is a moving sight. But it is not distributed.
This is certainly a collaborative action, but it is centralised, not
distributed.

Our semitopological framework adds to the above by allowing us to study
_distributed_ collaborative action, which can progress by local state updates
on actionable coalitions (which certainly do not need to be simple
majorities), and they can so act without _necessarily_ having to synchronise
step-by-synchronous-step on global state updates.

###  1.2 Semitopology applied to distributed collaborative action

In this short subsection we give a taste of how topological ideas can be
applied to understand distributed collaborative action. This is not an
exhaustive overview (for that, see Subsection 1.3).

Recall the Hausdorff separability condition that two points have disjoint open
neighbourhoods, and invert it: call two points _intertwined_ when all of their
open neighbourhoods intersect (see Definition 3.6.1 and Remark 3.6.10). Within
a set of intertwined points, topological continuity implies agreement (see
Lemma 2.2.4 and Corollary 3.6.9). As we build up the mathematics further and
understand more deeply what is going on, we will discover deeper and more
canonical mathematical reasons why this notion arises (having to do with
theories of dense subsets and continuous extensions of functions; see Section
11 and the high-level discussion in Remark 11.5.3).

Call a set of pairwise intertwined points that is open, a _topen set_ (for
_transitive open set_ ; Definition 3.2.1 and Remark 3.5.5). So this
intuitively is an actionable coalition that is guaranteed to be in agreement,
where algorithms succeed. One of our main early results is to prove that a
semitopological space partitions itself automatically into a collection of
disjoint maximal topen sets (Theorem 3.5.4). Thus, an arbitrary semitopology
naturally partitions itself into areas of local collaboration, reflecting the
way that e.g. people tend to self-organise themselves into tribes or
communities.

We then identify a well-behavedness criterion of being a _regular point_
(Definition 4.1.4(4.1.4)) and relate this to other well-behavedness conditions
in results discussed in Remark 5.6.1 and 6.5.9. We go on to identify results
which echo Arrow’s theorem from social choice theory, which prove that any
semitopology must contain certain _kernel_ subsets that dictate its behaviour.
See the discussion in Remark 10.1.1.

The interested reader might like to jump to one of these results, and read
backwards or forwards from there.

This is a long paper, in part because our goal is to introduce a new field of
research (even if it does consciously draw on classical techniques from point-
set topology), and show what is possible within it. The reader is not obliged
to read linearly and is free to look up what interests them, and proceed from
there.

###  1.3 Map of the paper

  1. 1.

Section 1 is the Introduction. You Are Here.

  2. 2.

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

  3. 3.

In Section 3 we introduce _transitive sets_ , _topens_ , and _intertwined
points_. These are all different views on the anti-separation well-behavedness
properties that will interest us in this paper. Most of Section 3 is concerned
with showing how these different views relate and in what senses they are
equivalent (e.g. Theorem 3.6.8). Transitive sets are guaranteed to be in
agreement (in a sense made precise in Theorem 3.2.3 and Corollary 3.2.5), and
we take a first step to understanding the fine structure of semitopologies by
proving that every semitopology partitions into topen sets (Theorem 3.5.4),
plus other kinds of points which we classify in the next Section.

  4. 4.

In Section 4 we start to classify points in more detail, introducing notions
of _regular_ , _weakly regular_ , and _quasiregular_ points (Definition
4.1.4).444The other main classification is _conflicted_ points, in Definition
6.1.1. These properties are connected by an equation: regular = weakly regular
+ unconflicted; see Theorem 6.2.2.

Regular points are those contained in some topen set, and they display
particularly good behaviour. Regularity will be very important to us and we
will characterise it in multiple ways: see Remark 4.2.5. (A survey of
characterisations of weak regularity requires more machinery and appears in
Remark 5.4.7.)

  5. 5.

In Section 5 we study closed sets, and in particular the interaction between
intertwined points, topens, and closures. Typical results are Proposition
5.4.3 and Theorem 5.6.2 which characterise sets of intertwined points as
minimal closures. The significance to consensus is discussed in Remarks 5.5.1
and 5.5.5.

  6. 6.

In Section 6 we study unconflicted and hypertransitive points, leading to two
useful characterisations of regularity in Theorems 6.2.2 and 6.5.8.

  7. 7.

In Section 7 we consider product semitopologies. These are defined just as for
topologies (Definition 7.1.2) but we study how the semitopological properties
we have considered above — like being intertwined, topen, regular, conflicted,
and so forth — interact with taking products. This is also useful for building
large complex counterexamples out of smaller simpler ones (examples in
Corollary 7.2.6 or Theorem 7.3.4).

  8. 8.

In Section 8 we construct a novel theory of computationally tractable
semitopologies, based on _witness functions_ (Definition 8.2.2(8.2.2)). We
call semitopologies generated by witness functions _witness semitopolgies_.
These display excellent algorithmic behaviour (Remarks 8.4.6 and 8.4.14) and
we note deep reasons why this is so by showing that witness functions
correspond to Horn clause theories, and that open and closed sets in the
witness semitopology are related to answer sets to those theories; see
Subsection 8.5.

  9. 9.

In Section 9 we introduce _(strongly) chain-complete_ semitopologies. We argue
in Remark 9.4.6 that these have properties making them a suitable abstraction
of finite semitopologies — finite semitopologies are of particular interest
because these are the ones that we can build. We study their properties and
prove a key result that witness semitopologies are chain-complete (Theorem
9.4.1), even if they are infinite.555We discuss why infinite semitopologies
matter, even in a world of finite implementations, in Remark 9.4.7. Note also
that in a real system there may be hostile participants who report an
unbounded space of ‘phantom’ points, either for denial-of-service or to create
‘extra voters’. So even a system that is physically finite may present itself
as infinite.

  10. 10.

A key property in a strongly chain-complete semitopology is that the poset of
open sets is _atomic_ , i.e. minimal nonempty open sets always exist. In
Section 10 we study the _kernel_ of a point $p$ — unions of atomic transitive
open sets — especially in strongly chain-complete semitopologies where atoms
are guaranteed to exist. We will see that the kernel dictates behaviour at
$p$, in a sense we make formal (see discussion in Remark 10.1.1).

  11. 11.

In Section 11 we study the notion of ‘dense subset of’ from topology and see
that this splits into two notions: _weakly dense in_ and _strongly dense in_
(Definition 11.1.2). Transitivity turns out to be closely related to denseness
(Proposition 11.4.6). We prove a continuous extension result and show that
this leads naturally back to the notion of regular point and topen set which
we developed to begin with (Remark 11.5.1).

This closes the arc of the mathematics: from initial definitions to a high-
level explanation of why these were so useful.

  12. 12.

In Section 12 we conclude and discuss related and future work. We discuss
connections with related work in Subsection 12.2 (notably: semiframe theory,
semilattice theory, minimal structures, algebraic topology, and fail-prone
systems and quorum systems).

######  Remark 1.3.1.

Algebraic topology has been applied to the solvability of distributed-
computing tasks in various computational models (e.g. the impossibility of
wait-free $k$-set consensus using read-write registers and the Asynchronous
Computability Theorem [HS93, BG93, SZ93]; see [HKR13] for a survey).
Semitopology is not topology, and this is not a paper about algebraic topology
applied to the solvability of distributed-computing tasks!

This paper is about the mathematics of actionable coalitions, as made precise
by point-set semitopologies; their antiseparation properties; and the
implications to partially continuous functions on of them. If we discuss
distributed systems, it is by way of providing motivating examples or noting
applicability.

##  2 Semitopology

###  2.1 Definitions, examples, and some discussion

####  2.1.1 Definitions

Recall from Definition 1.1.2 the definition of a semitopology.

######  Remark 2.1.1.

As a sets structure, a semitopology on $\bm{\mathsf{P}}$ is like a _topology_
on $\bm{\mathsf{P}}$, but without the condition that the intersection of two
open sets be an open set.

As a lattice structure, a semitopology on $\bm{\mathsf{P}}$ is a bounded
complete join-subsemilattice of $\mathit{pow}(\bm{\mathsf{P}})$.666 _Bounded_
means closed under empty intersections and unions, i.e. containing the empty
and the full set of points. _Complete_ means closed under arbitrary (possibly
empty, possibly infinite) sets unions. The reader may know that a complete
lattice is also co-complete: if we have all joins, then we also have all
meets. The reader should just note that there is no reason for the meets in
$\mathsf{Open}$ to coincide with the meets in $\mathit{pow}(\bm{\mathsf{P}})$,
i.e. for them to be sets intersections.

Every semitopology $(\bm{\mathsf{P}},\mathsf{Open})$ gives rise to a topology
just by closing opens under intersections. But, there is more to
semitopologies than being subbases for a corresponding topology, because:

We are explicitly interested in situations where intersections of open sets
need _not_ be open.

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 $\bm{\mathsf{P}}$ is infinite. See also the overview in
Subsection 12.1.

Semitopologies are not topologies. We take a moment to spell out one concrete
difference:

######  Lemma 2.1.2.

In topologies, if a point $p$ has a minimal open neighbourhood then it is
least. In semitopologies, a point may have multiple distinct minimal open
neighbourhoods.777We study minimal open neighbourhoods in detail, starting
from Definition 9.5.2.

###### Proof.

To see that in a topology every minimal open neighbourhood is least, just note
that if $p\in A$ and $p\in B$ then $p\in A\cap B$. So if $A$ and $B$ are two
minimal open neighbourhoods then $A\cap 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 $(\bm{\mathsf{P}},\mathsf{Open})$
defined as follows, as illustrated in Figure 1:

$\bm{\mathsf{P}}=\\{0,1,2\\}$

$\mathsf{Open}=\bigl{\\{}\varnothing,\ \\{0,1\\},\ \\{1,2\\},\
\\{0,1,2\\}\bigr{\\}}$ Note that $1$ has two minimal open neighbourhoods:
$\\{0,1\\}$ and $\\{1,2\\}$. ∎

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

####  2.1.2 Examples

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

######  Definition 2.1.3.

Call $(\bm{\mathsf{P}},\mathit{pow}(\bm{\mathsf{P}}))$ the discrete
semitopology on $\bm{\mathsf{P}}$.

We may call a set with the discrete semitopology a semitopology of values, and
when we do we will usually call it $\mathsf{Val}$. We may identify
$\mathsf{Val}$-the-set and $\mathsf{Val}$-the-discrete-semitopology; meaning
will always be clear.

When $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and $\mathsf{Val}$ is
a semitopology of values, we may call a function
$f:\bm{\mathsf{P}}\to\mathsf{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. 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(2.1.3)).

  2. 2.

The initial semitopology $(\varnothing,\\{\varnothing\\})$ and the final
semitopology $(\\{\ast\\},\\{\varnothing,\\{\ast\\}\\})$ are semitopologies.

  3. 3.

An important discrete semitopological space is

$\mathbb{B}=\\{\bot,\top\\}\quad\text{with the discrete
semitopology}\quad\mathsf{Open}(\mathbb{B})=\\{\varnothing,\\{\bot\\},\\{\top\\},\\{\bot,\top\\}\\}.$

We may silently treat $\mathbb{B}$ as a (discrete) semitopological space
henceforth.

  4. 4.

Take $\bm{\mathsf{P}}$ to be any nonempty set. Let the trivial semitopology on
$\bm{\mathsf{P}}$ have

$\mathsf{Open}=\\{\varnothing,\bm{\mathsf{P}}\\}.$

So (as usual) there are only two open sets: the one containing nothing, and
the one containing every point.

The only nonempty open is $\bm{\mathsf{P}}$ itself, reflecting a notion of
actionable coalition that requires unanimous agreement.

  5. 5.

Suppose $\bm{\mathsf{P}}$ is a set and
$\mathcal{F}\subseteq\mathit{pow}(\bm{\mathsf{P}})$ is nonempty and up-closed
(so if $P\in\mathcal{F}$ and $P\subseteq P^{\prime}\subseteq\bm{\mathsf{P}}$
then $P^{\prime}\in\mathcal{F}$, then $(\bm{\mathsf{P}},\mathcal{F})$ is a
semitopology. This is not necessarily a topology, because we do not insist
that $\mathcal{F}$ is a filter (i.e. is closed under intersections).

In particular:

    1. (a)

Take $\bm{\mathsf{P}}=\\{0,1,\dots,41\\}$. Let the supermajority semitopology
have

$\mathsf{Open}=\\{\varnothing\\}\cup\\{O\subseteq\bm{\mathsf{P}}\mid\mathit{cardinality}(O)\geq
28\\}.$

Since $\bm{\mathsf{P}}$ has 42 elements, $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.

    2. (b)

Take $\bm{\mathsf{P}}$ to be any nonempty set. Let the many semitopology have

$\mathsf{Open}=\\{\varnothing\\}\cup\\{O\subseteq\bm{\mathsf{P}}\mid\mathit{cardinality}(O)=\mathit{cardinality}(\bm{\mathsf{P}})\\}.$

For example, if $\bm{\mathsf{P}}=\mathbb{N}$ then open sets include
$\mathit{evens}=\\{2*n\mid n\in\mathbb{N}\\}$ and
$\mathit{odds}=\\{2*n{+}1\mid n\in\mathbb{N}\\}$.

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

    3. (c)

Take $\bm{\mathsf{P}}$ to be any nonempty set. Let the all-but-one
semitopology have

$\mathsf{Open}=\\{\varnothing,\
\bm{\mathsf{P}}\\}\cup\\{\bm{\mathsf{P}}\setminus\\{p\\}\mid
p\in\bm{\mathsf{P}}\\}.$

This semitopology is not a topology. See also Lemma 8.3.3.

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

    4. (d)

Take $\bm{\mathsf{P}}$ to be any set with cardinality at least $2$. Let the
more-than-one semitopology have

$\mathsf{Open}=\\{\varnothing\\}\cup\\{O\subseteq\bm{\mathsf{P}}\mid\mathit{cardinality}(O)\geq
2\\}.$

This semitopology is not a topology. See also Lemma 8.3.5.

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

Take $\bm{\mathsf{P}}=\mathbb{R}$ (the set of real numbers) and set
$O\subseteq\mathbb{R}$ to be open when it has 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. 7.

In [NW94] a notion of _quorum system_ is discussed, defined as any collection
of pairwise intersecting sets. Quorum systems are a field of study in their
own right, especially in the theory of concrete consensus algorithms.

Every quorum system gives rise naturally to a semitopology, just by closing
under arbitrary unions. We obtain what in this paper we would call an
_intertwined space_ (Notation 3.6.4; a semitopology all of whose nonempty open
sets intersect).888A topologist would call this a _hyperconnected space_ , but
be careful! There are multiple such notions in semitopologies, so intuitions
need not transfer over. See the discussion in Subsection 3.7.3.

Going in the other direction is interesting for a different reason, that it is
slightly less canonical: of course every intertwined space is already a quorum
system; but (for the finite case) we can also map to the set of all open
covers of all points (Definition 9.5.2(2); in the notation of that Definition,
we would write this as $\bigcup_{p\in\bm{\mathsf{P}}}\\{O\in\mathsf{Open}\mid
O\gtrdot p\\}$).

To give one specific example of a quorum system from [NW94], consider $n\times
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.

######  Remark 2.1.5 (Logical models of semitopologies).

One class of examples of semitopologies deserves its own discussion. Consider
an arbitrary logical system with predicates $\mathsf{Pred}$ and entailment
relation $\vdash$.999A validity relation $\vDash$ would also work. Call
$\Phi\subseteq\mathsf{Pred}$ deductively closed when $\Phi\vdash\phi$ implies
$\phi\in\Phi$. Then take

$\bm{\mathsf{P}}=\mathsf{Pred}$, and

let $O\in\mathsf{Open}$ be $\varnothing$ or the complement to a deductively
closed set $\Phi$, so $O=\mathsf{Pred}\setminus\Phi$. Note that an arbitrary
union of open sets is open (because an arbitrary intersection of deductively
closed sets is deductively closed), but an intersection of open sets need not
be open (because the union of deductively closed sets need not be deductively
closed). This is a semitopology.

This example will be important to us and we will return to it in Subsection
8.5.

We can note further that:

  1. 1.

There is a traditional, simple model of propositional logic whereby we let
propositions be denoted by open sets. Intuitively, these points are ‘worlds’
at which the proposition is ‘true’. The example of semitopologies given above
is _not_ this. For a start, in the model above propositions are points, not
sets of points.

  2. 2.

Variations on our model above are possible, all with a theme that associates
closed sets with consistency and deductive closure, and open sets with
inconsistency. For example:

  3. 3.

Call $\Phi\subseteq\mathsf{Pred}$ inconsistent when $\Phi\vdash$.

Then we can take $\bm{\mathsf{P}}=\mathsf{Pred}$, and we can let
$\mathsf{Open}$ be the set of inconsistent sets of predicates. Note that an
arbitrary union of inconsistent sets of predicates is inconsistent, but an
intersection of inconsistent sets of predicates need not be inconsistent.

  4. 4.

We can take open sets to be arbitrary unions of _minimal_ inconsistent sets of
predicates; then the previous notion of ‘open set’ can be recovered as ‘has a
nonempty open interior’.

  5. 5.

We can restrict $\bm{\mathsf{P}}$ to _atomic predicates_ (ones not created by
logical connectives or quantifiers, such as ${\boldsymbol{\wedge}}$,
${\boldsymbol{\Rightarrow}}$, or  $\forall$ ).101010In a proposition logic
these would be called _propositional constants_ , such as it is raining; in a
predicate logic these might thake the form of predicate-formers applied to
closed terms, such as mortal(Socrates) or perhaps 1+2=3.

####  2.1.3 Some discussion

######  Remark 2.1.6 (Why the name ‘semitopologies’).

When we give a name ‘semitopologies’ to things that are like topologies but
without intersections, this is a riff on

‘semilattices’, for things that are like lattices with joins but without meets
(or vice-versa), and

‘semigroups’, for things that are like groups but without inverses. But, this
terminology also reflects a real mathematical connection, because
semitopologies _are_ semilattices _are_ semigroups, in standard ways which we
take a moment to spell out:

A semitopology $(\bm{\mathsf{P}},\mathsf{Open})$ is a bounded join
subsemilattice of the powerset $\mathit{pow}(\bm{\mathsf{P}})$, by taking the
join ${\boldsymbol{\vee}}$ to be sets union $\cup$ and the bounds $\bot$ and
$\top$ to be $\varnothing$ and $\bm{\mathsf{P}}$ respectively.

A semilattice is an idempotent commutative monoid, which is an idempotent
commutative semigroup with an identity, by taking the multiplication $\circ$
to be ${\boldsymbol{\vee}}$ and the identity element to be $\bot$ ($\top$
becomes what is called a _zero_ or _absorbing_ element, such that $\top\circ
x=\top$ always).

Figure 2: Two nonidentical semitopologies (Remark 2.1.7)

######  Remark 2.1.7 (Semitopologies are not _just_ semilattices).

We noted in Remark 2.1.6 that every semitopology is a semilattice. This is
true, but the reader should not read this statement as reductive:
semitopologies are not _just_ semilattices.

To see why, consider the following two simple semitopologies, as illustrated
in Figure 2:

$(\bm{\mathsf{P}},\mathsf{Open})$ where $\bm{\mathsf{P}}=\\{0,1,2\\}$ and
$\mathsf{Open}=\bigl{\\{}\varnothing,\\{0,1\\},\\{1,2\\},\\{0,1,2\\}\bigr{\\}}$.

$(\bm{\mathsf{P}}^{\prime},\mathsf{Open}^{\prime})$ where
$\bm{\mathsf{P}}=\\{0,2\\}$ and
$\mathsf{Open}^{\prime}=\bigl{\\{}\varnothing,\\{0\\},\\{2\\},\\{0,2\\}\bigr{\\}}$.
Note that the semilattices of open sets $\mathsf{Open}$ and
$\mathsf{Open}^{\prime}$ are isomorphic — so, when viewed as semilattices
these two semitopologies are the same (up to isomorphism).

However, $(\bm{\mathsf{P}},\mathsf{Open})$ is not the same semitopology as
$(\bm{\mathsf{P}}^{\prime},\mathsf{Open}^{\prime})$. There is more than one
way to see this, but perhaps the simplest indication is that there is no
inverse pair of continuous injections
$f:(\bm{\mathsf{P}},\mathsf{Open})\to(\bm{\mathsf{P}}^{\prime},\mathsf{Open}^{\prime})$
and
$g:(\bm{\mathsf{P}}^{\prime},\mathsf{Open}^{\prime})\to(\bm{\mathsf{P}},\mathsf{Open})$
(we will define continuity in a moment in Definition 2.2.1(2) but is just as
for topologies, so we take the liberty of using it here). There are a limited
number of possibilities for $f$ and $g$, and we can just enumerate them and
check:

If $f(0)=0$ and $f(2)=2$ then there is no continuous inverse $g$: if $g(1)=0$
then $g^{\text{-}1}(\\{2\\})=\\{2\\}\not\in\mathsf{Open}$, and similarly if
$g(1)=1$ then $g^{\text{-}1}(\\{0\\})=\\{0\\}\not\in\mathsf{Open}$.

If $f(0)=0$ and $f(2)=1$ then there is still no continuous inverse $g$: if
$g(1)=0$ then $g^{\text{-}1}(\\{2\\})=\\{1\\}\not\in\mathsf{Open}$, and
similarly if $g(1)=2$ then
$g^{\text{-}1}(\\{0\\})=\\{0\\}\not\in\mathsf{Open}$.

Other possibilites are no harder.

######  Remark 2.1.8 (‘Stronger’ does not necessarily equal ‘better’).

We conclude with some easy predictions about the theory of semitopologies,
made just from general mathematical principles. Fewer axioms means:

_more_ models,

_finer discrimination_ between definitions, and

(because there are more models) _more counterexamples_. So we can expect a
theory with the look-and-feel of topology, but with new models, new
distinctions between definitions that in topology may be equivalent, and some
new definitions, theorems, and counterexamples — and this indeed will be the
case.

Note that fewer axioms does not necessarily mean fewer interesting things to
say and prove. On the contrary: if we can make finer distinctions, there may
also be more interesting things to prove; and furthermore, assumptions we make
can become _more_ impactful in a weaker system, because these assumptions may
exclude more models than would have been the case with more powerful axioms.
We see this e.g. in the theory of semigroups, which has its own character that
is quite distinct from the theory of groups.111111To take this to an extreme,
consider the _terminal_ theory, which has just one first-order axiom: $\exists
x.\forall y.x=y$. This theory ‘subsumes’ groups, lattices, graphs, and much
besides, in the sense that every model of the terminal theory _is_ a group, a
lattice, and a graph, in a natural way. However, the theory is so strong, and
the class of its models is so restricted — just the singleton model with one
element — that there is not much left to say about it. Additional assumptions
we may make on elements add literally nothing of value, because there was only
one element to begin with! So a ‘stronger’ set of axioms is not necessarily
‘better’, and conversely a ‘weaker’ set of axioms is not necessarily ‘less
useful’. It depends on what we want to do, and on how the maths turns out.

###  2.2 Continuity, and its interpretation

We can import the topological notion of continuity and it works fine in
semitopologies, and the fact that there are no surprises is a feature. In
Remark 2.2.5 we explain how these notions matter to us:

######  Definition 2.2.1.

We import standard topological notions of inverse image and continuity:

  1. 1.

Suppose $\bm{\mathsf{P}}$ and $\bm{\mathsf{P}}^{\prime}$ are any sets and
$f:\bm{\mathsf{P}}\to\bm{\mathsf{P}}^{\prime}$ is a function. Suppose
$O^{\prime}\subseteq\bm{\mathsf{P}}^{\prime}$. Then write
$f^{\text{-}1}(O^{\prime})$ for the inverse image or preimage of $O^{\prime}$,
defined by

$f^{\text{-}1}(O^{\prime})=\\{p{\in}\bm{\mathsf{P}}\mid f(p)\in
O^{\prime}\\}.$

  2. 2.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ and
$(\bm{\mathsf{P}}^{\prime},\mathsf{Open}^{\prime})$ are semitopological spaces
(Definition 1.1.2). Call a function
$f:\bm{\mathsf{P}}\to\bm{\mathsf{P}}^{\prime}$ continuous when the inverse
image of an open set is open. In symbols:

$\forall
O^{\prime}{\in}\mathsf{Open}^{\prime}.f^{\text{-}1}(O^{\prime})\in\mathsf{Open}.$

  3. 3.

Call a function $f:\bm{\mathsf{P}}\to\bm{\mathsf{P}}^{\prime}$ continuous at
$p\in\bm{\mathsf{P}}$ when

$\forall O^{\prime}{\in}\mathsf{Open}^{\prime}.f(p)\in
O^{\prime}\Longrightarrow\exists O_{p,O^{\prime}}{\in}\mathsf{Open}.p\in
O_{p,O^{\prime}}\land O_{p,O^{\prime}}\subseteq f^{\text{-}1}(O^{\prime}).$

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

Call a function $f:\bm{\mathsf{P}}\to\bm{\mathsf{P}}^{\prime}$ continuous on
$P\subseteq\bm{\mathsf{P}}$ when $f$ is continuous at every $p\in P$.

(It is routine to check that $f$ is continous on $\bm{\mathsf{P}}$ precisely
when it is continuous in the sense of part 2 of this Definition.)

######  Lemma 2.2.2.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ and
$(\bm{\mathsf{P}}^{\prime},\mathsf{Open}^{\prime})$ are semitopological spaces
(Definition 1.1.2) and suppose $f:\bm{\mathsf{P}}\to\bm{\mathsf{P}}^{\prime}$
is a function. Then the following are equivalent:

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

$f$ is continuous at every $p\in\bm{\mathsf{P}}$ (Definition 2.2.1(3)).

###### Proof.

The top-down implication is immediate, taking $O=f^{\text{-}1}(O^{\prime})$.

For the bottom-up implication, given $p$ and an open neighbourhood
$O^{\prime}\ni f(p)$, we write

$O=\bigcup\\{O_{p,O^{\prime}}\in\mathsf{Open}\mid p\in\bm{\mathsf{P}},\
f(p)\in O^{\prime}\\}.$

Above, $O_{p,O^{\prime}}$ is the open neighbourhood of $p$ in the preimage of
$O^{\prime}$, which we know exists by Definition 2.2.1(3).

It is routine to check that $O=f^{\text{-}1}(O^{\prime})$, and since this is a
union of open sets, it is open. ∎

######  Definition 2.2.3.

Suppose that:

$(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and

$\mathsf{Val}$ is a semitopology of values (Definition 2.1.3(2.1.3)) and

$f:\bm{\mathsf{P}}\to\mathsf{Val}$ is a value assignment (Definition
2.1.3(2.1.3); an assignment of a value to each element in $\bm{\mathsf{P}}$).
Then:

Call $f$ locally constant at $p\in\bm{\mathsf{P}}$ when there exists $p\in
O_{p}\in\mathsf{Open}$ such that $\forall
p^{\prime}{\in}O_{p}.f(p)=f(p^{\prime})$.

So $f$ is locally constant at $p$ when it is constant on some open
neighbourhood $O_{p}$ of $p$.

Call $f$ locally constant when it is locally constant at every
$p\in\bm{\mathsf{P}}$.

######  Lemma 2.2.4.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and $\mathsf{Val}$
is a semitopology of values and $f:\bm{\mathsf{P}}\to\mathsf{Val}$ is a value
assignment. Then the following are equivalent:

$f$ is locally constant / locally constant at $p\in\bm{\mathsf{P}}$
(Definition 2.2.3).

$f$ is continuous / continuous at $p\in\bm{\mathsf{P}}$ (Definition 2.2.1).

###### Proof.

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

  * •

Suppose $f$ is continuous, consider $p\in\bm{\mathsf{P}}$, and write $v=f(p)$.
By our assumptions we know that $f^{\text{-}1}(v)$ is open, and $p\in
f^{\text{-}1}(v)$. This is an open neighbourhood $O_{p}$ on which $f$ is
constant, so we are done.

  * •

Suppose $f$ is locally constant, consider $p\in\bm{\mathsf{P}}$, and write
$v=f(p)$. By assumption we can find $p\in O_{p}\in\mathsf{Open}$ on which $f$
is constant, so that $O_{p}\subseteq f^{\text{-}1}(v)$. ∎

######  Remark 2.2.5 (Continuity = distributed agreement).

Lemma 2.2.4 tells us that we can view the problem of attaining agreement
across an actionable coalition (as discussed in Subsection 1.1) as being the
same thing as computing a value assignment that is continuous on that
coalition (and possibly elsewhere).

To see why, consider a semitopology $(\bm{\mathsf{P}},\mathsf{Open})$ and
following the intuitions discussed in Subsection 1.1 view points
$p\in\bm{\mathsf{P}}$ as _participants_ ; and view open neighbourhoods $p\in
O\in\mathsf{Open}$ as actionable coalitions that include $p$. Then to say “$f$
is a value assignment that is continuous at $p$” is to say that:

$f$ assigns a value or belief to $p\in\bm{\mathsf{P}}$, and

$p$ is part of a (by Lemma 2.2.4 continuity) set of peers that agrees with $p$
and (being open) can progress to act on this agreement. Conceptually and
mathematically this reduces the general question

> _How can we model distributed collaborative action?_

(which, to be fair, has more than one possible answer!) to a more specific
research question

> _Understand continuous value assignments on semitopologies_.

The rest of this paper is devoted to elaborating (some of) a body of
mathematics that we can pull out of this idea.

###  2.3 Neighbourhoods of a point

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

######  Definition 2.3.1.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$p\in\bm{\mathsf{P}}$ and $O\in\mathsf{Open}$. Then call $O$ an open
neighbourhood of $p$ when $p\in O$.

In other words: an open set is (by definition) an _open neighbourhood_
precisely for the points that it contains.

######  Lemma 2.3.2.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and suppose
$P\subseteq\bm{\mathsf{P}}$ is any set of points. Then the following are
equivalent:

$P\in\mathsf{Open}$.

Every point $p$ in $P$ has an open neighbourhood in $P$. In symbols we can
write:

$\forall p{\in}P.\exists O{\in}\mathsf{Open}.(p\in O\land O\subseteq
P)\quad\text{if and only if}\quad P\in\mathsf{Open}$

###### Proof.

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

Conversely, if every $p\in P$ contains some open neighbourhood $p\in
O_{p}\subseteq P$ then $P=\bigcup\\{O_{p}\mid p\in P\\}$ and this is open by
condition 1.1.2 of Definition 1.1.2. ∎

######  Remark 2.3.3.

An initial inspiration for modelling distributed 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 [LGM19, Property 1]; the connection to topological ideas had not been
noticed in [LGM19].

##  3 Transitive sets and topens

###  3.1 Some background on sets intersection

Some notation will be convenient:

######  Notation 3.1.1.

Suppose $X$, $Y$, and $Z$ are sets.

Write

$X\between Y\quad\text{when}\quad X\cap Y\neq\varnothing.$

When $X\between Y$ holds then we say (as standard) that $X$ and $Y$ intersect.

We may chain the $\between$ notation, writing for example

$X\between Y\between Z\quad\text{for}\quad X\between Y\ \land\ Y\between Z$

We may write $X\mathbin{\cancel{\between}}Y$ for $\neg(X\between Y)$, thus
$X\mathbin{\cancel{\between}}Y$ when $X\cap Y=\varnothing$.

######  Remark 3.1.2.

_Note on design in Notation 3.1.1:_ It is uncontroversial that if
$X\neq\varnothing$ and $Y\neq\varnothing$ then $X\between Y$ should hold
precisely when $X\cap Y\neq\varnothing$.

But there is an edge case! What truth-value should $X\between Y$ return when
$X$ or $Y$ is empty?

It might be nice if $X\subseteq Y$ would imply $X\between Y$. This argues for
setting

$(X=\varnothing\lor Y=\varnothing)\Longrightarrow X\between Y.$

It might be nice if $X\between Y$ were monotone on both arguments (i.e. if
$X\between Y$ and $X\subseteq X^{\prime}$ then $X^{\prime}\between Y$). This
argues for setting

$(X=\varnothing\lor Y=\varnothing)\Longrightarrow
X\mathbin{\cancel{\between}}Y.$

It might be nice if $X\between X$ always — after all, should a set _not_
intersect itself? — and this argues for setting

$\varnothing\between\varnothing,$

even if we also set $\varnothing\mathbin{\cancel{\between}}Y$ for nonempty
$Y$. All three choices are defensible, and they are consistent with the
following nice property:

$X\between Y\Longrightarrow(X\between X\lor Y\between Y).$

We choose the second — if $X$ or $Y$ is empty then
$X\mathbin{\cancel{\between}}Y$ — because it gives the simplest definition
that $X\between Y$ precisely when $X\cap Y\neq\varnothing$.

We list some elementary properties of $\between$:

######  Lemma 3.1.3.

$X\between X$ if and only if $X\neq\varnothing$.

$X\between Y$ if and only if $Y\between X$.

$X\between(Y\cup Z)$ if and only if $(X\between Y)\lor(X\between Z)$.

If $X\subseteq X^{\prime}$ and $X\neq\varnothing$ then $X\between X^{\prime}$.

Suppose $X\between Y$. Then $X\subseteq X^{\prime}$ implies
$X^{\prime}\between Y$, and $Y\subseteq Y^{\prime}$ implies $X\between
Y^{\prime}$.

If $X\between Y$ then $X\neq\varnothing$ and $Y\neq\varnothing$.

###### Proof.

By facts of sets intersection. ∎

###  3.2 Transitive open sets and value assignments

######  Definition 3.2.1.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology. Suppose
$T\subseteq\bm{\mathsf{P}}$ is any set of points.

Call $T$ transitive when

$\forall O,O^{\prime}{\in}\mathsf{Open}.O\between T\between
O^{\prime}\Longrightarrow O\between O^{\prime}.$

Call $T$ topen when $T$ is nonempty transitive and open.121212The 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.

We may write

$\mathsf{Topen}=\\{T\in\mathsf{Open}\mid T\text{ is topen}\\}.$

Call $S$ a maximal topen when $S$ is a topen that is not a subset of any
strictly larger topen.131313‘Transitive open’ $\to$ ‘topen’, like ‘closed and
open’ $\to$ ‘clopen’.

######  Remark 3.2.2.

Notions of _strong_ transitivity and topen are in Definition 3.7.5.

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

######  Theorem 3.2.3.

Suppose that:

$(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology.

$\mathsf{Val}$ is a semitopology of values (a nonempty set with the discrete
semitopology; see Definition 2.1.3(1)).

$f:\bm{\mathsf{P}}\to\mathsf{Val}$ is a value assignment (Definition
2.1.3(2.1.3)).

$T\subseteq\bm{\mathsf{P}}$ is a transitive set (Definition 3.2.1) — in
particular this will hold if $T$ is topen — and $p,p^{\prime}\in T$. Then:

If $f$ is continuous at $p$ and $p^{\prime}$ then $f(p)=f(p^{\prime})$.

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^{\prime})$ for _any_
$p,p^{\prime}\in T$, then by definition $f$ is constant on $T$. So we now just
need to prove part 1 of this result.

Consider $p,p^{\prime}\in T$. By continuity on $T$, there exist open
neighbourhoods $p\in O\subseteq f^{\text{-}1}(f(p))$ and $p^{\prime}\in
O^{\prime}\subseteq f^{\text{-}1}(f(p^{\prime}))$. By construction $O\between
T\between O^{\prime}$ (because $p\in O\cap T$ and $p^{\prime}\in T\cap
O^{\prime}$). By transitivity of $T$ it follows that $O\between O^{\prime}$.
Thus, there exists $p^{\prime\prime}\in O\cap O^{\prime}$, and by construction
$f(p)=f(p^{\prime\prime})=f(p^{\prime})$. ∎

A notation will be useful:

######  Notation 3.2.4.

Suppose $\bm{\mathsf{X}}$ is a set and $f$ is some function on
$\bm{\mathsf{X}}$ and $X\subseteq\bm{\mathsf{X}}$. Suppose further that it is
known that $f$ is constant on $X$. In symbols:

$\exists c.\forall x{\in}X.f(x)=c.$

Then we may write $f(X)$ for the unique constant value that $f(x)$ takes as
$x$ ranges over $X$.141414We feel a bit guilty about this. A more principled
approach might be to define $f(X)=\\{f(x)\mid x\in X\\}$, and then write
$\\{c\\}$ for $f(X)$ where $f$ is known constant on $X$. The reader is welcome
to fill in the “$\exists c.\forall x{\in}X.f(x)=c\land\dots$” as appropriate.

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

######  Corollary 3.2.5.

Suppose that:

$(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology.

$f:\bm{\mathsf{P}}\to\mathsf{Val}$ is a value assignment to some set of values
$\mathsf{Val}$ (Definition 2.1.3).

$f$ is continuous on topen sets $T,T^{\prime}\in\mathsf{Topen}$. Then

$T\between T^{\prime}\quad\text{implies}\quad f(T)=f(T^{\prime}).$

###### Proof.

By Theorem 3.2.3 $f$ is constant on $T$ and $T^{\prime}$, so we can write
$f(T)$ and $f(T^{\prime})$ as per Notation 3.2.4. We assumed that $T$ and
$T^{\prime}$ intersect, and the result follows. ∎

A converse to Theorem 3.2.3 also holds:

######  Proposition 3.2.6.

Suppose that:

$(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology.

$\mathsf{Val}$ is a semitopology of values with at least two elements (to
exclude a denegerate case that no functions exist, or they exist but there is
only one because there is only one value to map to).

$T\subseteq\bm{\mathsf{P}}$ is any set. Then

_if_ for every $p,p^{\prime}\in T$ and every value assignment
$f:\bm{\mathsf{P}}\to\mathsf{Val}$, $f$ continuous at $p$ and $p^{\prime}$
implies $f(p)=f(p^{\prime})$,

_then_ $T$ is transitive.

###### Proof.

We prove the contrapositive. Suppose $T$ is not transitive, so there exist
$O,O^{\prime}\in\mathsf{Open}$ such that $O\between T\between O^{\prime}$ and
yet $O\cap O^{\prime}=\varnothing$. We choose two distinct values $v\neq
v^{\prime}\in\mathsf{Val}$ and define $f$ to map any point in $O$ to $v$ and
any point in $\bm{\mathsf{P}}\setminus O$ to $v^{\prime}$.

Choose some $p\in O$ and $p^{\prime}\in O^{\prime}$. It does not matter which,
and some such $p$ and $p^{\prime}$ exist, because $O$ and $O^{\prime}$ are
nonempty by Lemma 3.1.3(3.1.3), since $O\between T$ and $O^{\prime}\between
T$).

We note that $f(p)=v$ and $f(p^{\prime})=v^{\prime}$ and $f$ is continuous at
$p\in O$ and $p^{\prime}\in O^{\prime}\subseteq\bm{\mathsf{P}}\setminus O$,
yet $f(p)\neq f(p^{\prime})$. ∎

######  Remark 3.2.7.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and $\mathsf{Val}$
is a semitopology of values with at least two elements. Say that a value
assignment $f:\bm{\mathsf{P}}\to\mathsf{Val}$ splits a set
$T\subseteq\bm{\mathsf{P}}$ when there exist $p,p^{\prime}\in T$ such that $f$
is continuous at $p$ and $p^{\prime}$ and $f(p)\neq f(p^{\prime})$. Then
Theorem 3.2.3 and Proposition 3.2.6 together say in words that:

> $T\subseteq\bm{\mathsf{P}}$ is transitive if and only if it cannot be split
> by a value assignment.

Intuitively, transitive sets characterise areas of guaranteed agreement.

This reminds us of a basic result in topology about _connected spaces_ [Wil70,
section 26, Chapter 8]. Call a topology $(\bm{\mathsf{T}},\mathsf{Open})$
disconnected when there exist open sets $O,O^{\prime}\in\mathsf{Open}$ such
that $O\cap O^{\prime}=\varnothing$ (in our notation:
$O\mathbin{\cancel{\between}}O^{\prime}$) and $O\cup
O^{\prime}=\bm{\mathsf{T}}$; otherwise call $(\bm{\mathsf{T}},\mathsf{Open})$
connected. Then $(\bm{\mathsf{T}},\mathsf{Open})$ is disconnected if and only
if (in our terminology above) it can be split by a value assignment. Theorem
3.2.3 and Proposition 3.2.6 are not identical to that result, but they are in
the same spirit.

###  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 $(\bm{\mathsf{P}},\leq)$ is a poset. Then:

Call $p\in\bm{\mathsf{P}}$ maximal when $\forall
p^{\prime}.p{\leq}p^{\prime}\Longrightarrow p^{\prime}=p$ and minimal when
$\forall p^{\prime}.p^{\prime}{\leq}p\Longrightarrow p^{\prime}=p$.

Call $p\in\bm{\mathsf{P}}$ greatest when $\forall p.p^{\prime}\leq p$ and
least when $\forall p^{\prime}.p\leq p^{\prime}$.

######  Example 3.3.2 (Examples of transitive sets).

$\\{p\\}$ is transitive, for any single point $p\in\bm{\mathsf{P}}$.

The empty set $\varnothing$ is (trivially) transitive, but not topen because
we insist in Definition 3.2.1(3.2.1).

Call a set $P\subseteq\bm{\mathsf{P}}$ _topologically indistinguishable_ when
(using Notation 3.1.1) for every open set $O$,

$P\between O\Longleftrightarrow P\subseteq O.$

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

######  Example 3.3.3 (Examples of topens).

Take $\bm{\mathsf{P}}=\\{0,1,2\\}$, with open sets $\varnothing$,
$\bm{\mathsf{P}}$, $\\{0\\}$, $\\{2\\}$, and $\\{0,1,2\\}$. This has two
maximal topens $\\{0\\}$ and $\\{2\\}$, and an isolated point $1$, as
illustrated in Figure 3 (top-left diagram).

Take $\bm{\mathsf{P}}=\\{0,1,2\\}$, with open sets $\varnothing$,
$\bm{\mathsf{P}}$, $\\{0\\}$, $\\{0,1\\}$, $\\{2\\}$, $\\{1,2\\}$, and
$\\{0,2\\}$. This has two maximal topens $\\{0\\}$ and $\\{2\\}$, and an
isolated point $1$, as illustrated in Figure 3 (top-right diagram).

Take $\bm{\mathsf{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 $\\{2,3\\}$, and an isolated point $0$, as illustrated
in Figure 3 (lower-left diagram).

Take $\bm{\mathsf{P}}=\\{0,1,2,\ast\\}$, with open sets generated by
$\\{0\\}$, $\\{1\\}$, $\\{2\\}$, $\\{0,1,\ast\\}$, and $\\{1,2,\ast\\}$. This
has three maximal topens $\\{0\\}$, $\\{1\\}$, and $\\{2\\}$, and an isolated
point $\ast$, as illustrated in Figure 3 (lower-right diagram).

Take the all-but-one semitopology from Example 2.1.4(5c) on $\mathbb{N}$: so
$\bm{\mathsf{P}}=\mathbb{N}$ with opens $\varnothing$, $\mathbb{N}$, and
$\mathbb{N}\setminus\\{x\\}$ for every $x\in\mathbb{N}$. This has a single
maximal topen equal to $\mathbb{N}$ itself.

The semitopology in Figure 7 has no topen sets at all ($\varnothing$ is
transitive and open, but by definition in Definition 3.2.1(3.2.1) topens have
to be nonempty).

Figure 3: Examples of topens (Example 3.3.3)

######  Remark 3.3.4 (Discussion).

We take a moment for a high-level discussion of where we are going.

The semiopologies in Example 3.3.3 invite us to ask what makes these examples
different (especially parts 3.3.3 and 3.3.3). Clearly they are not equal, but
that is a superficial answer in the sense that it is valid just in the world
of sets, and it ignores semitopological structure.

For comparison: if we ask what makes $0$ and $1$ different in $\mathbb{N}$, we
could just to say that $0\neq 1$, but this ignores what makes them different
_as numbers_. For more insight, we could note that $0$ is the additive unit
whereas $1$ is the multiplicative unit of $\mathbb{N}$ as a semiring; or that
$0$ is a least element and $1$ is the unique atom of $\mathbb{N}$ as a well-
founded poset; or that $1$ is the successor of $0$ of $\mathbb{N}$ as a well-
founded inductive structure. Each of these answers gives us more
understanding, not only into $0$ and $1$ but also into the structures that can
be given to $\mathbb{N}$ itself.

So we can ask:

> _What semitopological property or properties on points can identify the
> essential nature of the differences between the semitopologies in Example
> 3.3.3?_

There would be some truth to saying that the rest of this paper is devoted to
developing different answers to this question! In particular, we will shortly
define the set of _intertwined points_ $p_{\between}$ in Definition 3.6.1.
Example 3.6.2 will note that $1_{\between}=\\{0,1,2\\}$ in Example
3.3.3(3.3.3), whereas $1_{\between}=\\{1\\}$ in Example 3.3.3(3.3.3), and
$x_{\between}=\mathbb{N}$ for every $x$ in Example 3.3.3(3).

###  3.4 Closure properties of transitive sets

######  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 — will 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^{\prime}$ is open. See Subsection 3.5.

######  Lemma 3.4.2.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$T\subseteq\bm{\mathsf{P}}$. Then:

If $T$ is transitive and $T^{\prime}\subseteq T$, then $T^{\prime}$ is
transitive.

If $T$ is topen and $\varnothing\neq T^{\prime}\subseteq T$ is nonempty and
open, then $T^{\prime}$ is topen.

###### Proof.

  1. 1.

By Definition 3.2.1 it suffices to consider open sets $O$ and $O^{\prime}$
such that $O\between T^{\prime}\between O^{\prime}$, and prove that $O\between
O^{\prime}$. But this is simple: by Lemma 3.1.3(5) $O\between T\between
O^{\prime}$, so $O\between O^{\prime}$ follows by transitivity of $T$.

  2. 2.

Direct from part 1 of this result and Definition 3.2.1(3.2.1). ∎

Lemmas 3.5.2 and 3.4.5 are required for, and extended by, Lemma 3.5.2:

######  Lemma 3.4.3.

Suppose that:

$(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology.

$T,T^{\prime}\subseteq\bm{\mathsf{P}}$ are transitive.

At least one of $T$ and $T^{\prime}$ is open. Then:

$\forall O,O^{\prime}\in\mathsf{Open}.O\between T\between T^{\prime}\between
O^{\prime}\Longrightarrow O\between O^{\prime}$.

If $T\between T^{\prime}$ then $T\cup T^{\prime}$ is transitive.

###### Proof.

  1. 1.

We simplify using Definition 3.2.1 and our assumption that one of $T$ and
$T^{\prime}$ is open. We consider the case that $T^{\prime}$ is open:

$\begin{array}[]{r@{\ }l@{\qquad}l}O\between T\between T^{\prime}\between
O^{\prime}\Longrightarrow&O\between T^{\prime}\between O^{\prime}&\text{$T$
transitive, $T^{\prime}$ open}\\\ \Longrightarrow&O\between
O^{\prime}&\text{$T^{\prime}$ transitive}.\end{array}$

The argument for when $T$ is open, is precisely similar.

  2. 2.

Suppose $O\between T\cup T^{\prime}\between O^{\prime}$. By Lemma 3.1.3(3.1.3)
(at least) one of the following four possibilities must hold:

$O\between T\land T\between O^{\prime},\quad O\between T^{\prime}\land
T\between O^{\prime},\quad O\between T\land T^{\prime}\between
O^{\prime},\quad\text{or}\quad O\between T^{\prime}\land T^{\prime}\between
O^{\prime}.$

If $O\between T\ \land\ T^{\prime}\between O^{\prime}$ then by part 1 of this
result we have $O\between O^{\prime}$ as required. The other possibilities are
no harder. ∎

######  Definition 3.4.4 (Ascending/descending chain).

A chain of sets $\mathcal{X}$ is a collection of sets that is totally ordered
by subset inclusion $\subseteq$.151515A total order is reflexive, transitive,
antisymmetric, and total.

We may call a chain ascending or descending if we want to emphasise that we
are thinking of the sets as ‘going up’ or ‘going down’.

######  Lemma 3.4.5.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and suppose
$\mathcal{T}$ is a chain of transitive sets. Then $\bigcup\mathcal{T}$ is a
transitive set.

###### Proof.

Suppose $O\between\bigcup\mathcal{T}\between O^{\prime}$. Then there exist
$T,T^{\prime}\in\mathcal{T}$ such that $O\between T$ and $T^{\prime}\between
O^{\prime}$. But $\mathcal{T}$ is totally ordered, so either $T\subseteq
T^{\prime}$ or $T\supseteq T^{\prime}$. In the former case it follows that
$O\between T^{\prime}\between O^{\prime}$ so that $O\between O^{\prime}$ by
transitivity of $T^{\prime}$; the latter case is precisely similar. ∎

###  3.5 Closure properties of topens

Definition 3.5.1 will be useful in Lemma 3.5.2(2):

######  Definition 3.5.1.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology. Call a nonempty
set of nonempty open sets
$\mathcal{O}\subseteq\mathsf{Open}_{\neq\varnothing}$ a clique when its
elements pairwise intersect.161616We call this a _clique_ , because if we form
the _intersection graph_ with nodes elements of $\mathcal{O}$ and with an
(undirected) edge between $O$ and $O^{\prime}$ when $O\between O^{\prime}$,
then $\mathcal{O}$ is a clique precisely when its intersection graph is indeed
a clique. We could also call $\mathcal{O}$ a _connected_ set of opens; this
terminology would evoke a concept from topology, which we will in fact use
later in Definition 3.7.12. In symbols:

$\mathcal{O}\subseteq\mathsf{Open}\ \text{is a
clique}\quad\text{when}\quad\forall O,O^{\prime}\in\mathcal{O}.O\between
O^{\prime}.$

Note that if $\mathcal{O}$ is a clique then every $O\in\mathcal{O}$ is
nonempty, since $\varnothing\between O$ is impossible (Notation 3.1.1).

######  Lemma 3.5.2.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology. Then:

If $T$ and $T^{\prime}$ are an intersecting pair of topens (i.e. $T\between
T^{\prime}$), then $T\cup T^{\prime}$ is topen.

If $\mathcal{T}$ is a clique of topens (Definition 3.5.1), then
$\bigcup\mathcal{T}$ is topen.

If $\mathcal{T}$ is a chain of topens then $\bigcup\mathcal{T}$ is topen.

###### Proof.

  1. 1.

$T\cup T^{\prime}$ is open because by Definition 1.1.2(1.1.2) open sets are
closed under arbitrary unions, and by Lemma 3.4.3(2) $T\cup T^{\prime}$ is
transitive.

  2. 2.

$\bigcup\mathcal{T}$ is open by Definition 1.1.2(1.1.2). Also, if
$O\between\bigcup\mathcal{T}\between O^{\prime}$ then there exist
$T,T^{\prime}\in\mathcal{T}$ such that $O\between T$ and $T^{\prime}\between
O^{\prime}$. We assumed $T\between T^{\prime}$, so by Lemma 3.4.3(1) (since
$T$ and $T^{\prime}$ are open) we have $O\between O^{\prime}$ as required.

  3. 3.

Any chain is pairwise intersecting. We use part 2 of this result.171717We
could also use Lemma 3.4.5. The reader might now ask why Lemma 3.4.5 was not
derived directly from Lemma 3.4.3(2); this is because (interestingly) Lemma
3.4.5 does not require openness. ∎

######  Corollary 3.5.3.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology. Then every topen
$T$ is contained in a unique maximal topen.

###### Proof.

Consider $\mathcal{T}$ defined by

$\mathcal{T}=\\{T\cup T^{\prime}\mid T^{\prime}\text{ topen}\land T\between
T^{\prime}\\}.$

By Lemma 3.5.2(2) this is a set of topens. By construction they all contain
$T$, and by our assumption that $T\neq\varnothing$ they pairwise intersect
(since they all contain $T$, at least). By Lemma 3.5.2(3) therefore,
$\bigcup\mathcal{T}$ is a transitive open set. It is easy to check that this
is the unique maximal transitive open set that contains $T$. ∎

######  Theorem 3.5.4.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology. Then any
$P\subseteq\bm{\mathsf{P}}$, and in particular $\bm{\mathsf{P}}$ itself, can
be partitioned into:

Some disjoint collection of maximal topens.

A set of other points, which are not contained in any topen. In Definition
4.1.4 we will call these points _irregular_. See also Corollary 4.3.3.

###### Proof.

Routine from Corollary 3.5.3. ∎

######  Remark 3.5.5.

It may be useful to put Theorem 3.5.4 in the context of the terminology,
results, and examples that will follow below. We will have Definition
4.1.4(4.1.4) and Theorem 4.2.6. These will allow us to call a point $p$
contained in some maximal topen $T$ _regular_ , and to call the maximal topen
$T$ of a regular point its _community_. Then Theorem 3.5.4 says that a
semitopology $\bm{\mathsf{P}}$ can be partitioned into:

Regular points, which partition into disjoint communities — each community is,
in a sense made formal in Theorem 3.2.3, a coalitions of strongly-correlated
regular points acting together — and

a set of irregular points, which have no commmunity and so are not members of
any such coalition. We give examples in Example 3.3.3 and Figure 3, and we
will see more elaborate examples below (see in particular the collection in
Example 5.6.10).

In the special case that the entire space consists of a single topen
community, there are no irregular points and all participants are guaranteed
to agree, where algorithms succeed. For the application of a single blockchain
trying to arrive at consensus, this discussion tells us that we want it to
consist, semitopologically, of a single topen.

###  3.6 Intertwined points

####  3.6.1 The basic definition, and some lemmas

######  Definition 3.6.1.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$p,p^{\prime}\in\bm{\mathsf{P}}$.

Call $p$ and $p^{\prime}$ intertwined when $\\{p,p^{\prime}\\}$ is transitive.
Unpacking Definition 3.2.1 this means:

$\forall O,O^{\prime}{\in}\mathsf{Open}.(p\in O\land p^{\prime}\in
O^{\prime})\Longrightarrow O\between O^{\prime}.$

By a mild abuse of notation, write

$p\mathrel{\between}p^{\prime}\quad\text{when}\quad\text{$p$ and $p^{\prime}$
are intertwined}.$

Define $p_{\between}$ (read ‘intertwined of $p$’) to be the set of points
intertwined with $p$. In symbols:

$p_{\between}=\\{p^{\prime}\in\bm{\mathsf{P}}\mid
p\mathrel{\between}p^{\prime}\\}.$

######  Example 3.6.2.

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

$1_{\between}=\\{0,1,2\\}$ and $0_{\between}=\\{0\\}$ and
$2_{\between}=\\{2\\}$.

$1_{\between}=\\{1\\}$ and $0_{\between}=\\{0\\}$ and $2_{\between}=\\{2\\}$.

$x_{\between}=\bm{\mathsf{P}}$ for every $x$.

It might be tempting to suppose that points being intertwined should be
transitive. Lemma 3.6.3 shows that this is not necessarily the case:

######  Lemma 3.6.3.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology. Then the ‘is
intertwined’ relation $\between$ is not necessarily transitive. That is:
$p\mathrel{\between}p^{\prime}\mathrel{\between}p^{\prime\prime}$ does not
necessarily imply $p\mathrel{\between}p^{\prime\prime}$.

###### Proof.

It suffices to provide a counterexample. The semitopology from Example
3.3.3(3.3.3) (illustrated in Figure 3, top-left diagram) will do. Take

$\bm{\mathsf{P}}=\\{0,1,2\\}\quad\text{and}\quad\mathsf{Open}=\\{\varnothing,\bm{\mathsf{P}},\\{0\\},\\{2\\}\\}.$

Then

$0\between 1\ \ \text{and}\ \ 1\between 2,\quad\text{but}\quad\neg(0\between
2).$

∎

There is more to be said about Lemma 3.6.3 but will need more machinery to
express it; we will pick up this thread again in Definition 6.1.1.

We conclude with an easy observation:

######  Notation 3.6.4.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology. Call
$\bm{\mathsf{P}}$ intertwined when

$\forall p,p^{\prime}\in\bm{\mathsf{P}}.p\mathrel{\between}p^{\prime}.$

In words: $\bm{\mathsf{P}}$ is intertwined when all of its points are pairwise
intertwined.

######  Lemma 3.6.5.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology. Then the
following conditions are equivalent:

$\bm{\mathsf{P}}$ is an intertwined space.

$\bm{\mathsf{P}}$ is a transitive set in the sense of Definition 3.2.1(3.2.1).

All nonempty open sets intersect.

###### Proof.

Routine by unpacking the definitions. ∎

######  Remark 3.6.6.

A topologist would call an intertwined space _hyperconnected_ (see Definition
3.7.12 and the following discussion). This is also — modulo closing under
arbitrary unions — what an expert in the classical theory of consensus might
call a _quorum system_ [NW94].

####  3.6.2 Pointwise characterisation of transitive sets

######  Lemma 3.6.7.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$T\subseteq\bm{\mathsf{P}}$. Then the following are equivalent:

$T$ is transitive.

$\\{p,p^{\prime}\\}$ is transitive for every $p,p^{\prime}\in T$.

$p\mathrel{\between}p^{\prime}$ for every $p,p^{\prime}\in T$.

###### Proof.

The equivalence of parts 2 and 3 above just restates Definition 3.6.1. We now
prove equivalence of parts 1 and 2.

  * •

_Suppose $T$ is transitive._

By Lemma 3.4.2(1), $\\{p,p^{\prime}\\}$ is transitive for every
$p,p^{\prime}\in T$.

  * •

_Suppose $\\{p,p^{\prime}\\}$ is transitive for every $p,p^{\prime}\in T$._

Consider open sets $O$ and $O^{\prime}$ such that $O\between T\between
O^{\prime}$. Choose $p\in O\cap T$ and $p^{\prime}\in O\cap T^{\prime}$. By
construction $\\{p,p^{\prime}\\}\subseteq T$ so this is transitive. It follows
that $O\between O^{\prime}$ as required. ∎

######  Theorem 3.6.8.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$T\subseteq\bm{\mathsf{P}}$. Then the following are equivalent:

$T$ is topen.

$T\in\mathsf{Open}_{\neq\varnothing}$ and $\forall
p,p^{\prime}{\in}T.p\mathrel{\between}p^{\prime}$. In words we can say:

> A topen is a nonempty open set of intertwined points.

###### Proof.

By Definition 3.2.1(3.2.1), $T$ is topen when it is nonempty, open, and
transitive. By Lemma 3.6.7 this last condition is equivalent to
$p\mathrel{\between}p^{\prime}$ for every $p,p^{\prime}\in T$. ∎

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

######  Corollary 3.6.9.

Suppose $\mathsf{Val}$ is a semitopology of values and
$f:\bm{\mathsf{P}}\to\mathsf{Val}$ is a value assignment (Definition 2.1.3)
and $p,p^{\prime}\in\bm{\mathsf{P}}$ and $p\between p^{\prime}$. Then if $f$
continuous at $p$ and $p^{\prime}$ then $f(p)=f(p^{\prime})$.

###### Proof.

$\\{p,p^{\prime}\\}$ is transitive by Theorem 3.6.8; we use Theorem 3.2.3. ∎

######  Remark 3.6.10 (Intertwined as ‘non-Hausdorff’).

Recall that we call a topological space $(\bm{\mathsf{P}},\mathsf{Open})$
Hausdorff (or $\mathbf{T_{2}}$) when any two points can be separated by
pairwise disjoint open sets. Using the $\between$ symbol from Notation 3.1.1,
we rephrase the Hausdorff condition as

$\forall p,p^{\prime}.p\neq p^{\prime}\Longrightarrow\exists
O,O^{\prime}.(p\in O\land p^{\prime}\in O^{\prime}\land\neg(O\between
O^{\prime})),$

and we can then simplify to this:

$\neg\exists p,p^{\prime}.p\neq p^{\prime}\land
p\mathrel{\between}p^{\prime}.$

Now note that the Hausdorff condition can be compactly written just as

$\forall p.p_{\between}=\\{p\\}.$ (1)

Note how distinct $p$ and $p^{\prime}$ being intertwined is the _opposite_ of
being Hausdorff: $p\mathrel{\between}p^{\prime}$ when $p^{\prime}\in
p_{\between}$, and they _cannot_ be separated by pairwise disjoint open sets.
Thus the assertion $p\mathrel{\between}p^{\prime}$ in Theorem 3.6.8 is a
negation to the Hausdorff property:

$\exists p.p_{\between}\neq\\{p\\}.$

This is useful because for semitopologies as applied to consensus,

being Hausdorff means that the space is separated (which is probably a bad
thing, if we are looking for a system with lots of points in consensus),
whereas

being full of intertwined points means by Theorem 3.2.3 that the system will
(where algorithms succeed) be full of points whose value assignment agrees
(which is a good thing). In the literature this might be called _avoiding
forking_.

###  3.7 Strong topens: topens that are also subspaces

####  3.7.1 Definition and main result

Let us take stock and recall that:

$T$ is _topen_ when it is a nonempty open transitive set (Definition 3.2.1).

$T$ is _transitive_ when $O\between T\between O^{\prime}$ implies $O\between
O^{\prime}$ for all $O,O^{\prime}\in\mathsf{Opens}$ (Definition 3.2.1).

$O\between O^{\prime}$ means that $O\cap O^{\prime}\neq\varnothing$ (Notation
3.1.1). But, note above that if $T$ is topen and $O\between T\between
O^{\prime}$ then $O\cap O^{\prime}$ need not intersect _inside $T$_. It could
be that $O$ and $O^{\prime}$ intersect outside of $T$ (an example is in the
proof Lemma 3.7.2 below).

Definition 3.7.1 spells out a standard topological construction in the
language of semitopologies:

######  Definition 3.7.1 (Subspaces).

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and suppose
$T\subseteq\bm{\mathsf{P}}$ is a set of points. Write $(T,\mathsf{Open}\cap
T)$ for the semitopology such that:

The points are $T$.

The open sets have the form $O\cap T$ for $O\in\mathsf{Open}$. We say that
$(T,\mathsf{Open}\cap T)$ is $T$ with the semitopology inherited from
$(\bm{\mathsf{P}},\mathsf{Open})$.

We may call $(T,\mathsf{Open}\cap T)$ a subspace of
$(\bm{\mathsf{P}},\mathsf{Open})$, and if the open sets are understood then we
may omit mention of them and just write:

> A subset $T\subseteq\bm{\mathsf{P}}$ is naturally a (semitopological)
> subspace of $\bm{\mathsf{P}}$.

(a) A topen that is not strong (Lemma 3.7.2) (b) A transitive set that is not
strongly transitive (Lemma 3.7.6(2))

Figure 4: Two counterexamples for (strong) transitivity

######  Lemma 3.7.2.

The property of being a (maximal) topen is not necessarily closed under taking
subspaces.

###### Proof.

It suffices to exhibit a semitopology $(\bm{\mathsf{P}},\mathsf{Open})$ and a
subset $S\subseteq\bm{\mathsf{P}}$ such that $S$ is topen in
$(\bm{\mathsf{P}},\mathsf{Open})$ but $S$ is not topen in
$(S,\mathsf{Open}\cap S)$. We set:

$\bm{\mathsf{P}}=\\{0,1,2\\}\qquad\mathsf{Open}=\\{\varnothing,\
\bm{\mathsf{P}},\ \\{0,2\\},\ \\{1,2\\},\ \\{0,1\\}\\}\qquad T=\\{0,1\\}$

as illustrated in Figure 4 (left-hand diagram). Now:

$T$ is topen in $(\bm{\mathsf{P}},\mathsf{Open})$, because every open
neighbourhood of $0$ — that is $\\{0,2\\}$, $\\{0,1\\}$, and $\bm{\mathsf{P}}$
— intersects with every open neighbourhood of $1$ — that is $\\{1,2\\}$,
$\\{0,1\\}$, and $\bm{\mathsf{P}}$.

$T$ is not topen in $(T,\mathsf{Open}\cap T)$, because $\\{0\\}$ is an open
neighbourhood of $0$ and $\\{1\\}$ is an open neighbourhood of $1$ and these
do not intersect. ∎

Lemma 3.7.2 motivates the following definitions:

######  Definition 3.7.3.

Suppose $X$, $Y$, and $Z$ are sets. Write $X\between_{Y}Z$, and say that $X$
and $Z$ meet or intersect in $Y$, when $(X\cap Y)\between(Z\cap Y)$.

######  Lemma 3.7.4.

Suppose $X$, $Y$, and $Z$ are sets. Then:

The following are equivalent:

$X\cap Y\cap Z\neq\varnothing\quad\Longleftrightarrow\quad
X\between_{Y}Z\quad\Longleftrightarrow\quad
Y\between_{X}Z\quad\Longleftrightarrow\quad X\between_{Z}Y.$

$X\between_{Y}Y$ if and only if $X\between Y$.

If $X\between_{Y}Z$ then $X\between Z$.

###### Proof.

From Definition 3.7.3, by elementary sets calculations. ∎

######  Definition 3.7.5.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and recall from
Definition 3.2.1 the notions of _transitive set_ and _topen_.

Call $T\subseteq\bm{\mathsf{P}}$ strongly transitive when

$\forall O,O^{\prime}{\in}\mathsf{Open}.O\between T\between
O^{\prime}\Longrightarrow O\between_{T}O^{\prime}.$

Call $T$ a strong topen when $T$ is nonempty open and strongly transitive,

######  Lemma 3.7.6.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$T\subseteq\bm{\mathsf{P}}$. Then:

If $T$ is strongly transitive then it is transitive.

The reverse implication need not hold (even if
$(\bm{\mathsf{P}},\mathsf{Open})$ is a topology): it is possible for $T$ to be
transitive but not strongly transitive.

###### Proof.

We consider each part in turn:

  1. 1.

Suppose $T$ is strongly transitive and suppose $O\between T\between
O^{\prime}$. By Lemma 3.7.4(2) $O\between_{T}T\between_{T}O^{\prime}$. By
strong transitivity $O\between_{T}O^{\prime}$. By Lemma 3.7.4(3) $O\between
O^{\prime}$. Thus $T$ is transitive.

  2. 2.

It suffices to provide a counterexample. This is illustrated in Figure 4
(right-hand diagram). We set:

  3. 3.

$\bm{\mathsf{P}}=\\{0,1,2\\}$, and

  4. 4.

$\mathsf{Open}=\\{\varnothing,\ \\{1\\},\ \\{0,1\\},\ \\{1,2\\},\
\\{0,1,2\\}\\}$.

  5. 5.

We set $T=\\{0,2\\}$. We note that $(\bm{\mathsf{P}},\mathsf{Open})$ is a
topology, and it is easy to check that $T$ is transitive — we just note that
$\\{0,1\\}\between T\between\\{1,2\\}$ and $\\{0,1\\}\between\\{1,2\\}$.
However, $T$ is not strongly transitive, because
$\\{0,1\\}\cap\\{1,2\\}=\\{1\\}\not\subseteq T$. ∎

######  Proposition 3.7.7.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and suppose
$T\in\mathsf{Open}$. Then the following are equivalent:

$T$ is a strong topen.

$T$ is a topen in $(T,\mathsf{Open}\cap T)$ (Definition 3.7.1).

###### Proof.

Suppose $T$ is a strong topen; thus $T$ is nonempty, open, and strongly
transitive in $(\bm{\mathsf{P}},\mathsf{Open})$. Then by construction $T$ is
open in $(T,\mathsf{Open}\cap T)$, and the strong transitivity property of
Definition 3.7.5 asserts precisely that $T$ is transitive as a subset of
$(T,\mathsf{Open}\cap T)$.

Now suppose $T$ is a topen in $(T,\mathsf{Open}\cap T)$; thus $T$ is nonempty,
open, and transitive in $(T,\mathsf{Open}\cap T)$. Then $T$ is nonempty and by
assumption above $T\in\mathsf{Open}$.181818It does not follow from $T$ being
open in $(T,\mathsf{Open}\cap T)$ that $T$ is open in
$(\bm{\mathsf{P}},\mathsf{Open})$, which is why we included an assumption that
this holds in the statement of the result. Now suppose
$O,O^{\prime}\in\mathsf{Open}$ and $O\between T\between O^{\prime}$. Then by
Lemma 3.7.4(2) $O\between_{T}T\between_{T}O^{\prime}$, so by transitivity of
$T$ in $(T,\mathsf{Open}\cap T)$ also $O\between_{T}O^{\prime}$, and thus by
Lemma 3.7.4(3) also $O\between O^{\prime}$. ∎

####  3.7.2 Connection to lattice theory

There is a notion from order-theory of a _join-irreducible_ element (see for
example in [DP02, Definition 2.42]), and a dual notion of _meet-irreducible_
element:

######  Definition 3.7.8.

Call an element $s$ in a lattice $\mathcal{L}$

join-irreducible when $x\vee y=s$ implies $x=s$ or $y=x$, and

meet-irreducible when $x\wedge y=s$ implies $x=s$ or $y=s$.

######  Example 3.7.9.

Consider the lattice of finite (possibly empty) subsets of $\mathbb{N}$, with
$\mathbb{N}$ adjoined as a top element. Then $\mathbb{N}$ is join-irreducible;
if $x\cup y=\mathbb{N}$ then either $x=\mathbb{N}$ or $y=\mathbb{N}$.

Consider $\mathbb{N}$ with the final segment semitopology such that opens are
either $\varnothing$ or sets $n_{\geq}=\\{n^{\prime}\in\mathbb{N}\mid
n^{\prime}\geq n\\}$.

Then $\varnothing$ is meet-irreducible; if $x\cap y=\varnothing$ then either
$x=\varnothing$ or $y=\varnothing$.

Consider the natural numbers with the lattice structure in which meet is
minimum and join is maximum. Then every element is join- and meet-irreducible;
if $x\vee y=z$ then $x=z$ or $y=z$, and similarly for $x\wedge y$. Thus we see
that irreducibility captures a notion that an element cannot be approached by
finitely many joins (or meets).

We spell out how this is relates to our notions of transitivity from
Definitions 3.2.1 and 3.7.5:

######  Lemma 3.7.10.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$T\subseteq\bm{\mathsf{P}}$. Then:

$T$ is strongly transitive if and only if $\varnothing$ is meet-irreducible in
$(T,\mathsf{Open}\cap T)$ (Definition 3.7.1).

$T$ is transitive if $\varnothing$ is meet-irreducible in
$(T,\mathsf{Open}\cap T)$.

If $T$ is transitive it does not necessarily follow that $\varnothing$ is
meet-irreducible in $(T,\mathsf{Open}\cap T)$.

###### Proof.

We are abusing terminology talking about meet-irreducibility in the set of
open sets $\\{O\cap T\mid O\in\mathsf{Open}\\}$ of the subspace
$(T,\mathsf{Open}\cap T)$, because this is not a lattice since $\mathsf{Open}$
is not closed under intersections in general.191919Unless
$(\bm{\mathsf{P}},\mathsf{Open})$ happens to be a topology and not just a
semitopology, of course. However, some meets may still exist and in particular
it makes sense to ask whether two elements have a sets intersection that is
equal to $\varnothing$, since $\varnothing$ is in $\\{O\cap T\mid
O\in\mathsf{Open}\\}$ — if this reader does not approve, they can call the
property ‘partial $\cap$-irreducibility’ instead of ‘meet-irreducibility’ and
no harm will come of it. We can now proceed to reason as follows:

  1. 1.

$\varnothing$ is meet-irreducible in $(T,\mathsf{Open}\cap T)$ means that
$(O\cap T)\cap(O^{\prime}\cap T)=\varnothing$ implies $O\cap T=\varnothing$ or
$O\cap T^{\prime}=\varnothing$.

$T$ is strongly transitive when (taking the contrapositive in Definition
3.7.5(1)) $(O\cap T)\cap(T\cap O^{\prime})=\varnothing$ implies $O\cap
T=\varnothing$ or $T\cap O^{\prime}=\varnothing$.

That these conditions are equivalent follows by straightforward sets
manipulations.

  2. 2.

We can use part 1 of this result and Lemma 3.7.6(1), or give a direct argument
by sets calculations: if $O\cap O^{\prime}=\varnothing$ then $(O\cap
T)\cap(T\cap O^{\prime})=\varnothing$ and by meet-irreducibility $O\cap
T=\varnothing$ or $T\cap O^{\prime}=\varnothing$ as required.

  3. 3.

Figure 4 (left-hand diagram) provides a counterexample, taking $T=\\{0,1\\}$
and $O=\\{0,2\\}$ and $O^{\prime}=\\{1,2\\}$. Then $(O\cap T)\cap(T\cap
O^{\prime})=\varnothing$ but it is not the case that $O\cap T=\varnothing$ or
$O^{\prime}\cap T=\varnothing$. ∎

######  Remark 3.7.11.

The proof of Lemma 3.7.10 not hard, but the result is interesting for what it
says, and also for what it does not say:

  1. 1.

The notion of being a strong topen maps naturally to something in order
theory; namely that $\varnothing$ is meet-irreducible in the induced poset
$\\{O\cap T\mid O\in\mathsf{Open}\\}$ which is the set of open sets of the
subspace $(T,\mathsf{Open}\cap T)$ of $(\bm{\mathsf{P}},\mathsf{Open})$.

  2. 2.

However, this mapping is imperfect: the poset is not a lattice, and it is also
not a sub-poset of $\mathsf{Open}$ — even if $T$ is topen. If $\mathsf{Open}$
were a topology and closed under intersections then we would have a lattice —
but it is precisely the point of difference between semitopologies vs.
topologies that open sets need not be closed under intersections.

  3. 3.

Being transitive does not correspond to meet-irreducibility; there is an
implication in one direction, but certainly not in the other.

So, Lemma 3.7.10 says that (strong) transitivity has a flavour of meet-
irreducibility, but in a way that also illustrates — as did Proposition
5.6.6(2) — how semitopologies are different, because they are not closed under
intersections, and have their own behaviour.

See also the characterisation of strong transitivity in Lemma 11.4.2 and the
surrounding discussion.

####  3.7.3 Topens in topologies

We conclude by briefly looking at what ‘being topen’ means if our semitopology
is actually a topology. We recall a standard definition from topology:

######  Definition 3.7.12.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology. Call
$T\subseteq\bm{\mathsf{P}}$ hyperconnected when all nonempty open subsets of
$T$ intersect.202020Calling this _hyperconnected_ is a slight abuse of
terminology: in topology, ‘hyperconnected’ is typically used to refer to an
entire space rather than an open subset of it. It would be more accurate to
call $T$ a _hyperconnected open subspace_. In symbols:

$\forall O,O^{\prime}\in\mathsf{Open}_{\neq\varnothing}.O,O^{\prime}\subseteq
T\Longrightarrow O\between O^{\prime}.$

######  Lemma 3.7.13.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$T\subseteq\bm{\mathsf{P}}$. Then:

If $T$ is transitive then it is hyperconnected.

The reverse implication need not hold; it is possible for $T$ to be
hyperconnected but not transitive, even if $(\bm{\mathsf{P}},\mathsf{Open})$
is a topology (not just a semitopology).

The reverse implication need not hold; it is possible for $T$ to be
hyperconnected but not transitive, even if $T$ is an open set.

###### Proof.

We consider each part in turn:

  1. 1.

Suppose $\varnothing\neq O,O^{\prime}\subseteq T$. Then $O\between T\between
O^{\prime}$ and by transitivity $O\between O^{\prime}$ as required.

  2. 2.

It suffices to provide a counterexample. Consider the semitopology illustrated
in the lower-left diagram in Figure 3 (which is a topology), and set
$T=\\{0,4\\}$. This has no nonempty open subsets so it is trivially
hyperconnected. However, $T$ is not transitive because $\\{0,1\\}\between
T\between\\{3,4\\}$ yet $\\{0,1\\}\mathbin{\cancel{\between}}\\{3,4\\}$.

  3. 3.

It suffices to provide a counterexample. Consider the semitopology illustrated
in the top-right diagram in Figure 3, and set $T=\\{0,1\\}$. This has two
nonempty open subsets, $\\{0\\}$ and $\\{0,1\\}$, so it is hyperconnected.
However, $T$ is not transitive, because $\\{0\\}\between T\between\\{1,2\\}$
yet $\\{0\\}\mathbin{\cancel{\between}}\\{1,2\\}$. ∎

We know from Lemma 3.7.6(2) that ‘transitive’ does not imply ‘strongly
transitive’ for an arbitrary subset $T\subseteq\bm{\mathsf{P}}$, even in a
topology. When read together with Lemma 3.7.13, this invites the question of
what happens when

$(\bm{\mathsf{P}},\mathsf{Open})$ is a topology, and _also_

$T$ is an open set. In this natural special case, strong transitivity,
transitivity, and being hyperconnected, all become equivalent:

######  Lemma 3.7.14.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a topology and suppose
$T\in\mathsf{Open}$ is an open set. Then the following are equivalent:

$T$ is a strong topen (Definition 3.7.5(3.7.5)).

$T$ is a topen.

$T$ is hyperconnected.

###### Proof.

We assumed $T$ is open, so the equivalence above can also be thought of as

> strongly transitive $\Longleftrightarrow$ transitive $\Longleftrightarrow$
> all nonempty open subsets intersect.

We prove a chain of implications:

  * •

If $T$ is a strong topen then it is a topen by Lemma 3.7.6(1).

  * •

If $T$ is a topen then we use Lemma 3.7.13(1).

  * •

Suppose $T$ is hyperconnected, so every pair of nonempty open subsets of $T$
intersect; and suppose $O,O^{\prime}\in\mathsf{Open}_{\neq\varnothing}$ and
$O\between T\between O^{\prime}$. Then also $(O\cap T)\between
T\between(O^{\prime}\cap T)$. Now $O\cap T$ and $O^{\prime}\cap T$ are open:
because $T$ is open; and $\bm{\mathsf{P}}$ is a topology (not just a
semitopology), so intersections of open sets are open. By transitivity of $T$
we have $O\cap T\between O^{\prime}\cap T$. Since $O$ and $O^{\prime}$ were
arbitrary, $T$ is strongly transitive. ∎

##  4 Open interiors, communities, and regular points

###  4.1 Community of a (regular) point

Definition 4.1.1 is standard:

######  Definition 4.1.1 (Open interior).

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$P\subseteq\bm{\mathsf{P}}$. Define $\mathit{interior}(P)$ the interior of $P$
by

$\mathit{interior}(P)=\bigcup\\{O\in\mathsf{Open}\mid O\subseteq P\\}.$

######  Lemma 4.1.2.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$P\subseteq\bm{\mathsf{P}}$. Then $\mathit{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.1.2(1.1.2)). ∎

######  Corollary 4.1.3.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$P,P^{\prime}\subseteq\bm{\mathsf{P}}$. Then if $P\subseteq P^{\prime}$ then
$\mathit{interior}(P)\subseteq\mathit{interior}(P^{\prime})$.

###### Proof.

Routine using Lemma 4.1.2. ∎

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

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$p\in\bm{\mathsf{P}}$. Then:

Define $\mathit{K}(p)$ the community of $p$ by

$\mathit{K}(p)=\mathit{interior}(p_{\between}).$

Extend $\mathit{K}$ to subsets $P\subseteq\bm{\mathsf{P}}$ by taking a sets
union:

$\mathit{K}(P)=\bigcup\\{\mathit{K}(p)\mid p\in P\\}.$

Call $p$ regular when its community is a topen neighbourhood of $p$. In
symbols:

$p\text{ is regular}\quad\text{when}\quad p\in\mathit{K}(p)\in\mathsf{Topen}.$

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

$p\text{ is weakly regular}\quad\text{when}\quad
p\in\mathit{K}(p)\in\mathsf{Open}.$

Call $p$ quasiregular when its community is nonempty. In symbols:

$p\text{ is
quasiregular}\quad\text{when}\quad\varnothing\neq\mathit{K}(p)\in\mathsf{Open}.$

If $p$ is not regular then we may call it irregular or just not regular.

If $P\subseteq\bm{\mathsf{P}}$ and every $p\in P$ is regular/weakly
regular/quasiregular/irregular then we may call $P$ regular/weakly
regular/quasiregular/irregular respectively (see also Definition 6.1.1(2)).

######  Remark 4.1.5.

Note of Definition 4.1.4(4.1.4) that $\mathit{K}(p)$ the community of $p$ is
always an open set by Lemma 4.1.2, however:

$\mathit{K}(p)$ might be empty: see any $x\in\mathbb{R}$ in Example 4.4.1(1).
If the community is not empty, then $p$ is quasiregular.

$\mathit{K}(p)$ need not contain $p$: see point $0$ in Example 4.4.1(13). If
the community does contain $p$ then $p$ is weakly regular.

$\mathit{K}(p)$ need not be topen: see point $1$ in Example 4.4.1(2). If the
community is topen and it contains $p$, then $p$ is regular.

######  Remark 4.1.6.

Our development will mostly be concerned with regular and weakly regular
points. The property of being quasiregular is also interesting and will also
turn up, though less often.

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

######  Lemma 4.1.7.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$p\in\bm{\mathsf{P}}$. Then:

If $p$ is regular, then $p$ is weakly regular.

If $p$ is weakly regular, then $p$ is quasiregular.

The converse implications need not hold (we sharpen this result in Theorem
6.2.2).

Furthermore, it is possible for a point $p$ to not be quasiregular.

###### Proof.

We consider each part in turn:

  1. 1.

If $p$ is regular then by Definition 4.1.4(4.1.4)
$p\in\mathit{K}(p)\in\mathsf{Topen}$, so certainly $p\in\mathit{K}(p)$ and by
Definition 4.1.4(4.1.4) $p$ is weakly regular.

  2. 2.

If $p$ is weakly regular then by Definition 4.1.4(4.1.4)
$p\in\mathit{K}(p)\in\mathsf{Open}$, so certainly
$\mathit{K}(p)\neq\varnothing$ and by Definition 4.1.4(4.1.4) $p$ is
quasiregular.

  3. 3.

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

  4. 4.

Point $1$ in Example 4.1.8(4.1.8) (illustrated in Figure 3, top-left diagram)
is weakly regular ($\mathit{K}(1)=\\{0,1,2\\}$) but not regular
($\mathit{K}(1)$ is open but not topen).

  5. 5.

Point $\ast$ in Example 4.1.8(4.1.8) (illustrated in Figure 3, lower-right
diagram) is quasiregular ($\mathit{K}(\ast)=\\{1\\}$ is nonempty but does not
contain $\ast$).

  6. 6.

To see that $p$ may not even be quasiregular, take
$\bm{\mathsf{P}}=\mathbb{R}$ (real numbers), with its usual topology (which is
also a semitopology). Then $x_{\between}=\\{x\\}$ and
$\mathit{K}(x)=\varnothing$ for every $x\in\mathbb{R}$. More on this in
Example 4.4.1(1) and the surrounding discussion. ∎

######  Example 4.1.8.

In Figure 4 (left-hand 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\\}$.

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

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

In Figure 3 (top-right diagram), $0$ and $2$ are regular and $1$ is neither
regular, weakly regular, nor quasiregular ($\mathit{K}(1)=\varnothing$).

In a semitopology of values $(\mathsf{Val},\mathit{pow}(\mathsf{Val}))$
(Definition 2.1.3) every value $v\in\mathsf{Val}$ is regular, weakly regular,
and unconflicted.

In $\mathbb{R}$ with its usual topology every point is unconflicted because
the topology is Hausdorff and by Equation 1 in Remark 3.6.10 this means
precisely that $p_{\between}=\\{p\\}$ so that is intertwined just with itself;
and every point is not weakly regular because
$\mathit{K}(p)=\mathit{interior}(p_{\between})=\varnothing$.

######  Example 4.1.9.

When we started looking at semitopologies we gave some examples in Example
2.1.4. These may seem quite elementary now, but we run through them commenting
on which spaces are regular, weakly regular, or quasiregular:

  1. 1.

The initial semitopology is regular: it has no topen neighbourhoods, but also
no points. The final semitopology is regular: it has one topen neighbourhood,
containing one point.

  2. 2.

$\mathbb{B}$ with the discrete semitopology, is regular. It has two topen
neighbourhoods: $\\{{\boldsymbol{\bot}}\\}$ and $\\{{\boldsymbol{\top}}\\}$.

  3. 3.

The trivial topology is regular; it has a single topen neighbourhood that is
$\bm{\mathsf{P}}$ itself.

  4. 4.

The supermajority semitopology is regular. It has one topen neighbourhood
containing all of $\bm{\mathsf{P}}$.

  5. 5.

The many semitopology is regular if $\bm{\mathsf{P}}$ is finite (because it is
equal to the trivial semitopology), and not even quasiregular if
$\bm{\mathsf{P}}$ is finite, because (for infinite $\bm{\mathsf{P}}$)
$p_{\between}=\varnothing$ for every point. For example, if
$\bm{\mathsf{P}}=\mathbb{N}$ and $p$ is even and $p^{\prime}$ is odd, then
$\mathit{evens}=\\{2*n\mid n\in\mathbb{N}\\}$ and
$\mathit{odds}=\\{2*n{+}1\mid n\in\mathbb{N}\\}$ are disjoint open
neighbourhoods of $p$ and $p^{\prime}$ respectively.

  6. 6.

The all-but-one semitopology is regular for $\bm{\mathsf{P}}$ having
cardinality of $3$ or more, since all points are intertwined so there is a
single topen neighbourhood which is the whole space. If $\bm{\mathsf{P}}$ has
cardinality $2$ or $1$ then we have a discrete semitopology (on two points or
one point) and these too are regular, with two or one topen neighbourhoods.

  7. 7.

The more-than-one semitopology is not even quasiregular for $\bm{\mathsf{P}}$
having cardinality of $4$ or more. If $\bm{\mathsf{P}}$ has cardinality $3$
then we get the left-hand topology in Figure 4, which is regular. If
$\bm{\mathsf{P}}$ has cardinality $2$ then we get the trivial semitopology,
which is regular.

  8. 8.

Take $\bm{\mathsf{P}}=\mathbb{R}$ (the set of real numbers) and set
$O\subseteq\mathbb{R}$ to be open when it has the form $[0,r)$ or $(-r,0]$ for
any strictly positive real number $r>0$. The reader can check that this
semitopology is regular.

  9. 9.

For the automaton example we cannot comment, because it depends on the
automaton.

######  Remark 4.1.10.

Definition 4.1.4 is a key definition and we pause to discuss it:

  1. 1.

We can ask:

  2. 2.

It it always the case that the community of $p$ exists? _(Yes)_

  3. 3.

Is the community of $p$ always open? _(Yes)_

  4. 4.

Is it always topen? _(No)_

  5. 5.

Is it always an open (or a topen) neighbourhood for $p$? _(No)_

  6. 6.

Is it always nonempty? _(No)_ A wealth of behaviour is possible and is
explored below, including in Lemma 4.2.3 and in the examples in Subsection
4.4.

  7. 7.

Why is it interesting to consider $p$ such that $p\in\mathit{K}(p)$? Clearly
calling $p$ ‘regular’ suggests that non-regular behaviour is ‘bad’, and
regular behaviour is ‘good’. But what is this good behaviour that regularity
implies? Theorem 3.2.3 (continuous value assignments are constant on topens)
tells us that a regular $p$ is surrounded by a topen neighbourhood of points
$\mathit{K}(p)=\mathit{interior}(p_{\between})$ that must agree with it under
continuous value assignments. Using our terminology _community_ and _regular_
, we can says that _the community of a regular $p$ shares its values_.

  8. 8.

We can sum up the above intuitively as follows:

  9. 9.

We care about transitivity because it implies agreement.

  10. 10.

We care about being open, because it implies actionability.

  11. 11.

Thus, a regular point is interesting because it is a participant in a maximal
topen neighbourhood and therefore can _i)_ come to agreement and _ii)_ take
action on that agreement.

  12. 12.

A mathematical question then arises: how can the community of $p$ can be
(semi)topologically characterised? We will explore this theme, notably in
Theorem 4.2.6, Proposition 5.4.9, and Theorem 5.6.2; see also Remark 5.6.1.

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

######  Remark 4.2.1.

Recall three common separation axioms from topology:

$T_{0}$: if $p_{1}\neq p_{2}$ then there exists some $O\in\mathsf{Open}$ such
that $(p_{1}\in O)\mathbin{\mathsf{\small xor}}(p_{2}\in O)$, where
$\mathbin{\mathsf{\small xor}}$ denotes _exclusive or_.

$T_{1}$: if $p_{1}\neq p_{2}$ then there exist $O_{1},O_{2}\in\mathsf{Open}$
such that $p_{i}\in O_{j}\Longleftrightarrow i=j$ for $i,j\in\\{1,2\\}$.

$T_{2}$, or the _Hausdorff condition_ : if $p_{1}\neq p_{2}$ then there exist
$O_{1},O_{2}\in\mathsf{Open}$ such that $p_{i}\in O_{j}\Longleftrightarrow
i=j$ for $i,j\in\\{1,2\\}$, and $O_{1}\cap O_{2}=\varnothing$. Cf. the
discussion in Remark 3.6.10. 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/$T_{2}$ (though
not to being $T_{1}$), as Lemma 4.2.2 makes formal.

######  Lemma 4.2.2.

Every quasiregular Hausdorff semitopology is discrete.

In more detail: if $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology that is
quasiregular (Definition 4.1.4(4.1.4)) and Hausdorff (equation 1 in Remark
3.6.10), then $\mathsf{Open}=\mathit{pow}(\bm{\mathsf{P}})$.

There exists a (quasi)regular $T_{1}$ semitopology that is not discrete.

###### Proof.

We consider each part in turn:

  1. 1.

By the Hausdorff property, $p_{\between}=\\{p\\}$. By the quasiregularity
property, $\mathit{K}(p)\neq\varnothing$. It follows that
$\mathit{K}(p)=\\{p\\}$. But by construction in Definition 4.1.4(4.1.4),
$\mathit{K}(p)$ is an open interior. Thus $\\{p\\}\in\mathsf{Open}$. The
result follows.

  2. 2.

It suffices to provide an example. We use the left-hand semitopology in Figure
4. Thus $\bm{\mathsf{P}}=\\{0,1,2\\}$ and $\mathsf{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 $T_{1}$. ∎

Lemma 4.2.3 confirms in a different way that regularity (Definition
4.1.4(4.1.4)) is non-trivially distinct from weak regularity and
quasiregularity:

######  Lemma 4.2.3.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$p\in\bm{\mathsf{P}}$. Then:

$\mathit{K}(p)\in\mathsf{Open}$.

$\mathit{K}(p)$ is not necessarily topen; equivalently $\mathit{K}(p)$ is not
necessarily transitive. (More on this later in Subsection 4.4.)

###### Proof.

$\mathit{K}(p)$ is open by construction in Definition 4.1.4(4.1.4), since it
is an open interior.

For part 2, it suffices to provide a counterexample. We consider the
semitopology from Example 3.3.3(3.3.3) (illustrated in Figure 3, top-left
diagram). We calculate that $\mathit{K}(1)=\\{0,1,2\\}$ so that
$\mathit{K}(1)$ is an open neighbourhood of $1$ — but it is not transitive,
and thus not topen, since $\\{0\\}\cap\\{2\\}=\varnothing$.

Further checking reveals that $\\{0\\}$ and $\\{2\\}$ are two maximal topens
within $\mathit{K}(1)$. ∎

So what is $\mathit{K}(p)$? We start by characterising $\mathit{K}(p)$ as the
_greatest_ topen neighbourhood of $p$, if this exists:

######  Lemma 4.2.4.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and recall from
Definition 4.1.4(4.1.4) that $p$ is regular when $\mathit{K}(p)$ is a topen
neighbourhood of $p$.

If $\mathit{K}(p)$ is a topen neighbourhood of $p$ (i.e. if $p$ is regular)
then $\mathit{K}(p)$ is a maximal topen.

If $p\in T\in\mathsf{Topen}$ is a maximal topen neighbourhood of $p$ then
$T=\mathit{K}(p)$.

###### Proof.

  1. 1.

Since $p$ is regular, by definition, $\mathit{K}(p)$ is topen and is a
neighbourhood of $p$. It remains to show that $\mathit{K}(p)$ is a maximal
topen.

Suppose $T$ is a topen neighbourhood of $p$; we wish to prove
$T\subseteq\mathit{K}(p)=\mathit{interior}(p_{\between})$. Since $T$ is open
it would suffice to show that $T\subseteq p_{\between}$. By Theorem 3.6.8
$p\mathrel{\between}p^{\prime}$ for every $p^{\prime}\in T$, and it follows
immediately that $T\subseteq p_{\between}$.

  2. 2.

Suppose $T$ is a maximal topen neighbourhood of $p$.

First, note that $T$ is open, and by Theorem 3.6.8 $T\subseteq p_{\between}$,
so $T\subseteq\mathit{K}(p)$.

Now consider any open $O\subseteq p_{\between}$. Note that $T\cup O$ is an
open subset of $p_{\between}$, so by Theorem 3.6.8 $T\cup O$ is topen, and by
maximality $T\cup O\subseteq T$ and thus $O\subseteq T$. It follows that
$\mathit{K}(p)\subseteq T$. ∎

######  Remark 4.2.5.

We can use Lemma 4.2.4 to characterise regularity in five equivalent ways: see
Theorem 4.2.6 and Corollary 4.2.8. Other characterisations will follow but
will require additional machinery to state (the notion of _closed
neighbourhood_ ; see Definition 5.4.1). See Corollary 5.4.12 and Theorem 5.6.2
.

######  Theorem 4.2.6.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$p\in\bm{\mathsf{P}}$. Then the following are equivalent:

$p$ is regular, or in full: $p\in\mathit{K}(p)\in\mathsf{Topen}$.

$\mathit{K}(p)$ is a greatest topen neighbourhood of $p$.

$\mathit{K}(p)$ is a maximal topen neighbourhood of $p$.

$p$ has a maximal topen neighbourhood.

$p$ has some topen neighbourhood.

###### Proof.

We prove a cycle of implications:

  1. 1.

If $\mathit{K}(p)$ is a topen neighbourhood of $p$ then it is maximal by Lemma
4.2.4(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 Lemma 3.5.2(3.5.2) (union of
intersecting topens is topen).

  2. 2.

If $p_{\between}$ is a greatest topen neighbourhood of $p$, then certainly it
is a maximal topen neighbourhood of $p$.

  3. 3.

If $p_{\between}$ is a maximal topen neighbourhood of $p$, then certainly $p$
has a maximal topen neighbourhood.

  4. 4.

If $p$ has a maximal topen neighbourhood then certainly $p$ has a topen
neighbourhood.

  5. 5.

Suppose $p$ has a topen neighbourhood $T$. By Corollary 3.5.3 we may assume
without loss of generality that $T$ is a maximal topen. We use Lemma 4.2.4(2).
∎

Theorem 4.2.6 has numerous corollaries:

######  Corollary 4.2.7.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$p\in\bm{\mathsf{P}}$ and $\\{p\\}\in\mathsf{Open}$. Then $p$ is regular.

###### Proof.

We noted in Example 3.3.2(3.3.2) that a singleton $\\{p\\}$ is always
transitive, so if $\\{p\\}$ is also open, then it is topen, so that $p$ has a
topen neighbourhood and by Theorem 4.2.6(4.2.6) $p$ is topen.212121It does not
follow from $p\in\\{p\\}\in\mathsf{Topen}$ that $\mathit{K}(p)=\\{p\\}$:
consider $\bm{\mathsf{P}}=\\{0,1\\}$ and
$\mathsf{Open}=\\{\varnothing,\\{0\\},\\{0,1\\}\\}$ and $p=0$; then
$\\{p\\}\in\mathsf{Topen}$ yet $\mathit{K}(p)=\\{0,1\\}$. ∎

######  Corollary 4.2.8.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$p\in\bm{\mathsf{P}}$. Then the following are equivalent:

$p$ is regular.

$p$ is weakly regular and $\mathit{K}(p)=\mathit{K}(p^{\prime})$ for every
$p^{\prime}\in\mathit{K}(p)$. It might be useful to look at Example
3.3.3(3.3.3) and Figure 3 (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.6:

  * •

Suppose $p$ is regular. By Lemma 4.1.7(4.1.7) $p$ is weakly regular. Now
consider $p^{\prime}\in\mathit{K}(p)$. By Theorem 4.2.6 $\mathit{K}(p)$ is
topen, so it is a topen neighbourhood of $p^{\prime}$. By Theorem 4.2.6
$\mathit{K}(p^{\prime})$ is a greatest topen neighbourhood of $p^{\prime}$.
But by Theorem 4.2.6 $\mathit{K}(p)$ is also a greatest topen neighbourhood of
$p$, and $\mathit{K}(p)\between\mathit{K}(p^{\prime})$ since they both contain
$p^{\prime}$. By Lemma 3.5.2(3.5.2) and maximality, they are equal.

  * •

Suppose $p$ is weakly regular and suppose
$\mathit{K}(p)=\mathit{K}(p^{\prime})$ for every $p^{\prime}\in\mathit{K}(p)$,
and consider $p^{\prime},p^{\prime\prime}\in\mathit{K}(p)$. Then
$p^{\prime}\mathrel{\between}p^{\prime\prime}$ holds, since
$p^{\prime\prime}\in\mathit{K}(p^{\prime})=\mathit{K}(p)$. By Theorem 3.6.8
$\mathit{K}(p)$ is topen, and by weak regularity $p\in\mathit{K}(p)$, so by
Theorem 4.2.6 $p$ is regular as required. ∎

######  Corollary 4.2.9.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$p,p^{\prime}\in\bm{\mathsf{P}}$. Then if $p$ is regular and
$p^{\prime}\in\mathit{K}(p)$ then $p^{\prime}$ is regular and has the same
community.

###### Proof.

Suppose $p$ is regular — so by Definition 4.1.4(4.1.4)
$p\in\mathit{K}(p)\in\mathsf{Topen}$ — and suppose
$p^{\prime}\in\mathit{K}(p)$. Then by Corollary 4.2.8
$\mathit{K}(p)=\mathit{K}(p^{\prime})$, so
$p^{\prime}\in\mathit{K}(p^{\prime})\in\mathsf{Topen}$ and by Theorem 4.2.6
$p^{\prime}$ is regular. ∎

######  Corollary 4.2.10.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology. Then the
following are equivalent for $T\subseteq\bm{\mathsf{P}}$:

$T$ is a maximal topen.

$T\neq\varnothing$ and $T=\mathit{K}(p)$ for every $p\in T$.

###### Proof.

If $T$ is a maximal topen and $p\in T$ then by Theorem 4.2.6(4.2.6)
$T=\mathit{K}(p)$.

If $T\neq\varnothing$ and $T=\mathit{K}(p)$ for every $p\in T$, then
$\mathit{K}(p)=\mathit{K}(p^{\prime})$ for every $p^{\prime}\in\mathit{K}(p)$
and by Corollary 4.2.8 $p$ is regular, so that by Definition 4.1.4(4.1.4)
$T=\mathit{K}(p)\in\mathsf{Topen}$ as required. ∎

###  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\ni q$. Suppose further that our topen neighbourhood $O$ intersects with the
maximal topen neighbourhood $\mathit{K}(p)$ of some other regular point $p$.
Then Proposition 4.3.1 tells us that were inside $\mathit{K}(p)$ all along.
See also Remark 5.3.3.

######  Proposition 4.3.1.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$p\in\bm{\mathsf{P}}$ is regular. Suppose $O\in\mathsf{Topen}$ is a topen.
Then

$O\between\mathit{K}(p)\quad\text{if and only if}\quad
O\subseteq\mathit{K}(p).$

###### Proof.

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

For the left-to-right implication, suppose $O\between\mathit{K}(p)$. By
Theorem 4.2.6 $\mathit{K}(p)$ is a maximal topen, and by Lemma 3.5.2(3.5.2)
$O\cup\mathit{K}(p)$ is topen. Then $O\subseteq\mathit{K}(p)$ follows by
maximality. ∎

######  Proposition 4.3.2.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and suppose
$p,p^{\prime}\in\bm{\mathsf{P}}$ are regular. Then

$\mathit{K}(p)\between\mathit{K}(p^{\prime})\quad\Longleftrightarrow\quad\mathit{K}(p)=\mathit{K}(p^{\prime})$

(See also Corollary 6.4.6, which considers similar properties for $p$ and
$p^{\prime}$ that are not necessarily regular.)

###### Proof.

We prove two implications.

  * •

Suppose there exists
$p^{\prime\prime}\in\mathit{K}(p)\cap\mathit{K}(p^{\prime})$. By Corollary
4.2.9 ($p^{\prime\prime}$ is regular and)
$\mathit{K}(p)=\mathit{K}(p^{\prime\prime})=\mathit{K}(p^{\prime})$.

  * •

Suppose $\mathit{K}(p)=\mathit{K}(p^{\prime})$. By assumption
$p\in\mathit{K}(p)$, so $p\in\mathit{K}(p^{\prime})$. Thus
$p\in\mathit{K}(p)\cap\mathit{K}(p^{\prime})$. ∎

We obtain a simple characterisation of regular semitopological spaces:

######  Corollary 4.3.3.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology. Then the
following are equivalent:

$(\bm{\mathsf{P}},\mathsf{Open})$ is regular.

$\bm{\mathsf{P}}$ partitions into topen sets: there exists some set of topen
sets $\mathcal{T}$ such that $T\mathbin{\cancel{\between}}T^{\prime}$ for
every $T,T^{\prime}\in\mathcal{T}$ and $\bm{\mathsf{P}}=\bigcup\mathcal{T}$.

Every $X\subseteq\bm{\mathsf{P}}$ has a cover of topen sets: there exists some
set of topen sets $\mathcal{T}$ such that $X\subseteq\bigcup\mathcal{T}$.

###### Proof.

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

  1. 1.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is regular, meaning by Definition
4.1.4(4.1.4&4.1.4) that $p\in\mathit{K}(p)\in\mathsf{Topen}$ for every
$p\in\bm{\mathsf{P}}$. We set $\mathcal{T}=\\{\mathit{K}(p)\mid
p\in\bm{\mathsf{P}}\\}$. By assumption this covers $\bm{\mathsf{P}}$ in
topens, and by Proposition 4.3.2 the cover is a partition.

  2. 2.

Suppose $\mathcal{T}$ is a topen partition of $\bm{\mathsf{P}}$. By definition
for every point $p$ there exists $T\in\mathcal{T}$ such that $p\in T$ and so
$p$ has a topen neighbourhood. By Theorem 4.2.6(4.2.6&4.2.6) $p$ is regular.

We prove equivalence of parts 2 and 3:

  1. 1.

Suppose $\mathcal{T}$ is a topen partition of $\bm{\mathsf{P}}$, and suppose
$X\subseteq\mathcal{P}$. Then trivially $X\subseteq\bigcup\mathcal{T}$.

  2. 2.

Suppose every $X\subseteq\bm{\mathsf{P}}$ has a cover of topen sets. Then
$\bm{\mathsf{P}}$ has a cover of topen sets; write it $\mathcal{T}$. By Lemma
3.5.2(3.5.2) we may assume without loss of generality that $\mathcal{T}$ is a
partition, and we are done. ∎

######  Notation 4.3.4.

Call a semitopology $(\bm{\mathsf{P}},\mathsf{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
$\mathbb{R}$. Put crudely:

‘Bad’ spaces are spaces that are not regular.

$\mathbb{R}$ with its usual topology (which is also a semitopology) is an
example of a ‘bad’ semitopology; it is not even quasiregular.

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

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 successful distributed collaboration is the
study of semitopological spaces that consist of a single topen set of points
that are all intertwined with one another.

###  4.4 Examples of communities and (ir)regular points

By Definition 4.1.4 a point $p$ is regular when its community is a topen
neighbourhood. Then a point is _not_ regular when its community is _not_ a
topen neighbourhood of $p$. We saw one example of this in Lemma 4.2.3. In this
subsection we take a moment to investigate the possible behaviour in more
detail.

######  Example 4.4.1.

  1. 1.

Take $\bm{\mathsf{P}}$ to be $\mathbb{R}$ the real numbers, with its usual
topology (which is also a semitopology). Then $x_{\between}=\\{x\\}$ and
$\mathit{K}(x)=\varnothing$ for every $x\in\mathbb{R}$.

In particular, no $x\in\mathbb{R}$ is regular.

  2. 2.

We continue the semitopology from Example 3.3.3(3.3.3) (illustrated in Figure
3, top-left diagram), as used in Lemma 4.2.3:

  3. 3.

$\bm{\mathsf{P}}=\\{0,1,2\\}$.

  4. 4.

$\mathsf{Open}$ is generated by $\\{0\\}$ and $\\{2\\}$. Then:

  5. 5.

$0_{\between}=\\{0,1\\}$ and
$\mathit{K}(0)=\mathit{interior}(0_{\between})=\\{0\\}$.

  6. 6.

$2_{\between}=\\{1,2\\}$ and
$\mathit{K}(2)=\mathit{interior}(2_{\between})=\\{2\\}$.

  7. 7.

$1_{\between}=\\{0,1,2\\}$ and $\mathit{K}(1)=\\{0,1,2\\}$.

  8. 8.

We take, as illustrated in Figure 5 (left-hand diagram):

  9. 9.

$\bm{\mathsf{P}}=\\{0,1,2,3,4\\}$.

  10. 10.

$\mathsf{Open}$ is generated by $\\{1,2\\}$, $\\{0,1,3\\}$, $\\{0,2,4\\}$,
$\\{3\\}$, and $\\{4\\}$. Then:

  11. 11.

$x_{\between}=\\{0,1,2\\}$ and
$\mathit{K}(x)=\mathit{interior}(x_{\between})=\\{1,2\\}$ for
$x\in\\{0,1,2\\}$.

  12. 12.

$x_{\between}=\\{x\\}=\mathit{K}(x)$ for $x\in\\{3,4\\}$. (We return to this
example in Example 10.1.3(12), and we will also use it in the proof of Lemma
10.2.4.)

  13. 13.

We take, as illustrated in Figure 5 (right-hand diagram):

  14. 14.

$\bm{\mathsf{P}}=\\{0,1,2,3,4\\}$.

  15. 15.

$\mathsf{Open}$ is generated by $\\{1\\}$, $\\{2\\}$, $\\{3\\}$, $\\{4\\}$,
$\\{0,1,2,3\\}$, and $\\{0,1,2,4\\}$. Then:

  16. 16.

$0_{\between}=\\{0,1,2\\}$ and $\mathit{K}(0)=\\{1,2\\}$.

  17. 17.

$\mathit{K}(0)$ is not transitive and consists of two distinct topens
$\\{1\\}$ and $\\{2\\}$.

  18. 18.

$0\not\in\mathit{K}(0)$. See Remark 5.6.3 for further discussion of this
example.

  19. 19.

The reader can also look ahead to Example 5.6.10. In Example 5.6.10(1), every
point $p$ is regular and $\mathit{K}(p)=\mathbb{Q}^{2}$. In Example 5.6.10(2),
no point $p$ is regular and
$\mathit{K}(p)=\varnothing\subseteq\mathbb{Q}^{2}$.

Figure 5: Illustration of Example 4.4.1(8&13)

######  Lemma 4.4.2.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$p\in\bm{\mathsf{P}}$. Then precisely one of the following possibilities must
hold, and each is possible:

  1. 1.

$p$ is regular: $p\in\mathit{K}(p)$ and $\mathit{K}(p)$ is topen (nonempty,
open, and transitive).

  2. 2.

$\mathit{K}(p)$ is topen, but $p\not\in\mathit{K}(p)$.

  3. 3.

$\mathit{K}(p)=\varnothing$.

  4. 4.

$\mathit{K}(p)$ is open but not transitive. (Both $p\in\mathit{K}(p)$ and
$p\not\in\mathit{K}(p)$ are possible.)

###### Proof.

  1. 1.

To see that $p$ can be regular, consider $\bm{\mathsf{P}}=\\{0\\}$ with the
discrete topology. Then $p\in\mathit{K}(p)=\\{0\\}$.

  2. 2.

To see that it is possible for $\mathit{K}(p)$ to be topen but $p$ is not in
it, consider Example 4.4.1(8). There, $\bm{\mathsf{P}}=\\{0,1,2,3,4\\}$ and
$1_{\between}=\\{0,1,2\\}$ and $\mathit{K}(1)=\\{0,2\\}$. Then $\mathit{K}(1)$
is topen, but $1\not\in\mathit{K}(1)$.

  3. 3.

To see that $\mathit{K}(p)=\varnothing$ is possible, consider Example 4.4.1(1)
(the real numbers $\mathbb{R}$ with its usual topology). Then by Remark 3.6.10
$r_{\between}=\\{r\\}$ and so
$\mathit{K}(x)=\mathit{interior}(\\{r\\})=\varnothing$. (See also Example
5.6.10(2) for a more elaborate example.)

  4. 4.

To see that it is possible for $\mathit{K}(p)$ to be an open neighbourhood of
$p$ but not transitive, see Example 4.4.1(2). There,
$\bm{\mathsf{P}}=\\{0,1,2\\}$ and $1\in
1_{\between}=\\{0,1,2\\}=\mathit{K}(1)$, but $\\{0,1,2\\}$ is not transitive
(it contains two disjoint topens: $\\{0\\}$ and $\\{2\\}$).

To see that it is possible for $\mathit{K}(p)$ to be open and nonempty yet not
contain $p$ and not be transitive, see Example 4.4.1(13) for $p=0$, and see
also Remark 5.6.3 for a discussion of the connection with minimal closed
neighbourhoods.

The possibilities above are clearly mutually exclusive and exhaustive. ∎

##  5 Closed sets

###  5.1 Closed sets

######  Remark 5.1.1.

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. From Subsection
5.3 and the following Subsections we will study the close relation between
closures and sets of intertwined points.

First, we spare a few words on why closures are particularly interesting in
semitopologies:

A participant may wish to compute a quorum that it can be confident of
remaining in agreement with, where algorithms succeed. The notion of maximal
topen from Definition 3.2.1(3.2.1) provides this, as discussed in Remark 3.2.7
— but computing maximal topens is hard since the definition involves
quantifications over all open sets and there may be many of them.

However, computing _closures_ is quite tractable in the right circumstances
(see Section 8 and Remark 8.4.14), so a characterisation of maximal topens
using closed sets and closures is of practical interest.

Closures are significant for other reasons too: see the discussions in Remarks
5.5.1 and 5.5.5, and see the later material in Section 11 that considers
_dense sets_. Thus, and just as is the case in topology, closures are an
interesting object of study.

######  Definition 5.1.2.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and suppose
$p\in\bm{\mathsf{P}}$ and $P\subseteq\bm{\mathsf{P}}$. Then:

Define $|P|\subseteq\bm{\mathsf{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^{\prime}\in\bm{\mathsf{P}}\mid\forall
O{\in}\mathsf{Open}.p^{\prime}\in O\Longrightarrow P\between O\\}.$

As is standard, we may write $|p|$ for $|\\{p\\}|$. Unpacking definitions for
reference:

$|p|=\\{p^{\prime}\in\bm{\mathsf{P}}\mid\forall
O{\in}\mathsf{Open}.p^{\prime}\in O\Longrightarrow p\in O\\}.$

######  Lemma 5.1.3.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and suppose
$P,P^{\prime}\subseteq\bm{\mathsf{P}}$. Then taking the closure of a set is:

_Monotone:_ If $P\subseteq P^{\prime}$ then $|P|\subseteq|P^{\prime}|$.

_Increasing:_ $P\subseteq|P|$.

_Idempotent:_ $|P|=||P||$.

###### Proof.

By routine calculations from Definition 5.1.2. ∎

######  Lemma 5.1.4.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$P\subseteq\bm{\mathsf{P}}$ and $O\in\mathsf{Open}$. Then

$P\between O\quad\text{if and only if}\quad|P|\between O.$

###### Proof.

Suppose $P\between O$. Then $|P|\between O$ using Lemma 5.1.3(5.1.3).

Suppose $|P|\between O$. Pick $p\in|P|\cap O$. By construction of $|P|$ in
Definition 5.1.2 $p\in O\Longrightarrow P\between O$. It follows that
$P\between O$ as required. ∎

######  Definition 5.1.5.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and suppose
$C\subseteq\bm{\mathsf{P}}$.

Call $C$ closed when $C=|C|$.

Call $C$ clopen when $C$ is closed and open.

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

######  Lemma 5.1.6.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and suppose
$S\subseteq\bm{\mathsf{P}}$. Then $|S|$ is closed and contains $S$. In
symbols:

$S\subseteq|S|\in\mathsf{Closed}.$

###### Proof.

From Definition 5.1.5(1) and Lemma 5.1.3(5.1.3 & 5.1.3). ∎

######  Example 5.1.7.

  1. 1.

Take $\bm{\mathsf{P}}=\\{0,1\\}$ and
$\mathsf{Open}=\\{\varnothing,\\{0\\},\\{0,1\\}\\}$. Then the reader can
verify that:

  2. 2.

$\\{0\\}$ is open.

  3. 3.

The closure of $\\{1\\}$ is $\\{1\\}$ and $\\{1\\}$ is closed.

  4. 4.

The closure of $\\{0\\}$ is $\\{0,1\\}$.

  5. 5.

$\varnothing$ and $\\{0,1\\}$ are the only clopen sets.

  6. 6.

Now take $\bm{\mathsf{P}}=\\{0,1\\}$ and
$\mathsf{Open}=\\{\varnothing,\\{0\\},\\{1\\},\\{0,1\\}\\}$.222222Following
Definition 2.1.3 and Example 2.1.4(3), this is just $\\{0,1\\}$ with the
_discrete semitopology_. Then the reader can verify that:

  7. 7.

Every set is clopen.

  8. 8.

The closure of every set is itself.

######  Remark 5.1.8.

There are two standard definitions for when a set is closed: when it is equal
to its closure (as per Definition 5.1.5(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.9.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology. Then:

Suppose $C\in\mathsf{Closed}$ is closed (by Definition 5.1.5: $C=|C|$). Then
$\bm{\mathsf{P}}\setminus C$ is open.

Suppose $O\in\mathsf{Open}$ is open. Then $\bm{\mathsf{P}}\setminus O$ is
closed (by Definition 5.1.5: $|\bm{\mathsf{P}}\setminus
O|=\bm{\mathsf{P}}\setminus O$).

###### Proof.

  1. 1.

Suppose $p\in\bm{\mathsf{P}}\setminus C$. Since $C=|C|$, we have
$p\in\bm{\mathsf{P}}\setminus|C|$. Unpacking Definition 5.1.2, this means
precisely that there exists $O_{p}\in\mathsf{Open}$ with $p\in
O_{p}\mathbin{\cancel{\between}}C$. We use Lemma 2.3.2.

  2. 2.

Suppose $O\in\mathsf{Open}$. Combining Lemma 2.3.2 with Definition 5.1.2 it
follows that $O\mathbin{\cancel{\between}}|\bm{\mathsf{P}}\setminus O|$ so
that $|\bm{\mathsf{P}}\setminus O|\subseteq\bm{\mathsf{P}}\setminus O$.
Furthermore, by Lemma 5.1.3(5.1.3) $\bm{\mathsf{P}}\setminus
O\subseteq|\bm{\mathsf{P}}\setminus O|$. ∎

######  Corollary 5.1.10.

If $C\in\mathsf{Closed}$ then $\bm{\mathsf{P}}\setminus
C=\bigcup_{O\in\mathsf{Open}}O\mathbin{\cancel{\between}}C$.

###### Proof.

By Lemma 5.1.9(1) $\bm{\mathsf{P}}\setminus
C\subseteq\bigcup_{O\in\mathsf{Open}}O\mathbin{\cancel{\between}}C$.
Conversely, if $O\mathbin{\cancel{\between}}C$ then
$O\subseteq\bm{\mathsf{P}}\setminus C$ by Definition 5.1.2(5.1.2). ∎

######  Corollary 5.1.11.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ is a semitopology and
$P\subseteq\bm{\mathsf{P}}$ and
$\mathcal{C}\subseteq\mathit{pow}(\bm{\mathsf{P}})$. Then:

$\varnothing$ and $\bm{\mathsf{P}}$ are closed.

If every $C\in\mathcal{C}$ is closed, then $\bigcap\mathcal{C}$ is closed. Or
succinctly in symbols:

$\mathcal{C}\subseteq\mathsf{Closed}\Longrightarrow\bigcap\mathcal{C}\in\mathsf{Closed}.$

$|P|$ is equal to the intersection of all the closed sets that contain it. In
symbols:

$|P|=\bigcap\\{C\in\mathsf{Closed}\mid P\subseteq C\\}.$

###### Proof.

  1. 1.

Immediate from Lemma 5.1.9(2).

  2. 2.

From Lemma 5.1.9 and Definition 1.1.2(1&2).

  3. 3.

By Lemma 5.1.6 $\bigcap\\{C\in\mathsf{Closed}\mid P\subseteq
C\\}\subseteq|P|$. By construction
$P\subseteq\bigcap\\{C\in\mathsf{Closed}\mid P\subseteq C\\}$, and using Lemma
5.1.3(5.1.3) and part 2 of this result we have

$|P|\stackrel{{\scriptstyle
L\ref{lemm.closure.monotone}(\ref{closure.monotone})}}{{\subseteq}}|\bigcap\\{C\in\mathsf{Closed}\mid
P\subseteq C\\}|\stackrel{{\scriptstyle
pt.2}}{{=}}\bigcap\\{C\in\mathsf{Closed}\mid P\subseteq C\\}.$

∎

The usual characterisation of continuity in terms of inverse images of closed
sets being closed, remains valid:

######  Corollary 5.1.12.

Suppose $(\bm{\mathsf{P}},\mathsf{Open})$ and
$(\bm{\mathsf{P}}^{\prime},\mathsf{Open}^{\prime})$ are semitopological spaces
(Definition 1.1.2) and suppose $f:\bm{\mathsf{P}}\to\bm{\mathsf{P}}^{\prime}$
is a function. Then the following are equivalent:

$f$ is continuous, meaning by Definition 2.2.1(2) that
$f^{\text{-}1}(O^{\prime})\in\mathsf{Open}$ for every
$O^{\prime}\in\mathsf{Open}^{\prime}$.

$f^{\text{-}1}(C^{\prime})\in\mathsf{Closed}$ for every
$C^{\prime}\in\mathsf{Closed}^{\prime}$.

###### Proof.

By routine calculations as for topologies, using Lemma 5.1.9 and the fact that
the inverse image of a complement is the complement of the inverse image; see
[Wil70, Theorem 7.2, page 44] or [Eng89, Proposition 1.4.1(iv), page 28]. ∎

###  5.2 Duality between closure and interior

The usual dualities between closures and interiors remain valid in
semitopologies. There are no surprises but this still needs checked so we