Understanding equivalence class, equivalence relation, partition

Solution 1:

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

Solution 2:

Why? How do we know how these definitions are related?

Fix a set $S$

Consider an equivalence relation $\sim$ on $S$. Consider the equivalence classes $[a]=\{ x \in S : x \sim a \}$. By definition these are subsets of $S$. Their union is $S$ because by reflexivity $a\in[a]$ for every $a\in S$. Finally, they are disjoint because if $x \in [a]$ and $x \in [b]$ then $x \sim a$ and so $a \sim x$, by symmetry. But then $a \sim b$ by transitivity and so $a\in [b]$. Every $y \in [a]$ is also in $[b]$ again by transitivity. This means that $[a]\subseteq [b]$. Swapping $a$ and $b$, we conclude $[a]=[b]$. All this means that the equivalence classes form a partition of $S$.

Conversely, given a partition of $S$ in subsets $C_\lambda$, define an equivalence relation in $S$ by $a\sim b$ iff there is a $\lambda$ such that $a$ and $b$ are both in $C_\lambda$. Since the $C_\lambda$ cover $S$, every $a\in S$ is in one of those and so $\sim$ is reflexive. By definition, $\sim$ is symmetric. Since the $C_\lambda$ are disjoint, $\sim$ is transitive.

Note: Every partition of a set determines an equivalence relation on that set, and for every equivalence relation, the equivalence classes corresponding to that relation form a partition of the set.

To try to put into words the relationship between a partition on a set, and the equivalence relation determined by that partition (or vice versa):

Think of simple examples of an equivalence relation on a set X, and its corresponding equivalence classes (say, $\equiv \pmod 2$ on the set of integers). What are the corresponding equivalence classes? There are two: the set of even integers, and the set of odd integers.

Evens: $E = \{x \in \mathbb{Z}\mid x\equiv 0 \pmod{2}\}$, Odds: $O = \{y \in \mathbb{Z} \mid x\equiv 1\pmod{2}\}$

Is the union of the two equivalence classes equal to the set of integers? (yes). That is, $E \cup O = \mathbb{Z}$.

Is any integer in more than one of those classes? (no). That is, $E\cap O = \varnothing$.

So we have two equivalence classes whose union is the set of integers, and whose intersection is empty. Hence, we have a partition on $\mathbb{Z}$ into two sets: the set of all even integers, and the set of all odd integers.

By definition every element in a given equivalence class is related to every other element in that class, and not to any element belonging to a different equivalence class. In the example I give above, all even numbers are related (they are even i.e., $\equiv 0 \pmod{2}$), all odd numbers are related (they are all odd, i.e., $\equiv 1 \pmod{2}$), but no integer is both even and odd.

The collection of all the equivalence classes is a partition of $X$. Every $x \in X$ belongs to one and only one equivalence class.

For example, the second definition is telling you that the union of all the equivalence classes of $X$ IS $X$ (put differently, every element of X is contained in an equivalence class) and that if any two equivalence classes are not equal, then they are disjoint: their intersection is the empty set. So every element of $X$ is in one and only one equivalence class.

Solution 3:

1) If $R$ is an equivalence relation on $X$, then the equivalence class of an element $x\in X$ with respect to $R$ is the set of all elements of $X$ which are equivalent to $x$ under $R$.

The definition you have written for the set of all equivalence classes looks very strange. It surely shouldn't start with $\exists X$, since $X$ is the specific set you want to take equivalence classes in. I would just write

$$X/R = \{ [x]/R \mid x\in X \},$$ where $[x]/R$ denotes the equivalence class of $x$ with respect to $R$.

2) A partition of a set $X$ is just a collection of non-empty subsets of $X$ which are pairwise disjoint (i.e. non-intersecting) and whose union is the whole of $X$. For example, $\{ \{1,3\}, \{2,4\} \}$ is a partition of $\{1,2,3,4\}$, but $\{ \{1,2\}, \{2,3,4\} \}$ and $\{ \{1,2\}, \{2,3\} \}$ are not.

As people have mentioned in the comments, the collections equivalence classes of $X$ under an equivalence relation form a partition of $X$. Do you see why?

3) The equivalence relation generated by a partition $P$ of $X$ is simply the relation where we declare two elements of $X$ to be related if and only if they are in the same set in $P$. It's easy to check that the definition of a partition guarantees that this really is an equivalence relation.

Solution 4:

The definitions of the concepts in words are

1. The equivalence classes of an equivalence relation are subsets of the set on which the equivalence relation is defined, such that two elements are in the same equivalence class if and only if they are related by the equivalence relation.

2. A partition of a set is a collection of subsets of the set, whose union is the whole set, and such that no two subsets share any elements in common, and none of which are the empty set.

3. The relation induced by a partition is the relation given by "the two objects are related if they lie in the same cell of the partition" (where a "cell" is one of the subsets of the partitioned set that make up the partition.).