help with abstract math
Produced by Charles Wells. Home Website TOC Website Index Blog
Posted 21 May 2009
EQUIVALENCE RELATIONS

A partition of a set S is a set of nonempty subsets of S which are pairwise disjoint and whose union is all of S. An equivalence relation on a set S is a reflexive, symmetric, transitive relation on S. Both of these structures is motivated by the idea of grouping objects that are alike in some respect. Partition and equivalence relation provide exactly the same class of structures. Each definition is a different way of presenting the same type of structure. This chapter spells this out in detail.
Equivalence relations and partitions
An equivalence relation determines a partition
A partition determines an equivalence relation
The fundamental theorem on equivalence relations
Consciousnessraising examples
This section concerns the idea of objects being alike in some respect.
¨ With poker chips, some are red, some are white and some are blue. You can group them into three subsets the red ones, the white ones, and the blue ones. You can say two red chips are alike in having the same color, and a red and a blue chip are not alike because they have different colors.
¨ With natural numbers, some are divisible by 2 and some are not. You can group them into even ones and odd ones. We can say 4 and 10 are alike in that they are both even, and 5 and 11 are alike in that they are both odd. However, 4 and 5 are not alike in that respect.
In both these examples, we can abstract the idea of being alike in some respect by grouping the like objects together (clumping) or by making a statement that two given objects are alike or different. (See two.) These two ideas can be abstracted into the idea of partition and of equivalence relation.
If S is a set, a family of subsets of S (called the blocks or equivalence classes of ) is a partition of S if it satisfies the following axioms:
PAR.1 Every block of is nonempty.
PAR.2 Every element of S is an element of exactly one block of .
If S is a set, a family of subsets of S is a partition of S if
APAR.1 Every block of is nonempty.
APAR.2 S is the union of all the blocks in .
APAR.3 If B and C are blocks in and , then .

¨ is the Greek letter capital pi.
¨ The word “partition” has several other meanings in math.
¨ In everyday English, the word “partition” can refer to the division of something into pieces, but it can also refer to a wall that divides a room in two. Don’t let this mess with your mind: the mathematical idea has nothing to do with walls.
¨ A partition is a set of blocks. Don’t refer to one block as a partition.
¨ APAR.3 means by definition that is pairwise disjoint.
Here are four partitions of the set {1, 2, 3, 4, 5}:
¨
¨
¨
¨
Think about the remarks below until you see why they are correct:
¨ and are the same partition (see here).
¨ and are different partitions, because they have different blocks.
¨ In , as in any partition with two blocks, each block is the complement of the other one.
¨ is the only partition of {1, 2, 3, 4, 5} with exactly one block. Every nonempty set has a partition consisting of the whole set as the only block.
¨ is the only partition with five blocks. Every nonempty set has a partition whose blocks are all the singleton subsets of the set.
¨ The empty set has just one partition, whose set of blocks is empty.
¨ is not a partition of the set {1, 2, 3, 4, 5} because the element 4 is not in any block. It is, however, a partition of the set {1, 2, 3, 5}.
¨ is not a partition (of any set) because 4 is in two different blocks, violating PAR.1. It violates APAR.3, too, because but .
¨ is not a partition because one of its blocks is empty.
Small finite partitions can be represented by diagrams like the following, which represents :
In this diagram, the circles are merely for grouping. The fact that they are circles has no significance. All that matters is which elements are in which circles.
The functions that count partitions are the Bell numbers and the Stirling numbers of the second kind.
¨
The set {1, 2, 3, 4, 5} has 52 different partitions altogether. The
¨
There are 25 different partitions of the set {1, 2, 3, 4, 5} that have
three blocks each ( is one of them). The
If is a partition of a set S and , then there is a unique block of that contains x as an element. This block is denoted by . For example, , and .
It may happen that an author refers to a partition as if it were a sequence of sets. For example, they might say is the partition , where , and . Be warned: the order the blocks are listed in doesn’t matter, even though in sequence notation it usually does matter.
Provide an example with the given property of a partition of the set of real numbers. Answers.
a) has at least one block with exactly three elements.
b) {1,2} and {3} are blocks of .
c) has at least one finite block and at least one infinite block.
d) has an infinite number of finite blocks.
e) has an infinite number of infinite blocks.
Find a partition of that has an infinite number of infinite blocks. Answer.
The concept of equivalence relation is an abstraction of the idea of two math objects being like each other in some respect.
¨ If an object a is like an object b in some specified way, then b is like a in that respect.
¨ a is like itself in every respect!
So if you want to give an abstract definition of a type of relation intended to capture the idea of being alike in some respect, two of the properties you could require are reflexivity and symmetry. The nearness relations are reflexive and symmetric. Relations with those two properties are studied in applied math NEED REFERENCE but here we are going to require the additional property of transitivity, which roughly speaking forces the objects to fall into discrete types, making a partition of the set of objects being studied.
An equivalence relation on a set S is a reflexive, symmetric, transitive relation on S.
Note This definition is an abstraction of the idea of “being like each other”. You don’t have to have some property or mode of similarity in mind to define an equivalence relation.
See also these examples.
¨ The relation “equals” on any set is an equivalence relation. On the set {1, 2, 3}, “equals” is the relation {(1,1),(2,2),(3,3)}.
¨ The relation E on the real numbers defined by if and only if is an equivalence relation. In this case, x and y are like each other in this respect: They have the same square.
¨ Let A = {1, 2, 3, 4, 5} and let . Then is an equivalence relation on A. You can define this relation more easily by saying: “ if and only if x and y are in the same block of (above).” This is the key to the relationship between equivalence relations and partitions.
¨ For any integer k, congruence (mod k) is an equivalence relation, discussed here.
¨ The relation “ ” on the set of real numbers is not an equivalence relation. It is reflexive and transitive but not symmetric: For example, is true but is false. This relation is an example of an ordering.
¨ The relation E defined on the real numbers by if and only if and is not an equivalence relation. It is symmetric and transitive but not reflexive. It is a partial equivalence relation.
¨ The relation D defined on a set of sets by x D y if and only if x and y are disjoint is not an equivalence relation. It is reflexive and symmetric but not transitive.
This is the fundamental fact connecting equivalence relations and partitions:
Every equivalence relation on a set S determines a specific partition of S and every partition of S determines a specific equivalence relation on S. These operations are inverse to each other.
This statement is not a theorem because I haven’t told you how each equivalence relation induces a partition and vice versa. The proper statement is the Fundamental Theorem on Equivalence Relations below, but to state it requires several definitions. A more detailed explanation with proofs is given here.
If an equivalence relation E is given on a set S, the elements of S can be collected together into subsets, with two elements in the same subset if and only if they are related by E. This collection of subsets of S is a set denoted S/E, the quotient set of S by E. Here is the formal definition of S/E:
Let E be an equivalence relation on a set S. For each , the equivalence class of x mod E, denoted by , is the subset of S. The quotient set of E is the set of equivalence classes of x mod E for all .
I have now defined two notations that look like for some symbol s. If s denotes a partition, is the block of the partition that contains x. If s denotes an equivalence relation, denotes the set . Thus the notation “ ” is overloaded. However, the fundamental theorem below says don’t worry, be happy about this.
Let A = {1, 2, 3, 4, 5} and let
(We looked at this example before.) Notice that , because by definition
and you can see that the only three pairs in whose second coordinate is 2 are (1,2), (2,2) and (5,2). Reasoning in the same way, we have
so by definition the quotient set of is the partition , which I called above. In other words, .
The fact that the quotient set is a partition is always true:
If S is a set and E is an equivalence relation on S, then the quotient set S/E is a partition of S.
¨ Proof of Par.1: Any block of S/E is of the form for some . By definition, . Since E is reflexive, x E x, so is nonempty because it contains x.
¨ Proof of Par.2: We know that x is in at least one set because by reflexivity. Suppose and . We must show that as sets. That means by definition of set equality we must show that for any element w, if and only if . Suppose (modus ponens) that . Then by comprehension, w E y. Then , so x E y. By symmetry, y E x. So by transitivity, w E x. Since , we know x E z. So by transitivity, w E z, which means . That is half the proof. You do the other half.
If E is an equivalence relation on S, you can think of the quotient set S/E as obtained by merging equivalent elements of S. In the example above, 3 and 4 are equivalent so they are merged into the equivalence class {3, 4}, which is both and .
One often says that one identifies equivalent elements. Here, “identify” means “make identical” rather than “discover the identity of”. Mathematicians may also say we glue equivalent elements together. Thus we form the Möbius strip by gluing the left and right edge of the unit square together in a certain way.
BTWO Let S = {1, 2, 3, 4}. Find two different equivalence relations E and E' with the property that the subset {1, 2} is a block of both S/E and S/E'. Answer.
INTB Give an example of an equivalence relation E on the set of real numbers with the property that the interval [0, 1] is one of the equivalence classes of E. Answer
Given a partition , you get an equivalence relation by the definition:
In other words, if and only if x and y are in the same block of . The relation is welldefined because
each element is in exactly one block of by PAR.2.
For a partition of S,
the relation is an equivalence relation on S.
All three steps in this proof depend on the fact that each element of S is in exactly one block (Par.2).
¨ Since x is in the same block as itself, , so is reflexive.
¨ If , then x and y are in the same one and only block, which is the same thing as saying that y and x are in the same block, so . So is symmetric.
¨ If and , then x is in the same block as y and z is in the same block as y. By Par.2, x and z must be in the same block, so Hence is transitive.
Above we showed how to take an equivalence relation E and construct a partition S/E. Then we showed how to take a partition of a set S and construct an equivalence relation .
The fundamental
theorem on equivalence relations says that if you perform one construction
and then the other you
get back what you started with. In other
words:
¨ If you have an equivalence relation E, construct the quotient set S/E, which is a partition, and then construct the equivalence relation corresponding to that partition, you get the equivalence relation E you started with.
¨ If you have a partition of S, construct the corresponding equivalence relation and then construct the quotient set _{ }of , you get the partition back again.
Lots of math in research papers is excruciatingly succinct.
You need to practice unwinding what
they say.

The proof of the fundamental theorem involves the same sort of arguments given above.
Let S be a set, let be the set of all partitions of S, and let E(S) be the set of all equivalence relations on S. The fundamental theorem says that the two constructions given above produce a function and a function that are inverses to each other. This means they are bijections. In fact, E and are functors that are naturally isomorphic by these bijections.
If S = {1, 2}, then
¨ is the set {{{1}, {2}}, {{1, 2}}}. It has two elements, the partition {{1}, {2}} and the partition {{1, 2}}.
¨ E(S) is the set {{1, 1), (2, 2)}, {(1, 1), (2, 2), (1, 2), (2, 1)}}. It contains the two equivalence relations {1, 1), (2, 2)} and {(1, 1), (2, 2), (1, 2), (2, 1)}.
¨ R[{{1}, {2}}] = {(1, 1), (2, 2)} and R[{{1, 2}}] = {(1, 1), (2, 2), (1, 2), (2, 1)}.
¨ Q[ {(1, 1), (2, 2)} ] = {{1}, {2}} and Q[ {(1, 1), (2, 2), (1, 2), (2, 1)}] = {{1, 2}}.
According to the fundamental theorem,
An equivalence relation is the same thing as a partition
Of course, they are
described differently, but once you have an equivalence relation you have a partition
and vice versa. All you know about the partition
is determined by the data of the equivalence relation and all you know about
the equivalence relation is determined by the data of the partition.
The relationship
between equivalence relations and partitions is a basic and important example
of the fact that two
different looking kinds of structures can actually be two different
descriptions of the same kind of structure.
For now, read about this in Wikipedia here.
Let be the partition of whose blocks are all subsets of the form for all . is the quotient set of the squaring function defined by . Observe that:
¨ has an infinite number of blocks.
¨ , and are blocks of .
¨ Every block of except has exactly two elements.
For any given real number c, let . This defines an infinite family of functions . For a given c, the graph of is the subset , which I will denote by , of the real plane . You can check that these subsets are a partition of . The picture below shows some of the blocks.
¨ These blocks are dense in , meaning that between any two of them there is an infinite number of others. There is no block next to a given block. They are dense in just like the points on the real line are dense.
¨
This is a baby example of a foliation (Wikipedia, MathWorld).
Answers to Exercise PAR. Each problem has many possible answers. I give only one for each.
a)
Let and the set of all real numbers except
1, 3 and 5.
b) Let
.
and the set of all real numbers except
1, 2 and 3.
c) The answers to a) and to b) also work for this one.
d) For each positive integer n, let , and let the set of all real numbers that are not integers.
e) For each integer n, let . Can you think of a partition of the integers that has an infinite number of infinite blocks?
For each prime p, let . Let . (See set subtraction). Then set . Then is a partition of with an infinite number of infinite blocks. Note: I have deliberately used succinct notation that you may have to unwind extensively before you understand it. (Pretend you are a kitten attacking a ball of yarn.)
There are exactly two
such equivalence relations, namely {(1,1), (2,2), (3,3), (4,4), (1,2), (2,1)}
and {(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (3,4), (4,3)} . Note that {(1,1), (2,2), (3,3), (4,4),
(1,2), (2,1), (1,3), (3,1), (2,3), (3,2)} is not an
answer. Its partition is {{1, 2, 3},
{4}}, and althouogh 1 and 2 are indeed in the same block, {1, 2} is not a
block.
The easiest way to answer questions like this is to put everything outside of [0, 1] into singleton blocks, so the answer would be
There is an
infinite number of other answers.