Injective function

Image:Gen injection not surjection.svgInjection. Maximum one arrow to each element in the codomain B (from an element in domain A). 

In mathematics, a injective function is a function f : A → B with the following property: for every element b in the codomain B, there is at most one element a in the domain A such that f(a)=b, or equivalently, distinct elements in the domain map to distinct elements in the codomain.

The term injection and the related terms surjection and bijection were introduced by Nicholas Bourbaki. In the 1930s, he and a group of other mathematicians published a series of books on modern advanced mathematics.

An injective function is often called a 1-1 (read "one-to-one") function. However, this is to be distinguished from a 1-1 correspondence, which is a bijective function (both injective and surjective).

Image:Gen not surjection not injection.svgNot an injection. Two elements {X} and {Y} in the domain A are mapped to the same element {1} in the codomain B. 
Basic properties
Formally:
  is an injective function if     or equivalently
  is an injective function if  
The element  is called a pre-image of the element  if  . Injections have one or none pre-images for every element b in B.

Cardinality
Cardinality is the number of elements in a set. The cardinality of A={X,Y,Z,W} is 4. This is written as #A=4. 

If the cardinality of the codomain is less than the cardinality of the domain, then the function cannot be an injection. For example, there is no injection from 6 elements to 5 elements, since it is impossible to map 6 elements to 5 elements without a duplicate.

Examples 
Elementary functions
Let f(x):ℝ→ℝ be a real-valued function y=f(x) of a real-valued argument x. (This means both the input and output are real numbers.)
Graphic meaning: The function f is an injection if every horizontal line intersects the graph of f in at most one point.
Algebraic meaning: The function f is an injection if f(xo)=f(x1) means xo=x1.

Example: The linear function of a slanted line is 1-1. That is, y=ax+b where a≠0 is an injection. (It is also a surjection and thus a bijection.)
Proof: Let xo and x1 be real numbers. Suppose the line maps these two x-values to the same y-value.  This means a·xo+b=a·x1+b. Subtract b from both sides. We get a·xo=a·x1. Now divide both sides by a (remember a≠0).  We get xo=x1. So we have proved the formal definition and the function y=ax+b where a≠0 is an injection.

Example: The polynomial function of third degree: f(x)=x3 is an injection. However, the polynomial function of third degree: f(x)=x3 –3x is not an injection.
Discussion 1: Any horizontal line intersects the graph of f(x)=x3 exactly once. (Also, it is a surjection.)
Discussion 2. Any horizontal line between y=-2 and y=2 intersects the graph in three points so this function is not an injection. (However, it is a surjection.)

Example: The quadratic function f(x) = x2 is not an injection. 
Discussion: Any horizontal line y=c where c>0 intersects the graph in two points. So this function is not an injection. (Also, it is not a surjection.)

Note: One can make a non-injective function into an injective function by eliminating part of the domain. We call this restricting the domain. For example, restrict the domain of f(x)=x² to non-negative numbers (positive numbers and zero). Define 
  where  
This function is now an injection. (See also restriction of a function.)

Example: The exponential function f(x) = 10x is an injection. (However, it is not a surjection.)
Discussion: Any horizontal line intersects the graph in at most one point. The horizontal lines y=c where c>0 cut it in exactly one point. The horizontal lines y=c where c≤0 do not cut the graph at any point.

Note: The fact that an exponential function is injective can be used in calculations. 

Example:   

 Injection: no horizontal line intersects more than one point of the graph130px Injection. f(x):ℝ→ℝ (and surjection)220px Injection. f(x):ℝ→ℝ (and surjection)220px Not an injection. f(x):ℝ→ℝ (is surjection)220px Not an injection. f(x):ℝ→ℝ (not surjection)220pxInjection. f(x):ℝ→ℝ (not surjection)220pxInjection. f(x):(0,+∞)→ℝ (and surjection)

Other examples 

Example: The logarithmic function base 10  f(x):(0,+∞)→ℝ defined by f(x)=log(x) or y=log10(x) is an injection (and a surjection). (This is the inverse function of 10x.)

Example: The function f:ℕ→ℕ that maps every natural number n to 2n is an injection. Every even number has exactly one pre-image. Every odd number has no pre-image.

Related pages
Function (mathematics)
Surjective function
Bijective function

References

Other websites
  interactive quiz
  interactive

Category:Functions and mappings
Category:Algebra