# Hyperspaces and Function Graphs in Digital Topology

Laurence Boxer  Department of Computer and Information Sciences, Niagara
University, Niagara University, NY 14109, USA; and Department of Computer
Science and Engineering, State University of New York at Buffalo. email:
<EMAIL_ADDRESS>
###### Abstract

We adapt the study of hyperspaces and function spaces from classical topology
to digital topology. We define digital hyperspaces and digital function
graphs, and study some of their relationships and graphical properties.

Key words and phrases: digital topology, digital image, Hausdorff metric,
hyperspace, function space

MSC: 54B20, 54C35

##  1 Introduction

Classical topology has a large literature devoted to the study of hyperspaces,
in which a topology is induced on some set of subsets of a given topological
space. By the time of the publication of [27], hundreds of papers had been
published on hyperspaces, and many more have appeared subsequently. Typically,
the topology of a hyperspace is induced by using the Hausdorff metric, which
essentially measures how two objects approximate each other with respect to
position. The Hausdorff metric can be computed efficiently [29, 14] and has
been used by some students of digital image processing as a crude measure of
whether two images might represent the same real-world object. Other metrics
have been developed in order to compare objects with respect to topological or
geometric properties [2, 4, 16, 17, 7, 9]. Variations on the Hausdorff metric
were introduced in [18, 11, 32, 13]

Classical topology also has a large literature on function spaces, in which
the set of functions

$Y^{X}=\\{f:X\to Y~{}|~{}f\mbox{ is continuous}\\}$

between topological spaces, or some interesting subset of $Y^{X}$, is
considered as a topological space whose topology is determined from those of
$X$ and $Y$; see, e.g., [3, 33, 5, 6, 8].

In the current paper, we develop notions of hyperspaces and function graphs
(the latter, an analog of function spaces) for digital topology. The paper is
organized as follows.

  * •

Section 2 reviews basics of digital topology.

  * •

In section 3, we introduce the adjacency that we use to form a hyperspace of
digital images.

  * •

Section 4 has elementary observations on the cardinalities of digital
hyperspaces.

  * •

In section 5 we discuss certain digitally continuous functions on hyperspaces.
In section 5.3, we introduce the concept of a function graph as a digital
analog of a function space. Classical topology studies relations between
hyperspaces and function spaces, e.g., [5, 6, 8]; in section 5.3 and later in
the paper, we study relations between digital hyperspaces and function graphs.

  * •

In section 6 we study connectedness properties of digital hyperspaces.

  * •

In section 7 we consider various notions of continuous multivalued functions
in digital topology and their relations with digital hyperspaces.

  * •

In section 8 we obtain results concerning cycles and Girth in digital
hyperspaces.

  * •

In sections 9 and 10, we study, respectively, dominating sets and diameters of
digital hyperspaces.

  * •

We give some concluding remarks in section 11.

##  2 Preliminaries

Much of this section is quoted or paraphrased from [12, 13].

We use ${\mathbb{N}}$ to indicate the set of natural numbers, ${\mathbb{Z}}$
for the set of integers, and ${\mathbb{R}}$ for the set of real numbers. We
use $\\#X$ for the number of points in a set $X$.

###  2.1 Adjacencies

A digital image is a graph $(X,\kappa)$, where $X$ is a nonempty subset of
${\mathbb{Z}}^{n}$ for some positive integer $n$, and $\kappa$ is an adjacency
relation for the points of $X$. The $c_{u}$-adjacencies are commonly used. Let
$x,y\in{\mathbb{Z}}^{n}$, $x\neq y$, where we consider these points as
$n$-tuples of integers:

$x=(x_{1},\ldots,x_{n}),~{}~{}~{}y=(y_{1},\ldots,y_{n}).$

Let $u\in{\mathbb{N}}$, $1\leq u\leq n$. We say $x$ and $y$ are
$c_{u}$-adjacent if

  * •

There are at most $u$ indices $i$ for which $|x_{i}-y_{i}|=1$.

  * •

For all indices $j$ such that $|x_{j}-y_{j}|\neq 1$ we have $x_{j}=y_{j}$.

Often, a $c_{u}$-adjacency is denoted by the number of points adjacent to a
given point in ${\mathbb{Z}}^{n}$ using this adjacency. E.g.,

  * •

In ${\mathbb{Z}}^{1}$, $c_{1}$-adjacency is 2-adjacency.

  * •

In ${\mathbb{Z}}^{2}$, $c_{1}$-adjacency is 4-adjacency and $c_{2}$-adjacency
is 8-adjacency.

  * •

In ${\mathbb{Z}}^{3}$, $c_{1}$-adjacency is 6-adjacency, $c_{2}$-adjacency is
18-adjacency, and $c_{3}$-adjacency is 26-adjacency.

We write $x\leftrightarrow_{\kappa}x^{\prime}$, or $x\leftrightarrow
x^{\prime}$ when $\kappa$ is understood, to indicate that $x$ and $x^{\prime}$
are $\kappa$-adjacent. Similarly, we write
$x\leftrightarroweq_{\kappa}x^{\prime}$, or $x\leftrightarroweq x^{\prime}$
when $\kappa$ is understood, to indicate that $x$ and $x^{\prime}$ are
$\kappa$-adjacent or equal.

A sequence $P=\\{y_{i}\\}_{i=0}^{m}$ in a digital image $(X,\kappa)$ is a
$\kappa$-path from $a\in X$ to $b\in X$ if $a=y_{0}$, $b=y_{m}$, and
$y_{i}\leftrightarroweq_{\kappa}y_{i+1}$ for $0\leq i<m$.

$Y\subset X$ is $\kappa$-connected [28], or connected when $\kappa$ is
understood, if for every pair of points $a,b\in Y$ there exists a
$\kappa$-path in $Y$ from $a$ to $b$.

Let $N(X,x,\kappa)$ be the set

$N(X,x,\kappa)=\\{y\in X~{}|~{}x\leftrightarrow_{\kappa}y\\}.$

###  2.2 Digitally continuous functions

In a metric space, the continuity of $f:X\to Y$ is defined to preserve the
intuition that if $x_{0}$ and $x_{1}$ are sufficiently close, then $f(x_{0})$
and $f(x_{1})$ are close; i.e., “closeness,” and therefore connectivity, are
preserved by a continuous function. Digital continuity is defined to preserve
connectedness, as at Definition 2.1 below. By using adjacency as our standard
of “closeness,” we get Theorem 2.2 below.

######  Definition 2.1.

[12] (generalizing a definition of [28]) Let $(X,\kappa)$ and $(Y,\lambda)$ be
digital images. A function $f:X\rightarrow Y$ is $(\kappa,\lambda)$-continuous
if for every $\kappa$-connected $A\subset X$ we have that $f(A)$ is a
$\lambda$-connected subset of $Y$.

If $Y\subset X$, we use the abbreviation $\kappa$-continuous for
$(\kappa,\kappa)$-continuous.

When the adjacency relations are understood, we will simply say that $f$ is
_continuous_. Continuity can be expressed in terms of adjacency of points:

######  Theorem 2.2.

[28, 12] A function $f:X\to Y$ is continuous if and only if $x\leftrightarrow
x^{\prime}$ in $X$ implies $f(x)\leftrightarroweq f(x^{\prime})$.

See also [19, 20], where similar notions are referred to as immersions,
gradually varied operators, and gradually varied mappings.

######  Proposition 2.3.

[12] If $f:(X,\kappa)\to(Y,\lambda)$ and $g:(Y,\lambda)\to(W,\mu)$ are
continuous maps between digital images, then $g\circ f:X\to W$ is
$(\kappa,\mu)$-continuous.

######  Remark 2.4.

Notice $P$ is a $\kappa$-path if and only if there is a
$(c_{1},\kappa)$-continuous function $p:[0,n]_{{\mathbb{Z}}}\to X$ such that
$p([0,n]_{{\mathbb{Z}}})=P$. It is therefore common to call such a function a
$\kappa$-path.

To express the idea of following one path and then another, the product or
concatenation of paths is defined as follows.

######  Definition 2.5.

[24] Let $p_{1}:[0,m]_{{\mathbb{Z}}}\to X$ and $p_{2}:[0,n]_{{\mathbb{Z}}}\to
X$ be $\kappa$-paths such that $p_{1}(m)=p_{2}(0)$. The product or
concatenation of these paths is the function $p_{1}\cdot
p_{2}:[0,m+n]_{{\mathbb{Z}}}\to X$ given by

$(p_{1}\cdot p_{2})(t)=\left\\{\begin{array}[]{ll}p_{1}(t)&\mbox{if }0\leq
t\leq m;\\\ p_{2}(t-m)&\mbox{if }m\leq t\leq m+n.\end{array}\right.$

######  Lemma 2.6.

[10] The concatenation of paths is associative, i.e.,

$(p_{1}\cdot p_{2})\cdot p_{3}=p_{1}\cdot(p_{2}\cdot p_{3}).$

Let $Y\subset X$. A $\kappa$-continuous function $r:X\to Y$ is a retraction,
and $Y$ is a $\kappa$-retract of $X$, if $r|_{Y}=\operatorname{id}_{Y}$.

A homotopy between continuous functions may be thought of as a continuous
deformation of one of the functions into the other over a finite time period.

######  Definition 2.7.

([12]; see also [24]) Let $X$ and $Y$ be digital images. Let $f,g:X\rightarrow
Y$ be $(\kappa,\lambda)$-continuous functions. Suppose there is a positive
integer $m$ and a function $F:X\times[0,m]_{{{\mathbb{Z}}}}\rightarrow Y$ such
that

  * •

for all $x\in X$, $F(x,0)=f(x)$ and $F(x,m)=g(x)$;

  * •

for all $x\in X$, the induced function
$F_{x}:[0,m]_{{{\mathbb{Z}}}}\rightarrow Y$ defined by

$F_{x}(t)~{}=~{}F(x,t)\mbox{ for all }t\in[0,m]_{{{\mathbb{Z}}}}$

is $(2,\lambda)-$continuous. That is, $F_{x}(t)$ is a path in $Y$.

  * •

for all $t\in[0,m]_{{{\mathbb{Z}}}}$, the induced function $F_{t}:X\rightarrow
Y$ defined by

$F_{t}(x)~{}=~{}F(x,t)\mbox{ for all }x\in X$

is $(\kappa,\lambda)-$continuous.

Then $F$ is a digital $(\kappa,\lambda)-$homotopy between $f$ and $g$, and $f$
and $g$ are digitally $(\kappa,\lambda)-$homotopic in $Y$, denoted
$f\sim_{\kappa,\lambda}g$.

If for some $x_{0}\in X$ and $y_{0}\in Y$ we have
$F(x_{0},t)=F(x_{0},0)=y_{0}\in Y$ for all $t\in[0,m]_{{{\mathbb{Z}}}}$, we
say $F$ holds $x$ fixed, $F$ is a pointed homotopy, and $x_{0}$ and $y_{0}$
are basepoints of the homotopy. $\Box$

A different notion of digital homotopy has been introduced by [26, 30]. The
latter paper calls this strong homotopy. It is defined as follows.

######  Definition 2.8.

Let $X$ and $Y$ be digital images. Let $f,g:X\rightarrow Y$ be
$(\kappa,\lambda)$-continuous functions. Suppose there is a positive integer
$m$ and a function $F:X\times[0,m]_{{{\mathbb{Z}}}}\rightarrow Y$ such that

  * •

for all $x\in X$, $F(x,0)=f(x)$ and $F(x,m)=g(x)$; and

  * •

if $x\leftrightarroweq_{\kappa}y$ in $X$ and
$t_{0}\leftrightarroweq_{c_{1}}t_{1}$ in $[0,m]_{{{\mathbb{Z}}}}$, then
$F(x,t_{0})\leftrightarroweq_{\lambda}F(y,t_{1})$ in $Y$.

Then $F$ is a strong homotopy between $f$ and $g$, and $f$ and $g$ are
strongly $(\kappa,\lambda)$-homotopic in $Y$.

If for some $x_{0}\in X$ and $y_{0}\in Y$ we have
$F(x_{0},t)=F(x_{0},0)=y_{0}\in Y$ for all $t\in[0,m]_{{{\mathbb{Z}}}}$, we
say $F$ holds $x_{0}$ fixed, $F$ is a strong pointed homotopy, and $x_{0}$ and
$y_{0}$ are basepoints of the homotopy.

If there is a (strong) (pointed) $(\kappa,\kappa)$-homotopy
$F:X\times[0,m]_{{\mathbb{Z}}}\to X$ between the identity function $1_{X}$ and
a constant function, we say $F$ is a (digital) (strong) (pointed)
$\kappa$-contraction and $X$ is (strongly) (pointed) $\kappa$-contractible.

If there are continuous $f:(X,\kappa)\to(Y,\lambda)$ and
$g:(Y,\lambda)\to(X,\kappa)$ such that $g\circ f$ is (strongly) (pointed)
homotopic to $\operatorname{id}_{X}$ and $f\circ g$ is (strongly) (pointed)
homotopic to $\operatorname{id}_{Y}$, then $(X,\kappa)$ and $(Y,\lambda)$ are
(strongly) (pointed) homotopy equivalent or have the same (strong) (pointed)
homotopy type.

If $r:X\to X$ is a $\kappa$-retraction of $X$ to $Y\subset X$ that is
(strongly) homotopic to $\operatorname{id}_{X}$, then $r$ is a (strong in the
sense of digital homotopy) deformation retraction. If a (strong in the sense
of digital homotopy) deformation retraction of $X$ to $Y\subset X$ holds fixed
every point of $Y$, then $r$ is a strong (in the sense of deformation theory)
(strong in the sense of digital homotopy) deformation retraction.

If $f:(X,\kappa)\to(Y,\lambda)$ is a continuous bijection such that
$f^{-1}:(Y,\lambda)\to(X,\kappa)$ is continuous, then $f$ is an isomorphism
(called homeomorphism in [10]) and $(X,\kappa)$ and $(Y,\lambda)$ are
isomorphic.

##  3 Hyperspaces

The book [27] is a good source for much of the material discussed in this
section that is taken from classical topology.

In classical topology, given a topological space $X$, we denote by $2^{X}$ the
set or hyperspace of nonempty compact subsets of $X$. If $X$ is a metric space
with metric $d$, $2^{X}$ becomes a metric space with the Hausdorff metric, or
some other metric, based on $d$.

Given a digital image $(X,\kappa)$, we seek a somewhat parallel construction
of a graph based on finite subsets of $X$. We let

$2^{X}=\\{Y~{}|~{}\emptyset\neq Y\subset X,~{}\\#Y<\infty\\}.$

We define the $\kappa^{\prime}$ adjacency for $2^{X}$ as follows.

######  Definition 3.1.

Let $\\{A,B\\}\subset 2^{X}$, $A\neq B$. Then
$A\leftrightarrow_{\kappa^{\prime}}B$ if and only if given $a\in A$ and $b\in
B$, there exist $a_{0}\in A$ and $b_{0}\in B$ such that
$a\leftrightarroweq_{\kappa}b_{0}$ and $b\leftrightarroweq_{\kappa}a_{0}$.

The pair $(2^{X},\kappa^{\prime})$ is a graph or tolerance space [34], the
hyperspace of $(X,\kappa)$. Note we do not call this hyperspace a digital
image, since $2^{X}$ is not a subset of ${\mathbb{Z}}^{n}$. However, since
digital topology’s notions of continuous functions are defined in terms of
graph adjacency, or, alternately, graph connectedness, they are naturally
applied to this construction.

In classical topology, it is common to denote by $C(X)$ the subset of $2^{X}$
consisting of connected members of $2^{X}$. Since the notation $C(X,\kappa)$
is established in the literature of digital topology as the set of
$\kappa$-continuous self maps on $X$, we use the notation

$K(X,\kappa^{\prime})=(\\{A\in 2^{X}~{}|~{}A\mbox{ is
$\kappa$-connected}\\},\kappa^{\prime}).$

We will use the abbreviation $K(X)$ when $\kappa$ is understood.

######  Example 3.2.

$K([a,b]_{{\mathbb{Z}}},c_{1}^{\prime})$ and
$(\\{(x,y)\in{\mathbb{Z}}^{2}~{}|~{}a\leq x\leq y\leq b\\},c_{2})$ are
isomorphic graphs.

###### Proof.

Let $X=K([a,b]_{{\mathbb{Z}}},c_{1}^{\prime})$,
$Y=\\{(x,y)\in{\mathbb{Z}}^{2}~{}|~{}a\leq x\leq y\leq b\\}$. Consider the
function $F:X\to Y$ given by $F([m,n]_{{\mathbb{Z}}})=(m,n)$. It is elementary
to show that $F$ is a $(c_{1}^{\prime},c_{2})$-isomorphism. ∎

##  4 Cardinality

######  Remark 4.1.

Let $(X,\kappa)$ be a digital image such that $\\#X=n$. Then
$\\#2^{X}=2^{n}-1$. This is because for each $x\in X$ and $A\in 2^{X}$, either
$x\in A$ or $x\not\in A$. This yields $2^{n}$ possible combinations of pixels,
but we exclude the empty set.

However, the following example shows that $K(X)$ may be considerably smaller
than $2^{X}$.

######  Example 4.2.

$\\#K([1,n]_{{\mathbb{Z}}},c_{1}^{\prime})=n(n+1)/2$.

###### Proof.

For $i\in[1,n]_{{\mathbb{Z}}}$, the members of
$K([1,n]_{{\mathbb{Z}}},c_{1}^{\prime})$ that have $i$ as their largest member
are those of $\\{[j,i]_{{\mathbb{Z}}}\\}_{j=1}^{i}\\}$. Since there are $i$
digital intervals with largest member $i$ in
$K([1,n]_{{\mathbb{Z}}},c_{1}^{\prime})$,

$\\#K([1,n]_{{\mathbb{Z}}},c_{1}^{\prime})=\sum_{i=1}^{n}i=n(n+1)/2.$

∎

##  5 Maps on digital hyperspaces

In this section, we study maps induced on hyperspaces by continuous maps
between digital images.

###  5.1 Induced maps

Given a continuous map $f:(X,\kappa)\to(Y,\lambda)$, we show below that $f$
induces a $(\kappa^{\prime},\lambda^{\prime})$-continuous map $f_{*}:2^{X}\to
2^{Y}$ such that $f_{*}|_{K(X)}:K(X)\to K(Y)$ is also
$(\kappa^{\prime},\lambda^{\prime})$-continuous. In the following, we will use
the notation $f_{*}$ to abbreviate $f_{*}|_{K(X)}$.

######  Theorem 5.1.

Let $(X,\kappa)$ and $(Y,\lambda)$ be digital images and let $f:X\to Y$. Then
$f$ is $(\kappa,\lambda)$-continuous if and only if the induced functions
$f_{*}:2^{X}\to 2^{Y}$ and $f_{*}:K(X)\to K(Y)$ defined by $f_{*}(A)=f(A)$ are
$(\kappa^{\prime},\lambda^{\prime})$-continuous.

###### Proof.

Since a digitally continuous function preserves adjacency and connectivity,
the same argument works for both of the induced functions.

Suppose $f$ is continuous. Let $A,B\in 2^{X}$ such that
$A\leftrightarrow_{\kappa^{\prime}}B$. Let $x\in A$. There exists $y\in B$
such that $x\leftrightarroweq_{\kappa}y$. By the continuity of $f$ we have
$f(x)\leftrightarroweq_{\lambda}f(y)$. Similarly, for $b\in B$, there exists
$a\in A$ such that $a\leftrightarroweq_{\kappa}b$ and
$f(a)\leftrightarroweq_{\lambda}f(b)$. Therefore,
$f_{*}(A)=f(A)\leftrightarroweq_{\lambda^{\prime}}f(B)=f_{*}(B)$. Thus $f_{*}$
is $(\kappa^{\prime},\lambda^{\prime})$-continuous.

Suppose $f_{*}$ is $(\kappa^{\prime},\lambda^{\prime})$-continuous. Let
$x,y\in X$ such that $x\leftrightarrow_{\kappa}y$. Then
$\\{x\\}\leftrightarrow_{\kappa^{\prime}}\\{y\\}$, so

$\\{f(x)\\}=f_{*}(\\{x\\})\leftrightarroweq_{\lambda^{\prime}}f_{*}(\\{y\\})=\\{f(y)\\}.$

Therefore, $f(x)\leftrightarroweq_{\lambda}f(y)$. Thus, $f$ is
$(\kappa,\lambda)$-continuous. ∎

We have the following as an immediate consequence of Theorem 5.1.

######  Corollary 5.2.

Let $(X,\kappa)$ and $(Y,\lambda)$ be digital images and let $f:X\to Y$. Then
the following are equivalent.

  * •

$f$ is a $(\kappa,\lambda)$-isomorphism;

  * •

the induced function $f_{*}:2^{X}\to 2^{Y}$ is a
$(\kappa^{\prime},\lambda^{\prime})$-isomorphism; and

  * •

the induced function $f_{*}:K(X)\to K(Y)$ is a
$(\kappa^{\prime},\lambda^{\prime})$-isomorphism

######  Proposition 5.3.

Given continuous functions $f:(X,\kappa)\to(Y,\lambda)$ and
$g:(Y,\lambda)\to(W,\mu)$, we have $(g\circ f)_{*}=g_{*}\circ f_{*}$.

###### Proof.

The assertion follows from the observation that $A\in 2^{X}$ implies

$(g\circ f)_{*}(A)=(g\circ f)(A)=g(f(A))=g_{*}(f_{*}(A))=(g_{*}\circ
f_{*})(A).$

∎

The following is elementary.

######  Lemma 5.4.

Let $(X,\kappa)$ be a digital image. Then
$(\operatorname{id}_{X})_{*}=\operatorname{id}_{(2^{X},\kappa^{\prime})}$ and
$(\operatorname{id}_{X})_{*}=\operatorname{id}_{(K(X),\kappa^{\prime})}$.

######  Theorem 5.5.

The hyperspace construction yields covariant functors $F,F^{\prime}$ from the
category of digital images and continuous functions to the category of graphs
and continuous functions (respectively, to the category of connected graphs
and continuous functions), in which $F(X,\kappa)=(2^{X},\kappa^{\prime})$,
$F^{\prime}(X,\kappa)=K(X,\kappa^{\prime})$ and for
$f:(X,\kappa)\to(Y,\lambda)$ we have $F(f)=f_{*}$, $F^{\prime}(f)=f_{*}$.

###### Proof.

This follows from Proposition 5.3 and Lemma 5.4. ∎

Not every continuous function on the hyperspace of a digital image is induced
by a continuous map between digital images, as shown by the following.

######  Example 5.6.

Let $X=[0,1]_{{\mathbb{Z}}}$. Let $F:K(X,c_{1}^{\prime})\to
K(X,c_{1}^{\prime})$ be the function given by $F(A)=X$ for all $A\in K(X)$.
$F$ is constant, hence continuous, and is not induced by any $f:X\to X$ since
for each such function, e.g., $f(0)\in X=\\{\,0,1\,\\}=f_{*}(0)$, hence
$f_{*}(\\{\,0\,\\})\neq F(0)$.

###  5.2 Retraction and homotopy

######  Theorem 5.7.

Let $(X,\kappa)$ and $(Y,\kappa)$ be digital images and let $r:X\to Y$ be a
$\kappa$-retraction. Then the induced maps $r_{*}:2^{X}\to 2^{Y}$ and
$r_{*}:K(X)\to K(Y)$ are $\kappa^{\prime}$-retractions.

###### Proof.

It follows from Theorem 5.1 that each version of $r_{*}$ is
$\kappa^{\prime}$-continuous. It is clear that
$r_{*}|_{2^{Y}}=\operatorname{id}_{2^{Y}}$, $r_{*}(2^{X})=2^{Y}$,
$r_{*}(K(X))=K(Y)$, $r_{*}|_{K(Y)}=\operatorname{id}_{K(Y)}$. The assertion
follows. ∎

######  Theorem 5.8.

Let $f$ and $g$ be (strongly) (pointed) homotopic maps from $(X,\kappa)$ to
$(Y,\lambda)$. Then $f_{*}$ and $g_{*}$ are (strongly) (pointed) homotopic
maps from $(2^{X},\kappa^{\prime})$ to $(2^{Y},\lambda^{\prime})$, and from
$K(X)$ to $K(Y)$. In the case of (strongly) pointed homotopy, if $x_{0}\in X$
is held fixed by the (strong) pointed homotopy from $f$ to $g$, then
$\\{x_{0}\\}$ is held fixed by the (strong) pointed homotopy from $f_{*}$ to
$g_{*}$.

###### Proof.

We give a proof for homotopy using $2^{X}$ and $2^{Y}$. The proofs for strong
or pointed homotopies and for $K(X)$ and $K(Y)$ are similar.

By hypothesis, there is a function $H:X\times[0,n]_{{\mathbb{Z}}}\to Y$ for
some $n\in{\mathbb{N}}$ such that

  * •

$H(x,0)=f(x)$ and $H(x,n)=g(x)$ for all $x\in X$.

  * •

For all $x\in X$, the induced function $H_{x}:[0,n]_{{\mathbb{Z}}}\to Y$
defined by $H_{x}(t)=H(x,t)$ is $(c_{1},\lambda)$-continuous.

  * •

For all $t\in[0,n]_{{\mathbb{Z}}}$, the induced function $H_{t}:X\to Y$
defined by $H_{t}(x)=H(x,t)$ is $(\kappa,\lambda)$-continuous.

Let $H_{*}:2^{X}\times[0,n]_{{\mathbb{Z}}}\to 2^{Y}$ be the function
$H_{*}(A,t)=H_{t}(A)$.

  * •

We have

$H_{*}(A,0)=H_{0}(A)=f(A)=f_{*}(A).$

Similarly, $H_{*}(A,n)=g_{*}(A)$.

  * •

For all $A\in 2^{X}$, consider the induced function
$H_{*,A}:[0,n]_{{\mathbb{Z}}}\to 2^{Y}$ defined by

$H_{*,A}(t)=H(A,t)=\bigcup_{x\in A}\\{H_{x}(t)\\}.$

Since $0\leq t<n$ implies $H_{x}(t)\leftrightarroweq_{\lambda}H_{x}(t+1)$, it
follows that $H_{*,A}(t)\leftrightarroweq_{\lambda^{\prime}}H_{*,A}(t+1)$.
Thus the induced function $H_{*,A}$ is $(c_{1},\lambda^{\prime})$-continuous.

  * •

For all $t\in[0,n]_{{\mathbb{Z}}}$, consider the induced function
$H_{*,t}:2^{X}\to 2^{Y}$ given by

$H_{*,t}(A)=H(A,t)=\bigcup_{x\in A}\\{H_{t}(x)\\}.$

If $A\leftrightarrow_{\kappa^{\prime}}B$ then for each $a\in A$ there exists
$b\in B$ such that $a\leftrightarroweq_{\kappa}b$, and for each $\beta\in B$
there exists $\alpha\in A$ such that $\alpha\leftrightarroweq_{\kappa}\beta$.
Therefore, $H_{t}(a)\leftrightarroweq_{\lambda}H_{t}(b)$ and
$H_{t}(\alpha)\leftrightarroweq_{\lambda}H_{t}(\beta)$. It follows that
$H_{*,t}(A)\leftrightarroweq_{\lambda^{\prime}}H_{*,t}(B)$. Thus $H_{*,t}$ is
$(\kappa^{\prime},\lambda^{\prime})$-continuous.

The above shows that $H_{*}$ is a homotopy from $f_{*}$ to $g_{*}$. ∎

######  Theorem 5.9.

Let $(X,\kappa)$ and $(Y,\lambda)$ be digital images.

  1. 1.

If $(X,\kappa)$ and $(Y,\lambda)$ have the same (pointed) homotopy type, then
$(2^{X},\kappa^{\prime})$ and $(2^{Y},\lambda^{\prime})$ have the same
(pointed) homotopy type; as do $K(X,\kappa^{\prime})$ and
$K(Y,\lambda^{\prime})$.

  2. 2.

If $(X,\kappa)$ and $(Y,\lambda)$ have the same strong (pointed) homotopy
type, then $(2^{X},\kappa^{\prime})$ and $(2^{Y},\lambda^{\prime})$ have the
same strong (pointed) homotopy type; as do $K(X,\kappa^{\prime})$ and
$K(Y,\lambda^{\prime})$.

  3. 3.

Let $(X,\kappa)$ be (pointed) contractible (respectively, (pointed) strongly
contractible). Then $(2^{X},\kappa^{\prime})$ is contractible (respectively,
(pointed) strongly contractible); as is $K(X,\kappa^{\prime})$.

###### Proof.

We give proofs for the full hyperspaces $2^{X}$ and $2^{Y}$; the proofs for
$K(X,\kappa^{\prime})$ and $K(Y,\lambda^{\prime})$ are similar.

  1. 1.

By hypothesis, there are continuous (pointed) maps
$f:(X,\kappa)\to(Y,\lambda)$ and $g:(Y,\lambda)\to(X,\kappa)$ (with basepoints
$x_{0}\in X$, $y_{0}\in Y$) such that $g\circ
f\sim_{(\kappa,\kappa)}\operatorname{id}_{X}$ (holding $x_{0}$ fixed) and
$f\circ g\sim_{(\lambda,\lambda)}\operatorname{id}_{Y}$ (holding $y_{0}$
fixed). By Proposition 5.3 and Theorem 5.8,

$g_{*}\circ f_{*}=(g\circ
f)_{*}\sim_{(\kappa^{\prime},\kappa^{\prime})}(\operatorname{id}_{X})_{*}=\operatorname{id}_{2^{X}}\mbox{
(holding $\\{x_{0}\\}$ fixed)}$

and

$f_{*}\circ g_{*}=(f\circ
g)_{*}\sim_{(\lambda^{\prime},\lambda^{\prime})}(\operatorname{id}_{Y})_{*}=\operatorname{id}_{2^{Y}}\mbox{
(holding $\\{y_{0}\\}$ fixed)}.$

Therefore, $(2^{X},\kappa^{\prime})$ and $(2^{Y},\lambda^{\prime})$ have the
same homotopy type.

  2. 2.

The proof for strong homotopy type is similar.

  3. 3.

Since (pointed) contractible (respectively, (pointed) strongly contractible)
means having the same (pointed) homotopy type (respectively, (pointed) strong
homotopy type) as a digital image of a single point, the assertions concerning
(pointed) contractibility (respectively, (pointed) strong contractibility)
follow from the above.

∎

######  Theorem 5.10.

Let $H:(X,\kappa)\times[0,n]_{{\mathbb{Z}}}\to(X,\kappa)$ be a (strong, in the
sense of strong homotopy) (strong, in the sense of retraction theory)
deformation retraction of $X$ to a subset $Y$, i.e., a (strong) homotopy
between the induced maps $H_{0},H_{n}:X\to X$ such that
$H_{0}=\operatorname{id}_{X}$ and $H_{n}$ is a retraction (that holds fixed
every point of $Y$). Then
$H_{*}:(2^{X},\kappa^{\prime})\times[0,n]_{{\mathbb{Z}}}\to(2^{X},\kappa^{\prime})$
(respectively,
$H_{*}:(K(X),\kappa^{\prime})\times[0,n]_{{\mathbb{Z}}}\to(K(X),\kappa^{\prime})$)
is a (strong, in the sense of strong homotopy) (strong, in the sense of
retraction theory) deformation retraction of $(2^{X},\kappa^{\prime})$ to
$(2^{Y},\kappa^{\prime})$ (respectively, of $(K(X),\kappa^{\prime})$ to
$(K(X),\kappa^{\prime})$).

###### Proof.

These assertions follow from Theorems 5.9 and 5.7. ∎

###  5.3 Function graphs

In this section, we explore an analog of function spaces for digital images.

######  Definition 5.11.

Let $(X,\kappa)$ and $(Y,\lambda)$ be digital images. Consider the set
$(Y,\lambda)^{(X,\kappa)}$, or $Y^{X}$ when $\kappa$ and $\lambda$ can be
assumed, defined by

$(Y,\lambda)^{(X,\kappa)}=\\{f:X\to Y~{}|~{}f\mbox{ is
$(\kappa,\lambda)$-continuous}\\}.$

We say $f,g\in Y^{X}$ are $\Phi(\kappa,\lambda)$-adjacent, or $\Phi$-adjacent
when $\kappa$ and $\lambda$ can be assumed, if for all $x\in X$ we have
$f(x)\leftrightarroweq_{\lambda}g(x)$.

A more restrictive adjacency for $Y^{X}$, which we denote as
$\Psi(\kappa,\lambda)$, is proposed in [26]. We have the following.

######  Definition 5.12.

[26] Let $f,g\in Y^{X}$. Then $f\leftrightarrow_{\Psi(\kappa,\lambda)}g$ if
given $x_{0}\leftrightarroweq_{\kappa}x_{1}$ in $X$,
$f(x_{0})\leftrightarroweq_{\lambda}g(x_{1})$ in $Y$.

######  Remark 5.13.

It is clear that $f\leftrightarrow_{\Psi(\kappa,\lambda)}g$ implies
$f\leftrightarrow_{\Phi(\kappa,\lambda)}g$. The converse is not generally
valid. For example, consider the functions
$f,g:[0,2]_{{\mathbb{Z}}}\to[0,2]_{{\mathbb{Z}}}$ given by $f(x)=x$,
$g(x)=\min\\{2,x+1\\}$. It is easily seen that $f,g\in
C([0,2]_{{\mathbb{Z}}},c_{1})$ and $f\leftrightarrow_{\Phi(c_{1},c_{1})}g$.
However, since $0\leftrightarrow_{c_{1}}1$ and
$f(0)=0\not\leftrightarrow_{c_{1}}2=g(1)$, $f$ and $g$ are not
$\Psi(c_{1},c_{1})$-adjacent.

We show below, at Example 5.17, an important difference between
$\Phi(c_{1},c_{1})$ and $\Psi(c_{1},c_{1})$.

######  Lemma 5.14.

Let $(X,\kappa)$ and $(Y,\lambda)$ be digital images. Let $f,g\in Y^{X}$. Then
$f$ and $g$ are homotopic in one step if and only if
$f\leftrightarroweq_{\Phi}g$.

###### Proof.

Suppose $f$ and $g$ are homotopic in one step. Then there exists
$H:X\times[0,1]_{{\mathbb{Z}}}\to Y$ such that for all $x\in X$, $H(x,0)=f(x)$
and $H(x,1)=g(x)$, and the induced function $H_{x}:[0,1]_{{\mathbb{Z}}}\to Y$
given by $H_{x}(t)=H(x,t)$ is $(c_{1},\lambda)$ continuous. The latter implies

$f(x)=H(x,0)\leftrightarroweq_{\lambda}H(x,1)=g(x)$

for all $x\in X$, so $f\leftrightarroweq_{\Phi}g$.

Suppose $f\leftrightarroweq_{\Phi}g$. Then one sees easily that the function
$H:X\times[0,1]_{{\mathbb{Z}}}\to Y$ defined by

$H(x,0)=f(x),~{}~{}~{}H(x,1)=g(x),$

is a homotopy in one step from $f$ to $g$. ∎

The following was suggested by an anonymous reviewer.

######  Theorem 5.15.

Let $(X,\kappa)$ and $(Y,\lambda)$ be digital images. Let $f,g\in Y^{X}$. Then
$f$ and $g$ are homotopic if and only if $f$ and $g$ belong to the same
component of $(Y^{X},\Phi)$.

###### Proof.

Since both homotopy between functions and being connected by a path are
transitive relations, the assertion follows from Lemma 5.14. ∎

Let $(S_{n},\kappa)$ be any cyclic graph of $n>4$ points, with point set
$S_{n}=\\{x_{i}\\}_{i=0}^{n-1}$ such that $x_{i}\leftrightarrow_{\kappa}x_{j}$
if and only if $|i-j|\in\\{1,n-1\\}$. Let $r_{j}\in C(S_{n},\kappa)$ be the
rotation $r_{j}(x_{i})=x_{(i+j)\mod n}$. We have the following.

######  Theorem 5.16.

[15] If $f\in C(S_{n},\kappa)$ such that $f$ and $\operatorname{id}_{S_{n}}$
are $\kappa$-homotopic, then $f=r_{j}$ for some $j$, $0\leq j<n$.

We do not get a similar outcome if we substitute $\Psi$ for $\Phi$ in Theorem
5.15, as shown in the following.

######  Example 5.17.

Let $(S_{n},\kappa)$ be any cyclic graph of $n>4$ points. Then all the
rotations $r_{j}$ are homotopic. However, no distinct $r_{j}$ and $r_{k}$
belong to the same component of $(S_{n}^{S_{n}},\Psi)$.

###### Proof.

Without loss of generality, $k=j+m<n$ for some $m$, $0<m<n-j$. Then
$H:S_{n}\times[0,m]_{{\mathbb{Z}}}\to S_{n}$, defined by
$H(x_{i},t)=r_{j+t}(x_{i})$, is a homotopy from $r_{j}$ to $r_{k}$.

It follows from Theorem 5.16 that every induced map $H_{t}$ of $H$ for
$t\in[0,m]_{{\mathbb{Z}}}$, and in particular, $H_{1}$, is a rotation.

  * •

For $1\leq m<n-2$, $r_{j}(x_{0})=x_{j}$ and $r_{k}(x_{1})=x_{(j+m+1)\mod n}$
are not $\kappa$-adjacent.

  * •

For $m=n-2$, we cannot follow the pattern used above, since

$r_{k}(x_{1})=r_{j+n-2}(x_{1})=r_{j-2\mod n}(x_{1})=x_{j-1\mod n}$

is adjacent to $r_{j}(x_{0})$. However,

$r_{k}(x_{0})=r_{j+n-2}(x_{0})=r_{j-2\mod n}(x_{0})=x_{j-2\mod n}$

is neither adjacent nor equal to $r_{j}(x_{0})$.

  * •

For $m=n-1$ we must have $j=0$. Therefore, $r_{j}(x_{1})=x_{1}$ and
$r_{k}(x_{0})=x_{n-1}$ are not $\kappa$-adjacent.

In every case, $r_{j}$ and $r_{k}$ are not $\Psi$-adjacent. This completes the
proof. ∎

######  Theorem 5.18.

Let $(X,\kappa)$ and $(Y,\lambda)$ be digital images. Let $W$ be a
$\lambda$-retract of $Y$. Then $(W^{X},\Phi(\kappa,\lambda))$ is a retract of
$(Y^{X},\Phi(\kappa,\lambda))$.

###### Proof.

Let $r:Y\to W$ be a $\lambda$-retraction. Then for every
$(\kappa,\lambda)$-continuous $f:X\to Y$, $r\circ f:X\to W$ is continuous by
Proposition 2.3. Further, if $f(X)\subset W$ then $r\circ f=f$. The assertion
follows. ∎

We present results that link the topics of hyperspaces and function graphs.

######  Theorem 5.19.

Let $f\leftrightarrow_{\Phi(\kappa,\lambda)}g$ in $Y^{X}$. Then for $A\in
2^{X}$, $f(A)\leftrightarroweq_{\lambda^{\prime}}g(A)$.

###### Proof.

Let $y_{f}\in f(A)$. Let $x_{f}\in f^{-1}(y_{f})$. Then
$y_{f}=f(x_{f})\leftrightarroweq_{\lambda}g(x_{f})$. Similarly, given
$y_{g}\in g(A)$, there exists $x_{g}\in g^{-1}(y_{g})$ such that
$f(x_{g})\leftrightarroweq_{\lambda}g(x_{g})=y_{g}$. It follows that
$f(A)\leftrightarroweq_{\lambda^{\prime}}g(A)$. ∎

######  Theorem 5.20.

Let $(W,\kappa)$, $(X,\lambda)$, and $(Y,\mu)$ be digital images. Suppose
$f,g\in Y^{X}$ are $(\lambda,\mu)$-continuous. If $f$ and $g$ are

  * •

(strongly) $(\lambda,\mu)$-homotopic;

  * •

(strongly) pointed $(\lambda,\mu)$-homotopic with $x_{0}$ held fixed,

then the induced maps
$f_{*},g_{*}:(X^{W},\Phi(\kappa,\lambda))\to(Y^{W},\Phi(\kappa,\mu))$, defined
for all $F\in X^{W}$ by

$f_{*}(F)=f\circ F,~{}~{}~{}~{}~{}g_{*}(F)=g\circ F,$

are $(\Phi(\kappa,\lambda),\Phi(\kappa,\mu))$-continuous and, respectively,
$f_{*}$ and $g_{*}$ are,

  * •

(strongly) $(\Phi(\kappa,\lambda),\Phi(\kappa,\mu))$-homotopic;

  * •

(strongly) pointed $(\Phi(\kappa,\lambda),\Phi(\kappa,\mu))$-homotopic with
the constant function $\hat{x}_{0}$ held fixed.

###### Proof.

Let $F,G\in X^{W}$ be $(\kappa,\lambda)$-continuous with
$F\leftrightarrow_{\Phi(\kappa,\lambda)}G$ and let $w\in W$. Then

$F(w)\leftrightarroweq_{\lambda}G(w),\mbox{ so }f_{*}(F)(w)=f\circ
F(w)\leftrightarroweq_{\mu}f\circ G(w)=f_{*}(G)(w),$

so $f_{*}(F)\leftrightarroweq_{\Phi(\kappa,\mu)}f_{*}(G)$, hence $f_{*}$ is
continuous. Similarly, $g_{*}$ is continuous.

We proceed with a proof for homotopic maps; the other assertions are proven
similarly.

Let $H:X\times[0,n]_{{\mathbb{Z}}}\to Y$ be a $(\lambda,\mu)$-homotopy from
$f$ to $g$. Let
$H_{*}:(X^{W},\Phi(\kappa,\lambda))\times[0,n]_{{\mathbb{Z}}}\to(Y^{W},\Phi(\kappa,\mu))$
be given by $H_{*}(F,t)(x)=H(F(x),t)$. We have the following.

  * •

$H_{*}(F,0)(x)=H(F(x),0)=f(F(x))=f_{*}(F)(x)$, so $H_{*}|_{t=0}=f_{*}$; and
$H_{*}(F,n)(x)=H(F(x),n)=g(F(x))=g_{*}(F)(x)$, so $H_{*}|_{t=n}=g_{*}$.

  * •

Given $F\in X^{W}$, the induced function $H_{*,F}:[0,n]_{{\mathbb{Z}}}\to
Y^{W}$ given by $H_{*,F}(t)(w)=H(F(w),t)$ satisfies, for
$t_{0}\leftrightarrow_{c_{1}}t_{1}$ in $[0,n]_{{\mathbb{Z}}}$,

$H_{*,F}(t_{0})(w)=H(F(w),t_{0})\leftrightarroweq_{\mu}H(F(w),t_{1})(w)=H_{*,F}(t_{1})(w),$

so $H_{*,F}$ is $(c_{1},\Phi(\lambda,\mu))$-continuous.

  * •

Given $t\in[0,n]_{{\mathbb{Z}}}$, the induced function $H_{*,t}:X^{W}\to
Y^{W}$ given by $H_{*,t}(F)(w)=H(F(w),t)$ satisfies, for
$F_{0}\leftrightarrow_{\Phi(\kappa,\lambda)}F_{1}$ in $X^{W}$,

$H_{*,t}(F_{0})(w)=H(F_{0}(w),t)\leftrightarroweq_{\mu}H(F_{1}(w),t)=H_{*,t}(F_{1})(w).$

Therefore, $H_{*,t}$ is $(\Phi(\kappa,\lambda),\Phi(\kappa,\mu))$-continuous.

Therefore, $H_{*}$ is a homotopy from $f_{*}$ to $g_{*}$. ∎

######  Proposition 5.21.

Let $(V,\kappa)$, $(W,\lambda)$, $(X,\mu)$, $(Y,\nu)$ be digital images. Let
$f:(W,\lambda)\to(X,\mu)$ and $g:(X,\mu)\to(Y,\nu)$ be continuous. Consider
the induced maps $f_{*}:W^{V}\to X^{V}$ and $g_{*}:X^{W}\to Y^{W}$. We have
$(g\circ f)_{*}=g_{*}\circ f_{*}:W^{V}\to Y^{V}$.

###### Proof.

Given $F:V\to W$, we have

$g_{*}\circ f_{*}(F)=g_{*}(f\circ F)=g\circ(f\circ F)=(g\circ f)\circ
F=(g\circ f)_{*}(F).$

The assertion follows. ∎

######  Corollary 5.22.

Let $(X,\kappa)$ and $(Y,\lambda)$ be digital images. Suppose $(X,\kappa)$ and
$(Y,\lambda)$ have the same (strong) (pointed) homotopy type. Then
$(X^{X},\Phi(\kappa,\kappa))$ and $(Y^{Y},\Phi(\lambda,\lambda))$ have the
same (strong) (pointed) homotopy type, respectively.

###### Proof.

We give a proof for “same homotopy type”; the other assertions are established
similarly (in the pointed cases, if $x_{0}\in X$ and $y_{0}\in Y$ are the
basepoints of the assumption, then the constant maps $\hat{x_{0}}\in X^{X}$
and $\hat{y_{0}}\in Y^{Y}$ are the basepoints of the conclusion).

If $(X,\kappa)$ and $(Y,\lambda)$ have the same homotopy type, then there are
continuous functions $f:X\to Y$ and $g:Y\to X$ such that $g\circ
f\sim_{\kappa,\kappa}\operatorname{id}_{X}$ and $f\circ
g\sim_{\lambda,\lambda}\operatorname{id}_{Y}$. By Theorem 5.20 and Proposition
5.21, we have

$(g\circ
f)_{*}\sim_{\Phi(\kappa,\kappa)}(\operatorname{id}_{X})_{*}=\operatorname{id}_{X^{X}}$

and similarly,

$(f\circ
g)_{*}\sim_{\Phi(\lambda,\lambda)}(\operatorname{id}_{Y})_{*}=\operatorname{id}_{Y^{Y}}.$

Thus, $(X^{X},\Phi(\kappa,\kappa))$ and $(Y^{Y},\Phi(\lambda,\lambda))$ have
the same homotopy type. ∎

######  Corollary 5.23.

Let $(X,\kappa)$ be a digital image. Suppose $(X,\kappa)$ is

  * •

(strongly) contractible;

  * •

(strongly) pointed contractible with basepoint $x_{0}$.

Then, respectively, $(X^{X},\Phi(\kappa,\kappa))$ is

  * •

(strongly) contractible;

  * •

(strongly) pointed contractible with the constant function $\hat{x_{0}}$ as
basepoint.

###### Proof.

We give a proof for “contractible”; the other assertions follow similarly.

Since “contractible” means homotopy equivalent to a digital image with a
single point, the assertion follows from Corollary 5.22. ∎

##  6 Connectedness in digital hyperspaces

We have the following.

######  Proposition 6.1.

Let $(X,\kappa)$ be a digital image. Let $W$ be a nonempty
$\kappa^{\prime}$-connected subset of $K(X)$. Then $W^{\prime}=\bigcup_{Y\in
W}Y$ is a $\kappa$-connected subset of $X$.

###### Proof.

Let $x_{0},x_{1}\in W^{\prime}$. There exist $Y_{i}\in W$ such that $x_{i}\in
Y_{i}\in K(X,\kappa^{\prime})$. Since $W$ is $\kappa^{\prime}$-connected,
there exists a $\kappa^{\prime}$-path $\\{W_{i}\\}_{i=0}^{n}\subset W$ from
$Y_{0}$ to $Y_{1}$, i.e., $W_{0}=Y_{0}$,
$W_{i}\leftrightarrow_{\kappa^{\prime}}W_{i+1}$, and $W_{n}=Y_{1}$.

By Definition 3.1, there exist $p_{i}\in W_{i}$, $q_{i+1}\in W_{i+i}$ such
that $p_{i}\leftrightarroweq_{\kappa}q_{i+1}$. As each $W_{i}$ is
$\kappa$-connected, there exist $\kappa$-paths $P_{0}\subset Y_{0}=W_{0}$ from
$x_{0}$ to $p_{0}$; $P_{i}\subset W_{i}$ from $q_{i}$ to $p_{i+1}$, $1\leq
i<n$; and $P_{n}\subset W_{n}=Y_{1}$ from $p_{n}$ to $x_{1}$.

Then $\bigcup_{i=0}^{n}P_{i}$ is a $\kappa$-path in $W^{\prime}$ from $x_{0}$
to $x_{1}$. It follows that $W^{\prime}$ is $\kappa$-connected. ∎

######  Proposition 6.2.

Let $C_{0}$ and $C_{1}$ be distinct components of $(X,\kappa)$. Let

$A_{i}\in K(C_{i},\kappa^{\prime})\mbox{ for }i\in\\{0,1\\}.$ (1)

Then $A_{0}$ and $A_{1}$ are points of distinct components of
$K(X,\kappa^{\prime})$.

###### Proof.

Were $A_{0}$ and $A_{1}$ in the same component of $K(X,\kappa^{\prime})$, then
there would exist a path $\\{B_{j}\\}_{j=0}^{n}\subset K(X,\kappa^{\prime})$
such that $A_{0}=B_{0}$,

$B_{j}\leftrightarrow_{\kappa^{\prime}}B_{j+1}\mbox{ for }1\leq j<n,$ (2)

and $B_{n}=A_{1}$. By (1), there is a smallest $k\in{\mathbb{N}}$ such that
$0\leq k<n$, $B_{k}\subset C_{0}$, and $B_{k+1}\not\subset C_{0}$. But by (2),
$B_{k}\cup B_{k+1}$ is $\kappa$-connected and therefore must be a subset of
$C_{0}$, contrary to our choice of $k$. It follows that $A_{0}$ and $A_{1}$
are points of distinct components of $K(X,\kappa^{\prime})$. ∎

######  Proposition 6.3.

Let $(X,\kappa)$ be a finite connected digital image. Then
$K(X,\kappa^{\prime})$ is connected.

###### Proof.

Let $A\in K(X,\kappa^{\prime})$. We show there is a path in
$K(X,\kappa^{\prime})$ from $A$ to $X$. If $A=X$, we are done. Otherwise,
since $X$ is connected, there are sequences $\\{x_{i}\\}_{i=1}^{m}\subset
X\setminus A$ and $\\{A_{j}\\}_{j=0}^{m}$ such that $A=A_{0}$,
$A_{j+1}=A_{j}\cup\\{x_{j+1}\\}$, $A_{j+1}$ is connected, and $A_{m}=X$.
Therefore, $A_{j}\leftrightarrow_{\kappa^{\prime}}A_{j+1}$. Thus
$\\{A_{j}\\}_{j=0}^{m}$ is a $\kappa^{\prime}$-path in $K(X,\kappa^{\prime})$
from $A$ to $X$.

Since $A$ was arbitrarily chosen, it follows that $K(X,\kappa^{\prime})$ is
connected. ∎

######  Proposition 6.4.

Let $D$ be a component of $(X,\kappa)$. Then $K(D,\kappa^{\prime})$ is a
component of $K(X,\kappa^{\prime})$.

###### Proof.

By Proposition 6.3, $K(D,\kappa^{\prime})$ is connected. The conclusion
follows from Proposition 6.2. ∎

######  Theorem 6.5.

Let $(X,\kappa)$ be a digital image. Then $X$ is $\kappa$-connected if and
only if $K(X,\kappa^{\prime})$ is $\kappa^{\prime}$-connected.

###### Proof.

Suppose $(X,\kappa)$ is connected. By Proposition 6.4, $K(X,\kappa^{\prime})$
is $\kappa^{\prime}$-connected.

Conversely, suppose $K(X,\kappa^{\prime})$ is $\kappa^{\prime}$-connected. By
Proposition 6.2, $(X,\kappa)$ must be connected. ∎

######  Lemma 6.6.

Let $(X,\kappa)$ be a digital image. Let $A$ be a finite member of
$K(X,\kappa^{\prime})$. Then there is a path ${\cal P}$ in
$K(A,\kappa^{\prime})$ from a singleton to $A$.

###### Proof.

Let $x_{0}\in A$. By Proposition 6.3, there is a path in
$K(A,\kappa^{\prime})$ from $\\{\,x_{0}\,\\}$ to $A$. ∎

Suppose $(X,\kappa)$ is a connected digital image. We say $Y\subset X$
disconnects $(X,\kappa)$ if $X\setminus Y$ is not $\kappa$-connected.

######  Theorem 6.7.

Let $(X,\kappa)$ be a connected digital image. Let $Y\subset X$. Let

${\cal Y}=\\{B\in K(X,\kappa^{\prime})~{}|~{}B\cap Y\neq\emptyset\\}.$ (3)

If $Y$ disconnects $(X,\kappa)$ then ${\cal Y}$ disconnects
$K(X,\kappa^{\prime})$.

###### Proof.

Suppose $Y$ disconnects $(X,\kappa)$. Then there are $x_{0},x_{1}$ that are in
distinct components of $X\setminus Y$.

Suppose ${\cal Y}$ fails to disconnect $K(X,\kappa^{\prime})$. Then there
exists a $\kappa^{\prime}$-path

${\cal P}=\\{B_{j}\\}_{j=0}^{n}\subset K(X,\kappa^{\prime})\setminus{\cal Y}$
(4)

from $\\{x_{0}\\}$ to $\\{x_{1}\\}$. By Definition 3.1, there exist
$y_{j},z_{j}\in B_{j}$ such that $y_{j}\leftrightarroweq_{\kappa}z_{j+1}$ for
$j<n$. Since $B_{j}$ is connected, there are $\kappa$-paths $P_{0}\subset
B_{0}$ from $x_{0}$ to $y_{0}$, $P_{j}\subset B_{j}$ from $z_{j}$ to $y_{j}$,
and $P_{n}\subset B_{n}$ from $z_{n}$ to $x_{1}$. Then
$P=\bigcup_{j=0}^{n}P_{j}$ is a $\kappa$-path in
$\bigcup_{j=0}^{n}B_{j}\subset X$ from $x_{0}$ to $x_{1}$. Since $Y$
disconnects $X$, we must have $P\cap Y\neq\emptyset$. Hence for some $k$,
$B_{k}\cap Y\neq\emptyset$, contrary to (4). The contradiction establishes
that ${\cal Y}$ disconnects $K(X,\kappa^{\prime})$. ∎

##  7 Multivalued functions and hyperspaces

In this section, we examine relations between various notions of continuous
multivalued functions between digital images, and hyperspaces of digital
images.

######  Definition 7.1.

A multivalued function $F:(X,\kappa)\multimap(Y,\lambda)$

  * •

has strong continuity [31] if for each pair of adjacent $x,y\in X$, every
point of $F(x)$ is adjacent or equal to some point of $F(y)$ and every point
of $F(y)$ is adjacent or equal to some point of $F(x)$;

  * •

has weak continuity [31] if for each pair of adjacent $x,y\in X$, $F(x)$ and
$F(y)$ are adjacent sets in $Y$, i.e., there exist $a\in F(x)$, $b\in F(y)$
such that $a\leftrightarroweq_{\lambda}b$;

  * •

is connectivity preserving [25] if $F(A)\subset Y$ is connected whenever
$A\subset X$ is connected;

  * •

is continuous [21, 22] if $X\subset{\mathbb{Z}}^{n}$, $\kappa=c_{u}$ for
$1\leq u\leq n$, and $F$ is generated by a continuous function $f:S(X,r)\to Y$
for some positive integer $r$; where $S(X,r)=\bigcup_{x\in X}S(\\{x\\},r)$,
where for $x=(x_{1},\ldots,x_{n})$, $S(\\{x\\},r)$ is the set of all points
$(y_{1},\ldots,y_{n})$ such that for each index $i$ we have
$y_{i}=x_{i}+k_{i}/r$ for some integer $k_{i}$ such that $0\leq k_{i}<r$;
$S(X,r)$ inherits $c_{u}$ in the sense that
$(y_{1},\ldots,y_{n})\leftrightarroweq_{c_{u}}(a_{1},\ldots,a_{n})$ in
$S(X,r)$ if for at most $u$ indices $i$, $|y_{i}-a_{i}|=1/r$ and for all other
indices $j$, $y_{j}=a_{j}$; and “$F$ is generated by $f$” means for all $x\in
X$, $F(x)=\bigcup_{y\in S(\\{x\\},r)}\\{f(y)\\}$.

We have the following.

######  Theorem 7.2.

Let $F:(X,\kappa)\multimap(Y,\lambda)$ be a strongly continuous multifunction
between digital images. Then the function
$F_{*}:(2^{X},\kappa^{\prime})\to(2^{Y},\lambda^{\prime})$ defined by
$F_{*}(A)=F(A)$ is continuous.

###### Proof.

Let $A_{0}\leftrightarrow_{\kappa^{\prime}}A_{1}$ in $2^{X}$. We must show
that $F(A_{0})\leftrightarroweq_{\lambda^{\prime}}F(A_{1})$ in $2^{Y}$.

Let $x\in A_{0}$, $y\in A_{1}$ such that $x\leftrightarroweq_{\kappa}y$. By
Definition 7.1, for every $p\in F(x)$ there exists $q\in F(y)$ such that
$p\leftrightarroweq_{\lambda}q$. Similarly, given $u\in A_{1}$, $v\in A_{0}$
such that $u\leftrightarrow_{\kappa}v$, for every $r\in F(u)$ there exists
$s\in F(v)$ such that $r\leftrightarroweq_{\lambda}s$. The assertion follows.
∎

The following shows that in substituting weak continuity, continuity, or
connectivity-preserving for strong continuity, we fail to obtain a result
analogous to Theorem 7.2.

######  Example 7.3.

Let $F:([0,1]_{{\mathbb{Z}}},c_{1})\multimap([0,2]_{{\mathbb{Z}}},c_{1})$ be
defined by $F(0)=\\{0\\}$, $F(1)=\\{1,2\\}$. Then $F$ has weak
$c_{1}$-continuity, is $c_{1}$-continuous, and is $c_{1}$-connectivity-
preserving, but since $2\in F(1)$ has no $c_{1}$-neighbor in $F(0)$, the
induced function $F_{*}:(2^{X},c_{1}^{\prime})\to(2^{Y},c_{1}^{\prime})$ is
not $(c_{1}^{\prime},c_{1}^{\prime})$-continuous.

##  8 Cycles and Girth

The reader is reminded that:

  * •

a point in $2^{X}$ is a nonempty subset of $X$;

  * •

a cycle in $X$ is a closed path of at least 3 distinct points in which no node
repeats, but in which a point $x$ can be adjacent to points distinct from the
predecessor and successor of $x$ in the path (the cycle does not need to be
chordless).

######  Proposition 8.1.

Let $(X,\kappa)$ be a digital image. Then $K(X,\kappa^{\prime})$ has a 3-cycle
if and only if $(X,\kappa)$ has a non-isolated point.

###### Proof.

It is elementary that if the points of $(X,\kappa)$ are all isolated, then
$K(X,\kappa^{\prime})$ has no cycle.

Suppose $x\in X$ is not isolated in $(X,\kappa)$. Then there exists $y\in X$
such that $x\leftrightarrow_{\kappa}y$. Then
$\left\\{\\{x\\},\\{x,y\\},\\{y\\}\right\\}$ is a 3-cycle in
$K(X,\kappa^{\prime})$. ∎

The girth of a graph $(X,\kappa)$ is variously described in the literature as
the length of a shortest or of a longest [1] cycle in $(X,\kappa)$. We may
distinguish these concepts as girth and Girth, respectively. In light of
Proposition 8.1, the Girth is more interesting, so in the following we focus
on Girth.

######  Example 8.2.

If $(X,\kappa)$ is a digital image and $x\in X$ such that $N(X,x,\kappa)$ has
distinct points $u$ and $v$ that are not $\kappa$-adjacent, then
$K(X,\kappa^{\prime})$ has Girth of at least 6.

###### Proof.

By hypothesis, there exist distinct $u,v\in N(X,x,\kappa)$. Then by Definition
3.1, $K(X,\kappa^{\prime})$ has a 6-cycle

$\\{u\\},\\{u,x\\},\\{u,x,v\\},\\{x,v\\},\\{v\\},\\{x\\}.$

∎

######  Example 8.3.

The Girth of $(2^{[1,4]_{{\mathbb{Z}}}},c_{1}^{\prime})$ is 15, which is equal
to $\\#(2^{[1,4]_{{\mathbb{Z}}}},c_{1}^{\prime})$. I.e.,
$(2^{[1,4]_{{\mathbb{Z}}}},c_{1}^{\prime})$ has a cycle containing all members
of $(2^{[1,4]_{{\mathbb{Z}}}},c_{1}^{\prime})$.

###### Proof.

It is easy to see that the following sequence of the 15 distinct members of
$(2^{[1,4]_{{\mathbb{Z}}}},c_{1}^{\prime})$ is a $c_{1}^{\prime}$-cycle.

$\\{1,2\\},\\{1,2,3\\},\\{1,3\\},\\{1,4\\},\\{1,3,4\\},\\{1,2,4\\},\\{1,2,3,4\\},\\{2,3,4\\},\\{2,3\\},$
$\\{2,4\\},\\{3,4\\},\\{4\\},\\{3\\},\\{2\\},\\{1\\}$

∎

##  9 Dominating set

A subset $D$ of a graph $(X,\kappa)$ is a dominating set for, or dominates,
$(X,\kappa)$, if given $x\in X$ there exists $d\in D$ such that
$d\leftrightarroweq_{\kappa}x$.

######  Theorem 9.1.

Let $(X,\kappa)$ be a digital image and let $D\subset X$. Let

${\cal D}=\\{A\in 2^{X}~{}|~{}A\cap D\neq\emptyset\\}$

Then $D$ dominates $(X,\kappa)$ if and only if ${\cal D}$ dominates
$(2^{X},\kappa^{\prime})$.

###### Proof.

Suppose $D$ dominates $(X,\kappa)$. Let $x\in A\in 2^{X}$. There exists $y\in
D$ such that $x\leftrightarroweq_{\kappa}y$. It follows from Definition 3.1
that

$A^{\prime}=A\cup\\{y\\}\leftrightarroweq_{\kappa^{\prime}}A.$

Since $A$ is arbitrary and $A^{\prime}\in{\cal D}$, it follows that ${\cal D}$
dominates $(2^{X},\kappa^{\prime})$.

Suppose ${\cal D}$ dominates $(2^{X},\kappa^{\prime})$. Let $x\in X$. Then
there exists $A\in{\cal D}$ such that
$A\leftrightarroweq_{\kappa^{\prime}}\\{x\\}$. Therefore, for all $a\in A$ we
have $a\leftrightarroweq_{\kappa}x$. Since there exists $d\in A\cap D$,
$d\leftrightarroweq_{\kappa}x$. Thus, $D$ dominates $X$. ∎

##  10 Diameter

######  Definition 10.1.

[23] Let $(X,\kappa)$ be a connected graph. The shortest path metric for
$(X,\kappa)$ is

$d_{\ell}(x,y)=\min\\{length(P)~{}|~{}P\mbox{ is a $\kappa$-path in $X$ from
$x$ to $y$}\\},\mbox{ for }x,y\in X.$

######  Definition 10.2.

The diameter of a finite connected graph $(X,\kappa)$ is

$diam(X,\kappa)=\max\\{d_{\ell}(x,y)~{}|~{}x,y\in X\\}.$

######  Definition 10.3.

[1] Let $(X,\kappa)$ be a connected digital image. For $x\in X$, the
associated number $e(x)$ of $x$ is

$e(x)=\max\\{d_{\ell}(x,y)~{}|~{}y\in X\\}.$

A center of $(X,\kappa)$ is a point $x_{0}\in X$ such that

$e(x_{0})=\min\\{e(x)~{}|~{}x\in X\\}.$

The associated number of the center is the radius of $(X,\kappa)$.

We have the following.

######  Theorem 10.4.

Let $(X,\kappa)$ be a finite connected digital image with radius $r$. Let
$\\#X=n$. Then $diam(K(X,\kappa^{\prime}))<2(n+r-1)$.

###### Proof.

Let $x_{0}$ be a center of $(X,\kappa)$. Let $A_{0},A_{1}\in
K(X,\kappa^{\prime})$. Let $y_{0}\in A_{0}$, $y_{1}\in A_{1}$. By assumption,
there are paths $P_{i}$ of length at most $r$ from $x_{0}$ to $y_{i}$. Thus,
$P_{0}\cup P_{1}$ is a $\kappa$-path in $X$ of length at most $2r$ from
$y_{0}$ to $y_{1}$. It follows from Definition 3.1 that ${\cal
P}=\\{\\{p\\}~{}|~{}p\in P_{0}\cup P_{1}\\}$ is a $\kappa^{\prime}$-path in
$K(X)$ of length at most $2r$ from $\\{y_{0}\\}$ to $\\{y_{1}\\}$.

Let $Q_{0}=\\{y_{0}\\}$. We argue inductively as follows. Suppose we have
$Q_{k}\in K(X,\kappa^{\prime})$ such that $Q_{k}\subset A_{0}$. If $Q_{k}\neq
A_{0}$, then since $A_{0}$ is connected, there exists $q\in A_{0}\setminus
Q_{k}$ such that for some $q^{\prime}\in Q_{k}$,
$q\leftrightarrow_{\kappa}q^{\prime}$. By Definition 3.1, we have

$Q_{k+1}=Q_{k}\cup\\{q^{\prime}\\}\leftrightarrow_{\kappa^{\prime}}Q_{k}.$

Since $Q_{\\#A_{0}-1}=A_{0}$, the set ${\cal
P}_{0}=\\{Q_{j}\\}_{j=0}^{\\#A_{0}-1}$ is a path in $K(X,\kappa^{\prime})$ of
length $\\#A_{0}-1$ from $\\{y_{0}\\}$ to $A_{0}$; equivalently, from $A_{0}$
to $\\{y_{0}\\}$.

Similarly, we can construct a path ${\cal P}_{1}$ in $K(X,\kappa^{\prime})$ of
length $\\#A_{1}-1$ from $\\{y_{1}\\}$ to $A_{1}$. Therefore, ${\cal
P}_{0}\cup{\cal P}\cup{\cal P}_{1}$ is a path in $K(X,\kappa^{\prime})$ of
length at most

$\\#A_{0}-1+2r+\\#A_{1}-1\leq 2(n+r-1)$

from $A_{0}$ to $A_{1}$. Further, we may assume
$\min\\{\\#A_{0},\\#A_{1}\\}<n$; since otherwise $A_{0}=X=A_{1}$, so there is
a path of length 0 from $A_{0}$ to $A_{1}$ in $K(X,\kappa^{\prime})$. It
follows that for any $A_{0},A_{1}\in K(X,\kappa^{\prime})$ there is a path in
$K(X,\kappa^{\prime})$ from $A_{0}$ to $A_{1}$ of length less than $2(n+r-1)$.
The assertion follows. ∎

##  11 Further remarks

We have introduced into digital topology the study of hyperspaces of digital
images, and have taken a somewhat different approach to function graphs than
that introduced in [26]. We have studied some relations between digital
hyperspaces and digital function graphs. We have examined a number of
properties of digital hyperspaces concerning cardinality, continuous maps and
homotopy, connectivity, cycles and Girth, dominating sets, and diameters.

Suggestions from anonymous reviewers are gratefully acknowledged.

##  12 Declarations

This research was not supported by a grant, nor by any organizational funding.
The author has no relevant financial or non-financial interests to disclose.

## References

  * [1] C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973
  * [2] K. Borsuk, On some metrizations of the hyperspace of compact sets, Fundamenta Mathematicae 41 (1954), 168-202
  * [3] K. Borsuk, Concerning the set of retractions, Colloquium Mathematicum 18 (1967), 197 - 201
  * [4] K. Borsuk, On a metrization of the hyperspace of a metric space, Fundamenta Mathematicae 94 (1977), 191 - 207
  * [5] L. Boxer, Retraction spaces and the homotopy metric, Topology and its Applications 11 (1980), 17 - 29
  * [6] L. Boxer, AANR’s and ARI maps, Topology Proceedings 6 (1981), 219 - 226
  * [7] L. Boxer, Hyperspaces where convergence to a calm limit implies eventual shape equivalence, Fundamenta Mathematicae 115 (1983), 213 - 222
  * [8] L. Boxer, Maps related to calmness, Topology and its Applications 15 (1983), 11 - 17
  * [9] L. Boxer, Computing deviations from convexity in polygons, Pattern Recognition Letters 14 (1993), 163-167
  * [10] L. Boxer, Digitally continuous functions, Pattern Recognition Letters 15 (1994), 833-839.
  * [11] L. Boxer, On Hausdorff-like metrics for fuzzy sets, Pattern Recognition Letters 18 (1997), 115 - 118. Corrigenda: Pattern Recognition Letters 18 (1997), 505-506
  * [12] L. Boxer, A classical construction for the digital fundamental group, Journal of Mathematical Imaging and Vision 10 (1999), 51-62
  * [13] L. Boxer, Beyond the Hausdorff metric in digital topology, Applied General Topology 23 (1) (2022), 69-77
  * [14] L. Boxer and R. Miller, Coarse grained gather and scatter operations with applications, Journal of Parallel and Distributed Computing 64 (2004), 1297-1320
  * [15] L. Boxer and P.C. Staecker, Fixed point sets in digital topology, 1, Applied Digital Topology 21 (1) (2020), 87-110
  * [16] Z. $\check{C}$erin, $\cal{C}$-calmly regular convergence, Topology Proceedings 4 (1979), 29 - 49
  * [17] Z. $\check{C}$erin, $\cal{C}$-regularly movable convergence, Houston Journal of Mathematics 6 (4) (1980), 471 - 490
  * [18] B.B. Chaudhuri and A. Rosenfeld, On a metric distance between fuzzy sets, Pattern Recognition Letters 17 (11) (1996), 1157 - 1160
  * [19] L. Chen, Gradually varied surfaces and its optimal uniform approximation, SPIE Proceedings 2182 (1994), 300-307.
  * [20] L. Chen, Discrete Surfaces and Manifolds, Scientific Practical Computing, Rockville, MD, 2004
  * [21] C. Escribano, A. Giraldo, and M. Sastre, Digitally continuous multivalued functions, in Discrete Geometry for Computer Imagery. Lecture Notes in Computer Science, vol. 4992, pp. 81 - 92, Springer, Berlin (2008)
  * [22] C. Escribano, A. Giraldo, and M. Sastre, Digitally continuous multivalued functions, morphological operations and thinning algorithms, Journal of Mathematical Imaging and Vision 42 (2012), 76 - 91
  * [23] S-E Han, Non-product property of the digital fundamental group, Information Sciences 171 (2005), 73-91
  * [24] E. Khalimsky, Motion, deformation, and homotopy in finite spaces, in Proceedings IEEE International Conference on Systems, Man, and Cybernetics, IEEE International Conference on Systems, Man, and Cybernetics, 1987, 227-234.
  * [25] V.A. Kovalevsky, A new concept for digital geometry, in Shape in Picture, Springer, New York (1994)
  * [26] G. Lupton, J. Oprea, and N.A. Scoville, Homotopy theory in digital topology, Discrete $\&$ Computational Geometry 67 (1) (2022), 112 - 165
  * [27] S.B. Nadler, Jr., Hyperspaces of Sets, Marcel Dekker, New York, 1978
  * [28] A. Rosenfeld, ‘Continuous’ functions on digital images, Pattern Recognition Letters 4 (1987), 177-184
  * [29] R. Shonkwiler, An image algorithm for computing the Hausdorff distance efficiently in linear time, Information Processing Letters 30 (2) (1989), 87-89
  * [30] P.C. Staecker, Digital homotopy relations and digital homology theories, Applied General Topology 22 (2) (2021), 223-250
  * [31] R. Tsaur and M Smyth, ‘Continuous’ multifunctions in discrete spaces with applications to fixed point theory. In: G. Bertrand, A. Imiya, and R. Klette, eds., Digital and Image Geometry, Lecture Notes in Computer Science, vol. 2243, pp 151-162. Springer, Berlin (2001), doi:10.1007/3-540-45576-05
  * [32] T. Vergili, Digital Hausdorff distance on a connected digital image, Communications Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics 69 (2) (2020), 76-88
  * [33] N. Wagner, The space of retractions of the 2-sphere and the annulus, Transactions of the American Mathematical Society 158 (1971), 319 - 329
  * [34] E.C. Zeeman and O.P. Buneman, Tolerance spaces and the brain, in The Origin of Life: Toward a Theoretical Biology, v. 1, C.H. Waddington, ed., Routledge, New York, 2017, 140 - 151