©©aª,©bª,©cª©dªª,
©©a, b, c, dªª,
to name a few. Intuitively, a partition is just a dividing up of A into pieces.
Example 11.14
Consider the equivalence relations in Figure 11.2. Each
of these is a relation on the set A = © − 1, 1, 2, 3, 4ª. The equivalence classes
of each relation are listed on the right side of the figure. Observe that,
in each case, the set of equivalence classes forms a partition of A. For
©©
example, the relation R1 yields the partition
− 1ª, ©1ª, ©2ª, ©3ª, ©4ªª of A.
©©
Likewise the equivalence classes of R2 form the partition
− 1, 1, 3ª, ©2, 4ªª.
Example 11.15
Recall that we worked out the equivalence classes of the
equivalence relation ≡ (mod 3) on the set Z. These equivalence classes
give the following partition of Z:
©© ...,−3,0,3,6,9,...ª,©...,−2,1,4,7,10,...ª,©...,−1,2,5,8,11,...ªª.
©
We can write it more compactly as [0], [1], [2]ª.
Our examples and experience suggest that the equivalence classes of
an equivalence relation on a set form a partition of that set. This is indeed
the case, and we now prove it.
Theorem 11.2
Suppose R is an equivalence relation on a set A. Then
©
the set [a] : a ∈ Aª of equivalence classes of R forms a partition of A.
Proof.
©
To show that [a] : a ∈ Aª is a partition of A we need to show two
things: We need to show that the union of all the sets [a] equals A, and
we need to show that if [a] 6= [b], then [a] ∩ [b] = ;.
190
Relations
S
Notationally, the union of all the sets [a] is
a∈A[a], so we need to prove
Sa∈A[a] = A. Suppose x ∈ Sa∈A[a]. This means x ∈ [a] for some a ∈ A. Since
[a] ⊆ A
S
, it then follows that x ∈ A. Thus
a∈A[a] ⊆ A. On the other hand,
suppose x ∈ A. As x ∈ [x], we know x ∈ [a] for some a ∈ A (namely a = x).
S
Therefore x ∈ Sa∈A[a], and this shows A ⊆ Sa∈A[a]. Since
a∈A[a] ⊆ A and
A ⊆ S
S
a∈A[a], it follows that
a∈A[a] = A.
Next we need to show that if [a] 6= [b] then [a] ∩ [b] = ;.
Let’s use
contrapositive proof. Suppose it’s not the case that [a] ∩ [b] = ;, so there is
some element c with c ∈ [a] ∩ [b]. Thus c ∈ [a] and c ∈ [b]. Now, c ∈ [a] means
cRa, and then aRc since R is symmetric. Also c ∈ [b] means cRb. Now
we have aR c and cRb, so aRb (because R is transitive). By Theorem 11.1,
aRb implies [a] = [b]. Thus [a] 6= [b] is not true.
We’ve now shown that the union of all the equivalence classes is A,
and the intersection of two different equivalence classes is ;. Therefore
the set of equivalence classes is a partition of A.
■
Theorem 11.2 says the equivalence classes of any equivalence relation
on a set A form a partition of A. Conversely, any partition of A describes
an equivalence relation R where xR y if and only if x and y belong to the
same set in the partition. (See Exercise 4 for this section, below.) Thus
equivalence relations and partitions are really just two different ways of
looking at the same thing. In your future mathematical studies, you may
find yourself easily switching between these two points of view.
Exercises for Section 11.3
1. List all the partitions of the set A = ©a, bª. Compare your answer to the answer
to Exercise 5 of Section 11.2.
2. List all the partitions of the set A = ©a, b, cª. Compare your answer to the
answer to Exercise 6 of Section 11.2.
3. Describe the partition of Z resulting from the equivalence relation ≡ (mod 4).
4. Suppose P is a partition of a set A. Define a relation R on A by declaring xR y
if and only if x, y ∈ X for some X ∈ P. Prove R is an equivalence relation on A.
Then prove that P is the set of equivalence classes of R.
5. Consider the partition P = ©©...,−4,−2,0,2,4,...ª,©...,−5,−3,−1,1,3,5,...ªª of Z.
Let R be the equivalence relation whose equivalence classes are the two ele-
ments of P. What familiar equivalence relation is R?
The Integers Modulo n
191
11.4 The Integers Modulo n
Example 11.8 proved that for a given n ∈ N, the relation ≡ (mod n) is
reflexive, symmetric and transitive, so it is an equivalence relation. This
is a particularly significant equivalence relation in mathematics, and in
the present section we deduce some of its properties.
To make matters simpler, let’s pick a concrete n, say n = 5. Let’s begin
by looking at the equivalence classes of the relation ≡ (mod 5). There are
five equivalence classes, as follows:
[0]
=
©x ∈ Z : x ≡ 0 (mod 5))ª = ©x ∈ Z : 5 | (x − 0)ª = ©...,−10,−5,0,5,10,15,...ª,
[1]
=
©x ∈ Z : x ≡ 1 (mod 5))ª = ©x ∈ Z : 5 | (x − 1)ª = ©..., −9,−4,1,6,11,16,...ª,
[2]
=
©x ∈ Z : x ≡ 2 (mod 5))ª = ©x ∈ Z : 5 | (x − 2)ª = ©..., −8,−3,2,7,12,17,...ª,
[3]
=
©x ∈ Z : x ≡ 3 (mod 5))ª = ©x ∈ Z : 5 | (x − 3)ª = ©..., −7,−2,3,8,13,18,...ª,
[4]
=
©x ∈ Z : x ≡ 4 (mod 5))ª = ©x ∈ Z : 5 | (x − 4)ª = ©..., −6,−1,4,9,14,19,...ª.
Notice how these equivalence classes form a partition of the set Z.
We label the five equivalence classes as [0], [1], [2], [3] and [4], but you
know of course that there are other ways to label them. For example,
[0] = [5] = [10] = [15], and so on; and [1] = [6] = [−4], etc. Still, for this
discussion we denote the five classes as [0], [1], [2], [3] and [4].
These five classes form a set, which we shall denote as Z5. Thus
Z5 = ©[0],[1],[2],[3],[4]ª
is a set of five sets. The interesting thing about Z5 is that even though its
elements are sets (and not numbers), it is possible to add and multiply
them. In fact, we can define the following rules that tell how elements of
Z5 can be added and multiplied.
[a] + [b] = [a + b]
[a] · [b]
=
[ a · b ]
For example, [2] + [1] = [2 + 1] = [3], and [2] · [2] = [2 · 2] = [4]. We stress
that in doing this we are adding and multiplying sets (more precisely
equivalence classes), not numbers. We added (or multiplied) two elements
of Z5 and obtained another element of Z5.
Here is a trickier example. Observe that [2] + [3] = [5]. This time we
added elements [2], [3] ∈ Z5, and got the element [5] ∈ Z5. That was easy,
except where is our answer [5] in the set Z5 = ©[0], [1], [2], [3], [4]ª? Since
[5] = [0], it is more appropriate to write [2] + [3] = [0].
192
Relations
In a similar vein, [2] · [3] = [6] would be written as [2] · [3] = [1] because
[6] = [1]. Test your skill with this by verifying the following addition and
multiplication tables for
Z5.
+
[0]
[1]
[2]
[3]
[4]
·
[0]
[1]
[2]
[3]
[4]
[0]
[0]
[1]
[2]
[3]
[4]
[0]
[0]
[0]
[0]
[0]
[0]
[1]
[1]
[2]
[3]
[4]
[0]
[1]
[0]
[1]
[2]
[3]
[4]
[2]
[2]
[3]
[4]
[0]
[1]
[2]
[0]
[2]
[4]
[1]
[3]
[3]
[3]
[4]
[0]
[1]
[2]
[3]
[0]
[3]
[1]
[4]
[2]
[4]
[4]
[0]
[1]
[2]
[3]
[4]
[0]
[4]
[3]
[2]
[1]
We call the set Z5 = ©[0], [1], [2], [3], [4]ª the integers modulo 5. As our
tables suggest, Z5 is more than just a set: It is a little number system
with its own addition and multiplication. In this way it is like the familiar
set Z which also comes equipped with an addition and a multiplication.
Of course, there is nothing special about the number 5. We can also
define Zn for any natural number n. Here is the definition:
Definition 11.6
Let n ∈ N. The equivalence classes of the equivalence
relation ≡ (mod n) are [0], [1], [2], . . . , [n − 1]. The integers modulo n is the
set Zn = ©[0], [1], [2], . . . , [n − 1]ª. Elements of Zn can be added by the rule
[a] + [b] = [a + b] and multiplied by the rule [a] · [b] = [ab].
Given a natural number n, the set Zn is a number system containing n
elements. It has many of the algebraic properties that Z, R and Q possess.
For example, it is probably obvious to you already that elements of Zn obey
the commutative laws [a] + [b] = [b] + [a] and [a] · [b] = [b] · [a]. You can also
verify the distributive law [a] · ([b] + [c]) = [a] · [b] + [a] · [c], as follows:
[a] · ([b] + [c]) = [a] · [b + c]
= [a(b + c)]
= [ab + ac]
= [ab] + [ac]
= [a] · [b] + [a] · [c].
The integers modulo n are significant because they more closely fit certain
applications than do other number systems such as Z or R. If you go on to
The Integers Modulo n
193
take a course in abstract algebra, then you will work extensively with Zn
as well as other, more exotic, number systems. (In such a course you will
also use all of the proof techniques that we have discussed, as well as the
ideas of equivalence relations.)
To close this section we take up an issue that may have bothered
you earlier. It has to do with our definitions of addition [a] + [b] = [a + b]
and multiplication [a] · [b] = [ab]. These definitions define addition and
multiplication of equivalence classes in terms of representatives a and b
in the equivalence classes. Since there are many different ways to choose
such representatives, we may well wonder if addition and multiplication
are consistently defined. For example, suppose two people, Alice and Bob,
want to multiply the elements [2] and [3] in Z5. Alice does the calculation
as [2] · [3] = [6] = [1], so her final answer is [1]. Bob does it differently.
Since [2] = [7] and [3] = [8], he works out [2] · [3] as [7] · [8] = [56]. Since 56 ≡ 1
(mod 5), Bob’s answer is [56] = [1], and that agrees with Alice’s answer. Will
their answers always agree or did they just get lucky (with the arithmetic)?
The fact is that no matter how they do the multiplication in Zn, their
answers will agree. To see why, suppose Alice and Bob want to multiply
the elements [a], [b] ∈ Zn, and suppose [a] = [a0] and [b] = [b0]. Alice and Bob
do the multiplication as follows:
Alice:
[a] · [b] = [ab],
Bob:
[a0] · [b0] = [a0b0].
We need to show that their answers agree, that is, we need to show
[ab] = [a0b0]. Since [a] = [a0], we know by Theorem 11.1 that a ≡ a0 (mod n).
Thus n | (a − a0), so a − a0 = nk for some integer k. Likewise, as [b] = [b0], we
know b ≡ b0 (mod n), or n | (b − b0), so b − b0 = n ` for some integer `. Thus
we get a = a0 + nk and b = b0 + n `. Therefore:
ab
= (a0 + nk)(b0 + n `)
= a0b0 + a0n ` + nkb0 + n2k `,
hence ab − a0b0
= n(a0 ` + kb0 + nk `).
This shows n | (ab − a0b0), so ab ≡ a0b0 (mod n), and from that we conclude
[ab] = [a0b0]. Consequently Alice and Bob really do get the same answer, so
we can be assured that the definition of multiplication in Zn is consistent.
Exercise 8 below asks you to show that addition in Zn is similarly
consistent.
194
Relations
Exercises for Section 11.4
1. Write the addition and multiplication tables for Z2.
2. Write the addition and multiplication tables for Z3.
3. Write the addition and multiplication tables for Z4.
4. Write the addition and multiplication tables for Z6.
5. Suppose [a],[b] ∈ Z5 and [a] · [b] = [0]. Is it necessarily true that either [a] = [0]
or [b] = [0]?
6. Suppose [a],[b] ∈ Z6 and [a] · [b] = [0]. Is it necessarily true that either [a] = [0]
or [b] = [0]?
7. Do the following calculations in Z9, in each case expressing your answer as [a]
with 0 ≤ a ≤ 8.
(a) [8] + [8]
(b) [24] + [11]
(c) [21] · [15]
(d) [8] · [8]
8. Suppose [a],[b] ∈ Zn, and [a] = [a0] and [b] = [b0]. Alice adds [a] and [b] as
[a] + [b] = [a + b]. Bob adds them as [a0] + [b0] = [a0 + b0]. Show that their answers
[a + b] and [a0 + b0] are the same.
11.5 Relations Between Sets
In the beginning of this chapter, we defined a relation on a set A to
be a subset R ⊆ A × A. This created a framework that could model any
situation in which elements of A are compared to themselves. In this
setting, the statement xR y has elements x and y from A on either side
of the R because R compares elements from A.
But there are other
relational symbols that don’t work this way. Consider ∈. The statement
5 ∈ Z expresses a relationship between 5 and Z (namely that the element 5
is in the set Z) but 5 and Z are not in any way naturally regarded as both
elements of some set A. To overcome this difficulty, we generalize the idea
of a relation on A to a relation from A to B .
Definition 11.7
A relation from a set A to a set B is a subset R ⊆ A × B.
We often abbreviate the statement (x, y) ∈ R as xR y. The statement (x, y) ∉ R
is abbreviated as x 6R y.
Example 11.16
Suppose A = ©1, 2ª and B = P(A) = ©;, ©1ª, ©2ª, ©1, 2ªª. Then
R = ©(1,©1ª),(2,©2ª),(1,©1,2ª),(2,©1,2ª)ª ⊆ A×B is a relation from A to B. Note
that we have 1R©1ª, 2R©2ª, 1R©1, 2ª and 2R©1, 2ª. The relation R is the
familiar relation ∈ for the set A, that is, x R X means exactly the same
thing as x ∈ X .
Relations Between Sets
195
Diagrams for relations from A to B differ from diagrams for relations
on A. Since there are two sets A and B in a relation from A to B, we have
to draw labeled nodes for each of the two sets. Then we draw arrows from x
to y whenever xR y. The following figure illustrates this for Example 11.16.
A
B
;
©
1
1ª
©
2
2ª
©1,2ª
Figure 11.3. A relation from A to B
The ideas from this chapter show that any relation (whether it is a
familiar one like ≥, ≤, =, |, ∈ or ⊆, or a more exotic one) is really just a
set. Therefore the theory of relations is a part of the theory of sets. In
the next chapter, we will see that this idea touches on another important
mathematical construction, namely functions. We will define a function to
be a special kind of relation from one set to another, and in this context
we will see that any function is really just a set.
CHAPTER
12
Functions
ou know from calculus that functions play a fundamental role in math-
Y ematics. You likely view a function as a kind of formula that describes
a relationship between two (or more) quantities. You certainly understand
and appreciate the fact that relationships between quantities are impor-
tant in all scientific disciplines, so you do not need to be convinced that
functions are important. Still, you may not be aware of the full significance
of functions. Functions are more than merely descriptions of numeric
relationships. In a more general sense, functions can compare and relate
different kinds of mathematical structures. You will see this as your
understanding of mathematics deepens. In preparation of this deepening,
we will now explore a more general and versatile view of functions.
The concept of a relation between sets (Definition 11.7) plays a big role
here, so you may want to quickly review it.
12.1 Functions
Let’s start on familiar ground. Consider the function f (x) = x2 from R to R.
Its graph is the set of points R = ©(x, x2) : x ∈ Rª ⊆ R × R.
R
(x, x2)
R
x
Figure 12.1. A familiar function
Book of Proof Page 27
