All Topics  
Bijection

 

 
   Email Print
   Bookmark   Link
 

 

Bijection
 
 
  Topics Bijection Topic Home

In mathematics
Mathematics

Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere....
, a bijection, or a bijective function is a function
Function (mathematics)

The mathematical concept of a function expresses dependence between two quantities, one of which is known and the other which is produced. A function associates a single output to each input element drawn from a fixed Set , such as the real numbers , although different inputs may have the same output....
 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.

Alternatively, f is bijective if it is a one-to-one correspondence between those sets; i.e., both one-to-one (injective
Injective function

In mathematics, an injective function is a function which associates distinct arguments with distinct values.An injective function is called an injection, and is also said to be a one-to-one function ....
) and onto (surjective
Surjective function

In mathematics, a function f is said to be surjective or onto, if its values span its whole codomain; that is, for every y in the codomain, there is at least one x in the domain such that f = y ....
).






Discussion
Ask a question about 'Bijection'
Start a new discussion about 'Bijection'
Answer questions from other users
Full Discussion Forum



Recent Posts

How do you prove that a total function f, has an inverse that is also a total function if and only i...








Encyclopedia


Bijection
In mathematics
Mathematics

Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere....
, a bijection, or a bijective function is a function
Function (mathematics)

The mathematical concept of a function expresses dependence between two quantities, one of which is known and the other which is produced. A function associates a single output to each input element drawn from a fixed Set , such as the real numbers , although different inputs may have the same output....
 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.

Alternatively, f is bijective if it is a one-to-one correspondence between those sets; i.e., both one-to-one (injective
Injective function

In mathematics, an injective function is a function which associates distinct arguments with distinct values.An injective function is called an injection, and is also said to be a one-to-one function ....
) and onto (surjective
Surjective function

In mathematics, a function f is said to be surjective or onto, if its values span its whole codomain; that is, for every y in the codomain, there is at least one x in the domain such that f = y ....
). (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 integer
Integer

The integers are natural numbers including 0 and their negative and non-negative numberss . They are numbers that can be written without a fractional or decimal component, and fall within the set ....
s to , 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
Permutation

In several fields of mathematics the term permutation is used with different but closely related meanings. They all relate to the notion of mapping the element s of a set to other elements of the same set, i.e., exchanging elements of a set....
.

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

Bijective functions play a fundamental role in many areas of mathematics, for instance in the definition of isomorphism
Isomorphism

In abstract algebra, an isomorphism is a bijection map f such that both f and its inverse function f −1 are homomorphisms, i.e., structure-preserving mappings....
 (and related concepts such as homeomorphism
Homeomorphism

In the mathematics field of topology, a homeomorphism or topological isomorphism is a continuous function between two topological spaces....
 and diffeomorphism
Diffeomorphism

In mathematics, a diffeomorphism is an isomorphism of smooth manifolds. It is an invertible function that map s one differentiable manifold to another, such that both the function and its inverse are smooth function....
), permutation group
Permutation group

In mathematics, a permutation group is a group G whose elements are permutations of a given Set M, and whose group operation is the composition of permutations in G ; the relationship is often written as ....
, projective map, and many others.

Composition and inverses

A function f is bijective if and only if its inverse relation
Inverse relation

In mathematics, the inverse relation of a binary relation is the relation that occurs when you switch the order of the elements in the relation....
  f −1 is a function. In that case, f −1 is also a bijection.

The composition g o f of two bijections f X'Y and g Y'Z is a bijection. The inverse of g o f is (g o f)−1 = (f −1) o (g−1).

Bijective Composition
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
Surjective function

In mathematics, a function f is said to be surjective or onto, if its values span its whole codomain; that is, for every y in the codomain, there is at least one x in the domain such that f = y ....
.

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
Identity function

In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument....
 on X, and f o g is the identity function
Identity function

In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument....
 on Y. Consequently, the sets have the same cardinality.

Bijections and cardinality

If X and Y are finite
Finite set

In mathematics, finite set is a Set that has a finite number of element . For example,is a finite set with five elements. The number of elements of a finite set is a natural number , and is called the cardinality of the set....
 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
Cardinal number

In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of Set ....
, a way to distinguish the various sizes of infinite sets.

Examples and counterexamples

  • For any set X, the identity function
    Identity function

    In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument....
     idX from X to X, defined by idX(x) = x, is bijective.
  • The function f from the real line
    Real line

    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 space of some sort, such as a topological space or a vector space....
         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.
  • The exponential function
    Exponential function

    The exponential function is a function in mathematics. The application of this function to a value x is written as exp. Equivalently, this can be written in the form ex, where e is the mathematical constant that is the base of the natural logarithm and that is also known as Euler's number....
     g :     R R, with g(x) = ex, is not bijective: for instance, there is no x in R such that g(x) = −1, showing that g is not surjective. However if the codomain is changed to be the positive real numbers R+ = (0,+8), then g becomes bijective; its inverse is the natural logarithm
    Natural logarithm

    The natural logarithm, formerly known as the hyperbolic logarithm, is the logarithm to the base e , where e is an irrational number constant approximately equal to 2.718281828....
     function ln.
  • The function h : R [0,+8) 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,+8), 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 p/3 and 2p/3 are both in the domain and both map to (v3)/2.


Properties

  • A function f from the real line
    Real line

    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 space of some sort, such as a topological space or a vector space....
         R to R is bijective if and only if its plot is intersected by any horizontal line at exactly one point.
  • 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
    Symmetric group

    In mathematics, the symmetric group on a Set X, denoted by SX, or Sym, is the group whose underlying set is the set of all bijective function s from X to X, in which the group operation is that of Function composition, i.e., two such functions f and g can be composed to yield a new bijective function ,...
     of X, which is denoted variously by S(X), SX, or X! (the last reads "X factorial
    Factorial

    In mathematics, the factorial of a negative and non-negative numbers integer n, denoted by n!, is the Product of all positive integers less than or equal to n....
    ").
  • For a subset A of the domain with cardinality
    Cardinality

    In mathematics, the cardinality of a set is a measure of the "number of Element of the set". For example, the set A = contains 3 elements, and therefore A has a cardinality of 3....
     |A| and subset B of the codomain with cardinality |B|, one has the following equalities:
|f(A)| = |A| and |f−1(B)| = |B|.
  • If X and Y are finite
    Finite set

    In mathematics, finite set is a Set that has a finite number of element . For example,is a finite set with five elements. The number of elements of a finite set is a natural number , and is called the cardinality of the set....
     sets with the same cardinality, and f: X ? Y, then the following are equivalent:
  1. f is a bijection.
  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. That is to say, the number of permutation
    Permutation

    In several fields of mathematics the term permutation is used with different but closely related meanings. They all relate to the notion of mapping the element s of a set to other elements of the same set, i.e., exchanging elements of a set....
    s (another name for bijections) of elements of S is the same as the number of total orderings of that set -- namely, n!.


Bijections and category theory

Formally, bijections are precisely the isomorphism
Isomorphism

In abstract algebra, an isomorphism is a bijection map f such that both f and its inverse function f −1 are homomorphisms, i.e., structure-preserving mappings....
s in the category
Category theory

In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them: it abstracts from set s and function s to objects linked in diagrams by morphisms or arrows....
 Set
Category of sets

In mathematics, the category of sets, denoted as Set, is the Category theory whose Category theory are all Set and whose morphisms are all function s....
 of sets and functions. However, the bijections are not always the isomorphisms. For example, in the category Top
Category of topological spaces

In mathematics, the category of topological spaces, often denoted Top, is the category whose object s are topological spaces and whose morphisms are continuous maps....
 of topological spaces
Topological space

Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connected space, and Continuous function ....
 and continuous functions, the isomorphisms must be homeomorphisms
Homeomorphism

In the mathematics field of topology, a homeomorphism or topological isomorphism is a continuous function between two topological spaces....
 in addition to being bijections.

See also

  • Category theory
    Category theory

    In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them: it abstracts from set s and function s to objects linked in diagrams by morphisms or arrows....
  • Injective function
    Injective function

    In mathematics, an injective function is a function which associates distinct arguments with distinct values.An injective function is called an injection, and is also said to be a one-to-one function ....
  • Symmetric group
    Symmetric group

    In mathematics, the symmetric group on a Set X, denoted by SX, or Sym, is the group whose underlying set is the set of all bijective function s from X to X, in which the group operation is that of Function composition, i.e., two such functions f and g can be composed to yield a new bijective function ,...
  • Surjective function
  • Bijective numeration
    Bijective numeration

    Bijective numeration is any numeral system that establishes a bijection between the set of non-negative integers and the set of finite strings over a finite set of digits....
  • Bijective proof
    Bijective proof

    In combinatorics, bijective proof is a mathematical proof technique that finds a bijective function f : A ? B between two Set A and B, thus proving that they have the same number of elements, |A| = |B|....