EF Graph for an equivalence relation

Section 18.5 Graph for an equivalence relation

Given an equivalence relation on a finite set

A,

what will we observe if we draw the relation’s graph?

🔗
Since an equivalence relation is reflexive, we might as well omit the loops at each node.
🔗
Since an equivalence relation is symmetric, we might as well replace the pairs of arrows between each related pair of nodes with a single edge, turning the directed graph into an ordinary graph.
🔗
Since an equivalence relation partitions a set into a disjoint union of equivalence classes (Theorem 18.3.8), the graph of an equivalence relation will be disconnected, with each connected component representing a specific equivalence class.
🔗
Since each element in an equivalence class is equivalent to every other element in the class (Statement 2 of Proposition 18.3.3), each connected component in the graph will be complete.

Let

A = {a, b, c, d},

and let

\equiv

be the equivalence relation on

P (A)

defined by

B \equiv B^{'}

| B | = | B^{'} | .

That is, two subsets of

A

will be considered equivalent if they contain the same number of elements. Figure 18.5.2 contains the graph for

\equiv,

with reflexive loops and symmetric bidirectional arrows omitted.