Injective function

{{Redirect|Injective|other uses|Injective module|and|Injective object}}

In mathematics, an injective function (also known as injection, or one-to-one functionSometimes one-one function, in Indian mathematical education. {{Cite web |title=Chapter 1:Relations and functions |url=https://ncert.nic.in/ncerts/l/lemh101.pdf |via=NCERT |url-status=live |archive-url=https://web.archive.org/web/20231226194119/https://ncert.nic.in/ncerts/l/lemh101.pdf |archive-date= Dec 26, 2023 }} ) is a function {{math|f}} that maps distinct elements of its domain to distinct elements of its codomain; that is, {{math|1=x₁ ≠ x₂}} implies {{math|f(x₁) {{≠}} f(x₂)}} (equivalently by contraposition, {{math|f(x₁) {{=}} f(x₂)}} implies {{math|1=x₁ = x₂}}). In other words, every element of the function's codomain is the image of {{em|at most}} one element of its domain.{{Cite web|url=https://www.mathsisfun.com/sets/injective-surjective-bijective.html|title=Injective, Surjective and Bijective|website=Math is Fun |access-date=2019-12-07}} (There may be some elements in the codomain that are not mapped from elements in the domain.) The term {{em|one-to-one function}} must not be confused with {{em|one-to-one correspondence}} that refers to bijective functions, which are functions such that each element in the codomain is an image of exactly one element in the domain.

A homomorphism between algebraic structures is a function that is compatible with the operations of the structures. For all common algebraic structures, and, in particular for vector spaces, an {{em|injective homomorphism}} is also called a {{em|monomorphism}}. However, in the more general context of category theory, the definition of a monomorphism differs from that of an injective homomorphism.{{Cite web|url=https://stacks.math.columbia.edu/tag/00V5|title=Section 7.3 (00V5): Injective and surjective maps of presheaves |website=The Stacks project |access-date=2019-12-07}} This is thus a theorem that they are equivalent for algebraic structures; see {{slink|Homomorphism|Monomorphism}} for more details.

A function $f$ that is not injective is sometimes called many-to-one.

Definition

file:Injection.svg.]]

Let $f$ be a function whose domain is a set $X.$ The function $f$ is said to be injective provided that for all $a$ and $b$ in $X,$ if $f(a) = f(b),$ then $a = b$ ; that is, $f(a) = f(b)$ implies $a=b.$ Equivalently, if $a \neq b,$ then $f(a) \neq f(b)$ in the contrapositive statement.

Symbolically, $\forall a,b \in X, \;\; f(a)=f(b) \Rightarrow a=b,$

which is logically equivalent to the contrapositive,{{Cite web|url=http://www.math.umaine.edu/~farlow/sec42.pdf|title=Section 4.2 Injections, Surjections, and Bijections |last=Farlow|first=S. J.|author-link= Stanley Farlow |website=Mathematics & Statistics - University of Maine |access-date=2019-12-06 |url-status=dead |archive-url= https://web.archive.org/web/20191207035302/http://www.math.umaine.edu/~farlow/sec42.pdf |archive-date= Dec 7, 2019 }} $\forall a, b \in X, \;\; a \neq b \Rightarrow f(a) \neq f(b).$ An injective function (or, more generally, a monomorphism) is often denoted by using the specialized arrows ↣ or ↪ (for example, $f:A\rightarrowtail B$ or $f:A\hookrightarrow B$ ), although some authors specifically reserve ↪ for an inclusion map.{{Cite web |title=What are usual notations for surjective, injective and bijective functions? |url=https://math.stackexchange.com/questions/46678/what-are-usual-notations-for-surjective-injective-and-bijective-functions |access-date=2024-11-24 |website=Mathematics Stack Exchange |language=en}}

Examples

For visual examples, readers are directed to the gallery section.

For any set $X$ and any subset $S \subseteq X,$ the inclusion map $S \to X$ (which sends any element $s \in S$ to itself) is injective. In particular, the identity function $X \to X$ is always injective (and in fact bijective).
If the domain of a function is the empty set, then the function is the empty function, which is injective.
If the domain of a function has one element (that is, it is a singleton set), then the function is always injective.
The function $f : \R \to \R$ defined by $f(x) = 2 x + 1$ is injective.
The function $g : \R \to \R$ defined by $g(x) = x^2$ is {{em|not}} injective, because (for example) $g(1) = 1 = g(-1).$ However, if $g$ is redefined so that its domain is the non-negative real numbers [0,+∞), then $g$ is injective.
The exponential function $\exp : \R \to \R$ defined by $\exp(x) = e^x$ is injective (but not surjective, as no real value maps to a negative number).
The natural logarithm function $\ln : (0, \infty) \to \R$ defined by $x \mapsto \ln x$ is injective.
The function $g : \R \to \R$ defined by $g(x) = x^n - x$ is not injective, since, for example, $g(0) = g(1) = 0.$

More generally, when $X$ and $Y$ are both the real line $\R,$ then an injective function $f : \R \to \R$ is one whose graph is never intersected by any horizontal line more than once. This principle is referred to as the {{em|horizontal line test}}.

Injections can be undone

Functions with left inverses are always injections. That is, given $f : X \to Y,$ if there is a function $g : Y \to X$ such that for every $x \in X$ , $g(f(x)) = x$ , then $f$ is injective. In this case, $g$ is called a retraction of $f.$ Conversely, $f$ is called a section of $g.$

Conversely, every injection $f$ with a non-empty domain has a left inverse $g$ . It can be defined by choosing an element $a$ in the domain of $f$ and setting $g(y)$ to the unique element of the pre-image $f^{-1}[y]$ (if it is non-empty) or to $a$ (otherwise).{{refn|Unlike the corresponding statement that every surjective function has a right inverse, this does not require the axiom of choice, as the existence of $a$ is implied by the non-emptiness of the domain. However, this statement may fail in less conventional mathematics such as constructive mathematics. In constructive mathematics, the inclusion $\{ 0, 1 \} \to \R$ of the two-element set in the reals cannot have a left inverse, as it would violate indecomposability, by giving a retraction of the real line to the set {0,1}.}}

The left inverse $g$ is not necessarily an inverse of $f,$ because the composition in the other order, $f \circ g,$ may differ from the identity on $Y.$ In other words, an injective function can be "reversed" by a left inverse, but is not necessarily invertible, which requires that the function is bijective.

Injections may be made invertible

In fact, to turn an injective function $f : X \to Y$ into a bijective (hence invertible) function, it suffices to replace its codomain $Y$ by its actual image $J = f(X).$ That is, let $g : X \to J$ such that $g(x) = f(x)$ for all $x \in X$ ; then $g$ is bijective. Indeed, $f$ can be factored as $\operatorname{In}_{J,Y} \circ g,$ where $\operatorname{In}_{J,Y}$ is the inclusion function from $J$ into $Y.$

More generally, injective partial functions are called partial bijections.

Other properties

{{See also|List of set identities and relations#Functions and sets}}

Image:Injective composition2.svg

If $f$ and $g$ are both injective then $f \circ g$ is injective.
If $g \circ f$ is injective, then $f$ is injective (but $g$ need not be).
$f : X \to Y$ is injective if and only if, given any functions $g,$ $h : W \to X$ whenever $f \circ g = f \circ h,$ then $g = h.$ In other words, injective functions are precisely the monomorphisms in the category Set of sets.
If $f : X \to Y$ is injective and $A$ is a subset of $X,$ then $f^{-1}(f(A)) = A.$ Thus, $A$ can be recovered from its image $f(A).$
If $f : X \to Y$ is injective and $A$ and $B$ are both subsets of $X,$ then $f(A \cap B) = f(A) \cap f(B).$
Every function $h : W \to Y$ can be decomposed as $h = f \circ g$ for a suitable injection $f$ and surjection $g.$ This decomposition is unique up to isomorphism, and $f$ may be thought of as the inclusion function of the range $h(W)$ of $h$ as a subset of the codomain $Y$ of $h.$
If $f : X \to Y$ is an injective function, then $Y$ has at least as many elements as $X,$ in the sense of cardinal numbers. In particular, if, in addition, there is an injection from $Y$ to $X,$ then $X$ and $Y$ have the same cardinal number. (This is known as the Cantor–Bernstein–Schroeder theorem.)
If both $X$ and $Y$ are finite with the same number of elements, then $f : X \to Y$ is injective if and only if $f$ is surjective (in which case $f$ is bijective).
An injective function which is a homomorphism between two algebraic structures is an embedding.
Unlike surjectivity, which is a relation between the graph of a function and its codomain, injectivity is a property of the graph of the function alone; that is, whether a function $f$ is injective can be decided by only considering the graph (and not the codomain) of $f.$

Proving that functions are injective

A proof that a function $f$ is injective depends on how the function is presented and what properties the function holds.

For functions that are given by some formula there is a basic idea.

We use the definition of injectivity, namely that if $f(x) = f(y),$ then $x = y.$ {{cite web|last=Williams|first=Peter|title=Proving Functions One-to-One|url=http://www.math.csusb.edu/notes/proofs/bpf/node4.html |date=Aug 21, 1996 |website=Department of Mathematics at CSU San Bernardino Reference Notes Page |archive-date= 4 June 2017|archive-url=https://web.archive.org/web/20170604162511/http://www.math.csusb.edu/notes/proofs/bpf/node4.html}}

Here is an example:

$f(x) = 2 x + 3$

Proof: Let $f : X \to Y.$ Suppose $f(x) = f(y).$ So $2 x + 3 = 2 y + 3$ implies $2 x = 2 y,$ which implies $x = y.$ Therefore, it follows from the definition that $f$ is injective.

There are multiple other methods of proving that a function is injective. For example, in calculus if $f$ is a differentiable function defined on some interval, then it is sufficient to show that the derivative is always positive or always negative on that interval. In linear algebra, if $f$ is a linear transformation it is sufficient to show that the kernel of $f$ contains only the zero vector. If $f$ is a function with finite domain it is sufficient to look through the list of images of each domain element and check that no image occurs twice on the list.

A graphical approach for a real-valued function $f$ of a real variable $x$ is the horizontal line test. If every horizontal line intersects the curve of $f(x)$ in at most one point, then $f$ is injective or one-to-one.

Gallery

{{Gallery

|perrow=4

|align=center

|Image:Injection.svg|An injective non-surjective function (injection, not a bijection)

|Image:Bijection.svg|An injective surjective function (bijection)

|Image:Surjection.svg|A non-injective surjective function (surjection, not a bijection)

|Image:Not-Injection-Surjection.svg|A non-injective non-surjective function (also not a bijection)

}}

{{Gallery

|perrow=3

|align=center

|Image:Non-injective function1.svg|Not an injective function. Here $X_1$ and $X_2$ are subsets of $X, Y_1$ and $Y_2$ are subsets of $Y$ : for two regions where the function is not injective because more than one domain element can map to a single range element. That is, it is possible for {{em|more than one}} $x$ in $X$ to map to the {{em|same}} $y$ in $Y.$

|Image:Non-injective function2.svg|Making functions injective. The previous function $f : X \to Y$ can be reduced to one or more injective functions (say) $f : X_1 \to Y_1$ and $f : X_2 \to Y_2,$ shown by solid curves (long-dash parts of initial curve are not mapped to anymore). Notice how the rule $f$ has not changed – only the domain and range. $X_1$ and $X_2$ are subsets of $X, Y_1$ and $Y_2$ are subsets of $Y$ : for two regions where the initial function can be made injective so that one domain element can map to a single range element. That is, only one $x$ in $X$ maps to one $y$ in $Y.$

|Image:Injective function.svg|Injective functions. Diagramatic interpretation in the Cartesian plane, defined by the mapping $f : X \to Y,$ where $y = f(x),$ {{nowrap| $X =$ domain of function}}, {{nowrap| $Y =$ range of function}}, and $\operatorname{im}(f)$ denotes image of $f.$ Every one $x$ in $X$ maps to exactly one unique $y$ in $Y.$ The circled parts of the axes represent domain and range sets— in accordance with the standard diagrams above

}}

Notes

References

{{Citation|last1=Bartle|first1=Robert G.|title=The Elements of Real Analysis|publisher=John Wiley & Sons|location=New York|edition=2nd|isbn=978-0-471-05464-1|year=1976}}, p. 17 ff.
{{Citation|last1=Halmos|first1=Paul R.|author1-link=Paul R. Halmos|title=Naive Set Theory|isbn=978-0-387-90092-6|year=1974|publisher=Springer|location=New York}}, p. 38 ff.

External links

[http://jeff560.tripod.com/i.html Earliest Uses of Some of the Words of Mathematics: entry on Injection, Surjection and Bijection has the history of Injection and related terms.]
[http://www.khanacademy.org/math/linear-algebra/v/surjective--onto--and-injective--one-to-one--functions Khan Academy – Surjective (onto) and Injective (one-to-one) functions: Introduction to surjective and injective functions]

Category:Functions and mappings

Category:Basic concepts in set theory

Category:Types of functions