An equivalence relation is a relation which "looks like" ordinary equality of numbers, but which may hold between other kinds of objects. Here are three familiar properties of equality of real numbers:
1. Every number is equal to itself: for all
.
2. Equalities can be "reversed": If and
, then
.
3. You can "chain" equalities together: If and
and
, then
.
These three properties are captured in the axioms for an equivalence relation.
Definition. An equivalence
relation on a set X is a relation on X such that:
1. for all
. (The relation is reflexive.)
2. If , then
. (The relation is symmetric.)
3. If and
, then
. (The relation is transitive.)
Example. Show that the less-than relation on the set of real numbers is not an equivalence
relation. What about the relation
? For no real number x is it true that
, so reflexivity never holds.
If x and y are real numbers and , it is false that
. For example,
is true, but
is false.
It is true that if and
, then
. Thus,
is transitive.
Suppose instead I consider less-than-or-equal-to, the relation on
.
Reflexivity now holds, since for any it is true that
. Transitivity holds just as before.
However, symmetry still doesn't hold: , but
. Thus,
is not an equivalence relation.
Example. (a) Is the relation whose graph is drawn below an equivalence relation?
(b) Is the relation whose graph is drawn below an equivalence relation?
(c) Is the relation whose graph is drawn below an equivalence relation?
(a) The relation is not an equivalence relation. is not in the relation, so the relation is not
reflexive.
(b) is in the relation, but
is not. Therefore, the relation is not symmetric, so
it's not an equivalence relation.
(c) This relation is reflexive and symmetric. However, and
are in the relation, but
is not. The relation is not transitive, and therefore
it's not an equivalence relation.
Example. A relation is defined on by
Check each axiom for an equivalence relation. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.
but
, and
. Hence,
and the
relation is not reflexive.
Suppose . Then
, so
. Hence,
. The relation is symmetric.
, because
and
.
, because
and
.
However, , as I showed above. Hence, the
relation is not transitive.
Example. Define a relation on
by
Check each axiom for an equivalence relation. If the axioms holds, prove it. If the axiom does not hold, give a specific counterexample.
For all ,
Therefore, for all x, and
is reflexive.
Suppose . This means that
. By commutativity of addition,
. Hence,
. Therefore,
is symmetric.
Transitivity does not hold.
However, , because
Therefore, and
do not imply
.
Example. A relation is defined on by
Check each axiom for an equivalence relation. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.
In words, the definition says two pairs are related if either their first components are equal or their second components are equal.
, because the first components are
both a and hence equal.
Suppose . Then either
or
. In the first case, if
, then
,
because their first components are equal:
implies
. In the second case,
if
, then
, because their second components are
equal:
implies
.
, because their first components
are equal. And
, because their
second components are equal. But
, because neither their first nor
their second components are equal.
Example. Define a relation on by
if and only if
is divisible by 3.
Check each axiom for an equivalence relation. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.
For example, , since
, and 24 is divisible by 3. And
, since
, and -9 is divisible by 3.
However, , since
, and 34 is
not divisible by 3.
If x is an integer, is divisible by 3.
Therefore,
for all
, and
is reflexive.
Suppose x and y are integers. If , then
is divisible by 3. Say
, where
. Now
Therefore, is divisible by 3, so
. Hence,
is symmetric.
You might be wondering how I knew to start with " ". I reasoned
backwards on scratch paper this way.
To prove symmetry, I had to show that if , then
.
By the definition of , that's the same as
showing: If
is divisible by 3, then
is divisible by 3.
If being divisible by 3 is going to force
to be divisible by 3, there's probably be some
connection involving 3,
, and
.
As in many proofs, you often reach a point where you need to play around with the stuff you have. You don't know in advance what will work, and there isn't a step-by-step method for finding out. You have to experiment.
So you think: "3?" " ?" "
?" You might
try various ways of combining the expressions ... and maybe you
realize that
and
(notice the 3's!), and then:
Since the "then" part of what I want to prove involves , I'll solve the last equation for
:
And there's the equation I started with.
Now suppose x, y, and z are integers. Assume and
. This means that
is divisible by 3, and
is divisible by 3. I'll express these as equations:
I want to show that is divisible by 3. My proof
looks like this so far, with the assumptions at the top and the
conclusion at the bottom.
How can I get from and
to
? Make what you've got look like what you
want. What I have involves x, y, and z, but what I want seems to
involve only x and z. It looks like I want to get rid of the y's. How
can I do that? One way is to solve the second equation for y:
Then plug into the first:
I look at my target equation . Make what you've got look like what you
want. I need
on the left side, so I'll just
do algebra to force it to happen:
The left side is what I want ( ), but I need
on the right ... oh, just factor
out 3:
I'll plug this derivation into the proof outline above:
This is a complete proof of transitivity, though some people might
prefer more words. Thus, is an equivalence
relation.
Notice that if you were presented with this proof without any of the scratchwork or backward reasoning, it might look a little mysterious: You can see each step is correct, but you might wonder how anyone would think of doing those things in that order. This is an unfortunate consequence of the way math is often presented: After the building is finished, the scaffolding is removed, and you may then wonder how the builders managed to get the materials up to the roof!
The lesson here is that you should not look at a finished proof and assume that the person who wrote it had a flash of genius and then wrote the thing down from start to finish. While that can happen, more often proofs involve messing around and attempts that don't work and lots of scratch paper!
Equivalence relations give rise to partitions. As a real-world example, consider a deck of playing cards. It is divided into 4 suits: spades, hearts, diamonds, and clubs. Define two cards in the deck to be equivalent if they belong to the same suit. This is an equivalence relation. Every card in the deck belongs to one and only one suit, which is the set of all cards in the same suit as the given card.
In general, if is an equivalence relation on a set
X and
, the
equivalence class of x consists of all the elements of X which
are equivalent to x. In the previous example, the suits are the
equivalence classes.
Definition. Let X be a set. A partition of X is a collection of subsets of X such that:
1. .
2. If and
, then
.
(The subsets
are pairwise
disjoint.)
Thus, the elements of a partition are like the pieces of a jigsaw puzzle:
Example. Why don't the following sets
partition the set of integers ?
(a)
(b)
(a) Every integer is in one of these sets, but the two sets overlap
(at 0).
(b) The sets don't overlap, but -1 is not contained in either
set.
Example. Prove: If X is a set and S is a
subset of X, then is a partition of X.
If , then either
or
. In the second case,
. Thus, every element of X is either in S
or in
.
If , then
and
, which is a
contradiction. Hence, S and
are disjoint.
Therefore, is a partition of X.
Here is how equivalence relations are related to partitions.
Theorem. Let X be a set. An equivalence
relation on X gives rise to a partition of X
into equivalence classes. Conversely, a
partition of X gives rise to an equivalence relation on X whose
equivalence classes are exactly the elements of the partition.
Proof. Suppose is an equivalence relation on X. If
, let
Thus, is the equivalence class of x. Now
, so
. Clearly,
.
Now some of the 's may be identical; throw out the
duplicates. This means that I have
's where
, and Y is a
subset of X --- and if
and
, then
. Since I've
just thrown out duplicates, I still have
. I will have a
partition if I show that the remaining
's don't intersect.
Suppose and
, but
. I'll show
that this gives a contradiction. By definition,
and
, so by symmetry and
transitivity,
.
Now I'll show . I'll show each is
contained in the other. Suppose
. Then
, but
, so
, and
.
This shows . But the argument clearly
works the other way around, so
. Hence,
.
Since I threw out all the duplicates earlier, this is a
contradiction. Hence, there is no such z, which means . This means that the
's for
partition X.
Conversely, suppose is a
partition of X. Define a relation on X by saying
if and only if
for some
.
If , then
for some i because
--- to be in the union means
you're in one of the sets in the union. Now x is in the same
as itself ---
--- so
. It's reflexive.
If , then
for some i. Obviously,
, so
. It's symmetric.
Finally, if and
, then
and
for some i
and j. Now
, but this can only
happen if
. Then
, so
.
It's transitive, and hence it's an equivalence relation.
The equivalence classes of are exactly the
's, by construction.
Example. Suppose . Consider the following
partition of X:
What is the equivalence relation defined by this partition?
The equivalence relation defined by this partition is: for all
, and
In other words, 1, 4, and 5 are equivalence to each other, 2 and 6
are equivalent, and 3 is only equivalent to itself.
Example. Consider the relation on defined by
if and only if
--- that is, if
is an integer.
Check each axiom for an equivalence relation. If the axioms holds, prove it. If the axiom does not hold, give a specific counterexample.
Let . Then
. Therefore,
, and
is reflexive.
Suppose , so
. Since the negative of an integer
is an integer,
. Hence,
, and
is symmetric.
Suppose and
. Then
and
. But the sum of integers is an
integer, so
Therefore, , and
is transitive. Thus,
is an equivalence relation.
Here's a typical equivalence class for :
A little thought shows that all the equivalence classes look like
like one: All real numbers with the same "decimal part".
Each class will contain one element --- 0.3942 in the case of the
class above --- in the interval . Therefore, the set of equivalence
classes of
looks like
. Moreover, since
, it's as if this interval had its ends
"glued together":
This is an important use of equivalence relations in mathematics ---
to "glue together" or identify parts of a set to
create a new set.
Example. Let , the x-y plane. Define
to mean that
In words, this means that and
are the same distance from the origin.
Show that this is an equivalence relation, and sketch the partition
of into equivalence classes that it
determines.
Since , it follows that
. Hence, the relation is
reflexive.
Suppose , so
Then
Hence, . Hence, the relation is
symmetric.
Suppose and
. Then
Hence,
Therefore, . Hence, the relation is
transitive. This show that
is an equivalence
relation.
The resulting partition of into equivalence
classes consists of circles centered at the origin. The origin is in
an equivalence class by itself.
Notice that the axioms for a partition are satisfied: Every point in
the plane lies in one of the circles, and no point lies in two of the
circles.
Example. An equivalence relation is defined on
the set by:
List the elements of the equivalence classes of .
Two numbers are in the same class if they differ by a multiple of 3. So the equivalence classes are:
Copyright 2019 by Bruce Ikenaga