Proof of theorem about equivalence classes

Question

I am looking to understand the following theorem, and I am also wondering what is meant by "mutually disjoint", or at least how it's to be understood in the following context:

The distinct equivalence classes of an equivalence relation on $A$ provide us with a decomposition of $A$ as a union of mutually disjoint subsets, conversely given a decomposition of $A$ as a union of mutually disjoint, nonempty subsets, we can define an equivalence relation on $A$ for which these subsets are the distinct equivalence classes.

I am also looking to know if there is any common name to this theorem, or any best accepted proof of this? Also, I am just wanting to better understand the intuition of this, and why it holds and makes sense, etc. Thank you.

Answer 1

I would call the result you're asking about the "fundamental theorem for equivalence relations" (relevant Wikipedia link; also, take a look here), but the result is also tantamount to the "first isomorphism theorem for sets".

The intuition for this theorem is extremely simple:

If you've defined "related", you can group objects according to whether they're related.

If you've grouped objects, you can define "related" to mean "in the same group".

We start with a set of objects, $X$. If I tell you a rule (the rule is usually named $\sim$) which says when two elements of $X$ are "related", then I can divide the objects of $X$ into groups where

• every object in a given group is related to every other object in that group
• any two objects from different groups are not related

(that's the "mutually disjoint" collection of subsets of $X$).

Conversely, if I've divided the objects of $X$ into some arbitrary groups, then I can define a rule that says two objects of $X$ are related if and only if they are in the same group.

---

A collection of sets $\mathcal{S}=\{S_\alpha\}_{\alpha\in I}$ is mutually disjoint (relevant Wikipedia link), sometimes just disjoint for conciseness, if for any two distinct $\alpha,\beta\in I$, we have $$S_\alpha\cap S_\beta=\varnothing.$$ Thus, for example, the collection $\mathcal{T}=\{\{x,y\},\{w,z\},\{a,b\}\}$ is mutually disjoint because $$\begin{align*} \{x,y\}\cap\{w,z\}&=\varnothing\\ \{x,y\}\cap\{a,b\}&=\varnothing\\ \{w,z\}\cap\{a,b\}&=\varnothing \end{align*}$$ but the collection $\mathcal{U}=\{\{1,2\},\{3,4\},\{1,5\}\}$ is not, because $$\{1,2\}\cap \{1,5\}=\{1\}$$

Answer 2

Mutually disjoint means that any two subsets have an empty intersection

Proof => : Take the image of the application f, where f(x) is the equivalence class of x

<= : Define the equivalence relation xRy iff y is in the subset that contains x.

Answer 3

A family of sets $\{ A_{i} : i \in I \}$ is mutually disjoint or pairwise disjoint if $A_{i} \cap A_{j} = \emptyset$ whenever $i \neq j$. That an equivalence class on $S$ induces a partition of $S$ (i.e. a family $\mathcal{F}$ of subsets of $S$ such that $\mathcal{F}$ is mutually disjoint, and $S = \cup_{F \in \mathcal{F}} F$) is a property of equivalence classes which is very commonly invoked, as well as easy to show (see further below).

Let $\equiv$ be an equivalence relation on a set $S$, and define \begin{align*} [s] & = \{ t \in S : s \equiv t \}. \end{align*} Now let $\mathcal{F} = \{ [s] : s \in S \}$, i.e. the set of all equivalence classes. We just need to check that (i) $\cup_{F \in \mathcal{F}} = S$, and (ii) if $F, G \in \mathcal{F}$, and $F \neq G$, then $F \cap G = \emptyset$.

First, let's check (i). If we pick any $s \in S$, then there exists $F \in \mathcal{F}$ such that $s \in F$, namely $F = [s]$. Now for (ii), let's review what defines an equivalence relation. In particular, equivalence relations are transitive. We're going to show the contrapositive of (ii), i.e. that if $F \cap G \neq \emptyset$, then $F = G$. To do this, suppose we have $F = [s], G = [t]$, and $u \in F \cap G$. Then $u \equiv s$, and $u \equiv t$. But that means $s \equiv u \equiv t \Rightarrow s \equiv t \Rightarrow [s] = [t]$. This concludes the proof. Now you can use this property freely.

Answer 4

Let me first explain what is meant by a decomposition of a set $A$ as a union of mutually disjoint subsets. It is a partition of $A$ into sets $B_i$ such that $\cup B_i = A$ and if $i \ne j$, $B_i \cap B_j = \emptyset$. The members of partition are mutually disjoint, that is, have no element in common and taken together form the set $A$.

Your theorem can now be written as "Every equivalence relation on $A$ induces a partition in $A$ and conversely, every partition in $A$ induces an equivalence relation on $A$". Let me know give you a sketch of the proof.

Let us first prove that "Every equivalence relation on $A$ induces a partition in $A$". Let $a \in A$ and let $[a]$ denote the equivalence class of the element $a$. Clearly, $a \in [a]$ and if $b \in [a]$ then $[a] = [b]$. Thus, the equivalence relation partitions $A$ into mutually disjoint equivalence classes.

Now let us prove the converse. Let a set $A$ be partitioned by $B_i$. Define the equivalence relation $R$ on $A$ as $xRy$ if $x, y \in B_i$. Clearly, $xRx$, $xRy \Leftrightarrow yRx$ and finally $xRy, yRz \Rightarrow xRz$. Thus, R is indeed an equivalence relation.