Ideas from Zariski topology in the study of cubical sets, cubical maps, and their homology

Tomasz Kaczynski ^{∗} Marian Mrozek ^{†} Anik Trahan

January 24, 2005

Abstract

Cubical sets and their homology have been used in dynamical systems as well as in digital imaging. We take a refreshing view on this topic, following Zariski ideas from algebraic geometry. The cubical topology is defined to be a topology in ℝ^{d} in which a set is closed if and only if it is cubical. This concept is a convenient frame for describing a variety of important features of cubical sets. Separation axioms which, in general, are not satisfied here, characterize exactly those pairs of points which we want to distinguish. The noetherian property guarantees the convergence of algorithms. Moreover, maps between cubical sets which are continuous and closed with respect to the cubical topology are precisely those for whom the homology map can be defined and computed without grid subdivisions. A combinatorial version of the Vietoris-Begle is derived and used for an algorithm computing homology of maps which are continuous with respect to the Euclidean topology.

∗Research supported by a grant from NSERC †Research supported by Polish KBN grant no. 2 P03A 041 24 02000 Mathematics Subject Classification: Primary 55-04; Secondary 52B05, 54C60, 68W05, 68W30, 68U10.

1 Introduction

Representable sets, in particular, cubical sets, and their homology have proved to be useful geometric structures in a variety of applications from the Conley index in dynamical systems [8, 12, 15, 16] to image and pattern recognition in digital imaging [2, 3, 8]. We take a new refreshing view on this topic, following Zariski ideas from algebraic geometry. Recall from [4, 7] that the Zariski topology in the Euclidean space ℝ^{d} is defined by declaring that a proper subset of ℝ^{d} is closed if and only if it is algebraic. The cubical topology is a topology in ℝ^{d} in which a proper subset is closed if and only if it is cubical.

It seems foolish at first to abandon the standard Euclidean topology and introduce one which is not metrizable — more than that — which does not satisfy any separation axiom! Nevertheless, the points which we want to distinguish in a cubical set are exactly those which belong to different cells or different elementary cubes, thus, the points separated by the cubical topology. In digital imaging, computer scientists seem to have a hard time deciding if they prefer to interpret pixels as unit size squares or as isolated points in a square grid. The cubical topology permits these two interpretations co-exist on mathematical grounds.

Cubical topology has some more interesting features. A crucial property of the Zariski topology, related to the Hilbert Nullstellensatz is that it is noetherian, that is, every decreasing sequence of closed sets eventually becomes constant. That the cubical topology is noetherian is quite obvious but the simplicity of this observation does not diminish its importance: In fact, all algorithms constructing isolating neighborhoods and index pairs in dynamics are based on this property. Also, irreducible closed sets are precisely elementary cubes. Moreover, maps f : X → Y between cubical sets which are continuous and closed with respect to the cubical topology are precisely those for whom the homology map H_{∗}(f) can be defined and computed without grid rescaling (the concept of rescaling is defined in [8]) or, equivalently, without grid subdivisions. Although this class of maps, called cubical maps, seems somewhat restrictive, its study leads to algorithms for constructing homology of maps which are continuous with respect to the Euclidean topology.

This paper is organized as follows. In Section 2, definitions and properties of cubical sets, cubical chain complex, and representable sets are recalled from [8]. Note that the cubical chain complex studied here is a combinatorial concept in contrast with a well known but less suitable for algorithms concept of singular cubical complex presented for instance in [9]. In Section 3, definition and properties of cubical topology are presented. For some routine proofs we refer to [17]. In Section 4, we define the class of cubical maps as the class of maps on cubical sets which are continuous and closed with respect to the relative cubical topology. We discuss the relation of this definition to the one given in [5], and give an explicit formula for a cubical map in terms of it’s coordinate functions. Using that formula, the homomorphism induced in homology by a cubical map is constructed. In Section 4.3 a combinatorial version of the Vietoris-Begle Theorem (see, e.g. [6] for one of classical formulations) is derived for cubical maps. In Section 5, we show how that result is used for constructing the homology of maps on cubical sets which are continuous in Euclidean topology. The construction is based on ideas from [6] and [1], and it has been implemented in [10]. The related algorithm is presented in Section 6.

2 Preliminaries

We recall here from [8] basic terminology related to cubical sets, cubical chain complex, and representable sets. The proofs of all statements of this section can be found in [8] except for Proposition 2.1 which is proved in [17].

2.1 Cubical Sets

An elementary cube is a finite product of intervals

Q = I_{1} × I_{2} × … × I_{d} ⊂ ℝ^{d},  (1)

where I_{i} is either a unit interval [l_{i}, l_{i} + 1] or a point (degenerated interval) [l_{i}, l_{i}] = [l_{i}] := {l_{i}}, and l_{i} ∈ ℤ, ℤ the set of all integers. The set of all elementary cubes is denoted by K and the set of those which are in ℝ^{d} for a specific d is denoted by K^{d}. The number d in (1) is called the embedding number of Q and is denoted by emb Q. The dimension of Q is the number of non-degenerated intervals I_{i} of the form [l_{i}, l_{i} + 1] in (1) is called the dimension and is denoted by dim Q. We put

K_{k} := {Q ∈ K | dim Q = k}

and

K_{k}^{d} := K^{d} ∩ K_{k}.

Let Q, P ∈ K. If Q ⊂ P, then Q is a face of P. If Q ⊂ P and Q ≠ P, then Q is a proper face of P.

Proposition 2.1 Let Q ∈ K_{k}^{d}, then Q has 3^{k} faces.

A set X ⊂ ℝ^{d} is cubical if X can be written as a finite union of elementary cubes.

Given a cubical set X ⊂ ℝ^{d}, we denote by K(X), respectively K_{k}(X), the set of those Q ∈ K^{d}, respectively in Q ∈ K_{k}^{d}, that Q ⊂ X. If Q ∈ K(X) is not a proper face of some P ∈ K(X), then it is called a maximal face in X. The set of maximal faces in X is denoted by K_{max}(X).

2.2 Cubical Chain Complex

The group C_{k}^{d} of k-dimensional chains of ℝ^{d} (k-chains for short) is the free abelian group generated by K_{k}^{d}. By definition, the elements of C_{k}^{d} are functions c : K_{k}^{d} → ℤ such that c(Q) = 0 for all but a finite number of Q ∈ K_{k}^{d}. We distinguish between the geometric objects, elementary cubes Q ∈ K_{k}^{d}, and the corresponding algebraic objects, their duals Q̂ : K_{k}^{d} → ℤ, defined on any P ∈ K^{d} by

Q̂(P) := \{ \begin{matrix}1 & if P = Q, \\ 0 & otherwise, \end{matrix}  (2)

The set {Q̂ | Q ∈ K_{k}^{d}} is the canonical basis for C_{k}^{d}.

We put C_{k}^{d} = 0 if k > d, k < 0, or d < 0. In order to define the chain complex structure for the collection of groups {C_{k}^{d}}_{k∈ℤ}, we first need the following auxiliary operation.

Given P ∈ K_{k}^{d} and Q ∈ K_{k′}^{d′}, we have P × Q ∈ K_{k+k′}^{d+d′}. Set

P̂ ⋄ Q̂ := { \atop P × Q}.

This definition extends to arbitrary chains c_{1} ∈ C_{k}^{d} and c_{2} ∈ C_{k′}^{d′} by

c_{1} ⋄ c_{2} := ∑_{P ∈K_{k},Q∈K_{k′}} c_{1}(P)c_{2}(Q){ \atop P × Q}.

The chain c_{1} ⋄ c_{2} ∈ C_{k+k′}^{d+d′} is called the cubical product of c_{1} and c_{2}. Given k ∈ ℤ, the cubical boundary map

∂_{k} : C_{k}^{d} → C_{k−1}^{d}

is a homomorphism defined on generators Q̂, where Q ∈ K_{k}^{d}, by induction on the embedding number d as follows.

Let first d = 1. Then Q = [l] ∈ K_{0}^{1} or Q = [l, l + 1] ∈ K_{1}^{1} for some l ∈ ℤ. Define

∂_{k}Q̂ := \{ \begin{matrix}0 & if Q=[l], \\ { \atop [l + 1]} − ˆ[l] & if Q = [l, l + 1]. \end{matrix}

Let d > 1 and Q = ∏_{i=1}^{d} I_{i}, where I_{i} are intervals (some possibly degenerated) in ℝ. Put I = I_{1} and P = ∏_{i=2}^{d} I_{i}. Then Q̂ = Î⋄ P̂. Define

∂_{k}Q̂ := ∂_{k_{1}} Î⋄ P̂ + (−1)^{dim I} Î⋄ ∂_{k_{2}} P̂,  (3)

where k_{1} = dim I and k_{2} = dim P. Finally, we extend the definition to all chains by linearity. It is shown in [8] that cubical boundary maps satisfy the algebraic condition for a boundary map in an arbitrary chain complex, that is,

∂_{k} ∘ ∂_{k+1} = 0,  (4)

for all k ∈ ℤ. Thus C := {C_{k}, ∂_{k}}_{k∈ℤ} is a chain complex. We shall now localize this chain complex to cubical sets. The support of a chain c ∈ C_{k}^{d} is the cubical set

|c| := ⋃ {Q ∈ K_{k}^{d} | c(Q) ≠ 0} .

Given a cubical set X ⊂ ℝ^{d}, we define

C_{k}(X) = {c ∈ C_{k}^{d} | |c| ⊂ X} .  (5)

C_{k}(X) is a finitely generated free abelian group and the set {Q̂ | Q ∈ K_{k}(X)} is its basis called canonical basis. We also have

∂_{k}(C_{k}(X)) ⊂ C_{k−1}(X).

Hence, the restricted boundary map ∂_{k}^{X} : C_{k}(X) → C_{k−1}(X) is well defined and

C(X) := {C_{k}(X), ∂_{k}^{X}}_{k∈ℤ} ,

is a chain complex called cubical chain complex of X. When X it is clear from the context, we will use the notation ∂_{k} for the restricted map ∂_{k}^{X}.

The homology of X is the collection H_{∗}(X) = {H_{k}(X)}_{k∈ℤ} of quotient groups

H_{k}(X) := Z_{k}(X)/B_{k}(X),

where Z_{k}(X) := ker ∂_{k}^{X} is the group of k-cycles of X and B_{k}(X) := im ∂_{k+1}^{X} is the group of k-boundaries of X.

2.3 Representable Sets

Note that any cubical set X ⊂ ℝ^{d} is closed and bounded. Intersections and finite unions of cubical sets are cubical. We want to obtain a larger class of sets, closed under the substraction X \ Y.

Given any elementary cube Q = I_{1} × I_{2} × … × I_{d}, the corresponding elementary cell

Q^{∘} = I^{∘}_{1} × I^{∘}_{2} × … × I^{∘}_{d}

is the set obtained by replacing all non-degenerated closed intervals I_{i} = [l_{i}, l_{i} + 1] in the expression for Q by the open ones I^{∘}_{i} = (l_{i}, l_{i} + 1), while

I^{∘}_{i} := I_{i} if I_{i} = [l_{i}].

Proposition 2.2 Elementary cells have the following properties:

(i) ℝ^{d} = ⋃{Q^{∘} | Q ∈ K^{d}}.

(ii) If A ⊂ ℝ^{d} is bounded then the set {Q ∈ K^{d} | Q^{∘} ∩ A ≠ ∅} is finite.

(iii) If P, Q ∈ K^{d}, then P^{∘} ∩ Q^{∘} = ∅ or P = Q.

(iv) For every Q ∈ K, cl Q^{∘} = Q.

(v) Q ∈ K^{d} implies that Q = ⋃{P^{∘} | P ∈ K^{d} such that P^{∘} ⊂ Q}.

(vi) If X is a cubical set and Q^{∘} ∩ X ≠ ∅ for some elementary cube Q, then Q ⊂ X.

A set Y ⊂ ℝ^{d} is called representable if it is a finite union of elementary cells. The family of representable sets in ℝ^{d} is denoted by R^{d}.

Proposition 2.3 Representable sets have the following properties:

(i) Every elementary cube is representable.

(ii) If A, B ∈ R^{d}, then A ∪ B, A ∩ B, A \ B ∈ R^{d}.

(iii) A set X ⊂ ℝ^{d} is cubical if and only if it is closed and representable.

(iv) A bounded set A ⊂ ℝ^{d} is representable if and only if for every Q ∈

K^{d}, Q^{∘} ∩ A ≠ ∅ implies Q^{∘} ⊂ A.

Let A ⊂ ℝ^{d} be a bounded set. Then the open hull of A is

oh (A) := ⋃{Q^{∘} | Q ∈ K, Q ∩ A ≠ ∅},  (6)

and the closed hull of A is

ch (A) := ⋃{Q | Q ∈ K, Q^{∘} ∩A ≠ ∅}.  (7)

Proposition 2.4 Assume A ⊂ ℝ^{d}. Then

(i) oh (A) = ⋂{U ∈ R^{d} | U is open and A ⊂ U}.

(ii) ch (A) = ⋂{B ∈ R^{d} | B is closed and A ⊂ B}.

3 Cubical Topology

It is obvious that a union of a finite family of cubical sets in ℝ^{d} is a cubical set and easy to show that the intersection of any family of cubical sets is a cubical set. Thus the following definition makes sense.

Definition 3.1 The cubical topology in ℝ^{d} is defined by the family V^{d} of closed sets given by

V^{d} := {X ∈ ℝ^{d} | X is a cubical set} ∪ {∅, X}.

More precisely, the family T^{d} of open sets called the cubical topology in ℝ^{d} is given by

U ∈ T^{d} if and only if ℝ^{d} \ U ∈ V^{d}.

Note that open sets, the complements of cubical sets, are unbounded. In particular, representable sets which are open with respect to Euclidean topology are not open in cubical topology. This slight inconvenience may be avoided by restricting the topology to a fixed cubical set X ⊂ ℝ^{d} which is always done in practical applications. Let

T_{|X} := {U ∩ X | U ∈ T^{d}}

be the relative cubical topology of X. It is easily verified that

Proposition 3.2 Let X be a cubical set. A set U ⊂ X is in T_{|X} if and only if U is open in the relative Euclidean topology of X and representable.

It is easy to see that the cubical topology does not satisfy any separation axioms. For example, points in the open interval (1, 2) ⊂ ℝ cannot be separated in the sense of any axiom. We introduce the following refinement of two axioms of our interest.

Definition 3.3 Let (X, T ) be a topological space and x, y ∈ X. We say that

(i) The points x and y are T_{0}-separable if there exists U ∈ T which contains exactly one of those two points.

(ii) The points x and y are T_{1}-separable if there exist U, W ∈ T such that U contains x and not y and W contains y and not x.

(iii) The points x and y are T_{2}-separable or Hausdorff-separable if there exist U, W ∈ T such that U ∩ W = ∅, x ∈ U and y ∈ W.

Proposition 3.4 Consider the cubical topology T^{d} and let x, y ∈ ℝ^{d}. Then

(i) The points x and y are T_{0}-separable if and only if they are in distinct

elementary cells P^{∘}, Q^{∘}.

(ii) The points x and y are T_{1}-separable if and only they are in distinct

elementary cells P^{∘}, Q^{∘}, such that neither P ⊂ Q nor Q ⊂ P.

(iii) Let X be a cubical set with the restricted cubical topology T_{|X} and let x, y ∈ X. The points x and y are T_{2}-separable in X if and only if oh (x) ∩ oh (y) = ∅.

Proof: (i) Suppose that x and y are T_{0} separable, and let U ∈ T be a set with x ∈ U, y ∉ U. Then Y = ℝ^{d} \ U is a cubical set containing y. By Proposition 2.2(i) and Proposition 2.3(iii) both U and Y are unions of elementary cells, hence there exist P, Q ∈ K such that x ∈ P^{∘} ⊂ U and

y ∈ Q^{∘} ⊂ Y. Since U and Y are disjoint, so are P^{∘} and Q^{∘}.

Now suppose that there exist distinct cells P^{∘} and Q^{∘} such that x ∈ P^{∘}

and y ∈ Q^{∘}. If x ∉ Q then we may take U = ℝ^{d} \ Q. Then x ∈ U and y ∉ U. If y ∉ P then we may take U = ℝ^{d} \ P and the conclusion follows the same way. If neither of these assumptions hold, then x ∈ Q ∩ P^{∘} and

y ∈ P ∩ Q^{∘}. Then Proposition 2.3(iv) implies that P^{∘} ⊂ Q and Q^{∘} ⊂ P. By Proposition 2.2(iv), P = Q, a contradiction.

(ii) Suppose that x and y are T_{1} separable, let U ∈ T be a set with x ∈ U, y ∉ U and W ∈ T be a set with y ∈ W, x ∉ W. Then x ∈ U \ W and y ∈ W \ U. Since U and W are both unions of elementary cells, there

are cells P^{∘} and Q^{∘} such that x ∈ P^{∘} ⊂ U \ W and y ∈ Q^{∘} ⊂ W \ U. It remains

to show that P ⊄ Q and Q ⊄ P. We have Q^{∘} ∩ U = ∅. Since U is open in

T , it is also open in the Euclidean topology, and since Q = cl Q^{∘}, it follows that Q ∩ U = ∅. If P ⊂ Q, we get a contradiction to P^{∘} ⊂ U. The argument for Q ⊄ P is analogous.

Now suppose that there exist distinct cells P^{∘} and Q^{∘} such that x ∈ P^{∘},

y ∈ Q^{∘}, P ⊄ Q, and Q ⊄ P. If x ∉ Q and y ∉ P then we may take U = ℝ^{d} \ Q, W = ℝ^{d} \ P and the conclusion follows as in the proof of (i). If one of these assumptions fails, for example x ∈ Q, then we show, as in (i), that P^{∘} ⊂ Q, so P = cl P^{∘} ⊂ Q, a contradiction.

(iii) By Proposition 2.4(i), oh (x) and oh (y) are the smallest open (in the Euclidean topology) representable sets containing respectively x and y. Therefore the conclusion follows from Proposition 3.2.

Cubical topology has analogous properties to Zariski topology. This analogy is exhibited in the following definitions and propositions.

Definition 3.5 A topological space (X, T ) is called noetherian if, given any decreasing family V_{1} ⊃ V_{2} ⊃ V_{3} ⊃ ⋯ of closed sets, there exists an integer n ≥ 1 such that V_{n} = V_{n+j} for all j ∈ ℕ.

Proposition 3.6 The space (ℝ^{d}, T^{d}) is noetherian.

Proof: Consider a decreasing sequence V_{1} ⊃ V_{2} ⊃ V_{3} ⊃ ⋯ of closed sets. If V_{i} = ℝ^{d} for all i or V_{n} = ∅ for a sufficiently large n, the conclusion is obviously satisfied, so we may assume that there exists k such that X_{i} is a cubical set for all i ≥ k. In in particular, X_{k} can be written as X_{k} = ⋃_{j=1}^{m} Q_{j}, where Q_{j} ∈ K^{d}. By Proposition 2.1, there exists at most m3^{d} elementary cubes included in X_{k} and at most 2^{m3^{d}} − 2 proper cubical subsets of X_{2}. Thus V_{i+1} = V_{i} for all but finitely many i, and the conclusion follows.

Definition 3.7 Let (X, T ) be a topological space. A closed set V ⊂ X is irreducible if, given any decomposition V = V_{1} ∪ V_{2} with V_{1}, V_{2} closed, we must have V = V_{1} or V = V_{2}.

Proposition 3.8 Let V ∈ V^{d}. Then V is irreducible if and only if V = ℝ^{d} or V is an elementary cube.

Proof: First, observe that ℝ^{d} is irreducible because all other elements of V^{d} are cubical sets. Cubical sets are bounded and ℝ^{d} is not, so it cannot be a union of two cubical sets. Let V ⊂ ℝ^{d} be an irreducible closed set. If V ≠ ℝ^{d}, then V is a cubical set, so it may be written as a union of n elementary cubes, V = ⋃_{i=1}^{n} Q_{i}, Q_{i} ∈ K^{d}. We argue by induction on n that V is an elementary cube. If n = 1, V = Q_{1} is an elementary cube. If n > 1, consider the decomposition V = V_{1} ∪ V_{2} with V_{1} = Q_{1} and V_{2} = ⋃_{i=2}^{n} Q_{i}. Since V is irreducible, either V = V_{1} or V = V_{2} and the induction hypothesis applies to both cases.

Suppose that V = Q is an elementary cube and consider its decompo-

sition Q = V_{1} ∪ V_{2} to two closed, hence cubical, subsets. Then the cell Q^{∘} intersects either V_{1} or V_{2} and the conclusion follows from Proposition2.2(iv).

Proposition 3.9 For any V ∈ V^{d} there exists a unique family of irreducible sets {V_{k}}_{k=1,2,...n} such that V_{j} ⊄ V_{k} for j ≠ k and V = ⋃_{k=1}^{n} V_{k}.

Proof: The set V = ℝ^{d} is irreducible, so we may assume that V is a cubical set, hence, it can be written as a finite union of elements of K^{d}. By the definition of a maximal face, it can be written as

V = ⋃{Q ∈ K^{d} | Q ∈ K_{max}(X)}.

This union extends over a finite set and it remains to show that it is unique. Suppose that V = ⋃_{k=1}^{n} V_{k} where V_{k} are irreducible and V_{j} ⊄ V_{k}. By Proposition 3.8, V_{k} is an elementary cube for each k. We need to show that

{V_{k} | k = 1, … n} = K_{max}(V).

Suppose that Q ∈ K_{max}(V). Since ⋃_{k=1}^{n} V_{k} = V, there exists k such that Q ∩ V_{k} ≠ ∅. By Proposition 2.2(vi), Q ⊂ V_{k}. Since Q is maximal, Q = V_{k}. Thus

K_{max}(V) ⊂ {V_{k} | k = 1, … n}.  (8)

The reverse inclusion is shown by contradiction. Suppose that V_{j} ∉ K_{max}(V) for some j. Then there exists Q ∈ K_{max}(V) such that V_{j} is a proper face of Q. By (8), Q = V_{k} for some k. But V_{j} ⊄ V_{k}, a contradiction.

We end this section with a remark that the statements of all propositions in this section hold true for relative cubical topology in a given cubical set.

4 Cubical Maps and Their Homology

4.1 Cubical Maps

In Section 2 the definition of homology of a cubical set is recalled. We want now to extend this definition to maps f : X → Y where X, Y ⊂ ℝ^{d} are cubical sets. Following [5], we would like to define the homomorphism H_{∗}(f) induced in homology for a class maps satisfying the following two conditions:

1. f(Q) ∈ K(Y) for every Q ∈ K(X),

2. The restriction f_{|Q} to every Q ∈ K(X) is affine linear.

These conditions somewhat mimic the definition of simplicial maps in the simplicial homology theory. The difference between these two classes of maps is that, vertices of a simplex are affine independent whereas vertices of an elementary cubes are not. Thus, any simplicial vertex map admits a unique linear extension to each simplex and the passage from a combinatorial concept of a simplicial vertex map to a topological concept of a piecewise continuous map is very natural. This is not true for maps defined on vertices of elementary cubes which causes that the condition (2) is restrictive and not natural. However, the only purpose of this condition is to obtain a continuous map. When the cubical topology introduced in Section 3 is considered, the condition (2) is not necessary and the definition of a cubical map can be stated as follows.

Definition 4.1 Let X, Y be cubical sets. A map f : X → Y is called a cubical map if it is a continuous and closed map with respect to the relative cubical topology in X and Y.

Here is a more explicit equivalent formulation:

Proposition 4.2 Let X, Y be cubical sets. A map f : X → Y is a cubical map if and only if it

(a) f^{−1}(Q) is a cubical set for every Q ∈ K(Y),

(b) f(Q) ∈ K(Y) for every Q ∈ K(X).

Proof: By definition of the relative cubical topology, f is continuous if and only if f^{−1}(A) is a cubical set in X for every cubical set A in Y. Since every cubical set is a finite union of elementary cubes and a finite union of cubical sets is a cubical set, this is equivalent to (a).

Again by definition, f is a closed map if and only if f(A) is a cubical set in Y for every cubical set A in X. By the previous arguments, this is equivalent to the condition that f(Q) is a cubical set for every Q ∈ K(X). We show, by contradiction, that f(Q) must be an elementary cube. Suppose that f(Q) is a cubical set which is not an elementary cube. By Proposition 3.8, there are two cubical sets R and S, neither equal to f(Q), such that f(Q) = R ∪ S. Then Q = f^{−1}(R) ∪ f^{−1}(S). Since Q is irreducible and f^{−1}(R) and f^{−1}(S) are cubical, we must have Q = f^{−1}(R) or Q = f^{−1}(S), so f(Q) = R or f(Q) = S, a contradiction.

The following property of cubical maps will be used later:

Proposition 4.3 Let X, Y be cubical sets and f : X → Y a cubical map. For any Q ∈ K(X)

dim f(Q) ≤ dim Q.

Proof: We argue by induction on the dimension k = dim Q. If k = 0, Q is a singleton and so is f(Q), hence dim f(Q) = dim Q = 0. Suppose that the conclusion holds for a given k ≥ 0. Let Q ∈ K_{k+1}(X) and m = dim f(Q). If m = 0, we are done. If m > 0, there are two opposite faces P_{+} and P_{−} of f(Q) of dimension m − 1. Since P_{+} and P_{−} are disjoint elementary cubes, f^{−1}(P_{+}) and f^{−1}(P_{−}) are two disjoint proper cubical subsets of Q. Therefore, dim f^{−1}(P_{+}) ≤ k and dim f^{−1}(P_{−}) ≤ k. By induction hypothesis, k ≤ m − 1, so dim Q = k + 1 ≤ m = dim f(Q).

The identity map id_{X} obviously is a cubical map and it is easy to check that the composition g ∘ f of two cubical maps is a cubical map. Thus we may form a category Cub whose objects are cubical sets and morphisms are cubical maps.

Note that cubical maps are not necessarily continuous with respect to the Euclidean topology. For example, any surjective function f : [0, 1] → [0, 1] such that f^{−1}({0, 1}) = {0, 1} is a cubical map. We can modify values of a cubical function inside elementary cells freely as long as images of elementary cubes remain the same. Therefore it makes sense to define an equivalence relation for cubical maps f, g : X → Y by setting f ∼ g if and only f(Q) = g(Q) for all Q ∈ K(X). The equivalence class of f is called the cubical class of f. We will soon see that any cubical map contains, in its cubical class, a representative which is continuous and whose restriction to any elementary cube is affine linear, that is, a linear map possibly composed with a translation. Before proceeding further, it is helpful to have some examples of cubical maps.

Example 4.4 An inclusion of cubical sets i : A ↪ X is a cubical map. The following maps of the Euclidean space, when restriced to a cubical set and its image, become cubical maps:

1. Projection p : ℝ^{d} → R^{d−1}, p(x) = (x_{2}, x_{3}, … x_{d});

2. Coordinate immersion, j : ℝ^{d} → ℝ^{d+1}; j(x) = (m, x_{1}, x_{2}, …, x_{d}), m ∈ ℤ;

3. Translation x ↦ m + x, where m ∈ ℤ^{d};

4. Transpose (x_{i}, x_{i+1}) ↦ (x_{i+1}, x_{i});

5. Inversion x_{i} ↦ −x_{i}.

A composition of cubical maps is a cubical map hence more maps can be generated from the above examples. We proceed towards an explicit formula which implies, in particular, that any cubical map can be obtained by composing the maps listed in Example 4.4, up to the cubical equivalence class.

In the sequel, the following notation is be helpful. We first put

ℕ_{d} = {1, 2, 3, …, d}.

Next, given an elementary cube Q = I_{1} × I_{2} × … × I_{d} ∈ K^{d}, we put

ess(Q) := {i ∈ ℕ_{d} | I_{i} is non-degenerate}.

Theorem 4.5 Let X ⊂ ℝ^{d} and Y ⊂ ℝ^{d′} be cubical sets. The cubical class of any cubical map g : X → Y contains a map f with the following property: For all Q ∈ K(X), the restriction of f = (f_{1}, f_{2}, …, f_{d′}) to Q can be expressed coordinate-wise by the formula

f_{i}(x) = m_{i} + ϵ_{i}x_{μ(i)},  (9)

where i ∈ ℕ_{d′}, m_{i} ∈ ℤ, ϵ_{i} ∈ {−1, 0, 1} and μ is a function from ℕ_{d′} to ℕ_{d}. Moreover, ϵ_{i} and m_{i} are uniquely determined by i, μ(i) is uniquely determined by i unless ϵ_{i} = 0, and the function ν_{f,Q} : ess(f(Q)) → ess(Q) such that ν_{f,Q}(k) = μ(k) is injective and uniquely determined by f and Q. Conversely, any map defined on elementary cubes in X by (9) is a cubical map.

Proof: The construction of f on each elementary cube Q goes by induction on k = dim Q.

Let k = 0. Then g(Q) ∈ K_{0}^{d′}(Y) by Proposition 4.3, so we may write

g(Q) = ∏_{i=1}^{d′}[l_{i}], l_{i} ∈ ℤ.

Hence f_{i}(Q) = l_{i} + 0 is a unique function of the form (9) except that μ arbitrary because ϵ_{i} = 0. The function ν_{g,Q} is not defined in this case because ess(g(Q)) = ∅ = ess(Q). Thus we may put f_{|Q} := g_{|Q}.

Suppose that the construction is done for all elementary cubes of dimension k ≥ 0 so that the restriction of g and f to the k’th skeleton of X,

X^{(k)} = ⋃{Q ∈ K_{i}(X) | i ≤ k}

satisfies the conclusion of the theorem. Consider Q ∈ K_{k+1}(X).

If ess(g(Q)) = ∅, we get as previously, g_{i}(Q) = l_{i} + 0 and f_{|Q} := g_{|Q}. If ess(g(Q)) ≠ ∅, choose n ∈ ess(g(Q)) and let

g_{n}(Q) = [r_{n}, r_{n} + 1].

Put

P = g(Q),

P_{0} = g_{1}(Q) × g_{2}(Q) × ⋯ × g_{n−1}(Q) × [r_{n}] × g_{n+1}(Q) × ⋯ × g_{d′}(Q),

and

Q_{0} = Q ∩ g^{−1}(P_{0}).

Since P_{0} is a proper face of P, Q_{0} ⊊ Q. It follows from Proposition 3.8 that Q_{0} is an elementary cube. Indeed, suppose that R_{1}, R_{2} are cubical sets such that Q_{0} = R_{1} ∪ R_{2}. Then g(R_{1}) ∪ g(R_{2}) = P_{0} but g is a cubical map and P_{0} is an elementary cube hence g(R_{1}) = P_{0} or g(R_{2}) = P_{0}. Consequently, R_{1} = Q_{0} or R_{2} = Q_{0}. Hence Q_{0} is an elementary cube and a proper face of Q. We show that dim Q_{0} = k. Indeed, if dim Q_{0} < k, there exists R_{0}K(X) such that Q_{0} ⊊ R_{0} ⊊ Q and then g(Q_{0}) = P_{0} ⊊ g(R_{0}) ⊊ g(Q) = P. This is impossible because the three sets are elementary cubes and dim g(Q) = dimP_{0} + 1. Thus dim Q_{0} = dim P_{0} = k.

By the induction hypothesis, f_{Q_{0}} is defined coordinate-wise by formulas f_{0i}(x) = m_{0i} + ϵ_{0i}x_{μ_{0}(i)}, i ∈ ℕ_{d′}, ϵ_{0i}, m_{0i} and μ_{0}(i) are uniquely determined by i. Since dim_{Q_{0}} = k, there is a unique j ∈ ess(Q) such that j ∉ ess(Q_{0}). The j’th component I_{j} of Q can be written as I_{j} = [l_{j}, l_{j} + 1] and the j’th component I_{0j} of Q_{0} is either [l_{j}] or [l_{j} + 1].

In the case I_{0j} = [l_{j}], we put f_{i}(x) = f_{0i}(x) for all i ≠ n and f_{n}(x) = r_{n} − l_{j} + x_{j}. This uniquely determines m_{n} = r_{n} − l_{j}, ϵ_{n} = 1 and μ(n) = j.

In the case I_{0j} = [l_{j} + 1], we put f_{i} = f_{0i} for all i ≠ n and f_{n} = r_{n} + 1 + l_{j} − x_{j}. This uniquely determines m_{n} = r_{n} + 1 + l_{j}, ϵ_{n} = −1 and μ(n) = j.

We show that ν_{f,Q} : ess(f(Q)) → ess(Q) such that ν_{f,Q}(k) = μ(k) an injective function. Consider a, b ∈ ess(f(Q)), a ≠ b. If a ≠ n and b ≠ n, then a, b ∈ ess(f(Q_{0})) and, by induction hypothesis, a ≠ b implies ν(a) ≠ ν(b). If a = n ≠ b, then ν(a) = ν(n) = j and b ∈ ess(f(Q_{0})). However, j is not in the image of ν_{f,Q_{0}}, hence ν(a) ≠ ν(b).

The converse statement is obvious.

Note that the coordinate function f_{i} in the formula (9) for a given elementary cube Q depends only on one coordinate of x, namely x_{μ(i)}. Thus, we may introduce cubical functions f^{i} : I_{μ(i)} → J_{i} defined on elementary intervals appearing in Q = ∏_{j=1}^{d} I_{j}, f(Q) = ∏_{i=1}^{d′} J_{i}, given by

f^{i}(t) = m_{i} + ϵ_{i}t.  (10)

With the help of these one-dimensional functions, the formulas (9) for i ∈ N_{d′} can be replaced by the formula

f(x) = (f^{1}(x_{μ(1)}), f^{2}(x_{μ(2)}), …, f^{d′}(x_{μ(d′)})) .  (11)

It is clear that the maps defined by (9) and (11) are affine linear on each elementary cube and since the formulas coincide on common faces of elementary cubes, they extend to a map f : X → Y which is continuous in Euclidean topology. Thus every cubical class contains a representative which is continuous in the traditional sense.

4.2 Induced Chain Maps

We shall now proceed towards the definition of H_{∗}(f), the homomorphism induced by a cubical map f.

First, let us introduced the following notation. Given A, B ⊂ ℕ and a function α : A → B, we define its sign by

sgn α := \{ \begin{matrix}(−1)^{card \{(i,j)∈A^{2}|α_{j}<α_{i}\}} & if α is bijective, \\ 0 & otherwise. \end{matrix}

where card stands for the number of elements of a set.

Definition 4.6 Let f : X → Y be a cubical map, X ⊂ ℝ^{d} and Y ⊂ ℝ^{d′} cubical sets. The homomorphism induced by f on k-chains f_{#k} : C_{k}(X) → C_{k}(Y) is defined on the generators Q̂ ∈ K_{k}^{d}(X) by induction on d as follows.

(a) Let k = 0 and d = 1. Then Q = [l] for some l ∈ ℤ and we put

f_{#0}( ˆ[l]) = { \atop [f(l)]}

(b) Let k = 1 and d = 1. Then Q = [l, l + 1] for some l ∈ ℤ and we put

f_{#1}({ \atop [l, l + 1]}) = \{ \begin{matrix}{ \atop [f(l), f(l + 1)]} & if f(l) < f(l + 1) \\ −{ \atop [f(l + 1), f(l)]} & if f(l) > f(l + 1) \\ 0 & if f(l) = f(l + 1) \end{matrix}

(c) Let d > 1, Q = ∏_{i=1}^{d} I_{i}, dim f(Q) = n, and let l_{1} < l_{2} < ⋯ l_{n} be the indices in ess(f(Q)). We define

f_{#k}(Q̂) = sgn (f, Q) ♢_{i=1}^{n} f_{#1}^{i}(Î_{ν_{f,Q}(l_{i})})  (12)

where sgn (f, Q) := sgn (ν_{f,Q}) is defined in Theorem 4.5, and f^{i} is defined in (10).

Note that the image of a k-chain is always a k-chain because if dim Q ≠ dim f(Q) then sgn (f, Q) = 0.

Theorem 4.7 The family of homomorphisms f_{#} := {f_{#k}} : C(X) → C(Y) is a chain map, that is, it commutes with the boundary operator. More explicitly, for any k ∈ ℕ, k ≠ 0 we have

∂_{k} ∘ f_{#k} = f_{#k−1} ∘ ∂_{k}.  (13)

Proof: Obviously it is enough to verify (13) on elements of the canonical basis Q̂ ∈ C(X). If emb Q = 1, the verification is straightforward. Thus assume Q = ∏_{i=1}^{d} I_{i} with d > 1. Let I_{i} = [a_{i}, b_{i}] for some a_{i} ∈ ℤ and b_{i} ∈ {a_{i}, a_{i} + 1}. Let μ : ℕ_{d′} → ℕ_{d} be as in Theorem 4.5. Let A := ess(Q), B := ess(f(Q)) and ν := ν(f, Q) = μ_{|B} : B → A. If ν is not a bijection then one easily verifies that both sides of (13) are zero. Thus assume that ν is a bijection. For i ∈ B put

s_{i} := card {ν(j) ∈ A | j < i} = card {j ∈ B | j < i} ,
p_{i} := card {j ∈ B | j < i and ν(j) > ν(i)} ,
n_{i} := card {j ∈ B | j > i and ν(j) < ν(i)} ,
t_{i} := card {j ∈ B | ν(j) < ν(i)} = card {ν(j) ∈ A | ν(j) < ν(i)} ,
B_{i} := B \ {i},
r_{i} := card {(l, m) ∈ B_{i}^{2} | l < m and ν(l) > ν(m)} ,
γ_{i} := (−1)^{∑_{j=1}^{i−1} dim f_{#}^{j}(Î_{ν(j)})},
ϵ_{i} := sgn (f, Q)γ_{i}.

Since ν is bijective, dim f_{#}^{i}(Î_{ν(i)}) = dim Î_{ν(i)}, therefore

γ_{i} = (−1)^{∑{i−1 \atop j=1} dim Î_{ν(j)}} = (−1)^{s_{i}}.

Let

Q_{a}^{i} := ∏_{j=1}^{i−1} I_{j} × [a_{i}] × ∏_{k=i+1}^{d} I_{k},

Q_{b}^{i} := ∏_{j=1}^{i−1} I_{j} × [b_{i}] × ∏_{k=i+1}^{d} I_{k}.

Note that ess(Q_{a}^{i}) = B_{i} =ess(Q_{b}^{i}), therefore sgn (f, Q_{a}^{i}) = (−1)^{r_{i}} = sgn (f, Q_{b}^{i}). Denote this common value by δ_{i}. We have

sgn (f, Q) = (−1)card^{{^{(l,m)∈B^{2}|l<m and ν(l)>ν(m)}}} = (−1)^{r_{i}+p_{i}+n_{i}}.

Therefore

δ_{i} = (−1)^{r_{i}} = sgn (f, Q)(−1)^{p_{i}+n_{i}}.

Consequently

ϵ_{i}δ_{i} = sgn (f, Q)^{2}(−1)^{s_{i}+p_{i}+n_{i}} = (−1)^{t_{i}}.

From equation (3) and definition 4.6 we get

(∂ ∘ f)_{#}(Q̂) = ∑_{i=1}^{d} ϵ_{i}( ♢_{h=1}^{i−1} f_{#}^{h}(Î_{μ(h)})) ⋄ ∂f_{#}^{i}(Î_{μ(i)}) ⋄ ( ♢_{h=i+1}^{d} f_{#}^{h}(Î_{μ(h)}))

= ∑_{i∈B} ϵ_{i}( ♢_{h=1}^{i−1} f_{#}^{h}(Î_{ν(h)})) ⋄ f_{#}^{i}({ \atop [b_{ν(i)}]}) ⋄ ( ♢_{h=i+1}^{d} f_{#}^{h}(Î_{ν(h)}))

− ∑_{i∈B} ϵ_{i}( ♢_{h=1}^{i−1} f_{#}^{h}(Î_{ν(h)})) ⋄ f_{#}^{i}({ \atop [a_{ν(i)}]}) ⋄ ( ♢_{h=i+1}^{d} f_{#}^{h}(Î_{ν(h)}))

= ∑_{i∈B} ϵ_{i}δ_{i}f_{#}(( ♢_{h=1}^{i−1} Î_{ν(h)}) ⋄ { \atop [b_{ν(i)}]} ⋄ ( ♢_{h=i+1}^{d} Î_{ν(h)}))

− ∑_{i∈B} ϵ_{i}δ_{i}f_{#}(( ♢_{h=1}^{i−1} Î_{ν(h)}) ⋄ { \atop [a_{ν(i)}]} ⋄ ( ♢_{h=i+1}^{d} Î_{ν(h)}))

= f_{#}(∑_{i∈B}(−1)^{t_{i}}( ♢_{h=1}^{i−1} Î_{ν(h)}) ⋄ ∂Î_{ν(i)} ⋄ ( ♢_{h=i+1}^{d} Î_{ν(h)}))

= f_{#}(∑_{l∈A}(−1)^{card^{{m∈A|m<l}}}( ♢_{h=1}^{l−1} Î_{h}) ⋄ ∂Î_{l} ⋄ ( ♢_{h=l+1}^{d} Î_{h}))

= f_{#}(∑_{l=1}^{d}(−1)^{∑{l−1 \atop j=1} dim Î_{j}}( ♢_{h=1}^{l−1} Î_{h}) ⋄ ∂Î_{l} ⋄ ( ♢_{h=l+1}^{i−1} Î_{h}))
= f_{#} ∘ ∂(Q̂).

The correctness of the following definition is a standard consequence of the property (13) of any chain map on chain complexes.

Definition 4.8 Let f : X → Y be a cubical map and f_{#} : C(X) → C(Y) the induced chain map. The homomorphism H_{k}(f) : H_{k}(X) → H_{k}(Y) induced by f_{#} on quotient groups is called the the kth homology of f. The family of maps H_{∗}(f) = {H_{k}(f)} : H_{∗}(X) → H_{∗}(Y) is called the homology map of f.

Lemma 4.9 The definition of a chain map induced by a cubical map is functorial in the following sense.

(a) Given a cubical set X, (id_{X})_{#k} = id_{C_{k}(X)} for all k,

(b) Given two cubical maps f : X → Y and g : Y → Z on cubical sets, g_{#k} ∘ f_{#k} = (g ∘ f)_{#k} for all k.

Proof: Let X ⊂ ℝ^{d}, Y ⊂ ℝ^{d′} and Z ⊂ ℝ^{d′′}. It is enough to verify (a) and (b) on elements of the canonical basis Q̂ ∈ K_{k}^{d}(X). Put Q = ∏_{i=1}^{d} I_{i}.

(a) Since ν_{id_{X,Q}} : ℕ_{d} → ℕ_{d} is the identity, we have

(id_{X})_{#k}(Q̂) = sgn(id_{X}, Q) ♢_{i=1}^{d}(id_{X})_{#1}Î_{ν(i)} = ♢_{i=1}^{d} Î_{i} = Q̂.

(b) Let first d = d′ = d′′ = 1. If dim Q = 0 then Q = [l] for some l ∈ ℤ and

(g_{#0} ∘ f_{#0}) [l] = g_{#0}{ \atop [f(l)]} = { \atop [(g ∘ f)(l)]} = (g ∘ f)_{#0} ˆ[l].

If dim Q = 1, then Q = [l, l + 1] for some l ∈ ℤ. Put a = f(l), b = f(l + 1), c = g(a), and d = g(b). We have

(g_{#1} ∘ f_{#1})({ \atop [l, l + 1]}) = \{ \begin{matrix}g_{#1} ˆ[a, b] & if a < b \\ −g_{#1} ˆ[b, a] & if b < a \\ g_{#1}0 & if a = b \end{matrix}

= \{ \begin{matrix}ˆ[c, d] & if a < b and c < d \\ − ˆ[d, c] & if a < b and d < c \\ − ˆ[d, c] & if b < a and d < c \\ ˆ[c, d] & if b < a and c < d \\ 0 & otherwise \end{matrix}

= \{ \begin{matrix}ˆ[c, d] & if c < d \\ − ˆ[d, c] & if d < c \\ 0 & otherwise \end{matrix}

= (g ∘ f)_{#1}({ \atop [l, l + 1]}).

Let now d, d′, d′′ ≥ 1 not all equal to 1. We use abbreviations ν_{f} = ν_{f,Q} and ν_{g} = ν_{f(Q)}g. We let k_{1} < k_{2} < ⋯ k_{m} be the essential indices of f(Q) and l_{1} < l_{2} < ⋯ l_{n} the essential indices of g(f(Q)).

By the linearity of g_{#} and by (12),

(g_{#k} ∘ f_{#k})(Q̂) = g_{#k} (sgn(f, Q) ♢_{i=1}^{m} f_{#k}^{k_{i}}Î_{ν_{f} (k_{i})})
= sgn(ν_{f}) g_{#k} ( ♢_{i=1}^{m} f_{#k}^{k_{i}}Î_{ν_{f} (k_{i})})
= sgn(ν_{f}) sgn(ν_{g}) ♢_{j=1}^{n} g_{#k}^{l_{j}} (f_{#k}^{ν_{f} (l_{j})}(Î_{ν_{f} (ν_{g}(l_{j}))})) .

Since sgn(σ ∘ τ) = sgn(σ) sgn(τ) for any permutations σ, τ, using the result proved in the case d = d′ = d′′ = 1, we get

(g_{#k} ∘ f_{#k})(Q̂) = sgn(ν_{f} ∘ ν_{g}) ( ♢_{j=1}^{n}(g^{l_{j}} ∘ f^{ν(l_{j})})_{#k}Î_{ν_{f} ∘ν_{g}(l_{j})})
= sgn(ν_{f} ∘ ν_{g}) ( ♢_{j=1}^{n}(g ∘ f)_{#k}^{l_{j}}Î_{ν_{f} ∘ν_{g}(l_{j})})
= sgn(ν_{g∘f}) ( ♢_{j=1}^{n}(g ∘ f)_{#k}^{l_{j}}Î_{ν_{f∘g}(l_{j})}) = (g ∘ f)_{#k}

By standard homological algebra arguments, Lemma 4.9 implies the following.

Theorem 4.10 H_{∗} is a functor from Cub to the category of graded groups. More explicitly,

(a) Given a cubical set X, H_{∗}(id_{X}) = id_{H_{∗}(X)},

(b) Given two cubical maps f : X → Y and g : Y → Z on cubical sets, H_{∗}(g) ∘ H_{∗}(f) = H_{∗}(g ∘ f).

The following examples are related to first three maps in Example 4.4.

Example 4.11 Assume A ⊂ X are cubical sets. If i : A → X is the inclusion map then i_{#} : C(A) → C(X) is also an inclusion map.

Example 4.12 Consider the elementary cubes Q = [0, 1]^{d}, Q′ = [0, 1]^{d−1} and the projection map p : Q → Q′ given by

p(x_{1}, x_{2}, x_{3}, …, x_{d}) := (x_{2}, x_{3}, …, x_{d}).

Any face P of Q can be written as P = I_{1} × P′, where I_{1} can be [0, 1], [0], or [1], and P′ = p(P) is a complementary face of P. The induced chain map p_{#} : C(Q) → C(Q′) is given by

π_{#k}(P̂) := \{ \begin{matrix}P̂′ & if I_{1} = [0] or I_{1} = [1], \\ 0 & otherwise. \end{matrix}  (14)

Example 4.13 Let Q and Q′ be as in Example 4.12. The map j : Q′ → Q given by

j(x_{1}, x_{2}, x_{3}, …, x_{d−1}) := (0, x_{1}, x_{2}, …, x_{d−1})

is a cubical map, and the induced chain map p_{#} : C(Q′) → C(Q) is given by

j_{#k}(c) := ˆ[0] ⋄ c.

Note that pj = id_{Q′}, therefore p_{#}j_{#} = (pj)_{#} = id_{C(Q′)}. Next, j_{#}p_{#} = (jp)_{#} is chain homotopic to id_{C(Q)}, with the chain homotopy D_{k} : C_{k}(Q) → C_{k+1}(Q) given by

D_{k}(P̂) := \{ \begin{matrix}ˆ[0, 1] ⋄ P̂′ & if I_{1} = [1], \\ 0 & if I_{1} = [0], \\ 0 & if I_{1} = [0, 1], \end{matrix}

where P = I_{1} × P′ ∈ K(Q) is as in Example 4.12. It follows that H_{∗}(pj) : H_{∗}(Q′) → H_{∗}(Q) is the inverse of H_{∗}(pj) : H_{∗}(Q) → H_{∗}(Q′). Consequently, H_{∗}(Q′) ≅ H_{∗}(Q).

From the result presented in Example 4.13, one can conclude, by induction on d, that Q = [0, 1]^{d} is acyclic, that is, its homology is isomorphic to homology of a point:

H_{k}(Q) ≅ \{ \begin{matrix}ℤ & if k = 0, \\ 0 & otherwise. \end{matrix}

That is probably the simplest way of proving it without using the homotopy invariance theorem, whose proof is more involved.

4.3 Combinatorial Vietoris Theorem

Here is a combinatorial version of the Vietoris Theorem [6].

Theorem 4.14 Let X, Y be cubical sets and f : X → Y a cubical map. If f is surjective and f^{−1}(Q) is acyclic for each Q ∈ K(Y) then f_{∗} : H_{∗}(X) → H_{∗}(Y) is an isomorphism.

Proof: We construct by induction a chain map

ψ = {ψ_{k} : C_{k}(X) → C_{k}(Y)}

and we prove that it is a homological inverse of f_{∗}.

Let k = 0. Let Q̂ ∈ C_{0}(X) be an elementary 0-chain. Since f is surjective and cubical, there exists a P ∈ K_{0}(X) such that f(P) = Q. Then f_{#}(P̂) = Q̂ and we put ψ_{0}(Q̂) := P̂.

Suppose now that k ≥ 1 and ψ_{i} : C_{i}(X) → C_{i}(Y) is constructed for i = 1, 2, … k − 1 so that

|ψ_{i}(Q̂)| ⊂ f^{−1}(Q) for all Q ∈ K_{i}(Y)  (15)
ψ_{i−1}∂_{i} = ∂_{i}ψ_{i}.  (16)

Note that then for any Q ∈ K_{k}(Y)

|ψ_{k−1} (∂Q̂)| ⊂ f^{−1} (|∂Q̂|) ⊂ f^{−1} (|Q̂|) ⊂ f^{−1}(Q).

By the induction hypothesis, ψ_{k−1}∂Q̂ ∈ ℤ_{k−1}(f^{−1}(Q)). Since f^{−1}(Q) is acyclic, its reduced homology H̃_{∗}(f^{−1}(Q)) is zero. Therefore, there exists a c ∈ C_{k}(f^{−1}(Q)) such that ∂c = ψ_{k−1}∂Q̂. In the case k > 1 this is straightforward while in the case k = 1 it follows from the fact that Q is an interval so, by the definition of Ψ_{0}, ψ_{0}∂Q̂ is a difference of two vertices, thus it is a reduced cycle. We put ψ_{k}Q̂ := c.

Thus the map ψ is constructed. We will show now that

f_{#} ∘ ψ = id_{C(Y)}.  (17)

The proof is again by induction. For k = 0 the assertion follows immediately from the definition of ψ_{0}. Suppose that ψ_{#i} ∘ ψ_{i} = id_{C_{i}(Y)} for 0 ≤ i ≤ k − 1. Given any Q ∈ K_{k}(Y), we have

∂Q̂ = f_{#k−1} ∘ ψ_{k−1}(∂Q̂) = ∂_{k} ∘ f_{#k} ∘ ψ_{k}(Q̂)

and, by the definition of ψ,

|f_{#k} ∘ ψ(Q̂)| ⊂ f(|ψ(Q̂)|) ⊂ f(f^{−1}(Q)) ⊂ Q.

Therefore f_{#k} ∘ ψ_{k}(Q̂) is a k-chain which has the same boundary as Q̂. It follows that f_{#k} ∘ ψ_{k}(Q̂) − Q̂ is a cycle in Q. However, H̃_{∗}(Q) = 0, hence, every k-cycle in Q is a boundary. Since dim Q = k, the only (k + 1)- dimensional boundary in Q is zero. Thus

f_{#k} ∘ ψ(Q̂) = Q̂.

In the last step we will show that ψ ∘ f_{#} is chain homotopic to id_{C(X)}. To do this we construct by induction a chain homotopy

D = {D_{i} : C_{i}(X) → C_{i+1}(X)}

such that

∂_{i+1} ∘ D_{i} + D_{i−1} ∘ ∂_{i} = ψ_{i} ∘ f_{#i} − id_{C_{i}(X)}  (18)
|D_{i}(c)| ⊂ f^{−1}(Q) for any c ∈ C_{i}(f^{−1}(Q)) and Q ∈ K_{i}(Y).  (19)

Let k = 0 and take any P ∈ K_{0}(X). Let Q := f(P) and let c := ψ_{0}(Q̂). Then ψ_{0} ∘ f_{#}(P̂) = c. Since |c| ∪ |P̂| ⊂ f^{−1}(Q), we have |c − P̂| ⊂ f^{−1}(Q).

Since H̃_{∗}(f^{−1}(Q)) = 0, there exists a c′ ∈ C_{1}(f^{−1}(Q)) such that

∂c′ = c − P̂ = (ψ_{0} ∘ f_{#0} − id_{C_{0}(X)}) (P̂).

We put D_{0}(P̂) := c′.

Now suppose that for i = 0, 1, 2, … k−1 the maps D_{i} : C_{i}(X) → C_{i+1}(X) are constructed so that properties (18) and (19) are satisfied. Take any P ∈ K_{k}(X). Let Q := f(P) and let c := ψ_{k}(Q̂) = ψ_{k}(f_{#}(P̂)). Since both |P̂| and |c| are in f^{−1}(Q), the induction hypothesis (19) and the subadditivity of support in [8, Chapter 2, Proposition 2.19(iv)] imply that

|c − P̂ − D_{k−1}∂_{k}P̂| ⊂ |c| ∪ |P̂| ∪ |D_{k−1}∂_{k}P̂| ⊂ f^{−1}(Q).

Since H̃_{∗}(f^{−1}(|Q|)) = 0, there exists a c′ ∈ C_{k+1}(f^{−1}(Q)) such that

∂c′ = c − P̂ − D_{k−1}∂_{k}P̂ = (ψ_{k} ∘ f_{#k} − id_{C_{k}(X)} − D_{k−1}∂_{k}) (P̂).

It remains to define D_{k}(P̂) := c′. Then (18) is obviously satisfied and (19) follows when the construction is completed for all cubes P in f^{−1}(Q).

5 Homology of continuous maps via cubical maps.

From now on, by a continuous map we mean a map which is continuous with respect to the Euclidean topology. As we pointed out in Section 4.1, the class of cubical maps is small. In particular it is to small to obtain a counterpart of the theorem stating that every continuous map may be approximated by simplicial maps. Since this approximation theorem is crucial in the definition of simplicial homology of continuous maps, one can see that there is no way to carry over the definition of the homology of a continuous map from the simplicial case to the cubical case by means of approximation. One way to overcome this difficulty is by considering cubical multivalued maps and their homology. This approach is presented in [8]. The main difficulty of this approach does not lie in the construction of the multivalued map itself but in the construction of the so called chain selector of the multivalued map. In particular it requires solving a large linear equation for each elementary cube in the domain of the multivalued map.

However, it turns out that approximation, which is convenient in the case of simplicial homology, may be replaced by Cartesian approach, which is natural for cubical homology. This approach is used in [10] to present a new algorithm for computing homology of continuous maps. Since the presentation there is technical and oriented on efficiency, in this section we will describe the Cartesian approach without all the improvements designed for the efficiency but hiding the main idea.

The construction is based on the definition of the homology of a multivalued map via projections from the graph given in [6] and an idea from [1]. Let X, Y be two cubical sets and let f : X → Y be continuous in Euclidean topology. Our goal is to define the homology of f in terms of homology of some cubical maps. Recall that the graph of f is the set

graph(f) := {(x, y) ∈ X × Y | y = f(x)} .

Obviously, graph(f) is not a cubical set unless f is locally constant. However, we may consider a cubical set Z ⊂ X × Y such that graph(f) ⊂ Z. Let p_{Z} : Z → X and q_{Z} : Z → Y denote projections respectively to X and Y. Then we have the following commutative diagram of continuous maps.

\begin{aligned}& & Z \\ & ↙ ^{p_{Z}} & & ↘ ^{q_{Z}} \\ X & & ⟶^{f} & & Y \end{aligned}  (20)

We know from Example 4.4 that p_{Z} and q_{Z} are cubical maps and therefore their homology is well defined. Since homology is functorial, the homology of f must satisfy

H_{∗}(f) ∘ H_{∗}(p_{Z}) = H_{∗}(q_{Z}).

This may be solved for H_{∗}(f) if H_{∗}(p_{Z}) is an isomorphism. Since obviously p_{Z} is surjective, by Theorem 4.14 H_{∗}(p_{Z}) is an isomorphism if for every x ∈ X the set

p_{Z}^{−1}(x) = {x} × Y ∩ Z  (21)

is acyclic. The simplest candidate for Z is ch (f), the closed hull of f in X × Y. In practice, it often fulfils the acyclicity condition of (21). In the case when the acyclicity condition of (21) fails, one has to go through the process of subdivision or rescaling, similarly as in the multivalued approach presented in [8]. One can prove that with a sufficiently large subdivision or rescaling the closed hull of the graph satisfies the acyclicity condition of (21).

6 Algorithms

In this section we present the algorithms, which compute the homology of a cubical map and a continuous map. We use the notation and the syntax of algorithms introduced in [8]. In particular let us recall the following notation.

    typedef endpoint := (left, right);

typedef interval := hash{endpoint} of int ;

typedef cube := array[1 : ] of interval; typedef chain := hash{cube} of int ; typedef chainMap = array[0 : ] of hash{cube} of chain;

To store a cubical map it is natural to use the following data structure.

    typedef cubicalMap := hash{ cube} of cube;

The algorithm computing the homology of a cubical map is straightforward. It consists of two steps. The first step is based on Definition 4.6 and produces the associated chain map. Then a straightforward to implement algorithm homologyOfChainMap is used to get the homology of the chain map. Here is a possible implementation.

Algorithm 6.1 Homology of a cubical map

   function homologyOfCubicalMap(cubicalMap m)
   chainMap phi := ();

for i := 1 to lastIndex(m) do for each Q in keys(m[i]) do if dim(Q) = dim(m[i]{Q)});

phi[Q] := sgn(m, Q)m[i]{Q)}; endif; endfor;

endfor;

   return homologyOfChainMap(phi);

Now we are ready to present the prototype of an algorithm computing homology of a continuous map. Of course the fundamental question is to what class of continuous maps we can apply the algorithm. Obviously it is not possible to apply it to all continuous map, because there is uncountably many of them. One has to choose a suitable countable subclass. What matters is that for the continuous maps in the class one should be able to construct the closed hull of the graph. This may be done in many ways and we do not want to go into details here. The typical approach is based on interval arithmetic [11]. Some ways to achieve this task for certain classes of continuous functions are discussed in [8], [13] and [14]. For the sake of this paper we simply assume that a suitable class of continuous functions is available, the elements of this class can be stored in the data structure contMap and algorithm closedHullOfGraph finding the closed hull of the graph of a continuous map is given. We also assume that projection is an algorithm which given a set Z ⊂ X ×Y and X or Y returns the projection of Z on X or respectively Y. The algorithm is straightforward to implement.

Algorithm 6.2 Homology of a continuous map

   function homologyOfContMap(cubicalSetX, Y, contMapf)
   Z := closedHullOfGraph(X, Y, f);
   p := projection(Z, X);
   q := projection(Z, Y);
   p := homologyOfCubicalMap(p);
   q := homologyOfCubicalMap(q);

return q ∘ p^{−1};

Theorem 6.3 Assume Algorithm 6.2 is called with f representing a continuous map f. If the cubical set represented by Z satisfies the acyclicity condition of (21), then the algorithm stops and returns the homology of f.

Proof: The proof of this theorem follows immediately from the discussion in Section 5.

The strength of Algorithm 6.2 lies in the fact that one avoids solving a large number of large linear equations what is needed in the algorithm presented in [8]. However, a direct application of Algorithm 6.2 would not be efficient for another reason. The problem is that with introducing the graph one raises the dimension of the problem from the maximum of dimensions of the cubical sets X and Y to the sum of these dimensions. The solution is to perform some preprocessing, which allows one to replace the graph by another set in X × Y whose dimension is the same as the dimension of X. The preprocessing is quite complicated but leads to an algorithm which has been implemented and performs well in concrete applications. The details are presented in [10].

References

[1] M. Allili and T. Kaczynski, An algorithmic approach to the construction of homomorphisms induced by maps in homology, Trans. Amer. Math. Soc., 352 (2000), 2261-2281.

[2] M. Allili, K. Mischaikow, and A. Tannenbaum, Cubical homology and the topological classification of 2D and 3D imagery, ICIP-01, 2(2001), 173–176.

[3] M. Allili and D. Ziou, Topological feature extraction in binary images, Proc. 6th Intl. Symposium on Signal Processing and its Appl., Vol. 2, IEEE 2001, 651–654.

[4] J. A. Dieudonné, Cours de géométrie algébrique, Collection SUP, Le mathématicien, 10-11, Paris 1974.

[5] R. Ehrenborg and G. Hetyei, Generalizations of Baxter’s Theorem and Cubical Homology, J. Combinatorial Theory, Series A, 69 (1995), 233-287.

[6] L. Górniewicz, Homological Methods in Fixed Point Theory of Multi-Valued Maps, Dissertationes Math. (129), PWN Warsaw 1976.

[7] N. Jacobson, Basic Algebra II, W.H. Freedman & Co., San Francisco, 1974 (I), 1980 (II).

[8] T. Kaczynski, K. Mischaikow, and M. Mrozek, Computational Homology, Springer-Verlag, Appl. Math. Sci. Series Vol. 157, New York 2004.

[9] W. S. Massey, A Basic Course in Algebraic Topology, Springer-Verlag, New York 1991.

[10] K. Mischaikow, M. Mrozek, and P. Pilarczyk, Graph approach to the computation of the homology of continuous maps, to appear.

[11] R.E. Moore, Interval analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1966.

[12] M. Mrozek, An algorithmic approach to the Conley index theory, J. Dyn. Diff. Equ., 11(1999), 711-734.

[13] M. Mrozek, Topological invariants, multivalued maps and computer assisted proofs in dynamics, Computers & Mathematics, 32, (1996) 83–104.

[14] M. Mrozek, P. Zgliczyński, Set arithmetic and the enclosing problem in dynamics, Ann. Polon. Math. 74 (2000), 237–259.

[15] A. Szymczak, A combinatorial procedure for finding isolating neighbourhoods and index pairs, Proc. Roy. Soc. Edinburgh Sect. A 127 (5) (1997), 1075–1088.

[16] A. Szymczak, Index pairs: From dynamics to combinatorics and back, Ph.D. thesis, Georgia Inst. Tech., Atlanta, 1999.

[17] A. Trahan, Ensembles cubiques : Topologie et algorithmes de correction d’homologie, M. Sc. dissertation, Dép. de math. Fac. des Sci., Université de Sherbrooke, Sherbrooke 2004.

Département de mathématiques Université de Sherbrooke, Sherbrooke (Québec), Canada J1K 2R1 Tomasz.Kaczynski@usherbrooke.ca Anik.Trahan@usherbrooke.ca

Division of Computational Mathematics, Graduate School of Business, ul. Zielona 27, 33-300 Nowy Sa̧cz, Poland Marian.Mrozek@wsb-nlu.edu.pl and Institute of Computer Science Jagiellonian University 31-072 Kraków, Poland Marian.Mrozek@ii.uj.edu.pl