Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 68 Β· Sets, Relations and Functions

Functions and Cardinality

Learn injective, surjective and bijective functions, composition, inverses, counting functions, and why some infinite sets are bigger than others.

A function is a relation with a strict rule: every input has exactly one output. That single rule makes functions the workhorse of mathematics and of programming. A Python function, a hash table lookup, a database key, an encryption routine: each one sends inputs to outputs, and the questions you ask about them are the same. Can two inputs collide? Does every output get hit? Can I run the function backwards?

Those questions lead to three famous properties (injective, surjective, bijective) and then to a surprising place: a way to compare the sizes of sets, including infinite ones. In this lesson you will classify functions on finite sets with code, count how many functions of each kind exist, and then see why the real numbers cannot be listed in a sequence.

Functions as special relations

A function f: A β†’ B assigns to each element of the domain A exactly one element of the codomain B. As a relation (see Relations), f is a set of pairs (a, b) such that every a in A appears as a first component exactly once. The range (or image) is the set of outputs that are actually produced; it is a subset of the codomain and may be smaller.

For finite sets, a Python dict is a function: its keys are the domain, and each key has exactly one value. That is why the language will not let you give one key two values.

Injective, surjective, bijective

Three properties describe how a function treats its inputs and outputs.

  • Injective (one-to-one): different inputs give different outputs. If f(x) = f(y) then x = y. No collisions.
  • Surjective (onto): every element of the codomain is hit. The range equals the codomain.
  • Bijective: both at once. Every output is hit by exactly one input, so inputs and outputs pair up perfectly.

Three ways a function can behave

Injective No two inputs share an output.
Surjective Every element of the codomain is hit.
Bijective A perfect one-to-one pairing.

The codomain matters. The same rule can be onto for one codomain and not for another.

1 / 2

Whether a function is surjective depends on the codomain you declare. The rule f(x) = xΒ² is not onto the integers (nothing maps to 3), but it is onto the set of perfect squares. It is also not injective on the integers, because f(2) = f(-2) = 4. Restrict the domain to the non-negative integers and it becomes injective.

For finite sets, counting gives a shortcut. If |A| = |B| = n, then a function from A to B is injective if and only if it is surjective, and both mean bijective. If |A| > |B|, no injective function exists: this is the pigeonhole principle, which you will meet again in Counting Principles.

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.

The squaring map collides on residues (1 and 4 both square to 1 mod 5), so it is neither. x // 2 hits all of {0, 1, 2}, so it is onto that codomain but not onto the wider one. Doubling never collides but misses every odd number.

One-one, many-one, into and onto: the older names

Many textbooks, especially in exam syllabuses, use a different vocabulary for the same ideas. It helps to know both.

  • One-one is the same as injective: no two inputs share an output.
  • Many-one means the opposite: at least two inputs share an output.
  • Onto is surjective: the range equals the codomain.
  • Into means the range is a proper subset of the codomain: at least one codomain element is missed.

Crossing the two pairs gives four kinds of function:

Kind Inputs sharing outputs? Every codomain element hit? Example on the integers mod 5
One-one onto (bijective, a one-one correspondence) no yes x -> 2x mod 5
One-one into no no x -> x from {0,1,2} into {0,...,4}
Many-one onto yes yes x -> x // 2 from {0,...,4} onto {0,1,2}
Many-one into yes no x -> x*x mod 5 from {0,...,4} into {0,...,4}

Two more words go with these. The image of an element x is f(x). The pre-image of an element y of the codomain is the set {x : f(x) = y} of all inputs that map to it, and this set may be empty (if y is missed), a single element, or several. More generally the pre-image of a set T is f^-1(T) = {x : f(x) in T}. Writing f^-1(y) does not mean the function has an inverse; only bijections have inverse functions, while pre-images exist for every function.

Python Pre-images and the four kinds of function

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.

Counting functions

How many functions go from a set with m elements to a set with n elements? Each of the m inputs independently picks one of n outputs, so there are n^m functions. Injective ones are more constrained: the first input has n choices, the second n-1, and so on, giving n Γ— (n-1) Γ— … Γ— (n-m+1) when m ≀ n, and zero otherwise. Counting the surjective ones is harder and uses inclusion-exclusion (see Advanced Counting later); brute force is a fine check for small cases.

Python Count functions by brute force

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.

There are no surjective functions from 3 inputs onto 4 outputs, which the code confirms: you cannot hit four targets with only three arrows.

Composition and inverses

If g: A β†’ B and f: B β†’ C, the composition f ∘ g: A β†’ C applies g first, then f: (f ∘ g)(x) = f(g(x)). Order matters, and the notation reads right to left. Composition of injective functions is injective, and composition of surjective functions is surjective, so composing bijections gives a bijection.

A function f has an inverse f⁻¹ exactly when f is bijective. The inverse undoes f: f⁻¹(f(x)) = x and f(f⁻¹(y)) = y. If f is not injective, going backwards is ambiguous (which input produced this output?). If f is not surjective, some outputs have no preimage. For a finite function stored as a dict, the inverse is simply the dict with keys and values swapped, and the swap only makes sense for a bijection.

Python Composition and inverse

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.

Cardinality: comparing sizes

The cardinality |A| of a finite set is its number of elements. The remarkable idea of Georg Cantor was to define "same size" without counting: two sets have the same cardinality if there is a bijection between them. For finite sets this agrees with counting. For infinite sets it gives surprising answers.

A set is countably infinite if it can be matched one-to-one with the natural numbers {0, 1, 2, …}; it is countable if it is finite or countably infinite. The even numbers are countable, even though they are "half" of the naturals: pair n with 2n. The integers are countable too: list them as 0, 1, -1, 2, -2, … Even pairs of naturals are countable, by walking diagonals through the grid. The rationals are countable for the same reason, since each fraction is a pair of integers.

Two sets related by an injection each way have the same size (the Cantor-SchrΓΆder-Bernstein theorem), and an injection from A into B shows |A| ≀ |B|.

Python Finite demos of countability

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 diagonal argument

Is every infinite set countable? No. Cantor proved that the set of infinite binary sequences (equivalently, the subsets of the naturals, or the real numbers between 0 and 1) is uncountable. The proof is short and worth knowing.

Suppose someone claims to have listed all infinite binary sequences as sβ‚€, s₁, sβ‚‚, …. Build a new sequence d by looking at the diagonal: the n-th digit of d is the opposite of the n-th digit of sβ‚™. Then d differs from sβ‚€ in position 0, from s₁ in position 1, and from every sβ‚™ in position n. So d is not on the list, contradicting the claim that the list was complete. No list can ever work.

This is a proof by contradiction, a technique you will study in Contradiction and Contrapositive. The consequence is that there are different sizes of infinity: the power set of the naturals is strictly bigger than the naturals. In computing terms, there are uncountably many languages (sets of strings) but only countably many programs, so some languages cannot be recognized by any program.

You cannot run an infinite list, but you can see the construction on a finite square, where it works just as well.

Python The diagonal construction on a finite list

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 diagonal sequence is on no row of the list, however the list was built. For a list of n sequences of length n, there are 2^n possible rows, so a list can hold only a tiny part of them. The infinite version is the same trick, applied to a list that never ends.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. Which statement describes an injective function?

    Injective (one-to-one) means no collisions: f(x) = f(y) forces x = y. Hitting every output is surjectivity.
  2. 2. How many functions are there from a 3-element set to a 5-element set?

    Each of the 3 inputs independently picks one of 5 outputs, giving 5^3 = 125. The number 60 counts only the injective ones (5 x 4 x 3).
  3. 3. A function f from a finite set A to a finite set B with |A| = |B| is injective. What follows?

    n distinct inputs give n distinct outputs, which fills all n elements of B. For finite sets of equal size, injective and surjective are equivalent.
  4. 4. What does the diagonal argument prove?

    Flipping the n-th digit of the n-th listed sequence builds a sequence missing from any proposed list, so the set of infinite binary sequences is uncountable. The integers and rationals are countable.

Summary

  • A function gives every input exactly one output; the codomain you choose decides whether it is onto.
  • Injective means no collisions, surjective means every target is hit, bijective means both, and only bijections have inverses.
  • There are n^m functions from an m-set to an n-set, and perm(n, m) of them are injective.
  • Composition f ∘ g applies g first; it preserves injectivity, surjectivity and bijectivity.
  • Two sets have the same cardinality when a bijection links them; the integers, pairs of naturals and rationals are countable.
  • Cantor's diagonal argument shows the infinite binary sequences (and the real numbers) are uncountable.

Next: How Proofs Work, where we turn from using definitions to proving statements about them.