18.5: Graph for an equivalence relation

Last updated
Save as PDF

Page ID: 93869

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Given an equivalence relation on a finite set \(A\text{,}\) 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.1), 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.1), each connected component in the graph will be complete.

Example \(\PageIndex{1}\): Graph of the “same cardinality” equivalence relation.

Let \(A = \{a,b,c,d\}\text{,}\) and let \(\mathord{\equiv}\) be the equivalence relation on \(\mathscr{P}(A)\) defined by \(B \equiv B'\) if \(\vert B \vert = \vert B' \vert \text{.}\) That is, two subsets of \(A\) will be considered equivalent if they contain the same number of elements. Figure \(\PageIndex{1}\) contains the graph for \(\mathord{\equiv}\text{,}\) with reflexive loops and symmetric bidirectional arrows omitted.

Figure \(\PageIndex{1}\): Graph for equivalence of cardinality on a power set.