# Relations and Equivalent Relations

# Relation

A relation is any subset of a Cartesian product. For instance, a subset of , called a “binary relation from to ,” is a collection of ordered pairs with first components from and second components from , and, in particular, a subset of is called a “relation on .” For a binary relation , one often writes to mean that is in

# 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