Recall that in lesson 11 we saw how the set of fractions (which we denoted by FRAC) is so extremely infinite. In particular, we had “infinitely many infinities” due to the fact that between any two fractions there are infinitely many fractions, and between any of those fractions there are again infinitely fractions, and so on, forever. Moreover, the initial two fractions that we chose in this process could have been any of the infinitely fractions that exist! In this sense, FRAC appears to have “infinity times infinity” elements. Of course, the notion of “infinity times infinity” is not yet well defined, because the only infinity that we’ve defined is “infinity type 1”, which is the infinity corresponding to the set
This lesson will be devoted to showing that this vague idea of “infinity times infinity” is in fact the same as infinity type 1. In other words, we’ll find a bijective function from to FRAC. It may seem surprising that this is possible after we’ve seen how the “infinite-ness” of FRAC is so seemingly different from the “infinite-ness” of which does not share the property that between any two of its elements there are infinitely more elements. Accordingly, we’ll have to get a lot more creative in defining this bijective function than we did when we defined a bijection function from to in lesson 10.
The reason why we have to get more creative is relatively easy to see. In the function from to , we were able to exploit the fact that B has a sort of order to it (as does A). Namely, the negative numbers in B have a kind of order, as do the positive numbers of B. Similarly, the odd numbers of A have an order to them, as do the even numbers. We then sent the odd numbers of A to the positive numbers in B, and the even numbers in A to the negative numbers in B, in the obvious way.
The problem with FRAC is that there is no meaningful order to them. Given two distinct fractions we are of course able to say which is bigger, but suppose that you give me a fraction and ask me what the “next biggest” fraction is. I would quickly respond by saying that your question is impossible to answer because, as we’ve seen, any fraction I were to say would in fact have infinitely many elements between it and the fraction you gave me, and thus surely couldn’t be the “next largest fraction”!
Therefore we can see that there will be no nice and obvious function between these two sets, and that is why we need to get creative (which isn’t the end of the world). Let us now construct this function. We will in fact only construct a function from the even elements of A to the positive elements of FRAC (recall that fractions can be positive or negative), and once we’ve done this it will be obvious that we can finish the job by sending the odd elements of A to the negative elements of FRAC in the exact same way.
We begin by recalling the following two facts. Firstly, we recall that every fraction is nothing but “some whole number upstairs, and some (non-zero) whole number downstairs”. Implicit in this statement is the fact that any whole number is itself a fraction merely by putting “1” downstairs. Secondly, we recall that and and and (etc.) are all the same element in FRAC.
Using the first fact as motivation, we construct an infinite chart where positive whole numbers go across the top and down the left (see figure 1). We then call the positive whole numbers across the top “numerators” and those going down the left “denominators”. Note that this chart goes infinitely far in both directions, so that it includes all of the positive whole numbers on each axis. The reason we call the numbers on the top “numerators” and those on the left “denominators” is clear: the number that goes in the corresponding square on the chart is that fraction which has its column’s “numerator” as the numerator, and its row’s “denominator” as its denominator. Note that in the figure I abbreviated “denominator” by “denom”. Clearly figure 1 only shows a small portion of the entire infinite chart, primarily because it would take me too long to write out the whole thing!
The important thing to note about this chart is that it includes every positive fraction, seeing as it contains every possible combination of “numerator” and “denominator”, so long as we limit ourselves to the positive ones. Sure, there are some duplicates in the chart, since and , and so on. Once you buy that every positive fraction is on this chart somewhere, then our hard work is pretty much done. In fact, this chart contains more than every positive fraction, since it contains every fraction as well as all of its duplicates! Note, for example, that 1 shows up on every diagonal entry because and so on.
Now all we do is take the even elements of and assign them in an intelligent way to this chart. Namely, we want to “walk along” this chart and make sure that we get every single square (so that the map is surjective), but only in such a way that we don’t count the duplicates (so that the map is injective). This is actually extremely easy—we’ll just zig-zag our way through the chart so that we get every square, and we’ll skip over the squares that are duplicates.
Thus, we simply define the function from the even elements of A to this chart in the following way. Assign 2 in A to the top-left-most element in the chart (which is ). Now take a step to the right. We’re now sitting on the square containing . Assign the next even number, which is 4, to this square. Now head diagonally down to the left, and land on the square containing . Assign the next even number, which is 6, to this square. Now take a step down, so that we’re standing on the square with in it. Assign the next even number, which is 8, to this square. Now head diagonally up and to the right, so that we’re standing on the square with in it. But wait! We’ve already assigned an even number to 1 (it was in fact our first assignment!). So we skip this, and head up and to the right again, and now we’re standing on 3. Since we haven’t assigned anything to 3 yet, we assign the next even number, which is 10, to 3. Now take a step right, assign, then down and to the left, skipping all duplicates until we hit the left edge of the chart. Take a step down, assign, and then up and to the right until we hit the top edge again, as always skipping all duplicates. And that’s it! We just do this forever, since we have infinitely many even numbers to play with. Moreover, since we’re skipping duplicates, this function is perfectly injective. To illustrate how I’ve zig-zagged through the chart, I’ve ruined my chart by creating figure 2. (Note also that zig-zagging through the chart was necessary because if we tried to, for example, assign the even numbers in A to an entire row, we’d never be able to get to the rest of the chart because each row and each column is infinite in length. Zig-zagging avoids this problem.)
Now to finish the map from A to FRAC, we simply make another chart with all of the negative fractions and assign the odd elements of A to these fractions in the exact same way that we have for the positive fractions and even elements of A.
And with that, we’re done! We have successfully tamed the wild infinities that exist in FRAC and shown that FRAC is really “the same infinity” as despite our initial thoughts to the contrary.
Note that this function we’ve constructed is in no way “nice”, meaning that it does not have a nice pattern to it. If we call this function from A to FRAC “F”, then we see that and similarly (mapping to the negative fractions). The farther into the chart we go, the more this function “jumps around”. But it doesn’t matter! The function is most definitely surjective and injective, and so it’s bijective, and thus with our definitions we are forced to say that FRAC is “just as infinite” as
We must indeed go on to the next lesson, where we finally see a brand new infinity!