Let A denote the set of all even numbers, and let B denote the set of all multiples of 4. Obviously, B is contained inside of A; every multiple of 4 is even. Since every other even number is a multiple of 4, it is intuitively clear that in the context of the natural numbers, A is not only bigger than B, but is "twice as big" as B, even though both sets have infinitely many elements. How can we make this precise?

We need an appropriate notion of size. What won't work is considering the cardinality of the sets A and B. The cardinality of a finite set is just the number of elements it has. Thus the cardinality of {1, 2, 3, ..., N} is N. Sets of this form can contain as many natural numbers as we want, but not all of them; the set of natural numbers is, of course, not finite. For this reason, we must declare the (infinite) cardinality of the natural numbers to be some symbol, call it X here. X is then an infinite cardinal, terror to altar boys everywhere; it is "bigger" than any number, in the sense that the size of any finite set is strictly smaller than X.

"Great!" you say. "Then the cardinality of the even numbers is X/2, since half the natural numbers are even, and for the same reason the cardinality of the multiples of 4 is X/4." Not so fast! Ignoring the fact that the attempting to extend arithmetic operations (including division) from real numbers to infinite cardinals leads to contradictions, consider the following: Imagine a hotel with infinitely many rooms, all occupied. A bus with infinitely many passengers pulls up to the hotel, and they all need a room. Too bad, right? All the rooms are already occupied.


"Wait!" says the hotelier. "There's plenty of room for all of you! Here, I'll just tell the guy in Room 1 to move to Room 2, the guy in Room 2 to move to Room 4, and, in general, the guy in Room N to move to Room 2N. Presto! All the odd-numbered rooms are now free! So, Passenger 1, you can have Room 1; Passenger 2, you get Room 3; Passenger 3, you get Room 5; and in general, Passenger N gets room 2N-1. Please enjoy your stay at Hilbert's Hotel!"

This silly story is meant to illustrate the existence of a one-to-one correspondence between the set of natural numbers and the set of even numbers: Every natural number corresponds to an even number via multiplication by two, and every even number corresponds to a natural number via division by two. The existence of such a correspondence is what it means for two infinite sets to have the same cardinality.

So the sets A, B, and the entire set of natural numbers are all the same size, in the sense of cardinality. If that's not weird enough, notice that I said that X is an infinite cardinal. Any set for which a one-to-one correspondence with the natural numbers (like the one above) exists has cardinality X; this is true of the natural numbers and all of its infinite subsets, but also the integers (allowing 0 and negative whole numbers) and even the rationals: all ratios n/m where n and m are integers. (If you think about it, this is very surprising, since the rational numbers have the property that you can always find another one between any two of them, which is certainly not true of the natural numbers. Writing down the one-to-one correspondence that exists between the rationals and the naturals is sort of a pain, but you can look it up.) Any set with cardinality X is called countable, and one must go all the way to the real numbers to find an infinite set which is uncountable. To see that no one-to-one correspondence between the reals and the naturals can exist, read Georg Cantor's "diagonal argument." It is conjectured that there are no cardinals strictly between X and the cardinality of the reals.


OK. So cardinality is a thing that says there are just as many even numbers as there are even and odd numbers, and if you think that means cardinality is bullshit, then I really can't blame you. Back to the drawing board: How do we capture, mathematically, the innocent idea that there are half as many evens as there are natural numbers?

Like this: How many natural numbers, up to and including 100 (and not including zero because ugh I don't want to get into it), are even? 50 - exactly half of them. How many are multiples of 4? 25 - exactly one quarter of them. What about up to 1000? Same result: 1/2 are even, 1/4 are multiples of 4. What about up to a million? Same result! Considering the proportion of increasingly large finite sets that a certain subset occupies allows us to sidestep the tricky business of infinity.

This notion of "size in context" is called density. Allow me to flail at a precise definition without too much notation: If A denotes a subset of the natural numbers, then the density of A in the natural numbers is the limit of the number of elements of A less than a certain number N, divided by N, as that number tends to infinity. If that didn't make any sense - or even if it did - think of the density of a subset of the natural numbers as the probability that you would randomly choose an element of that subset from among (an arbitrarily large subset of) the natural numbers. For even numbers, that probability is 1/2, since every other number is even. For multiples of 4, we get 1/4. Indeed, for multiples of any number M, we get 1/M.

For a finite set, we get 0: If you restrict yourself to the first N numbers, and your set has k elements, then the probability you'll randomly choose an element of your set is k/N (taking N larger than k). But as N tends to infinity, k/N tends to 0.

Yes. The probability that you will choose an element of a finite set from among all natural numbers is 0, even though those finitely many elements, perfectly good numbers themselves, totally exist and you could totally pick them, you can't say I could never pick them, I mean why couldn't I pick them, this makes no sense, I don't get it, math is bullshit — Deal with it. We get our hands on infinity by thinking about really big finite sets and what happens as those sets get bigger, and sometimes things happen that may be counterintuitive. (For example, there are infinite subsets of the natural numbers for which the probability of choosing an element of it randomly - that is, the limit I mentioned above - doesn't even exist! I can try to give an example in the comments, if anyone's curious.)

There are even infinite sets of numbers that have density 0. For example, the set of perfect squares {1^2, 2^2, 3^2, 4^2, ...} has density zero: Up to N^2, exactly N numbers are perfect squares - so N/N^2 = 1/N of them. Thus, up to N^2, with probability 1/N, you would choose a perfect square at random. By taking N (the size of my "sample set") as big as I want, I can make this probability as small as I want. Hence, among all natural numbers, the probability of choosing a perfect square is 0.


This post is already huge and unwieldy and has belabored many points, so let me wrap up real quick: I care about the primes. The set of primes is infinite, but as we saw above, that doesn't say much about its density. What are the chances that, if I picked a number at random, it would be prime?

Startlingly, the answer is zero. The primes occupy no proportion at all of the natural numbers. There are not a lot of them, in this sense. Now, here's where it gets good: A proof of this hinges on the fact that, in an entirely different sense, there are a lot of prime numbers.

There are not too many primes, because there are not too few primes. But why don't we save that for next time?