Injective function

Function that preserves distinctness

"Injective" redirects here. For other uses, see Injective module and Injective object.

Function

x ↦ f (x)
History of the function concept
Examples of domains and codomains

* X {\displaystyle X} → B {\displaystyle \mathbb {B} } , B {\displaystyle \mathbb {B} } → X {\displaystyle X} , B n {\displaystyle \mathbb {B} ^{n}} → X {\displaystyle X}
* X {\displaystyle X} → Z {\displaystyle \mathbb {Z} } , Z {\displaystyle \mathbb {Z} } → X {\displaystyle X}
* X {\displaystyle X} → R {\displaystyle \mathbb {R} } , R {\displaystyle \mathbb {R} } → X {\displaystyle X} , R n {\displaystyle \mathbb {R} ^{n}} → X {\displaystyle X}
* X {\displaystyle X} → C {\displaystyle \mathbb {C} } , C {\displaystyle \mathbb {C} } → X {\displaystyle X} , C n {\displaystyle \mathbb {C} ^{n}} → X {\displaystyle X}

Classes/properties

* Constant
* Identity
* Linear
* Polynomial
* Rational
* Algebraic
* Analytic
* Smooth
* Continuous
* Measurable
* Injective
* Surjective
* Bijective

Constructions

* Restriction
* Composition
* λ
* Inverse

Generalizations

* Partial
* Multivalued
* Implicit
* Space

* v
* t
* e

In mathematics, an injective function (also known as injection, or one-to-one function[1] ) is a function f that maps distinct elements of its domain to distinct elements; that is, x1 ≠ x2 implies f(x1) ≠ f(x2). (Equivalently, f(x1) = f(x2) implies x1 = x2 in the equivalent contrapositive statement.) In other words, every element of the function's codomain is the image of at most one element of its domain.[2] The term one-to-one function must not be confused with 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 injective homomorphism is also called a monomorphism. However, in the more general context of category theory, the definition of a monomorphism differs from that of an injective homomorphism.[3] This is thus a theorem that they are equivalent for algebraic structures; see Homomorphism § Monomorphism for more details.

A function  f {\displaystyle f} that is not injective is sometimes called many-to-one.[2]

## Definition[edit]

An injective function, which is not also surjective

Further information on notation: Function (mathematics) § Notation

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

Symbolically,

∀ a , b ∈ X , f ( a ) = f ( b ) ⇒ a = b , {\displaystyle \forall a,b\in X,\;\;f(a)=f(b)\Rightarrow a=b,}

which is logically equivalent to the contrapositive,[4]

∀ a , b ∈ X , a ≠ b ⇒ f ( a ) ≠ f ( b ) . {\displaystyle \forall a,b\in X,\;\;a\neq b\Rightarrow f(a)\neq f(b).}

## Examples[edit]

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

* For any set  X {\displaystyle X} and any subset  S ⊆ X , {\displaystyle S\subseteq X,} the inclusion map S -> X {\displaystyle S\to X} (which sends any element  s ∈ S {\displaystyle s\in S} to itself) is injective. In particular, the identity function X -> X {\displaystyle 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 -> R {\displaystyle f:\mathbb {R} \to \mathbb {R} } defined by  f ( x ) = 2 x + 1 {\displaystyle f(x)=2x+1} is injective.
* The function  g : R -> R {\displaystyle g:\mathbb {R} \to \mathbb {R} } defined by  g ( x ) = x 2 {\displaystyle g(x)=x^{2}} is not injective, because (for example)  g ( 1 ) = 1 = g ( − 1 ) . {\displaystyle g(1)=1=g(-1).} However, if  g {\displaystyle g} is redefined so that its domain is the non-negative real numbers [0,+∞), then  g {\displaystyle g} is injective.
* The exponential function exp : R -> R {\displaystyle \exp :\mathbb {R} \to \mathbb {R} } defined by  exp ⁡ ( x ) = e x {\displaystyle \exp(x)=e^{x}} is injective (but not surjective, as no real value maps to a negative number).
* The natural logarithm function  ln : ( 0 , ∞ ) -> R {\displaystyle \ln :(0,\infty )\to \mathbb {R} } defined by  x ↦ ln ⁡ x {\displaystyle x\mapsto \ln x} is injective.
* The function  g : R -> R {\displaystyle g:\mathbb {R} \to \mathbb {R} } defined by  g ( x ) = x n − x {\displaystyle g(x)=x^{n}-x} is not injective, since, for example,  g ( 0 ) = g ( 1 ) = 0. {\displaystyle g(0)=g(1)=0.}

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

## Injections can be undone[edit]

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

Conversely, every injection  f {\displaystyle f} with a non-empty domain has a left inverse  g {\displaystyle g} . It can be defined by choosing an element  a {\displaystyle a} in the domain of  f {\displaystyle f} and setting  g ( y ) {\displaystyle g(y)} to the unique element of the pre-image  f − 1 [ y ] {\displaystyle f^{-1}[y]} (if it is non-empty) or to  a {\displaystyle a} (otherwise).[5]

The left inverse  g {\displaystyle g} is not necessarily an inverse of  f , {\displaystyle f,} because the composition in the other order,  f ∘ g , {\displaystyle f\circ g,} may differ from the identity on  Y . {\displaystyle 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[edit]

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

More generally, injective partial functions are called partial bijections.

## Other properties[edit]

See also: List of set identities and relations § Functions and sets

The composition of two injective functions is injective.

* If  f {\displaystyle f} and  g {\displaystyle g} are both injective then  f ∘ g {\displaystyle f\circ g} is injective.
* If  g ∘ f {\displaystyle g\circ f} is injective, then  f {\displaystyle f} is injective (but  g {\displaystyle g} need not be).
* f : X -> Y {\displaystyle f:X\to Y} is injective if and only if, given any functions  g , {\displaystyle g,} h : W -> X {\displaystyle h:W\to X} whenever  f ∘ g = f ∘ h , {\displaystyle f\circ g=f\circ h,} then  g = h . {\displaystyle g=h.} In other words, injective functions are precisely the monomorphisms in the category Set of sets.
* If  f : X -> Y {\displaystyle f:X\to Y} is injective and  A {\displaystyle A} is a subset of  X , {\displaystyle X,} then  f − 1 ( f ( A ) ) = A . {\displaystyle f^{-1}(f(A))=A.} Thus,  A {\displaystyle A} can be recovered from its image f ( A ) . {\displaystyle f(A).}
* If  f : X -> Y {\displaystyle f:X\to Y} is injective and  A {\displaystyle A} and  B {\displaystyle B} are both subsets of  X , {\displaystyle X,} then  f ( A ∩ B ) = f ( A ) ∩ f ( B ) . {\displaystyle f(A\cap B)=f(A)\cap f(B).}
* Every function  h : W -> Y {\displaystyle h:W\to Y} can be decomposed as  h = f ∘ g {\displaystyle h=f\circ g} for a suitable injection  f {\displaystyle f} and surjection  g . {\displaystyle g.} This decomposition is unique up to isomorphism, and  f {\displaystyle f} may be thought of as the inclusion function of the range  h ( W ) {\displaystyle h(W)} of  h {\displaystyle h} as a subset of the codomain  Y {\displaystyle Y} of  h . {\displaystyle h.}
* If  f : X -> Y {\displaystyle f:X\to Y} is an injective function, then  Y {\displaystyle Y} has at least as many elements as  X , {\displaystyle X,} in the sense of cardinal numbers. In particular, if, in addition, there is an injection from  Y {\displaystyle Y} to  X , {\displaystyle X,} then  X {\displaystyle X} and  Y {\displaystyle Y} have the same cardinal number. (This is known as the Cantor–Bernstein–Schroeder theorem.)
* If both  X {\displaystyle X} and  Y {\displaystyle Y} are finite with the same number of elements, then  f : X -> Y {\displaystyle f:X\to Y} is injective if and only if  f {\displaystyle f} is surjective (in which case  f {\displaystyle 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 {\displaystyle f} is injective can be decided by only considering the graph (and not the codomain) of  f . {\displaystyle f.}

## Proving that functions are injective[edit]

A proof that a function  f {\displaystyle 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 ) , {\displaystyle f(x)=f(y),} then  x = y . {\displaystyle x=y.} [6]

Here is an example:

f ( x ) = 2 x + 3 {\displaystyle f(x)=2x+3}

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

There are multiple other methods of proving that a function is injective. For example, in calculus if  f {\displaystyle 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 {\displaystyle f} is a linear transformation it is sufficient to show that the kernel of  f {\displaystyle f} contains only the zero vector. If  f {\displaystyle 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 {\displaystyle f} of a real variable  x {\displaystyle x} is the horizontal line test. If every horizontal line intersects the curve of  f ( x ) {\displaystyle f(x)} in at most one point, then  f {\displaystyle f} is injective or one-to-one.

## Gallery[edit]

* An injective non-surjective function (injection, not a bijection)

* An injective surjective function (bijection)

* A non-injective surjective function (surjection, not a bijection)

* A non-injective non-surjective function (also not a bijection)

* Not an injective function. Here  X 1 {\displaystyle X_{1}} and  X 2 {\displaystyle X_{2}} are subsets of  X , Y 1 {\displaystyle X,Y_{1}} and  Y 2 {\displaystyle Y_{2}} are subsets of  Y {\displaystyle 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 more than one x {\displaystyle x} in  X {\displaystyle X} to map to the same y {\displaystyle y} in  Y . {\displaystyle Y.}

* Making functions injective. The previous function  f : X -> Y {\displaystyle f:X\to Y} can be reduced to one or more injective functions (say)  f : X 1 -> Y 1 {\displaystyle f:X_{1}\to Y_{1}} and  f : X 2 -> Y 2 , {\displaystyle 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 {\displaystyle f} has not changed – only the domain and range.  X 1 {\displaystyle X_{1}} and  X 2 {\displaystyle X_{2}} are subsets of  X , Y 1 {\displaystyle X,Y_{1}} and  Y 2 {\displaystyle Y_{2}} are subsets of  Y {\displaystyle 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 {\displaystyle x} in  X {\displaystyle X} maps to one  y {\displaystyle y} in  Y . {\displaystyle Y.}

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

## See also[edit]

* Bijection, injection and surjection – Properties of mathematical functions
* Injective metric space – Type of metric space
* Monotonic function – Order-preserving mathematical function
* Univalent function – mathematical conceptPages displaying wikidata descriptions as a fallback

## Notes[edit]

1. ^ Sometimes one-one function, in Indian mathematical education. "Chapter 1:Relations and functions" (PDF).
2. ^ a b c "Injective, Surjective and Bijective". www.mathsisfun.com. Retrieved 2019-12-07.
3. ^ "Section 7.3 (00V5): Injective and surjective maps of presheaves—The Stacks project". stacks.math.columbia.edu. Retrieved 2019-12-07.
4. ^ Farlow, S. J. "Injections, Surjections, and Bijections" (PDF). math.umaine.edu. Retrieved 2019-12-06.
5. ^ 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 {\displaystyle 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 } -> R {\displaystyle \\{0,1\\}\to \mathbb {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}.
6. ^ Williams, Peter. "Proving Functions One-to-One". Archived from the original on 4 June 2017.

## References[edit]

* Bartle, Robert G. (1976), The Elements of Real Analysis (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-05464-1, p. 17 ff.
* Halmos, Paul R. (1974), Naive Set Theory, New York: Springer, ISBN 978-0-387-90092-6, p. 38 ff.

## External links[edit]

Wikimedia Commons has media related to Injectivity.

Look up injective in Wiktionary, the free dictionary.

* Earliest Uses of Some of the Words of Mathematics: entry on Injection, Surjection and Bijection has the history of Injection and related terms.
* Khan Academy – Surjective (onto) and Injective (one-to-one) functions: Introduction to surjective and injective functions

* v
* t
* e

Mathematical logic

General|

* Axiom
* list
* Cardinality
* First-order logic
* Formal proof
* Formal semantics
* Foundations of mathematics
* Information theory
* Lemma
* Logical consequence
* Model
* Theorem
* Theory
* Type theory

Theorems (list)
& paradoxes|

* Gödel's completeness and incompleteness theorems
* Tarski's undefinability
* Banach–Tarski paradox
* Cantor's theorem, paradox and diagonal argument
* Compactness
* Halting problem
* Lindström's
* Löwenheim–Skolem
* Russell's paradox

Logics|

| Traditional|

* Classical logic
* Logical truth
* Tautology
* Proposition
* Inference
* Logical equivalence
* Consistency
* Equiconsistency
* Argument
* Soundness
* Validity
* Syllogism
* Square of opposition
* Venn diagram

|

Propositional|

* Boolean algebra
* Boolean functions
* Logical connectives
* Propositional calculus
* Propositional formula
* Truth tables
* Many-valued logic
* 3
* finite
* ∞

Predicate|

* First-order
* list
* Second-order
* Monadic
* Higher-order
* Free
* Quantifiers
* Predicate
* Monadic predicate calculus

Set theory|

* Set
* hereditary
* Class
* (Ur-)Element
* Ordinal number
* Extensionality
* Forcing
* Relation
* equivalence
* partition
* Set operations:
* intersection
* union
* complement
* Cartesian product
* power set
* identities

Types of sets|

* Countable
* Uncountable
* Empty
* Inhabited
* Singleton
* Finite
* Infinite
* Transitive
* Ultrafilter
* Recursive
* Fuzzy
* Universal
* Universe
* constructible
* Grothendieck
* Von Neumann

Maps & cardinality|

* Function/Map
* domain
* codomain
* image
* In/Sur/Bi-jection
* Schröder–Bernstein theorem
* Isomorphism
* Gödel numbering
* Enumeration
* Large cardinal
* inaccessible
* Aleph number
* Operation
* binary

Set theories|

* Zermelo–Fraenkel
* axiom of choice
* continuum hypothesis
* General
* Kripke–Platek
* Morse–Kelley
* Naive
* New Foundations
* Tarski–Grothendieck
* Von Neumann–Bernays–Gödel
* Ackermann
* Constructive

Formal systems (list),
language & syntax|

* Alphabet
* Arity
* Automata
* Axiom schema
* Expression
* ground
* Extension
* by definition
* conservative
* Relation
* Formation rule
* Grammar
* Formula
* atomic
* closed
* ground
* open
* Free/bound variable
* Language
* Metalanguage
* Logical connective
* ¬
* ∨
* ∧
* →
* ↔
* =
* Predicate
* functional
* variable
* propositional variable
* Proof
* Quantifier
* ∃
* !
* ∀
* rank
* Sentence
* atomic
* spectrum
* Signature
* String
* Substitution
* Symbol
* function
* logical/constant
* non-logical
* variable
* Term
* Theory
* list

Example axiomatic
systems (list)|

* of arithmetic:
* Peano
* second-order
* elementary function
* primitive recursive
* Robinson
* Skolem
* of the real numbers
* Tarski's axiomatization
* of Boolean algebras
* canonical
* minimal axioms
* of geometry:
* Euclidean:
* Elements
* Hilbert's
* Tarski's
* non-Euclidean

* Principia Mathematica

Proof theory|

* Formal proof
* Natural deduction
* Logical consequence
* Rule of inference
* Sequent calculus
* Theorem
* Systems
* axiomatic
* deductive
* Hilbert
* list
* Complete theory
* Independence (from ZFC)
* Proof of impossibility
* Ordinal analysis
* Reverse mathematics
* Self-verifying theories

Model theory|

* Interpretation
* function
* of models
* Model
* equivalence
* finite
* saturated
* spectrum
* submodel
* Non-standard model
* of arithmetic
* Diagram
* elementary
* Categorical theory
* Model complete theory
* Satisfiability
* Semantics of logic
* Strength
* Theories of truth
* semantic
* Tarski's
* Kripke's
* T-schema
* Transfer principle
* Truth predicate
* Truth value
* Type
* Ultraproduct
* Validity

Computability theory|

* Church encoding
* Church–Turing thesis
* Computably enumerable
* Computable function
* Computable set
* Decision problem
* decidable
* undecidable
* P
* NP
* P versus NP problem
* Kolmogorov complexity
* Lambda calculus
* Primitive recursive function
* Recursion
* Recursive set
* Turing machine
* Type theory

Related|

* Abstract logic
* Automated theorem proving
* Category theory
* Concrete/Abstract category
* Category of sets
* History of logic
* History of mathematical logic
* timeline
* Logicism
* Mathematical object
* Philosophy of mathematics
* Supertask

Mathematics portal
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template