D: Partitions and Equivalence Relations
- Page ID
- 74654
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)A partition of a set \(X\) is a collection \(\mathcal{P}\) of pairwise disjoint, non-empty subsets of \(X\) whose union is \(X\). The elements of \(\mathcal{P}\) are called the blocks of the partition.
For example, if \(X=[9]= \{1,2,3,4,5,6,7,8,9\}\) then \[\mathcal{P}=\{ \{1,2\},\{3\},\{5,8,9\}, \{4,6,7\} \}\] is a partition of \(X\). Note that this partition has four blocks \(\{1,2\}\), \(\{3\}\), \(\{5,8,9\}\), and \(\{4,6,7\}\).
Remark: In the definition of partition we used the term collection. This is just another name for set. It is just more natural to say collection of sets than to say set of sets. So in fact, a partition of \(X\) is a set whose elements are themselves sets which we choose to call blocks– satisfying three properties:
- Each block is a non-empty subset of \(X\).
- No two different blocks have an element in common.
- Every element of \(X\) lies in at least one block.
Problem D.1 Find all partitions of the set \([4]\). List them according to the numbers of blocks in each partition. The number of blocks may be any integer from 1 to 4.
Problem D.2 Find a partition \(\mathcal{P}_k\) of the set \(\mathbb{Z}\) that has exactly \(k\) blocks for each of the following values of \(k\): 1,2,3,4,5,10.
A (binary) relation on a set \(X\) is a subset \(\rho\) of the Cartesian product \(X \times X\). If \((a,b) \in R\) we write \(a \rho b\) and we say that \(a\) is related to \(b\) with respect to the relation \(R\).
Since we will only be concerned with binary relations, we will leave off the modifier binary. Examples of relations are \(<\) and \(\le\) on the set \(\mathbb{R}\), \(=\) on any set, and \(\cong\) on the class of all groups. Rather than use \(\rho\) for a generic relation, we use the symbol \(\sim\).
A relation \(\sim\) on a set \(X\) is an equivalence relation on \(X\) if the following properties hold for all \(x,y,z \in X\).
- \(x \sim x\).
- If \(x \sim y\) then \(y \sim x\).
- If \(x \sim y\) and \(y \sim z\) then \(x \sim z\).
The properties in the above definition are called reflexivity, symmetry, transitivity, respectively.
The most common equivalence relation is equality. Equality is an equivalence relation on any set.
If \(\sim\) is an equivalence relation on the set \(X\), and \(a \in X\) we define the set \[[a] = \{ x \in X \ | \ x \sim a \}.\] \([a]\) is called the equivalence class of \(a\) relative to the equivalence relation \(\sim\).
If \(\sim\) is any equivalence relation on the set \(X\) then the collection of all equivalence classes is a partition of \(X\). Conversely, given any partition \(\mathcal{P}\) of the set \(X\), one may define an equivalence relation \(\sim\) on \(X\) by the rule \[a \sim b \Longleftrightarrow a,b \in B \mbox{ for some block $B \in \mathcal{P}$}\] in which case the equivalence classes of \(\sim\) are precisely the blocks of the partition \(\mathcal{P}\).