Encountering Infinity Twice in a Row

My last few posts have been on life at Cornell, and this one is really not much different. I typically blog about other topics, but this school, this place is so interesting! Anyway, what I cover in this post are two of my classes, Math 2230 and Comp-Sci 1610 (both of which I took two days ago, one right after the other), and how we looked at the idea of infinity in each of them.

Induction

Math 2230 is Theoretical Linear Algebra and Calculus, which covers linear algebra and multivariable calculus. The reason it is theoretical is that the class is very based on theorems and proofs rather than real-world applications. In contrast, Math 1920 is Multivariable Calculus for Engineers. As a math major, I’m in the liberal arts college and not the engineering college, so I get to take 2230.

Anyway, the very first thing we cover is induction. That is, inductive proofs. It is an amazing form of proof because, in just two steps, you can prove that some proposition applies for an infinite number of cases—and often, for all cases.

Essentially, you imagine an infinite chain of dominoes but with a starting domino. If you can show that for any given domino, if it can be knocked over, the next one will also be knocked over, then you have shown that all of them can be knocked over (!). Well, there’s one catch. You have to also prove that some initial domino can be knocked over, usually the first one. Those are the two steps.

It is usually done the other way around. Say I wanted to prove the proposition that 2^n < n! for natural numbers n \geq 4. Let’s plug in a random number to check, say 5. In this case, we have 2^5 = 32 on the left-hand side and 5! = 120 on the right, and 32 is clearly smaller than 120, so the proposition is true. Now suppose n is 10. We then have 2^{10} = 1024 on the left-hand side and 10! = 3628800 on the right, which seems to support the proposition even more. As n goes up, n! is much more than 2^n.

But how do we prove this for all integers of at least 4? Well, we should show that the first domino can be knocked over, i.e., that the proposition is true for n = 4. A quick check gives 16 < 24, so the proposition is true. Now we just need to show that if the proposition is true for a given number k, then it must also be true for k + 1. This requires what seems at first to be a leap of faith. We must assume the proposition is true for k, no questions asked. The proof still makes logical sense, but this part is somewhat unsettling at first.

In this case, we assume that for an arbitrary number k \geq 4, we have 2^k < k!. The next step is to show that this assumption implies 2^{k+1} < (k + 1)!. It’s easier than it seems. It’s because you can rewrite this as 2^k \cdot 2 < k! (k + 1). We certainly know that if we compare the left term of both sides, we will find that the left-hand side is smaller: by assumption, 2^k must be less than k!. It turns out that if we compare the other term, we also find that the left-hand side is smaller: 2 < k + 1, because k must be at least 4. So we’re comparing the product of two smaller numbers against the product of two larger numbers—of course the product of two larger numbers is greater. This shows that 2^{k+1} < (k + 1)!. And it in turn proves that the proposition is true for all n \geq 4.

The domino analogy, in full:

Domino The example
The first domino can be knocked over. The proposition is true for the first relevant value (n = 4).
If any domino is knocked over, the next one will also be knocked over. If the proposition is true for any value k, it is also true for k + 1.
Therefore, all of the dominoes can be knocked over. Therefore, the proposition is true for all n \geq 4.

It’s the conclusion, the third step, that ties induction to infinity. If the proposition is true for 4, it must also be true for 5, which means it must be true for 6, etc. The key is that the positive integers are arranged in order, so we don’t leave out any relevant integers by continuing 4, 5, 6, etc.

Cardinality

Comp-Sci 1610 is Computing in the Arts, and is cross-listed as computer and information science, engineering, music, film, dance, and psychology. If, by any chance, you know what I refer to by “cardinality,” you’re probably wondering, how is THAT related to any of these subjects? Well, it’s not quite related. But the professor spent at least half an hour on this, including the proofs, so I’ll include it here.

Cardinality refers to the size of a set, that is, how many things are in it. The cardinality of “the set of people living in the United States” is a bit over 300 million. What about the set of natural numbers (1, 2, 3, 4, etc.)? It’s infinity. And the set of real numbers (0.25282859…, pi, 32.33…)? Also infinity. But are these two infinities the same? It turns out they aren’t, because if they were, cardinality would become infinitely less interesting.

Actually, it is due to a lack of one-to-one correspondence. If the two sets (the set of natural numbers and the set of real numbers) were the same size, then there would be some way to match each natural number with a real number and vice versa, and not have any of either number left over. Cantor proved this was impossible.

The proof is by contradiction. He first assumed that the natural numbers could be put in one-to-one correspondence, and then showed that in that situation a paradox occurs, so the assumption must be false.

He basically created a hypothetical list of correspondence between the natural numbers and real numbers between 0 and 1. This is because if there are more real numbers in just the 0-1 interval than the entire set of natural numbers, obviously the entire set of real numbers must also be larger.

1 \leftrightarrow 0.\mathbf{1}234567891011...

2 \leftrightarrow 0.9\mathbf{3}71263636363...

3 \leftrightarrow 0.32\mathbf{7}5218383734...

etc.

Cantor essentially conjures another real number that cannot be in this list. He does this by creating a number that differs by each real number in the list in at least one digit. Note the bolded digits above. We simply add 5 (or subtract 5, as to not go over 9) to each bolded digit, and create a new number out of the modified digits. So the new number’s first digit is 6 (1 + 5), second digit is 8 (3 + 5), and third digit is 2 (7 – 5). Obviously this new number cannot be the first number in the list, because it’s wrong on the first digit. Likewise, it can’t be the second number, because it differs on the second digit. This continues on infinitely. Hence, it is impossible to put the natural numbers and the real numbers in a one-to-one correspondence—there are more real numbers than there are natural numbers.

But that’s obvious, you say. Between 0 and 1, inclusive, there are only two natural numbers and an infinite number of real numbers, so there must be more real numbers.

This is true, but is not the case, however, with rational numbers, i.e., fractions. Even though between 0 and 1 there are an infinite number of fractions (1/2, 1/3, 1/4, 5/8, etc.), it can be proved that the cardinalities of the set of natural numbers and the set of rational numbers are the same, because you can list the rational numbers in order.

Essentially, a rational number is just the ratio of two integers, so you can think of it as a point on a graph, with the x-coordinate being the numerator and the y-coordinate being the denominator. Now it is possible to start at (0, 0) and spiral your way around, touching every integer coordinate.

Spiral GraphEach arrow can have a unique natural number associated with it, the first arrow being 1, the second being 2, etc. And since each natural number corresponds to an arrow, which corresponds to a coordinate, which corresponds to a rational number, we have shown that there is a one-to-one correspondence between the natural numbers and the rational numbers. So the natural numbers have the same cardinality as the rational numbers.

This also means, if you take into account the previous result, that there are more real numbers than there are rational numbers.

Still, this does not answer the question of how this is related to computer science, or psychology, or music, or film. Well, it wasn’t really that related—the professor just went on a tangent. Anyway this has been an interesting introduction to math at Cornell!*

*(I had already learned both induction and a bit on cardinalities, enough to know that the naturals and the rationals have the same size, less than that of the reals. It was fun anyways. Especially seeing the artists/liberal arts people in the second class squirm at Cantor’s diagonal proof.)

2 thoughts on “Encountering Infinity Twice in a Row”

  1. “it can be proved that the cardinalities of the set of natural numbers and the set of natural numbers are the same”

    I don’t doubt it, but that may not have been your point.

    Like

    1. Thank you for spotting that!

      I did mean the rational numbers on the second part. The statement should read: “it can be proved that the cardinalities of the set of natural numbers and the set of rational numbers are the same.” (Fixed in the post.)

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s