1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Maybe all reals can be listed?

  1. Jul 2, 2017 #1
    Firstly, thanks to everyone who participated in my last thread. It helped a lot! This will be the only other topic I can think of posting in physics forums, because, honestly, I don't know very much.

    I remember sitting down one time and thinking I was quite brilliant when I started to make a binary tree; one trunk starting with all the expansions starting with 1, and another for all the expansions starting with zero. I was convinced I had found them all! Then someone pointed out to me that while every number was being slowly constructed, it kept changing places on the list, therefor, I wasn't actually, listing them, in fact, they are never listed. When I saw this, I realized, "oh, I guess I'm not so brilliant."

    One thing that struck me however was the diagonalization argument, and constructions upon the diagonalizations (such as adding 1 to each digit). It's certainly not a proof that all the reals are being counted, but it is a proof that diagonalization isn't a disproof. Why? Because you can just make a new list of all the diagonalizations for each regular list, and then the diagonalizations of those diagonalization lists. This disproves the diagonalization argument, but doesn't in itself prove that all the reals are being counted.

    From this, a new argument must be constructed to better understand what actually is a disproof that the reals cannot be listed.

    Lets say you have lists:

    List 1
    Diagonalizations of List 1
    Diagonalizations of diagonalizations of List 1


    List 2
    Diagonalizations of list 2
    Diagonalizations of diagonalizations of List 2

  2. jcsd
  3. Jul 2, 2017 #2


    User Avatar
    Science Advisor
    Gold Member
    2017 Award

    You are missing an important point in the diagonalization argument. A person who believes the reals can be listed should be able to present a list that is complete and has all the reals. He is not allowed to say "Oops, never mind, here is another list." The diagonalization argument shows that this is impossible, because the list is missing at least one real. Therefore, the reals can not be listed.
  4. Jul 2, 2017 #3


    User Avatar
    2017 Award

    Staff: Mentor

    The assumption of the diagonalization argument is, that you already have listed all numbers. If it's countable, you can do so. A second list isn't necessary.
  5. Jul 2, 2017 #4


    Staff: Mentor

    I'm not sure you understand what Cantor's diagonal argument is doing.
    It starts by assuming that it is possible to list all of the real numbers (in binary or base-2). He then constructs a number that isn't in the list, thereby contradicting the earlier assumption that the list contains all possible numbers. The conclusion is that the list did not contain all possible real numbers.

    This is a proof by contradiction, a standard technique used in mathematical arguments.

    You are not "disproving the diagonalization argument."

  6. Jul 2, 2017 #5
    It's not obvious to me that just because you can't complete a single list, that an infinite number of lists won't suffice.

    Here's my best attempt at an inferential proof for the reals in one list:

    My technique for sequencing the rationals.... I call it the mirroring technique, because i realized that if you mirror all of the natural numbers you have all of the decimals.

    The way it works is that the first ten numbers are counted just as themselves and their negatives:

    0,1, -1,2, -2,3, -3,4, -4,5, -5,6, -6,7, -7,8, -8,9, -9

    Then after that you count 10 and then the next number is the mirror of 10, which is 01 and then you move the decimal point in once to get the 12th number being 0.1, then the thirteenth number (not counting the negatives which are numbered every other) is 0.(1 repeating). These steps continue until you reach three digit numbers and higher. Once you count 100, you then count the next number as 0.01, then 0.0(1 repeating) then 0.(01 repeating), then you count 101 and it's mirror. If you keep marching in the decimal point when the number that's about to be mirrored ends in zero it causes infinite overlap. The number 100 ends in a zero, so after you mirror it you only march the decimal in for one place to the right, if you march it two places to the right, you end up with 00.1, which is the same mirror that you get when the number 10 is mirrored, and will occur an infinite number of times as the zeros expand and you keep marching in the decimal point (which will give you infinite overlap as the sequence expands).

    However, if the number doesn't end in a zero, you keep marching in the decimal point, say the number 102. The next number is mirroring it, so it's 2.01, then you do the repeating decimals by next counting 2.0(1 repeating) and then 2.(01 repeating), then you march the decimal point in once more to get 20.1, and then you do the repeating decimals by having 20.(1 repeating). (If you march the decimal in one more time, you get 201, and have infinite overlap as well.) Then you count the number 103 and then mirror it and do this forever.

    ...312111019876543 : 34567891011121...
    ...121110198765432 : 23456789101112...
    ...211101987654321 : 12345678910111...
    ...111019876543210 : 01234567891011...
    ...111019876543210 : 012345678910111
    ...211101987654321 : 123456789101112...
    ...121110198765432 : 234567891011121...
    ...312111019876543 : 345678910111213…

    As my mirroring technique for counting the rational numbers expands, you interpolate it with this sequence for every digit (the grid above)…

    You slowly spiral out from the middle of this infinite sequence grid! (one axis is negatives and the perpendicular axis is decimal points)

    As you spiral out, you list 8 consecutive directionality's, up, down, right, left and all the diagonals… then list another atonal number, then go back to the reals grid, spiral out again, list all 8 directionality's, then list another rational etc…

    The proof looks inferential, but I'm not 100% sure. This technique obviously uses all diagonals.
  7. Jul 2, 2017 #6


    Staff: Mentor

    How about this:
    List 1 - all of the real numbers in the interval [0, 1]
    List 2 - all of the real numbers in the interval [1, 2]
    List N: all of the real numbers in the interval [N - 1, N]

    For each of the infinite number of lists shown here, the assumption is that we have listed all possible real numbers in that specific interval.

    It can be shown, using Cantor's diagonal argument, that one more number can be constructed in each of the lists above. Therefore, it is not possible to list all of the real numbers in any of the intervals, which means it is not possible to list all of the real numbers.
  8. Jul 2, 2017 #7
    That doesn't address the point I made or the question I asked… it's just reasserting what you already said.

    Let's say you have [N-1, N], and Cantor shows that each list has an infinite number of uncounted diagonals for each list… well, then make another list for each list that always does the diagonals, and the diagonals of those diagonals and the diagonals of those diagonals. Cantor no longer has an argument, and neither do you.
  9. Jul 2, 2017 #8
    Ever since I figured out the diagonal argument isn't a disproof, I started to analyze certain list constructions and came up with this:

    I use a technique that I called 1 dimensional flooding to show that all of the reals cannot be counted in one list with one dimension, which is differnt than Cantors diagonalization argument.

    use the lists..



    To do one dimensional flooding, you simply add an infinite list to each place in the previous infinite list...


    When the list converges at infinity, there is no way to begin counting...


    Because you never pass the zero's.
  10. Jul 2, 2017 #9


    User Avatar
    Science Advisor
    Gold Member

    But can you show these listings are countably infinite, i.e., that you can do a listing, or a matching with the naturals?
  11. Jul 2, 2017 #10


    Staff: Mentor

    My quote above directly addresses the statement you made that I quote at the top of this post. Please take the time to carefully read what I and other people responding to your posts are writing.

    I'm showing an infinite number of lists, none of which can possibly contain all the real numbers in the given interval.

    Your thinking is incorrect. It most certainly disproves the original assumption that it is possible to list all of the real numbers.

    Why do you believe that the diagonal argument is incorrect?
  12. Jul 2, 2017 #11
    They aren't naturals. The new lists have to be something like 1, 1.1, 1.2, 1.3… etc…

    I showed you my single list attempt at an inferential proof. I posted it about 3 posts ago. It's much more complex than the inferential proof of the natural numbers (1,2,3,4,5,6,7,8…) where you just add 1 each time. When you have issues with dimensional flooding, you need a separator, and a new operator, or you need scattering …. scattering is the distinction between an ordered and well ordered (not scattered, but sequential) set.
  13. Jul 2, 2017 #12

    Mark, your lists are still on a single axis. It's the difference between night and day. You actually didn't address what I said at all.

    Besides, if you can make a list of (n -1, n), you wouldn't even need an infinite number of lists on a single axis in the first place. You're confusing yourself about what you're trying to imply or argue, relative to what I'm making, from my perspective, exceedingly clear.
  14. Jul 2, 2017 #13


    Staff: Mentor

    All of the numbers you list here are rational numbers. You aren't generating irrational numbers, as far as I can see.
    Why do you believe that the diagonal argument is incorrect?

    Cantor's argument has nothing to do with natural numbers.
    This is nonsense.
  15. Jul 2, 2017 #14
    Mark, wow, you're getting mad.

    The diagonal argument is false because for every list you can make…

    List 1:

    List 2:

    List 3:


    You can use another axis to include EVERY diagonal

    List 1.1, List 1.2, List 1.3

    List 2.1, List 2.2, List 2.3


    Suddenly, the diagonal argument doesn't exist anymore *poof* it's gone, done, over, meaningless.

    My comment about inferential proof (comparing it to the most obvious one we use - natural numbers, of which there are an infinite number of which nobody will ever see), and explanation of how to order sets with infinities… apparently is nonsense to you. I think this area of mathematics is clouding your judgement with anger. I'm justing to be exceedingly clear. You're not asking questions or restating things to imply you even understand - which isn't communication. When I was adding 0.1, 0.01, 0.001 in the last thread to get 0.111..., you understood the error I was making and pointed out that one is subtraction and the other is division. I was glad you could clear that up, the error in my head. You have yet to even hint that you even understand what I'm saying in this thread, in order to correct it.

    correction: One is subtraction, the other is addition (instead of division)
  16. Jul 2, 2017 #15


    User Avatar
    2017 Award

    Staff: Mentor

    If you have a countable list of countable lists, you can combine them to a single countable list - this is done to show that the set of rational numbers is countable, for example. If you cannot make a single countable list of real numbers (and you cannot), then adding list 2, list 3 and so on doesn't help.

    An uncountable set of lists works, of course. Just put every real number into its own list, and you are done. But that is trivial.
    It is correct, you just don't understand it.

    It is like trying to argue that 1+1=3. It is not. We can help you understand why it is not, but you first have to understand that it is not true.
  17. Jul 2, 2017 #16
    Ok. I don't know the proof, for why adding a different operator to expand the axis implies that this means the numbers have to be countable on a single axis… but I'll just assume it for now. What's wrong with my post #5 on this thread? Can you find a number not on that list? It's a single axis list.
  18. Jul 2, 2017 #17


    User Avatar
    Science Advisor
    Gold Member
    2017 Award

    There is no advantage to a countable number of countable lists, since they can all be easily combined into one list. So let's skip to the end and say that you have already combined your countably infinite lists into one list, L. Now you can not say "Oops, never mind about L. Here is a different list." You either can combine into one final list L, or they are not listable. Now apply the diagonalization argument to that list L.
  19. Jul 2, 2017 #18
    I'll add something half in your favor (this is a chain - post, so I also posted above)

    "Direct Diagonalization" (straight line as a diagonal) can be accounted for. However, take the digits for pi, and make a diagonalization out of those digits as you slowly diagonalize out --- the diagonal will no longer be a straight line, and there are an infinite number of combinations as there are an infinite number of different sequences you can use for diagonalization. When I try to solve this problem, it really hurts my head!
  20. Jul 2, 2017 #19


    User Avatar
    2017 Award

    Staff: Mentor

    Forget about the axis.

    If ##\mathbb{R}## was countable, then what does this mean?
    It means, we can imagine a list of all real numbers, numbered as ##1.\, , \,2.\, , \,3.\, , \,\ldots##
    So far we only used the definition of countable. We do not care which order these numbers have, whether they are positive or negative, whether they are increasing, decreasing or wildly mixed, or whether they are written as decimals, as binary digits or whatever. We only have to imagine to have them written in any system.
    Now the diagonal argument shows, that there is a number which cannot be part of the list. It is not in there.
    But we have written all of them, so this number has to be in the list.
    And this is a contradiction: the number cannot be part of the list and simultaneously not part of the list.
    This means, somewhere in our conclusions, must have been a wrong statement.
    But beside the definition of countablility and the existence of some representation of numbers, we have only used, that ##\mathbb{R}## is countable. So the only possibility for something wrong, is the If at the very beginning.
  21. Jul 2, 2017 #20
    My list in post #5 of this thread can't even do diagonals… so Cantors argument can't be used on it anyways.
  22. Jul 2, 2017 #21


    Staff: Mentor


    You have a fundamental misunderstanding of how mathematical proofs work.

    Cantor's argument shows that the real numbers are uncountable; that is, they can't all be listed.
    Before anyone will take your convoluted argument seriously, you first have to show that there is a flaw in Cantor's argument. So far, you have not done so. Coming up with extra diagonals, extra axes, etc. doesn't convince any of us that Cantor was wrong. If you want to prove that 1 + 1 = 3 (as in mfb's example), you have to first show the statement 1 + 1 = 2 is wrong.
    Last edited: Jul 2, 2017
  23. Jul 2, 2017 #22


    User Avatar
    Science Advisor
    Gold Member
    2017 Award

    Any list of real numbers can be rewritten or re-represented, element by element, without changing the order of the real numbers, in a form where the diagonalization argument can be applied.
  24. Jul 2, 2017 #23
    Whoa! You just gave me a big insight there. I think I might be able to understand this now. I have two questions about my list in post #5.

    Is it a closed list (meaning: are the diagonals on the list? I read about closed lists on the Cantor Diagonal Argument wikipedia page), and if not…

    Oh wait whoa! I need to do more work!! I don't know how to make another iteration of my list from a possible list that comes from it.

    This has been huge help! Thank you!

    I'm using the expanding zeroes that Mark taught me about to make my list diagonalizationable. Which means, I can actually falsify my list in post #5, which means you may all prove correct.
  25. Jul 2, 2017 #24


    Staff: Mentor

    I would assume that "closed list" means that it has a first number and a last number.
    As far as whether the diagonals are on the list (in post #5), I don't know, and frankly don't care. At the risk of sounding like a broken record, unless you give a cogent argument about why Cantor's argument is wrong, I'm not going to try to untangle your complicated scheme.
    I couldn't find either "closed" or "list" on the wiki page (https://en.wikipedia.org/wiki/Cantor's_diagonal_argument)
    You can't "falsify a list." You can contradict an assumption, which is at the heart of why Cantor's proof works.
  26. Jul 2, 2017 #25
    Oh, I'll give you a simple closed list, they get more complicated though…

    1.) 111111111…
    2.) 111111111…
    3.) 111111111…

    Etc… That's a closed list.

    I remember a huge section on closed lists back when I read it - I guess they took it down.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook