Functions

A function f from set A to set B (written f: A → B) is a relation that assigns to each element in A exactly one element in B.

∀a ∈ A, ∃!b ∈ B, f(a) = b

Terminology

Domain: The set A (input set).
Codomain: The set B (output set).
Range (Image): The set {f(a) | a ∈ A} ⊆ B (actual outputs). The range can be a proper subset of the codomain.
Preimage: For b ∈ B, f⁻¹(b) = {a ∈ A | f(a) = b}.

Example: f: ℝ → ℝ, f(x) = x².

Domain: ℝ
Codomain: ℝ
Range: [0, ∞) (non-negative reals)
f⁻¹(4) = {-2, 2}

Representing Functions

Formula: f(x) = 2x + 1
Table/mapping: {(1, a), (2, b), (3, a)}
Graph: Set of points {(x, f(x)) | x ∈ A}
Algorithm/program: A function in programming is a mathematical function (if pure)

A relation R ⊆ A × B is a function iff:

Every element of A appears as a first component (total).
No element of A appears with two different second components (well-defined).

Types of Functions

Injective (One-to-One)

∀a₁, a₂ ∈ A, f(a₁) = f(a₂) → a₁ = a₂

Different inputs always produce different outputs. No two elements map to the same value.

Equivalently (contrapositive): a₁ ≠ a₂ → f(a₁) ≠ f(a₂).

Examples:

f(x) = 2x + 1 is injective. ✓
f(x) = x² (on ℝ) is not injective (f(-2) = f(2) = 4). ✗
f(x) = x² (on ℝ≥0) is injective. ✓

Surjective (Onto)

∀b ∈ B, ∃a ∈ A, f(a) = b

Every element of the codomain is "hit" by at least one element of the domain. Range = Codomain.

Examples:

f: ℝ → ℝ, f(x) = 2x + 1 is surjective (every y has x = (y-1)/2). ✓
f: ℝ → ℝ, f(x) = x² is not surjective (no x maps to -1). ✗
f: ℝ → ℝ≥0, f(x) = x² is surjective. ✓

Bijective (One-to-One Correspondence)

A function that is both injective and surjective.

Every element of B is mapped to by exactly one element of A. Bijections establish a "perfect pairing" between A and B.

Examples:

f: ℝ → ℝ, f(x) = 2x + 1 is bijective. ✓
f: ℤ → ℤ, f(n) = n + 1 is bijective. ✓

A bijection exists between A and B if and only if |A| = |B|.

Visual Summary

Injective:          Surjective:         Bijective:
A    B              A    B              A    B
1 → a              1 → a              1 → a
2 → b              2 ↗                2 → b
3 → c              3 → b              3 → c
     d (unmapped)

Composition

If f: A → B and g: B → C, the composition g ∘ f: A → C is:

(g ∘ f)(x) = g(f(x))

Note: Apply f first, then g. Read right-to-left.

Properties:

Associative: h ∘ (g ∘ f) = (h ∘ g) ∘ f
Not commutative in general: g ∘ f ≠ f ∘ g
Identity: f ∘ id_A = f and id_B ∘ f = f where id_A(a) = a

Composition preserves properties:

If f and g are injective, then g ∘ f is injective.
If f and g are surjective, then g ∘ f is surjective.
If f and g are bijective, then g ∘ f is bijective.

Inverse Functions

If f: A → B is a bijection, then the inverse f⁻¹: B → A exists and satisfies:

f⁻¹(f(a)) = a    for all a ∈ A
f(f⁻¹(b)) = b    for all b ∈ B

Equivalently: f⁻¹ ∘ f = id_A and f ∘ f⁻¹ = id_B.

A function has an inverse if and only if it is bijective.

If f is only injective (not surjective), we can define a left inverse g: g ∘ f = id_A. If f is only surjective (not injective), we can define a right inverse g: f ∘ g = id_B. (This requires the Axiom of Choice.)

Example: f(x) = 2x + 1. Then f⁻¹(y) = (y - 1)/2.

Verify: f⁻¹(f(x)) = f⁻¹(2x + 1) = (2x + 1 - 1)/2 = x. ✓

The Pigeonhole Principle

Basic form: If n + 1 objects are placed into n boxes, then at least one box contains at least 2 objects.

Generalized form: If N objects are placed into k boxes, then at least one box contains at least ⌈N/k⌉ objects.

Formal statement (in terms of functions): If f: A → B and |A| > |B|, then f is not injective (some pair maps to the same element).

Examples

Example 1: Among 367 people, at least two share a birthday (366 possible birthdays).

Example 2: In a group of 5 integers, at least two have the same remainder when divided by 4 (4 possible remainders: 0, 1, 2, 3).

Example 3: If 5 points are placed in a unit square, at least two are within √2/2 ≈ 0.707 of each other. (Divide the square into 4 smaller squares of side 1/2; by pigeonhole, some square contains 2 points; diagonal = √2/2.)

Example 4: In any sequence of n² + 1 distinct numbers, there is either an increasing subsequence of length n + 1 or a decreasing subsequence of length n + 1. (Erdos-Szekeres theorem — proved using pigeonhole.)

Cardinality

The cardinality of a set A, written |A|, measures its "size."

For finite sets: |A| = number of elements.

For infinite sets: cardinality compares sizes using bijections.

Definition: |A| = |B| if there exists a bijection f: A → B.

Definition: |A| ≤ |B| if there exists an injection f: A → B.

Schroeder-Bernstein Theorem

If |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|.

(If injections exist in both directions, a bijection exists.)

Countable and Uncountable Sets

Countably Infinite

A set A is countably infinite if |A| = |ℕ|, i.e., there exists a bijection f: ℕ → A.

Equivalently: the elements can be listed in a sequence a₁, a₂, a₃, ...

Examples of countably infinite sets:

ℤ: list as 0, 1, -1, 2, -2, 3, -3, ... The bijection f(n) maps 2k → k and 2k+1 → -k.
ℚ: use Cantor's zigzag enumeration of the rationals.
ℕ × ℕ: use the Cantor pairing function.
The set of all finite strings over a finite alphabet.
The set of all polynomials with integer coefficients.
The set of all computer programs.

Countable: A set is countable if it is finite or countably infinite.

Cantor's Pairing Function

A bijection from ℕ × ℕ to ℕ:

π(m, n) = (m + n)(m + n + 1)/2 + m

This shows |ℕ × ℕ| = |ℕ|, which is remarkable: "an infinite square has no more points than a line."

Uncountable Sets

A set is uncountable if it is not countable — it is "strictly larger" than ℕ.

Cantor's Theorem

Theorem: For any set A, |A| < |P(A)|.

That is, the power set is always strictly larger than the set itself. There is no surjection from A to P(A).

Proof (by contradiction): Suppose f: A → P(A) is surjective. Consider:

D = {a ∈ A | a ∉ f(a)}

Since f is surjective, D = f(d) for some d ∈ A. But:

If d ∈ D, then by definition d ∉ f(d) = D. Contradiction.
If d ∉ D, then by definition d ∈ f(d) = D. Contradiction.

So no surjection exists, hence |A| < |P(A)|. ∎

Corollary: |ℕ| < |P(ℕ)| < |P(P(ℕ))| < ... There are infinitely many sizes of infinity.

Cantor's Diagonalization

Theorem: The real numbers ℝ (even just (0,1)) are uncountable.

Proof: Suppose (0, 1) is countable, so we can list all reals in (0, 1):

r₁ = 0.d₁₁ d₁₂ d₁₃ d₁₄ ...
r₂ = 0.d₂₁ d₂₂ d₂₃ d₂₄ ...
r₃ = 0.d₃₁ d₃₂ d₃₃ d₃₄ ...
r₄ = 0.d₄₁ d₄₂ d₄₃ d₄₄ ...
⋮

Construct a new real number x = 0.e₁ e₂ e₃ e₄ ... where:

eᵢ = { 5 if dᵢᵢ ≠ 5
      { 6 if dᵢᵢ = 5

Then x differs from rₙ in the n-th decimal place, so x ≠ rₙ for all n. But x ∈ (0, 1) and x is not in our list. Contradiction. ∎

Cardinality Hierarchy

|ℕ| = |ℤ| = |ℚ| = ℵ₀           (aleph-null, countably infinite)
|ℝ| = |P(ℕ)| = 2^ℵ₀ = c        (continuum)
|P(ℝ)| = 2^c                    (strictly larger)

The Continuum Hypothesis (CH) states: there is no set whose cardinality is strictly between |ℕ| and |ℝ|. Gödel and Cohen proved that CH is independent of ZFC — it can neither be proved nor disproved from the standard axioms.

Special Functions

Floor and ceiling:

⌊x⌋ = greatest integer ≤ x
⌈x⌉ = least integer ≥ x

Factorial: n! = n × (n-1) × ... × 2 × 1, with 0! = 1.

Fibonacci: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2).

Real-World Applications

Hash functions: A function from keys to indices. Not injective (collisions). Desired to be "close to" surjective for even distribution.
Encryption: Bijective functions (for invertibility). RSA uses modular exponentiation, which is bijective over the right domain.
Compression: An injective function from data to compressed representations (lossless). Cannot be injective from all strings to shorter strings (pigeonhole principle) — hence compression exploits patterns.
Countability and computability: Programs are countable (finite strings). Real numbers are uncountable. Therefore most real numbers are not computable. Most functions from ℕ to ℕ are not computable. This is the foundation of uncomputability.
Database normalization: Functional dependencies (A → B) are literally functions from one set of attributes to another.
Type systems: Function types A → B directly model mathematical functions. Generics model parametric polymorphism (functions on type variables).