Difference between revisions of "Injection"

From Maths
Jump to: navigation, search
m (Added navbox... this page does need updating though)
(Added arrow with tail notation)
Line 5: Line 5:
 
Or equivalently:
 
Or equivalently:
 
* <math>\forall x_1,x_2\in X[x_1\ne x_2\implies f(x_1)\ne f(x_2)]</math> (the [[Contrapositive|contrapositive]] of the above)
 
* <math>\forall x_1,x_2\in X[x_1\ne x_2\implies f(x_1)\ne f(x_2)]</math> (the [[Contrapositive|contrapositive]] of the above)
 +
Sometimes an injection is denoted {{M|\rightarrowtail}}{{rNOSTYM}} (and a [[surjection]] {{M|\twoheadrightarrow}} and a [[bijection]] is both of these combined (as if super-imposed on top of each other) - there is no LaTeX arrow for this however) - we do not use this convention.
 
==Statements==
 
==Statements==
 
* [[Every injection yields a bijection onto its image]]
 
* [[Every injection yields a bijection onto its image]]

Revision as of 00:06, 4 February 2017

An injective function is 1:1, but not nessasarally onto.

Definition

For a function [math]f:X\rightarrow Y[/math] every element of [math]X[/math] is mapped to an element of [math]Y[/math] and no two distinct things in [math]X[/math] are mapped to the same thing in [math]Y[/math]. That is[1]:

  • [math]\forall x_1,x_2\in X[f(x_1)=f(x_2)\implies x_1=x_2][/math]

Or equivalently:

  • [math]\forall x_1,x_2\in X[x_1\ne x_2\implies f(x_1)\ne f(x_2)][/math] (the contrapositive of the above)

Sometimes an injection is denoted [ilmath]\rightarrowtail[/ilmath][2] (and a surjection [ilmath]\twoheadrightarrow[/ilmath] and a bijection is both of these combined (as if super-imposed on top of each other) - there is no LaTeX arrow for this however) - we do not use this convention.

Statements

Notes

Terminology

  • An injective function is sometimes called an embedding[1]
  • Just as surjections are called 'onto' an injection may be called 'into'[3] however this is rare and something I frown upon.
    • This is French, from "throwing into" referring to the domain, not elements themselves (as any function takes an element into the codomain, it need not be one-to-one)
    • I do not like using the word into but do like onto - I say:
      "But [ilmath]f[/ilmath] maps [ilmath]A[/ilmath] onto [ilmath]B[/ilmath] so...."
      "But [ilmath]f[/ilmath] is an injection so...."
      "As [ilmath]f[/ilmath] is a bijection..."
    • I see into used rarely to mean injection, and in fact any function [ilmath]f:X\rightarrow Y[/ilmath] being read as [ilmath]f[/ilmath] takes [ilmath]X[/ilmath] into [ilmath]Y[/ilmath] without meaning injection[1][4]

Properties

  • The cardinality of the inverse of an element [math]y\in Y[/math] may be no more than 1
    • Note this means it may be zero
      In contrast to a bijection where the cardinality is always 1 (and thus we take the singleton set [math]f^{-1}(y)=\{x\}[/math] as the value it contains, writing [ilmath]f^{-1}(y)=x[/ilmath])

See also

References

  1. 1.0 1.1 1.2 Analysis: Part 1 - Elements - Krzysztof Maurin
  2. Notes On Set Theory - Second Edition - Yiannis Moschovakis
  3. http://mathforum.org/library/drmath/view/52454.html
  4. Real and Abstract Analysis - Edwin Hewitt and Karl Stromberg