krit.club logo

Relations and Functions - Types of Relations: Reflexive, Symmetric, Transitive and Equivalence

Grade 12ICSE

Review the key concepts, formulae, and examples before starting your quiz.

🔑Concepts

•

A relation RR on a set AA is a subset of the Cartesian product A×AA \times A. Visually, if we represent elements of AA as points, a relation can be seen as a directed graph where an arrow from aa to bb indicates that the pair (a,b)∈R(a, b) \in R.

•

A relation RR is Reflexive if every element a∈Aa \in A is related to itself, meaning (a,a)∈R(a, a) \in R for all a∈Aa \in A. In a visual diagram, this is represented by every vertex having a 'self-loop' (an arrow starting and ending at the same point).

•

A relation RR is Symmetric if for every pair (a,b)∈R(a, b) \in R, the reverse pair (b,a)(b, a) is also in RR. Visually, if there is an arrow pointing from aa to bb, there must be a corresponding arrow pointing back from bb to aa.

•

A relation RR is Transitive if whenever (a,b)∈R(a, b) \in R and (b,c)∈R(b, c) \in R, then (a,c)∈R(a, c) \in R. This means if you can travel from aa to cc via bb, there must be a direct 'shortcut' path from aa to cc. Visually, this forms triangles in the directed graph of the relation.

•

An Equivalence Relation is one that is simultaneously Reflexive, Symmetric, and Transitive. Such a relation partitions the set AA into disjoint subsets called Equivalence Classes. Visually, the set is divided into separate 'clusters' where every element in a cluster is connected to every other element in that same cluster.

•

Equivalence Class: For an equivalence relation RR on set AA, the equivalence class of an element a∈Aa \in A, denoted by [a][a], is the set of all elements x∈Ax \in A such that (x,a)∈R(x, a) \in R. Visually, an equivalence class is one complete 'island' or partition of the set where all members are mutually related.

•

The Identity Relation IA={(a,a):a∈A}I_A = \{(a, a) : a \in A\} is the smallest reflexive relation and is always an equivalence relation. The Universal Relation R=A×AR = A \times A is the largest possible relation on AA and is also always an equivalence relation.

📐Formulae

Reflexive condition: ∀a∈A,(a,a)∈R\forall a \in A, (a, a) \in R

Symmetric condition: (a,b)∈R  ⟹  (b,a)∈R(a, b) \in R \implies (b, a) \in R

Transitive condition: (a,b)∈R and (b,c)∈R  ⟹  (a,c)∈R(a, b) \in R \text{ and } (b, c) \in R \implies (a, c) \in R

Number of relations on a set with nn elements: 2n22^{n^2}

Number of reflexive relations on a set with nn elements: 2n2−n2^{n^2 - n}

Equivalence class of aa: [a]={x∈A:(x,a)∈R}[a] = \{x \in A : (x, a) \in R\}

💡Examples

Problem 1:

Let TT be the set of all triangles in a plane. Let RR be a relation in TT defined as R={(T1,T2):T1≅T2}R = \{(T_1, T_2) : T_1 \cong T_2\} (where ≅\cong denotes congruence). Prove that RR is an equivalence relation.

Solution:

  1. Reflexivity: Every triangle T1T_1 is congruent to itself (T1≅T1T_1 \cong T_1). Therefore, (T1,T1)∈R(T_1, T_1) \in R for all T1∈TT_1 \in T. RR is reflexive.
  2. Symmetry: If (T1,T2)∈R(T_1, T_2) \in R, then T1≅T2T_1 \cong T_2. By the property of congruence, T2≅T1T_2 \cong T_1. Therefore, (T2,T1)∈R(T_2, T_1) \in R. RR is symmetric.
  3. Transitivity: If (T1,T2)∈R(T_1, T_2) \in R and (T2,T3)∈R(T_2, T_3) \in R, then T1≅T2T_1 \cong T_2 and T2≅T3T_2 \cong T_3. This implies T1≅T3T_1 \cong T_3. Therefore, (T1,T3)∈R(T_1, T_3) \in R. RR is transitive. Since RR is reflexive, symmetric, and transitive, it is an equivalence relation.

Explanation:

To prove a relation is an equivalence relation, we must verify all three fundamental properties (reflexive, symmetric, and transitive) using the given logical definition of the relation.

Problem 2:

Check if the relation RR on the set of integers Z\mathbb{Z} defined by R={(a,b):a−b is divisible by 3}R = \{(a, b) : a - b \text{ is divisible by } 3\} is an equivalence relation.

Solution:

  1. Reflexive: For any a∈Za \in \mathbb{Z}, a−a=0a - a = 0. Since 00 is divisible by 33, (a,a)∈R(a, a) \in R. Thus, RR is reflexive.
  2. Symmetric: Let (a,b)∈R(a, b) \in R. Then a−b=3ka - b = 3k for some integer kk. Then b−a=−(a−b)=−3k=3(−k)b - a = -(a - b) = -3k = 3(-k). Since −k-k is an integer, b−ab - a is divisible by 33, so (b,a)∈R(b, a) \in R. Thus, RR is symmetric.
  3. Transitive: Let (a,b)∈R(a, b) \in R and (b,c)∈R(b, c) \in R. Then a−b=3ka - b = 3k and b−c=3mb - c = 3m for integers k,mk, m. Adding these: (a−b)+(b−c)=3k+3m  ⟹  a−c=3(k+m)(a - b) + (b - c) = 3k + 3m \implies a - c = 3(k + m). Since k+mk + m is an integer, a−ca - c is divisible by 33, so (a,c)∈R(a, c) \in R. Thus, RR is transitive. Since all three hold, RR is an equivalence relation.

Explanation:

This demonstrates an equivalence relation over an infinite set (Integers). We use algebraic manipulation to show that if the condition holds for specific pairs, it must hold for the reflexive and transitive requirements.