Introduction
A metric space is connected if it cannot be split into two disjoint non-empty open sets. Intuitively, a
connected space is "all in one piece" and cannot be separated into isolated regions.
Why does this matter? In optimization, connectedness rules out the presence of isolated "islands" in the feasible region,
so that the space is topologically one piece rather than two or more separated components. The stronger property of
path-connectedness, introduced later, goes further. It guarantees that any two feasible points can be
joined by a continuous curve inside the feasible set, so that an optimization algorithm can in principle move from any
starting point to any other. For open subsets of \(\mathbb{R}^n\), the two notions coincide, and in most practical
machine-learning settings they can be used interchangeably.
Connectedness is also foundational for more advanced structures like manifolds, which we will explore in
later pages. In those contexts, we often study a space by analyzing its individual connected parts, and path-connectedness
is what lets us measure distances along a surface.
Connected Sets
Formally, the notion of a space being "in one piece" is captured by the absence of a
separation. A separation of \(X\) is a pair of disjoint non-empty open
sets whose union is \(X\). If no such separation exists, the space is rigid enough to
support global continuity properties, such as the Intermediate Value Theorem.
Definition: Connected Metric Space
A metric space \(X\) is called a connected metric space if and only if
\(X\) cannot be expressed as the union of two disjoint non-empty open subsets of itself.
While the definition above provides the core intuition, connectedness is often easier to analyze through its equivalent
topological properties. The following theorem collects several tests for determining whether a space is truly in one piece.
Theorem: Criteria for Connectedness
Suppose \(X\) is a metric space. The following statements are equivalent, and \(X\) is connected if and only if it
satisfies any one of them.
- Boundary Criterion
Every proper non-empty subset of \(X\) has non-empty boundary in \(X\).
- Open-Closed Criterion
No proper non-empty subset of \(X\) is both open and closed in \(X\).
- Open Union Criterion
\(X\) is not the union of two disjoint non-empty open subsets of itself.
- Closed Union Criterion
\(X\) is not the union of two disjoint non-empty closed subsets of itself.
- Continuity Criterion
Either \(X = \emptyset\) or the only continuous functions from \(X\) to the discrete space
\(\{0, 1\}\) are the two constant functions.
Proof Sketch:
All five criteria say the same thing in different dialects. A separation of \(X\) is a partition
\(X = U \cup V\) into two disjoint non-empty open sets. This is exactly what (3) forbids. In such a partition, each
piece is also closed, being the complement of the other open piece. Hence (3) and (4) are the same statement with the
roles of open and closed interchanged. A subset that is both open and closed (clopen), proper and non-empty,
is precisely one half of a separation, giving (2).
Now let \(U\) be any proper non-empty subset of \(X\) and consider its
boundary \(\partial U\). The
conditions "\(U\) is open" and "\(U\) is closed" together force \(\partial U = \emptyset\), and conversely
\(\partial U = \emptyset\) makes \(U\) clopen. It follows that having a proper non-empty subset with empty boundary is
the same as having a clopen proper non-empty subset, giving (1).
The continuity criterion (5) is the same idea through a different lens. A continuous function \(f: X \to \{0, 1\}\)
into the two-point discrete space (where every subset is clopen, since the metric \(d(0,1) = 1\) makes each singleton
open) is determined by the preimages \(f^{-1}(\{0\})\) and \(f^{-1}(\{1\})\), which partition \(X\) and are themselves
clopen because
continuity is equivalent to openness of preimages.
Constant functions correspond to the trivial case where one preimage is empty. Non-constant continuous functions
correspond to genuine separations. So the absence of non-constant continuous \(\{0,1\}\)-valued functions is the
absence of clopen partitions, which is (2).
Connectedness is not just a static property of a space but is also remarkably stable under transformations. Specifically,
continuous functions cannot "break" a
connected space into pieces.
Theorem: Continuity Preserves Connectedness
Every continuous image of a connected metric space is connected. That is, if \(X\) is connected and
\(f: X \to Y\) is continuous, then \(f(X) \subseteq Y\) is connected.
Proof:
We use the Continuity Criterion (item 5 of the criteria for connectedness). We may assume \(X \neq \emptyset\), since
otherwise \(f(X) = \emptyset\) is connected. Let \(g: f(X) \to \{0,1\}\) be any continuous function into the discrete
two-point space. Viewed as a map onto the
metric subspace \(f(X)\), the
function \(f\) is still continuous, so \(g \circ f : X \to \{0,1\}\) is continuous as a
composition of continuous maps.
Since \(X\) is connected, the Continuity Criterion forces \(g \circ f\) to be constant on \(X\), say
\((g \circ f)(x) = c\) for all \(x \in X\). Every \(y \in f(X)\) has the form \(y = f(x)\) for some \(x \in X\), so
\(g(y) = g(f(x)) = c\). Thus \(g\) is constant on \(f(X)\). Applying the Continuity Criterion in the reverse direction,
we conclude that \(f(X)\) is connected.
When we apply these general topological principles to the familiar setting of the real line, we arrive at a
definitive characterization of connectivity in one dimension.
Corollary: Connected Subsets of \(\mathbb{R}\)
Suppose \(S\) is a non-empty subset of \(\mathbb{R}\). Then \(S\) is connected if and only if
\(S\) is an interval.
Proof:
(\(\Leftarrow\)) Suppose \(S\) is an interval, and for contradiction suppose \(S\) admits a separation \(S = U \cup V\)
with \(U, V\) disjoint non-empty open subsets of \(S\). Pick \(a \in U\) and \(b \in V\). By swapping \(U\) and \(V\)
if necessary, assume \(a \lt b\). Because \(S\) is an interval containing both \(a\) and \(b\), the entire closed
interval \([a, b]\) lies in \(S\).
The idea is to walk from \(a\) toward \(b\) staying inside \(U\) and ask how far we can go. Formally, set
\[
c = \sup\{\, t \in [a,b] : [a,t] \subseteq U \,\}.
\]
The set on the right is non-empty (it contains \(t = a\), since \([a,a] = \{a\} \subseteq U\)) and bounded above by
\(b\), so the supremum exists and \(a \le c \le b\). Since \([a,b] \subseteq S\), we have \(c \in S\), and since
\(S = U \cup V\) is a disjoint union, either \(c \in U\) or \(c \in V\). Each case leads to a contradiction.
We will use the fact that a subset \(W \subseteq S\) is open in \(S\) precisely when
\(W = S \cap \tilde{W}\) for some open \(\tilde{W} \subseteq \mathbb{R}\),
so that for any \(x \in W\) there exists \(\delta \gt 0\)
with \((x - \delta, x + \delta) \cap S \subseteq W\).
Case \(c \in U\).
Openness of \(U\) in \(S\) gives \(\delta \gt 0\) with
\((c - \delta, c + \delta) \cap S \subseteq U\). By the definition of \(c\) as a supremum, there exists
\(t_0 \in (c - \delta, c]\) with \([a, t_0] \subseteq U\). Combining this with
\([t_0, c] \subseteq (c - \delta, c + \delta) \cap S \subseteq U\) gives
\[
[a, c] = [a, t_0] \cup [t_0, c] \subseteq U.
\]
If \(c = b\), then \(b \in U\). But \(b \in V\) by choice, contradicting \(U \cap V = \emptyset\). If \(c \lt b\),
shrink \(\delta\) if needed so that \(c + \delta \le b\). Then
\([c, c + \delta/2] \subseteq (c - \delta, c + \delta) \cap S \subseteq U\), and together with \([a, c] \subseteq U\)
we obtain \([a, c + \delta/2] \subseteq U\). This makes \(c + \delta/2\) an element of
\(\{t \in [a,b] : [a,t] \subseteq U\}\) strictly larger than \(c\), contradicting the fact that \(c\) is the supremum.
Case \(c \in V\).
Openness of \(V\) in \(S\) gives \(\delta \gt 0\) with
\((c - \delta, c + \delta) \cap S \subseteq V\). Note \(a \ne c\) (since \(a \in U\), \(c \in V\), and
\(U \cap V = \emptyset\)), so \(a \lt c\). By the definition of \(c\) as a supremum, there exists
\(t_0 \in (c - \delta, c]\) with \([a, t_0] \subseteq U\). In particular \(t_0 \in U \subseteq S\). Combining
\(t_0 \in (c - \delta, c]\) with \(t_0 \in S\) gives \(t_0 \in (c - \delta, c + \delta) \cap S \subseteq V\), so
\(t_0 \in U \cap V = \emptyset\), a contradiction.
Both cases are impossible, so no such separation exists and \(S\) is connected.
(\(\Rightarrow\)) Conversely, suppose \(S\) is connected, and for contradiction suppose \(S\) is not an interval. Then
there exist \(a, b \in S\) and \(c \in \mathbb{R} \setminus S\) with \(a \lt c \lt b\). The sets
\(U = S \cap (-\infty, c)\) and \(V = S \cap (c, \infty)\) are open in \(S\)
(intersections of \(S\) with open subsets of \(\mathbb{R}\)),
disjoint, and non-empty (\(a \in U\), \(b \in V\)). Their union is \(S \setminus \{c\} = S\) since
\(c \notin S\). This is a separation, contradicting connectedness of \(S\).
Insight: Continuity and Interval Preservation
The fact that connected subsets of \(\mathbb{R}\) are exactly intervals is the fundamental reason why the Intermediate
Value Theorem holds. Since continuity preserves connectedness, the continuous image of an interval must also be an
interval, so a continuous function cannot "skip" values.
Intermediate Value Theorem
The Intermediate Value Theorem (IVT), a staple of calculus, can be viewed as a natural result of topology.
If a space is connected, a continuous function cannot skip any values as it moves across that space.
Proof:
By the theorem that
continuity preserves connectedness,
\(f(X) \subseteq \mathbb{R}\) is connected. The hypothesis on \(\alpha\) forces \(\inf f(X) \lt \sup f(X)\), so
\(f(X)\) is non-empty, and the corollary classifying
connected subsets of \(\mathbb{R}\) as
intervals shows that \(f(X)\) is an interval. Since \(\alpha \in (\inf f(X), \sup f(X))\), the defining properties of
infimum and supremum give points \(a, b \in f(X)\) with \(a \lt \alpha \lt b\). The interval \(f(X)\) then contains
\(\alpha\), so there exists \(z \in X\) with \(f(z) = \alpha\).
This proof shows that the IVT is not a special rule for real numbers but a fundamental property of how continuity and
connectivity work together.
Insight: Topological Foundation of the IVT
The Intermediate Value Theorem is a direct consequence of the fact that continuity preserves connectedness. In
optimization, this ensures that the image of any continuous objective function over a connected feasible region is
itself an interval. No intermediate value can be "missed." This is the logical basis for
root-finding algorithms like the bisection method, where the existence of a zero is guaranteed within
any interval where the function changes sign.
Connected Components
When a space is not connected, we can decompose it into its maximal connected subsets. These "islands" of connectivity
allow us to analyze the global structure of a space by studying its individual parts.
Definition: Connected Component
Suppose \(X\) is a metric space. A subset \(U\) of \(X\) is called a connected component of
\(X\) if and only if \(U\) is connected and there is no proper superset of \(U\) in \(X\) that is connected.
The definition above picks out a single component. What matters globally is how the components fit together.
Theorem: Components Partition a Metric Space
Suppose \(X\) is a metric space. Then the connected components of \(X\) are mutually disjoint and
all closed in \(X\). Moreover, \(X\) is the union of its connected components.
Proof Sketch:
The argument rests on one key fact, which we record for reuse:
Union Lemma.
If \(\{C_i\}_{i \in I}\) is a family of connected subsets of \(X\) sharing a common
point \(p\), then \(\bigcup_{i} C_i\) is connected.
Why it holds.
Suppose for contradiction that the union admits a separation \(\bigcup_i C_i = U \sqcup V\)
into disjoint non-empty sets open in \(\bigcup_i C_i\). The common point \(p\) lies in exactly one piece, say
\(p \in U\). Since \(V\) is non-empty, pick \(q \in V\). Then \(q \in C_{i_0}\) for some index \(i_0\), so
\(C_{i_0} \cap V\) is non-empty, and \(C_{i_0} \cap U\) contains \(p\) and is also non-empty. The pair
\((C_{i_0} \cap U,\, C_{i_0} \cap V)\) therefore consists of disjoint non-empty sets
open in \(C_{i_0}\)
whose union is \(C_{i_0}\), so it is a separation of \(C_{i_0}\), contradicting the connectedness of \(C_{i_0}\).
Cover.
For each \(x \in X\), let \(C(x)\) denote the union of all connected subsets of \(X\)
containing \(x\). This family is non-empty since \(\{x\}\) is trivially connected, and all its members share the common
point \(x\), so the Union Lemma gives \(C(x)\) connected. By construction, every connected set containing \(x\) is a
subset of \(C(x)\). Hence \(C(x)\) admits no strictly larger connected superset, making it a connected component. Every
point lies in its own component, so \(X = \bigcup_{x \in X} C(x)\). Conversely, every component arises this way. When
\(X \neq \emptyset\) a component \(D\) cannot be empty, since any singleton would be a strictly larger connected
superset, and choosing \(z \in D\) gives \(D \subseteq C(z)\), so maximality of \(D\) forces \(D = C(z)\).
Disjointness.
Suppose two components \(C(x)\) and \(C(y)\) intersect at a point \(p\). Both
contain \(p\), so the Union Lemma applies to \(\{C(x), C(y)\}\). The union \(C(x) \cup C(y)\) is connected and contains
\(C(x)\). Maximality of \(C(x)\) as a component forbids a strictly larger connected superset, so
\(C(x) \cup C(y) = C(x)\), that is, \(C(y) \subseteq C(x)\). The symmetric argument gives \(C(x) \subseteq C(y)\),
hence \(C(x) = C(y)\).
Closedness.
We claim the
closure of any connected
set is connected. Suppose for contradiction that \(\overline{C} = U \sqcup V\) is a separation into non-empty disjoint
sets open in \(\overline{C}\). Then \(C \cap U\) and \(C \cap V\) are disjoint and
open in \(C\). Moreover, both are
non-empty. Given \(q \in U\), openness of \(U\) in \(\overline{C}\) yields \(\varepsilon \gt 0\)
with \(B(q, \varepsilon) \cap \overline{C} \subseteq U\). Since \(q \in \overline{C}\) means
\(\operatorname{dist}(q, C) = 0\), the ball \(B(q, \varepsilon)\) contains a point of \(C\), which then lies in
\(C \cap U\). Symmetrically for \(V\). Their union is \(C\), giving a separation of \(C\) and contradicting
connectedness. We now apply this to a component \(C\). Its closure \(\overline{C}\) is connected and contains \(C\), so
maximality forces \(\overline{C} = C\), making \(C\) closed.
This decomposition into components is what turns an abstract topological statement into a practical tool for data analysis.
CS Insight: Clustering as Component Identification
In machine learning, clustering can be formally
viewed as identifying the connected components of an underlying data manifold. Algorithms like
DBSCAN define connectivity via density-reachable points, allowing for the discovery of clusters with
arbitrary non-convex shapes. Centroid-based approaches such as K-means cannot achieve this.
While the original DBSCAN is a foundational connectivity-based algorithm, its modern evolution,
HDBSCAN, is widely used in contemporary data science. By analyzing the
hierarchical structure of connected components across varying density levels, HDBSCAN eliminates
the need for a fixed distance parameter, making it robust for datasets with non-uniform densities.
This principle of "connectivity across scales" is a cornerstone of modern topological data analysis.
Furthermore, this topological concept is bridged to linear algebra through Spectral Clustering.
By representing data as a graph, the number of connected components corresponds exactly to the
multiplicity of the eigenvalue 0
in the Graph Laplacian matrix. This highlights
how the topological structure of a space directly dictates the capability of the algorithms operating within it.
References
-
Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996).
"A density-based algorithm for discovering clusters in large spatial databases with noise."
In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96).
[PDF via AAAI]
-
Campello, R. J., Moulavi, D., & Sander, J. (2013).
"Density-based clustering based on hierarchical density estimates."
In Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, Berlin, Heidelberg.
[Link via Springer]
Path-Connectedness
In optimization, path-connectedness is a more intuitive and often more useful property, since it asks whether we can "walk"
from one point to another along a continuous curve.
Definition: Path in a Metric Space
Suppose \(X\) is a metric space. Every continuous function \(f: [0, 1] \to X\) from the closed interval \([0, 1]\) into
\(X\) is called a path in \(X\) from the point \(f(0)\) to the point \(f(1)\). The points \(f(0)\) and
\(f(1)\) of \(X\) are called the endpoints of the path.
With the formal definition of a single path in place, we can now define a space where every point is continuously reachable
from every other point.
Definition: Pathwise Connected
Suppose \(X\) is a metric space. Then \(X\) is said to be pathwise connected if and only if
for each \(a, b \in X\), there is a path in \(X\) with endpoints \(a\) and \(b\).
Theorem: Path-Connected Implies Connected
Every pathwise connected metric space is connected.
Proof:
Suppose \(X\) is a pathwise connected metric space. We assume for the sake of contradiction that \(X\) is disconnected.
According to the Open Union Criterion, there exists a separation \(X = U \cup V\), where \(U\) and \(V\) are disjoint,
non-empty open sets.
Since \(U\) and \(V\) are non-empty, we can pick arbitrary points \(a \in U\) and \(b \in V\).
Because \(X\) is pathwise connected, there exists a continuous path \(f: [0, 1] \to X\) such that \(f(0) = a\) and \(f(1) = b\).
The closed interval \([0,1]\) is connected (connected subsets of \(\mathbb{R}\) are intervals),
and \(f\) is continuous, so by the theorem that
continuity preserves connectedness,
the image \(K = f([0,1])\) is connected. Therefore \(K\) admits no separation. In particular,
it cannot be written as
\[
K = (K \cap U) \cup (K \cap V)
\]
with \(K \cap U\) and \(K \cap V\) disjoint non-empty open subsets of \(K\).
However, since \(a \in K \cap U\) and \(b \in K \cap V\), both intersections are non-empty.
Moreover \(K \cap U\) and \(K \cap V\) are open in \(K\)
(intersections of \(K\) with open subsets of \(X\))
and disjoint. Their union is \(K\) since \(K \subseteq X = U \cup V\).
This gives a separation of \(K\), contradicting the connectedness of \(K\) established above.
Hence no separation of \(X\) can exist, and \(X\) must be connected.
The converse fails in general, and the classical counterexample is the topologist's sine curve examined in
the box below. For open subsets of \(\mathbb{R}^n\) the converse does hold. In most optimization problems
and machine-learning models the two concepts can therefore be treated as effectively equivalent, and a "connected" feasible
region is also one where we can "walk" between any two solutions.
Counterexample: The Topologist's Sine Curve
To see that connectedness does not imply path-connectedness, consider the subset of \(\mathbb{R}^2\)
\[
T = \{(x, \sin(1/x)) : x \in (0, 1]\} \cup \bigl(\{0\} \times [-1, 1]\bigr).
\]
This is the graph of \(\sin(1/x)\) on \((0, 1]\), together with the vertical segment \(\{0\} \times [-1, 1]\) on the
\(y\)-axis. As \(x \to 0^+\), the graph oscillates between \(-1\) and \(+1\) infinitely often, "accumulating" onto the
entire vertical segment.
\(T\) is connected. The graph piece \(S = \{(x, \sin(1/x)) : x \in (0, 1]\}\) is path-connected
(parametrize by \(x\)), hence connected by the theorem that
path-connected spaces are connected.
A direct computation shows that the closure of \(S\) in \(\mathbb{R}^2\) is exactly \(T\). Every point
\((0, y_0) \in \{0\} \times [-1, 1]\) is the limit of \((x_n, \sin(1/x_n))\) for a suitable sequence \(x_n \to 0^+\)
with \(\sin(1/x_n) = y_0\). Since the closure of a connected set is connected (established in the
components-partition proof above),
\(T\) is connected.
\(T\) is not path-connected. Intuitively, any continuous path from a point on the vertical segment
(for example, the origin) to a point on the graph (for example, \((1, \sin 1)\)) must pass near \(x = 0\), where the
oscillation of \(\sin(1/x)\) forces the path to traverse the full vertical range \([-1, 1]\) arbitrarily close to the
segment. Continuity at the endpoint on the segment cannot survive this, so no such path exists.
The topologist's sine curve shows that path-connectedness is strictly stronger than connectedness. The pathological
behavior comes from the lack of local path-connectedness near the \(y\)-axis. Once we additionally assume "locally
path-connected" (which holds for open subsets of \(\mathbb{R}^n\), manifolds, and CW-complexes), the two notions
coincide. This example will reappear when we generalize these ideas to arbitrary topological spaces.
Insight: Path-Connectedness in Loss Landscapes
In deep learning we operate in the parameter space \(\mathbb{R}^n\), which is path-connected. This
vital structural property implies that there are no topological barriers (like "holes" or separate components)
preventing an optimizer from theoretically moving between any two points in the weight space.
The research into Mode Connectivity further suggests that the set of "good" solutions (local minima
with low loss) often forms a path-connected structure. This allows different neural network models to be
linearly or non-linearly interpolated along a low-loss path, implying that optimization is not just
about finding isolated points but
about navigating a continuous manifold of high-performing parameters.
References
-
Garipov, T., Izmailov, P., Podoprikhin, D., Vetrov, D. P., & Wilson, A. G. (2018).
"Loss surfaces, mode connectivity, and fast ensembling of DNNs."
In Advances in Neural Information Processing Systems (NeurIPS).
[arXiv:1802.10026]
Looking Ahead: Toward Manifolds
Connectedness and path-connectedness are essential for manifold theory. A manifold is typically defined as a space that
locally looks like \(\mathbb{R}^n\) (together with Hausdorff and second-countability conditions). Most manifolds in
analysis and geometry are studied one connected component at a time, so connectedness plays a structural role. Many
theorems assume the manifold is connected to avoid component-wise bookkeeping. On manifolds, paths become smooth
curves, and the study of shortest paths leads to geodesics, which are central to differential geometry and to modern ML
methods such as manifold learning.