Discrete Mathematics

Set and Function

Shin Hong
Sets 2

•A set is an unordered collection of objects.

- E.g., the students in this class, the chairs in this room

•The objects in a set are called the elements, or members of

the set.
- A set is said to contain its elements.

•The notation a ∈ A denotes that a is an element of A

Set and
- If a is not a member of A, write a ∉ A Function
Discrete Math.

2021-10-03
Defining a Set: Roster Method 3

• S = {a,b,c,d }
- Order does not mean any thing: S = {a,b,c,d} = {b,c,a,d}

• Each distinct object is either a member or not; listing more than o

nce does not change the set.
S = {a,b,c,d} = {a,b,c,b,c,d}

• Elipses (…) may be used to describe a set without listing all of the
members when the pattern is clear. Set and
S = {a,b,c,d, …,z } Function
Discrete Math.

2021-10-03
Examples 4

• Set of all vowels in the English alphabet:

V = {a,e,i,o,u}
• Set of all odd positive integers less than 10:
O = {1,3,5,7,9}
• Set of all positive integers less than 100:
S = {1,2,3,……..,99}
• Set of all integers less than 0:
S = {…., -3,-2,-1} Set and
Function
Discrete Math.

2021-10-03
Conventional Notions of Important Sets 5

N = natural numbers = {1,2,3, …}

Z = integers = {…,-3,-2,-1,0,1,2,3,…}
Z⁺ = positive integers = {1,2,3,…..}
R = set of real numbers
R+ = set of positive real numbers
C = set of complex numbers.
Q = set of rational numbers
Set and
Function
Discrete Math.

2021-10-03
Defining a Set with Set-Builder Notation 6

• To specify the properties that all members must satisfy:

S = {x | x is a positive integer less than 100}
O = {x | x is an odd positive integer less than 10}
O = {x ∈ Z⁺ | x is odd and x < 10}

• A predicate may be used: S = {x | P(x)}

- Example: S = {x | Prime(x)}
- Example: Positive rational numbers:
Q+ = {x ∈ R | x = 𝑝/𝑞 for 𝑝 ∈ ℤ+ and 𝑞 ∈ ℤ+ } Set and
Function
Discrete Math.

2021-10-03
Defining a Set with Interval Notation 7

[a,b] = {x | a ≤ x ≤ b }
[a,b) = {x | a ≤ x < b } E.g., [a,b)
(a,b] = {x | a < x ≤ b }
(a,b) = {x | a < x < b }
a b

closed interval [a,b]

open interval (a,b) Set and
Function
Discrete Math.

2021-10-03
Universal Set and Empty Set 8

•The universal set U is the set containing everything

currently under consideration.
- Sometimes implicit
- Sometimes explicitly stated U
- Contents depend on the context
V
aei
•The empty set is the set with no elements. ou

- denoted as ∅, or {} Set and

Function
Discrete Math.

2021-10-03
Some things to remember 9

• Sets can be elements of sets.

{{1,2,3}, a, {b,c}}
{N, Z, Q, R}

• The empty set is different from a set containing the empty set.
∅ ≠{∅}

Set and
Function
Discrete Math.

2021-10-03
Set Cardinality 10

Definition: If there are exactly n distinct elements in S where n is

a non-negative integer, we say that S is finite. Otherwise it is infinite.
Definition: The cardinality of a finite set A, denoted by |A|, is the
number of (distinct) elements of A.
Examples:
1. |ø| = 0
2. Let S be the letters of the English alphabet. Then |S| = 26
3. |{1,2,3}| = 3
Set and
4. |{ø}| = 1 Function
5. The set of integers is infinite. Discrete Math.

2021-10-03
Russell’s Paradox 11

•Let R be the set of all sets each of which is not a member

of itself.
- 𝑅 = 𝑆 𝑆 ∉ 𝑆}
- A paradox results from trying to answer the question Bertrand
“Is R a member of itself?” Russell
(1872-1970)
Cambridge,
UK
•Related Paradox: Nobel Prize
Winner
- Henry is a barber who shaves every man if and only if the man
does not shave himself. A paradox results from trying to answer Set and
Function
the question “Does Henry shave himself?”
Discrete Math.

2021-10-03
Set Equality 12

Definition: Two sets are equal if and only if they have the same ele
ments.
- Therefore if A and B are sets, then A and B are equal if and only if

- We write A = B if A and B are equal sets.

{1,3,5} = {3, 5, 1}
{1,5,5,5,3,3,1} = {1,3,5} Set and
Function
Discrete Math.

2021-10-03
Another look at Equality of Sets 13

• Recall that two sets A and B are equal, denoted by A = B iff

∀𝑥 (𝑥 ∈ 𝐴 ↔ 𝑥 ∈ 𝐵)

• Using logical equivalences we have that A = B iff

∀𝑥 [ 𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐵 ∧ 𝑥 ∈ 𝐵 → 𝑥 ∈ 𝐴 ]

• This is equivalent to
A⊆B and B⊆A
Set and
Function
Discrete Math.

2021-10-03
Subsets 14

Definition: The set A is a subset of B, if and only if every element

of A is also an element of B.
- The notation A ⊆ B is used to indicate that A is a subset of the set B.
- A ⊆ B holds if and only if ∀𝑥 𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐵 is true.
1. Because a ∈ ∅ is always false, ∅ ⊆ S ,for every set S.
2. Because a ∈ S → a ∈ S, S ⊆ S, for every set S.

Set and
Function
Discrete Math.

2021-10-03
Proper Subsets 15

Definition: If A ⊆ B, but A ≠B, then we say A is a proper subset of B,

denoted by A ⊂ B or A ⊆ B
If A ⊂ B, then

U
B
A Set and
Function
Discrete Math.

2021-10-03
Power Sets 16

Definition: The set of all subsets of a set A, denoted P(A), is calle

d the power set of A.
Example: If A = {a,b} then
P(A) = {ø, {a},{b},{a,b}}

• If a set has n elements, then the cardinality of the power set is 2ⁿ.
(In Chapters 5 and 6, we will discuss different ways to show this.)

Set and
Function
Discrete Math.

2021-10-03
Cartesian Product René Descartes 17
(1596-1650)

Definition: The Cartesian Product of two sets A and B, denoted by A × B is

the set of ordered pairs (a, b) where a ∈ A and b ∈ B .

Example:
A = {a,b} B = {1,2,3}
A × B = {(a,1),(a,2),(a,3), (b,1),(b,2),(b,3)}
• c.f. Relation
- A subset R of the Cartesian product A × B is called a relation from the set
A to the set B. Set and
- Will be covered in depth in Chapter 9. Function
Discrete Math.

2021-10-03
Cartesian Product 18

Definition: The cartesian products of the sets A1,A2,……,An, denoted by A1 ×

A2 × …… × An , is the set of ordered n-tuples (a1,a2,……,an) where ai belon
gs to Ai for i = 1, … n.

Example: What is A × B × C where A = {0,1}, B = {1,2} and C = {0,1,2}

Solution: 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,1,2)}
Set and
Function
Discrete Math.

2021-10-03
Tuples 19

• The n-tuple (a1,a2,…..,an) is the ordered collection of objects, whic

h has a1 as its first element and a2 as its second element and so o
n until an as its last element.
- Two n-tuples are equal if and only if their corresponding elements are equal.
• 2-tuples are called ordered pairs.
- The ordered pairs (a,b) and (c,d) are equal if and only if a = c and b = d.

Set and
Function
Discrete Math.

2021-10-03
Union 20

• Definition: Let A and B be sets. The union of the sets A and B, den
oted by A ∪ B, is the set:

• Example: What is {1,2,3} ∪ {3, 4, 5}?

Venn Diagram for A ∪ B

Solution: {1,2,3,4,5}
U
A B Set and
Function
Discrete Math.

2021-10-03
Intersection 21

• Definition: The intersection of sets A and B, denoted by A ∩ B, is

- Note if the intersection is empty, then A and B are said to be disjoint.

• Example: What is? {1,2,3} ∩ {3,4,5} ?
Solution: {3}
• Example:What is? Venn Diagram for A ∩B

{1,2,3} ∩ {4,5,6} ? U
A B Set and
Solution: ∅ Function
Discrete Math.

2021-10-03
Complement 22

Definition: If A is a set, then the complement of the A (with respe

ct to U), denoted by Ā is the set U - A
Ā = {x ∈ U | x ∉ A}
(The complement of A is sometimes denoted by Ac .)
Example: If U is the positive integers less than 100, what is the co
mplement of {x | x > 70}
Solution: {x | x ≤ 70}
Venn Diagram for Complement
U
Set and
Ā Function
A
Discrete Math.

2021-10-03
Difference 23

• Definition: Let A and B be sets. The difference of A and B, denoted

by A – B, is the set containing the elements of A that are not in B. T
he difference of A and B is also called the complement of B with re
spect to A.
A – B = {x | x ∈ A  x ∉ B} = A ∩B

U Venn Diagram for A − B

A Set and
B Function
Discrete Math.

2021-10-03
The Cardinality of the Union of Two Sets 24

• Inclusion-Exclusion
U
|A ∪ B| = |A| + | B| - |A ∩ B|
A B

Venn Diagram for A, B, A ∩ B, A ∪ B

• Example: Let A be the math majors in your class and B be the CS majors. To count
the number of students who are either math majors or CS majors, add the number
of math majors and the number of CS majors, and subtract the number of joint
CS/math majors.
• We will return to this principle in Chapter 6 and Chapter 8 where we will derive a
formula for the cardinality of the union of n sets, where n is a positive integer. Set and
Function
Discrete Math.

2021-10-03
Symmetric Difference (optional) 25

Definition: The symmetric difference of A and B, denoted by

is the set

Example:
U = {0,1,2,3,4,5,6,7,8,9,10}
A = {1,2,3,4,5} B ={4,5,6,7,8}
What is:
- Solution: {1,2,3,6,7,8} U
A B

Set and
Function
Venn Diagram Discrete Math.

2021-10-03
Set Identities 26

• Identity laws

• Domination laws

• Idempotent laws

• Complementation law
Set and
Function
Discrete Math.
Continued on next slide →
2021-10-03
Set Identities 27

• Commutative laws

• Associative laws

• Distributive laws

Set and
Function
Discrete Math.
Continued on next slide →
2021-10-03
Set Identities 28

• De Morgan’s laws

• Absorption laws

• Complement laws Set and

Function
Discrete Math.

2021-10-03
Functions 29

• Let A and B be nonempty sets.

• A function f from A to B, denoted f: A → B is an assignment of each element
of A to exactly one element of B.
• We write f(a) = b if b is the unique element of B assigned by the function
f to the element a of A.

• Functions are sometimes called mappings or transformations.

Students Grades
A
Carlota Rodriguez
B

Sandeep Patel C Set and

Function
Jalen Williams D
Discrete Math.
F
Kathy Scott 2021-10-03
 Functions 30

• A function f: A → B can also be defined as a subset of A× B (a relation).

This subset is restricted to be a relation where no two elements of the
relation have the same first element.
• Specifically, a function f from A to B contains one, and only one ordered
pair (a, b) for every element a∈ A.

Set and
Function
Discrete Math.

2021-10-03
Functions 31

Given a function f: A → B:
• We say f maps A to B or
f is a mapping from A to B.
• A is called the domain of f.
• B is called the codomain of f.
• If f(a) = b,
- then b is called the image of a under f.
- a is called the preimage of b.
Set and
Function
Discrete Math.

2021-10-03
Questions 32

f(a) = ? z A B
a
The image of d is ? z x

b
The domain of f is ? A y
c
The codomain of f is ? B
d z
The preimage of y is ? b
Set and
Function
Discrete Math.

2021-10-03
Question on Functions and Sets 33

• If and S is a subset of A, then

A B
f {a,b,c,} is ? {y,z} a
x

b
f {c,d} is ? {z} y
c Set and
Function
d z
Discrete Math.

2021-10-03
Injections 34

Definition: A function f is said to be 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 function is said to be an injection if it is one-to-one.

A B
a x

v
b
y
c Set and
z Function
d
Discrete Math.

w 2021-10-03
Surjections 35

A function f : A → B is called onto or surjective iff

for every element there is an element
such that .
A function f is called a surjection if it is onto.

A B
a x

b Set and
y
Function
c
Discrete Math.
z
d
2021-10-03
Example 36

Example 1: for f : {a,b,c,d} → {1,2,3}, f(a) = 3, f(b) = 2, f(c) = 1, and

f(d) = 3. Is f an onto function?

Solution: Yes, f is onto since all three elements of the codomain are
images of elements in the domain.

Example 2: Is the function f(x) = x2 from the set of integers onto?

Solution: No, f is not onto since there is no integer x with x2 = −1, Set and
for example. Function
Discrete Math.

2021-10-03
Bijections 37

A function f is a one-to-one correspondence, or a bijection, if it is b

oth one-to-one and onto (surjective and injective).

A B
a x

b
y
c
Set and
d z
Function
w Discrete Math.

2021-10-03
Inverse Functions 38

Definition: Let f be a bijection from A to B. Then the inverse of f,

denoted, is the function from B to A defined as
No inverse exists unless f is a bijection. Why?

Set and
Function
Discrete Math.

2021-10-03
Inverse Functions 39

A f
B A B
a V V
a

b b
W W
c c

d X X Set and
d
Function
Discrete Math.
Y Y
2021-10-03
Questions 40

Example 2: Let f: Z → Z be such that f(x) = x + 1. Is f invertible,

and if so, what is its inverse?
Solution: The function f is invertible because it is a one-to-one
correspondence. The inverse function f-1 reverses the
correspondence so f-1 (y) = y – 1.

Example 3: Let f: R → R be such that 𝑓 𝑥 = 𝑥 2 .

Is f invertible, and if so, what is its inverse?
Set and
Solution: The function f is not invertible because it is not one-to-one. Function
Discrete Math.

2021-10-03
Composition 41

• Definition: Let f: B → C, g: A → B. The composition of f with g, denoted

is the function from A to C defined by

Set and
Function
Discrete Math.

2021-10-03
Composition 42

g f
A B C A C
V a
a h h
b i b
W i
c
c
X j
d
d j
Y

Set and
Function
Discrete Math.

2021-10-03
Composition 43

Example 1: If and , then

and

Set and
Function
Discrete Math.

2021-10-03
Composition Questions 44

Example 2: Let g be a function from {a,b,c} to itself s.t.

g(a) = b, g(b) = c, and g(c) = a.

Let f be a function from {a,b,c} to {1,2,3} s.t.

f(a) = 3, f(b) = 2, and f(c) = 1.
What is the composition of f and g, and what is the composition of g and f.
Solution: The composition f∘g is defined by
𝑓 ∘ 𝑔 (𝑎) = 𝑓(𝑔(𝑎)) = 𝑓(𝑏) = 2.
𝑓 ∘ 𝑔 (𝑏) = 𝑓(𝑔(𝑏)) = 𝑓(𝑐) = 1.
𝑓 ∘ 𝑔 (𝑐) = 𝑓(𝑔(𝑐)) = 𝑓(𝑎) = 3. Set and
Function
Note that 𝑔 ∘ 𝑓 is not defined, because the range of f is not a subset Discrete Math.
of the domain of g. 2021-10-03
Graphs of Functions 45

• Let f be a function from the set A to the set B. The graph of the fun
ction f is the set of ordered pairs {(a,b) | a ∈A and f(a) = b}.

Set and
Function
Graph of f(n) = 2n + 1 Graph of f(x) = x2 Discrete Math.

from Z to Z from Z to Z 2021-10-03

Partial Functions 46

A partial function f from a set A to a set B, denoted 𝑓: 𝐴 ⊸⟶ 𝐵

is an assignment to each element a in a subset of A on a unique
element b in B.
- The subset of A is called the domain of definition of f
- f is undefined for elements in A that are not in the domain of
definition of f.
- When the domain of definition of f equals A, we say that f is a
total function.

Example: f: N → R where f(n) = √n is a partial function from Z to Set and

Function
R where the domain of definition is the set of nonnegative integers.
Discrete Math.
Note that f is undefined for negative integers.
2021-10-03