# Set Theory, Relations, Functions: Preliminaries: part VIIIA

(We continue from part VII of the same blog article series with same reference text).

Theorem 4:

A set M can be partitioned into classes by a relation R (acting as a criterion for assigning two elements to the same class) if and only R is an equivalence relation on M.

Proof of Theorem 4:

Every partition of M determines a binary relation on M, where $aRb$ means that “a belongs to the same class as b.” It is then obvious that R must be reflexive, symmetric and transitive, that is, R is an equivalence relation on M.

Conversely, let R be an equivalence relation on M, and let $K_{a}$ be the set of all elements $x \in M$ such that $xRa$ (clearly, $a \in K_{a}$, since R is reflexive). Then, two classes $K_{a}$ and $K_{b}$ are either identical or disjoint. In fact, suppose that an element c belongs to both $K_{a}$ and $K_{b}$, so that $cRa$ and $cRb$. But by symmetry of R, being an equivalence relation, we can infer that $aRc$ also and, further by transitivity, we say that $aRb$. If now, $x \in K_{a}$ then we have $xRa$ and hence, $xRb$ (since we already have $aRb$ and using transitivity).

Similarly, we can prove that $x \in K_{b}$ implies that $x \in K_{a}$.

Therefore, $K_{a}=K_{b}$ if $K_{a}$ and $K_{b}$ have an element in common. Therefore, the distinct sets $K_{a}$ form a partition of M into classes.

QED.

Remark:

Because of theorem 4, one often talks about the decomposition of a set M into equivalence classes.

There is an intimate connection between mappings and partitions into classes, as illustrated by the following examples:

Example 1:

Let f be a mapping of a set A into a set B and partition A into sets, each consisting of all elements with the same image $b=f(a) \in B$. This gives a partition of A into classes. For example, suppose f projects the xy-plane onto the x-axis by mapping the point $(x,y)$ into the point $(x,0)$. Then, the preimages of the points of the x-axis are vertical lines, and the representation of the plane as the union of these lines is the decomposition into classes corresponding to f.

Example 2:

Given any partition of a set A into classes, let B be the set of these classes and associate each element $a \in A$ with the class (that is, element of B) to which it belongs. This gives a mapping of A into B. For example, suppose we partition three-dimensional space into classes by assigning to the same class all points which are equidistant from the origin of coordinates. Then, every class is a sphere of a certain radius. The set of all these classes can be identified with the set of points on the half-line $[0, \infty)$ each point corresponding to a possible value of the radius. In this sense, the decomposition of 3-dimensional space into concentric spheres corresponds to the mapping of space into the half-line $[0,\infty)$.

Example 3:

Suppose that we assign all real numbers with the same fractional part to the same class. Then, the mapping corresponding to this partition has the effect of “winding” the real line onto a circle of unit circumference. (Note: The largest integer $\leq x$ is called the integral part of x, denoted by [x], and the quantity $x -[x]$ is called the fractional part of x).

In the next blog article, let us consider a tutorial problem set based on last two blogs of this series.

🙂 🙂 🙂

Nalin Pithwa

This site uses Akismet to reduce spam. Learn how your comment data is processed.