Equivalence Relation

From Math Images

Jump to: navigation, search
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.
The criteria for equivalence relation drawn as arrows relating two objects.
The criteria for equivalence relation drawn as arrows relating two objects.
In order to understand intuitively what an equivalence relation is, let's take a look at what "equivalent" and "relation" both mean here.

"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.

Figure 1. This simple graph shows that the adjacency relation is not an equivalence relation.
Figure 1. This simple graph shows that the adjacency relation is not an equivalence relation.
  • 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:

[a]=\{x \in X| x \sim a\}

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.

[3] = \{x \in \mathbb{N}|x\equiv 3\pmod{10}\}

[3] = \{3,13,23,\dots \}

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.

In graph theory, there is the notion of the walk, which a "trip" around a graph going from vertex to vertex by the edges connecting them. Two vertices u and v are called connected if there is a walk from u to v. As discussed in the graph theory page, the connected relation forms an equivalence relation. We can make an equivalence class using a graph G as the set, the connected relation as the equivalence relation, and a vertex u as the specific object. The equivalence class would be the set of all of the vertices in G that are connected to u, which defines a component of G.

However, connectedness in a directed graph, or digraph, is not quite the same as a regular graph. Walks in a digraph can only follow the directions of the edges, so we need to add something to the idea of connectedness in digraphs to make an equivalence relation that looks like the connected relation.

Figure 2. A digraph with strongly connected components, in purple, green, and orange. Each component is disjoint from the others. The edges are not part of the set.
Figure 2. A digraph with strongly connected components, in purple, green, and orange. Each component is disjoint from the others. The edges are not part of the set.
The equivalence relation on the set of vertices of a digraph is called the strongly connected relation. Here is how mathematicians define it. A vertex v is reachable from u if there is a walk from u to v in the digraph. The vertices u and v are strongly connected if u is reachable from v and v is reachable from u. Given the set of vertices of a digraph V(G), and three vertices u, v, and w, the relation fits the three criteria:
  • u is strongly connected to u, by the trivial walk consisting of no edges
  • If u is strongly connected to v, then v is strongly connected to u, by definition
  • If u is strongly connected to v and v is strongly connected to w, then u is strongly connected to w.

This last fact is true because a walk from u to w can be created by first going from u to v, and then from v to w. Similarly, a walk from w to u can be created by going from w to v and from v to u.

An equivalence class in the set of vertices of a digraph with the strongly connected relation is the set of all vertices strongly connected to a given vertex u. This equivalence class is called a strongly connected component. In Figure 2, the equivalence classes with the strongly connected relation between u, v, and w are shown in purple. Since the directed edges that go to the green vertices lead away from the purple ones, the purple vertices are not strongly connected to the green ones. [3]

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.

In order to prove this, we will show that if two equivalence classes have one member in common, then they have all members in common. If we prove this, then we have shown that two equivalence classes are exactly the same, or have nothing in common.

Let a and b be members of a set X with the equivalence relation "~". The equivalence classes [a] and [b] are defined as the following.

[a]=\{x \in X| x \sim a\} [b]=\{x \in X| x \sim b\}

Let's assume that the two equivalence classes have an element in common. Let j be this member that [a] and [b] have in common.

By definition of the equivalence classes;

j \sim a j \sim b

By symmetry on the first expression, we have

a \sim j j \sim b

By the transitive property of "~";

a \sim b

Now, we will show that [a] and [b] are the same by showing that they are subsets of each other. For any x that is a member of [a],

x \sim a

By the above relation between a and b and the transitive property,

x \sim b

Thus, every member of [a] is in [b]:

[a] \subset [b]

Similarly, for some y that is a member of [b]:

y \sim b

By the symmetric and transitive properties

y \sim a

Thus, every member of [b] is also in [a]:

[b] \subset [a]

Since [a] and [b] are subset of each other, they are equal.

[a]=[b]

So, if two equivalence classes with the same equivalence relation over the same set have an element in common, then the two classes are equal. This implies that either the sets are exactly the same, or have nothing in common. We have established the result.

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

  1. ↑ Weisstein, Eric W. "Equivalence Class." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EquivalenceClass.html
  2. ↑ Maurer, Stephen B. Discrete Algorithmic Mathematics". A. K. Peters Ltd. Wellesley MA: 2004.
  3. ↑ http://classes.soe.ucsc.edu/cmpe177/Fall04/slides/digraphs.pdf
Retrieved from "http://mathforum.org/mathimages/index.php/Equivalence_Relation"
Personal tools
Create or Edit a Page