Home / Courses / Intro to Proofs / Unit 8

Intro to Proofs Unit 8: Functions: Injective, Surjective, Bijective

Functions are the links between sets. This unit defines injective, surjective and bijective functions, shows how to prove each property, and connects them to composition, inverses and counting.

Covers: Domain, codomain and range, Injective functions, Surjective functions, Bijections and inverse functions, Composition of functions, Images and preimages of sets, Counting functions between finite sets

Study guide

A function f: A → B assigns to each element of the domain A exactly one element of the codomain B. The range or image f(A) = {f(a) : a ∈ A} is the set of outputs actually produced, which may be smaller than B. The same rule can have different properties depending on the domain and codomain: x² is neither injective nor surjective as a map ℝ → ℝ, surjective as a map ℝ → [0, ∞), and bijective as a map [0, ∞) → [0, ∞). So always state the domain and codomain before asking whether a function is one-to-one or onto.

f is injective (one-to-one) if f(a₁) = f(a₂) implies a₁ = a₂: distinct inputs give distinct outputs. To prove it, assume f(a₁) = f(a₂) and use algebra to show a₁ = a₂. To disprove it, give two different inputs with the same output. f is surjective (onto) if for every b ∈ B there is some a ∈ A with f(a) = b. To prove it, take an arbitrary b, find a candidate a (often by solving f(a) = b), check that a is in the domain, and verify f(a) = b. To disprove it, name a b that is never hit.

f is bijective if it is both injective and surjective, and exactly then it has an inverse f⁻¹: B → A with f⁻¹(f(a)) = a and f(f⁻¹(b)) = b. Find the inverse by solving y = f(x) for x. Composition (g ∘ f)(x) = g(f(x)) applies f first. Compositions of injections are injective and of surjections are surjective. Going backward, if g ∘ f is injective then f is injective, and if g ∘ f is surjective then g is surjective. If g ∘ f = id_A, then f is injective and g is surjective, but neither need be a bijection.

For S ⊆ A, the image is f(S) = {f(x) : x ∈ S}, and for C ⊆ B the preimage is f⁻¹(C) = {x ∈ A : f(x) ∈ C}. The preimage makes sense even when f has no inverse. Preimages respect unions, intersections and complements exactly, but images only satisfy f(S ∩ T) ⊆ f(S) ∩ f(T). For finite sets with |A| = m and |B| = n there are nᵐ functions and n(n − 1)⋯(n − m + 1) injections, and surjections are counted by inclusion-exclusion. When |A| = |B| is finite, injective and surjective are equivalent.

Key ideas

• A function gives every domain element exactly one output.
• Injective: equal outputs force equal inputs.
• Surjective: every codomain element has a preimage.
• A function is invertible exactly when it is bijective.
• Changing the domain or codomain can change injectivity or surjectivity.
• If g ∘ f is injective then f is; if g ∘ f is surjective then g is.
• For finite sets of the same size, injective and surjective are equivalent.

Formulas and rules

Common mistakes

• Proving injectivity by assuming a₁ = a₂ and showing f(a₁) = f(a₂), which holds for every function.
• Forgetting to check that the proposed preimage lies in the domain when proving surjectivity.
• Confusing the codomain with the range.
• Writing g ∘ f but applying g first.
• Confusing the preimage f⁻¹(C) with an inverse function, which may not exist.

Before the test, make sure you can

• Identify the domain, codomain and range of a function.
• Prove a function is injective by assuming f(a₁) = f(a₂).
• Prove a function is surjective by solving f(a) = b and checking the domain.
• Disprove injectivity or surjectivity with explicit counterexamples.
• Find the inverse of a bijection and state its domain.
• Prove and apply the composition facts for injective and surjective maps.
• Compute images and preimages of sets.
• Count functions, injections and surjections between finite sets.

Words to know

Function

A rule f: A → B giving each element of A exactly one element of B.

Domain

The set A of allowed inputs of f: A → B.

Codomain

The set B in which outputs of f: A → B must lie.

Range (image)

f(A) = {f(a) : a ∈ A}, the set of outputs actually produced.

Injective

One-to-one: f(a₁) = f(a₂) implies a₁ = a₂.

Surjective

Onto: every element of the codomain equals f(a) for some a.

Bijective

Both injective and surjective; a one-to-one correspondence.

Inverse function

f⁻¹: B → A with f⁻¹(f(a)) = a and f(f⁻¹(b)) = b; exists iff f is bijective.

Composition

(g ∘ f)(x) = g(f(x)): apply f, then g.

Identity function

id_A(a) = a for every a ∈ A.

Image of a set

f(S) = {f(x) : x ∈ S}.

Preimage

f⁻¹(C) = {x : f(x) ∈ C}, defined for every function.

Left inverse

A function g with g ∘ f = id; exists exactly when f is injective (for nonempty domain).

Pigeonhole principle

If m > n objects go into n boxes, some box gets two; no injection exists from a larger finite set to a smaller one.

Sample practice questions

30 more questions like these, from level 1 to 5, are in the practice set.