Injective, Surjective, and Bijective Functions

A function $f$ is injective (one-to-one) if different inputs always produce different outputs — no two distinct inputs ever land on the same output value. It is surjective (onto) if every element of the target set is actually hit by some input — nothing in the output range is left unreachable. A function that is both — bijective — pairs up inputs and outputs perfectly one-for-one, which is exactly the condition needed for the function to have a genuine inverse: reversing a bijection just swaps which set is the input and which is the output, with no ambiguity and nothing missed.

For example, $f(x) = x^2$ on all real numbers is neither injective (since $f(2) = f(-2) = 4$, two different inputs collide) nor surjective onto all real numbers (negative numbers are never reached as outputs). Restricting the domain to non-negative $x$ makes it injective, and restricting the target set to non-negative reals as well makes it bijective — the same formula becomes different types of function purely by choosing its domain and range.

These classifications matter beyond pure math: an encoding scheme that must be uniquely decodable needs to be injective, and a hashing or compression scheme that claims to cover its full output space needs surjectivity checked explicitly, not assumed. A common brainteaser tests exactly this distinction: asked whether a given transformation "loses information," the real question is whether it's injective — if two different inputs can map to the same output, that information cannot be recovered from the output alone, regardless of how the function otherwise behaves.