Bijection, injection and surjection

<table><tbody><tr><th></th><th>surjective</th><th>non-surjective</th></tr><tr><th>injective</th><td>bijective</td><td>injective-only</td></tr><tr><th>non-injective</th><td>surjective-only</td><td>general </td></tr></tbody></table>
<table><tbody><tr><td></td><td></td></tr><tr><td></td><td></td></tr></tbody></table>
In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, injections, surjections, and bijections are classes of <a href="/facts/Function_(mathematics)/CdReEKCh">functions</a> distinguished by the manner in which <a href="/facts/Parameter/zFvVFMv9">arguments</a> (input <a href="/facts/Expression_(mathematics)/MPrMlYbE">expressions</a> from the <a href="/facts/Domain_of_a_function/FQvoeUpX">domain</a>) and <a href="/facts/Image_(mathematics)/KANefMAl">images</a> (output expressions from the <a href="/facts/Codomain/MGc43nwQ">codomain</a>) are related or mapped to each other.
A function <a href="/facts/Map_(mathematics)/FABF1l2f">maps</a> elements from its domain to elements in its codomain. Given a function 
 
 
 
 f
 :
 X
 →
 Y
 
 
 {\displaystyle f\colon X\to Y}
 
:

<ul><li>The function is <a href="/facts/Injective_function/5ES6tqf5">injective</a>, or one-to-one, if each element of the codomain is mapped to by at most one element of the domain, or equivalently, if distinct elements of the domain map to distinct elements in the codomain. An injective function is also called an injection. Notationally:</li></ul>

∀
        x
        ,
        
          x
          ′
        
        ∈
        X
        ,
        f
        (
        x
        )
        =
        f
        (
        
          x
          ′
        
        )
        
        ⟹
        
        x
        =
        
          x
          ′
        
        ,
      
    
    {\displaystyle \forall x,x'\in X,f(x)=f(x')\implies x=x',}

or, equivalently (using <a href="/facts/Transposition_(logic)/lJaaRrxT">logical transposition</a>),

∀
 x
 ,
 
 x
 ′
 
 ∈
 X
 ,
 x
 ≠
 
 x
 ′
 
 
 ⟹
 
 f
 (
 x
 )
 ≠
 f
 (
 
 x
 ′
 
 )
 .
 
 
 {\displaystyle \forall x,x'\in X,x\neq x'\implies f(x)\neq f(x').}
 
<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a><a class="footnote-ref" id="fnref:3" href="#fn:3">3</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
<ul><li>The function is <a href="/facts/Surjective_function/KezhLpCb">surjective</a>, or onto, if each element of the codomain is mapped to by at least one element of the domain; that is, if the image and the codomain of the function are equal. A surjective function is a surjection. Notationally:</li></ul>

∀
 y
 ∈
 Y
 ,
 ∃
 x
 ∈
 X
 ,
 y
 =
 f
 (
 x
 )
 .
 
 
 {\displaystyle \forall y\in Y,\exists x\in X,y=f(x).}
 
<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>
<ul><li>The function is <a href="/facts/Bijective_function/j4gTuTmW">bijective</a> (one-to-one and onto, one-to-one correspondence, or invertible) if each element of the codomain is mapped to by exactly one element of the domain; that is, if the function is both injective and surjective. A bijective function is also called a bijection. That is, combining the definitions of injective and surjective,</li></ul>

∀
        y
        ∈
        Y
        ,
        ∃
        !
        x
        ∈
        X
        ,
        y
        =
        f
        (
        x
        )
        ,
      
    
    {\displaystyle \forall y\in Y,\exists !x\in X,y=f(x),}

where 
 
 
 
 ∃
 !
 x
 
 
 {\displaystyle \exists !x}
 
 means "there <a href="/facts/Uniqueness_quantification/qBpdIqel">exists exactly one</a> x".
<ul><li>In any case (for any function), the following holds:</li></ul>

∀
        x
        ∈
        X
        ,
        ∃
        !
        y
        ∈
        Y
        ,
        y
        =
        f
        (
        x
        )
        .
      
    
    {\displaystyle \forall x\in X,\exists !y\in Y,y=f(x).}

An injective function need not be surjective (not all elements of the codomain may be associated with arguments), and a surjective function need not be injective (some images may be associated with more than one argument). The four possible combinations of injective and surjective features are illustrated in the adjacent diagrams.

Bijection, injection and surjection open-in-new

Bijection, injection and surjection