Injective function

Injection. 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).

Not 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:

$f:A\rightarrow B$  is an injective function if  $\forall a_{1},\,a_{2},\in A,\,\,\,\,a_{1}\neq a_{2}\,\,\Rightarrow \,\,f(a_{1})\neq f(a_{2})$  or equivalently

$f:A\rightarrow B$  is an injective function if  $\forall a_{1},\,a_{2},\in A,\,\,\,\,f(a_{1})=f(a_{2})\,\,\Rightarrow \,\,a_{1}=a_{2}$

The element $a$ is called a pre-image of the element $b$ if $f(a)=b$ . 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(x_o)=f(x₁) means x_o=x₁.

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 x_o and x₁ be real numbers. Suppose the line maps these two x-values to the same y-value. This means a·x_o+b=a·x₁+b. Subtract b from both sides. We get a·x_o=a·x₁. Now divide both sides by a (remember a≠0). We get x_o=x₁. 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)=x³ is an injection. However, the polynomial function of third degree: f(x)=x³ –3x is not an injection.

Discussion 1: Any horizontal line intersects the graph of

f(x)=x³ 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) = x² 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

$f_{/[0,+\infty )}(x):[0,+\infty )\rightarrow \mathbf {R}$  where  $f_{/[0,+\infty )}(x)=x^{2}$

This function is now an injection. (See also restriction of a function.)

Example: The exponential function f(x) = 10^x 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.

$a^{x_{0}}=a^{x_{1}}\,\,\Rightarrow \,\,x_{0}=x_{1},\,a>0$ 

Example:  $100=10^{x-3}\,\,\Rightarrow \,\,2=x-3\,\,\Rightarrow \,\,x=5$ 

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

Other examples

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

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

Other websites

• "Injective, Surjective, Bijective". Mathsisfun. 2013. Retrieved 2013-12-01. interactive quiz
• "Injectivity, Surjectivity". Wolfram alpha. Archived from the original on 2013-11-25. Retrieved 2013-12-01. interactive