Homology, Homotopy and Applications, vol.5(2), 2003, pp.1–17

DICOVERING SPACES

LISBETH FAJSTRUP

(communicated by Gunnar Carlsson)

Abstract For a local po-space X and a base point x_{0} ∈ X, we define the universal dicovering space Π : X̃_{x_{0}} → X. The image of Π is the future ↑ x_{0} of x_{0} in X and X̃_{x_{0}} is a local po-space such that | π^{→}_{1} (X̃, [x_{0}], x_{1})| = 1 for the constant dipath [x_{0}] ∈ Π^{−1}(x_{0}) and x_{1} ∈ X̃_{x_{0}}. Moreover, dipaths and dihomotopies of dipaths (with a fixed starting point) in ↑ x_{0} lift uniquely to X̃_{x_{0}}. The fibers Π^{−1}(x) are discrete, but the cardinality is not constant. We define dicoverings P : X̂ → X_{x_{0}} and construct a map ϕ : X̃_{x_{0}} → X̂ covering the identity map. Dipaths and dihomotopies in X̂ lift to X̃_{x_{0}}, but we give an example where ϕ is not continuous.

1. Introduction

Among the various models suggested for concurrency is the idea of a Higher Dimensional Automaton, an HDA, introduced by V. Pratt in [7]. The geometric analogue of this model is the geometric realization of a semi-cubical complex, [2], which is a topological space with a local time direction, a local po-space (2.1). Executions of a program are paths which increase with time, dipaths (2.5), and equivalent executions are represented by dipaths, which are dihomotopic (2.7). To study this and other geometric models, various tools from algebraic topology have been used. E. Goubault in [3] uses combinatorial homology and J. Gunawardena [5] uses methods from homotopy theory to prove a result in database theory. In [2], we gave the first definitions of homotopy theory with a (time) direction, and in [1], these methods were used to develop an algorithm for deadlock detection in concurrent systems.

In general, the tools from algebraic topology are not immediately applicable in this setting; for instance, two dipaths may be homotopic, but not dihomotopic. Hence, the strategy is to adjust the tools to make them work in the directed case. In this paper we study another part of the algebraic topology machinery, namely coverings. We adjust the definitions of coverings to the directed case, i.e., we introduce and study dicoverings. From the computer science point of view, a dicovering

Acknowledgements: The final revisions of this paper were made during a months visit to LIX, Ecole Polytechnique, Paris. Stefan Sokolowski made the drawing for Fig. 1. Received October 15, 2001, revised September 9, 2002; published on April 22, 2002. 2000 Mathematics Subject Classification: 57M10, 51H15, 54E99. Key words and phrases: Covering spaces, abstract homotopy theory, dihomotopy theory. \begin{matrix}c \\ ◯ \end{matrix} 2003, Lisbeth Fajstrup. Permission to copy for private use granted.

map between higher dimensional automata gives a bijection between dipaths, i.e., execution paths, and also between dihomotopies of dipaths, i.e., equivalences of executions. Hence, if an automaton is a dicovering of another automaton, they have the same computational power. An example of a universal dicovering is the infinite “delooping” of a loop, which is the usual covering of S^{1}, except that it has a direction. But even without diloops, there could be non-dihomotopic dipaths and hence non-trivial dicoverings:

Example 1.1. For two basic cases, the case of a loop in one process, and the case where two concurrent processes share one object, it is not hard to see what the set of all dipaths (from the minimal point) up to dihomotopy is. This has been studied before for instance in [9] as a partially ordered set, but we want to give it a topology as indicated in Fig. 1. In the first example, an edge followed by a loop followed by an edge, the universal dicovering of the loop itself is a helix, with each turn of the helix representing a turn of the loop below as in the non-directed case. There is only one edge in the cover over the edge leading into the loop, since there is precisely one dipath up to dihomotopy from the initial point to any point on that edge. There are infinitely many edges covering the edge which leaves the loop; they represent leaving the loop after 0, 1, 2, 3, …, n, … turns.

In the other example, the partial order on the subset of ℝ^{2} is (x_{1}, x_{2}) ⩽ (y_{1}, y_{2}) if x_{i} ⩽ y_{i}, and the topology is the usual topology. In this two-dimensional example, there are no diloops. But the dipaths going “under” the hole and the dipaths going “over” the hole are not dihomotopic, and hence they lift to dipaths ending in different layers in the covering. So there are two points in the fiber P^{−1}(x) when x is in the upper right hand corner of the square, but only one point over all other points. The computer scientific interpretation of this example is, that two processes want access to a common resource, which allows only one to access at a time. In the model, one process runs along the x− axis and the other along the y−axis. An execution is a dipath from the minimal point to the maximal point. The hole is the points where both processes access the common resource, i.e., these points cannot be part of an execution. The two different (non dihomotopic) dipaths correspond to which process gets access to the resource first.

It is not a priori clear, what general properties one should require of a dicovering. From the examples above, we know that one should not expect for instance a constant fiber dimension, so we cannot define dicoverings by this property as in the undirected case.

The approach in this paper is somewhat backwards compared to the usual definition of coverings. We first define (in Def. 3.2) what certainly has to be the universal dicovering with respect to a point x_{0} ∈ X of a locally diconnected (2.9) local pospace X by giving a topology and a local partial order on the set of dipaths with initial point x_{0} up to dihomotopy. Then we prove that the universal dicovering Π : X̃_{x_{0}} → X has unique lifting of dipaths and of dihomotopies of dipaths with fixed initial point in the future of x_{0} - given a lift of the initial point; and that the fibers are discrete. Moreover, the restriction of Π to the local future of a point x ∈ X̃_{x_{0}} is a continuous bijection to the local future of Π(x).

[figure: P; P]

Figure 1: The universal dicovering in two cases. A process with a loop and two concurrent processes having one shared object.

The universal dicovering has trivial dihomotopy with respect to x_{0}. We prove that π^{→}_{1} (X̃_{x_{0}}, [x_{0}], x), where [x_{0}] is the constant dipath at x_{0}, has at most one element for all x, but on the other hand, we provide an example, where X̃_{x_{0}} has a directed loop (which then does not contain [x_{0}]). In particular, X̃_{x_{0}} is not a (global) po-space.

A dicovering with respect to x_{0} ∈ X is a dimap such that dipaths and dihomotopies of dipaths initiating in x_{0} lift uniquely given a lifting of the initial point. This implies that dipaths and dihomotopies initiating in a point in the future of x_{0} lift. In the classical case, the path lifting property implies lifting of homotopies, but the lifting property for dipaths does not imply lifting of non-directed paths, and in particular not lifting of dihomotopies, which are non-directed in one coordinate.

The universal dicovering is universal in the following sense: If P : X̂ → X is a dicovering with respect to x_{0}, then there is a map ϕ : X̃_{x_{0}} → X̂ which has unique lifting of dipaths and dihomotopies of dipaths. In general, ϕ preserves the local partial order, but we give an example where it is not continuous and hence it is not a dicovering. We expect, but do not prove here, that the category of local po-spaces, where ϕ is a dicovering, is quite large. In a subsequent paper, we will prove that semi cubical complexes and hence HDA are in this category.

In future work, we hope to give a category of local po-spaces, which is large enough to be interesting, but small enough not to contain the (admittedly) pathological examples given her. The category of semi cubical complexes does not have the pathological examples, but one could hope for an even larger category.

2. Preliminary Definitions

Definition 2.1. Let X be a topological space.

• A collection U(X) of pairs (U, ⩽_{U}) with partially ordered open subsets U covering X is a local partial order on X if for every x ∈ X there is a nonempty open neighbourhood W (x) ⊂ X with a partial order ⩽_{W (x)} such that the restrictions of ⩽_{U} and ⩽_{W (x)} to U ∩ W (x) coincide for all U ∈ U(X) with x ∈ U, i.e.,

y ⩽_{U} z ⟺ y ⩽_{W (x)} z  for all U ∈ U(X) such that x ∈ U and for all y, z ∈ W (x) ∩ U  (2.1)

• Two local partial orders on X are equivalent if their union is a local partial order.

• A topological space X together with an equivalence class of local partial orders is called a locally partially ordered space. If, moreover, X is Hausdorff and there is a covering U such that for all (U, ⩽_{U}) ∈ U the order ⩽_{U} on U is a closed relation ( (U, ⩽_{U}) is a pospace ), then X together with an equivalence class of coverings by po-spaces is a local pospace.

When X is a local po-space, a neighbourhood W (x) as in Def. 2.1, s.t. the partial order on W (x) is closed, is called a po-neighbourhood of x.

We will consider (local) po-spaces and not the more general (locally) partially ordered spaces in this article. Most of the constructions make sense for the more general category, and we leave it to the reader to make this generalisation.

Example 2.2. Let X = S^{1} = {e^{iθ} ∈ ℂ}, the unit circle. We want the local partial order to be the usual order, i.e., by increasing θ. Let U_{1} = {e^{iθ}|π/4 < θ < 7π/4} and U_{2} = {e^{iθ}| − 3π/4 < θ < 3π/4} ordered by increasing θ. Then the partial order is closed and W_{1} = {e^{iθ}| − π/4 < θ < 5π/4} and W_{2} = {e^{iθ}|3π/4 < θ < 9π/4} ordered by increasing θ give local po-neighborhoods of all points.

Remark 2.3. If W (x) is a po-neighborhood, then any subset of W (x), which is a neighborhood of x is a po-neighborhood with the partial order induced from W (x). Hence w.l.o.g. one can assume that W (x) ⊂ U for some U ∈ U(X) and hence that the partial order on W (x) is induced from U. The po-neighborhoods satisfying this extra condition are called small po-neighborhoods and they give a neighborhood basis for the topology on X, since the intersection of two small po-neighborhoods is again a small po-neighborhood. Moreover, the covering by small po-neighborhoods defines the local partial order. In example 2.2, the po-neighborhoods are not small, and W_{1} ∩ W_{2} is not a po-neighborhood with a structure induced from W_{1} and W_{2}, since e^{iπ}, e^{0} ∈ W_{1} ∩ W_{2} but e^{iπ} ⩾_{W_{1}} e^{0} while e^{iπ} ⩽_{W_{2}} e^{0}; hence the partial orders on W_{1} and W_{2} do not induce a common partial order on the intersection. It is not hard to see, however, that there are small po-neighborhoods of each point.

Definition 2.4. Let (X, U) and (Y, V) be local po-spaces. A continuous map f : X → Y is called a dimap (directed map) if for any x ∈ X there are po-neighbour-hoods W (x) and W (f(x)) such that

x_{1} ⩽_{W (x)} x_{2} ⇒ f(x_{1}) ⩽_{W (f(x))} f(x_{2})

whenever x_{1}, x_{2} ∈ f^{−1}(W (f(x))) ∩ W (x).

Definition 2.5. Let X be a local po-space and let I^{→} denote the unit interval [0, 1] with the usual order.

• A dimap γ : I^{→}→ X is called a dipath.

• If there is a dipath such that γ(0) = x and γ(1) = y then we write x ⪯ y. If

γ( I^{→}) ⊆ U ⊆ X we write x ⪯_{U} y.

• If γ(1) = μ(0) the composition is

γ ∗ μ(t) = \{ \begin{matrix}γ(2t) & 0 ⩽ t ⩽ 1/2 \\ μ(2t − 1) & 1/2 ⩽ t ⩽ 1 \end{matrix}

• For a subset U ⊆ X and x ∈ X the future of x in U is

↑_{U} (x) = {y ∈ U|x ⪯_{U} y}

When U = X, we write ↑ x and omit the subscript X.

Remark 2.6. We get a new local partial order {(U, ⪯_{U})|U ∈ U} on X. When considering dipaths and dihomotopies of dipaths, as in this paper, this is the important part of the local partial order. Notice that • ⩽ may be closed and ⪯ not closed: Let I^{2}^{∘} ∪{(1/4, 0), (1/2, 0)} be the open unit

square and two extra points in ℝ^{2} with the induced partial order (x_{1}, x_{2}) ⩽ (y_{1}, y_{2}) if x_{1} ⩽ y_{1} and x_{2} ⩽ y_{2} and with the induced topology. Then ⩽ is closed, but ⪯ is not: (1/4, 0) ⪯̸ (1/2, 0) but any pair of neighborhoods of (1/4, 0) and (1/2, 0) contains points which are related.

• ⪯ may be closed and ⩽ not closed: Let X = [0, 1] × [0, 1] ∪ [2, 3] × [0, 1] and let the partial order and the topology be induced from the partial order on ℝ^{2} except that (1/2, 1/2) ⩽̸ (5/2, 1/2). Then ⩽ is not closed, but ⪯ is.

When γ is a dipath, the restriction γ :[0, a]^{→}→ X can be linearly reparametrized to a dipath γ|_{[0,a]} : I^{→}→ X, and we will do that without further mentioning.

Dihomotopies are only ordered along the paths:

Definition 2.7. For a local po-space X, a dimap H : I× I^{→}→ X is a dihomotopy from the dipath H_{0}(t) = H(0, t) to the dipath H_{1}(t) = H(1, t). An endpoint preserving dihomotopy is a dihomotopy such that H(s, 0) = x_{0} and H(s, 1) = x_{1} for all s ∈ I. We define π^{→}_{1} (X, x_{0}, x_{1}), the equivalence classes of dipaths from x_{0} to x_{1} modulo endpoint preserving dihomotopy. When U ⊆ X and x_{0} ∈ X we

define π^{→}_{1} (X, x_{0}, U) = ⋃{π^{→}_{1} (X, x_{0}, x_{1})|x_{1} ∈ U}. When U = X we denote this

π^{→}_{1} (X, x_{0}).

Example 2.8. Let X be a local po-space and let γ : I^{→}→ X be a non-trivial diloop, i.e., γ(0) = γ(1). Then γ is not dihomotopic through diloops to a constant dipath. Suppose there was such a dihomotopy H : I× I^{→}→ X, H_{0}(t) = γ(t), H_{1}(t) = p, H_{s}(0) = H_{s}(1), and suppose w.l.o.g. that H_{s} is trivial only for s = 1. Let U_{p} be a po-neighborhood of p. Then, since I^{→} is compact, there is an ε such that ]1 − ε, 1]× I^{→}⊆ H^{−1}(U_{p}). Then H_{1−ε/2}(t) is a non-trivial diloop in U_{p}, but this violates transitivity (or reflexivity) of the partial order on U_{p}

Definition 2.9. Let X be a local po-space. Then X is locally diconnected if the topology on X is generated by path-connected small po-neighbourhoods W ⊆ X such that

1. For any pair of points x, y ∈ W the dihomotopy class π^{→}_{1} (W, x, y) has at most one element.

2. x ⩽_{W} y ⇔ x ⪯_{W} y.

3. W is diconvex: If U is a po-neighborhood, x, y ∈ U ∩ W and x ⩽_{U} z ⩽_{U} y then z ∈ W.

Condition 2 could be replaced by requiring diconvexity with respect to ⪯_{U} and that ⪯_{U} is closed. The important condition is 1, and for this to hold on intersections, we need diconvexity with respect to ⪯_{W}. These sets actually give a basis:

Lemma 2.10. If U and V satisfy 2.9, then their intersection satisfies 2.9.

Proof. Let W = U ∩ V then W is a small po-neighborhood and the partial order on W coincides with the orders on both U and V. Now let x, y ∈ W with x ⩽_{W} y.

Since x ⩽_{U} y there is a dipath in U from x to y. If this dipath is not contained in W, there is a point z ∉ W with x ⩽_{U} z ⩽_{U} y, but this contradicts the diconvexity of V, since x ⩽_{V} y. Hence W satisfies condition 2) and this argument also proves that W is diconvex. Moreover, for a proof of 1), suppose there are two dipaths from x to y. Then they are dihomotopic in both U and V, and by diconvexity, this dihomotopy is in W.

3. The Universal Dicoveringspace

Definition 3.1. Let X be locally diconnected, let U be the covering by all opens satisfying 2.9 and let U ∈ U. We define an equivalence relation ∼_{U} on π^{→}_{1} (x_{0}, U):

[γ] ∼_{U} [η] if there is a dimap H : I× I^{→}→ X such that H(0, t) = γ(t), H(1, t) = η(t), H(s, 0) = x_{0} and H(s, 1) ∈ U for all s ∈ I

Notice that this is well defined on π^{→}_{1} (X, x_{0}, U).

Definition 3.2. Let X be a locally diconnected local po-space, let U satisfy 2.9 and let x_{0} ∈ X. The universal dicovering space X̃_{x_{0}} of X with respect to x_{0} is the set π^{→}_{1} (X, x_{0}). The topology on X̃_{x_{0}} is generated by these subsets: For γ such that γ(1) ∈ U, where U ∈ U, let

U_{[γ]} = {[η] ∈π^{→}_{1} (X, x_{0}, U)|[η] ∼_{U} [γ]}

For an example of this topology, see Fig. 2

Lemma 3.3. The sets U_{[γ]} generate a topology on X̃_{x_{0}}

Proof. We have to see that when [λ] ∈ U_{[γ]} ∩ V_{[η]} there is a W_{[α]} such that [λ] ∈ W_{[α]} ⊆ U_{[γ]} ∩ V_{[η]}. When U = V, this follows from the observation U_{[γ]} ∩ U_{[η]} ≠ ∅ ⇔ U_{[γ]} = U_{[η]}. When U ≠ V, let W = U ∩V. Then λ(1) ∈ W and W_{[λ]} ⊆ U_{[γ]}∩V_{[η]}.

Remark 3.4. In the non-directed situation, this is the usual definition of the topology on the universal covering space: Let α be a path in U and let H : I × I → X be a non-directed, endpoint preserving homotopy of γ ∗ α and η. Then H gives rise to a homotopy H̃ = H ∘ F^{−1} of γ and η with H̃(1, s) = α(s) ∈ U and vice versa via the (non-directed) bijection F : I × I/ ∼→ I × I where (1, y) ∼ (1, 1). See Fig. 3

F (x, y) = \{ \begin{matrix}((2 − y)x, y) & for x ⩽ 1/2 \\ (1 + (x − 1)y, 2y(1 − x) + 2x − 1) & for x ⩾ 1/2 \end{matrix}

and

F^{−1}(z, w) = \{ \begin{matrix}(\frac{z}{2−w} , w) & for z ⩽ 1 − \frac{w}{2} \\ (\frac{1}{2}(w − 1 + 2z), \frac{2(z−1)}{w−3+2z}) & for 1 − \frac{w}{2} ⩽ z \end{matrix}

Definition 3.5. The local partial order on X̃_{x_{0}} is defined by [γ] ⩽_{U_{[λ]}} [η] if there is a dipath μ in U such that [γ ∗ μ] = [η].

This is well defined since [γ_{1}] = [γ_{2}] ⇒ γ_{1}(1) = γ_{2}(1) and the dihomotopy from γ_{1} to γ_{2} extends to a dihomotopy of γ_{1}∗μ and γ_{2}∗μ and since [γ] ∈ U_{[λ]} ⇒ [γ∗μ] ∈ U_{[λ]}.

Homology, Homotopy and Applications, vol. 5(2), 2003 8

Figure 2: The topology on the universal covering. Figure 3: The bijection in Rem. 3.4 Definition 3.6. Let X be a locally diconnected local po-space and let U be the set of po-neighborhoods satisfying 2.9. Then X is locally relatively diconnected with respect to x_{0} ∈ X if for any x ∈ X there is a U ∈ U such that for any pair

[γ], [μ] ∈π^{→}_{1} (x_{0}, x), [γ] ∼_{U} [μ] ⇔ [γ] = [μ].

This condition ensures that X̃_{x_{0}} is Hausdorff and that the fibers are discrete. As in the non-directed case, 2.9 and 3.6 are excluding Hawaiian earrings in different situations:

Example 3.7. Let

H = ⋃_{n∈IN}{(1/n, 0) + 1/n(cos(θ), sin(θ)) ∈ ℝ^{2}|θ ∈ [−π, π]}

be topologized as a subset of ℝ^{2}. This is a Hawaiian earring - a union of circles of radius 1/n and center (1/n, 0). The partial order on each circle by increasing θ - as in Ex. 2.2 is not a local partial order, since all neighborhoods of (0, 0) contain circles. The partial order “from (0, 0) to (0, 2/n)”: (1/n, 0) + 1/n(cos(θ_{1}), sin(θ_{1})) ⩽ (1/n, 0) + 1/n(cos(θ_{2}), sin(θ_{2})) if π ⩾ θ_{1} ⩾ θ_{2} ⩾ 0 or −π ⩽ θ_{1} ⩽ θ_{2} ⩽ 0 is a local partial order, but it does not satisfy 2.9. Neither does the reverse of this partial order. Some Hawaiian earrings do satisfy 2.9, but not 3.6.

We define a Hawaiian truncated cone: Let

C_{n} =

\{((1 + t\frac{1 − n}{n})(1 + cos(θ)), (1 + t\frac{1 − n}{n}) sin(θ), t − 1) ∈ ℝ^{3}|0 ⩽ t ⩽ 1, θ ∈ [−π, π]\}

C_{n} is a truncated cone defined by lines from the circle with center (1/n, 0, 0) and radius 1/n to the circle of radius 1 and center (1, 0, −1), both parallel to the x − y−plane. Then the Hawaiian truncated cone is CH = ⋃_{n∈IN} C_{n} with the topology induced from ℝ^{3}. We define a partial order on each C_{n} in terms of the coordinates (t, θ):

(t_{1}, θ) ⩽ (t_{2}, θ) if t_{1} ⩽ t_{2} and (0, θ_{1}) ⩽ (0, θ_{2}) if 0 ⩽ θ_{1} ⩽ θ_{2} ⩽ π or 0 ⩾ θ_{1} ⩾ θ_{2} ⩾ −π. See Fig. 4.

There are two non dihomotopic dipaths in CH from (1, 0, −1) to (0, 0, 0) in CH. We give them in terms of the (t, θ) ∈ [0, 1] × [−π, π] coordinates on a C_{n}:

γ_{1}(u) = \{ \begin{matrix}(0, 2πu) & for; 0 ⩽ u ⩽ \frac{1}{2} \\ (2u − 1, π) & for; u ⩾ \frac{1}{2} \end{matrix}

γ_{2}(u) = \{ \begin{matrix}(0, −2πu) & for; 0 ⩽ u ⩽ \frac{1}{2} \\ (2u − 1, −π) & for; u ⩾ \frac{1}{2} \end{matrix}

This is well defined, since the paths are on the intersection of all C_{n} in CH. These dipaths are not dihomotopic with fixed endpoints, but for each neighborhood of (0, 0, 0) there is a dihomotopy whose path of endpoints traverses one of the small circles contained in this neighborhood. Given a neighborhood U of (0, 0, 0), there is an n such that {(1/n, 0, 0) + 1/n(cos(θ), sin(θ), 0)|θ ∈ [π, π]} ∈ U. We give a

Figure 4: A Hawaiian truncated cone and one of the C_{n}

dihomotopy from γ_{1} to γ_{2} with endpoints varying in U. Let (t, θ) be the coordinates

on C_{n} then H : I× I^{→}→ C_{n} is

H(s, u) = \{ \begin{matrix}(0, 2πu) & for u ⩽ \frac{s}{2} \\ (\frac{2u−s}{2−s}, πs) & for u ⩾ \frac{s}{2} \end{matrix}

This is a dihomotopy of γ_{1} and μ(u) = (u, 0), and symmetrically, γ_{2} is dihomotopic to μ.

Hence CH is not locally relatively diconnected with respect to (1, 0, −1).

There are local po-spaces containing topological Hawaiian earrings, which are neither violating 2.9 nor 3.6. An example is CH with another basepoint.

Proposition 3.8. Let X be a local po-space which is locally relatively diconnected with respect to x_{0} ∈ X. Then X̃_{x_{0}} is a local po-space.

Proof. X̃_{x_{0}} is Hausdorff, since 3.6 is satisfied: Suppose [γ_{1}] ≠ [γ_{2}].If γ_{1}(1) ≠ γ_{2}(1) there are disjoint neighborhoods U_{i} with γ_{i}(1) ∈ U_{i} for i = 1, 2 and then the U_{i}_{[γ_{i}]} are disjoint. If γ_{1}(1) = γ_{2}(1), let U be as in 3.6, then U_{[γ_{1}]} ≠ U_{[γ_{2}]} and hence U_{[γ_{1}]} ∩ U_{[γ_{2}]} = ∅.

We have to see that when U satisfies 3.6 and η(1) ∈ U, then U_{[η]} is a po-space: Suppose [γ_{1}] ⩽̸_{U_{[η]}} [γ_{2}]. If γ_{1}(1) ≠ γ_{2}(1) there are disjoint neighborhoods of [γ_{1}] and [γ_{2}] by the above argument.

Suppose now that γ_{1}(1) = γ_{2}(1) then [γ_{1}] ⩽_{U_{[η]}} [γ_{2}] ⇔ [γ_{1}] = [γ_{2}], since there are no loops in U. Hence [γ_{1}] ⩽̸_{U_{[η]}} [γ_{2}] if and only if U_{[γ_{1}]} ≠ U_{[γ_{2}]}, i.e., U_{[γ_{1}]} ∩ U_{[γ_{2}]} = ∅.

Proposition 3.9. Let X be a locally diconnected local po-space and x_{0} ∈ X. Define Π : X̃_{x_{0}} → X by Π([γ]) = γ(1). Then Π is a dimap.

Proof. Let U be a basic set in X. Then Π^{−1}(U) = ∪_{{γ|γ(1)∈U}}U_{[γ]}, i.e., a union of basic sets, so Π is continuous. To see that the local partial order is preserved, suppose [η_{i}] ∈ U_{[γ]} and [η_{1}] ⩽_{U_{[γ]}} [η_{2}], then η_{1}(1) ⩽_{U} η_{2}(1).

Lemma 3.10. Let [γ] ∈ X̃_{x_{0}}. Then Γ(t) = [γ_{|[0,t]}] is a dipath in X̃_{x_{0}}, and Π∘Γ(t) = γ(t).

Proof. Let [γ_{[0,t_{0}]}] ∈ U_{[η]}. Then the interval

] inf{t|γ([t, t_{0}]) ⊂ U}, sup{t|γ([t_{0}, t]) ⊂ U}[

is nonempty and contained in Γ^{−1}(U_{[η]}) so t_{0} is an inner point. Hence Γ^{−1}(U_{[η]}) is open. Moreover, Γ is monotone as a map from this neighborhood of t_{0} to U_{[η]}.

Proposition 3.11. The universal dicovering Π : X̃_{x_{0}} → X of a local po-space X which is locally relatively diconnected w.r.t. x_{0} has the following properties:

1. The fibers Π^{−1}(x) are discrete for any x ∈ X.

2. For any basic set U ⊆ X and x ∈ Π^{−1}(U)

Π :↑_{Π^{−1}(U)} x →↑_{U} Π(x) is a continuous bijection

3. Dipaths lift uniquely given a lift of the initial point:

\xymatrix{\{0\} \ar[r] \ar@{^{(}->}[d] & X̃_{x_{0}} \ar[d]^{Π} \\ I^{→} \ar[r]^{γ} \ar@{-->}[ur]^{∃!γ̃} & X}

Let γ : I^{→}→ X and suppose y ∈ Π^{−1}(γ(0)). Then there is a unique lift γ̃ : I^{→}→ X̃_{x_{0}} such that γ̃(0) = y and Π ∘ γ̃(t) = γ(t) for all t ∈ I^{→}.

4. Dihomotopies with fixed initial point lift uniquely given a lift of the initial point: Let H : I× I^{→}→ X be a dimap and suppose H(I ×{0}) = x, y ∈ Π^{−1}(x). Then there is a unique dimap H̃ : I× I^{→}→ X̃_{x_{0}} such that Π ∘ H̃(s, t) = H(s, t) for

all (s, t) ∈ I× I^{→} and H̃(s, 0) = y

Proof. Proof of 1): Let [γ_{i}] ∈ Π^{−1}(x). Since X is locally relatively diconnected with respect to x_{0}, there is a U s.t. U_{[γ_{i}]} ≠ U_{[γ_{j}]} ⇔ [γ_{i}] ≠ [γ_{j}] and hence U_{[γ_{i}]} ∩ U_{[γ_{j}]} = ∅. And U_{[γ_{i}]} ∩ Π^{−1}(x) = [γ_{i}].

Proof of 2): Let [η] ∈ U_{[γ]}. Then ↑_{U_{[γ]}} [η] = {[η ∗ μ]|μ : I^{→}→ U, μ(0) = η(1)}.

On the other hand ↑_{U} Π([η]) =↑_{U} η(1) = {x ∈ U|x ⪰_{U} η(1)} = {x ∈ U|∃μ : I^{→}→ U : μ(0) = η(1) μ(1) = x} = Π(↑_{U_{[γ]}} [η]). Hence Π :↑_{U_{[γ]}} [η] →↑_{U} Π([η]) and it is a surjection. If η ∗ μ_{1}(1) = η ∗ μ_{2}(1) then μ_{1} is dihomotopic to μ_{2} through a dihomotopy in U, by condition 1) of 2.9 and thus [η ∗ μ_{1}] = [η ∗ μ_{2}], which proves injectivity.

Proof of 3): Let y = [η]. Then η(1) = γ(0). The lift is γ̃(t) = [η ∗ γ_{|[0,1/2+t/2]}]. This is a lift by Lem. 3.10. By 2), the lift is unique.

Proof of 4): Since dipaths lift uniquely, we only have to see that the map H̃ : I× I^{→}→ X̃_{x_{0}} defined by lifting the dipaths is continuous. For this it suffices to see that it is continuous in the (non directed) I-direction. Suppose H̃(s_{0}, t_{0}) ∈ U_{[η]}. Then, since H is continuous, there is an ε > 0 such that H(]s_{0}−ε, s_{0}+ε[×{t_{0}}) ∈ U.

Since H̃(s, t) ∈ U_{[η]} if and only if [H_{s}(t)_{|[0,t_{0}]}] ∼_{U} [η] and since [H_{s}(t)_{|[0,t_{0}]}] ∼_{U} [H_{s_{0}}(t)_{|[0,t_{0}]}] for s ∈]s_{0}−ε, s_{0}+ε[ it follows that ]s_{0}−ε, s_{0}+ε[×{t_{0}} ⊂ H̃^{−1}(U_{[η]}).

Theorem 3.12. Let X̃_{x_{0}} be the universal cover of X, where X is locally relatively diconnected w.r.t. x_{0}. Then π^{→}_{1} (X̃_{x_{0}}, [x_{0}], [γ]) has precisely one element for any [γ] ∈ X̃_{x_{0}}, where [x_{0}] ∈ X̃_{x_{0}} is the constant path.

Proof. Let [γ] ∈ X̃_{x_{0}}. We have to see, that there is precisely one dipath from [x_{0}] to [γ] up to dihomotopy. The lifting Γ of γ is a dipath from [x_{0}] to [γ]. Suppose there is another dipath Λ from [x_{0}] to [γ] and let λ = Π ∘ Λ. If λ was not dihomotopic to γ, the endpoint [λ] of the unique lift, Λ, would be different from [γ]. Since λ lifts to a dipath which has [γ] as its endpoint, λ is then dihomotopic to γ. Now dihomotopies lift and hence Λ is dihomotopic to Γ.

Corollary 3.13. Let X be locally relatively diconnected w.r.t. x_{0} and let X̃_{x_{0}} be the universal cover of X. Then X̃_{x_{0}} is locally relatively diconnected w.r.t. [x_{0}]

Proof. Let U satisfy 2.9 and 3.6 on X w.r.t. x_{0}. Then by Thm. 3.12, any U_{[η]} will satisfy 3.6 w.r.t. [x_{0}].

For a proof that U_{[η]} satisfies 2.9, 2) holds by definition. For 1) and 3), observe

that when ϕ : I^{→}→ U is lifted to Φ : I^{→}→ X̃_{x_{0}}, then Φ : I^{→}→ U_{Φ(0)}.

Now let [γ_{1}], [γ_{2}] ∈ U_{[η]} and let Λ_{i} : I^{→}→ U_{[η]}, i = 1, 2 have Λ_{i}(0) = [γ_{1}] and Λ_{i}(1) = [γ_{2}]. Now Π ∘ Λ_{i} ∈π^{→}_{1} (U, γ_{1}(1), γ_{2}(1)), so they are dihomotopic in U. The dihomotopy in U of Π ∘ Λ_{i} lifts to a dihomotopy with initial point [γ_{1}] and hence it is a dihomotopy in U_{[η]} = U_{[γ_{1}]}. Diconvexity of U_{[η]} follows in the same way.

Corollary 3.14. Let X be a locally diconnected local po-space and suppose | π^{→}_{1} (X, x_{0}, x)| ⩽ 1 for all x ∈ X. Then Π : X̃_{x_{0}} →↑ x_{0} is a continuous bijection.

Proof. Π is continuous and surjective by construction, and since |Π^{−1}(x)| = | π^{→}_{1} (X, x_{0}, x)| = 1 for x ∈↑ x_{0} it is also injective.

Example 3.15. There may be more than one element in π^{→}_{1} (X̃_{x_{0}}, [γ_{1}], [γ_{2}]) when [γ_{1}] ≠ [x_{0}]: Let X = ∂I^{3}\]0, 1[×]0, 1[×{1} be partially ordered and topologized as a subspace of ℝ^{3} (a box with the lid removed) and let x_{0} = (0, 0, 0). Then Π : X̃_{x_{0}} → X is a homeomorphism: It is a bijection by Cor. 3.14. To see that Π^{−1} is continuous, let U be a connected basic open subset of X and let γ(1) ∈ U. Then any x ∈ U is in Π(U_{[γ]}): Let μ : I → U be a path from γ(1) to x. Then we leave it

to the reader to see, that there is a dihomotopy H : I× I^{→}→ X with H_{0}(t) = γ(t), and H(s, 1) = μ(t). Hence the dipath H_{1}(t) has x as endpoint and is in U_{[γ]}, so U = Π(U_{[γ]}).

Now let [γ_{1}] represent π^{→}_{1} (X, x_{0}, (0, 0, 1/2)) and let [γ_{2}] represent

π^{→}_{1} (X, x_{0}, (1, 1, 1/2)). Then

μ_{1}(t) = \{ \begin{matrix}(0, 2t, 1/2) & for 0 ⩽ t ⩽ 1/2 \\ (2t − 1, 1, 1/2) & for 1/2 ⩽ t ⩽ 1 \end{matrix}

Figure 5: Example 3.16

and

μ_{2}(t) = \{ \begin{matrix}(2t, 0, 1/2) & for 0 ⩽ t ⩽ 1/2 \\ (1, 2t − 1, 1/2) & for 1/2 ⩽ t ⩽ 1 \end{matrix}

are dipaths from [γ_{1}] to [γ_{2}] and they are not dihomotopic.

Example 3.16. There may even be non-trivial diloops in X̃_{x_{0}}. Let X = I^{→} ×I/ ∼ where (t, 0) ∼ (t, 1) for t ∈ I^{→} and (0, s) ∼ (0, 0) for s ∈ I. The partial order is the product (t_{1}, s) ⩽ (t_{2}, s) if t_{1} ⩽ t_{2} and moreover, (1, s_{1}) ⩽ (1, s_{2}) whenever s_{1} ⩽ s_{2}. (There is a loop. See Fig. 5).

We claim that X̃_{(0,0)} = X, i.e., that Π is a homeomorphism. For t < 1 there is only one dipath (up to reparametrization) from (0, 0) to (t, s), so | π^{→}_{1} ((0, 0), (t, s))| = 1 We give the argument that π^{→}_{1} ((0, 0), (1, 0)) contains only one element- even though there is a loop at (1, 0): Let γ(t) = (t, 0) = (t, 1) and let μ(t) = (2t, 0) for t ⩽ 1/2 and μ(t) = (1, 2t − 1) for t ⩾ 1/2. Then

H(t, s) = \{ \begin{matrix}(\frac{2t}{2−s}, 1 − s) & for t ⩽ 1 − s/2 \\ (1, 2t − 1) & for t ⩾ 1 − s/2 \end{matrix}

is a dihomotopy between γ and μ. It is not hard to see how to modify this dihomotopy to prove | π^{→}_{1} ((0, 0), (1, s))| = 1 for all other s. Hence Π is a continuous bijection. Now let [γ] ∈ U_{[η]}, an open set in X̃_{x_{0}}. The line l(t) from (0, 0) to Π([γ]) = γ(1) is a representative of [γ]. Let W ⊂ U be a connected open neighborhood of γ(1), then for any p ∈ W, let μ : I → W have μ(0) = γ(1) and μ(1) = p. The line from (0, 0) to p is dihomotopic to γ through a linear dihomotopy H(t, s) = (tμ_{1}(s), μ_{2}(s)) and hence W ∈ Π(U_{[γ]}). Thus Π is a dihomeomorphism and the diloop σ(t) = (1, t) lifts to a diloop in X̃_{(0,0)}.

Example 3.17. In property 2 in Prop. 3.11, we cannot sharpen the statement and claim that Π is a homeomorphism. It is not even true that there exists a neighborhood U of all points such that Π :↑_{U_{[γ]}} [γ] →↑_{U} γ(1) is a homeomorphism This is because the topology on the covering space is defined by the dipaths and dihomotopies, and there may be topology on X which is not captured by this: Let X = I × I with topology generated by the standard topology on ℝ^{2} and the subsets

I_{a} = {(x, ax)|0 < x < a}

for any a > 0.

Let the partial order be : (x_{1}, ax_{1}) ⩽ (x_{2}, ax_{2}) if a ⩾ 0, and x_{1} ⩽ x_{2}, (0, y_{1}) ⩽ (0, y_{2}) if y_{1} ⩽ y_{2}. This is a po-space, and since the only dipaths are segments of lines through (0, 0) it is easy to check that it is locally relatively diconnected with respect to (0, 0). And X̃_{(0,0)} is a disjoint wedge of halflines, since the only dihomotopies are reparametrizations. For any neighborhood U of (0, 0) there is an a such that {(x, ax)|0 ⩽ x < 2a} ⊂↑_{U} (0, 0). Now Π^{−1}({(x, ax)|a < x < 2a}) is open in X̃_{(0,0)}, but {(x, ax)|a < x < 2a} is not open in ↑_{U} (0, 0).

4. Coverings.

It is not clear what the proper definition of a dicovering should be. One could require the properties from Prop. 3.11, but we take the minimal requirements - following [6] and just require lifting properties of dipaths and dihomotopies and that the map is a dimap. We expect that this will imply the other properties in sufficiently well-behaved categories of local po-spaces, for instance the geometric realization of a semi-cubical complex, but this has to be seen.

Definition 4.1. Let Π : X̂ → X be a dimap of local po-spaces. Then Π is a dicovering with respect to x_{0} ∈ X if for any y_{0} ∈ Π^{−1}(x_{0}):

1. For any dipath γ : I^{→}→ X such that γ(0) = x_{0}, there is a unique lift γ̂ : I^{→}→ X̂, such that Π ∘ γ̂ = γ and γ̂(0) = y_{0}.

2. For any dihomotopy H : I× I^{→}→ X with H(s, 0) = x_{0} there is a unique lift

Ĥ : I× I^{→}→ X̂ s.t. Π ∘ Ĥ = H and Ĥ(s, 0) = y_{0}.

When X =↑_{X} x_{0}, Π^{−1}(x_{0}) = x̂_{0} and X̂ =↑X̂ x̂_{0}, the dicovering is a simple dicovering

Remark 4.2. The lifting property for dihomotopies does not follow from the lifting property for dipaths as it does in the non-directed case. Let X be the quotient [0, 2]× I^{→} / ∼ and let X̂ = [0, 1]× I^{→} ⊔]1, 2]× I^{→} / ∼, where (s, 0) ∼ (0, 0) for all s. The identity map is not a dicovering w.r.t. (0, 0): Dipaths from (0, 0) lift uniquely, but the dihomotopy H(s, t) = (2s, t) does not.

Lemma 4.3. Let Π : X̂ → X be a dicovering. Let γ : I^{→}→ X, γ(0) ∈↑_{X} x_{0} and let y ∈ Π^{−1}(γ(0))∩ ↑X̂ (Π^{−1}(x_{0})). Then there is a dipath Γ : I^{→}→ X̂ such that Γ(0) = y

and Π(Γ(t)) = γ(t) for all t ∈ I^{→}.

Proof. Choose a dipath μ from x̂_{0} ∈ Π^{−1}(x_{0}) to x̂. This is possible, since x̂ ∈↑X̂ (Π^{−1}(x_{0})). Then Π ∘ μ ∗ γ lifts uniquely to a dipath with initial point x̂_{0}, and this gives the lift of γ.

Corollary 4.4. With notation as above, let H : I× I^{→}→ X be a dihomotopy with H(s, 0) ∈↑_{X} x_{0}. Then there is a unique lift Ĥ of H such that Ĥ(s, 0) = y.

Proof. The dipaths H(s_{0}, t) lift uniquely by Lemma 4.3. This lift of dipaths composed with μ (as in the above proof) gives a lifting of the dihomotopy H̄(s, t) = Π ∘ μ(2t) for 0 ⩽ t ⩽ 1/2 and H̄(s, t) = H(s, 2t − 1) for 1/2 ⩽ t ⩽ 1. And since dipaths initiating in x_{0} lift uniquely, this has to be the unique lift of H̄. Hence in particular the restriction to t ⩾ 1/2 is continuous, so it is a lift of H.

Proposition 4.5. Let Π : X̂ → X be a simple dicovering w.r.t. x_{0} ∈ X. Then for

x ∈ X, |Π^{−1}(x)| ⩽ | π^{→}_{1} (X, x_{0}, x)|

Proof. Let y_{1} ≠ y_{2} ∈ Π^{−1}(x) and let Γ_{i} : I^{→}→ X̂ be dipaths with Γ_{i}(0) = x̂_{0} and Γ_{i}(1) = y_{i}. Then [Π ∘ Γ_{1}] ≠ [Π ∘ Γ_{2}] ∈π^{→}_{1} (X, x_{0}, x), since dihomotopies with fixed endpoints lift to dihomotopies with fixed endpoints by continuity.

Proposition 4.6. Let P : X̂_{x_{0}} → X be a dicovering w.r.t. x_{0} ∈ X such that P^{−1}(x_{0}) = x̂_{0}, and suppose X is relatively diconnected w.r.t. x_{0}. Then there is a map ϕ : X̃_{x_{0}} → X̂_{x_{0}} covering the identity.

Proof. Let ϕ([γ]) = γ̂(1), where γ̂ is the unique lift of γ with initial point x̂_{0}. This is well defined, since if [λ] = [γ] ∈ X̃_{x_{0}}, λ is dihomotopic to γ and λ(1) = γ(1). Now, since dihomotopies with fixed endpoints lift to dihomotopies with fixed endpoints (by continuity), it follows that λ̂(1) = γ̂(1).

The map ϕ is clearly locally increasing, but it is not continuous in general:

Example 4.7. We define a Hawaiian star for δ an irrational number:

S = ⋃_{n=1}^{∞}\{(u cos(nπδ), u sin(nπδ))|[0 ⩽ u ⩽ \frac{1}{n}\}

with the subspace topology from ℝ^{2}. The dicone on S is

CS = ⋃_{n=1}^{∞}{(tu cos(nπδ), tu sin(nπδ), t − 1)|(u, t) ∈ [0, 1/n]× I^{→}}

with topology induced from ℝ^{3} and partial order in terms of the (u, t) coordinates: (u, t_{1}) ⩽ (u, t_{2}) if t_{1} ⩽ t_{2}.

Let γ_{n}(t) = (\frac{t}{n} cos(nπδ), \frac{t}{n} sin(nπδ), t − 1). Then γ_{n} is a dipath in CS. Moreover, the sequence [γ_{n}] in C̃S_{(0,0,−1)} converges to γ, where γ(t) = (0, 0, t − 1): Let U be a neighborhood of (0, 0, 0) in ℝ^{3} and let B((0, 0, 0), r), be an open ball contained in U. Then for n > 1/r, γ_{n} ∼_{U∩CS} γ via the dihomotopy H(s, t) = (s\frac{t}{n} cos(nπδ), s\frac{t}{n} sin(nπδ), t − 1), so [γ_{n}] ∈ U_{[γ]}. And this is the convergence condition.

Now define ĈS to be CS with an extra open set:

V = ⋃_{n=1}^{∞}\{(tu cos(nπδ), tu sin(nπδ), t − 1)|(u, t) ∈ [0, \frac{1}{2n}[× I^{→}\}

Let P : ĈS → CS be the identity map. This is a dicovering w.r.t. (0, 0, −1): It is continuous, dipaths in CS are segments of lines from (0, 0, −1) and such lines are also dipaths in ĈS. Similarly, dihomotopies in CS are still dihomotopies in ĈS, since H^{−1}(V) is open whenever H is a dihomotopy.

Now ϕ([γ_{n}]) = γ_{n}(1) = (\frac{1}{n} cos(nπδ), \frac{1}{n} sin(nπδ), 0) ∉ V, so ϕ([γ_{n}]) does not converge to ϕ(γ) = (0, 0, 0) and hence ϕ is not continuous.

Proposition 4.8. Let P : X̂x̂_{0} → X_{x_{0}} be a dicovering with P^{−1}(x_{0}) = x̂_{0}. Then ϕ : X̃_{x_{0}} → X̂x̂_{0} has unique dipath lifting and unique dihomotopy lifting for dipaths and dihomotopies with initial point x̂_{0}.

Proof. Let μ : ( I^{→}, 0) → (X̂x̂_{0}, x̂_{0}) Then P ∘ μ lifts uniquely to X̃_{x_{0}} and it is not hard to see, that this is a lift of μ. Suppose η is another lift. Then μ(t) = ϕ ∘ η(t) = { \atop Π ∘ η}_{|[0,t]}(1). Hence μ is the unique lift of Π ∘ η, so P ∘ μ = Π ∘ η and we conclude that η is the unique lift of P ∘ μ.

The same argument goes for dihomotopies.

From this we see that if ϕ is continuous, it is in fact a dicovering.

5. Concluding remarks.

We have given a definition of the universal covering of a local po-space with some diconnectedness properties. This is very similar to the non-directed situation and indeed, the basic ideas are the same.

From the various examples, it is clear that the category of local po-spaces, even with the extra requirements in 2.9 and 3.6, is too large to give good covering properties.

For a good category, one should expect the projection map Π in the universal dicovering and also the projections in a general dicovering to be a local dihomeomorphism on local futures, i.e., a more satisfying property 2 in 3.11. Moreover, we would require that the map ϕ in 4.6 is continuous and hence a dicovering and that ϕ is the universal dicovering. The geometric realization of a semi cubical complex as in [2] should has some of these properties. This is because the local topology of semi cubical complexes is a (union of) products of I^{→}, and since dipaths lift. We will study this in a follow up to [2].

There is another notion of dihomotopy which is used by M. Grandis ([4]). An elementary dihomotopy is a dimap from I^{→} × I^{→}, and the equivalence relation is the symmetric transitive closure of this. The construction of the universal dicover and in particular the definition of the topology can be copied almost verbatim to that case. Some of the examples do not work in that setting. For semi cubical complexes, this notion of dihomotopy and the one we use her, are equivalent; a fact which we proved recently and did not yet publish. Hence the covering theory with the two notions of dihomotopy is also the same in that category.

Another question is: What are the decktransformations? We already know that the fiberdimension at a point x of a dicovering X̂_{x_{0}} is less than π^{→}_{1} (X, x_{0}, x), and other connections to the different fundamental categories defined in [8] should be investigated.

More generally, one should give a good definition of difibrations and dicofibrations.

References

[1] L. Fajstrup, E. Goubault, and M. Raußen, Detecting Deadlocks in Concurrent Systems, CONCUR’98; Concurrency Theory (Nice, France) (D. Sangiorgi and R. de Simone, eds.), Lect. Notes Comp. Science, vol. 1466, Springer-Verlag, September 1998, 9th Int. Conf., Proceedings, pp. 332 – 347.

[2] , Algebraic topology and concurrency, Tech. Report R-99-2008, Department of Mathematical Sciences, Aalborg University, 9220 Aalborg Øst, June 1999.

[3] E. Goubault, The Geometry of Concurrency, Ph.D. thesis, Ecole Normale Superieure, Paris, 1995.

[4] M. Grandis, Directed Homotopy Theory I. The Fundamental Category, Tech. Report 443, Dip. di Matematica dell’ Univ. di Genova, 2001, to appear in Cahiers Top. Géom. Diff. Catég.

[5] J. Gunawardena, Homotopy and concurrency, Bulletin of the EATCS 54 (1994), 184–193.

[6] P.J.Higgins, Categories and groupoids, Van Nostrand, 1971.

[7] V. Pratt, Modeling concurrency with geometry, Proc. of the 18th ACM Symposium on Principles of Programming Languages. (1991).

[8] M. Raussen, State Spaces and Dipaths up to Dihomotopy, Tech. Report R-01-2023, Department of Mathematical Sciences, Aalborg University, DK-9220 Aalborg Øst, 2001, revised version to appear in Homology Homotopy Appl.

[9] S.Sokolowski, Investigation of concurrent processes by means of homotopy functors, to appear in Math. Struct Comp. Sci. (2001).

This article may be accessed via WWW at http://www.rmi.acnet.ge/hha/ or by anonymous ftp at

ftp://ftp.rmi.acnet.ge/pub/hha/volumes/2003/n2a1/v5n2a1.(dvi,ps,pdf)

Lisbeth Fajstrup fajstrup@math.auc.dk

Department of Mathematics Aalborg Universitet 9100 Aalborg Denmark