Functions

A function f: A → B assigns to each element of A exactly one element of B.

• A is the domain; B is the codomain.
• f(a) is the image of a. The set of all images is the range, a subset of B.

A Python dictionary whose keys are all of A is a function on a finite domain: f = {1: "x", 2: "y", 3: "x"}.

Three kinds of function

def describe(f, codomain):
    outputs = set(f.values())
    injective = len(outputs) == len(f)
    surjective = outputs == codomain
    return injective, surjective, injective and surjective

B = {"x", "y", "z"}
f = {1: "x", 2: "y", 3: "z"}
g = {1: "x", 2: "x", 3: "z"}
print("f: injective, surjective, bijective =", describe(f, B))
print("g: injective, surjective, bijective =", describe(g, B))

# f is a bijection, so it has an inverse
f_inverse = {v: k for k, v in f.items()}
print("f inverse:", f_inverse, "| f⁻¹(f(2)) =", f_inverse[f[2]])

# Composition: first f, then h
h = {"x": 10, "y": 20, "z": 30}
h_after_f = {a: h[f[a]] for a in f}
print("(h ∘ f) =", h_after_f)

• On a finite domain, f is injective exactly when its range has as many elements as its domain: len(set(f.values())) == len(f).
• It is surjective when its range is the whole codomain: set(f.values()) == B.

So for finite sets: an injection A → B needs |A| ≤ |B|, a surjection needs |A| ≥ |B|, and a bijection needs |A| = |B|. "There is a bijection between A and B" is in fact how mathematicians define "A and B have the same size", even for infinite sets.

Composition and inverses

The composition g ∘ f is "first f, then g": (g ∘ f)(x) = g(f(x)). It needs f's codomain to fit g's domain.

A function has an inverse f⁻¹ (with f⁻¹(f(x)) = x) exactly when it is a bijection: if two inputs shared an output, the inverse would not know which to give back; if some output were missing, the inverse would have nothing to give for it.

Floor and ceiling

• Floor ⌊x⌋ is the largest integer ≤ x: ⌊3.7⌋ = 3, ⌊−3.7⌋ = −4. Python: math.floor, and // for integers.
• Ceiling ⌈x⌉ is the smallest integer ≥ x: ⌈3.2⌉ = 4. Python: math.ceil.

They appear everywhere in computing: 100 students in groups of 30 need ⌈100/30⌉ = 4 rooms.

Counting functions

From a set of size m to a set of size n there are n^m functions (each of the m inputs picks one of n outputs), and n × (n − 1) × ... × (n − m + 1) injective ones (each input must pick an output not used yet).

Mark lesson complete