Equivalence Relation

Equivalence Relation

A binary relation tex:$$ \sim $$ is said to be an equivalence relation if the following three statements hold:

  • For all tex:$$ a $$, tex:$$ a \sim a $$,
  • tex:$$ a \sim b $$ if and only if tex:$$ b \sim a $$,
  • If tex:$$ a \sim b $$ and tex:$$ b \sim c $$, it follows that tex:$$ a \sim c $$.

Given tex:$$ n $$ objects which are related via an equivalence relation, it is possible to partition the objects into groups where all objects within a group are related and two objects from different groups are not related. These groups are called equivalence classes.

Examples

  • The relationship between people defined by "is the same age as",
  • The relationship tex:$$ a/b \sim c/d $$ if tex:$$ ad = bc $$ defines all rational numbers which are equal; for example, 1/2, 2/4, 3/6, etc.
  • The Landau symbol tex:$$ f = \Theta(g) $$ defines an equivalence relation.

References