Equivalence Relation

In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent (with respect to the equivalence relation) if and only if they are elements of the same cell. The intersection of any two different cells is empty; the union of all the cells equals the original set.

Notation
Although various notations are used throughout the literature to denote that two elements a and bof a set are equivalent with respect to an equivalence relation R, the most common are "a ~ b" and "a ≡ b", which are used when R is the obvious relation being referenced, and variations of "a ~_Rb", "a ≡_R b", or "aRb"


Definition

A given binary relation ~ on a set A is said to be an equivalence relation if and only if it is reflexive, symmetric and transitive. Equivalently, for all a, b and c in A:

• a ~ a. (Reflexivity)
• if a ~ b then b ~ a. (Symmetry)
• if a ~ b and b ~ c then a ~ c. (Transitivity)

A together with the relation ~ is called a setoid. The equivalence class of a under ~, denoted [a], is defined as .

Reflexivity follows from symmetry and transitivity if for every element a∈A, there exists another element b∈A such that a~b holds. However, reflexivity does not follow from symmetry and transitivity alone. For example, let A be the set of integers, and let two elements of A be related if they are both even numbers. This relation is clearly symmetric and transitive, but in view of the existence of odd numbers, it is not reflexive.

On the other hand, let A be the set of integers, and let two elements of A be related if their difference is even. This is an equivalence relation, which partitions the integers into two equivalence classes, the even and odd integers.

Examples

The following are all equivalence relations:

• "Is equal to" on the set of real numbers
• "Has the same birthday as" on the set of all people.
• "Is similar to" on the set of all triangles.
• "Is congruent to" on the set of all triangles.
• "Is congruent to, modulo n" on the integers.
• "Has the same image under a function" on the elements of the domain of the function.
  • "Has the same absolute value" on the set of real numbers
  • "Has the same cosine" on the set of all angles.
• "Is parallel to" on the set of subspaces of an affine space.

Relations that are not equivalences

• The relation "≥" between real numbers is reflexive and transitive, but not symmetric. For example, 7 ≥ 5 does not imply that 5 ≥ 7. It is, however, a partial order.
• The relation "has a common factor greater than 1 with" between natural numbers greater than 1, is reflexive and symmetric, but not transitive. (Example: The natural numbers 2 and 6 have a common factor greater than 1, and 6 and 3 have a common factor greater than 1, but 2 and 3 do not have a common factor greater than 1).
• The empty relation R on a non-empty set X (i.e. aRb is never true) is vacuously symmetric and transitive, but not reflexive. (If X is also empty then R is reflexive.)
• The relation "is approximately equal to" between real numbers, even if more precisely defined, is not an equivalence relation, because although reflexive and symmetric, it is not transitive, since multiple small changes can accumulate to become a big change. However, if the approximation is defined asymptotically, for example by saying that two functions f and g are approximately equal near some point if the limit of f-g is 0 at that point, then this defines an equivalence relation.
• The relation "is a sibling of" (used to connote pairs of distinct people who have the same parents) on the set of all human beings is not an equivalence relation. Although siblinghood is symmetric (if A is a sibling of B, then B is a sibling of A) and transitive on any 3 distinct people (if A is a sibling of B and C is a sibling of B, then A is a sibling of C, provided A is not C), it is not reflexive (A cannot be a sibling ofA).