1.

$$\forall p\in \underset{―}{E},\downarrow p\in {\mathcal{C}}^{\mathrm{o}}(E)$$

This stems from the fact that $\downarrow p$ is:

• finite by definition of $E$ being an event structure
• down-closed, by transitivity of ${\le }_E$

• consistent, as

  • $\{p\}\in {\mathrm{Con}}_E$

  • and by the third property of ${\mathrm{Con}}_E$ (with $x=\{p\}$): $\forall p_1\in \downarrow p,\{p,p_1\}\in {\mathrm{Con}}_E$

    as a result of which, by a straightforward recurrence (by setting $x=\{p,p_1\},\dots ,\{p,p_1,\cdots ,p_n\}$):

    $$\forall p_1,\dots ,p_n\in \downarrow p,\{p,p_1,\dots ,p_n\}\in {\mathrm{Con}}_E$$

    so by closure under inclusion:

    $$\forall p_1,\dots ,p_n\in \downarrow p,\underset{\text{any finite subset of }\downarrow p\text{ is of this form}}{\underbrace{\{p_1,\dots ,p_n\}}}\in {\mathrm{Con}}_E$$

2.

A finite subset of events is in the consistency relation iff it occurs as a subset of a finite configuration.

• $⟹$: if $x\in {\mathrm{Con}}_E$, then $x\subseteq \downarrow x\stackrel{\scriptscriptstyle\mathrm{def}}{=}\bigcup _{e\in x}\downarrow e$, which is:

  • finite, as it is a finite ($x$ is finite) union of finite (by the event structure definition) sets
  • down-closed, by transitivity of ${\le }_E$

  • consistent: like in the first exercise (and since any subset of $x$ is in ${\mathrm{Con}}_E$ by closure by inclusion), we can show by recurrence that for all $y\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{e^{(1)},\dots ,e^{(k)}\}\in {\mathcal{P}}_{\mathrm{f}\mathrm{i}\mathrm{n}}(x)$:

    $$\begin{array}{c}\forall e_1^{(1)},\dots ,e_{n_1}^{(1)},\dots ,e_1^{(k)},\cdots ,e_{n_k}^{(k)}\in \downarrow x,\\ y\cup \{e_1^{(1)},\dots ,e_{n_1}^{(1)},\dots ,e_1^{(k)},\cdots ,e_{n_k}^{(k)}\}\in {\mathrm{Con}}_E\end{array}$$

    which implies, by closure under inclusion, that:

    $$\begin{array}{c}\forall e_1^{(1)},\dots ,e_{n_1}^{(1)},\dots ,e_1^{(k)},\cdots ,e_{n_k}^{(k)}\in \downarrow x,\\ \underset{\text{any finite subset of }\downarrow x\text{ is of this form}}{\underbrace{\{e_1^{(1)},\dots ,e_{n_1}^{(1)},\dots ,e_1^{(k)},\cdots ,e_{n_k}^{(k)}\}}}\in {\mathrm{Con}}_E\end{array}$$

• $⟸$: owing to the fact that any configuration is consistent.

3.

For all $e,e^{\prime }\in \underset{―}{E}$, we have: $e\le e^{\prime }⟺(\forall x\in {\mathcal{C}}^{\mathrm{o}}(E),e^{\prime }\in x⟹e\in x)$

• $⟹$: it’s due to the fact that $x$ is down-closed, as a configuration.

• $⟸$: with $x\stackrel{\scriptscriptstyle\mathrm{def}}{=}\downarrow e^{\prime }$, it results that $e\in \downarrow e^{\prime }$, i.e. $e\le e^{\prime }$

4.

For any map $f:E⟶F$:

$$\forall e\in \underset{―}{E},\downarrow fe\subseteq f(\downarrow e)$$

$\downarrow fe$ is the smallest configuration containing $fe$, since

• it is a configuration
• for any configuration $y$ such that $fe\in y$, $\downarrow fe\subseteq y$ as $y$ is down-closed

And:

• as $f$ preserves configurations, $f[\downarrow e]$ is also a configuration
• $fe\in f[\downarrow e]$

so the result follows by minimality of $\downarrow fe$.

5.

For any map $f:E⟶F$:

$$\forall x\subseteq \underset{―}{E},\downarrow f[x]\subseteq f[\downarrow x]$$

$$\begin{array}{rl}\downarrow f[x]& =\downarrow f[\bigcup _{e\in x}e]\\ & =\downarrow \bigcup _{e\in x}f(e)& & \text{(since the direct images preserve union)}\\ & =\bigcup _{e\in x}\downarrow f(e)& & \text{(by definition of }\downarrow \text{ on sets)}\\ & \subseteq \bigcup _{e\in x}f(\downarrow e)& & \text{(by the previous lemma)}\\ & =f[\bigcup _{e\in x}\downarrow e]\\ & =f[\downarrow x]& & \text{(by definition of }\downarrow x\text{ )}\end{array}$$

6.

Any map $f:E⟶F$ is causality reflecting on configurations:

$$\forall e_1,e_2\in x\in \mathcal{C}(E),f{e}_1{\le }_{F}f{e}_2⟹e_1{\le }_E{e}_2$$

If $f(e_1)\in \downarrow f(e_2)\subseteq f(\downarrow e_2)$, then there exists $e_0{\le }_E{e}_2$ such that

$$f(e_1)=f(e_0)$$

As the configuration $x$ is down-closed: $e_0\in x$. On top of that, as $f$ is injective on the configuration $x\ni e_1,e_0$:

$$e_1=e_0$$

and $e_1=e_0{\le }_E{e}_2$

NB: a map is not necessarily causality reflecting on the whole carrier set, as exemplfied by the following counter-example: if

• $$\begin{array}{rl}\underset{―}{E}& \stackrel{\scriptscriptstyle\mathrm{def}}{=}\{a,b\}\\ {\mathrm{Con}}_E& \stackrel{\scriptscriptstyle\mathrm{def}}{=}\{\{a\},\{b\},\varnothing \}\\ a& {\nleqq }_{E}b\end{array}$$
• $$\begin{array}{rl}\underset{―}{F}& \stackrel{\scriptscriptstyle\mathrm{def}}{=}\{c\}\\ {\mathrm{Con}}_F& \stackrel{\scriptscriptstyle\mathrm{def}}{=}\{\{c\},\varnothing \}& \end{array}$$

then the only map $f:E⟶F$ (sending all the elements to $c$) is not reflecting causality:

$$c=f(a){\le }_{F}f(b)=c\text{ but }a\nleqq b$$

7.

Note that $f:\underset{―}{E}⟶\underset{―}{F}$ is

• monotone iff $\forall e\in \underset{―}{E},f[\downarrow e]\subseteq \downarrow f(e)$

• causality reflecting on configurations iff $∀ x ∈ \Confstar[E], ∀ e∈ x, \, f^{-1}_{

  x}[\dc f(e)] ⊆ \dc e$

The proof is straightforward.

8.

Any rigid map $f:E⟶F$ is configuration reflecting on configurations:

$$\forall x^{\prime }\subseteq x\in \mathcal{C}(E),f[x^{\prime }]\in \mathcal{C}(F)⟹x^{\prime }\in \mathcal{C}(E)$$

Let’s show that any $x^{\prime }\subseteq x\in \mathcal{C}(E)$ such that $f[x^{\prime }]\in \mathcal{C}(F)$ is a configuration of $E$.

• $x^{\prime }$ is consistent, as $x$ is (and $\subseteq$ is transitive)

• $x^{\prime }$ is down-closed:

  As $f[x^{\prime }]$ is a configuration, hence down-closed:

  $$\downarrow f[x^{\prime }]\subseteq f[x^{\prime }]$$

  But $f$ being monotone implies:

  $$f[\downarrow x^{\prime }]\subseteq \downarrow f[x^{\prime }]$$

  So

  $$f[\downarrow x^{\prime }]\subseteq f[x^{\prime }]$$

  and as taking preimages preserves inclusion and $f$ is injective on the configuration $x\supseteq x^{\prime }$:

  $$\downarrow x^{\prime }\stackrel{\text{injectivity}}{=}{f}^{-1}(f(\downarrow x^{\prime }))\subseteq f^{-1}(f(x^{\prime }))\stackrel{\text{injectivity}}{=}{x}^{\prime }$$

9.

Any map $f:E⟶F$ is rigid iff

$$\forall x\in {\mathcal{C}}^{\mathrm{o}}(E),\forall y\in {\mathcal{C}}^{\mathrm{o}}(F),y\subseteq f[x]⟹\exists x^{\prime }\in {\mathcal{C}}^{\mathrm{o}}(E),x^{\prime }\subseteq x\wedge f{x}^{\prime }=y$$

• $⟹$: Let’s assume that $f$ is rigid and $y\subseteq f[x]$. Then $y\stackrel{\scriptscriptstyle\mathrm{def}}{=}f[x^{\prime }]$, where $x^{\prime }\in {\mathcal{P}}_{\mathrm{f}\mathrm{i}\mathrm{n}}(x)$. All that remains to be shown is that $x$ is a configuration, which directly results from the previous lemma.

• $⟸$: it’ll be sufficient to show that for all $e\in \underset{―}{E}$, $f[\downarrow e]\subseteq \downarrow f(e)$. As $f$ is a map:

  $$y\stackrel{\scriptscriptstyle\mathrm{def}}{=}\downarrow f(e)\subseteq f[\downarrow e]$$

  So there exists ${\mathcal{C}}^{\mathrm{o}}(E)\ni x^{\prime }\subseteq \downarrow e$ such that $f{x}^{\prime }=y$. On top of that, $f(e)\in y$ so by injectivity of $f$ on the configuration $\downarrow e$:

  $$e\in x^{\prime }$$

  Therefore:

  $$\begin{array}{rlrl}& \downarrow e\subseteq x^{\prime }& & \text{(as }{x}^{\prime }\text{ is down-closed)}\\ ⟹& f[\downarrow e]\subseteq \underset{=y\stackrel{\scriptscriptstyle\mathrm{def}}{=}\downarrow f(e)}{\underbrace{f[x^{\prime }]}}& & \text{(as images preserve inclusion)}\end{array}$$

10.

Let $P$ be a well-founded poset. Then $⟨\underset{―}{P},{\le }_P,{\mathcal{P}}_{\mathrm{f}\mathrm{i}\mathrm{n}}(P)⟩$ is an event structure.

All the properties to check are trivially true:

• ${\le }_P$ is indeed a partial order for which all the downard closures are finite (as $P$ is well-founded)

• all the singletons are members of ${\mathcal{P}}_{\mathrm{f}\mathrm{i}\mathrm{n}}(P)$

• ${\mathcal{P}}_{\mathrm{f}\mathrm{i}\mathrm{n}}(P)$ is stable under inclusion

• the augmentation property holds, as $x\cup \{e^{\prime }\}$ is finite provided $x$ is.

11.

Let $P,Q$ be well-founded posets, and $f:\underset{―}{P}⟶\underset{―}{Q}$ be any function. Then: $f$ is a rigid map iff $\forall p\in \underset{―}{P},f[\downarrow p]=\downarrow fp$ and $f$ is causality reflecting.

• $⟹$: if $f$ is a rigid map, then it is a map, and it is causality reflecting on configurations as showed previously, and for all $p\in \underset{―}{P}$:

  • $f[\downarrow p]\subseteq \downarrow fp$ as $f$ is monotone
  • $\downarrow fp\subseteq f[\downarrow p]$ as shown previously (since $\downarrow fp$ is the smallest configuration containing $fp$)

• $⟸$: if $f$ is causality reflecting and $f[\downarrow p]=\downarrow fp$, then:

  • $f$ is monotone as $f[\downarrow p]\subseteq \downarrow fp$ for all $p\in \underset{―}{P}$
  • $f$ is configuration preserving, as the image of a finite set is a finite set

  • $f$ is injective (and hence locally injective): if $f(e)=f(e^{\prime })$, then as $f$ is causality reflecting:

    • $f(e){\le }_{F}f(e^{\prime })$ so $e{\le }_E{e}^{\prime }$
    • $f(e^{\prime }){\le }_{F}f(e)$ so $e^{\prime }{\le }_{E}e$

    thus $e=e^{\prime }$ by antisymmetry.

12.

We can regard $⟨{\mathcal{C}}^{\mathrm{o}}(E),\subseteq ⟩$ as a sub-category of the comma $I\downarrow E$. Is it full?

It’s not: with

• $\underset{―}{E}\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{\alpha ,\beta \},\alpha \nleqq \beta$
• $x\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{\alpha \}\in {\mathcal{C}}^{\mathrm{o}}(E)$
• $f\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{\begin{array}{lll}x& ⟶E\alpha & \mapsto \beta \end{array}$

then the following diagram commutes:

$$xffEidE$$

so that $f\in {\mathrm{Hom}}_{I\downarrow E}(x,E)$, but $f$ is not the inclusion map.

13.

A rigid map $f:E⟶F$ satisfies the path lifting property iff:

$$\forall x\in {\mathcal{C}}^{\mathrm{o}}(E),\forall y\in {\mathcal{C}}^{\mathrm{o}}(F),f[x]\subseteq y⟹\exists x^{\prime }\in {\mathcal{C}}^{\mathrm{o}}(E);x\subseteq x^{\prime }\wedge f[x^{\prime }]=y$$

• $⟹$: Let $x\in {\mathcal{C}}^{\mathrm{o}}(E)$ and $y\in {\mathcal{C}}^{\mathrm{o}}(F)$ such that $f[x]\subseteq y$. Then by lifting property, the following square factors into these two triangles (where ${\iota }_x$ and ${\iota }_y$ are the inclusion maps):

  $$x{\iota }_x{f}_{|x}Efy{\iota }_y\exists \phi F$$

  By setting $x^{\prime }\stackrel{\scriptscriptstyle\mathrm{def}}{=}\phi [y]$:

  • $x^{\prime }\in {\mathcal{C}}^{\mathrm{o}}(E)$: since is the image of a finite configuration by a configuration-preserving map

  • $x\subseteq x^{\prime }$: as

    $$\begin{array}{rl}& f[x]\subseteq y\\ ⟺& \underset{={\iota }_x[x]=x}{\underbrace{\phi [f[x]]}}\subseteq \underset{\stackrel{\scriptscriptstyle\mathrm{def}}{=}{x}^{\prime }}{\underbrace{\phi [y]}}& & \text{(since taking images preserves inclusion)}\end{array}$$
  • $f[x^{\prime }]=f[\phi [y]]={\iota }_y(y)=y$

• $⟸$: let $P,Q\in \mathbb{P}$ such that the following square commutes:

  $$PpgEfQqF$$

  Then $x\stackrel{\scriptscriptstyle\mathrm{def}}{=}p[P]\in {\mathcal{C}}^{\mathrm{o}}(E)$ and $y\stackrel{\scriptscriptstyle\mathrm{def}}{=}q[Q]\in {\mathcal{C}}^{\mathrm{o}}(F)$ (images of finite configurations by configuration-preserving maps) are such that

  $$f[x]=f[p(P)]=q[g[P]]\stackrel{g[P]\subseteq Q}{\subseteq }q[Q]\stackrel{\scriptscriptstyle\mathrm{def}}{=}y$$

  so there exists a finite configuration ${\mathcal{C}}^{\mathrm{o}}(E)\ni x^{\prime }\supseteq x$ such that $f[x^{\prime }]=y$.

  By local injectivity, the function $f_{

  x’}^{

  y}: x’ ⟶ y$(corestrictionto$y$oftherestrictionto$x’$) is bijective. One can check that its inverse ${f_{

  x’}^{

  y}}^{-1}$ remains a rigid map:

  • it is injective, thus locally injective.
  • it is monotone, since the map $f$ is causality reflecting on configurations (as seen previously)

  • it is configuration-preserving, that is:

    $$\forall {\mathcal{C}}^{\mathrm{o}}(F)\ni y^{\prime }\subseteq y,f^{-1}[y^{\prime }]\in {\mathcal{C}}^{\mathrm{o}}(E)$$

    It amounts to show that

    $$\forall x^{″}\subseteq x^{\prime },y^{\prime }\stackrel{\scriptscriptstyle\mathrm{def}}{=}f[x^{″}]\in {\mathcal{C}}^{\mathrm{o}}(F)⟹x^{″}\in {\mathcal{C}}^{\mathrm{o}}(E)$$

    which results from $f$ being configuration-reflecting on the configuration $x^{\prime }$ (as it is a rigid map: cf. lemma 8).

  So by setting $φ ≝ {f_{

  x’}^{

  y}}^{-1} \circ q$, the result follows, as

  $$\begin{array}{rl}\phi \circ g& ={f_{|x^{\prime }}^{|y}}^{-1}\circ \underset{=f\circ p}{\underbrace{q\circ g}}\\ & =p& & \text{(as }f\circ p:P⟶f[x]\subseteq f[x^{\prime }]=y\text{ )}\end{array}$$ $$PpgEfQq\phi F$$