Definition:Bijection

From ProofWiki
Jump to: navigation, search

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 $\left({x, y}\right) \in f$
$(2): \quad$ for each $y \in T$ there exists one and only one $x \in S$ such that $\left({x, y}\right) \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}\) $\quad$ $\quad$
\(\displaystyle T\) \(=\) \(\displaystyle \set {p, q, r, s}\) $\quad$ $\quad$

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\) $\quad$ $\quad$
\(\displaystyle \map f b\) \(=\) \(\displaystyle r\) $\quad$ $\quad$
\(\displaystyle \map f c\) \(=\) \(\displaystyle s\) $\quad$ $\quad$
\(\displaystyle \map f d\) \(=\) \(\displaystyle q\) $\quad$ $\quad$
Bijection-and-Inverse.png
$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\) $\quad$ $\quad$
\(\displaystyle \map {f^{-1} } q\) \(=\) \(\displaystyle \set d\) $\quad$ $\quad$
\(\displaystyle \map {f^{-1} } r\) \(=\) \(\displaystyle \set c\) $\quad$ $\quad$
\(\displaystyle \map {f^{-1} } s\) \(=\) \(\displaystyle \set c\) $\quad$ $\quad$


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


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

$\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.


Also see


  • Results about bijections can be found here.


Basic Properties of a Bijection



Sources