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

 

 

 

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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