Good Math, Bad Math

Fun With Set Theory: Cantor’s Diagonalization

Posted by Mark C. Chu-Carroll on May 14, 2007
(42)
More »

While I’ve been writing about the Surreal numbers lately, it reminded me of some of the fun of Set theory. As a result, I’ve been going back to look at some old books. Since I’ve been enjoying it, I thought you folks would as well.

Set theory, along with its cousin, first order predicate logic, is pretty much the
foundation of nearly all modern math. You can construct math from a lot of
different foundations, but axiomatic set theory is currently pretty much the dominant approach. (Although Topoi seem to be making some headway…)

There’s a reason for that. Set theory starts with some of the simplest ideas, and extends in a reasonably straightforward way to encompass the most astonishingly complicated one. It’s truly remarkable in that – none of the competitors to set theory
as a foundation can approach the intuitive simplicity of set theory.

So I’m going to write a bit about set theory as I explore my old books. And I thought that a good place to start was Cantor’s diagonalization. Cantor is the inventor of set theory, and the diagonalization is an example of one of the first major results that Cantor published. It’s also a good excuse for talking a little bit about where set theory came from, which is not what most people expect. Set theory was originally created as a tool for talking about the relative sizes of different infinities.

Almost anyone who went to school in the last 40 years has had some exposure to sets, so we tend to think of them in terms of foundations. It surprises most people that sets were not proposed as a foundation at all: in fact, set theory started as
an outgrowth of number theory! Back in the 19th century, Cantor was doing work on
number theory and algebra, and invented what grew into set theory as a tool for comparing
the sizes of various sets of numbers. The original motivation behind the ideas that ended up growing into set theory was Cantors recognition of the fact that there’s a difference between the size of the set of rational numbers, and the size of the set of real numbers. They’re both infinite – but they’re not the same!

Cantor’s original idea was to abstract away the details of numbers – order, structure, etc., and just look at them as collections of objects – that is, as sets. Then, if you can create a one-to-one correspondence between two sets of numbers, then those sets must be the same size. But when you look at the set of real numbers and the set of rational numbers, there’s no way to create a one-to-one mapping: in fact, you can easily prove that any one-to-one mapping between the rationals and the reals will necessarily
omit some of the real numbers.

It’s worth taking the time to repeat that basic proof here. I’m going to use a slightly simplified version, which shows that you can’t map between the natural numbers and the reals between 0 and 1; since it’s easy to show that there’s a one-to-one mapping between the natural numbers and the rationals; and that there’s a one-to-one mapping between the set of all reals between 0 and 1 and the set of all reals, it means the same thing, but there are less tricks involved.

It’s a basic proof by contradiction. Suppose that we can create a one-to-one correspondence between the natural numbers and the reals between 0 and 1. What that would mean is that there would be a total one-to-one onto function R from the natural numbers to the reals. So we could create a complete list of all of the real numbers: R(0), R(1), R(2), …

If we could do that, then we could also create another function, D (for digit), where D(x,y)=the yth digit of the binary expansion of R(x). So D is effectively a table where every row is a real number, and every column is a digit position in the binary expansion of a real number. D(x,3) is the third digit of the binary expansion of x. So, for example, if x=3/8, then the binary expansion of x is 0.011. So D(3/8,1)=0, D(3/8,2)=1, D(3/8,3)=1, D(3/8,4)=0, …

Now, here comes the nifty part. Take the table for D, and start walking down the diagonal. So we’re going to go down the table looking at D(1,1), D(2,2), D(3,3), and so on. And as we walk down that diagonal, we’re going to write down digits. For D(0,0), the first digit, we’ll write 0 if D(0,0)=1, and 1 if D(0,0)=0. We’ll do the same thing for each digit. For the ith digit, if D(i,i)=0, we’ll write 1, and if D(i,i)=1, we’ll write 0.

The result that we get is a series of binary digits – that is, a binary expansion of some number. Let’s call that number T. T is different from every row in D in at least one digit – for the ith row, T is different at digit i. So there’s no x where R(x)=T. But T is clearly a real number between 0 and 1. So the mapping can’t
possible work. And since we didn’t specify the structure of the mapping – we just assumed that there was one, that means that there’s no possible mapping that will work: this construction will always create a counterexample showing that the mapping is incomplete.

So the set of all real numbers between 0 and 1 is strictly larger than the set of all natural numbers. And by extension, the set of all real numbers is strictly larger than the set of all rational numbers.

That argument is called Cantor’s diagonalization. And it’s pretty much the argument
that put set theory on the map.

(42)
More »

Comments

  1. #1 Cat lover
    May 14, 2007

    I feel obliged to make the nitpicky comment that your version of the argument doesn’t quite work, since real numbers don’t have unique binary expansions. (The standard way around this is to work in, say, base 3, disallow terminating strings of 2′s in the initial list, and avoid using 2′s in the diagonalization step.)

    On a more substantive note, I must confess that I don’t particularly like the place-value diagonalization argument in the first place, for the reason that, by the time you understand the subtleties involved in making it a rigorous argument, you probably already know that the reals are uncountable. Personally, I prefer the general diagonalization argument for powersets, followed by noting that the interval (0,1) is (at least for set-theoretic purposes) the same as the powerset of a countable set.

  2. #2 Chad Groft
    May 15, 2007

    Glad to see you doing some articles on this!

    Minor historical note: there’s another proof that R is uncountable which runs along quite different lines, and which I believe was Cantor’s original proof. To wit: suppose {x_n} is a sequence containing all the real numbers. Define a new sequence {a_n} as follows: a_0 = x_0, and a_1 is the first entry in the sequence {x_n} which is greater than a_0. From there, a_(n+2) is the first entry in {x_n} which lies after a_(n+1) in the sequence and lies strictly between a_n and a_(n+1) in the standard ordering on the reals. (This must always be possible, otherwise {x_n} doesn’t really hit all of the real numbers.)

    It’s not too hard to see that the subsequence {a_(2n)} is monotone increasing, and bounded above (by a_1). It therefore has a limit b, which is not among the {a_n}; it’s greater than every a_(2n) and less than every a_(2n+1). But by that same token, if b = x_i for some index i, then it would have been caught in the sequence {a_n} at some point, being strictly between its earlier terms. Contradiction.

    There are other proofs which use Lebesgue measure or first and second category. I think the diagonal proof is the clearest, but this one is interesting too, if only because it uses the axioms for the real line more directly.

  3. #3 Susan B.
    May 15, 2007

    Hooray! Cantor’s Diagonalization is one of my favorite pieces of mathematics–a fairly simple (but not obvious!) and elegant method for achieving a very deep result! I’ve used this as an example to several of my friends when they’ve claimed that mathematics can’t be beautiful, and it can’t be beat.

  4. #4 Mark Dow
    May 15, 2007

    Nice, for good math and bad, that you chose this clever proof for an introduction to set theory. This proof has irked many, and led to an unusual amount literature, cranky and philosophical. See Controversy over Cantor’s theory for an overview of criticism, and Wilfrid Hodges’ paper An Editor Recalls Some Hopeless Papers for analysis of specific misperceptions:
    “I dedicate this essay to the two-dozen-odd people whose refutations of Cantor’s diagonal argument have come to me either as referee or as editor in the last twenty years or so. …”

  5. #5 Thony C.
    May 15, 2007

    As usual for me some historical comments:

    Cantor’s diagonalization

    Everybody talks of Cantor’s diagonalisation but in fact it was Paul du Bois-Reymond who first invented and used this process, which of course plays a central role in Gödels work.

    Cantor is the inventor of set theory…Almost anyone who went to school in the last 40 years has had some exposure to sets

    I always get a little annoyed when I read statements like this (no offence to Mark who as usual written a very good and very interesting article) and such statements are unfortunately almost universal. The so-called naïve set theory taught in schools is not Cantor’s Mengenlehre but the Algebra of Classes invented/discovered (choose your own word according to your personal philosophy of mathematics) by George Boole and first published by him in 1847 in his Mathematical Analysis of Logic.

    The original motivation behind the ideas that ended up growing into set theory was Cantors recognition of the fact that there’s a difference between the size of the set of rational numbers, and the size of the set of real numbers. They’re both infinite – but they’re not the same!

    Cantor was not the first person to notice the so-called paradoxes of infinity. As far as I know the earliest reference is Galileo who noticed that the set of whole numbers can be put in one to one correspondence with the set of odd or even numbers. In the nineteenth century De Morgan wrote extensively on the subject. Canton was however the first to apply strict mathematical methods to the subject.

  6. #6 Torbjörn Larsson, OM
    May 15, 2007

    Usually I don’t like the modern colloquialism “infinitely” much. But comparing infinities and diagonalizing them (or not) is really “infinitely enlightening”.

    Or enlightening infinities. Whatever.

  7. #7 Maya Incaand
    May 15, 2007

    Uncountable gives the idea that there is something to count.

    IF there is a continuum there are no “points”.

    Even if there is no continuum a real just goes on and on for ever, you can never write it down.

    So the whole idea of 1:1 correspondence is complete nonsense.

    (Yep, I’m a constructive kind of guy).

  8. #8 Chris Grant
    May 15, 2007

    (1) Chad Groft is correct that Cantor’s original proof of the uncountability of the reals was not the diagonalization proof. I haven’t thought about Chad’s alternative proof carefully enough to see if it’s equivalent to Cantor’s original proof, but you can check for yourself by examining my translation of Cantor’s original paper here. (The only other translation I know of is in Ewald’s expensive sourcebook. His translation may be more elegant–I don’t know, I’ve never seen it–but mine is free!)

    (2) Thony C. is right that we sometimes attribute too much of set theory to Cantor. A highly recommendable book that chronicles the contributions of others is Jose Ferreiros’s Labyrinth of Thought, of which a paperback edition is coming in August at half the cost of the pricey hardback.

    (3) While Cantor’s early work was in number theory, I don’t think it is correct to place his set-theoretic work in that context, as opposed to the context of analysis, particularly Fourier analysis. See, e.g., page 30 of Dauben’s standard biography of Cantor.

    (4) Finally, my most important comment: It’s “fewer tricks”, not “less tricks”!

  9. #9 Anonymous
    May 15, 2007

    Out of curiosity, which books are you reading? I’m (slowly) going through ONAG, and I get the feeling I need more set theory background. Any suggestions?

  10. #10 Mark C. Chu-Carroll
    May 15, 2007

    The book I’ve got is the revise edition of the classic text by Quine. Not exactly easy going, but it is pretty much the definitive text. I’ll put a link to it in my next post.

  11. #11 Thony C.
    May 15, 2007

    Jose Ferreiros’s Labyrinth of Thought, of which a paperback edition is coming in August at half the cost of the pricey hardback.

    Even half of $168 is still f*#%!+g expensive!

  12. #12 Chris Grant
    May 15, 2007

    Re #10:

    Worth every penny. And here’s a cost-savings tip: Springer books are often substantially cheaper at Amazon.ca than at Amazon.com. Ferreiros’s paperback lists at 56.56CDN at the former.

  13. #13 Polymath
    May 15, 2007

    you might be interested in the coolest proof i’ve seen of the countability of the rationals (not covered in this post, but a counterintuitive fact about cardinality as well). it’s on my blog at

    http://polymathematics.typepad.com/polymath/2006/08/countability.html

  14. #14 Jonathan Lubin
    May 15, 2007

    My understanding is that although Number Theory was Cantor’s first field of endeavor, he came to Set Theory not through that but through Fourier Analysis. The Wikipedia article seems to support this idea. The problems of the infinite are much more likely to crop up in Fourier stuff than in ordinary Number Theory, it seems to me.

  15. #15 Brian Jaress
    May 15, 2007

    If you haven’t seen it, you might want to check out “An Editor Recalls Some Hopeless Papers:”

    http://www.math.ucla.edu/~asl/bsl/0401/0401-001.ps

    It’s about attempts to refute Cantor’s argument and contains examples of bad math.

  16. #16 Mark W
    May 15, 2007

    I suppose you will talk about the Axiom of Choice at some point?

  17. #17 Harald Hanche-Olsen
    May 15, 2007

    Another version of the diagonal argument, which neatly avoids the problem with nonuniqueness, employs continued fractions: Every positive real number can be written uniquely as a continued fraction [a0;a1,a2,...] where a0 is a nonnegative integer and the other coefficients are positive integers. If the reals are enumerated, write all these below each other, then go down the diagonal and pick a 1 everywhere, except you pick a 2 whenever you see a 1. The result is a new continued fraction that is not in the list.

  18. #18 Harald Hanche-Olsen
    May 15, 2007

    Oh, and Polymath, your proof of the countability may be cool, but I know one that is supercool. Unfortunately, I cannot claim credit for it myself:

    The trick is to place the positive rational numbers at the nodes of an infinite binary tree. At the root you place 1=1/1. Below m/n, where m and n are mutually prime natural numbers, you place m/(m+n) as the left child and (m+n)/n as the right one. This puts the rationals in a one-to-one correspondence with the nodes of this tree.

    To find the position of a number p/q in this tree (with p, q mutually prime), if p>q then the number is the right child of (p-q)/q, while if p<q then it is the left child of p/(q-p). Repeat until you reach 1/1, and you have your position. Note that what you’re really doing here is to follow Euclid’s algorithm. Note that division is repeated subtraction after all.

    But there’s more: To establish a one-to-one correspondence with the naturals, label the root node of the tree as number 1, then label the left child of the node numbered N as 2N and the right child as 2N+1. In binary, this just means appending a 0 or a 1 to the binary digits of N.

    In summary, to find the sequence number of p/q, you collect the binary digits starting at the rear, alternately adding zeros and ones in numbers corresponding to the quotients as you reduce the number by Euclid’s algorithm.

    I wish I remembered who showed this to me, so I could give appropriate credit.

  19. #19 Polymath
    May 15, 2007

    harald:

    i like your proof too, since the act of locating p/q in the tree has mathematical significance in itself. but for sheer simplicity and persuasiveness, i’m going to stick with mine as the coolest i know.

    good thing intelligent people can disagree here.

  20. #20 Dylan
    May 15, 2007

    The passage, “So, for example, if x=3/8, then the binary expansion of x is 0.011. So D(3/8,1)=0, D(3/8,2)=1, D(3/8,3)=1, D(3/8,4)=0, …” should read, “So, for example, if R(x)=3/8, then the binary expansion of R(x) is 0.011. So D(x,1)=0, D(x,2)=1, D(x,3)=1, D(x,4)=0, …”

  21. #21 Xanthir, FCD
    May 16, 2007

    Harald:

    I’m assuming that, when you’re trying to populate the children of the root node, you assume that 1/1 has its num and den mutually prime? That way the children are then just 1/2 and 2/1?

  22. #22 Harald Hanche-Olsen
    May 16, 2007

    Xanthir: You’re right.

  23. #23 Jon
    May 16, 2007

    Harald (or someone else):
    If you take your tree and make it the right child of a tree with 0 as it’s root and a left child that is the original tree flipped and inverted (so it’s root is -1/1, its right child is -1/2 and it’s left child is -2/1) I believe you get a tree representing all of the surreal numbers (or games, not sure which if either). I’m not sure if that is at all insightful or correct, but just thought I’d point it out.

    MarkCC (or someone else):
    In that “An Editor Recalls Some Hopeless Papers” one thing I didn’t understand was why the infinite preceding zero’s argument is wrong. Or rather, what that set would be if it isn’t the natural numbers and why it can’t be mapped to the natural numbers.

  24. #24 Xanthir, FCD
    May 16, 2007

    Jon: That was my first thought as well, but a quick look at Harald’s construction shows that it’s not quite equivalent with the surreals.

    For starters, any surreal with a finite birthday is a dyadic rational, of the form x/2n, for some x and n. However, Harald’s construction yields the number 1/3 on the 3rd level, as the left child of 1/2.

    Note, though, that even if this *did* represent the surreals, it wouldn’t correspond with games, as games are (generally) non-numeric. On the other hand, every element in this tree is constructed from numbers using well defined [number -> number] functions.

  25. #25 Ørjan Johansen
    May 16, 2007

    Jon:
    If you add 0 and a flipped tree of negatives to the left you get all the rational numbers, not all the surreals or games. For the surreals in +- notation the rule for what are the left and right children is quite different and only gives you rational numbers whose denominators are powers of two, unless you go to infinite birthdays, in which case they no longer form an ordinary tree.

    I just looked at “An Editor Recalls Some Hopeless Papers” and he doesn’t mention “infinite preceding zeros” anywhere. Although he does mention p-adic numbers. Indeed the natural numbers are just the p-adic numbers with infinitely many of the digits zero.

  26. #26 Ørjan Johansen
    May 16, 2007

    I mean, all but finitely many of the digits zero.

  27. #27 Antendren
    May 16, 2007

    Also, note that that tree is a set – in fact, it’s countable. Meanwhile, the surreals are a proper class (i.e., way too big to be that tree).

  28. #28 Jon L
    May 16, 2007

    Ok, that makes sense. It didn’t seem right (I didn’t think the surreals where countable) but I wasn’t sure why it was wrong.

    As for the “Hopeless Papers”, yeah p-adic numbers are what I was talking about (I didn’t actually click that link but had seen it before). After wiki-ing p-adic numbers and sitting and thinking for a few minutes, I think I understand why they aren’t one-to-one onto with the naturals.

  29. #29 Ørjan Johansen
    May 16, 2007

    Cantor’s diagonalization proof is easily reused for the p-adics, just switch the direction of the digit sequence.

  30. #30 Jon L
    May 17, 2007

    Heh, I didn’t even mention this but I didn’t find cantor’s diagonalization particularly convincing (intuitively)

    Point being it’s not really what I’m looking for. It doesn’t (to me, in an intuitive way) explain why the natural numbers have to have a finite number of digits. I’m assuming that is true even though in my own, naive understanding the natural numbers are simply all positive integers and infinity is a number sufficiently large or a limit that grows without bounds. In other words, if the domain of the naturals is 0 to infinity why can’t I approximate infinity as an infinite number of 9′s? And my answer to my own question was that an infinite number of 9′s isn’t exactly a number. But then that raises the question of what a number is and at that point I deleted most of my previous post and just put ‘I think I understand.’ (also now that I think about it I guess the natural numbers are also defined as the counting numbers, and no matter how long you count your not reaching an infinite number of 9′s. Heheh, and furthermore defining an approximation of infinity as an infinite number of 9′s doesn’t even make sense since it’s approximating infinity in terms of itself.)

    So, yeah, now you see why I deleted most of this rambling last time :)

  31. #31 Ørjan Johansen
    May 17, 2007

    Well, finite means having a size equal to a natural number. And as a very rough estimate, every natural number from 1 on has a number of digits that is less than or equal to the number itself.

    This is proved by induction, and the axiom of induction is what limits the set of natural numbers not to include anything more than necessary.

  32. #32 Peter
    May 17, 2007

    Cantor’s proof is one of the most beautiful pieces of math it is my privilege to understand.

    My top 3

    Euclid’s proof of the infinitude of the primes
    The proof that square root 2 is irrational
    Cantor’s proof.

  33. #33 Jon Runge
    May 25, 2007

    I am a member of the fairly large group of people who disagrees with Cantor’s theories of the infinite. If anyone cares to read the short five paragraph critique of the diagonal method (directly following), and to comment, I would appreciate it. Thanks to anyone for constructive comments.

    A. The problem with Cantor’s use of the diagonal method is that it uses a bait and switch tactic in proving the existence of the transfinite numbers. “Bait and switch” refers to a sales tactic in which customers are attracted by an ad for a low priced item and then are encouraged to buy a higher priced one. In a similar fashion Cantor’s diagonal method makes a switch in the course of the proof that involves a shift in what is being “sold” to the reader. This “switch” involves the diagonal method.

    B. One way to see how Cantor’s bait and switch works is by doing an honest comparison of the two infinities. The infinite set of the natural numbers and the infinite set of the real numbers are compared (see below) using base 2 arithmetic for convenience. First, write the natural numbers in a list in the usual order beginning with the integer 1. Next construct a list of the real numbers in the interval between zero and 0.1111111….. in a way that is completely transparent (unlike Cantor’s approach).

    C. In the lists below the first sixteen natural numbers are put in a one to one pairing with the first sixteen real numbers according to the following rule. For every natural number there is a corresponding real number which involves a symmetry about the decimal point. (The “~~~~” symbols are used below to create spacing so that the lists are lined up.) For example, the natural number 1 is matched with the real number 0.1. The natural number 10 is matched with the real number 0.01. The natural number 11 is matched with the real number 0.11, etc. etc. etc. Then the real numbers in the second column are put in numeric order in the third column to make it easy to see how the infinite list of the real numbers compares with the infinite list of the natural numbers.

    1~~~~~~~0.1~~~~~~~0.0001
    10~~~~~~0.01~~~~~~0.0010
    11~~~~~~0.11~~~~~~0.0011
    100~~~~~0.001~~~~~0.0100
    101~~~~~0.101~~~~~0.0101
    110~~~~~0.011~~~~~0.0110
    111~~~~~0.111~~~~~0.0111
    1000~~~~0.0001~~~~0.1000
    1001~~~~0.1001~~~~0.1001
    1010~~~~0.0101~~~~0.1010
    1011~~~~0.1101~~~~0.1011
    1100~~~~0.0011~~~~0.1100
    1101~~~~0.1011~~~~0.1101
    1110~~~~0.0111~~~~0.1110
    1111~~~~0.1111~~~~0.1111
    10000~~~0.00001~~~
    …..~~~~~…….~~~~~……….

    D. Note that the infinite list of the natural numbers (first list) and the infinite list of the real numbers (third list) are equivalent to one another, except for the imposition of a decimal point. This creates an irrefutable, one to one correspondence between the two lists. Now both of these infinite lists are honest and transparent in indicating how to list all of the elements in the list. Both of these lists are also identically infinite, which supports the concept of a uniformly consistent absolute infinity. Finally, in a transparent comparison of the list of the natural numbers and the real numbers it is seen that the DIAGONAL METHOD CANNOT BE SELECTIVELY APPLIED TO JUST ONE OF THESE LISTS (as Cantor does with the diagonal method). It is clear that both lists are complete. It is clear that it is impossible to create a number in either infinite list that is not already on the list.

    E. Thanks to anyone for constructive criticism. One of the best responses to claims that the diagonal method proves anything seems to come from poetry. The diagonal method gives the illusion of being an extremely powerful method for proving a statement about the infinite that can be understood in five or ten minutes. Alexander Pope describes this kind of an illusion.

    “A little learning is a dangerous thing.
    Drink deep, or taste not the Pierian spring.**
    There shallow droughts intoxicate the brain,
    And drinking largely sobers us again.”
    **a spring in Macedonia, sacred to the Muses, or a source of inspiration

  34. #34 Mark C. Chu-Carroll
    May 25, 2007

    Jon:

    First – you’re arguing about Cantor’s reals; the transfinites have nothing to do with the diagonalization proof. Your mention of the transfinites in the context of a discussion of the correctness of Cantor’s proof about the size of the set of reals is just a red herring.

    The problem with your argument is simple – and illustrated by the following question: Where does π appear in your list of the reals?

    The way that you list the reals, your list will never include an irrational number. You’ll never get to one. So your so-called list of the reals is really just another version of a list of the rationals – and not even a complete list of the rationals at that.

    So yeah – if you eliminate all of the irrational numbers, and in fact all of the non-terminating forms of rational numbers, then you get a set of numbers which can be put into one to one correspondance with the naturals. But that’s because you’ve excluded most of the set of real numbers.

  35. #35 Antendren
    May 25, 2007

    Another point, which has less to do with math and more to do with rhetoric: you claim that there’s a flaw in Cantor’s proof, but you don’t actually say what it is (at least, not in a way that’s clear to me). I’m familiar with concept of a bait and switch, but you haven’t shown me how Cantor employs one.

  36. #36 Mark C. Chu-Carroll
    May 25, 2007

    Anterendren:

    If I’m understanding him correctly, I think that he thinks that the system of enumerating the reals in the diagonalization is a cheat: so the “bait and switch” that he claims is switching the set of the reals for the enumerated set used by the diagonalization. He’s arguing that the set enumerated in the diagonalization is not the set of the reals, and that the “switch” from his preferred enumeration of the reals to any of the enumerations used in forms of the diagonalization is replacing the set of reals (which he believe is enumerable) with a false set of reals (which causes the problem).

    It’s one of the common arguments from people who hate Cantor’s proof: that the proof relies on a specific trick in the enumeration, and that that trick is a cheat, which for one reason or another doesn’t really work; but if you’ll just use their enumeration, the proof will fall apart.

    But as usual, it’s a silly argument: take his preferred enumeration, and you can easily find reals that will never appear in it – meaning that it’s an incomplete enumeration, and thus not a disproof of Cantor. In the case of Jon, as I pointed out, his preferred enumeration – basically a lexicographically ordered listing of terminating binary forms – fails by following the diagonalization procedure on it; and we can also just point out numerous reals that will never actually appear anywhere in his enumeration: π, e, the square root of 2, 1/3…. In fact, his enumeration is far weaker, than the classic one that he claims is some kind of cheat.

  37. #37 Jon Runge
    May 25, 2007

    First, I usually like to think carefully about a subject like this before speaking, or posting a message. But I have a limited amount of time for working on this, and so I will make some off the cuff remarks which hopefully will clarify points of disagreement. I have a great deal of respect for the intelligence of the people who are reading this post, although for the most part I cannot figure out why you think the way that you do. No disrespect intended. I am just perplexed.

    Second, the real problem seems to be that we begin with very different assumptions about mathematical logic and infinity and so forth. This should not be surprising. There are different “schools” of mathematics, each of which has its own philosophy. I just believe that Cantor’s and Russell’s and Hilbert’s philosophy or theology of mathematics ends in utter chaos.

    Third, now for some specifics. The following statement from the preceding post is correct. “If I’m understanding him correctly, I think that he thinks that the system of enumerating the reals in the diagonalization is a cheat: so the “bait and switch” that he claims is switching the set of the reals for the enumerated set used by the diagonalization.” This is correct.

    Let me try to clarify this point further. I admit that this is a bit convoluted. Cantor’s diagonalization is a technique used to show that the integers and the reals cannot be put into a one to one correspondence because the uncountably infinite set of the real numbers is larger than the countably infinite set of integers. The key is that diagonalization is used in a proof by contradiction or a reductio ad absurdum.

    POINT ONE: The proof initially assumes that infinite lists of the reals and the integers are equivalent and complete. POINT TWO: Then diagonalization is used to prove a contradiction, or that the list of the reals is not complete. POINT THREE: This is because diagonalization creates a “dwarf”, or a truncated infinite set of real numbers. POINT FOUR: In the proof by contradiction this dwarf makes it possible for Cantor to say that the list of reals is not complete.

    At the risk of oversimplification, and given time constraints, that is about as simple as I can make it. Now which point or points does a reader agree with? Disagree with? Is the disagreement a matter of wording? Or of substance? Can any differences be resolved, or is this impossible?

    Fourth, here is something else that causes me to become perplexed. From the preceding post: “The way that you list the reals, your list will never include an irrational number. You’ll never get to one.” It seems that the idea here is that one gets to infinity (or some infinite number) by going at 1000 miles per hour for so much time or something like that. That is not how I think of these infinite lists. Once you make the rule for describing elements in the list, you are already everywhere on the list, or anywhere specifically that you want to be. After all, it is not like you are going to get there in ten seconds or ten minutes or something like that.

    Fifth, the previous posting says, “So your so-called list of the reals is really just another version of a list of the rationals – and not even a complete list of the rationals at that.” Since the list of the reals is equivalent to the list of the integers (as I expressed it), is this saying that the infinity of the integers is less than the infinity of the rational numbers?

    I think of myself primarily as an amateur theologian, and of course theologians are very much interested in thinking logically about the subject of infinity. I welcome your criticism and comments. I will respond (as long as you care to discuss this subject) as frequently as I am able. I will be working on other things for a few days. Thank you for your thoughts on this subject.

  38. #38 Antendren
    May 26, 2007

    I’m happy to discuss this.

    With points 1 and 2, I agree completely.

    Point 3 I take small issue with: the diagonalization creates a single new real, not an infinite set of them.

    Point 4 I then agree with: the new real allows us to say that the list is incomplete.

    Taken together, these four points seem to support Cantor’s proof. Which of these points do you find fault with? Or do you disagree that together they prove the result?

    Once you make the rule for describing elements in the list, you are already everywhere on the list, or anywhere specifically that you want to be. After all, it is not like you are going to get there in ten seconds or ten minutes or something like that.

    Agreed. When Mark said “you’ll never get to an irrational number”, that was simply a convenient short-hand for “irrational numbers do not appear anywhere on your list”. It’s a commonly used turn of phrase amongst mathematicians, but it does suggest an approach that’s not strictly accurate.

    That said, I agree with his point of contention. I claim that your list is not complete. If it is, you should be able to tell me where on that list π occurs. To what integer is it associated?

  39. #39 Jon Runge
    May 31, 2007

    Antendren,

    I have been thinking about your post for the last few days. It seems to me that we are using the same words, but that we attach different meanings to the same words. This is one source of our disagreement.

    For example, my post says —— “POINT ONE: The proof initially assumes that infinite lists of the reals and the integers are equivalent and complete. POINT TWO: Then diagonalization is used to prove a contradiction, or that the list of the reals is not complete. POINT THREE: This is because diagonalization creates a “dwarf”, or a truncated infinite set of real numbers. POINT FOUR: In the proof by contradiction this dwarf makes it possible for Cantor to say that the list of reals is not complete.”

    Then your post responds —– “With points 1 and 2, I agree completely. Point 3 I take small issue with: the diagonalization creates a single new real, not an infinite set of them. Point 4 I then agree with: the new real allows us to say that the list is incomplete.”

    Specifically, it appears to me that we are not using words like “complete” and “diagonalization” in the same way. To some extent this reflects the fact that we are not operating under the same assumptions (or the same axioms). It also reflects the fact that there can be honest confusion about what Cantor is saying. To continue: It seems to me that your idea of infinity is represented by counting to infinity in a BASE ONE FORMAT, or as /, //, ///, ////, /////, //////, ///////, etc. If these elements are put in vertical order, this way of counting to infinity even gives a “diagonal method” for counting to infinity. Using a base one number system to count is certainly a very pure and acceptable way of counting to infinity in whole numbers. This also fits with a reluctance to apply diagonal methods (in the reverse order) to an infinite list of the integers.

    By comparison, when I think of a complete infinity, I think in terms of an “absolute” infinity. Using integers in a base 10 system as a model for an absolute infinity means that this would include all of the integers from 1, 2, 3, etc. to ….999999 (where there is an endless string of 9′s extending to the left of the 9′s that are shown). To me it seems reasonable to create a one-to-one correspondence between this set of the integers and the set of the real numbers by using a symmetry about the decimal point (see a previous post).

    For example, you ask where the integer is that corresponds to pi in a one-to-one correspondence between the infinite set of the integers and the real numbers. The answer is that there is a symmetry about the decimal point which gives where this number is located. This one-to-one correspondence for pi (actually pi/10) that gives an integer is given by

    …….951413.314159…….

    where there is an identical string of numbers to the left and the right. Therefore, if you will show me where pi (or pi/10) is on the list of the real numbers, I can write out the corresponding integer …..951413. In fact, it is possible to do this for every entry on Cantor’s list of the real numbers.

    Also, in thinking in the logic of absolute infinity, I am not concerned about “getting to” a number like pi or ……999999. In absolute infinity it is AXIOMATIC that these numbers are just “there” in the “complete” set of the integers/real numbers. This is the nature of an absolute infinity. The advantage of thinking axiomatically about infinities like this is that it also eliminates Russell’s paradox and Cantor’s paradox for the set of all sets. It is too much of a digression to go into this here. I know that this violates what the textbooks teach, but I don’t believe that whatever Cantor or Hilbert or Russell or Godel etc. says is true (just because they say so —- and especially on the subject of infinity). I do not believe everything that I read in the newspapers either.

    Also, there is the point about the diagonalization process. I just looked at several places on the Internet which seem (??? —- I am wondering if I read these articles correctly) to support your contention. I am not a Cantorian, but it is my understanding that (in the spirit of Cantor) one does the diagonalization over and over an infinite number of times to demonstrate that it is impossible to ever “get to” a complete list of the real numbers. It seems to me that if diagonalization just creates one single new real number (as you seem to be saying), then this number can be added to the “incomplete” list of the real numbers to make a “complete” list of the real numbers. Then there is no actual difference between the infinite list of the real numbers and the infinite list of the integers.

    This may just be a question of semantics, but in any case I do not find Cantorian arguments convincing. Thank you for your response.

  40. #40 Antendren
    May 31, 2007

    First allow me to clarify: A list of real numbers is “complete” if every real number shows up on it.

    “Diagonalization” is a process by which, from any list of real numbers, we can create a new real number which is not on the list.

    For the purposes of Cantor’s proof, we only need to create 1 such number. Yes, we could easily modify our list by adding this 1 number to it, but that doesn’t matter. We assumed the list was complete, and the existence of even 1 number not on it is a contradiction.

    The heart of our disagreement comes from this:
    “this would include all of the integers from 1, 2, 3, etc. to ….999999″

    There is no such integer “…999″. Integers extend only finitely far to the left. This is not a question of different ways of thinking about infinity; it’s simply the definition of the integers.

    One certainly can think about numbers that extend infinitely far to the left, but they’ll be something else (e.g., p-adics). And when you consider these numbers, they will have the same size as the reals, as you just showed.

  41. #41 Jon Runge
    May 31, 2007

    Thank you for the information. I have been curious about “p-adic numbers”, but I never had time to check up on what they are exactly.

  42. #42 John Gabriel
    January 9, 2008

    Cantor’s peers did not agree with him. This can be a good sign but in Cantor’s case showed only that Cantor was not very smart indeed. However, it does not take genius to see that Cantor’s theories are full of ‘holes’. In fact your article contains quite a few errors too. One that leaps out at me is your statement about not being able to place the real interval [0,1] in a 1-1 correspondence with the natural numbers. This is completely untrue. It can be done fairly easy.

    Cantor’s diagonalization argument is invalid. Rather than try to explain all this here, you might visit my url and read a blog called “Are real numbers countable?”. The blog answers these questions.