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 and be the following subsets of the plane:

and

is an integer

(a) Show that is an equivalence relation on the real line and . Describe the equivalence classes of .

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

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

(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 , this is the set we've been calling in previous problems. And so an equivalence relation lives in , as can be seen from the definition of .

Reflexivity is established by the fact that , and so simply means is true for all . Recognizing this as a real number axiom, we take for granted its veracity.

Symmetry: by definition, with . We wish to show that , and this would mean . Rearranging this in turn suggests that , or . Now is also an integer by closure of the ring operation "addition" (), and so . Thus, and are in .

Transitivity. Picking elements , we want to show . Again we will resort to the definitions. That the first point is in suggests with , and the second that with . Substituting we get , with by closure of the ring structure of integers. Thus, .

To show the inclusion , recast as and . Obviously , and also includes any subset of , too.

Having picked an , the equivalence classes can be described by . 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 , or, in other words, if we index by . Thus, .

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

Transitivity. First notice that each and all equivalence relations are transitive. So now pick points . These points are in all equivalence relations because they are in the intersection. But then the point is in all equivalence relations as well. Therefore it will find its way in the intersection , and is transitive.

(c)

The set is an equivalence relation, by (b) above. contains because the elements of are in all equivalence relations by the definition of intersection. Also, contains the set by reflexivity. Then by symmetry, contains . There are additional elements that are included by transitivity: pick two points with . This last statement suggests , but must be greater than zero because of the restriction of , so . These elements obtained by transitivity indicate that points of the set are in . By symmetry again, . We should try applying transitivity on , to make sure we're not missing any elements of . Pick another two points , with . These elements cannot be in because they lie outside . One checks this covers all transitivity possibilities.

Summarizing: .

The equivalence classes: for and , each equivalence class has as its single element. belong to an equivalence class. Elements belong to a 3-member equivalence class, .