Functions
WIX1001 Computing Mathematics 1
What is a function?
●
Let X and Y be sets.
●
A function f from X to Y
is a subset of the
Cartesian product X × Y
having the property that
for each x ∈ X, there is
exactly one y ∈ Y with
(x, y) ∈ f .
●
In less technical way, a
function is a mapping of You even can see
each of the element in functions when you
set X to one element in have your meal!
set Y. 2 / 64
Why we learn functions
●
Functions are widely used in computer
science
●
Many computing operations are described as
function.
●
Concept of function is also adopted by
programming languages
●
The well known deep learning technology in
artificial intelligence is actually a set of
functions!
●
Encryption and decryption of passwords are
also functions. 3 / 64
Functions
●
The typical way to write a function:
Examples:
4 / 64
More examples
5 / 64
What Can Functions Do?
●
A function processes elements of a set and
returns elements in another set
●
Which means a set can be an input and an
output to a function
●
Mapping / Transformation
{(1,4), (5,8), (2,3), (100,-1)} 6 / 64
More examples
●
Given f(x) = -x2 + 4x + 1
f(2) = -(2)2 + 4(2) + 1
=5
7 / 64
More examples
●
Given f(x) = -x2 + 4x + 1
f(2) = -(2)2 + 4(2) + 1
=5
f(t) = -t2 + 4t + 1
8 / 64
More examples
●
Given f(x) = -x2 + 4x + 1
f(2) = -(2)2 + 4(2) + 1
=5
f(t) = -t2 + 4t + 1
f(x–2) = -(x-2)2 + 4(x–2) + 1
= -x2 + 8x + 11
9 / 64
More examples
●
Given f(x) = -x2 + 4x + 1
f(2) = -(2)2 + 4(2) + 1
=5
f(t) = -t2 + 4t + 1
f(x–2) = -(x-2)2 + 4(x–2) + 1
= -x2 + 8x + 11
f(x+h) = -(x+h)2 + 4(x+h) + 1
= -x2 + 4x – 2xh + 4h - h2 + 1 10 / 64
Characteristics of a Function
●
Each element in A must be matched with an
element in B
●
Some elements in B may not be matched with any
element in A
●
Two or more elements in A may be matched with
the same element in B
●
An element in A (domain) cannot be matched with
two different elements in B
11 / 64
Domain, Codomain and Range
● Function f(x) = 2x+1
●
Set A is the domain (input)
●
Set B is the codomain
(output)
●
Elements in B that is
selected as actual output is
the range/image
●
Domain = {1,2,3,4}
●
Codomain = {1,2,3, ...,
8,9,10}
●
Range = {3,5,7,9}
12 / 64
Multiple Functions
● Let f1 and f2 be functions from A to B:
► (f1 + f2)(x) = f1(x) + f2(x)
► (f1 f2)(x) = f1(x) f2(x)
► Both map from A to B
13 / 64
Multiple Functions
● Let f1 and f2 be functions from A to B:
► (f1 + f2)(x) = f1(x) + f2(x)
► (f1 f2)(x) = f1(x) f2(x)
► Both map from A to B
● Example: Let f1 and f2 be functions from R to R such
that f1(x) = x2 and f2(x) = x-x2 . Find f1+f2 and f1 f2.
(f1 + f2)(x) = f1(x) + f2(x) = x2 + x - x2 = x
14 / 64
Multiple Functions
● Let f1 and f2 be functions from A to B:
► (f1 + f2)(x) = f1(x) + f2(x)
► (f1 f2)(x) = f1(x) f2(x)
► Both map from A to B
● Example: Let f1 and f2 be functions from R to R such
that f1(x) = x2 and f2(x) = x-x2 . Find f1+f2 and f1 f2.
(f1 + f2)(x) = f1(x) + f2(x) = x2 + x - x2 = x
(f1 f2)(x) = f1(x) f2(x) = (x2)(x - x2)= x3 - x4
15 / 64
Inverse Functions
And
Composition of Functions
16 / 64
Inverse Functions
●
Let f be a function from set A to set B. The
inverse function of f is noted as f −1 .
17 / 64
Inverse Functions
●
Let f be a function from set A to set B. The
inverse function of f is noted as f −1 .
Say we have f(x) = 2x + 3. In a flow diagram this
can be represented as follow:
18 / 64
Inverse Functions
●
Let f be a function from set A to set B. The
inverse function of f is noted as f −1 .
Say we have f(x) = 2x + 3. In a flow diagram this
can be represented as follow:
The inverse function of f(x) = 2x + 3 would be as
follow:
19 / 64
Finding Inverse Functions
●
We usually solve the inverse function using
algebraic method:
20 / 64
Composition of Functions
●
Function composition is applying one function to the
result of another.
●
The result of f() is sent through g()
●
You can write the composition above as
g( f(x) ) or (g ∘ f)(x)
21 / 64
Examples
22 / 64
Properties of Functions:
Injective, Surjective and Bijective
23 / 64
Injective
●
Injective / One-to-one function
●
A function f from X to Y is said to be one-to-
one if for each y∈Y, there is at most one
x∈X with f(x)=y.
●
Example:
Given X={1,2,3} and Y={a,b,c,d}, and
f : X → Y is defined as
f = {(1,b), (2,c), (3,a)}
The function f is a one-to-one function.
24 / 64
Invertible Functions
●
A one-to-one function is called invertible
function because we can define an inverse of
this function.
●
A function is not invertible if it is not a one-to-
one correspondence, because the inverse of
such a function does not exist.
●
Example:
► f(x) = x2 is not one-to-one, so it is not
invertible.
► f(2) = f(-2) = 4.
► f-1(x) = ± x½ is not a function 25 / 64
Surjective
●
A function f from X to Y is said to be
surjective if the range of f is Y, f is said to be
onto Y.
●
Example:
Given X={1,2,3,4} and Y={a,b,c}, and
f : X → Y is defined as
f = {(1,b), (2,c), (3,a),(4,a)}
The function f is a surjective function.
●
Range = Codomain! 26 / 64
Bijective
●
A function f from X to Y that is both injective
and surjective is called bijective.
●
Example:
Given X={1,2,3} and Y={a,b,c}, and
f: X→Y is defined as
f = {(1,b), (2,c), (3,a)}
●
The function f is a bijective function
●
Injective + surjective → Bijective
27 / 64
Example
28 / 64
Example
29 / 64
How to determine a function is injective
(method 1: show that f(a) = f(b) iff a=b)
●
Example: show that for f:ℝ→ℝ defined as f(x)=5x+9
is an injective function.
30 / 64
How to determine a function is injective
(method 1: show that f(a) = f(b) iff a=b)
●
Example: show that for f:ℝ→ℝ defined as f(x)=5x+9
is an injective function.
Assume a and b are real numbers in the domain.
f(a) = 5a+9 and f(b) = 5b+9
31 / 64
How to determine a function is injective
(method 1: show that f(a) = f(b) iff a=b)
●
Example: show that for f:ℝ→ℝ defined as f(x)=5x+9
is an injective function.
Assume a and b are real numbers in the domain.
f(a) = 5a+9 and f(b) = 5b+9
If f(x) is an injective function,
f(a) = f(b),
5a+9 = 5b+9
a=b
32 / 64
How to determine a function is injective
(method 1: show that f(a) = f(b) iff a=b)
●
Example: show that for f:ℝ→ℝ defined as f(x)=5x+9
is an injective function.
Assume a and b are real numbers in the domain.
f(a) = 5a+9 and f(b) = 5b+9
If f(x) is an injective function,
f(a) = f(b),
5a+9 = 5b+9
a=b
The only chance f(a)=f(b) is that a=b, so f(x) is injective
33 / 64
How to determine a function is injective
(method 1: show that f(a) = f(b) iff a=b)
●
Example 2: show that for f:ℝ→ℝ defined as
f(x)=x2+9 is not an injective function.
34 / 64
How to determine a function is injective
(method 1: show that f(a) = f(b) iff a=b)
●
Example 2: show that for f:ℝ→ℝ defined as
f(x)=x2+9 is not an injective function.
Assume a and b are real numbers in the domain.
f(a) = a2+9 and f(b) = b2+9
35 / 64
How to determine a function is injective
(method 1: show that f(a) = f(b) iff a=b)
●
Example 2: show that for f:ℝ→ℝ defined as
f(x)=x2+9 is not an injective function.
Assume a and b are real numbers in the domain.
f(a) = a2+9 and f(b) = b2+9
If f(x) is an injective function,
f(a) = f(b),
a2+9 = b2+9
a = ±√b2
36 / 64
How to determine a function is injective
(method 1: show that f(a) = f(b) iff a=b)
●
Example 2: show that for f:ℝ→ℝ defined as
f(x)=x2+9 is not an injective function.
Assume a and b are real numbers in the domain.
f(a) = a2+9 and f(b) = b2+9
If f(x) is an injective function,
f(a) = f(b),
a2+9 = b2+9
a = ±√b2
f(a)=f(b) when a=b and also a=-b, so f(x) is not injective
37 / 64
How to determine a function is injective
(method 2: Using graph for a known domain)
For the domain with the property of function is fully known, we
can proof the function is injective in the given domain.
38 / 64
How to determine a function is injective
(method 2: Using graph for a known domain)
For the domain with the property of function is fully known, we
can proof the function is injective in the given domain.
Example: f(x) = 5x+9
39 / 64
How to determine a function is injective
(method 2: Using graph for a known domain)
For the domain with the property of function is fully known, we
can proof the function is injective in the given domain.
Example: f(x) = 5x+9
injective function iff no
horizontal line intersects the
graph at more than one point 40 / 64
How to determine a function is injective
(method 2: Using graph for a known domain)
For the domain with the property of function is fully known, we
can proof the function is injective in the given domain.
Example: f(x) = 5x+9 Example: f(x) = x2+9
injective function iff no
horizontal line intersects the
graph at more than one point 41 / 64
How to determine a function is injective
(method 2: Using graph for a known domain)
For the domain with the property of function is fully known, we
can proof the function is injective in the given domain.
Example: f(x) = 5x+9 Example: f(x) = x2+9
injective function iff no Non injective function if a
horizontal line intersects the horizontal line intersects the
graph at more than one point graph at more than one point 42 / 64
How to determine a function is NOT
injective
(method 3: counterexample)
We can proof a function is NOT injective by providing a
counterexample
43 / 64
How to determine a function is NOT
injective
(method 3: counterexample)
We can proof a function is NOT injective by providing a
counterexample
Example: Proof that f(x) = x2 + 9 is not injective
44 / 64
How to determine a function is NOT
injective
(method 3: counterexample)
We can proof a function is NOT injective by providing a
counterexample
Example: Proof that f(x) = x2 + 9 is not injective
f(3) = 32 + 9 = 18
f(-3) = (-3)2 + 9 = 18
Both x=3 and x=-3 maps to 18, with this counter example, we
proof that f(x) is not injective
45 / 64
How to determine a function is NOT
injective
(method 3: counterexample)
We can proof a function is NOT injective by providing a
counterexample
Example: Proof that f(x) = x2 + 9 is not injective
f(3) = 32 + 9 = 18
f(-3) = (-3)2 + 9 = 18
Both x=3 and x=-3 maps to 18, with this counter example, we
proof that f(x) is not injective
NOTE: never proof a function is
injective by providing examples
46 / 64
How to determine a function is
Surjective
Given function f : A→ B. To proof that it is surjective,
we need to show ∀y∃x y=f(x)
47 / 64
How to determine a function is
Surjective
Given function f : A→ B. To proof that it is surjective,
we need to show ∀y∃x y=f(x)
Example: Given f:R→R, Proof that f(x) = 5x + 9 is
surjective
48 / 64
How to determine a function is
Surjective
Given function f : A→ B. To proof that it is surjective,
we need to show ∀y∃x y=f(x)
Example: Given f:R→R, Proof that f(x) = 5x + 9 is
surjective
Assume f(x) = y = 5x + 9
x = (y-9)/5
49 / 64
How to determine a function is
Surjective
Given function f : A→ B. To proof that it is surjective,
we need to show ∀y∃x y=f(x)
Example: Given f:R→R, Proof that f(x) = 5x + 9 is
surjective
Assume f(x) = y = 5x + 9
x = (y-9)/5
From the expression, x∈R if y∈R, therefore we proof
that f(x) = 5x + 9 is surjective
50 / 64
How to determine a function is
Surjective
Example 2 : Given f:R→R, Proof that f(x) = x2 + 9 is
not surjective
51 / 64
How to determine a function is
Surjective
Example 2 : Given f:R→R, Proof that f(x) = x2 + 9 is
not surjective
Assume f(x) = y = x2 + 9
x = ±√y-9
52 / 64
How to determine a function is
Surjective
Example 2 : Given f:R→R, Proof that f(x) = x2 + 9 is
not surjective
Assume f(x) = y = x2 + 9
x = ±√y-9
From the expression, y∈R doesn’t implies x∈R (e.g.
y=0), therefore we proof that f(x) is not surjective
53 / 64
How to determine a function is
Surjective
Example 3: Given f:N→N, determine whether
f(x) = 5x + 9 is surjective
54 / 64
How to determine a function is
Surjective
Example 3: Given f:N→N, determine whether
f(x) = 5x + 9 is surjective
Using counterexample:
Assume f(x) = 2
2 = 5x + 9
x = -1.4
55 / 64
How to determine a function is
Surjective
Example 3: Given f:N→N, determine whether
f(x) = 5x + 9 is surjective
Using counterexample:
Assume f(x) = 2
2 = 5x + 9
x = -1.4
From the result, if f(x)=2∈N, x=-1.4 but not a natural
number. Therefore we proof that f(x) is not surjective
56 / 64
How to determine a function is
Surjective
Example 3: Given f:N→N, determine whether
f(x) = 5x + 9 is surjective
Using counterexample:
Assume f(x) = 2
2 = 5x + 9
x = -1.4
From the result, if f(x)=2∈N, x=-1.4 but not a natural
number. Therefore we proof that f(x) is not surjective
NOTE: never proof a function is
surjective by providing examples 57 / 64
More examples
●
f: R → R where y = x3
●
f: Z → Z where y = 9 − x2
●
f: R+ → R where f(x) = √ x+5
58 / 64
Common Functions
and
Function Types
59 / 64
Floor function
●
The floor function rounds x
down to the closest integer
less than or equal to x.
●
this function has the same
value throughout the interval
[n, n + 1), namely n.
●
Example: The floor of 3.9
and -3.9 are 3 and -4
respectively.
60 / 64
Ceiling function
●
The ceiling function rounds x
up to the closest integer
greater than or equal to x
●
this function has the same
value throughout the interval
(n, n + 1], namely n + 1.
●
Example: The ceiling of 4.1
and -3.1 are 5 and -3
respectively.
61 / 64
Piecewise Functions
A function that behaves
differently based on input
x is called a piecewise
function.
Example:
62 / 64
Multivariable Functions
●
Some functions have more than one variables.
f: X x Y → Z
where X and Y are domains and Z is codomain
●
Sometimes, we can consider the variables of these
as vectors.
●
Example:
f(x,y) = x-y
f(4,2) = 2
f(3,-5) = 8
63 / 64
Formula
●
Assume that |X| and |Y| represent the number of
element in X and Y respectively.
●
The number of functions in f : X → Y is given by:
|Y||X|
●
The number of bijective functions in f : X → Y is:
|X|!
provided |X| = |Y|
Or 0 otherwise.
64 / 64
