• S
    SwaseekhGATE Preparation
General
  • Dashboard
  • Syllabus
  • Questions
  • Aptitude
  • Mock Tests
  • TCS NQT 2026
Account
  • Pricing
  • Contact
  1. GATE CS
  2. PYQs
  3. Discrete Mathematics

Let S be a set of n elements. The number of ordered pairs in the largest and the smallest equivalence relations on S are: A. n and n B. n^2 and n C. n^2 and 0 D. n and 1

GATE 2007 · Discrete Mathematics · Relations · medium

Answer: Largest: n^2 pairs (= S x S); Smallest: n pairs (= identity relation). Answer: B. n^2 and n.

  1. Largest equivalence relation: S x S contains all n^2 ordered pairs. Check: every (a,a) is in S x S (reflexive); (a,b) in S x S implies (b,a) in S x S (symmetric); transitivity holds trivially. So S x S is a valid equivalence relation with n^2 pairs.
  2. Smallest equivalence relation: The identity relation I_S = {(a,a) : a in S} has exactly n pairs. It is reflexive by definition; it is symmetric because the only pairs are self-pairs; it is transitive because (a,a) and (a,a) gives (a,a). Any equivalence relation must at least contain all (a,a) by reflexivity, so I_S is the minimum with n pairs.