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

On Real Enumeration

  1. Nov 10, 2012 #1
    Hey, I've been reading up on Cantor's work recently, and was wondering if the following series can be considered an enumeration for the reals between 0 and 1 in binary:

    [0] => 0.00000...
    [1] => 0.10000...
    [2] => 0.01000...
    [3] => 0.11000...
    [4] => 0.00100...
    [5] => 0.10100...
    [6] => 0.01100...
    [7] => 0.11100...
    [8] => 0.00010...
    [9] => 0.10010...
    [10] => 0.01010...
    [11] => 0.11010...
    [12] => 0.00110...
    [13] => 0.10110...
    [14] => 0.01110...
    [15] => 0.11110...

    If not then can you please explain why this isn't an accurate enumeration? Thank You!
  2. jcsd
  3. Nov 10, 2012 #2
    Cantor clearly shows why in his diagonalization argument. I can easily create an infinite length binary string that isn't on your list.
  4. Nov 10, 2012 #3
    I don't get it, the list I made is defined to go through every possible combination of 0's and 1's for a binary expansion of any number of digits. So how could there be a binary string not in the set of every possible binary strings?
  5. Nov 10, 2012 #4
    Again, the diagonalization argument provides an explicit procedure for constructing such a string.

    The first digit in your first string is zero, so the first digit in my string is one.
    The second digit in your second string is one, so the second digit in my string is zero
    And so on...

    My string differs from every string on your list. Your enumeration fails.
  6. Nov 10, 2012 #5
    Which number corresponds to 0.101010101010101... ??
  7. Nov 10, 2012 #6
    Could you please elaborate? I have just a basic understanding of these ideas, I admit, but I see n=1,5,9,13, which all start with the example you gave. And if you continued with your list, I can keep giving you n's which start with the sequence you give.
  8. Nov 10, 2012 #7
    Yes, you can find a number which corresponds with the first few values of my sequence. But the point is, you can never give a number which corresponds with my entire sequence.

    I'm sure you can find numbers which correspond to
    and so on.

    But can you find a number corresponding with the entire (infinite) sequence 0.101010101010101... ?? That's what Cantor's theorem is about.
  9. Nov 10, 2012 #8
    While that is true, the point of the construction is that even though you can add our new constructed number to your list, we can then immediately construct another a number that is not in your infinite list. The fact that there is always such a number available, no matter how many numbers you add to your list is the point of the diagonalization argument. We explicitly construct a number that is designed to not be equal to any individual number in a given list, whether that list is finite or infinite.
  10. Nov 10, 2012 #9
    Oh ok, I get that. In that case, I see this now as more of a logical problem: yes, I can't come up with a number corresponding with your binary expansion, but at the same time, can't I be sure that, logically, it must exist? After all, each binary expansion in my list in my OP was defined to infinity so is a real, and each n is associated with exactly one of the unique binary expansions. So while I don't have a formulaic way of giving you an n for a particular binary expansion, why can't I apply logic that it must be in the set based on the definition and have a unique n associated with it?
    Last edited: Nov 10, 2012
  11. Nov 10, 2012 #10
    Every number on your list has only finitely many nonzero decimals. So any number with infinite nonzero decimals won't be on the list. That proves that the number is not on the list.
  12. Nov 10, 2012 #11
    Your definition says no such thing.

    That's irrelevant. The point is that your list is not exhaustive. You have an injective function to the reals; but that's not what an enumeration is.
  13. Nov 10, 2012 #12


    User Avatar
    Science Advisor
    Gold Member
    2017 Award

    you list only has numbers with finitely many zeros
  14. Nov 10, 2012 #13
    Thank you all for your responses! It hit me that I had read this idea of finitely many nonzero digits before so I think I understand what you are saying now.

    I'm curious though, being outside of academia myself, to what extent are Cantor's ideas criticized? Specifically, I'm speaking about the idea that a one-to-one correspondence with the naturals is enough to sensibly conclude that the two sets are of equal cardinality even though the members of one set, in the case of the even numbers for example, might be twice in measure of the members of the other set. And I'm asking this in context to the fact that we are doing the counting without reference to a measurable interval. (Sorry for the non-standard terminology).

    I mean, if I generally want to know how many of two marker types there are on an infinitely long road, and you give me that marker type A is spaced X units apart, and marker type B is spaced Y units apart, I couldn't possibly give you a sensible answer without being given some interval to divide the markers into.

    What I don't get is that if Cantor himself developed the measure of the cardinality of infinite sets, namely aleph-0, then why not use alepth-0 as an interval measure into which one puts members of two different sets in order to determine their cardinality. In this case, I imagine that one would get a different result for the naturals and the even naturals.
  15. Nov 10, 2012 #14
    It is not. Every serious mathematician has accepted Cantor's ideas as true. The only criticism comes from laymen and philosophers.
    That said: there are of course attempts to make other axiom systems. Other axioms might mean that Cantor's theorems become false. But that doesn't mean that anybody doubts the truth of Cantor's theorems as they are only true in the given axiom system.

    That sets are of equal cardinality if there exists a one-to-one correspondence between them is a definition. We have defined it to be true. Another definition might give another answer, but this definition has turned out to be quite fruitful.
    Furthermore, when you say that the even numbers are "twice in measure", then you first need to define measure.

    Yeah, I don't really get this. Could you explain?

    Well, infinite roads and infinite markers don't exist. Don't make the mistake that Cantor's infinities actually say something about actual reality. They are purely abstract mathematical ideas. They are useful in describing mathematics. But they don't necessarily say anything about reality.

    Sorry. Could you expand?? I'm not understanding what you're trying to say.

    Are you talking about the distance between different natural numbers?? And you're saying that the distance between the even numbers is bigger than the distance between natural numbers?? That makes sense and it is true. But Cantor doesn't talk about distances. A distance is another type of structure. Cantor just talks about sets and nothing else. If you want to talk about distances, then you shouldn't go to Cantor but to the theory of topology or metric spaces.
  16. Nov 11, 2012 #15
    Right, I did read that his continuum hypothesis is neither provable nor disprovable in ZFC, so is it then the case that criticism can only be made on grounds of an axiomatic system? And have there been attempts to develop an axiom system with the specific intent of dealing with the intuitive (at least for me) inconsistencies that result from saying the set of naturals and even naturals have the same cardinality, for example (while recognizing, of course, that this is completely consistent in ZFC)?

    I understand the part about it being a definition, but like I said, it doesn't make intuitive sense to me as I am not convinced that infinities of different sizes, as Cantor showed them to exist, should have different properties than numbers of different sizes. Again, I realize that infinities have different properties then natural numbers due to definitions in ZFC. So I guess what I'm really criticizing is the ZFC definition of infinity? And by twice the measure, I really just meant, in this case, 2x, as opposed to x.

    I just mean, that if you ask me how many markers spaced X units apart are there, I would require from you a clearly measured interval to know how many such markers fit inside that interval. And by measured, I don't necessarily mean a countable number like 1 or 2, it could also be 1*aleph-0 or 2*aleph-0. Otherwise, the vaguely defined infinity simply absorbs all attempts to put a discreet measure on it.

    I don't need Cantor's infinities to say anything about reality, but I do need them to say something intuitively sensible. And the idea that there are as many naturals as even naturals is not intuitive to me since, if I'm understanding correctly, half as many even naturals would fit in an interval aleph-0 in length as the naturals.

    Yes, I suppose I am speaking about distances, but I can't see how we can try and make definitions of infinities without reference to the distance between the elements of infinite sets. Again, I can see that this is perfectly consistent with the mainstream axiom system of ZFC, but it is unintuitive non-the-less. I will look into areas of study you mentioned, thank you!
  17. Nov 12, 2012 #16


    User Avatar
    Science Advisor

    You don't have to develop new axioms to rescue this particular intuition. You just need a new definition.

    Define "asymptotic density" for a subset S of the naturals by dividing (how many elements of S are less than n) by n and taking the limit as n increases without bound.

    The even naturals have an "asymptotic density" of 0.5 If you choose to intuit this as "half of all naturals are even", we can't stop you.

    A problem is that this notion of "how many" only works for subsets of the natural numbers and does not work for all subsets of the naturals.

    For instance: { n : 2^k <= n < 2^k+1 for some even k } does not have an asymptotic density. This set is { 1, 4, 5, 6, 7, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 64, ... }. Intuitively, the density of this subset of the naturals ranges between 1/3 and 2/3 depending on how far out you count.
  18. Nov 12, 2012 #17
    Oh sorry, I didn't mean that, it would of course be silly to make a new axiom system from scratch lol. I just meant how the inclusion of the axiom of choice changes the title from ZF to ZFC.

    You had me thinking you made this up on the spot for a second there :smile: But yeah, this is along the lines of what I was thinking.

    Which makes complete intuitive sense, doesn't it? For me, the bigger problem here is to assume that the density should converge as it goes to infinity (I hope I'm using 'converge' correctly here). After all, if Cantor has established that different sized infinities exist, then it matters which infinity we're talking about doesn't it? Just as the asymptotic density of n fluctuates as you go to higher values of n, it should equally fluctuate as n goes to higher values of infinity, no? It is at least intuitive, if you ask me.
  19. Nov 12, 2012 #18


    User Avatar
    Science Advisor

    Density is not guaranteed to converge. Which means that asymptotic density is not guaranteed to exist.

    Assuming that density will converge does not make it so. Adding an axiom to make it so won't help -- that'll just give you an inconsistent formal system.

    This bit is not clear.

    The asymptotic density of n does not exist -- n is not defined.
    The asymptotic density of S does exist. But it does not fluctuate.
    The density of S intersect {1 .. n} could be defined as a function of n. That could be seen as fluctuating. Because it fluctuates it would not converge.

    Perhaps you are saying that an intuitively satisfying notion of density should exist for any subset and should have a numeric value that converges as you "count through" the parent set, regardless of how you count through. I fear that such a metric is impossible to find.
  20. Nov 12, 2012 #19
    Some misunderstanding here I suspect. If I'm following right, I was saying the same thing. I said that it is just this idea, that we should assume that density should converge, that I have a problem with. And I cited Cantor's different infinities as examples for why it need not converge as there are different 'sized' infinities.

    Though I generally follow that my usage of terms was loose, I won't pretend to be fully competent in the mathematics here (though I am working on it), so I'll keep this short for now.

    Again I am, I think, saying precisely the opposite: the numeric value of the asymptotic density need not converge if we go to infinity because the the standard infinity has no measure assigned to it, rather it is by my understanding a process of unbounded growth. So if you allow unbounded growth to a set S that has fluctuating densities as you count out to infinity, you will of course not converge to any particular asymptotic density. On the other hand, if you speak of a particular infinity with a defined measure (i.e. aleph-0, aleph-1, etc.), then you might then possess the tools needed to converge to a particular asymptotic density when n=aleph-0, which might be different then when n=2*aleph-0 or n=aleph-1?

    Btw, I don't have a working definition of metric at the moment -_- (nvm, I looked it up).
    Last edited: Nov 12, 2012
  21. Nov 12, 2012 #20
    I'm sorry, but this is making little sense. My suggestion to you is to get a good book on set theory and to work through it. Good books include the following:


    Once you have an idea of the terminology and ideas of set theory, we can talk about it. But otherwise, I fear we will just talk without understanding eachother.
    Last edited by a moderator: May 6, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook