The Central Idea
An equivalence relation tells us when two objects should be regarded as the same in some specified sense.
The relation groups the set into equivalence classes.
Every element belongs to exactly one class, and two elements lie in the same class exactly when they are equivalent.
Equivalence therefore turns a set of individual objects into a collection of structural categories.
Relations Revisited
A relation on a set \(A\) is a subset of
\[ A\times A. \]If
\[ (a,b)\in R, \]we may write
\[ aRb. \]An equivalence relation is a relation on \(A\) satisfying three special properties.
The Three Conditions
A relation \(\sim\) on \(A\) is an equivalence relation when it is:
- reflexive;
- symmetric;
- transitive.
All three conditions are required.
Reflexive
A relation is reflexive when every element is related to itself.
\[ \boxed{a\sim a\quad\text{for every }a\in A.} \]If even one element fails to relate to itself, the relation is not reflexive.
Symmetric
A relation is symmetric when reversing a true relation keeps it true.
\[ \boxed{a\sim b\Longrightarrow b\sim a.} \]Equivalence cannot point in only one direction.
Transitive
A relation is transitive when two compatible relation steps combine.
\[ \boxed{ a\sim b\text{ and }b\sim c \Longrightarrow a\sim c. } \]Transitivity makes equivalence propagate through a class.
Example: Equality
Ordinary equality is an equivalence relation.
It is reflexive because
\[ a=a. \]It is symmetric because
\[ a=b\Longrightarrow b=a. \]It is transitive because
\[ a=b\text{ and }b=c\Longrightarrow a=c. \]Equality Produces Singleton Classes
Under ordinary equality, the only object equal to \(a\) is \(a\) itself.
Therefore the equivalence class of \(a\) is
\[ [a]=\{a\}. \]Equality creates the finest possible equivalence classification.
What Is an Equivalence Class?
Let \(\sim\) be an equivalence relation on \(A\).
The equivalence class of \(a\in A\) is
\[ \boxed{ [a]=\{x\in A:x\sim a\}. } \]It contains every element equivalent to \(a\).
The Representative
The element \(a\) used in the notation
\[ [a] \]is called a representative of the class.
A class may have many different representatives.
Any member of the class can represent the entire class.
Equivalent Representatives Give the Same Class
If
\[ a\sim b, \]then
\[ \boxed{[a]=[b]}. \]Equivalent elements do not generate different classes.
They are members of the same block.
Non-Equivalent Representatives Give Disjoint Classes
If
\[ a\not\sim b, \]then their equivalence classes do not overlap:
\[ \boxed{[a]\cap[b]=\varnothing}. \]Two equivalence classes are therefore either identical or disjoint.
Every Element Belongs to Its Own Class
Reflexivity guarantees
\[ a\sim a. \]Therefore
\[ \boxed{a\in[a]}. \]No element is left outside the equivalence-class system.
Equivalence Classes Cover the Set
Because every element belongs to its own class, the union of all equivalence classes is the entire set:
\[ \bigcup_{a\in A}[a]=A. \]Thus equivalence classes completely cover the underlying set.
Equivalence Classes Form a Partition
Equivalence classes are:
- nonempty;
- pairwise disjoint;
- collectively exhaustive.
Therefore they form a partition of \(A\).
\[ \boxed{ \text{equivalence relation} \Longrightarrow \text{partition into equivalence classes} }. \]Partitions Define Equivalence Relations
The connection also works in reverse.
Suppose \(A\) is partitioned into blocks.
Define
\[ a\sim b \]when \(a\) and \(b\) belong to the same block.
This relation is reflexive, symmetric, and transitive.
Equivalence Relations and Partitions Are Two Views of One Structure
An equivalence relation describes which pairs are considered equivalent.
A partition describes the resulting groups.
These are two representations of the same classification structure.
Example: Same Parity
On the integers, define
\[ a\sim b \]when \(a\) and \(b\) have the same parity.
That means both are even or both are odd.
The equivalence classes are
\[ [0]=\{\ldots,-4,-2,0,2,4,\ldots\} \]and
\[ [1]=\{\ldots,-3,-1,1,3,5,\ldots\}. \]Parity Is Reflexive
Every integer has the same parity as itself.
Therefore
\[ a\sim a. \]The relation is reflexive.
Parity Is Symmetric
If \(a\) has the same parity as \(b\), then \(b\) has the same parity as \(a\).
Therefore
\[ a\sim b\Longrightarrow b\sim a. \]Parity Is Transitive
If \(a\) has the same parity as \(b\), and \(b\) has the same parity as \(c\), then \(a\) and \(c\) have the same parity.
Therefore the relation is transitive.
Congruence Modulo \(n\)
A major equivalence relation in discrete mathematics is congruence modulo \(n\).
For a positive integer \(n\), define
\[ a\equiv b\pmod n \]when
\[ n\mid(a-b). \]Equivalently, \(a\) and \(b\) leave the same remainder upon division by \(n\).
Example: Congruence Modulo \(3\)
Modulo \(3\), every integer belongs to one of three equivalence classes.
\[ [0]=\{\ldots,-6,-3,0,3,6,\ldots\}, \] \[ [1]=\{\ldots,-5,-2,1,4,7,\ldots\}, \] \[ [2]=\{\ldots,-4,-1,2,5,8,\ldots\}. \]These classes partition \(\mathbb{Z}\).
Different Representatives, Same Residue Class
Modulo \(3\),
\[ 1\equiv4\equiv7\pmod3. \]Therefore
\[ [1]=[4]=[7]. \]The symbols differ, but they represent the same equivalence class.
Residue Classes
Equivalence classes under congruence modulo \(n\) are called residue classes.
There are exactly \(n\) such classes:
\[ [0],[1],\ldots,[n-1]. \]These will be developed further in the number-theory section.
Example: Same Absolute Value
On the integers, define
\[ a\sim b \]when
\[ |a|=|b|. \]Then
\[ [0]=\{0\}, \]while for \(n>0\),
\[ [n]=\{-n,n\}. \]Example: Same Fractional Value
Ordered integer pairs can represent fractions.
For pairs \((a,b)\) and \((c,d)\) with nonzero second coordinates, define
\[ (a,b)\sim(c,d) \]when
\[ ad=bc. \]Then
\[ (1,2)\sim(2,4)\sim(3,6). \]These different pairs represent the same rational number.
Equivalence Can Identify Different Representations
One important use of equivalence classes is to treat multiple descriptions of the same mathematical object as one class.
Examples include:
- fractions representing the same rational number;
- integers having the same residue modulo \(n\);
- geometric objects related by a chosen symmetry;
- states differing only by irrelevant labels.
Canonical Representatives
Sometimes one representative is chosen as a standard form for an entire class.
Such a choice is called a canonical representative.
For congruence modulo \(5\), the standard representatives are often
\[ 0,1,2,3,4. \]Every integer is equivalent to exactly one of these.
Why Canonical Representatives Help
Canonical representatives provide a consistent way to label classes.
Instead of writing
\[ [17] \]modulo \(5\), we may use
\[ [2] \]because
\[ 17\equiv2\pmod5. \]The Quotient Set
The set of all equivalence classes of \(A\) under \(\sim\) is called the quotient set.
It is written
\[ \boxed{A/{\sim}}. \]Its elements are equivalence classes rather than the original individual elements.
Example: Quotient by Parity
Under same-parity equivalence,
\[ \mathbb{Z}/{\sim} \]contains two elements:
\[ [0] \]and
\[ [1]. \]Thus an infinite set of integers becomes a two-element quotient set.
Example: Quotient Modulo \(4\)
Under congruence modulo \(4\),
\[ \mathbb{Z}/4\mathbb{Z} \]may be represented by
\[ \{[0],[1],[2],[3]\}. \]Each class contains infinitely many integers, but the quotient has only four classes.
Class Size
Equivalence classes do not need to have the same cardinality in every equivalence relation.
For the relation
\[ |a|=|b| \]on \(\mathbb{Z}\),
\[ [0]=\{0\} \]has one element, while
\[ [5]=\{-5,5\} \]has two.
Finite Equivalence Classes
On a finite set, every equivalence class is finite.
For
\[ A=\{1,2,3,4,5,6\}, \]suppose equivalence is defined by having the same remainder modulo \(3\).
The classes are
\[ \{3,6\},\qquad \{1,4\},\qquad \{2,5\}. \]Classifying by an Attribute
Suppose objects have a category label.
Define
\[ x\sim y \]when \(x\) and \(y\) have the same category.
If category assignment is well defined, this is naturally an equivalence relation.
Each category becomes one equivalence class.
Classifying by a Function Value
Let
\[ f:A\to B. \]Define
\[ x\sim y \]when
\[ f(x)=f(y). \]This is an equivalence relation.
Each class contains all inputs sharing the same function value.
Fibers as Equivalence Classes
For a function
\[ f:A\to B, \]the set
\[ f^{-1}(\{b\}) \]contains all inputs mapping to \(b\).
Such sets are often called fibers.
Under the relation \(x\sim y\iff f(x)=f(y)\), the nonempty fibers are the equivalence classes.
Example: Classification by Last Digit
Define integers to be equivalent when they have the same final decimal digit.
Then
\[ 17\sim27\sim107. \]This relation is the same as congruence modulo \(10\).
The quotient has ten classes.
Example: Strings by Length
Let \(\Sigma^*\) be the set of all finite strings over an alphabet \(\Sigma\).
Define
\[ u\sim v \]when
\[ |u|=|v|. \]Strings are equivalent when they have the same length.
Each class consists of all strings of one fixed length.
Example: Sets by Cardinality
In an appropriate collection of finite sets, define
\[ A\sim B \]when
\[ |A|=|B|. \]Then all three-element sets lie in one class, all four-element sets in another, and so on.
A Relation Need Not Be an Equivalence Relation
Many familiar relations fail one or more required properties.
For example,
\[ < \]is not reflexive and not symmetric.
Therefore less-than does not produce equivalence classes.
Example: Less Than Fails Reflexivity
Reflexivity would require
\[ a for every \(a\).This is false.
Therefore \(<\) is not an equivalence relation.
Example: Less Than Fails Symmetry
If
\[ 2<5, \]symmetry would require
\[ 5<2. \]That is false.
Example: “Is a Parent of”
The relation
\[ xRy \]meaning “\(x\) is a parent of \(y\)” is not an equivalence relation.
It is not reflexive and not symmetric.
Parent-child structure is directional rather than equivalence-based.
Example: “Has Met” May Fail Transitivity
Suppose \(A\) has met \(B\), and \(B\) has met \(C\).
It does not follow that \(A\) has met \(C\).
Thus a symmetric relation can still fail transitivity.
Testing Reflexivity on a Finite Set
For a finite set
\[ A=\{a_1,\ldots,a_n\}, \]reflexivity requires every diagonal pair:
\[ (a_1,a_1),\ldots,(a_n,a_n). \]In a relation matrix, every diagonal entry must therefore be \(1\).
Testing Symmetry with Ordered Pairs
For every pair
\[ (a,b)\in R, \]symmetry requires
\[ (b,a)\in R. \]In a relation matrix, symmetry corresponds to
\[ M_{ij}=M_{ji}. \]Testing Transitivity with Chains
For every pair of relation steps
\[ aRb \]and
\[ bRc, \]transitivity requires
\[ aRc. \]On a finite relation, every such two-step chain must be checked.
Equivalence Relations as Graphs
A finite equivalence relation can be represented as a directed graph.
Reflexivity creates a loop at every vertex.
Symmetry creates edges in both directions.
Transitivity forces each equivalence class to behave as a fully connected relation block.
Undirected Picture of an Equivalence Relation
If loops and paired arrow directions are suppressed visually, each equivalence class appears as a connected cluster in which every pair of vertices is equivalent.
Distinct classes have no equivalence edges between them.
Equivalence Matrices Have Block Structure
After arranging equivalent elements next to one another, the relation matrix of a finite equivalence relation can be organized into blocks of \(1\)'s along the diagonal, with \(0\)'s between distinct classes.
This matrix pattern is another representation of the underlying partition.
Example: Two Equivalence Classes
Suppose
\[ A=\{1,2,3,4\} \]is partitioned into
\[ \{1,3\} \]and
\[ \{2,4\}. \]Then
\[ 1\sim3 \]and
\[ 2\sim4, \]while no member of the first block is equivalent to a member of the second.
Class Membership Determines Equivalence
Once the partition is known,
\[ a\sim b \]exactly when
\[ [a]=[b]. \]Equivalence can therefore be tested either through the relation rule or through class membership.
Quotienting Removes Irrelevant Differences
Passing from \(A\) to
\[ A/{\sim} \]intentionally ignores distinctions that the equivalence relation declares irrelevant.
Instead of working with every original object separately, we work with classes of structurally equivalent objects.
Equivalence in State Spaces
Two states may be treated as equivalent when they differ only in details irrelevant to the current problem.
For example, two configurations might be equivalent under a relabeling of identical components.
Grouping equivalent states can reduce the effective size of a state space.
Symmetry and Equivalent Configurations
Suppose two objects are physically indistinguishable.
Swapping their labels may produce a different tuple representation without producing a genuinely different configuration.
An equivalence relation can identify these representations.
Equivalence in Counting
Counting problems often first count labeled or ordered representations and then group together representations that should be regarded as equivalent.
This idea appears in:
- symmetry correction;
- circular arrangements;
- unlabeled partitions;
- graph isomorphism;
- identical-object counting.
Common Error: Assuming Similarity Is Automatically Equivalence
Informal words such as “similar,” “related,” or “close” do not automatically define equivalence relations.
The relation must still be reflexive, symmetric, and transitive.
Common Error: Forgetting Reflexivity
Suppose a relation only links distinct objects that share a property.
If the rule excludes
\[ a\sim a, \]then it cannot be an equivalence relation even if it seems like a classification rule.
Common Error: Checking Symmetry but Not Transitivity
The relation “has met” may be symmetric:
\[ aRb\Longrightarrow bRa. \]But it may fail transitivity.
All three equivalence properties must be checked independently.
Common Error: Treating Representatives as Different Classes
Modulo \(5\),
\[ [2]=[7]=[12]. \]These are not three classes.
They are three names for the same class because
\[ 2\equiv7\equiv12\pmod5. \]Common Error: Allowing Equivalence Classes to Partially Overlap
Two equivalence classes cannot share some elements while remaining different.
If
\[ [a]\cap[b]\ne\varnothing, \]then
\[ \boxed{[a]=[b]}. \]Common Error: Confusing a Class with Its Representative
The representative
\[ a \]is one element.
The equivalence class
\[ [a] \]is a set of elements.
They are different kinds of mathematical objects.
A Reliable Procedure for Testing an Equivalence Relation
- Identify the underlying set.
- Write the relation rule precisely.
- Check reflexivity for every allowed element.
- Check symmetry by reversing a general related pair.
- Check transitivity through a general two-step relation chain.
- If all three hold, determine the equivalence classes.
- Check that the classes are nonempty and disjoint.
- Check that their union covers the entire set.
- Choose convenient representatives when useful.
- Form the quotient set if the problem requires class-level structure.
Example: Full Analysis Modulo \(4\)
Define
\[ a\sim b \]when
\[ a\equiv b\pmod4. \]The relation is reflexive because
\[ 4\mid(a-a). \]It is symmetric because
\[ 4\mid(a-b)\Longrightarrow4\mid(b-a). \]It is transitive because if
\[ 4\mid(a-b) \]and
\[ 4\mid(b-c), \]then
\[ 4\mid[(a-b)+(b-c)]=a-c. \]Therefore congruence modulo \(4\) is an equivalence relation.
Its classes are
\[ \boxed{[0],[1],[2],[3]}. \]Practice 1: Reflexive?
On the integers, define
\[ aRb \]when
\[ a=b. \]Is \(R\) reflexive?
Practice 2: Symmetric?
On the integers, define
\[ aRb \]when
\[ aPractice 3: Same Parity
Are
\[ 8 \]and
\[ 14 \]equivalent under same-parity equivalence?
Practice 4: Modulo \(5\)
Determine whether
\[ 17\equiv2\pmod5. \]Practice 5: Same Class?
Modulo \(4\), are
\[ [3] \]and
\[ [11] \]the same equivalence class?
Practice 6: Class under Absolute Value
Under the relation
\[ a\sim b\iff |a|=|b|, \]find
\[ [7]. \]Practice 7: Partition Check
Does
\[ \big\{ \{1,3\}, \{2,4\} \big\} \]form a partition of
\[ \{1,2,3,4\}? \]Practice 8: Class Overlap
If two equivalence classes share one element, what must be true about the two classes?
Practice 9: Quotient Size
How many equivalence classes does congruence modulo \(6\) produce on \(\mathbb{Z}\)?
Practice 10: Is This an Equivalence Relation?
On people, define
\[ xRy \]when \(x\) and \(y\) have met.
Explain one equivalence property that may fail.
Practice Answers
Practice 1
Yes. Every integer equals itself:
\[ \boxed{a=a}. \]Therefore equality is reflexive.
Practice 2
No. For example,
\[ 2<5 \]but
\[ 5<2 \]is false.
Practice 3
Yes. Both \(8\) and \(14\) are even:
\[ \boxed{8\sim14}. \]Practice 4
Since
\[ 17-2=15 \]and
\[ 5\mid15, \]we have
\[ \boxed{17\equiv2\pmod5}. \]Practice 5
Yes. Since
\[ 11-3=8 \]and
\[ 4\mid8, \]we have
\[ \boxed{[3]=[11]}. \]Practice 6
\[ \boxed{[7]=\{-7,7\}}. \]Practice 7
Yes. The blocks are nonempty, disjoint, and together contain every element of the original set.
Practice 8
They must be the same class:
\[ \boxed{[a]=[b]}. \]Practice 9
Congruence modulo \(6\) produces the six residue classes
\[ [0],[1],[2],[3],[4],[5]. \]Therefore the quotient has
\[ \boxed{6} \]classes.
Practice 10
Transitivity may fail. If \(A\) has met \(B\) and \(B\) has met \(C\), it does not follow that \(A\) has met \(C\).
What to Remember
- An equivalence relation is reflexive, symmetric, and transitive.
- The equivalence class \([a]\) contains all elements equivalent to \(a\).
- Equivalent representatives determine the same class.
- Different equivalence classes are disjoint.
- Equivalence classes partition the underlying set.
- Every partition defines an equivalence relation by same-block membership.
- Congruence modulo \(n\) is a central equivalence relation.
- Residue classes are equivalence classes of integers modulo \(n\).
- The quotient set \(A/{\sim}\) is the set of equivalence classes.
- Equivalence is a tool for ignoring differences that the model declares irrelevant.
The central habit is: first verify reflexivity, symmetry, and transitivity; then think in terms of the resulting partition rather than individual representatives.
Where We Go Next
Equivalence classes identify groups of objects that remain interchangeable under a chosen relation. Many discrete arguments go further by identifying properties that remain unchanged while a system is transformed or evolves.
The next lesson, Structural Invariants, develops these preserved quantities and properties as tools for classification, impossibility proofs, state-space analysis, and discrete reasoning.