Constructing Bijections

Prove two sets are equinumerous with an explicit pairing.

The idea

A bijection is a rule pairing every element of a set $A$ with exactly one element of a set $B$, and every element of $B$ with exactly one element of $A$. If a bijection between $A$ and $B$ exists, then $|A| = |B|$, so a count of $B$ is also a count of $A$.

Constructing a bijection is therefore a counting method. To count an awkward collection — the subsets of a set, the routes across a grid — encode its objects as the objects of a collection you already know how to count, and count that one instead. For instance, the subsets of a set pair with the binary strings that record, bit by bit, which elements are present. The awkward collection never has to be listed.

A rule qualifies as a bijection when it is one-to-one (different objects of $A$ never produce the same object of $B$) and onto (every object of $B$ is produced by some object of $A$). The fastest check is usually to exhibit the reverse rule: if each object of $A$ can be recovered from its image, then nothing was merged and nothing was missed, which settles both conditions at once.

Ways to work on it

• Walkthrough. Match subsets to binary strings to count them.
• Practice. Count a set by a bijection to an easier one.
• Hardest. Prove even and odd subsets are equinumerous, then count.

Not sure where to start? Take the ten-question placement test.