Injective function

Last updated

In mathematics, an injective function (also known as injection, or one-to-one function) is a function f that maps distinct elements to distinct elements; that is, f(x1) = f(x2) implies x1 = x2. [1] In other words, every element of the function's codomain is the image of at most one element of its domain. [2] The term one-to-one function must not be confused with one-to-one correspondence that refers to bijective functions, which are functions such that each element in the codomain is an image of exactly one element in the domain.

Contents

A homomorphism 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 spaces, an injective homomorphism is also called a monomorphism . However, in the more general context of category theory, the definition of a monomorphism differs from that of an injective homomorphism. [3] This is thus a theorem that they are equivalent for algebraic structures; see Homomorphism § Monomorphism for more details.

A function that is not injective is sometimes called many-to-one. [2]

Definition

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

Symbolically,

which is logically equivalent to the contrapositive, [4]

Examples

Injective functions. Diagramatic interpretation in the Cartesian plane, defined by the mapping
f
:
X
-
Y
,
{\displaystyle f:X\to Y,}
where
y
=
f
(
x
)
,
{\displaystyle y=f(x),}
X
=
{\displaystyle X=}
domain of function,
Y
=
{\displaystyle Y=}
range of function, and
im
[?]
(
f
)
{\displaystyle \operatorname {im} (f)}
denotes image of
f
.
{\displaystyle f.}
Every one
x
{\displaystyle x}
in
X
{\displaystyle X}
maps to exactly one unique
y
{\displaystyle y}
in
Y
.
{\displaystyle Y.}
The circled parts of the axes represent domain and range sets-- in accordance with the standard diagrams above. Injective function.svg
Injective functions. Diagramatic interpretation in the Cartesian plane, defined by the mapping where domain of function, range of function , and denotes image of Every one in maps to exactly one unique in The circled parts of the axes represent domain and range sets— in accordance with the standard diagrams above.

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 horizontal line test . [2]

Not an injective function. Here
X
1
{\displaystyle X_{1}}
and
X
2
{\displaystyle X_{2}}
are subsets of
X
,
Y
1
{\displaystyle X,Y_{1}}
and
Y
2
{\displaystyle Y_{2}}
are subsets of
Y
{\displaystyle Y}
: for two regions where the function is not injective because more than one domain element can map to a single range element. That is, it is possible for more than one
x
{\displaystyle x}
in
X
{\displaystyle X}
to map to the same
y
{\displaystyle y}
in
Y
.
{\displaystyle Y.} Non-injective function1.svg
Not an injective function. Here and are subsets of and are subsets of : for two regions where the function is not injective because more than one domain element can map to a single range element. That is, it is possible for more than one in to map to the same in
Making functions injective. The previous function
f
:
X
-
Y
{\displaystyle f:X\to Y}
can be reduced to one or more injective functions (say)
f
:
X
1
-
Y
1
{\displaystyle f:X_{1}\to Y_{1}}
and
f
:
X
2
-
Y
2
,
{\displaystyle f:X_{2}\to Y_{2},}
shown by solid curves (long-dash parts of initial curve are not mapped to anymore). Notice how the rule
f
{\displaystyle f}
has not changed - only the domain and range.
X
1
{\displaystyle X_{1}}
and
X
2
{\displaystyle X_{2}}
are subsets of
X
,
Y
1
{\displaystyle X,Y_{1}}
and
Y
2
{\displaystyle Y_{2}}
are subsets of
Y
{\displaystyle Y}
: for two regions where the initial function can be made injective so that one domain element can map to a single range element. That is, only one
x
{\displaystyle x}
in
X
{\displaystyle X}
maps to one
y
{\displaystyle y}
in
Y
.
{\displaystyle Y.} Non-injective function2.svg
Making functions injective. The previous function can be reduced to one or more injective functions (say) and shown by solid curves (long-dash parts of initial curve are not mapped to anymore). Notice how the rule has not changed – only the domain and range. and are subsets of and are subsets of : for two regions where the initial function can be made injective so that one domain element can map to a single range element. That is, only one in maps to one in

Injections can be undone

Functions with left inverses are always injections. That is, given if there is a function such that for every

( can be undone by ), then is injective. In this case, is called a retraction of Conversely, is called a section 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. [5]

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, 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 from into

More generally, injective partial functions are called partial bijections.

Other properties

The composition of two injective functions is injective. Injective composition2.svg
The composition of two injective functions is injective.

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 [6]

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. If every horizontal line intersects the curve of in at most one point, then is injective or one-to-one.

See also

Notes

    1. "The Definitive Glossary of Higher Mathematical Jargon — One-to-One". Math Vault. 2019-08-01. Retrieved 2019-12-07.
    2. 1 2 3 "Injective, Surjective and Bijective". www.mathsisfun.com. Retrieved 2019-12-07.
    3. "Section 7.3 (00V5): Injective and surjective maps of presheaves—The Stacks project". stacks.math.columbia.edu. Retrieved 2019-12-07.
    4. Farlow, S. J. "Injections, Surjections, and Bijections" (PDF). math.umaine.edu. Retrieved 2019-12-06.
    5. Unlike the corresponding statement that every surjective function has a right inverse, this does not require the axiom of choice, as the existence of is implied by the non-emptiness of the domain. However, this statement may fail in less conventional mathematics such as constructive mathematics. In constructive mathematics, the inclusion of the two-element set in the reals cannot have a left inverse, as it would violate indecomposability, by giving a retraction of the real line to the set {0,1}.
    6. Williams, Peter. "Proving Functions One-to-One". Archived from the original on 4 June 2017.

    Related Research Articles

    Bijection Function that is one to one and onto (mathematics)

    In mathematics, a bijection, 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 set, and each element of the other set is paired with exactly one element of the first set. There are no unpaired elements. In mathematical terms, a bijective function f: XY is a one-to-one (injective) and onto (surjective) mapping of a set X to a set Y. The term one-to-one correspondence must not be confused with one-to-one function.

    Equivalence relation Mathematical concept for comparing objects

    In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The relation "is equal to" is the canonical example of an equivalence relation.

    Group homomorphism

    In mathematics, given two groups, and, a group homomorphism from to is a function h : GH such that for all u and v in G it holds that

    In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type. The word homomorphism comes from the Ancient Greek language: ὁμός meaning "same" and μορφή meaning "form" or "shape". However, the word was apparently introduced to mathematics due to a (mis)translation of German ähnlich meaning "similar" to ὁμός meaning "same". The term "homomorphism" appeared as early as 1892, when it was attributed to the German mathematician Felix Klein (1849–1925).

    Inverse function Mathematical concept

    In mathematics, an inverse function is a function that "reverses" another function: if the function f applied to an input x gives a result of y, then applying its inverse function g to y gives the result x, i.e., g(y) = x if and only if f(x) = y. The inverse function of f is also denoted as .

    In mathematics, a partial functionf from a set X to a set Y is a function from a subset S of X to Y. The subset S, that is, the domain of f viewed as a function, is called the domain of definition of f. If S equals X, that is, if f is defined on every element in X, then f is said to be total.

    Ring homomorphism

    In ring theory, a branch of abstract algebra, a ring homomorphism is a structure-preserving function between two rings. More explicitly, if R and S are rings, then a ring homomorphism is a function f : RS such that f is:

    Surjective function Function such that every element has a preimage (mathematics)

    In mathematics, a surjective function is a function f that maps an element x to every element y; that is, for every y, there is an x such that f(x) = y. In other words, every element of the function's codomain is the image of at least one element of its domain. It is not required that x be unique; the function f may map one or more elements of X to the same element of Y.

    Codomain Target set of a mathematical function

    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 Y in the notation f: XY. The term range is sometimes ambiguously used to refer to either the codomain or image of a function.

    In category theory, an epimorphism is a morphism f : XY that is right-cancellative in the sense that, for all objects Z and all morphisms g1, g2: YZ,

    Function (mathematics) Mapping that associates a single output value to each input

    In mathematics, a function is a binary relation between two sets that associates each element of the first set to exactly one element of the second set. Typical examples are functions from integers to integers, or from the real numbers to real numbers.

    In mathematics, more specifically topology, a local homeomorphism is a function between topological spaces that, intuitively, preserves local structure. If is a local homeomorphism, is said to be an étale space over Local homeomorphisms are used in the study of sheaves. Typical examples of local homeomorphisms are covering maps.

    In mathematics, more specifically in topology, an open map is a function between two topological spaces that maps open sets to open sets. That is, a function is open if for any open set in the image is open in Likewise, a closed map is a function that maps closed sets to closed sets. A map may be open, closed, both, or neither; in particular, an open map need not be closed and vice versa.

    In mathematics, especially in the field of category theory, the concept of injective object is a generalization of the concept of injective module. This concept is important in cohomology, in homotopy theory and in the theory of model categories. The dual notion is that of a projective object.

    In algebra, a module homomorphism is a function between modules that preserves the module structures. Explicitly, if M and N are left modules over a ring R, then a function is called an R-module homomorphism or an R-linear map if for any x, y in M and r in R,

    Image (mathematics) Set of all values of a function

    In mathematics, the image of a function is the set of all output values it may produce.

    In category theory, a faithful functor is a functor that is injective when restricted to each set of morphisms that have a given source and target.

    Bijection, injection and surjection Properties of mathematical functions

    In mathematics, injections, surjections, and bijections are classes of functions distinguished by the manner in which arguments and images are related or mapped to each other.

    In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms are functions; in linear algebra, linear transformations; in group theory, group homomorphisms; in topology, continuous functions, and so on.

    References