Bijection

Bijection

Overview

A bijection is a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

 giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function
Inverse function
In mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...

 from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements. For infinite sets the picture is more complex, leading 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 sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...

, a way to distinguish the various sizes of infinite sets.

A bijective function from a set to itself is also called a permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

.

Bijective functions are essential to many areas of mathematics including the definitions of isomorphism
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations.  If there exists an isomorphism between two structures, the two structures are said to be isomorphic.  In a certain sense, isomorphic structures are...

, homeomorphism
Homeomorphism
In the mathematical field of topology, a homeomorphism or topological isomorphism or bicontinuous function is a continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphisms in the category of topological spaces—that is, they are...

, diffeomorphism
Diffeomorphism
In mathematics, a diffeomorphism is an isomorphism in the category of smooth manifolds. It is an invertible function that maps one differentiable manifold to another, such that both the function and its inverse are smooth.- Definition :...

, 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...

, and projective map.


To have an exact pairing between X and Y (where Y need not be different from X), four properties must hold:
  1. each element of X must be paired with at least one element of Y,
  2. no element of X may be paired with more than one element of Y,
  3. each element of Y must be paired with at least one element of X, and
  4. no element of Y may be paired with more than one element of X.


Satisfying properties (1) and (2) means that a bijection is a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

 with domain X.
Discussion
Ask a question about 'Bijection'
Start a new discussion about 'Bijection'
Answer questions from other users
Full Discussion Forum
 
Unanswered Questions
Recent Discussions
Encyclopedia

A bijection is a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

 giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function
Inverse function
In mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...

 from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements. For infinite sets the picture is more complex, leading 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 sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...

, a way to distinguish the various sizes of infinite sets.

A bijective function from a set to itself is also called a permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

.

Bijective functions are essential to many areas of mathematics including the definitions of isomorphism
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations.  If there exists an isomorphism between two structures, the two structures are said to be isomorphic.  In a certain sense, isomorphic structures are...

, homeomorphism
Homeomorphism
In the mathematical field of topology, a homeomorphism or topological isomorphism or bicontinuous function is a continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphisms in the category of topological spaces—that is, they are...

, diffeomorphism
Diffeomorphism
In mathematics, a diffeomorphism is an isomorphism in the category of smooth manifolds. It is an invertible function that maps one differentiable manifold to another, such that both the function and its inverse are smooth.- Definition :...

, 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...

, and projective map.

Definition


To have an exact pairing between X and Y (where Y need not be different from X), four properties must hold:
  1. each element of X must be paired with at least one element of Y,
  2. no element of X may be paired with more than one element of Y,
  3. each element of Y must be paired with at least one element of X, and
  4. no element of Y may be paired with more than one element of X.


Satisfying properties (1) and (2) means that a bijection is a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

 with domain X. It is more common to see properties (1) and (2) written as a single statement: Every element of X is paired with exactly one element of Y. Functions which satisfy property (3) are said to be "onto Y " and are called surjections
Surjective function
In mathematics, a function f from a set X to a set Y is surjective , or a surjection, if every element y in Y has a corresponding element x in X so that f = y...

 (or surjective functions). Functions which satisfy property (4) are said to be "one-to-one functions" and are called injections
Injective function
In mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...

 (or injective functions). With this terminology, a bijection is a function which is both a surjection and an injection, or using other words, a bijection is a function which is both one-to-one and onto.

Example


As a concrete example of a bijection, consider the batting line-up
Batting order (baseball)
The batting order, or batting lineup, in baseball is the sequence in which the nine members of the offense take their turns in batting against the pitcher. The batting order is the main component of a team's offensive strategy. The batting order is set by the manager before the game begins...

 of a baseball
Baseball
Baseball is a bat-and-ball sport played between two teams of nine players each. The aim is to score runs by hitting a thrown ball with a bat and touching a series of four bases arranged at the corners of a ninety-foot diamond...

 team. The set X will be the nine players on the team and the set Y will be the nine positions in the batting order (1st, 2nd, 3rd, etc.) The "pairing" is given by which player is in what position in this order. Property (1) is satisfied since each player is somewhere in the list. Property (2) is satisfied since no player bats in two (or more) positions in the order. Property (3) says that for each position in the order, there is some player batting in that position and property (4) states that two or more players are never batting in the same position in the list.

Inverses


A bijection f with domain X ("functionally" indicated by f: X → Y) also defines a relation
Relation (mathematics)
In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...

 starting in Y and going to X (by turning the arrows around). The process of "turning the arrows around" for an arbitrary function does not usually yield a function, but properties (3) and (4) of a bijection say that this 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. For example, the inverse of the relation 'child of' is the relation 'parent of'...

 is a function with domain Y. Moreover, properties (1) and (2) then say that this inverse function is a surjection and an injection, that is, the inverse function
Inverse function
In mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...

 exists and is also a bijection. Functions that have inverse functions are said to be invertible. Bijections are the invertible functions.

Stated in concise mathematical notation, a function is bijective if and only if it satisfies the condition
for every there is a unique with .


Continuing with the baseball batting line-up example, the function that is being defined takes as input the name of one of the players and outputs the position of that player in the batting order. Since this function is a bijection, it has an inverse function which takes as input a position in the batting order and outputs the player who will be batting in that position.

Composition


The composition  of two bijections and is a bijection. The inverse of is .


Conversely, if the composition of two functions is bijective, we can only say that f is injective
Injective function
In mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...

 and g is surjective
Surjective function
In mathematics, a function f from a set X to a set Y is surjective , or a surjection, if every element y in Y has a corresponding element x in X so that f = y...

.

Bijections and cardinality


If X and Y are finite sets, then there exists a bijection between the two sets X and Y iff
IFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...

 X and Y have the same number of elements. Indeed, in axiomatic set theory, this is taken as the 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 sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...

, a way to distinguish the various sizes of infinite sets.

Examples and non-examples

  • 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...

     , is bijective.
  • The function is bijective, since for each y there is a unique such that .
  • The exponential function
    Exponential function
    In mathematics, the exponential function is the function ex, where e is the number such that the function ex is its own derivative. The exponential function is used to model a relationship in which a constant change in the independent variable gives the same proportional change In mathematics,...

    , , is not bijective: for instance, there is no such that , showing that g is not surjective. However if the codomain
    Codomain
    In mathematics, the codomain or target set of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation...

     is restricted to the positive real numbers , then g becomes bijective; its inverse is the natural logarithm
    Natural logarithm
    The natural logarithm is the logarithm to the base e, where e is an irrational and transcendental constant approximately equal to 2.718281828...

     function ln.
  • The function is not bijective: for instance, , showing that h is not injective. However, if the domain is restricted to , then h becomes bijective; its inverse is the positive square root function.

Properties

  • A function is bijective if and only if its graph
    Graph of a function
    In mathematics, the graph of a function f is the collection of all ordered pairs . In particular, if x is a real number, graph means the graphical representation of this collection, in the form of a curve on a Cartesian plane, together with Cartesian axes, etc. Graphing on a Cartesian plane is...

     meets every horizontal and vertical line exactly once.
  • If X is a set, then the bijective functions from X to itself, together with the operation of functional composition (∘), form a group, the symmetric group
    Symmetric group
    In mathematics, the symmetric group Sn on a finite set of n symbols is the group whose elements are all the permutations of the n symbols, and whose group operation is the composition of such permutations, which are treated as bijective functions from the set of symbols to itself...

     of X, which is denoted variously by S(X), SX, or X! (X factorial
    Factorial
    In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...

    ).
  • Bijections preserve cardinalities of sets: 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−1(B)| = |B|.
  • If X and Y are finite sets with the same cardinality, and , then the following are equivalent:
    1. f is a bijection.
    2. f is a surjection.
    3. f is an injection.
  • 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 mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

    s of elements of S is the same as the number of total orderings of that set—namely, n!.

Bijections and category theory


Bijections are precisely the isomorphism
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations.  If there exists an isomorphism between two structures, the two structures are said to be isomorphic.  In a certain sense, isomorphic structures are...

s in the category
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...

 Set
Category of sets
In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets A and B are all functions from A to B...

 of sets and set functions. However, the bijections are not always the isomorphisms for more complex categories. For example, in the category Gr
Category of groups
In mathematics, the category Grp has the class of all groups for objects and group homomorphisms for morphisms. As such, it is a concrete category...

 of groups
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...

, the morphisms must be homomorphism
Homomorphism
In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures . The word homomorphism comes from the Greek language: ὁμός meaning "same" and μορφή meaning "shape".- Definition :The definition of homomorphism depends on the type of algebraic structure under...

s since they must preserve the group structure, so the isomorphisms are group isomorphisms which are bijective homomorphisms.

See also


  • Injective function
    Injective function
    In mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...

  • Surjective function
    Surjective function
    In mathematics, a function f from a set X to a set Y is surjective , or a surjection, if every element y in Y has a corresponding element x in X so that f = y...

  • Bijection, injection and surjection
    Bijection, injection and surjection
    In mathematics, injections, surjections and bijections are classes of functions distinguished by the manner in which arguments and images are related or mapped to each other.A function maps elements from its domain to elements in its codomain.*A function f: \; A \to B is injective...

  • Symmetric group
    Symmetric group
    In mathematics, the symmetric group Sn on a finite set of n symbols is the group whose elements are all the permutations of the n symbols, and whose group operation is the composition of such permutations, which are treated as bijective functions from the set of symbols to itself...

  • Bijective numeration
  • Bijective proof
    Bijective proof
    In combinatorics, bijective proof is a proof technique that finds a bijective function f : A → B between two sets A and B, thus proving that they have the same number of elements, |A| = |B|. One place the technique is useful is where we wish to know the size of A, but can find no direct way of...

  • Cardinality
  • Category theory
    Category theory
    Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...

  • Ax–Grothendieck theorem

External links