Bijection

In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Given a function

f

:

A

→

B

{\displaystyle f:A\to B}

, the image of an element

a

∈

A

{\displaystyle a\in A}

is the element

f

(

a

)

∈

B

{\displaystyle f(a)\in B}

in the codomain. The pre-image of an element

b

∈

B

{\displaystyle b\in B}

is any element

a

∈

A

{\displaystyle a\in A}

in the domain such that

f

(

a

)

=

b

{\displaystyle f(a)=b}

. Equivalently, a bijection is a relation between two sets such that each element of either set is paired with exactly one element of the other set.

A function is bijective if and only if it is invertible; that is, a function

f

:

X

→

Y

{\displaystyle f:X\to Y}

is bijective if and only if there is a function

g

:

Y

→

X

,

{\displaystyle g:Y\to X,}

the inverse of f, such that each of the two ways for composing the two functions produces an identity function:

g

(

f

(

x

)

)

=

x

{\displaystyle g(f(x))=x}

for each

x

{\displaystyle x}

in

X

{\displaystyle X}

and

f

(

g

(

y

)

)

=

y

{\displaystyle f(g(y))=y}

for each

y

{\displaystyle y}

in

Y

.

{\displaystyle Y.}

For example, the multiplication by two defines a bijection from the integers to the even numbers, which has the division by two as its inverse function.

A function is bijective if and only if it is both injective (or one-to-one)—meaning that each element in the codomain is mapped from at most one element of the domain—and surjective (or onto)—meaning that each element of the codomain is mapped from at least one element of the domain. The term one-to-one correspondence must not be confused with one-to-one function, which means injective but not necessarily surjective.

The elementary operation of counting establishes a bijection from some finite set to the first natural numbers (1, 2, 3, ...), up to the number of elements in the counted set. It results that two finite sets have the same number of elements if and only if there exists a bijection between them.