Bijection

In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other set, and each element of the other set is paired with exactly one element of the first set. There are no unpaired elements. In mathematical terms, a bijective function f: X → Y is a one-to-one (injective) and onto (surjective) mapping of a set X to a set Y. The term one-to-one correspondence must not be confused with one-to-one function (a.k.a. injective function) (see figures).An injective non-surjective function (injection, not a bijection)An injective surjective function (bijection)A non-injective surjective function (surjection, not a bijection)A non-injective non-surjective function (also not a bijection) In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other set, and each element of the other set is paired with exactly one element of the first set. There are no unpaired elements. In mathematical terms, a bijective function f: X → Y is a one-to-one (injective) and onto (surjective) mapping of a set X to a set Y. The term one-to-one correspondence must not be confused with one-to-one function (a.k.a. injective function) (see figures). A bijection from the set X to the set Y has an inverse function 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 complicated, leading to the concept of cardinal number, a way to distinguish the various sizes of infinite sets. A bijective function from a set to itself is also called a permutation. Bijective functions are essential to many areas of mathematics including the definitions of isomorphism, homeomorphism, diffeomorphism, permutation group, and projective map. For a pairing between X and Y (where Y need not be different from X) to be a bijection, four properties must hold: Satisfying properties (1) and (2) means that a bijection is a function 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 (or surjective functions). Functions which satisfy property (4) are said to be 'one-to-one functions' and are called injections (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'. Bijections are sometimes denoted by a two-headed rightwards arrow with tail (.mw-parser-output .monospaced{font-family:monospace,monospace}U+2916 ⤖ .mw-parser-output .smallcaps{font-variant:small-caps}RIGHTWARDS TWO-HEADED ARROW WITH TAIL), as in f : X ⤖ Y. This symbol is a combination of the two-headed rightwards arrow (U+21A0 ↠ RIGHTWARDS TWO HEADED ARROW) sometimes used to denote surjections and the rightwards arrow with a barbed tail (U+21A3 ↣ RIGHTWARDS ARROW WITH TAIL) sometimes used to denote injections. Consider the batting line-up of a baseball or cricket team (or any list of all the players of any sports team where every player holds a specific spot in a line-up). The set X will be the players on the team (of size nine in the case of baseball) and the set Y will be the 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.