# Online Encyclopedia

# Bijection

In mathematics, a **bijection**, **bijective function**, or **one-to-one correspondence** 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 and each output value with exactly one input value. (In some references, the phrase "one-to-one" is used alone to mean *bijective*. This encyclopedia does not follow this older usage.)

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

Bijective (injective and surjective) | Injective, not surjective |

Surjective, not injective | Not surjective, not injective |

When `X` and `Y` are both the real line **R**, then a bijective function `f`: **R** → **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 `f`: **R** → **R** defined by `f`(`x`) = 2`x` + 1. This function is bijective, since given an arbitrary real number `y`, we can solve `y` = 2`x` + 1 to get exactly one real solution `x` = (`y` − 1)/2.

On the other hand, the function `g`: **R** → **R** defined by `g`(`x`) = `x`^{2} 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 `x`^{2} = −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` = `x`^{2} to get exactly one nonnegative real solution `x` = √`y`.

## Properties

- A function
`f`:`X`→`Y`is bijective if and only if there exists a function`g`:`Y`→`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 Set 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`),`S`_{X}, or`X`! (the last read "`X`factorial").

See also: Injective function, Surjection