31 Responses to “Counting Infinity”

1. infinity on January 6th, 2009 2:24 am

   Nice article, really liked it. Thanks for sharing

2. Oscar Pereira on January 6th, 2009 5:30 am

   Yes, great article indeed! Math rocks!

3. Lamnk on January 6th, 2009 5:52 am

   Very good explanation, I wish my statistic lectures were this good.

4. Alex Railean on January 6th, 2009 8:47 am

   Great article, I wish I were your math-student; I missed some things in school, the void remained there and took its toll on my high-school performance, and that propagated to the university as well.

   I keep filling that void, but I know that there is so much stuff out there that is “too high-tech for me”. If you intend to continue this series, there will be a guaranteed audience of >=1 readers (-:

5. Carlos ‘Bill’ Nilton on January 6th, 2009 9:02 am

   THANK YOU!

   Your blog is awesome.

   Best regards,
   Carlos.

6. beantacos on January 6th, 2009 1:25 pm

   Extremely interesting! Had to read it about 6 times to follow, but that’s because I’ve been reading too many comics lately and not enough good stuff. Found your blog after linked in Lifehacker (I believe?) and have been loving it since. Keep up the great work!

7. Chipping the web: January 6th – Chip’s Quips on January 6th, 2009 4:00 pm

   […] Counting InfinityWhen you have a spare minuteTags: numbers infinity mathematics gustavoduarte […]

8. Gustavo Duarte on January 7th, 2009 12:45 am

   Damn, maybe I should stop doing computer work and go be a teacher heheh.

   Thanks for the comments.

   @Alex: sounds good. I’ll keep throwing in math stuff into the mix. I want to add more CompSci stuff anyway.

   cheers

9. Karan on January 7th, 2009 9:16 am

   Awesome explanation, very entertaining. I look forward to more articles like this (new rss subscriber)!

10. Matt Schinckel on January 18th, 2009 11:25 pm

    @Gustavo: I’ve just done the reverse (Teacher -> Computer Scientist).

11. Gustavo Duarte on January 19th, 2009 1:49 am

    @Matt: welcome to the ranks I really enjoy Math and CS, doing it, learning it, teaching it, anything. In fact, not just Math and CS, but anything analytical is pretty fun as well.

    However I do get an extra kick from teaching because I think it’s such a positive thing to do in the world, whereas I can’t say the same about my paid computer work, and lately this has been on my mind (a la Tim O’Reilly’s Work on stuff that matters).

    I’d like to move towards aligning my work with my ideals. But $ is a factor, as an independent developer my pay is well above what I’d get teaching, for example. We’ll see how it goes.

12. Drew on January 19th, 2009 2:59 am

    Great article. I’m not convinced by this line in your proof:
    The digits of this number p are random and go on infinitely; it is a real number.

    I agree that p can’t be in the list because we have constructed it such that it is not real. I fail to see any property of p that would require it to be real. So I reject the contradiction on the grounds that p is not a real number.

    To complete the contradiction, you should trace its realness back to one of the real number construction methods (http://en.wikipedia.org/wiki/Construction_of_the_real_numbers). I’m not sure that that’s possible, because I suspect p is non-real. Not a mathematician though

13. P on January 19th, 2009 3:16 am

    Most excellent. Thank you.

14. Kalid on January 19th, 2009 4:17 am

    Hi Gustavo, I just wanted to commend you on doing a fantastic job on this writeup. I’m a big fan of clear, intuitive explanations and I think approaching topics with analogies & humor is a great tactic. I’ve been personally interested in understanding infinity better, and am looking forward to the next article!

15. amix on January 19th, 2009 6:40 am

    I would recommend watching Dangerous Knowledge: http://www.google.com/search?q=Dangerous%20Knowledge – it’s a BBC documentary on the fathers of modern mathematics:

    “In this one-off documentary, David Malone looks at four brilliant mathematicians – Georg Cantor, Ludwig Boltzmann, Kurt Gödel and Alan Turing – whose genius has profoundly affected us, but which tragically drove them insane and eventually led to them all committing suicide.”

16. Juan Reyero › Contando inifinitos on January 19th, 2009 11:46 am

    […] Excelente artículo de Gustavo Duarte sobre infinitos. Habla de infinitos numerables, y muestra que el conjunto de los racionales lo es. El todo que equivale a la parte: los números racionales incluyen a los enteros y a cualquier número que puedas construir con una fracción, pero Cantor vio que puedes asociar un número entero a cada número racional, sin dejarte ninguno. Los dos conjuntos son infinitos y equivalentes —equipotentes es la forma correcta de decirlo— a pesar de que uno de ellos incluye al otro. […]

17. Gustavo Duarte on January 19th, 2009 2:50 pm

    Thank you all for the feedback.

    @Drew: That is a really smart observation. In other uses of diagonalization, people make arguments very much like what you just made. For example, Turing does _exactly_ what you did with computable numbers by building a diagonal off a list of computable numbers, getting a resulting number, and showing that the resulting number is not computable.

    However, in this specific case, by definition our number _is_ real. Here is what you said:

    I fail to see any property of p that would require it to be real. So I reject the contradiction on the grounds that p is not a real number.

    My question to you would be this: if p is not real, then what is it? Is there some other set you’re proposing?

    It turns out that due to the way the reals are _defined_, they must contain our number, and any other number like it. If you write a program to generate a number whose digits are completely random, using a natural source for random bits, the result _by definition_ is a real number.

    So basically, ‘every number is in the reals’, unless it’s imaginary (http://en.wikipedia.org/wiki/Imaginary_number). This is a crude way of expressing it of course, but it follows from the precise definitions of the reals.

    The definition in question is that the reals are Dedekind-complete: http://en.wikipedia.org/wiki/Dedekind_completion.

    Suppose our crazy random number P were NOT a real number. Then it would divide the reals in two sets, one set A of all reals less than our number, and one set B of all reals more than our number. But P itself would not be in A nor B. But this violates the property of Dedekind completeness, so P must be in the reals.

    @Kalid: your site rocks, I have read many of your articles as well.

    Again, thank you all for stopping by.

18. Doetoe on January 21st, 2009 4:22 am

    To Drew and Gustavo:
    On the page mentioned by Drew\

    http://en.wikipedia.org/wiki/Construction_of_the_real_numbers
    several constructions are mentioned from which it can easily be seen that p is (or rather defines a) real number:
    one of the ways the real numbers are constructed is as equivalence classes of (or intuitively, limit of) Cauchy sequences of rational numbers. A sequence of decimal digits behind the decimal point really is (in this construction) the limit of its truncations, which is a Cauchy sequence of rational numbers. In fact, on that page it also mentions the construction as decimal expansions explicitly.
    The construction by Dedekind cuts that Gustavo is referring to also is easy to apply: in this construction p stands for the Dedekind cut of the rationals defined as follows: given a rational number you can say whether it is greater or smaller than p by looking at its decimal expansion and comparing those (lexicographically).
    Gustavo, I’m afraid your argument is not entirely watertight. Dedekind completeness means that if (A,B) is a Dedekind cut of the real numbers, then every real number is either contained in A or in B. If p is not a real number, there is no contradiction in p not being contained in either.

19. Doetoe on January 21st, 2009 8:11 am

    Correction: the last paragraph must be
    If (A,B) is a Dedekind cut of the real numbers, by definition every real number is either contained in A or in B. If p is not a real number, there can be no contradiction in p not being contained in either.
    (Dedekind completeness, meaning that B has a minimal element for every Dedekind cut, doesn’t enter the picture)

20. Gustavo Duarte on January 21st, 2009 4:14 pm

    @Doetoe: thanks for stopping by. I’ve been meaning to get my math back in shape, so this is great discussion. Here’s a better write up on completeness and what I tried to say (but failed):

    The rationals, reals and complex numbers are all ordered fields, roughly because they meet some criteria when it comes to addition, multiplication, and the relation < . So far so good.

    Now take a subset A of an ordered field F (eg, subset 0 to 2, inclusive, of the rationals). If we have an element u in F such that a <= u for all a in A, then that element is an _upper bound_ for A. For [0,2], here are some examples of upper bounds: 2, 3, 2.5, 1000, etc.

    But [0,2] has a special upper bound: 2. 2 is significant because it is an upper bound for [0,2] and it is <= _any other_ upper bound of [0,2]. 2 in this case is a _least upper bound_ or _supremum_ for [0,2].

    More generally, if A is a subset of ordered field F, s in F is a _least upper bound_ for A if and only if: 1) s is an upper bound for A; 2) s <= t for all upper bounds t of A.

    Now comes the rub: an ordered field F is _complete_ if and only if every nonempty subset of F that has an upper bound in F has a supremum that is also in F.

    The rationals are NOT complete. For example, think of the subset of rationals A, x in A such that x >= 0 and x^2 < = 2. This subset has plenty of rational upper bounds. For example: 1.5, 2, 300, etc.

    But it does NOT have a supremum in A. This is because fractions can always get closer and closer to the square root of 2, but they never reach it. So if you think you have a supremum s, it’s always possible to come up with a fraction such that it is > s and < = square root of 2. Thus s wasn’t a supremum after all. This can go on indifinitely.

    The reals, on the other hand, are complete. We define them as such, either directly or by defining another property that implies completeness. They are ‘the’ complete field, in fact, because any two complete ordered fields are isomorphic.

    So, in the case of the reals, this is what is going on: if the number p is NOT in the reals, I can define a subset A such that x in A: x < p. A has upper bounds in the reals, in fact any x > 1 is an upper bound for A due to how p was defined. However this subset does NOT have a supremum in the reals, because even though p is not in the reals, you can always approximate it a little further. But then, if this subset doesn’t have a supremum, the reals are NOT complete. This is a contradiction. Thus p is a real number, and it is indeed the supremum for A.

    So basically, that was a long way to say that by definition p is in the reals And now I want to go to grad school. hahah. Maybe I should take analysis in the fall.

21. Drew on January 21st, 2009 10:06 pm

    Let’s say we define the set of all p-like numbers S (where each kth digit is not the kth digit of the kth real).

    By the definition of the set S, to prove “p is real” it is necessary and sufficient to prove “S is the set of reals.”

    To undertake this task, we must do the following:

    ​1. Define a basic algebra on S.
    2. Show the set S Archimedian
    3. Show the set S complete.

    None of these are trivial undertakings. If even one of them falls, the entire system falls.

    What algebra are we defining in S? What would be the operation to add two elements of S, for instance? To multiply two elements of S?

    We can make S Archimedian easy enough, simply by using a left alphabetic ordering:

    1230…
    …
    1231…
    …
    1232…
    …
    1233…
    …
    1234…
    …
    1235…
    …
    1236…
    …
    1237…
    …
    1238…

    Proof by contradiction: this ordering is incomplete. Assume the ordering we’ve described is complete. In that case, each subset of S would have a least upper bound in S. We define such a subset to be the numbers in the ordering above. That is, for t element of S, 1230000… < t < 12389999…

    At this point we would have to invoke a little algebra to get a least upper bound. Surprisingly, that upper bound would be the number q = 12390000… Since each subset of S has a least upper bound in S, and since q is the least upper bound, q must be in S *

    However, by the definition of S, the kth digit cannot be some number k. Since we have accepted [0,1,2,3,4,5,6,7,8] in the 4th digit for elements in S, by the definition of S, there cannot exist some number in S with 9 in the 4th digit. Since q has a 9 in the 4th digit, it cannot be in S*. Since q is in S and q is not in S, we have a contradiction. QED.

22. Gustavo Duarte on January 21st, 2009 10:55 pm

    Drew,

    Here is what I think are the two problems with the proof:

    Let’s say we define the set of all p-like numbers S (where each kth digit is not the kth digit of the kth real).

    By the definition of the set S, to prove “p is real” it is necessary and sufficient to prove “S is the set of reals.”

    The first problem is the notion of the ‘kth’ real. There’s no such thing, _unless_ the reals are denumerable. So you’d have to prove that first before evoking the notion of kth real.

    The second problem is stating that it is necessary to prove that S is the set of reals. It would indeed be sufficient, but it’s not necessary. S can be a _subset_ of the reals, hence not complete.

    In fact, if you define some function mapping the naturals to the reals, such that the ‘kth’ real makes sense (the function would be non-surjective, assuming Cantor is right) and proceed to build set S, you’re right that S would not be complete.

    That would not be due to the fact that the numbers in it aren’t reals, but just because S would be a subset of the reals that isn’t complete, much like the naturals or rationals.

23. shinod on January 23rd, 2009 10:21 pm

    Thank you very much.
    its nice and very useful

24. Poromenos on January 27th, 2009 6:52 pm

    Great post, I’ve been meaning to read about infinities for a while but never found something this concise and understandable. I only have one addition: Where you say “It differs in at least one digit.”, it would perhaps be helpful to explain *why* this is so. It was not immediately obvious to me, and I had to look it up in Wikipedia.

    The answer, of course, is that if that number *were* on the list and was the Nth number, its Nth digit would be the red one, but we know that its Nth digit is different than the red one.

25. John Gabriel on April 25th, 2009 6:14 pm

    Is this forum a gathering place of idiots? Cantor was a fool and so I am not surprised.

    Your (Cantor’s) argument is lame. Do you understand that by changing the elements on the diagonal that you still end up with a number that is in fact in the original list? This of course being true assuming that every real number in the interval (0,1) can be represented as a decimal…

26. Gustavo Duarte on April 25th, 2009 8:22 pm

    @John: it is. Glad you stopped by!

27. Charles Ellmaker on October 27th, 2009 4:43 pm

    Gustavo -

    Excellent article. I’m not a mathematician but was introduced to the Cantor diagonal via Gödel, Escher, Bach. Anyway, I found in discussions with colleagues that it was necessary to be more explicit in the explanation. Something like:

    You take the digits on the diagonal in the table and construct a(n infinitely long) “new” number, which one assumes would be found someone in the infinitely long list of reals since all real numbers are in the table. However, now you change each digit in our “new” number by adding or subtracting one, etc., to make a new digit, and hence a new number. Strangely, that number is nowhere in the list.

    [Incredulity on the part of others. Huh? What?]

    Well, the new number is not the same as the first number in the list because the first digit is different.
    It’s not the same as the second number in the list because the second digit is different.
    …

    Anyway, I know that’s a bit long-winded, but most people need it spelled out explicity, at which point the light bulb goes on.

    Cheers,

    Charles

28. ShdNx on March 21st, 2011 12:35 pm

    An excellent article, thank you very much!

29. Wilson Maravilha on August 3rd, 2013 1:31 am

    Great Article Indeed! And awesome site. Today was my first visit but I intend to stick around. Was the post above inspired on D Hofstadter’s (GEB-EGB) presentation of the topic?

30. Gustavo Duarte on August 7th, 2013 6:21 am

    Wilson: thank you It wasn’t really inspired by GEB, to be honest I don’t remember reading Hofstadter’s presentation, but now I’m really curious, I’ll go check it out!