Comparing Infinities

Hello mathematicians, puzzlers, and other curious people!

A questioner over at Quora was curious about how to compare two particular infinite sets — the set of natural numbers and the set of prime numbers. Here\’s what I posted:

They’re the same size.

Since the prime numbers are a subset of the natural numbers, which are well-ordered, there’s a smallest, or first, prime number (2, as it happens). Then we can cross that out and take the smallest of what remains which is the second prime number (i.e., 3), and do that again to get the third prime number (i.e., 5), and so on, making the following familiar list:

2, 3, 5, 7, 11, 13, 17, 19, …

Then we can set up a bijection between prime numbers and their place in the list of primes:

f(2)=1, f(3)=2, f(5)=3, f(7)=4, etc.

Since we have a bijection, the sets must be the same size; since one of them is the natual numbers, that size is the infinity called countable.

(By the way, a similar argument applies to any non-finite subset of the natural numbers.)

When I mentioned a \”bijection,\” that\’s the technical term for a function that pairs up elements of two sets in such a way as to use up all elements of both sets (but, because it\’s a function, only once). If you\’ve studied invertible functions, that\’s a very closely related idea.

One fact I didn\’t prove, because the person clearly already is familiar with it, is that the set of prime numbers is infinite. Aside from because a teacher said so, do you have a good reason to believe this fact? You can talk this over in the comments section and form your own opinion about whether the questioner and I are right to accept prime numbers as an infinite set.

It might sound from my proof like all infinite sets are equal in size. But actually, strange though it seems, there are bigger infinities. Try to think of something that there might be more of than there are natural numbers; that could be another good topic to discuss in the comments section.

(Those of you who have already taken classes dealing formally with topics like number theory and cardinality, where you would have learned certain proofs in class, try to go easy on the spoilers for everyone else so they get a chance to figure something out.)

Calc You Later!