Discrete Mathematics

and Its Applications

Sixth Edition
By Kenneth Rosen

Chapter 2
Basic Structures:
Sets, Functions,
Sequences, and Sums
 Outlines

2.1 Sets
2.2 Set Operations
2.3 Functions
2.4 Sequences and Summations
 Getting Started

2.1 Sets
2.2 Set Operations
2.3 Functions
2.4 Sequences and Summations
 2.1 Sets(1/8)

• Definition 1: A set is an unordered

collection of objects
• Definition 2: Objects in a set are called
elements, or members of the set.
– a A, a  A
– V = {a, e, i, o, u}
– O = {1, 3, 5, 7, 9}
or O = {x|x is an odd positive integer less
than 10}
or O = {xZ+|x is odd and x<10}
 2.1 Sets(2/8)

– N={0, 1, 2, 3, …}, natural numbers

– Z={…,-2, -1, 0, 1, 2, …}, integers
– Z+={1, 2, 3, …}, positive integers
– Q={p/q|pZ, qZ, and q0}, rational numbers
– Q+={xR|x=p/q, for positive integers p and q}
– R, real numbers
 2.1 Sets(3/8)

• Definition 3: Two sets are equal if and

only if they have the same elements.
A=B iff x(x  A  x  B)
• Venn diagram
– Universal set U
– Empty set (null set)  (or {})
 FIGURE 1 (2.1)

FIGURE 1 Venn Diagram for the Set of Vowels.

P. 114
 2.1 Sets(5/8)

• Definition 4: The set A is a subset of B if

and only if every element of A is also an
element of B.
A  B iff x(x  A  x  B)
• Theorem 1: For every set S,
(1)   S and (2) S  S.
• Proper subset: A  B
x(x  A  x  B)  x(x  B  x  A)
 2.1 Sets(6/8)

• If AB and BA, then A=B

• Sets may have other sets as members
– A={, {a}, {b}, {a,b}}
B={x|x is a subset of the set {a,b}}
– A=B
 FIGURE 2 (2.1)

FIGURE 2 Venn Diagram Showing that A Is a Subset of B.

 2.1 Sets(8/8)

• Definition 5: If there are exactly n distinct

members in the set S (n is a nonnegative
integer), we say that S is a finite set and that
n is the cardinality of S.
|S|= n
– ||=0
• Definition 6: A set is infinite if it’s not
finite.
– Z+
 The Power Set

• Definition 7: The power set of S is the set

of all subset of the set S. P(S)
– P({0,1,2})
– P()
– P({})
• If a set has n elements, then its subset has
2n elements.
 Cartesian Products

• Definition 8: Ordered n-tuple (a1, a2, …, an) is the

ordered collection that has ai as its ith element
for i=1, 2, …, n.
• Definition 9: Cartesian product of A and B,
denoted by A  B, is the set of all ordered pairs
(a, b), where a  A and b  B.
A  B = {(a, b)| a  A  b  B}
– E.g. A = {1, 2}, B = {a, b, c}
– A  B and B  A are not equal, unless A= or B= or
A=B
• Definition 10: Cartesian product of A1, A2,
…, An, denoted by A1 A2  … An, is the
set of all ordered n-tuples (a1, a2, …, an),
where ai  Ai for i=1,2,…,n.
A1 A2  … An = {(a1, a2, …, an)| ai  Ai for
i=1,2,…,n}
• Using set notation with quantifiers
 xS (P(x)): x (xS  P(x))
 xS (P(x)): x (xS  P(x))
– ∃x : x^2 = 4 is true, since 2 is an x for which
x^ 2 = 4. On the other hand, ∀x : x^2 = 4 is
clearly false; not all numbers, when squared,
are equal to 4.
• Truth sets of quantifiers
Given a predicate P, and a domain D, we define the truth
set of P to be the set of elements x in D for which P (x) is true.
Then the truth set of P: {x  D | P(x)}
• For Example:
What are the truth sets of the predicates P (x), where the domain
is the set of integers and P (x) is “|x| = 1”.
Solution: The truth set of P, {x ∈ Z | |x| = 1}, is the set of integers for
which |x| = 1. Because |x| = 1 when x = 1 or x = −1, and for no
other integers x, we see that the truth set of P is the set {−1, 1}.
 Getting Started

2.1 Sets
2.2 Set Operations
2.3 Functions
2.4 Sequences and Summations
 2.2 Set Operations

• Definition 1: The union of the sets A and

B, denoted by AB, is the set containing
those elements that are either in A or in B,
or in both.
– AB={x|xA  xB}
• Definition 2: The intersection of the sets
A and B, denoted by AB, is the set
containing those elements in both A and B.
– A  B={x|xA  xB}
 Figure 1 (2.2)

FIGURE 1 Venn Diagram Representing the Union of A and B.

 FIGURE 2 (2.2)

FIGURE 2 Venn Diagram Representing the Intersection of A and B.

• Definition 3: Two sets are disjoint if their
intersection is the empty set.
• |AB|=|A|+|B|-| A  B |
– Principle of inclusion-exclusion
• Definition 4: The difference of the sets A and B,
denoted by A-B, is the set containing those
elements that are in A but not in B.
– Complement of B with respect to A
– A-B={x|xA  xB}
• Definition 5: The complement of the set A,
denoted by Ā, is the complement of A with
resepect to U.
– Ā = {x|xA}
 FIGURE 3 (2.2)

FIGURE 3 Venn Diagram for the Difference of A and B.

 FIGURE 4 (2.2)

FIGURE 4 Venn Diagram for the Complement of the Set A.

TABLE 1 (2.2)
 Set Identities

• To prove set identities

– Show that each is a subset of the other
– Using membership tables
– Using those that we have already proved
TABLE 2 (2.2)
 Generalized Unions and Intersections

• Definition 6: The union of a collection of sets is

the set containing those elements that are
members of at least one set in the collection.
n

– A1 A2  …  An = Ai 1
i

• Definition 7: The intersection of a collection of

sets is the set containing those elements that are
members of all the sets in the collection.
n

– A1 A2  …  An = Ai 1
i

• Computer Representation of Sets

– Using bit strings
 FIGURE 5 (2.2)

FIGURE 5 The Union and Intersection of A, B, and C.

P. 127
 Getting Started

2.1 Sets
2.2 Set Operations
2.3 Functions
2.4 Sequences and Summations
 2.3 Functions

• Definition 1: A function f from A to B is

an assignment of exactly one element of B
to each element of A. f: AB
• Definition 2: f: AB.
– A: domain of f, B: codomain of f.
– f(a)=b, a: preimage of b, b: image of a.
– Range of f: the set of all images of elements of
A
– f: maps A to B
 FIGURE 1
x 2x+1
1
2
1
3
4
2
5 Range
6
3
7
or
4
8 Image
9

Domain Co-domian

FIGURE 1.1: An example of function with it’s components.

 FIGURE 2
x 2x+1
1
1 2
3
2 4
5 Range
3 6 or
7 Image
4 8

Domain Co-domian

FIGURE 1.2: An example of not being function

 FIGURE 3
1
2
a
3
4
b
5 Range
6
c
7
or
d
8 Image
9

Domain Co-domian

FIGURE 1.3: An example of not being function

 FIGURE 2 (2.3)

FIGURE 2 The Function f Maps A to B.

• Definition 3: Let f1 and f2 be functions
from A to R. f1+f2 and f1f2 are also functions
from A to R:
– (f1+f2)(x) = f1(x)+f2(x)
– (f1f2)(x)=f1(x)f2(x)
• Definition 4: f: AB, S is a subset of A.
The image of S under the function f is:
f(S)={t|sS(t=f(s))}
 One-to-One and Onto Functions

• Definition 5: A function f is one-to-one or

injective, iff f(a)=f(b) implies that a=b for all a
and b in the domain of f.
 ab( f(a)=f(b)  a=b ) or
ab( a  b  f(a)  f(b) )
• Definition 6: A function f is increasing if
f(x)≤f(y), and strictly increasing if f(x)<f(y)
whenever x<y. f is called decreasing if f(x)≥f(y),
and strictly decreasing if f(x)>f(y) whenever x<y.
 FIGURE 3 (2.3)

FIGURE 3 A One-to-One Function.

 One-to-One and Onto Functions

• Definition 7: A function f is onto or

surjective, iff for every element bB there is
an element aA with f(a)=b.
 yx( f(x)=y ) or
ab( a  b  f(a)  f(b) )
– When co-domain = range
• Definition 8: A function f is a one-to-one
correspondence or a bijection if it is both
one-to-one and onto.
– Ex: identity function ιA(x)=x
FIGURE 4 (2.3)

FIGURE 4 An Onto Function.

 FIGURE 5 (2.3)

FIGURE 5 Examples of Different Types of Correspondences.

 Inverse Functions and Compositions of
Functions

• Definition 9: Let f be a one-to-one

correspondence from A to B. The inverse
function of f is the function that assigns to
an element b in B the unique element a in
A such that f(a)=b.
– f-1(b)=a when f(a)=b

Prove It

If a function is one-to-one correspondence then it’s inverse is possible

 FIGURE 6 (2.3)

FIGURE 6 The Function f － 1

Is the Inverse of Function f.
• Definition 10: Let g be a function from A
to B, and f be a function from B to C. The
composition of functions f and g, denoted
by f○g, is defined by:
– f○g(a) = f(g(a))
– f○g and g○f are not equal --- Prove it
 FIGURE 7 (2.3)

FIGURE 7 The Composition of the Functions f and g.

 Graphs of Functions
• Definition 11: The graph of function f is
the set of ordered pairs {(a,b)|aA and
f(a)=b}
 FIGURE 8 (2.3)

FIGURE 8 The Graph of f(n) = 2n + 1 from Z to Z.

 FIGURE 9 (2.3)

FIGURE 9 The Graph of f(x) = x2 from Z to Z.

 Floor and Ceil Functions

• Definition 12: The floor function assigns

to x the largest integer that is less than or
equal to x (x or [x])..
• Definition 13: The ceiling function assigns
to x the smallest integer that is greater
than or equal to x (x)
 FIGURE 10 (2.3)

FIGURE 10 Graphs of the (a) Floor and (b) Ceiling Functions.

TABLE 1 (2.3)
Proof: 4(a)
 Getting Started

2.1 Sets
2.2 Set Operations
2.3 Functions
2.4 Sequences and Summations
 2.4 Sequences and Summations

• Definition 1: A sequence is a function

from a subset of the set of integers to a set
S. We use an to denote the image of the
integer n (a term of the sequence)
– The sequence {an}
• Ex: an=1/n
• Definition 2: A geometric progression is a
sequence of the form
a, ar, ar2, …, arn, …
where the initial term a and the common ratio r are
real numbers
• Definition 3: A arithmetic progression is a
sequence of the form
a, a+d, a+2d, …, a+nd, …
where the initial term a and the common difference
d are real numbers
• Ex. 1, 3, 5, 7, 9, …
• Ex. 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, …
• Ex. 1, 7, 25, 79, 241, 727, 2185, 6559, 19681,
59047, …
TABLE 1 (2.4)
 Summing a Sequence

• Specific sum

1 + 2 + 3 + ….. + n-1 + n
• General summation of a sequence of terms:

a1 + a2 + …… an

ak terms

where k = 1 , 2 , … n
 Summing a Sequence
• Each element ak of a sum is called a term.

• The terms are often specified implicitly as

formulas that follow a readily perceived
pattern.
• In such cases we must sometimes write
them in an expanded form so that the
meaning is clear.
 Summing a Sequence

1 + 2 + ……….

1 + 2 + ….. + 2n-1

1 + 2 + 4 + ……. + 2n-1

20 + 21 + 22 + ……. + 2n-1

The three-dots notation has many uses, but it

can be ambiguous and a bit long-winded
 Delimited Form of Sum

• Three-dots notation is vague and wordy

which is also called Sigma-notation because it

uses the Greek letter
 Delimited Form of Sum

• Parts of notation
– Summand

– Index variable

– Lower limit

– Upper limit
 Delimited Form of Sum

• Sigma notation inline

 Delimited Form of Sum

Sums the terms ak where index k is an integer

from lower limit 1 to upper limit n

or

sum over k from 1 to n

 Generalized Sigma-Notation
• Specify a condition that the index variable
must satisfy

• We simply write one or more conditions

under the to specify the set of indices over
which summation should take place.
 Generalized Sigma-Notation

• The general form allows us to take sums

over index sets that aren’t restricted to
consecutive integers.
 Generalized Sigma-Notation
• Express the sum of the squares of all odd
positive integers below 100

• The delimited equivalent of this sum

 Generalized Sigma-Notation

• The sum of reciprocals of all prime

numbers between 1 and N

• The delimited equivalent of this sum

(N) = Number of primes given
Advantage of Generalized Sigma-
Notation
• We can manipulate it more easily than the
delimited form
Advantage of Generalized Sigma-
Notation
• Change the index variable k to k + 1

• Generalized Sigma-notation

• Delimited form
 Advantage of Delimited Form
• It’s nice and tidy, and we can write it
quickly
=

• Needs less symbol than generalized sigma

notation.
 Delimited Form Vs. Generalized
Sigma-Notation
• Delimited Form
– Used in presenting or stating a problem

• Generalized Sigma-Notation
– Used when index variable needs to be
transformed.
 Summations

• Summation notation:
n

a j 
n
j m
aj 
1 j  n
aj
j m

– am+am+1+…+an
– j: index of summation
– m: lower limit
– n: upper limit
• Theorem 1 (geometric series): If a and r are
real numbers and r≠0, then
 ar n 1  a
n
 if r  1
 ar j
  r 1
j 0 (n  1 )a if r  1

– Prove it yourself
TABLE 2 (2.4)
 Cardinality

• Definition 4: The sets A and B have the same

cardinality iff there is a one-to-one
correspondence from A to B.
• Definition 5: A set that is either finite or has the
same cardinality as the set of positive integers is
called countable. A set that is not countable is
called uncountable. When an infinite set S is
countable, |S|=0‫“( א‬aleph null”)
– Ex: the set of odd positive integers is countable
 FIGURE 1 (2.4)

FIGURE 1 A One-to-One Correspondence Between Z+ and

the Set of Odd Positive Integers, f(n) = 2n - 1.
 FIGURE 2 (2.4)

FIGURE 2 The Positive Rational Numbers Are Countable.

歐亞書局 P. 159