Lecture 5

2.3 Functions

2020/9/9 1
 From calculus, you are familiar with the concept
of a real-valued function f,
which assigns to each number x∈R a particular
value y=f (x), where y∈R.
But, the notion of a function can also be naturally
generalized to the concept of assigning elements
of any set to elements of any set. (Also known as
a map.)

2020/9/9 2
Function: Formal Definition
For any sets A, B, we say that a function f from (or
“mapping”) A to B (f :A→B) is a particular
assignment of exactly one element f (x)∈B to each
element x∈A.

2020/9/9 3
Graphical Representations
Functions can be represented graphically in
several ways:

f A B
• •
f • •
a• • • y
b •
•
•
• x
A
B Bipartite Graph Plot
Like Venn diagrams

2020/9/9 4
Some Function Terminology
If it is written that f :A→B, and f (a)=b (where a∈A &
b∈B), then we say:
 A is the domain of f.
 B is the codomain of f. We also say
the signature
 b is the image of a under f. of f is A→B.
 a is a pre-image of b under f.
 In general, b may have more than 1 pre-image.
 The range R ⊆ B of f is R={b | there exists a such that f (a)=b}.

2020/9/9 5
Range versus Codomain
The range of a function might not be its whole
codomain.
The codomain is the set that the function is
declared to map all domain values into.
The range is the particular set of values in the
codomain that the function actually maps elements
of the domain to.

2020/9/9 6
Range vs. Codomain -
Example
Suppose I declare to you that: “f is a function
mapping students in this class to the set of grades
{A,B,C,D,E}.”
At this point, you know f’s codomain is:
{A,B,C,D,E}
__________, and its range is unknown!
________.
Suppose the grades turn out all As and Bs.
{A,B} but its
Then the range of f is _________,
still {A,B,C,D,E}!
codomain is __________________.

2020/9/9 7
Class Exercise 1
Find the domain and range of these function
a. The function that assigns to each pair of positive integers the
first integer of the pair
b. The function that assigns to each positive integer its largest
decimal digit
c. The function that assigns to a bit string the difference between
the number of ones and the number of zeros in the string
d. The function that assigns to each positive integer the largest
integer not exceeding the square root of the integer
e. The function that assigns to a bit string the longest substring of
ones in the string

2020/9/9 8
Function Operator Example
+, × (“plus”,“times”) are binary operators over R.
(Normal addition & multiplication.)
Therefore, we can also add and multiply functions
f, g:R→R:
 (f + g):R→R, where (f + g)(x) = f (x) + g(x)
 (f × g):R→R, where (f × g)(x) = f (x) × g(x)

2020/9/9 9
Function Composition Operator

For functions g :A→B and f :B→C, there is a

special operator called compose (“◦”).
 It composes (creates) a new function out of f and g by
applying f to the result of applying g.
 We say (f ◦g):A→C, where (f ◦g)(a) :≡ f (g(a)).
 Note g (a)∈B, so f (g (a)) is defined and ∈C.
 Note that ◦ (like Cartesian ×, but unlike +,∧,∪) is non-
commuting. (Generally, f ◦ g ≠ g ◦ f.)

2020/9/9 10
Images of Sets under Functions

Given f :A→B, and S ⊆ A,

The image of S under f is simply the set of all
images (under f ) of the elements of S.
f (S) = {f (s) | s∈S}
= {b | there exists s∈S: f (s)=b}.
Note the range of f can be defined as simply the
image (under f ) of f ’s domain!

2020/9/9 11
One-to-One Functions
A function is one-to-one (1-1), or injective, or an
injection, iff every element of its range has only 1 pre-
image.
 Formally: given f:A→B,
“x is injective” means if x ≠ y, then f(x) ≠ f(y) (i.e., not many to 1)
or, contrapositively, if f(x) = f(y), then x = y.
Only one element of the domain is mapped to any given
one element of the range.
 Domain & range have same cardinality. What about codomain?

2020/9/9 12
One-to-One Illustration
Bipartite (2-part) graph representations of
functions that are (or not) one-to-one:

• • • •
• • •
• • •
• • •
• • • •
• • •
• • • •
• • •
Not one-to-one Not even a
One-to-one function!

2020/9/9 13
Sufficient Conditions for 1-1ness

For functions f over numbers, we say:

 f is strictly (or monotonically) increasing
iff x>y → f (x)>f (y) for all x,y in domain;
 f is strictly (or monotonically) decreasing
iff x>y → f (x)<f (y) for all x,y in domain;
If f is either strictly increasing or strictly
decreasing, then f is one-to-one. E.g. x3
 Converse is not necessarily true

2020/9/9 14
Onto (Surjective) Functions
A function f :A→B is onto or surjective or a
surjection iff its range is equal to its codomain
(For any b∈B, there exists a∈A: f (a)=b).
Think: An onto function maps the set A onto (over,
covering) the entirety of the set B, not just over a
piece of it.
E.g., for domain & codomain R, x3 is onto,
whereas x2 isn’t. (Why not?)

2020/9/9 15
Illustration of Onto
Some functions that are, or are not, onto their
codomains:

•
• • • • • • • •
• • • • • •
• •
• • • •
• • • •
• • • •
• • • •
• •
Onto Not Onto Both 1-1 1-1 but
(but not 1-1) (or 1-1) and onto not onto

2020/9/9 16
Class Exercise 2
Determine whether each of these functions from Z
to Z is one-to-one and which are onto?

a) f(n) = n – 1
b) f(n) = n2 + 1
c) f(n) = n3

2020/9/9 17
Think
You are given two finite sets, how can you
determine whether they have the same number of
elements?
E.g. {3, 5, 90, 23, 499, 234} and { 5, 2, g, a, d, 8}

By counting!

What about the two sets are infinite?

2020/9/9 18
Think 1
Which of the following two sets has more elements?

{0, 1, 2, 3, 4, 5, 6, …}

{0, 2, 4, 6, 8, 10, 12, …}

(Hint: Show that the function f(n) = 2n is a bijection.)

2020/9/9 19
Bijections
A function f is said to be a one-to-one
correspondence, or a bijection, or reversible, or
invertible, iff it is both one-to-one and onto.
For bijections f:A→B, there exists an inverse of f,
written f −1:B→A, which is the unique function
such that
−1
f  f = IA
(where IA is the identity function on A)

2020/9/9 20
The Identity Function
For any domain A, the identity function I:A→A
(variously written, IA, 1, 1A) is the unique function
such that for all a∈A: I(a)=a.
Some identity functions you’ve seen:
 +ing 0, ·ing by 1, ∧ing with T, ∨ing with F, ∪ing with
∅, ∩ing with U.
Note that the identity function is always both one-
to-one and onto (bijective).

2020/9/9 21
Graphs of Functions
We can represent a function f :A→B as a set of
ordered pairs {(a,f (a)) | a∈A}.
Note that for all a, there is only 1 pair (a, b).
For functions over numbers, we can represent an
ordered pair (x, y) as a point on a plane.
 A function is then drawn as a curve (set of points), with
only one y for each x.

2020/9/9 22
A Couple of Key Functions
In discrete math, we will frequently use the
following two functions over real numbers:
 The floor function ·:R→Z, where x (“floor of x”)
means the largest (most positive) integer ≤ x. I.e.,
x :≡ max({i∈Z|i ≤x}).
 The ceiling function · :R→Z, where x (“ceiling of
x”) means the smallest (most negative) integer ≥ x.
x :≡ min({i∈Z|i ≥x})

2020/9/9 23
Visualizing Floor & Ceiling
Real numbers “fall to their floor” or “rise to their
ceiling.”
3
Note that if x∉Z, 2 1.6 . . 1.6=2

−x ≠ − x & .

1
−x ≠ − x 1.6=1

0
Note that if x∈Z, −1 −1.4. .
−1.4= −1

x = x = x. .
−2 −1.4= −2

−3 .. .
−3
−3=−3= −3

2020/9/9 24
Plots with floor/ceiling
Note that for f (x)=x, the graph of f includes the point (a,
0) for all values of a such that a≥0 and a<1, but not for the
value a=1.
We say that the set of points (a,0) that is in f does not
include its limit or boundary point (a,1).
 Sets that do not include all of their limit points are generally called
open sets.
In a plot, we draw a limit point of a curve using an open
dot (circle) if the limit point is not on the curve, and with a
closed (solid) dot if it is on the curve.

2020/9/9 25
Plots with floor/ceiling:
Example
Plot of graph of function f (x) = x/3:
f(x)

Set of points (x, f(x)) +2

−3 +3 x

−2

Class Exercise

2020/9/9 26
Class Exercise 3

Determine whether the function f(n): from Z to Z

is one-to-one and whether it is onto.

2020/9/9 27