6 ms·

You can count natural numbers. Elementary school children do it every day. Now, try to count the real numbers. What comes after 1?

by haneul 4y ago

nico 4y ago
> What comes after 1? Whatever I want. Why do you have to produce them in some predefined order? You could generate random real numbers, one at a time, and sort them as you add them to your set. When you stop, you will have a set of real numbers in order. If you want to know where a new one goes, you just generate it, add it to the set and sort it (or just add it in the proper position). And you will have a finite set of real numbers. If you never stop, you will keep forever generating real numbers, exactly the same as you would with natural numbers. The only thing that matters is whether you stop counting or not. If you stop counting, you get a finite set. If you don’t stop counting, you get an infinite one (but you’d never finish generating it). There is no way for a human to count for infinite time… so we can only speculate about that case. The only case that will ever occur in reality for us, is the finite case.
- LegionMammal978 4y ago
  > There is no way for a human to count for infinite time… so we can only speculate about that case. We can talk about whether or not a countably infinite sequence S contains a given element x. We iterate through each element s of S one-by-one. If x is contained in S, then eventually we will find an element s such that s = x. But if x is not contained in S, then we will keep iterating for all eternity. For all countably infinite sets, we can always produce such a sequence, where the iteration will eventually halt if and only if the element is contained in the set. But for the set of real numbers, no matter what sequence we choose, we will never ever find the diagonalized number in our sequence. That's why we call the set of real numbers uncountable. You dispute that we can't physically count through all of the infinite elements in the real world. But math has no problem talking about what would hypothetically happen if we were to try. It lets us prove ahead of time that certain events will eventually happen if we iterate long enough, and other events will never ever happen.
  - nico 4y ago
    > But for the set of real numbers, no matter what sequence we choose, we will never ever find the diagonalized number in our sequence. So then it’s only proving that if you choose the ordering ahead of time, you won’t be able to do it, because real numbers don’t have a predefined order. You can only order them as you produce them. If you re-sort after each iteration (or insert them in order), you can count as many real numbers as you want. In any case, for practical applications, you could never count anything infinite, at some point you’d run out of physical storage to keep the count. How many bits can be encoded in the universe? That will give the limit of what could ever be counted. And it’s not infinite.
    - hgsgm 4y ago
      We're talking about infinity, not practical considerations. > (or insert them in order), There is no order. You can't describe one, and it is proven that no order exists. > you can count as many real numbers as you want No, you can't count more than 0% of them, even in infinite steps.
      - nico 4y ago
        The order is arbitrary. What is the order of natural numbers? If you say they are in ascending order, that’s just the order in which you count them. The same way, I can just generate random real numbers, then define my set as in ascending order, and insert them in that order. Which is what we essentially do with natural numbers as well. Except that the order is a sort of mainstream standard and has been drilled into our minds since babies.
        LegionMammal978 4y ago
        > The same way, I can just generate random real numbers, then define my set as in ascending order, and insert them in that order. To perform the diagonalization, we can simply look at each real number that you randomly generate and add digits to the diagonalized number based on that order. It doesn't matter how much you shuffle them around afterward: the diagonalized number will still be different from all the generated numbers.
- haneul 4y ago
  You’re avoiding the difference. You can count (for example via generator function), the natural numbers, though you may never finish. Typically, people generate via numerical order, so 1, 2, 3, 4,… Now try doing that with the real numbers. You explicitly said you can sort them after. So, tell me, what comes immediately after 1, so I can attempt to convince you that it does not. In other words, that the real numbers only have local sorting, not global sorting, whereas the natural numbers have both.
  - roywiggins 4y ago
    It's not obvious how to order the rationals either, but there are of course loads of orderings that work, and it turns out that they can easily be put into correspondence with the naturals. Such orderings are not from lowest to highest, obviously, but they exist, and you might naturally assume there's one for the reals. The thing with the reals is that no orderings work, that's what Cantor's diagonalization proof does.
    - nico 4y ago
      As long as you have time and you keep counting, you can count anything. But eventually you will have to stop. Counting infinity is a contradiction, as you can never stop. Hence you can never get a final output. It doesn’t make sense that the cardinality of the set of natural numbers is some finite symbol (aleph-null). We can never truly know the cardinality of that set, because we can’t count to infinity. There’s an additional issue here. Which is: what does it mean to count? Because counting natural numbers usually means generating them in a certain order. The issue is that we cant come up with a way to produce reals in an orderly way one after the other. But we can always generate a random real number, then add it to a set in a position between a smaller and a bigger number. That way the set will always be in order, even if the number wasn’t produced right after a smaller number and before a bigger number. The order is essentially ad-hoc and varies as you generate the set. And if you kept going “for infinity” you would generate all the real numbers. But we can never count to infinity, not even for the natural numbers.
      - 4y ago
- roywiggins 4y ago
  The idea behind Cantor's diagonalization proof is that you can't find any way to assign "first", "second," "third", etc to the reals. The proof assumes that you can, and that you've already assigned every real number a unique natural number. It then derives a contradiction by proving that there must be reals that aren't in that ordering, without making any assumptions about the ordering. So any ordering has this problem and none of them work.
  - nico 4y ago
    The proof starts assuming you can count natural numbers, which you can’t. It’s impossible to have a known cardinality of an “infinite set”. The definition of set is “a collection of items”. You cannot “have” an infinite collection of items. You can have a method/function/formula/algorithm that generates as many items as you can in a certain amount of time, but by definition of infinity, you can never “count” an infinite number of elements. Hence, you can never know the cardinality of an infinite set (like the natural numbers). Once you think you can reduce something unknowable, to a symbol, you can prove anything. Like when proving 1=2 by dividing by 0. But then what’s the point?
    - roywiggins 4y ago
      Sure, that way lies intuitionism, which is a perfectly respectable (if not particularly popular) school of mathematics. > Once you think you can reduce something unknowable, to a symbol, you can prove anything. That doesn't follow. If ZFC is trivially inconsistent then someone would probably have noticed by now and proved P && !P for some P and brought it crashing down. That hasn't happened though, so even if you have strong aesthetic preferences against infinite sets being actually real, it seems like you can treat them as if they are real and produce a productive and not-obviously-inconsistent mathematical system. Most mathematicians don't really care if the naturals are actually infinite or just can be productively treated as if they are.
      - nico 4y ago
        > That doesn't follow. If ZFC is trivially inconsistent then someone would probably have noticed by now and proved P && !P for some P and brought it crashing down. Ahh, the classic economic argument, “that’s not a $100 bill on the sidewalk, because if it was, someone else would have picked it up already”. That’s a great way of accepting everything blindly to justify not questioning things. It also means you are using popularity as a measure of truth. It’s fine if mathematicians don’t care if naturals are “actually infinite”, but then what’s the point in reasoning about infinity through math if technically you are not really saying anything, but you’re going in circles around your own definitions instead?
- filoeleven 4y ago
  > Why do you have to produce them in some predefined order? That’s not counting. You were asked to count. If we are just going to make stuff up, let’s just use a different language instead of co-opting concepts from natural language.

You can count natural numbers. Elementary school children do it every day. Now, try to count the real numbers. What comes after 1?

by haneul 4y ago

You can count natural numbers. Elementary school children do it every day. Now, try to count the real numbers. What comes after 1?

nico 4y ago

> What comes after 1? Whatever I want. Why do you have to produce them in some predefined order? You could generate random real numbers, one at a time, and sort them as you add them to your set. When you stop, you will have a set of real numbers in order. If you want to know where a new one goes, you just generate it, add it to the set and sort it (or just add it in the proper position). And you will have a finite set of real numbers. If you never stop, you will keep forever generating real numbers, exactly the same as you would with natural numbers. The only thing that matters is whether you stop counting or not. If you stop counting, you get a finite set. If you don’t stop counting, you get an infinite one (but you’d never finish generating it). There is no way for a human to count for infinite time… so we can only speculate about that case. The only case that will ever occur in reality for us, is the finite case.

LegionMammal978 4y ago
> There is no way for a human to count for infinite time… so we can only speculate about that case. We can talk about whether or not a countably infinite sequence S contains a given element x. We iterate through each element s of S one-by-one. If x is contained in S, then eventually we will find an element s such that s = x. But if x is not contained in S, then we will keep iterating for all eternity. For all countably infinite sets, we can always produce such a sequence, where the iteration will eventually halt if and only if the element is contained in the set. But for the set of real numbers, no matter what sequence we choose, we will never ever find the diagonalized number in our sequence. That's why we call the set of real numbers uncountable. You dispute that we can't physically count through all of the infinite elements in the real world. But math has no problem talking about what would hypothetically happen if we were to try. It lets us prove ahead of time that certain events will eventually happen if we iterate long enough, and other events will never ever happen.
- nico 4y ago
  > But for the set of real numbers, no matter what sequence we choose, we will never ever find the diagonalized number in our sequence. So then it’s only proving that if you choose the ordering ahead of time, you won’t be able to do it, because real numbers don’t have a predefined order. You can only order them as you produce them. If you re-sort after each iteration (or insert them in order), you can count as many real numbers as you want. In any case, for practical applications, you could never count anything infinite, at some point you’d run out of physical storage to keep the count. How many bits can be encoded in the universe? That will give the limit of what could ever be counted. And it’s not infinite.
  - hgsgm 4y ago
    We're talking about infinity, not practical considerations. > (or insert them in order), There is no order. You can't describe one, and it is proven that no order exists. > you can count as many real numbers as you want No, you can't count more than 0% of them, even in infinite steps.
    - nico 4y ago
      The order is arbitrary. What is the order of natural numbers? If you say they are in ascending order, that’s just the order in which you count them. The same way, I can just generate random real numbers, then define my set as in ascending order, and insert them in that order. Which is what we essentially do with natural numbers as well. Except that the order is a sort of mainstream standard and has been drilled into our minds since babies.
      - LegionMammal978 4y ago
        > The same way, I can just generate random real numbers, then define my set as in ascending order, and insert them in that order. To perform the diagonalization, we can simply look at each real number that you randomly generate and add digits to the diagonalized number based on that order. It doesn't matter how much you shuffle them around afterward: the diagonalized number will still be different from all the generated numbers.
haneul 4y ago
You’re avoiding the difference. You can count (for example via generator function), the natural numbers, though you may never finish. Typically, people generate via numerical order, so 1, 2, 3, 4,… Now try doing that with the real numbers. You explicitly said you can sort them after. So, tell me, what comes immediately after 1, so I can attempt to convince you that it does not. In other words, that the real numbers only have local sorting, not global sorting, whereas the natural numbers have both.
- roywiggins 4y ago
  It's not obvious how to order the rationals either, but there are of course loads of orderings that work, and it turns out that they can easily be put into correspondence with the naturals. Such orderings are not from lowest to highest, obviously, but they exist, and you might naturally assume there's one for the reals. The thing with the reals is that no orderings work, that's what Cantor's diagonalization proof does.
  - nico 4y ago
    As long as you have time and you keep counting, you can count anything. But eventually you will have to stop. Counting infinity is a contradiction, as you can never stop. Hence you can never get a final output. It doesn’t make sense that the cardinality of the set of natural numbers is some finite symbol (aleph-null). We can never truly know the cardinality of that set, because we can’t count to infinity. There’s an additional issue here. Which is: what does it mean to count? Because counting natural numbers usually means generating them in a certain order. The issue is that we cant come up with a way to produce reals in an orderly way one after the other. But we can always generate a random real number, then add it to a set in a position between a smaller and a bigger number. That way the set will always be in order, even if the number wasn’t produced right after a smaller number and before a bigger number. The order is essentially ad-hoc and varies as you generate the set. And if you kept going “for infinity” you would generate all the real numbers. But we can never count to infinity, not even for the natural numbers.
    - 4y ago
roywiggins 4y ago
The idea behind Cantor's diagonalization proof is that you can't find any way to assign "first", "second," "third", etc to the reals. The proof assumes that you can, and that you've already assigned every real number a unique natural number. It then derives a contradiction by proving that there must be reals that aren't in that ordering, without making any assumptions about the ordering. So any ordering has this problem and none of them work.
- nico 4y ago
  The proof starts assuming you can count natural numbers, which you can’t. It’s impossible to have a known cardinality of an “infinite set”. The definition of set is “a collection of items”. You cannot “have” an infinite collection of items. You can have a method/function/formula/algorithm that generates as many items as you can in a certain amount of time, but by definition of infinity, you can never “count” an infinite number of elements. Hence, you can never know the cardinality of an infinite set (like the natural numbers). Once you think you can reduce something unknowable, to a symbol, you can prove anything. Like when proving 1=2 by dividing by 0. But then what’s the point?
  - roywiggins 4y ago
    Sure, that way lies intuitionism, which is a perfectly respectable (if not particularly popular) school of mathematics. > Once you think you can reduce something unknowable, to a symbol, you can prove anything. That doesn't follow. If ZFC is trivially inconsistent then someone would probably have noticed by now and proved P && !P for some P and brought it crashing down. That hasn't happened though, so even if you have strong aesthetic preferences against infinite sets being actually real, it seems like you can treat them as if they are real and produce a productive and not-obviously-inconsistent mathematical system. Most mathematicians don't really care if the naturals are actually infinite or just can be productively treated as if they are.
    - nico 4y ago
      > That doesn't follow. If ZFC is trivially inconsistent then someone would probably have noticed by now and proved P && !P for some P and brought it crashing down. Ahh, the classic economic argument, “that’s not a $100 bill on the sidewalk, because if it was, someone else would have picked it up already”. That’s a great way of accepting everything blindly to justify not questioning things. It also means you are using popularity as a measure of truth. It’s fine if mathematicians don’t care if naturals are “actually infinite”, but then what’s the point in reasoning about infinity through math if technically you are not really saying anything, but you’re going in circles around your own definitions instead?
filoeleven 4y ago
> Why do you have to produce them in some predefined order? That’s not counting. You were asked to count. If we are just going to make stuff up, let’s just use a different language instead of co-opting concepts from natural language.