Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Absurdity of Cantor's Diagonal Slash

  1. Mar 2, 2005 #1
    Cantor's diagonal slash has been used to argue that the infinity of reals is uncountable, whereas the infinity of integers is countable (hence the two infinities are different). I assume that readers are familiar with Cantor's diagonal slash argument.

    What happens if we apply Cantor's diagonal slash to the integers? How can this be done? Think of the infinite binary tree, which starts at ground level as the trunk and splits in two (bifurcates) as we ascend; if we take the left branch then we assign 0 to the first binary digit, if the right branch then 1. At the next level we do the same....0 if we go left, 1 if we go right.... and we ascend the binary tree all the way to infinity. In this way every possible infinite sequence of binary digits is represented somehow or other (mapped out) by a path up the tree; and every path up the tree corresponds to a unique infinite sequence of binary digits.

    For those who are curious, the number of routes up the tree is equal to 2^n (where n is the number of levels), and the number of nodes (branches) in the tree is equal to (2^n)-1.

    Now we can arrange all of these paths in an infinite x infinite binary matrix, of form similar to the infinite x infinite matrix of real numbers that Cantor used for his diagonal slash. What happens if we perform Cantor's diagonal slash on this infinite binary matrix? According to Cantor, we produce a new infinite binary sequence which is NOT contained within the original matrix (nor is it contained on the infinite binary tree). But how can this be? The matrix contains every possible route up the binary tree, there IS no other route not contained in the matrix.

    What does this show?

    That Cantor's diagonal slash argument is meaningless when applied to infinite matrices.
     
  2. jcsd
  3. Mar 2, 2005 #2
    You're assuming this is possible. You haven't provided a method for actually placing all of these paths into a matrix.

    Note that not all possible paths will correspond to an integer; so you can't use the fact that the integers are countable to produce a listing of all possible paths.

    Actually, it shows that the set of all possible paths through an infinite binary tree is uncountable. Unless you can produce some separate proof that the set is countable, you haven't found a contradiction.
     
  4. Mar 2, 2005 #3
    It shows that your understanding of the proof and related issues is poor.

    For starters you need to figure out if you're talking about the collection of all vertices/nodes in the tree or the collection of all paths. You seem to be talking about either at any given point in your argument but they are different things. For example we can't have:

    and

     
    Last edited: Mar 2, 2005
  5. Mar 2, 2005 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Cantor's diagonal argument is clearer in a more algebraic form.

    Suppose f is a 1-1 mapping between the positive integers and the reals.

    Let dn be the function that returns the n-th digit of a real number.


    Now, let's construct a real number, r. For the n-th digit of r, select something different from dn(f(n)), and not 0 or 9.

    Now, suppose f(m) = r. Then, the m-th digit of r must be dm(r) = dm(f(m)), but by construction that cannot be the m-th digit of r.


    Therefore, no such f exists.

    Thus, there is no 1-1 mapping between the positive integers and the reals.


    The important thing to note is when I construct r, it really is a real number.


    (by n-th digit, I mean to the right of the decimal point)
     
  6. Mar 3, 2005 #5
    Each path to the top of the infinite binary tree is coded by a unique binary number of infinite digits. There are an infinite number of different paths. Each path (infinite binary number) can be a row of the matrix, and there will then be an infinite number of rows, hence we have an infinite by infinite matrix. This is conceptually no different to the construction of an infinite by infinite matrix of real numbers which is classically used to demonstrate Cantor's diagonal slash.

    Sorry, you are incorrect. Every possible path up to the top of the binary tree is coded by a unique binary integer (each of infinite length). There is no path which does not correspond to an integer.

    It shows nothing of the kind. An infinite binary tree is simply a set of integers (binary integers). There are no real numbers involved. Each infinite binary integer in the tree can be paired uniquely with a correspionding unique decimal integer. If you believe the set of infinite binary integers is uncountable then this implies also that the set of decimal integers is uncountable (and I don't think you really believe that?). My "proof" that the set is countable is by pairing each binary integer (each path up the tree) with a corresponding unique decimal integer (and this can be done because each binary integer can be converted to a corresponding unique decimal integer)
     
  7. Mar 3, 2005 #6
    Any path with an infinite number of 1's in it does not correspond to an integer. Given any integer, the binary encoding of it will contain a finite number of 1's. That's why the diagonalization argument doesn't work on the integers; the "number" it constructs is not an integer.
     
  8. Mar 3, 2005 #7
    My post explicitly refers to : "every path up the tree corresponds to a unique infinite sequence of binary digits."

    I made the additional reference to the number of "nodes" simply out of passing interest (that the number of nodes is equal to the number of paths minus 1).

    If you find this confusing then please delete all reference to the number of nodes - the argument (based purely on the number of paths) stands.

    MF

    In reply to Hurkyl, I show below essentially the same (fallacious) argument in the same algebraic form that he suggested in his post, in order to demonstrate that the original argument must be absurd :

    Suppose f is a 1-1 mapping between the positive decimal integers and the positive binary integers from the infinite binary tree.

    Let dn be the function that returns the n-th digit of an infinite binary integer.

    Now, let's construct a new binary integer, r. For the n-th digit of r, select something different from dn(f(n)).

    Now, suppose f(m) = r. Then, the m-th digit of r must be dm(r) = dm(f(m)), but by construction that cannot be the m-th digit of r.

    The important thing to note is when I construct r, it really is a positive binary integer.

    Therefore, no such f exists.

    Thus, there is no 1-1 mapping between the positive decimal integers and the positive binary integers from the infinite binary tree.


    However, this conclusion is absurd (every binary integer CAN be mapped to a unuique decimal integer), therefore there must be something wrong with Cantor's argument.
     
  9. Mar 3, 2005 #8
    Can you tell me what is the binary coding of the decimal integer 9999...... ? (where ...... means "continue to infinity")

    You claim that the binary coding of any integer will always contain a finite number of 1's. I don't see how an infinite decimal integer can be coded to a finite binary integer?

    If an infinite number of binary 1's is not an integer, then what about any infinite string of binary digits? Would 1010101....... be an integer? If not, why not? If it is not an integer, then what is it (it exists, and it is certainly not a real number)?
     
  10. Mar 3, 2005 #9
    Any integer can be represented with a finite number of digits; this is pretty much by definition. While I'm sure you can construct a model where "infinite decimal integers" means something, this model would no longer be countable, so applying the diagonal argument to it wouldn't be very interesting.

    Cantor's argument relies upon the fact that every decimal expansion of the form [itex]0.d_1d_2d_3...[/itex] represents a real number. Not every decimal expansion of the form [itex]...d_3d_2d_1[/itex] is an integer, so you can't apply the same argument to the integers.
     
  11. Mar 3, 2005 #10
    I beg to differ. Two issues here :

    The online Webster dictionary defines an Integer as "A complete entity; a whole number, in contradistinction to a fraction or a mixed number." In trawling through many other dictionaries I cannot find any definition which says an integer cannot comprise an infinite number of digits.

    If we take your assertion "Any integer can be represented with a finite number of digits" at face value, then this means that there can be no concept of infinity at all when using integers; ie there can be no such thing as an infinite integer (no matter what base you define your integers in, binary, decimal or hexadecimal or whatever, an infinite integer MUST have an infinite number of digits.)

    This is tantamount to saying that no concept of infinity is countable, and I think most mathematicians would disagree with you there. The infinite set of integers is generally acknowledged by most mathematicians as being a countable set.

    Wrong. Cantor's argument relies upon the fact that the numbers he is working on have an infinite number of digits (it makes no difference whether these digits are to the left or right of the decimal point). My point is that an infinite string of integer digits is still an integer, and the argument therefore still works.

    If both 999999...... and 1111111..... are indeed not integers (as you claim), then what are they?
     
  12. Mar 3, 2005 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    They aren't integers. Go learn some maths before criticizing it, and that doesn't mean scanning Websters.

    A (positive) integer is a number which can obtained from adding 1 to itself a *finite* number of times.
    Positions to the left and right of the decimal point do matter.
    The strings you wrote out are not elements of the integers, nor R, with any reasonable interpretation of them.
    They are elements of a p-adic system, though.
     
  13. Mar 3, 2005 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    And that is exactly correct.
     
  14. Mar 3, 2005 #13

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Also, if you still think that Cantor's diagonal argument is flawed, try pointing out a flawed step.
     
  15. Mar 3, 2005 #14
    Quote:
    there can be no such thing as an infinite integer

    In 1874 Georg Cantor postulated that there is more than one level of infinity. The lowest level he called "countable infinity" and higher levels he called "uncountable infinities." The natural numbers are an example of a countably infinite set and the real numbers are supposed to be an example of an uncountably infinite set.

    The postulate of a countably infinite set of integers is well accepted in set theory and number theory.
     
  16. Mar 3, 2005 #15
    Hey, I wasn't the one who first referred to the "definition" of an integer.

    And in which maths bible does it specify an integer can be obtained in this way only a *finite* number of times?

    Not for the diagonal slash argument they don't. It works equally well for either, as long as the total string of digits is infinite.

    What you are arguing implies that the set of integers is not an infinite set. Suggest you go read about Cantor and his work on infinite sets before you go any further.
     
  17. Mar 3, 2005 #16
    I have done this already in Post #7 of this thread, using your own argument to show the absurdity of Cantor's method (if you like, a kind of reductio ad absurdum argument)

    What my post shows is that if Cantor's argument is used then we can show the number of binary integers is not equal to the number of decimal integers, which is absurd.

    The only real argument presented against this so far in this thread has been the suggestion that there is no such thing as an infinite integer, which I think you will find is incorrect.
     
  18. Mar 3, 2005 #17

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    And I think you'll find you are completely wrong. Integers in base 10 with the usual rules of presentation have only a finite number of non-zero digits. You should possibly hold back from telling some people who all have degrees or higher in mathematics or related areas things like that.
     
  19. Mar 3, 2005 #18
    Wrong.

    Suppose for the sake of argument that we accept your definition of integers as being allowed to have an infinite number of digits. Then we can define a subset of those which only have a finite number of non-zero digits. Call them the fintegers. Then firstly

    1) The fintegers are an infinite set. (Otherwise there would be a largest one. Can you tell me what it is?)

    2) Cantor's diagonal argument shows that the real numbers can't be put into 1 to 1 correspondence with the fintegers

    3) The fintegers are useful in everyday life, while your integers with an infinite number of digits aren't, so it would be the fintegers which appeared in dictionaries and the like.
     
  20. Mar 3, 2005 #19
    It is well established in set theory that each of the sets of natural numbers, integers and rational numbers is countably infinite.

    This means that each of these sets has infinite cardinality.

    This means that there are infinitely many natural numbers, integers and rational numbers.

    Any natural number or integer which is infinite must have an infinite number of digits.

    Or perhaps you can explain how an infinite integer can have a finite number of digits?
     
  21. Mar 3, 2005 #20

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    There is no such thing as an infinite integer. Spot the gap in your logic.....
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Absurdity of Cantor's Diagonal Slash
  1. Cantor's s(w)et (Replies: 5)

Loading...