Section 14.1 Equivalence relations
Consider the relation \(R\) on \(X=\{a,b,c,d,e,f,g\}\text{,}\) where
The digraph is drawn below:
The directed graph of the above relation. There is a loop at each element. The elements \(a\text{,}\) \(d\text{,}\) and \(g\) are all related to each other in both directions, as are \(b\text{,}\) \(c\text{,}\) \(e\text{,}\) and \(f\text{.}\)
The most visually striking feature of this directed graph is that the set \(X\) is partitioned into separated “blocks”: the piece with \(a\text{,}\) \(d\text{,}\) and \(g\text{,}\) and the piece with \(b\text{,}\) \(c\text{,}\) \(e\text{,}\) and \(f\text{.}\)
To understand this phenomenon, let's try to understand what properties \(R\) has? It is reflexive, it is symmetric, and it is transitive. (Verify these for yourself.) Taken together they imply a “fullness” of the relation in the blocks: the arrow \((a,d)\) brings with it the arrows \((a,a)\text{,}\) \((d,a)\text{,}\) and \((d,d)\text{,}\) and if we add \((d,g)\text{,}\) we get \((a,g)\text{,}\) \((g,d)\text{,}\) \((g,a)\text{,}\) and \((g,g)\text{.}\)
A relation with this set of properties is useful enough to earn its own title.
Definition 14.1.2.
An equivalence relation is any relation that is reflexive, symmetric, and transitive.
The idea is that an equivalence relation behaves like equality, as evidenced in the examples below.
Example 14.1.3.
The relation given by the statement \(x=y\) on any set \(X\) is an equivalence relation. In fact it is the prototypical equivalence relation, in the sense that the point of an equivalence relations is to get the idea of equality in a less strict way.
Example 14.1.4.
The typical way to define equivalence between sets is to say that two sets \(X\) and \(Y\) are isomorphic if \(|X|=|Y|\text{.}\) This relation is an equivalence relation, but \(X\) and \(Y\) do not need to actually be equal to be equivalent. (You may have noticed often we relabel the elements of a set in proofs and examples. This is because, when we are just looking at things on the set level, we don't care what the elements are but rather how many there are.)
Example 14.1.5.
Let \(\mathscr{S}\) be a family of propositional statements on a set of statement letters and define the relation \(\phi \equiv \psi\) to mean that \(\phi \to \psi\) and \(\psi \to \phi\) are both always true regardless of the truth values of the statement letters that compose \(\phi\) and \(\psi\text{.}\)
This relation, which should be familiar from the first few chapters of this book, is an equivalence relation. It is reflexive because \(\phi \to \phi\) is a tautology. It is symmetric because “\(\phi \to \psi\) and \(\psi \to \phi\) are both tautologies” is the same sentence as “\(\psi \to \phi\) and \(\phi \to \psi\) are both tautologies”. Finally, it is transitive because the conditional is. Let \(\gamma\) be a third statement and suppose \(\phi \to \psi\) and \(\psi \to \gamma\) are both tautologies. Then, \(\phi \to \gamma\) is a tautology as well.
Definition 14.1.6.
Let \(R\) be an equivalence relation on a set \(X\text{.}\) The equivalence class of \(x \in X\) is the set of all elements to which it is equivalent:
Example 14.1.7.
Let again
be a relation on \(X = \{a,b,c,d,e,f,g\}\) whose directed graph is reproduced below. This relation divides its underlying set into the equivalence classes
and
precisely the discrete “blocks” of the digraph. Note that the name of the equivalence class is an arbitrarily chosen representative: \([b]\text{,}\) \([c]\text{,}\) \([e]\text{,}\) and \([f]\) all refer to the same set.
Let's do something a little weird, and order the elements of the set as follows: \((a, d, g, b, c, e, f)\text{.}\) The following Boolean matrix is constructed in that order, so that the second row represents the elements that \(d\) is related to. What do you notice?
Example 14.1.8.
Consider the set \(\mathscr{B}_2\) of all \(2\times 2\) Boolean matrices. Define an equivalence relation on this set by saying that \(A \sim B\) if and only if \(A\) and \(B\) have the same number of ones. Confirm for yourself that this relation is reflexive, symmetric, and transitive.
The equivalence classes under this relation are as follows:
Observe that, in this case, each equivalence class contains \({{4}\choose{r}}\) matrices. Do you see why?