Chapter 2

Basic Structures Set, Functions,

Sequences and Sums
MAD101
Ly Anh Duong

duongla3@[Link]
 Table of Contents
1 Sets

▶ Sets

▶ Set operations

▶ Functions

▶ Sequences

▶ Summations

▶ Problems
 Definitions and notation
1 Sets

Definition. A set is an unordered collection of elements.

Examples.
• {1, 2, 3} is the set containing “1” and “2” and “3.”
• {1, 1, 2, 3, 3} = {1, 2, 3} since repetition is irrelevant.
• {1, 2, 3} = {3, 2, 1} since sets are unordered.
• {1, 2, 3, . . . } is a way we denote an infinite set (in this case, the natural
numbers).
• ∅ = is the empty set, or the set containing no element.
Note. ∅ =
̸ {∅}

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 3 / 76
 Definitions and notation
1 Sets

• x ∈ S means “x is an element of set S.”

• x∈/ S means “x is not an element of set S.”
• A ⊆ B means “A is a subset of B.”
or, “B contains A.”
or, “every element of A is also in B.”
or, ∀x((x ∈ A) → (x ∈ B))

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 4 / 76
 Definitions and notation
1 Sets

• A ⊆ B means “A is a subset of B.”

• A ⊇ B means “A is a superset of B.”
• A = B if and only if A and B have exactly the same elements
Iff, A ⊆ B and B ⊆ A
Iff, A ⊆ B and A ⊇ B
Iff, ∀x((x ∈ A) ↔ (x ∈ B))
Note. To show equality of sets A and B, show: A ⊆ B and B ⊆ A

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 5 / 76
 Definitions and notation
1 Sets

A ⊂ B means “A is a proper subset of B.” That means

A ⊆ B and A ̸= B
∀x((x ∈ A) → (x ∈ B)) ∧ ∃x((x ∈ B) ∧ (x ∈
/ A))

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 6 / 76
 Example.
1 Sets

• {1, 2, 3} ⊆ {1, 2, 3, 4, 5}
• {1, 2, 3} ⊂ {1, 2, 3, 4, 5}
• ∅ ⊆ {1, 2, 3}
• Is ∅ ∈ {1, 2, 3}
• Is ∅ ⊆ {∅, 1, 2, 3}
• Is ∅ ∈ {∅, 1, 2, 3}

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 7 / 76
 Example.
1 Sets

• Is {x} ⊆ {x}
• Is {x} ∈ {x, {x}}
• Is {x} ⊆ {x, {x}}
• Is {x} ∈ {x}

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 8 / 76
 Ways to define sets
1 Sets

• Explicitly: {John, Paul, George, Ringo}

• Implicitly: {1, 2, 3, . . . }, or{2, 3, 5, 7, 11, 13, 17, . . . }
• Set builder: {x : x is prime}, {x|x is odd}
• In general {x : P (x)}, where P(x) is some predicate. We read “the set of all x
such that P(x)”

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 9 / 76
 Cardinality
1 Sets

If S is finite, then the cardinality of S, |S|, is the number of distinct elements in S.

Example.
S = {1, 2, 3} → |S|=3
S = {2, 4, 1, 7} → |S|=4
S = ∅ → |S|=0
S = {∅, {∅}, {∅, {∅}}} |S|=3
S = {1, 2, 3, ....} → |S| is infinite.

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 10 / 76
 Power sets
1 Sets
If S is a set, then the power set of S is P (S) = 2S = {x : x ⊆ S}. We say, “P(S) is
the set of all subsets of S.”
Example.
• If S = {a} then 2S = {∅, {a}}
• If S = {a, b} then 2S = {∅, {a}, {b}, {a, b}}
• If S = ∅ then 2S = {∅}
• If S = {∅, {∅}} then 2S = {∅, {∅}, {{∅}}, {∅, {∅}}}
Note. If S finite, then |2S | = 2|S| (If |S| = n, then |2S | = 2n )
• If S = {a} then 2S = {∅, {a}} → 2S = 2
• If S = {a, b} then 2S = {∅, {a}, {b}, {a, b}} → |2S | = 22 = 4
• If S = ∅ then 2S = {∅} → |2S | = 20 = 1
• If S = {∅, {∅}} then 2S = {∅, {∅}, {{∅}}, {∅, {∅}}} → |2S | = 22 = 4
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 11 / 76
 Cartesian Product
1 Sets

The Cartesian Product of two sets A and B is A × B = {(a, b) : a ∈ A ∧ b ∈ B}

Example.
If A = {Lâm, Bình, Chi}, and B = {Xung, Ca}, then
A × B= {(Lâm, Xung), (Lâm, Ca), (Bình, Xung), (Bình, C), (Chi, Xung),
(Chi, Ca)}
Notes.
• (a, b) = (c, d) iff a = c, and b = d
• A,B finite → |A × B| = |A||B|
If A = {Lâm, Bình, Chi} → |A|=3, and B = {Xung, Ca} → |B|=2
A × B= {(Lâm, Xung), (Lâm, Ca), (Bình, Xung), (Bình, C), (Chi, Xung),
(Chi, Ca)} → |A × B| = 3.2 = 6
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 12 / 76
 Cartesian Product
1 Sets

The Cartesian Product of n sets A1 , A2 , . . . , An is:

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

Note.

An = A × A × A × ... × A(n times) = {(a1 , a2 , ...., an ) : ai ∈ A, ∀i = 1, 2, ..., n}

Example.
A = {a, b}, B = {1, 2, 3}, C = {0, 1}
A×B×C =
{(a, 1, 0), (a, 1, 1), (a, 2, 0), (a, 2, 1), (a, 3, 0), (a, 3, 1), (b, 1, 0), (b, 1, 1), (b, 2, 0), (b, 2, 1), (b
|A × B × C| = |A||B||C| = 2.3.2 = 12
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 13 / 76
 Quizz
1 Sets

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 14 / 76
 Quizz
1 Sets

Ans: d (|A|=2 → |A × A| = 4 → P(A × A)=24 = 16)

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 14 / 76
 Table of Contents
2 Set operations

▶ Sets

▶ Set operations

▶ Functions

▶ Sequences

▶ Summations

▶ Problems
 Union
2 Set operations

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 16 / 76
 Intersection
2 Set operations

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 17 / 76
 Example.
2 Set operations

If A = {x : x is a US president}, and B = {x : x is in this room}, then

A ∩ B = {x : x is a US president in this room} =∅.

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 18 / 76
 Complement
2 Set operations

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 19 / 76
 Difference and symmetric difference
2 Set operations

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 20 / 76
 Set Identities
2 Set operations

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 21 / 76
 Set Identities
2 Set operations

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 22 / 76
 Set Identities
2 Set operations

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 23 / 76
 Set Identities
2 Set operations

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 24 / 76
 Set Identities
2 Set operations

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 25 / 76
 Computer Representation of Sets
2 Set operations

• Let U = {x1 , x2 , . . . , xn }, and choose an arbitrary order of the elements of U,

say
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 ai = 1 if xi ∈ A, and 0 otherwise.
Example. Let U = {x1 , x2 , x3 , x4 , x5 , x6 } and A = {x1 , x3 , x5 , x6 }. Then the bit
string representation of A is 101011

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 26 / 76
 Computer Representation of Sets
2 Set operations

Let U = {x1 , x2 , x3 , x4 , x5 , x6 } and A = {x1 , x3 , x5 , x6 }, B = {x2 , x3 , x6 }. Then we

have a quick way of finding the bit string corresponding to of A ∪ B and A ∩ B

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 27 / 76
 Quizz
2 Set operations

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 28 / 76
 Quizz
2 Set operations

Ans: C
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 28 / 76
 Table of Contents
3 Functions

▶ Sets

▶ Set operations

▶ Functions

▶ Sequences

▶ Summations

▶ Problems
 Introduction
3 Functions
Definition. A function f is a rule that assigns to each element x in a set A
exactly one element y=f(x) in a set B.

• A is the domain, B is the codomain of f.

• b = f(a) is the image of a and a is the preimage of b.
• The range of f is the set {f (a), a ∈ A}
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 30 / 76
 Example.
3 Functions

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 31 / 76
 Example.
3 Functions

What are functions?

1. f : Z → R : f (x) = x2 + 2 →

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 32 / 76
 Example.
3 Functions

What are functions?

1. f : Z → R : f (x) = x2 + 2 → YES
1
2. f : Z → R : f (x) = + 5x →
(x − 1)2

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 32 / 76
 Example.
3 Functions

What are functions?

1. f : Z → R : f (x) = x2 + 2 → YES
1
2. f : Z → R : f (x) = + 5x → NO
(x − 1)2
2x + 5
3. f : R → R : f (x) = →
7

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 32 / 76
 Example.
3 Functions

What are functions?

1. f : Z → R : f (x) = x2 + 2 → YES
1
2. f : Z → R : f (x) = + 5x → NO
(x − 1)2
2x + 5
3. f : R → R : f (x) = → YES
7
(2x + 5)2
4. f : Z → R : f (x) = →
7 − 2x
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 32 / 76
 Example.
3 Functions

What are functions?

1. f : Z → R : f (x) = x2 + 2 → YES
1
2. f : Z → R : f (x) = + 5x → NO
(x − 1)2
2x + 5
3. f : R → R : f (x) = → YES
7
(2x + 5)2
4. f : Z → R : f (x) = → YES
7 − 2x
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 32 / 76
 Functions as sets of ordered pairs
3 Functions

A function can be defined as a set of ordered pairs: {(a, b)|b = f (a), a ∈ A}

Example. {(2, 4), (3, 5), (7, 3)} is a function that says ”2 is related to 4”, ”3 is
related to 5”, ”7 is related to 3”
Notes.
• The domain is {2, 3, 7} (input values)
• The range is {4, 5, 3} (output values)

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 33 / 76
 Some Important Functions
3 Functions

1. Ceiling. f (x) = ⌈x⌉ the least integer y so that x ≤ y. Example.

a. ⌈1.2⌉ =

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 34 / 76
 Some Important Functions
3 Functions

1. Ceiling. f (x) = ⌈x⌉ the least integer y so that x ≤ y. Example.

a. ⌈1.2⌉ = 2
b. ⌈−1.2⌉ =

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 34 / 76
 Some Important Functions
3 Functions

1. Ceiling. f (x) = ⌈x⌉ the least integer y so that x ≤ y. Example.

a. ⌈1.2⌉ = 2
b. ⌈−1.2⌉ = − 1
c. ⌈1⌉ = 1
2. Floor. f (x) = ⌊x⌋ the greatest integer y so that y ≤ x
a. ⌊1.8⌋ =

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 34 / 76
 Some Important Functions
3 Functions

1. Ceiling. f (x) = ⌈x⌉ the least integer y so that x ≤ y. Example.

a. ⌈1.2⌉ = 2
b. ⌈−1.2⌉ = − 1
c. ⌈1⌉ = 1
2. Floor. f (x) = ⌊x⌋ the greatest integer y so that y ≤ x
a. ⌊1.8⌋ = 1
b. ⌊−1.8⌋ =

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 34 / 76
 Some Important Functions
3 Functions

1. Ceiling. f (x) = ⌈x⌉ the least integer y so that x ≤ y. Example.

a. ⌈1.2⌉ = 2
b. ⌈−1.2⌉ = − 1
c. ⌈1⌉ = 1
2. Floor. f (x) = ⌊x⌋ the greatest integer y so that y ≤ x
a. ⌊1.8⌋ = 1
b. ⌊−1.8⌋ = − 2
c. ⌊−5⌋ =

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 34 / 76
 Some Important Functions
3 Functions

1. Ceiling. f (x) = ⌈x⌉ the least integer y so that x ≤ y. Example.

a. ⌈1.2⌉ = 2
b. ⌈−1.2⌉ = − 1
c. ⌈1⌉ = 1
2. Floor. f (x) = ⌊x⌋ the greatest integer y so that y ≤ x
a. ⌊1.8⌋ = 1
b. ⌊−1.8⌋ = − 2
c. ⌊−5⌋ = − 5

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 34 / 76
Note. ⌊x⌋ ≤ x ≤ ⌈x⌉ . What is ⌈−1.1 + ⌊1.1⌋⌉

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 35 / 76
Note. ⌊x⌋ ≤ x ≤ ⌈x⌉ . What is ⌈−1.1 + ⌊1.1⌋⌉ = 0

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 35 / 76
 Quizz
3 Functions

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 36 / 76
 Quizz
3 Functions

Ans: b
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 36 / 76
 Quizz
3 Functions

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 37 / 76
 Quizz
3 Functions

Ans: d
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 37 / 76
 One-to-One Functions
3 Functions

Definition.A function f : A → B is one-to-one (injective, an injection) if

∀x, y(f (x) = f (y) → x = y)
Remarks.
• A function f : A → B is one-to-one (injective, an injection) iff
∀x, y(x ̸= y) → f (x) ̸= f (y)
• A strictly increasing (tăng) or strictly decreasing function on an interval
I is one-to-one on I
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 38 / 76
 Example.
3 Functions
The following functions are one to one or not:
1. f : Z → Z, f (x) = x2

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 39 / 76
 Example.
3 Functions
The following functions are one to one or not:
1. f : Z → Z, f (x) = x2 (No)
2. f : [0, +∞) → R, f (x) = x2 + 1

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 39 / 76
 Example.
3 Functions
The following functions are one to one or not:
1. f : Z → Z, f (x) = x2 (No)
2. f : [0, +∞) → R, f (x) = x2 + 1 (Yes)
3. Function

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 39 / 76
 Example.
3 Functions
The following functions are one to one or not:
1. f : Z → Z, f (x) = x2 (No)
2. f : [0, +∞) → R, f (x) = x2 + 1 (Yes)
3. Function

(No)
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 39 / 76
 Onto Functions
3 Functions

Definition. A function f : A → B is onto (surjective, a surjection) if

∀b ∈ B, ∃a ∈ A|f (a) = b
Example. The following functions are onto or not
1. f : Z → Z, f (x) = x2

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 40 / 76
 Onto Functions
3 Functions

Definition. A function f : A → B is onto (surjective, a surjection) if

∀b ∈ B, ∃a ∈ A|f (a) = b
Example. The following functions are onto or not
1. f : Z → Z, f (x) = x2 (No)
2. f : Z → Z, f (x) = x + 1
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 40 / 76
 Onto Functions
3 Functions

Definition. A function f : A → B is onto (surjective, a surjection) if

∀b ∈ B, ∃a ∈ A|f (a) = b
Example. The following functions are onto or not
1. f : Z → Z, f (x) = x2 (No)
2. f : Z → Z, f (x) = x + 1 (Yes)
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 40 / 76
 Example.
3 Functions
Function

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 41 / 76
 Example.
3 Functions
Function

(No)
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 41 / 76
 Bijection
3 Functions

Definition. A function f : A → B is bijective if it is one-to-one and onto. We

also say that f is a bijection.
Example. The following functions are bijection or not
1. f : R → R, f (x) = x3 + 1

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 42 / 76
 Bijection
3 Functions

Definition. A function f : A → B is bijective if it is one-to-one and onto. We

also say that f is a bijection.
Example. The following functions are bijection or not
1. f : R → R, f (x) = x3 + 1 (Yes)
2. Function

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 42 / 76
 Bijection
3 Functions

Definition. A function f : A → B is bijective if it is one-to-one and onto. We

also say that f is a bijection.
Example. The following functions are bijection or not
1. f : R → R, f (x) = x3 + 1 (Yes)
2. Function

(Yes)
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 42 / 76
 Example.
3 Functions

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 43 / 76
 Quizz
3 Functions

√
Ans: d (x = ± y + 2, y = 2 → ∄x ∈ Z)
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 44 / 76
 Quizz
3 Functions

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 45 / 76
 Quizz
3 Functions

Ans: 6.5.4
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 45 / 76
 Quizz
3 Functions

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 46 / 76
 Quizz
3 Functions

Ans: 16 (|B × B| = |B||B| = 2.2 = 4,mỗi phần tử thuộc B 2 có 2 cách chọn ảnh)
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 46 / 76
 Inverse Functions
3 Functions

Definition. Let f : A → B be a bijection. Then the inverse function of f ,

denoted by f −1 is the function that assigns each element b in B the unique
element a in A such that f(a) = b. Thus f −1 (b) = a.
Example.

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 47 / 76
 Example.
3 Functions

• Is the function f (x) = x2 from Z to Z invertible? (i.e. the inverse function

exists)
The function f is not onto. Therefore it is not a bijection, and hence not
invertible
• Is the function f(x) = x + 1 from Z to Z invertible?
The function f is a bijection so it is invertible.

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 48 / 76
 Example.
3 Functions

Is the function f(x) = x + 1 from Z to Z invertible? What is its inverse?

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 49 / 76
 Compositions of Functions
3 Functions

Definition. The composition of a function g : A → B and a function f : B → C

is the function f ◦ g : A → C defined by

f ◦ g(x) = f (g(x))

Note. The domain of fog is also the domain of g, and the codomain of fog is also
the codomain of f.

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 50 / 76
 Arrow diagram for f ◦ g
3 Functions

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 51 / 76
 Example.
3 Functions

let f (x) = x2 and g(x) = x – 3 are functions from R to R. Find f ◦ g and g ◦ f

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 52 / 76
 Table of Contents
4 Sequences

▶ Sets

▶ Set operations

▶ Functions

▶ Sequences

▶ Summations

▶ Problems
 Definition.
4 Sequences

A sequence {ai } is a function f : N → R, where we write ai to indicate f (i).

Example.
• 1, 1/2, 1/3, ..., 1/n, ...
• Finite sequence {ai }, where ai = i, i = 0, 1, 2: a0 = 0, a1 = 1, a2 = 2
• Infinite sequence {ai }, where ai = i2 : a0 = 0, a1 = 1, a2 = 4, ...
• a0 = 1, an = 2an−1 − 3, n = 1, 2, ... → a1 = −1 a2 = −5....
• Geometric progression: a, ar, ar2 , ..., arn , ...
• Arithmetic progression: a, a + d, a + 2d, ..., a + nd, ...

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 54 / 76
 Table of Contents
5 Summations

▶ Sets

▶ Set operations

▶ Functions

▶ Sequences

▶ Summations

▶ Problems
 Introduction
5 Summations

k
P
• Notation. ai = a1 + a2 + ... + ak
i=1
• Properties.
k
P k
P k
P
1. (cai + dbi ) = c ai + d bi
i=1 i=1 i=1
Pk
2. a = a + a + .... + a = ka
i=1

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 56 / 76
 Familiar Summation Formulae
5 Summations

n
P n(n + 1)
• k = 1 + 2 + ... + n =
k=1 2

n 1 − rn+1
ark = a (r ̸= 1)
P
•
k=0 1−r

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 57 / 76
 Some Useful Summation Formulae
5 Summations

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 58 / 76
 Cardinality
5 Summations

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 59 / 76
 Quizz
5 Summations

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 60 / 76
 Quizz
5 Summations

Ans: C
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 60 / 76
 Quizz
5 Summations

Ans: b
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 61 / 76
 Quizz
5 Summations

Ans: C
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 62 / 76
 Quizz
5 Summations

Ans: a & c
Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences
duongla3@[Link]
and Sums 63 / 76
 Table of Contents
6 Problems

▶ Sets

▶ Set operations

▶ Functions

▶ Sequences

▶ Summations

▶ Problems
 Sets
6 Problems

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 65 / 76
 Sets
6 Problems

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 66 / 76
 Sets
6 Problems

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 67 / 76
 Sets
6 Problems

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 68 / 76
 Set operations
6 Problems

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 69 / 76
 Functions
6 Problems

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 70 / 76
 Functions
6 Problems

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 71 / 76
 Functions
6 Problems

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 72 / 76
 Functions
6 Problems

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 73 / 76
 Sequences and Summations
6 Problems

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 74 / 76
 Sequences and Summations
6 Problems

Ly Anh Duong Chapter 2 Basic Structures Set, Functions, Sequences

duongla3@[Link]
and Sums 75 / 76
 Q&A
Thank you for listening!