### Equivalence (Preorder Plus Symmetry)

4 min read

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} ≤∩ ^{−1} _{BB}. In other words, this equivalence relation is obtained by taking the preorder ≤ _{BB} and intersecting it with its inverse. The fact that BB ∩ ^{−1} 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: