Lecture 3

Functions
Chapter 2.3
Kenneth Rosen Book
 Functions
• Def: Let A and B be sets. A function f (or more
completely, f : A → B) is a rule that assigns to
each element a єA exactly one element f(a) є B,
called the value of f at a.

• We also say that f : A → B is a mapping from

domain A to codomain B.

• f(a) is called the image of the element a, and the

element a is called a preimage of f(a).
 Graphical Representations
• Functions can be represented graphically
in several ways:

f A B
• •
f • •
• • • y
a b •
•
•
• x
A
B Bipartite Graph Plot
Like Venn diagrams
 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.
– b is the image of a under f.
– 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 | a f(a)=b }.
 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.
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 __________________.
 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)
 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.
• 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!
 Onto (Surjective) Functions
• A function f:AB is onto or surjective or
a surjection iff its range is equal to its
codomain (bB, 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.
 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
Some more examples
 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
1
unique function such that f  f  IA
– (where IA is the identity function on A)
Composition of f and g
 Graphs of Functions
• We can represent a function f:AB as a
set of ordered pairs {(a,f(a)) | aA}.
• Note that 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.
 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})
 Visualizing Floor & Ceiling
• Real numbers “fall to their floor” or “rise to
their ceiling.”
• Note that if xZ, 3
. 1.6=2
2 .
x   x & 1.6
.
1
x   x 1.6=1

0
• Note that if xZ, 1 .
. 1.4= 1

1.4
x = x = x. 2 .
1.4= 2

3 3 .. .
3=3= 3
 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.
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
Plots with floor/ceiling
 Review of §2.3 (Functions)
• Function variables f, g, h, …
• Notations: f:AB, f(a), f(A).
• Terms: image, preimage, domain, codomain,
range, one-to-one, onto, strictly (in/de)creasing,
bijective, inverse, composition.
• Function unary operator f 1,
binary operators , , etc., and ○.
• The RZ functions x and x.