👁 Preview — Study, Practice and Revise are open; mock tests and the rest of the syllabus unlock on subscription. Unlock all · ₹4,999
← Back to Algebra
Study mode

Equivalence Relation

Study Practice Revise 🔒 Test
Learning objective
Understand equivalence relations and their properties including equivalence classes.

Understanding Equivalence Relations

An equivalence relation is a fundamental concept in algebra and set theory that helps us classify elements of a set into distinct groups where elements are "equivalent" under some criteria. Formally, a relation \( R \) on a set \( A \) is called an equivalence relation if it satisfies three key properties:

  • Reflexive: Every element is related to itself.
    Mathematically, \( \forall a \in A, (a, a) \in R \).
  • Symmetric: If an element \( a \) is related to \( b \), then \( b \) is related to \( a \).
    Mathematically, \( \forall a, b \in A, (a, b) \in R \Rightarrow (b, a) \in R \).
  • Transitive: If \( a \) is related to \( b \), and \( b \) is related to \( c \), then \( a \) is related to \( c \).
    Mathematically, \( \forall a, b, c \in A, (a, b) \in R \text{ and } (b, c) \in R \Rightarrow (a, c) \in R \).

When these three properties hold, the relation partitions the set \( A \) into disjoint subsets called equivalence classes. Each equivalence class contains elements that are all equivalent to each other under the relation \( R \).

Visualizing Equivalence Classes

Consider the set \( A = {1, 2, 3, 4, 5, 6} \) and define a relation \( R \) such that two numbers are related if they have the same parity (both even or both odd). Then:

  • Equivalence class of odd numbers: \( {1, 3, 5} \)
  • Equivalence class of even numbers: \( {2, 4, 6} \)

These classes partition \( A \) into two subsets where each element is equivalent to others in its class.

graph TD  A1[1] --- A3[3]  A3 --- A5[5]  B2[2] --- B4[4]  B4 --- B6[6]

Equivalence Relation vs Other Relations

Not all relations are equivalence relations. For example, the "less than" relation \( < \) on numbers is:

  • Not reflexive (since \( a < a \) is false)
  • Not symmetric (if \( a < b \), then \( b < a \) is false)
  • Transitive (if \( a < b \) and \( b < c \), then \( a < c \))

Thus, \( < \) is not an equivalence relation.

Connection to Set Theory Concepts

Equivalence relations are closely related to the concept of partition of a set. A partition divides a set into mutually exclusive and collectively exhaustive subsets. Each equivalence class forms one such subset.

Moreover, the idea of equivalence of sets is often defined by the existence of a bijection (one-to-one and onto function) between them, which implies they have the same cardinality (number of elements). This is a form of equivalence relation on the class of all sets.

Important Set Properties Relevant to Equivalence Relations

  • Null set as subset: The null set \( \emptyset \) is a subset of every set.
  • Set inclusion: Every set is a subset of itself.
  • Power set cardinality: If a set has \( n \) elements, its power set has \( 2^n \) elements.

These properties often appear in problems involving equivalence relations and set operations.

Common Mistakes to Avoid

  • Confusing equivalence relation with partial order (which requires antisymmetry instead of symmetry).
  • Assuming all relations are equivalence relations without checking all three properties.
  • Mixing up equality of sets with equivalence of sets (equal sets have exactly the same elements; equivalent sets have the same cardinality but not necessarily the same elements).

Exam Tips

  • Always verify reflexivity, symmetry, and transitivity separately when asked to prove or disprove equivalence relations.
  • Use examples and counterexamples to illustrate your points clearly.
  • Remember the connection between equivalence relations and partitions to answer questions on equivalence classes.
  • For cardinality problems, recall the formula for power sets and use the inclusion-exclusion principle for unions and intersections.

Worked Examples

Example 1: Checking if a Relation is an Equivalence Relation (Easy)

Let \( A = {1, 2, 3} \). Define a relation \( R \) on \( A \) by \( R = {(1,1), (2,2), (3,3), (1,2), (2,1)} \). Is \( R \) an equivalence relation?

Solution:

  • Reflexive: Check if \( (a,a) \in R \) for all \( a \in A \).
    Given \( (1,1), (2,2), (3,3) \in R \), so reflexive holds.
  • Symmetric: For every \( (a,b) \in R \), check if \( (b,a) \in R \).
    \( (1,2) \in R \), and \( (2,1) \in R \), so symmetric holds.
  • Transitive: For \( (1,2) \in R \) and \( (2,1) \in R \), check if \( (1,1) \in R \). It is.
    For other pairs, no violation found.
    Hence, transitive holds.

Since all three properties hold, \( R \) is an equivalence relation.

Example 2: Equivalence Classes of Congruence Modulo 3 (Medium)

Define a relation \( R \) on integers \( \mathbb{Z} \) by \( aRb \) if \( a \equiv b \pmod{3} \). Find the equivalence classes.

Solution:

Two integers are related if their difference is divisible by 3.

Equivalence classes are:

  • Class of 0: \( [0] = {\ldots, -6, -3, 0, 3, 6, 9, \ldots} \)
  • Class of 1: \( [1] = {\ldots, -5, -2, 1, 4, 7, 10, \ldots} \)
  • Class of 2: \( [2] = {\ldots, -4, -1, 2, 5, 8, 11, \ldots} \)

These classes partition \( \mathbb{Z} \) into three disjoint sets.

Example 3: Power Set Cardinality (Easy)

If a set \( S = {a, b, c, d} \), find the number of subsets of \( S \).

Solution:

Number of elements \( n = 4 \). Number of subsets = \( 2^n = 2^4 = 16 \).

Example 4: Finding \( n(A \cap B) \) Given \( n(A), n(B), n(A \cup B) \) (Medium)

Given \( n(A) = 37 \), \( n(B) = 25 \), and \( n(A \cup B) = 50 \), find \( n(A \cap B) \).

Solution:

Using the formula:

\[ n(A \cup B) = n(A) + n(B) - n(A \cap B) \]

Substitute values:

\[ 50 = 37 + 25 - n(A \cap B) \]\[ n(A \cap B) = 37 + 25 - 50 = 12 \]

Example 5: Maximum Number of Elements in \( A \cap B \) (Hard)

Given \( n(A) = 4 \) and \( n(B) = 3 \), find the maximum possible value of \( n(A \cap B) \).

Solution:

The intersection cannot have more elements than the smaller set.

So, maximum \( n(A \cap B) = \min(n(A), n(B)) = 3 \).

Example 6: Find \( (A \times B) \cap (B \times A) \) (Medium)

Let \( A = {1, 2, 5, 6} \) and \( B = {1, 2, 3} \). Find \( (A \times B) \cap (B \times A) \).

Solution:

Cartesian products:

  • \( A \times B = {(a,b) : a \in A, b \in B} \)
  • \( B \times A = {(b,a) : b \in B, a \in A} \)

For an ordered pair to be in both, it must be of the form \( (x,y) \) where \( x \in A \cap B \) and \( y \in A \cap B \) and \( (x,y) = (y,x) \), which implies \( x = y \).

Find \( A \cap B = {1, 2} \).

So, \( (A \times B) \cap (B \times A) = {(1,1), (2,2)} \).

Formula Bank

  • Reflexive property: \( \forall a \in A, (a,a) \in R \)
  • Symmetric property: \( (a,b) \in R \Rightarrow (b,a) \in R \)
  • Transitive property: \( (a,b) \in R \text{ and } (b,c) \in R \Rightarrow (a,c) \in R \)
  • Power set cardinality: If \( |S| = n \), then \( |\mathcal{P}(S)| = 2^n \)
  • Union and intersection cardinality: \( n(A \cup B) = n(A) + n(B) - n(A \cap B) \)
  • Maximum intersection size: \( \max n(A \cap B) = \min(n(A), n(B)) \)
  • Symmetric difference: \( A \oplus B = (A - B) \cup (B - A) \)
Curated videos per subtopic
Top YouTube explainers, AI-ranked for your exam and language. Unlocks with subscription.
Unlock

Try Practice next.

Progress tracking is paywalled — subscribe to mark subtopics as understood and save your streak.

Go to practice →
Ask a doubt
Equivalence Relation · 10 free messages
Ask me anything about this subtopic. You have 10 free messages this session — chat history isn't saved in preview.