Author |
Topic: Adding Cantor Sets (Read 3115 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Adding Cantor Sets
« on: Sep 8th, 2003, 5:02am » |
 Quote  Modify
|
Adding Cantor Sets
Let C represent the Cantor set over [0,1]. Show that
C + C = { x + y | x,y [in] C } = [0,2]
Pretty cool problem eh? 
Note 1: What's the Cantor set over [0,1]? Start with the unit interval, and remove the middle third, to get [0,1/3] [cup] [2/3,1]. Now remove the middle thirds of the remaining intervals, to get [0,1/9] [cup] [2/9,1/3] [cup] [2/3,7/9] [cup] [8/9,1]. Keep doing this, removing the middle thirds of remaining intervals ad infinitum. The remaining set of points (after removing thirds ad infinitum) is called the Cantor set.
Note 2: Thanks to psilo for relaying this problem to me. I came up with a simple constructive proof, but he had an elegant nonconstructive proof. If we modify the puzzle such that only constructive proofs are allowed, I would put this problem in medium.
Note 3: Here's a cool quote ...
"When I was a freshman, a graduate student showed me the Cantor set, and remarked that although there were supposed to be points in the set other than the endpoints, he had never been able to find any. I regret to say that it was several years before I found any for myself."
-Ralph P. Boas, Jr
Lion Hunting & Other Mathematical Pursuits
|
| « Last Edit: Sep 8th, 2003, 1:23pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Adding Cantor Sets
« Reply #1 on: Sep 8th, 2003, 3:55pm » |
Quote Modify
|
Although the definition given is standard, there is a simple way to express the elements of the Cantor set, which may (I haven't thought it out yet) make this challenge easy. Since that is the case, I will hold off giving it at this time, so as not to "spoil the fun". However, had Boas or his graduate student instructor been aware of it, they would not have been challenged to find a non-endpoint element of the set.
|
|
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
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Adding Cantor Sets
« Reply #2 on: Sep 9th, 2003, 7:42am » |
Quote Modify
|
The number 1/3 is in the Cantor set. In fact, another way of generating the Cantor set is to start with the numbers 0, 2/3, then add the numbers 0 + 0/3, 0 + 2/3/3, 2/3 + 0/3, 2/3 + 2/3/3, and so on.
It is evident that the cantor set consists of all the numbers of the following form in base 3:
0.a1a2a3a4... where ai is 0 or 2.
Then all that remains to be seen is that any positive number smaller than or equal to 1.222222222... in base 3 can be represented as the sum of two such Cantor numbers.
But we can give a method to break such numbers down into two Cantor numbers. It should not be too difficult to show how.
|
| « Last Edit: Sep 9th, 2003, 7:43am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Barukh
Guest
|
Continuing the James's post, here's my attempt for solution:
Write the addition table of single digits of Cantor set numbers, considering carries (a, b - input digits, d - result digit, ci - carry-in, co - carry-out):
a b ci | d co
--------------
0 0 0 | 0 0
0 0 1 | 1 0
0 2 0 | 2 0
0 2 1 | 0 1
2 2 0 | 1 1
2 2 1 | 2 1
All the possible pairs (d, co) are represented, and we define the function (a, b, ci) = F(d, co). Then, given a number c0.d0d1d2..., find two numbers x = 0.a0a1a2... and y = 0.b0b1b2... as follows: (ai, bi, ci+1) = F(di, ci) for i = 0, 1, 2, ...
I think, in this scheme, the regular numbers (those with finite radix-3 expansion) must be represented in the equivalent infinite form (i.e. with infinitely many trailing 2's).
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Adding Cantor Sets
« Reply #4 on: Sep 9th, 2003, 12:02pm » |
Quote Modify
|
Here's a pretty way to show it. Consider the closed square (0,0)-(1,1). Now remove the cross that is the union of (0,1/3)-(1,2/3) and (1/3,0)-(2/3,1). It is easy to see that no lines of the form x+y=a, where 0 [le] a [le] 2 can now be drawn without intersecting the remaining four squares.
Now delete a cross in the middle of each of the remaining four squares. Still, no lines x+y=a can be drawn through without intersecting the remaining 16 squares.
It is plain to see that deleting the cross in the middle of a square does not change the silhouette of the square when viewed from a 45 degree angle.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Adding Cantor Sets
« Reply #5 on: Sep 9th, 2003, 11:38pm » |
Quote Modify
|
James: Sweeeet.
Additional, similar problem:
Subtracting Cantor Sets
Show C - C = { x - y | x,y[in] C } = [-1,1].
As an aside, we know that if S is a set of positive Lebesgue measure, S - S contains an interval. It's interesting to note here that although the Cantor set has Lebesgue measure zero, the difference between two Cantor sets still contains an interval.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Adding Cantor Sets
« Reply #6 on: Sep 16th, 2003, 10:55pm » |
Quote Modify
|
Another cool non-constructive proof that C + C = [0,2] -- it may seem complicated and uncool at first, but after you digest it, I think you will agree it is cool :
Given two sets A and B, denote h(A,B) as the Hausdorff distance between them: h(A,B) = inf {d(x,y) : x in A, y in B}, where d is the metric function defined for this space, and inf is the infimum (greatest lower bound of a set).
For a given x in [0,1], consider the function
f(s) = h({x+s}, C[cap][x+s,1]) - h({x-s}, C[cap][0,x-s])
This measures the difference between the distances from x-s and x+s to the Cantor set. (This function may need to be re-read a few times to be grasped.)
Initially x will be in some gap of C. The closest Cantor point to x's left is some distance away, and the closest Cantor point to x's right is some distance away. Denote the greater of these two distances by d. Then in the process of varying s from 0 to d, we are assured that f(s) changes sign. Since f is continuous, the intermediate value theorem says there exists a positive s such that f(s) = 0. This means there exists two points in C which are equidistant from x. Consequently, their average is x, and their sum is 2x. Since x can be anything in [0,1], it follows that the sum of the two aformentioned Cantor points will map to a point in [0,2]. QED.
|
| « Last Edit: Sep 17th, 2003, 1:09am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Adding Cantor Sets
« Reply #7 on: Sep 17th, 2003, 4:27am » |
Quote Modify
|
Honestly, it's not obvious to me that the function f you defined via distances to subsets of the Cantor set is continuous.
I just looked up the fact that all elements of the Cantor set are limit points. Can anyone reassure me that this is sufficient for f to be continuous? Or has my mathematical intuition led me on the wrong track?
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Adding Cantor Sets
« Reply #8 on: Sep 17th, 2003, 6:27am » |
Quote Modify
|
Yeah, I don't see how f could be continuous either. For most elements u in the Cantor set, there will be a bunch of elements arbitrarily close to u on one side only. On the other side, there is usually a well-defined gap to the next element.
As we near these elements, we should get quasi-continuous behaviour of f on one side, and discontinuous behaviour on the other side, at least for some values of x. In fact, I think you could say that f has an infinite number of point discontinuities, and has zero derivative everywhere except at these discontinuities (where the derivative is undefined).
I think this approach can't work by showing f continuous (because I don't think it is). Perhaps we should change the definition of f to be:
f(s) = h({x+s}, C[cap][x+s,1]) - h({x+s}, C[cap][x,x+s])
This one has an infinite number of point discontinuities, but otherwise is continuous, and the derivative is always -2. It passes through zero between every pair of points in the Cantor set.
|
| « Last Edit: Sep 17th, 2003, 6:28am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove