Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 38 Ā· Relations and Functions

Injective, Surjective and Bijective Functions

Learn one-to-one, onto and bijective functions, how to prove or disprove each, how inverse functions work, and why bijections count infinite sets.

A function sends every input to one output, but it says nothing about outputs being shared or missed. Three properties describe how a function covers its codomain: injective (no two inputs share an output), surjective (every output is hit) and bijective (both). Bijections are the central tool of this track, because they are how we decide that two sets have "the same size".

Injective (one-to-one)

A function f : A → B is injective if different inputs always give different outputs:

Text
for all a₁, aā‚‚ ∈ A:  f(a₁) = f(aā‚‚)  implies  a₁ = aā‚‚

On the arrow diagram, no element of B has two arrows arriving. The second form of the definition is the one you prove with: assume the outputs are equal and show the inputs are equal.

Example (prove). f : ā„ → ā„, f(x) = 3x + 5 is injective. If 3x₁ + 5 = 3xā‚‚ + 5 then 3x₁ = 3xā‚‚, so x₁ = xā‚‚.

Example (disprove). g : ā„ → ā„, g(x) = x² is not injective, because g(2) = g(āˆ’2) = 4 but 2 ≠ āˆ’2. If we restrict the domain to [0, āˆž), the same rule becomes injective.

Surjective (onto)

A function f : A → B is surjective if every element of the codomain is an output:

Text
for all b ∈ B there is a ∈ A with f(a) = b

Equivalently, ran(f) = B. On the arrow diagram, every element of B has at least one arrow arriving. To prove it, take an arbitrary b and find an a.

Example (prove). f : ā„ → ā„, f(x) = 3x + 5 is surjective. Given b, choose a = (b āˆ’ 5)/3; then f(a) = b.

Example (disprove). g : ā„ → ā„, g(x) = x² is not surjective, since āˆ’1 is never a square. But g : ā„ → [0, āˆž) is surjective: for b ≄ 0 choose a = √b. This shows why the codomain is part of the function.

Bijective

A function is bijective (a bijection, or a one-to-one correspondence) if it is both injective and surjective. Every element of B is hit by exactly one arrow. The function f(x) = 3x + 5 on ā„ is a bijection.

Property Arrows into each element of B Picture
injective at most one no collisions
surjective at least one no misses
bijective exactly one perfect pairing
flowchart LR
    subgraph S1["Injective, not onto"]
    a1["1"] --> b1["x"]
    a2["2"] --> b2["y"]
    b3["z"]
    end
    subgraph S2["Onto, not injective"]
    c1["1"] --> d1["x"]
    c2["2"] --> d1
    c3["3"] --> d2["y"]
    end

Left: injective, but z receives no arrow. Right: onto, but two inputs collide at x.

Counting on finite sets

For finite sets, bijections only exist when the sizes match, and the properties are linked to size:

  • If f : A → B is injective, then |A| ≤ |B|.
  • If f : A → B is surjective, then |A| ≄ |B|.
  • If |A| = |B| is finite, then injective ⇔ surjective ⇔ bijective.

The last statement fails for infinite sets. The function f : ā„• → ā„•, f(n) = n + 1 is injective but not surjective (0 is never hit), which is impossible for a finite set. This strange behavior is exactly what defines infinite sets, and you will use it in the chapter on cardinality.

The number of bijections from an n-element set to itself is n! (the permutations).

Python Classify functions on finite sets

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Inverse functions

A function f : A → B has an inverse function f⁻¹ : B → A exactly when f is a bijection. The inverse sends each b back to the unique a with f(a) = b. Then

Text
f⁻¹(f(a)) = a  for all a ∈ A,     f(f⁻¹(b)) = b  for all b ∈ B

If f is not injective, the flipped relation has an input with two outputs. If f is not surjective, the flipped relation misses some inputs. Either way it is not a function. The inverse of f(x) = 3x + 5 is f⁻¹(y) = (y āˆ’ 5)/3.

Two other facts: the composition of two injective functions is injective, the composition of two surjective functions is surjective, so the composition of bijections is a bijection, and (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹ (undo in reverse order, like taking off shoes and socks).

Python Inverting a bijection

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why bijections matter

Saying that two sets are in bijection means you can pair their elements one to one with nothing left over. For finite sets, this is just "same number of elements". The idea works without counting, so it extends to infinite sets, where it is the definition of "same size". The next chapter builds the theory of cardinality on this one concept.

Check your understanding

Quick check Ā· 4 questions

of 4 answered You scored / 4 Ā· perfect!

  1. 1. f : ā„ → ā„, f(x) = x² is:

    f(2) = f(-2), so not injective; -1 is never an output, so not surjective.
  2. 2. To prove f is injective you usually:

    The second option proves surjectivity. For injectivity, assume equal outputs and derive equal inputs.
  3. 3. Which function is a bijection?

    x³ is injective and every real number has a real cube root, so it is onto. The third function misses 0 (if ā„• includes 0).
  4. 4. How many bijections are there from a 4-element set to itself?

    They are the permutations: 4! = 24.

Summary

  • Injective: f(a₁) = f(aā‚‚) ⇒ a₁ = aā‚‚. Surjective: every b is an output. Bijective: both.
  • Prove injectivity by assuming equal outputs; prove surjectivity by constructing a preimage; disprove with a counterexample.
  • A function has an inverse function exactly when it is a bijection.
  • For finite sets of equal size the three notions coincide; for infinite sets they do not.
  • Bijections are how set theory compares sizes.

Next: Equivalence Relations