Injective Functions

Can two different inputs to a function ever produce the same output? For some functions the answer is always no. These functions turn out to be exactly the ones that can be "undone" on their range. This single question — does distinctness of inputs guarantee distinctness of outputs — is the heart of the notion of an injective function, also called a one-to-one function. It sounds like a small technical property. But it is one of the load-bearing walls of modern mathematics. It is the precise tool used to compare the sizes of infinite sets, to embed one structure inside another without collapsing information, and to certify that an operation like encryption or hashing does not destroy distinctions between messages. The idea matters because "size" and "sameness" for infinite collections cannot be checked by counting. Instead, mathematicians certify that one set is "at least as large as" another by exhibiting an injective function from the first into the second. This is a rule that assigns to each element of the first set a distinct partner in the second. Injectivity is therefore the engine behind the entire theory of Comparing Cardinalities. This includes the celebrated fact that the real numbers outnumber the natural numbers. The big picture is this: a function is a package of input–output pairs satisfying a rule (see Functions as Special Relations). Injectivity is one of the two independent properties — the other being surjectivity. Their conjunction (bijectivity) makes a function reversible. Understanding injectivity in isolation, with clean proof techniques, is the prerequisite for understanding Bijections and Inverse Functions correctly. An inverse function can only be defined without ambiguity when the original function never sends two points to the same place. This article gives the precise definition of injectivity, the standard proof strategies (direct argument and contrapositive), a full worked derivation for both a polynomial-type and a piecewise function, a theorem connecting injectivity to left-invertibility, and a counterexample showing exactly what fails when the codomain is chosen carelessly.

Key takeaways

An injective (one-to-one) function never sends two distinct inputs to the same output.
Formally: $f$ is injective iff $f(x_1) = f(x_2) \implies x_1 = x_2$ for all $x_1, x_2$ in the domain.
The standard proof technique is the direct argument or its logical twin, the contrapositive: $x_1 \neq x_2 \implies f(x_1) \neq f(x_2)$ .
Injectivity is equivalent to the existence of a left inverse function (a retraction), when the domain is nonempty.
Graphically, injectivity is the horizontal line test: no horizontal line meets the graph more than once.
Key idea: injectivity is a promise that the function loses no information — it is the algebraic seed of comparing the sizes of sets.

Where this lives today

Injectivity is not a museum piece confined to introductory proof courses — it is load-bearing machinery across mathematics and its applications.

Cardinality and set theory. The relation $|A| \le |B|$ is defined by the existence of an injection $A \to B$ ; the Cantor–Schröder–Bernstein theorem shows that mutual injections $A \to B$ and $B \to A$ force a bijection to exist, the technical foundation for Comparing Cardinalities.
Linear algebra. A linear map $T : V \to W$ between vector spaces is injective if and only if its kernel is $\{0\}$ ; this single fact converts an infinite verification into a one-line computation, and underlies rank-nullity arguments.
Cryptography. Encryption functions must be injective (for a fixed key) so that decryption — a left inverse in the exact sense of the theorem above — is possible; a non-injective cipher would make some ciphertexts undecryptable to a unique plaintext.
Hash functions and data structures. Ideal hash functions aim to approximate injectivity ("collision resistance"); the entire theory of hash collisions is the theory of failures of injectivity, studied quantitatively via the birthday bound.
Real analysis. Strictly monotonic functions (strictly increasing or strictly decreasing) are always injective, giving a fast sufficient criterion used constantly when justifying the existence of inverse functions like $\ln$ , $\arcsin$ (on restricted domains), and root functions.
Computer science. Injective functions model perfect encodings: lossless compression schemes and unique object identifiers (serial numbers, memory addresses under certain guarantees) are required to be injective on their domain of legitimate inputs.
Category theory. The categorical generalization of "injective" is a monomorphism, defined by a left-cancellation property that specializes exactly to the set-theoretic definition given here when working in the category of sets.

Ask the tutor: How does injectivity of a function combine with surjectivity to prove the Cantor–Schröder–Bernstein theorem when comparing infinite sets?

f : A \to B

Intuition

Think of a function as a machine with input slot $A$ and output slot $B$ . Injectivity says the machine keeps a perfect paper trail: if you only ever see the output, you can still work out which input produced it, provided you know the output came from this function at all. Nothing is ever "merged." Two different students never get assigned the same locker; two different countries never get the same capital-city code; two different DNA sequences (in an idealized world) never hash to the same fingerprint. This is exactly the geometric content of the horizontal line test for real-valued functions of a real variable: draw the graph of $f$ , and draw any horizontal line $y = c$ . If $f$ is injective, that line can touch the graph in at most one point, because two intersection points would be two different $x$ -values sharing the same output $c$ . It is essential to keep injectivity conceptually separate from surjectivity (hitting every element of $B$ ) — a function can miss most of $B$ and still be injective, as long as it never doubles up on the elements it does hit. The rectangle-and-arrows picture below makes this visible: every arrow lands on a different target, but some targets in $B$ receive no arrow at all. That is completely compatible with injectivity.

Figure

An injective function

f:A\to B

with

A=\{a_1,a_2,a_3\}

: three distinct inputs land on three distinct outputs, even though

B

has an extra unused element

b_4

Proof techniques in practice

There are exactly two standard logical strategies for establishing $f: A \to B$ is injective, and one standard strategy for refuting it. 1. Direct proof of the implication. Fix arbitrary $x_1, x_2 \in A$ , assume $f(x_1) = f(x_2)$ , and derive $x_1 = x_2$ using algebra or the definition of $f$ . 2. Contrapositive proof. Fix arbitrary $x_1, x_2 \in A$ with $x_1 \neq x_2$ , and show $f(x_1) \neq f(x_2)$ . This is logically equivalent to the direct method and is often easier when $f$ involves strict monotonicity or absolute values. 3. Refutation by counterexample. To show $f$ is not injective, it suffices to exhibit one explicit pair $x_1 \neq x_2$ with $f(x_1) = f(x_2)$ — an existential witness, not a universal argument.

f : A \to B

\Leftarrow

f : A \to B

x_1, x_2 \in A

Worked examples

Example 1 — a rational (non-polynomial) function, asymmetric domain. Let $A = (-\infty, 2) \cup (2, \infty)$ — the reals excluding the single point $2$ — and let $B = \mathbb{R} \setminus \{0\}$ . Define

f(x) = \frac{3}{x - 2}.

We claim $f : A \to B$ is injective. First check $f$ is well-defined into $B$ : for $x \neq 2$ , $x - 2 \neq 0$ so $f(x)$ is defined, and $f(x) = 3/(x-2) \neq 0$ since a nonzero numerator over a finite denominator is never $0$ ; so indeed $f(x) \in B$ for all $x \in A$ . Direct proof of injectivity. Let $x_1, x_2 \in A$ with $f(x_1) = f(x_2)$ :

\frac{3}{x_1 - 2} = \frac{3}{x_2 - 2}.

Both denominators are nonzero (since $x_1, x_2 \neq 2$ ), so we may cross-multiply:

3(x_2 - 2) = 3(x_1 - 2).

Dividing both sides by $3$ (nonzero), $x_2 - 2 = x_1 - 2$ , hence $x_1 = x_2$ . This establishes injectivity directly, verifying the definition for arbitrary $x_1, x_2$ . Sanity check with actual numbers. Take $x_1 = 5$ : $f(5) = 3/3 = 1$ . Take $x_2 = -1$ : $f(-1) = 3/(-3) = -1$ . Indeed $1 \neq -1$ and $5 \neq -1$ , consistent with injectivity — no collision occurs. Take $x_2 = 5$ again with a different candidate $x_3 = 2.5$ : $f(2.5) = 3/0.5 = 6 \neq 1 = f(5)$ , again no collision, as guaranteed by the theorem above since $5 \neq 2.5$ . Left inverse, explicitly constructed as in the theorem. Since $\operatorname{ran}(f) = B$ here (one can check every nonzero real is hit: given $y \neq 0$ , solve $y = 3/(x-2)$ to get $x = 2 + 3/y \in A$ ), the left inverse is total on $B$ and is given by

g(y) = 2 + \frac{3}{y}.

Check: $g(f(x)) = 2 + \dfrac{3}{3/(x-2)} = 2 + (x - 2) = x$ . This matches $\mathrm{id}_A$ , confirming injectivity via the equivalence proved above.

Example 2 — a piecewise function requiring case analysis. Define $f : \mathbb{Z} \to \mathbb{Z}$ by

f(n) = \begin{cases} 2n & n \geq 0 \\ -2n - 1 & n < 0. \end{cases}

(This is a classical pairing-style function: nonnegative integers go to nonnegative even numbers, negative integers go to nonnegative odd numbers.) We show $f$ is injective using the contrapositive strategy combined with case analysis, since the formula itself splits into cases. Suppose $n_1 \neq n_2$ in $\mathbb{Z}$ . We must show $f(n_1) \neq f(n_2)$ . There are three sub-cases depending on the signs of $n_1, n_2$ . Case A: $n_1, n_2 \geq 0$ . Then $f(n_1) = 2n_1$ and $f(n_2) = 2n_2$ . If $f(n_1) = f(n_2)$ then $2n_1 = 2n_2$ , so $n_1 = n_2$ , contradicting $n_1 \neq n_2$ . So $f(n_1) \neq f(n_2)$ in this case. Case B: $n_1, n_2 < 0$ . Then $f(n_1) = -2n_1 - 1$ and $f(n_2) = -2n_2-1$ . If these were equal, $-2n_1 = -2n_2$ , so $n_1 = n_2$ , again a contradiction. So $f(n_1)\neq f(n_2)$ . Case C: one is $\geq 0$ and the other $<0$ (WLOG $n_1 \geq 0 > n_2$ ). Then $f(n_1) = 2n_1$ is even and nonnegative, while $f(n_2) = -2n_2 - 1$ is odd (since $-2n_2$ is even, subtracting $1$ makes it odd). An even number can never equal an odd number, so $f(n_1) \neq f(n_2)$ automatically — no algebra even needed here, only parity. Since all three exhaustive cases give $f(n_1) \neq f(n_2)$ , the contrapositive holds for every pair with $n_1 \neq n_2$ , so $f$ is injective. Numeric check. $f(-3) = -2(-3) - 1 = 5$ . $f(2) = 4$ . $f(0) = 0$ . $f(-1) = 1$ . All four outputs $5, 4, 0, 1$ are distinct, consistent with injectivity, and note the outputs are exactly $\{0,1,4,5\}$ — a mix of small evens and odds, matching the parity argument in Case C (evens from nonnegative inputs, odds from negative inputs).

Why the domain/codomain framing matters

x_1, x_2

Scope, edge cases & common traps

Situation	What to check	Common error
Domain is a proper subset of a larger natural domain	Injectivity must hold on the stated domain, not some ambient superset	Forgetting the restriction and testing points outside it
Codomain larger than the range	Injectivity says nothing about hitting every element of $B$	Confusing injective with surjective/bijective
Empty domain $A = \varnothing$	The universal statement is vacuously true: $f = \varnothing$ is injective by default	Assuming injectivity requires a nonempty witness; it does not
Piecewise formulas	Must rule out cross-case collisions, not just within-case collisions	Checking each branch separately and skipping the "one from each branch" case
Finite sets	If $\|A\| > \|B\|$ , no function $A \to B$ can be injective (pigeonhole)	Trying to construct an injection anyway instead of citing the counting argument

The mathematician behind it

Origins · 1 minNicolas Bourbaki (collective pseudonym) and how this was discovered

Nicolas Bourbaki (collective pseudonym)

founded 1935, active through the 20th century · Modern foundational mathematics, France

The terms "injective," "surjective," and "bijective" were coined and standardized by the Bourbaki group, a collective of mostly French mathematicians writing under a shared pseudonym starting in the 1930s. Their multi-volume Éléments de mathématique fixed the modern set-theoretic vocabulary for functions that undergraduates use today, replacing older, less uniform terminology like "one-to-one" (still common in English-language texts as a synonym for injective) and "onto" (for surjective). The idea of injectivity itself is far older — implicit already in Cantor's late-19th-century work comparing the sizes of infinite sets — but the crisp trichotomy of injective/surjective/bijective, and the systematic proof style built around it, is a 20th-century codification.

History

- 1874–1884: Georg Cantor develops the theory of comparing infinite sets via correspondences, implicitly using injective and bijective maps to define and compare cardinalities.

- 1888: Richard Dedekind, in Was sind und was sollen die Zahlen?, gives an explicit set-theoretic treatment of one-to-one mappings ("ähnliche Abbildung," similar mapping) between sets.

- 1895–1897: Cantor formalizes cardinal comparison

|A| \leq |B|

via the existence of an injection

A \to B

, laying groundwork for the Cantor–Schröder–Bernstein theorem.

- 1935 onward: The Bourbaki collective introduces the standardized terms injective, surjective, bijective in their foundational volumes on set theory.

- 1950s: The vocabulary becomes standard in university curricula worldwide, cementing "injective function" as the modern term for "one-to-one function."

Is "injective" the same thing as "one-to-one"?

Yes — in most English-language textbooks, "injective" and "one-to-one" are exact synonyms, both meaning distinct inputs always give distinct outputs. The word "injective" (and "injection" for the function itself) is the term standardized by the Bourbaki school and used in more formal or research-level writing, while "one-to-one" is the older, still very common phrasing in introductory courses. Be careful with the closely related but different phrase "one-to-one correspondence," which is a synonym for bijective, not merely injective — the word "correspondence" is doing important extra work there, signaling that the function is also surjective.

Can an injective function fail to be surjective, and vice versa?

Yes to both, and they are logically independent properties. The function $f: \mathbb{N} \to \mathbb{N}$ given by $f(n) = 2n$ is injective (distinct naturals double to distinct naturals) but not surjective, since no odd number is ever hit. Conversely, $g : \mathbb{N} \to \mathbb{N}$ given by $g(0) = 0$ and $g(n) = n - 1$ for $n \geq 1$ is surjective (every natural number $m$ is hit by $m+1$ ) but not injective, since $g(0) = 0 = g(1)$ . A function that is both injective and surjective is called bijective, the subject of Bijections and Inverse Functions.

How does injectivity interact with function composition when the composite is injective but the pieces are not?

If $h \circ f$ is injective, it forces $f$ itself to be injective: if $f(x_1) = f(x_2)$ then $h(f(x_1)) = h(f(x_2))$ , so $(h\circ f)(x_1) = (h\circ f)(x_2)$ , and injectivity of the composite forces $x_1 = x_2$ . However, this argument says nothing about $h$ on its own — $h$ can be wildly non-injective outside the range of $f$ . For instance, let $f : \{1\} \to \mathbb{R}$ send $1 \mapsto 5$ , and let $h:\mathbb{R}\to\mathbb{R}$ send every real to $0$ except that $h(5) = 5$ is not even required; here $h\circ f$ is trivially injective (a one-point domain always gives an injective function) despite $h$ collapsing everything else. So "composite injective" only certifies the first map, not the second.

Is the empty function injective?

Yes, vacuously. If $A = \varnothing$ , then $f : \varnothing \to B$ is the empty set of pairs, and the defining implication " $\forall x_1, x_2 \in A\,(f(x_1)=f(x_2) \implies x_1=x_2)$ " has a universally quantified statement over an empty domain. Since there are no elements of $A$ to serve as counterexamples, the universal statement is vacuously true, exactly as with any universally quantified claim over an empty set. This is a standard and important edge case, not a paradox.

Does injectivity depend only on the formula, or also on the stated domain and codomain?

It depends on all three together — the formula, the domain, and (for well-definedness, though not directly for injectivity) the codomain. As shown in the counterexample above, $f(x) = x^2$ is injective as a function $[0,\infty)\to\mathbb{R}$ but not as a function $\mathbb{R}\to\mathbb{R}$ , even though the algebraic rule never changes. Whenever you assert " $f$ is injective," you are implicitly asserting it about a fully specified function — rule plus domain — not about a bare formula. Always state the domain explicitly before checking injectivity.

What is the fastest sufficient condition for injectivity of a real function, without doing the full algebraic proof?

For a function $f$ defined on an interval, if $f$ is strictly increasing (i.e. $x_1 < x_2 \implies f(x_1) < f(x_2)$ ) or strictly decreasing throughout its domain, then $f$ is automatically injective: distinct points get strictly ordered outputs, which are therefore unequal. This is provable directly from the trichotomy of real numbers ( $x_1 < x_2$ , $x_1 = x_2$ , or $x_1 > x_2$ ) applied case by case. In calculus, checking $f'(x) > 0$ (or $<0$ ) on an interval is the usual shortcut to strict monotonicity, and hence to injectivity, without doing an algebraic solve of $f(x_1)=f(x_2)$ .

How does injectivity generalize beyond functions on sets, say to structures with extra properties?

In algebra, an injective homomorphism between groups, rings, or vector spaces is a structure-preserving map that is also injective as a set function; for linear maps this reduces to the map having trivial kernel. In category theory more broadly, the right generalization is a monomorphism: a morphism $f$ such that $f \circ g_1 = f \circ g_2$ implies $g_1 = g_2$ for all morphisms $g_1, g_2$ with matching codomain. In the category of sets this categorical definition is provably equivalent to the elementwise definition given in this article, but in other categories (e.g. rings) monomorphisms and set-theoretic injections can occasionally diverge in subtle ways, which is part of why category theory treats "injective" and "monomorphism" as related but formally distinct notions.