[proofplan] We first define the equivalence class of an element and prove that these classes cover $X$ by reflexivity. We then prove the key overlap lemma: two equivalence classes that meet must be equal, using symmetry and transitivity of the [equivalence relation](/page/Equivalence%20Relation). Finally, starting from a [partition](/page/Partition), we define the same-part relation and verify reflexivity, symmetry, and transitivity, then identify its equivalence classes with the parts of the partition. [/proofplan] [step:Define the equivalence classes and prove that they cover $X$] For each $x \in X$, define the equivalence class of $x$ by \begin{align*} [x] := \{y \in X : y \sim x\}. \end{align*} Since $\sim$ is an equivalence relation, it is reflexive. Hence $x \sim x$ for every $x \in X$, so $x \in [x]$. Therefore every element of $X$ belongs to at least one equivalence class, and \begin{align*} X = \bigcup_{x \in X} [x]. \end{align*} [/step] [step:Show that two equivalence classes with a common element are equal] [claim:Overlapping equivalence classes are equal] For all $x,y \in X$, if $[x] \cap [y] \neq \varnothing$, then $[x] = [y]$. [/claim] [proof] Let $x,y \in X$, and suppose $[x] \cap [y] \neq \varnothing$. Choose $z \in [x] \cap [y]$. By the definition of equivalence class, $z \sim x$ and $z \sim y$. Since $\sim$ is symmetric, $x \sim z$. By transitivity applied to $x \sim z$ and $z \sim y$, we obtain $x \sim y$. We prove $[x] \subset [y]$. Let $w \in [x]$. Then $w \sim x$. Since $x \sim y$, transitivity applied to $w \sim x$ and $x \sim y$ gives $w \sim y$. Thus $w \in [y]$ by the definition of $[y]$. Hence $[x] \subset [y]$. We prove $[y] \subset [x]$. Let $w \in [y]$. Then $w \sim y$. Since $x \sim y$, symmetry gives $y \sim x$. Transitivity applied to $w \sim y$ and $y \sim x$ gives $w \sim x$. Thus $w \in [x]$. Hence $[y] \subset [x]$. Therefore $[x] = [y]$. [/proof] [guided] We want to prove that overlap forces equality. Let $x,y \in X$, and assume $[x] \cap [y] \neq \varnothing$. This means there exists an element $z \in X$ such that $z \in [x]$ and $z \in [y]$. By the definition \begin{align*} [x] := \{u \in X : u \sim x\}, \end{align*} the membership $z \in [x]$ gives $z \sim x$, and the membership $z \in [y]$ gives $z \sim y$. The goal is to connect $x$ and $y$. Since $\sim$ is symmetric and $z \sim x$, we get $x \sim z$. Since $\sim$ is transitive, applying transitivity to $x \sim z$ and $z \sim y$ gives \begin{align*} x \sim y. \end{align*} Now we show the two inclusions. First let $w \in [x]$. Then $w \sim x$. We already know $x \sim y$, so transitivity applied to $w \sim x$ and $x \sim y$ gives $w \sim y$. Therefore $w \in [y]$. Since this holds for every $w \in [x]$, we have \begin{align*} [x] \subset [y]. \end{align*} For the reverse inclusion, let $w \in [y]$. Then $w \sim y$. From $x \sim y$ and symmetry, we obtain $y \sim x$. Applying transitivity to $w \sim y$ and $y \sim x$ gives $w \sim x$. Hence $w \in [x]$. Since this holds for every $w \in [y]$, we have \begin{align*} [y] \subset [x]. \end{align*} The two inclusions imply $[x] = [y]$. [/guided] [/step] [step:Conclude that equivalence classes form a partition] The preceding cover identity shows that every element of $X$ lies in at least one equivalence class. The overlap claim shows that if two equivalence classes are not equal, then they are disjoint: indeed, if $[x] \cap [y] \neq \varnothing$, the claim gives $[x] = [y]$. Therefore the family \begin{align*} \{[x] : x \in X\} \end{align*} is a partition of $X$. [/step] [step:Define the same-part relation from a partition] Conversely, let $\mathcal{P}$ be a partition of $X$. Thus every part $P \in \mathcal{P}$ is a nonempty subset of $X$, the parts are pairwise disjoint, and \begin{align*} X = \bigcup_{P \in \mathcal{P}} P. \end{align*} Define a relation $\sim$ on $X$ by declaring, for $a,b \in X$, \begin{align*} a \sim b \quad \Longleftrightarrow \quad \text{there exists } P \in \mathcal{P} \text{ such that } a \in P \text{ and } b \in P. \end{align*} [/step] [step:Verify that the same-part relation is an equivalence relation] We verify the three defining properties of an equivalence relation. Reflexivity: let $a \in X$. Since $\mathcal{P}$ covers $X$, there exists $P \in \mathcal{P}$ such that $a \in P$. Therefore $a$ and $a$ lie in the same part $P$, so $a \sim a$. Symmetry: let $a,b \in X$ and suppose $a \sim b$. Then there exists $P \in \mathcal{P}$ such that $a \in P$ and $b \in P$. The same part $P$ contains $b$ and $a$, so $b \sim a$. Transitivity: let $a,b,c \in X$ and suppose $a \sim b$ and $b \sim c$. Then there exist parts $P,Q \in \mathcal{P}$ such that $a,b \in P$ and $b,c \in Q$. Since $b \in P \cap Q$ and distinct parts of a partition are disjoint, we must have $P = Q$. Hence $a,c \in P$, so $a \sim c$. Thus $\sim$ is an equivalence relation on $X$. [guided] We must check reflexivity, symmetry, and transitivity for the relation \begin{align*} a \sim b \quad \Longleftrightarrow \quad \text{there exists } P \in \mathcal{P} \text{ such that } a \in P \text{ and } b \in P. \end{align*} For reflexivity, fix $a \in X$. Because $\mathcal{P}$ is a partition, its parts cover $X$, so there is some part $P \in \mathcal{P}$ with $a \in P$. Then both entries $a$ and $a$ lie in this same part $P$. By the definition of $\sim$, this gives $a \sim a$. For symmetry, fix $a,b \in X$ and assume $a \sim b$. By definition, there is a part $P \in \mathcal{P}$ such that $a \in P$ and $b \in P$. The order of listing the two elements does not change membership in $P$, so $b \in P$ and $a \in P$. Therefore $b \sim a$. For transitivity, fix $a,b,c \in X$ and assume $a \sim b$ and $b \sim c$. From $a \sim b$, choose a part $P \in \mathcal{P}$ such that $a,b \in P$. From $b \sim c$, choose a part $Q \in \mathcal{P}$ such that $b,c \in Q$. Now $b$ lies in both $P$ and $Q$, so \begin{align*} b \in P \cap Q. \end{align*} Because $\mathcal{P}$ is a partition, two distinct parts cannot intersect. Since $P \cap Q$ contains $b$, the parts cannot be distinct; hence $P = Q$. Therefore $a$ and $c$ both lie in the same part $P$, and the definition of $\sim$ gives $a \sim c$. The relation is reflexive, symmetric, and transitive, so it is an equivalence relation. [/guided] [/step] [step:Identify the equivalence classes with the parts of the partition] Let $a \in X$. Since $\mathcal{P}$ is a partition of $X$, there exists a unique part $P_a \in \mathcal{P}$ such that $a \in P_a$. The equivalence class of $a$ under the same-part relation is \begin{align*} [a] = \{b \in X : b \sim a\}. \end{align*} If $b \in [a]$, then $b \sim a$, so $b$ and $a$ lie in some part $Q \in \mathcal{P}$. Since $a \in Q$ and $a \in P_a$, uniqueness of the part containing $a$ gives $Q = P_a$, hence $b \in P_a$. Thus $[a] \subset P_a$. Conversely, if $b \in P_a$, then $a$ and $b$ lie in the same part $P_a$, so $b \sim a$ and therefore $b \in [a]$. Hence $P_a \subset [a]$. Therefore \begin{align*} [a] = P_a. \end{align*} Thus the equivalence classes of the relation defined by the partition are precisely the parts of $\mathcal{P}$. [/step]