A bijection is a function that pairs every element in one set with exactly one element in another set, with nothing left over and no duplicates on either side. Think of it as a perfect matching: every input has its own unique output, and every possible output is actually reached by some input. In more formal terms, a bijection is a function that is both injective (one-to-one) and surjective (onto).
The Two Requirements: Injective and Surjective
A bijection has to satisfy two conditions simultaneously. Understanding each one separately makes the whole concept click.
A function is injective (one-to-one) when no two different inputs produce the same output. If you plug in 3 and get 7, then no other input can also give you 7. More precisely, whenever the outputs are equal, the inputs must have been equal too. The function f(x) = 2x is injective because if 2a = 2b, then a = b. But f(x) = x² is not injective over all real numbers because both 3 and −3 produce 9.
A function is surjective (onto) when every element in the target set actually gets hit by some input. There are no “orphan” values in the output set that nothing maps to. For example, f(x) = x² from real numbers to real numbers is not surjective because negative numbers like −4 never appear as outputs. But if you restrict the target set to only non-negative numbers, it becomes surjective.
A bijection requires both properties at once. Every output is used (surjective), and every output is used by only one input (injective). Combining those: each element in the output set has exactly one corresponding element in the input set.
A Simple Way to Visualize It
If you’re working with a graph on a coordinate plane, the horizontal line test tells you everything you need. Draw horizontal lines across the graph at every height. If every horizontal line crosses the curve at exactly one point, the function is a bijection. If some horizontal line misses the curve entirely, the function isn’t surjective. If some horizontal line crosses in two or more places, it isn’t injective.
You can also picture bijections with two columns of dots. Put the input set on the left and the output set on the right, then draw lines connecting them according to the function. In a bijection, every dot on the left connects to exactly one dot on the right, every dot on the right receives exactly one connection, and no dot on either side is left unconnected. It looks like a set of perfectly parallel, non-crossing lines.
Common Examples
The function f(x) = 2x + 1, from all real numbers to all real numbers, is a bijection. It’s injective because two different inputs always produce different outputs. It’s surjective because for any real number y, you can solve for x = (y − 1)/2, which is always a valid real number. Every output is accounted for exactly once.
The function f(x) = x³ over all real numbers is also a bijection. Each real number has a unique cube, and every real number is the cube of something. Contrast that with f(x) = x², which fails on both counts when defined over all real numbers: it’s not injective (positive and negative inputs share outputs) and not surjective (negative outputs are never produced).
The identity function, which simply returns whatever you give it (f(x) = x), is the most straightforward bijection possible. And any function that just rearranges a finite list, like shuffling a deck of cards, is a bijection from the set of positions to itself.
Why Bijections Guarantee an Inverse
One of the most important properties of a bijection is that it can always be reversed. If f is a bijection from set A to set B, then there exists an inverse function that goes from B back to A, undoing what f did. This inverse is itself a bijection.
This works precisely because of the two requirements. Surjectivity guarantees that every element in B has at least one input that maps to it, so the reverse function is defined everywhere on B. Injectivity guarantees that each element in B came from at most one input, so the reverse function gives a single, unambiguous answer. Together, the reverse mapping is a proper function, not just a vague relation.
Functions that aren’t bijections can’t be cleanly reversed. If f(x) = x², knowing the output is 9 doesn’t tell you whether the input was 3 or −3. The reverse mapping isn’t a function because it doesn’t give one clear answer.
Bijections and Counting
Bijections play a central role in understanding the size of sets. If a bijection exists between two sets, those sets have the same number of elements. This might seem obvious for finite sets: if you can perfectly pair up 5 students with 5 desks, there are the same number of each. But the principle extends to infinite sets, where it becomes the primary tool for comparing sizes. It’s how mathematicians prove, for example, that there are “as many” even numbers as whole numbers, despite even numbers being a subset.
For finite sets, the logic runs in both directions. If set A has n elements and there’s a bijection from A to B, then B also has exactly n elements. This is the formal basis for something we do intuitively whenever we count by matching items one-to-one.
Bijections in Cryptography
Bijections aren’t just abstract math. They show up in encryption, where the ability to reverse a function is essential. When an encryption algorithm scrambles your data, it needs to be reversible so the intended recipient can decrypt it. That means the scrambling step must be a bijection: each possible input maps to a unique output, and every possible output traces back to exactly one input.
Modern symmetric encryption algorithms use components called substitution boxes that are specifically designed as bijective mappings. Each block of input bits maps to a unique block of output bits of the same size. This bijective structure ensures the encryption can be undone with the right key while also providing resistance against attacks trying to recover that key. If the substitution weren’t bijective, information would be lost during encryption and decryption would be impossible.