CTK Exchange
CTK Wiki Math
Front Page
Movie shortcuts
Personal info
Awards
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Products to download and subscription Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Cantor Set"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange Thoughts and Suggestions Topic #100
Reading Topic #100
Paolo Di Muccio
guest
Feb-09-11, 12:14 PM (EST)
 
"Cantor Set"
 
   Do you really need compactness in the first proof that C - C = <0,1>?

It'seems to me that {Bi} and {Ci} converge on their own...

Reference: A. Bogomolny, Difference of two Cantor sets from Interactive Mathematics Miscellany and Puzzles
https://www.cut-the-knot.org/do_you_know/cantor3.shtml, Accessed 09 February 2011


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

  Subject     Author     Message Date     ID  
  RE: Cantor Set alexbadmin Feb-09-11 1
     RE: Cantor Set Paolo Di Muccio Feb-12-11 2
         RE: Cantor Set alexbadmin Feb-12-11 3
     RE: Cantor Set mr_homm Feb-12-11 4
         RE: Cantor Set alexbadmin Feb-13-11 5
             RE: Cantor Set mr_homm Feb-16-11 6
                 RE: Cantor Set alexbadmin Feb-17-11 7
                     RE: Cantor Set mr_homm Feb-17-11 8
                         RE: Cantor Set alexbadmin Feb-18-11 9

Conferences | Forums | Topics | Previous Topic | Next Topic
alexbadmin
Charter Member
2769 posts
Feb-09-11, 12:29 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
1. "RE: Cantor Set"
In response to message #0
 
   > It'seems to me that {Bi} and {Ci} converge on their own...

We actually know nothing of the behavior of {Bi} and {Ci}, except that Ai = Bi - Ci. While Ai does have a limit, Bi and Ci may a priori oscilate any other way. They become close to each other, yes. But they both may grow in magnitude, at least in principle.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
Paolo Di Muccio
guest
Feb-12-11, 04:22 PM (EST)
 
2. "RE: Cantor Set"
In response to message #1
 
   I'm sorry to bother again. In the example:

"As an example, for a = 0.1202112, we have successively

0.1 = 0.2 - 0.0222...
0.12 = 0.22 - 0.0222...
0.120 = 0.220 - 0.0222...
0.1202 = 0.2202 - 0.0222...
0.12021 = 0.2202 - 0.02222
0.120211 = 0.220202 - 0.022220222...
0.1202112 = 0.2202022 - 0.022220222... "

both {Bi} and {Ci} converge, if I am not mistaken, and I cannot think of an example where this is not the case! :-(


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexbadmin
Charter Member
2769 posts
Feb-12-11, 04:23 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
3. "RE: Cantor Set"
In response to message #2
 
   So, prove that this is always the case.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since Jan-5-11
Feb-12-11, 11:23 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
4. "RE: Cantor Set"
In response to message #1
 
   This has started me thinking about variations on the given proof #1.

We want to solve A = B - C with A in [0, 1] and B, C in the Cantor set. As in the given proof, A, B, and C are written as ternary strings, with B and C free of the digit 1. Let's think of the problem as A + C = B, set up in the format of the usual grade-school arithmetic exercise with sums and carries at each digit location.

Now the basic limitation of the given proof is that the carry value propagates from right to left, so that one must have a starting point for the calculation at the right end of the digit'sequence. Hence only finite digit sequences can be constructed, and topological arguments are needed to obtain the solution for the rest.

This can be avoided by the following trick borrowed from computer science: in designing an algorithm for a recursive calculation one tries to reformulate the problem to make as much of it as possible non-recursive, leaving only a minimal core of recursion. Let us then try to split the calculation into a recursive step which computes ONLY THE CARRY, and a non-recursive step which then specifies the solution.

At each digit location, one of the following 6 possibilities holds, where i = the carry into this digit, o = the carry out to the left neighbor digit, and x is a free choice of 0 or 2:


o i | 0 0 1 1 1 0 0 1 0 0 1 1
a | 0 0 1 1 2 2
+ c | x 2 2 0 0 x
--- | --- --- --- --- --- ---
= b | x 0 0 2 2 x

When a = 0 or 2, i = o, and when a = 1, i = ~o, and both of these relations are symmetrical in i and o. It is therefore clear that the carry can be propagated from left to right instead of right to left. Simply start with i(0) = 0 (so that the resulting number B will not exceed 1), and move to the right through the digits of A, toggling i(n) whenever a(n) = 1. This constructs a unique (binary) carry string I for any A in [0, 1].

With the carry string available, the computation of each digit of B and C is independent and can be carried out non-recursively. Specifically, let D = A + I mod 3 (where the addition and mod 3 reduction is separate for each digit). Then define C by c(n) =2*(d(n) == 1) and B by b(n) = 2*(d(n) == 2). B and C are then the desired elements of the Cantor set.

B and C are also the SMALLEST pair that works, since we have chosen zero for every value of x. If we further define E by e(n) = x*(d(n) == 0), where each x is 0 or 2 arbitrarily, then B' = B+E and C' = C+E is another pair of solutions. Since I, B, and C are completely determined by A, the only variation possible is in E; hence the set of all B', C' is the complete set of solutions to the problem.

Further, the arbitrary choices in E can be described by choosing a binary string X in [0, 1] and letting 2*x(n) be the nth digit choice made in E (not the nth digit of E, but the nth occurance of d = 0). Then each X corresponds to a solution B', C' and the full set of solutions is indexed by [0, 1] if there are infinitely many 0 digits in D. If D has only finitely many 0 digits, then of course there are finitely many choices. From this, we have the interesting corollary:

For every A in [0, 1], the number of distinct pairs of Cantor set members satisfying A = B - C is 2^z, where z is the number of occurances of the digit 0 in D. This is true even if z is infinite, since 2^card(N) = card([0, 1]).

Thank you for this very interesting problem. I hope this approach is to your liking.

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexbadmin
Charter Member
2769 posts
Feb-13-11, 12:15 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
5. "RE: Cantor Set"
In response to message #4
 
   Stuart,

> Thank you for this very interesting problem.

You made the problem interesting. Thank you for the very enlightening solution.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since Jan-5-11
Feb-16-11, 03:57 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
6. "RE: Cantor Set"
In response to message #5
 
   > Thank you for the very enlightening solution.

Glad you enjoyed it. I've been thinking further, and it'seems that Paolo's point is well taken. The algorithm you use to generate the digit sequences never changes a digit once it has been set. Hence if one wants to think of the finite digit sequences as partial sums of the finished infinite sequence, one may do so.

Then for any N > 0, and for any m and k both > N, the partial sums 0. b_0 b_1 ... b_k and 0. b_0 b_1 ... b_m agree to at least N places, and so differ by at most 3^(-N). But this clearly shows that the sequence is a Cauchy sequence (for any epsilon > 0, simply choose N so 3^(-N) < epsilon), hence it converges independent of any compactness assumption. Of course the same applies to {c_n} as well.

So I agree that topology must come into the proof in order to reach the infinite digit sequences, but only via the Cauchy criterion; compactness appears unnecessary. Or have I jumped to a conclusion somewhere?

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexbadmin
Charter Member
2769 posts
Feb-17-11, 08:49 AM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
7. "RE: Cantor Set"
In response to message #6
 
   Oh, yes.

At the time of writing I assumed that there are many ways a number can be a difference of two Cantor's terms - which you actually showed and which is more or less clear from the diagram in the second proof.

What I missed to observe or to capitalize on was that the algorithm in the first proof does not change the already established established digits.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since Jan-5-11
Feb-17-11, 11:41 AM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
8. "RE: Cantor Set"
In response to message #7
 
   I see you've added my proof to the Cantor set page. It looks much nicer now that it has proper formatting. Thank you!

--Stuart


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexbadmin
Charter Member
2769 posts
Feb-18-11, 11:46 AM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
9. "RE: Cantor Set"
In response to message #8
 
   Thank you, Stuart.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK