Equivalence Relation
From Math Images
This is a Helper Page for:


Graph Theory 
Contents 
An equivalence relation, ~, is a relation between members,a, b, and c, of a set X such that it meets the following criteria.^{[1]}
 Reflexivity: a ~ a.
 Symmetry: If a ~ b, then b ~ a.
 Transitivity: If a ~ b and b ~ c, then a ~ c.
"Equivalent" is related to the word "equal". In fact, one of the first concepts of arithmetic—equality of two numbers—is an equivalence relation. For three numbers x, y, and z:
 x = x.
 If x = y, then y = x.
 If x = y and y = z, then x = z.
However, equality is but one example of an equivalence relation. The equivalence relation is a more general idea in mathematics that was developed based on the properties of equality.
But what exactly is a "relation"? Formally, a relation is a collection of ordered pairs of objects from a set. As far as equivalence relations are concerned, two objects are related because they share a common property. So an equivalence relation is a more general form of equality that deals with sets of objects that have some property in common.^{[2]}
Examples
Here are some examples of equivalence relations
 "=" on the set of numbers
 "is the same height as" on a set of people
 "is the same color as" on a set of platypuses
 These equivalence relations show that even though two people, or platypuses, are not exactly the same, they can be related together by one aspect, namely their height or color.
 "has the same modulo as" on a set of numbers
 3 is the same modulo base 10 as itself (reflexivity)
 3 is the same modulo base 10 as 13 and vice versa (symmetry)
 3 is the same modulo as 13, and 13 is the same modulo as 23, and thus 3 is the same modulo as 23 (all in base 10). (transitivity)
 "is congruent to" on the set of triangles
 "is connected to" on a set of vertices of a graph
Almost an Equivalence Relation
While it may seem easy to create an equivalence relation over a set, there are some relations that seem to be equivalence relations, but really are not.
 The relation "≠" over the set of numbers is symmetric, but it is neither reflexive nor transitive.
 For example 5 ≠ 5 is not true, so "≠" is not reflexive.
 It is true that 5 ≠ 4 and 4 ≠ 5. But if the transitive property applied, then this would mean 5 ≠ 5, which is not the case. So transitivity is also disproved on "≠".
 The "greater (or less) than" relation also over the set of numbers is transitive, but it is neither reflexive or symmetric. "Greater (or less) than or equal to" is reflexive and transitive, but it is not symmetric.
 5 > 5 is not true.
 "If 5 > 4, then 4 > 5" is also not a true statement. (This also applies to "≥".)
 In Graph Theory, "Is adjacent to" over the set of vertices in a graph is reflexive and symmetric, but it is not transitive.
 For example, consider the vertices u, v, and w in figure 1. u is adjacent to v, and v is adjacent to w, but u is not adjacent to w. Thus the relation isn't transitive.
Equivalence Classes
An equivalence class is a subset of objects in a set that are all equivalent to another given object. Formally, given a set X, an equivalence relation "~", and a in X, then an equivalence class is:
For example, let us consider the equivalence relation "the same modulo base 10 as" over the set of positive integers numbers. We can make an equivalence class, say [3], by finding all of the numbers that have modulo 3 base ten.
In this example, the 3 corresponds to a, the set of natural numbers corresponds to the set X, and "congruent" and "mod 10" both correspond to the equivalence relation, ~. Below is another example of an equivalence class in graph theory. This requires knowledge of Graph Theory.
Now, equivalence classes have a nice property. Let us consider two equivalence classes, [a] and [b], with the same equivalence relation over the same set and generated by the objects a and b respectively. It can be shown that either [a] and [b] are the same, or they have no elements in common.
It is rather surprising that two simple definitions can generate such a generalized result. Below is a formal proof.
There do not have to be just two equivalence classes with the same equivalence relation in a given set—sets can have an infinite number of them. But we know that none of them can overlap! So, an equivalence relation also can be used to divide sets into various subsets. This is because every member of a set it at least a member of its own equivalence class, by the reflexive property. Thus, since the classes are disjoint and every member of a set is included in one, equivalence classes with the same equivalence relation can divide up a set into disjoint sets.
References
 ↑ Weisstein, Eric W. "Equivalence Class." From MathWorldA Wolfram Web Resource. http://mathworld.wolfram.com/EquivalenceClass.html
 ↑ Maurer, Stephen B. Discrete Algorithmic Mathematics". A. K. Peters Ltd. Wellesley MA: 2004.
 ↑ http://classes.soe.ucsc.edu/cmpe177/Fall04/slides/digraphs.pdf