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.