18-03-2023

Problem: Let $\mathcal{P} (\mathbb{R} )$ denotes the set of all subsets of $\mathbb{R} $ and $|A|$ denotes the cardinality of $A$. Define a relation on $\mathcal{P} (\mathbb{R} )$ as \[ A \sim B \iff |A| = |B|,~\text{for }A,B\in \mathcal{P}(\mathbb{R}). \]

  1. Prove that the relation $\sim$ is an equivalence relation.
  2. Find out the equivalence classes of the sets $\{0,1,2,\ldots,n\},~\mathbb{Z} $ and $\mathbb{Q} $.
  3. Describe all equivalence classes of the relation $\sim$.

Solution: On $\mathcal{P} (\mathbb{R} )$ we have the $A\sim B \iff \vert A \vert = \vert B \vert $.

  1. We want to prove that the relation is an equivalence relation.
    • Reflexive: We need to show that for every $A\in \mathcal{P} (\mathbb{R} )$, $A\sim A$. This is true as the cardinality of $A$ is same as $A$.
    • Symmetric: If $A\sim B$, then \[ \vert A \vert = \vert B \vert \implies \vert B \vert = \vert A \vert \implies B\sim A. \]
    • Transitive: Let $A\sim B$ and $B\sim C$. We need to prove that $A\sim C$. Note that \[ A \sim B \implies \vert A \vert =\vert B \vert, \text{ and } B\sim C \implies \vert B \vert = \vert C \vert . \] Therefore, we have \[ \vert A \vert =\vert B \vert =\vert C \vert . \] Hence, $B\sim C$.

  2. The equivalence class of the set $I_n \coloneqq \left\{ 0,1,\ldots ,n \right\} $ will be \begin{align*} \left[ I_n \right] & = \left\{ A\subseteq \mathbb{R} : I_n \sim A \right\} \\ & = \left\{ A\subseteq \mathbb{R} : \left\vert I_n \right\vert = \vert A \vert \right\} \\ & = \left\{ A \subseteq \mathbb{R} : \vert A \vert = n \right\}. \end{align*} Similarly, the equivalence class of $\mathbb{Z} $ will be \begin{align*} \left[ \mathbb{Z} \right] & = \left\{ A\subseteq \mathbb{R} : \vert A \vert = \left\vert \mathbb{Z} \right\vert \right\} \\ & = \left\{ A \subseteq \mathbb{R} : A \text{ is countable} \right\}. \end{align*} Therefore, $\mathbb{Q} \in \left[ \mathbb{Z} \right] $ and hence, $\left[ \mathbb{Q} \right] = \left[ \mathbb{Z} \right] $.

  3. From the above examples, we have the following equivalence classes of this relation. \[ \left\{ I_n : n\in \mathbb{N} \right\}, ~ \mathbb{Z} ,~\mathbb{R} . \] The first one contains all finite subsets of $\mathbb{R} $ the second one contains all countable sets and the last one contains all uncountable subsets of $\mathbb{R} $. A subset of $\mathbb{R} $can either be of finite cardinality, or countable or uncountable and have the same cardinality as of $\mathbb{R} $. Thus, these are the all equivalence classes of the given relation.