Bijective function

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Gen bijection.svg
Bijection. There is exactly one arrow to every element in the codomain B (from an element of the domain A).

In mathematics, a bijective function or bijection is a function f : AB that is both an injection and a surjection. This means: for every element b in the codomain B there is exactly one element a in the domain A such that f(a)=b. Another name for bijection is 1-1 correspondence.[1][2]

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

Gen not surjection not injection.svg
Not a bijection. (It is not a surjection. It is not an injection.)

Basic properties[change | change source]

Formally:

f:A \rightarrow B  is a bijective function if  \forall b \in B  there is a unique  a \in A  such that  f(a)=b \,.

The element b is called the image of the element a.

  • The formal definition means: Every element of the codomain B is the image of exactly one element in the domain A.

The element a is called a pre-image of the element b.

  • The formal definition means: Every element of the codomain B has exactly one pre-image in the domain A.

Note: Surjection means minimum one pre-image. Injection means maximum one pre-image. So bijection means exactly one pre-image.

Cardinality[change | change source]

Cardinality is the number of elements in a set. The cardinality of A={X,Y,Z,W} is 4. We write #A=4.[4]

  • Definition: Two sets A and B have the same cardinality if there is a bijection between the sets. So #A=#B means there is a bijection from A to B.

Bijections and inverse functions[change | change source]

Formally: Let f : AB be a bijection. The inverse function g : BA is defined by if f(a)=b, then g(b)=a. (See also Inverse function.)

  • The inverse function of the inverse function is the original function.[5]
  • A function has an inverse function if and only if it is a bijection.[6][7][8]

Note: The notation for the inverse function of f is confusing. Namely,

 f^{-1}(x)  denotes the inverse function of the function f, but  x^{-1}=\frac{1}{x} denotes the reciprocal value of the number x.

Examples[change | change source]

Elementary functions[change | change source]

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

  • Graphic meaning: The function f is a bijection if every horizontal line intersects the graph of f in exactly one point.
  • Algebraic meaning: The function f is a bijection if for every real number yo we can find at least one real number xo such that yo=f(xo) and if f(xo)=f(x1) means xo=x1 .

Proving that a function is a bijection means proving that it is both a surjection and an injection. So formal proofs are rarely easy. Below we discuss and do not prove. (See surjection and injection.)

Example: The linear function of a slanted line is a bijection. That is, y=ax+b where a≠0 is a bijection.

Discussion: Every horizontal line intersects a slanted line in exactly one point (see surjection and injection for proofs). Image 1.

Example: The polynomial function of third degree: f(x)=x3 is a bijection. Image 2 and image 5 thin yellow curve. Its inverse is the cube root function f(x)= ∛x and it is also a bijection f(x):ℝ→ℝ. Image 5: thick green curve.

Example: The quadratic function f(x) = x2 is not a bijection (from ℝ→ℝ). Image 3. It is not a surjection. It is not an injection. However, we can restrict both its domain and codomain to the set of non-negative numbers (0,+∞) to get an (invertible) bijection (see examples below).

Note: This last example shows this. To determine whether a function is a bijection we need to know three things:

  • the domain
  • the function machine
  • the codomain

Example: Suppose our function machine is f(x)=x².

  • This machine and domain=ℝ and codomain=ℝ is not a surjection and not an injection. However,
  • this same machine and domain=[0,+∞) and codomain=[0,+∞) is both a surjection and an injection and thus a bijection.

Bijections and their inverses[change | change source]

Let f(x):AB where A and B are subsets of ℝ.

  • Suppose f is not a bijection. For any x where the derivative of f exists and is not zero, there is a neighborhood of x where we can restrict the domain and codomain of f to be a bisection.[4]
  • The graphs of inverse functions are symmetric with respect to the line y=x. (See also Inverse function.)

Example: The quadratic function defined on the restricted domain and codomain [0,+∞)

f(x):[0,+\infty) \,\, \rightarrow \,\, [0,+\infty)  defined by  f(x) = x^2

is a bijection. Image 6: thin yellow curve.

Example: The square root function defined on the restricted domain and codomain [0,+∞)

f(x):[0,+\infty) \,\, \rightarrow \,\, [0,+\infty)  defined by  f(x) = \sqrt{x}

is the bijection defined as the inverse function of the quadratic function: x2. Image 6: thick green curve.

Example: The exponential function defined on the domain ℝ and the restricted codomain (0,+∞)

f(x):\mathbf{R} \,\, \rightarrow \,\, (0,+\infty)  defined by  f(x) = a^x \, ,\,\, a>1

is a bijection. Image 4: thin yellow curve (a=10).

Example: The logarithmic function base a defined on the restricted domain (0,+∞) and the codomain ℝ

f(x):(0,+\infty) \,\, \rightarrow \,\, \mathbf{R}  defined by  f(x) = \log_a x \, ,\,\, a>1

is the bijection defined as the inverse function of the exponential function: ax. Image 4: thick green curve (a=10).

Bijection: every vertical line (in the domain) and every horizontal line (in the codomain) intersects exactly one point of the graph.
Line explicit ex.svg
1. Bijection. All slanted lines are bijections f(x):ℝ→ℝ.
Xto3.svg
2. Bijection. f(x):ℝ→ℝ. f(x)=x³.
Xto2.svg
3. Not a bijection. f(x):ℝ→ℝ. f(x)=x² is not a surjection. It is not an injection.
Logx inv.svg
4. Bijections. f(x):ℝ→ (0,+∞). f(x)=10x (thin yellow) and its inverse f(x):(0,+∞)→ℝ. f(x)=log10x (thick green).
Xto1over3.svg
5. Bijections. f(x):ℝ→ℝ. f(x)=x³ (thin yellow) and its inverse f(x)=∛x (thick green).
Xsqrt pos.svg
6. Bijections. f(x):[0,+∞)→[0,+∞). f(x)=x² (thin yellow) and its inverse f(x)=√x (thick green).

See also[change | change source]

References[change | change source]

  1. Weisstein, Eric. "Bijective function" (in English). From MathWorld--a Wolfram Web Resource. http://mathworld.wolfram.com/Bijection.html. Retrieved February 2014.
  2. C.Clapham, J.Nicholson (2009). "Oxford Concise Dictionary of Mathematics, Bijection" (in English). addison-Wesley. p. 88. http://web.cortland.edu/matresearch/OxfordDictionaryMathematics.pdf. Retrieved February 2014.
  3. Miller, Jeff (2010). "Earliest Uses of Some of the Words of Mathematics" (in English). Tripod. http://jeff560.tripod.com/i.html. Retrieved February 2014.
  4. 4.0 4.1 Tanton, James (2005). Encyclopedia of Mathematics, Cardinality. Facts on File, New York. p. 60. ISBN 0-8160-5124-0 . (English)
  5. "Inverse of Bijection is Bijection" (in English). http://www.proofwiki.org/wiki/Inverse_of_Bijection_is_Bijection. Retrieved February 2014.
  6. "Injection iff Left Inverse" (in English). http://www.proofwiki.org/wiki/Injection_iff_Left_Inverse. Retrieved February 2014.
  7. "Surjection iff Right Inverse" (in English). http://www.proofwiki.org/wiki/Surjection_iff_Right_Inverse. Retrieved February 2014.
  8. iff_Left_and_Right_Inverse "Bijection_iff Left and Right Inverse" (in English). http://www.proofwiki.org/wiki/Bijection iff_Left_and_Right_Inverse. Retrieved February 2014.

Other websites[change | change source]