Proving a Function Is Bijective: Injectivity and Surjectivity

Welcome back. In the previous lesson, induction proved an infinite family of claims by establishing a base case and a general implication from $P(k)$ to $P(k+1)$. This lesson uses the same proof discipline in a different setting: a bijection claim is not a single intuition such as “the formula has an inverse.” It is the conjunction of two precise statements, each with its own quantifiers and proof strategy.

We will learn to prove that a function is injective and surjective, then combine those proofs to establish bijectivity. The key theme is that the declared domain and codomain are part of the function, not decoration.

---

Two ways a function can succeed

Let

$$f:X\to Y$$

be a function. Every element of $X$ is assigned exactly one output in $Y$. The questions of injectivity and surjectivity ask about the reverse direction: how do elements of $Y$ arise from inputs in $X$?

A function is injective (or one-to-one) when distinct inputs cannot collide at the same output. Formally,

$$\forall x_1,x_2\in X,f(x_1)=f(x_2)⟹x_1=x_2.$$

Equivalently, the contrapositive says

$$\forall x_1,x_2\in X,x_1\ne x_2⟹f(x_1)\ne f(x_2).$$

Thus, an injectivity proof usually begins by assuming two outputs are equal and then uses algebra or definitions to force the inputs to be equal.

A function is surjective (or onto) when every element of the stated codomain is actually attained:

$$\forall y\in Y,\exists x\in X\text{ such that }f(x)=y.$$

The order of the quantifiers matters. You begin with an arbitrary target $y$, then construct an input $x$, which may depend on that chosen $y$.

A function is bijective precisely when it is both injective and surjective. In a bijection, every element of the codomain comes from exactly one input.

Read the three diagrams carefully:

• In the injection diagram, no green dot receives two arrows, but one green dot is unused.
• In the surjection diagram, every green dot receives at least one arrow, but two orange dots share an output.
• In the bijection diagram, every green dot receives exactly one arrow.

For finite sets, this provides a quick visual test. For functions on infinite sets or functions given by formulas, however, a proof must work with the definitions.

---

The proof obligations are different

Because the definitions have different quantifier structures, injectivity and surjectivity cannot be proved by the same opening move.

Property	Start with	What you must produce
Injective	Arbitrary $x_1,x_2\in X$ and $f(x_1)=f(x_2)$	A derivation of $x_1=x_2$
Surjective	Arbitrary $y\in Y$	A specific $x\in X$ satisfying $f(x)=y$
Bijective	A complete injectivity proof and a complete surjectivity proof	The conclusion that both conditions hold

For a formula, surjectivity often begins with useful scratchwork: solve the equation

$$f(x)=y$$

for $x$. That algebra suggests a possible preimage. But a finished proof has two further duties:

1. Verify that your proposed $x$ lies in the domain.
2. Substitute it back and verify that its image is the arbitrary target $y$.

The domain and codomain can completely change the answer. Consider the same formula in two settings:

$$g(x)=3x+2.$$

As a function

$$g:\mathbb{R}\to \mathbb{R},$$

it is bijective. Given any $y\in \mathbb{R}$, the input

$$x=\frac{y-2}{3}$$

is a real number and satisfies $g(x)=y$.

But as a function

$$g:\mathbb{Z}\to \mathbb{Z},$$

it remains injective while failing to be surjective. For example, $0\in \mathbb{Z}$ has no integer preimage, since

$$3x+2=0$$

would require

$$x=-\frac{2}{3},$$

which is not an integer. The formula did not change; the permissible inputs did.

This distinction is especially important in number theory, where a proposed preimage may be rational or real but not integral.

---

A complete bijection proof

Consider the function

$$f:\mathbb{R}\setminus \{-1\}\to \mathbb{R}\setminus \{1\}$$

defined by

$$f(x)=\frac{x}{x+1}.$$

We will prove that $f$ is bijective.

Before proving the two main properties, notice that the rule really does land in the stated codomain. If $x\ne -1$, the denominator is nonzero. Also, $f(x)$ cannot equal $1$, since

$$\frac{x}{x+1}=1$$

would imply

$$x=x+1,$$

which is impossible. Thus $f(x)\in \mathbb{R}\setminus \{1\}$, as required.

Injectivity

Let $a,b\in \mathbb{R}\setminus \{-1\}$, and suppose

$$f(a)=f(b).$$

By the definition of $f$,

$$\frac{a}{a+1}=\frac{b}{b+1}.$$

Because $a+1\ne 0$ and $b+1\ne 0$, cross-multiplication is valid:

$$a(b+1)=b(a+1).$$

Expanding both sides gives

$$ab+a=ab+b.$$

Subtracting $ab$ yields

$$a=b.$$

Therefore,

$$f(a)=f(b)⟹a=b,$$

so $f$ is injective.

The proof did not begin by declaring $a\ne b$. Instead, it assumed equal outputs and established equal inputs, exactly matching the definition.

Surjectivity

Let

$$y\in \mathbb{R}\setminus \{1\}$$

be arbitrary. We seek $x$ such that

$$\frac{x}{x+1}=y.$$

Solving this equation in scratchwork gives

$$x=\frac{y}{1-y}.$$

Now use this as the candidate preimage:

$$x=\frac{y}{1-y}.$$

Since $y\ne 1$, the denominator $1-y$ is nonzero, so $x$ is a real number. Moreover,

$$x+1=\frac{y}{1-y}+1=\frac{1}{1-y},$$

which is nonzero. Hence $x\ne -1$, and therefore

$$x\in \mathbb{R}\setminus \{-1\}.$$

It remains to check that this input reaches the selected target:

$$\begin{array}{rl}f(x)& =f\left(\frac{y}{1-y}\right)\\ & =\frac{\frac{y}{1-y}}{\frac{y}{1-y}+1}\\ & =\frac{\frac{y}{1-y}}{\frac{1}{1-y}}\\ & =y.\end{array}$$

Thus every $y\in \mathbb{R}\setminus \{1\}$ has a preimage in the domain. Therefore $f$ is surjective.

Since $f$ is both injective and surjective, it is bijective. $\square$

---

Why this proof works

The surjectivity calculation uncovered more than existence: for each target $y$, it found the only possible preimage,

$$\frac{y}{1-y}.$$

Injectivity ensures that no second input can map to the same $y$. Together, the two parts justify defining an inverse function

$$f^{-1}:\mathbb{R}\setminus \{1\}\to \mathbb{R}\setminus \{-1\}$$

by

$$f^{-1}(y)=\frac{y}{1-y}.$$

For now, regard an inverse as a useful consequence and a source of scratchwork. The essential proof of bijectivity remains the two-part argument above; simply writing down a plausible inverse formula is not a substitute for checking that it is well-defined and truly reverses the function.

A final proof-writing checklist is worth keeping:

1. Write the full function declaration. Include both domain and codomain.
2. Check that the formula lands in the codomain, if this is not automatic.
3. Prove injectivity using arbitrary domain elements with equal outputs.
4. Prove surjectivity using an arbitrary codomain target and a constructed preimage.
5. Verify domain membership of that proposed preimage.
6. Conclude explicitly: “Therefore $f$ is injective and surjective, hence bijective.”

---

Key takeaways

An injective function has no output collisions:

$$f(x_1)=f(x_2)⟹x_1=x_2.$$

A surjective function misses no element of its stated codomain:

$$\forall y\in Y,\exists x\in X\text{ such that }f(x)=y.$$

A bijection requires both properties. In a formal proof, injectivity is normally an equality argument, while surjectivity is a construction argument: begin with an arbitrary target, solve for a candidate preimage, show that it belongs to the domain, and verify that it maps to the target.

This completes the foundational proof-methods module. Next, the course turns to divisibility and the division algorithm, where the same habits of precise definitions and carefully chosen constructions will reappear.