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

I Regarding Cantor's diagonal proof.

  1. Feb 28, 2017 #1
    I am very open minded and I would fully trust in Cantor's diagonal proof yet this question is the one that keeps holding me back. My question is the following:

    In any given infinite set, there exist a certain cardinality within that set, this cardinality can be holded as a list. When you change the value of the diagonal within that list, you obtain a new number that is not in infinity, here is my problem, now that if inf + 1 = infinity, why would doing that to the diagonal be any different from simply adding or subtracting from infinity.

    Perhaps the new number has a value different from the list yet if adding or subtracting from an infinite sequence gives you infinity regardless, why would it be any different doing it to a certain number within that sequence, the way I see it, the new number is not outside of infinity, yet is instead outside of the cardinality of an infinite sequence therefore isn't really greater than infinity, just different from infinity and just by cardinality, not naturally.
     
  2. jcsd
  3. Feb 28, 2017 #2

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    It proves that there can be no counting of the real numbers. What is more, it is clear from the proof that you can make up many more missing numbers than there are on the list. So the "infinity" of the real numbers (##\aleph##1) is a level above the infinity of the counting numbers (##\aleph##0) . So ##\aleph##1 > ##\aleph##0.


     
  4. Feb 28, 2017 #3

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    In he standard proof, we assume the entire set can be written as an infinite list.
    The diagonal is not changed. An element of the set is constructed by taking a copy of the diagonal and modifying every term.
    It is not in the list.
    Nothing is done to the diagonal. It doesn't change.

    The significance of the newly constructed element is that we assumed the list contained all the elements, but this new element proves it did not.
     
  5. Feb 28, 2017 #4
    Your question contains a lot of statements that make no sense.\
    Do you mean, every infinite set has a subset with a certain cardinality?
    Do you mean this subset is countable, So you can make a list of this subset? (by producing a 1-1 correspondence with the integers)
    Do you mean: when you change the values of of all the numbers on the diagonal?
    This also means you're looking at a set of numbers with an unlimited decimal expansion.
    Probably easier to name the real numbers up front.
    I have no idea what that means. The diagonal will be a number that is not on the list.
    The diagonal is not infinity, but a real number, so none of this makes sense.
    Most versions of the proof produce a number between 0 and 1. Changing all the numbers on the diagonal is nothing like adding 1 to the diagonal.
     
  6. Feb 28, 2017 #5
    The diagonal is a real number that tends to infinity, that's why I assumed it would be treated the same as infinity.
    Yes when I was talking about the cardinality I was refering to 1-1 correspondance.
    The diagonal is not changed, instead it was copied and changed, therefore it was changed.

    My point was, if the list is an infinite sequence of numbers and we add 1 to the diagonal, then wouldn't the sequence reach that 1 we added? because the way I see it, it's the same thing as inf + 1 = infinity.

    "The diagonal is not infinity, but a real number, so none of this makes sense.
    Most versions of the proof produce a number between 0 and 1. Changing all the numbers on the diagonal is nothing like adding 1 to the diagonal."

    The diagonal is a real number with tendance to infinity, why would it be different from an infinite number or an infinite sequence? And when I say add 1 to the diagonal i'm only referring to the change of the values in that diagonal.

    And the diagonal being a real number or not doesn't matter in my point.
    If we say inf + 1 = infinity, why would adding 1 to the diagonal of an infinite list not equal infinity, in other words, why would the new number be any different from the meaning of infinity on the list, the new number looks different from the ones on the list, yet only because of 1-1 correspondance, which is the order of the list, why would it be any different from the meaning of infinity and why would it be greater than infinity? i'm suggesting that the infinity on the list is absolute and that the new number is different from the numbers on the list, yet just because of 1 - 1 correspondance not because it's any different from an infinite number.
     
  7. Feb 28, 2017 #6
    When I was in middle school I didn't accept the Cantor diagonal proof because I thought math had to be grounded in reality. Numbers only existed because they referred to actual measurements we could make in the universe. The problem I had with Cantor's proof is that it claims that the number constructed by taking the diagonal entries and modifying each digit is different from every other number. But as you go down the list, you find that the constructed number might differ by smaller and smaller amounts from a number on the list. And extending to infinity, we are claiming that the number only disagrees with a number on the list by an infinitesimal amount. We already claim that 0.9999... = 1.0000, so why are we saying that two numbers that disagree by an infinitesimal amount are different numbers? We can't physically measure the difference.

    Well, as I got older, I realized that math is not just a tool for describing reality, but it is a creature of our mind, which happens to be very useful. In math we can talk about infinities and such, which we can't really measure. As long as it's consistent, it's all fine.

    Anyways, it's not mathematically valid to say inf + 1 = infinity. And it's not a problem of just a single number that we can't match up into a 1-1 correspondence. Any single number we can easily accommodate into the list by shifting the entries down one. The problem is that no matter how many numbers we shift in, there are always more numbers we haven't added yet.
     
  8. Feb 28, 2017 #7

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    But the original assumption was that the list included ALL of the reals. You are thinking that there is only 1 new one to add. (In fact there are many more omitted from the list than on it, since for every diagonal digit, there are 9 other digits that could be there, making numbers that were omitted.) Saying that it was not in the original list violates the original assumption. So the reals can not be counted in a list and there are more of them than there are natural numbers. The "infinity" of the reals ( ##\aleph##1 ) is greater than the "infinity" of the natural numbers ( ##\aleph##0 ).
     
    Last edited: Feb 28, 2017
  9. Feb 28, 2017 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No, you seem to have misunderstood the process completely. Consider this example.
    Suppose our infinite list happens to look like thsi:
    .2
    .32
    .312
    .3142
    .31412
    .314152
    .3141592
    .....
    (I think you can see how it goes.)
    Now we construct a real number by copying the diagonal:
    .222222222....
    then adding 1 to each digit:
    .3333333333....
    I.e. 1/3. This number is a perfectly good real number, not infinite, but definitely not in the list.
     
  10. Feb 28, 2017 #9

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    But the number created by the diagonalization method is significantly different from every number on the list. There is nothing infinitesimal about each difference. The difference from each number on the list is "grounded in reality". All you are saying is that it is possible to have a countable set of numbers that is dense in the real line. The rational numbers are such a set. That is not a weakness in the proof and it does not prevent it from being grounded in reality.
     
  11. Feb 28, 2017 #10
    I think there is a point in the following sense (not a significant one but it came to my mind while reading this thread):
    Suppose the number constructed by taking elements from the diagonal was:
    0.1999999....

    If our rule for changing digits was:
    0 to 1
    1 to 2
    2 to 3
    ........
    9 to 0

    then the above number would be changed to:
    0.200000....

    But that is again equal to the previous number (without changing digits). And hence this number may very well be on the original list.

    Of course it could easily be shown that this doesn't affect the actual result. Or alternatively we could just choose a slightly different rule for altering digits.
     
  12. Feb 28, 2017 #11

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    Since there are 9 available choices for each digit of the generated number, it is easy to avoid any problem pattern.
     
  13. Feb 28, 2017 #12
    Yes you are right. Even if one didn't do that it would be very easy to show that this is not an issue as far as countability or uncountability related issues are concerned.

    Certainly this isn't the source of OP's confusion (which might just be a matter of seeing enough concrete exampes).
     
  14. Feb 28, 2017 #13
    Correct me if i'm wrong, but what I understood with your arguments is that the diagonal has a next number, the next number has 9 different possibilites or 10 if we include zero, no matter the list, the number that goes after that number can't fullfill those 9 possibilites at the same time. Yet I still don't know why this would mean it's greater than infinity and not simply a different kind of infinity. Now that if we change the diagonal by adding 2 to each number, it would still only fullfill one possibility, 1/9.
     
  15. Feb 28, 2017 #14

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    What is "it" here?
     
  16. Feb 28, 2017 #15
    Pehaps infinity doesn't have a value whatsoever, yet if that's the case I don't know why omega would play in the game before ever reaching absolute infinity without it being an assumption of the order of infinity.

    If there exist 9 different possibilites after a number in the sequence, uncountable would start at saying there exist 2 out of 9 possibilites or 3 out of 9 possibilites at the same time, and you could even say it's possible to have 9/9 possibilites even though it's impossible to actually see something like that, but this only makes me believe in uncountable numbers and absolute infinity, yet not in omega, I see omega and omega + 1 as an assumption of the order of absolute infinity, why isn't it?
     
  17. Feb 28, 2017 #16

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    You still have not grasped the reductio ad absurdum nature of the proof. We are not adding one or 2 or 9 entries to the list to make a longer one.

    1. If the reals are countable then the reals between 0 and 1 can be arranged in a list. That is, there exists a list which contains every real in that range.
    2. Suppose we had such a list. We construct from it a real in the range which is missing from the list.
    3. Therefore no such list can exist.
     
    Last edited: Feb 28, 2017
  18. Feb 28, 2017 #17

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    Exactly. It is a different kind of infinity. Countably infinite, like the natural numbers is indicated by ##\aleph##0. The larger infinity of the real numbers is indicated by ##\aleph##1. There are larger and larger types of infinity, ##\aleph##2, ##\aleph##3, ... etc. There is no limit.
    There is no reason to stick to a pattern like adding 2. You can pick any number you like that is not the current diagonal digit of the listed number. If that diagonal digit is 3, then you can generate 9 example numbers by putting 0,1,2,4,5,6,7,8,9 there. If the next diagonal number is 8, pick any of 0,1,2,3,4,5,6,7,9. You don't have to follow any pattern. There are so many real numbers that are not in the list that they are MUCH more numerous than the numbers in the list.
     
  19. Feb 28, 2017 #18
    So basically you can make an infinite amount of different lists of reals, and you can always get a real which wouldn't be on the list, which is aleph null, and therefore it's sensical to think that all the aleph nulls could be arranged in an order by using a graph, reasonable!
    But hang on a second, omega is basically a reprentation of the order of uncountable sets, why does it come in play before reaching absolute infinity without simply being an assumption of the order of infinity, I can't seem to find the true purpose of ordinals. And also, aleph null represents the uncountable real numers, yet regardless of that, the order of aleph null is made still made by only 1/10 possibilites of the different numbers you could have chosen, what about 2/10 numbers you could choose at the same time, it's impossible to see it or represent it, but wouldn't it still exist?
     
  20. Mar 4, 2017 #19
    I have a related question which I posted here http://math.stackexchange.com/quest...f-infinite-sets-and-infinite-sets-as-whole-ob . Since it looks like that isn't going to get much attention, I figure I might as well contribute to this thread and ask your advice since my question is highly related.

    My difficulty with feeling certain about the diagnonalization proof, explained in more detail on math exchange, is that picking an element s that differs at one digit by all of the elements in an infinite set seams like an undoable thing, there is no base case. We can write a rule for trying that seams like it would work if applied without bound, but actually completing the action (it needs to be applied infinitely)? Then selecting s seams a little bit like saying let n' be the largest natural number (which we know doesn't exist).
     
  21. Mar 4, 2017 #20

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    There is no difficulty as long as the number is defined by a finite rule. You are happy with the existence of a number we call pi. If you need to know what any given digit is, you have a rule for finding it that will terminate in a finite number of steps.
    Moreover, we have theorems that show the rule converges, and by the axioms for the reals it converges to a real number. The same is not true of the "largest natural number" analogy.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Regarding Cantor's diagonal proof.
Loading...