# Definition:Bijection

## Definition

### Definition 1

A mapping $f: S \to T$ is a bijection if and only if both:

$(1): \quad f$ is an injection

and:

$(2): \quad f$ is a surjection.

### Definition 2

A mapping $f: S \to T$ is a bijection if and only if:

$f$ has both a left inverse and a right inverse.

### Definition 3

A mapping $f: S \to T$ is a bijection if and only if:

the inverse $f^{-1}$ of $f$ is a mapping from $T$ to $S$.

### Definition 4

A mapping $f \subseteq S \times T$ is a bijection if and only if:

for each $y \in T$ there exists one and only one $x \in S$ such that $\tuple {x, y} \in f$.

### Definition 5

A relation $f \subseteq S \times T$ is a bijection if and only if:

$(1): \quad$ for each $x \in S$ there exists one and only one $y \in T$ such that $\tuple {x, y} \in f$
$(2): \quad$ for each $y \in T$ there exists one and only one $x \in S$ such that $\tuple {x, y} \in f$.

## Graphical Depiction

The following diagram illustrates the bijection:

$f: S \to T$

and its inverse, where $S$ and $T$ are the finite sets:

 $\displaystyle S$ $=$ $\displaystyle \set {a, b, c, d}$ $\displaystyle T$ $=$ $\displaystyle \set {p, q, r, s}$

and $f$ is defined as:

$f = \set {\tuple {a, p}, \tuple {b, r}, \tuple {c, s}, \tuple {d, q} }$

Thus the images of each of the elements of $S$ under $f$ are:

 $\displaystyle \map f a$ $=$ $\displaystyle p$ $\displaystyle \map f b$ $=$ $\displaystyle r$ $\displaystyle \map f c$ $=$ $\displaystyle s$ $\displaystyle \map f d$ $=$ $\displaystyle q$
$S$ is the domain of $f$.
$T$ is the codomain of $f$.
$\set {p, q, r, s}$ is the image of $f$.

The preimages of each of the elements of $T$ under $f$ are:

 $\displaystyle \map {f^{-1} } p$ $=$ $\displaystyle \set a$ $\displaystyle \map {f^{-1} } q$ $=$ $\displaystyle \set d$ $\displaystyle \map {f^{-1} } r$ $=$ $\displaystyle \set c$ $\displaystyle \map {f^{-1} } s$ $=$ $\displaystyle \set c$

## Also known as

The terms

biunique correspondence
bijective correspondence

are sometimes seen for bijection.

Authors who prefer to limit the jargon of mathematics tend to use the term one-one and onto mapping for bijection.

If a bijection exists between two sets $S$ and $T$, then $S$ and $T$ are said to be in one-to-one correspondence.

Occasionally you will see the term set isomorphism, but the term isomorphism is usually reserved for mathematical structures of greater complexity than a set.

Some authors, developing the concept of inverse mapping independently from that of the bijection, call such a mapping invertible.

The symbol $f: S \leftrightarrow T$ is sometimes seen to denote that $f$ is a bijection from $S$ to $T$.

Also seen sometimes is the notation $f: S \cong T$ or $S \stackrel f \cong T$ but this is cumbersome and the symbol has already got several uses.

## Technical Note

The $\LaTeX$ code for $f: S \leftrightarrow T$ is f: S \leftrightarrow T .

The $\LaTeX$ code for $f: S \cong T$ is f: S \cong T .

The $\LaTeX$ code for $S \stackrel f \cong T$ is S \stackrel f \cong T .

## Examples

### Arbitrary Mapping on Sets

Let $A = \set {a_1, a_2, a_3, a_4}$.

Let $B = \set {b_1, b_2, b_3, b_4}$.

Let $f \subseteq {A \times B}$ be the mapping defined as:

$f = \set {\tuple {a_1, b_3}, \tuple {a_2, b_2}, \tuple {a_3, b_4}, \tuple {a_4, b_1} }$

Then $f$ is a bijection.

### $\paren {-1}^x \floor {\dfrac x 2}$ from $\N$ to $\Z$

Let $f: \N \to \Z$ be the mapping defined from the natural numbers to the integers as:

$\forall x \in \N: f \paren x = \paren {-1}^x \floor {\dfrac x 2}$

Then $f$ is a bijection.

### $2 x + 1$ Function on Real Numbers is Bijective

Let $f: \R \to \R$ be the mapping defined on the set of real numbers as:

$\forall x \in \R: \map f x = 2 x + 1$

Then $f$ is a bijection.

## Also see

• Results about bijections can be found here.