V. Partitions and Equivalence Relations: My Notes

References:

  1. Topology and Modern Analysis, G F Simmons, Tata McGraw Hill Publications, India.
  2. Toplcs in Algebra, I N Herstein.
  3. Abstract Algebra, Dummit and Foote.
  4. Topology by James Munkres.

In the first part of this section, we consider a non-empty set X, and we study decompositions of X into non-empty subsets which fill it out and have no elements in common with one another. We give special attention to the tools (equivalence relation) which are normally used to generate such decompositions.

A partition of X is a disjoint class \{ X_{i} \} of non-empty subsets of X whose union if the full set X itself. The X_{i}‘s are called the partition sets. Expressed somewhat differently, a partition of X is the result of splitting it, or subdividing it, into non-empty subsets in such a way that each element of X belongs to one and only one of the given subsets. ]

If X is the set \{1,2,3,4,5 \}, then \{1,3,5 \}, \{2,4 \} and \{1,2,3 \} and \{ 4,5\} are two different partitions of X. If X is the set \Re of all real numbers, then we can partition \Re into the set of all rationals and the set of all irrationals, or into the infinitely many closed open intervals of the form [n, n+1) where n is an integer. If X is the set of all points in the coordinate plane, then we can partition X in such a way that each partition set consists of all points with the same x coordinate (vertical lines), or so that each partition set consists of all points with the same y coordinate (horizontal lines).

Other partitions of each of these sets will readily occur to the reader. In general, there are many different ways in which any given set can be partitioned. These manufactored examples are admittedly rather uninspiring and serve only to make our ideas more concrete. Later in this section we consider some others which are more germane to our present purposes.

A binary relation in the set X is a mathematical symbol or verbal phrase, which we denote by R in this paragraph, such that for each ordered pair (x,y) of elements of X the statement x \hspace{0.1in} R \hspace{0.1in} y is meaningful, in the sense that it can be classified definitely as true or false. For such a binary relation, x \hspace{0.1in} R \hspace{0.1in}y symbolizes the assertion that x is related by R to y, and x \not {R} \hspace{0.1in}y the negation of this, namely, the assertion that x is not related by R to y. Many examples of binary relations can be given, some familiar and others less so, some mathematical and others not. For instance, if X is the set of all integers and R is interpreted to mean “is less than,” which of course is usually denoted by the symbol <, then we clearly have 6<7 and 5 \not < 2. We have been speaking of binary relations, which are so named because they apply only to ordered pairs of elements, rather than to ordered triples, etc. In our work, we drop the qualifying adjective and speak simply of a relation in X, since we shall have occasion to consider only relations of this kind. {NB: Some writers prefer to regard a relation R in X as a subset R of X \times X. From this point of view, x R y and x \not {R} y are simply equivalent ways of writing (x,y) \in R and (x,y) \notin R. This definition has the advantage of being more tangible than our definition, and the disadvantage that few people really think of a relation in this way.” )

We now assume that a partition of our non-empty set X is given, and we associate with this partition a relation on X. This relation is defined to be in the following way: we say that x is equivalent to y and write this as x \sim y (the symbol \sim is pronounced “wiggle”.), if x and y belong to the same partition set. It is obvious that the relation \sim has the following properties:

a) x \sim x for every x (reflexivity)

b) x \sim y \Longrightarrow y \sim x (symmetry)

c) x \sim y \hspace{0.1in} and \hspace{0.1in} y \sim z \Longrightarrow x \sim z (transitivity)

This particular relation in X arose in a special way, in connection with a given partition of X, and its properties are immediate consequences of the definition. Any relation whatever in X which possesses these three properties is called an equivalence relation in X.

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

Let \sim be an equivalence relation in X; that is, assume that it is reflexive, symmetric, and transitive in the sense described above. If x is an element of X, the subset of X defined by [x] = \{ y: y \sim x\} is called the equivalence set of x. The equivalence set of x is thus the set of all elements which are equivalent to x. We show that the class of all distinct equivalence sets forms a partition of X. By reflexivity, x \in [x] for each element x in X, so each equivalence set is non-empty and their union is X. It remains to be shown that any two equivalence sets [x_{1}] and [x_{2}] are either disjoint or identical. We prove this by showing that if [x_{1}] and [x_{2}] are not disjoint, then they must be identical. Suppose that [x_{1}] and [x_{2}] are not disjoint, that is, suppose that they have a common element z. Since x belongs to both equivalence sets, z \sim x_{1} and z \sim x_{2}, and by symmetry x_{1} \sim z. Let y be any element of x_{1}, so that y \sim x_{1}. Since y \sim x_{1} and x_{1} \sim z, transitivity shows that y \sim z. By another application of transitivity, y \sim z and z \sim x_{2}, imply that y \sim x_{2} so that y is in [x_{2}]. Since y was arbitrarily chosen in [x_{1}], we see by this that [x_{1}] \subseteq [x_{2}]. The same reasoning shows that [x_{2}] \subseteq [x_{1}] and from this we conclude that [x_{1}] = [x_{2}].

The above discussion demonstrates that there is no real distinction (other than a difference in language) between partitions of a set and equivalence relation by regarding elements as equivalent if they belong to the same partition set, and if we start with an equivalence relation, we get a partition by grouping together into subsets all elements which are equivalent to one another. We have here a single mathematical idea, which we have been considering from two different points of view, and the approach we choose in any particular application depends entirely on our own convenience. In practice, it is almost invariably the case that we use equivalence relations (which are usually easy to define) to obtain partitions (which are sometimes difficult to describe fully).

We now turn to several of the more important simple examples of equivalence relations.

Let I be the set of integers. If a and b are elements of this set, we write a = b (and say that a equals b) if a and b are the same integer. Thus, 2+3=5 means that the expression on the left and right are simply different ways of writing the same integer. It is apparent that = used in this sense is an equivalence relation in the set I:

i) a=a for every a

ii) a=b \Longrightarrow b=a

iii) a=b \hspace{0.1in} b=c \Longrightarrow a=c.

Clearly, each equivalence set consists of precisely one integer.

Another familiar example is this relation of equality commonly used for fractions. We remind the reader that, strictly speaking, a fraction is merely a symbol of the form a/b, where a and b are integers and b is not zero. The fractions 2/3 and 4/6 are obviously not identical, but nevertheless we consider them to be equal. In general, we say that two fractions a/b and c/d are equal, written \frac{a}{b} = \frac{c}{d}, if ad and bc are equal as integers in the usual sense (see the paragraph above). (HW quiz: show this is an equivalence relation on the set of fractions). An equivalence set of fractions is what we call a rational number. Every day usage ignores the distinction between fractions and rational numbers, but it is important to recognize that from the strict point of view it is the rational numbers (and not the fractions) which form part of the real number system.

Our final example has a deeper significance, for it provides us with the basic tool for our work of the next two sections.

For the remainder of all this section, we consider a relation between pairs of non-empty sets, and each set mentioned (whether we say so explicitly or not) is assumed to be non-empty. If X and Y are two sets, we say that X is numerically equivalent to Y if there exists a one-to-one correspondence between X and Y, that is, if there exists a one-to-one mapping of X onto Y. This relation is reflexive, since the identity mapping i_{X}: X \rightarrow X is one-to-one onto; it is symmetric since if f: X \rightarrow Y is one-to-one onto, then its inverse mapping f^{-1}: Y \rightarrow X is also one-to-one onto; and it is transitive, since if f: X \rightarrow Y and g: Y \rightarrow Z are one-to-one onto, then gf: X \rightarrow Z is also one-to-one onto. Numerical equivalence has all the properties of an equivalence relation, and if we consider it as an equivalence relation in the class of all non-empty subsets of some universal set U, it groups together into equivalence sets all those subsets of U which have the “same number of elements.” After we state and prove the following very useful but rather technical theorem, we shall continue in Sections 6 and 7 with an exploration of the implications of these ideas.

The theorem we have in mind — the Schroeder-Bernstein theorem: If X and Y are two sets each of which is numerically equivalent to a subset of the other, then all of X is numerically equivalent to all of Y. There are several proofs of this classic theorem, some of which are quite difficult. The very elegant proof we give is essentially due to Birkhoff and MacLane.

Proof:

Assume that f: X \rightarrow Y is a one-to-one mapping of X into Y, and that g: Y \rightarrow X is a one-to-one mapping of Y into X. We want to produce a mapping F: X \rightarrow Y which is one-to-one onto. We may assume that neither f nor g is onto, since if f is, we can define F to f, and if g is, we can define F to be g^{-1}. Since both f and g are one-to-one, it is permissible to use the mappings f^{-1} and g^{-1} as long as we keep in mind that f^{-1} is defined only on f(X) and g^{-1} is defined only on g(Y). We obtain the mapping F by splitting both X and Y into subsets which we characterize in terms of the ancestry of their elements. Let x be an element of X. We apply g^{-1} (if we can) to get the element g^{-1}(x) in Y. If g^{-1}(x) exists, we call it the first ancestor of x. The element x itself we call the zeroth ancestor of x. We now apply f^{-1} to g^{-1}(x) if we can, and if (f^{-1}g^{-1})(x) exists, we call it the second ancestor of x. We now apply g^{-1} to (f^{-1}g^{-1})(x) if we can, and if (g^{-1}f^{-1}g^{-1})(x) exists, we call it the third ancestor of x. As we continue this process of tracing back the ancestry of x, it becomes apparent that there are three possibilities — (1) x has infinitely many ancestors. We denote by X_{i}, the subset of X, which consists of all elements with infinitely many ancestors (2) x has an even number of ancestors, this means that x has a last ancestor (that is, one which itself has no first ancestor) in X. We denote by X_{e} the subset of X consisting of all elements with an even number of ancestors. (3) x has an odd number of ancestors; this means that x has a last ancestor in Y. We denote by X_{o} the subset of X which consists of all elements with an odd number of ancestors. The three sets X_{i}, X_{e}, X_{o} form a disjoint class whose union is X. We decompose Y in just the same way into three subsets Y_{i}, Y_{e}, Y_{o}. It is easy to see that f maps X_{i} onto Y_{i}, and X_{e} onto Y_{e}, and that g^{-1} maps X_{o} onto Y_{o}, and we complete the proof by defining F in the following piecemeal manner:

F(x) = f(x) if x \in X_{i} \bigcup X_{e}

and F(x) = g^{-1}(x) if x \in X_{o}.

QED.

The Schroeder Bernstein theorem has great theoretical and practical significance. It main value for us lies in its role as a tool by means of which we can prove numerical equivalence with a minimum of effort for many specific sets. We put it to work in Section 7.

Regards,

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.