Story #3

An Infinity of Infinities

by Corina Murg

How do we decide when two quantities are equal? Simple: we measure them. Take for example two different sets of numbers, set A = {1, 3.4, 5, 8.9, 10, 14, 18} and set B = {2, 4, 6, 8, 10, 12, 14}. We count the elements of A (seven), then we count the elements of B (seven), and conclude that A has the same number of elements as B does.

Now let’s say we are thinking about comparing the set of natural numbers N with the set of rational numbers Q. Simple? No. Because the set of rational numbers is infinite, just as the set of natural numbers is also infinite. Does it even make sense to compare the two sets since both are infinitely large? Can there be an infinite set that is larger than another infinite set? And after all, in the words of Gauss, “the infinite is only a manner of speaking.”

Fortunately for the world of mathematics, in the early 1870’s, a Russian born mathematician, Georg Cantor concluded otherwise and set to find a method for comparing infinite sets. His idea was that instead of counting each element of a set, which was an impossible task, one should use the very basic approach of creating a one-to-one correspondence between the elements of the two sets.

Cantor explains his method with the following definition: “Two sets M and N are equivalent … if it is possible to put them, by some law, in such a relation to one another that to every element of each one of them corresponds one and only element of the other.” When two sets have the same number of elements, neither set will have any unpaired element. We say that the two sets have the same cardinality. The example used by William Dunham in his book “Journey through Genius” reveals the essence of this definition:

”… imagine an audience filtering into a large auditorium. To answer the question of           whether there are as many spectators as seats, we could go through the tedious process of  counting both audience and chairs and then compare our final counts. But instead, we could simply ask all in attendance to sit down. If each person had a seat and each seat had a person, the answer is “yes,” since the very process of sitting has exhibited a perfect one-to-one correspondence.

If we consider the set of natural numbers N = {1, 2, 3, 4, 5, …} and the set of even natural numbers E = {2, 4, 6, 8, 10, …}, we can pair up every element in N with one and only one element in E.

The two sets have the same cardinality, written as |N| = |E|, and Cantor chose  , a Hebrew letter, to represent this cardinality. Any infinite set that has a one-to-one correspondence with the set of natural numbers is called a denumerable or countable infinity, and its cardinality is . (A countable infinity is a set that continues to infinity, but its elements can be ordered just like the set of natural numbers, with no numbers left unaccounted for.)

Are there other sets that have cardinality ? Using a similar method, we can prove that the set of integers Z = { … , -3, -2, -1, 0, 1, 2, 3, …} has cardinality .

Notice that every element in Z is being produced by the formula , where n is an element in N.

For example, when n = 3, the corresponding element in Z is

What about Q, the rational numbers set?

Intuitively we might think there are more rational numbers than natural numbers. Cantor has a simple and ingenious answer that proves this intuition wrong: arrange all the rational numbers by rows and columns such that all are accounted for. Then we can set them in correspondence with elements in N.

Notice how the row number gives us the denominator of the element in Q.

Where would we find 91/150 in this diagram? We would go to row 150, column 181. Why column 181? Because every positive integer is followed by its negative counterpart. Number 91 has before it all the integers from – 90 to -1 and from 1 to 90, a total of 180 numbers.

Every rational number is accounted for in this diagram, with some elements repeating themselves. The arrows skip over elements that have already been accounted. For example, once we account for 1, we can ignore its “copies” 2/2, 3/3 , etc. Once we account for 1/2, we can ignore 2/4, 3/6, etc.

Now we can use the above diagram to create a correspondence map between elements in sets N and Q, using only one “copy” of each element in Q:

Therefore |N| = |Q| = |Z| = |E| = .

Now let’s pause and think: is every infinity numerable? Could R, the set of all real numbers, have the same cardinality as N? Or is the infinity of R greater than the infinity of N?

Back to Stories of Mathematics Page

Recent stories

How to Measure π in the Sands of the Nile?

Area of Circles

Ticket to Time Machine