Encyclopedia > Bijection

  Article Content

Bijection

A function fX → Y is called bijective or a bijection if for every y in the codomain Y there is exactly one x in the domain X with f(x) = y. Put another way, a bijection is a function which is both injective and surjective, and therefore bijections are also called one-to-one and onto. (In some references, the phrase "one-to-one" is used alone to mean bijective. Wikipedia does not follow this older usage.)


Surjective, not injective

Injective, not surjective

Bijective

Not surjective, not injective

When X and Y are both the real line R, then a bijective function fR → R can be visualized as one whose graph is intersected exactly once by any horizontal line.

If X and Y are finite sets, then there exists a bijection between the two sets X and Y if and only if X and Y have the same number of elements. Generalising this to infinite sets leads to the concept of cardinal number, a way to distinguish the various infinite sizes of infinite sets.

Examples and counterexamples

Consider the function fR → R defined by f(x) = 2x + 1. This function is bijective, since given an arbitrary real number y, we can solve y = 2x + 1 to get exactly one real solution x = (y − 1)/2.

On the other hand, the function gR → R defined by g(x) = x2 is not bijective, for two essentially different reasons. First, we have (for example) g(1) = 1 = g(−1), so that g is not injective; also, there is (for example) no real number x such that x2 = −1, so that g is not surjective either. Either one of these facts is enough to show that g is not bijective.

However, if we define the function hR+ → R+ by the same formula as g, but with the domain and codomain both restricted to only the nonnegative real numbers, then the function h is bijective. This is because, given an arbitrary nonnegative real number y, we can solve y = x2 to get exactly one nonnegative real solution x = √y.

Properties

  • A function fX → Y is bijective if and only if there exists a function gY → X such that g o f is the identity function on X and f o g is the identity function on Y. (In fancy language, bijections are precisely the isomorphisms in the category of sets.) In this case, g is uniquely determined by f and we call g the inverse function of f and write f −1 = g. Furthermore, g is also a bijection, and the inverse of g is f again.
  • If f o g is bijective, then f is surjective and g is injective.
  • If f and g are both bijective, then f o g is also bijective.
  • If X is a set, then the bijective functions from X to itself, together with the operation of functional composition (o), form a group, the symmetric group of X, which is denoted variously by S(X), SX, or X! (the last read "X factorial").


See also: Injective function, Surjection



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Topology

... "discrete", more computable invariants to maps and spaces, often in a functorial way. Ideas from algebraic topology have had strong influence on algebra and ...