Bijection

Bijective function.

A bijection is a mapping that is both surjective and injective . In a bijective mapping, each element of one set corresponds to exactly one element of another set, and the inverse mapping is defined, which has the same property. Therefore, a bijective mapping is also called a one-to-one mapping (correspondence), a one-to-one mapping .

If between two sets it is possible to establish a one-to-one correspondence (bijection), then such sets are called equal-power . From the point of view of set theory , equal power sets are indistinguishable.

A one-to-one mapping of a finite set into itself is called a permutation (or permutation) of the elements of this set.

Content

Definition

Function $f\colon X\to Y$ ${\ displaystyle f \ colon X \ to Y}$ called a bijection (and denoted by $f\colon X\leftrightarrow Y$ ${\ displaystyle f \ colon X \ leftrightarrow Y}$ ), If she:

Translates various elements of a set $X$ {\ displaystyle X} into different elements of the set $Y$ {\ displaystyle Y} ( injectivity ). In other words,
- $\forall x_{1}\in X,\;\forall x_{2}\in X\;x_{1}\neq x_{2}\Rightarrow f(x_{1})\neq f(x_{2})$ ${\ displaystyle \ forall x_ {1} \ in X, \; \ forall x_ {2} \ in X \; x_ {1} \ neq x_ {2} \ Rightarrow f (x_ {1}) \ neq f (x_ {2})}$ .
Any item from $Y$ {\ displaystyle Y} has its prototype ( surjectivity ). In other words,
- $\forall y\in Y,\;\exists x\in X\;f(x)=y$ ${\ displaystyle \ forall y \ in Y, \; \ exists x \ in X \; f (x) = y}$ .

Examples

Identity mapping $\mathrm {id} \colon X\to X$ ${\ displaystyle \ mathrm {id} \ colon X \ to X}$ on set $X$ ${\ displaystyle X}$ bijectively.
$f(x)=x,\;f(x)=x^{3}$ ${\ displaystyle f (x) = x, \; f (x) = x ^ {3}}$ - bijective functions from $\mathbb {R}$ ${\ displaystyle \ mathbb {R}}$ in yourself. In general, any monomial of one variable of odd degree is a bijection from $\mathbb {R}$ ${\ displaystyle \ mathbb {R}}$ in yourself.
$f(x)=e^{x}$ ${\ displaystyle f (x) = e ^ {x}}$ - bijective function of $\mathbb {R}$ ${\ displaystyle \ mathbb {R}}$ at $\mathbb {R} _{+}=(0,\;+\infty )$ ${\ displaystyle \ mathbb {R} _ {+} = (0, \; + \ infty)}$ .
$f(x)=\sin x$ ${\ displaystyle f (x) = \ sin x}$ is not a bijective function, if you consider it defined on all $\mathbb {R}$ ${\ displaystyle \ mathbb {R}}$ .
Strictly monotonous and continuous function. $f(x)$ ${\ displaystyle f (x)}$ is a bijection of a segment $[a,b]$ ${\ displaystyle [a, b]}$ on the segment $[f(a),f(b)]$ ${\ displaystyle [f (a), f (b)]}$ .

Properties

The composition of injections and surjections , giving a bijection.

Function $f\colon X\to Y$ ${\ displaystyle f \ colon X \ to Y}$ is bijective if and only if there is an inverse function $f^{-1}\colon Y\to X$ ${\ displaystyle f ^ {- 1} \ colon Y \ to X}$ such that

\forall x\in X\;f^{-1}(f(x))=x

{\ displaystyle \ forall x \ in X \; f ^ {- 1} (f (x)) = x}

and

\forall y\in Y\;f(f^{-1}(y))=y.

{\ displaystyle \ forall y \ in Y \; f (f ^ {- 1} (y)) = y.}

If functions $f$ ${\ displaystyle f}$ and $g$ ${\ displaystyle g}$ bijective, then the composition of functions $g\circ f$ ${\ displaystyle g \ circ f}$ bijective, in this case $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$ ${\ displaystyle (g \ circ f) ^ {- 1} = f ^ {- 1} \ circ g ^ {- 1}}$ . Briefly: the composition of bijections is a bijection. The reverse, however, is incorrect: if $g\circ f$ ${\ displaystyle g \ circ f}$ bijective, then we can only say that $f$ ${\ displaystyle f}$ injective, and $g$ ${\ displaystyle g}$ surjective.

Applications

In computer science

One-to-one connection between relational database tables based on primary keys .

Notes

Literature

N. K. Vereshchagin, A. Shen. Part 1. Beginning of the theory of sets // Lectures on mathematical logic and theory of algorithms. - 2nd ed., Corr. - M .: MTSNMO , 2002. - 128 p.
Ershov Yu. L., Palyutin E. A. Mathematical Logic: Study Guide. - 3rd, stereotype. ed. - SPb: Lan, 2004. - 336 p.