Functions

Definition

Function

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

A is the domain, B is the codomain. The range (or image) of f is {f(a) | a ∈ A} ⊆ B.

Definition

Injective (One-to-One)

A function f: A → B is injective (one-to-one) if different inputs always give different outputs: f(a₁) = f(a₂) implies a₁ = a₂.

Equivalently, no two elements in A map to the same element in B.

Example: f(x) = 2x is injective on ℤ. f(x) = x² is NOT injective on ℤ because f(2) = f(-2) = 4.

Definition

Surjective (Onto)

A function f: A → B is surjective (onto) if every element of B is mapped to by some element of A: For all b ∈ B, there exists a ∈ A such that f(a) = b.

Equivalently, the range of f equals B.

Example: f: ℤ → ℤ defined by f(x) = x + 1 is surjective. f: ℤ → ℤ defined by f(x) = x² is NOT surjective (e.g., -1 is not in the range).

Definition

Bijective (One-to-One Correspondence)

A function that is both injective AND surjective is called bijective. A bijection establishes a perfect pairing between the elements of A and B.

If f: A → B is a bijection, then |A| = |B| (for finite sets), and f has an inverse function f⁻¹: B → A.

Example

Classifying Functions

f: {1,2,3} → {a,b,c} with f(1)=a, f(2)=b, f(3)=c. Injective ✓ (all outputs distinct), Surjective ✓ (all of {a,b,c} covered), Bijective ✓.

g: {1,2,3} → {a,b,c} with g(1)=a, g(2)=a, g(3)=b. Injective ✗ (g(1)=g(2)), Surjective ✗ (c not in range), Bijective ✗.

Definition

Composition of Functions

If f: A → B and g: B → C, the composition g ∘ f: A → C is defined by (g ∘ f)(a) = g(f(a)).

Apply f first, then g.

Example: f(x) = x + 1, g(x) = 2x. (g ∘ f)(3) = g(f(3)) = g(4) = 8. (f ∘ g)(3) = f(g(3)) = f(6) = 7.

Note: g ∘ f ≠ f ∘ g in general (composition is not commutative).