# Causal Unfoldings and Disjunctive Causes

Marc de Visme  Univ Lyon, ENS de Lyon, CNRS, UCB Lyon 1, LIP, France  marc.de-
<EMAIL_ADDRESS>and  Glynn Winskel  Computer Laboratory, University of
Cambridge, UK<EMAIL_ADDRESS>
###### Abstract.

In the simplest form of event structure, a prime event structure, an event is
associated with a unique causal history, its prime cause. However, it is quite
common for an event to have disjunctive causes in that it can be enabled by
any one of multiple sets of causes. Sometimes the sets of causes may be
mutually exclusive, inconsistent one with another, and sometimes not, in which
case they coexist consistently and constitute parallel causes of the event.
The established model of general event structures can model parallel causes.
On occasion however such a model abstracts too far away from the precise
causal histories of events to be directly useful. For example, sometimes one
needs to associate probabilities with different, possibly coexisting, causal
histories of a common event. Ideally, the causal histories of a general event
structure would correspond to the configurations of its causal unfolding to a
prime event structure; and the causal unfolding would arise as a right adjoint
to the embedding of prime in general event structures. But there is no such
adjunction. However, a slight extension of prime event structures remedies
this defect and provides a causal unfolding as a universal construction. Prime
event structures are extended with an equivalence relation in order to
dissociate the two roles, that of an event and its enabling; in effect, prime
causes are labelled by a disjunctive event, an equivalence class of its prime
causes. With this enrichment a suitable causal unfolding appears as a pseudo
right adjoint. The adjunction relies critically on the central and subtle
notion of extremal causal realisation as an embodiment of causal history.
Finally, we explore subcategories which support parallel causes as well the
key operations needed in developing probabilistic distributed strategies with
parallel causes.

###### Key words and phrases:

Event Structures, Parallel Causes, Causal Unfolding, Probability

##  1\. Introduction

Work on probabilistic distributed strategies based on event structures brought
us face to face with a limitation in existing models of concurrent
computation, and in particular with the theory of event structures as it had
been developed. In order to adequately express certain intuitively natural,
optimal probabilistic strategies, it was necessary to simultaneously support:
probability on event structures with opponent moves, itself rather subtle;
parallel causes, in which an event may be enabled in several distinct but
compatible ways; and a hiding operation crucial in the composition of
strategies. The difficulties did not show up in the less refined development
of nondeterministic strategies; there the simplest form of event structure,
prime event structures, sufficed. The “obvious” remedy, to base strategies on
more general event structures, which do support parallel causes, failed to
support probability and hiding adequately.111In the context of games,
deterministic general event structures do support parallel causes and hiding
so strategies with parallel causes such as that of parallel-or, but of course
not the underlying nondeterminism required for probabilistic strategies
[CCW17, Win16]. The problems and a solution are documented in the article
[dVW17].

That work uncovered a central construction, which we here call the causal
unfolding of a model with parallel causes. It is based on the notion of
extremal causal realisation and attendant prime extremal realisation which
plays a role analogous to that of complete prime in distributive orders. Both
concepts deserve to be better known and are expanded on comprehensively with
full proofs here. As will shortly be explained more fully, intuitively, a
prime extremal realisation is a finite partial order expressing a minimal
causal history for an event to occur, even in the presence of several parallel
causes for the event. Extremal realisations provide us with a way to unfold a
model supporting parallel causes (general event structures—Section 2.2, or
equivalence families—Section 3) into a structure describing all its causal
histories—its causal unfolding. As is to be hoped, the unfolding will be a
form of right adjoint giving the causal unfolding and extremal realisations a
categorical significance.

To give an idea of prime extremal realisations of events we give a short,
necessarily informal, preview of two examples from the paper. The simplest
concerns a general event structure comprising three events $a$, $b$ and $d$
where $d$ can occur once $a$ or $b$ have occurred and where all events can
occur together. The events $a$ and $b$ constitute parallel causes of the event
$d$. We can picture the situation in the diagram:

$\textstyle{d}$$\textstyle{OR}$$\textstyle{a}$$\textstyle{b}$

Here there are two minimal causal histories associated with the occurrence of
the event $d$, viz. $d$ after $a$, and $d$ after $b$ :

$\textstyle{d}$$\textstyle{d}$ and $\textstyle{a}$$\textstyle{b}$

These will be the prime extremal realisations associated with the occurrence
of $d$. But this example is deceptively simple. To add a level of difficulty,
consider the general event structure

$\textstyle{d}$$\textstyle{c}$ANDOR$\textstyle{a}$$\textstyle{b}$

which portrays an event $d$ enabled through the occurrence of all of the
events $a$, $b$ and $c$ but where $c$ is enabled by either $a$ or $b$. This
time the two minimal causal histories associated with the occurrence of the
event $d$, one after $c$ caused by $a$, and the other after $c$ caused by $b$,
give rise to the two prime extremal realisations:

$\textstyle{d}$$\textstyle{c}$$\textstyle{a}$$\textstyle{b}$ and
$\textstyle{d}$$\textstyle{c}$$\textstyle{a}$$\textstyle{b}$

There are also more subtle ‘non-injective’ prime extremal realisations in
which the same event of a general event structure occurs in several different
ways—see Example 4.2, though these have been ruled out in our application to
strategies with parallel causes [dVW17].

The new adjunction, with its right adjoint the causal unfolding, supplies a
missing link in the landscape of models for concurrency [WN95]. The adjunction
connects models with parallel causes, such as general event structures, to
those based on partial orders of events. It does this through the introduction
of a simple, new model which is based on prime event structures extended with
an equivalence relation on their sets of events. In its most general form the
adjunction relates two new models, prime event structures with an equivalence
relation to families of configurations with a similar equivalence. We explore
how the adjunction restricts and simplifies on subcategories, in particular,
between event structures with disjunctive causes (edc’s) and stable families
with equivalence. Via the simplified adjunction we show that the category of
edc’s has the constructions pullback, pseudo pullback and factorisation needed
to develop distributed probabilistic strategies with parallel causes [dVW17].
We point the reader to the figure of the Conclusion; it summarises the
adjunctions relating the models we encounter and develop in the article.

More broadly, often in systems with parallel causes it is necessary to
associate probabilities with causal histories, and the causal unfolding
provides a suitable structure on which to do this systematically [dVW17].
Outside probability, there is a similar need for causal unfoldings, for
example, when reversible computing encounters parallel causes [Cri15, CKV15],
and in extracting biochemical pathways, forms of causal history in biochemical
systems where parallel causes are rife [DFF+12].

##  2\. Event structures and their maps

We briefly review two well-established forms of event structure and explain
the absence of an adjunction associated with the embedding of prime into
general event structures. It is through such an adjunction one might otherwise
have thought to find a causal unfolding of general event structures to prime
event structures. The absence motivates a new model based on prime event
structures with an equivalence relation. (We refer the reader to [Win80,
Win86] in particular for background and intuitions.)

###  2.1. Prime event structures

A prime event structure comprises $(E,\leq,\textrm{Con})$, consisting of a set
$E$ of events which are partially ordered by $\leq$, the causal dependency
relation, and a non-empty consistency relation Con consisting of finite
subsets of $E$. The relation $e^{\prime}\leq e$ expresses that event $e$
causally depends on the previous occurrence of event $e^{\prime}$. Write $[X]$
for the $\leq$-down-closure of a subset of events $X$. That a finite subset of
events is consistent conveys that its events can occur together by some stage
in the evolution of the process. Together the relations satisfy several
axioms:

$[e]={\\{e^{\prime}\ |\ e^{\prime}\leq e\\}}$ is finite, for all $e\in E$,
---
${\\{e\\}}\in\textrm{Con}$, for all $e\in E$,
$X\subseteq Y\in\textrm{Con}\implies X\in\textrm{Con}$, and
$X\in\textrm{Con}\ \&\ e\leq e^{\prime}\in X\implies
X\cup{\\{e\\}}\in\textrm{Con}$.

A configuration is a, possibly infinite, set of events $x\subseteq E$ which
is: consistent, $X\subseteq x\hbox{ and }X\hbox{ is finite}\hbox{ implies
}X\in\textrm{Con}$ ; and down-closed,  $[x]=x$. It is part and parcel of prime
event structures that an event $e$ is associated with a unique causal history
$[e]$.

Prime event structures have a long history. They first appeared in describing
the patterns of event occurrences that occurred in the unfolding of a (1-safe)
Petri net [NPW81]. As their configurations, ordered by inclusion, form a Scott
domain, prime event structures provided an early bridge between the semantic
theories of Dana Scott and Carl Petri; one early result being that a
confusion-free Petri net unfolded to a prime event structure with
configurations taking the form of a concrete domain, as defined by Kahn and
Plotkin. Generally, the configurations of a countable prime event structure
ordered by inclusion coincide with the dI-domains of Berry—distributed Scott
domains which satisfy a finiteness axiom [Win86]. The domains of configuration
of a prime event structure had been characterised earlier in [NPW81] as prime
algebraic domains, Scott domains with a subbasis of complete primes.222A
complete prime in an order which supports least upper bounds $\bigsqcup X$ of
compatible subsets $X$ is an element $p$ such that $p\sqsubseteq\bigsqcup X$
implies $p\sqsubseteq x$ for some $x\in X$. In the configurations of a prime
event structure the complete primes are exactly those configurations $[e]$ for
an event $e$.

###  2.2. General event structures

A general event structure [Win80, Win86] permits an event to be caused
disjunctively in several ways, possibly coexisting in parallel, as parallel
causes. A general event structure comprises $(E,\textrm{Con},\vdash)$ where
$E$ is a set of events, the consistency relation Con is a non-empty collection
of finite subsets of $E$, and the enabling relation ${\vdash}$ is a relation
in $\textrm{Con}\times E$ such that

$\begin{matrix}X\subseteq Y\in\textrm{Con}\implies X\in\textrm{Con}\,,\hbox{
and}\\\ Y\in\textrm{Con}\ \&\ Y\supseteq X\ \&\ X\vdash e\implies Y\vdash
e\,.\end{matrix}$

A configuration is a subset $x$ of $E$ which is: consistent,
$X\subseteq_{\textrm{fin}}x\implies X\in\textrm{Con}$; and secured, $\forall
e\in x\exists e_{1},\cdots,e_{n}\in x.\ \ e_{n}=e\ \ \&\ \forall i\leq
n.{\\{e_{1},\cdots,e_{i-1}\\}}\vdash~{}e_{i}\,$. We write
$\>\\!{\mathcal{C}}^{\infty}(E)$ for the configurations of $E$ and
$\>\\!{\mathcal{C}}(E)$ for its finite configurations. (For illustrations of
small general event structures see, for instance, Example 2.3 and $E_{0}$ of
Example 4.2.)

An event $e$ being enabled in a configuration has been expressed through the
existence of a securing chain $e_{1},\cdots,e_{n}$, with $e_{n}=e$, within the
configuration. The chain represents a complete enabling of $e$ in the sense
that every event in the chain is itself enabled by earlier members of the
chain. Just as mathematical proofs are most usefully viewed not merely as
sequences, so later complete enablings expressed more generally as partial
orders—“causal realisations”—will play a central role.

A map
$f:(E,\textrm{Con},\vdash)\to(E^{\prime},\textrm{Con}^{\prime},\vdash^{\prime})$
of general event structures is a partial function $f:E\rightharpoonup
E^{\prime}$ such that

$\begin{matrix}[l]\forall X\in\textrm{Con}\,.\
fX\in\textrm{Con}^{\prime}\,,\\\ \forall X\in\textrm{Con},e_{1},e_{2}\in X.\
f(e_{1})=f(e_{2})\text{ (both defined)}\implies e_{1}=e_{2}\,,\hbox{ and }\\\
\forall X\in\textrm{Con},e\in E.\ X\vdash e\ \&\ f(e)\text{ is defined
}\implies fX\vdash^{\prime}f(e)\,.\end{matrix}$

Maps compose as partial functions. Write $\mathcal{G}$ for the category of
general event structures.

W.r.t. a family of subsets ${\mathcal{F}}$, a subset $X$ of ${\mathcal{F}}$ is
compatible (in ${\mathcal{F}}$), if there is $y\in{\mathcal{F}}$ such that
$x\subseteq y$ for all $x\in X$; in particular ${\\{x,y\\}}$ is compatible if
there is $z\in{\mathcal{F}}$ such that $x,y\subseteq z$. Say a subset is
finitely compatible iff every finite subset is compatible.

We can now characterise those families of configurations arising from a
general event structure [Win86]. A family of configurations comprises a non-
empty family ${\mathcal{F}}$ of sets such that if $X\subseteq{\mathcal{F}}$ is
finitely compatible in ${\mathcal{F}}$ then $\bigcup X\in{\mathcal{F}}$; and
if $e\in x\in{\mathcal{F}}$ there is a securing chain $e_{1},\cdots,e_{n}=e$
in $x$ such that ${\\{e_{1},\cdots,e_{i}\\}}\in{\mathcal{F}}$ for all $i\leq
n$.333The latter condition is equivalent to: (i) if $e\in x\in{\mathcal{F}}$
there is a finite $x_{0}\in{\mathcal{F}}$ s.t. $e\in x_{0}\in{\mathcal{F}}$
and (ii) (coincident-freeness) for distinct $e,e^{\prime}\in x$, there is
$y\in{\mathcal{F}}$ with $y\subseteq x$ s.t. $e\in y\iff e^{\prime}\not\in y$.
Its events are elements of the underlying set $\bigcup{\mathcal{F}}$.

A map between families of configurations from ${\mathcal{A}}$ to
${\mathcal{B}}$ is a partial function
$f:\bigcup{\mathcal{A}}\rightharpoonup\bigcup{\mathcal{B}}$ between their
events such that $fx\in{\mathcal{B}}$ if $x\in{\mathcal{A}}$ and any event of
$fx$ arises as the image of a unique event of $x$, i.e. the following local
injectivity is fulfilled:

$e_{1},e_{2}\in x\ \&\ f(e_{1})=f(e_{2})\hbox{ (both defined) }\implies
e_{1}=e_{2}\,.$

Maps compose as partial functions. Write $\mathcal{F}\\!am$ for the category
of families of configurations. In Section 7.2, we shall meet the subcategory
$\mathcal{S\\!F}\\!am$ of stable families of configurations, with objects
${\mathcal{A}}$ of $\mathcal{F}\\!am$ that satisfy

$\forall x,y,z\in{\mathcal{A}}.\ \ x,y\subseteq z\ \Rightarrow\ x\cap
y\in{\mathcal{A}}\,,$

which plays an important role in constructions on prime event structures
[Win82, Win86].

Characterisations of the orders obtained from the configurations of a general
event structure can be found in [Win80].444Complete irreducibles are the
customary generalisation of complete primes to nondistributive orders such as
those of configurations of general event structures ordered by inclusion
[Win80]. A complete irreducible in an order which supports least upper bounds
$\bigsqcup X$ of compatible subsets $X$ is an element $r$ such that
$r=\bigsqcup X$ implies $r=x$ for some $x\in X$. In the configurations of a
general event structure the complete irreducibles are exactly those minimal
configurations which contain an event $e$. A forewarning: only in very special
circumstances will prime extremal realisations—the generalisation of complete
prime of this paper—coincide with complete irreducibles—see Example 4.2.

###  2.3. A coreflection and non-coreflection

There is a forgetful functor $\mathcal{G}\to\mathcal{F}\\!am$ taking a general
event structure to its family of configurations. It has a left adjoint, which
constructs a canonical general event structure from a family: given
${\mathcal{A}}$, a family of configurations with underlying events $A$,
construct a general event structure $(A,\textrm{Con},\vdash)$ with
$X\in\textrm{Con}$ iff $X\subseteq_{\textrm{fin}}y$, for some
$y\in{\mathcal{A}}$; and with $X\vdash a$ iff $a\in A$, $X\in\textrm{Con}$ and
$a\in y\subseteq X\cup{\\{a\\}}$, for some $y\in{\mathcal{A}}$. The above
yields a coreflection555A coreflection is an adjunction where the left adjoint
is full and faithful, or equivalently the unit is iso.

$\textstyle{\mathcal{F}\\!am\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\top}$$\textstyle{\mathcal{G}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

of families of configurations in general event structures. It cuts down to an
equivalence between families of configurations and replete general event
structures. A general event structure $(E,\textrm{Con},\vdash)$ is replete iff

$\begin{matrix}[l]\forall e\in E\,\exists X\in\textrm{Con}.\ X\vdash e\ \,,\\\
\forall X\in\textrm{Con}\,\exists x\in\>\\!{\mathcal{C}}(E).\ X\subseteq x\
\text{ and }\\\ X\vdash e\implies\exists x\in\>\\!{\mathcal{C}}(E).\ e\in x\
\&\ x\subseteq X\cup{\\{e\\}}\,.\end{matrix}$

A map of prime event structures is a map of their families of configurations.
Write $\mathcal{E}$ for the category of prime event structures. (A map in
$\mathcal{E}$ need not preserve causal dependency; when it does and is total
it is called rigid.)

There is an obvious “inclusion” functor $\mathcal{E}\to\mathcal{F}\\!am$ fully
and faithfully embedding the category of prime event structures in the
category of families of configurations and so in general event structures. We
might expect the functor $\mathcal{E}\to\mathcal{F}\\!am$ to be the left
adjoint of a coreflection

$\textstyle{\mathcal{E}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\top}$$\textstyle{\mathcal{F}\\!am\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$?$\scriptstyle{\top}$$\textstyle{\mathcal{G}\,,\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

so yielding a composite right adjoint $\mathcal{G}\to\mathcal{E}$ which
unfolds a general event structure to a prime event structure [Win86, WN95].
However under reasonable assumptions this cannot exist, as the following
example indicates.

Consider a general event structure comprising three events $a$, $b$ and $d$
with all subsets consistent and minimal enablings $\emptyset\vdash a,b$ and
${\\{a\\}}\vdash d$ and ${\\{b\\}}\vdash d$. Imagine concurrent treatments $a$
and $b$ of two doctors which sadly lead to the death $d$ of the patient.

$\textstyle{d}$$\textstyle{OR}$$\textstyle{a}$$\textstyle{b}$

As its unfolding it is hard to avoid a prime event structure with events and
causal dependency $a<d_{a}$ and $b<d_{b}$—the event $d_{a}$ representing
“death by $a$” and the event $d_{b}$ “death by $b$”—with the counit of the
adjunction collapsing $d_{a}$ and $d_{b}$ to the common event $d$. (If we are
to apportion blame to the doctors we shall need the probabilities of $d_{a}$
and $d_{b}$ given $a$ and $b$ [Pea13].) In order for the counit to be a map we
are forced to make ${\\{d_{a},d_{b}\\}}$ inconsistent. This is one issue: why
should death by one doctor’s treatment be in conflict with death by the
other’s—they could be jointly responsible? But even more damningly the
tentative counit fails the universal property required of it! Consider another
prime event structure with three events comprising $a<d$ and $b<d$ (“death due
to both doctors’ treatments”). The obvious map to the family of configurations
of the general event structure—the identity on events—fails to factor uniquely
through the putative counit: $d$ can be sent to either $d_{a}$ or $d_{b}$; the
event “death by both doctors” can be sent to either “death by a” or “death by
b.” This raises the second issue: if we are to obtain the required universal
property we have to regard these two maps as essentially the same.

The two issues raised in the example suggest a common solution: to enrich
prime event structures with equivalence relations. This will allow a broader
class of maps, settling the first issue, and introduce an equivalence on maps,
settling the second. The causal unfolding of the “doctors example” will be
very simple and comprise the prime event structure $a<d_{a}$ and $b<d_{b}$
with $d_{a}$ and $d_{b}$ equivalent events; with all events consistent. In
general the construction of the unfolding is surprisingly involved; causal
histories can be much more intricate than in the simple example.

##  3\. Events with an equivalence, categories ${\mathcal{E}}_{\equiv}$ and
$\mathcal{F}\\!am_{\equiv}$

We build causal unfoldings in a new model, based on the obvious extension to
events with an equivalence relation. A (prime) event structure with
equivalence (an ese) is a structure

$(P,\leq,\textrm{Con},\equiv)$

where $(P,\leq,\textrm{Con})$ satisfies the axioms of a prime event structure
and $\equiv$ is an equivalence relation on $P$. The intention is that the
events of $P$ represent prime causes while the $\equiv$-equivalence classes of
$P$ represent disjunctive events: $p$ in $P$ is a prime cause of the event
${\\{p\\}}_{\equiv}$. Notice there may be several prime causes of the same
event and that these may be parallel causes in the sense that they are
consistent with each other and causally independent.

The extension by an equivalence relation on events is accompanied by an
extension to families of configurations. An equivalence-family (ef) is a
family of configurations ${\mathcal{A}}$ with an equivalence relation
$\equiv_{A}$ on its underlying set
$A\mathrel{=_{\mathrm{def}}}\bigcup{\mathcal{A}}$ (with no further axioms).
Equivalence-families are the most general model we shall consider; they
support parallel causes and, later, a causal unfolding.

Let $({\mathcal{A}},\equiv_{A})$ and $({\mathcal{B}},\equiv_{B})$ be ef’s,
with respective underlying sets $A$ and $B$. A map
$f:({\mathcal{A}},\equiv_{A})\to({\mathcal{B}},\equiv_{B})$ is a partial
function $f:A\rightharpoonup B$ which preserves $\equiv$, if
$a_{1}\equiv_{A}a_{2}$ then either both $f(a_{1})$ and $f(a_{2})$ are
undefined or both defined with $f(a_{1})\equiv_{B}f(a_{2})$, such that

$x\in{\mathcal{A}}\implies fx\in{\mathcal{B}}\ \&\ \forall a_{1},a_{2}\in x.\
f(a_{1})\equiv_{B}f(a_{2})\implies a_{1}\equiv_{A}a_{2}\,.$

Composition is composition of partial functions. We regard two maps

$f_{1},f_{2}:({\mathcal{A}},\equiv_{A})\to({\mathcal{B}},\equiv_{B})$

as equivalent, and write $f_{1}\equiv f_{2}$, iff they are equidefined and
yield equivalent results, i.e. if $f_{1}(p)$ is defined then so is $f_{2}(p)$
and $f_{1}(p)\equiv_{Q}f_{2}(p)$, and if $f_{2}(p$) is defined then so is
$f_{1}(p)$ and $f_{1}(p)\equiv_{Q}f_{2}(p)$. Composition respects $\equiv$.
This yields a category of equivalence families $\mathcal{F}\\!am_{\equiv}$; it
is enriched in the category of sets with equivalence relations (also called
setoids).666Appendix A provides background on categories enriched in
equivalence relations.

Clearly from an ese $(P,\equiv_{P})$ we obtain an ef
$(\>\\!{\mathcal{C}}^{\infty}(P),\equiv_{P})$ and we take a map of ese’s to be
a map between their associated ef’s. Write ${\mathcal{E}}_{\equiv}$ for the
category of ese’s; it too is enriched in the category of sets with equivalence
relations. When the equivalence relations $\equiv$ of ese’s are the identity
we essentially have prime event structures and their maps. There is clearly a
full-and-faithful embedding

${\mathcal{E}}_{\equiv}\to\mathcal{F}\\!am_{\equiv}\,,$

which preserves and reflects the equivalence on maps. One virtue of ese’s is
that they support a hiding operation, associated with a factorisation system
[dVW17].

We sometimes use an alternative description of their maps:

######  Proposition 1.

A map of ese’s from $P$ to $Q$ is a partial function $f:P\rightharpoonup Q$
which preserves $\equiv$ such that

  1. (i)

for all $X\in\textrm{Con}_{P}$ the direct image $fX\in\textrm{Con}_{Q}$ and
$\forall p_{1},p_{2}\in X.\ f(p_{1})\equiv_{Q}f(p_{2})\implies
p_{1}\equiv_{P}p_{2}$ , and

  2. (ii)

whenever $q\leq_{Q}f(p)$ there is $p^{\prime}\leq_{P}p$ such that
$f(p^{\prime})=q$ .

While an ese determines an ef, the converse, how to construct the causal
unfolding of an ef to an ese, is much less clear. To do so we follow up on the
idea of Section 2.2 of basing minimal complete enablings on partial orders. A
minimal complete enabling will correspond to a prime extremal realisation.
Realisations and extremal realisations are our next topic.

##  4\. Causal histories as extremal realisations

Extremal causal realisations formalise the notion of causal history in models
with parallel causes, viz. general event structures and the most general model
of equivalence-families. They will be the central tool in constructing the
causal unfoldings of such models.

###  4.1. Causal realisations

Let ${\mathcal{A}}$ be a family of configurations with underlying set $A$. A
(causal) realisation of ${\mathcal{A}}$ comprises a partial order $(R,\leq)$,
its carrier, such that the set ${\\{e^{\prime}\in R\ |\ e^{\prime}\leq e\\}}$
is finite for all events $e\in R$, together with a function $\rho:R\to A$ for
which the image $\rho x\in{\mathcal{A}}$ when $x$ is a down-closed subset of
$R$. We say a realisation is injective when it is injective as a function.

A map between realisations $(R,\leq),\rho$ and
$(R^{\prime},\leq^{\prime}),\rho^{\prime}$ is a partial surjective function
$f:R\rightharpoonup R^{\prime}$ which preserves down-closed subsets and
satisfies $\rho(e)=\rho^{\prime}(f(e))$ for all $e\in R$ where $f(e)$ is
defined. It is convenient to write such a map as
$\rho\succeq^{f}\rho^{\prime}$. Occasionally we shall write
$\rho\succeq\rho^{\prime}$, or the converse $\rho^{\prime}\preceq\rho$, to
mean there is a map of realisations from $\rho$ to $\rho^{\prime}$.

A map of realisations $\rho\succeq^{f}\rho^{\prime}$ factors into a
“projection” followed by a total map

$\rho\succeq^{f_{1}}_{1}\rho_{0}\succeq^{f_{2}}_{2}\rho^{\prime}\,,$

where $\rho_{0}$ stands for the realisation $(R_{0},\leq_{0}),\rho_{0}$ where
$R_{0}={\\{e\in R\ |\ f(e)\hbox{ is defined}\\}}\,$ is the domain of
definition of $f$; $\leq_{0}$ is the restriction of $\leq$; $f_{1}$ is the
inverse relation to the inclusion $R_{0}\subseteq R$; and $f_{2}:R_{0}\to
R^{\prime}$ is the total part of function $f$. We are using $\succeq_{1}$ and
$\succeq_{2}$ to signify the two kinds of maps. Notice that $\succeq_{1}$-maps
are reverse inclusions. Notice too that $\succeq_{2}$-maps are exactly the
total maps of realisations. Total maps $\rho\succeq_{2}^{f}\rho^{\prime}$ are
precisely those functions $f$ from the carrier of $\rho$ to the carrier of
$\rho^{\prime}$ which preserve down-closed subsets and satisfy
$\rho=\rho^{\prime}f$.

###  4.2. Extremal realisations

Let ${\mathcal{A}}$ be a configuration family with underlying set $A$. We
shall say a realisation $\rho$ is extremal when
$\rho\succeq_{2}^{f}\rho^{\prime}$ implies $f$ is an isomorphism, for any
realisation $\rho^{\prime}$; it is called prime extremal when it in addition
has a top element, i.e. its carrier contains an element which dominates all
other elements in the carrier. Intuitively, an extremal realisation is a most
economic causal history associated with its image, a configuration of
${\mathcal{A}}$; it is extremal in being a realisation with minimal causal
dependencies.

Any realisation in ${\mathcal{A}}$ can be coarsened to an extremal
realisation.

######  Lemma 2.

For any realisation $\rho$ there is an extremal realisation $\rho^{\prime}$
with $\rho\succeq_{2}^{f}\rho^{\prime}$.

######  Proof 4.1.

The case when $(R,\leq),\rho$ is finite is straightforward. Assume there
exists $\rho^{\prime}$ such that $\rho\succeq_{2}^{f}\rho^{\prime}$. The
cardinality of ${\\{(a,b)\ |\ a\leq b\\}}$ is necessarily greater or equal to
that of ${\\{(a,b)\ |\ a\leq^{\prime}b\\}}$; it is equal if and only if $\rho$
and $\rho^{\prime}$ are isomorphic. So if we consider a sequence of non-
isomorphic $\rho\succeq_{2}^{f}\rho_{1}\succeq_{2}^{f}\dots$, this sequence is
necessarily finite, of size at most the cardinality of ${\\{(a,b)\ |\ a\leq
b\\}}$. This ensures the existence of an extremal realisation in the finite
case. The infinite case is more subtle, and relies on colimits and Zorn’s
lemma.

The category of realisations with total maps has colimits of total-order
diagrams. A diagram $d$ from a total order $(I,\leq)$ to realisations,
comprises a collection of total maps of realisations $d_{i,j}:d(i)\to d(j)$
when $i\leq j$ s.t. $d_{i,i}$ is always the identity map and if $i\leq j$ and
$j\leq k$ then $d_{i,k}=d_{j,k}\circ d_{i,j}$. We suppose each realisation
$d(i)$ has carrier $(R_{i},\leq_{i})$ with $d(i):R_{i}\to A$. We construct the
colimit realisation of the diagram as follows.

The elements of the colimit realisation consist of equivalence classes of
elements of the disjoint union $R\mathrel{=_{\mathrm{def}}}\biguplus_{i\in
I}R_{i}$ under the equivalence

$(i,e_{i})\sim(j,e_{j})\iff\exists k\in I.\ i\leq k\ \&\ j\leq k\ \&\
d_{i,k}(e_{i})=d_{j,k}(e_{j})\,.$

Consequently we may define a function $\rho_{R}:R\to A$ by taking
$\rho_{R}({\\{e_{i}\\}}_{\sim})=\rho_{i}(e_{i})$. Because every $d_{i,j}$ is a
surjective function, every equivalence class in $R$ has a representative in
$R_{i}$ for every $i\in I$. Moreover, for any $e\in R$ there is $k\in I$ s.t.

${\\{e^{\prime}\in R\ |\
e^{\prime}\leq_{R}e\\}}={\\{{\\{e^{\prime}_{k}\\}}_{\sim}\ |\
e^{\prime}_{k}\leq_{k}e_{k}\\}}\,,$

where $e={\\{e_{k}\\}}_{\sim}$, so is finite. It follows that $\rho_{R}$ is a
realisation. The maps $f_{i}:\rho_{i}\succeq_{2}\rho_{R}$, where $i\in I$,
given by $f_{i}(e_{i})={\\{e_{i}\\}}_{\sim}$ form a colimiting cocone.

Suppose $\rho$ is a realisation. Consider all total-order diagrams $d$ from a
total order $(I,\leq)$ to realisations starting from $\rho$ with $d_{i,j}$ not
an isomorphism if $i<j$. Amongst them, by Zorn’s lemma, there is a maximal
diagram w.r.t. extension. From the maximality of the diagram its colimit is
necessarily extremal. In more detail, construct a colimiting cocone
$f_{i}:d(i)\succeq_{2}\rho_{R}$, $i\in I$, with the same notation as above. By
maximality of the diagram some $f_{k}$ must be an isomorphism; otherwise we
could extend the diagram by adding a top element to the total order and
sending it to $\rho_{R}$. If $j$ should satisfy $k<j$ then $f_{j}\circ
d_{k,j}=f_{k}$ so $f_{k}^{-1}\circ f_{j}\circ d_{k,j}=\textrm{id}_{R_{k}}$. It
would follow that $d_{k,j}$ is injective, as well as surjective, it being a
total map of realisations, and consequently that $d_{k,j}$ is an isomorphism—a
contradiction. Hence $k$ is the maximum element in $(I,\leq)$. If the colimit
were not extremal we could again adjoin a new top element above $k$ thus
extending the diagram—a contradiction.

For example, as a corollary, a countable configuration of a family of
configurations always has an injective extremal realisation. By serialising
the countable configuration, $a_{1}\leq a_{2}\leq\cdots\leq a_{n}\leq\cdots$,
where ${\\{a_{1},\cdots,a_{n}\\}}\in{\mathcal{A}}$ for all $n$, we obtain an
injective realisation $\rho$. By Lemma 2 we can coarsen $\rho$ to an extremal
realisation $\rho^{\prime}$ with $\rho\succeq_{2}^{f}\rho^{\prime}$. As
$\rho=\rho^{\prime}f$ the surjective function $f$ is also injective, so a
bijection, ensuring that the extremal realisation $\rho^{\prime}$ is
injective.

The following rather technical lemma and corollary are crucial.

######  Lemma 3.

Assume $(R,\leq),\rho$, $(R_{0},\leq_{0}),\rho_{0}$ and
$(R_{1},\leq_{1}),\rho_{1}$ are realisations.

  1. (i)

Suppose $f=\rho\succeq_{1}^{f_{1}}\rho_{0}\succeq_{2}^{f_{2}}\rho_{1}$. Then
there are maps so that
$f=\rho\succeq_{2}^{g_{2}}\rho^{\prime}\succeq_{1}^{g_{1}}\rho_{1}$:

$\textstyle{\rho\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f_{1}}$$\scriptstyle{g_{2}}$$\textstyle{\rho^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g_{1}}$$\textstyle{\rho_{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f_{2}}$$\textstyle{\rho_{1}}$

  2. (ii)

Suppose $\rho\succeq_{1}^{f_{1}}\rho_{0}$ where $R_{0}$ is not a down-closed
subset of $R$. Then there are maps so that
$f_{1}=\rho\succeq_{2}^{g_{2}}\rho^{\prime}\succeq_{1}^{g_{1}}\rho_{0}$ with
$g_{2}$ not an isomorphism:

$\textstyle{\rho\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f_{1}}$$\scriptstyle{g_{2}}$$\textstyle{\rho^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g_{1}}$$\textstyle{\rho_{0}}$

######  Proof 4.2.

(i) Construct the realisation $(R^{\prime},\leq^{\prime}),\rho^{\prime}$ as
follows. Define

$R^{\prime}=(R\setminus R_{0})\cup R_{1}$

where w.l.o.g. we assume the sets $R\setminus R_{0}$ and $R_{1}$ are disjoint.
Define $g_{2}:R\to R^{\prime}$ to act as the identity on elements of
$R\setminus R_{0}$ and as $f_{2}$ on elements of $R_{0}$.

When $b\in R\setminus R_{0}$, define

$a\leq^{\prime}b\ \text{ iff }\ \exists a_{0}\in R.\ a_{0}\leq b\ \&\
g_{2}(a_{0})=a\,.$

When $b\in R_{1}$, define

$a\leq^{\prime}b\ \text{ iff }\ a\in R_{1}\ \&\ a\leq_{1}b\,.$

To see $\leq^{\prime}$ is a partial order observe that reflexivity and
antisymmetry follow directly from the corresponding properties of $\leq$ and
$\leq_{1}$. Transitivity requires an argument by cases. For example, in the
most involved case, where

$c\leq^{\prime}a\hbox{ with }a\in R_{1}\hbox{ and }a\leq^{\prime}b\hbox{ with
}b\in R\setminus R_{0}$

we obtain

$c\leq_{1}a\hbox{ and }a_{0}\leq b$

for some $a_{0}\in R_{0}$ with $f_{2}(a_{0})=a$. As $f_{2}$ is surjective and
preserves down-closed subsets,

$c_{0}\leq_{0}a_{0}\hbox{ and }a_{0}\leq b$

for some $c_{0}\in R_{0}$ with $f_{2}(c_{0})=c$. Consequently, $c_{0}\leq b$
with $g_{2}(c_{0})=c$, making $c\leq^{\prime}b$, as required for transitivity.

Define $\rho^{\prime}$ to act as $\rho$ on elements of $R\setminus R_{0}$ and
as $\rho_{1}$ on elements of $R_{1}$. Then $\rho=\rho^{\prime}g_{2}$ directly.
We check $\rho^{\prime}$ preserves down-closed subsets, so is a realisation.
Let $b\in R^{\prime}$. If $b\in R_{1}$ then
$\rho^{\prime}[b]^{\prime}=\rho_{1}[b]_{1}\in{\mathcal{A}}$. If $b\in
R\setminus R_{0}$ then $\rho^{\prime}[b]^{\prime}=\rho g_{2}[b]$ is the image
under $\rho$ of the down-closed subset $g_{2}[b]$, so in ${\mathcal{A}}$.
Because $f_{2}$ preserves down-closed subsets so does $g_{2}$. We already have
$\rho=\rho^{\prime}g_{2}$, making $g_{2}$ a map of realisations
$\rho\succeq_{2}^{g_{2}}\rho^{\prime}$. Define
$g_{1}:R^{\prime}\rightharpoonup R_{1}$ to be the reverse of the inclusion
$R_{1}\subseteq R^{\prime}$. Because $\rho_{1}$ is the restriction of
$\rho^{\prime}$ to $R_{1}$, $g_{1}$ is a map of realisations
$\rho^{\prime}\succeq_{1}^{g_{1}}\rho_{1}$. By construction $f=g_{1}g_{2}$.

(ii) This follows from the construction of
$(R^{\prime}\leq^{\prime}),\rho^{\prime}$ used in (i) but in the special case
where $f_{2}$ is the identity map (with $R_{0}=R_{1}$). Then $R^{\prime}=R$
but $\leq^{\prime}\neq\leq$ as there is $e\in R_{0}$ with
$[e]_{0}\subsetneq[e]$ ensuring that $[e]^{\prime}=[e]_{0}\neq[e]$.

######  Corollary 4.

If $\rho$ is extremal and $\rho\succeq^{f}\rho^{\prime}$, then $\rho^{\prime}$
is extremal and there is $\rho_{0}$ s.t.
$f:\rho\succeq_{1}\rho_{0}\cong\rho^{\prime}$. Moreover, the carrier $R_{0}$
of $\rho_{0}$ is a down-closed subset of the carrier $R$ of $\rho$, with order
the restriction of that on $R$.

######  Proof 4.3.

Directly from Lemma 3. Assume $\rho$ is extremal and
$\rho\succeq^{f}\rho^{\prime}$. We can factor $f$ into
$\rho\succeq_{1}^{f_{1}}\rho_{0}\succeq_{2}^{f_{2}}\rho^{\prime}$. From (i),
if $\rho_{0}$ were not extremal nor would $\rho$ be—a contradiction; hence
$f_{2}$ is an isomorphism. From (ii), the carrier $R_{0}$ of $\rho_{0}$ has to
be a down-closed subset of the carrier $R$ of $\rho$, as otherwise we would
contradict the extremality of $\rho$.

It follows that if $\rho$ is extremal and $\rho\succeq^{f}\rho^{\prime}$ then
$\rho^{\prime}$ is extremal and the inverse relation
$g\mathrel{=_{\mathrm{def}}}f^{-1}$ is an injective function preserving and
reflecting down-closed subsets, i.e. $g[r^{\prime}]=[g(r^{\prime})]$ for all
$r^{\prime}\in R^{\prime}$. In other words:

######  Corollary 5.

If $\rho$ is extremal and $\rho\succeq^{f}\rho^{\prime}$, then $\rho^{\prime}$
is extremal and the inverse $g\mathrel{=_{\mathrm{def}}}f^{-1}$ is a rigid
embedding from the carrier of $\rho^{\prime}$ to the carrier of $\rho$ such
that $\rho^{\prime}=\rho g$.

######  Lemma 6.

Let $(R,\leq),\rho$ be an extremal realisation. Then

  1. (i)

if $r^{\prime}\leq r$ and $\rho(r)=\rho(r^{\prime})$ then $r=r^{\prime}$;

  2. (ii)

if $[r)=[r^{\prime})$ and $\rho(r)=\rho(r^{\prime})$ then $r=r^{\prime}$. Here
$[r)\mathrel{=_{\mathrm{def}}}[r]\setminus{\\{r\\}}$.

######  Proof 4.4.

(i) Suppose $r^{\prime}\leq r$ and $\rho(r)=\rho(r^{\prime})$. By Corollary 5,
we may project to $[r]$ to obtain an extremal realisation $\rho_{0}:[r]\to A$.
Suppose $r$ and $r^{\prime}$ were unequal. We can define a realisation as the
restriction of $\rho_{0}$ to $[r)$. The function from $[r]$ to $[r)$ taking
$r$ to $r^{\prime}$ and otherwise acting as the identity function is a map of
realisations from the realisation $\rho_{0}$ and clearly not an isomorphism,
showing $\rho_{0}$ to be non-extremal—a contradiction. Hence $r=r^{\prime}$,
as required.

(ii) Suppose $[r)=[r^{\prime})$ and $\rho(r)=\rho(r^{\prime})$. Projecting to
$[{\\{r,r^{\prime}\\}}]$ we obtain an extremal realisation. If $r$ and
$r^{\prime}$ were unequal there would be a non-isomorphism map to the
realisation obtained by projecting to $[r]$, viz. the map from
$[{\\{r,r^{\prime}\\}}]$ to $[r]$ sending $r^{\prime}$ to $r$ and fixing all
other elements.

In fact, by modifying condition (i) in the lemma above a little we can obtain
a characterisation of extremal realisations—though not strictly necessary for
the rest of of the paper:

######  Lemma 7.

Let $(R,\leq),\rho$ be a realisation. Then $\rho$ is extremal iff

  1. (i)

if $X\subseteq[r)$, with $X$ down-closed and $r\in R$, and
$\rho(X\cup{\\{r\\}})\in{\mathcal{A}}$ then $X=[r)$; and

  2. (ii)

if $[r)=[r^{\prime})$ and $\rho(r)=\rho(r^{\prime})$ then $r=r^{\prime}$.

######  Proof 4.5.

“Only if”: Assume $\rho$ is extremal. We have already established (ii) in
Lemma 6. To show (i), suppose $X$ is down-closed and $X\subseteq[r)$ in $R$
with $\rho(X\cup{\\{r\\}})\in{\mathcal{A}}$. By Corollary 5, we may project to
$[r]$ to obtain an extremal realisation $\rho_{0}:[r]\to A$. Modify the
restricted order $[r]$ to one in which $r^{\prime}\leq r$ iff $r^{\prime}\in
X\cup{\\{r\\}}$, and is otherwise unchanged. The same underlying function
$\rho_{0}$ remains a realisation, call it $\rho_{0}^{\prime}$, on the modified
order. The identity function gives us a map
$f:\rho_{0}\succeq_{2}\rho_{0}^{\prime}$ which is an isomorphism between
realisations iff $X=[r)$.

“If”: Assume (i) and (ii). Suppose $f:\rho\succeq_{2}\rho^{\prime}$, where
$R^{\prime},\rho^{\prime}$ is a realisation. We show $f$ is injective and
order-preserving. As $f$ is presumed to be surjective and to preserve down-
closed subsets we can then conclude it is an isomorphism.

To see $f$ is injective suppose the contrary that $f(r_{1})=f(r_{2})$ for
$r_{1}\neq r_{2}$. W.l.o.g. we may suppose $r_{1}$ and $r_{2}$ are minimal in
the sense that

$r_{1}^{\prime}\neq r_{2}^{\prime}\ \&\ r_{1}^{\prime}\leq r_{1}\ \&\
r_{2}^{\prime}\leq r_{2}\ \&\ f(r_{1}^{\prime})=f(r_{2}^{\prime})\implies
r_{1}^{\prime}=r_{1}\ \&\ r_{2}^{\prime}=r_{2}\,.$

Define $r^{\prime}\mathrel{=_{\mathrm{def}}}f(r_{1})=f(r_{2})$. Then

$[r^{\prime}]\subseteq f[r_{1}]\ \&\ [r^{\prime}]\subseteq f[r_{2}]\,.$

Furthermore, as only $r^{\prime}$ can be the image of $r_{1}$ and $r_{2}$
under the function $f$,

$[r^{\prime})\subseteq f[r_{1})\ \&\ [r^{\prime})\subseteq f[r_{2})\,.$

It follows that

$[r^{\prime})\subseteq f[r_{1})\cap f[r_{2})=f([r_{1})\cap[r_{2}))$

where the equality is a consequence of the minimality of $r_{1},r_{2}$. Taking
$X\mathrel{=_{\mathrm{def}}}[r_{1})\cap[r_{2})$ we have
$(fX)\cup{\\{r^{\prime}\\}}$ is down-closed in $R^{\prime}$. Therefore

$\rho(X\cup{\\{r_{1}\\}})=\rho^{\prime}f(X\cup{\\{r_{1}\\}})=\rho^{\prime}(fX\cup{\\{r^{\prime}\\}})\in{\mathcal{A}}\,.$

By condition (i), $X=[r_{1})$. Similarly, $X=[r_{2})$, so $[r_{1})=[r_{2})$.
Obviously
$\rho(r_{1})=\rho^{\prime}f(r_{1})=\rho^{\prime}f(r_{1})=\rho(r_{2})$, so we
obtain $r_{1}=r_{2}$ by (ii) —a contradiction, so $f$ is injective.

We now check that $f$ preserves the order. Let $r\in R$. Define

$X\mathrel{=_{\mathrm{def}}}[{\\{r_{1}\leq r\ |\ f(r_{1})<f(r)\\}}]\,,$

where the square brackets signify down-closure in $R$. Then $X$ is down-closed
in $R$ by definition and $X\subseteq[r)$. We have $[f(r)]\subseteq f[r]$
whence

$fX=f[r]\cap[f(r))=[f(r))\,.$

Therefore $fX\cup{\\{f(r)\\}}$ is down-closed in $R^{\prime}$, so

$\rho(X\cup{\\{r\\}})=\rho^{\prime}f(X\cup{\\{r\\}})=\rho^{\prime}(fX\cup{\\{f(r)\\}})\in{\mathcal{A}}\,.$

Hence $X=[r)$, by (i). It follows that

$r_{1}<r\implies r_{1}\in X\implies f(r_{1})<f(r)\hbox{ in }R^{\prime}\,.$

This shows that $f$ preserves the order on $R$.

######  Lemma 8.

There is at most one map between extremal realisations.

######  Proof 4.6.

Let $(R,\leq),\rho$ and $(R^{\prime},\leq^{\prime}),\rho^{\prime}$ be extremal
realisations. Let $f,f^{\prime}:\rho\to\rho^{\prime}$ be maps with converse
relations $g$ and $g^{\prime}$ respectively. We show the two functions $g$ and
$g^{\prime}$ are equal, and hence so are their converses $f$ and $f^{\prime}$.
Suppose otherwise that $g\neq g^{\prime}$. Then there is an $\leq$-minimal
$r^{\prime}\in R^{\prime}$ for which $g(r^{\prime})\neq
g^{\prime}(r^{\prime})$ and $g[r^{\prime})=g^{\prime}[r^{\prime})$. Hence
$[g(r^{\prime}))=[g^{\prime}(r^{\prime}))$ and
$\rho(g(r^{\prime}))=\rho^{\prime}(r^{\prime})=\rho(g^{\prime}(r^{\prime}))$.
As $\rho$ is extremal, by Lemma 6(ii) we obtain
$g(r^{\prime})=g^{\prime}(r^{\prime})$—a contradiction.

Hence extremal realisations of $A$ under $\preceq$ form a preorder. The order
of extremal realisations has as elements isomorphism classes of extremal
realisations ordered according to the existence of a map between
representatives of isomorphism classes. Alternatively, we could take a choice
of representative from each isomorphism class and order these according to
whether there is a map from one to the other. Recall a prime extremal
realisation is an extremal realisation with a top element, i.e. when its
carrier contains an element which dominates all other elements in the carrier.
The following is a direct corollary of Proposition 11 in the next section.

######  Proposition 9.

The order of extremal realisations of a family of configurations
${\mathcal{A}}$ forms a prime-algebraic domain [NPW81] with complete primes
the prime extremal realisations.

The proofs of the following observations are straightforward consequences of
the definitions. They emphasise that prime extremal realisations are a
generalisation of complete primes.

######  Proposition 10.

Let $(A,\leq_{A},\textrm{Con}_{A})$ be a prime event structure. For an
extremal realisation $(R,\leq_{R}),\rho$ of $\>\\!{\mathcal{C}}^{\infty}(A)$,
the function $\rho:R\to\rho R$ is an order isomorphism between $(R,\leq_{R})$
and the configuration $\rho R\in\>\\!{\mathcal{C}}^{\infty}(A)$ ordered by the
restriction of $\leq_{A}$. The function taking an extremal realisation
$(R,\leq_{R}),\rho$ to the configuration $\rho R$ is an order isomorphism from
the order of extremal realisations of $\>\\!{\mathcal{C}}^{\infty}(A)$ to the
configurations of $A$; prime extremal realisations correspond to complete
primes of $\>\\!{\mathcal{C}}^{\infty}(A)$.

A configuration $x\in{\mathcal{F}}$, of a family of configurations
${\mathcal{F}}$, is irreducible iff there is a necessarily unique $e\in x$
such that $\forall y\in{\mathcal{F}},\ e\in y\subseteq x$ implies $y=x$.
Irreducibles coincide with complete (join) irreducibles w.r.t. the order of
inclusion. It is tempting to think of irreducibles as representing minimal
complete enablings. But, as sets, irreducibles both (1) lack sufficient
structure: in the formulation we are led to, of minimal complete enablings as
prime extremal realisations, several prime realisations can have the same
irreducible as their underlying set; and (2) are not general enough: there are
prime realisations whose underlying set is not an irreducible. We conclude
with examples illustrating the nature of extremal realisations; it is
convenient to describe families of configurations by general event structures.
This example shows that prime extremal realisations do not correspond to
irreducible configurations. First, we show a general event structure $E_{0}$
(all subsets consistent) with irreducible configuration ${\\{a,b,c,d\\}}$ and
two (injective) prime extremals $E_{1}$ and $E_{2}$ with tops $d_{1}$ and
$d_{2}$ which both have the same irreducible configuration ${\\{a,b,c,d\\}}$
as their image. The lettering indicates the functions associated with the
realisations, e.g. events $d_{1}$ and $d_{2}$ in the partial orders map to $d$
in the general event structure.

$E_{0}$ |  | $E_{1}$ |  | $E_{2}$ |  | $F_{0}$ |  | $F_{1}$
---|---|---|---|---|---|---|---|---
$\textstyle{d}$$\textstyle{c}$ANDOR$\textstyle{a}$$\textstyle{b}$ |  | $\textstyle{d_{1}}$$\textstyle{c_{1}}$$\textstyle{a}$$\textstyle{b}$ |  | $\textstyle{d_{2}}$$\textstyle{c_{2}}$$\textstyle{a}$$\textstyle{b}$ |  | $\textstyle{d}$$\textstyle{c}$ANDOR$\textstyle{a}$$\textstyle{b}$ |  | $\textstyle{d_{1}}$$\textstyle{c_{1}}$$\textstyle{a}$$\textstyle{b}$

On the other hand there are prime extremal realisations of which the image is
not an irreducible configuration. Consider the general event structure
$F_{0}$. The prime extremal $F_{1}$ describes a situation where $d$ is enabled
by $b$ and $c$, and $c$ is enabled by $a$. It has image the configuration
${\\{a,b,c,d\\}}$ which is not irreducible, being the union of the two
incomparable configurations ${\\{a\\}}$ and ${\\{b,c,d\\}}$.

It is possible to have extremal realisations in which an event depends on an
event of the family having been enabled in two distinct ways, as in the
following prime extremal realisation, on the left; it is clearly not
injective.

$\textstyle{f}$$\textstyle{f}$$\textstyle{AND}$$\textstyle{d}$$\textstyle{e}$$\textstyle{d}$$\textstyle{e}$$\textstyle{c_{1}}$$\textstyle{c_{2}}$$\textstyle{c}$$\textstyle{OR}$$\textstyle{a}$$\textstyle{b}$$\textstyle{a}$$\textstyle{b}$

The extremal describes the event $f$ being enabled by $d$ and $e$ where they
are in turn enabled by different ways of enabling $c$. We assume all subsets
consistent.

##  5\. The causal unfolding: an adjunction from ${\mathcal{E}}_{\equiv}$ to
$\mathcal{F}\\!am_{\equiv}$

Furnished with the concept of extremal realisation, we can now exhibit an
adjunction (precisely, a very simple case of biadjunction or pseudo
adjunction) from ${\mathcal{E}}_{\equiv}$, the category of ese’s, to
$\mathcal{F}\\!am_{\equiv}$, the category of equivalence families. The left
adjoint $I:{\mathcal{E}}_{\equiv}\to\mathcal{F}\\!am_{\equiv}$ is the full and
faithful functor which takes an ese to its family of configurations with the
original equivalence.

The right adjoint, the causal unfolding,
$\textit{er}:\mathcal{F}\\!am_{\equiv}\to{\mathcal{E}}_{\equiv}$ is defined on
objects as follows. Let ${\mathcal{A}}$ be an equivalence family with
underlying set $A$. Define
$\textit{er}({\mathcal{A}})=(P,\textrm{Con}_{P},\leq_{P},\equiv_{P})$ where

  * •

$P$ consists of a choice from within each isomorphism class of the prime
extremals $p$ of ${\mathcal{A}}$ —we write $\textit{top}(p)$ for the image of
the top element in $A$;

  * •

Causal dependency $\leq_{P}$ is $\preceq$ on $P$;

  * •

$X\in\textrm{Con}_{P}$ iff $X\subseteq_{\textrm{fin}}P$ and
$\textit{top}\,[X]_{P}\in{\mathcal{A}}$ —the set $[X]_{P}$ is the
$\leq_{P}$-downwards closure of $X$, so equal to ${\\{p^{\prime}\in P\ |\
\exists p\in X.\ p^{\prime}\preceq p\\}}$;

  * •

$p_{1}\equiv_{P}p_{2}$ iff $p_{1},p_{2}\in P$ and
$\textit{top}(p_{1})\equiv_{A}\textit{top}(p_{2})$.

######  Proposition 11.

The configurations of $P$, ordered by inclusion, are order-isomorphic to the
order of extremal realisations: an extremal realisation $\rho$ corresponds, up
to isomorphism, to the configuration ${\\{p\in P\ |\ p\preceq\rho\\}}$ of $P$;
conversely, a configuration $x$ of $P$ corresponds to an extremal realisation
$\textit{top}:x\to A$ with carrier $(x,\preceq)$, the restriction of the order
of $P$ to $x$.

######  Proof 5.1.

It will be helpful to recall, from Corollary 5, that if
$\rho\succeq^{f}\rho^{\prime}$ between extremal realisations, then the inverse
relation $f^{-1}$ is a rigid embedding of (the carrier of) $\rho^{\prime}$ in
(the carrier of) $\rho$; so $\rho^{\prime}\preceq\rho$ stands for a rigid
embedding. Suppose $x\in\>\\!{\mathcal{C}}^{\infty}(P)$. Then $x$ determines
an extremal realisation

$\theta(x)\mathrel{=_{\mathrm{def}}}\textit{top}:(x,\preceq)\to A\,.$

The function $\theta(x)$ is a realisation because each $p$ in $x$ is, and
extremal because, if not, one of the $p$ in $x$ would fail to be extremal, a
contradiction. Clearly $\rho^{\prime}\preceq\rho$ implies
$\theta(\rho^{\prime})\subseteq\theta(\rho)$. Conversely, it is easily checked
that any extremal realisation $\rho:(R,\leq)\to A$ defines a configuration
${\\{p\in P\ |\ p\preceq\rho\\}}$. If $x\subseteq y$ in
$\>\\!{\mathcal{C}}^{\infty}(P)$ then $\phi(x)\preceq\phi(y)$. It can be
checked that $\theta$ and $\phi$ are mutual inverses, i.e. $\phi\theta(x)=x$
and $\theta\phi(\rho)\cong\rho$ for all configurations $x$ of $P$ and extremal
realisations $\rho$.

From the above proposition we see that the events of
$\textit{er}({\mathcal{A}})$ correspond to the order-theoretic completely-
prime extremal realisations [NPW81]. This justifies our use of the term ‘prime
extremal’ for extremal with top element.

The component of the counit of the adjunction
$\,\epsilon_{A}:I(\textit{er}({\mathcal{A}}))\to{\mathcal{A}}$ is given by the
function

$\,\epsilon_{A}(p)=\textit{top}(p)\,.$

It is a routine check to see that $\,\epsilon_{A}$ preserves $\equiv$ and that
any configuration $x$ of $P$ images under top to a configuration in
${\mathcal{A}}$, moreover in a way that reflects $\equiv$.

######  Theorem 12.

Let ${\mathcal{A}}\in\mathcal{F}\\!am_{\equiv}$. For all
$f:I(Q)\to{\mathcal{A}}$ in $\mathcal{F}\\!am_{\equiv}$, there is a map
$h:Q\to\textit{er}({\mathcal{A}})$ in ${\mathcal{E}}_{\equiv}$ such that
$f=\,\epsilon_{A}\circ I(h)$, i.e. so the diagram

$\textstyle{\mathcal{A}}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces
I(\textit{er}({\mathcal{A}}))}$$\scriptstyle{\,\epsilon_{A}}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces
I(Q)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{I(h)}$

commutes. Moreover, if $h^{\prime}:Q\to\textit{er}({\mathcal{A}})$ is a map in
${\mathcal{E}}_{\equiv}$ s.t. $f\equiv\,\epsilon_{A}\circ I(h^{\prime})$, i.e.
the diagram above commutes up to $\equiv$, then $h^{\prime}\equiv h$.

######  Proof 5.2.

Let $Q=(Q,\textrm{Con}_{Q},\leq_{Q},\equiv_{Q})$ be an ese and
$f:I(Q)\to{\mathcal{A}}$ a map in $\mathcal{F}\\!am_{\equiv}$. We shall define
a map $h:Q\to\textit{er}({\mathcal{A}})$ s.t. $f=\,\epsilon_{A}h$. (As here,
in the proof we shall elide the composition symbol $\circ$, and $I$ on maps
which it leaves unchanged.)

We define the map $h:Q\to\textit{er}({\mathcal{A}})$ by induction on the depth
of $Q$. The depth of an event in an event structure is the length of a longest
$\leq$-chain up to it—so an initial event has depth 1. We take the depth of an
event structure to be the maximum depth of its events. (Because of our
reliance on Lemma 2, we use the axiom of choice implicitly.)

Assume inductively that $h^{(n)}$ defines a map from $Q^{(n)}$ to
$\textit{er}({\mathcal{A}})$ where $Q^{(n)}$ is the restriction of $Q$ to
depth below or equal to $n$ such that $f^{(n)}$ the restriction of $f$ to
$Q^{(n)}$ satisfies $f^{(n)}=\,\epsilon_{A}h^{(n)}$. (In particular, $Q^{(0)}$
is the empty ese and $h^{(0)}$ the empty function.) Then, by Proposition 11,
any configuration $x$ of $Q^{(n)}$ determines an extremal realisation
$\rho_{x}:h^{(n)}x\to A$ with carrier $(h^{(n)}x,\preceq)$.

Suppose $q\in Q$ has depth $n+1$. If $f(q)$ is undefined take $h^{(n+1)}(q)$
to be undefined. Otherwise, note there is an extremal realisation $\rho_{[q)}$
with carrier $(h[q),\preceq)$. Extend $\rho_{[q)}$ to a realisation
$\rho_{[q)}^{\top}$ with carrier that of $\rho_{[q)}$ with a new top element
$\top$ adjoined, and make $\rho_{[q)}^{\top}$ extend the function $\rho_{[q)}$
by taking $\top$ to $f(q)$. By Lemma 2, there is an extremal realisation
$\rho$ such that $\rho_{[q)}^{\top}\succeq_{2}\rho$. Because $\rho_{[q)}$ is
extremal, $\rho\succeq_{1}\rho_{[q)}$, so $\rho$ only extends the order of
$\rho_{[q)}$ with extra dependencies of $\top$. (For notational simplicity we
identify the carrier of $\rho$ with the set $h[q)\cup{\\{\top\\}}$.) Project
$\rho$ to the extremal with top $\top$. Define this to be the value of
$h^{(n+1)}(q)$. In this way, we extend $h^{(n)}$ to a partial function
$h^{(n+1)}:Q^{(n+1)}\to\textit{er}({\mathcal{A}})$ such that
$f^{(n+1)}=\,\epsilon_{A}h^{(n+1)}$. To see that $h^{(n+1)}$ is a map we can
use Proposition 1. By construction $h^{(n+1)}$ satisfies property (ii) of
Proposition 1 and the other properties are inherited fairly directly from $f$
via the definition of $\textit{er}({\mathcal{A}})$.

Defining $h=\bigcup_{n\in\omega}h^{(n)}$ we obtain a map
$h:Q\to\textit{er}({\mathcal{A}})$ such that $f=\,\epsilon_{A}h$.

Suppose $h^{\prime}:Q\to\textit{er}({\mathcal{A}})$ is a map s.t.
$f\equiv\,\epsilon_{A}h^{\prime}$. Then, for any $q\in Q$,

$\textit{top}(h^{\prime}(q))=\,\epsilon_{A}h^{\prime}(q)\equiv_{A}f(q)=\,\epsilon_{A}h(q)=\textit{top}(h(q))\,,$

so $h^{\prime}(q)\equiv_{P}h(q)$ in $\textit{er}({\mathcal{A}})$. Thus
$h^{\prime}\equiv h$.

The theorem does not quite exhibit a traditional adjunction, because the usual
cofreeness condition specifying an adjunction is weakened to only having
uniqueness up to $\equiv$. However the condition it describes does specify an
exceedingly simple case of a pseudo adjunction (or biadjunction) between
2-categories—a set together with an equivalence relation (a setoid) is a very
simple example of a category. As a consequence, whereas the usual cofreeness
condition allows us to extend the right adjoint to arrows, so obtaining a
functor, in this case following that same line will only yield a pseudo
functor er as right adjoint: thus extended, er will only preserve composition
and identities up to $\equiv$.

The map $(P,\equiv)\to\textit{er}(\>\\!{\mathcal{C}}^{\infty}(P),\equiv)$
which takes $p\in P$ to the realisation with carrier $([p],\leq)$, the
restriction of the causal dependency of $P$, with the inclusion function
$[p]\hookrightarrow P$ is an isomorphism; recall from Proposition 10 that the
configurations of a prime event structure correspond to its extremal
realisations. Such maps furnish the components of the unit of the pseudo
adjunction:

$\textstyle{{\mathcal{E}}_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{I}$$\scriptstyle{\top}$$\textstyle{\mathcal{F}\\!am_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$er

On the right we show a general event structure (all subsets consistent) and on
its left its causal unfolding to an ese under er ; the unfolding’s events are
the prime extremals.777See [dV15] for further examples of the causal unfolding
including an inductive characterisation in 5.2.2.

$\textstyle{d_{1}}$$\textstyle{d_{2}}$$\textstyle{d}$$\textstyle{c_{1}}$$\textstyle{c_{2}}$$\textstyle{c}$$\scriptstyle{AND}$$\textstyle{{OR}}$$\textstyle{a}$$\textstyle{b}$$\textstyle{a}$$\textstyle{b}$

##  6\.  Unfolding general event structures

Recall $\mathcal{G}$ is the category of general event structures. We obtain a
pseudo adjunction from ${\mathcal{E}}_{\equiv}$ to $\mathcal{G}$ via an
adjunction from $\mathcal{F}\\!am_{\equiv}$ to $\mathcal{G}$. The right
adjoint ${\it fam}:\mathcal{G}\to\mathcal{F}\\!am_{\equiv}$ is most simply
described. Given $(E,\textrm{Con},\vdash)$ in $\mathcal{G}$ it returns the
equivalence family $(\>\\!{\mathcal{C}}^{\infty}(E),=)$ in
$\mathcal{F}\\!am_{\equiv}$ comprising the configurations together with the
identity equivalence between events that appear within some configuration; the
partial functions between events that are maps in $\mathcal{G}$ are
automatically maps in $\mathcal{F}\\!am_{\equiv}$—the action of ${\it fam}$ on
maps.

For the effect of the left adjoint ${\it
col}:\mathcal{F}\\!am_{\equiv}\to\mathcal{G}$ on objects, define the collapse

${\it col}({\mathcal{A}})\mathrel{=_{\mathrm{def}}}(E,\textrm{Con},\vdash)$

where

  * •

$E=A_{\equiv}$, the equivalence classes of events in
$A\mathrel{=_{\mathrm{def}}}\bigcup{\mathcal{A}}$ ;

  * •

$X\in\textrm{Con}$ iff
$X\subseteq_{\textrm{fin}}y_{\equiv}\mathrel{=_{\mathrm{def}}}{\\{{\\{a\\}}_{\equiv}\
|\ a\in y\\}}$, for some $y\in{\mathcal{A}}$ ; and

  * •

$X\vdash e$ iff $e\in E$, $X\in\textrm{Con}$ and $e\in y_{\equiv}\subseteq
X\cup{\\{e\\}}$, for some $y\in{\mathcal{A}}$.

It follows that $y_{\equiv}$ is a configuration of ${\it col}({\mathcal{A}})$
whenever $y\in{\mathcal{A}}$. From this it is easy to see that ${\it
col}({\mathcal{A}})$ is a replete general event structure.

Let $({\mathcal{A}},\equiv)\in\mathcal{F}\\!am_{\equiv}$. Assume that
${\mathcal{A}}$ has underlying set $A$. The unit of the adjunction is defined
to have typical component $\eta_{A}:({\mathcal{A}},\equiv)\to{\it fam}({\it
col}({\mathcal{A}},\equiv))$ given by $\eta_{A}(a)={\\{a\\}}_{\equiv}\,.$ It
is easy to check that $\eta_{A}$ is a map in $\mathcal{F}\\!am_{\equiv}$.

######  Theorem 13.

Suppose that $B=(B,\textrm{Con}_{B},\vdash_{B})\in\mathcal{G}$ and that
$g:({\mathcal{A}},\equiv)\to(\>\\!{\mathcal{C}}^{\infty}(B),=)$ is a map in
$\mathcal{F}\\!am_{\equiv}$. Then, there is a unique map $k:{\it
col}({\mathcal{A}},\equiv)\to B$ in $\mathcal{G}$ such that the diagram

$\textstyle{({\mathcal{A}},\equiv)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\eta_{A}}$$\scriptstyle{g}$$\textstyle{{\it
fam}({\it
col}({\mathcal{A}},\equiv))\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{{\it
fam}(k)}$$\textstyle{(\>\\!{\mathcal{C}}^{\infty}(B),=)}$

commutes.

######  Proof 6.1.

The map $k:{\it col}({\mathcal{A}},\equiv)\to B$ is given as the function
$k(e)=g(a)\hbox{ where }e={\\{a\\}}_{\equiv}\,.$ It is easily checked to be a
map in $\mathcal{G}$ and moreover to be the unique map from ${\it
col}({\mathcal{A}},\equiv)$ to $B$ making the above diagram commute.

Theorem 13 determines an adjunction:

$\textstyle{\mathcal{F}\\!am_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{{\it
col}}$$\scriptstyle{\top}$$\textstyle{\mathcal{G}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{{\it
fam}}$

The construction ${\it col}$ automatically extends from objects to maps; maps
in $\mathcal{F}\\!am_{\equiv}$ preserve equivalence so collapse to functions
preserving equivalence classes. The counit of the adjunction has components
$\,\epsilon_{E}:{\it col}((\>\\!{\mathcal{C}}^{\infty}(E),=))\to E$ which send
singleton equivalence classes ${\\{e\\}}$ to $e$. The counit is an isomorphism
at precisely those general event structures $E$ which are replete, so cuts
down to a reflection from the subcategory of replete general event structures
into equivalence families.

Composing

$\textstyle{{\mathcal{E}}_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{I}$$\scriptstyle{\top}$$\textstyle{\mathcal{F}\\!am_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$er$\scriptstyle{{\it
col}}$$\scriptstyle{\top}$$\textstyle{\mathcal{G}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{{\it
fam}}$

we obtain a pseudo adjunction

$\textstyle{{\mathcal{E}}_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\top}$$\textstyle{\mathcal{G}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\,.}$

Its right adjoint constructs the causal unfolding of a general event
structure.

The composite pseudo adjunction from ${\mathcal{E}}_{\equiv}$ to $\mathcal{G}$
cuts down to a reflection, in the sense that the counit is a natural
isomorphism, when we restrict to the subcategory of $\mathcal{G}$ where all
general event structures are replete. Then the right adjoint provides a pseudo
functor embedding replete general event structures (and so families of
configurations) in ese’s.

This concludes the construction of causal unfoldings of (very general)
equivalence-families, and, in particular, general event structures.

We can ask for those extra axioms an ese should satisfy in order that it
arises from a general event structure; an axiomatisation is given in Appendix
C.

##  7\. Pullbacks of ese’s?

A major motivation has been to develop probabilistic strategies with parallel
causes. In the composition of strategies the constructions of (pseudo)
pullback and hiding play a crucial role. In composing strategies, essentially
by playing them off against each other—the role of (pseudo) pullbacks, it is
important to hide the moves associated with this interaction. Do event
structures with equivalence, ${\mathcal{E}}_{\equiv}$, support these
constructions?

Ese’s do support hiding. Let $(P,\leq,\textrm{Con}_{P},\equiv)$ be an ese. Let
$V\subseteq P$ be a $\equiv$-closed subset of ‘visible’ events. Define the
projection of $P$ on $V$, to be
$P{\mathbin{\downarrow}}V\mathrel{=_{\mathrm{def}}}(V,\leq_{V},\textrm{Con}_{V},\equiv_{V})$,
where $v\leq_{V}v^{\prime}\hbox{ iff }v\leq v^{\prime}\ \&\ v,v^{\prime}\in V$
and $X\in\textrm{Con}_{V}\hbox{ iff }X\in\textrm{Con}\ \&\ X\subseteq V$ and
$v\equiv_{V}v^{\prime}\hbox{ iff }v\equiv v^{\prime}\ \&\ v,v^{\prime}\in V$.

Hiding is associated with a factorisation of partial maps. Let $f$ be a
partial map from $(P,\leq_{P},\textrm{Con}_{P},\equiv_{P})$ to
$(Q,\leq_{Q},\textrm{Con}_{Q},\equiv_{Q})$. Letting
$V\mathrel{=_{\mathrm{def}}}{\\{e\in E\ |\ f(e)\hbox{ is defined}\\}}$, the
map $f$ factors into the composition

$\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f_{0}}$$\textstyle{P{\mathbin{\downarrow}}V\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f_{1}}$$\textstyle{Q}$

of $f_{0}$, a partial map of ese’s taking $p\in P$ to itself if $p\in V$ and
undefined otherwise, and $f_{1}$, a total map of ese’s acting like $f$ on $V$.
We call $f_{1}$ the defined part of the partial map $f$. Because
$\equiv$-equivalent maps share the same domain of definition,
$\equiv$-equivalent maps will determine the same projection and
$\equiv$-equivalent defined parts. The factorisation is characterised to
within isomorphism by the following universal characterisation: for any
factorisation
$\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g_{0}}$$\textstyle{P_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g_{1}}$$\textstyle{Q}$
where $g_{0}$ is partial and $g_{1}$ is total there is a (necessarily total)
unique map $h:P{\mathbin{\downarrow}}V\to P_{1}$ such that we obtain the
commuting diagram

$\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f_{0}}$$\scriptstyle{g_{0}}$$\textstyle{P{\mathbin{\downarrow}}V\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\scriptstyle{f_{1}}$$\textstyle{Q}$$\textstyle{P_{1}\,.\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g_{1}}$

By analogy with early work on prime event structures and their representation
by stable families [Win82, Win86] we might hope to obtain pullbacks and pseudo
pullbacks in ${\mathcal{E}}_{\equiv}$ via the adjunction to
$\mathcal{F}\\!am_{\equiv}$. The category $\mathcal{F}\\!am_{\equiv}$ has
pullbacks and pseudo pullbacks which are easy to construct—see Section 7.3.

But unfortunately (pseudo) pullbacks in $\mathcal{F}\\!am_{\equiv}$ don’t
provide us with (pseudo) pullbacks in ${\mathcal{E}}_{\equiv}$ because the
right adjoint is only a pseudo functor: in general it will only carry pseudo
pullbacks to bipullbacks. While ${\mathcal{E}}_{\equiv}$ does have bipullbacks
(in which commutations and uniqueness are only up to the equivalence $\equiv$
on maps) it doesn’t always have pseudo pullbacks or pullbacks—Appendix B.
Whereas pseudo pullbacks and pullbacks are characterised up to isomorphism,
bipullbacks are only characterised up to a weaker equivalence—that induced on
objects by the equivalence on maps.888Objects $P$ and $Q$ are equivalent iff
there are two maps $f:P\to Q$, $g:Q\to P$ s.t. $gf\equiv\textrm{id}_{P}$ and
$fg\equiv\textrm{id}_{Q}$.

We explore subcategories of ${\mathcal{E}}_{\equiv}$, in particular w.r.t.
whether they support (pseudo) pullbacks.

###  7.1. Subcategories of ${\mathcal{E}}_{\equiv}$

Consider the following successively weaker axioms on an ese
$(P,\textrm{Con},\leq,\equiv)$:

  * Ax0.  ${\\{p_{1},p_{2}\\}}\in\textrm{Con}\ \&\ p_{1}\equiv p_{2}\implies p_{1}=p_{2}\,.$

  * Ax1.  $p_{1},p_{2}\leq p\ \&\ p_{1}\equiv p_{2}\implies p_{1}=p_{2}\,.$

  * Ax2.  $p_{1}\leq p_{2}\ \&\ p_{1}\equiv p_{2}\implies p_{1}=p_{2}\,.$

Ax0 says that any two prime causes of disjunctive event are mutually
exclusive. Ax2 we have met as a consequence of a realisation being extremal
(Lemma 6(i)) so it will always hold of any image under the construction er.
Ax1 forbids any prime cause from depending on two distinct prime causes of a
common disjunctive event; while it does not hold of all extremal realisations
(see Example 4.2) and so can fail in an image under the construction er, Ax1
enforces a form atomicity on disjunctive events: whereas several prime causes
of a disjunctive event may appear in a configuration, no other event is
permitted to detect and react on the occurrence of a nontrivial conjunction of
prime causes of the disjunctive event.

Restricting to the full subcategories of ${\mathcal{E}}_{\equiv}$ satisfying
these axioms we obtain ${\mathcal{E}}_{\equiv}^{0}$,
${\mathcal{E}}_{\equiv}^{1}$ and ${\mathcal{E}}_{\equiv}^{2}$ respectively.
The factorisation of maps we met for ${\mathcal{E}}_{\equiv}$ is inherited by
all the subcategories as their respective axioms are preserved by the
projection operation. So all the subcategories support hiding.

The full inclusion functors

${\mathcal{E}}_{\equiv}^{0}\hookrightarrow{\mathcal{E}}_{\equiv}^{1}\hookrightarrow{\mathcal{E}}_{\equiv}^{2}\hookrightarrow{\mathcal{E}}_{\equiv}$

all have right adjoints so forming a chain of coreflections. Essentially the
right adjoints work by restricting the structures to that part satisfying the
stronger axiom. The adjunctions are enriched in the sense that the associated
natural isomorphisms preserve and reflect the equivalence $\equiv$ between
maps.

For example, ${\mathcal{E}}_{\equiv}^{0}$ is the full subcategory of
${\mathcal{E}}_{\equiv}$ in which objects $(P,\textrm{Con},\leq,\equiv)$
satisfy the strongest axiom Ax0. Consequently its maps are traditional maps of
event structures which preserve equivalence. The inclusion functor
${\mathcal{E}}_{\equiv}^{0}\hookrightarrow{\mathcal{E}}_{\equiv}$ has a right
adjoint $r:{\mathcal{E}}_{\equiv}\to{\mathcal{E}}_{\equiv}^{0}$ taking
$Q=(Q,\textrm{Con}_{Q},\leq_{Q},\equiv_{Q})$ to
$(Q^{\prime},\textrm{Con}^{\prime},\leq^{\prime},\equiv^{\prime})$ where

  * •

$Q^{\prime}$ consists of all $q\in Q$ s.t. $q_{1}\not\equiv_{Q}q_{2}$ for all
$q_{1},q_{2}\leq_{Q}q$;

  * •

$X\in\textrm{Con}^{\prime}$ iff $X\subseteq Q^{\prime}$ and
$X\in\textrm{Con}_{Q}$ and $q_{1}\not\equiv_{Q}q_{2}$ for all $q_{1},q_{2}\in
X$;

  * •

$\leq^{\prime}$ and $\equiv^{\prime}$ are the restrictions of $\leq_{Q}$ and
$\equiv_{Q}$ to $Q^{\prime}$.

The adjunction is enriched in the sense that the isomorphism

${\mathcal{E}}_{\equiv}^{0}(P,r(Q))\cong{\mathcal{E}}_{\equiv}^{0}(P,Q)\,,$

natural in $P\in{\mathcal{E}}_{\equiv}^{0}$ and $Q\in{\mathcal{E}}_{\equiv}$,
preserves and reflects the equivalence $\equiv$ between maps.

As a consequence we obtain an adjunction from ${\mathcal{E}}_{\equiv}^{0}$ to
$\mathcal{G}$. The universality of counit is only up to $\equiv$.999It was
falsely claimed in [Win86] that the ‘inclusion’ of the category of prime event
structures in that of general event structures had a right adjoint. The
adjunction from ${\mathcal{E}}_{\equiv}^{0}$ to $\mathcal{G}$ corrects that
originally incorrect idea; though the repair is at the cost of uniqueness up
to $\equiv$.

The most important subcategory for us is ${\mathcal{E}}_{\equiv}^{1}$. Amongst
the subcategories of ${\mathcal{E}}_{\equiv}$ it is the smallest extension of
prime event structures which supports parallel causes and hiding. Its objects
are called event structures with disjunctive causes (edc’s) [dVW17]. The right
adjoint to the inclusion

${\mathcal{E}}_{\equiv}^{1}\hookrightarrow{\mathcal{E}}_{\equiv}$

on objects simply restricts them to those events which satisfy Ax1. In
general, within ${\mathcal{E}}_{\equiv}$ we lose the local injectivity
property that we’re used to seeing for maps of event structures. However for
${\mathcal{E}}_{\equiv}^{1}$ we recover local injectivity w.r.t. prime
configurations $[p]$. If $f:P\to Q$ is a map in ${\mathcal{E}}_{\equiv}^{1}$,
then

$p_{1},p_{2}\in[p]\ \&\ f(p_{1})=f(p_{2})\implies p_{1}=p_{2}\,.$

In the composite adjunctions from ${\mathcal{E}}_{\equiv}^{1}$ to
$\mathcal{F}\\!am_{\equiv}$, and from ${\mathcal{E}}_{\equiv}^{1}$ to
$\mathcal{G}$, the right adjoint has the effect of restricting to those
extremal realisations within which Ax1 holds; recall that the prime extremal
realisations of an equivalence family ${\mathcal{A}}$ correspond to the
configurations of $\textit{er}({\mathcal{A}})$. Because such prime extremals
are necessarily injective functions their carriers can be taken to be
configurations of the equivalence family or general event structure of which
they are realisations. Appendix C.1 provides an axiomatisation of those edc’s
which arise from general event structures.

As we shall see, ${\mathcal{E}}_{\equiv}^{1}$ also has pullbacks and pseudo
pullbacks. It is within ${\mathcal{E}}_{\equiv}^{1}$ that we have developed
probabilistic distributed strategies with parallel causes [dVW17, Win16]. The
coreflection from ${\mathcal{E}}_{\equiv}^{0}$ to ${\mathcal{E}}_{\equiv}^{1}$
is helpful in thinking about constructions like pullback and pseudo pullback
in ${\mathcal{E}}_{\equiv}^{1}$ as its right adjoint will preserve such
limits. In the category ${\mathcal{E}}_{\equiv}^{0}$, maps coincide with the
traditional maps of labelled event structures, regarding events as labelled by
their equivalence classes. Constructions such as pullback are already very
familiar in ${\mathcal{E}}_{\equiv}^{0}$. What changes in the corresponding
constructions in ${\mathcal{E}}_{\equiv}^{1}$ is the manner of dealing with
consistency.

While not strictly a subcategory of ${\mathcal{E}}_{\equiv}$, we should also
mention the relationship with the category $\mathcal{E}$ of traditional event
structures. There is an obvious ‘inclusion’ functor from the category of event
structures $\mathcal{E}$ to the category ${\mathcal{E}}_{\equiv}^{0}$; it
takes an event structure to the same event structure but with the identity
equivalence adjoined. Regarding ${\mathcal{E}}_{\equiv}^{0}$ as a category, so
dropping the enrichment by equivalence relations, the ‘inclusion’ functor

$\mathcal{E}\hookrightarrow{\mathcal{E}}_{\equiv}^{0}$

has a right adjoint, viz. the forgetful functor which simply drops the
equivalence $\equiv$ from the ese. The adjunction is a coreflection because
the inclusion functor is full. Of course it is no longer the case that the
adjunction is enriched: the natural bijection of the adjunction cannot respect
the equivalence on maps.

The adjunction

$\mathcal{E}\hookrightarrow{\mathcal{E}}_{\equiv}^{1}$

is obtained as the composite of the adjunctions from $\mathcal{E}$ to
${\mathcal{E}}_{\equiv}^{0}$ and ${\mathcal{E}}_{\equiv}^{0}$ to
${\mathcal{E}}_{\equiv}^{1}$ and is necessarily not enriched. Despite this the
adjunction from $\mathcal{E}$ to ${\mathcal{E}}_{\equiv}^{1}$ has been useful
in relating strategies based on edc’s to strategies based on event structures.
Its right adjoint, the functor forgetting equivalence, preserves all limits
and especially pullbacks important in composing strategies. While this does
not entail that composition of strategies is preserved by the forgetful
functor—because the forgetful functor does not commute with hiding, it gives
us a strong relationship, between composition of strategies before and after
applying the forgetful functor [Win16].

###  7.2. Edc’s and stable ef’s—a coreflection

The closeness of edc’s to event structures suggests a generalisation of stable
families to aid with constructions such as product, pullback and pseudo
pullback in $\mathcal{E\\!S}^{1}$.101010It is hard to define the product and
pullback of prime event structures directly. However the category of prime
event structures is in coreflection with the category of stable families where
product and pullback are easily defined; for example, the product of event
structures is then obtained as the image under the right adjoint of the
product of their stable families of configurations [Win82, Win86].

We are fortunate in that the complicated pseudo adjunction between ese’s and
ef’s restricts to a much simpler adjunction, in fact a coreflection, between
edc’s and stable ef’s now defined.

In an equivalence family $({\mathcal{A}},\equiv_{A})$ say a configuration
$x\in{\mathcal{A}}$ is unambiguous iff $\forall a_{1},a_{2}\in x.\
a_{1}\equiv_{A}a_{2}\implies a_{1}=a_{2}\,$. An equivalence family
$({\mathcal{A}},\equiv_{A})$, with underlying set of events $A$, is stable iff
it satisfies

$\forall x,y,z\in{\mathcal{A}}.\ \ x,y\subseteq z\ \&\ z$ is unambiguous
$\,\Rightarrow\,x\cap y\in{\mathcal{A}}$ ,  and
---
$\forall a\in A,x\in{\mathcal{A}}.\ \,a\in x\,\Rightarrow\exists
z\in{\mathcal{A}},\,z$ is unambiguous $\&\,a\in z\subseteq x\,$.

Given the other axioms of an ef, we can deduce the seemingly stronger property

$\emptyset\neq X\subseteq{\mathcal{A}},z\in{\mathcal{A}}.\ (\forall x\in X.\
x\subseteq z)\ \&\ z\hbox{ is unambiguous }\implies\bigcap
X\in{\mathcal{A}}\,$

of a stable ef ${\mathcal{A}}$.

In effect, a stable equivalence family contains a stable subfamily of
unambiguous configurations out of which all other configurations are
obtainable as unions. Local to any unambiguous configuration $x$ there is a
partial order on its events $\leq_{x}$: each $a\in x$ determines a prime
configuration

$[a]_{x}\mathrel{=_{\mathrm{def}}}\bigcap{\\{y\in{\mathcal{A}}\ |\ a\in
y\subseteq x\\}}\,,$

the minimum set of events on which $a$ depends within $x$; taking $a\leq_{x}b$
iff $[a]_{x}\subseteq[b]_{x}$ defines causal dependency between $a,b\in x$.
Write $\mathcal{S\\!F}\\!am_{\equiv}$ for the subcategory of stable ef’s.

The configurations of an edc with its equivalence are easily seen to form a
stable ef providing a full and faithful embedding of $\mathcal{E\\!D\\!C}$ in
$\mathcal{S\\!F}\\!am_{\equiv}$. The embedding has a right adjoint $\Pr$. It
is built out of prime extremals but we can take advantage of the fact that in
a stable ef unambiguous prime extremals have the simple form of prime
configurations. From a stable ef$({\mathcal{A}},\equiv_{A})$ we produce an edc
$\Pr({\mathcal{A}},\equiv_{A})=_{{\rm def}}(P,\textrm{Con},\leq,\equiv)$ in
which $P$ comprises the prime configurations with

  * •

$[a]_{x}\equiv[a^{\prime}]_{x^{\prime}}\hbox{ iff }a\equiv_{A}a^{\prime}\,,$

  * •

$Z\in\textrm{Con}\hbox{ iff }Z\subseteq P\ \&\ \bigcup
Z\in{\mathcal{F}}\,,\hbox{ and}$

  * •

$p\leq p^{\prime}\hbox{ iff }p,p^{\prime}\in P\ \&\ p\subseteq p^{\prime}$ .

The adjunction is enriched in the sense that its natural bijection preserves
and reflects the equivalence on maps:

$\textstyle{\mathcal{E\\!D\\!C}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\top}$$\textstyle{\mathcal{S\\!F}\\!am_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\Pr}$

Compare the definition above with that of $\Pr$ on stable families. The
significant difference is in the way that consistency is defined; in the
construction on a stable ef the consistency is inherited not from the stable
family of unambiguous configurations but from the ambient ef ${\mathcal{A}}$
in which configurations may not be unambiguous.

A stable equivalence family ${\mathcal{A}}$ contains a stable subfamily ${\it
unamb}({\mathcal{A}})$ of unambiguous configurations out of which all other
configurations are obtainable as unions. There is an obvious ‘inclusion’
functor from the category of stable families $\mathcal{S\\!F}\\!am$ to
$\mathcal{S\\!F}\\!am_{\equiv}$; it takes a stable family ${\mathcal{A}}$,
with underlying set $A$, to the stable ef $({\mathcal{A}},\textrm{id}_{A})$.
Its has ${\it unamb}$ as a right adjoint:

$\textstyle{\mathcal{S\\!F}\\!am\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\top}$$\textstyle{\mathcal{S\\!F}\\!am_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\,.}$$\scriptstyle{{\it
unamb}}$

As the ‘inclusion’ functor from $\mathcal{S\\!F}\\!am$ to
$\mathcal{S\\!F}\\!am_{\equiv}$ is full the adjunction is a coreflection. The
adjunction is not enriched in the sense that its natural bijection ignores the
equivalence on maps present in $\mathcal{S\\!F}\\!am_{\equiv}$. As right
adjoints preserve limits, the stable family of unambiguous configurations of
the product, or pullback, of stable ef’s is the product, respectively
pullback, in stable families of the unambiguous configurations of the
components.

We can now obtain a (pseudo) pullback in edc’s by first forming the (pseudo)
pullback of the stable ef’s obtained as their configurations and then taking
its image under the right adjoint $\Pr$.

###  7.3. Constructions

We make use of the constructions of product, pullback and pseudo pullback of
ef’s; just as with prime event structures we cannot expect such constructions
to be easily achieved directly on ese’s. The constructions of product and
pullback of ef’s will reduce to product and pullback on families of
configurations when we take the equivalences $\equiv$ to be the identity
relation. On stable families they reduce to the product and pullback of stable
families [Win82, Win86].

The product of ef’s is given as follows. Let ${\mathcal{A}}$ and
${\mathcal{B}}$ be ef’s with underlying sets $A$ and $B$. Their product will
have underlying set $A\times_{*}B$, the product of $A$ and $B$ in sets with
partial functions with projections $\pi_{1}$ to $A$ and $\pi_{2}$ to $B$. We
take $c\equiv c^{\prime}$ in $A\times_{*}B$ iff
$\pi_{1}c\equiv\pi_{1}c^{\prime}$, or both are undefined, and
$\pi_{2}c\equiv\pi_{2}c^{\prime}$, or both are undefined. Define the
configurations of the product by: $x\in{\mathcal{A}}\times{\mathcal{B}}$ iff

  * •

$x\subseteq A\times_{*}B$ such that

  * •

$\pi_{1}x\in{\mathcal{A}}\ \&\ \pi_{2}x\in{\mathcal{B}}\,,$

  * •

$\forall c,c^{\prime}\in x.\ \pi_{1}(c)\equiv_{A}\pi_{1}(c^{\prime})\hbox{ or
}\pi_{2}(c)\equiv_{B}\pi_{2}(c^{\prime})\implies c\equiv c^{\prime}\,$ and

  * •

$\forall c\in x\exists c_{1},\cdots,c_{n}\in x.\ c_{n}=c\ \&\ \\\ \hbox{\
}\,\quad\forall i\leq n.\ \pi_{1}{\\{c_{1},\cdots,c_{i}\\}}\in{\mathcal{A}}\
\&\ \pi_{2}{\\{c_{1},\cdots,c_{i}\\}}\in{\mathcal{B}}\,.$

We obtain the product in stable ef’s by restricting to those configurations of
the product of the stable ef’s which are unions of unambiguous configurations.
Notice that unambiguous configurations of the product of stable ef’s are
exactly the configurations in the product in stable families of the
subfamilies of unambiguous configurations.

Restriction w.r.t. sets of events which are closed under $\equiv$ and
synchronised compositions are defined analogously to before. In particular we
obtain pullbacks and bipullbacks as restrictions of the product.

Pullbacks exist in general but we concentrate on pullbacks of total maps. Let
$f:{\mathcal{A}}\to{\mathcal{C}}$ and $g:{\mathcal{B}}\to{\mathcal{C}}$ be
total maps of ef’s. Assume ${\mathcal{A}}$ and ${\mathcal{B}}$ have underlying
sets $A$ and $B$. Define $D\mathrel{=_{\mathrm{def}}}{\\{(a,b)\in A\times B\
|\ f(a)=g(b)\\}}$ with projections $\pi_{1}$ and $\pi_{2}$ to the left and
right components. On $D$, take $d\equiv_{D}d^{\prime}$ iff
$\pi_{1}(d)\equiv_{A}\pi_{1}(d^{\prime})$ and
$\pi_{2}(d)\equiv_{B}\pi_{2}(d^{\prime})$. Define a family of configurations
of the pullback to consist of $x\in{\mathcal{D}}$ iff

  * •

$x\subseteq D$ such that

  * •

$\pi_{1}x\in{\mathcal{A}}\ \&\ \pi_{2}x\in{\mathcal{B}}\,,$ and

  * •

$\forall d\in x\exists d_{1},\cdots,d_{n}\in x.\ d_{n}=d\ \&\ \\\ \hbox{\
}\,\quad\forall i\leq n.\ \pi_{1}{\\{d_{1},\cdots,d_{i}\\}}\in{\mathcal{A}}\
\&\ \pi_{2}{\\{d_{1},\cdots,d_{i}\\}}\in{\mathcal{B}}\,.$

The pullback in stable ef’s is again obtained by restricting to those
configurations which are unions of unambiguous configurations. The unambiguous
configurations in the pullback of stable ef’s are obtained as the pullback in
stable families of the subfamilies of unambiguous configurations.

Given that maps are related by an equivalence relation it is sensible to
broaden our constructions to pseudo pullbacks—the universal characterisation
of pseudo pullback follows the concrete construction.

Pseudo pullbacks of total maps $f:{\mathcal{A}}\to{\mathcal{C}}$ and
$g:{\mathcal{B}}\to{\mathcal{C}}$ of ef’s are obtained in a similar way to
pullbacks. Assume ${\mathcal{A}}$ and ${\mathcal{B}}$ have underlying sets $A$
and $B$. Define $D\mathrel{=_{\mathrm{def}}}{\\{(a,b)\in A\times B\ |\
f(a)\equiv_{C}g(b)\\}}$ with projections $\pi_{1}$ and $\pi_{2}$ to the left
and right components. On $D$, take $d\equiv_{D}d^{\prime}$ iff
$\pi_{1}(d)\equiv_{A}\pi_{1}(d^{\prime})$ and
$\pi_{2}(d)\equiv_{B}\pi_{2}(d^{\prime})$. Define a family of configurations
of the pseudo pullback to consist of $x\in{\mathcal{D}}$ iff

  * •

$x\subseteq D$ such that

  * •

$\pi_{1}x\in{\mathcal{A}}\ \&\ \pi_{2}x\in{\mathcal{B}}\,,$ and

  * •

$\forall d\in x\exists d_{1},\cdots,d_{n}\in x.\ d_{n}=d\ \&\ \\\ \hbox{\
}\,\quad\forall i\leq n.\ \pi_{1}{\\{d_{1},\cdots,d_{i}\\}}\in{\mathcal{A}}\
\&\ \pi_{2}{\\{d_{1},\cdots,d_{i}\\}}\in{\mathcal{B}}\,.$

When ${\mathcal{A}}$ and ${\mathcal{B}}$ are stable ef’s we obtain their
pseudo pullback by restricting to those configurations obtained as the union
of unambiguous configurations.

Recall the universal property of a pseudo pullback of
$f:{\mathcal{A}}\to{\mathcal{C}}$ and $g:{\mathcal{B}}\to{\mathcal{C}}$ (in
this simple case). A pseudo pullback comprises two maps
$\pi_{1}:{\mathcal{D}}\to{\mathcal{A}}$ and
$\pi_{2}:{\mathcal{D}}\to{\mathcal{B}}$ such that $f\pi_{1}\equiv g\pi_{2}$
with the universal property that given any two maps
$p_{1}:{\mathcal{D}}^{\prime}\to{\mathcal{A}}$ and
$p_{2}:{\mathcal{D}}^{\prime}\to{\mathcal{B}}$ such that $fp_{1}\equiv gp_{2}$
there is a unique map $h:{\mathcal{D}}^{\prime}\to{\mathcal{D}}$ such that
$p_{1}=\pi_{1}h$ and $p_{2}=\pi_{2}h$:

|
---|---
$\textstyle{{\mathcal{D}}^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p_{2}}$$\scriptstyle{p_{1}}$$\scriptstyle{h}$$\textstyle{{\mathcal{D}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{=}$$\scriptstyle{=}$$\scriptstyle{\pi_{2}}$$\scriptstyle{\pi_{1}}$$\textstyle{{\mathcal{A}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{\equiv}$$\textstyle{{\mathcal{B}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\textstyle{\mathcal{C}}$

Pseudo pullbacks are defined up to isomorphism. Pseudo pullbacks coincide with
pullbacks when the maps involved have an event structure as their common
codomain.

Fortunately we do have both pullbacks and pseudo pullbacks in the subcategory
${\mathcal{E}}_{\equiv}^{1}$. The constructions of pullbacks and pseudo
pullbacks in ${\mathcal{E}}_{\equiv}^{1}$ can by-pass the complicated er
construction and be done via the corresponding constructions in
$\mathcal{S\\!F}\\!am_{\equiv}$ in the manner familiar from event structures
and stable families. This is because we have an adjunction from
${\mathcal{E}}_{\equiv}^{1}$ to $\mathcal{S\\!F}\\!am_{\equiv}$ and moreover
an adjunction which is enriched with respect the equivalence on homsets. So,
for example, to form the (pseudo) pullback of ese’s in
${\mathcal{E}}_{\equiv}^{1}$ we regard their configurations as stable ef’s,
form the (pseudo) pullback in $\mathcal{S\\!F}\\!am_{\equiv}$ and take the
image under the right adjoint $\Pr$. Each stable ef includes a subfamily of
unambiguous configurations and it is fortunate indeed that e.g. the subfamily
of unambiguous configurations of the pullback of stable ef’s
$f:{\mathcal{A}}\to{\mathcal{C}}$ and $g:{\mathcal{B}}\to{\mathcal{C}}$ is got
as the pullback in stable families of $f$ and $g$ between the subfamilies of
unambiguous configurations.

##  8\. Conclusion

This completes our exploration of extensions of event structures to support
disjunctive and especially parallel causes. We summarise the models and
adjunctions we have met in a figure.

|  |
---|---
|
$\textstyle{{\mathcal{E}}_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{I}$$\scriptstyle{\top}$$\textstyle{\mathcal{F}\\!am_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$er$\scriptstyle{{\it
col}}$$\scriptstyle{\top}$$\textstyle{\mathcal{G}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{{\it
fam}}$$\textstyle{{\mathcal{E}}_{\equiv}^{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\vdash}$$\textstyle{{\mathcal{E}}_{\equiv}^{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\top}$$\scriptstyle{\vdash}$$\textstyle{\mathcal{S\\!F}\\!am_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\Pr}$$\scriptstyle{{\it
unamb}}$$\textstyle{{\mathcal{E}}_{\equiv}^{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\vdash}$$\textstyle{{\mathcal{E}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\vdash}$$\scriptstyle{\top}$$\textstyle{\mathcal{S\\!F}\\!am\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\vdash}$$\scriptstyle{\Pr}$

The adjunction
$\textstyle{{\mathcal{E}}_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{I}$$\scriptstyle{\top}$$\textstyle{\mathcal{F}\\!am_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$er
is a proper pseudo adjunction.

The adjunctions
$\textstyle{{\mathcal{E}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\top}$$\textstyle{{\mathcal{E}}_{\equiv}^{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
and
$\textstyle{\mathcal{S\\!F}\\!am\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\top}$$\textstyle{\mathcal{S\\!F}\\!am_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{{\it
unamb}}$
are not enriched in the sense that the natural bijection does not respect the
equivalence $\equiv$ on maps.

The adjunctions of the figure bridge between the two “classical” models of
prime event structures $\mathcal{E}$ and general event structures
$\mathcal{G}$; the former appropriate when each event has a unique cause, the
latter permitting causes in parallel. The other “classical” model of stable
families $\mathcal{S\\!F}\\!am$ supports exclusive disjunctive causes; an
event may be enabled in several, though incompatible, ways. Equivalence
families $\mathcal{F}\\!am_{\equiv}$ and its subcategories provide us with
constructions of product and (pseudo) pullback. All the categories to the left
of the figure, subcategories of ese’s ${\mathcal{E}}_{\equiv}$, have the
partial-total factorisation property used to support an operation of hiding.
The category ${\mathcal{E}}_{\equiv}^{1}$ of edc’s distinguishes itself in
also having pullbacks and pseudo pullbacks. It thus answered the original
motivation for our search, to find a model in which to develop strategies with
parallel causes. The category ${\mathcal{E}}_{\equiv}^{1}$ supports hiding and
probability, has pullbacks, pseudo pullbacks and through this leads to a
robust definition of probabilistic strategies with parallel causes [dVW17,
Win16]. The tools described here have been essential in carrying out that
programme. While parallel causes are ubiquitous, their more formal treatment
has been rather sparse. The techniques of this paper should be relevant
wherever causal models allowing parallel causes are in use.

Acknowledgments Thanks to the anonymous referees. Thanks to Simon Castellan,
Pierre Clairambault, Ioana Cristescu, Mai Gehrke, Jonathan Hayman, Tamas
Kispeter, Jean Krivine, Martin Hyland and Daniele Varacca for discussions,
advice and encouragement; to ENS Paris for supporting Marc de Visme’s
internship; and to the ERC for Advanced Grant ECSYM.

## References

  * [CCW17] Simon Castellan, Pierre Clairambault, and Glynn Winskel.  Observably deterministic concurrent strategies and intensional full abstraction for parallel-or.  In FSCD 2017, volume 84 of LIPIcs, pages 12:1–12:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [CKV15] Ioana Cristescu, Jean Krivine, and Daniele Varacca.  Rigid families for CCS and the pi-Calculus.  In International Colloquium on Theoretical Aspects of Computing ICTAC, 12th ed. Cali, Colombia, 2015.
  * [Cri15] Ioana Cristescu.  Operational and denotational semantics for the reversible pi-calculus.  PhD thesis, PPS, Université Paris Diderot, 2015.
  * [DFF+12] Vincent Danos, Jerome Feret, Walter Fontana, Russell Harmer, Jonathan Hayman, Jean Krivine, Chris Thompson-Walsh, and Glynn Winskel.  Graphs, Rewriting and Pathway Reconstruction for Rule-Based Models.  In FSTTCS 2012, volume 18 of LIPIcs, pages 276–288. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012.
  * [dV15] Marc de Visme.  Cambridge internship report, ENS Paris.  Available from Glynn Winskel’s homepage http://www.cl.cam.ac.uk/$\sim$gw104/mdv-report.pdf, 2015.
  * [dVW17] Marc de Visme and Glynn Winskel.  Strategies with parallel causes.  In CSL 2017, volume 82 of LIPIcs. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017.
  * [Kel82] G. M. Kelly.  Basic concepts of enriched category theory.  LNM 64. CUP, 1982.
  * [KP14] Y. Kinoshita and J. Power.  Category theoretic structure of setoids.  TCS, 546, 2014.
  * [NPW81] Mogens Nielsen, Gordon Plotkin, and Glynn Winskel.  Petri nets, event structures and domains.  TCS, 13:85–108, 1981.
  * [Pea13] Judea Pearl.  Causality.  CUP, 2013.
  * [Pow98] John Power.  2-categories.  BRICS Notes Series NS-98-7, 1998.
  * [Win80] Glynn Winskel.  Events in computation.  Edinburgh University, 1980.  PhD thesis, Edinburgh.
  * [Win82] Glynn Winskel.  Event structure semantics for CCS and related languages.  In ICALP 9, volume 140 of LNCS. Full version available as University of Aarhus, CS Technical Report 1983, and from http://www.cl.cam.ac.uk/$\sim$gw104/eventStructures82.pdf, 1982.
  * [Win86] Glynn Winskel.  Event structures.  In Advances in Petri Nets, LNCS 255, 1986.
  * [Win16] Glynn Winskel.  ECSYM Notes: Event Structures, Stable Families and Concurrent Games.  http://www.cl.cam.ac.uk/$\sim$gw104/ecsym-notes.pdf, 2016.
  * [WN95] Glynn Winskel and Mogens Nielsen.  Models for concurrency.  In Samson Abramsky and Dov Gabbay, editors, Semantics and Logics of Computation. OUP, 1995.

##  Appendix A Equiv-enriched categories

Here we explain in more detail what we mean when we say “enriched in the
category of sets with equivalence relations” and employ terms such as
“enriched adjunction,” “pseudo adjunction” and “pseudo pullback.” The classic
text on enriched categories is [Kel82], but for this paper the articles [KP14]
and [Pow98] provide short, accessible introductions to the notions we use from
Equiv-enriched categories and 2-categories, respectively.

Equiv is the category of equivalence relations. Its objects are
$(A,\equiv_{A})$ comprising a set $A$ and an equivalence relation $\equiv_{A}$
on it. Its maps $f:(A,\equiv_{A})\to(B,\equiv_{B})$ are total functions
$f:A\to B$ which preserve equivalence.

We shall use some basic notions from enriched category theory [Kel82]. We
shall be concerned with categories enriched in Equiv, called Equiv-enriched
categories, in which the homsets possess the structure of equivalence
relations, respected by composition [KP14]. This is the sense in which we say
categories are enriched in (the category of) equivalence relations. We
similarly borrow the concept of an Equiv-enriched functor between Equiv-
enriched categories for a functor which preserves equivalence in acting on
homsets. An Equiv-enriched adjunction is a usual adjunction in which the
natural bijection of the adjunction preserves and reflects equivalence.

Because an object in Equiv can be regarded as a (very simple) category, we can
regard Equiv-enriched categories as (very simple) 2-categories to which
notions from 2-categories apply [Pow98].

A pseudo functor between Equiv-enriched categories is like a functor but the
usual laws only need hold up to equivalence. A pseudo adjunction (or
biadjunction) between 2-categories permits a weakening of the usual natural
isomorphism between homsets, now also categories, to a natural equivalence of
categories. In the special case of a pseudo adjunction between Equiv-enriched
categories the equivalence of homset categories amounts to a pair of
$\equiv$-preserving functions whose compositions are $\equiv$-equivalent to
the identity function. With traditional adjunctions, by specifying the action
of one adjoint solely on objects, we determine it as a functor; with pseudo
adjunctions we can only determine it as a pseudo functor—in general a pseudo
adjunction relates two pseudo functors. Pseudo adjunctions compose in the
expected way. An Equiv-enriched adjunction is a special case of a 2-adjunction
between 2-categories and a very special case of pseudo adjunction. In Section
6 we compose an Equiv-enriched adjunction with a pseudo adjunction to obtain a
new pseudo adjunction.

Similarly we can specialise the notions pseudo pullbacks and bipullbacks from
2-categories to Equiv-enriched categories which is highly relevant to the
companion paper [dVW17] in which we use pullbacks and pseudo pullbacks to
compose strategies with parallel causes. Let $f:A\to C$ and $g:B\to C$ be two
maps in an Equiv-enriched category. A pseudo pullback of $f$ and $g$ is an
object $D$ and maps $p:D\to A$ and $q:D\to B$ such that $f\circ p\equiv g\circ
q$ which satisfy the further property that for any $D^{\prime}$ and maps
$p^{\prime}:D^{\prime}\to A$ and $q^{\prime}:D^{\prime}\to B$ such that
$f\circ p^{\prime}\equiv g\circ q^{\prime}$, there is a unique map
$h:D^{\prime}\to D$ such that $p^{\prime}=p\circ h$ and $q^{\prime}=q\circ h$;
note the insistence on the last two equalities, rather than just equivalences.
There is an obvious weakening of pseudo pullbacks to the situation in which
the uniqueness is replaced by uniqueness up to $\equiv$ and the equalities by
$\equiv$—these are simple special cases of bilimits called bipullbacks.

Right adjoints in a 2-adjunction preserve pseudo pullbacks whereas right
adjoints in a pseudo adjunction are only assured to preserve bipullbacks.

##  Appendix B On (pseudo) pullbacks of ese’s

We show that the enriched category of ese’s ${\mathcal{E}}_{\equiv}$ does not
always have pullbacks and pseudo pullbacks of maps $f:A\to C$ and $g:B\to C$,
the reason why we use the subcategory $\mathcal{E\\!D\\!C}$, which does, as a
foundation on which to develop strategies with parallel causes. It suffices to
exhibit the lack of pullbacks when $C$ is an (ese of an) event structure as
then pullbacks and pseudo pullbacks coincide. Take $A$, $B$, $C$ as below,
with the obvious maps $f:A\to C$ and $g:B\to C$ (given by the lettering). In
fact, $A$ and $B$ are edc’s.

ese A |  | ese B |  | ese C |  | edc P
---|---|---|---|---|---|---
$\textstyle{a1}$$\textstyle{a2}$$\textstyle{b1}$$\textstyle{b2}$$\textstyle{c1}$$\textstyle{c2}$$\textstyle{d}$$\textstyle{e}$ |  | $\textstyle{a}$$\textstyle{b}$$\textstyle{c}$$\textstyle{d}$$\textstyle{e}$ |  | $\textstyle{a}$$\textstyle{b}$$\textstyle{c}$$\textstyle{d}$$\textstyle{e}$ |  | $\textstyle{a1}$$\textstyle{a2}$$\textstyle{b1}$$\textstyle{b2}$$\textstyle{c1}$$\textstyle{c2}$$\textstyle{d}$$\textstyle{e}$

The pullback in edc’s $\mathcal{E\\!D\\!C}$ does exist and is given by $P$
with the obvious projection maps. However this is not a pullback in
${\mathcal{E}}_{\equiv}$. Consider the ese D with the obvious total maps to
$A$ and $B$; they form a commuting square with $f$ and $g$. This cannot factor
through $P$: event $b2$ has to be mapped to $b2$ in $P$, but then $a1$ cannot
be mapped to $a1$ (it wouldn’t yield a map) nor to $a2$ (it would violate
commutation required of a pullback).

ese D |  | ese bP |  | ese E
---|---|---|---|---
$\textstyle{a1}$$\textstyle{b1}$$\textstyle{b2}$$\textstyle{c1}$$\textstyle{c2}$$\textstyle{d}$$\textstyle{e}$ |  | $\textstyle{a1}$$\textstyle{a2^{\prime}}$$\textstyle{a1^{\prime}}$$\textstyle{a2}$$\textstyle{b1}$$\textstyle{b2}$$\textstyle{c1}$$\textstyle{c2}$$\textstyle{d}$$\textstyle{e}$ |  | $\textstyle{a1}$$\textstyle{b1}$$\textstyle{b2}$$\textstyle{c1}$$\textstyle{c2}$$\textstyle{d}$$\textstyle{e}$

There is a bipullback $bP$ got by applying the pseudo functor er to the
pullback in ef’s. But this is not a pullback because in the ese $E$ the
required mediating map is not unique in that $a1$ can go to either $a1$ or
$a1^{\prime}$. In fact, there is no pullback of $f$ and $g$. To show this we
use the additional ese F.

Suppose $Q$ with projection maps to $A$ and $B$ were a pullback of $f$ and $g$ in ${\mathcal{E}}_{\equiv}$. Consider the three ese’s $D$, $E$ and $F$ with their obvious maps to $A$ and $B$; in each case they form a commuting square with $f$ and $g$. There are three unique maps $h_{D}:D\to Q$, $h_{E}:E\to Q$, and $h_{F}:F\to Q$ such that the corresponding pullback diagrams commute. We remark that there are also obvious maps $k_{D}:E\to D$ and $k_{F}:E\to F$ (given by the lettering) which commute with the maps to the components $A$ and $B$. By uniqueness, we have $h_{D}\circ k_{D}=h_{E}=h_{F}\circ k_{F}$, so we have $h_{D}(a1)=h_{F}(a1)$. From the definition of the maps, the event $h_{D}(a1)=h_{F}(a1)$ has at most one $\leq$-predecessor in $Q$ which is sent to $b$ in $C$ (as $D$ only has one). Because of the projection to $B$, it has at least one (as $B$ has one). So the event $h_{D}(a1)=h_{F}(a1)$ has exactly one predecessor which is sent to $b$. From the definition of maps, this event is $h_{D}(b2)$ which equals $h_{F}(b1)$. But $h_{D}(b2)$ cannot equal $h_{F}(b1)$ as they go to two different events of $A$ —a contradiction. |  ese F

$\textstyle{a1}$$\textstyle{b1}$$\textstyle{b2}$$\textstyle{c1}$$\textstyle{c2}$$\textstyle{d}$$\textstyle{e}$
---|---

Hence there can be no pullback of $f$ and $g$ in ${\mathcal{E}}_{\equiv}$. (By
adding intermediary events, we would encounter essentially the same example in
the composition, before hiding, of strategies if they were to be developed
within the broader category of ese’s.)

##  Appendix C General event structures as ese’s

The pseudo adjunction

$\textstyle{{\mathcal{E}}_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\top}$$\textstyle{\mathcal{G}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\,.}$

cuts down to a reflection, in which the counit is a natural isomorphism, when
we restrict to the subcategory of $\mathcal{G}$ where all general event
structures are replete. The right adjoint provides a full and faithful
embedding of replete general event structures (and so families of
configurations) in ese’s.

We can ask on what subcategory of ${\mathcal{E}}_{\equiv}$ the pseudo
adjunction further cuts down to a pseudo equivalence with the category of
replete general event structures. We do this by characterising those ese’s
which are obtained to within isomorphism as images of replete general event
structures under the right adjoint, or equivalently as images of families of
configurations.

The characterising axioms on an ese $(P,\leq,\textrm{Con},\equiv)$ are:

  * (A)

For $X$ a finite down-closed subset of $P$,
$X\equiv y\ \&\ y\in\>\\!{\mathcal{C}}(P)\implies X\in\>\\!{\mathcal{C}}(P)$ ;

  * (B)

For $p,q\in P$, $[p)=[q)\ \&\ p\equiv q\implies p=q$ ;

  * (C)

For $X$ a down-closed subset of $P$ and $p\equiv q$,
$X\subseteq[p)\ \&\ [q)_{\equiv}\subseteq X_{\equiv}\implies X=[p)$ ;

  * (D)

For $x\in\>\\!{\mathcal{C}}(P)$ and $t\in P$,
$x\cup[t]\in\>\\!{\mathcal{C}}(P)\ \&\
(x\cup[t])_{\equiv}=x_{\equiv}\cup{\\{{\\{t\\}}_{\equiv}\\}}\implies\exists
p\in P.\ p\equiv t\ \&\ x\cup{\\{p\\}}\in\>\\!{\mathcal{C}}(P)$ .

In writing the axioms we have used expressions such as $X\equiv Y$, for
subsets $X$ and $Y$ of $P$, to mean for any $p\in X$ there is $q\in Y$ with
$p\equiv q$ and vice versa; and $X_{\equiv}$ to stand for the set of
$\equiv$-equivalence classes ${\\{{\\{p\\}}_{\equiv}\ |\ p\in X\\}}$; so
$X\equiv Y$ iff $X_{\equiv}=Y_{\equiv}$.

Axiom (D) may be replaced by

  * (D′)

For $x,y\in\>\\!{\mathcal{C}}(P)$ and $t\in P$,
$x{\stackrel{{\scriptstyle
t}}{{\mathrel{-}\joinrel\relbar\joinrel\subset\,}}}\ \&\ x\equiv
y\implies\exists p\in P.\ p\equiv t\ \&\
x\cup{\\{p\\}}\in\>\\!{\mathcal{C}}(P)$ .

Assume (D) and, for $x,y\in\>\\!{\mathcal{C}}(P)$, that
$x{\stackrel{{\scriptstyle
t}}{{\mathrel{-}\joinrel\relbar\joinrel\subset\,}}}$ and $x\equiv y$. Then, by
(A), $y\cup[t]\in\>\\!{\mathcal{C}}(P)$ as $y\cup[t]\equiv x\cup{\\{t\\}}$,
clearly consistent; whence $y\cup{\\{p\\}}\in\>\\!{\mathcal{C}}(P)$ for some
$p$ by (D). Conversely, assuming (D′) and $x\cup[t]\in\>\\!{\mathcal{C}}(P)$
and $(x\cup[t])_{\equiv}=x_{\equiv}\cup{\\{{\\{t\\}}_{\equiv}\\}}$, in the
case where $t\notin x$ we obtain $x\cup[t){\stackrel{{\scriptstyle
t}}{{\mathrel{-}\joinrel\relbar\joinrel\subset\,}}}$ and $x\cup[t)\equiv x$;
whence $x\cup{\\{p\\}}\in\>\\!{\mathcal{C}}(P)$ for some $p$ by (D′). This
shows $(D)$ follows from (D′) in the case when $t\notin x$; in the case when
$t\in x$, axiom (D) is obvious.

######  Theorem 14.

Let $P\in{\mathcal{E}}_{\equiv}$. Then, $P\cong\textit{er}({\mathcal{A}})$ for
some equivalence family ${\mathcal{A}}$ iff $P$ satisfies axioms (A), (B), (C)
and (D).

######  Proof C.1.

We show axioms (A), (B), (C), (D) hold of any ese
$P=\textit{er}({\mathcal{A}})$, constructed from a family of configurations
${\mathcal{A}}$. We obtain $P$ satisfies axiom (A) from the way the
consistency of $\textit{er}({\mathcal{A}})$ is defined: if $X\equiv y$, with
$y$ a configuration, $X$ inherits consistency from $y$ ensuring that $X$,
assumed down-closed, is a configuration. If $[p)=[q)$ and $p\equiv q$, then
$p$ and $q$ correspond to the same extremal realisation with top, so are
equal—ensuring (B) holds of $P$. We obtain (C) via Lemma 7(i), as $[p]$
corresponds to an extremal with top $p$. Given the correspondence between
configurations of $P$ and extremal realisations, axiom (D) expresses an
obvious extension property of extremal realisations.

Conversely, we now show that if an ese $P=(P,\textrm{Con},\leq,\equiv)$
satisfies (A), (B), (C), (D) then there is an isomorphism

$\eta_{P}:P\cong\textit{er}({\mathcal{A}})$

if we take the family of configurations so

${\mathcal{A}}=\>\\!{\mathcal{C}}^{\infty}({\it
col}(\>\\!{\mathcal{C}}^{\infty}(P),\equiv))\,.$

Recall, from Proposition 11, that the configurations of
$\textit{er}({\mathcal{A}})$ correspond to extremal realisations of ${\it
col}(\>\\!{\mathcal{C}}^{\infty}(P),\equiv)$.

Before we define the map $\eta_{P}$ we remark that a configuration $x$ of $P$
determines an extremal realisation of ${\it
col}(\>\\!{\mathcal{C}}^{\infty}(P),\equiv)$: the realisation has carrier $x$
with order inherited from $P$ and map taking $p\in x$ to the equivalence class
${\\{p\\}}_{\equiv}$. Axioms (B) and (C) ensure that this realisation is
extremal, via Lemma 7.

It follows from the remark that we define a map
$\eta_{P}:P\to\textit{er}({\mathcal{A}})$ by sending $p\in P$ to the
realisation with carrier $[p]$, ordered as in $P$, and function $[p]\to
P_{\equiv}$ taking elements to their equivalence classes. The injectivity of
$\eta_{P}$ follows from (B). Moreover $\eta_{P}$ reflects consistency because
of axiom (A). We now only require its surjectivity to ensure $\eta_{P}$ is an
isomorphism.

We use (D) in showing that $\eta_{P}$ is surjective. We show by induction on
$n\in\omega$ that all extremal realisations with top of ${\it col}(P)$ of
depth less than $n$ are in the image of $\eta_{P}$. (Recall the depth of an
event in an event structure is the length of a longest $\leq$-chain up to it;
we take the depth of an event structure to be the maximum depth of its
events.) Because $\eta_{P}$ reflects consistency the induction hypothesis
entails that all extremal realisations of depth less than $n$ are (up to
isomorphism) in the image under $\eta_{P}$ of configurations of $P$.

Let $(R,\leq_{R})$ of depth $n$ with $\rho:R\to{\it col}(P)$ be an extremal
realisation with top $r$, so $R=[r]_{R}$. Then its restriction
$\rho^{\prime}:[r)_{R}\to{\it col}(P)$ is an extremal realisation of lesser
depth. By induction there is $x^{\prime}\in\>\\!{\mathcal{C}}(P)$ and an
isomorphism of realisations
$\theta^{\prime}:\rho^{\prime}\cong\eta_{P}x^{\prime}$. Write
$y\mathrel{=_{\mathrm{def}}}\rho^{\prime}[r)_{R}$,
$z\mathrel{=_{\mathrm{def}}}\rho[r]_{R}$. Then $y,z\in\>\\!{\mathcal{C}}({\it
col}(P))$ and $y{\stackrel{{\scriptstyle
e}}{{\mathrel{-}\joinrel\relbar\joinrel\subset\,}}}z$ for some $e\in
P_{\equiv}$. From the definition of ${\it col}(P)$, it follows fairly directly
that there is some $t\in P$ s.t. ${\\{t\\}}_{\equiv}=e$ and
$[t)_{\equiv}\subseteq y$. As $\eta_{P}$ reflects consistency,
$x^{\prime}\cup[t]\in\>\\!{\mathcal{C}}(P)$. We have

$(x^{\prime}\cup[t])_{\equiv}=x^{\prime}_{\equiv}\cup{\\{{\\{t\\}}_{\equiv}\\}}=z\,.$

By (D) there is some $p\in P$ s.t. $p\equiv t$ and
$x^{\prime}\cup{\\{p\\}}\in\>\\!{\mathcal{C}}(P)$. The configuration
$x\mathrel{=_{\mathrm{def}}}x^{\prime}\cup{\\{p\\}}$ with order inherited from
$P$ and map taking $p^{\prime}\in x$ to ${\\{p^{\prime}\\}}_{\equiv}$ is the
realisation $\eta_{P}x$. Let $\theta$ be the function $\theta:R\to x$
extending $\theta^{\prime}$ s.t. $\theta(r)=p$. Then
$\theta:\rho\succeq\eta_{P}x$ is a map of realisations. But $\rho$ is extremal
ensuring $\theta:\rho\cong\eta_{P}x$, and that $\eta_{P}$ is surjective.

######  Corollary 15.

The pseudo adjunction from ${\mathcal{E}}_{\equiv}$ to $\mathcal{G}$ cuts down
to a pseudo equivalence of categories between the subcategory of
${\mathcal{E}}_{\equiv}$ satisfying axioms (A), (B), (C), (D) and the
subcategory of $\mathcal{G}$ comprising the replete general event structures.

###  C.1. General event structures as edc’s

The composite

$\textstyle{{\mathcal{E}}_{\equiv}^{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\top}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\mathcal{E}}_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{I}$$\scriptstyle{\top}$$\textstyle{\mathcal{F}\\!am_{\equiv}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$er$\scriptstyle{{\it
col}}$$\scriptstyle{\top}$$\textstyle{\mathcal{G}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{{\it
fam}}$

forms pseudo adjunction from edc’s to general event structures; we call its
composite right adjoint edc. As above we can cut this down to a pseudo
equivalence between the subcategory ${\mathcal{E}}_{\equiv}^{1}$ of edc’s and
replete general event structures via a slight modification of Axiom (D) on
ese’s $(P,\leq,\textrm{Con},\equiv)$:

  * (D1)

For $x$ an unambiguous configuration in $\>\\!{\mathcal{C}}(P)$ and $t\in P$,
$x\cup[t]\in\>\\!{\mathcal{C}}(P)\ \&\
(x\cup[t])_{\equiv}=x_{\equiv}\cup{\\{{\\{t\\}}_{\equiv}\\}}\implies\exists
p\in P.\ p\equiv t\ \&\ x\cup{\\{p\\}}\in\>\\!{\mathcal{C}}(P)$ .

Axiom (D1) may be replaced by

  * (D${}_{1}^{\prime}$)

For $x,y\in\>\\!{\mathcal{C}}(P)$, with $y$ unambiguous, and $t\in P$,
$x{\stackrel{{\scriptstyle
t}}{{\mathrel{-}\joinrel\relbar\joinrel\subset\,}}}\ \&\ x\equiv
y\implies\exists p\in P.\ p\equiv t\ \&\
x\cup{\\{p\\}}\in\>\\!{\mathcal{C}}(P)$ .

######  Theorem 16.

Let $P$ be an edc. Then, $P\cong\textrm{edc}(G)$ for some general event
structure $G$ iff $P$ satisfies axioms (A), (B), (C) and (D1).

######  Proof C.2.

The proof is a slight refinement of the proof of Theorem 14 above.

######  Corollary 17.

The pseudo adjunction from ${\mathcal{E}}_{\equiv}$ to $\mathcal{G}$ cuts down
to a pseudo equivalence of categories between the subcategory of edc’s
${\mathcal{E}}_{\equiv}^{1}$ satisfying axioms (A), (B), (C), (D1) and the
subcategory of $\mathcal{G}$ comprising the replete general event structures.