Chapter 2: Basic Structures: Sets, Functions,

Sequences, Sums, and Matrices

Nguyen Thi Minh Tam

tamntm16@fe.edu.vn

May 28, 2020

1 2.1 Sets

2 2.2 Set operations

3 2.3 Functions

4 2.4 Sequences and Summations

5 2.5 Cardinality of Sets

 2.1 Sets
2.2 Set operations
2.3 Functions
2.4 Sequences and Summations
2.5 Cardinality of Sets

2.1 Sets

Intuitive Definition of a Set

A set is an unordered collection of objects.
The objects in a set are called the elements, or members of
the set.
A set is said to contain its elements.
a ∈ A: a is an element of the set A.
a∈
/ A: a is not an element of the set A.

3/43
Some important sets in discrete mathematics:
N = {0, 1, 2, 3, . . .}, the set of natural numbers
Z = {. . . , −2, −1, 0, 1, 2, . . .}, the set of integers
Z+ = {1, 2, 3, . . .}, the set of positive integers
Q = {p/q | p ∈ Z, q ∈ Z, and q 6= 0}, the set of rational
numbers
R, the set of real numbers
Equal Sets
Two sets A and B are called equal, written A = B, if they
have the same elements.
A = B if and only if ∀x(x ∈ A ↔ x ∈ B).

The Empty Set

The empty set (null set), denoted by ∅, is a set that has no
elements.
Subsets
The set A is a subset of B ( A ⊆ B) if and only if every
element of A is also an element of B.
A ⊆ B if and only if ∀x(x ∈ A → x ∈ B).
A is a proper subset of B ( A ⊂ B) if and only if A ⊆ B and
A 6= B.

Figure: Venn diagram showing that A is a subset of B.

Theorem 1
For every set S, (i) ∅ ⊆ S and (ii) S ⊆ S

The Size of a Set

Let S be a set.
If there are exactly n distinct elements in S where n is a
nonnegative integer, we say that S is a finite set and that n is
the cardinality of S.
The cardinality of S is denoted by |S|.

|S| = the number of elements in S

A set is said to be infinite if it is not finite.

Power Sets
Given a set S, the power set of S, denoted by P(S), is the set of
all subsets of the set S.

Example 1. What is the power set of the set S = {0, 1, 2}?

Note: If |S| = n then |P(S)| = 2n

ordered n-tuples
The ordered n-tuple (a1 , a2 , . . . , an ) is the ordered collection that
has a1 as its first element, a2 as its second element,..., and an as
its nth element.

the Cartesian Product of Two Sets

Let A and B be sets. The Cartesian product of A and B, denoted
by A × B, is the set

A × B = {(a, b) | a ∈ A, b ∈ B}

Example 2.
Let A = {a, b, c} and B = {1, 2}. Find A × B and B × A.
the Cartesian Product of more than Two Sets
The Cartesian product of the sets A1 , A2 , . . . , An , denoted by
A1 × A2 × . . . × An , is the set

A1 × A2 × . . . × An = {(a1 , a2 , . . . , an ) | ai ∈ Ai , ∀i = 1, 2, . . . , n}

Example 3.
Let A = {a, b, c}, B = {x, y }, and C = {0, 1}. Find A × B × C .
 2.1 Sets
2.2 Set operations
2.3 Functions
2.4 Sequences and Summations
2.5 Cardinality of Sets

2.2 Set operations

The union of the sets A and B, denoted by A ∪ B, is the set

A ∪ B = {x | x ∈ A ∨ x ∈ B}

The intersection of the sets A and B, denoted by A ∩ B, is the

set
A ∩ B = {x | x ∈ A ∧ x ∈ B}

(a) Venn Diagram for A ∪ B. (b) Venn Diagram for A ∩ B.

11/43
 The difference of A and B, denoted by A − B, is the set

A − B = {x | x ∈ A ∧ x ∈
/ B}

Let U be the universal set. The complement of the set A,

denoted by A, is the set

A = U − A = {x | x ∈
/ A}

(c) Venn Diagram for A − B. (d) Venn Diagram for A.

The symmetric difference of A and B, denoted by A ⊕ B, is the set

A⊕B =A∪B −A∩B

= {x | (x ∈ A ∨ x ∈ B) ∧ (x ∈
/ A ∩ B)}

Figure: Venn diagram for A ⊕ B.

Set Identities
Generalized Unions and Intersections

n
[
Ai = A1 ∪ A2 ∪ . . . ∪ An
i=1
= {x | (x ∈ A1 ) ∨ (x ∈ A2 ) ∨ . . . ∨ (x ∈ An )}
n
\
Ai = A1 ∩ A2 ∩ . . . ∩ An
i=1
= {x | x ∈ Ai , ∀i = 1, 2, . . . , n}

Example 4.
n
[ n
\
For i = 1, 2, . . ., let Ai = {i, i + 1, i + 2, . . .}. Find Ai , Ai .
i=1 i=1
Computer Representation of Sets
Assume that the universal set U is finite.
First, specify an arbitrary ordering of the elements of U, for
instance a1 , a2 , . . . , an .
Represent a subset A of U with the bit string of length n,
where the ith bit in this string is 1 if ai belongs to A and is 0
if ai does not belong to A.

Example 5.
Suppose that the universal set is U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
a) Express each of the following sets with bit strings

A = {1, 3, 5, 7, 9}, B = {1, 2, 3, 4, 5}

b) What is the bit string for the complement of A?

c) Use bit strings to find the union and intersection of A and B.
 2.1 Sets
2.2 Set operations
2.3 Functions
2.4 Sequences and Summations
2.5 Cardinality of Sets

2.3 Functions

Let A and B be nonempty sets. A function f from A to B,

denoted by f : A → B, is an assignment of exactly one element of
B to each element of A.
A: the domain of f
B: the codomain of f .
If f (a) = b, then b is called the image of a.
The range of f is the set of all images of elements of A.

Functions are sometimes also called mappings or transformations.

18/43
Figure: The function f maps A to B.
(a) Function (b) Not a function
Functions as sets of ordered pairs
A function can be represented by a set of ordered pairs in which no
two different ordered pairs have the same first coordinate.

Example 6.
a) The set {(−2, 2), (−1, 1), (0, 0), (1, 1), (2, 2)} represents a
function.
the domain is {−2, −1, 0, 1, 2}
the range is {2, 1, 0}
b) The set {(10, 6), (23, –1), (38, 6), (10, 4), (59, 4)} does not
represent a function.
Example 7. Determine whether f is a function if
a) f : Z → R, f (x) = x 2 + 2
1
b) f : Z → R, f (x) = + 5x
(x − 1)2
(2x + 5)2
c) f : R → R, f (x) =
7 − 2x
(2x + 5)2
d) f : Z → R, f (x) =
7 − 2x
Some Important Functions
Floor function
f : R → Z, f (x) = bxc = the largest integer that is less than
or equal to x.
Ceiling function
f : R → Z, f (x) = dxe = the smallest integer that is greater
than or equal to x.

Example 8. Compute b 32 − d3 + 54 ec
One-to-One Functions
A function f is said to be one-to-one (injective) if and only if
f (a) = f (b) implies that a = b for all a and b in the domain of f .

Figure: A one-to-one function.

Example 9. Determine whether the following function is

one-to-one.
f : Z → Z, f (x) = x 2
Onto Functions
A function f : A → B is called onto (surjective), if and only if for
every element b ∈ B there is an element a ∈ A with f (a) = b.

Figure: A onto function.

Example 10.
Determine whether the function f : Z × Z → Z is onto if
a) f (m, n) = m + n
b) f (m, n) = |n|
Bijective Functions
The function f is a one-to-one correspondence, or a bijection, if it
is both one-to-one and onto. We also say that such a function is
bijective.
Inverse Functions
Let f : A → B be a bijection. The inverse function of f , denoted
by f −1 , is the function that assigns to an element b ∈ B the
unique element a ∈ A such that f (a) = b.

f −1 (b) = a when f (a) = b

Example 11. Let f : Z → Z be such that f (x) = x + 1. Is f
invertible, and if it is, what is its inverse?
Compositions of Functions
Let g : A → B, f : B → C . The composition of the functions f
and g , denoted by f ◦ g , is defined by

(f ◦ g )(a) = f (g (a)), ∀a ∈ A
Example 12. Let f (x) = 5x + 4, g (x) = 4x + 3. Suppose that
f ◦ g (x) = ax + b. Find a + b.
 2.1 Sets
2.2 Set operations
2.3 Functions
2.4 Sequences and Summations
2.5 Cardinality of Sets

2.4 Sequences and Summations

Sequences
A sequence is a function from a subset of Z (usually either the
set {0, 1, 2, . . .} or the set {1, 2, . . .}) to a set S.
We use the notation an to denote the image of the integer n.
an is called a term of the sequence.
We use the notation {an } to describe the sequence.

32/43
Geometric Progression
A geometric progression is a sequence of the form

a, ar , ar 2 , . . . , ar n , . . .

where the initial term a and the common ratio r are real numbers.

The sequence {an } with an = ar n is a geometric progression.

Arithmetic Progression
An 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.

The sequence {an } with an = a + nd is an arithmetic progression.

How to deduce a possible formula for the terms of a sequence or a
rule for generating the terms of a sequence
Does the same value occur many times in the sequence?
Are terms obtained from previous terms by adding the same
amount or an amount that depends on the position in the
sequence?
Are terms obtained from previous terms by multiplying by a
particular amount?
Are terms obtained by combining previous terms in a certain
way?
Are there cycles among the terms?
Compare the terms of a sequence of interest with the terms of
a well-known integer sequence.
Some Useful Sequences
Example 13. Find formulae for the sequences with the following
first terms:
a) 5, 11, 17, 23, 29, 35, 41, 47, 53, 59.
b) 1, 3, 4, 7, 11, 18, 29, 47, 76, 123.
c) 1, −1, 1, −1, 1.
d) 1, 2, 2, 3, 3, 3, 4, 4, 4, 4.
e) 1, 7, 25, 79, 241, 727, 2185, 6559, 19681, 59047.
Summations

n
X
Pn P
am + am+1 + . . . + an = i=m ai = m≤i≤n ai = ai
i=m
i: the index of summation
m: lower limit
n: upper limit

8
X
Example 14. What is the value of (−1)k ?
k=4
The sum of terms of a geometric progression
If a and r are real numbers and r 6= 0, then

n  ar n+1 − a
X
j
ar = if r 6= 1
r −
 (n + 1)a1
j=0 if r = 1
Some Useful Summation Formulae
Example 15. Compute
P100 2
a) k=50 k
10
X
b) (2i+1 − 2i )
i=0
 2.1 Sets
2.2 Set operations
2.3 Functions
2.4 Sequences and Summations
2.5 Cardinality of Sets

2.5 Cardinality of Sets

The sets A and B have the same cardinality (|A| = |B|) if and
only if there is a one-to-one correspondence from A to B.
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, we denote the cardinality
of S by ℵ0 .

42/43
Exercises

Section 2.1: 12-26, 29-40 (page 126)

Section 2.2: 16-24, 29 (page 136), 30, 32-43, 46-51 (page 137)
Section 2.3: 2, 3, 5, 9, 14, 17, 23, 33, 36 (page 152-154)
Section 2.4: 30-34 (page 169)