2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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\}$$

$\endgroup$
  • $\begingroup$ Thank you for the link and example $\endgroup$ – PersonaA Jun 21 '15 at 5:58
1
$\begingroup$

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 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 S$, 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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.