EQUIVALENCE RELATIONS

Suppose students in a class are getting together in groups to do an activity.
The teacher wants to make sure of two things:

From a mathematical viewpoint, what has been created is a partition of the class:

DEFINITION partition
A partition of a set [beautiful math coming... please be patient] $\,S\,$ is a collection of non-overlapping subsets of $\,S\,$ that, together,
make up all of $\,S\,$.

More precisely, ‘make up all of $\,S\,$’ means that the union of the subsets is $\,S\,$.

A partition of a set $\,S\,$

EXAMPLES:
Let [beautiful math coming... please be patient] $\,S=\{1,2,3,4,5\}\,$.

The sets $\,\{1,2,3\}\,$ and $\,\{4,5\}\,$ form a partition of $\,S\,$:
they don't overlap, and, together, they make up all of $\,S\,$.
The sets [beautiful math coming... please be patient] $\,\{1,5\}\,$ and $\,\{2,3,4\}\,$ form a different partition of $\,S\,$.
The sets [beautiful math coming... please be patient] $\,\{1\}\,$ and $\,\{3\}\,$ and $\,\{2,4,5\}\,$ form a different partition of $\,S\,$.
The sets [beautiful math coming... please be patient] $\,\{1,2\}\,$ and $\,\{3,4\}\,$ do not form a partition of $\,S\,$;
together, they don't make up all of $\,S\,$.
The sets [beautiful math coming... please be patient] $\,\{1,2,3\}\,$ and $\,\{3,4,5\}\,$ do not form a partition of $\,S\,$;
they overlap—the number $\,3\,$ is in more than one of the subsets.
The sets [beautiful math coming... please be patient] $\,\{1,2\}\,$ and $\,\{2,3\}\,$ and $\,\{4,5\}\,$ do not form a partition of $\,S\,$;
they overlap—the number $\,2\,$ is in more than one of the subsets.
BEING ‘RELATED TO EACH OTHER’ IN A SET

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 [beautiful math coming... please be patient] $\,S\,$, we first need a way to talk about members of the set being related to each other.
The symbol ‘$\,\sim\,$’ is used for ‘is related to’.
The sentence ‘$\,x\sim y\,$’ is read as ‘$\,x\,$ is related to $\,y\,$’.

The concept is best illustrated with some examples:

EQUIVALENCE RELATIONS

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

DEFINITION equivalence relation
Let [beautiful math coming... please be patient] $\,S\,$ be a set.
Then, $\,\sim \,$ is an equivalence relation on $\,S\,$   if and only if
the following properties are satisfied for all members $\,x\,$, $\,y\,$ and $\,z\,$ in $\,S\,$:
  • REFLEXIVE property:   $\,x\sim x\,$
    (every member is related to itself)
  • SYMMETRY property:   if $\,x\sim y\,$, then $\,y\sim x\,$
    (if one member is related to another, then the other is related to the one)
  • TRANSITIVE property:   if $\,x\sim y\,$ and $\,y\sim z\,$, then $\,x\sim z\,$
    (if one is related to another, and this other is related to a third,
    then the first is related to the third)
EXAMPLE:   an equivalence relation on the set of all people
(1)   Let [beautiful math coming... please be patient] $\,S\,$ be the set of all people, and let $\,x\,$ and $\,y\,$ be members of $\,S\,$ .
Define:   $\,x\sim y\,$   if and only if   $\,x\,$ and $\,y\,$ have the same sex
Then, $\,\sim \,$ is an equivalence relation on $\,S\,$, as follows:
EXAMPLE:   an equivalence relation on the set of all nonnegative integers
(2)   Let [beautiful math coming... please be patient] $\,S=\{0,1,2,3,\ldots\}\,$.
For $\,x\,$ and $\,y\,$ in $\,S\,$, define:
$\,x\sim y\,$   if and only if   $\,x\,$ and $\,y\,$ have the same remainder upon division by $\,3\,$
Then, $\,\sim \,$ is an equivalence relation on $\,S\,$, as follows:
EXAMPLE:   NOT an equivalence relation
(3)   Let [beautiful math coming... please be patient] $\,S=\{0,1,2,3,\ldots\}\,$.
For $\,x\,$ and $\,y\,$ in $\,S\,$, define:
$\,x\sim y\,$   if and only if   $\,x\lt y\,$
Then, $\,\sim \,$ 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\,$).
EQUIVALENCE CLASSES

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 [beautiful math coming... please be patient] $\,\sim \,$ 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:

As a final example, congruence is an equivalence relation on the set of all geometric figures.
Let [beautiful math coming... please be patient] $\,G_1\,$, $\,G_2\,$, and $\,G_3\,$ be geometric figures. Then:

Master the ideas from this section
by practicing the exercise at the bottom of this page.

When you're done practicing, move on to:
Triangle Congruence


On this exercise, you will not key in your answer.
However, you can check to see if your answer is correct.
PROBLEM TYPES:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19  
AVAILABLE MASTERED IN PROGRESS

(MAX is 19; there are 19 different problem types.)