Discrete Mathematics
Discrete Mathematics
Discrete Mathematics
2.3 Functions
Let A and B be nonempty sets. A function f from A to B is an assignment of exactly one element
of B to each element of A. If f is a function from A to B, wee write f : A → B.
A function from A to B:
f :A→B
A is the domain
B is the codomain
The range is a specific subset of the Codomain(B) containing the actual values the function out-
puts.
The range can be written as f (A).
Injection (One-to-One)
A function where each element in the Domain maps to a single, unique element in the Codomain.
[Domain and Range have the same cardinality]. Strictly increasing or strictly decreasing functions
are one-to-one.
Surjection (Onto)
A function where every element in the Codomain is a valid output of the function. [Range is equal
to Codomain].
Bijection
Identity Function
Inverse Function
Given the bijective function f , such that f : A → B and f (a) = b where a ∈ A and b ∈ B, the
inverse function is defined as f −1 , such that f −1 : B → A and f −1 (b) = a.
1
ICS 141: Discrete Mathematics I (Fall 2014)
Composition
Given two functions, f and g, such that the range of g is a subset of the domain of f , the composi-
tion of f with g (f ◦ g) is defined as f (g(x)), with x ∈(g’s domain).
Floor Function
Ceiling Function
2.3 pg 153 # 13
a) f (n) = n − 1
This is surjective since every integer is 1 less than some integer.
b) f (n) = n2 + 1
Not surjective because the range cannot include negative integers.
c) f (n) = n3
Not surjective because any element in the codomain that is not a perfect cube will not be
mapped to.
2.3 pg 153 # 23
a) f (x) = 2x + 1
Bijective. This is injective because for every a 6= b, we have f (a) 6= f (b) (every number is
1 more than 2 times some number). We also know that the function is surjective because the
range is all real numbers from 2((y − 1)/2) + 1 = y.
b) f (x) = x2 + 1
Not injective and not surjective. We know the function is not injective because we can have
the same value for f (x) given two different x values. For example, f (2) = 22 + 1 = 5 and
f (−2) = (−2)2 + 1 = 5. The function is also not surjective because the range is all real
numbers greater than or equal to 1, or can be written as [1, ∞).
c) f (x) = x3
Bijective. This is injective because for every a 6= b, we have f (a) 6= f (b) (every number is
the cube of some number). We also know that the function is surjectve because the range is
all real numbers from (y 1/3 )3 = y.
2
ICS 141: Discrete Mathematics I (Fall 2014)
Extra Problem
a) f (x) = x2
g(x) = x + 1
(f (g(x)) = f (x + 1) = (x + 1)2
b) f (x) = 2x + 1
g(x) = x2 + 4x + 4
(f (g(x)) = f (x2 + 4x + 4) = 2(x2 + 4x + 4) + 1 = 2x2 + 8x + 9
c) f (x) = {(1, 3), (2, 4), (5, 6), (4, 8)}
g(x) = {(1, 1), (4, 5), (6, 2)}
(f ◦ g) = {(1, 3), (4, 6), (6, 4)}
2.3 pg 154 # 31
2.3 pg 154 # 43
3
ICS 141: Discrete Mathematics I (Fall 2014)
b) g −1 ({−1, 0, 1})
We know that the numbers from -1 to 2 (exclusive) round down to either -1, 0, or 1, then
g −1 ({−1, 0, 1}) = {x | −1 ≤ x < 2}
2.3 pg 155 # 69
Solve for x.
y = x3 + 1
y − 1 = x3
(y − 1)1/3 = x
Extra Problem
For each function from R to R, if the function has a defined inverse, find it.
a) f (x) = x2 − 2
This function is not bijective, so there is no inverse function.
b) f (x) = 3
This function is not bijective, so there is no inverse function.