Author |
Topic: plane embedding (Read 2489 times) |
|
kiochi
Newbie
Posts: 42
|
 |
plane embedding
« on: Jan 9th, 2007, 12:33pm » |
 Quote  Modify
|
I guess this might not belong here, but I wasn't sure how commonly known the term "uncountable" is.
Q: Is it possible to embed uncountably many:
A) nonconcentric circles without intersection
B) figure 8s without intersection
in the plane?
In each case, if so, explain how you can do it; if not, prove why not.
|
|
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
|
Re: plane embedding
« Reply #1 on: Jan 9th, 2007, 1:16pm » |
Quote Modify
|
A. No problem, just offset the centers a bit to make them non-concentric; consider the set of circles (x-t)2+y2=(2t)2 for e.g. 1 < t < 2.
B. I don't think so. Considering a parameterized mapping similar to the above, it would seem to me that, given some value of the parameter t, for every value of x < some epsilon the figure-eight given by parameter (t+x) overlaps the figure-eight given by parameter t. However, given that the Cantor Set is uncountable, I don't feel confident I can comfortably rule out the existance of any possible "fractal" embedding with that argument.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: plane embedding
« Reply #2 on: Jan 9th, 2007, 1:31pm » |
Quote Modify
|
In fact:
B. Yes. Take the classic cunstruction of the Cantor Set: start with the interval [0,1] and repeatedly remove the middle thirds of all segments. Now, in the plane, take the x-axis between 0 and 1 as the interval [0,1], and every time a segment is removed in constructing the Cantor Set, draw a figure-eight centered on the x-axis with extents in x not exceeding those of the removed segment. When you're done, you'll have a figure-eight for every removed segment in the Cantor Set -- i.e. one for every two points in the Cantor Set; and since the number of points in the Cantor Set can be proven to be uncountable, you must have an uncountable number of non-overlapping figure-eights as well.
I'll attach a diagram when I have time.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
kiochi
Newbie
Posts: 42
|
|
Re: plane embedding
« Reply #3 on: Jan 9th, 2007, 1:45pm » |
Quote Modify
|
on Jan 9th, 2007, 1:31pm, SMQ wrote:In fact:
B. Yes. Take the classic cunstruction of the Cantor Set: start with the interval [0,1] and repeatedly remove the middle thirds of all segments. Now, in the plane, take the x-axis between 0 and 1 as the interval [0,1], and every time a segment is removed in constructing the Cantor Set, draw a figure-eight centered on the x-axis with extents in x not exceeding those of the removed segment. When you're done, you'll have a figure-eight for every removed segment in the Cantor Set -- i.e. one for every two points in the Cantor Set; and since the number of points in the Cantor Set can be proven to be uncountable, you must have an uncountable number of non-overlapping figure-eights as well.
I'll attach a diagram when I have time.
--SMQ |
|
Hmm, I don't think that quite works. Sure, the number of points in the cantor set is uncountable, but that doesn't imply that there are uncountably many conitinuous intervals in its complement.
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: plane embedding
« Reply #4 on: Jan 9th, 2007, 1:47pm » |
Quote Modify
|
Sorry SMQ, but that construction will not work. Only countably many intervals are removed in the construction of the Cantor set. The Cantor set has lots of points which are not the endpoint of a removed open interval. In fact, if you remove all the points which are endpoints of removed intervals, the resulting set is still countable.
I believe the answer to B is no , but I have to think about it some more.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: plane embedding
« Reply #5 on: Jan 9th, 2007, 3:09pm » |
Quote Modify
|
You might be right (see my extended querries below), that construction may not work, but I think this one does. 
Step 1: draw a figure-eight, call it "0"
Step 2: draw 2 figures-eight, one inside each lobe of the one drawn in step 1; call them "0.0" and "0.1"
Step 3: draw 4 figures-eight, one inside each lobe of the ones drawn in step 2; call them "0.00", "0.01", "0.10", and "0.11".
...
Step N: draw 2N-1 figures-eight, one inside each lobe of the ones drawn in step N-1; call them "0.00...", etc. (all terminating binary fractions of length N).
...
Step aleph-null: draw 2aleph-null figures-eight.
Clearly there is a one-to-one correspondence between figures-eight and the real numbers in the interval [0,1] with terminating binary fraction expansions. Since there are an uncountable number of the latter, there must also be an uncountable number of the former.
Also, since the number of figures-eight is 2aleph-null > aleph-one, and aleph-one is uncountable, the number of figures-eight is uncountable.
Furthermore, by displacing the scaled-down figures at each step (rather than embedding them in the lobes of the previous figures, I believe it should be possible to embed an uncountable number of any bounded figure in the plane in a bounded area of the plane.
[Edit] fixed numbering problem and added reference to my confusion below [/Edit]
--SMQ
|
| « Last Edit: Jan 9th, 2007, 7:49pm by SMQ » |
IP Logged |
--SMQ
|
|
|
kiochi
Newbie
Posts: 42
|
|
Re: plane embedding
« Reply #6 on: Jan 9th, 2007, 4:40pm » |
Quote Modify
|
No, that construction doesn't work either (even when you correct the numbering ). As is often the case with these sorts of things, everything is fine in the finite stages, but things change when you get to the limit.
I could give you a deeper argument about why that fails, but I don't want to spoil it. You guys seem to be getting this fairly quickly 
|
| « Last Edit: Jan 9th, 2007, 4:46pm by kiochi » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: plane embedding
« Reply #7 on: Jan 9th, 2007, 4:50pm » |
Quote Modify
|
To be more specific, your "step aleph-null" cannot be carried out. The average diameter of the lobes of a nested figure 8 must be < 1/2 the diameter of the figure 8 it is nested in. By the time you have an infinite regression, you no longer have any open space to draw another figure 8 in.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: plane embedding
« Reply #8 on: Jan 9th, 2007, 7:46pm » |
Quote Modify
|
OK, I never claimed to be an expert, and I'm experienced enough to know that my intuition often fails me when infinities are involved... but wait, what? 
Icarus' geometric interpretation I think I understand, but I've been a lay fractal fan for 20+ years and thought I was starting to get part of my mind around the transfinite cardinals. Not that I, in any way, doubt the more-informed statements made above, but:
on Jan 9th, 2007, 1:47pm, Obob wrote:| The Cantor set has lots of points which are not the endpoint of a removed open interval. |
|
It does? Could you please name or describe any such point for me?
on Jan 9th, 2007, 1:47pm, Obob wrote:| Only countably many intervals are removed in the construction of the Cantor set. |
|
Now here I'm really confused.
Argument A: One of the ways that the reals differ from the natural numbers is that if I take any two natural numbers there are a finite number of other natural numbers between them, while if I take any two real numbers there are an (uncountably) infinite number of other reals between them. It seems to me that if I take any two removed intervals in the Cantor set, there are certainly an infinite number of other removed intervals between them. I suppose if the total number of removed intervals really is countable then there's only a countably-infinite number of removed intervals between them? It seems very odd to me that it should be a countable set if there are infinitely-many elements between any two chosen elements...is there a more-simply-constructed example of another set with this property I could examine?
Argument B: At step 1 of constructing the Cantor Set we remove one interval; at step 2, 2 intervals; at step 3, 4 intervals; at step n, 2(n-1) intervals, yes? Do we not, then, remove 2aleph-0 intervals in total? Or, have I horribly misunderstood something I read along the way and is 2aleph-0 not equal to C, the cardinality of the reals (and therefore uncountable)? I am perfectly willing to believe I've made an unwarranted assumption or illegal operation in that process, but clearly there's something I'm not understanding.
And back to the riddle: Have I not constructed a unique figure-eight for every real in [0,1] with a terminating binary fraction expansion? Are those not uncountable? Again, I'm happy to be corrected, and thereby further my learning, but my current understanding is clearly deficient.
on Jan 9th, 2007, 4:40pm, kiochi wrote:| I could give you a deeper argument about why that fails, but I don't want to spoil it. You guys seem to be getting this fairly quickly |
|
Once someone (who, I suspect, won't be me) has given a sufficient answer to part B of the riddle (I did answer part A correctly at least, yes?), I would be delighted to hear it!
--SMQ
|
| « Last Edit: Jan 9th, 2007, 7:57pm by SMQ » |
IP Logged |
--SMQ
|
|
|
kiochi
Newbie
Posts: 42
|
|
Re: plane embedding
« Reply #9 on: Jan 9th, 2007, 7:58pm » |
Quote Modify
|
on Jan 9th, 2007, 7:46pm, SMQ wrote: It seems very odd to me that it should be a countable set if there are infinitely-many elements between any two chosen elements...is there a more-simply-constructed example of another set with this property I could examine?
|
|
The rationals.
on Jan 9th, 2007, 7:46pm, SMQ wrote:
Do we not, then, remove 2aleph-0 intervals in total? Or, have I horribly misunderstood something I read along the way and is 2aleph-0 not equal to C, the cardinality of the reals (and therefore uncountable)?
|
|
No, we don't.
2aleph-0 is certainly uncountable and equal to the cardinality of the reals.
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: plane embedding
« Reply #10 on: Jan 9th, 2007, 8:07pm » |
Quote Modify
|
The points in the Cantor set are real numbers whose ternary expansions consist of 0's and 2's. If I'm not mistaken, the points corresponding to endpoints of removed intervals are just the points with finite ternary expansions. So the vast majority of points are not endpoints.
One of the basic results on countable sets is that the "countable union of countable sets is countable." So think of removing 1 interval, then 2 intervals, then 4, etc., as removing a countable union of finite collections of intervals. Since finite sets are countable, so is the set of intervals we remove.
More surprisingly, the set of finite-length sequences of integers is countable. In cardinal notation, aleph_0+(aleph_0)^2+(aleph_0)^3+... = aleph_0. You have constructed a unique figure-eight for every real in [0,1] with a terminating binary expansion, but this set is countable.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: plane embedding
« Reply #11 on: Jan 9th, 2007, 9:24pm » |
Quote Modify
|
In step 1 of the Cantor construction, we remove 1 open interval, leaving 2 closed intervals. In step 2, remove 2 open intervals, leaving 4 closed intervals. In step n, we remove 2n-1 open intervals, leaving 2n closed intervals.
We can enumerate the open intervals as follows:
U1 is the interval removed in step 1: (1/3, 2/3). U2 & U3 are the intervals removed in step 2 (taken in increasing order), U4 through U7 are the intervals removed in step 3. More generally, U2^(n-1) to U2^n - 1 are the intervals removed in step n.
This enumeration includes all removed intervals, and clearly shows that they are countable. A simpler argument is to note that the removed intervals are all disjoint, and each interval contains a rational number, hence there cannot be more intervals than rational numbers (the same argument shows that the non-removed intervals are also countable).
As for the question of whether all Cantor set numbers are endpoints of an interval - you should note that the endpoints of all the intervals are rational - more particularly, they are all of the form m/3n. Again, they must be countable. But as you know the Cantor set itself is uncountable. The vast majority of it's entries are numbers that always fall in the middle of the intervals - never the ends.
Obob brings up an easy way of answering some of your questions. Note that the interval removed in step 1 consists exactly of those points all of whose ternary expressions have "1" as their first digit right of the radix. (1/3 & 2/3 of course have two ternary expressions each, but in each case, one of the expressions does not have a "1" as the first digit, so they don't get removed.) In step two, we remove exactly those numbers with a "1" as the second digit in all of their ternary expressions. And so on for steps 3+. What is left behind are all the numbers that have a ternary expansion with no "1" digits. Note that Obob is right about the endpoints: they are all of the form m/3n - therefore they have terminating ternary expansions. To show an example of a Cantor point that is not an endpoint - just choose any non-terminating ternary: 0.20202..., for example.
As for terminating binary expansions: those represent numbers of the form m/2n, which are all rational, so again they are countable.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: plane embedding
« Reply #12 on: Jan 9th, 2007, 9:56pm » |
Quote Modify
|
Thanks, all! If I'd made the connection to the rationals I'd have seen my misunderstanding much sooner...stupid rationals.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: plane embedding
« Reply #13 on: Jan 9th, 2007, 10:46pm » |
Quote Modify
|
There was a similar thread with other shapes here.
The key observation for this one is that a figure-eight with diameter d fits inside one with diameter D only if d < D/2.
| hidden: | Each figure-eight has some diameter in the interval (0, infinity). Partition them into countably many classes: for each integer k, consider those with diameter in [2k, 2k+1). Fix a class C. By the above observation, no figure-eight in C can fit inside another one in C, so the "filled in" figure-eights of C are disjoint.
For a positive integer R, let CR denote the set of figure-eights of C which are within R of some fixed origin of the plane. Since each element of C has positive area, bounded below (depending only on C), and the (disjoint) union of the filled in figure-eights of CR is contained in a circle of radius R, which has finite area, it follows each CR is finite. Since C is the countable union of the CRs, over all positive integers R, it follows C is countable.
Since there are only countably many classes of figure-eights, and each class is countable, it follows there are only countably many figure-eights altogether. |
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: plane embedding
« Reply #14 on: Jan 9th, 2007, 11:16pm » |
Quote Modify
|
on Jan 9th, 2007, 7:46pm, SMQ wrote:| Argument B: At step 1 of constructing the Cantor Set we remove one interval; at step 2, 2 intervals; at step 3, 4 intervals; at step n, 2(n-1) intervals, yes? Do we not, then, remove 2aleph-0 intervals in total? |
|
The confusion here I think is similar to the difference between ordinal and cardinal exponentiation.
Cardinal exponentiation is not continuous (wrt the order topology). That is, after step n, we've removed a total of 2n - 1 intervals, but as n->aleph0, 2n doesn't converge to 2aleph_0, since 2n never enters the open interval (aleph0, 22^aleph_0), for example.
Ordinal exponentiation, on the other hand, is pretty much defined to be continuous. That is, as n -> omega, 2n -> 2omega. (The limit of an increasing sequence of ordinals is their least upper bound, which is their union. And the union, over n<omega, of 2n, is omega, which is also the order type of the ordinal exponential 2omega.)
|
| « Last Edit: Jan 9th, 2007, 11:19pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print