2Sets, functions and relations
IA Numbers and Sets
2.2 Functions
Definition
(Function/map)
.
A function (or map)
f
:
A → B
is a “rule” that
assigns, for each
a ∈ A
, precisely one element
f
(
a
)
∈ B
. We can write
a 7→ f
(
a
).
A and B are called the domain and co-domain respectively.
If we wish to be very formal, we can define a function to be a subset
f ⊆ A×B
such that for any
a ∈ A
, there exists a unique
b ∈ B
such that (
a, b
)
∈ f
. We
then think of (
a, b
)
∈ f
as saying
f
(
a
) =
b
. However, while this might act as a
formal definition of a function, it is a terrible way to think about functions.
Example. x
2
:
R → R
is a function that sends
x
to
x
2
.
1
x
:
R → R
is not a
function since
f
(0) is not defined.
±x
:
R → R
is also not a function since it is
multi-valued.
It is often helpful to categorize functions into different categories.
Definition
(Injective function)
.
A function
f
:
X → Y
is injective if it hits
everything at most once, i.e.
(∀x, y ∈ X) f(x) = f(y) ⇒ x = y.
Definition
(Surjective function)
.
A function
f
:
X → Y
is surjective if it hits
everything at least once, i.e.
(∀y ∈ Y )(∃x ∈ X) f(x) = y
Example. f : R → R
+
∪ {0} with x 7→ x
2
is surjective but not injective.
Definition
(Bijective function)
.
A function is bijective if it is both injective
and surjective. i.e. it hits everything exactly once.
Definition (Permutation). A permutation of A is a bijection A → A.
Definition
(Composition of functions)
.
The composition of two functions is a
function you get by applying one after another. In particular, if
f
:
X → Y
and
G
:
Y → Z
, then
g ◦ f
:
X → Z
is defined by
g ◦ f
(
x
) =
g
(
f
(
x
)). Note that
function composition is associative.
Definition
(Image of function)
.
If
f
:
A → B
and
U ⊆ A
, then
f
(
U
) =
{f
(
u
) :
u ∈ U}. f(A) is the image of A.
By definition, f is surjective iff f(A) = B.
Definition
(Pre-image of function)
.
If
f
:
A → B
and
V ⊆ B
, then
f
−1
(
V
) =
{a ∈ A : f(a) ∈ V }.
This is the pre-image of the function
f
, and acts on subsets of
B
. This is
defined for any function
f
. It is important to note that we use the same symbol
f
−1
to denote the inverse function, which we will define later, but they are very
distinct entities. For example, we will see that the inverse function exists only
for bijective functions.
To define the inverse function, we will first need some preliminary definitions.
Definition
(Identity map)
.
The identity map
id
A
:
A → A
is defined as the
map a 7→ a.
Definition
(Left inverse of function)
.
Given
f
:
A → B
, a left inverse of
f
is a
function g : B → A such that g ◦f = id
A
.
Definition
(Right inverse of function)
.
Given
f
:
A → B
, a right inverse of
f
is a function g : B → A such that f ◦ g = id
B
.
Theorem. The left inverse of f exists iff f is injective.
Proof.
(
⇒
) If the left inverse
g
exists, then
∀a, a
0
∈ A, f
(
a
) =
f
(
a
0
)
⇒ g
(
f
(
a
)) =
g(f(a
0
)) ⇒ a = a
0
. Therefore f is injective.
(⇐) If f is injective, we can construct a g defined as
g :
(
g(b) = a if b ∈ f(A), where f(a) = b
g(b) = anything otherwise
.
Then g is a left inverse of f.
Theorem. The right inverse of f exists iff f is surjective.
Proof.
(
⇒
) We have
f
(
g
(
B
)) =
B
since
f ◦ g
is the identity function. Thus
f
must be surjective since its image is B.
(
⇐
) If
f
is surjective, we can construct a
g
such that for each
b ∈ B
, pick
one a ∈ A with f(a) = b, and put g(b) = a.
(Note that to prove the second part, for each
b
, we need to pick an
a
such
that
f
(
a
) =
b
. If
B
is infinite, doing so involves making infinite arbitrary choices.
Are we allowed to do so?
To make infinite choices, we need to use the Axiom of choice, which explicitly
says that this is allowed. In particular, it says that given a family of sets
A
i
for
i ∈ I, there exists a choice function f : I →
S
A
i
such that f(i) ∈ A
i
for all i.
So can we prove the theorem without the Axiom of Choice? The answer is
no. This is since if we assume surjective functions have inverses, then we can
prove the Axiom of Choice.
Assume any surjective function
f
has a right inverse. Given a family of
non-empty sets
A
i
for
i ∈ I
(wlog assume they are disjoint), define a function
f
:
S
A
i
→ I
that sends each element to the set that contains the element. This
is surjective since each set is non-empty. Then it has a right inverse. Then the
right inverse must send each set to an element in the set, i.e. is a choice function
for A
i
.)
Definition
(Inverse of function)
.
An inverse of
f
is a function that is both a
left inverse and a right inverse. It is written as
f
−1
:
B → A
. It exists iff
f
is
bijective, and is necessarily unique.