Functions and Inverses

CS 2800: Discrete Structures, Spring 2015

Sid Chaudhuri
 Recap: Relations and Functions
● A relation between sets A (the domain) and B (the
codomain) is a set of ordered pairs (a, b) such that
a ∈ A, b ∈ B (i.e. it is a subset of A × B) Cartesian
product
– The relation maps each a to the corresponding b
● Neither all possible a's, nor all possible b's, need be covered
– Can be one-one, one-many, many-one, many-many

Alice
CS 2800
Bob
A Carol CS 2110 B
David CS 3110
 Recap: Relations and Functions
● A function is a relation that maps each element
of A to a single element of B
– Can be one-one or many-one
– All elements of A must be covered, though not
necessarily all elements of B
– Subset of B covered by the function is its range/image

Alice
Balch
Bob
A Carol Jameson B
David Mews
 Recap: Relations and Functions
● Instead of writing the function f as a set of pairs,
we usually specify its domain and codomain as:
f:A→B
… and the mapping via a rule such as:
f (Heads) = 0.5, f (Tails) = 0.5
or f : x ↦ x2

The function f maps x to x2

 Recap: Relations and Functions
● Instead of writing the function f as a set of pairs,
we usually specify its domain and codomain as:
f:A→B
… and the mapping via a rule such as:
f (Heads) = 0.5, f (Tails) = 0.5
or f : x ↦ x2 f(x)
● Note: the function is f, not f(x)!
– f(x)is the value assigned by f
the function f to input x
x
 Recap: Injectivity
● A function is injective (one-to-one) if every
element in the domain has a unique image in the
codomain
– That is, f(x) = f(y) implies x = y

Albany
NY
New York
A MA Sacramento B
CA Boston
... ...
 Recap: Surjectivity
● A function if surjective (onto) if every element of
the codomain has a preimage in the domain
– That is, for every b ∈ B there is some a ∈ A such that
f(a) = b
– That is, the codomain is equal to the range/image
August
September
October
November Autumn
December Winter
A January
February
March
Spring B
April Summer
May
June
July
 Recap: Surjectivity
● A function if surjective (onto) if every element of
the codomain has a preimage in the domain
– That is, for every b ∈ B there is some a ∈ A such that
f(a) = b
– That is, the codomain is equal to the range/image
August
September (Ithaca etc)
October
November Almost Winter
December Winter
A January
February
March
Still Winter B
April Road Construction
May
June
July
 Recap: Bijectivity
● A function is bijective if it is both surjective and
injective

January 1
February 2
March 3
April 4
May 5
A June
July
6
7 B
August 8
September 9
October 10
November 11
December 12
 Composition of Functions
● The composition of two functions
f:B→C
g:A→B
is the function f ○ g : A → C defined as
f ○ g : x ↦ f ( g (x) )

g
x 1 f
Even
y 2
Odd
z 3
A B C
 Composition of Functions
● The composition of two functions
f:B→C g ○ f is not possible
g:A→B unless A = C !

is the function f ○ g : A → C defined as

f ○ g : x ↦ f ( g (x) )

x f○g
Even
y
Odd
z
A C
 Factoid of the Day #1
Composition is associative
(f ○ g) ○ h = f ○ (g ○ h)

(two functions are equal if for every input, they give the same output)

Prove it!
h
x 1 g Even f True
y 2
False
z 3 Odd
A B C D
 Left Inverse of a Function
● g : B → A is a left inverse of f : A → B if
g ( f (a) ) = a for all a ∈ A
– If you follow the function from the domain to the
codomain, the left inverse tells you how to go back to
where you started

a f(a)

A B
 Left Inverse of a Function
● g : B → A is a left inverse of f : A → B if
g ( f (a) ) = a for all a ∈ A
– If you follow the function from the domain to the
codomain, the left inverse tells you how to go back to
where you started

a f(a)

A ? B
 Left Inverse of a Function
● g : B → A is a left inverse of f : A → B if
g ( f (a) ) = a for all a ∈ A
– If you follow the function from the domain to the
codomain, the left inverse tells you how to go back to
where you started

a f(a)
g
A B
 Right Inverse of a Function
● h : B → A is a right inverse of f : A → B if
f ( h (b) ) = b for all b ∈ B
– If you're trying to get to a destination in the codomain,
the right inverse tells you a possible place to start

A B
 Right Inverse of a Function
● h : B → A is a right inverse of f : A → B if
f ( h (b) ) = b for all b ∈ B
– If you're trying to get to a destination in the codomain,
the right inverse tells you a possible place to start

? b

A B
 Right Inverse of a Function
● h : B → A is a right inverse of f : A → B if
f ( h (b) ) = b for all b ∈ B
– If you're trying to get to a destination in the codomain,
the right inverse tells you a possible place to start

h(b) b
h
A B
 Right Inverse of a Function
● h : B → A is a right inverse of f : A → B if
f ( h (b) ) = b for all b ∈ B
– If you're trying to get to a destination in the codomain,
the right inverse tells you a possible place to start

h(b) b
h
A B
 Note the subtle difference!
● The left inverse tells you how to exactly retrace
your steps, if you managed to get to a destination
– “Some places might be unreachable, but I can always
put you on the return flight”

● The right inverse tells you where you might have

come from, for any possible destination
– “All places are reachable, but I can't put you on the
return flight because I don't know exactly where you
came from”
 Factoid of the Day #2

Left and right inverses need not exist,

and need not be unique

Can you come up with some examples?

 Left inverse ⇔ Injective
● Theorem: A function is injective (one-to-one) iff
it has a left inverse
● Proof (⇐): Assume f : A → B has left inverse g
– If f(x) = f(y) ...
– … then g(f(x)) = g(f(y)) (any fn maps equals to equals)
– … i.e. x = y (since g is a left inverse)
– Hence f is injective
 Left inverse ⇔ Injective
● Theorem: A function is injective (one-to-one) iff
it has a left inverse
● Proof (⇒): Assume f : A → B is injective
– Pick any a0 in A, and define g as
a if f(a) = b
g(b) = a0 otherwise
– This is a well-defined function: since f is injective,
there can be at most a single a such that f(a) = b
– Also, if f(a) = b then g(f(a)) = a, by construction
– Hence g is a left inverse of f
 Right inverse ⇔ Surjective
● Theorem: A function is surjective (onto) iff it has
a right inverse
● Proof (⇐): Assume f : A → B has right inverse h
– For any b ∈ B, we can apply h to it to get h(b)
– Since h is a right inverse, f(h(b)) = b
– Therefore every element of B has a preimage in A
– Hence f is surjective
 Right inverse ⇔ Surjective
● Theorem: A function is surjective (onto) iff it has
a right inverse
● Proof (⇒): Assume f : A → B is surjective
– For every b ∈ B, there is a non-empty set Ab ⊆ A such
that for every a ∈ Ab, f(a) = b (since f is surjective)
– Define h : b ↦ an arbitrary element of Ab
– Again, this is a well-defined function since Ab is
non‑empty (and assuming the “axiom of choice”!)
– Also, f(h(b)) = b for all b ∈ B, by construction
– Hence h is a right inverse of f
 Recap: Left and Right Inverses
● A function is injective (one-to-one) iff it has a left
inverse
● A function is surjective (onto) iff it has a right
inverse
 Factoid for the Day #3
If a function has both a left inverse and a right
inverse, then the two inverses are identical, and this
common inverse is unique
(Prove!)

This is called the two-sided inverse, or usually just the

inverse f –1 of the function f

http://www.cs.cornell.edu/courses/cs2800/2015sp/handouts/jonpak_function_notes.pdf
 Bijection and two-sided inverse
● A function f is bijective iff it has a two-sided
inverse
● Proof (⇒): If it is bijective, it has a left inverse
(since injective) and a right inverse (since
surjective), which must be one and the same by
the previous factoid
● Proof (⇐): If it has a two-sided inverse, it is both
injective (since there is a left inverse) and
surjective (since there is a right inverse). Hence it
is bijective.