Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
Bijection
Main Page | See live article | Alphabetical index

Bijection

   

In mathematics, a bijective function (or one-to-one correspondence or bijection) is a function that is both injective ("one-to-one") and surjective ("onto"), and therefore bijections are also called one-to-one and onto.

Intuitively, a bijective function creates a correspondence that associates each input value with exactly one output value. (In some references, the phrase "one-to-one" is used alone to mean bijective. Wikipedia does not follow this older usage.)

More formally, a function fX → Y is bijective if for every y in the codomain Y there is exactly one x in the domain X with f(x) = y.


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. (This is a special case of the horizontal line test.)

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. Indeed, in axiomatic set theory, this is taken as the very definition of "same number of elements", and generalising this definition to infinite sets leads to the concept of cardinal number, a way to distinguish the various 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 h: [0, ∞) → [0, ∞) 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


See also: Injective function, Surjection