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.
Contents
Partitions
Definitions
Simple examples
Counting Partitions
Notation
Equivalence relations
Equivalence relations and partitions
An equivalence relation determines a partition
A partition determines an equivalence relation
The fundamental theorem on equivalence relations
Consciousness-raising examples
Answers to exercises
Abstraction of similarity
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.
Partitions
Definition: Partition
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 .
Alternative Definition: Partition
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 .
Remarks
¨
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}:
¨
¨
¨
¨
Remarks
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.
Non-examples
¨
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.
Representing partitions
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 Bell number B5 = 52.
¨
There are 25 different partitions of the set {1, 2, 3, 4, 5} that have
three blocks each ( is one of them). The Stirling
number S(5,3) = 25.
Blocks
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 .
Sequence notation
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.
Exercise PAR
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.
Equivalence relations
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.
Definition: Equivalence relation
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.
Examples
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.
Non-examples
¨
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.
An equivalence relation determines a
partition
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:
Definition: quotient set of an
equivalence relation
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:
Theorem
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
¨
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.
How to think about S/E
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.
Exercises
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
A partition determines an equivalence
relation
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 well-defined because
each element is in exactly one block of by PAR.2.
Theorem
For a partition of S,
the relation is an equivalence relation on S.
Proof
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.
One way to state the fundamental theorem
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.
In
short:
and
Note This pair of equations condenses
the information down to two cryptic statements. It is worthwhile spending a few minutes trying to spell out to yourself
in detail just what they say.
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.
Another way to state the fundamental theorem
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.
Partition of Z by remainders To Do
For now, read about this in Wikipedia here.
The quotient of the squaring function
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.
A foliation of the real plane
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?
Answer to Exercise IIZ
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.)
Answer to Exercise BTWO
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.
Answer to Exercise INTB.
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.
