Discrete Math · Undergraduate

One-to-One, Onto and Bijective Functions

Quick answer

A function from A to B assigns each element of A exactly one element of B. It is one-to-one when different inputs always give different outputs, onto when every element of B is an output, and a bijection when it is both. A bijection pairs the two sets off perfectly, so finite sets with a bijection between them have the same size, and only bijections have inverse functions. Counting rules give the number of functions, one-to-one functions and bijections between finite sets.

What you'll learn

  • Decide whether a function is one-to-one, onto or a bijection
  • Prove or disprove each property for a formula
  • Count functions, one-to-one functions and bijections between finite sets
  • Explain why exactly the bijections have inverses

Three properties

A function f:A→Bf : A \to B assigns every element of AA exactly one element of BB. The set AA is the domain and BB the target. Two questions classify it.

  • One-to-one: do different inputs always give different outputs? If f(a)=f(b)f(a) = f(b) forces a=ba = b, no two inputs share an output.
  • Onto: is every element of BB hit? If every b∈Bb \in B equals f(a)f(a) for some aa, the outputs cover BB. Onto functions are also called surjective.

A function that is both is a bijection: it pairs the elements of AA and BB off exactly, one to one, with none left over.

Why only bijections have inverses

An inverse f−1f^{-1} must send each output back to the input it came from. If two inputs share an output, f−1f^{-1} would not know which one to choose, so ff must be one-to-one. If some element of BB is never an output, f−1f^{-1} has nothing to send it to, so ff must be onto. One-to-one makes the inverse well defined; onto makes it defined everywhere. That is the set-level reason behind the horizontal line test for inverse functions.

It also explains counting by pairing. Two finite sets have the same size exactly when some bijection matches them up.

Worked examples

Common mistakes

Practice problems

  1. Is f(x)=3x−7f(x) = 3x - 7, from R\mathbb{R} to R\mathbb{R}, a bijection? Find its inverse.

    Answer

    Yes; f−1(y)=y+73f^{-1}(y) = \tfrac{y + 7}{3}

    Full solution

    3a−7=3b−73a - 7 = 3b - 7 gives a=ba = b, and x=y+73x = \tfrac{y + 7}{3} solves f(x)=yf(x) = y for every yy.

  2. Is f(x)=exf(x) = e^x, from R\mathbb{R} to R\mathbb{R}, one-to-one? Onto?

    Answer

    One-to-one, but not onto

    Full solution

    exe^x is increasing, so it never repeats a value, but it never reaches 00 or any negative number. Onto (0,∞)(0, \infty) it is a bijection, with inverse ln⁡y\ln y.

  3. How many functions are there from a 22-element set to a 55-element set?

    Answer

    2525

    Full solution

    525^2.

  4. How many bijections are there from a 55-element set to itself?

    Answer

    120120

    Full solution

    5!=5×4×3×2×15! = 5 \times 4 \times 3 \times 2 \times 1: each is a rearrangement.

  5. How many one-to-one functions are there from a 33-element set to a 66-element set?

    Answer

    120120

    Full solution

    6×5×46 \times 5 \times 4.

  6. Can there be a one-to-one function from a 55-element set to a 44-element set?

    Answer

    No

    Full solution

    By the pigeonhole principle, two of the 55 inputs must share one of the 44 outputs.

  7. Is f(n)=n+1f(n) = n + 1, from the integers to the integers, a bijection? From the natural numbers {0,1,2,…}\{0, 1, 2, \ldots\} to themselves?

    Answer

    On the integers, yes. On the natural numbers, one-to-one but not onto.

    Full solution

    On the natural numbers, nothing maps to 00. On the integers, n−1n - 1 maps to any nn.

  8. A student says g(x)=x2g(x) = x^2 has an inverse because x\sqrt{x} undoes it. What is wrong?

    Answer

    On all of R\mathbb{R}, gg is not one-to-one, so  \sqrt{\ } only undoes it for x≥0x \ge 0.

    Full solution

    (−3)2=3\sqrt{(-3)^2} = 3, not −3-3. Restricting gg to [0,∞)[0, \infty) makes it a bijection whose inverse is  \sqrt{\ }.

Frequently asked questions

What is a one-to-one function?

A function where different inputs always give different outputs: if f(a) = f(b), then a = b.

What is an onto function?

A function whose outputs cover the whole target set: every element of B is f(a) for some a in A. It is also called surjective.

What is a bijection?

A function that is both one-to-one and onto. It pairs every element of A with exactly one element of B and leaves nothing out.

Which functions have inverses?

Exactly the bijections. One-to-one makes the inverse well defined, and onto makes it defined on all of B.

How many functions are there from a 3-element set to a 4-element set?

4³ = 64 in all, of which 4 × 3 × 2 = 24 are one-to-one. None are onto, since 3 inputs cannot cover 4 outputs.

What to learn next