Bijection injection and surjection: Encyclopedia - Bijection injection and surjection

Bijection, injection and surjection

In mathematics, injections, surjections and bijections are classes of functions distinguished by the manner in which arguments (input expressions from the domain) and images (output expressions from the codomain) are related or mapped to each other.

• A function is injective (one-to-one) if or, equivalently, if . One could also say that every element of the codomain (sometimes called range) is mapped to by at most one element (argument) of the domain; not every element of the codomain, however, need have an argument mapped to it. An injective function is an injection.
• A function is surjective (onto) if every element of the codomain is mapped to by some element (argument) of the domain; some images may be mapped to by more than one argument. (Equivalently, a function where the range is equal to the codomain.) A surjective function is a surjection.
• A function is bijective (one-to-one and onto) if and only if (iff) it is both injective and surjective. (Equivalently, every element of the codomain is mapped to by exactly one element of the domain.) A bijective function is a bijection (one-to-one correspondence).

(Note: a one-to-one function is injective, but may fail to be surjective, while a one-to-one correspondence is both injective and surjective.)

An injective function need not be surjective (not all elements of the codomain may be associated with arguments), and a surjective function need not be injective (some images may be associated with more than one argument). The four possible combinations of injective and surjective features are illustrated in the following diagrams.

Bijection injection and surjection - Injection

A function is injective (one-to-one) if every possible element of the codomain is mapped to by at most one argument. Equivalently, a function is injective if it maps distinct arguments to distinct images. An injective function is an injection. The formal definition is the following.

• A function f : A → B is injective if and only if A is empty or f is left-invertible, that is, there is a function g: B → A such that g o f = identity function on A.
• Since every function is surjective when its codomain is restricted to its range, every injection induces a bijection onto its range. More precisely, every injection f : A → B can be factored as a bijection followed by an inclusion as follows. Let f_R : A → f(A) be f with codomain restricted to its image, and let i : f(A) → B be the inclusion map from f(A) into B. Then f = i o f_R. A dual factorisation is given for surjections below.
• The composition of two injections is again an injection, but if g o f is injective, then it can only be concluded that f is injective. See the figure at right.
• Every embedding is injective.

Bijection injection and surjection - Surjection

A function is surjective (onto) if every possible image is mapped to by at least one argument. In other words, every element in the codomain has non-empty preimage. Equivalently, a function is surjective if its range is equal to its codomain. A surjective function is a surjection. The formal definition is the following.

• A function f : A → B is surjective if and only if it is right-invertible, that is, if and only if there is a function g: B → A such that f o g = identity function on B. (This statement is equivalent to the axiom of choice.)
• By collapsing all arguments mapping to a given fixed image, every surjection induces a bijection defined on a quotient of its domain. More precisely, every surjection f : A → B can be factored as a projection followed by a bijection as follows. Let A/~ be the equivalence classes of A under the following equivalence relation: x ~ y if and only if f(x) = f(y). Equivalently, A/~ is the set of all preimages under f. Let P(~) : A → A/~ be the projection map which sends each x in A to its equivalence class [x]_~, and let f_P : A/~ → B be the well-defined function given by f_P([x]_~) = f(x). Then f = f_P o P(~). A dual factorisation is given for injections above.
• The composition of two surjections is again a surjection, but if g o f is surjective, then it can only be concluded that g is surjective. See the figure at right*.

Bijection injection and surjection - Bijection

A function is bijective if it is both injective and surjective. A bijective function is a bijection (one-one correspondence). A function is bijective if and only if every possible image is mapped to by exactly one argument. This equivalent condition is formally expressed as follows.

• A function f : A → B is bijective if and only if it is invertible, that is, there is a function g: B → A such that g o f = identity function on A and f o g = identity function on B. This function maps each image to its unique preimage.
• The composition of two bijections is again a bijection, but if g o f is a bijection, then it can only be concluded that f is injective and g is surjective. (See the figure at right and the remarks above regarding injections and surjections.)
• The bijections from a set to itself form a group under composition, called the symmetric group.

Bijection injection and surjection - Cardinality

Suppose you want to define what it means for two sets to "have the same number of elements". One way to do this is to say that two sets "have the same number of elements" if and only if all the elements of one set can be paired with the elements of the other, in such a way that each element is paired with exactly one element. Accordingly, we can define two sets to "have the same number of elements" if there is a bijection between them. We say that the two sets have the same cardinality.

Bijection injection and surjection - 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.

Bijection injection and surjection - Injective and surjective bijective

• For every set A the identity function id_A and thus specifically .
• and thus also its inverse .
• The exponential function and thus also its inverse the natural logarithm

Bijection injection and surjection - Injective and non-surjective

• The exponential function

Bijection injection and surjection - Non-injective and surjective

• The sine function f(x) = sin x

Bijection injection and surjection - Non-injective and non-surjective

Bijection injection and surjection - 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.

Bijection injection and surjection - Category theory

In the category of sets, injections, surjections, and bijections correspond precisely to monomorphisms, epimorphisms, and isomorphisms, respectively.

Bijection injection and surjection - History

This terminology was originally coined by the Bourbaki group.

See also

• injective module
• permutation
• horizontal line test

Category: Set theory

Adapted from the Wikipedia article "Bijection injection and surjection", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki