To prove a function is a bijection, you need to show two things: the function is injective (one-to-one) and surjective (onto). These are separate properties that require separate arguments, and most proofs tackle them in sequence. There are also shortcut methods, like constructing an inverse function, that establish both properties at once.
What a Bijection Actually Requires
A bijection is a function f : A → B where every element in B gets “hit” exactly once. That breaks into two conditions:
- Injective (one-to-one): No two different inputs produce the same output. If f(x₁) = f(x₂), then x₁ = x₂.
- Surjective (onto): Every element in B is an output of some element in A. For every y ∈ B, there exists an x ∈ A such that f(x) = y.
If either condition fails, the function is not a bijection. A function that sends two different inputs to the same output fails injectivity. A function whose outputs don’t cover the entire codomain fails surjectivity. You need both.
Proving Injectivity
The standard technique uses the contrapositive form of the definition. Instead of showing that different inputs give different outputs (which is awkward to work with), you assume the outputs are equal and show the inputs must be equal too. The structure looks like this:
Start with: “Let x₁, x₂ be elements of A such that f(x₁) = f(x₂).” Then use algebra to manipulate that equation until you arrive at x₁ = x₂. If you can always reach that conclusion, the function is injective.
For a concrete example, suppose f : ℝ → ℝ is defined by f(x) = 3x + 7. Assume f(x₁) = f(x₂). Then 3x₁ + 7 = 3x₂ + 7. Subtract 7 from both sides: 3x₁ = 3x₂. Divide by 3: x₁ = x₂. Done. The function is injective.
For functions with multiple variables or more complex expressions, the algebra gets harder but the logic is identical. You always start from f(x₁) = f(x₂) and work toward x₁ = x₂ using whatever tools the function’s formula gives you: factoring, substitution, solving systems of equations.
Proving Surjectivity
Surjectivity requires a different approach. You need to show that every element in the codomain B actually has something mapping to it. The proof structure is:
Start with: “Let y be an arbitrary element of B.” Then find (or construct) an element x in A such that f(x) = y. If you can always produce such an x, the function is surjective.
Using the same example, f(x) = 3x + 7 with codomain ℝ. Pick any y ∈ ℝ. You need an x such that 3x + 7 = y. Solving gives x = (y − 7)/3. Since (y − 7)/3 is a real number for any real y, this x is in the domain. And plugging it back in confirms f((y − 7)/3) = 3·(y − 7)/3 + 7 = y. So every y in ℝ is covered, and f is surjective.
The key move in a surjectivity proof is “scratch work.” Before writing the formal proof, you solve the equation f(x) = y for x. That tells you what the preimage should be. Then in the actual proof, you present that x, verify it’s in the domain, and confirm f(x) = y. The scratch work is where you figure out the answer; the proof is where you verify it.
The Inverse Function Shortcut
If you can construct an inverse function, you prove bijectivity in one step instead of two. A function f : A → B is bijective if and only if there exists a function g : B → A satisfying both f(g(y)) = y for all y ∈ B, and g(f(x)) = x for all x ∈ A. These two conditions are sometimes written as f ∘ g = id_B and g ∘ f = id_A.
This works because the first condition (f ∘ g = identity) forces f to be surjective, since every y in B equals f(g(y)), meaning every y has a preimage. The second condition (g ∘ f = identity) forces f to be injective, since if f(x₁) = f(x₂), applying g to both sides gives x₁ = x₂.
When an inverse exists, it’s also unique. If two functions g₁ and g₂ are both inverses of f, they must be the same function. This is a useful sanity check: if your inverse candidate is ambiguous (you can’t pick a single output for some input), something has gone wrong.
For the f(x) = 3x + 7 example, the inverse is g(y) = (y − 7)/3. You verify: f(g(y)) = 3·(y − 7)/3 + 7 = y, and g(f(x)) = (3x + 7 − 7)/3 = x. Both compositions produce the identity, so f is bijective.
The Horizontal Line Test
For functions whose graphs you can draw or visualize, there’s a quick graphical check. Draw horizontal lines across the graph. If every horizontal line through the range hits the graph at exactly one point, the function is one-to-one. Combined with checking that the range covers the entire codomain, this confirms a bijection.
This test is useful for building intuition or checking your work, but it’s not a formal proof. In a written proof, you still need the algebraic argument. Think of it as a way to spot functions that aren’t bijective before you invest time in a proof attempt.
Why Domain and Codomain Matter
The same formula can be a bijection or not, depending on what sets you’re working with. This is one of the most common sources of confusion.
Take f(x) = x² − 5. Defined as f : ℝ → ℝ, it fails both conditions. It’s not injective because f(−2) = f(2) = −1. It’s not surjective because no input maps to any value below −5. But restrict the domain to positive reals and the codomain to y ≥ −5, making f : ℝ⁺ → [−5, ∞), and the same formula becomes bijective. Restricting the domain eliminates the mirror-image problem, and restricting the codomain eliminates the gap in the range.
Another example: f(x) = 1/x + 2 defined on all nonzero reals, f : ℝ\{0} → ℝ. This function is injective (different inputs always give different outputs) but not surjective, because no input produces the output 2. Narrowing the codomain to ℝ\{2} fixes this, and the inverse becomes g(y) = 1/(y − 2).
Before attempting any bijection proof, check that the domain and codomain are clearly specified. A proof that ignores these sets is incomplete.
Bijections Between Finite Sets
For finite sets, there’s a powerful constraint: a bijection between two finite sets can only exist if both sets have the same number of elements. If |A| = |B|, a bijection from A to B exists. If |A| ≠ |B|, no bijection is possible.
This gives you two practical tools. First, if you’re asked whether a bijection exists between two finite sets, just count. Second, if you’re working with finite sets of equal size, proving just injectivity or just surjectivity is enough. For finite sets with |A| = |B|, an injective function from A to B is automatically surjective (and vice versa), because there are exactly enough elements to pair up. This shortcut doesn’t work for infinite sets.
Putting a Proof Together
A complete bijection proof typically has this structure:
- State the function, domain, and codomain clearly. For example: “Let f : ℝ → ℝ be defined by f(x) = 3x + 7.”
- Prove injectivity. Assume f(x₁) = f(x₂), then derive x₁ = x₂ through algebraic steps.
- Prove surjectivity. Take an arbitrary y in the codomain, construct an x in the domain with f(x) = y, and verify both that x belongs to the domain and that f(x) actually equals y.
- Conclude. Since f is both injective and surjective, f is a bijection.
Alternatively, if the inverse approach is cleaner, define g : B → A explicitly, then verify f ∘ g = id and g ∘ f = id.
Whichever method you choose, the most common mistakes are forgetting to verify that constructed preimages actually belong to the domain, and neglecting to check both directions when using the inverse method. If you only show f ∘ g = id without also showing g ∘ f = id, you’ve only proven surjectivity, not the full bijection.