Functions and cardinality

A function in mathematics is a rule that assigns to each input exactly one output. Programming functions are named after this idea, though they differ in important ways. This lesson defines functions precisely, classifies them as injective, surjective or bijective, introduces composition and inverses, proves the pigeonhole principle, and then uses functions to compare the sizes of sets, including infinite ones. The surprising result at the end, that some infinite sets are larger than others, underlies the limits of computation studied in CMPUT-474.

Functions as sets of pairs

A function \(f\) from a set \(A\) to a set \(B\), written \(f: A \to B\), assigns to each element \(a \in A\) exactly one element \(f(a) \in B\). The set \(A\) is the domain, \(B\) is the codomain, and the set of values actually taken, \(\{f(a) \mid a \in A\}\), is the range or image. Formally, a function is a subset of \(A \times B\) in which every \(a \in A\) appears as the first coordinate of exactly one pair. Two conditions are packed into that definition: every input has an output (the function is total), and no input has two outputs (the function is well defined).

A Python dictionary is a finite function: its keys are the domain and each key maps to exactly one value. A Python function that always returns a value and has no side effects also behaves like a mathematical function. Programming functions can break both conditions: a function that raises an exception for some inputs is not total, and one that reads a clock or a random generator can return different outputs for the same input, so it is not a function in the mathematical sense.

Injective, surjective and bijective

A function \(f: A \to B\) is injective (one-to-one) if different inputs give different outputs: \(f(a_1) = f(a_2) \to a_1 = a_2\). It is surjective (onto) if every element of the codomain is hit: \(\forall b \in B\, \exists a \in A\, (f(a) = b)\). It is bijective if it is both. A bijection pairs the elements of \(A\) and \(B\) perfectly, with nothing left over on either side.

def injective(f, A):
    images = [f(a) for a in A]
    return len(images) == len(set(images))

def surjective(f, A, B):
    return {f(a) for a in A} == set(B)

A = range(6)
B = range(6)
tests = {
    "x -> 2x mod 6": lambda x: (2 * x) % 6,
    "x -> x + 1 mod 6": lambda x: (x + 1) % 6,
    "x -> 5x mod 6": lambda x: (5 * x) % 6,
    "x -> x*x mod 6": lambda x: (x * x) % 6,
}
for name, f in tests.items():
    print(f"{name:16s} injective={injective(f, A)!s:5s} surjective={surjective(f, A, B)}")

x -> 2x mod 6    injective=False surjective=False
x -> x + 1 mod 6 injective=True  surjective=True
x -> 5x mod 6    injective=True  surjective=True
x -> x*x mod 6   injective=False surjective=False

Proofs of these properties follow the definitions directly. To prove injectivity, assume \(f(a_1) = f(a_2)\) and deduce \(a_1 = a_2\). To prove surjectivity, take an arbitrary \(b\) in the codomain and find an \(a\) with \(f(a) = b\), usually by solving the equation. To disprove either, give a counterexample.

The domain and codomain matter, as the last remark shows. The squaring function is not injective on \(\mathbb{R}\), since \((-2)^2 = 2^2\), but it is injective on the non-negative reals. It is not surjective onto \(\mathbb{R}\), since nothing squares to \(-1\), but it is surjective onto the non-negative reals.

Composition and inverses

If \(f: A \to B\) and \(g: B \to C\), the composition \(g \circ f: A \to C\) is defined by \((g \circ f)(a) = g(f(a))\): apply \(f\) first, then \(g\). Composition is how programs are built from smaller functions, and it is associative but not commutative in general. If \(f(x) = x + 1\) and \(g(x) = 2x\), then \(g(f(3)) = 8\) but \(f(g(3)) = 7\).

A function \(f: A \to B\) has an inverse \(f^{-1}: B \to A\) with \(f^{-1}(f(a)) = a\) and \(f(f^{-1}(b)) = b\) exactly when \(f\) is a bijection. Injectivity ensures each output came from only one input, so the inverse is well defined; surjectivity ensures every \(b\) has some input to return, so the inverse is total. Encryption and decryption, encoding and decoding, and compression and decompression are inverse pairs, and lossless compression works only because the compression function is injective on the files it handles.

# A Caesar shift is a bijection on the 26 letters; its inverse shifts back.
import string
L = string.ascii_lowercase
shift = lambda k: (lambda c: L[(L.index(c) + k) % 26])
enc, dec = shift(3), shift(-3)
msg = "discrete"
c = "".join(enc(ch) for ch in msg)
print(msg, "->", c, "->", "".join(dec(ch) for ch in c))
print("enc is injective on letters:", len({enc(ch) for ch in L}) == 26)

discrete -> glvfuhwh -> discrete
enc is injective on letters: True

The pigeonhole principle

If more than \(n\) objects are placed into \(n\) boxes, some box contains at least two objects. Stated with functions: if \(|A| > |B|\) and both are finite, no function \(f: A \to B\) is injective. The principle sounds trivial, but it proves surprising facts. The generalized form says that if \(N\) objects go into \(k\) boxes, some box contains at least \(\lceil N/k \rceil\) objects.

The pigeonhole principle also explains why no lossless compressor can shrink every file. There are \(2^n\) files of exactly \(n\) bits, but only \(2^n - 1\) files of fewer than \(n\) bits (counting the empty file). A compressor that made every \(n\)-bit file shorter would map \(2^n\) inputs into \(2^n - 1\) outputs, so two different files would compress to the same output and could not both be recovered.

import random
random.seed(1)
buckets = 365
keys = [random.getrandbits(32) for _ in range(1000)]
counts = [0] * buckets
for k in keys:
    counts[k % buckets] += 1
print("largest bucket:", max(counts), " guaranteed at least:", -(-1000 // buckets))
# birthday-style: how many random keys until the first collision?
seen, n = set(), 0
while True:
    n += 1
    h = random.getrandbits(32) % buckets
    if h in seen:
        break
    seen.add(h)
print("first collision after", n, "keys (pigeonhole guarantees one by key 366)")

largest bucket: 10  guaranteed at least: 3
first collision after 9 keys (pigeonhole guarantees one by key 366)

Cardinality and infinite sets

For finite sets, the cardinality \(|A|\) is the number of elements. Two finite sets have the same size exactly when there is a bijection between them. Georg Cantor took that as the definition for all sets: \(A\) and \(B\) have the same cardinality if there is a bijection between them. For infinite sets this leads to results that defy intuition.

A set is countably infinite if it has the same cardinality as \(\mathbb{N}\), meaning its elements can be listed in a sequence \(a_0, a_1, a_2, \ldots\) that eventually reaches every element. The even natural numbers are countable via \(n \mapsto 2n\), even though they seem to be half of \(\mathbb{N}\). The integers are countable via the listing \(0, 1, -1, 2, -2, 3, -3, \ldots\). Even the rational numbers are countable: arrange the fractions \(a/b\) in a grid and walk along the diagonals, skipping repeats.

from math import gcd
def rationals():
    """Yield every positive rational exactly once by walking diagonals a + b = s."""
    s = 2
    while True:
        for a in range(1, s):
            b = s - a
            if gcd(a, b) == 1:
                yield f"{a}/{b}"
        s += 1

gen = rationals()
print([next(gen) for _ in range(20)])
z = lambda n: (n + 1) // 2 if n % 2 else -(n // 2)     # bijection N -> Z
print([z(n) for n in range(11)])

['1/1', '1/2', '2/1', '1/3', '3/1', '1/4', '2/3', '3/2', '4/1', '1/5', '5/1', '1/6', '2/5', '3/4', '4/3', '5/2', '6/1', '1/7', '3/5', '5/3']
[0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5]

Cantor's diagonal argument

Are all infinite sets countable? Cantor proved in 1891 that they are not. The set of all infinite binary sequences, equivalently the real numbers between 0 and 1 written in binary, is uncountable. The proof is by contradiction and is one of the most influential arguments in mathematics.

The diagonal argument has a direct consequence for computing. Every program is a finite string over a finite alphabet, so the set of all programs is countable: list them by length, then alphabetically. But the set of all functions from \(\mathbb{N}\) to \(\{0, 1\}\), that is, all yes-or-no problems about natural numbers, is uncountable by the diagonal argument. Therefore some problems have no program that solves them. Alan Turing found a specific one, the halting problem, using a diagonal argument of the same shape; you will study it in CMPUT-474.