# connected components equivalence relation

Prove that the relation $x \sim y$ iff $y$ is an element of the connected component of $x$ is an equivalence relation.

This question is confusing me, do I simply go about showing the relation is reflexive, symmetric, and transitive? I don't really see how to do this for this question. Any suggestions or hints are appreciated!

HINT: Perhaps the easiest way to prove that this is an equivalence relation is to show that the connected components of a space $X$ partition $X$: they are pairwise disjoint, and their union is $X$. It will then follow immediately from the relationship between equivalence relations and partitions that $x\sim y$ is an equivalence relation: it’s the equivalence relation induced on $X$ by the partition of $X$ into connected components.

If you need a review of the relationship between equivalence relations and partitions, I discussed it at some length in this answer.

• I don't understand one direction of the implication. Take the partition of the real numbers induced by the sign of $Sin(x)$. Then $\pi/2 \sim 5 \pi/ 2$ but they're not in the same connected component. – alancalvitti Feb 22 '13 at 20:24
• @alancalvitti: Why on earth would you look at that partition? It has nothing to do with the question (or my answer). – Brian M. Scott Feb 22 '13 at 20:25
• Isn't it an example of equivalence relation to share the same sign? – alancalvitti Feb 22 '13 at 20:32
• @alancalvitti: So what? Why are you worried about completely irrelevant equivalence relations? – Brian M. Scott Feb 22 '13 at 20:33
• Am I misreading OP's statement? "relation x∼y iff y is an element of the connected component of x is an equivalence relation". Doesn't it have to hold for all equivalences? – alancalvitti Feb 22 '13 at 20:42

So define $x \sim y$ iff $y$ is in the connected component of $x$, where the connected component of $x$ is the largest connected subset of $X$ that contains $x$.

To see this is well-defined, we can define for fixed $x$ the collection $\mathcal{C}_x = \left\{C \subset X \mid C \mbox { connected and } x \in X \right\}$, and note that any 2 members of $\mathcal{C}_x$ intersect (in $x$) and so their union $C(x) = \cup \mathcal{C_x}$ is also connected, by a standard theorem on connected subsets, and clearly $C \subset C(x)$ for all $C \in \mathcal{C}_x$, as $C$ is one of the sets we take the union of to construct $C(x)$, so $C(x)$ is the component of $x$ (by construction it is the maximal connected subset that contains $x$).

So $x \sim y$ iff $y \in C(x)$.

Clearly for all $x$, $x \sim x$, as $x$ is in $C(x)$ by definition.

Suppose $y \sim x$ so $y \in C(x)$. Then $C(x)$ is a connected subset of $X$ that contains $y$, and $C(y)$ is the maximal such subset, so $(x \in) C(x) \subset C(y)$, which means that $x \sim y$. This shows symmetry. Note that by reversing the roles of $x$ and $y$ we also get $C(y) \subset C(x)$ and so $x \sim y$ iff $C(x) = C(y)$ as sets.

The last reformulation clearly shows transitivity as well: $x \sim y$ and $y \sim z$, then $C(x) = C(y) = C(z)$, so $x \sim z$.

This shows that thus is indeed an equivalence relation.

Yes. Whenever you are asked to verify that a certain mathematical object (in this case a relation) has a specific property (in this case, an equivalence relation), you really just need to verify that the definition of this property hold for this object.

In this case, you simply need to show that the relation is reflexive, symmetric and transitive.

Of course, sometimes it is diffcult to verify the definitions, or it might be long and tedious. And there are sometimes ways to go around this issue. For example, you might know that if the object (or a related object) have a certain property, you could conclude what you want. For example, sometimes showing that something is connected is complicated, and it's easier to show that it is path connected which would imply this.

As Brian suggests in his answer, if you show that the collection of connected component is a partition then you can conclude that the relation you are after is an equivalence relation. This is because equivalence relations and partitions are strongly connected mathematically.

Let's call our space $S$. For any $x\in S,$ we can define $C_x$, the connected component of $x$, to be the $\subseteq$-greatest connected subset $A$ of $S$ such that $x\in A.$ Put another way, $C_x$ is the union of all connected subsets of $S$ containing $x$ as an element--we can show that such a union is connected in various ways.

Then $x\sim y$ if and only if $y\in C_x$. Clearly, $x\in C_x$, so $x\sim x$.

If $x\sim y$, then $C_x$ is a connected set containing $y$, so $C_x\subseteq C_y$ (since $C_y$ is the $\subseteq$-greatest subset of $S$ containing $y$), and so $x\in C_y$, meaning $y\sim x$.

If $x\sim y$ and $y\sim z$, then $y\in C_x$ and $z\in C_y$. As with the symmetry proof, we then have $C_x\subseteq C_y$ and $C_y\subseteq C_z$, so it follows that $x\in C_z$. But then $C_z$ is a connected set containing $x$, so $C_z\subseteq C_x$, and so $z\in C_x$, meaning $x\sim z$.

When I look at this question, I get confused. Nothing like putting the 'horse before the cart'! But if you wipe from your mind the concept of connected components, something more interesting can be examined. So, yes, for educational reasons, I think it is justified to answer a modified question.

Definition: Let $X$ be a topological space. If $x$ and $y$ are two points in $X$, we say that $x \text{ is connected to } y$ if there exists a connected subset of $X$ that contains both these points. We denote this relationship symbolically by writing $x \, \sim_\gamma \, y$.

Proposition 2: The relation $x \, \sim_\gamma \, y$ is an equivalence relation on $X$.
Proof
Since the singleton space is always connected, the relation is reflexive. Since conjunction is commutative, the relation is symmetric. To show it is transitive, let $x,y \in A$, $y,z \in B$ with both $A$ and $B$ connected subspaces of $X$. Observe that the point $y$ belongs to both the sets $A$ and $B$. Transitivity, $x \, \sim_\gamma \, z$, will be established once we show that $C = A \cup B$ is connected.

Recall that the following is equivalent to saying that a topological space $G$ is connected:

$\quad$ All continuous functions from $G$ to $\{0,1\}$ are constant, $\qquad$ $\qquad$ $\qquad$$\qquad$ $\text{(1)}$
$\quad$ where $\{0,1\}$ is the two-point space endowed with the discrete topology.

To now show that $A \cup B$ is connected, you can check this out. $\qquad \blacksquare$

Now this is exciting! We now know that we can partition $X$ and if two points belong to the same block a connected subspace of $X$ can be found that contains both of these points. In fact, starting with any point $x$, it is easy to see that the union of all connected subspaces of $X$ that contain $x$ is precisely the block in the partition to which $x$ belongs.

With this approach we have partitioned $X$ but we have not yet shown that the blocks are connected.

Exercise 1: Using $\text{(1)}$, show that each block of the partition is connected (Hint: start with any point $x$ in the block).

So now we can call these blocks the connected components of $X$.

From the arguments above, no connected component can be a proper subset of a connected set.

The above can be abstracted into a general set theory argument.

Proposition: Let $(U_i)_{\, i \in I}$ a family of nonempty subsets of $X$ the union of which is all of $X$. There exists a unique partition $\hat I$ of $I$ so that with

$\quad \hat U_\iota = \bigcup_{i \in \iota} \, U_i \text{, } \iota \in \hat I$

the following conditions are satisfied:

$\tag 1 \text{For all } i\in I \text{ there exists } \iota \in \hat I \text{ with } U_i\subset \hat U_\iota$
$\tag 2 \text{For all } \mu \in \hat I \text{, } \nu \in \hat I \text{ with } \mu \ne \nu \text{, } \hat U_\mu \cap \hat U_\nu = \emptyset$
$\tag 3 \text{For all } i, j \in I \text{, if } U_i \cap U_j \ne \emptyset \text{ then there exists an } \iota \in \hat I \text{ with } U_i \cup U_j \subset \hat U_\iota$

Proof
Define the relation $i \sim j$ on $I$ if, letting ${U_k}_1 = U_i$ and ${U_k}_n = U_j$, there exists a finite $n \text{-}$chain

$\tag 4 ({U_k}_1, {U_k}_2,{U_k}_3,\dots,{U_k}_{n-1},{U_k}_n)$

with ${U_k}_m \cap {U_k}_{m+1} \ne \emptyset$ for $1 \le m \le n - 1$. It is easy to see that $\sim$ is an equivalence relation and the rest of argument follows a natural path. $\qquad \blacksquare$

Note that it is certainly possible that all the $U_i$ get combined together into the set $X$ itself.

I felt compelled to add this when I looked at A union represented as a disjoint union: weaker than choice?. The AOC is not necessary here, but of course the partition on $X$ is completely different.