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

A way to count the uncountable Cantor Set.

  1. Feb 28, 2012 #1
    It's not that I discovered a way to count it or anything, but I think I have some confusion about it.

    I understand that Cantor set isn't countable and I accept the proof also.

    But, what if we count the elements of the set like the following?

    1, 0, 1/3, 2/3, 1/9, 2/9, 7/9, 8/9, 1/27, 2/27, 7/27, 8/27, 19/27, 20/27, 25/27, 26/27

    It might help to see the image in this link, to see how the sequence I wrote above goes.

    Basically every time you cut off the middle part from each bar, you're counting the endpoints from the left, excluding the ones you've already counted.

    Anyway, to my intuition, this sequence can be matched with positive integers, which means it's countable.

    What am I getting wrong here?

    I came across this set recently so I don't have much understanding about it. It would be great if some of you can give me some insight. Thank you.
  2. jcsd
  3. Feb 28, 2012 #2
    You are missing almost all of the Cantor set. Your sequence include only numbers with a finite ternary representation, while the Cantor set include all ternary numbers without the digit 1. For example 1/4 = 0,0202020... (base 3) is in the Cantor set, but not in your list.
  4. Feb 28, 2012 #3
    It's easy to show that the Cantor set is uncountable, although I admit it's a really counterintuitive fact. Consider a point x in the Cantor set. When you remove the first middle third, find out if x ends up in the left or right third. Then when you remove the middle third from the subinterval x is in, find out if x ends up in the left or right third of that subinterval. And just repeat that process forever, of finding out whether x is in the left or right third after each stage. So you'll construct an infinite sequence of lefts and rights, like L,R,L,R,R,L... But by labeling L by 0 and R by 1, you'll produce an infinite binary sequence. And if you put a decimal point in front of the number, you get a real number between 0 and 1 in binary notation, like .010110... So there is a one-to-one correspondence between the points in the Cantor set and the real numbers in the Cantor set, which implies that the Cantor set is uncountable.

    The weird fact about the Cantor set is that it's nowhere dense, meaning there is no interval which is a subset of it. So you would naturally assume that the Cantor only consist of the endpoints of the intervals you get at each stage. But you can have a point which is not the end point of any such interval, but is located at just the right place so that it never ends up in any of the middle thirds which are removed. Norweigan's example 1/4 is a good one, because it first ends up in the left third, then in the right third of that, then in the left third of that..., so somehow it survives all the way to the end. And this isn't an unusual case: it turns out MOST points in the Cantor set are non-endponts! That's how it's possible for the Cantor set to be uncountable even though the set of endpoints is countable. It's counterintuitive, but that's the way it works.
  5. Feb 28, 2012 #4
    Nowhere dense, by the way, doesn't mean that it contains no intervals. The rationals contain no intervals but are everywhere dense. It's nowhere dense because its closure doesn't contain any intervals, but that's a minor contention.
  6. Feb 28, 2012 #5
    Thank you very much!
  7. Jun 12, 2012 #6


    User Avatar

    That is all well and good, but as far as I can tell, the Cantor set is a subset of the set of rationals (which is countable) and every infinite subset of a countable set is countable. Where am I going wrong?
  8. Jun 12, 2012 #7
    Not all the points in the Cantor set are rational. In fact, MOST points are irrational. The really counterintuitive thing about the Cantor set is that the endpoints of the subintervals you take out are not the only points in the set. There are points that somehow "survive" each removal of subintervals, even though they're never endpoints! In fact, MOST points in the Cantor set fit that description.
  9. Jun 12, 2012 #8
    The Cantor set is *not* a subset of the rationals. Remember, we start with a real interval. We only remove intervals, and every nonempty nonsingleton interval contains both rational and irrational numbers. This doesn't in itself prove that its not a subset of the rationals, but hopefully it dispels your intuition that it is.

    The way to see this is to note that the Cantor set consists of all real numbers in [0,1] whose ternary expansion contains no 1's. That is, when expanded in base 3, each digit is zero or two. (This can be seen by considering its recursive construction. The middle thirds correspond to ones, and we move out inductively along their ternary expansions pruning out the points that lie in any middle third.)

    Now consider the following function from the Cantor set to the interval [0,1]: given a ternary expansion with no "1"s, replace all the "2"s with "1"s and consider it as a binary expansion instead. It's not hard to see that this map is a bijection, so there are exactly as many points in the Cantor set as there are in the real line.
  10. Jun 12, 2012 #9


    User Avatar

    Thank you for the replies.

    But then does this also mean that the intersection of infinitely many nested closed intervals can never be a singleton? (EDIT: in the sense that there will also still be "something left" in this case as well?)

    (Please pardon my ignorance if the above is not analogous or is not a valid question. I'm still feeling my way around the different kinds of infinity that exist out there.)
  11. Jun 12, 2012 #10
    Nope! Note that singletons are in fact closed intervals. Therefore, if one of the closed intervals is a singleton than it can be.

    That's not necessary, though. Consider In=[-1/n,1/n]. Zero is in every one of those intervals, and every nonzero number fails to be in one of the intervals. Therefore, their intersection is {0}, even though none of those intervals are singletons.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook