Suppose that I drew an infinite number of disjoint closed curves in the plane (such as circles, squares, etc.). Suppose that I then tell you that there is one curve for each positive real number.

You would not have too much trouble believing my assertions at this point. For example, I could have drawn all circles with center at the origin. They are all disjoint, and for each positive real number x, there is a corresponding circle - namely, the circle of radius x.

But suppose that I also tell you that all the curves I drew were figure eights. Can you believe my assertions now?

(A figure eight is a curve in the plane obtained from the basic "8" shape by any combination of translation, rotation, expansion, or shrinking.)

(In reply to re(6): I think it's... - Elaboration by David Shin)

It took me a little while on this one, but I think I can modify my proof further.

This is my proof shown earlier, the infinite induction error in bold.

"Let's assume that we can enclose uncountably many figure 8s in a single largest one.  If this is tre[sic], then we should be able to fit just as many even when we limit the area used to only the left compartments.  The right compartments each enclose a region with positive area.  There is one empty right compartment for every figure 8.  As a result, we will have uncountably many disjoint regions in a plane.  But there cannot be uncountably many disjoint regions in a plane (this is the same reason that we cannot reach uncountable infinity when no figure 8 encloses another)."

Replace the sentence in bold with "Assume that all area used is confined to the left compartments."  The conclusion of the paragraph should then be that at most, the number of figure 8s is countable when the used area is confined to only left compartments.  Therefore, there should be countably many empty right compartments.

Now we can add a figure 8 that looks exactly like the original, except smaller, to every right compartment.  If I were to analogize this to bit strings, I would start with the set of all strings containing only 0s, then would add all strings containing a single 1.  This is a countable union of countable sets, so the result is still countable.  We could do this process again and again to infinity.  Back to the string analogy, I would be adding all strings with 2 ones, then 3 ones, 4 ones, etc., retaining countable infinity each time.  This final union will contain all figure 8s because none will have infinite ones.

I'm going to try and foresee any more slippery slope counterproofs by applying the same proof to the set of all binary strings, infinite and finite.

First we limit the set to all strings containing only 0s.  There are obviously countably many: 0, 00, 000, ...
Next, we add all sets with only 1 one: 1, 10, 100, ..., 01, 010, ...
Then, all sets with 2 ones: 11, 110, ..., 101, ... 011, ..., 0101, ...
And all with three ones, and so forth.
But the union of all these sets only contains the strings with a finite number of 1s, so the string of infinitely alternating 0s and 1s, for instance, is not contained.

Now, I think I'm done... but I thought the same thing last comment.

Posted by Tristan on 2005-02-19 03:22:30