PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q1(a)

Theory of Computation · 2 marks

Open in the Padhaiko app

Topic: Sets, Functions & Relations

Question

Define equivalence and partial-equivalence relation.

Solution

Equivalence Relation Definition and Properties: A binary relation on a set is an equivalence relation if and only if it satisfies three fundamental properties for all :

  1. Reflexivity: .
  2. Symmetry: .
  3. Transitivity: .

Example: The relation of congruence modulo on the integers , defined by iff , is an equivalence relation because every number is congruent to itself, congruence is bidirectional, and modular differences chain transitively.

Partial-Equivalence Relation (PER) Definition: A binary relation on a set is a partial-equivalence relation (PER) if it is symmetric and transitive, but not necessarily reflexive:

  1. Symmetry: .
  2. Transitivity: .

For a partial-equivalence relation, an element is related to itself () if and only if there exists some such that . Consequently, forms an ordinary equivalence relation on the restricted domain .

Example: On , define . Here, is not related to itself, so reflexivity fails on , but symmetry and transitivity hold everywhere.

Answer:

An equivalence relation is reflexive, symmetric, and transitive (e.g., congruence modulo ). A partial-equivalence relation (PER) is symmetric and transitive without requiring reflexivity for all elements of the underlying set.

All past exam questions for Theory of Computation