There are always a lot of things that I encounter which make me think that I should write them on the blog but had no time to do so... In order to deal with it and keep some kind of an 'interesting reading list' for myself and for interested other, I decided to share these 'random curiosities' in a bulk manner. So here are this week's:
- The most significant and interesting thing that I've learnt this week was the so-called 'Benford's Law'. It is an unintuitive law that concerns the frequency distributions of the first digits of random-data. I will definitely elaborate on this one in one of my future post but there are a lot of great references where you can dive deep into it! For instance this article from Plus Maths really nails it down really nicely! If you have only 10 minutes, this video from Numberphile would work too..
- Moving on with statistics and there is this really curious article in Quanta Magazine called 'For Persi Diaconis’ Next Magic Trick'. It is about shuffling a deck of cards in order to make them 'random'. But the method proposed is not ordinary shuffling, which they have already proven that only seven shuffle is enough to achieve it, but 'smooshing' which is basically spreading the cards out on a table, swishing them around with your hands, and then gathering them up. Standford mathematician Persi Diaconis's proposal involves one of the fundamental ideas of statistical physics namely mixing. Quite an inspiring read...
- One of my past-time activities, especially in the busy traffic of Istanbul is to listen to interesting podcasts on the way and one of my favourite is ABC's 'Future Tense'. It is some kind of a 'futuristic' program but all the ideas have grounds on the present, it is not a sci-fi kind of future in a sense. One of the last week's program was themed 'Crowds and Motion' which deals with interesting problems and proposed solutions to urban planning and modeling the crowds as particles and simulations related with it. There was two interesting models, one with pedestrians walking in open space avoiding collisions and other one, namely "Steffen Method" of Airplane Boarding.. Further details and recorded audio is on the website.
- Web's first-class online science magazine Nautilus's this months theme is 'Dominoes' and their first week's installment includes a fascinating article called 'The Amazing, Autotuning Sandpile'. It is one of those 'simple to state but having jaw-dropping consequences' kind of problems of statistical physics. Simple mathematical model of a sand pile creating a very complex and dynamical patterns and behaviour, namely avalanches. The article is accompanied by nice pictures and simulations..
- Biology related, another Quanta Mag. article released this week was 'How Structure Arose in the Primordial Soup', telling the story of the search of the origins of fundamental transitions like formation of the cell, creation of the genetic code and making up the energy supplying metabolism functions way before the last common ancestor. The main ideas resonates with a Maynard Smith's wonderful book that I've been reading recently, The Origins of Life, and also an interesting method is proposed involving tracing the amino-acid code in the Tree of Life. An inspiring read...
- Academic tips and tricks side, I've read a very well-written compact blog post related to 'A few steps toward cleaner, better-organized code' which I desperately need more and more.
- And also a seemingly a trivia but one of the most complex thing that I've seen lately, solving a 17 X 17 Rubick's Cube. It is just beyond explanation...
Showing posts with label recreations. Show all posts
Showing posts with label recreations. Show all posts
Saturday, April 18, 2015
Friday, April 10, 2015
Constructing a Cantor Set
Seemingly basic and simple things generally proves to be really really complex if we are talking about real numbers. We had a discussion of one of them in our recent class which I've been following this semester as a guest student. The class is an introduction course for beginner physics undergraduates to rather abstract and mathematical notions and related theoretical physics problems. For instance, we have started with a simple billiard problem and we ended up counting the real numbers and who knows where we will end up... Today our stop was famous Cantor Set.
We construct the Cantor Set by basically dividing the closed interval $[0,1]$ into equal 3 parts and leaving the middle part out. Then we continue the same process to the remaining two parts, i.e to the intervals $[0,\frac{1}{3}]$ and $[\frac{2}{3},1]$ and iterate for infinitely many times. After several steps the picture looks more or less like this:
Let us name the intervals left in each step as sets $C_0, C_1, C_2, ..., C_n$ where $n$ denote the steps starting with $0$ and runs to $n$.. For instance: $C_0 = [0,1]$ and $C_1 = [0,\frac{1}{3}] \cup [\frac{2}{3},1]$ and so on.. Cantor Set is the intersection of all these sets $C_n$: \[ C = \bigcap_{n} C_n \] We can also see that $C$ is a contracting set, i.e $C_0 \supset C_1 \supset C_2 ... \supset C_n \supset ...$. If we denote the length of the intervals at step $n$ as $\Delta n$, we can see that $\Delta n = \frac{1}{3^n}$. Also let $N_n$ be the number of intervals at step $n$, thus $N_n = 2^n$.
Now we have got all we need to calculate the total length of the interval at the $n^{th}$ step which is given by \[l_n = \Delta n \times N_n = (\frac{2}{3})^n\]Remember that we are doing the procedure of cutting into three and discarding the middle one infinitely many times, hence when $n \to \infty$, $l_n \to 0$, i.e the lengths contracting to end up being zero at the limit $n \to \infty$. Does that mean that our Cantor Set is empty?
Obviously not, since we can see easily see that the end points of the intervals that we create every time stays in the set. As in the case of $0, 1, \frac{1}{3}, \frac{2}{3}, \frac{1}{9}, \frac{2}{9}$ etc... Actually we can define a map \[x_n = \frac{1}{3^n} \,\,\,\,\,\,\, \mathbb{N} \to C \]so that we can map all of the end points with a natural number. This implies that $\mathbb{N} \preceq C$. Since $\mathbb{N}$ is dominated by $C$, cardinality of $C$ is at least $\aleph_0$. In the mean time, since $C \subset [0,1]$, the cardinality of $C$ can not exceed $\aleph_1$, which is the cardinality of $[0,1]$ interval itself (proof omitted). The critical question is whether the cardinality of $C$ is also $\aleph_1$ and the suprising answer to that is YES!
In order to prove that, we can start by labeling the intervals by 0,1 sequences so that after each division, the left remaining part is denoted by $0$ and the right one by $1$. Let us start with naming the interval $[0,1] = I$. Then we divide it by 3 and leave out the middle one, we label the left part $I_0$ and the right one $I_1$. Then we continue the iterations as in the figure below:
All the elements of the Cantor Set can be traced back to upper levels by looking whether it is on the left interval or the right one at each level. For instance if we look for $\frac{1}{4}$, it is in the interval $I$, then in $I_0$ (left), then $I_{01}$ (right), then $I_{010}$(left again)... It alternates between the left interval and the right one. We have denoted the left and right intervals with $0$ and $1$ respectively, thus we can claim that each 0-1 infinite sequence corresponds to an element of our Cantor Set. If we denote the all 0-1 sequences as $l_{\{0,1\}}$, then it can be shown that $card (l_{\{0,1\}}) = \aleph_1$ (proof omitted). Since we have previously said that the cardinality of $C$ can not exceed $\aleph_1$ so we can finally deduce that:
\[l_{\{0,1\}} \preceq C\] thus,
\[ card(C) = \aleph_1\]We showed that the cardinality of the Cantor Set is $\aleph_1$. This means that starting from the interval $[0,1]$, we constructed a set of intervals by removing infinitely many of the them in between, then joining them together we ended up with a set with the same "number of elements" we started with in the first place!
We construct the Cantor Set by basically dividing the closed interval $[0,1]$ into equal 3 parts and leaving the middle part out. Then we continue the same process to the remaining two parts, i.e to the intervals $[0,\frac{1}{3}]$ and $[\frac{2}{3},1]$ and iterate for infinitely many times. After several steps the picture looks more or less like this:
Let us name the intervals left in each step as sets $C_0, C_1, C_2, ..., C_n$ where $n$ denote the steps starting with $0$ and runs to $n$.. For instance: $C_0 = [0,1]$ and $C_1 = [0,\frac{1}{3}] \cup [\frac{2}{3},1]$ and so on.. Cantor Set is the intersection of all these sets $C_n$: \[ C = \bigcap_{n} C_n \] We can also see that $C$ is a contracting set, i.e $C_0 \supset C_1 \supset C_2 ... \supset C_n \supset ...$. If we denote the length of the intervals at step $n$ as $\Delta n$, we can see that $\Delta n = \frac{1}{3^n}$. Also let $N_n$ be the number of intervals at step $n$, thus $N_n = 2^n$.
Now we have got all we need to calculate the total length of the interval at the $n^{th}$ step which is given by \[l_n = \Delta n \times N_n = (\frac{2}{3})^n\]Remember that we are doing the procedure of cutting into three and discarding the middle one infinitely many times, hence when $n \to \infty$, $l_n \to 0$, i.e the lengths contracting to end up being zero at the limit $n \to \infty$. Does that mean that our Cantor Set is empty?
Obviously not, since we can see easily see that the end points of the intervals that we create every time stays in the set. As in the case of $0, 1, \frac{1}{3}, \frac{2}{3}, \frac{1}{9}, \frac{2}{9}$ etc... Actually we can define a map \[x_n = \frac{1}{3^n} \,\,\,\,\,\,\, \mathbb{N} \to C \]so that we can map all of the end points with a natural number. This implies that $\mathbb{N} \preceq C$. Since $\mathbb{N}$ is dominated by $C$, cardinality of $C$ is at least $\aleph_0$. In the mean time, since $C \subset [0,1]$, the cardinality of $C$ can not exceed $\aleph_1$, which is the cardinality of $[0,1]$ interval itself (proof omitted). The critical question is whether the cardinality of $C$ is also $\aleph_1$ and the suprising answer to that is YES!
In order to prove that, we can start by labeling the intervals by 0,1 sequences so that after each division, the left remaining part is denoted by $0$ and the right one by $1$. Let us start with naming the interval $[0,1] = I$. Then we divide it by 3 and leave out the middle one, we label the left part $I_0$ and the right one $I_1$. Then we continue the iterations as in the figure below:
All the elements of the Cantor Set can be traced back to upper levels by looking whether it is on the left interval or the right one at each level. For instance if we look for $\frac{1}{4}$, it is in the interval $I$, then in $I_0$ (left), then $I_{01}$ (right), then $I_{010}$(left again)... It alternates between the left interval and the right one. We have denoted the left and right intervals with $0$ and $1$ respectively, thus we can claim that each 0-1 infinite sequence corresponds to an element of our Cantor Set. If we denote the all 0-1 sequences as $l_{\{0,1\}}$, then it can be shown that $card (l_{\{0,1\}}) = \aleph_1$ (proof omitted). Since we have previously said that the cardinality of $C$ can not exceed $\aleph_1$ so we can finally deduce that:
\[l_{\{0,1\}} \preceq C\] thus,
\[ card(C) = \aleph_1\]We showed that the cardinality of the Cantor Set is $\aleph_1$. This means that starting from the interval $[0,1]$, we constructed a set of intervals by removing infinitely many of the them in between, then joining them together we ended up with a set with the same "number of elements" we started with in the first place!
Subscribe to:
Posts (Atom)