# Definition:Bijection

## Contents

## 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:

### 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\) |

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.

### Basic Properties of a Bijection

- In Bijection iff Left and Right Inverse, it is shown that a mapping $f$ is a
**bijection**if and only if it has both a left inverse and a right inverse, and that these are the same, called the (two-sided) inverse.

- In Bijection iff Inverse is Bijection, it is shown that the inverse mapping $f^{-1}$ of a
**bijection**$f$ is also a**bijection**, and that it is the same mapping as the (two-sided) inverse.

- In Composite of Bijection with Inverse is Identity Mapping, it is established that the inverse mapping $f^{-1}$ and the (two-sided) inverse are the same thing.

- In Bijection iff Left and Right Cancellable, it is shown that a mapping $f$ is a
**bijection**if and only if it is both left cancellable and right cancellable.

## Sources

- 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next): Entry:**one-to-one correspondence ($1$-$1$ correspondence)** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next): Entry:**one-to-one correspondence (one-one or $1$-$1$ correspondence)** - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next): Entry:**correspondence**

- Barile, Margherita. "One-to-One." From
*MathWorld*--A Wolfram Web Resource, created by Eric W. Weisstein. http://mathworld.wolfram.com/One-to-One.html