Lesson 11: Infinity times Infinity

In the previous lesson we used our new weapons for counting and applied them to “counting” infinite sets.  Namely, we saw that we can “double” the number of elements in a set with infinity type 1 elements, and get a new set which also has infinity type 1 elements.  We also saw that we could add any finite number of elements to a set with infinity type 1 elements, and still have a set with infinity type 1 elements.  Recall that whether or not a set “still has infinity type 1 elements” is determined solely by whether or not we can define a bijective function from \{1, 2, 3, ...\} to the set.

But last lesson was just a warm-up lesson for the next couple of lessons.  The statements of the next two lessons, and their proofs, will take some more creativity and perhaps a bit more thought.  That said, I can promise two things.  One is that it won’t be that bad.   And the second is that the results will make the process entirely worth it (as is usually the case with math).

So what is it that we want to prove in this lesson and the next one?  We’re going to show that the set of all fractions also only has “infinity type 1” elements in it.  This is a truly remarkable result, and in order to fully appreciate it we need to first remind ourselves about fractions and the nature of their infinity.  This is the subject of this lesson, saving the actual proof for the next one.

Recall that fractions are nothing but things like \frac{1}{2} (“one-half”, or “1 divided by two”), or \frac{3}{4} or \frac{2}{5}.  Namely, “\frac{1}{2} ” is a symbol which represents the abstract idea of the number that, when multiplied by 2, gives 1.  In the same way, “\frac{3}{4}” is a symbol which represents the abstract idea of the number that, when multiplied by 4, gives 3.  Accordingly, we can think of fractions as nothing but a pair of whole numbers: the number that is “on top” and the number that is “on the bottom”.  Thus, in the fraction \frac{3}{4}, 3 is the number “on top” and 4 is the number “on the bottom”.  Given a fraction, if we multiply it by the number that is “on the bottom”, then we get the number that is “on top”.  I.e., 4 \times \frac{3}{4}=3, 2 \times \frac{1}{2}=1, and 111 \times \frac{112}{111} = 112.  This might all be familiar, but if it’s not I hope this suffices as a reminder.  Lastly, recall that we usually call the number “on top” the numerator, and the number “on the bottom” the denominator.  Fractions are not scary at all when you recall that a quarter of a basketball game is just \frac{1}{4} of a whole game, or that a nickel is just \frac{1}{20} of a whole dollar, or that a cup can be \frac{3}{8} full.

The last thing we need to recall is that there is a notion of equality between two fractions that might at first sight look different.  Namely, we have that \frac{1}{2} and \frac{2}{4} are the same.  Also, \frac{1}{3} and \frac{3}{9} are the same fraction, as is \frac{2}{5} and \frac{4}{10}.  The general idea is that if we have one fraction and we obtain another fraction by multiplying “the top” and “the bottom” by the same number, then the resulting fraction is actually the same as the one we started with.   Thus, when I define the set FRAC=\{\mathrm{all\ fractions}\}, I’m implying that \frac{1}{2} and \frac{2}{4} are the same element in FRAC.

Now that the crash course on fractions is over, let’s see what makes the fractions seemingly “more infinite” than \{1, 2, 3, ...\}.  There is a very important fact about fractions that has no analogue in the set \{1, 2, 3, ...\}.  Namely, between any two distinct fractions, there are infinitely many more fractions!   Seeing why this is not the case in \{1, 2, 3, ...\} is easy.  Suppose you gave me two distinct elements in \{1, 2, 3, ...\}.  Call them M and N.  One of these two numbers will be bigger than the other (since they’re different), so let’s suppose N is bigger than M.  Then clearly there are only finitely many elements between M and N, because all we need to do is count off M, M+1, M+2, until we hit N.  Since both M and N are finite numbers, we’ll only have to count off finitely many elements.

Let’s take a classic example now to see why there are infinitely many elements between any two distinct fractions.  Let’s ask the question: how many fractions are there between \frac{1}{2} and 1 (Recall that whole numbers are fractions whose “bottom” number is just 1, i.e., 1=\frac{1}{1})?  Well, what we’re going to do is essentially just take the fraction “halfway” between \frac{1}{2} and 1, and then the fraction halfway between that fraction and 1, and then the fraction halfway between that fraction and 1, and so on.  We can do this infinitely many times without ever reaching 1, thus finding infinitely many fractions between \frac{1}{2} and 1.  Thus, \frac{3}{4} is between \frac{1}{2} and 1, \frac{7}{8} is between \frac{3}{4} and 1, \frac{15}{16} is between \frac{7}{8} and 1, \frac{31}{32} is between \frac{15}{16} and 1.  We can keep doing this forever, thus uncovering infinitely many elements between \frac{1}{2} and 1 in FRAC.

The point is that we can make this argument between any two fractions.  All we do is step halfway from one to the other, then halfway again, then halfway again, and so on.  Since each of these “halfway points” will be new fractions in their own right, we’ll uncover infinitely many fractions between any two distinct fractions.

Now here’s the rub.  Suppose the enemy hands me two distinct fractions.  From the above considerations, we know that we can find infinitely many fractions between these two fractions.  But in fact, we can do better!  For between any two of these fractions that we’ve now found, there is yet another infinity of fractions!  In other words, every time we take a step halfway from one fraction to another, we can find another infinity of fractions between the two we just “stepped between”!  Moreover, if we then dive into that infinity of fractions, we’ll keep uncovering new infinite sets of fractions.

Let us go back to our example to see just how infinite the set of fractions are.  We know that there are infinitely many fractions between \frac{1}{2} and 1.  One of the fractions between them is \frac{3}{4}.  But now we automatically know that there are infinitely many elements between \frac{1}{2} and \frac{3}{4}, because we can just do the same “half-way” argument.  One fraction between \frac{1}{2} and \frac{3}{4} is \frac{2}{3}.  Again, we now know that there are infinitely many elements between \frac{2}{3} and \frac{3}{4}!  One such fraction is \frac{7}{10}.  Then BOOM!  There’s another infinity of fractions between \frac{2}{3} and \frac{7}{10}!  In this way, infinities just keep “popping out” everywhere we turn.  Namely, we just keep picking different fractions, no matter how close they are, and there will be infinitely many fractions between them.  ALWAYS!

This sort of infinity certainly has a different quality about it than the infinity type 1 of \{1, 2, 3, ...\}.  Namely, \{1, 2, 3, ...\} just kind of “goes in one direction”, whereas we can “zoom in” on the fractions infinitely far, in infinitely many places, infinitely many times!  This is what I mean by “infinity times infinity”.  Between any two of the infinitely many elements in FRAC, there are infinitely many elements, and between any two of those elements, there are infinitely many elements, and between any two of those elements, there are infinitely many elements, and on and on and on!

Believe it or not, we actually still can define a bijective function from \{1, 2, 3, ...\} to FRAC.  To see that we can define an injective function is easy, since every whole number is itself a fraction.  Thus we could define an injective function just by sending 1 to 1, and 2 to 2, and 3 to 3, and so on.  But this function certainly isn’t surjective.  In fact, it might seem pretty unlikely that we can “hit” all of the fractions just with \{1, 2, 3, ...\}, but we actually can!  It will take some work, and this will be the subject of the next lesson.  Don’t lose faith though, pretty soon we will see a whole new kind of infinity!

Next Lesson

Previous Lesson

Back to the quick note

10 Responses to Lesson 11: Infinity times Infinity

  1. Anonymous says:

    Typo here – a 3/4 that should be 7/8.

    • Wow, that’s a great catch, because what was written was technically wrong, but it surely wasn’t what I was trying to write. It’s fixed now…Thanks for that!

      • Michael Wales says:

        Well, it wasn’t technically wrong, it just didn’t fit the argument.

        • Exactly, which is probably why no one else (including myself) caught it yet, so thanks again!

          • Anonymous says:

            No problem. I really do like this blog. Lesson 17 is missing a link to lesson 18. When you fix the that, I’ll binge on the rest.

          • Fixed. Again, thanks a lot for the edit(s), there’s too much up here now for me to catch everything so I really appreciate it. I’m glad you’re liking the site, and apologies for not having updated in a while. I’m swamped right now but fully intend on adding a whole lot more over the approaching holidays. Hope you keep reading!

  2. Karthik says:

    The halfway fractions between 1 and 1/2 that are shown here are of the form (n – 1)/n. Will all of them be like that? If so, why?

    • Hi Karthik, First of all that’s a fantastic observation and a fantastic question: that’s what being a mathematician is all about! I’m seriously impressed.

      The answer is yes. As we step halfway from 1/2 to 1, and then halfway from that fraction to 1, and then halfway from that fraction to 1, and so on, every fraction that we come across will be of the form (n-1)/n. Namely, 1/2 is of this form with n=2, 3/4 is of this form with n=4, 7/8 is of this form with n=8, and so on. Indeed, we might additionally notice that all of the n’s are of the form 2^k for some k, pretty nice! Now, like any mathematician, we need to figure out WHY this is true (as you correctly asked). So let’s figure that out.

      We first note that in order to find the next halfway fraction, we do the following. We take which fraction we’re on, say it’s F, and we divide 1-F by 2. (Thus, if F=1/2 (i.e., at the first step, then we want to consider 1-1/2 divided by 2, to give us 1/4). This is because 1-F divided by 2 is the distance halfway from F to 1. We then want to add this distance to F. Thus, in short, the halfway fraction that comes after F is (1-F)/2+F. Now, let’s see what this leads to when F is of the form n-1/n. By simply plugging in (n-1)/n for F in the expression (1-F)/2+F, we find (after a little algebra) that (1-F)/2+F, which is the next halfway fraction, equals (2n-1)/2n. Namely, the next halfway fraction is of the form (m-1)/m with m=2n. Thus, since 1/2 is of this form, we know that the next one will be of this form as well, and therefore so will the next one, and therefore so will the next one. Indeed, this is the idea behind an inductive proof.

      Note also that we have also found why the n’s are all of the form 2^k for some k. In particular, we have found that the next halfway fraction is of the form (m-1)/m where m is twice the “m” of the previous fraction, and since our initial fraction involved n=2, we see that all of the halfway fractions will involve an n that is some power of 2.

      Does that all make sense? Again, that’s a fantastic question. And now, being mathematicians and having solved one problem, let us try to find another problem and solve it too. Namely, here’s another good question (and if you find other good questions then let me know). Here we found that if we keep moving halfway from 1/2 to 1, then every fraction we land on will be of the form (2^k-1)/2^k. What if, instead of keeping the fraction of the distance between successive fractions constant (namely, one half), what if we ask the following. What fraction of the distance to 1 must we add to the next fraction in order to setup the pattern 1/2, 2/3, 3/4, 4/5, 5/6, 6/7, 7/8, 8/9, and so on? Namely, 2/3 is 1/3 of the way from 1/2 to 1. What can we say about the rest?

      Thanks again for your question! 🙂

      • Karthik says:

        Thanks for the quick and detailed reply.

        1). I am not a mathematician. I always struggled with math in school and college. Still do!

        2). The (1-F)/2+F paragraph explains the sequence. I had used (F+1)/2 which is the simplified
        version of your expression but your explanation is way better. Also, just saying that the
        fractions are (n-1)/n was incomplete. You completed it by pointing out that it is actually
        (2^k-1)/2^k. I missed the 2^k part.

        3). The proof by induction method explains that every fraction will be (n-1)/n but does
        it explain *why* they are so? I guess this is like asking why prime numbers have that
        property (of primality) but I am not sure if I understand is the “why”.

        4). Coming to 1/2, 2/3, 3/4, 4/5, 5/6, 6/7, 7/8, 8/9. You provided the clue that the distance is
        not going to be constant. I calculated the fractions but am unable to derive a generic
        formula from it. The fractions to be added (to get the next number) are : 1/3, 1/4, 1/5,…
        I took your expression and replaced the 2 with x. So, we have ((1-F)/x)+F.

        ((1 – 1/2) / 3) + 1/2) = 2/3
        ((1 – 2/3) / 4) + 2/3) = 3/4
        ((1 – 3/4) / 5) + 3/4) = 4/5
        . . .
        By substituting (n-1)/n in ((1-F)/x)+F, I reached ((x(n-1)+1)/2n but am unsure how to
        go further.

        • Sorry for my late response! The last several weeks have been absolutely nuts for me in several regards, but now that’s done so let’s get back to it.

          In response to 1), that’s awesome that you’re staying on the horse and continuing to give math a go, and I hope my site helps 🙂

          As for 2), glad I could help 🙂

          As for 3), you’re right, it’s tough to say precisely “why” something is true in math. Namely, answers to “why” usually involve connections to more “familiar” parts of math, but that’s subjective. Namely, a geometric fact might be true “because” if we endow it with some algebraic names and do some manipulations, then something happens. Conversely, an algebraic fact might be true “because” if we view things geometrically they may become obvious. Thus, the answer to “why” something is true is difficult, and mathematical arguments are meant to show THAT something is true (and give some insight into the elusive “why”). This is actually a very deep, almost spiritual point that you bring up. Is there some ultimate “why” it is true that the length of the circumference of a circle divided by the length of its radius is an irrational number (namely, a multiply of Pi)? I can give various arguments to show you THAT this is the case, and some may take this as a way of seeing “why” this is the case, but it’s not all that unreasonable to suppose that there could have been a system of logic or a universe or whatever in which the radius of a circle is a quarter of the length of its circumference. But then, this actually can’t be the case, because every time you draw a circle it’s automatically true that its circumference and radius are related in the way that they are, so we actually can’t imagine things to be different.

          Anyway, I therefore can’t tell you much about “why” the pattern of numbers one gets by starting at 1/2 and stepping halfway to 1 is what it is, other than giving you different reasons for the fact THAT it is the way it is. This is, in my opinion, an extremely beautiful aspect of math.

          Finally, for 4), the first hint I’ll give you is that to get from 1/2 to 2/3, we actually have to add 1/6 (not 1/3). Namely, 1/2=3/6, so 1/2+1/6=4/6=2/3. The second hint I’ll give you is that 1/6 is precisely 1/3 the distance from 1/2 to 1. Namely, to get from 1/2 to 2/3, we had to step 1/3 the distance from 1/2 to 1. So now how much of the distance from 2/3 to 1 do we have to step in order to get to 3/4? Can you guess the pattern? If so, can you prove it? If not, what is the amount of the distance from 3/4 to 1 that we have to step to get to 4/5? Let me know if you want me to spoil the surprise and simply answer the question, but until then I’ll preserve the possibility of your own “aha!” moment 🙂

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