Aditya Makkar
Partitions and Equivalence Relations

I want to show how these two concepts are a single mathematical idea.

Partition

Definition 1: A partition of a nonempty set, XX, is a disjoint class {Xi}i∈I\{X_i\}_{i \in I} of non-empty subsets of XX whose union is X.X. Each of the XiX_i is called a partition set.

For example, if X=RX = \mathbb R, then XX can be partitioned as

X=⋃n∈Z[n,n+1).\begin{aligned} X = \bigcup_{n \in \mathbb{Z}}[n, n+1).\end{aligned}

Equivalence Relation

Definition 2: A binary relation, or simply relation, RR, in the set XX is a subset of X×X.X \times X.

For x,y∈Xx, y \in X, we denote the fact (x,y)∈R(x,y) \in R by writing xRy.x R y. A function may be defined as a special kind of binary relation.

Let's assume that a partition of our non-empty set XX is given, and we associate with this partition a relation, ∼\sim, in XX defined as follows: x∼yx \sim y if xx and yy belong to the same partition set. It can easily checked that the relation ∼\sim satisfies:

  1. x∼yx \sim y for every x∈Xx \in X (reflexivity);

  2. x∼y ⟹ y∼xx \sim y \implies y \sim x (symmetry);

  3. x∼yx \sim y and y∼zy \sim z ⟹ \implies x∼zx \sim z (transitivity).

Definition 3: Any relation in XX which possesses these three properties is called an equivalence relation in X.X.

Examples

  1. Let X=ZX = \mathbb{Z} and let x∼yx \sim y if 2∣x−y2 \vert x-y for x,y∈X.x,y \in X. Then clearly ∼\sim is an equivalence relation in X.X.

  2. Let XX, YY be any non-empty sets and ff be a mapping from XX onto Y.Y. Let x∼yx \sim y if f(x)=f(y)f(x) = f(y) for x,y∈X.x,y \in X. This defines an equivalence relation in X.X. Indeed, f(x)=f(x)f(x) = f(x), and so x∼x.x \sim x. If f(x)=f(y)f(x) = f(y) then f(y)=f(x)f(y) = f(x), and so x∼y ⟹ y∼x.x \sim y \implies y \sim x. Finally, if f(x)=f(y)f(x) = f(y) and f(y)=f(z)f(y) = f(z) then f(x)=f(z),f(x) = f(z), and so x∼yx \sim y and y∼zy \sim z implies x∼z.x \sim z. The first example is a special case of this one if we take X=ZX = \mathbb{Z}, Y={0,1}Y = \{0,1\} and f(x)=xmod 2.f(x) = x \mod 2.

“Relation” to Partition

We have just seen that each partition of XX has associated with it a natural equivalence relation in X.X. Let us now reverse the situation and show that a given equivalence relation in XX determines a natural partition of X.X.

Let ∼\sim be an equivalence relation in X.X. For every x∈Xx \in X define the set

[x]:={y∈X:y∼x}\begin{aligned} [x] := \{ y \in X : y \sim x\}\end{aligned}
called the equivalence set of x.x. We show that the class of all distinct equivalence sets forms a partition of X.X.

By reflexivity, x∈[x]x \in [x] for every x∈Xx \in X, and thus each equivalence set is non-empty and their union is X.X. We now need to show that any two equivalence sets [x1][x_1] and [x2][x_2] are either disjoint or identical. We prove this by showing that if [x1][x_1] and [x2][x_2] are not disjoint then they are identical. To this end, let zz be a common element of [x1][x_1] and [x2].[x_2]. Let yy be any element of [x1].[x_1]. Using transitivity,

y∼x1∼z∼x2.\begin{aligned} y \sim x_1 \sim z \sim x_2.\end{aligned}

Therefore, y∈[x2].y \in [x_2]. Since yy was an arbitrary element of [x1][x_1], we get [x1]⊆[x2].[x_1] \subseteq [x_2]. We can similarly show that [x2]⊆[x1].[x_2] \subseteq [x_1]. In short, [x1]=[x2].[x_1] = [x_2].

We have shown that there is no real distinction between partitions of a set and equivalence relations in the set. They are two equivalent approaches for the same mathematical idea. The approach we choose in an application depends entirely on our own convenience.