----- > [!proposition] Proposition. ([[partitions are always determined uniquely by equivalence relations]]) > For every [[partition]] $\mathscr{D}$ of a set $A$, there exists a unique [[equivalence relation]] on $A$ from which it is derived. > [!proof]- Proof. ([[partitions are always determined uniquely by equivalence relations]]) > Let $\mathscr{D}:=\bigsqcup_{i \in I} D_{i}$ be a [[partition]] of $A$ ($I$ an index set). Define the [[equivalence relation]] $\sim \subset A \times A$ by $\sim:= \{ (x,y): x \in D_{i} \text{ and } y \in D_{i} \text{ for some } i \in I \}.$ Let $x \in A$. Then $x$ belongs to $D_{j}$ for some $j \in I$. Its [[equivalence class]] $E_{x}$ is $E_{x}=\{ y \in A : y \in D_{j} \text{ also} \}=D_{j}.$ Since [[two equivalence classes are either disjoint or equal]] and $x$ was arbitrary, we conclude that the collection $\mathscr{D}$ equals the collection of [[equivalence class]]es determined by $\sim$. \ For uniqueness: suppose that the collection $\mathscr{D}$ equals the collection of [[equivalence class]]es determined by an [[equivalence relation]] $C$ on $A$. Given $x \in A$, We will show that $y C x$ if and only if $y\sim x$, from which it follows that $\sim=C$. First suppose $yCx$. Then $y$ is in the [[equivalence class]] of $x$ determined by $C$; hence $y$ and $x$ belong to the same item in $\mathscr{D}$ since $\mathscr{D}$ is assumed to be a collection of [[equivalence class]]es. Thus, $y \sim x$. Conversely assume that $y \sim x$. Then $y$ and $x$ belong to the same item in $\mathscr{D}$ by definition of $\sim$. But $\mathscr{D}$ is assumed to be a collection of [[equivalence class]]es determined by $C$, so we must in turn have $y C x$. $\qedin$ ----- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```