Inline videos. See also:Category: Articles with embedded Videos..

Bijection, injection and surjection

From Biocrawler, the free encyclopedia.

(Redirected from Surjective)

In mathematics, the injection, surjection and bijection are classes of function distinguished by the manner in which arguments and images are mapped. An injection maps distinct arguments (input) only to unique images (output valuess). A surjection maps at least one input to all possible images. A bijection is a function that is both injective and surjective. The four possible combinations of injective and surjective features are illustrated in the following illustrations.

Injective and surjective (bijective)	Injective and non-surjective
Non-injective and surjective	Non-injective and non-surjective

Contents

4.1 Injective and surjective (bijective)
4.2 Injective and non-surjective
4.3 Non-injective and surjective
4.4 Non-injective and non-surjective

5 Properties

6 Category theory

7 See also

[edit]

Injection

An injection, injective function or one-to-one function is a function which maps distinct arguments to distinct images. More formally a function f : A → B is injective if, for every x and y in its domain A, if x $\ne$ y then also f(x) $\ne$ f(y). Thus at most one argument is mapped to any possible image. Since trivially every function is surjective when its codomain is restricted to its range, every injection is actually a bijection to its range and thus there exists an inverse from its range to its domain. The composition of two injections is again an injection, but if the composition of two functions is an injection, then it can only be concluded that the first applied is injective, since its entire image must be included in the domain of the second, which may be non-injective on a part of its domain which is not in the range of the first.

[edit]

Surjection

A surjection, surjective function or onto function is a function which maps to all possible images. More formally a function f : A → B is surjective if, for every y in its codomain B, there exists an x in its domain A such that f(x)=y. Put another way, a function is surjective if its range is equal to its codomain, or equivalently, if every element in the codomain has non-empty preimage. Thus at least one argument is mapped to any possible image. The composition of two surjections is again a surjection, but if the composition of two functions is a surjection, then it can only be concluded that the second applied is surjective.

[edit]

Bijection

A bijection or bijective function is per definition a function that is both injective (one-to-one) and surjective (onto). A bijection associates each possible image with exactly one argument. More formally, a function f: A → B is bijective if for every y in its codomain B, there exists exactly one x in its domain A such that f(x) = y. We can use this property to define a new function which maps each image to its unique preimage. This function is the (two-sided) inverse. The composition of two bijections is again a bijection, but if the composition of two functions is a bijection, then it can only be concluded that the first applied is injective and that the second applied is surjective. The bijections from a set to itself form a group under composition, called the symmetric group.

[edit]

Cardinal numbers

Suppose you want to define what it means for two sets to have the same number of elements. Surely if you can pair off each element of the first set with an element of the second set, then they must have the same number of elements. Accordingly, for two sets to have the same number of elements is defined to mean that there exists a bijection between them. The equivalence classes of this equivalence relation are called cardinal numbers.

[edit]

Examples

It is important to specify the domain and codomain of each function since by changing these, functions which we think of as the same may have different jectivity.

[edit]

Injective and surjective (bijective)

For every set A the identity function id_A and thus specifically $\mathbf{R} \to \mathbf{R} : x \mapsto x$ .
$\mathbf{R}^+ \to \mathbf{R}^+ : x \mapsto x^2$ and thus also its inverse $\mathbf{R}^+ \to \mathbf{R}^+ : x \mapsto \sqrt{x}$
The exponential function $\exp : \mathbf{R} \to \mathbf{R}^+ : x \mapsto \mathrm{e}^x$ and thus also its inverse the natural logarithm $\ln : \mathbf{R}^+ \to \mathbf{R}^+ : x \mapsto \ln{x}$

[edit]

Injective and non-surjective

The exponential function $\exp : \mathbf{R} \to \mathbf{R} : x \mapsto \mathrm{e}^x$

[edit]

Non-injective and surjective

$\mathbf{R} \to \mathbf{R} : x \mapsto (x-1)x(x+1) = x^3 - x$

[edit]

Non-injective and non-surjective

$\mathbf{R} \to \mathbf{R} : x \mapsto x^2$

[edit]

Properties

For every function f, subset A of the domain and subset B of the codomain we have A ⊂ f⁻¹(fA) and f(f⁻¹B) ⊂ B. If f is injective we have A = f⁻¹(fA) and if f is surjective we have f(f⁻¹B) = B.
For every function h : A → C we can define a surjection H : A → h(A) : a → h(a) and an injection I : h(A) → C : a → a. It follows that h = I o H. This decomposition is unique up to isomorphism.