Page 136 - Discrete Mathematics and Its Applications

CH A P TER

2 Basic Structures: Sets, Functions,

Sequences, Sums, and Matrices

2.1 Sets uch of discrete mathematics is devoted to the study of discrete structures, used to repre-
Msent discrete objects. Many important discrete structures are built using sets, which are
2.2 Set Operations
collections of objects.Among the discrete structures built from sets are combinations, unordered
2.3 Functions collections of objects used extensively in counting; relations, sets of ordered pairs that represent
relationships between objects; graphs, sets of vertices and edges that connect vertices; and finite
2.4 Sequences and state machines, used to model computing machines. These are some of the topics we will study
Summations
in later chapters.
2.5 Cardinality of The concept of a function is extremely important in discrete mathematics.A function assigns
Sets to each element of a first set exactly one element of a second set, where the two sets are not
necessarily distinct. Functions play important roles throughout discrete mathematics. They are
2.6 Matrices
used to represent the computational complexity of algorithms, to study the size of sets, to count
objects, and in a myriad of other ways. Useful structures such as sequences and strings are
special types of functions. In this chapter, we will introduce the notion of a sequence, which
represents ordered lists of elements. Furthermore, we will introduce some important types of
sequences and we will show how to define the terms of a sequence using earlier terms. We will
also address the problem of identifying a sequence from its first few terms.
In our study of discrete mathematics, we will often add consecutive terms of a sequence of
numbers. Because adding terms from a sequence, as well as other indexed sets of numbers, is
such a common occurrence, a special notation has been developed for adding such terms. In this
chapter, we will introduce the notation used to express summations. We will develop formulae
for certain types of summations that appear throughout the study of discrete mathematics. For
instance, we will encounter such summations in the analysis of the number of steps used by an
algorithm to sort a list of numbers so that its terms are in increasing order.
The relative sizes of infinite sets can be studied by introducing the notion of the size, or
cardinality, of a set. We say that a set is countable when it is finite or has the same size as the
set of positive integers. In this chapter we will establish the surprising result that the set of
rational numbers is countable, while the set of real numbers is not. We will also show how the
concepts we discuss can be used to show that there are functions that cannot be computed using
a computer program in any programming language.
Matrices are used in discrete mathematics to represent a variety of discrete structures. We
will review the basic material about matrices and matrix arithmetic needed to represent relations
and graphs. The matrix arithmetic we study will be used to solve a variety of problems involving
these structures.

2.1 Sets

Introduction

In this section, we study the fundamental discrete structure on which all other discrete structures
are built, namely, the set. Sets are used to group objects together. Often, but not always, the
objects in a set have similar properties. For instance, all the students who are currently enrolled
in your school make up a set. Likewise, all the students currently taking a course in discrete
mathematics at any school make up a set. In addition, those students enrolled in your school
who are taking a course in discrete mathematics form a set that can be obtained by taking the
elements common to the first two collections. The language of sets is a means to study such

115