Chapter 2
Basic Structures:
Sets, Functions, Sequences & Sums
MAD101
Ly Anh Duong
duongla3@[Link]
Table of Contents
1 Sets
▶ Sets
▶ Set operations
▶ Functions
▶ Sequences
▶ Summations
Sets
1 Sets
Definition 1.1
A set is an unordered collection of distinct objects, called elements or members of the set. A set is said to
contain its elements. We write a ∈ A to denote that a is an element of the set A. The notation a ∈ /A
denotes that a is not an element of the set A.
Example 1.1.
1. {1, 2, {3}} is the set containing “1” and “2” and “{3}”.
2. {1, 1, 2, 3, 3} = {1, 2, 3} = {3, 2, 1}.
3. ∅ = {} is the empty set, or the set containing no element.
4. ∅ =
̸ {∅}.
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 3 / 28
Venn Diagrams
1 Sets
1. N = {0, 1, 2, 3, . . . }, the set of all natural numbers.
2. Z = {. . . , −2, −1, 0, 1, 2, . . . }, the set of all integers.
3. Z+ = {1, 2, 3, . . . }, the set of all positive integers.
Figure: Venn diagram for the set of vowels.
4. Q = {p/q|p ∈ Z, q ∈ Z}, the set of all rational
numbers.
5. R is the set of real numbers.
6. C is the set of all complex numbers.
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 4 / 28
Subset (⊆) & Proper subset (⊂)
1 Sets
A⊆B A⊂B
“A is a subset of B.” “A is a proper subset of B.”
∀x((x ∈ A) → (x ∈ B)) A ⊆ B and A ̸= B
Definition 1.2
Two sets are equal if and only if they have the same elements. Therefore, if A and B are sets, then A and
B are equal if and only if ∀x((x ∈ A) ↔ (x ∈ B)). We write A = B if A and B are equal sets.
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 5 / 28
Properties
1 Sets
Note 1.1. For every set S, (i ) ∅ ⊆ S and (ii ) S ⊆ S.
Example 1.2. Determine whether each of these statements is true or false.
1. {1, 2, 3} ⊆ {1, 2, 3, 4, 5} 6. ∅ ∈ {∅, 1, 2, 3}
2. {1, 2, 3} ⊂ {1, 2, 3, 4, 5} 7. {x} ⊆ {x}
3. ∅ ⊆ {1, 2, 3} 8. {x} ∈ {x, {x}}
4. ∅ ∈ {1, 2, 3} 9. {x} ⊆ {x, {x}}
5. ∅ ⊆ {∅, 1, 2, 3} 10. {x} ∈ {x}
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 6 / 28
Cardinality
1 Sets
Definition 1.3
If S is finite, then the cardinality of S, |S|, is the number of distinct elements in S.
Definition 1.4
A set is said to be infinite if it is not finite.
Example 1.3. Note 1.2. When a infinite set S is
1. S = {1, 2, 3} → |S|=3 countable, we denote the cardinality of
2. S = {2, 4, 1, 7} → |S|=4 S is |S|= N0 (aleph null).
3. S = ∅ → |S|=0 If S is uncountable and infinite, we
4. S = {∅, {∅}, {∅, {∅}}} → |S|=3 denote the cardinality of S is |S|= 2N0 .
5. S = {1, 2, 3, ....} → |S| is infinite
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 7 / 28
Power sets
1 Sets
Definition 1.5
Given a set S, the power set of S is the set of all subsets of the set S. The power set of S is denoted by
P (S) ≡ 2S .
Note 1.3. If S finite, then |2S | = 2|S| (If |S| = n, then |2S | = 2n )
Example 1.4.
• If S = {a} then 2S = {∅, {a}}
• If S = {a, b} then 2S = {∅, {a}, {b}, {a, b}}
• If S = ∅ then 2S = {∅}
• If S = {∅, {∅}} then 2S = {∅, {∅}, {{∅}}, {∅, {∅}}}
Example 1.5. Given A = {∅, 1, 2, 3}. Find the cardinality of P(A).
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 8 / 28
Cartesian Product
1 Sets
Definition 1.6
The Cartesian Product of two sets A and B is A × B = {(a, b) : a ∈ A ∧ b ∈ B}.
The Cartesian Product of n sets A1 , A2 , . . . , An is A1 × · · · × An = {(a1 , . . . , an ) : ai ∈ Ai , ∀i = 1, n}
Note 1.4.
1. A × B ̸= B × A.
2. If A, B are finite, |A × B| = |A||B|.
3. An = A × A × A × ... × A.
Example 1.6. Given A = {a, b}, B = {1, 2, 3}, C = {0, 1}. Find A × B, B × A,
A × B × C, A2 .
Example 1.7. Given A = {0, ∅}. Find the cardinality of P (A2 ).
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 9 / 28
Table of Contents
2 Set operations
▶ Sets
▶ Set operations
▶ Functions
▶ Sequences
▶ Summations
Set operations
2 Set operations
Union Intersection Difference Symmetric Complement
Difference
A∪B A∩B A−B A⊕B Ā/Ac
Definition 2.1
Two sets are called disjoint if their intersection is the empty set.
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 11 / 28
Computer representation of sets
2 Set operations
The universal set U = {x1 , x2 , . . . , xn }. Let A ⊆ U . Then the bit string representation of A is the bit
string of length n: a1 a2 . . . an such that
1, xi ∈ A
ai =
0, otherwise.
Example 2.1. Let U = {x1 , x2 , x3 , x4 , x5 , x6 } and A = {x1 , x3 , x5 , x6 }.
,→ The bit string representation of A is 101011.
Example 2.2. Let U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Given the subsets
A = {1, 2, 3, 4, 8}, B = {0, 5, 6, 7, 9}.
Find the bit string representing the subset A − B, A ∩ B, A ∪ B, A ⊕ B.
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 12 / 28
Table of Contents
3 Functions
▶ Sets
▶ Set operations
▶ Functions
▶ Sequences
▶ Summations
Functions
3 Functions
A function f consists of a set of inputs, a set of outputs, and a rule for assigning
each input to exactly one output. We denote
f : A −→ B
x 7−→ y = f (x)
| {z }
image
The set of inputs is called the domain A of the function. The set of outputs is
called the co-domain B of the function.
A function can be visualized as an
input/output device.
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 14 / 28
Example
3 Functions
What are functions?
1. f : Z → R : f (x) = x2 + 2. 1
3. f : R → R : f (x) = .
1 x2 − 2
2. f : Z → R : f (x) = + 5x. 1
(x − 1)2 4. f : Z → R : f (x) = 2 .
2x + 5 x −2
3. f : R → R : f (x) = . 1
7 5. f : Z → Z : f (x) = 2 .
x −2
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 15 / 28
Some Important Functions
3 Functions
Ceiling. f (x) = ⌈x⌉ the least integer Floor. f (x) = ⌊x⌋ the greatest
y so that x ≤ y. integer y so that y ≤ x.
Example 3.1. Example 3.2.
a. ⌈1.2⌉ a. ⌊1.8⌋
b. ⌈−1.2⌉
b. ⌊−1.8⌋
c. ⌈1⌉
c. ⌊−5⌋
Example 3.3. ⌈−1.1 + ⌊1.1⌋⌉ = . . .
Note 3.1. ⌊x⌋ ≤ x ≤ ⌈x⌉ .
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 16 / 28
Quiz
3 Functions
Q1. Let f be floor function and g be a Q2. Study relations in the set of real
ceiling function. Which of the following numbers R. x+1
is true? (i) f : R → R : f (x) = 2 .
x +3
Select one: x
(ii) f : R → R : f (x) = 2 .
2x − 6x − 1
a. f(-3.1)=-3 Select one:
a. (i) is not a function, (ii) is not a
b. g(-4.5)=-4 function.
b. (i) is a function, (ii) is a function.
c. g(7)=8 c. (i) is a function, (ii) is not a
function.
d. f(5.3)=6 d. (i) is not a function, (ii) is a
function.
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 17 / 28
One-to-One Function/Injection
3 Functions
Definition 3.1
A function f : A → B is one-to-one if and only if
∀x, y ∈ A, (x ̸= y) =⇒ f (x) ̸= f (y) ≡ ∀x, y ∈ A, f (x) = f (y) =⇒ x = y.
A function f : A → B is NOT one-to-one if ∃x, y ∈ A, (x ̸= y) ∧ (f (x) ̸= f (y)).
Example 3.4. The following functions
are one to one or not:
a. f : Z → Z, f (x) = x2
b. f : [0, +∞) → R, f (x) = x2 + 1
Figure: A one-to-one function.
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 18 / 28
Onto Function/Surjection
3 Functions
Definition 3.2
A function f : A → B is onto if and only if ∀y ∈ B, ∃x ∈ A|f (x) = y.
Example 3.5. The following functions
are onto or not
a. f : Z → Z, f (x) = x2
b. f : Z → Z, f (x) = x + 1
Figure: An onto function.
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 19 / 28
Bijection/One-to-one correspondence
3 Functions
Definition 3.3
The function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto.
Example 3.6. The following functions are bijection or not
1. f : R → R, f (x) = x + 1
2. f : Z → N, f (x) = (2 − x)2
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 20 / 28
Inverse Functions
3 Functions
Definition 3.4
Let f : A → B be a bijection. Then the inverse function of f , denoted by f −1 is the function that
assigns each element y in B the unique element x in A such that f(x) = y. Thus f −1 (y) = x.
f −1 : B −→ A
y 7−→ f −1 (y) = x
Example 3.7. Is the function
f (x) = x + 1 from R to R invertible?
What is its inverse?
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 21 / 28
Inverse Functions
3 Functions
Definition 3.5
Let f : A → B be a bijection. Then the inverse function of f , denoted by f −1 is the function that
assigns each element y in B the unique element x in A such that f(x) = y. Thus f −1 (y) = x.
f −1 : B −→ A
y 7−→ f −1 (y) = x
Example 3.8. Is the function
f (x) = x + 1 from R to R invertible?
What is its inverse?
Solution.
f : R → R, f (x) = x + 1 is bijection.
=⇒ ∃f −1 : R → R, f −1 (y) = y − 1.
We also write f −1 (x) = x − 1.
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 21 / 28
Function composition
3 Functions
Definition 3.6
Consider the function f : A −→ B, and the function g : D −→ E with domain D and range E. If B ⊂ D,
then the composite function (g ◦ f )(x) is the function with domain A such that (g ◦ f )(x) = g(f (x)).
Example 3.9. Given
f (x) = x2 + 1, g(x) = 1/x.
1. Find (g ◦ f )(x), (f ◦ g)(x) and state its
domain and range.
2. Evaluate (g ◦ f )(4), (g ◦ f )(−1/2).
Note 3.2. f ◦ g ̸= g ◦ f .
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 22 / 28
Function composition
3 Functions
Definition 3.7
Consider the function f : A −→ B, and the function g : D −→ E with domain D and range E. If B ⊂ D,
then the composite function (g ◦ f )(x) is the function with domain A such that (g ◦ f )(x) = g(f (x)).
Example 3.10. Given
f (x) = x2 + 1, g(x) = 1/x.
1. Find (g ◦ f )(x), (f ◦ g)(x) and state its
domain and range.
2. Evaluate (g ◦ f )(4), (g ◦ f )(−1/2).
Solution.
(g ◦ f )(x): D = R, the range is (0, 1].
(f ◦ g)(x): D = R \ {0}, the range is
Note 3.3. f ◦ g ̸= g ◦ f . (1, +∞)
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 22 / 28
Table of Contents
4 Sequences
▶ Sets
▶ Set operations
▶ Functions
▶ Sequences
▶ Summations
Sequences
4 Sequences
Definition 4.1
A sequence is a function from a subset of the set of integers (usually either the set {0, 1, 2, . . . } or the set
{1, 2, 3, . . . }) to a set S. We use the notation an to denote the image of the integer n. We call an a term of
the sequence.
f : N −→ R
n 7−→ f (n) = an
The list of the terms of this sequence, beginning with a1 , namely, a1 , a2 , a3 , a4 , . . . , an−1 , an , an+1 , . . . .
Example 4.1.
1 1 1 1
1. Consider the sequence {an }, where an = =⇒ 1, , , , . . .
n 2 3 4
2. Geometric progression: a, ar, ar2 , ..., arn , ... (r: common ratio).
3. Arithmetic progression: a, a + d, a + 2d, ..., a + nd, ... (d: common
difference).
4. Constant progression: c, c, c, c, c, c, . . . (c ∈ R).
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 24 / 28
Recurrence Relations
4 Sequences
Definition 4.2
A recurrence relation for the sequence {an } is an equation that expresses an in terms of one or more of the
previous terms of the sequence, namely, a0 , a1 , . . . , an1 , ∀n ∈ Z (n ≥ n0 , n0 ∈ Z+ ). A sequence is called a
solution of a recurrence relation if its terms satisfy the recurrence relation. (A recurrence relation is said to
recursively define a sequence. We will explain this alternative terminology in Chapter 5.)
Example 4.2. Let {an } be a sequence that satisfies the recurrence relation
an = an−1 + 3 for n = 1, 2, 3, . . . , and suppose that a0 = 2. What are a1 , a2 , and
a3 ?
Definition 4.3
The Fibonacci sequence, f0 , f1 , f2 , . . . , is defined by the initial conditions f0 = 0, f1 = 1, and the
recurrence relation fn = fn−1 + fn−2 for n = 2, 3, 4, . . .
Example 4.3. Find the Fibonacci numbers f2 , f3 , f4 , f5 , and f6 .
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 25 / 28
Table of Contents
5 Summations
▶ Sets
▶ Set operations
▶ Functions
▶ Sequences
▶ Summations
Summations
5 Summations
ai = a1 + a2 + ... + ak Example 5.1. What is the value of
k
• Notation.
P
i=1 4
• Properties. a. (i + 2)2
P
k k k i=1
1. (cai + dbi ) = c ai + d
P P P
bi 6
i=1 i=1 i=1
b. 2
P
k
2. a = a + a + .... + a = ka i=1
P
i=1 50
c. 2k
P
Note 5.1. k=1
n n(n + 1)
• k = 1 + 2 + ... + n =
P
1000
2 d. (−1)i .
Q
k=1
i=1
n 1 − rn+1
• ark = a (r ̸= 1)
P
3 P
4
k=0 1−r e.
P
ij
i=1 j=2
Ly Anh Duong Chapter 2 Basic Structures: Sets, Functions, Sequences
duongla3@[Link]
& Sums 27 / 28
Q&A
Thank you for listening!
