Injective function

From TCS Wiki
Revision as of 06:37, 8 October 2016 by imported>Auntof6 (use standard simple headings and/or general cleanup, typos fixed: 1930's → 1930s using AWB)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
File:Gen injection not surjection.svg
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 : AB with the following property. For every element b in the codomain B there is maximum one element a in the domain A such that f(a)=b.[1][2]

The term injection and the related terms surjection and bijection were introduced by Nicholas Bourbaki.[3] 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 function. However, a 1-1 correspondence is a bijective function (both injective and surjective). This is confusing, so be careful.[4]

File:Gen not surjection not injection.svg
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:

[math]\displaystyle{ f:A \rightarrow B }[/math]  is an injective function if  [math]\displaystyle{ \forall a_1, \,a_2 , \in A, \,\,\,\, a_1 \ne a_2 \,\, \Rightarrow \,\, f(a_1) \ne f(a_2) }[/math]  or equivalently
[math]\displaystyle{ f:A \rightarrow B }[/math]  is an injective function if  [math]\displaystyle{ \forall a_1, \,a_2 , \in A, \,\,\,\,f(a_1)=f(a_2) \,\, \Rightarrow \,\, a_1=a_2 }[/math]

The element  [math]\displaystyle{ a }[/math]  is called a pre-image of the element  [math]\displaystyle{ b }[/math]  if  [math]\displaystyle{ f(a)=b }[/math] . 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. We write #A=4.[5]

  • If the cardinality of the codomain is less than the cardinality of the domain, the function cannot be an injection. (For example, there is no way 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 an 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: Template:Nowrap beginf(x)=x3Template:Nowrap end is an injection. However, the polynomial function of third degree: Template:Nowrap beginf(x)=x3 –3xTemplate:Nowrap end is not an injection.

Discussion 1: Any horizontal line intersects the graph of Template:Nowrap beginf(x)=x3Template:Nowrap end 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 Template:Nowrap beginf(x) = x2Template:Nowrap end 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

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

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

Example: The exponential function Template:Nowrap beginf(x) = 10xTemplate:Nowrap end 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.

[math]\displaystyle{ a^{x_0}=a^{x_1} \,\, \Rightarrow \,\, x_0=x_1, \, a\gt 0 }[/math] 
Example:  [math]\displaystyle{ 100=10^{x-3} \,\, \Rightarrow \,\, 2=x-3 \,\, \Rightarrow \,\, x=5 }[/math] 
Injection: no horizontal line intersects more than one point of the graph
File:Line explicit ex.svg
Injection. f(x):ℝ→ℝ (and surjection)
File:Xto3.svg
Injection. f(x):ℝ→ℝ (and surjection)
File:Xto3minus3x.svg
Not an injection. f(x):ℝ→ℝ (is surjection)
File:Xto2.svg
Not an injection. f(x):ℝ→ℝ (not surjection)
File:10tox.svg
Injection. f(x):ℝ→ℝ (not surjection)
File:Logx.svg
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=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

References

Template:Reflist

Other websites