In
mathematics, an injective function (also known as injection, or one-to-one function) is a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
that maps
distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent
contrapositive
In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a statem ...
statement.) In other words, every element of the function's
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 the
image of one element of its
domain.
The term must not be confused with that refers to
bijective function
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 ...
s, which are functions such that each element in the codomain is an image of exactly one element in the domain.
A
homomorphism
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...
between
algebraic structures is a function that is compatible with the operations of the structures. For all common algebraic structures, and, in particular for
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
s, an is also called a . However, in the more general context of
category theory, the definition of a monomorphism differs from that of an injective homomorphism. This is thus a theorem that they are equivalent for algebraic structures; see for more details.
A function
that is not injective is sometimes called many-to-one.
Definition
An injective function
Let
be a function whose domain is a set
The function
is said to be injective provided that for all
and
in
if
then
; that is,
implies
Equivalently, if
then
in the
contrapositive
In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a statem ...
statement.
Symbolically,
which is logically equivalent to the
contrapositive
In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a statem ...
,
Examples
''For visual examples, readers are directed to the
gallery section.''
* For any set
and any subset
the
inclusion map
In mathematics, if A is a subset of B, then the inclusion map (also inclusion function, insertion, or canonical injection) is the function \iota that sends each element x of A to x, treated as an element of B:
\iota : A\rightarrow B, \qquad \iota ...
(which sends any element
to itself) is injective. In particular, the
identity function
Graph of the identity function on the real numbers
In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
is always injective (and in fact bijective).
* If the domain of a function is the
empty set, then the function is the
empty function
In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the functi ...
, which is injective.
* If the domain of a function has one element (that is, it is a
singleton set
In mathematics, a singleton, also known as a unit set or one-point set, is a set with exactly one element. For example, the set \ is a singleton whose single element is 0.
Properties
Within the framework of Zermelo–Fraenkel set theory, the ...
), then the function is always injective.
* The function
defined by
is injective.
* The function
defined by
is injective, because (for example)
However, if
is redefined so that its domain is the non-negative real numbers
, then is injective.
* The exponential function">,+∞), then
is injective.
* The exponential function
defined by
is injective (but not surjective, as no real value maps to a negative number).
* The natural logarithm function
defined by
is injective.
* The function
defined by
is not injective, since, for example,
More generally, when
and
are both the
real line then an injective function
is one whose graph is never intersected by any horizontal line more than once. This principle is referred to as the .
Injections can be undone
Functions with
left inverses are always injections. That is, given
if there is a function
such that for every
,
, then
is injective. In this case,
is called a
retraction of
Conversely,
is called a
section
Section, Sectioning or Sectioned may refer to:
Arts, entertainment and media
* Section (music), a complete, but not independent, musical idea
* Section (typography), a subdivision, especially of a chapter, in books and documents
** Section sig ...
of
Conversely, every injection
with non-empty domain has a left inverse
which can be defined by fixing an element
in the domain of
so that
equals the unique pre-image of
under
if it exists and
otherwise.
The left inverse
is not necessarily an
inverse of
because the composition in the other order,
may differ from the identity on
In other words, an injective function can be "reversed" by a left inverse, but is not necessarily
invertible
In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers.
Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that is ...
, which requires that the function is bijective.
Injections may be made invertible
In fact, to turn an injective function
into a bijective (hence invertible) function, it suffices to replace its codomain
by its actual range
That is, let
such that
for all
; then
is bijective. Indeed,
can be factored as
where
is the
inclusion function
In mathematics, if A is a subset of B, then the inclusion map (also inclusion function, insertion, or canonical injection) is the function \iota that sends each element x of A to x, treated as an element of B:
\iota : A\rightarrow B, \qquad \iota ...
from
into
More generally, injective
partial function
In mathematics, a partial function from a set to a set is a function from a subset of (possibly itself) to . The subset , that is, the domain of viewed as a function, is called the domain of definition of . If equals , that is, if is de ...
s are called
partial bijection
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 ...
s.
Other properties
* If
and
are both injective then
is injective.
* If
is injective, then
is injective (but
need not be).
*
is injective if and only if, given any functions
whenever
then
In other words, injective functions are precisely the
monomorphism
In the context of abstract algebra or universal algebra, a monomorphism is an injective homomorphism. A monomorphism from to is often denoted with the notation X\hookrightarrow Y.
In the more general setting of category theory, a monomorphism ...
s 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) ...
Set of sets.
* If
is injective and
is a
subset of
then
Thus,
can be recovered from its
image
* If
is injective and
and
are both subsets of
then
* Every function
can be decomposed as
for a suitable injection
and surjection
This decomposition is unique
up to isomorphism 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'' ...
, and
may be thought of as the
inclusion function
In mathematics, if A is a subset of B, then the inclusion map (also inclusion function, insertion, or canonical injection) is the function \iota that sends each element x of A to x, treated as an element of B:
\iota : A\rightarrow B, \qquad \iota ...
of the range
of
as a subset of the codomain
of
* If
is an injective function, then
has at least as many elements as
in the sense of
cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. T ...
s. In particular, if, in addition, there is an injection from
to
then
and
have the same cardinal number. (This is known as the
Cantor–Bernstein–Schroeder theorem.)
* If both
and
are
finite
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marke ...
with the same number of elements, then
is injective if and only if
is surjective (in which case
is bijective).
* An injective function which is a homomorphism between two algebraic structures is an
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 ...
.
* Unlike surjectivity, which is a relation between the graph of a function and its codomain, injectivity is a property of the graph of the function alone; that is, whether a function
is injective can be decided by only considering the graph (and not the codomain) of
Proving that functions are injective
A proof that a function
is injective depends on how the function is presented and what properties the function holds.
For functions that are given by some formula there is a basic idea.
We use the definition of injectivity, namely that if
then
Here is an example:
Proof: Let
Suppose
So
implies
which implies
Therefore, it follows from the definition that
is injective.
There are multiple other methods of proving that a function is injective. For example, in calculus if
is a differentiable function defined on some interval, then it is sufficient to show that the derivative is always positive or always negative on that interval. In linear algebra, if
is a linear transformation it is sufficient to show that the kernel of
contains only the zero vector. If
is a function with finite domain it is sufficient to look through the list of images of each domain element and check that no image occurs twice on the list.
A graphical approach for a real-valued function
of a real variable
is the
horizontal line test
In mathematics, the horizontal line test is a test used to determine whether a function is injective (i.e., one-to-one).
In calculus
A ''horizontal line'' is a straight, flat line that goes from left to right. Given a function f \colon \mathbb \t ...
. If every horizontal line intersects the curve of
in at most one point, then
is injective or one-to-one.
Gallery
See also
*
*
*
*
Notes
References
* , p. 17 ''ff''.
* , p. 38 ''ff''.
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.Khan Academy – Surjective (onto) and Injective (one-to-one) functions: Introduction to surjective and injective functions
{{Authority control
Functions and mappings
Basic concepts in set theory
Types of functions