Definition:Bijection

From ProofWiki
Jump to navigation Jump to 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 $\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$.


Class-Theoretical Definition

In the context of class theory, the definition follows the same lines:

Let $A$ and $B$ be classes.

Let $f: A \to B$ be a class mapping from $A$ to $B$.


Then $f$ is said to be a bijection if and only if:

$f$ is both a class injection and a class surjection.


Graphical Depiction

The following diagram illustrates the bijection:

$f: S \to T$

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

\(\ds S\) \(=\) \(\ds \set {a, b, c, d}\)
\(\ds T\) \(=\) \(\ds \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:

\(\ds \map f a\) \(=\) \(\ds p\)
\(\ds \map f b\) \(=\) \(\ds r\)
\(\ds \map f c\) \(=\) \(\ds s\)
\(\ds \map f d\) \(=\) \(\ds q\)
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:

\(\ds \map {f^{-1} } p\) \(=\) \(\ds \set a\)
\(\ds \map {f^{-1} } q\) \(=\) \(\ds \set d\)
\(\ds \map {f^{-1} } r\) \(=\) \(\ds \set c\)
\(\ds \map {f^{-1} } s\) \(=\) \(\ds \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 $\cong$ already has several uses.


In the context of class theory, a bijection is often seen referred to as a class bijection.


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.


$x^3$ 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 = x^3$

Then $f$ is a bijection.


Negative Functions on Standard Number Systems are Bijective

Let $\mathbb S$ be one of the standard number systems $\Z$, $\Q$, $\R$, $\C$.

Let $h: \mathbb S \to \mathbb S$ be the negation function defined on $\mathbb S$:

$\forall x \in \mathbb S: \map h x = -x$

Then $h$ 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


This page has been identified as a candidate for refactoring of medium complexity.
In particular: Some of all of these results are to be included as part of Equivalence of Definitions of Bijection.
Until this has been finished, please leave {{Refactor}} in the code.

New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only.

Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Refactor}} from the code.



Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Bijection&oldid=583706"