Bijection

related topics
{math, number, function}

In mathematics, a bijection, or a bijective function, is a function f from a set X to a set Y with the property that, for every y in Y, there is exactly one x in X such that f(x) = y. It follows from this definition that no unmapped element exists in either X or Y.

Alternatively, f is bijective if it is a one-to-one correspondence between those sets; i.e., both one-to-one (injective) and onto (surjective).

For example, consider the function succ, defined from the set of integers \Z to \Z, that to each integer x associates the integer succ(x) = x + 1. For another example, consider the function sumdif that to each pair (x,y) of real numbers associates the pair sumdif(x,y) = (x + y, x − y).

A bijective function from a set to itself is also called a permutation.

The set of all bijections from X to Y is denoted as XY. (Sometimes this notation is reserved for binary relations, and bijections are denoted by XY instead.) Occasionally, the set of permutations of a single set X may be denoted X!.

Bijective functions play a fundamental role in many areas of mathematics, for instance in the definition of isomorphism (and related concepts such as homeomorphism and diffeomorphism), permutation group, projective map, and many others.

Contents

Composition and inverses

A function f is bijective if and only if its inverse relation f −1 is a function. In that case, f −1 is also a bijection.

The composition g\circ f of two bijections f:X\to Y and g:Y\to Z is a bijection. The inverse of g\circ f is (g\circ f)^{-1}=(f^{-1})\circ(g^{-1}).

Full article ▸

related documents
Heap (data structure)
Alexandroff extension
Fibonacci coding
Domain (mathematics)
Pseudometric space
Waring's problem
Degenerate distribution
Closed set
Bernoulli process
Zeta distribution
Currying
Geometric mean
Iteration
General number field sieve
Static code analysis
Alternating group
Quadratic programming
Graph of a function
Hamming distance
Differential cryptanalysis
Sharp-P-complete
Extractor
Concatenation
Algebraic extension
Abstract factory pattern
Byte-order mark
Residue (complex analysis)
Unique factorization domain
Equality (mathematics)
Subtraction