Injective function

Injectivity or links uniqueness is a property of a mathematical function or relation.

It says that each element of the target set is at most once accepted as the function value. No two different elements of the definition of quantity so are mapped to one and the same element of the target set. The image set must be less than the target amount - as is the case for example in the graphic. This makes all the difference to a bijective mapping, in absolutely every element of the target set must correspond to an element of the set of definitions.

An injective function, also referred to as an injection, is a special case of a unique relation to the left.

Definitions

Be and quantities, as well as a mapping from to. The following definitions of injectivity are equivalent:

  • Is called injective if for each to a maximum of one out there with. ( " More than one " means: none or just one, but not more. ) Formal:
  • Is called injective if for the equality of function values ​​( values) in the equality of the function used values ​​follows. Formal:
  • Is called injective if different values ​​are always mapped to unequal values. Formal:

If one uses the third definition to prove the injectivity, this often leads to a proof by contradiction. Direct evidence with the second definition can be more elegant and shorter.

Graphical illustrations

Examples and counter-examples

  • Unmathematisches Example: The function with identity card assigns to each citizen of the Federal Republic of Germany, the number of its current identity card is injective, where as the target amount, the set of all possible identity card numbers is assumed ( because ID numbers are assigned only once ).
  • Denotes the set of the natural and the set of integers.

Properties

  • Note that the injectivity of a function depending only on the function graph (as opposed to surjectivity, which also depends on the target quantity, which can not be read at the function graph ).
  • A function is injective if and only if for all subsets.
  • A function is injective if for all.
  • The functions and injective, this also applies to the composition (concatenation).
  • From the injectivity of follows that is injective.
  • A function with a non-empty set of definitions is injective, if a left inverse has, therefore, a function with (the identity map referred to ).
  • A function is injective if it is linkskürzbar, ie with follows for any function. (This property motivates the term monomorphism used in category theory, but in general morphisms are injective and linkskürzbar no longer equivalent. )
  • Any function can be represented as concatenation, which is surjective and injective (namely inclusion mapping ) is.
  • A continuous real-valued function on a real interval is injective if it is strictly increasing or strictly decreasing in its entire domain of definition, ie for any two numbers and out of the domain of definition applies: It follows from (lowest to highest ) or follows (highest to lowest ).
  • Of group and homomorphism of vector is injective if its kernel is trivial, that is, only from the neutral element or the zero vector is.

Widths of sets

For a finite set, the cardinality is simply the number of elements. Is now an injective function between finite sets, then how must have at least as many elements, it is so.

This can be equivalently formulated as follows: If a function between finite sets and holds, then is not injective. So there are (at least) two different elements and with. This statement is also referred to as drawer principle.

For infinite sets of injections are used to compare widths by size.

History

After you've been for generations got by with phrases such as " one to one ", came only in the mid-20th century by the solid- set-theoretic representation of all mathematical subdivisions on the need for a more concise description. Probably the word was coined injective as well as surjective and bijective in the 1930s by N. Bourbaki. The noun injection was introduced in 1950 by S. MacLane, the adjective injective 1952 in the Foundations of algebraic topology of Eilenberg and Steenrod.

There is great confusion at times regarding the association between the concepts Explicitly one hand and injective or bijective other. Sources ( textbooks) from pure mathematics favor injective " non-specialist " sources favoring partial rather bijective. It should therefore be more apart from using the word Explicitly in this context.

Group homomorphism Null vector Saunders Mac Lane Samuel Eilenberg Norman Steenrod
412810
de