Sets, Proof Templates,
and Induction
The concept of a set underlies most of modem mathematics and much of computer sci-
ence. To use sets as a foundation for all the other structures in this text, we first need to
understand both the language used to describe sets and the operations normally associ-
ated with sets. The language of sets is very precise. When we use this language carefully,
we gain precision in expressing problems and describing solutions to problems. Under-
standing basic operations on sets and the properties of these operations is a model for the
approach that is used to introduce most other discrete structures in this text. In extending
our understanding of operations on sets, we will learn proof techniques to explore other
discrete mathematical topics, such as relations, functions, and graphs. We will use these
proof techniques, for example, to prove that algorithms are correct and to determine how
well we have chosen an algorithm for a given task.
This chapter has five main sections. The first introduces the notion of a set and the
language for describing collections of elements. In addition, this section introduces several
proof templates that are guides to both understanding and constructing proofs. The second
deals with the common operations on sets: unions, intersections, complements, products,
and the power set of a set. Some additional proof templates are introduced that are drawn
from proofs in this section. The third provides a way to count the number of elements in
a collection of sets in which some of the sets may contain some of the same elements that
the other sets contain. The fourth and fifth deal with important proof techniques called the
Principle of Mathematical Induction and the Strong Form of Mathematical Induction. We
use induction to find the set of elements for which a statement about the integers is true.
An important application of the Principle of Mathematical Induction, in both its forms,
is to show how algorithms can be proven to be correct without any execution by a computer.
Basic Definitions
The idea of a set is simple: A set is a collection of elements. The set {white, red,
green) contains the names of the colors white, red, and green and nothing else. The set
{0, 1, 2, 3, 4, 5, 1003456792311 contains seven integers. The set {red, yellow, blue) con-
tains the names of primary colors. A set of stamps stored in loose-leaf notebooks on a shelf
I