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) = b: b is the image of a; a is a pre-image of b.
• The range is the set of all images: {f(a) : a ∈ A} ⊆ B.

A relation fails to be a function if some element of A has no image or two images.

#Types of functions

def classify(f, A, B):
    images = [f(a) for a in A]
    injective = len(set(images)) == len(images)
    surjective = set(images) == set(B)
    return f"injective={injective}, surjective={surjective}, bijective={injective and surjective}"

A = range(-3, 4)
print("x+1 :", classify(lambda x: x + 1, A, range(-2, 5)))
print("x^2 :", classify(lambda x: x * x, A, range(0, 10)))
print("2x  :", classify(lambda x: 2 * x, A, range(-6, 7)))

x+1 : injective=True, surjective=True, bijective=True
x^2 : injective=False, surjective=False, bijective=False
2x  : injective=True, surjective=False, bijective=False

#Composition

(g ∘ f)(x) = g(f(x)) — apply f first, then g. Composition is associative but not commutative:

f = lambda x: x + 3
g = lambda x: 2 * x
print("(g∘f)(5) =", g(f(5)))     # 2 * (5 + 3) = 16
print("(f∘g)(5) =", f(g(5)))     # 2 * 5 + 3 = 13

(g∘f)(5) = 16
(f∘g)(5) = 13

#Inverse functions

A function has an inverse f⁻¹ if and only if it is a bijection. Then f⁻¹(b) = a exactly when f(a) = b, and f⁻¹(f(x)) = x. Example: f(x) = 3x + 2 on ℝ has f⁻¹(y) = (y − 2)/3.

#Floor and ceiling

• ⌊x⌋ (floor): the largest integer ≤ x. ⌊3.7⌋ = 3, ⌊−3.7⌋ = −4.
• ⌈x⌉ (ceiling): the smallest integer ≥ x. ⌈3.2⌉ = 4, ⌈−3.2⌉ = −3.

They appear constantly in algorithm analysis: a binary tree with n nodes has height at least ⌈log₂(n + 1)⌉ − 1; splitting n items into pages of 10 needs ⌈n/10⌉ pages.

#Counting functions

For finite sets with |A| = m and |B| = n:

#Pigeonhole connection

If m > n, no function A → B can be injective: some two elements of A must share an image. That is the pigeonhole principle.