Alas, we have finally gotten to the lesson where we’ll find a whole new kind of infinity! We’ve spent the last several lessons showing how infinite sets that seem different from 
Before we define this gigantic set, however, we need to first consider the elements that we’ll use to construct it. The elements in this set will be numbers that go by the technical name “real numbers”. Note that a real number is a technical object, and not the opposite of a “fake number”. What exactly is a real number? Well, there are actually many ways that we can motivate the definition of a real number, and all of which are currently beyond the tools that we have available to us. Thus, we’ll simply define a real number to be a number expressible as an infinite decimal. Let us therefore first remind ourselves of how decimals work.
A number like 1.5 or 12.6 should hopefully be relatively familiar to the reader. The digits to the left of the decimal point make up the “whole number part” of the real number, and the digits to the right of the decimal point make up the “fractional part” of the number. Thus, 1.5 is really just “1 and a half”, and 12.6 is just “12 and six tenths”, or equivalently “12 and 3 fifths”. A real number, however, is one in which the numbers to the right of the decimal go on forever. They are expressions like
where the “…” means, as usual, that this goes on forever. There doesn’t have to be any rhyme or reason to the numbers that are on the right of the decimal place.
Let us now make a few remarks about these numbers. The first remark is that any whole number can be written in this way, simply by letting the infinitely many numbers to the right of the decimal be zeros. Thus 1=1.0000000…, and -45=-45.000000000…. In a similar way, every fraction can be written as an infinite decimal. The general proof of this last statement is a little beyond us right now (and would not be particularly fun), but the intuitive reason for this is that every fraction either has a decimal expansion that “stops” eventually (i.e., has nothing but zeros forever after some point), or has a repeating pattern eventually (like 
The last thing that I’ll remark on, just so that you get the sense that these numbers are in fact “real”, is that these numbers actually have an extremely important role in mathematics. Namely, there are several extremely important numbers, such as “Pi” (which is the famous 
Let us now consider the set of all real numbers, which is commonly denoted in the business as 
But how does one show that something cannot happen? Showing that something can happen is easy—you just do it. Showing that something can’t happen is more tricky, but luckily we have an extremely powerful tool for proofs of this type. Namely, we use the method of proof by contradiction. We will assume that we can define such a bijective function and then arrive at a logical contradiction, thus showing that this assumption is impossible to make (and thus showing that no such function can exist). The following argument is insanely beautiful and profoundly clever. It is the brainchild of one of the greatest mathematicians to ever walk this planet, who went by the name Georg Cantor.
Cantor’s Proof of the existence of a new infinity
Suppose that there is a bijective function from 
We’re now going to introduce a notation for real numbers that, although somewhat confusing at first, will make the proof extremely easy (don’t be scared of the notation—let me explain it first). We know that 
What we’ll do is find a real number that cannot possibly be “hit” by this function, which is impossible because the function was defined to hit every single real number! This is the contradiction we’re after.
Given such a hypothetical function F, we can construct the following infinitely long list:
…
and so on, forever. Remember, the expressions on the right hand side here are just bookmarks for whatever real number our function F takes us to. We now use this information to find a real number that can’t possibly be in our list, and we do this using the “diagonal argument”. Note that we can write any real number as 
Let’s now ask where in our list P is. It must be somewhere, because P is a real number and our list contains all real numbers, by assumption. But P can’t be the first number because it differs from 
Thus our function, which supposedly hits every real number, missed at least one real number! A contradiction!!!
QED!
Thus such a function can’t exist, and thus the set of real numbers cannot be put into a bijective correspondence with the positive whole numbers. We’ve found our new infinity!
Even though we’ve extended our number system by including “infinity type 1”, we still have sets that we can’t count. Accordingly, we call a set that is infinite and that can’t be put into bijection with
The True Beauty of Math 
I have found it better to use P(N) instead of R as a first example if an uncountable set. For one thing, it doesn’t require the very awkward “definition” of real numbers, and for anothe the proof is somewhat more intuitive (in particular it is similar to the “sets which contain themselves” paradox).
That’s valid, perhaps it is a bit more logical (and/or easy to understand) to reverse the order that I present them. The only plus side of this proof is that it follows naturally(ish) after considering the set of fractions, simply because we’ve moved from, say, even numbers, to fractions, to real numbers, thus always staying in the realm of “numbers”. Even though the logic of the proof itself is nicer in the P(N) case, it might be that the construction of that set itself seems a bit less “real”, and therefore that the existence of other infinities is less “real” (I don’t know, this is hypothetical, just my guess). Showing that this happens even with sets of numbers makes it seem more necessary and unavoidable to have different infinities. Again, I don’t know, just guessing. Either way, though, I want to present both (to be able to mention the Continuum hypothesis), so I think I’ll just leave the ordering this way, unless I find out that people are really struggling with this one. As always, thanks for your input, it’s insight like yours that will help make this site better!
Here’s my intuition for why the set of fractions is a subset of the real numbers (or alternatively: why every fraction can be expressed as a repeating or terminating decimal):
Imagine that you’re trying to convert the fraction p/q into a decimal. Recall that by the definition of a fraction, p and q are nice little whole numbers (but q can’t be zero, though). Anyway, you’re beginning the tedious work of long division. Now if it is zero, we raise our hands and say we’re done. Also, if you’ve seen that (non-zero) remainder before, you know that since the results dividing the same thing by the same number will always be the same, you’re going to end up doing the same steps you did when you first saw that remainder (and which led to the remainder again). So you’ll be in a loop, and you can just declare the rest of the digits of the answer to be a repetition. Finally, you realize that the remainder has to be less than the divisor (mod arithmetic: cuz’ otherwise we could just take another bite of the divisor out of it), you’re going to have to end up at one of the 2 consequences above in a finite number of steps (not more than the divisor).
I’m probably using about twice or thrice more words than strictly necessary to convey that, but I hope you get the meaning. What I want to know is: does the above count as a rigorous explanation? If not, what’s the assumption that remains to be proven? Thanks!
That’s great intuition, and indeed the correct logic for proving that any fraction is either a finite or a repeating decimal. Your argument is perfectly rigorous, and is an “algorithmic proof”, in which a sequence of steps is laid out to arrive at the desired result. The only issues we need to worry about with such proofs is showing that any such sequence will only have a finite number of steps, so that we can be sure that the sequence of steps can indeed be completed (as an algorithm with infinitely many steps, all of which being necessary to arrive at the result, is not really an algorithm). You’ve done this in your description, which is good. And in regards to the “wordiness” of your explanation, I actually think it’s great. The only improvements that would need to be made would be to translate what your wrote into symbols, assigning lots of arbitrary variable names to the various quantities that arise throughout your discussion, but this is only possible once the idea of the argument is clear, and your description does indeed make it clear. Moreover, translating your description into symbols is simple (although tedious) once the method is understood. Thanks for the contribution!
I found this wording of the diagonal proof of infinity beyond infinity of real numbers to be most helpful: “Since the real number we defined using the diagonal method was different in one digit to every previously defined real number and since all previously defined real numbers were by definition different from each other, we can conclude that the real number we found is indeed unique and cannot be mapped to by natural numbers and is thus uncountable.”
This is the way I worded it to myself in my head after I looked over some additional materials on Wikipedia since I had difficulty understanding the concept.
Summarizing the concept like that might be helpful to others who read this lesson as well.
Good point, thanks! For now I’ll just let your comment do that work for me, as I’m struggling to get the next lesson up as it is (for purely technical reasons, unfortunately), but once I get some additional time I’ll consider changing this. Thanks for the input!
I do not think that Cantors diagonal slash is capable of examining every instance in the type of set proposed above and therefore cannot be used as proof of the non existence of a number within that set. This is because it is using a direct relationship between i and j, however the set requires i to be increasing at a greater rate than j.
Using this method on a finite set of binary numbers gives: –
F(1) = {00}
F(2) = {01}
F(3) = {10}
F(4) = {11}
The resulting P = {10} is clearly in the list, just not in the part of the list reached by the diagonal.
Scaling this up so when j=∞, i=2∞ , but i still has a direct relationship with A = {1,2,3…} as does j
Ah, I see the confusion. In Cantor’s diagonal slash argument, we’re not skipping over any of the numbers in our list. This is very important. So in your above example, we’re not “forgetting about” any of F(1), F(2), F(3), or F(4). What we’re doing is expressing each element in the list in decimal form, with infinitely many decimal spaces. In your example this is somewhat silly, since each image point is an integer 1, 2, 3, or 4 (just expressed in binary, but that doesn’t change anything), and this would be F(1)=00.000000…, F(2)=01.000000000…, f(3)=10.00000000…, f(4)=11.00000000…. Then Cantor’s diagonal slash argument instructs us to create a number that isn’t ANYWHERE in our list by going through EACH number in the list and changing the i^th decimal point (starting right after the decimal) in the number F(i). Thus my new number would differ from F(1) in the first digit after the decimal point, like 00.1… where the “…” means I still need to construct the next digit. I now change the second decimal point to differ from F(2), like 00.11…, and same for F(3), like 00.111…, and again for F(4), as 00.1111. In your example I would be done, since the list is finite, and indeed 00.1111=1/2+1/4+1/8+1/16 is not “hit” by our list! The point is, though, that I haven’t “skipped” any elements in my list, I haven’t “missed” anything, I’ve genuinely constructed a number that isn’t anywhere in my initial list. And moreover, this argument still works for the entire set of real numbers, as we discuss in the lesson.
You may also be worried that I’ve “extended” the initial set that you were talking about, by allowing for decimal places. In particular, it was only by allowing for decimal places that I constructed a number that our list didn’t hit. But that doesn’t matter. We used this argument for real numbers, and real numbers DO have infinitely many decimal places so that this argument DOES define a number that isn’t hit by the list, but is in the set of real numbers. The same argument certainly doesn’t work if I want to find an element in the set {1, 2, 3, 4} (your example set) that ISN’T hit by our list, but that’s because our list DOES hit every element! But just because our argument doesn’t work for this set (and nor should it!), doesn’t mean that it doesn’t work for the case that we’re interested in. Namely, our method shows that a particular kind of function is NOT surjective. Of course, if we use the same method of proof on a function (between different sets) that IS surjective, then it won’t work! 🙂
I hope that makes sense, and let me know if you have any other questions!
I wasn’t suggesting that anything in the list was “skipped” more that the latter part of the list could not be reached in order to check for the existence of the newly created number P.
I used the binary illustration because it was easier to notate the differing rate that i increases with respect to j. This could have been done using a finite string of decimal numbers, which when scaled up to an infinite string would be equivalent to your real number example where i=10^j. Both produce sets where i is increasing at a greater rate than j (a rectangular set), whereas the diagonal slash requires i and j to be increasing at the same rate (or a square set) in order to ensure it hits every instance. using the diagonal the alternative real number P can only be looked for within the list up to i=j. If j=100 i cannot be observed between f(101) and f(10^100) (which must exist in order to meet the criteria of having every possible combination). by then moving 1 decimal place so j=101 it does prove P is not within f(1-101), but it also expands the unreachable section of the list to f(102-10^101) and so on. therefore using the slash does not infer that P is not within this list only that the diagonal is insufficient to examine the whole list.
The conclusion drawn that there are different “sized” infinite is partially correct, in that within an infinite set of real numbers there are two sets tending toward infinity at different rates within the same system, the infinite set of real numbers and the infinite number of decimal places. but independently they both have a bijective relationship with A={1,2,3…} meaning they are both countable and the same size.
The diagonal argument has nothing to do with “how fast” we get to infinity, or “which part” of the list we’re looking at. The whole argument can be put much more simply. Suppose you hand me a bijection from the natural numbers to the real number. I can then immediately define a real number that differs from every number in the image of the list you just handed me. In particular, I can guarantee (abstractly, and all at once (having nothing to do with “getting all the way down the list”)) that my new number differs from the N^th number in the list you just handed me in the N^th decimal point.
That’s a completely general statement, and it has nothing to do with what part of the list we’re dealing with, or how fast we’re increasing i or j or anything of the sort. For if you claim that the real number that I just defined via the diagonal argument is ANYWHERE in your list, then it must have SOME finite location in the list. Suppose the placement of this number in the list is M. Then I immediately know that my real number differs from this number in the M^th decimal point. This is completely general, it has nothing to do with “only looking at the first M entries of the list”, it ONLY has to do with the fact that if you tell me SOME number in your list equals my real number, then there’s an immediate contradiction.
The uncountability of the real numbers is an extremely well established fact, and there are in fact many many other (even more infinite, i.e., even LESS countable) infinite sets that have absolutely no hope of being put into bijection with the natural numbers. I hope this helps to see that, and let me know if not!
“I can guarantee (abstractly, and all at once (having nothing to do with “getting all the way down the list”)) that my new number differs from the N^th number in the list you just handed me in the N^th decimal point.”
I completely agree and I can guarantee that your new number IS on the list somewhere between N+1 and 10^N and that this is not a contradiction to the above statement
I would be interested in learning more about these other uncountable infinite sets, can you point me in the right direction to find some examples?
No, you can’t guarantee that. Choose ANY N you want. If you say my number is in the list between N+1 and 10^N, then it’ll be at the position M where M is between N+1 and 10^N (you can even make the upper bound 10000^N^N^N^N^N, it doesn’t matter). Then I can guarantee that my number differs from that M^th number in the M^th decimal place. There my number is in the range you specified.
You can’t look at this as in “ranges”. Let me repeat:
The statement is that if my number is in the list at ANY position N, then it will differ by it in the N^th decimal place. That already allows for the possibility that N is any of the infinitely many locations. We don’t now what N is, we just know that it can be ANYWHERE in the list, and regardless of what it is, it’s not labeling my number. That’s it. That’s the proof. There’s nothing else to consider.
For other uncountably infinite sets check out future lessons here, they’re basically just power sets of the natural numbers. And power sets of those power sets, and so on. We then get an infinitely tall ladder of new, increasing infinities.
As we did with the FRAC set, why couldn’t we construct a matrix with its rows being every possible whole number and with its columns being every possible infinite combination of decimals? Then, P would be inside of it. Thank you!
Hi Luis,
That’s a great question! There’s a “nice” answer I can give and a “not so nice” answer I can give. The not so nice answer is the following: try it!
The nicer answer is the following. Try building a matrix that has every possible combination of decimals. It turns out it’s pretty tough to do so. In fact, it’s impossible to do so. The problem that you’ll immediately run into is the following: how do you organize it? The reason we could do this with the fractions is that we could organize the matrix by having one direction correspond to the numerators and one direction correspond to the denominators. However, with the real numbers this immediately becomes impossible. For example, where would the number 4.567929235239538535 be in relation to 4.5679292352395385351? And would about all the infinitely many real numbers between these two numbers? How can we even “get a handle” on this numbers. Infinitely many of the real numbers require an infinitely long decimal representation, whereas each fraction is specified solely by a numerator and a denominator. Thus, an “organizing principle” for putting the real numbers in a matrix just doesn’t really exist the same way it does for a fraction.
Additionally, we also simply KNOW that we can’t do it. Namely, if we COULD do it, then we could run the same argument as we did for FRAC and show that the real numbers have the “same infinity” as FRAC. However, we have already proven that the real numbers have a different infinity than FRAC. Thus, it MUST be impossible to put the real numbers in a matrix. This may seem like circular logic, but it’s important to understand why it is not. Namely, we found a particular way of showing that the real numbers have a different infinity than FRAC, and that’s enough to prove that it’s impossible to put the real numbers in a matrix in such a way that we do not miss any real numbers. By spending some time TRYING to put the real numbers in a matrix, one will simply be confirming what we already know. However, it is a good exercise to make this attempt, because it will then make us appreciate from various perspectives “why” we cannot do this real numbers.
Does that make sense? If not let me know and I’ll try again! 🙂 thanks for your great question!
Hello,
From the lesson, can I conclude as below?
We can construct a fonction from N to R but never from R to N. Coz it’s not bijective so there is not inverse fonction. Ex: f : N –>R defined by x–>square (x). The inverse function is g:R–>N defined x–>x^2. For x=pi, we don’t find the corresponding value in N.
So to prove the no bijective between N and R, just find a function from N to R and prove the inverse function is not possible. Does it make sense ?
Thank you for replying.
Hi! Good question. Unfortunately, it’s not about just showing that some particular function doesn’t have an inverse function, but rather that there is no possible bijective function at all. A different way of saying it is as follows. There are functions from N to R and there are functions from R to N. The point, though, is that there is no INJECTIVE function from R to N. Namely, if we try to send every element in R to some element in N, we unavoidably must eventually repeat where we send elements in R. The squaring function that you talked about is just one particular function, but we must show that ANY function from R to N is not bijective. Since we know we can a function from R to N surjective—just take the copy of N that lies in R and send them to their corresponding elements in N, then send the remaining elements in R to anything—then showing that there is no bijective function from R to N is the same as showing that there is no injective function from R to N.
In the lesson, we showed that there is no SURJECTIVE function from N to R, which is equivalent. Anyway, the key point is that this isn’t a statement about particular functions, it’s much more general than that. Does that help?