The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Equivalence Relations

Date: 10/02/98 at 00:24:35
From: shawn
Subject: Equivalence relations

Let X = {people in the world} and let R be a relation on the set X 
such that (x,y) is in R if either x and y live in a state that starts 
with the same letter or x and y live outside of the United States. For 
example, two people would be related if one lived in Michigan and the 
other lived in Massachusetts and two other people would be related if 
one lived in England and the other lived in Paris.

(a) Show that this relation is an equivalence relation
(b) List and describe the equivalence classes that would describe 
    this relation.

The problem is that I can not figure out the set or how this would be 
written in symbols. Any help would be appreciated. Thank you.

Date: 10/02/98 at 17:36:55
From: Doctor Anthony
Subject: Re: Equivalence relations

There are three criteria for an equivalence relation:

  (1) Reflexive   a R a

  (2) Symmetric   a R b -> b R a

  (3) Transitive  a R b  and  b R c  ->  a R c

Clearly if you take the relation as defined above, it satisfies these 
three criteria. I'll do the first one as an example. 

To show that a R a, you need to show that (a,a) is in R. Can you say 
that one person lives in a state that starts with the same letter as 
the state that the person lives in or lives outside of the United 
States? Yes. Now you need to show that if (a,b) is in R, then (b,a) is 
in R, and if (a,b),(b,c) are in R, (a,c) is in R.

An equivalence class of the element a is the set of all elements 
equivalent to a under the relation R.

One equivalence class is everyone not living in the United States.

The other equivalence classes are:

Individuals living in states with a name starting with the letter A, 
the letter B, the letter C, and so on.

Note that equivalence classes will partition the set X. No individual 
can be in two equivalence classes.

- Doctor Anthony, The Math Forum   
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.