Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 37 ยท Sets, Relations and Functions

Functions: Injective, Surjective, Bijective

Define functions as special relations, then master injective, surjective and bijective maps, composition, inverses and the pigeonhole principle with Python checks.

A function f: A โ†’ B is a relation f โІ A ร— B in which every a โˆˆ A is paired with exactly one b โˆˆ B. We write f(a) = b. A is the domain, B the codomain, and f(A) = {f(a) : a โˆˆ A} is the image (or range). The codomain is declared up front; the image may be smaller.

This set-theoretic definition matters: two functions are equal if they have the same domain and the same pairs, however they are computed. In relation terms, a function is a relation that is total on A and single-valued.

Representing a finite function

In Python a finite function is a dict. The check "total and single-valued" is automatic for dicts, but you must still check that every value lies in the codomain.

Python A function as a dict, with image and preimage

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.

Injective, surjective, bijective

  • Injective (one-to-one): different inputs give different outputs: f(a) = f(aโ€ฒ) implies a = aโ€ฒ.
  • Surjective (onto): every b โˆˆ B is hit: for each b there is some a with f(a) = b; equivalently image = codomain.
  • Bijective: both. Every element of B has exactly one preimage; A and B are in perfect pairing.

The same formula can be any of these depending on domain and codomain. f(x) = xยฒ from โ„ to โ„ is neither (it is not onto the negatives, and f(2) = f(โˆ’2)). Restricted to [0, โˆž) โ†’ [0, โˆž) it is bijective.

Three kinds of function

Injective No two inputs share an output
Surjective Every output is hit
Bijective A perfect pairing

Bijective means injective and surjective at once.

1 / 2
Python Classifying finite functions

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.

The pigeonhole principle and counting functions

For finite sets, comparing sizes tells you a lot. If |A| > |B|, no function A โ†’ B can be injective (pigeonhole principle). If |A| < |B|, none can be surjective. If |A| = |B|, injective, surjective and bijective are all equivalent. That equivalence fails for infinite sets: n โ†ฆ n + 1 on โ„• is injective but not surjective, which is a first taste of cardinality.

Counting: there are |B|^|A| functions from A to B, and when |A| = |B| = n there are n! bijections. Brute force confirms it for small sets.

Python Counting functions, injections and bijections

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.

Composition and inverses

The composition g โˆ˜ f applies f first: (g โˆ˜ f)(a) = g(f(a)). Composition is associative but not commutative. Useful facts:

  • If f and g are injective, so is g โˆ˜ f. Same for surjective and bijective.
  • If g โˆ˜ f is injective, then f is injective.
  • If g โˆ˜ f is surjective, then g is surjective.

The identity function id_A(a) = a is a unit for composition. A function f has an inverse fโปยน: B โ†’ A with fโปยน โˆ˜ f = id_A and f โˆ˜ fโปยน = id_B exactly when f is bijective. For a non-bijective f, the notation fโปยน(S) still makes sense but means the preimage set, not an inverse function.

Python Inverse and composition on finite maps

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.

To show a function is a bijection in a proof, either prove injective and surjective separately, or write down an explicit inverse and check both compositions give the identity.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A function f: A โ†’ B is surjective when

    Surjective means the image equals the codomain. The first option is injectivity.
  2. 2. How many functions are there from a 3-element set to a 4-element set?

    Each of the 3 inputs picks one of 4 outputs: 4^3 = 64.
  3. 3. Let |A| = 5 and |B| = 4. Which statement is certainly true?

    By the pigeonhole principle, five inputs cannot map to four outputs without a collision.
  4. 4. If g โˆ˜ f is injective, what must be true?

    If f(a) = f(aโ€ฒ) then g(f(a)) = g(f(aโ€ฒ)), so a = aโ€ฒ by injectivity of g โˆ˜ f. Nothing follows for g in general.

Summary

  • A function is a total, single-valued relation; domain, codomain and image are different things.
  • Injective means no collisions, surjective means every target is hit, bijective means both.
  • Finite sets obey the pigeonhole principle; there are |B|^|A| functions and n! bijections between n-element sets.
  • Composition preserves injectivity and surjectivity; only bijections have inverse functions.

Next: Cardinality and Countable Sets