Chapter 5
Algebra
You probably consider yourself an old hand at algebra. Nevertheless, you may have
picked up some bad habits or missed a few tricks in your mathematical education.
The purpose of this chapter is reeducation: We shall relearn algebra from the problem
solver's perspective.
Algebra, combinatorics, and number theory are intimately connected.
Please read thefirst/ew sections o/Chapters 6 and 7 concurrently with
th is chapter.5.1 Sets, Numbers, and Functions
This first section contains a review of basic set and function notation, and can probably
be skimmed (but make sure that you understand the function examples that begin on
page 145).Sets
Sets are collections of elements. If an element x belongs to (is an element of) a set A
we write x E A. Sets can be collections of anything (including other sets). One way to
define a set is by listing the elements inside brackets, for example,A = {2, 3, 8, Vi}.
A set can contain no elements at all; this is the empty set 0 = {}.
Recall the set operations U (union) and n (intersection). We define A UB to be the
set each of whose elements is contained either in A or in B (or in both). For example,
{1,2, 5}U {I,3,8} = {1,2,3,5, 8}.
Similarly, we define A n B to be the set whose elements are contained in both A
and B, so for example,
{1,2, 5}n{1,3,8} = { I}.
If all elements of a set A are contained in a set B, we say that A is a subset of B
and write A C B. Note that A C A and 0 C A for all sets A.143