Infinity is weird: what’s bigger than big?

Posted on November 24, 2013 by skullsinthestars

The second in what will (probably) be a three-part series of posts on the size of the infinite, as described in mathematical set theory. The first post can be read here.

When I was young, there was a series of jokes of the “what’s grosser than gross?” variety. Imagine the grossest thing you can, and then ask: what’s even grosser than that?

I don’t really want to talk about the grossest things I can imagine — learning about science and nature has exposed me to more grossness than I ever wanted to know –but on a related note, we can ask the question: what is bigger than big? Or, to put it in more suggestive language, what is bigger than infinity?

In the previous post, we introduced what we called the “smallest” infinite number, $\aleph_0$ . This is the label for the cardinality, or size, of the infinite set of natural numbers: $1,2,3,\ldots$ . Once we had described how to “count” the size of an infinite set, we were able to demonstrate unusual identities, such as

$\aleph_0+\aleph_0 = \aleph_0$ ,

i.e. “infinity plus infinity equals infinity,” and

$\aleph_0\cdot \aleph_0 =\aleph_0$ ,

i.e. “infinity times infinity equals infinity.”

If this were the end of the story, it would be supremely unsatisfying, and hardly even mathematics*, since the conclusion seems to be that there is one size of infinity, and any manipulation of it simply returns the same size infinity.

But this is not the end of the story! We can demonstrate that there is a bigger infinity than $\aleph_0$ , and it has been hiding in plain sight, so to speak, in even some of the most elementary mathematics.

So what is this giant, “more infinite than infinite” set? It is the set of all numbers between 0 and 1, but excluding 0 and 1:

But how big is the set of numbers that lie between 0 and 1? There are clearly at least an infinite amount of them, because the set of fractions $1/2, 1/3, 1/4, 1/5, \ldots$ is infinite, and all of these points lie within the range.

In order to answer the question deeper, we should review how we compare the sizes of sets, in a slightly revised version of the argument in the last lecture.

Suppose we have two really big piles of M&Ms, and we want to make sure that the two piles are of equal size. The most obvious way to do this is to count the number of M&Ms in each pile, and compare the resulting numbers. However, for a really big stack, this is inefficient: we end up counting two really big piles, and there exists the very likely possibility of making a mistake. Furthermore, we usually don’t care about the actual number of M&Ms in the pile, only that the two sets are equal — by counting, we’ve gathered information we didn’t even want.

A more efficient strategy is pictured below. Instead of counting each pile, we simply line them up side by side, and determine if there is a perfect “one-to-one” match between the two piles.

This is a better option for two reasons. First, we effectively do half as many mathematical operations, since we do one “matching” for each pair of M&Ms. Second, we don’t need to worry about keeping track of the total number of M&Ms at all, only whether every M&M of one pile has a partner in the other.

This second advantage is important for working with infinite sets. Since we can’t “count” an infinite number of objects, the only way we can compare the sizes of two different infinite sets is to see if we can make a similar “one-to-one correspondence” between elements of the sets.

In the previous post, we used this correspondence to show that the set of natural numbers $N = \{1,2,3,4,5,6,\ldots\}$ is the same size as the even numbers $E = \{2,4,6,8,10,\ldots\}$ , even though superficially it would seem that there should be fewer even numbers. We also showed that the set of rational numbers (i.e. fractions such as 1/1, 1/4, 5/3, and so forth), is the same size as the set of natural numbers, even though it seems that there should be more of them. Also the set of algebraic numbers, i.e. those numbers x that satisfy

$a_n x^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\ldots +a_1 x +a_0=0$ ,

for any integer $a_n$ , are also the same size as the set of natural numbers. All of these are what are known as countable infinities, since they can be arranged in order, and since there is no finite number that can be used to describe their size, it was given the label $\aleph_0$ by Georg Cantor, who first explored the subject.

Now we turn our attention to the set of numbers between 0 and 1. These numbers form what we call a continuum: there is a continuous range of numbers that lie between 0 and 1 without any “gaps.” In other words, there is a number that corresponds to every point on the line between 0 and 1.

It is potentially a bit trickier to determine the cardinality (size) of such an infinite set, but we can compare different size continuums via a geometrical argument. For instance, it is easy to demonstrate, as shown in the figure below, that the size of the line segment between 0 and 1 is equal to the size of the real numbers, i.e. all numbers that lie between -∞ (minus infinity) and ∞ (infinity).

To do so, we take the line segment of points between 0 and 1, and fold it, producing a “kink,” and place it above the infinite real line as shown. We then draw another line (shown in red) between the point above the kink that passes through both the line segment and the real line. For every point that the red line hits on the real line (in blue), there is a corresponding point (in red) on the line segment. As the red line gets more horizontal, it intersects the real line further along its length, in principle hitting it at “infinity” when it hits the point 1 on the line segment.

This shows geometrically that there is a one-to-one correspondence between points on the line segment and those on the infinite real line! The set of points on the finite line segment is the same size as the set of points on the infinite line. We refer to all sets of this type as the continuum, and label the size of the set as $\mathcal{C}$ .

But is the size $\mathcal{C}$ of this set the same as $\aleph_0$ ? It would seem that there are two possibilities: either they are the same size, in which case we should be able to find a one-to-one correspondence between the natural numbers and the continuum, or they are of different sizes, in which case we should be able to show that the one-to-one correspondence is impossible. In what must be one of the most remarkable and beautiful proofs in all of mathematics, Georg Cantor showed that the latter case is true: the continuum is a larger infinity than the set of natural numbers!

We prove this by contradiction, using what is now known as Cantor’s diagonal argument. First, we note that every number between 0 and 1 can be written in an infinite decimal form. For example, the whole number 5 can be written as $5.00000000\ldots$ , where 1/3 can be written $3.33333333\ldots$ . Now let us suppose that the set of numbers between 0 and 1 are countable; this suggests that we can put them in some list in correspondence with the natural numbers. The exact order is irrelevant; we imagine the nth digit of the first number is labeled $a_n$ , and so forth. We may draw the following picture:

Seems simple enough, right? Now Cantor constructed a new number, and let its first digit equal anything except $a_1$ , its second digit equal anything except $b_2$ , and so forth. The result is that the new number is defined by avoiding the “diagonal” digits on the list.

(Here I’ve used the notation of logic, where $!a_1$ means “not $a_1$ .”)

This new number, however, does not exist in our countable list — it has one digit different from every member of our list! We could try and add the new number to the beginning of the countable list, but we could then use the diagonalization method to construct another number that is not on the list. This process can be continued infinitely, without any change: it is therefore impossible to put the continuum into one-to-one correspondence with the natural numbers. Because there are more elements to the continuum, we can say that the continuum is an infinite set of larger size than the natural numbers. Symbolically, we may say that $\mathcal{C}$ is larger than $\aleph_0$ !

The implications of this result are huge. For one thing, it is worth noting that the real numbers, with cardinality $\mathcal{C}$ , contain algebraic numbers as a subset, which in turn contain the rationals as a subset, which in turn contain the natural numbers as a subset. In diagram form, we can illustrate this as follows.

Hierarchy of number types. (Adapted from Of Men and Numbers.)

We have already seen that the natural numbers have a size $\aleph_0$ , though they are a subset of the rational numbers, which also have a size $\aleph_0$ , which in turn are a subset of the algebraic numbers, which have size $\aleph_0$ . But the real numbers have a size $\mathcal{C}$ , which implies that the transcendental numbers also have a size $\mathcal{C}$ !

What are the transcendental numbers? They are any number that cannot be written as the solution to an algebraic equation. Most of us are only familiar with a few of these numbers, such as $\pi = 3.14159\ldots$ and Euler’s number $e = 2.71828\ldots$ , and in fact relatively few transcendental numbers are known. But, from the arguments above, we see that the transcendental numbers are a larger infinity than any of the numbers that we usually work with. Most of the numbers we work with and encounter in our everyday mathematical calculations are a negligible subset of the complete set of real numbers!

Cantor’s results found quite a bit of resistance in his time, in large part because his contemplations of infinity seemed to come into conflict with theological perceptions of the concept. Even today, there are a large number of “Cantor cranks” who are convinced, based on intuition, that his results are flawed and have come up with their own supposed counterexamples, despite the fact that the vast majority of mathematicians over a century have accepted Cantor’s results. (See “Good Math, Bad Math” for a multiple debunkings of these cranks, here, here and here.)

If we’re willing to accept Cantor’s proof, however, we can find even more unusual properties of this new infinity $\mathcal{C}$ ! For one thing, we can show that the set of all points in the square with $0 < x <1$ and $0< y<1$ have the same cardinality $\mathcal{C}$ .

The proof of this comes from the decimal notation of the numbers in a line segment again.

The “unit square,” excluding the boundary. A single point (x,y) is illustrated.

We can imagine writing the x-coordinate in a decimal notation as

$x = 0.x_1x_2x_3x_4x_5\ldots$

and the y-coordinate as

$y =0.y_1y_2y_3y_4y_5\ldots$ .

The question, then, is whether we can make a one-to-one correspondence between points in the square and points on a single line segment. We can do so by matching each point in the square to a point on the line segment given by

$r =0.x_1y_1x_2y_2x_3y_3x_4y_4\ldots$ .

This is a decimal number between zero and one itself, and with a bit of thought it becomes clear that every possible number between zero and one can be constructed from the x– and y-coordinates.

Therefore a two-dimensional region of space contains the same cardinality as a one-dimensional line. This argument can be extended to any finite-dimensional space. The set of points in three-dimensional space has the same cardinality as a one-dimensional line, as does a four-, five-, or N-dimensional space!

In equation form, this is equivalent to saying that

$N\cdot \mathcal{C} = \mathcal{C}$ .

We can also make the logical progression that

$\aleph_0\cdot \mathcal{C}=\mathcal{C}$ ,

and even

$\mathcal{C}\cdot\mathcal{C}=\mathcal{C}$ !

We now have demonstrated two different sizes of infinity, which we have labeled $\aleph_0$ and $\mathcal{C}$ ! Are there even larger size infinities? In fact, we can prove that there are an infinite number of increasingly larger infinities! … but this will be discussed in the third part of this series of posts!

***

* Adapting some arguments from J. Breuer’s “Introduction to the Theory of Sets” (Dover, 2006), which is also a nice introduction to the subject.

This entry was posted in Mathematics. Bookmark the permalink.

14 Responses to Infinity is weird: what’s bigger than big?

mjfairch says:

November 24, 2013 at 11:24 pm

Dear Dr. Gbur,

I love that you�re doing a three-part post about this topic. As you�re discussing Cantor, this seems the appropriate time to suggest the following 5-part BBC miniseries on Cantor, Boltzmann, Turing, and Godel, titled �Dangerous Knowledge.” (The ads are annoying, but the show is well-worth the occasional ad interruption.) Yes, one can pick nits with it, but overall it�s pretty decent. I apologize if I�ve suggested this to you before.

http://www.dailymotion.com/playlist/x1cbyd_xSilverPhinx_bbc-dangerous-knowledge/1

I love your blog. Keep it coming! (No need to respond.)

Mike

Reply
- skullsinthestars says:
  
  November 25, 2013 at 12:13 pm
  
  I’ll respond anyway — thanks!
  
  Reply
Yoron says:

November 25, 2013 at 3:57 am

Sorry, lose you there. Either there is a one to one correspondence, and then it shouldn’t matter how I construct the mathematics. No matter how one define it I should be able to lift out Cantors ‘new numbers’, aside the natural numbers for example, in a one to one correspondence. And even if it logically seems to exist different magnitudes of infinities, I don’t expect it to stop that ‘one to one correspondence’, ever.

So you suddenly seem to have a cat biting its tail here. No end to a one to one correspondence, at the same time as it is assumed that one infinity is bigger?

Reply
- skullsinthestars says:
  
  November 25, 2013 at 12:30 pm
  
  Not entirely sure of what your point is, but I’ll try and answer.
  
  When you say “shouldn’t matter how I construct the mathematics,” I assume you mean writing the real numbers in decimal form. In fact, it doesn’t depend on that assumption: we can apply the diagonal argument to numbers in binary form, octal form, hexidecimal form, base 18-form, or whatever number representation we want! Furthermore, the diagonal proof is not the only proof of uncountability of the real numbers: his first proof of the result (http://en.wikipedia.org/wiki/Cantor%27s_first_uncountability_proof) relied not at all on a number representation. It just turns out that the diagonal argument is much more elegant way of demonstrating the result.
  
  “No matter how one define it I should be able to lift out Cantors ‘new numbers’, aside the natural numbers for example, in a one to one correspondence.”
  
  The problem is that you’re making a statement without proof, and Cantor’s diagonal argument is a proof in direct contradiction to your statement! Cantor’s argument demonstrates that, no matter how you try to line up the real numbers next to the natural numbers, I can always find another number that won’t be included in your infinite list. It then follows that there are is fact an “infinite” set of numbers that won’t be included in your list. (Redo the diagonal argument, but let the first digit of the new number be “!b_1” and the second digit of the new number be “!b_2,$ with the rest unchanged.)
  
  Another way to understand that the real numbers are uncountable: given any two numbers between 0 and 1, no matter how close together, I can find another number that lies between them. When looking at the natural numbers, I can always identify the “nearest neighbors” of any number: for instance, 10 is adjacent to 9 and 11. However, there is no “nearest neighbor” for any real number, because for any neighbor I choose there’s always another one closer! Loosely speaking, the real numbers are so densely packed that they cannot be organized in a simple countable manner.
  
  (Updating post to add comment about density.)
  
  Reply
Simplicio says:

November 25, 2013 at 2:55 pm

“How can we understand this fundamental difference in size between the real numbers and the natural numbers? It helps to think about how densely packed the numbers are in their respective lists. If we consider the set of natural numbers in order (something we are not obliged to do), every number has a pair of nearest neighbors: 10, for instance, is right next to 9 and 11. No real number, however, has a nearest neighbor: for any pair of real numbers, no matter how close together, there exists yet another number that lies between them. Loosely speaking, this density of the real numbers indicates the impossibility of ordering them, and consequently that the infinite size of the reals is larger than the infinite size of the naturals.”

This argument is kind of weird. The natural numbers do in fact have two nearest numbers, but other systems that are the same size (aleph_null) don’t, at least when using the conventional ordering. The rational numbers, for example. There is no rational numbers (or set of rational numbers) that are nearest neighbors of a given number. You can always find another rational number in the interval between two others.

Yet the fact that you can put them on a list does suggest that you can construct some definition of “nearness” for which its true that each rational has two nearest neighbours.

Reply
- Simplicio says:
  
  November 25, 2013 at 3:04 pm
  
  So looking at the previous infinities post, it looks like using the ordering there 1 and .5 are the nearest neighbors of the number 2 (and are “equidistant from it), while numbers we think of as being closer to 2 (like 1.75) are quite a bit further, and most notably, 1.75 isn’t “between” 2 and 1.
  
  I’m not really going anywhere with this. It just seems interesting and counter-intuitive that you can take a “dense” number system and change its ordering to make it “not dense”.
  
  Reply
- skullsinthestars says:
  
  November 25, 2013 at 3:18 pm
  
  Yeah, that statement, which I added as an afterthought after posting, probably is more obfuscating than clarifying. I’ve taken it back out until I’ve given it some more thought.
  
  Reply
allmediamath says:

November 28, 2013 at 2:11 pm

I agree with you that Cantors proof must be one of (if not the) the most beautiful proof in mathematics … I came across it several times already and it always “wows” me. You don’t even need higher math to understand it, the concept of correspondence and some logic is sufficient. Thanks for the post!

Reply
- skullsinthestars says:
  
  November 29, 2013 at 11:47 am
  
  You’re welcome, and thanks for the comment!
  
  Reply
Akhil Balraj says:

December 5, 2013 at 3:22 pm

I’m a little confused. It looks like the Cantor’s diagonal argument shows that a particular method of creating a one to one correspondence between the two sets will not work rather than that there is no way to create such a correspondence. I’m missing the bit where the proof reveals that in general there is no possible way to create the one to one correspondence. Help would be appreciated but in any case I found this series of posts very interesting.
Thanks,
Akhil

Reply
- skullsinthestars says:
  
  December 5, 2013 at 5:38 pm
  
  The trick, such as it is, is that Cantor’s argument doesn’t specify the method for attempting to make the correspondence. If any one-to-one correspondence exists between the naturals and the reals, it must involve lining up the naturals next to the reals exactly as shown, which is pretty much the definition of “one-to-one”. We haven’t even attempted to write a specific ordering, and have labeled the decimal coefficients as a1, b1, etc. In fact, we could do the same thing with any representation of the real numbers, be it binary, hexidecimal, base-105, or whatever! Cantor’s diagram therefore exhausts all possible attempts to line them up, by definition.
  
  Reply
  - Akhil Balraj says:
    
    December 5, 2013 at 7:32 pm
    
    Ah… I see. I was thinking that you could take a number line, ignore everything but the naturals, and compress it so that the line of natural numbers would be as “dense” as the reals. From there, a geometric argument similar to the one you used earlier in the post could show a one to one correspondence. I guess Cantor’s proof implies that even if there is an infinite number of naturals they can never be lined up as densely as reals.
    Anyways, thanks for the help!
Grant says:

July 13, 2022 at 8:45 am

Greaat read thankyou

Reply
Rodney Kawecki says:

June 22, 2023 at 9:42 am

Albert Einsteins theories are about light and it’s speed. To think our system is weighed in a cup makes me wonder what that has to do with. In 1925 Erwin Hubble and I don’t think Erwin knew what he discovered at the time.
But, reality predicts the upmost. Expansion at a greater velocity than light as the universe is not standing still but is in motion another thing relativity deny. Than, we can clearly see the planets in our system from end to end and not deeper and deeper. Mobility or motion at the greater velocity allows planetary to stretch out and across their domain. Imagine trying to fly outa a hole like relativity has it. What happens to acceleration than?
The universe is neither flat but is expanding in the surface of a balloon like crest where we can only observe one-third it’s entirely at a time. It would also seem that if the universe retained a cosmological constant speed limit..
It would seem to look like a never dying bubble floating in expanding space lost in the kemlin.

Reply