Injective function

From Wikipedia for FEVERv2
Jump to navigation Jump to search

"Injective" redirects here. Injective function_sentence_0

For injective modules, see Injective module. Injective function_sentence_1

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 of its codomain. Injective function_sentence_2

In other words, every element of the function's codomain is the image of at most one element of its domain. Injective function_sentence_3

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. Injective function_sentence_4

A homomorphism between algebraic structures is a function that is compatible with the operations of the structures. Injective function_sentence_5

For all common algebraic structures, and, in particular for vector spaces, an injective homomorphism is also called a monomorphism. Injective function_sentence_6

However, in the more general context of category theory, the definition of a monomorphism differs from that of an injective homomorphism. Injective function_sentence_7

This is thus a theorem that they are equivalent for algebraic structures; see Homomorphism § Monomorphism for more details. Injective function_sentence_8

A function f that is not injective is sometimes called many-to-one. Injective function_sentence_9

Definition Injective function_section_0

Further information on notation: Function (mathematics) § Notation Injective function_sentence_10

Let f be a function whose domain is a set X. Injective function_sentence_11

The function f is said to be injective provided that for all a and b in X, whenever f(a) = f(b), then a = b; that is, f(a) = f(b) implies a = b.  Equivalently, if a ≠ b, then f(a) ≠ f(b). Injective function_sentence_12

Symbolically, Injective function_sentence_13

which is logically equivalent to the contrapositive, Injective function_sentence_14

Examples Injective function_section_1

Injective function_unordered_list_0

  • For any set X and any subset S of X, the inclusion map S → X (which sends any element s of S to itself) is injective. In particular, the identity function X → X is always injective (and in fact bijective).Injective function_item_0_0
  • If the domain X = or X has only one element, then the function X → Y is always injective.Injective function_item_0_1
  • The function f : R → R defined by f(x) = 2x + 1 is injective.Injective function_item_0_2
  • The function g : R → R defined by g(x) = x is not injective, because (for example) g(1) = 1 = g(−1). However, if g is redefined so that its domain is the non-negative real numbers [0,+∞), then g is injective.Injective function_item_0_3
  • The exponential function exp : R → R defined by exp(x) = e is injective (but not surjective, as no real value maps to a negative number).Injective function_item_0_4
  • The natural logarithm function ln : (0, ∞) → R defined by x ↦ ln x is injective.Injective function_item_0_5
  • The function g : R → R defined by g(x) = x − x is not injective, since, for example, g(0) = g(1) = 0.Injective function_item_0_6

More generally, when X and Y are both the real line R, then an injective function f : R → R is one whose graph is never intersected by any horizontal line more than once. Injective function_sentence_15

This principle is referred to as the horizontal line test. Injective function_sentence_16

Injections can be undone Injective function_section_2

Functions with left inverses are always injections. Injective function_sentence_17

That is, given f : X → Y, if there is a function g : Y → X such that for every x ∈ X, Injective function_sentence_18

Injective function_description_list_1

  • g(f(x)) = x (f can be undone by g), then f is injective. In this case, g is called a retraction of f. Conversely, f is called a section of g.Injective function_item_1_7

Conversely, every injection f with non-empty domain has a left inverse g, which can be defined by fixing an element a in the domain of f so that g(x) equals the unique preimage of x under f if it exists and g(x) = a otherwise. Injective function_sentence_19

The left inverse g is not necessarily an inverse of f, because the composition in the other order, f ∘ g, may differ from the identity on Y. Injective function_sentence_20

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. Injective function_sentence_21

Injections may be made invertible Injective function_section_3

In fact, to turn an injective function f : X → Y into a bijective (hence invertible) function, it suffices to replace its codomain Y by its actual range J = f(X). Injective function_sentence_22

That is, let g : X → J such that g(x) = f(x) for all x in X; then g is bijective. Injective function_sentence_23

Indeed, f can be factored as inclJ,Y ∘ g, where inclJ,Y is the inclusion function from J into Y. Injective function_sentence_24

More generally, injective partial functions are called partial bijections. Injective function_sentence_25

Other properties Injective function_section_4

Injective function_unordered_list_2

  • If f and g are both injective, then f ∘ g is injective.Injective function_item_2_8

Injective function_unordered_list_3

  • If g ∘ f is injective, then f is injective (but g need not be).Injective function_item_3_9
  • f : X → Y is injective if and only if, given any functions g, h : W → X whenever f ∘ g = f ∘ h, then g = h. In other words, injective functions are precisely the monomorphisms in the category Set of sets.Injective function_item_3_10
  • If f : X → Y is injective and A is a subset of X, then f(f(A)) = A. Thus, A can be recovered from its image f(A).Injective function_item_3_11
  • If f : X → Y is injective and A and B are both subsets of X, then f(A ∩ B) = f(A) ∩ f(B).Injective function_item_3_12
  • Every function h : W → Y can be decomposed as h = f ∘ g for a suitable injection f and surjection g. This decomposition is unique up to isomorphism, and f may be thought of as the inclusion function of the range h(W) of h as a subset of the codomain Y of h.Injective function_item_3_13
  • If f : X → Y is an injective function, then Y has at least as many elements as X, in the sense of cardinal numbers. In particular, if, in addition, there is an injection from Y to X, then X and Y have the same cardinal number. (This is known as the Cantor–Bernstein–Schroeder theorem.)Injective function_item_3_14
  • If both X and Y are finite with the same number of elements, then f : X → Y is injective if and only if f is surjective (in which case f is bijective).Injective function_item_3_15
  • An injective function which is a homomorphism between two algebraic structures is an embedding.Injective function_item_3_16
  • 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 f is injective can be decided by only considering the graph (and not the codomain) of f.Injective function_item_3_17

Proving that functions are injective Injective function_section_5

A proof that a function f is injective depends on how the function is presented and what properties the function holds. Injective function_sentence_26

For functions that are given by some formula there is a basic idea. Injective function_sentence_27

We use the definition of injectivity, namely that if f(x) = f(y), then x = y. Injective function_sentence_28

Here is an example: Injective function_sentence_29

Injective function_description_list_4

  • f = 2x + 3Injective function_item_4_18

Proof: Let f : X → Y. Injective function_sentence_30

Suppose f(x) = f(y). Injective function_sentence_31

So 2x + 3 = 2y + 3 ⇒ 2x = 2y ⇒ x = y. Injective function_sentence_32

Therefore, it follows from the definition that f is injective. Injective function_sentence_33

There are multiple other methods of proving that a function is injective. Injective function_sentence_34

For example, in calculus if f 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. Injective function_sentence_35

In linear algebra, if f is a linear transformation it is sufficient to show that the kernel of f contains only the zero vector. Injective function_sentence_36

If f 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. Injective function_sentence_37

A graphical approach for a real-valued function f of a real variable x is the horizontal line test. Injective function_sentence_38

If every horizontal line intersects the curve of f(x) in at most one point, then f is injective or one-to-one. Injective function_sentence_39

See also Injective function_section_6

Injective function_unordered_list_5

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: function.