---
tag: 0GV2573FP4
kind: statement
role: theorem
name: Bijection principle
msc: [05A19]
uses: [05099E1NMJ]
sources:
  - url: https://en.wikipedia.org/wiki/Bijective_proof
    locator: lead section
---

## 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|0R7JS3DP3W]] is a standard example. It uses the map $S \mapsto X \setminus S$ on the subsets of a finite set $X$.
[[Dyck words|0R9JR0465V]] and [[binary trees|02A8EMC83C]] are both counted by [[Catalan numbers|092DRBFKMG]], 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.