A bijective 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. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function

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). F G H I L In Mathematics, a function f is said to be surjective or onto, if its values span its whole Codomain; that is for every (One-to-one function means one-to-one correspondence (i. e. , bijection) to some authors, but injection to others. )

For example, consider the function succ, defined from the set of integers to , that to each integer x associates the integer succ(x) = x + 1. The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French 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. In several fields of Mathematics the term permutation is used with different but closely related meanings

The set of all bijections from X to Y is denoted as XY.

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. In Abstract algebra, an isomorphism ( Greek: ἴσος isos "equal" and μορφή morphe "shape" is a bijective Topological equivalence redirects here see also Topological equivalence (dynamical systems. In Mathematics, a diffeomorphism is an Isomorphism of Smooth manifolds It is an Invertible function that maps one Differentiable In Mathematics, a permutation group is a group G whose elements are Permutations of a given set M, and whose group operation A projective transformation is a transformation used in Projective geometry: it is the composition of a pair of Perspective projections It describes what

Composition and inverses

A function f is bijective if and only if its inverse relation f ⁻¹ is a function. ↔ In Mathematics, the inverse relation of a Binary relation is the relation taken 'backwards' as in changing the relation 'child of' to 'parent of' In that case, f ⁻¹ is also a bijection.

The composition g o f of two bijections f XY and g YZ is a bijection. In Mathematics, a composite function represents the application of one function to the results of another The inverse of g o f is (g o f)⁻¹ = (f ⁻¹) o (g⁻¹).

A bijection composed of an injection and a surjection.

On the other hand, if the composition g o f of two functions is bijective, we can only say that f is injective and g is surjective. In Mathematics, a function f is said to be surjective or onto, if its values span its whole Codomain; that is for every

A relation f from X to Y is a bijective function if and only if there exists another relation g from Y to X such that g o f is the identity function on X, and f o g is the identity function on Y. In Mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that In Mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that Consequently, the sets have the same cardinality.

Bijections and cardinality

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. In Mathematics, a set is called finite if there is a Bijection between the set and some set of the form {1 2. ↔ 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. Infinity (symbolically represented with ∞) comes from the Latin infinitas or "unboundedness This article describes cardinal numbers in mathematics For cardinals in linguistics see Names of numbers in English. In Set theory, an infinite set is a set that is not a Finite set.

Examples and counterexamples

• For any set X, the identity function id_X from X to X, defined by id_X(x) = x, is bijective. In Mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that
• The function f from the real line R to R defined by f(x) = 2x + 1 is bijective, since for each y there is a unique x = (y − 1)/2 such that f(x) = y. In Mathematics, the real line is simply the set R of singleton Real numbers However this term is usually used when R is to be treated as a
• The exponential function g : R R, with g(x) = e^x, is not bijective: for instance, there is no x in R such that g(x) = −1, showing that g is not surjective. The exponential function is a function in Mathematics. The application of this function to a value x is written as exp( x) However if the codomain is changed to be the positive real numbers R⁺ = (0,+∞), then g becomes bijective; its inverse is the natural logarithm function ln. The natural logarithm, formerly known as the Hyperbolic logarithm is the Logarithm to the base e, where e is an irrational
• The function h : R [0,+∞) with h(x) = x² is not bijective: for instance, h(−1) = h(+1) = 1, showing that h is not injective. However, if the domain too is changed to [0,+∞), then h becomes bijective; its inverse is the positive square root function.
• is not a bijection because −1, 0, and +1 are all in the domain and all map to 0.
• is not a bijection because π/3 and 2π/3 are both in the domain and both map to (√3)/2.

Properties

• A function f from the real line R to R is bijective if and only if its plot is intersected by any horizontal line at exactly one point. In Mathematics, the real line is simply the set R of singleton Real numbers However this term is usually used when R is to be treated as a
• 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 reads "X factorial"). In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element In Mathematics, the symmetric group on a set X, denoted by S X or Sym( X) is the group whose underlying Definition The factorial function is formally defined by n!=\prod_{k=1}^n k
• For a subset A of the domain with cardinality |A| and subset B of the codomain with cardinality |B|, one has the following equalities:

|f(A)| = |A| and |f⁻¹(B)| = |B|. In Mathematics, the cardinality of a set is a measure of the "number of elements of the set"

• If X and Y are finite sets with the same cardinality, and f: X → Y, then the following are equivalent:

1. f is a bijection. In Mathematics, a set is called finite if there is a Bijection between the set and some set of the form {1 2.
2. f is a surjection.
3. f is an injection.

• At least for a finite set S, there is a bijection between the set of possible total orderings of the elements and the set of bijections from S to S. In Mathematics and Set theory, a total order, linear order, simple order, or (non-strict ordering is a Binary relation That is to say, the number of permutations (another name for bijections) of elements of S is the same as the number of total orderings of that set -- namely, n!. In several fields of Mathematics the term permutation is used with different but closely related meanings

Bijections and category theory

Formally, bijections are precisely the isomorphisms in the category Set of sets and functions. In Abstract algebra, an isomorphism ( Greek: ἴσος isos "equal" and μορφή morphe "shape" is a bijective In Mathematics, category theory deals in an abstract way with mathematical Structures and relationships between them it abstracts from sets In Mathematics, the category of sets, denoted as Set, is the category whose objects are all sets and whose Morphisms are However, the bijections are not always the isomorphisms. For example, in the category Top of topological spaces and continuous functions, the isomorphisms must be homeomorphisms in addition to being bijections. In Mathematics, the category of topological spaces, often denoted Top, is the category whose objects are Topological spaces and whose Topological spaces are mathematical structures that allow the formal definition of concepts such as Convergence, connectedness, and continuity. In Mathematics, a continuous function is a function for which intuitively small changes in the input result in small changes in the output Topological equivalence redirects here see also Topological equivalence (dynamical systems.

See also

• injective function
• symmetric group
• surjective function
• Bijective numeration
• Bijective proof