Bijection principle

Statement

Let $A$ and $B$ be finite sets. If there is a bijection $f : A \to B$, then $|A| = |B|$. Conversely, if $|A| = |B|$, then there is a bijection from $A$ to $B$.

Remarks

A bijective proof shows that two sets have the same size by a bijection between them. The proof of the symmetry of binomial coefficients is a standard example. It uses the map $S \mapsto X \setminus S$ on the subsets of a finite set $X$. Dyck words and binary trees are both counted by Catalan numbers, and a bijection explains this.

Explanations

L1 human

To show that two collections have the same size, you can pair each element of one with exactly one element of the other. For example, the subsets of $\{1, 2, 3\}$ pair with the words of length 3 in the letters 0 and 1. A subset gives the word with 1 in the positions of its elements.