### Archive

Posts Tagged ‘Equivalence Relations’

## 1.3 Exercise 5

February 2nd, 2009 2 comments

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:

## 1.3 Exercise 4

January 30th, 2009 No comments

This problem was very interesting to me because it demonstrates the nifty idea that you can create an injective function out of any surjective function (hence a bijective function) by grouping members of the domain into equivalence classes -- or, in other words, by "partitioning" the domain appropriately.  Or, from a more poetical point-of-view, by "collecting-doubled-up-string," "string" being the function.  Perhaps what I mean will be clearer by working out the problem.

"Let $f : A \rightarrow B$ be a surjective function.  Let us define a relation on $A$ by setting $a_0 \sim a_1$ if

$f(a_0) = f(a_1)$.

(a) Show that this is an equivalence relation.

(b) Let $A^*$ be the set of equivalence classes.  Show there is a bijective correspondence of $A^*$ with $B$."

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

-------------

SOLUTION

(a)

Reflexivity, symmetry, and transitivity of the equivalence relation in this case follow from the reflexive, symmetric, and transitive properties of equality.

Reflexivity:  Pick any $a \in A$, and apply $f$.  By the reflexive property of equality, $f(a) = f(a)$.  So $a \sim a$$\forall a \in A$.

Symmetry: Pick $(a_0, a_1) \in A \times A$ so that $f(a_0) = f(a_1)$, or $a_0 \sim a_1$.  By the symmetric property of equality, $f(a_1) = f(a_0)$, or $a_1 \sim a_0$.

Transitivity:  Pick $(a_0, a_1), (a_1, a_2) \in A \times A$, such that $f(a_0) = f(a_1)$, or $a_0 \sim a_1$ and $f(a_1) = f(a_2)$, or $a_1 \sim a_2$.  By the transitive property of equality, it is easy to see that $f(a_0) = f(a_2)$, or $a_0 \sim a_2$.

(b)

Pick an equivalence class, $E \in A^*$.  Such $E = \{y \vert y \sim x\}$ ($y, x \in A$), so $f$ of any element $y \in E$ is $f(x) \in B$.  In other words, $f(E) = f(x)$, and such $f(x)$ is unique to that equivalence class  (having grouped all elements of $A$ that mapped to that $f(x)$ together and because equivalence classes are disjoint).  This shows injectivity.  Surjectivity is established by the fact that $f$ is surjective and all elements of $A$ belong to an equivalence class, so $f(E_i)$ sweeps all of $B$.

Categories:

## 1.3 Exercise 3

January 29th, 2009 No comments

"Here is a "proof" that every relation $C$ that is both symmetric and transitive is also reflexive: "Since $C$ is symmetric, $aCb$ implies $bCa$.  Since $C$ is transitive, $aCb$ and $bCa$ together imply $aCa$, as desired.''  Find the flaw in this argument."

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

--------

SOLUTION

Rephrasing, the argument suggests that every relation that is symmetric and transitive is reflexive, and hence is an equivalence relation.  The problem is that reflexivity must be true for all elements in the base set $A$.  Here's a counter-example that disproves the statement.

Suppose $A = \{1, 2, 3, 4, 5\}$, and let's assume we know the relation $C$ consists of the elements $\{(2, 3), (4, 5)\}$.  By following the argument, $C$ includes elements $\{(3, 2), (5, 4)\}$ by symmetry, and $\{(2, 2), (3, 3), (4, 4), (5, 5)\}$ by transitivity.  But the reflexive property of equivalence relations would require that $\{(1, 1)\}$ be in the relation, which, as we've seen, is not obtainable by symmetry and transitivity alone.  Despite being symmetric and transitive, $C$ is not, in this case, "totally" reflexive, and therefore it is not an equivalence relation.

Categories:

## 1.3 Exercise 2

January 28th, 2009 No comments

This problem is interesting because it shows that restrictions of equivalence relations are also equivalence relations.

"Let  $C$ be a relation on a set $A$.  If  $A_0 \subset A$, define the restriction of  $C$ to  $A_0$ to be the relation  $C \cap (A_0 \times A_0)$. Show that the restriction of an equivalence relation is an equivalence relation."

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

----------

SOLUTION

Reflexivity: Notice that  $A_0 \times A_0$ will naturally contain those reflexive elements that belong to it (pick a fixed element $a \in A_0$, then $(a, a) \in A_0 \times A_0$).  By hypothesis of reflexivity of  $C$, such are included in  $C$ too, because  $C$ contains all reflexive elements in  $A \times A$. It follows that such a point is also in the restriction.

Symmetry:  We want to show that, picking any point in the restriction, its symmetric point is also in the restriction.  First, notice that for any (fixed) element  $(a, b) \in A_0 \times A_0$, its symmetric partner  $(b, a) \in A_0 \times A_0$ because of the set's square-symmetry.  Now pick  $(x, y) \in C \cap A_0 \times A_0$.  Of course, such  $(x, y) \in A_0 \times A_0$, and also  $(x, y) \in C$ by the definition of intersection.  Since  $(x, y) \in C$, there exists a point  $(y, x) \in C$ by hypothesis of its symmetry in  $A \times A$.   $(y, x)$ is also a point in  $A_0 \times A_0$ by its square-symmetry.  Therefore  $(y, x) \in C \cap A_0 \times A_0$ and the restriction is symmetric.

Transitivity:  First, notice that transitivity holds in  $A_0 \times A_0$, because it contains all elements that belong to  $A_0$ in combination with themselves.  Thus, having chosen any three (fixed) elements  $a, b, c \in A_0$, specifically these elements  $(a, b), (b, c), (a, c)$ are in  $A_0 \times A_0$.  Now pick two elements  $(x, y), (y, z) \in C \cap A_0 \times A_0$.  There is an element  $(x, z) \in C$ by hypothesis of its transitivity in  $A \times A$.  Such exists in  $A_0 \times A_0$ as well by our aforementioned observation.  Since the element is in both  $C$ and  $A_0 \times A_0$, it is in their intersection and therefore in the restriction of  $C$.

Categories:

## 1.3 Exercise 1

January 27th, 2009 No comments

An easy problem that introduces equivalence relations in somewhat a different scenario than the usual "clock arithmetic" ($\mathbb{Z}$ modulo $n$) context.

"Define two points $(x_0, y_0)$ and $(x_1, y_1)$ of the plane to be equivalent if $y_0 - x_0^2 = y_1 - x_1^2$.  Check that this is an equivalence relation and describe the equivalence classes."

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

------------

SOLUTION

Reflexivity, symmetry, and transitivity of the relation $C$ is but a re-statement of reflexive, symmetric, and transitive properties of equality.

Reflexivity: $\forall x \in A, xCx$ means $\forall (x,y) \in \mathbb{R} \times \mathbb{R}, y + x^2 = y + x^2 \Rightarrow 0 = 0$ is a statement of the identity property of equality.

Symmetry: $xCy \Rightarrow yCx$ means $y_0 - x_0^2 = y_1 - x_1^2 \Rightarrow y_1 - x_1^2 = y_0 - x_0^2$.  This is a statement of symmetry of equality.

Transitivity: $xCy$ and $yCz \Rightarrow xCz$ means $y_0 - x_0^2 = y_1 - x_1^2$  and $y_1 - x_1^2 = y_2 - x_2^2 \Rightarrow y_0 - x_0^2 = y_2 - x_2^2$, which is clear by transitivity of equality.

The family of standard parabolas $y = x^2 + K$ are the equivalence classes ($y - x^2 = K$ describes the parabolic level curves, and hence all points on a particular parabola are in a particular equivalence class).  The statement $y_0 - x_0^2 = y_1 - x_1^2$ is a consequence of transitivity of equality on $K$.

Categories: