NationMaster - Encyclopedia: Bijection, injection and surjection

In mathematics and related technical fields, the term map or mapping is often a synonym for function. Along these lines, a partial map is a partial function, and a total map is a total function. Mathematics is often defined as the study of topics such as quantity, structure, space, and change. ... Look up Synonym on Wiktionary, the free dictionary Synonyms (in ancient Greek syn ÏƒÏ…Î½ = plus and onoma ÏŒÎ½Î¿Î¼Î± = name) are different words with similar or identical meanings and are interchangable. ... In mathematics, a function returns a unique output for a given input. ... This article needs to be cleaned up to conform to a higher standard of quality. ... In mathematics and computer science, a partial function from the domain X to the codomain Y is a binary relation over X and Y which associates with every element in the set X at most one element in the set Y. If a partial function associates with every element in...

In many specific branches of mathematics, the term is used for a function with a specific property relevant to that branch, such as a continuous function in topology, a linear transformation in linear algebra, etc. In mathematics, a continuous function is a function in which arbitrarily small changes in the input produce arbitrarily small changes in the output. ... Topology (Greek topos, place and logos, study) is a branch of mathematics concerned with spatial properties preserved under bicontinuous deformation (stretching without tearing or gluing); these are the topological invariants. ... In mathematics, a linear transformation (also called linear operator <<wrong! operators are LTs on the same vector space or linear map) is a function between two vector spaces that preserves the operations of vector addition and scalar multiplication. ... Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (or linear spaces), linear transformations, and systems of linear equations. ...

Sets of maps with special properties are the subjects of many important theories: see for instance Lie group, mapping class group, permutation group. This article needs a better explanation of technical details or more context regarding applications or importance to make it more accessible to a general audience, or at least to technical readers outside this specialty. ... In mathematics, in the sub-field of geometric topology, the mapping class group is an important algebraic invariant of a topological space. ... In mathematics, a permutation group is a group G whose elements are permutations of a given set M, and whose operation is the composition of permutations in G (which are thought of as bijective functions from the set M to itself); the relationship is often written as (G,M). ...

In formal logic, the term is sometimes used for a functional predicate, whereas a function is a model of such a predicate in set theory. Logic (from ancient Greek λόγος (logos), meaning reason) is the study of arguments. ... In formal logic and related branches of mathematics, a functional predicate, or function symbol, is a logical symbol that may be applied to an object term to produce another object term. ... In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the models which underlie mathematical systems. ... In mathematics, a predicate is a relation. ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ...

A mapping m which has domain A and codomain B can be denoted symbolically as In mathematics, the domain of a function is the set of all input values to the function. ... A codomain in mathematics is the set of output values associated with (or mapped to) the domain of inputs in a function. ...

If element a belongs to the domain A and if element b belongs to the codomain B and if mapping m maps element a to element b, this can be denoted symbolically as

$m : a mapsto b$ ,

"m maps a to b", which means the same as m(a) = b, "function m of a is b", in function notation. In such case, element b can be referred to as the image of element a. In mathematics, the image of an element x in a set X under the function f : X â†’ Y, denoted by f(x), is the unique y in Y that is associated with x. ...

For any element a in a mapping's domain, a has one and only one image. That is, there exists a b such that $m : a mapsto b$ and if then b = c. A principle, especially in software development, that values avoiding the hazards of redundancy. ...

A mapping's domain and codomain are uniquely defined, so that if m : A → B is some mapping, and if n : B ↪ C is an inclusion mapping, C being a proper superset of B, then the mapping n o m which is their composite is a different mapping from m. In mathematics, inclusion is a partial order on sets. ... In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ...

1 Classes of Map
2 See also

Classes of Map

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. Mathematics is often defined as the study of topics such as quantity, structure, space, and change. ... In mathematics, a function returns a unique output for a given input. ... A parameter is a measurement or value on which something else depends. ... An expression in the very basic sense is the noun form of the verb express. ... In mathematics, the domain of a function is the set of all input values to the function. ... In mathematics, the image of an element x in a set X under the function f : X â†’ Y, denoted by f(x), is the unique y in Y that is associated with x. ... A codomain in mathematics is the set of output values associated with (or mapped to) the domain of inputs in a function. ...

A function $f: ; A to B$ is injective (one-to-one) if or, equivalently, if $x ne y ; to ; f(x) ne f(y)$ . One could also say that elements of the codomain (sometimes called range by mistake) are 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.) In mathematics, the domain of a function is the set of all input values to the function. ... A codomain in mathematics is the set of output values associated with (or mapped to) the domain of inputs in a function. ... In mathematics, the range of a function is the set of all output values produced by that function. ... â†” â‡” â‰¡ logical symbols representing iff. ...

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.

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

A bijection. ... A bijection. ... Image File history File links Diagram to illustrate a function that is an injection but not a surjection. ... Image File history File links Diagram to illustrate a function that is an injection but not a surjection. ... Image File history File links A diagram illustrating a function that is not injective but is surjective. ... Image File history File links A diagram illustrating a function that is not injective but is surjective. ... Image File history File links A diagram illustrating a function neither injective nor surjective. ... Image File history File links A diagram illustrating a function neither injective nor surjective. ...

Injective

Injective composition: the second function need not be injective.

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. Image File history File links An illustration of two functions/mappings: the left is an injective and non-surjective function, the right is neither injective nor surjective. ... Image File history File links An illustration of two functions/mappings: the left is an injective and non-surjective function, the right is neither injective nor surjective. ...

The function $f: A to B$ is injective iff for all $a,b in A$ , we have $f(a) = f(b) Rarr a = b.$

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.

â†” â‡” â‰¡ For other possible meanings of iff, see IFF. In mathematics, philosophy, logic and technical fields that depend on them, iff is used as an abbreviation for if and only if. Common alternative phrases to iff or if and only if include Q is necessary and sufficient for P and P... A codomain in mathematics is the set of output values associated with (or mapped to) the domain of inputs in a function. ... In mathematics, the range of a function is the set of all output values produced by that function. ... In mathematics, an embedding (or imbedding) is one instance of some mathematical object contained within another instance, such as a group that is a subgroup. ...

Surjective

Surjective composition: the first function need not be surjective.

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. Image File history File links An illustration of two functions/mappings: the left is neither injective nor surjective and the right is non-injective and surjective. ... Image File history File links An illustration of two functions/mappings: the left is neither injective nor surjective and the right is non-injective and surjective. ... In mathematics, the image of an element x in a set X under the function f : X → Y, denoted by f(x), is the unique y in Y that is associated with x. ...

The function $f: A to B$ is surjective iff for all $b in B$ , there is $a in A$ such that

f (a) = b .

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

Bijective

Bijective composition: the first function need not be surjective and the second function need not be injective.

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. Image File history File links An illustration of two functions/mappings: the left is injective and non-surjective and the right is non-injective and surjective. ... Image File history File links An illustration of two functions/mappings: the left is injective and non-surjective and the right is non-injective and surjective. ... â†” â‡” â‰¡ logical symbols representing iff. ...

The function $f: A to B$ is bijective iff for all $b in B$ , there is a unique $a in A$ such that

f (a) = b .

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.

â†” â‡” â‰¡ For other possible meanings of iff, see IFF. In mathematics, philosophy, logic and technical fields that depend on them, iff is used as an abbreviation for if and only if. Common alternative phrases to iff or if and only if include Q is necessary and sufficient for P and P... In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ... In mathematics, the symmetric group on a set X, denoted by SX or Sym(X), is the group whose underlying set is the set of all bijective functions from X to X, in which the group operation is that of composition of functions, i. ...

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. In mathematics, the cardinality of a set is a measure of the number of elements of the set. There are two approaches to cardinality â€“ one which compares sets directly using bijections, injections, and surjections, and another which uses cardinal numbers. ...

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.

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}$

The exponential function is one of the most important functions in mathematics. ... The natural logarithm, invented by John Napier, is the logarithm to the base e, where e is equal to 2. ...

Injective and non-surjective

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

Non-injective and surjective

$mathbf{R} to mathbf{R} : x mapsto (x-1)x(x+1) = x^3 - x$
$mathbf{R} to [-1,1] : x mapsto sin(x)$

Non-injective and non-surjective

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

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.

In mathematics, the term up to xxxx is used to describe a situation in which members of an equivalence class can be regarded as a single entity for some purpose. ...

Category theory

In the category of sets, injections, surjections, and bijections correspond precisely to monomorphisms, epimorphisms, and isomorphisms, respectively. The word category (plural categories; from Greek κατηγορια meaning assertion or accusation, hence categorical denial) has several meanings: it is used informally to mean a class of things, as in the category of all living things. See categorization. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In the context of abstract algebra or universal algebra, a monomorphism is simply an injective homomorphism. ... In the context of abstract algebra or universal algebra, an epimorphism is simply a homomorphism onto or surjective homomorphism. ... In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of mapping between objects, devised by Eilhard Mitscherlich, which shows a relation between two properties or operations. ...

History

This terminology was originally coined by the Bourbaki group. Nicolas Bourbaki is the pseudonym under which a group of mainly French 20th-century mathematicians wrote a series of books of exposition of modern advanced mathematics, beginning in 1935. ...

Contents

Classes of Map GA_googleFillSlot("encyclopedia_square");