[Math] Understanding equivalence class, equivalence relation, partition

elementary-set-theoryequivalence-relationsrelationsset-partition

I'm having difficulty grasping a couple of set theory concepts, specifically concepts dealing with relations. Here are the ones I'm having trouble with and their definitions.

1) The collection of equivalence classes w.r.t. $R$

Def: Let $R$ be an equivalence relation in a set $X$. The collection of equivalence classes w.r.t. $R$ is the set:
$$[X]/R =\{S|(\exists x)(x\in X\land S=[x]/R)\}=\{[x]/R|x\in X\}$$

2) Partition

Def: Let $X$ be a set. A collection of sets $C$ is a partition of $X$ if:

(i) $$\bigcup_{S\in\ C} S=X.$$
(ii) $$\forall S \in C, S \neq \varnothing$$
(iii) $$\forall S, S' \in C, S' \neq S \Rightarrow S \cap S' = \varnothing$$

3) Relation induced by

Def: Let $C$ be a partition of $X$. The relation induced by $C$, denoted by $X/C$, is a relation in $X$ such that $$X/C = \{(x,y) | (\exists S \in C)(\exists x \in S \land \exists y \in S)\}$$

Best Answer

$\newcommand{\ms}{\mathscr}$Equivalence relations and partitions are very intimately related; indeed, it’s fair to say that they are two different ways of looking at basically the same thing.

Start with a set $A$. A partition $\ms P$ of $A$ is just a way of chopping $A$ up into pieces. More formally, it’s a collection of subsets of $A$ with a very simple property: every element of $A$ belongs to exactly one of the sets in $\ms P$. This is often expressed in a slightly more roundabout fashion: a collection $\ms P$ of non-empty subsets of $A$ is a partition of $A$ if

  1. $A=\bigcup_{P\in\ms P}P$, and
  2. if $P_1,P_2\in\ms P$ and $P_1\ne P_2$, then $P_1\cap P_2=\varnothing$, i.e., the members of $\ms P$ are pairwise disjoint.

The first of these conditions says that each element of $A$ belongs to at least one member of $\ms P$, and the second says that no element of $A$ belongs to more than one member of $\ms P$; put the two together, and you get my original definition.

We can use the partition $\ms P$ to define an associated relation $\overset{\ms P}\sim$ on $A$: for any $x,y\in A$, $x\overset{\ms P}\sim y$ if and only if $x$ and $y$ are in the same piece of the partition $\ms P$. For instance, if $A$ is a set of people, we can partition them according to their ages: the $20$-year-olds are one piece of the partition, the $50$-year-olds are another, and so on. The associated relation is simply has the same age as: $x\overset{\ms P}\sim y$ if and only if $x$ and $y$ are the same age. It’s easy to see in this case that $\overset{\ms P}\sim$ is an equivalence relation $-$ reflexive, symmetric, and transitive $-$ and it’s not hard to prove that this is always the case: if $\ms P$ is a partition of a set $A$, then $\overset{\ms P}\sim$ is an equivalence relation on $A$.

Now what are the equivalence classes of this relation $\overset{\ms P}\sim$? Fix $a\in A$. The equivalence class of $a$ is by definition $\{x\in A:a\overset{\ms P}\sim x\}$. But $a\overset{\ms P}\sim x$ just means that $a$ and $x$ are in the same piece of the partition $\ms P$, so $x$ is in the equivalence class of $a$ if and only if is in the same piece as $a$. In other words, the equivalence class of $a$ is the piece of $\ms P$ that contains $a$. And this is true for every $a\in A$, so the equivalence classes of the relation $\overset{\ms P}\sim$ are exactly the pieces of the partition $\ms P$, the ‘chunks’ into which it divides $A$.

Now set that aside for a moment, and let $R$ be an equivalence relation on $A$. For each $a\in A$ we set $[a]/R=\{x\in A:aRx\}$; this is the equivalence class of $a$, the set of things to which $a$ is related by $R$. It’s a subset of $A$. One of the first things that you prove about equivalence classes is that for any $a,b\in A$, either $aRb$, in which case $[a]/R=[b]/R$, or $a\not Rb$, in which case $[a]/R\cap[b]/R=\varnothing$: any two equivalence classes are either the same set or completely disjoint from each other. In other words, the equivalence classes chop up $A$ into pairwise disjoint pieces, and every element $a$ of $A$ belongs to exactly one of these pieces, namely $[a]/R$.

But this is exactly what it means to say that $A/R$, the collection of all of these equivalence classes, is a partition of $A$: each element of $A$ belongs to exactly one of the sets in the collection $A/R$. Just as a partition $\ms P$ of $A$ gives rise to an associated equivalence relation $\overset{\ms P}\sim$ on $A$, an equivalence relation $R$ on $A$ gives rise to an associated partition $A/R$ of $A$. What happens if we start with the partition $A/R$ and construct its associated equivalence relation $\overset{A/R}\sim$ on $A$? For any $x,y\in A$ we have by definition $x\overset{A/R}\sim y$ if and only if $x$ and $y$ are in the same piece of $A/R$. But the pieces of $A/R$ are the $R$-equivalence classes, so $x$ and $y$ are in the same piece of the partition $A/R$ if and only if $[x]/R=[y]/R$, i.e., if and only if $xRy$. That is, $x\overset{A/R}\sim y$ if and only if $xRy$, and $\overset{A/R}\sim$ and $R$ are exactly the same relation on $A$.

To recapitulate:

  1. Each partition $\ms P$ of $A$ induces an associated equivalence relation $\overset{\ms P}\sim$ on $A$, and each equivalence relation $R$ on $A$ induces an associated partition $A/R$ of $A$ into equivalences classes.

  2. These conversion operations from partition to equivalence relation and vice versa are inverses. If you start with a partition $\ms P$ of $A$, construct the equivalence relation $\overset{\ms P}\sim$ on $A$, and then construct the associated partition $A/\overset{\ms P}\sim$ of $A$, you’re back where you started: $A/\overset{\ms P}\sim=\ms P$. Similarly, if you start with an equivalence relation $R$ on $A$, construct the associated partition $A/R$ of $A$, and then build from that partition its associated equivalence relation $\overset{A/R}\sim$, you get the original relation $R$ back: $\overset{A/R}\sim=R$.

Related Question