### Archive

Archive for February 2nd, 2009

## 1.3 Exercise 5

This problem was fun but a bit long.  In it we see how we can construct a couple uncommon equivalence relations on the real line.  Having done this, one should have the grasp to create monsters of any kind.

"Let $S$ and $S'$ be the following subsets of the plane:

$S = \{(x, y)\verb| | \vert \verb| | y = x+1$ and $0

$S' = \{(x, y)\verb| | \vert \verb| | y - x$ is an integer$\}$

(a) Show that $S'$ is an equivalence relation on the real line and $S' \supset S$.  Describe the equivalence classes of $S'$.

(b) Show that given any collection of equivalence relations on a set $A$, their intersection is an equivalence relation on $A$.

(c) Describe the equivalence relation $T$ on the real line that is the intersection of all equivalence relations on the real line that contain $S$.  Describe the equivalence classes of $T$."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 28.)

-----------

SOLUTION

(a)

First, notice that the equivalence relation is on $\mathbb{R}$, this is the set we've been calling $A$ in previous problems.  And so an equivalence relation lives in $\mathbb{R} \times \mathbb{R}$, as can be seen from the definition of $S'$.

Reflexivity is established by the fact that $S' \supset \{(x, y) \verb| | \vert \verb| | y - x = 0 \}$, and so $\forall x \verb| | (x, x) \in C$ simply means $x - x = 0$ is true for all $x$.  Recognizing this as a real number axiom, we take for granted its veracity.

Symmetry: by definition, $S' \supset \{(x, y) \verb| | \vert \verb| | y - x = K \}$ with $K \in \mathbb{Z}$.  We wish to show that $(y, x) \in S'$, and this would mean $x - y = K$.  Rearranging this in turn suggests that $-(y - x) = K$, or $y - x = -K$.  Now $-K$ is also an integer by closure of the ring operation "addition" ($-K + K = 0 \verb| | \vert \verb| | K, 0 \in \mathbb{Z} \Rightarrow -K \in \mathbb{Z}$), and so $S' \supset \{(x, y) \verb| | \vert \verb| | y - x = -K \}$.  Thus, $(x, y)$ and $(y, x)$ are in $S'$.

Transitivity.  Picking elements $(x, y), (y, z) \in S'$, we want to show $(x, z) \in S'$.  Again we will resort  to the definitions.  That the first point is in $S'$ suggests $y - x = K_1$ with $K_1 \in \mathbb{Z}$, and the second that $z - y = K_2 \Rightarrow y = z - K_2$ with $K_2 \in \mathbb{Z}$. Substituting we get $z - K_2 - x = K_1 \Rightarrow z - x = K_1 + K_2 = K_3$, with $K_3 \in \mathbb{Z}$ by closure of the ring structure of integers.  Thus, $(x, z) \in S'$.

To show the inclusion $S' \supset S$, recast $S$ as $\{(x, y) \verb| | \vert \verb| | y - x = 1$ and $0 < x < 2\}$.  Obviously $S' \supset \{(x, y) \verb| | \vert \verb| | y - x = 1\}$, and $S'$ also includes any subset of $\{(x, y) \verb| | \vert \verb| | y - x = 1\}$, too.

Having picked an $i \in [0, 1)$, the equivalence classes can be described by $E_i = \{e \verb| | \vert \verb| | e = i + z, z \in \mathbb{Z}\}$.  The set of integers is an equivalence class, e.g.

(b)

Reflexivity is established by the fact that the reflexive elements belong to all equivalence relations on $A$, or, in other words, $\forall x \in A, (x, x) \in C_i$ if we index by $i$.  Thus, $\forall x \in A, (x, x) \in \cap C_i$.

Symmetry.  First, notice that any particular equivalence relation of $A$ is symmetric. So now pick any element in the intersection of equivalence relations, $(x, y) \in \cap C_i$.  Such a point belongs to all equivalence relations because it is in the intersection.  Its symmetric point $(y, x)$ is also in all equivalence relations, and therefore it is in the intersection. We can conclude $(y, x) \in \cap C_i$, or $\cap C_i$ is symmetric.

Transitivity. First notice that each and all equivalence relations are transitive.  So now pick points $(x, y), (y, z) \in \cap C_i$.  These points are in all equivalence relations because they are in the intersection.  But then the point $(x, z)$ is in all equivalence relations as well.  Therefore it will find its way in the intersection $(x, z) \in \cap C_i$, and $\cap C_i$ is transitive.

(c)

The set $T$ is an equivalence relation, by (b) above.  $T$ contains $S$ because the elements of $S$ are in all equivalence relations  by the definition of intersection.  Also, $T$ contains the set $\{(x, y) \verb| | \vert \verb| | y-x = 0\}$ by reflexivity.  Then by symmetry, $T$ contains $\{(x, y) \verb| | \vert \verb| | y = x -1, 1 < x < 3\}$.  There are additional elements that are included by transitivity: pick two points $(x, x+1), (x+1, x+2) \in S$ with $0 < x+1 < 2$.  This last statement suggests $-1 < x < 1$, but $x$ must be greater than zero because of the restriction of $S$, so $0 < x < 1$.  These elements obtained by transitivity indicate that points of the set $S^* = \{(x, y) \verb| | \vert \verb| | y = x+2, 0 are in $T$.  By symmetry again, $\{(x, y) \verb| | \vert \verb| | y = x-2, 2.  We should try applying transitivity on $S^*$, to make sure we're not missing any elements of $T$.  Pick another two points $(x, x+2), (x+2, x+4) \in S^*$, with $0.  These elements cannot be in $T$ because they lie outside $0 < x < 1$.  One checks this covers all transitivity possibilities.

Summarizing: $T = \{(x, y) \verb| | \vert \verb| | y - x = 0\} \cup \{(x, y) \verb| | \vert \verb| | y = x + 1, 0 < x < 2\} \cup \{(x, y) \verb| | \vert \verb| | y = x - 1, 1 < x < 3\} \cup \{(x, y) \verb| | \vert \verb| | y = x + 2, 0 < x < 1\} \cup \{(x, y) \verb| | \vert \verb| | y = x - 2, 2 < x < 3\}$.

The equivalence classes: for $-\infty < x \leq 0$ and $3 \leq x < \infty$, each equivalence class has $x$ as its single element. $\{1, 2\}$ belong to an equivalence class. Elements $0 < x < 1$ belong to a 3-member equivalence class, $\{x, x+1, x+2\}$.

Categories: