Bijections and counting functions

A function that is both one-one and onto is a bijection. It pairs the elements of A and B off perfectly, one with one, with nothing left over on either side.

To show a bijection, do both proofs. Example: f(x) = 5 – 2x on R.

• One-one: 5 – 2x₁ = 5 – 2x₂ gives x₁ = x₂.
• Onto: for any y, x = (5 – y)/2 is real and f(x) = y.

With fractions, watch the domain and co-domain. f(x) = (x + 1)/(x – 2) from R – {2} to R – {1}: solving y = f(x) gives x = (2y + 1)/(y – 1). This needs y ≠ 1, which is exactly why 1 is left out of the co-domain; and x is never 2, so it lies in the domain. So f is onto, and it is one-one too.

Finite sets behave nicely. For a function from a finite set to itself, one-one and onto always come together: if no two inputs share an output, n inputs give n different outputs, which fill all n places.

Counting:

• One-one functions from a set of n elements to itself: these are arrangements of the n elements, so there are n! of them. For 4 elements, 4! = 24.
• All functions from a set of m elements to a set of n elements: each of the m inputs has n choices, so nᵐ.

Two functions are equal when they have the same domain and agree at every point of it.