Number of Ordered Pairs

Let S be a set of nelements. The number of ordered pairs in the largest and the smallest equivalence relations on S are:


n and n


n2 and n


n2 and 0


n and 1


A relation is said to be an equivalence relation, when it satisfies 3 properties mainly:

  • Reflexive
  • Symmetric
  • Transitive

Largest equivalence relation on set S is of size n2 , this is the case when relation all the npossible pairs.

Smallest equivalence relation on set S is of size n , this is the case when relation has only reflexive element pairs.

Example: S = (1,3,5)
Largest ordered set are s x s = { (1,1) (1,3) (1,5) (3,1) (3,3) (3,5) (5,1) (5,3) (5,5) } which are 9 which equal to 3^2 = n^2
Smallest ordered set are { (1,1)( 3,3)(5,5)} which are 3 and equals to n. number of elements.

aditya @adityakumar100
22 Aug 2017 10:20 pm

Nice explanation...thanks


sanjay @sanjayrao
4 Sep 2017 12:17 am

What about empty relation ,is it an equivalence relation or not??could anyone explain with an example

deepak @nd2025
4 Sep 2017 01:02 am

In reflexive relation, all diagonal element have to present And   

empty set has no diagonal element;

hence empty relation is not an equivalence relation.

Habib Mohammad Khan @habibkhan
4 Sep 2017 01:18 am

Empty relation is not reflexive hence not an equivalence relation..

saurabh @emmazampa
20 Oct 2017 08:42 am

Can you make videos of this lecture?