Module #4 - Functions

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.
 Some further generalizations of this idea:

– A partial (non-total) function f assigns

zero or one elements of B to each
element xA.
– Functions of n arguments; relations (ch.
6).
113/10/17 1
Module #4 - Functions

Graphical Representations
 Functions can be represented
graphically in several ways:

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

113/10/17 2
Module #4 - Functions

Functions We’ve Seen So Far

A proposition can be viewed as a
function from “situations” to truth
values {T,F}
– A logic system called situation theory.
– p=“It is raining.”; s=our situation here,now
– p(s){T,F}.
A propositional operator can be viewed
as a function from ordered pairs of truth
values to truth values: ((F,T)) = T.

113/10/17
Another example: →((T,F)) = F. 3
Module #4 - Functions

More functions so far…

 A predicate can be viewed as a function
from objects to propositions (or truth
values): P :≡ “is 7 feet tall”;
P(Mike) = “Mike is 7 feet tall.” = False.
 A bit string B of length n can be viewed as

a function from the numbers {1,…,n}

(bit positions) to the bits {0,1}.
E.g., B=101  B(3)=1.

113/10/17 4
Module #4 - Functions

Still More Functions

 A set S over universe U can be viewed
as a function from the elements of U to
{T, F}, saying for each element of U
whether it is in S. S={3}; S(0)=F,
S(3)=T.
 A set operator such as ,, can be

viewed as a function from pairs of sets

to sets.
– Example: (({1,3},{3,4})) = {3}

113/10/17 5
Module #4 - Functions

A Neat Trick
 Sometimes we write YX to denote the
set F of all possible functions f:XY.
 This notation is especially appropriate,

because for finite X, Y, |F| = |Y||X|.

 If we use representations F0, T1,

2:{0,1}={F,T}, then a subset TS is

just a function from S to 2, so the power
set of S (set of all such fns.) is 2S in this
notation.

113/10/17 6
Module #4 - Functions

Some Function Terminology

 Iff:AB, and f(a)=b (where aA &
bB), then:
– 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 {b | a f(a)=b }.

113/10/17 7
Module #4 - Functions

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.
113/10/17 8
Module #4 - Functions

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}
__________, unknown!
and its range is ________.
 Suppose the grades turn out all As and

Bs.
{A,B} but its
 Then the range of f is _________,

codomain is __________________.
still {A,B,C,D,E}!

113/10/17 9
Module #4 - Functions

Operators (general definition)

 An n-ary operator over the set S is any
function from the set of ordered n-
tuples of elements of S, to S itself.
 E.g., if S={T,F},  can be seen as a

unary operator, and , are binary

operators on S.
 Another example:  and  are binary

operators on the set of all sets.

113/10/17 10
Module #4 - Functions
Constructing Function
Operators
 If  (“dot”) is any operator over B,
then we can extend  to also denote
an operator over functions f:AB.
 E.g.: Given any binary operator

:BBB, and functions f,g:AB, we

define
(f  g):AB to be the function defined
by:
aA, (f  g)(a) = f(a)g(a).
113/10/17 11
Module #4 - Functions

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)

113/10/17 12
Module #4 - Functions

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,g by applying f to the result of g.
– (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.)
113/10/17 13
Module #4 - Functions

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 |  sS: f(s)=b}.
 Note the range of f can be defined as

simply the image (under f) of f’s

domain!
113/10/17 14
Module #4 - Functions

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” : (x,y: xy  f(x)f(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?
 Each element of the domain is injected into a
different element of the range.
– Compare “each dose of vaccine is injected into a different
patient.”

113/10/17 15
Module #4 - Functions

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!

113/10/17 16
Module #4 - Functions

Sufficient Conditions for 1-1ness

 For functions f over numbers,
– 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. E.g. 1/x

113/10/17 17
Module #4 - Functions

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).
 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?)

113/10/17 18
Module #4 - Functions

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

113/10/17 19
Module #4 - Functions

Bijections
A function f is 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
f  1  f I
(the identity function)
113/10/17 20
Module #4 - Functions

The Identity Function

 For any domain A, the identity
function I:AA (variously written, IA, 1,
1A) is the unique function such that
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 both
one-to-one and onto (bijective).
113/10/17 21
Module #4 - Functions

Identity Function Illustrations

 The identity function:

•
• • y
• •
• •
• •

Domain and range x

113/10/17 22
Module #4 - Functions

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,f(a)).

– Later (ch.6): relations loosen this

restriction.
 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.

113/10/17 23
Module #4 - Functions
Comment About
Representations
 You can represent any type of discrete
structure (propositions, bit-strings,
numbers, sets, ordered pairs, functions)
in terms of virtually any of the other
structures (or some combination
thereof).
 Probably none of these structures is
truly more fundamental than the others
(whatever that would mean). However,
strings, logic, and sets are often used as
the foundation for all else.
113/10/17 24
Module #4 - Functions

A Couple of Key Functions

 In discrete math, we will frequently
use the following functions over real
numbers:
 x (“floor of x”) is the largest (most
positive) integer  x.
 x (“ceiling of x”) is the smallest (most
negative) integer  x.

113/10/17 25
Module #4 - Functions

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.4= 1
1 .
1.4
x  = x  = x . 2 .
1.4= 2

3 3 .. .
3=3= 3

113/10/17 26
Module #4 - Functions

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 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 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.
113/10/17 27
Module #4 - Functions

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

113/10/17 28
Module #4 - Functions

Infinite Cardinalities (from §3.2)

 Using what we learned about
functions in §1.8, it’s possible to
formally define cardinality for infinite
sets.
 We show that infinite sets come in

different sizes of infinite!

 This gives us some interesting proof

examples, in anticipation of chapter

3.
113/10/17 29
Module #4 - Functions

Cardinality: Formal Definition

 For any two (possibly infinite) sets A
and B, we say that A and B have the
same cardinality (written |A|=|B|) iff
there exists a bijection (bijective
function) from A to B.
 When A and B are finite, it is easy to

see that such a function exists iff A

and B have the same number of
elements nN.
113/10/17 30
Module #4 - Functions

Countable versus Uncountable

 For any set S, if S is finite or |S|=|N|, we say
S is countable. Else, S is uncountable.
 Intuition behind “countable:” we can enumerate
(generate in series) elements of S in such a way
that any individual element of S will eventually be
counted in the enumeration. Examples: N, Z.
 Uncountable: No series of elements of S (even
an infinite series) can include all of S’s elements.
Examples: R, R2, P(N)

113/10/17 31
Module #4 - Functions

Countable Sets: Examples

 Theorem: The set Z is countable.
– Proof: Consider f:ZN where f(i)=2i for
i0 and f(i) = 2i1 for i<0. Note f is
bijective.
 Theorem: The set of all ordered pairs of
natural numbers (n,m) is countable.
– Consider listing the pairs in order by their sum
s=n+m, then by n. Every pair appears once in
this series; the generating function is bijective.

113/10/17 32
Module #4 - Functions

Uncountable Sets: Example

 Theorem: The open interval
[0,1) : {rR| 0  r < 1} is uncountable.
 Proof by diagonalization: (Cantor, 1891)
– Assume the set is countable (has a bijection from N
to this set.
– Since there is a bijection to N,there is a sequential
series to list {ri} = r1, r2, ... that containing all
elements r[0,1).
– Consider listing the elements of {ri} in
decimal(binary…) representation (any base’s format
is also set with bijection to the [0,1) set).

113/10/17 33
Module #4 - Functions

Uncountability of Reals, cont’d

A postulated enumeration of the reals:
r1 = 0.d1,1 d1,2 d1,3 d1,4 d1,5 d1,6 d1,7 d1,8…
r2 = 0.d2,1 d2,2 d2,3 d2,4 d2,5 d2,6 d2,7 d2,8…
r3 = 0.d3,1 d3,2 d3,3 d3,4 d3,5 d3,6 d3,7 d3,8…
r4 = 0.d4,1 d4,2 d4,3 d4,4 d4,5 d4,6 d4,7 d4,8…
. Now, consider a real number generated by taking
all digits di,i that lie along the diagonal in this figure
. and replacing them with different digits.
.

113/10/17 34
Module #4 - Functions

Uncountability of Reals, fin.

 E.g., a postulated enumeration of the
reals:
r1 = 0.301948571…
r2 = 0.103918481…
r3 = 0.039194193…
r4 = 0.918237461…
 OK, now let’s add 1 to each of the diagonal
digits (mod 10), that is changing 9’s to 0.
 0.4103… can’t be on the list anywhere!

113/10/17 35
Module #4 - Functions

Transfinite Numbers

 The cardinalities of infinite sets are not

natural numbers, but are special objects
called transfinite cardinal numbers.
 The cardinality of the natural numbers,

0:|N|, is the first transfinite cardinal

number. (There are none smaller.)
 The continuum hypothesis claims that |

R|=1, the second transfinite cardinal.

113/10/17 36
Module #4 - Functions

Do Uncountable Sets Really

Exist?
 The set of objects that can be defined using finite-length
strings of symbols (“descriptions”) is only countable.
 Therefore, any uncountable set must consist primarily of
elements which individually have no finite description.
 Löwenheim-Skolem theorem: No consistent theory can ever
force an interpretation involving uncountables.
 The “constructivist school” asserts that only objects
constructible from finite descriptions exist. (e.g. R)
 Most mathematicians are happy to use uncountable sets
anyway, because postulating their existence has not led to any
demonstrated contradictions (so far).

113/10/17 37
Module #4 - Functions

Countable vs. Uncountable

 You should:
– Know how to define “same cardinality”
in the case of infinite sets.
– Know the definitions of countable and
uncountable.
– Know how to prove (at least in easy
cases) that sets are either countable or
uncountable.

113/10/17 38