Three important kinds of mathematical functions deserve special names: a function *f* : *X* `->` *Y* is called
#### Motivation

#### Examples

#### Propositions

- a
**surjection**(or**surjective**, or**onto**) if for every*y*in*Y*there is at least one*x*in*X*such that*f*(*x*) =*y* - an
**injection**(or**injective**, or**one-to-one**) if for every*y*in*Y*there is at most one*x*in*X*such that*f*(*x*) =*y* - a
**bijection**(or**bijective**, or**one-to-one and onto**) if it is both a surjection and an injection, i.e., if for every*y*in*Y*there is precisely one*x*in*X*such that*f*(*x*) =*y*.

These kinds of functions are generally useful for showing the relationships between different kinds of mathematical objects. Often, an injective relationship will correspond to a subset-like relationship, and the existence of a bijection will demonstrate an equality-like relationship.

For instance, a homomorphism θ is a relationship between two algebraic objects (that is sets with some kind of multiplication defined for the purposes of this example) which preserves multiplication; that is θ(*x*) * θ(*y*) = θ(*x* * *y*) for all *x* and *y*. If a homomorphism is also a bijection then the two algebraic objects are described as *isomorphic*; they are so closely equivalent that consideration of the algebraic properties of one is equivalent to consideration of the algebraic properties of the other; in writing a proof about one you may as well be writing a proof about the other. Therefore a convenient proof technique to show the existence of some property in object **A** is to demonstrate a bijection between **A** and some other object **B**, and realize that someone else has already proven this property for object **B**.

- The function
*abs*from**Z**(the set of Integers) to**Z**defined by*abs*(*x*) = |*x*| where |*x*| is the absolute value of*x*, is neither injective nor surjective. Since there exists an integer -5 in**Z**such that there is no integer*i*in**Z**with*abs*(*i*) = -5,*abs*is not surjective. Since*abs*(5) =*abs*(-5),*abs*is not injective. - Consider the function
*abs**from**Z**to**N**(the set of non-negative integers) that is defined by the same rule as*abs*. Then*abs**is onto, or a surjection, since for every*y*in**N**, that is, every non-negative integer, there is at least one*x*in*Z*such that*abs**(*x*) =*y*. - Consider the function
*add1*from**Z**to**Z**that is specified by the rule*add1*(*x*) =*x*+ 1. The function*add1*is one-to-one and onto or a bijection, since for every*y*in**Z**there is one and only one*x*in**Z**such that*add1*(*x*) =*y*(namely*x*=*y*- 1).

- A function is bijective if and only if it is injective and surjective.
- If
*f*o*g*is injective, then*g*is injective. - If
*f*o*g*is surjective, then*f*is surjective. - If
*f*and*g*are both injective, then*f*o*g*is injective. - If
*f*and*g*are both surjective, then*f*o*g*is surjective. - If
*h*o*f*=*h*o*g*and*h*is injective, then*f*=*g*. - If
*f*o*h*=*g*o*h*and*h*is surjective, then*f*=*g*. - If
*f*is injective, then*f*(^{ -1}*f*(*A*)) =*A*for any subset*A*of the domain of*f*. - If
*f*is surjective, then*f*(*f*(^{ -1}*B*)) =*B*for any subset*B*of the codomain of*f*. - Every function
*h*can be written as*h*=*f*o*g*with a suitable surjection*g*and an injection*f*. - A function
*f*:*X*`->`*Y*is bijective if and only if there exists a function*g*:*Y*->*X*such that*g*o*f*is the identity on*X*and*f*o*g*is the identity on*Y*. In this case,*g*is uniquely determined by*f*and we call*g*the*inverse function*of*f*and write*f*^{ -1}=*g*. - The bijective functions
*X*`->`*X*, together with functional composition, form a mathematical group, the*symmetric group*of*X*denoted by S(*X*).