# One To One

A function is defined as a mapping between two sets. The notation for this is

``` f: A -> B
```
This means that the function f maps an element from set A to an element in set B. Or, more informally, f takes an argument of type A, and returns an argument of type B.

Functions come in 3 flavours: Injection, Surjection and Bijection.

Injection

A function f: A -> B is one-to-one if for all a1, a2 in A, a1 != a2 implies f(a1) != f(a2).

This is also known as an injection. Informally, it means that no two elements in A map to the same element in B.

Surjection

A function g: A -> B is onto if for all b in B, there exists a in A with g(a) = b.

This is also known as a surjection. Informally, it means that all elements in B are mapped to. It is possible, unlike an injection, to have an element of B mapped to by more than one element in A.

Bijection

A function is a bijection if it is both an injection and a surjection.

If f: A -> B is one-to-one and onto, then it provides a one-to-one correspondence between the sets A and B. Informally, every element of A maps to exactly one element of B, and all elements of B are mapped to.

You often see one-to-one (mis)used to mean there is a one-to-one correspondence.

EditText of this page (last edited November 13, 2014) or FindPage with title or text search