Difficulty: Intermediate | Prerequisites: Set notation, Cartesian products, basic algebra
Functions are one of the most heavily tested topics in CS 182. This section builds on set theory (you should already be comfortable with domains, codomains, and ordered pairs) and introduces the three properties that classify how a function maps inputs to outputs. Expect at least one proof of injectivity or surjectivity on every exam.
A function is injective (one-to-one) if different inputs always produce different outputs. It is surjective (onto) if every element in the codomain is actually hit by some input. A function that is both injective and surjective is bijective, meaning it pairs every input with exactly one unique output and vice versa.
Function (f: A → B)
A rule that assigns to each element of set A (the domain) exactly one element of set B (the codomain).
In simple terms, every input gets exactly one output. Two different inputs may share an output, but one input cannot produce two outputs.
Injective (one-to-one)
A function f is injective if f(x₁) = f(x₂) implies x₁ = x₂. Equivalently, distinct inputs always give distinct outputs.
In simple terms, no two different inputs land on the same output. Think of it as: every output has at most one arrow pointing to it.
Surjective (onto)
A function f: A → B is surjective if for every y ∈ B, there exists some x ∈ A such that f(x) = y.
In simple terms, every element of the codomain is actually used. Nothing in B is left uncovered.
Bijective (one-to-one correspondence)
A function that is both injective and surjective. Every element of B is hit exactly once.
In simple terms, there is a perfect pairing between A and B, with no leftovers on either side.
Counterexample
A single specific case that disproves a universal claim. To show a function is not injective, you find two different inputs that produce the same output.
In simple terms, one concrete failure is enough to kill the claim.
The standard technique: assume f(x₁) = f(x₂), then show algebraically that x₁ = x₂.
Worked example: Prove f: ℝ → ℝ, f(x) = (√3 / 2)x + 4 is injective.
Assume f(x₁) = f(x₂).
Then (√3 / 2)x₁ + 4 = (√3 / 2)x₂ + 4.
Subtract 4 from both sides: (√3 / 2)x₁ = (√3 / 2)x₂.
Divide both sides by √3 / 2 (which is nonzero): x₁ = x₂.
Since equal outputs force equal inputs, the function is injective.
The key insight: a linear function with a nonzero slope is always injective over ℝ.
The standard technique: take an arbitrary y in the codomain, solve for x in terms of y, and verify that x is in the domain.
Worked example: Prove f: ℝ → ℝ, f(x) = (√3 / 2)x + 4 is surjective.
Let y be any real number. Solve (√3 / 2)x + 4 = y for x.
x = (y − 4) · (2√3 / 3).
Since y is real, x is real. So x is in the domain ℝ.
Substituting back confirms f(x) = y.
Every element of the codomain has a preimage, so the function is surjective.
Show both injectivity and surjectivity. The worked examples above together prove that f(x) = (√3 / 2)x + 4 is bijective.
To show a function is not injective, find two distinct inputs that map to the same output.
Worked example: Show f: ℝ × ℝ → ℝ × ℝ, f(x, y) = (x/√2 + y/√2, x/√2 + y/√2) is not injective.
Try (x₁, y₁) = (2, 0) and (x₂, y₂) = (1, 1).
f(2, 0) = (2/√2 + 0, 2/√2 + 0) = (√2, √2).
f(1, 1) = (1/√2 + 1/√2, 1/√2 + 1/√2) = (√2, √2).
The inputs are different but the outputs are identical.
One counterexample is sufficient. The function is not injective.
Why does this function fail? Both output components are identical (x/√2 + y/√2 appears twice). This means the function maps ℝ² into a one-dimensional line in ℝ², collapsing information. Any two points (x, y) with the same value of x + y will produce the same output.
Injectivity proof template:
Assume f(x₁) = f(x₂).
Manipulate algebraically.
Conclude x₁ = x₂.
Surjectivity proof template:
Let y be an arbitrary element of the codomain.
Solve f(x) = y for x.
Verify x is in the domain.
Conclude that y has a preimage.
Counterexample template (disproving injectivity):
Find specific x₁ ≠ x₂ with f(x₁) = f(x₂).
State the inputs, compute both outputs, confirm they match.
Conclude: f is not injective.
Bijections are the basis of encryption: a cipher must be bijective so that every encrypted message can be uniquely decrypted. Injective functions model database primary keys, where no two records share the same key. Surjective functions model hash functions in the ideal case, where every bucket is used.
Students often try to prove injectivity by picking one specific pair of inputs. You must start from the general assumption f(x₁) = f(x₂) and argue for all inputs, not just a chosen pair. (Disproving injectivity, by contrast, requires only one pair.)
Students often forget to verify the domain when proving surjectivity. If f: ℕ → ℕ and your formula for x yields a negative number, the proof fails.
Students often confuse the codomain with the range. A function f: ℝ → ℝ defined by f(x) = x² is not surjective because negative numbers in the codomain have no preimage, even though the range (nonneg reals) is fully covered.
Students often assume that showing a function is not injective also means it is not surjective. These are independent properties.
⚠️ The injective proof via "assume f(x₁) = f(x₂), derive x₁ = x₂" is almost guaranteed to appear. Practise until the template is automatic.
⚠️ Counterexamples must be fully computed, both inputs and both outputs written out. A claim without the calculation is incomplete.
⚠️ For multi-variable functions (like f: ℝ × ℝ → ℝ × ℝ), check whether different input pairs can produce the same output pair. Look for symmetry or repeated expressions in the output components.
⚠️ When the domain and codomain are both ℝ, a linear function ax + b with a ≠ 0 is always bijective. This is a quick sanity check.
True or false: Every bijective function has an inverse. True.
True or false: f(x) = x² from ℝ to ℝ is injective. False. f(−2) = f(2) = 4.
Fill in the blank: To disprove injectivity, you need ___ counterexample(s). One.
True or false: If f: A → B is surjective, then |A| ≥ |B| (for finite sets). True.
Q: Prove that f: ℝ → ℝ, f(x) = 3x − 7 is injective.
A: Assume f(x₁) = f(x₂). Then 3x₁ − 7 = 3x₂ − 7. Add 7 to both sides: 3x₁ = 3x₂. Divide by 3: x₁ = x₂. Therefore f is injective.
Q: Is the function f: ℤ → ℤ, f(x) = x² surjective? Why or why not?
A: No. For example, there is no integer x such that x² = 3 (since √3 is irrational). So 3 ∈ ℤ has no preimage, and f is not surjective.
Q: Give a function from {1, 2, 3} to {a, b} that is surjective but not injective.
A: f(1) = a, f(2) = b, f(3) = a. Both a and b are hit (surjective), but f(1) = f(3) = a with 1 ≠ 3 (not injective).
Q: If f: ℝ × ℝ → ℝ is defined by f(x, y) = x + y, is f injective?
A: No. f(1, 2) = f(0, 3) = 3, but (1, 2) ≠ (0, 3). One counterexample suffices.
Bijective functions connect directly to counting arguments: if you can build a bijection between two sets, they have the same cardinality. This is the core of many combinatorics proofs later in the course.
Injective and surjective properties also reappear in the study of relations and partial orders. A function that is injective corresponds to a relation where each element in the range has a unique preimage.
In later courses, the concept of a bijection underpins group theory in abstract algebra, where bijections on a set form the symmetric group.
Tags: functions, injective, one-to-one, surjective, onto, bijective, bijection, counterexample, proof, domain, codomain, range, preimage, inverse function, CS 182, Purdue, discrete mathematics, foundations of computer science