foundation23 min studyLesson 113 in Mathematics

Injections, surjections, and bijections: what an inverse needs

Track collisions and missing outputs, construct inverse maps, and compare finite sizes through functions.

Before you begin

Cartesian products and relations: record which pairs are allowed

On this page

The question for today

What you’ll understand

Test injectivity and surjectivity using quantified definitions.
Explain why a codomain changes a surjectivity claim.
Construct a bijection and check its inverse on both sides.

Suppose labels must be assigned to devices. Reusing a label creates a collision, while leaving a permitted label unused creates a gap. These are independent properties of the assignment. An injection forbids collisions, a surjection forbids gaps in the declared codomain, and a bijection forbids both. The vocabulary describes information loss precisely and turns the informal phrase same number of objects into an explicit reversible correspondence.

No collisions is an input statement

A function is injective when equal outputs force equal inputs. To prove this, begin with an arbitrary equality between two outputs and derive equality of the inputs. To disprove it, exhibit two distinct allowed inputs with the same output. Squaring real numbers fails because opposite nonzero inputs collide. Squaring restricted to nonnegative real numbers is injective because a nonnegative square root uniquely recovers the input. The formula alone never specifies the entire function.

A surjection reaches every element of its declared codomain. Its proof begins with an arbitrary target and constructs an allowed input mapping to it. The same squaring rule from real numbers to real numbers is not surjective because negative targets are missed. Changing its codomain to nonnegative real numbers makes it surjective while leaving its failure of injectivity unchanged. Range describes what is reached; codomain declares what would need to be reached.

f\text{ injective}:\ f(x)=f(y)\Rightarrow x=y;\qquad f\text{ surjective}:\ (\forall b\in B)(\exists a\in A)\ f(a)=b

The first condition holds for all x,y in A. The second targets every b in the declared codomain B.↔ Scroll wide equations horizontally.

A bijection has a two-sided inverse

If a function is both injective and surjective, every target has exactly one preimage. Sending each target to that preimage defines the inverse function. Both round trips must work: start with an input, map forward and back, or start with a target, map back and forward. Checking only one direction can conceal a missing output or a collision, especially when a formula was derived by rearranging an equation without recording restrictions.

For finite sets, an injection shows the domain has no more elements than the codomain, because distinct inputs occupy distinct targets. A surjection shows the domain has at least as many, because every target needs a representative. When finite sets have equal size, either property forces the other. This last shortcut fails for infinite sets: shifting natural numbers forward is injective but misses zero when zero is included in the codomain.

g\circ f=\operatorname{id}_A,\qquad f\circ g=\operatorname{id}_B,\qquad f:A\to B,\ g:B\to A

A two-sided inverse g proves that f is bijective. Each identity uses the correct starting set.↔ Scroll wide equations horizontally.

Choose encodings that preserve the question

A useful counting bijection sends difficult objects to easier ones and gives an explicit decoding rule. For example, a subset of a finite labelled set becomes a binary word by recording one for membership and zero for absence. Decoding reads those flags back into a subset. No information is lost, so counting binary words counts subsets. Merely assigning codes is insufficient unless different objects receive different codes and every proposed code represents an allowed object.

Composition preserves injectivity when both component maps are injective, and preserves surjectivity when both are surjective. Follow the definitions to see why: equal final outputs can be pulled backwards through two injection tests, while an arbitrary final target can be reached through two existence constructions. A bijection is therefore a reliable change of representation, not a numerical coincidence. The inverse and its domains are the strongest check that the representation is actually reversible.

Work it through

Recover an integer from an odd label

Consider f from the integers to the odd integers defined by f(n) = 2n + 1. Prove it is a bijection and give its inverse.

For injectivity, suppose 2n + 1 = 2m + 1. Subtract 1 and divide by 2 to obtain n = m, so no distinct inputs collide.
For surjectivity, take an arbitrary odd integer k. By the definition of odd, k = 2r + 1 for an integer r, and f(r) = k. Every declared target is reached.
Define g(k) = (k − 1)/2, which is an integer for odd k. Compute g(f(n)) = n and f(g(k)) = k, verifying both round trips on their respective domains.

The result

The function bijects integers with odd integers. Its inverse is defined on odd integers, not on arbitrary real targets.

The living notebook

Explore the model

Interactive lab

Interactive lab · function

See a collision and repair the domain

Set a positive coefficient in $y=ax^2$ and use position x to compare opposite inputs. Predict their equal outputs, then mentally restrict the domain to nonnegative positions. The displayed quadratic makes collisions visible; it does not change its domain or codomain automatically, and a=0 requires separate treatment.

y = ax²TangentSigned integral

y at chosen x: 0.608
Tangent slope · 2ax: 1.35
Signed area · ax³/3: 0.182

Coefficient a0.75Position x0.9

t = 0 s

This lab uses only y = ax². Playback traces the curve within the fixed integration interval from 0 to x; it does not estimate numerical error or change the chosen point. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forAn inverse needs both a unique preimage and a declared set of targets that are all reached.

Pause & reason

Check your understanding

Interactive checks need JavaScript. You can still read the explanation.

Read the checkpoint explanation

Every nonnegative target has a real square root, so the map is onto. Inputs 1 and −1 have the same output, so it is not one-to-one.

Your turn

Try it yourself

Classify f(n) = n + 1 from the nonnegative integers to themselves. Then change only its codomain to make it bijective.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Look for a target with no preimage before changing the formula.

Compare with the solution

The function is injective: equality n + 1 = m + 1 implies n = m. It is not onto the nonnegative integers because zero would require input −1. With the positive integers as codomain it becomes bijective, since every positive k has the unique nonnegative preimage k − 1. The same arithmetic rule describes different functions when the codomain changes.

Keep the idea

Take it with you

Injectivity forbids collisions; surjectivity reaches every declared target.
Domains and codomains are part of a function, not annotations that can be ignored.
A counting bijection needs a reversible encoding with both round trips checked.

Read further

Original sources and deeper explanations to follow at your own pace.

MIT OpenCourseWare — Chapter 11: Cardinality rules

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.