Content deleted Content added
Aimefournier (talk | contribs) m →Injections can be undone: linear ℝ → ℝ² example |
|||
| (30 intermediate revisions by 17 users not shown) | |||
Line 3:
{{Functions}}
In [[mathematics]], an '''injective function''' (also known as '''injection''', or '''one-to-one function'''<ref>Sometimes ''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 }}</ref> ) is a [[function (mathematics)|function]] {{math|''f''}} that maps [[Distinct (mathematics)|distinct]] elements of its ___domain to distinct elements of its codomain; that is, {{math|
A [[homomorphism]] between [[algebraic structure]]s is a function that is compatible with the operations of the structures. For all common algebraic structures, and, in particular for [[vector space]]s, 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.<ref>{{Cite web|url=https://stacks.math.columbia.edu/tag/00V5|title=Section 7.3 (00V5): Injective and surjective maps of
A function <math>f</math> that is not injective is sometimes called many-to-one.<ref name=":0" />
== Definition ==
{{Dark mode invert|[[file:Injection.svg|thumb|An injective function, which is not also [[Surjective function|surjective]]]]}}
{{Further|topic=notation|Function (mathematics)#Notation}}
Let <math>f</math> be a function whose ___domain is a set <math>X.</math> The function <math>f</math> is said to be '''injective''' provided that for all <math>a</math> and <math>b</math> in <math>X,</math> if <math>f(a) = f(b),</math> then <math>a = b</math>; that is, <math>f(a) = f(b)</math> implies <math>a=b.</math> Equivalently, if <math>a \neq b,</math> then <math>f(a) \neq f(b)</math> in the [[Contraposition|contrapositive]] statement.
Symbolically,<math display="block">\forall a,b \in X, \;\; f(a)=f(b) \Rightarrow a=b,</math>
which is logically equivalent to the [[Contraposition|contrapositive]],<ref>{{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=
== Examples ==
''For visual examples, readers are directed to the [[#Gallery|gallery section.]]''
* For any set <math>X</math> and any subset <math>S \subseteq X,</math> the [[inclusion map]] <math>S \to X</math> (which sends any element <math>s \in S</math> to itself) is injective. In particular, the [[identity function]] <math>X \to X</math> is always injective (and in fact bijective).
* If the ___domain of a function is
* If the ___domain of a function has one element (that is, it is a [[singleton set]]), then the function is always injective.
* The function <math>f : \R \to \R</math> defined by <math>f(x) = 2 x + 1</math> is injective.
* The function <math>g : \R \to \R</math> defined by <math>g(x) = x^2</math> is {{em|not}} injective, because (for example) <math>g(1) = 1 = g(-1).</math> However, if <math>g</math> is redefined so that its ___domain is the non-negative real numbers <nowiki>[0,+∞)</nowiki>, then <math>g</math> is injective.
* The [[exponential function]] <math>\exp : \R \to \R</math> defined by <math>\exp(x) = e^x</math> is injective (but not [[Surjective function|surjective]], as no real value maps to a negative number).
* The [[natural logarithm]] function <math>\ln : (0, \infty) \to \R</math> defined by <math>x \mapsto \ln x</math> is injective.
* The function <math>g : \R \to \R</math> defined by <math>g(x) = x^n - x</math> is not injective, since, for example, <math>g(0) = g(1) = 0.</math>
Line 32:
== Injections can be undone ==
Functions with [[Inverse function#Left and right inverses|left inverses]] are always injections. That is, given <math>f : X \to Y,</math> if there is a function <math>g : Y \to X</math> such that for every <math>x \in X</math>, <math>g(f(x)) = x</math>, then <math>f</math> is injective. The proof is that
<math display="block">f(a) = f(b) \rightarrow g(f(a))=g(f(b)) \rightarrow a = b.</math> In this case, <math>g</math> is called a [[Retract (category theory)|retraction]] of <math>f.</math> Conversely, <math>f</math> is called a [[Retract (category theory)|section]] of <math>g.</math> For example: <math>f:\R\rightarrow\R^2,x\mapsto(1,m)^\intercal x</math> is retracted by <math>g:y\mapsto\frac{(1,m)}{1+m^2}y</math>.
Conversely, every injection <math>f</math> with a non-empty ___domain has a left inverse <math>g</math>. It can be defined by choosing an element <math>a</math> in the ___domain of <math>f</math> and setting <math>g(y)</math> to the unique element of the pre-image <math>f^{-1}[y]</math> (if it is non-empty) or to <math>a</math> (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 <math>a</math> 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 <math>\{ 0, 1 \} \to \R</math> of the two-element set in the reals cannot have a left inverse, as it would violate [[Indecomposability (constructive mathematics)|indecomposability]], by giving a [[Retract (category theory)|retraction]] of the real line to the set {0,1}.}}
The left inverse <math>g</math> is not necessarily an [[Inverse function|inverse]] of <math>f,</math> because the composition in the other order, <math>f \circ g,</math> may differ from the identity on <math>Y.</math> In other words, an injective function can be
== Injections may be made invertible ==
In fact, to turn an injective function <math>f : X \to Y</math> into a bijective (hence invertible) function, it suffices to replace its codomain <math>Y</math> by its actual
More generally, injective [[partial function]]s are called [[partial bijection]]s.
Line 46 ⟶ 51:
== Other properties ==
{{See also|List of set identities and relations#Functions and sets}}
{{Dark mode invert|[[Image:Injective composition2.svg|thumb|300px|The composition of two injective functions is injective.]]}}
* If <math>f</math> and <math>g</math> are both injective then <math>f \circ g</math> is injective.
* If <math>g \circ f</math> is injective, then <math>f</math> is injective (but <math>g</math> need not be).
Line 61 ⟶ 66:
A proof that a function <math>f</math> 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 <math>f(x) = f(y),</math> then <math>x = y.</math><ref>{{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}}</ref>▼
▲We use the definition of injectivity, namely that if <math>f(x) = f(y),</math> then <math>x = y.</math><ref>{{cite web|last=Williams|first=Peter|title=Proving Functions One-to-One|url=http://www.math.csusb.edu/notes/proofs/bpf/node4.html|archive-date= 4 June 2017|archive-url=https://web.archive.org/web/20170604162511/http://www.math.csusb.edu/notes/proofs/bpf/node4.html}}</ref>
Here is an example:
Line 75 ⟶ 79:
==Gallery==
{{Gallery
|
|align=center
|Image:Injection.svg|An '''injective''' non-surjective function (injection, not a bijection)
Line 84 ⟶ 88:
{{Gallery
|
|align=center
|Image:Non-injective function2.svg|Making functions injective. The previous function <math>f : X \to Y</math> can be reduced to one or more injective functions (say) <math>f : X_1 \to Y_1</math> and <math>f : X_2 \to Y_2,</math> shown by solid curves (long-dash parts of initial curve are not mapped to anymore). Notice how the rule <math>f</math> has not changed – only the ___domain and range. <math>X_1</math> and <math>X_2</math> are subsets of <math>X, Y_1</math> and <math>Y_2</math> are subsets of <math>Y</math>: 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 <math>x</math> in <math>X</math> maps to one <math>y</math> in <math>Y.</math>▼
|Image:Non-injective function1.svg|Not an injective function. Here <math>X_1</math> and <math>X_2</math> are subsets of <math>X, Y_1</math> and <math>Y_2</math> are subsets of <math>Y</math>: for two regions where the function is not injective because more than one ___domain [[Element (mathematics)|element]] can map to a single range element. That is, it is possible for {{em|more than one}} <math>x</math> in <math>X</math> to map to the {{em|same}} <math>y</math> in <math>Y.</math>
▲|Image:Non-injective function2.svg|Making functions injective. The previous function <math>f : X \to Y</math> can be reduced to one or more injective functions (say) <math>f : X_1 \to Y_1</math> and <math>f : X_2 \to Y_2,</math> shown by solid curves (long-dash parts of initial curve are not mapped to anymore). Notice how the rule <math>f</math> has not changed – only the ___domain and range. <math>X_1</math> and <math>X_2</math> are subsets of <math>X, Y_1</math> and <math>Y_2</math> are subsets of <math>Y</math>: 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 <math>x</math> in <math>X</math> maps to one <math>y</math> in <math>Y.</math>
|Image:Injective function.svg|Injective functions. Diagramatic interpretation in the [[Cartesian plane]], defined by the [[Map (mathematics)|mapping]] <math>f : X \to Y,</math> where <math>y = f(x),</math> {{nowrap|<math>X =</math> ___domain of function}}, {{nowrap|<math>Y = </math> [[range of a function|range of function]]}}, and <math>\operatorname{im}(f)</math> denotes image of <math>f.</math> Every one <math>x</math> in <math>X</math> maps to exactly one unique <math>y</math> in <math>Y.</math> The circled parts of the axes represent ___domain and range sets— in accordance with the standard diagrams above
}}
| |||