A vital component found in every branch of mathematics is the idea of equivalence. And the ability to group objects together that are similar is the idea behind equivalence relations.
Jenn, Founder Calcworkshop®, 15+ Years Experience (Licensed & Certified Teacher)
What Is An Equivalence Relation
Formally, a relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive. This means that if a relation embodies these three properties, it is considered an equivalence relation and helps us group similar elements or objects.
So, an equivalence relation is a relationship on a set and is typically denoted by ∼ (tilde), with the following three properties:
Equivalence Relation Properties
For example, suppose a relation R in the set of integers is defined as R = {(a,b) | a – b is an integer}. Let’s determine whether the relation is an equivalence relation.
How To Prove An Equivalence Relation
To prove an equivalence relation, you must show reflexivity, symmetry, and transitivity, so using our example above, we can say:
Reflexivity: Since a – a = 0 and 0 is an integer, this shows that (a, a) is in the relation; thus, proving R is reflexive.
Symmetry: If a – b is an integer, then b – a is also an integer. This shows that if (a, b) is in the relation, then (b, a) is also in the relation; hence, R is symmetric.
Transitivity: If a – b is an integer and b – c is an integer, then (a – b) + (b – c) = a – c is an integer; consequently, R is transitive.
Therefore, since R is reflexive, symmetric, and transitive, we have shown that R is an equivalence relation.
Congruence Modulo
Now, one of the most useful equivalence relations is congruence modulo m, where m is an integer greater than 1.
We studied modular arithmetic in our Number Theory section, but let’s briefly review here.
Congruence Modulo Definition
Alright, assume m is an integer greater than 1. Let’s prove the following relation is an equivalence relation on the set of integers
Proof Mod M
Equivalence Class
Additionally, a unique subset of equivalence relations is equivalence classes.
Let R be an equivalence relation on set A. The set of all elements related to an element a of A is called the equivalence class of a. In other words, if R is an equivalence relation on A, the equivalence class of the element a is
Equivalence Class Notation
The Fundamental Theorem of Equivalence Relations nicely sums up these ideas.
Partition Of A Set
And this brings us to an essential idea about partitions of sets. If you recall from our study of sets, a partition is a pairwise disjoint nonempty set, and if P is a partition and R is an equivalence relation, then we have the following properties:
Partition Equivalence Properties
This means that every time you have a partition, you have an equivalence relation and vice versa because each element is related to all the elements in its partition (or block) and only those elements.
Equivalence Relation Classes Properties
For example, what are the sets in the partition of the integers arising from congruence modulo four?
Congruence Classes Mod 4
Hence, these congruence classes form a partition!
Together, we will prove equivalence relations by showing a relation is reflexive, symmetric, and transitive, and apply this knowledge to congruence modulo, equivalence classes, and partitions.
Let’s get to it!
Video Tutorial w/ Full Lesson & Detailed Examples
1 hr 31 min
Get access to all the courses and over 450 HD videos with your subscription
Monthly and Yearly Plans Available
Still wondering if CalcWorkshop is right for you?
Take a Tour and find out how a membership can take the struggle out of learning math.