Mathematical-Reasoning · Unit 22 · Video 2 · Interactive Practice

Injections: Proving a Function Is One-to-One

IKey Formulas

Statement (for a function $f : A \to B$ )	Role
$\forall x_1, x_2 \in A,\ \big(x_1 \ne x_2 \to f(x_1) \ne f(x_2)\big)$	Definition: $f$ is an injection (one-to-one, injective) — different inputs give different outputs
$\forall x_1, x_2 \in A,\ \big(f(x_1) = f(x_2) \to x_1 = x_2\big)$	Contrapositive, logically equivalent to the definition: the form used in proofs, because its hypothesis is an equation
$\exists x_1, x_2 \in A,\ \big(x_1 \ne x_2 \wedge f(x_1) = f(x_2)\big)$	Negation: $f$ is not an injection — one such pair is enough
$\forall x_1, x_2 \in A,\ \big(x_1 = x_2 \to f(x_1) = f(x_2)\big)$	True for every function (each input has exactly one output), so proving it shows nothing about injections

Key Insight: To disprove, exhibit one pair of different inputs with the same output. To prove, list every output when $A$ is finite; when $A$ is infinite, assume $f(x_1) = f(x_2)$ and derive $x_1 = x_2$ . Elements of $B$ that are never outputs do not affect injectivity.

IIOne Pair Is Enough

Every input of $h(x) = x^2 - 3x$ except $\tfrac{3}{2}$ shares its output with the input $3 - x$ .

x₁ 0

IIIFinite Domains: List Every Output

On a finite domain, one repeated output disproves injectivity, and a list with no repeats proves it.

Rule n 5

IVThe Contrapositive Proof, Step by Step

The same contrapositive algebra either forces the inputs to be equal or exposes the pairs that break injectivity.

Function Step 1

Claim. For all $m, n \in \mathbb{Z}$ , if $F(m) = F(n)$ , then $m = n$ .

(1) Let $m, n \in \mathbb{Z}$ and assume $F(m) = F(n)$ .

VQuiz Questions

Problem 1 · Cubes on $R_7$

Given: $R_7 = \{0, 1, 2, 3, 4, 5, 6\}$ and $f : R_7 \to R_7$ , $f(x) = x^3 \bmod 7$ . Which statement is correct?

✅ Correct! Two different inputs with the same output satisfy the negation of the definition, and one such pair is enough.

❌ Not quite. "Each input has exactly one output" says only that

f

is a function. Injectivity asks whether two different inputs can share an output — and

f(1) = f(2)

❌ Not quite. Every function

A \to B

has its outputs in

B

; that is part of being a function, not injectivity. Compute the outputs:

2^3 = 8

leaves remainder

1

, the same as

1^3

❌ Right verdict, wrong reason. Elements of the codomain that receive no arrow do not affect injectivity — an injection may leave part of the codomain unused. The reason is a repeated output:

f(1) = f(2) = 1

Show solution

The domain is finite, so list every output:

$x$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$x^3$	$0$	$1$	$8$	$27$	$64$	$125$	$216$
$f(x)$	$0$	$1$	$1$	$6$	$1$	$6$	$6$

For example $8 = 7 \cdot 1 + 1$ , so $f(2) = 1 = f(1)$ while $1 \ne 2$ . This pair satisfies $\exists x_1, x_2 \in R_7,\ \big(x_1 \ne x_2 \wedge f(x_1) = f(x_2)\big)$ , so $f$ is not an injection. (Other pairs work too, such as $f(3) = f(5) = 6$ .)

Problem 2 · Opening the Proof

Given: $g : \mathbb{R} - \{3\} \to \mathbb{R}$ , $g(x) = \dfrac{x + 1}{x - 3}$ . Which opening sets up a valid proof that $g$ is an injection?

✅ Correct! That is the contrapositive form: its hypothesis

g(x_1) = g(x_2)

is an equation we can work on with algebra.

❌ Not quite. "If

x_1 = x_2

, then

g(x_1) = g(x_2)

" is the converse of the contrapositive. It holds for every function, because each input has exactly one output, so proving it shows nothing about injections.

❌ Not quite. That is the opening for proving

g

is a surjection (every element of the codomain is an output) — a different property. It would fail here anyway:

\dfrac{x + 1}{x - 3} = 1

gives

x + 1 = x - 3

, which no

x

satisfies. Injectivity is about two inputs sharing an output.

❌ Not quite. The domain is infinite. Checking a few inputs says nothing about the inputs you did not check; a proof must handle all

x_1, x_2

at once.

Show solution

Proof. Let $x_1, x_2 \in \mathbb{R} - \{3\}$ and assume $g(x_1) = g(x_2)$ , that is,

\frac{x_1 + 1}{x_1 - 3} = \frac{x_2 + 1}{x_2 - 3}.

Since $x_1 \ne 3$ and $x_2 \ne 3$ , both denominators are nonzero, so we may multiply both sides by $(x_1 - 3)(x_2 - 3)$ :

(x_1 + 1)(x_2 - 3) = (x_2 + 1)(x_1 - 3)

x_1 x_2 - 3x_1 + x_2 - 3 = x_1 x_2 - 3x_2 + x_1 - 3

Cancel $x_1 x_2$ and $-3$ from both sides:

-3x_1 + x_2 = -3x_2 + x_1, \quad\text{so}\quad 4x_2 = 4x_1.

Dividing by $4$ gives $x_1 = x_2$ . Hence for all $x_1, x_2 \in \mathbb{R} - \{3\}$ , if $g(x_1) = g(x_2)$ , then $x_1 = x_2$ , and $g$ is an injection. ∎

Problem 3 · When the Algebra Splits

Given: $r : \mathbb{R} - \{0\} \to \mathbb{R}$ , $r(x) = x + \dfrac{1}{x}$ . Assume $r(x_1) = r(x_2)$ , multiply both sides by $x_1 x_2$ (nonzero), and move every term to one side.

Which factored equation do you reach?

What does it show about $r$ ?

✅ Correct! The factor

x_1 x_2 - 1

can vanish with

x_1 \ne x_2

, and any reciprocal pair such as

2

and

\tfrac{1}{2}

is a counterexample.

❌ Not quite. That is the factoring of

x_1^2 - x_2^2

, not of this equation. Here the terms are

x_1^2 x_2 - x_1 x_2^2 + x_2 - x_1 = x_1 x_2 (x_1 - x_2) - (x_1 - x_2)

❌ Check the sign.

x_1 x_2 (x_1 - x_2) - (x_1 - x_2)

factors as

(x_1 - x_2)(x_1 x_2 - 1)

: the second term is subtracted.

❌ Not quite. Factoring

x_1 - x_2

out of

x_1 x_2 (x_1 - x_2) - (x_1 - x_2)

leaves a second factor,

x_1 x_2 - 1

, which can also be zero.

❌ Not quite. The product is zero when either factor is zero. The factor

x_1 x_2 - 1

is zero for

x_1 = 2

x_2 = \tfrac{1}{2}

, so the proof cannot force

x_1 = x_2

, and that pair is a counterexample.

❌ Check the values.

r(1) = 1 + 1 = 2

but

r(-1) = -1 - 1 = -2

. The colliding pairs satisfy

x_1 x_2 = 1

, and

1 \cdot (-1) = -1

❌ Check the values.

r(2) = \tfrac{5}{2}

but

r(-2) = -\tfrac{5}{2}

. The colliding pairs satisfy

x_1 x_2 = 1

, and

2 \cdot (-2) = -4

Show solution

Let $x_1, x_2 \in \mathbb{R} - \{0\}$ and assume $r(x_1) = r(x_2)$ :

x_1 + \frac{1}{x_1} = x_2 + \frac{1}{x_2}.

Multiply both sides by $x_1 x_2 \ne 0$ and move every term to the left:

x_1^2 x_2 + x_2 = x_1 x_2^2 + x_1

x_1 x_2 (x_1 - x_2) - (x_1 - x_2) = 0

(x_1 - x_2)(x_1 x_2 - 1) = 0

So $x_1 = x_2$ or $x_1 x_2 = 1$ . The second case allows different inputs: take $x_1 = 2$ , $x_2 = \tfrac{1}{2}$ . Then

r(2) = 2 + \tfrac{1}{2} = \tfrac{5}{2}, \qquad r\big(\tfrac{1}{2}\big) = \tfrac{1}{2} + 2 = \tfrac{5}{2},

with $2 \ne \tfrac{1}{2}$ . This pair satisfies the negation of the definition, so $r$ is not an injection.

Problem 4 · Which One Is One-to-One?

Given: four functions $R_6 \to R_6$ , where $R_6 = \{0, 1, 2, 3, 4, 5\}$ . Which one is an injection?

✅ Correct! The outputs of

f_1

are

1

0

5

4

3

2

— six inputs, six different outputs.

❌ Not quite.

f_2(0) = 1

and

f_2(3) = 7 \bmod 6 = 1

, with

0 \ne 3

. Every output of

2x + 1

is odd, so only

1

3

5

are reached and six inputs must share them.

❌ Not quite.

f_3(1) = 1

and

f_3(5) = 25 \bmod 6 = 1

, with

1 \ne 5

— the squares of

x

and

6 - x

always agree mod

6

❌ Not quite.

f_4(0) = 2

and

f_4(2) = 8 \bmod 6 = 2

, with

0 \ne 2

: adding

2

x

adds

6

3x + 2

Show solution

The domain is finite, so list every output of each function:

$x$	$0$	$1$	$2$	$3$	$4$	$5$	verdict
$f_1$	$1$	$0$	$5$	$4$	$3$	$2$	no repeats: injection
$f_2$	$1$	$3$	$5$	$1$	$3$	$5$	$f_2(0) = f_2(3)$
$f_3$	$0$	$1$	$4$	$3$	$4$	$1$	$f_3(1) = f_3(5)$
$f_4$	$2$	$5$	$2$	$5$	$2$	$5$	$f_4(0) = f_4(2)$

For $f_1$ : $5 \cdot 2 + 1 = 11 = 6 \cdot 1 + 5$ , $5 \cdot 3 + 1 = 16 = 6 \cdot 2 + 4$ , and so on; the six outputs are all different, so no two inputs share an output and $f_1$ is an injection. Each of the others has a pair of different inputs with the same output, so none of them is an injection.

Solved: 0 / 4