Equivalence (Preorder Plus Symmetry)

Equivalence (Preorder plus Symmetry): An equivalence relation is reflexive, symmetric, and transitive. Consider the BB relation for three basketball players A, B, and C. Now, consider a “specialization” of this relation obtained by leaving out certain edges:
≡_BB = {A,A, A,B, B,A, B,B, C,C}.
This relation is an equivalence relation, as can be easily verified.
Note that ≡_BB =≤_BB ≤∩ ⁻¹ _BB. In other words, this equivalence relation is obtained by taking the preorder ≤ _BB and intersecting it with its inverse. The fact that BB ∩ ⁻¹ BB is an equivalence relation is not an accident. The following section demonstrates a general result in this regard.

Intersecting a preorder and its inverse: Theorem 4.1. The relation obtained by intersecting a preorder r with its inverse r−1 is an equivalence relation.
Proof: First we show that R∩R−1 is reflexive. Let R be a preorder over set S. Therefore, R is reflexive, i.e., it contains x, x pairs for every x ∈ S. From the definition of R−1, it also contains these pairs. Hence, the intersection contains these pairs. Therefore, R ∩ R−1 is reflexive. Next we show that R ∩ R−1 is symmetric. That is, to show that for every x, y ∈ S, x, y ∈ R ∩ R−1 implies y, x ∈ R ∩ R−1. If the antecedent, i.e., x, y ∈ R ∩ R−1 is false, the assertion is vacuously true. Consider when the antecedent is true for a certain x, y. These x and y must be such that x, y ∈ R and x, y ∈ R−1. The former implies that y, x ∈ R−1. The latter implies that y, x ∈ R. Hence, y, x ∈ R ∩ R−1. Hence, R ∩ R−1 is symmetric.
Next we prove that R∩R−1 is transitive. Since R is a preorder, it is transitive. We now argue that the inverse of any transitive relation is transitive. From the definition of transitivity, for every x, y, z ∈ S, from the antecedents x, y ∈ R and y, z ∈ R, the consequent x, z ∈ R follows. From these antecedents, we have that y, x ∈ R−1 and z, y ∈ R−1 respectively. From the above conclusion x, z ∈ R, we can infer that z, x ∈ R−1. Hence, R−1 is transitive and so is the conjunction of R and R−1.
Identity relation: Given a set S, the identity relation R over S is {x, x | x ∈ S}. An identity relation is one extreme (special case) of an equivalence relation. This relation is commonly denoted by the equality symbol, =, and relates equals with equals. Please note the contrast with Theorem 4.1.
Universal relation: The universal relation R over S is S × S, and represents the other extreme of relating everything to everything else. This is often an uninteresting binary relation.2

Equivalence class: An equivalence relation R over S partitions elements(R) = domain(R)∪ codomain(R) into equivalence classes. Intuitively, the equivalence classes Ei are those subsets of elements(R) such that every pair of elements in Ei is related by R, and Eis are the maximal such subsets. More formally, given an equivalence relation R, there are two cases:

R is a universal relation. In this case, there is a single equivalence class E1 associated with R, which is elements(R) itself.
R is not a universal equivalence relation. In this case, an equivalence class Ei is a maximal proper subset of elements(R) such that the restriction of R on Ei, R |Ei , is universal (meaning that every pair of elements inside each of the Eis is related by R).

Putting it all together, the set of all equivalence classes of an equivalence relation R is written “elements(R)/R.” It can be read, “the elements of R partitioned according to R.” In general, we will write S/ ≡, meaning “set S partitioned according to the equivalence relation ≡.” in Section 4.3.1, we will demonstrate Theorem 4.1 on the Power relation that relates machine types.

SKEDSOFT