Course: Discrete Structures

(501215-3)

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

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

P. 121
 2.1 Sets

• 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}
– 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

– {N,Z,Q,R}
• Definition 3: Two sets are equal if and
only if they have the same elements.
A=B iff x(x  A  x  B)
– {1, 3, 5} and {3, 5, 1} are equal
• Empty set (null set):  (or {})
• Venn diagram to graphically represent
sets
– Universal set U: rectangle
– Sets: circles
– Elements of a set: point
 FIGURE 1 (2.1)

FIGURE 1 Venn Diagram for the Set of Vowels.

6
P. 114
• 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 is a proper subset of B,
we note A  B, iff
x(x  A  x  B)  x(x  B  x  A)
• 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.

9
P. 115
• 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, P(S), is

the set of all subset of the set S.
– P({0,1,2}) = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0,
1, 2}}.
– P()={∅}
– P({})={∅, {∅}}
• If a set has n elements, then its power set
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={(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}.
– B×A =...
• 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}
– A = {0, 1}, B = {1, 2}, and C = {0, 1, 2}
– A × B × C = {(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0),
(0, 2, 1), (0, 2, 2),(1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2,
0), (1, 2, 1), (1, 2, 2)}.
 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 Venn Diagrams Representing the Union and

intersection of A and B. 15
P. 122
• Definition 3: Two sets are disjoint if their
intersection is the empty set.
• |AB|=|A|+|B|-| A  B |
• 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.

18
P. 123
 FIGURE 4 (2.2)

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

19
P. 123
• {1, 3, 5} ∪ {1, 2, 3} = {1, 2, 3, 5}
• {1, 3, 5} ∩ {1, 2, 3} = {1, 3}
• A = {1, 3, 5, 7, 9} , B = {2, 4, 6, 8, 10},
A ∩ B = ∅, A and B are disjoint
• {1, 3, 5} − {1, 2, 3} =…
• Let A be the set of positive integers greater
than 10. Then Ā = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
TABLE 1 (2.2)

21
P. 134
 Exercise

• Let A, B, and C be sets.

• Show that A ∪ (B ∩ C)= (𝐶ҧ ∪ 𝐵)
ത ∩ 𝐴ҧ
• A ∪ (B ∩ C)=…
 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 =  A i
i 1
• 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.
– A1 A2  …  An =  A
n

• Computer Representation of Sets

i 1

– Using bit strings

 FIGURE 5 (2.2)

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

24
P. 127
 Exercise

• Show that if A, B, and C are sets, then

𝐴 ∩ 𝐵 ∩ 𝐶= 𝐴ҧ ∪ 𝐵ത ∪ 𝐶ഥ
• a) by showing each side is a subset of the
other side:
…

• b) using a membership table.

 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
 Exercise
What are the domain, codomain, and range of
the function that assigns grades to students
described as follow?

27
P. 133
• Let G be the function that assigns a grade
to a student in our discrete mathematics
class. Note that G(Adams) = A.
• domain(G)=…

• Codomain(G)=…
• Range(G)=…
 Exercise

• Let f a function that assign the square of

an integer to this integer. Specify f.
– f (x) = …
– Domain(f)= …
– Codomain(f)=…
– Range(f)= …
 FIGURE 2 (2.3)

FIGURE 2 The Function f Maps A to B.

30
P. 134
 Sum and product of functions

• 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))}
 Exercise

• Let f1 and f2 be functions from R to R such

that f1(x) = x2 and f2(x) = x − x2. What are
the functions f1 + f2 and f1f2?
– (f1 + f2)(x) = …
– (f1f2)(x) =…
• Let A={a,b,c,d,e} and B={1,2,3,4} with
f(a)=2, f(b)=1, f(c)=4, f(d)=1, f(e)=1. What is
the image of S={b,c,d}?
– The image of the subset S is the set 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.

34
P. 137
 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) )
• 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.

36
P. 138
 FIGURE 5 (2.3)

FIGURE 5 Examples of Different Types of Correspondences.

37
P. 139
 Exercise
• Determine whether the function f (x) = x2
from ℤ to ℤ is one-to-one and/or onto.
– The function f (x) = x2 is…

– The function f is…

• Determine whether the function f(x)=x+1

from ℝ to ℝ is one-to-one and/or onto.
– f(x) is…
– f(x) is…
 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
 FIGURE 6 (2.3)

FIGURE 6 The Function f －1 Is the Inverse of Function f.

40
P. 139
 Exercise
• Let f be the function from {a, b, c} to {1, 2, 3}
such that f (a) = 2, f (b) = 3, and f (c) = 1. Is f
invertible, and if it is, what is its inverse?
– f is …

• Let f : Z → Z be such that f(x) = x + 1. Is f

invertible, and if it is, what is its inverse?
– f....
 Composition of functions

• 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
 FIGURE 7 (2.3)

FIGURE 7 The Composition of the Functions f and g.

43
P. 141
 Exercise

• Let g be the function such that g(a)=b, g(b)=c,

and g(c)=a. Let f be the function such that f
(a)=3, f (b)=2, and f (c)=1. What is f○g and g○f ?
– The composition f○g is defined by (f○g)(a)= f(g(a))=
…

– Note that g○f is not defined, because the range of f is

not a subset of the domain of g
 Exercise

• Let f and g be the functions from ℤ to ℤ

defined by f(x)=2x+3 and g(x)=3x+2. What
are f○g and g○f ?
– (f○g)(x) = …
– (g○f )(x) = …
 Some important Functions

• Definition 12: The floor function assigns to

x the largest integer that is less than or
equal to x (x). The ceiling function
assigns to x the smallest integer that is
greater than or equal to x (x).
– 1/2 = 0, - 1/2  = -1, 3.1 = 3, 7 = 7, 1/2
= 1, - 1/2  = 0,  3.1  = 4, 7 = 7
47
P. 150
 2.5 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)
– Notation: {an} describes the sequence
– Ex: an=1/n
 Progressions

• 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
 Examples

• {bn} with bn = (−1)n

• {cn} with cn = 2・5n

• {dn} with dn= 6・(1/3) n

 Examples

• The sequences {sn} with sn = −1 + 4n

• The sequences {tn} with tn = 7 − 3n

 Exercise

• Find formulae for the sequences with the

following first terms:
• 1, 1/2, 1/4, 1/8, 1/16
– an =
• 1, 3, 5, 7, 9, …
– an =

• 5, 11, 17, 23, 29, 35, 41, 47, 53, 59, …

– an =
TABLE 1 (2.4)

53
P. 153
 Summations

• Summation notation:
n

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

– am+am+1+…+an
– j: index of summation
– m: lower limit
– n: upper limit
 Exercises

• Use summation notation to express the

sum of the first 100 terms of the sequence
{aj}, where aj = 1/j for j = 1, 2, 3, . . . .
100
1

j 1 j
5
• What is the value of j
j 1
2
 Exercise
100
• Find k
j 50
2
TABLE 2 (2.4)

57
P. 157
• What are the values of these sums?
5 100
 (k  1) 3
100

k 1
k
k 1 k 1

3 4

 i  j
4 3

 2i  j
4 3

 ij
2

i 1 j  0 i 1 j  0
i 1 j 1