





































MelinAGT.dvi


@
Applied General Topology

c© Universidad Politécnica de Valencia

Volume 9, No. 1, 2008

pp. 51-66

Continuous extension
in topological digital spaces

Erik Melin

Abstract. We give necessary and sufficient conditions for the ex-
istence of a continuous extension from a smallest-neighborhood space
(Alexandrov space) X to the Khalimsky line. Using this result, we
classify the subsets A ⊂ X such that every continuous function A → Z
can be extended to all of X. We also consider the more general case of
mappings X → Y between smallest-neighborhood spaces, and prove a
digital no-retraction theorem for the Khalimsky plane.

2000 AMS Classification: Primary 54C20; Secondary 54C05, 54F07

Keywords: Khalimsky topology, digital geometry, Alexandrov space,
Continuous extension

1. Introduction

The classical Tietze extension theorem states that if X is a normal topological
space and A is a closed subset of X, then any continuous map from A into the
closed interval [a,b] can be extended to a continuous function on all of X into
[a,b]. In digital geometry it is more natural to study functions from a digital
space (defined below) to the integers. Having equipped the spaces with suit-
able topologies, we may consider continuous functions and the corresponding
extension problem.

We solve this problem for a fairly general class of topological digital spaces
and for continuous functions with the Khalimsky line as codomain. The Khal-
imsky topology is a topology that appears naturally in the study of digital
geometry, cf. Kong [12]. The notion of straight lines in Khalimsky spaces has
been studied in [18] and more general curves and surfaces in [17]. The results in
this paper are generalizations of a previous work [19], where the digital spaces
considered were restricted to Zn.

Digital topology can be considered from a graph-theoretical point of view;
one has a set of points and an adjacency relation, i.e., a symmetric binary



52 E. Melin

relation defining which points are adjacent. For example, in Zn one possibility
is to say that points p and q are adjacent if ‖p − q‖∞ = 1.

In such, graph based, spaces no topology, in the usual meaning, is directly
involved. Nevertheless, a theory for continuous functions has been developed
in this setting, for example by Boxer [2].

Herman and Webster [5] and Kovalevsky [16] have independently argued
that cellular complexes are appropriate topological spaces for digital geometry.
The results of this paper applies to such spaces, since they are topologically
equivalent to spaces of the type introduced in this article. See, for example,
Klette [10].

We shall only consider digital spaces that are also topological spaces and
where the topological notion of connectedness agrees with the notion of con-
nectedness in digital spaces. More details on the theory of such spaces and
applications to image analysis can be found in for example the survey by Kong
and Rosenfeld [14], in [13] by Kong et al. and in Koppermans’s [15] article.

2. Background

This section is devoted to some basic definitions and results that we will
need. Those unfamiliar with the subject might find Kiselman’s [9] Lecture
Notes helpful.

2.1. Smallest-neighborhood spaces. In any topological space, a finite inter-
section of open sets is open, whereas the stronger requirement that an arbitrary
intersection of open sets is open, is not satisfied in general. In a classical article,
Alexandrov [1] considers topological spaces that fulfill the stronger requirement,
where arbitrary intersections of open sets are open. In his paper, Alexandrov
called such spaces Diskrete Räume (discrete spaces). Unfortunately, this termi-
nology is not possible today since the term discrete topology is occupied by the
topology where every set is open. Instead, following Kiselman [9], we will call
such spaces smallest-neighborhood spaces. Another name that has been used is
Alexandrov spaces.

Let NX (x) denote the intersection of all neighborhoods of a point x in a
topological space X. If there is no danger of ambiguity, we will just write
N (x). In a smallest-neighborhood space, N (x) is always open and thus a
neighborhood of x; clearly N (x) is the smallest neighborhood of x. We may

note that x ∈ N (y) if and only if y ∈ C (x), where C (x) = {x} is the topological
closure of the singleton set containing x. Note that the familiar construction
of the closure, as an intersection of closed sets, is dual to the construction of
the smallest neighborhood.

Conversely, the existence of a smallest neighborhood around every point
implies that an arbitrary intersection of open sets is open; hence this existence
could have been used as an alternative definition of a smallest-neighborhood
space. A topological space X is called connected if the only sets which are both
closed and open are the empty set and X itself. Note that N (x) considered as a
subspace of X is always connected and that a two-point set {x,y} is connected



Continuous extension in digital spaces 53

if and only if x ∈ N (y) or y ∈ N (x). A point x is called open if the set {x} is
open, and is called closed if {x} is closed. If a point x is either open or closed
it is called pure, otherwise it is called mixed.

Kolmogorov’s separation axiom, also called the T0 axiom, states that given
two distinct points x and y, there is an open set containing one of them but not
the other. An equivalent formulation is that N (x) = N (y) implies x = y for
every x and y. This axiom is quite natural to impose; if x and y have the same
neighborhood, then they are indistinguishable from a topological point of view
and should perhaps be identified. The separation axiom T1, on the other hand,
is too strong. It states that points are closed and in a smallest-neighborhood
space this means that every set is closed. Hence only spaces with the discrete
topology are smallest-neighborhood spaces satisfying the T1 axiom.

Remark 2.1. There is a correspondence between smallest-neighborhood spaces
and partially ordered sets; namely if we define x 4 y if and only if y ∈ N (x).
This relation is always reflexive and transitive and is anti-symmetric if and only
the space is T0. Then the order is a partial order and is called the specialization
order. It was introduced by Alexandrov [1]. It is not hard to see that a func-
tion is continuous if and only if it is increasing for the specialization order. A
consequence is that our results can be formulated in the language of partially
ordered sets instead of topologies, if one prefers.

2.2. Topological digital spaces. In the graph-theoretical setting, a digital
space is called connected if it is path connected under the adjacency relation—
see [14] for details.

Given a topological space X we may try to identify it with a digital space
in this sense. It is natural to define the binary adjacency relation such that
distinct points x and y are adjacent if and only if {x,y} is connected (as a
subspace of X).

If X is not connected in the topological sense, it is obvious that it cannot
be path connected under the adjacency relation above. On the other hand, the
following lemma shows that a connected smallest-neighborhood space is indeed
also a connected digital space in the graph-theoretical sense. The result is also
stated in for example [4, Lemma 4.2.1], however, the present proof is shorter.

Lemma 2.2. Let X be a connected smallest-neighborhood space. Then for any
pair of points x and y of X there is a finite sequence (x0, . . . ,xn) such that
x = x0 and y = xn and {xj,xj+1} is connected for i = 0, 1, . . . ,n − 1.

Proof. Let x be a point in X, and denote by Y the set of points which can
be connected to x by such a finite sequence. Obviously x ∈ Y . Suppose that
y ∈ Y . It follows that N (y) ⊂ Y and C (y) ⊂ Y . Thus Y is open, closed and
nonempty. Since X is connected this reads Y = X. �

With this lemma as a motivation, we give the following definition: a topological
digital space is a connected smallest-neighborhood space.



54 E. Melin

Figure 1. Construction of the Khalimsky line.

2.3. Examples of topological digital spaces. We shall present some exam-
ples of digital spaces and examine some properties of these examples. Eckhardt
and Latecki [3] and Kong [11] give more examples of topologies on Z2 and Z3.

Example 2.3. Every finite topological space is obviously a smallest-neighbor-
hood space; therefore every connected finite space is a digital space. Properties
of finite spaces are studied by Stong [20]. Many results there are also true for
infinite smallest-neighborhood spaces.

Example 2.4 (The Khalimsky line [6, 7]). We shall construct a topology on
the digital line, Z, originally introduced by Efim Khalimsky. Let us identify
with each even integer m the closed, real, interval [m − 1/2,m + 1/2] and with
each odd integer the open interval ]m − 1/2,m + 1/2[. These intervals form a
partition of the Euclidean line R and we may therefore consider the quotient
space. Identifying each interval with the corresponding integer gives us the
Khalimsky topology on Z (see Figure 1). Since R is connected, the Khalimsky
line is connected. It follows easily that an even point is closed and that an odd
point is open. In terms of smallest neighborhoods, we have N (m) = {m} if m
is odd and N (n) = {n ± 1,n} if n is even.

As will be seen in the next section, the Khalimsky topology is of particular
importance in the study of topological digital spaces. Therefore we will here
make some further definitions. Let a and b be integers. A Khalimsky interval
is an interval [a,b] ∩ Z of integers with the topology induced from the Khal-
imsky line. We will denote such an interval by [a,b]Z. A Khalimsky arc is a
homeomorphic image of a Khalimsky interval into any topological space.

Unless otherwise stated, we will assume that Z is equipped with the Khal-
imsky topology from now on. This makes it meaningful to consider continuous
functions f : Z → Z. We will discuss some properties of such functions; more de-
tails can be found in [9]. Suppose that f is continuous. Since M = {m,m + 1}
is connected it follows that f(M) is connected, but this is the case only if
|f(m) − f(m + 1)| 6 1. Hence f is Lipschitz with Lipschitz constant 1; we
say f is Lip-1. Lip-1, however, is not sufficient for continuity. If y = f(x) is
odd, then U = f−1({y}) must be open, so if x is even then x ± 1 ∈ U. This
means that f(x ± 1) = f(x). It is straightforward to prove the following, see
[19, Lemma 2].

Proposition 2.5. f : Z → Z is continuous if and only if for every p,q ∈ Z
where p 6= q, one of the following conditions holds

(1) |f(q) − f(p)| < |q − p|
(2) |f(q) − f(p)| = |q − p| and p ≡ f(p) (mod 2).



Continuous extension in digital spaces 55

Corollary 2.6. A function f : A → Z, A ⊂ Z can be extended to a continuous
function F : Z → Z if and only if the condition in the above proposition holds
for every p,q ∈ A where p 6= q.

The following two examples give spaces with topologies that are derived from
the Khalimsky topology.

Example 2.7 (Khalimsky n-space). The Khalimsky plane is the Cartesian
product of two Khalimsky lines and in general, Khalimsky n-space is Zn with
the product topology. Points with all coordinates even are closed and points
with all coordinates odd are open. Points with both even and odd coordinates
are mixed.

Example 2.8. We may consider a quotient space Zm = Z/mZ for some even
integer m > 2 (if m is odd, we will end up identifying open and closed points,
which results in a space with the indiscrete topology, sometimes called the
chaotic topology). Such a space is called a Khalimsky circle. If m > 4, Zm is
a compact space which is locally homeomorphic to the Khalimsky line. In a
similar manner, we may construct a Khalimsky torus, by identifying the edges
of a Khalimsky rectangle, i.e., a product of two Khalimsky intervals (of even
length).

Our final example shows that there are topological digital spaces of arbitrarily
high cardinality.

Example 2.9. Let J be any index set and let K be the disjoint union of J
copies of the Khalimsky line. This space is of course not connected, but we
may identify the point 0 in every copy and then consider the quotient space
K0. It is easy to see that K0 is connected. Note also that N (0) may be a very
large set in this space.

2.4. Arc-connected spaces. Let X be a topological digital space satisfying
the T0 axiom and let x,y ∈ X. The following theorem shows that we can
actually find a Khalimsky arc in X with endpoints x and y, i.e., there is an
interval I = [a,b]Z and a function ψ : I → X such that ψ(a) = x, ψ(b) = y
and ψ is a homeomorphism of I and ψ(I). We call a topological space having
this property Khalimsky arc-connected or just arc-connected if it is clear from
the context what is intended. Note that an arc-connected space is always
connected; this can be proved with the same argument as is used to prove that
a path-connected space (in the usual topological sense) is connected.

Remark 2.10. In [7] the result below was proved for finite spaces only. An-
other difference in their version is that it was not required there that the space
in question satisfied the T0-axiom. This is because they allowed an arc with
two points {x,y} to have the indiscrete topology {∅,{x,y}}, which is clearly
necessary if N (x) = N (y) in X. With our definition, this type of two-point
arc is not allowed; hence we must require the space to be T0.

Theorem 2.11. A T0 topological digital space is Khalimsky arc-connected.



56 E. Melin

Proof. Let X be a topological digital space and let a,b ∈ X. First, use
Lemma 2.2 to get a finite, connected sequence of points (x0, . . . ,xn) such that
x0 = a and xn = b. Then use the finiteness of the sequence to choose a sub-
sequence Y = (y0, . . . ,ym) that is minimal with respect to connectedness, and
such that y0 = a and ym = b. With this, we mean that Y (considered as a
subset of X) has no connected proper subset containing a and b.

Suppose that i > j and that {yi,yj} is connected. Then i = j + 1; for if not,
the sequence (y0, . . . ,yj,yi, . . . ,ym) would be a connected proper subset of the
minimal sequence, which is a contradiction.

By the result of the above paragraph, there are two possibilities for NY (y0):
either NY (y0) = {y0} or NY (y0) = {y0,y1}. (If x ∈ NY (y), then x and y are
connected.) Let s = 1 in the first case and s = 0 in the second case. For a
clearer notation, let us agree to re-index the sequence {yi}, so that ys is its
first element and ym+s its last. We will show that the function

ψ : I = [s,s + m]Z → Y,i 7→ yi

is a homeomorphism.
Note that Y is T0 since X is T0. Clearly ψ is surjective, and by minimality

also injective. To show that ψ is a homeomorphism, it suffices to show that

(2.1) NY (yi) = ψ(NI (i)) for every i ∈ I.

For i = s this holds by the choice of s. We use finite induction. Suppose that
s < k 6 s + m, and that (2.1) holds for i = k − 1. We consider two cases:
Case 1: k is odd. Then NI (k) = {k}. We must show that yk−1 and yk+1 are
not in NY (yk). But since Eq. (2.1) holds for i = k − 1, and k ∈ NI (k − 1), we
know that yk ∈ NY (yk−1). It follows that yk−1 6∈ NY (yk) (Y is T0) and also
that yk+1 6∈ NY (yk), since NY (yk−1) ∩ NY (yk) is a neighborhood of yk which
does not include yk+1.
Case 2: k is even. We must show that yk−1 ∈ NY (yk) and yk+1 ∈ NY (yk)
provided k < s + m. Now, NY (yk−1) = {yk−1} by assumption, so clearly yk−1
belongs to NY (yk). If k < s+m and yk ∈ NY (yk+1), then NY (yk)∩NY (yk+1)
would be a neighborhood of yk not containing yk−1. This is a contradiction,
and hence yk+1 ∈ NY (yk). �

This result shows the fundamental importance of Khalimsky’s topology in the
theory of T0 digital spaces; in any such space, a minimal connected subset
containing two points x and y has the topological structure of a finite Khalimsky
interval. We state this important result formally:

Corollary 2.12. A subspace of a T0 digital space is a minimal connected sub-
space containing points x and y if and only if it is a Khalimsky arc with end-
points x and y.

Note that this result implies that the Khalimsky topology is the only topol-
ogy on Z (up to translation) such that Z is connected in the intuitive sense
(i.e., {m,m + 1} is connected for every m) and such that removing one point
separates the digital line into two components.



Continuous extension in digital spaces 57

3. The arc metric

Let X be a T0 topological digital space and let A be a Khalimsky arc in
X. We define the length of A, denoted L(A), to be the number of points in
A minus one, L(A) = |A| − 1. This means that an arc consisting of just one
element has length zero. The arc metric is defined to be the minimal length of
an arc between two points x and y.

Definition 3.1. Suppose that X is a T0 digital space. Then we define the arc
metric ρ on X to be

ρX (x,y) = min{L(A); A ⊂ X is a Khalimsky arc between x and y}.

If there is no danger of ambiguity, we may write just ρ(x,y).

The set of Khalimsky arcs between two points is not empty by Theorem 2.11
and their lengths form a discrete set, so the minimum does exist. Therefore
ρ is well defined and it is very easy to check that it satisfies the axioms for a
metric.

Remark 3.2. If Y is a subspace of X, the arc metric on Y need not equal the
restriction of the arc metric on X. We only have the inequality: ρX (x,y) 6
ρY (x,y) for every x,y ∈ Y . For example, consider a Khalimsky circle K with
at least 6 points. Take any b ∈ K and consider its two neighbors x and y. Then
ρK (x,y) = 2 but ρKr{b}(x,y) = card(K) − 2 > 2.

The following proposition will give some idea of the relation between this metric
and continuous functions on X.

Proposition 3.3. Suppose that X is a smallest-neighborhood space and that
f : X → Z is continuous. Then f is Lip-1 for the arc metric.

Proof. Suppose that x,y ∈ X and let A be an arc of minimal length connecting
x and y. By definition, A is a homeomorphic image of a Khalimsky interval;
there exist a homeomorphism η : I → A ⊂ X. Clearly the composition f ◦
η : I → Z is continuous and hence Lip-1. But the length of I equals L(A) and
by combining these facts it follows that |f(x) − f(y)| 6 L(A) = ρ(x,y), i.e., f
is Lip-1 for the arc metric. �

Remark 3.4. On the Khalimsky line we have ρ(m,n) = |m − n|. As we know
already from the study of continuous functions Z → Z (Proposition 2.5) the
Lip-1 condition is not sufficient for continuity.

Let A be a Khalimsky arc with L(A) > 1 in a topological space X. As a
subspace, we may think of A as a Khalimsky interval, or rather it is—up to
homeomorphism. Therefore it makes sense to speak of open and closed points
of A and every point in A is either open or closed. Note that a point, open
in A, may very well be closed in another Khalimsky arc B. If, however, the
point is pure in X, then it is either always open or always closed. The following
generalized concept turns out to be important in what follows.



58 E. Melin

Figure 2. The point (1, 0) is closed in one minimal arc con-
necting it to the point (2, 1) and open in another.

Definition 3.5. Let X be a T0 topological digital space and let x,y ∈ X be
distinct points in X. We say that x is open with respect to y if there is a
Khalimsky arc A between x and y of length ρ(x,y) such that x is open in A,
and we say that x is closed with respect to y if there is a Khalimsky arc B
between x and y of length ρ(x,y) such that x is closed in B.

Clearly a point x is either open or closed w.r.t. y, but can it be both? The
answer is in the affirmative; a simple example can be found in the Khalimsky
plane Z2. Let x = (1, 0) and y = (2, 1). Then ρ(x,y) = 2, and there are two
arcs of length 2 between x and y. In the one passing (1, 1), x is closed, in the
one passing through (2, 0), x is open. This is illustrated in Figure 2.

4. Extensions of continuous functions

The following definition gives a condition on a function which is stronger
than Lip-1. It is a generalization of Definition 7 in [19].

Definition 4.1. Let X be a T0 topological digital space, let A ⊂ X and consider
a function f : A → Z. Suppose x and y are two distinct points in A. If one of
the the following conditions hold

(1) |f(x) − f(y)| < ρ(x,y) or
(2) |f(x) −f(y)| = ρ(x,y) and x is open (closed) w.r.t. y implies that f(x)

is odd (even),

then we say that the function is strongly Lip-1 (in X) with respect to (the
points) x and y. If the function is strongly Lip-1 (in X) with respect to every
pair of distinct points in A then we simply say that f is strongly Lip-1 (w.r.t.
X).

We emphazise that (w.r.t X) means with respect to the (global) arc metric on
X and not to the arc metric of A. Confer Remark 3.2.

The relation f is strongly Lip-1 w.r.t. x and y is symmetric in x and y, and
the statement can intuitively be thought of as a guarantee that there is enough
distance between x in y along the shortest arcs (and thus any arc) connecting
these points for the function to change continuously from f(x) and f(y) along
these arcs, cf. Proposition 2.5.

Proposition 4.2. Let X be a T0 topological digital space and f : X → Z a
function. Then f is continuous if and only if f is strongly Lip-1 w.r.t. X.



Continuous extension in digital spaces 59

Proof. Assume first that f is continuous. The proof that f then is strongly Lip-
1 is practically the same as for Proposition 3.3. Suppose that x is open (closed)
w.r.t. y and let A be a minimal arc connecting these points such that x is open
(closed) in A. Let η and I be as in the proof of Proposition 3.3. As before, f ◦η
is continuous. Hence either |f(x) − f(y)| < ρ(x,y) or |f(x) − f(y)| = ρ(x,y)
and η−1(x) agrees in parity with f(x), which by assumption means that f(x)
is odd (even). But then f is strongly Lip-1 w.r.t. x and y and therefore f is
strongly Lip-1.

To prove the converse, assume that f is strongly Lip-1. It is sufficient to
show that NX (x) ⊂ f

−1(NZ(f(x))) for every x ∈ X. Suppose therefore that
y ∈ NX (x). Note that {x,y} is an arc connecting x and y and that x is closed
w.r.t. y. We have to consider two cases:
Case 1: f(x) is odd. Since x is closed w.r.t. y, |f(x) − f(y)| < ρ(x,y) = 1. It
follows that f(y) = f(x) ∈ NZ(f(x)).
Case 2: f(x) is even. Then |f(x) − f(y)| 6 ρ(x,y) = 1. But f(x) even also
implies NZ(x) = {f(x),f(x) ± 1}, so that f(y) ∈ NZ(f(x)). �

Now we will show that a strongly Lip-1 function defined on a subset of X can
be extended to a strongly Lip-1 function defined on all of X. We start with
the following lemma.

Lemma 4.3. Suppose that x and y are two distinct points in a T0 topological
digital space X, f : {x,y} → Z a function that is strongly Lip-1 w.r.t. X. Then
it is possible, for any point p ∈ X, to extend the function to F : {x,y,p} → Z
so that F is strongly Lip-1 w.r.t. X.

Proof. Suppose for definiteness that f(x) 6 f(y). Let A = (a1, . . . ,am) be
a minimal arc connecting x and p and let B = (b1, . . . ,bn) be a minimal arc
connecting y and p. If f(x) is even and x is open w.r.t. p, we can take A such
that x is open in A (and if f(x) is odd, ensure that x is closed in A if x is
closed w.r.t. p) and similarly for B and y.

Consider now the set A∪B. It is connected and hence it includes a (minimal)
arc C connecting x and y. If p is included in this arc we may argument as
follows: By minimality, C = (a1, . . . ,am−1,p,bn−1, . . .b1) and by the strongly
Lip-1 assumption, f can be continuously extended along the arc; in particular
a value is assigned to p and this value will be our F(p). Since we have chosen
A to be the arc yielding the strongest restriction possible for F to be strongly
Lip-1 w.r.t. x and p in X, and it succeeds in A by Proposition 4.2, F must be
strongly Lip-1 w.r.t. x and p in X. Similarly F is strongly Lip-1 w.r.t. y and p
in X, so F is indeed the required extension.

By the triangle inequality, we always have ρ(x,y) 6 ρ(x,p) + ρ(y,p). Sup-
pose that we have equality. This implies, with C defined as above that C =
A ∪ B and we are done. Next consider the possibility ρ(x,y) = ρ(x,p) +
ρ(y,p) − 1. Then it may happen that p is not included in C; we may have
C = (a1, . . . ,am−1,bn−1, . . .b1). We can still do a continuous extension along
C, say that it takes the value α at am−1 and β at bn−1. If α = β it is clear that
we can set F(p) = α, but what if β = α + 1? Assume for definiteness that α is



60 E. Melin

odd and β is even. If we set F(p) = α, we will have no problem along A, but we
may have along B, namely if p is closed in B. We now show that if it is so, then
we can set F(p) = β, or in other words that if p is closed in B, then p is also
closed in A. Assume therefore, on the contrary, that p is open in A. Our as-
sumptions can be summarized to the following: am−1 ∈ NC (bn−1) ⊂ N (bn−1)
(since α is odd and the extension along C is not constant at am−1 it follows
that am−1 is open), p ∈ NA(am−1) ⊂ N (am−1) (since p is assumed to be open
in A) and bn−1 ∈ NB(p) ⊂ N (p) (since p is closed in B) and the latter implies
p 6∈ N (bn−1) as we assume the space to be T0. The contradiction follows from
the following equation

p ∈ N (am−1) = N (am−1) ∩ N (bn−1) ⊂ N (bn−1) 6∋ p

Thus the bad configuration cannot occur, and it only remains to consider the
case ρ(x,y) 6 ρ(x,p) + ρ(y,p) − 2. Now, there is a maximal value M that F(p)
can take, if F is to be strongly Lip-1 w.r.t. x and p, and every integer between
f(x) and M will also make F strongly Lip-1. The following lower estimation
of m is immediate; M > f(x) + ρ(x,p) − 1. Similarly, there is a minimal value
N for F(p), so that F is strongly Lip-1 w.r.t. y and p; N 6 f(y) − ρ(y,p) + 1.
It is therefore sufficient to show that M > N. Assume on the contrary that
M < N, in other words that f(x) + ρ(y,p) + 1 < f(y) − ρ(y,p) + 1. But then

ρ(x,y) 6 ρ(x,p) + ρ(y,p) − 2 < f(y) − f(x)

This contradicts the fact that f is strongly Lip-1. �

Proposition 4.4. Suppose that X is a T0 topological digital space, that A is
a subspace of X and that f : A → Z is strongly Lip-1 w.r.t. X. Then f can be
extended to all of X so that the extended function is still strongly Lip-1.

Proof. If A is the empty set or A is all of X the lemma is trivially true, so we
need not consider these cases further. First we show that for any point where
f is not defined we can define it so that the new function still is strongly Lip-1.

To this end, let p be any point in X r A. For every x ∈ A it is possible to
extend f to fx defined on A ∪ {p} so that the new function is strongly Lip-1
w.r.t x and p—for example by letting fx(p) = f(x). It is also clear that there
is a minimal (say Nx) and a maximal (say Mx) value that fx(p) can attain if
it still is to be strongly Lip-1 w.r.t. x, and that fx(p) may also attain every
integer value in between Nx and Mx. Thus the set of possible values is in fact
an interval [Nx,Mx]Z. Now define

R =
⋂

x∈A

[Nx,Mx]Z

If R is empty, then there is an x and a y such that Mx < Ny. This means
that it is impossible to extend f at p so that it is strongly Lip-1 with respect to
both x and y. But this cannot happen according to Lemma 4.3 and therefore
R cannot be empty. Define f̃(p) to be, say, the smallest integer in R and

f̃(x) = f(x) if x ∈ A. Then f̃ : A ∪ {p} → Z is still strongly Lip-1.



Continuous extension in digital spaces 61

We will now use Zorn’s lemma to show existence of a strongly Lip-1 exten-
sion. Let E be the set of all (graphs of) strongly Lip-1 extensions of f. An
element in E is thus a subset of X × Z. A partial order on E is defined by set
inclusion. Let c be a chain in E. An upper bound for c is given by

⋃

c. Thus
E is inductive. By Zorn’s lemma, E has a maximal element and it corresponds
to a function F : Y → Z. It remains to be shown that Y = X. Suppose that
z ∈ X rY . Then, by the first part of the proof, there is a strongly Lip-1 exten-
sion of F , Y ∪ {z} → Z, which contradicts the maximality of F . We conclude
that F must in fact be the required extension of f. �

We now turn to the main theorem of this section.

Theorem 4.5 (Continuous extensions). Let A be a subspace of a T0 topological
digital space X and let f : A → Z be any function. Then f can be extended to
a continuous function on all of X if and only if f is strongly Lip-1 w.r.t. X.

Proof. That the function must be strongly Lip-1 follows from Proposition 4.2.
For the converse, first use Proposition 4.4 to find a strongly Lip-1 extension to
all of X and then Proposition 4.2 again to conclude that this extension is in
fact continuous. �

Remark 4.6. The case with a non-T0 digital space X can be handled. It
is not hard to see that if f : X → Z is continuous and N (x) = N (y), then
f(x) = f(y). Suppose that A ⊂ X and that f is a function on A. If f does
not satisfy the implication: if N (x) = N (y) then f(x) = f(y), then f cannot
be continuously extended. Otherwise we can identify the points with the same
neighborhood and consider the quotient space (which is T0) with the induced

function f̃. It follows that f can be continuously extended if and only if f̃ can
be extended, i.e., if and only if f̃ is strongly Lip-1.

Remark 4.7. Also the case where X is not connected can be handled; we may
consider extension of the function on each connected component separately.

We may include both these remarks in a modified version of Theorem 4.5. For
this we need to consider the extended arc metric ρ̃X defined on any smallest-
neighborhood space X as follows.

ρ̃X (x,y) =

{

1/2 if x 6= y and N (x) = N (y)
ρX (x,y) otherwise,

where ρX is defined by the same equation as before.

ρX (x,y) = min{L(A); A ⊂ X is a Khalimsky arc between x and y}.

Note that if X is not connected and x and y belong to different connected
components, we get ρ̃X (x,y) = min ∅ = +∞. Hence we allow here infinite
distance between points. If we replace the arc metric ρ with the extended
arc metric ρ̃ in definition 4.1, we may speak about strongly Lip-1 functions
defined on a smallest-neighborhood space X. Using this extended version of
the strongly Lip-1 condition, we have the following version of Theorem 4.5.



62 E. Melin

Figure 3. a) A completely arc-connected set. b) The set is
not completely arc-connected. Note that both sets are con-
nected, however.

Theorem 4.8. Let A be a subspace of a smallest-neighborhood space X and let
f : A → Z be any function. Then f can be extended to a continuous function
on all of X if and only if f is strongly Lip-1 w.r.t. X.

5. Completely arc-connected sets

The goal of this section is to use Theorem 4.5 to classify the subsets of a
topological digital space such that any continuous function defined there can
be continuously extended to all of X. This is a digital analogue of the classical
Tietze extension theorem.

Definition 5.1. Let X be a T0 topological digital space and A a subset of
X. Then A is called completely arc-connected in X if A is connected,
ρA = ρX

∣

∣

A
and for every pair x, y of distinct points in A, it is true that if x

is open (closed) w.r.t. y in X then x is also open (closed) w.r.t. y in A.

It is easy to see that A is completely arc-connected in X if and only if the
following conditions are satisfied for every pair of distinct points x and y: If x
is open (closed) w.r.t. y in X, then A contains an arc M connecting x and y,
such that x is open (closed) in M and L(M) = ρX (x,y).

Example 5.2. The set {(0, 0), (1, 1), (0, 2), (−1, 1)} in the Khalimsky plane
is completely arc-connected. The set M = {(1, 0), (1, 1), (2, 1)} is not, since
(1, 0) is both closed and open w.r.t. (2, 1) in Z2, but only closed w.r.t. (2, 1)
in M. Adding the point (2, 0) gives the set M ∪ {(2, 0)}, which is completely
arc-connected in Z2. The sets are shown in Figure 3.

The following theorem is now very easy to prove.

Theorem 5.3. Suppose that X is a T0 topological digital space and that A ⊂ X
is completely arc-connected in X. If f : A → Z is continuous in A, then f can
be extended to a continuous function F defined on all of X.

Proof. By Proposition 4.2, f is strongly Lip-1 w.r.t. A. We have to check that
f is also strongly Lip-1 w.r.t. X. Let x and y be distinct points in A. Since
ρX (x,y) = ρA(x,y), the conclusion follows easily if |f(x) − f(y)| < ρ(x,y).
Suppose that |f(x) − f(y)| = ρ(x,y). If x is open (closed) w.r.t. y in X, then
x is also open (closed) w.r.t. y in A. Therefore f(x) is odd (even) and thus
strongly Lip-1 w.r.t. X. �



Continuous extension in digital spaces 63

Theorem 5.4. Let X be a T0 topological digital space. If A ⊂ X is not
completely arc connected then there is a continuous function f : A → Z that
cannot be extended to all of X.

Proof. If A is not connected, the conclusion is immediate. Suppose therefore
that A is connected but not completely arc-connected and let x and y be points
in A such that some condition for arc-connectedness fails for the pair x and y.
We shall define a function g : {x,y} → Z and then we will show that g can be
extended to a continuous function on A but not to a continuous function on
X.

Suppose first that ρA(x,y) > ρX (x,y). Let g(x) = 0 if x is open w.r.t. y in
X, and g(x) = 1 otherwise. Then define g(y) = g(x) + ρA(x,y) − 1. We get

|g(x) − g(y)| = ρA(x,y) − 1 < ρA(x,y),

so g is strongly Lip-1 w.r.t. A and can therefore be continuously extended to
G: A → Z by Theorem 4.5. On the other hand, we have that

|G(x) − G(y)| = |g(x) − g(y)| = ρA(x,y) − 1 > ρX (x,y),

and by construction G(x) and x do not match in parity. Therefore, again by
Theorem 4.5, G cannot be extended to all of X.

The remaining case is ρA(x,y) = ρX (x,y). Here x must be both open and
closed w.r.t. y in X, but only open or only closed w.r.t. y in A. Define the
function g as g(x) = 0 if x is closed w.r.t. y in A and g(x) = 1 otherwise. Let
g(y) = g(x) + ρ(x,y). Clearly |g(x) − g(y)| = ρA(x,y) but since x and g(x)
match in parity, g is strongly Lip-1 w.r.t. A and can therefore be continuously
extended to G: A → Z. We also have |G(x) − G(y)| = ρX (x,y), however, x
is both closed and open w.r.t. y in X, so G is not strongly Lip-1 in X. This
completes the proof. �

Example 5.5. The set M of Example 5.2 is not completely arc-connected.
Define a function on M by f(1, 0) = 0, f(1, 1) = 1 and f(2, 1) = 2. Then f
is continuous on M but f cannot be continuously extended to M ∪ {(2, 0)}:
f(1, 0) = 0 implies that f(2, 0) = 0 and f(2, 1) = 2 implies that f(2, 0) = 2,
which is contradictory.

6. Continuous functions between digital spaces

Suppose that X and Y are T0 topological digital spaces and that A ⊂ X. Let
f : A → Y be a continuous function. What can we say about the possibilities to
extend f to all of X? Consider any continuous function g : X → Y and let x,y
be distinct points in X. If B is a minimal arc in X connecting x and y, then
g(B) is a connected subset of Y —hence g(B) contains an arc connecting g(x)
and g(y). From these observations we get the following chain of inequalities

(6.1) ρY (g(x),g(y)) 6 card(g(B)) − 1 6 card(B) − 1 = ρX (x,y)

If f is to be extended, it must therefore satisfy this inequality for every pair of
points where f is defined. We state this result as a proposition:



64 E. Melin

Proposition 6.1. Suppose that X and Y are T0 topological digital spaces and
that g : X → Y is continuous. Then g is Lip-1 for the arc metric.

This result is a generalization of Proposition 3.3. Guided by the sharpened
version of that result, Proposition 4.2, one might expect that a similar sharp-
ening is possible here too. Indeed, suppose we have equality in (6.1). Then g
is a continuous bijection between the Khalimsky arcs B and g(B). But then
g−1 is automatically continuous, as is easy to check, so B and g(B) are home-
omorphic. We conclude that if x is open (closed) w.r.t. y in X, then f(x) is
open (closed) w.r.t. f(y) in Y .

Definition 6.2. Let us call a function f : X → Y strongly Lip-1 w.r.t. the arc
metric if for every x,y ∈ X, x 6= y either

(1) ρY (f(x),f(y)) < ρX (x,y) or
(2) ρY (f(x),f(y)) = ρX (x,y) and x is open (closed) w.r.t. y in X implies

that f(x) is open (closed) w.r.t. f(y) in Y .

This definition is a generalization of Definition 4.1 since ρZ(m,n) = |m − n|
for points m and n on the Khalimsky line. We also get the following theorem,
corresponding to Proposition 4.2.

Theorem 6.3. Let X and Y be T0 topological digital spaces. Then f : X → Y
is continuous if and only if f is strongly Lip-1 w.r.t. the arc metric.

Proof. One direction is already clear; it remains to be proved that if f is
strongly Lip-1 w.r.t. the arc metric, then f is continuous. Assume that f
is strongly Lip-1. It is sufficient to show that NX (x) ⊂ f

−1(NY (f(x))) for
every x ∈ X. Let y ∈ NX (x). Then ρX (x,y) = 1. If ρY (f(x),f(y)) = 0
then f(x) = f(y) and the conclusion follows. The other possibility is that
ρY (f(x),f(y)) = 1. Since y ∈ NX (x), y is open w.r.t. x. Hence there is an arc
B of length 1 in Y such that f(y) is open in B. But clearly B = {f(x),f(y)}
and this means that f(y) ∈ NY (f(x)). �

However, strongly Lip-1 is not sufficient for an extension to exist; there is no
analogue of Proposition 4.4. Proposition 6.5 below demonstrates this. We need
to introduce some new notation and a result to formulate it.

Let X be any topological space. A Khalimsky Jordan curve in X is a home-
omorphic image of a Khalimsky circle, c.f. Example 2.8. We will let X be the
Khalimsky plane, Z2. The following theorem is proved by Khalimsky et al. in
[7]. Kiselman [8] has given a simplier proof.

Theorem 6.4 (Khalimsky Jordan curve theorem). Let J be any Khalimsky
Jordan curve in Z2. Then the complement Z2 r J has exactly two connectivity
components.

It is easy to see that one of these components must be finite. This component
together with its boundary J will be denoted DJ and called a Khalimsky disk.
The component itself, i.e., DJ r J, will be called the interior of DJ and is
denoted by int(DJ ).



Continuous extension in digital spaces 65

Proposition 6.5. Let J be any Khalimsky Jordan curve in Z2 and suppose that
f = (f1,f2) : DJ → DJ is a continuous mapping such that f

∣

∣

J
is the identity

mapping of J. Then f is the identity mapping of DJ .

Proof. Let x = (x1,x2) be a point in int(DJ ). Let

a = min{m ∈ N; x + (m, 0) ∈ J}

and

b = min{m ∈ N; x − (m, 0) ∈ J}.

Clearly 0 < a,b < ∞. Let p = x + (a, 0) and q = x − (b, 0). By assumption we
have f(p) = p and f(q) = q, so that

|f1(x) − p1| 6 ρ(f(x),p) = ρ(f(x),f(p)) 6 ρ(x,p) = |x1 − p1| = a

Here f1(x) is the first coordinate of f(x), and the first inequality follows since
|xi − yi| 6 ρ(x,y) for the i:th coordinate of any two points x,y in a Khalimsky
subspace. The second inequality follows from Theorem 6.3.

Similarly we have |f1(x) − q1| 6 b. But since |p1 − q1| = a + b, the only
possibility is f1(x) = x1. Using the same argument in the other coordinate
direction we get f2(x) = x2 and hence f(x) = x as required. �

If X is any topological space and A a subspace of X, a retraction of X onto
A is a continuous map ϕ: X → A such that ϕ

∣

∣

A
is the identity map of A. If

such a map exist we say that A is a retract of X. The well-known classical
no-retraction theorem states that there is no retraction of the unit disk B2 of
R

2 onto the circle S1, or more generally of Bn onto Sn−1.
In view of this, Proposition 6.5 in particular states the there is no retraction

from DJ onto J. Note also that f
∣

∣

J
, being the identity of J, is strongly Lip-1

w.r.t. the arc-metric on J but cannot be extended to DJ .

7. Conclusion

We have shown that a condition somewhat stronger than a Lipschitz condi-
tion with Lipschitz constant 1 for the arc metric is equivalent to continuity for
a function f : X → Y , where X and Y are T0 digital spaces. We call such a
function strongly Lip-1 w.r.t. X. Moreover, if Y = Z with the Khalimsky topol-
ogy, then any function defined on a subset of X such that f is strongly Lip-1
w.r.t. X can be extended to a continuous defined on all of X. Using this result,
we have proved a digital analogue of the classical Tietze extension theorem;
the subsets of A such that any continuous function A → Z can be extended to
all of X are precisely the subsets A where the notion of being strongly Lip-1
w.r.t. A agrees with the notion of being strongly Lip-1 w.r.t. X. We have also
proved a digital version of the no-retraction theorem for a disk in the plane.
This result shows that if the codomain Y is a more general space than Z, then
the strongly Lip-1 condition need not be sufficient for a continuous extension
to exist.



66 E. Melin

References

[1] P. Alexandrov, Diskrete Räume. Mat. Sb. 2 (1937), 501–519.
[2] L. Boxer, Digitally continuous functions, Pattern Recognition Lett. 15 (1994), 833–839.
[3] U. Eckhardt and L. J. Latecki, Topologies for the digital spaces Z2 and Z3 Computer

Vision and Image Understanding 90 (2003), 295–312.
[4] G. T. Herman, Geometry of digital spaces, Applied and Numerical Harmonic Analysis.

Birkhäuser Boston Inc., Boston, MA, 1998.
[5] G. T. Herman and D. Webster, A topological proof of a surface tracking algorithm,

Computer Vision, Graphics, and Image Processing 23 (1983), 162–177.
[6] E. Khalimsky, Topological structures in computer science, J. Appl. Math. Simulation 1

(1987), 25–40.
[7] E. Khalimsky, R. Kopperman and P. R. Meyer, Computer graphics and connected topolo-

gies on finite ordered sets, Topology Appl. 36 (1990), 1–17.
[8] C. O. Kiselman, Digital jordan curve theorems, In G. Borgefors, I. Nyström, and G. San-

niti di Baja, editors, Discrete Geometry for Computer Imagery, volume 1953 of Lecture
Notes in Computer Science, pages 46–56, 2000.

[9] C. O. Kiselman, Digital geometry and mathematical morphology. Lecture notes, Uppsala
University, 2004. Available at www.math.uu.se/~kiselman.

[10] Reinhard Klette, Topologies on the planar orthogonal grid, in 6th International Confer-
ence on Pattern Recognition (ICPR’02), volume II, pages 354–357, 2002.

[11] T. Y. Kong, Topological adjacency relations on Zn,Theoret. Comput. Sci. 283 (2002),
3-28.

[12] T. Y. Kong, The Khalimsky topologies are precisely those simply connected topologies
on Zn whose connected sets include all 2n-connected sets but no (3n − 1)-disconnected
sets, Theoret. Comput. Sci. 305 (2003), 221–235.

[13] T. Y. Kong, R. Kopperman and P. R. Meyer, A topological approach to digital topology,
Amer. Math. Monthly 98 (1991), 901–917.

[14] T. Y. Kong and A. Rosenfeld, Digital topology: Introduction and survey, Comput. Vision
Graph. Image Process. 48 (1989), 357–393.

[15] R. Kopperman, Topological digital topology. In Ingela Nyström, Gabriella Sanniti
di Baja, and Stina Svensson, editors, DGCI, volume 2886 of Lecture Notes in Com-
puter Science, pages 1–15. Springer, 2003.

[16] V. A. Kovalevsky, Finite topology as applied to image analysis, Comput. Vision Graph.
Image Process. 46 (1989), 141–161.

[17] E. Melin, How to find a Khalimsky-continuous approximation of a real-valued function,
In Reinhard Klette and Jovisa Žunić, editors, Combinatorial Image Analysis, volume
3322 of Lecture Notes in Computer Science, pages 351–365, 2004.

[18] E. Melin, Digital straight lines in the Khalimsky plane, Math. Scand. 96 (2005) 49–62.
[19] E. Melin, Extension of continuous functions in digital spaces with the Khalimsky topol-

ogy, Topology Appl. 153 (2005) 52–65.
[20] R. E. Stong, Finite topological spaces, Trans. Amer. Math. Soc. 123 (1966) 325–340.

Received August 2006

Accepted December 2007

Erik Melin (melin@math.uu.se)
Uppsala University, Department of Mathematics, Box 480, SE-751 06 Uppsala,
Sweden