Equivalence Relations

Due to math content, this page has special requirements (including JavaScript) for full functionality.
With your current viewing scenario, it is not appearing and behaving as it is supposed to!
Please visit Dr. Carol J.V. Fisher's Homepage to learn what this site has to offer.
Watch the "Welcome" video to get started—hope to see you back here soon!

Dr. Carol J.V. Fisher's Homepage

For this exercise, you need ♥ INTERNET EXPLORER 6.0 and above, with MathPlayer installed.♥

EQUIVALENCE RELATIONS

Jump right to the exercises!

DEFINITION (partition)
A partition of a set S is a collection of non-overlapping subsets of S that, together, make up all of S .

A partition of a set S

EXAMPLE:
Let S={1 ,2,3,4 ,5} .
Then, the sets {1 ,2,3} and {4 ,5} form a partition of S .
The sets {1 ,5} and {2 ,3,4} form a different partition of S .
The sets {1} and {3} and {2,4,5} form a different partition of S.

One of the most important ways in math to create a partition of a set is by using an equivalence relation,
which is the subject of this section.

Given a set S , we first need a way to talk about members of the set being related to each other.
The symbol ∼ is used for "is related to" .
The sentence x∼y is read as "x is related to y" .

The concept is best illustrated with some examples:

Let S be the set of all people, and let x and y be members of S .
Define:    x∼y    if and only if    x and y have the same sex

Suppose that Carol and Julia are female, and Rick and Karl are male. Then:
Carol ∼ Julia    (read as Carol is related to Julia ; this is true since both are female)
Carol ≁ Karl    (read as Carol is not related to Karl )
Rick ∼ Karl
Let S={0 ,1,2,3 ,...} .
For x and y in S , define:    x∼y    if and only if    x and y have the same remainder upon division by 3
Then:
5∼8    (both have remainder 2 when divided by 3 )
3∼12    (both have remainder 0 when divided by 3 )
1∼10    (both have remainder 1 when divided by 3 )
Let S be the set of all ordered pairs of positive integers.
For (a,b) and (c,d) in S , define:    (a,b) ∼(c,d)    if and only if    ad=bc
Then:
(1,3) ∼(2,6)    (since 1⋅6= 3⋅2 )
(2,5) ∼(4,10)    (since 2⋅10= 5⋅4 )
(This concept is very familiar to you; it's just being cast into an unfamiliar setting.
Hint—think about fractions!)

Now, we are in a position to define an equivalence relation:

DEFINITION (equivalence relation)
Let S be a set.
Let x , y , and z be arbitrary members of S .
Then, ∼ is an equivalence relation on S if it satisfies the following properties:

(REFLEXIVE property): x∼x
(every member is related to itself)
(SYMMETRY property): if x∼y , then y∼x
(if one member is related to another, then the other is related to the one)
(TRANSITIVE property): if x∼y and y∼z , then x∼z
(if one is related to another, and this other is related to a third, then the first is related to the third)

EXAMPLES:

(1) Let S be the set of all people, and let x and y be members of S .
Define: x∼y if and only if x and y have the same sex
Then, ∼ is an equivalence relation on S , as follows:

reflexivity: every person has the same sex as his/her self
symmetry: if a person has the same sex as another person, then the other person has the same sex as the first
transitivity: if person #1 has the same sex as person #2, and person #2 has the same sex as person #3, then person #1 has the same sex as person #3

(2) Let S={0 ,1,2,3 ,...} .
For x and y in S , define: x∼y if and only if x and y have the same remainder upon division by 3
Then, ∼ is an equivalence relation on S , as follows:

reflexivity: every number has the same remainder upon division by 3 as itself
symmetry: if a number has the same remainder upon division by 3 as another, then the other has the same remainder upon division by 3 as the first
transitivity: if a number has the same remainder upon division by 3 as another, and this other has the same remainder upon division by 3 as a third, then the first number has the same remainder upon division by 3 as the third

(3) Let S={0 ,1,2,3 ,...} .
For x and y in S , define: x∼y if and only if x<y
Then, ∼ is not an equivalence relation on S .
It fails both reflexivity (since x is not less than x ) and symmetry (if x is less than y , then y is not less than x ).

Once you select a member of a set which has an equivalence relation on it,
you often want to study all the members which are related to it.
This leads us to:

DEFINITION (equivalence class)
Let ∼ be an equivalence relation on a set S .
Let x be a member of S .
The equivalence class determined by x is the set of all members of S that are related to x .

Here is one key reason why equivalence relations are so important:

The equivalence classes of a set always form a PARTITION of the set.

For Example (1) above, there are only two equivalence classes: males and females.

For Example (2) above, there are three equivalence classes:

{0,3 ,6,...}	(numbers that are divisible by 3; that is, the remainder is 0 )
{1,4 ,7,...}	(numbers that leave a remainder of 1 upon division by 3 )
{2,5 ,8,...}	(numbers that leave a remainder of 2 upon division by 3 )

Congruence is an equivalence relation on the set of all geometric figures.
Let G1 , G2 , and G3 be geometric figures.
Then:
Reflexivity: G1 ≅G 1 (every geometric figure is congruent to itself)
Symmetry: if G1 ≅G 2 , then G2 ≅G 1
Transitivity: if G1 ≅G 2 and G2 ≅G 3 , then G1 ≅G 3

On this exercise, you will not key in your answers.
However, you can check to see if your answer is correct.