Fact-checked by Grok 2 weeks ago

Injective function

In , an injective function, also known as a function or an injection, is a f: A \to B between two sets that maps distinct elements of its domain A to distinct elements of its B; that is, if f(x) = f(y), then x = y for all x, y \in A. The terms "injective," "surjective," and "bijective" were introduced by the French mathematical collective in their foundational work on during the mid-20th century. Equivalently, an injective function ensures that each in the has at most one preimage in the , meaning no two elements share the same output. This property distinguishes injective functions from non-injective ones, where collisions occur (multiple inputs mapping to the same output). For example, the function f: \mathbb{R} \to \mathbb{R} defined by f(x) = x^3 is injective because distinct real numbers cube to distinct real numbers, whereas f(x) = x^2 is not, as f(2) = f(-2) = 4. The of an injective function is itself a , though it may not be defined on the entire unless the function is also surjective. Key properties of injective functions include closure under : if f: A \to B and g: B \to C are both injective, then g \circ f: A \to C is injective. For finite sets, an injective function from set A to set B implies that the cardinality of A is less than or equal to that of B (|A| \leq |B|). In linear , a linear between spaces is injective if and only if its is the zero , which is essential for understanding isomorphisms and bases. Injective functions form one half of the definition of a (the other being surjectivity), enabling correspondences between sets and playing a central role in comparisons, , and proofs of uncountability.

Definition and Characterization

Formal Definition

In set theory, a function f: A \to B is a relation that assigns to each element of the domain set A exactly one element of the codomain set B, without requiring that every element of B is assigned. Such a function f is injective if it maps distinct elements of A to distinct elements of B; formally, \forall x, y \in A, if f(x) = f(y), then x = y. This condition is equivalently stated as \forall x, y \in A, if x \neq y, then f(x) \neq f(y). The injectivity ensures a one-to-one correspondence between elements of A and their images under f in the subset f(A) \subseteq B. The term "injective" was coined by the collective of mathematicians known as and first appeared in their 1954 publication Théorie des ensembles to provide precise terminology in set-theoretic contexts.

Equivalent Formulations

An injective function f: A \to B can be equivalently characterized by the condition that distinct elements in the domain A map to distinct elements in the B, that is, for all x, y \in A, if x \neq y, then f(x) \neq f(y). This property is also equivalent to the statement that the preimage (or ) of every \{b\} for b \in B contains at most one from A, meaning each in B has at most one preimage under f. Injectivity differs from surjectivity, which requires every in B to have at least one preimage; a function that is both injective and surjective is bijective. A f: A \to B is bijective it has both a left g: B \to A such that g \circ f = \mathrm{id}_A and a right h: B \to A such that f \circ h = \mathrm{id}_B, where \mathrm{id}_A and \mathrm{id}_B are the identity functions on A and B, respectively (and in fact g = h). In arrow diagrams, which visually represent functions by drawing arrows from elements of A to their images in B, injectivity corresponds to the absence of converging arrows, ensuring no two elements from A point to the same element in B.

Examples and Illustrations

Injective Examples

One common example of an injective function is the inclusion map f: \mathbb{N} \to \mathbb{Z} defined by f(n) = n, where \mathbb{N} is the set of natural numbers (positive integers) and \mathbb{Z} is the set of all integers; this mapping embeds the natural numbers into the integers without repetition, making it injective but not surjective since negative integers lack preimages. Another straightforward example is the linear function f: \mathbb{R} \to \mathbb{R} given by f(x) = 2x, which scales real numbers by a factor of 2 and preserves distinctness, ensuring injectivity as distinct inputs yield distinct outputs. For finite sets, consider f: \{1,2,3\} \to \{a,b,c,d,e\} defined by f(1) = a, f(2) = b, f(3) = c; this assigns each element in the domain to a unique element in the codomain, demonstrating injectivity without covering the entire codomain. In non-mathematical contexts, an injective function can be analogized to assigning unique identification numbers to individuals in a , where each person receives a distinct ID to avoid overlaps, mirroring the correspondence of injectivity.

Non-Injective Counterexamples

A provides a simple to injectivity. Consider the function f: \mathbb{R} \to \mathbb{R} defined by f(x) = 5 for all x \in \mathbb{R}. This function maps every to the same output value 5, so for any distinct x_1 \neq x_2, it holds that f(x_1) = f(x_2), violating the injectivity condition. Another common non-injective function is the squaring function on the real numbers. Define f: \mathbb{R} \to \mathbb{R} by f(x) = x^2. Here, f(-1) = 1 = f(1), but -1 \neq 1, demonstrating that distinct inputs can produce the same output. Functions between finite sets can also fail injectivity when the domain is larger than the codomain, as illustrated by the pigeonhole principle. For example, consider f: \{1,2,3\} \to \{a,b\} where f(1) = a, f(2) = a, and f(3) = b. Since f(1) = f(2) but $1 \neq 2, the function is not injective. In each of these cases, the violation of injectivity arises because there exist distinct elements in the domain that map to the same element in the codomain.

Core Properties

Closure under Composition

Injective functions are closed under composition. Specifically, if f: A \to B and g: B \to C are both injective, then their composition g \circ f: A \to C is also injective. To see this, suppose (g \circ f)(x) = (g \circ f)(y); then g(f(x)) = g(f(y)), so f(x) = f(y) by injectivity of g, and thus x = y by injectivity of f. This property ensures that chains of injective mappings remain injective, which is useful in constructing embeddings and analyzing function structures.

Reversibility and Inverses

A function f: A \to B is injective if and only if there exists a left inverse g: B \to A such that the composition g \circ f = \mathrm{id}_A, the on A. To construct such a g, for each b \in B, if b is in the image f(A) then set g(b) to be the unique a \in A with f(a) = b, which exists and is unique by injectivity; if b \notin f(A), set g(b) to some fixed element of A (assuming A \neq \emptyset). This ensures g(f(x)) = x for all x \in A. This left inverse undoes the mapping of f precisely on its : for any x \in A, g(f(x)) = x, recovering the original input from its output in f(A). However, g need not be defined uniquely or meaningfully outside f(A), as elements of B \setminus f(A) are not in the of f. When restricted to its image, an injective function f: A \to f(A) becomes bijective, admitting a two-sided f^{-1}: f(A) \to A satisfying both f^{-1} \circ f = \mathrm{id}_A and f \circ f^{-1} = \mathrm{id}_{f(A)}. This inverse coincides with the left inverse g on f(A). Thus, injective functions are not generally invertible from A to B without adjusting the codomain to the image, underscoring that injectivity alone does not guarantee full reversibility over the entire .

Cardinality and Size Preservation

An injective function f: A \to B implies that the cardinality of the domain set A is less than or equal to the of the set B, denoted |A| \leq |B|. This inequality holds in general for any sets A and B, where for infinite sets, |A| \leq |B| is defined precisely by the existence of such an injection. For finite sets, an injective function f: A \to B implies |A| \leq |B| in the standard numerical sense, and equality |A| = |B| holds f is bijective. In this case, injectivity alone ensures that no elements of A map to the same element in B, so the size of the matches |A|, which cannot exceed |B| without repetition. Moreover, if |A| = |B|, the injection must cover all of B, making it surjective as well. In the infinite case, the situation is more subtle, as injectivity does not necessarily imply surjectivity even when cardinalities are equal. For example, the function f: \mathbb{N} \to \mathbb{Z} defined by f(n) = n/2 if n is even and f(n) = -(n+1)/2 if n is odd is injective but not surjective, yet |\mathbb{N}| = |\mathbb{Z}| because injections exist both ways, establishing equal cardinality via the Schröder–Bernstein theorem. The Schröder–Bernstein theorem states that if there exist injective functions f: A \to B and g: B \to A, then there is a bijection between A and B, so |A| = |B|. If |A| = |B|, an existing injection from A to B can be extended to a , though this extension generally requires the for infinite sets to select appropriate mappings on the complement of the image.

Preservation of Distinctness

An injective function preserves the distinctness of elements by ensuring that distinct inputs in the are mapped to distinct outputs in the . Formally, a f: A \to B is injective if for all x, y \in A, x \neq y implies f(x) \neq f(y), or equivalently, f(x) = f(y) implies x = y. This property prevents the collapsing of distinct points under the mapping, maintaining separation at the level of individual elements. This preservation extends to subsets of the domain. Specifically, if X and Y are disjoint subsets of A (i.e., X \cap Y = \emptyset), then their images under f are also disjoint: f(X) \cap f(Y) = \emptyset. To see this, suppose there exists z \in f(X) \cap f(Y); then z = f(x) for some x \in X and z = f(y) for some y \in Y, so f(x) = f(y) implies x = y by injectivity, contradicting X \cap Y = \emptyset. Injective functions also induce injections on collections of subsets. In particular, f induces an injective map from the power set \mathcal{P}(A) to \mathcal{P}(B), defined by sending each subset S \subseteq A to its image f(S) = \{f(s) \mid s \in S\}. This induced map is injective because if f(S) = f(T), then for every s \in S, f(s) \in f(T), so s \in T by injectivity of f, and similarly T \subseteq S, hence S = T. When an order is defined on the domain and codomain, monotonic injective functions further preserve that order. A strictly increasing (or strictly decreasing) function between ordered sets is injective and maintains the relative ordering of elements, as x < y implies f(x) < f(y) (or f(x) > f(y) for decreasing), ensuring both distinctness and structural separation.

Proof Techniques

Direct Proof Methods

One of the primary direct methods to establish that a function f: A \to B is injective involves assuming f(x) = f(y) for arbitrary x, y \in A and demonstrating that this equality implies x = y. This approach leverages algebraic properties of the function to manipulate the equation f(x) - f(y) = 0 and factor out (x - y), showing that the remaining factor is nonzero unless x = y. For polynomial functions, this technique is particularly effective. Consider f(x) = x^3 + x. Assume f(x) = f(y), so x^3 + x = y^3 + y. Rearranging gives x^3 - y^3 + x - y = 0, which factors as (x - y)(x^2 + [xy](/page/XY) + y^2 + 1) = 0. The factor x^2 + [xy](/page/XY) + y^2 + 1 can be rewritten as \left(x + \frac{y}{2}\right)^2 + \frac{3}{4}y^2 + 1 \geq 1 > 0 for all real x, y, since the is and the added constant ensures strict positivity. Thus, x - y = 0, so x = y, proving injectivity. Similarly, for exponential functions, direct algebraic manipulation applies. Let f(x) = e^x. Assume f(x) = f(y), so e^x = e^y. This implies e^{x - y} = 1. By the properties of the exponential function, e^z = 1 if and only if z = 0, so x - y = 0 and x = y. This confirms injectivity on the reals. For differentiable functions on the real numbers, another direct method uses the derivative to show strict monotonicity, which implies injectivity. If f'(x) > 0 for all x in an interval, then f is strictly increasing. To prove this leads to injectivity, suppose f(a) = f(b) with a < b. By Rolle's theorem, there exists c \in (a, b) such that f'(c) = 0, contradicting f'(x) > 0. Thus, no such a \neq b exists, so f is injective. For instance, f(x) = x^3 + x has f'(x) = 3x^2 + 1 > 0, confirming the earlier algebraic result via this calculus approach. In cases of finite domains, direct proof can involve explicit computational verification. For a function f: S \to T where S and T are finite sets, compute f(x) for each x \in S and confirm that all images are distinct, ensuring no collisions occur. This exhaustive check establishes injectivity when the domain size does not exceed the codomain size, as seen in simple mappings like permutations of finite sets.

Contrapositive and Other Approaches

One effective indirect method for establishing the injectivity of a function f: A \to B is to prove the contrapositive of the definition: for all x, y \in A, if x \neq y, then f(x) \neq f(y). This logically equivalent form often simplifies reasoning by assuming distinct inputs and showing distinct outputs. A classic example is the f(x) = e^x: \mathbb{R} \to (0, \infty). Assume x \neq y. , suppose x > y. Then, since the exponential function is strictly increasing, e^x > e^y, so f(x) \neq f(y). Thus, f is injective. In , consider the f(x) = ax + b \pmod{n} on \mathbb{Z}/n\mathbb{Z}. This is injective precisely when \gcd(a, n) = 1. To verify, assume x \neq y \pmod{n}, so x - y \not\equiv 0 \pmod{n}. Then a(x - y) \not\equiv 0 \pmod{n} because \gcd(a, n) = 1 implies a has a modular inverse. Thus, ax + b \not\equiv ay + b \pmod{n}, confirming injectivity under the gcd condition and extending to permutations of \mathbb{Z}/n\mathbb{Z}, where such functions generate the . For finite sets, the provides an indirect test for non-injectivity: if |A| > |B|, then f cannot be injective, as some element in B would have multiple preimages. Conversely, to affirm injectivity positively in finite cases, one may verify the contrapositive across all pairs with x \neq y or use the fact that injectivity holds if no collisions occur under the mapping.

Extensions and Generalizations

In Linear Algebra

In linear algebra, a T: [V](/page/V.) \to W between spaces is injective its is trivial, that is, \ker(T) = \{ \mathbf{0} \}. This condition means that the only in V mapped to the zero in W is the zero itself, ensuring that distinct vectors in V are mapped to distinct vectors in W. The rank-nullity theorem provides a dimensional perspective: for finite-dimensional vector spaces, \dim(V) = \dim(\ker(T)) + \dim(\im(T)). If T is injective, then \dim(\ker(T)) = 0, so \dim(V) = \dim(\im(T)) \leq \dim(W). This implies that injective linear maps exist only when the dimension of the does not exceed that of the , preserving or reducing dimensionality without collapse. In matrix terms, a T: \mathbb{R}^n \to \mathbb{R}^m is represented by an m \times n A, and T is if and only if A has full column , meaning \rank(A) = n. By the equality of row and column ranks, this requires the columns of A to be linearly independent. If m < n, full column rank is impossible, so no such injective map exists. For instance, the n \times n identity matrix I_n has full column rank n, representing an injective map from \mathbb{R}^n to \mathbb{R}^n, as its kernel is trivial and the rank-nullity theorem confirms \dim(\mathbb{R}^n) = 0 + n. In contrast, a singular matrix like \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} has rank 1 < 2, a non-trivial kernel spanned by (0,1)^T, and thus is not injective.

In Category Theory

In category theory, the notion of an injective function is generalized to that of a monomorphism, which captures the essential property of left-cancellability in an abstract setting. Specifically, a morphism f: A \to B in a category \mathcal{C} is a monomorphism, denoted \mono, if for every object C in \mathcal{C} and every pair of morphisms g, h: C \to A, the equality f \circ g = f \circ h implies g = h. This definition abstracts the idea that f does not identify distinct elements "upstream" in the category. In the category of sets, \Set, monomorphisms coincide precisely with injective functions, as the left-cancellability condition reduces to the standard set-theoretic notion of distinct elements mapping to distinct images. Similarly, in the category of groups, \Grp, a group homomorphism is a monomorphism if and only if it is injective as a map of underlying sets; for instance, the inclusion of a subgroup into a group is always a monomorphism. However, this equivalence does not hold in all categories: in the category of divisible abelian groups, \DivAb, the quotient homomorphism \pi: \mathbb{Q} \to \mathbb{Q}/\mathbb{Z} sending q \mapsto q + \mathbb{Z} is a monomorphism, despite not being injective on underlying sets, since integers map to the zero class. An important characterization of monomorphisms uses pullbacks: a morphism f: A \to B is a monomorphism if and only if the canonical diagonal morphism \Delta: A \to A \times_B A, defined by \Delta(a) = (a, a) where the pullback A \times_B A is taken along f and the identity on B, is an isomorphism. This equates the "fiber product" over f with the domain itself, reflecting that f identifies no distinct points. In the category of topological spaces, \Top, monomorphisms are the injective continuous maps, but in subcategories such as pointed connected locally path-connected spaces with pointed continuous maps, nontrivial covering maps (e.g., the n-fold cover S^1 \to S^1, z \mapsto z^n for n > 1) are monomorphisms despite failing to be injective on points, due to unique lifting properties.