Tuesday, April 28, 2015

A quick argument for the bijection principle

The bijection principle says that if we have two sets A and B and we can pair up all the objects of the two sets, then the the sets have the same number of members.

Some people don't like the bijection principle because it leads to the counterintuitive conclusion that there are as many primes as natural numbers.

Here's an argument for the bijection principle. Let's run the argument directly for the above controversial case—that should be enough of an intuition pump to get the general principle. Take infinitely many pieces of paper that are red on one side and blue on the other. Number the pieces of paper 1,2,3,..., putting the numerals down on the red sides. Then on the piece of paper numbered n on the red side, write down the nth prime on the blue side. Then:

  1. There are just as many natural numbers as red sides.
  2. There are just as many red sides as blue sides.
  3. There are just as many blue sides as prime numbers.
  4. So, there are just as many natural numbers as prime numbers.
It's very hard to deny that 4 follows from 1-3, and it's very hard to deny any of 1-3.

No comments: