Two things can go wrong when you try to run a function backwards. It may have sent two inputs to one output, so the backward rule cannot choose; or it may have missed part of the codomain, so the backward rule has nothing to say there. Ruling out the first is injectivity, ruling out the second is surjectivity, and a function with neither fault can be reversed exactly.

A cloakroom gives a ticket for each coat. If two coats ever got the same ticket, the attendant could not return them; if some ticket numbers were never issued, presenting one would mean nothing. A system with neither fault is a perfect matching between coats and tickets.

Here $f(a)=f(b)=p$, so the map is not injective, and nothing is sent to $r$, so it is not surjective either. Either fault alone is enough to stop the arrows being reversed.

Let $f\colon A\to B$. It is injective when $f(x)=f(y)$ forces $$; surjective when every is for some ; bijective when it is both. A bijection has an inverse function , the unique function with and . This is the one situation in which the symbol names a function rather than the preimage operation.

• To prove injectivity, assume $f(x)=f(y)$ and derive $x=y$. To disprove it, exhibit one pair $x\ne y$ with equal values.

Injectivity is a conditional statement, so the proof starts by assuming its hypothesis for the composite and works towards its conclusion. Unpack what the composite does, apply the injectivity of the outer map to strip it away, and then the injectivity of the inner map to finish. Each application is the same move: equal values force equal inputs.

Assume the hypothesis of the statement to be proved, for arbitrary points of the domain.

Unpack the composite; this is what it means.

Apply the injectivity of $g$ to the two values it has been given.

Apply the injectivity of $f$ in the same way.

The points were arbitrary, so the implication holds for every pair, which is the definition.

Injective rules out a repeated value. Surjective rules out a missed target.

An inverse function exists exactly when neither fault is present.

• Injective forbids a repeated value; surjective forbids a missed target.
• Surjectivity depends on the codomain, so it can be arranged by shrinking it to the range.
• A bijection is exactly a function with an inverse function.
• Both conditions pass to compositions; only the halves nearest the ends come back.

Great work! You now know how to:

• Prove and disprove injectivity and surjectivity by the standard opening move
• Say why surjectivity depends on the codomain and injectivity does not
• Recognise when an inverse function exists, and when only a preimage does
• Say which of the two conditions a composition inherits, and which halves come back