DISCRETE MATHEMATICS

&
APPLICATIONS

1
Chapter 2: Basic structures

2.1. Sets

2.2. Set Operations

2.3. Functions

2.4. Sequences and Summations

2
2.1 Sets

3
DEFINITION
Definitions. A set is an unordered collection of objects. An object of a set is called an element
(or member) of that set.
∎ We write 𝑎 ∈ 𝐴 to denote that 𝑎 is an element of the set 𝐴.
∎ Otherwise, we write 𝑎 ∉ 𝐴 to denote that 𝑎 is not an element of the set 𝐴.

Examples. ℕ = the set of natural numbers 0, 1, 2, …

ℤ = the set of integers −2, −1, 0, 1, 2, …

ℚ = the set of rational numbers.

ℝ = the set of real numbers.

4
REPRESENTING A SET
There are several ways to represent a set.

Statement form: describing elements of a set by using a specified rule.

Example: 𝐴 is the set of natural number less than or equal to 9.

Roster form: listing all elements of a set between curly brackets.

Example: 𝐴 = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 or briefly, 𝐴 = 0, 1, … , 9 .

Set-builder form: specifying a set as a selection from a larger set, determined by some conditions.

Example: 𝐴 = 𝑎 | 𝑎 ∈ ℕ, 𝑎 ≤ 9 or 𝐴 = 𝑎 ∈ ℕ | 𝑎 ≤ 9

5
FINITE SETS AND CARDINALITY

Definition. A finite set is a set that has finitely many (distinct) elements.
If 𝐴 is a finite set that has exactly 𝑛 (distinct) elements then we say that 𝑛 is the cardinality of 𝐴
and write 𝐴 = 𝑛.

Example. Find cardinality for each of the following sets.

𝐴 = 𝑎, 𝑏, 𝑎, 1, 𝑏, 𝑐 . 𝐶 = 𝑛 ∈ ℤ 𝑛2 ≤ 1000}
𝐵 = 𝑎, 𝑎 , 𝑏, 𝑏 , 𝑎, 𝑏 . 𝐷 = 𝑎 ∈ ℚ 0 ≤ 𝑎 ≤ 1}.

Definition. The empty set, denoted ∅, is the set that has no elements or equivalently, is the set
has cardinality 0.

6
SET RELATIONS
Definition. Two sets 𝐴 and 𝐵 are equal if they have the same elements.

Example. 𝑎, 𝑎 , 𝑏, 𝑏 , 𝑎, 𝑏 , 𝑏, 𝑎, 𝑐 = 𝑎, 𝑏, 𝑐, 𝑎 , 𝑏 , 𝑎, 𝑏 .

Definition. Let 𝐴 and 𝐵 be two sets.

∎ If every element of 𝐴 is also an element of 𝐵 then we say that 𝐴 is a subset of 𝐵 and write 𝐴 ⊆ 𝐵.
∎ If 𝐴 ⊆ 𝐵 and 𝐴 ≠ 𝐵 then we say that 𝐴 is a proper subset of 𝐵 and write 𝐴 ⊂ 𝐵.

Remark. ∎ 𝐴 ⊆ 𝐵 if and only if the prosition ∀𝑎 𝑎 ∈ 𝐴 ⟶ 𝑎 ∈ 𝐵 is true.

∎ 𝐴 = 𝐵 if and only if 𝐴 ⊆ 𝐵 and 𝐵 ⊆ 𝐴.

7
EXAMPLES

8
CARTESIAN PRODUCTS AND POWER SETS
Definition. The Cartesian product of two sets 𝐴 and 𝐵 is the set of all ordered pairs 𝑎, 𝑏 where
𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵:
𝐴×𝐵 = 𝑎, 𝑏 𝑎 ∈ 𝐴 ∧ b ∈ 𝐵}.

Example. Let 𝐴 = 𝑎, 1, 𝑐, 𝑎 and 𝐵 = 𝑏, 1 . Then we have

𝐴×𝐵 = 𝑎, 𝑏 , 𝑎, 1 , 1, 𝑏 , 1,1 , 𝑐, 𝑏 , 𝑐, 1

Definition. The power set of a set 𝐴, denoted by 𝑃 𝐴 , is the set of all subsets of 𝐴.

Exercise. Suppose that 𝐴 = 𝑚 and 𝐵 = 𝑛.

a) Show that 𝐴 × 𝐵 = 𝑚𝑛.
b) Show that 𝑃 𝐴 = 2𝑚 .
9
 2.2
Set Operations

10
BASIC OPERATIONS ON SETS

Definition. Let 𝐴 and 𝐵 be two sets.

1) Union of 𝐴 and 𝐵 is the set 𝐴 ∪ 𝐵 = 𝑥 | 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵 .

2) Intersection of 𝐴 and 𝐵 is the set 𝐴 ∩ 𝐵 = 𝑥 | 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵 .

3) Difference of 𝐴 with respect to 𝐵 is the set 𝐴 − 𝐵 = 𝑥 | 𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐵 .

4) Symmetric difference of 𝐴 and 𝐵 is the set 𝐴 ⊕ 𝐵 = 𝑥 | 𝑥 ∈ 𝐴 ⊕ 𝑥 ∈ 𝐵 .

5) Complement of 𝐴 with respect to a universal set 𝑈 is the set 𝐴ҧ = 𝑈 − 𝐴.

Exercise. Use Venn diagrams to depict the set operations mentioned above.

11
EXERCISES

Exercise. a) Is it true that 𝐴 − 𝐵 is a subset of 𝐴 ⊕ 𝐵?

b) Find conditions on 𝐴 and 𝐵 such that 𝐴 ∪ 𝐵 = 𝐴 ⊕ 𝐵.
c) Prove that 𝐴 ⊕ 𝐵 = 𝐴 ∪ 𝐵 − A ∩ 𝐵 .
d) Prove that 𝐴 − 𝐵 = 𝐴 − 𝐴 ∩ 𝐵 .

12
SET IDENTITIES

13
COMPUTER REPRESENTATIONS OF SETS

14
 2.3
Functions

15
DEFINITON
Definition. Let 𝐴 and 𝐵 be two sets. A function 𝑓 from 𝐴 to 𝐵 is a rule that assigns each element
𝑎 ∈ 𝐴 to a unique element 𝑓 𝑎 ∈ 𝐵. We will write 𝑓: 𝐴 ⟶ 𝐵 to denote that 𝑓 is a function from
𝐴 to 𝐵.
∎ The set 𝐴 is called the domain and 𝐵 is called the codomain of 𝑓.
∎ If 𝑓 𝑎 = 𝑏 then we say that 𝑏 is the image of 𝑎, and 𝑎 is the preimage of 𝑏.

16
IMAGE AND PREIMAGE
Definition. Let 𝑓: 𝐴 ⟶ 𝐵 be a function.
1) Let 𝑆 ⊆ 𝐴 be a subset of 𝐴. The image of 𝑺 is the set
𝑓 𝑆 = 𝑓(𝑎)| 𝑎 ∈ 𝑆 .
In particular, the range (or image) of 𝑓 is the set 𝑓 𝐴 .

2) Let 𝑇 ⊆ 𝐵 be a subset of 𝐵. The preimage of 𝑇 is the set

𝑓 −1 𝑇 = 𝑎 ∈ 𝐴 | 𝑓 𝑎 ∈ 𝑇 .

17
EXERCISES

1. Let 𝑓 be a function as depicted below.

Find the domain, codomain and range of 𝑓.

2. Let R be the relation with ordered pairs (Abdul, 22), (Brenda, 24), (Carla, 21), (Desire, 22), (Eddie,
24), and (Felicia, 22). Here each pair consists of a graduate student and his/her age. Specify a
function determined by this relation.

18
FLOOR AND CEILING FUNCTIONS
Definition. 1) Floor function is a function from ℝ to ℤ given by
𝑥 = the geatest integer that not larger than 𝑥.
2) Ceiling function is a function from ℝ to ℤ given by
𝑥 = the smallest integer that not less than 𝑥.

Remark. For every 𝑥 ∈ ℝ, one has

𝑥 − 1 ≤ 𝑥 ≤ 𝑥 ≤ 𝑥 ≤ 𝑥 + 1.

19
INJECTION

Definition. A function 𝑓: 𝐴 ⟶ 𝐵 is said to be injective (or one-to-one) if

𝑓 𝑎1 ≠ 𝑓 𝑎2 for all 𝑎1 ≠ 𝑎2 in 𝐴.
Equivalently, 𝑓 is injective if the proposition ∀𝑎1 ∀𝑎2 𝑓 𝑎1 = 𝑓 𝑎2 ⟶ 𝑎1 = 𝑎2 is true.

20
EXAMPLE

21
SURJECTION

Definition. A function 𝑓: 𝐴 ⟶ 𝐵 is said to be surjective (or onto) if for every 𝑏 ∈ 𝐵, there exists
𝑎 ∈ 𝐴 such that 𝑏 = 𝑓 𝑎 .
In other words, 𝑓 is surjective if the proposition ∀𝑏 ∈ 𝐵 ∃𝑎 ∈ 𝐴 𝑏 = 𝑓 𝑎 is true.

22
EXAMPLE

23
BIJECTION

Definition. A function 𝑓: 𝐴 ⟶ 𝐵 is said to be bijective (or one-to-one correspondence) if it is

both injective and surjective.

Exercise. Show that if 𝑓: 𝐴 ⟶ 𝐵 is an bijection between two finite sets then 𝐴 = 𝐵 .

24
EXAMPLE

25
COMPOSED FUNCTIONS
Definition. Let 𝑔: 𝐴 ⟶ 𝐵 and 𝑓: 𝐵 ⟶ 𝐶 be two functions. The composition of 𝑓 and 𝑔 is the
function 𝑓 ∘ 𝑔: 𝐴 ⟶ 𝐶 given by the formula
𝑓∘𝑔 𝑎 =𝑓 𝑔 𝑎 for every 𝑎 ∈ 𝐴.

26
INVERSES
Definition. Let 𝑓: 𝐴 ⟶ 𝐵 be a bijection. The inverse of 𝑓 is the function from 𝐵 to 𝐴 that assigns
to each 𝑏 ∈ 𝐵 the unique element 𝑎 ∈ 𝐴 such that 𝑓 𝑎 = 𝑏.
We write 𝑓 −1 : 𝐵 ⟶ 𝐴 to denote the inverse of 𝑓.

Exercise. Verify the following statements.

a) 𝑓 −1 is also a bijection.
b) (𝑓 −1 ∘ 𝑓)(𝑎) = 𝑎 for every 𝑎 ∈ 𝐴 and (𝑓 ∘ 𝑓 −1 )(𝑏) = 𝑏 for every 𝑏 ∈ 𝐵.
27
EXERCISES

1) Let 𝑔: 𝐴 ⟶ 𝐵 and 𝑓: 𝐵 ⟶ 𝐶 be two functions.

a) Show that if both 𝑓 and 𝑔 are injective, then so is 𝑓 ∘ 𝑔.
b) Show that if both 𝑓 and 𝑔 are surjective, then so is 𝑓 ∘ 𝑔.
c) Show that if both 𝑓 and 𝑔 are bijective, then so is 𝑓 ∘ 𝑔.
d) Show that if 𝑓 ∘ 𝑔 is surjective, then so is 𝑓.
e) Show that if 𝑓 ∘ 𝑔 is injective, then so is 𝑔.

2) Consider the function 𝑓: ℚ ⟶ ℚ given by the formula

𝑓 𝑎 = 2𝑎 + 1.
a) Prove that 𝑓 is bijective.
b) Find 𝑓 −1 .

28
 2.4
Sequences and Summations

29
SEQUENCES
Definition. Let 𝐴 be a set. A sequence in 𝑨 is a sequence of the form
𝑎1 , 𝑎2 , 𝑎3 , …
where 𝑎𝑛 ∈ 𝐴 for every 𝑛 ≥ 1. We usually write 𝑎𝑛 𝑛 = 1, 2, … } standing for such a sequence.

30
SUMMATIONS

31
SOME BASIC SUMMATIONS

32
EXAMPLES

33
PRACTICE

34
PRACTICE

35
PRACTICE

36
PRACTICE
Find a general formula for each of the following sequences.

37
PRACTICE

38
PRACTICE

39
PRACTICE

40
PRACTICE

41
PRACTICE

42
PRACTICE

43
PRACTICE

44
PRACTICE

45
PRACTICE

46
PRACTICE

47
PRACTICE

48
PRACTICE

49
PRACTICE

50
PRACTICE

51
PRACTICE

52
PRACTICE

53
PRACTICE

54
PRACTICE

55