EF Properties of functions

Section 10.2 Properties of functions

surjective function: 🔗
a function whose image is all of its codomain — that is, every element of the codomain is an output for the function;
surjection: 🔗
a surjective function
onto: 🔗
synonym for surjective
$f : A ↠ B$: 🔗
function $f$ is surjective

A function

f : A \to B

is surjective if

f (A) = B .

Since we have

f (A) \subseteq B

by definition of image, to show that a function is surjective we only need to show

f (A) \supseteq B .

🔗

Test 10.2.1. Surjective function.

🔗

🔗
Function $f : A \to B$ is surjective if $B \subseteq f (A) .$ That is, $f$ is surjective if for every element $b \in B,$ there exists at least one element $a \in A$ such that $f (a) = b .$
🔗
Function $f : A \to B$ is not surjective if there exists at least one element $b \in B$ for which there is no element $a \in A$ satisfying $f (a) = b .$ (Equivalently, there exists $b \in B$ for which every $a \in A$ satisifes $f (a) \neq b .$ )

🔗

Worked Example 10.2.2.

🔗

Show that, of the following functions,

f

is surjective and

g

is not.

\begin{aligned} f : Z & \to N & g : Z & \to Q \\ m & \mapsto | m | & m & \mapsto m / 2 \end{aligned}

Solution.

Show that $f$ is surjective.

Consider an arbitrary element

n

of the codomain

N .

Since

N \subseteq Z,

n

is also an element of the domain. In particular,

f (n) = n,

since

n \geq 0 .

Therefore, as an element of the codomain, we have

n \in f (Z) .

Show that $g$ is not surjective.

We need to find a specific example of a rational number that is not an output for

g .

For this, we could use

1 / 3,

since there is no integer such that

m / 2 = 1 / 3 .

🔗

injective function: 🔗
a function for which two different inputs never produce the same output
injection: 🔗
an injective function
embedding: 🔗
synonym for injection
one-to-one: 🔗
synonym for injective
$f : A ↪ B$: 🔗
function $f$ is injective

🔗

Test 10.2.3. Injective function.

🔗

🔗
Function $f : A \to B$ is injective if the following conditional always holds for elements $a_{1}, a_{2} \in A :$

🔗
if $a_{1} \neq a_{2}$ then $f (a_{1}) \neq f (a_{2}) .$

🔗
Alternatively, one can establish that the contrapositive of the above conditional always holds for elements $a_{1}, a_{2} \in A :$

🔗
if $f (a_{1}) = f (a_{2})$ then $a_{1} = a_{2} .$
🔗
Function $f : A \to B$ is not injective if there exists at least one pair of elements $a_{1}, a_{2} \in A$ with $a_{1} \neq a_{2}$ but $f (a_{1}) = f (a_{2}) .$

🔗

Example 10.2.4. Demonstrating that a function is not injective.

🔗

The function

f : R \to R,

f (x) = x^{2},

is not injective, since

f

has repeated outputs. For example,

f (- 1) = f (1) .

And in fact,

f (- x) = f (x)

for every

x \in R .

🔗

Worked Example 10.2.5. Demonstrating that a function is injective.

🔗

Verify that the function

f : N \to N,

f (n) = 2 n + 1,

is injective.

Solution.

Using the contrapositive version of the Injective Function Test, suppose domain elements

n_{1}, n_{2} \in N

satisfy

f (n_{1}) = f (n_{2}) .

Then using the formula defining the input-output rule for

f,

we have

2 n_{1} + 1 = 2 n_{2} + 1,

which reduces to

n_{1} = n_{2} .

🔗

An injection

f : A ↪ B

gives us a way of thinking of

A

as a subset of

B,

by considering

f (A) \subseteq B .

🔗

Example 10.2.6. Turning letters into numbers.

🔗

Let

Σ = {a, b, \dots, z},

and define

φ : Σ \to N

by the following table.

$σ$	$a$	$b$	$c$	$\dots$	$z$
$φ (σ)$	$1$	$2$	$3$	$\dots$	$26$

🔗

Then

f

embeds

Σ

into

N

in a familiar way, and lets us think of letters as numbers.

🔗

bijective function: 🔗
a function that is both injective and surjective
bijection: 🔗
an bijective function
one-to-one correspondence: 🔗
synonym for bijection

🔗

Example 10.2.7.

🔗

Function

f : R \to R,

f (x) = x^{3}

is bijective.

🔗

A bijection

f : A \to B

allows us to think of

A

and

B

as essentially the same sets.

🔗

Example 10.2.8. Identifying letters with numbers.

🔗

Consider again

f : Σ \to N

from Example 10.2.6. If we write

B = f (Σ) = {1, 2, 3, \dots, 26},

then really we could think of the function as being defined

f : Σ \to B .

This version of

f

is bijective, and allows us to identify each letter with a corresponding number:

\begin{aligned} a & \leftrightarrow 1, & b & \leftrightarrow 2, & c & \leftrightarrow 3, & \dots, & z & \leftrightarrow 26. \end{aligned}

🔗

In this way, we can think of

Σ

and

B

as essentially the same set.

🔗

Worked Example 10.2.9. Recognizing bijections.

🔗

Which of the following functions are bijections?

\begin{aligned} f : Z & \to Z, & g : Z & \to N, & h : Z & \to Z, \\ m & \mapsto 2 m, & m & \mapsto | m |, & m & \mapsto - m . \end{aligned}

Solution.

Is $f$ bijective?.

No,

f

is not bijective because it is not surjective. For example, there is no

m \in Z

such that

f (m) = 1 .

Is $g$ bijective?.

No,

g

is not bijective because it is not injective. For example,

g (- 1) = g (1) .

Is $h$ bijective?.

Yes,

h

is bijective. It is injective because if

m_{1} \neq m_{2}

then

- m_{1} \neq - m_{2} .

And it is surjective because for

n \in Z,

we can realize

n

as an output

n = h (m)

by setting

m = - n .

🔗

Checkpoint 10.2.10. Bijections of counting sets.

🔗

For

m \in N

write

N_{< m} = {n \in N | n < m} = {0, 1, \dots, m - 1} .

🔗

Prove that there exists a bijection

N_{< ℓ} \to N_{< m}

if and only if

ℓ = m .

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 10.2 Properties of functions

Test 10.2.1. Surjective function.

Worked Example 10.2.2.

Show that $f$ is surjective.

Show that $g$ is not surjective.

Test 10.2.3. Injective function.

Example 10.2.4. Demonstrating that a function is not injective.

Worked Example 10.2.5. Demonstrating that a function is injective.

Example 10.2.6. Turning letters into numbers.

Example 10.2.7.

Example 10.2.8. Identifying letters with numbers.

Worked Example 10.2.9. Recognizing bijections.

Is $f$ bijective?.

Is $g$ bijective?.

Is $h$ bijective?.

Checkpoint 10.2.10. Bijections of counting sets.

Section 10.2 Properties of functions

Test 10.2.1. Surjective function.

Worked Example 10.2.2.

Show that f is surjective.

Show that g is not surjective.

Test 10.2.3. Injective function.

Example 10.2.4. Demonstrating that a function is not injective.

Worked Example 10.2.5. Demonstrating that a function is injective.

Example 10.2.6. Turning letters into numbers.

Example 10.2.7.

Example 10.2.8. Identifying letters with numbers.

Worked Example 10.2.9. Recognizing bijections.

Is f bijective?.

Is g bijective?.

Is h bijective?.

Checkpoint 10.2.10. Bijections of counting sets.

Show that $f$ is surjective.

Show that $g$ is not surjective.

Is $f$ bijective?.

Is $g$ bijective?.

Is $h$ bijective?.