## Equivalence Relation

An equivalence relation on a set is a Subset of , i.e., a collection of ordered pairs of elements of , satisfying certain properties. Write '' to mean is an element of , and we say  is related to ,'' then the properties are

1. Reflexive: for all ,

2. Symmetric: Implies for all

3. Transitive: and imply for all ,

where these three properties are completely independent. Other notations are often used to indicate a relation, e.g., or .