Mathematics for Computer Science 201-N11 • CEGEP, Montreal

Revision sheet: injective, surjective and bijective functions (201-N11)

This chapter is almost never lost on a computation. It is lost on a misread question: the student looks at the rule, answers about the rule, and does not see that the question has changed the domain or the codomain since the previous part. The same rule $x \mapsto x^{2}$ successively takes all four possible natures depending on the two sets it is given, without a single sign changing in the formula.

This sheet therefore starts from the move that pays: circle the domain and the codomain before writing a word. Then comes the decision table of the triple, then the nine most costly false sentences of the chapter, each one refuted by an example with numbers, and the three write-ups the grader expects, one per verb in the question.

Mark this sheet as read or add it to your favourites: a free account, no password, keeps your read sheets and favourites from one visit to the next, tells you which chapter to tackle next and lets you ask for the method or exercise you are missing. Create your space, an email is enough.

The thread of the chapter

Injective, surjective and bijective never describe a formula: they describe the TRIPLE rule, domain, codomain, and changing just one of the two sets changes the answer.

This chapter is part of 201-N11, Mathematics for Computer Science

The essentials

The three natures are counted on the arrows RECEIVED

• A function $f : A \to B$ sends each element of $A$ to ONE image and ONLY ONE: exactly one arrow LEAVES each element on the left. This condition is already met before injectivity comes up; it is not proved again.
• INJECTIVE: each element of $B$ receives AT MOST one arrow. SURJECTIVE: AT LEAST one. BIJECTIVE: EXACTLY one.
• The arrows LEAVING are no longer counted once the function is recognized. The whole chapter is read on the CODOMAIN side.
• Immediate consequence on a finite set: counting is enough, one codomain element at a time. No computation is needed.

Four natures, one single move: top left,

d

receives nothing; top right,

a

receives two; bottom left, each one receives one; bottom right,

a

receives two and

b

none.

On a test, the sentence “each element of the codomain receives at most one arrow, so $f$ is injective” is worth as much as the algebraic proof when the sets are finite and given by a diagram.

The nature belongs to the TRIPLE, never to the rule

• A question that asks whether $x \mapsto x^{2}$ is injective without giving the two sets is not hard, it is incomplete.
• Shrinking the DOMAIN can make a function injective, and never makes it surjective.
• Shrinking the CODOMAIN can make a function surjective, and never changes injectivity.
• Shrinking the codomain down to the exact image $f(A)$ always makes the function surjective: it is the only choice that guarantees the result, and $\mathbb{N}$ is not the exact image of squaring on $\mathbb{Z}$ .

Same rule

n\mapsto n^{2}

\{-2,\ldots,2\}

: into

\{0,\ldots,4\}

2

and

3

receive nothing; into the exact image

\{0, 1, 4\}

, everything is hit.

The reflex that pays: circle the two sets in pencil as soon as you read the question, then never answer again without looking at them.

Inverse, inverse image, fibres: three objects, two notations

• $f^{-1}(Q)$ , applied to a SUBSET $Q$ of the codomain, exists for every function without exception: it is the set of preimages, and it may be empty.
• The inverse FUNCTION $f^{-1} : B \to A$ exists only if $f$ is bijective. It takes an element and returns an element.
• The nonempty fibres $f^{-1}(\{y\})$ form a partition of the domain: they are the classes of the relation having the same image.
• Composition: $(g \circ f)$ injective implies $f$ injective, $(g \circ f)$ surjective implies $g$ surjective. Injectivity travels back to the input, surjectivity travels forward to the output.
• Inverse of a composition: $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ , the order is reversed.

The fibres

f^{-1}(\{a\})=\{1, 2\}

f^{-1}(\{b\})=\{4\}

f^{-1}(\{c\})=\{3, 5\}

split the domain;

f^{-1}(\{d\})

exists too, and equals

\varnothing

The three cardinality inequalities, and what becomes of them for infinite sets

• An injection $A \to B$ forces $\lvert A \rvert \le \lvert B \rvert$ . A surjection forces $\lvert A \rvert \ge \lvert B \rvert$ . A bijection forces equality.
• Between FINITE sets of the same cardinality, injective is equivalent to surjective. This is false as soon as the sets are infinite.
• Useful counts: $\lvert B \rvert^{\lvert A \rvert}$ functions, $\frac{\lvert B \rvert!}{(\lvert B \rvert - \lvert A \rvert)!}$ injections, and $\lvert A \rvert!$ bijections when the two cardinalities are equal.
• Two sets are called equinumerous when there is a bijection from one onto the other. It is the only definition of equal cardinality that survives for infinite sets.

An injection places each element of the domain in a distinct slot: the codomain is at least as large. A surjection covers the codomain: the domain is at least as large.

The rules in table form

Each row reads from left to right: the assumptions, then the result. A red cell is not an answer, it is the finding that the form settles nothing and the instruction to rewrite it. Every case is followed by a worked example.

The same rule, five triples, four natures

Read this table from left to right only: the rule column is never enough, the middle column decides. Here $\mathbb{R}^{+}=[0,\infty)$ , zero included. The last row is in red because the question there is incomplete, and an incomplete question has no answer.

Rule	Domain $\to$ codomain	Nature
$x \mapsto x^{2}$	$\mathbb{R} \to \mathbb{R}$	none of the three
Example: $f(-2) = f(2) = 4$ kills injectivity, and $-1$ has no preimage.
$x \mapsto x^{2}$	$\mathbb{R}^{+} \to \mathbb{R}$	injective
Example: $a^{2} = b^{2}$ with $a, b \ge 0$ gives $a = b$ ; but $-1$ stays out of reach.
$x \mapsto x^{2}$	$\mathbb{R} \to \mathbb{R}^{+}$	surjective
Example: $y = 9$ has two preimages, $3$ and $-3$ , so everything is hit but nothing is unique.
$x \mapsto x^{2}$	$\mathbb{R}^{+} \to \mathbb{R}^{+}$	bijective
Example: $y = 9$ has the single preimage $3$ , and the inverse is $y \mapsto \sqrt{y}$ .
$n \mapsto n^{2}$	$\mathbb{Z} \to \mathbb{N}$	none of the three
Example: $(-3)^{2} = 3^{2} = 9$ , and $2$ , $3$ , $5$ , $6$ , $7$ are the squares of no integer.
$x \mapsto x^{2}$	not specified	no answer incomplete question
Example: The $5$ rows above give $4$ different natures for the same rule. What to do: Write down the domain and the codomain, and only then go back to the question. If the question does not give them, choose them and say so.

The table is also read from right to left, and that is how it is used on exams: you want a bijection, so you look for the pair of sets that gives one, and there is only one here.

The mistakes that cost marks

These are the errors I correct most often in session. Each one costs marks on a paper, even when the reasoning behind it is right.

1. Answering about the formula without looking at the domain and the codomain

the whole question, and often the four parts that follow

What not to write

“ $x^{2}$ is not injective, everybody knows that.”

What to write

“From $\mathbb{R}$ to $\mathbb{R}$ , $f$ is not injective because $f(-2) = f(2) = 4$ . From $\mathbb{R}^{+}$ to $\mathbb{R}^{+}$ , the same rule is bijective.”

From

\mathbb{R}

\mathbb{R}

, the line

y=4

cuts the parabola twice (red); on

\mathbb{R}^{+}

, only once (green): same rule, another triple, another nature.

Why: This is the error that structures the chapter: the nature is a property of the triple rule, domain, codomain, and exams test it by changing the sets from one part to the next without touching the formula.

2. Believing that shrinking the codomain is always enough to make a function surjective

2 marks, and the question about the inverse that depends on it

What not to write

“ $n \mapsto n^{2}$ goes from $\mathbb{Z}$ to $\mathbb{N}$ , so it is surjective: the square of an integer is indeed a natural number.”

What to write

“It is not surjective: $2$ is the square of no integer. The codomain that makes it surjective is the set of perfect squares, not $\mathbb{N}$ .”

Squaring from

\mathbb{Z}

\mathbb{N}

2

and

3

receive no arrow despite a codomain that seemed tailor-made, and

1

and

4

each receive two.

Why: Shrinking the codomain makes a function surjective only if you shrink it ALL THE WAY DOWN to the exact image $f(A)$ . A codomain that looks tailor-made almost never is: of the $26$ integers from $0$ to $25$ , only $6$ are squares.

3. Confusing surjective with “every element of the domain has an image”

2 marks, and the whole proof heads in the wrong direction

What not to write

“ $f$ is surjective, since each element of $A$ does have an image in $B$ .”

What to write

“Each element of $A$ has an image: that only says $f$ is a function. $f$ is surjective if each element of $B$ has at least one PREIMAGE, which is checked on the codomain side.”

Why: The definition of a function is already settled when the question is asked: proving it again earns nothing. Surjectivity is about the codomain, and the codomain alone.

4. Believing that every function has an inverse

the whole question, since everything after it rests on an object that does not exist

What not to write

“Apply $f^{-1}$ to both sides, so $x = f^{-1}(y)$ .”

What to write

“ $f$ is not injective, so the inverse function $f^{-1}$ does not exist. One can only write $x \in f^{-1}(\{y\})$ , the set of preimages.”

On the left, three keys fall into slot

0

: no arrow can be followed backwards, so there is no inverse. On the right, each file receives exactly one arrow, and the inverse exists.

Why: Only a bijection has an inverse. That is exactly why a hash table must store the key in the slot: the slot number does not lead back to the key.

5. Believing that injective means strictly increasing

2 marks, and the argument is rejected even when the conclusion is right

What not to write

“ $f$ is not monotonic, so it is not injective.”

What to write

“Strictly monotonic implies injective, never the converse. The function $x \mapsto \frac{1}{x}$ on $\mathbb{R}\setminus\{0\}$ is injective without being monotonic, and on a finite set the word increasing does not even make sense.”

x\mapsto\frac{1}{x}

\mathbb{R}\setminus\{0\}

is not monotonic, and yet each horizontal line cuts it at most once: it is injective.

Why: Monotonicity is a tool of differential calculus, injectivity a property of sets. In a discrete mathematics course, the domain is often not even ordered: an alphabet, a set of keys, a set of employees.

6. Proving injectivity in the wrong direction

the whole question: the wrong proof shows that

f

is a function

What not to write

“Let $a = b$ . Then $3a - 7 = 3b - 7$ , so $f(a) = f(b)$ : $f$ is injective.”

What to write

“Let $a$ and $b$ be such that $f(a) = f(b)$ . Then $3a - 7 = 3b - 7$ , so $3a = 3b$ , so $a = b$ . Therefore $f$ is injective.”

Why: The direction $a = b \Rightarrow f(a) = f(b)$ holds for absolutely every function, injective or not. The useful implication is the other one, and the grader first looks at which equality the proof starts from.

7. Believing that a bijection between two infinite sets is impossible

the whole question, and the misconception comes back in the chapter on cardinality

What not to write

“ $2\mathbb{N}$ is strictly contained in $\mathbb{N}$ , so it is smaller, so there is no bijection.”

What to write

“ $\psi : \mathbb{N} \to 2\mathbb{N}$ , $\psi(n) = 2n$ , is bijective: an infinite set can be in bijection with one of its proper subsets.”

\mathbb{N}

enumerates all of

\mathbb{Z}

, one rank per integer: each column carries exactly one arrow, so

\varphi

is bijective even though both sets are infinite.

Why: The argument by strict inclusion is only valid for finite sets. Cantor does not forbid bijections between infinite sets, he only says there is none from $\mathbb{N}$ onto $\mathbb{R}$ .

8. Reversing the direction of the cardinality inequalities

1 mark, and the conclusion of the counting problem is reversed

What not to write

“There is an injection from $A$ to $B$ , so $\lvert A \rvert \ge \lvert B \rvert$ .”

What to write

“An injection from $A$ to $B$ gives $\lvert A \rvert \le \lvert B \rvert$ : each element of $A$ takes a distinct place in $B$ , so $B$ is at least as large.”

Why: The memory aid that works: an injection PLACES $A$ in $B$ without collapsing, so $B$ must be large enough; a surjection COVERS $B$ with $A$ , so $A$ must be large enough. With $\lvert A \rvert = 4$ and $\lvert B \rvert = 3$ , there are $36$ surjections and zero injections.

9. Returning an element where $f^{-1}$ returns a set

0.5 mark each time, and the partition into fibres becomes unreadable

What not to write

“ $f^{-1}(b) = 4$ .”

What to write

“ $f^{-1}(\{b\}) = \{4\}$ : the inverse image of a subset is a SUBSET of the domain, even when it contains a single element, and it equals $\varnothing$ when nothing is sent to $b$ .”

Why: It is the distinction between $3$ and $\{3\}$ seen in the chapter on sets. The notation $f^{-1}(b)$ also assumes that the inverse function exists, which has not been proved and is often false.

Which method to choose

Which write-up for which verb in the question

You do not choose the write-up by topic, you choose it by verb. Proving and disproving are written in completely different ways, and the confusion costs the whole question even when the final answer is right.

If “prove that $f$ is injective” → start from $f(a) = f(b)$ , chain the implications, arrive at $a = b$

Example: $3a - 7 = 3b - 7 \Rightarrow a = b$

no numerical example belongs here: three tested values prove nothing
If “prove that $f$ is surjective” → take an arbitrary $y$ in the CODOMAIN, build $x$ , check $f(x) = y$

Example: $x = \frac{y+7}{3}$ gives $f(x) = y$

the final check is not optional: it is what proves that the $x$ you built works
If “prove that $f$ is NOT injective” → exhibit two distinct elements with the same image, with their values

Example: $g(0) = g(4) = 1$ for $g(x) = x^{2} - 4x + 1$

saying that the function is not monotonic disproves nothing
If “prove that $f$ is NOT surjective” → exhibit ONE element of the codomain and prove that it has no preimage

Example: $3$ is not even, so $2n = 3$ has no integer solution

the word prove matters: you must solve the equation and conclude that it has no solution in the domain
If “prove that $f$ is bijective” → either the two separate proofs, or build $f^{-1}$ and check BOTH compositions

Example: $f^{-1}(f(x)) = x$ and $f(f^{-1}(y)) = y$

the second method is faster as soon as the equation $f(x) = y$ can be solved explicitly
If “determine the nature” with a diagram or finite sets → count the arrows RECEIVED by each element of the codomain

Example: $a$ receives $2$ , $b$ none: neither injective nor surjective

no algebra is expected, and attempting some wastes time

If no branch applies, the question is asking about a property of the composition: then use the two inheritances, injectivity travels back to $f$ , surjectivity travels forward to $g$ .

The function does not work: which set to change

A problem often asks you to MAKE the function injective, surjective or bijective. Look at the defect, and the defect itself points to the set to change.

If two distinct elements have the same image → shrink the DOMAIN. Touching the codomain will change nothing

Example: $\mathbb{R} \to \mathbb{R}^{+}$ stays non-injective for $x \mapsto x^{2}$
If an element of the codomain has no preimage → shrink the CODOMAIN down to the exact image $f(A)$

Example: $n \mapsto 2n$ becomes bijective from $\mathbb{Z}$ onto $2\mathbb{Z}$
If the proposed codomain looks tailor-made → check element by element that it really is $f(A)$ , and not a set that resembles it

Example: $\mathbb{N}$ contains $2$ , $3$ , $5$ , which are not squares
If both defects are present → shrink both sets, in either order

Example: $\mathbb{R}^{+} \to \mathbb{R}^{+}$ makes squaring bijective

On finite sets, this choice is constrained by the cardinalities: no injection if $\lvert A \rvert > \lvert B \rvert$ , no surjection if $\lvert A \rvert < \lvert B \rvert$ . Checking the cardinalities BEFORE looking for a function saves several minutes.

How the answer is expected to be written

A marker ticks steps. Here they are in order, with the concluding sentence expected word for word.

Proving that a function is injective

When to use it: The question says show, prove or demonstrate that $f$ is injective, and the domain is infinite or given by a formula.

1 Write “Let $a$ and $b$ be in $A$ such that $f(a) = f(b)$ .” The word Let is what makes the proof universal.
2 Replace $f(a)$ and $f(b)$ by their expressions, without simplifying anything yet.
3 Transform until you reach $a = b$ , justifying every step that is not valid everywhere: dividing by $3$ is valid because $3 \ne 0$ , cancelling $x - 2$ is valid because $x \ne 2$ by definition of the domain.
4 Conclude with the standard sentence, naming the property.

Concluding sentence

“Two elements of $A$ with the same image are therefore equal: $f$ is injective.”

The trap: Starting from $a = b$ instead of $f(a) = f(b)$ . The proof is then true and completely useless, since it holds for every function.

Marking: Usually 3 marks: 1 for the correct start of the proof, 1 for the chain, 1 for the written conclusion.

Proving that a function is surjective

When to use it: The question asks for surjectivity, or for bijectivity through the two separate proofs.

1 Write “Let $y$ be an arbitrary element of $B$ .” The quantifier is on the CODOMAIN, not on the domain.
2 Solve the equation $f(x) = y$ for the unknown $x$ , treating $y$ as a parameter.
3 Check that the $x$ obtained does belong to the DOMAIN: no division by zero, no square root of a negative number, no value excluded from the domain.
4 Recompute $f(x)$ with the expression found and get back $y$ : this check is what earns the mark.
5 Conclude with the standard sentence.

Concluding sentence

“Every element $y$ of $B$ therefore has at least one preimage in $A$ : $f$ is surjective.”

The trap: Forgetting to check that the $x$ you built is in the domain. On $f : \mathbb{R} \setminus \{2\} \to \mathbb{R} \setminus \{3\}$ , that is exactly the point being graded.

Marking: Usually 3 marks, including 1 for the final check, which is the part most often skipped.

Disproving: the counterexample with numbers

When to use it: The question says show that $f$ is not injective, or asks for the nature of a function that has none of the three.

1 Choose two concrete elements of the domain, or one concrete element of the codomain, depending on the property to destroy.
2 Compute the images, or solve the equation, and write the numbers out in full on your copy.
3 Write the inequality that makes the counterexample valid: $0 \ne 4$ and yet $g(0) = g(4)$ .
4 Conclude by recalling that a single counterexample is enough to negate a universal statement.

Concluding sentence

“ $g(0) = g(4) = 1$ while $0 \ne 4$ : $g$ is not injective.”

The trap: Writing that it does not always work, without producing the values. A disproof without numbers earns no marks.

Marking: Usually 2 marks: 1 for the values, 1 for the sentence that ties them to the definition.

Check before you hand in

Five minutes of checking recover more marks than one more problem started in a hurry.

Reread the domain and the codomain, not the answer

Before handing in, go back over each question about the nature of a function and check that the two sets cited in your answer are really those of the question. An exam often changes one of the two from one part to the next.

If parts b), c) and d) have the same answer, that is a warning sign: they almost certainly have different sets.
The direction of the injectivity proof

Look at the FIRST line of the proof. It must contain $f(a) = f(b)$ . If it contains $a = b$ , the proof must be redone entirely, whatever follows.

A proof that ends with “so $f(a) = f(b)$ ” has shown that $f$ is a function, not that it is injective.
The cardinality test

On finite sets, compare the cardinalities BEFORE concluding. An injection requires $\lvert A \rvert \le \lvert B \rvert$ , a surjection $\lvert A \rvert \ge \lvert B \rvert$ , a bijection equality. An answer that violates one of these three inequalities is wrong without even looking at the arrows.

Answering injective for a function from $6$ keys to $3$ slots is impossible: $6 > 3$ .
Plug the preimage you built back in

Take the $x$ found in the surjectivity proof and recompute $f(x)$ . If you do not get exactly $y$ back, the error is in the solving, not in the conclusion.

With $x = \frac{2y+1}{y-3}$ , the computation gives $\frac{7y}{7} = y$ : the factor $7$ cancelling out is the sign that the solving is right.
A set or an element

Find every occurrence of $f^{-1}$ in your copy and check what is inside the parentheses. A set as input calls for a set as output, with braces.

$f^{-1}(\{a\}) = \{1, 3, 6\}$ reads correctly; $f^{-1}(a) = 1$ assumes an inverse that does not exist here.

The typical problem, taken apart

Prove that $f(x) = \frac{3x+1}{x-2}$ is bijective from $\mathbb{R} \setminus \{2\}$ onto $\mathbb{R} \setminus \{3\}$

Let $f : \mathbb{R} \setminus \{2\} \to \mathbb{R} \setminus \{3\}$ be defined by $f(x) = \frac{3x+1}{x-2}$ .

Prove that $f$ is bijective and give its inverse function. This is the standard exercise of the chapter: it tests at the same time the reading of the two sets, the write-up of injectivity, building a preimage and the existence of the inverse.

The curve avoids the vertical line

x=2

, excluded from the domain, and the horizontal line

y=3

, excluded from the codomain: these two exclusions are what make the statement true.

Step 1

The domain excludes $2$ because $x - 2$ vanishes at $2$ . The codomain excludes $3$ : if $\frac{3x+1}{x-2} = 3$ , then $3x + 1 = 3x - 6$ , that is $1 = -6$ , which is impossible.

Why

This step is not decoration: the two exclusions are exactly what makes the statement true. Without them, $f$ is neither injective nor surjective, and the grader expects you to justify them rather than copy them.

Step 2

Let $a$ and $b$ be in $\mathbb{R} \setminus \{2\}$ such that $f(a) = f(b)$ . Then $\frac{3a+1}{a-2} = \frac{3b+1}{b-2}$ , and since $a - 2 \ne 0$ and $b - 2 \ne 0$ , we can cross-multiply: $(3a+1)(b-2) = (3b+1)(a-2)$ .

Why

Cross-multiplying is valid only because both denominators are nonzero, and it is the domain that guarantees it. Writing this justification earns the rigour mark.

Step 3

Expanding: $3ab - 6a + b - 2 = 3ab - 6b + a - 2$ . The terms $3ab$ and $-2$ cancel, leaving $-6a + b = -6b + a$ , that is $7b = 7a$ , so $a = b$ .

Why

The term $3ab$ disappears on its own, and that is the sign that cross-multiplying was the right move. A copy that expands and does not see the cancellation almost always started from a wrong equality.

Step 4

Let $y \in \mathbb{R} \setminus \{3\}$ . Solve $\frac{3x+1}{x-2} = y$ , that is $3x + 1 = y(x-2)$ , that is $x(y - 3) = 2y + 1$ , so $x = \frac{2y+1}{y-3}$ , valid because $y \ne 3$ .

Why

Isolate $x$ by gathering its terms on one side. The condition $y \ne 3$ is used here and nowhere else: it is what allows the division, and it explains why the statement removes $3$ from the codomain.

Step 5

This $x$ is indeed in the domain: $\frac{2y+1}{y-3} = 2$ would give $2y + 1 = 2y - 6$ , that is $1 = -6$ , impossible. Check: $f\left(\frac{2y+1}{y-3}\right) = \frac{\frac{7y}{y-3}}{\frac{7}{y-3}} = y$ .

Why

Two moves that almost nobody writes and that the marking scheme grades both: the membership of the $x$ you built in the domain, then recomputing $f(x)$ . The factor $7$ that cancels is your internal proof that the computation is right.

Step 6

Numerical check: $f(3) = \frac{10}{1} = 10$ , and $\frac{2 \times 10 + 1}{10 - 3} = \frac{21}{7} = 3$ . Likewise $f(0) = \frac{1}{-2} = -0.5$ , and $\frac{2 \times (-0.5) + 1}{-0.5 - 3} = \frac{0}{-3.5} = 0$ .

Why

Two values are enough to catch a sign error in the inverse. This check proves nothing, it detects, and it costs twenty seconds.

The conclusion, written out

“ $f$ is injective and surjective from $\mathbb{R} \setminus \{2\}$ onto $\mathbb{R} \setminus \{3\}$ , hence bijective, and its inverse function is $f^{-1}(y) = \frac{2y+1}{y-3}$ , defined on $\mathbb{R} \setminus \{3\}$ .”

The classic mistake on this problem: Announcing bijectivity without ever saying why $2$ and $3$ are excluded. The copy then loses the two marks for reading the sets, even though the whole computation is right: the entire chapter is played out on these two exclusions.

Learn by heart

• INJECTIVE: each element of the CODOMAIN receives AT MOST one arrow. SURJECTIVE: AT LEAST one. BIJECTIVE: EXACTLY one.
• An injectivity proof starts from $f(a) = f(b)$ and arrives at $a = b$ . Never the other way around.
• A surjectivity proof takes $y$ in the codomain, BUILDS $x$ , checks $x \in A$ , then checks $f(x) = y$ .
• Shrinking the DOMAIN helps injectivity. Shrinking the CODOMAIN helps surjectivity. Neither one does the other's job.
• Injection: $\lvert A \rvert \le \lvert B \rvert$ . Surjection: $\lvert A \rvert \ge \lvert B \rvert$ . Bijection: $\lvert A \rvert = \lvert B \rvert$ .
• $f^{-1}(Q)$ on a SUBSET always exists; the FUNCTION $f^{-1}$ exists only if $f$ is bijective.
• $(g \circ f)$ injective implies $f$ injective; $(g \circ f)$ surjective implies $g$ surjective; and $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ .
• For FINITE sets of the same cardinality, injective is equivalent to surjective. For INFINITE sets, it is false: $n \mapsto 2n$ from $\mathbb{N}$ onto $2\mathbb{N}$ shows it.

Frequently asked questions

How do you tell whether a function is injective or surjective?

Look first at the domain and the codomain, never at the formula alone. On a diagram, count the arrows received by each element of the codomain: at most one means injective, at least one means surjective, exactly one means bijective. With a formula, start from f of a equals f of b for injectivity, and solve f of x equals y for surjectivity.

Is the squaring function injective?

The question is incomplete as it stands. From the reals to the reals, squaring is neither injective nor surjective. From the nonnegative reals to the reals, it becomes injective. From the reals to the nonnegative reals, it becomes surjective. From the nonnegative reals to the nonnegative reals, it is bijective, and its inverse is the square root. One rule, four natures.

What is the difference between injective and surjective?

Both are about the codomain, but not about the same thing. Injective forbids receiving two arrows: two distinct elements of the domain cannot have the same image. Surjective forbids receiving none: every element of the codomain must have at least one preimage. A function can have one without the other, both, or neither.

Does every function have an inverse?

No. Only a bijective function has an inverse function. A hash function, for example, collapses several keys onto the same slot: you cannot go back from the slot to the key, and that is why a hash table must store the key itself. The inverse image of a subset, on the other hand, can be computed for any function and returns a set, sometimes empty.

How do you prove that a function is bijective?

Two routes. The first does the two separate proofs, injectivity then surjectivity, and concludes. The second builds the inverse directly by solving f of x equals y, then checks both compositions: the inverse of f composed with f gives the identity, and f composed with the inverse does too. The second route is faster as soon as the equation can be solved.

Is a bijection between two infinite sets possible?

Yes, and it is even the definition of equal cardinality for infinite sets. The natural numbers are in bijection with the integers, by listing them as zero, minus one, one, minus two, two, and so on. An infinite set can also be in bijection with one of its proper subsets, which is impossible for finite sets.

Practise it

Corrected exercises: Injective, surjective and bijective functions, 201-N11

A method is proved on a paper, not on a sheet. The set for the same chapter takes each of these traps into a problem, with the solution written out step by step.

10 corrected exercises
100 points
150 minutes

Do the exercises

Something missing from this sheet? A method, a trap, an exercise to practise it, a mistake you spotted: tell me, I read every request.

Sending goes through your free space: that is how I can answer you and tell you when the exercise is added. An email is enough, no password. Create your space. Rather not create an account? Write to me directly.

Previous sheet Set theory and relations Next sheet Induction and recursion

© Ahmed Squalli Houssaini. Revision sheet published at www.letuteurscientifique.ca/en/fiches/cegep-n11-injective-surjective-functions. Free for personal and classroom use; republishing it elsewhere requires written permission (legal notice).

Looking for a 201-N11 tutor in Montreal?

Get in touch for a first session. With a B.Sc. in computer science from McGill and an M.Sc. in applied computer science from Concordia, I connect injections and bijections to what they become later on: hash tables, primary keys in a database and encryption functions.

Book a session WhatsApp

Site by Studio Squalli

Revision sheet: injective, surjective and bijective functions (201-N11)

The essentials

The three natures are counted on the arrows RECEIVED

The nature belongs to the TRIPLE, never to the rule

Inverse, inverse image, fibres: three objects, two notations

The three cardinality inequalities, and what becomes of them for infinite sets

The rules in table form

The same rule, five triples, four natures

The mistakes that cost marks

1. Answering about the formula without looking at the domain and the codomain

2. Believing that shrinking the codomain is always enough to make a function surjective

3. Confusing surjective with “every element of the domain has an image”

4. Believing that every function has an inverse

5. Believing that injective means strictly increasing

6. Proving injectivity in the wrong direction

7. Believing that a bijection between two infinite sets is impossible

8. Reversing the direction of the cardinality inequalities

9. Returning an element where f−1f^{-1}f−1 returns a set

Which method to choose

Which write-up for which verb in the question

The function does not work: which set to change

How the answer is expected to be written

Proving that a function is injective

Proving that a function is surjective

Disproving: the counterexample with numbers

Check before you hand in

The typical problem, taken apart

Prove that f(x)=3x+1x−2f(x) = \frac{3x+1}{x-2}f(x)=x−23x+1​ is bijective from R∖{2}\mathbb{R} \setminus \{2\}R∖{2} onto R∖{3}\mathbb{R} \setminus \{3\}R∖{3}

Learn by heart

Frequently asked questions

How do you tell whether a function is injective or surjective?

Is the squaring function injective?

What is the difference between injective and surjective?

Does every function have an inverse?

How do you prove that a function is bijective?

Is a bijection between two infinite sets possible?

Corrected exercises: Injective, surjective and bijective functions, 201-N11

See also

Looking for a 201-N11 tutor in Montreal?

9. Returning an element where $f^{-1}$ returns a set

Prove that $f(x) = \frac{3x+1}{x-2}$ is bijective from $\mathbb{R} \setminus \{2\}$ onto $\mathbb{R} \setminus \{3\}$