HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, injections, surjections, and bijections are classes of functions distinguished by the manner in which '' arguments'' (input expressions from the
domain Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined ** Domain of definition of a partial function ** Natural domain of a partial function **Domain of holomorphy of a function * ...
) and '' images'' (output expressions from the
codomain In mathematics, the codomain or set of destination of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation . The term range is sometimes ambiguously used to refer to either th ...
) are related or ''mapped to'' each other. A function
maps A map is a symbolic depiction emphasizing relationships between elements of some space, such as objects, regions, or themes. Many maps are static, fixed to paper or some other durable medium, while others are dynamic or interactive. Although ...
elements from its domain to elements in its codomain. Given a function f \colon X \to Y: *The function is
injective In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
, or one-to-one, if each element of the codomain is mapped to by ''at most'' one element of the domain, or equivalently, if distinct elements of the domain map to distinct elements in the codomain. An injective function is also called an injection. Notationally: ::\forall x, x' \in X, f(x) = f(x') \implies x = x', :or, equivalently (using logical transposition), ::\forall x,x' \in X, x \neq x' \implies f(x) \neq f(x'). *The function is
surjective In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element o ...
, or onto, if each element of the codomain is mapped to by ''at least'' one element of the domain. That is, the image and the codomain of the function are equal. A surjective function is a surjection. Notationally: ::\forall y \in Y, \exists x \in X \text y = f(x). *The function is
bijective In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
(one-to-one and onto, one-to-one correspondence, or invertible) if each element of the codomain is mapped to by ''exactly'' one element of the domain. That is, the function is ''both'' injective and surjective. A bijective function is also called a bijection. That is, combining the definitions of injective and surjective, ::\forall y\in Y, \exists! x\in X \text y=f(x), :where \exists! x means "there exists exactly one ". *In any case (for any function), the following holds: ::\forall x\in X, \exists! y\in Y \text y=f(x). 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 adjacent diagrams.


Injection

A function is injective (one-to-one) if each 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. :The function f \colon X \to Y is injective, if for all x,x' \in X, f(x) = f(x') \Rarr x = x'. The following are some facts related to injections: *A function f \colon X \to Y is injective
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bic ...
X is empty or f is left- invertible; that is, there is a function g \colon f(X) \to X such that g\circ f= identity function on ''X''. Here, f(X) is the image of f. *Since every function is surjective when its
codomain In mathematics, the codomain or set of destination of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation . The term range is sometimes ambiguously used to refer to either th ...
is restricted to its
image An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensio ...
, every injection induces a bijection onto its image. More precisely, every injection f \colon X \to Y can be factored as a bijection followed by an inclusion as follows. Let f_\colon X\rightarrow f(X) be f with codomain restricted to its image, and let i \colon f(X) \to Y be the inclusion map from f(X) into Y. Then f=i\circ f_. A dual factorization is given for surjections below. *The composition of two injections is again an injection, but if g\circ f is injective, then it can only be concluded that f is injective (see figure). *Every
embedding In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup. When some object X is said to be embedded in another object Y, the embedding is g ...
is injective.


Surjection

A function is ''surjective'' or ''onto'' if each element of the
codomain In mathematics, the codomain or set of destination of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation . The term range is sometimes ambiguously used to refer to either th ...
is mapped to by at least one element of the
domain Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined ** Domain of definition of a partial function ** Natural domain of a partial function **Domain of holomorphy of a function * ...
. In other words, each element of the codomain has non-empty
preimage In mathematics, the image of a function is the set of all output values it may produce. More generally, evaluating a given function f at each element of a given subset A of its domain produces a set, called the "image of A under (or through) ...
. Equivalently, a function is surjective if its image is equal to its codomain. A surjective function is a ''surjection''. The formal definition is the following. :The function f \colon X \to Y is surjective, if for all y \in Y, there is x \in X such that f(x) = y. The following are some facts related to surjections: *A function f \colon X \to Y is surjective if and only if it is right-invertible, that is, if and only if there is a function g \colon Y \to X such that f\circ g= identity function on Y. (This statement is equivalent to the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
.) *By collapsing all arguments mapping to a given fixed image, every surjection induces a bijection from a
quotient set In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
of its domain to its codomain. More precisely, the preimages under ''f'' of the elements of the image of f are the
equivalence classes In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
of an
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relatio ...
on the domain of f, such that ''x'' and ''y'' are equivalent if and only they have the same image under f. As all elements of any one of these equivalence classes are mapped by ''f''on the same element of the codomain, this induces a bijection between the
quotient set In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
by this equivalence relation (the set of the equivalence classes) and the image of f (which is its codomain when f is surjective). Moreover, ''f'' is the composition of the canonical projection from ''f'' to the quotient set, and the bijection between the quotient set and the codomain of f. *The composition of two surjections is again a surjection, but if g\circ f is surjective, then it can only be concluded that g is surjective (see figure).


Bijection

A function is ''bijective'' if it is both injective and surjective. A bijective function is also called a ''bijection'' or a ''one-to-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 follow. :The function f \colon X \to Y is bijective, if for all y \in Y, there is a unique x \in X such that f(x) = y. The following are some facts related to bijections: *A function f \colon X \to Y is bijective if and only if it is invertible, that is, there is a function g \colon Y \to X such that g\circ f= identity function on ''X'' and f\circ g= identity function on Y. This function maps each image to its unique preimage. *The composition of two bijections is again a bijection, but if g\circ 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 In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group ...
.


Cardinality

Suppose that one wants 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, one can define two sets to "have the same number of elements"—if there is a bijection between them. In which case, the two sets are said to have the same
cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
. Likewise, one can say that set X "has fewer than or the same number of elements" as set Y, if there is an injection from X to Y; one can also say that set X "has fewer than the number of elements" in set Y, if there is an injection from X to Y, but not a bijection between X and Y.


Examples

It is important to specify the domain and codomain of each function, since by changing these, functions which appear to be the same may have different properties. ;Injective and surjective (bijective) : The identity function id''X'' for every non-empty set ''X'', and thus specifically \mathbf \to \mathbf : x \mapsto x. : \mathbf^+ \to \mathbf^+ : x \mapsto x^2 , and thus also its inverse \mathbf^+ \to \mathbf^+ : x \mapsto \sqrt. : The
exponential function The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, ...
\exp \colon \mathbf \to \mathbf^+ : x \mapsto \mathrm^x (that is, the exponential function with its codomain restricted to its image), and thus also its inverse the
natural logarithm The natural logarithm of a number is its logarithm to the base of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...
\ln \colon \mathbf^+ \to \mathbf : x \mapsto \ln. ;Injective and non-surjective : The exponential function \exp \colon \mathbf \to \mathbf : x \mapsto \mathrm^x. ;Non-injective and surjective :\mathbf \to \mathbf : x \mapsto (x-1)x(x+1) = x^3 - x . :\mathbf \to 1,1: x \mapsto \sin(x). ;Non-injective and non-surjective :\mathbf \to \mathbf: x \mapsto \sin(x).


Properties

* For every function , subset of the domain and subset of the codomain, and . If is injective, then , and if is surjective, then . * For every function , one can define a surjection and an injection . It follows that . This decomposition is unique
up to Two mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R'' * if ''a'' and ''b'' are related by ''R'', that is, * if ''aRb'' holds, that is, * if the equivalence classes of ''a'' and ''b'' with respect to ''R'' ...
isomorphism In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
.


Category theory

In the
category Category, plural categories, may refer to: Philosophy and general uses *Categorization, categories in cognitive science, information science and generally * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) ...
of sets, injections, surjections, and bijections correspond precisely to monomorphisms, epimorphisms, and
isomorphism In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
s, respectively.


History

The
Oxford English Dictionary The ''Oxford English Dictionary'' (''OED'') is the first and foundational historical dictionary of the English language, published by Oxford University Press (OUP). It traces the historical development of the English language, providing a c ...
records the use of the word ''injection'' as a noun by S. Mac Lane in ''
Bulletin of the American Mathematical Society The ''Bulletin of the American Mathematical Society'' is a quarterly mathematical journal published by the American Mathematical Society. Scope It publishes surveys on contemporary research topics, written at a level accessible to non-experts. ...
'' (1950), and ''injective'' as an adjective by Eilenberg and Steenrod in ''Foundations of Algebraic Topology'' (1952). However, it was not until the French
Bourbaki group Nicolas Bourbaki () is the collective pseudonym of a group of mathematicians, predominantly French alumni of the École normale supérieure - PSL (ENS). Founded in 1934–1935, the Bourbaki group originally intended to prepare a new textbook ...
coined the injective-surjective-bijective terminology (both as nouns and adjectives) that they achieved widespread adoption.{{Cite book , last=Mashaal , first=Maurice , url=https://books.google.com/books?id=-CXn6y_1nJ8C&q=bijective%2C+surjective+injective+bourbaki&pg=PA106 , title=Bourbaki , date=2006 , publisher=American Mathematical Soc. , isbn=978-0-8218-3967-6 , pages=106 , language=en


See also

* Horizontal line test *
Injective module In mathematics, especially in the area of abstract algebra known as module theory, an injective module is a module ''Q'' that shares certain desirable properties with the Z-module Q of all rational numbers. Specifically, if ''Q'' is a submodule o ...
*
Permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pro ...


References


External links


Earliest Uses of Some of the Words of Mathematics: entry on Injection, Surjection and Bijection has the history of Injection and related terms.
Basic concepts in set theory Mathematical relations Functions and mappings