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 .

REFERENCES:

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 18, 1990.

Stewart, I. and Tall, D. The Foundations of Mathematics. Oxford, England: Oxford University Press, 1977.