INJECTIVE FUNCTION

(Redirected from One-to-one)




In mathematics, an 'injective function' is a function which associates distinct arguments to distinct values. More precisely, a function ''f'' is said to be 'injective' if it maps distinct ''x'' in the domain to distinct ''y'' in the codomain, such that ''f''(''x'') = ''y''.
Put another way, ''f'' is injective if ''f''(''a'') = ''f''(''b'') implies ''a'' = ''b'' (or ''a'' ≠ ''b'' implies ''f''(''a'') ≠ ''f''(''b'')), for any ''a'', ''b'' in the domain.
An injective function is called an 'injection', and is also said to be an 'information-preserving' or 'one-to-one function' (however, the latter name is best avoided, since some authors understand it to mean a ''one-to-one correspondence'', i.e. a bijective function).
A function ''f'' that is ''not'' injective is sometimes called 'many-to-one'. However, this name too is best avoided, since it is sometimes used to mean "single-valued", i.e. each argument is mapped to at most one value.

Contents

Examples and counter-examples

Injections can be undone

Injections may be made invertible

Other properties

Category theory view

See also

Examples and counter-examples

★ For any set ''X'', the identity function on ''X'' is injective.

★ The function ''f'' : 'R' → 'R' defined by ''f''(''x'') = 2''x'' + 1 is injective.

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

★ The exponential function $exp\; :\; mathbf\{R\}\; o\; mathbf\{R\}^+\; :\; x\; mapsto\; mathrm\{e\}^x$ is injective.

★ The natural logarithm function $ln\; :\; (0,+infty)\; o\; mathbf\{R\}\; :\; x\; mapsto\; ln\{x\}$ is injective.

★ The function ''g'' : 'R' → 'R' defined by $g(x)\; =\; x^n\; -\; x$ is not injective, since, for example, ''g''(0) = ''g''(1).
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.

Injections can be undone

Functions with left inverses (often called sections)
are always injections. That is to say, for ''f'' : ''X'' → ''Y'', if there exists a function ''g'' : ''Y'' → ''X'' such that, for every $x\; in\; X$
:$g(f(x))\; =\; x\; ,$ (''f'' can be undone by ''g'')
then ''f'' is injective. Conversely, it is usually assumed that every injection with non-empty domain has a left inverse.
Note that ''g'' may not be a complete inverse of ''f'' because the composition in the other order, ''f'' o ''g'', may not be the identity on ''Y''. In other words, a function that can be undone or "''reversed''", such as ''f'', is not necessarily invertible (bijective). Injections are "''reversible''" but not always invertible.

Injections may be made invertible

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''). That is, let ''g'' : ''X'' → ''J'' such that ''g''(''x'') = ''f''(''x'') for all ''x'' in ''X''; then ''g'' is bijective. Indeed, ''f'' can be factored as incl_''J'',''Y''o''g'', where incl_''J'',''Y''is the inclusion function from ''J'' into ''Y''.

Other properties

★ If ''f'' and ''g'' are both injective, then ''f'' o ''g'' is injective.


★ If ''g'' o ''f'' is injective, then ''f'' is injective (but ''g'' need not be).

★ ''f'' : ''X'' → ''Y'' is injective if and only if, given any functions ''g'', ''h'' : ''W'' → ''X'', whenever ''f'' o ''g'' = ''f'' o ''h'', then ''g'' = ''h''.

★ 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'').

★ If ''f'' : ''X'' → ''Y'' is injective and ''A'' and ''B'' are both subsets of ''X'', then ''f''(''A'' ∩ ''B'') = ''f''(''A'') ∩ ''f''(''B'').

★ Every function ''h'' : ''W'' → ''Y'' can be decomposed as ''h'' = ''f'' o ''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''.

★ If ''f'' : ''X'' → ''Y'' is an injective function, then ''Y'' has at least as many elements as ''X'', in the sense of cardinal numbers.

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

★ Every embedding is injective.

Category theory view

In the language of category theory, injective functions are precisely the monomorphisms in the category of sets.

See also

★ surjective function

★ injective module

★ monomorphism

★ Horizontal line test

★ Injective metric space