How Do You Count Two Things Without Counting Either? Pair Them Up
By the BrainSnail editorial team. How these articles are written and checked, and how to tell us when one is wrong.
Matching the members of two collections perfectly, one to one with none left over, proves they are the same size without anybody having to count them.
What the matching requires
A pairing between two collections qualifies when every member of the first is matched to exactly one member of the second, and every member of the second is matched to exactly one member of the first. Nothing is left over on either side and nothing is matched twice. If such a pairing exists, the two collections have the same number of members. The point is that establishing this requires no counting at all, which is what makes it useful where counting is impossible.
The everyday version
The idea predates mathematics and is used constantly without a name:
- •Knowing every chair is taken and nobody stands, without counting
- •A shepherd matching stones to sheep to check none is missing
- •Tally marks, which pair a scratch with an item
- •Checking a set of plates against a set of guests
- •Dancing partners, where nobody sits out and nobody has two
- •In each case equality is established by matching rather than by number
Why it matters for infinity
The technique is the only one available for comparing infinite collections and it produces results that genuinely shocked mathematicians. The whole numbers can be matched perfectly with the even numbers, by pairing each number with its double, so those collections are the same size despite one apparently containing the other. The same works for the fractions, which can be arranged in a sequence and matched with the whole numbers. Georg Cantor then proved that no such matching is possible with the decimals between zero and one, which means some infinities are strictly larger than others.
The argument that shocked everybody
Cantor's proof that the decimals cannot be matched with the whole numbers is short enough to follow and is worth seeing. Suppose somebody claims a complete list pairing every whole number with a decimal between zero and one. Build a new decimal by taking its first digit different from the first digit of the first listed number, its second different from the second digit of the second, and so on down the diagonal. The result differs from every number on the list in at least one place, so it was not on the list, so the list was not complete. No list can be.
The proofs it makes easy
Counting arguments in mathematics are frequently reduced to finding a matching, which converts a hard arithmetic problem into a visible one. Proving that a set of a given size has a particular number of subsets is done by matching each subset with a string of yes and no answers, one per member. Proving two apparently different counting problems have the same answer is done by matching their solutions directly, which explains why they agree rather than merely confirming it. That style of argument is a whole branch of the subject and is regarded as producing the most satisfying proofs available.
The takeaway
Pairing every member of one collection with exactly one member of another, with nothing left over on either side, proves they are the same size without counting. That is the only method available for infinite collections, and it shows the whole numbers match the even numbers and the fractions while failing to match the decimals. Matching also turns hard counting proofs into visible ones.