## Towards the Cantor set

Today we will “construct” the standard (ternary) Cantor set [1]. We start with the closed unit interval $\mathcal{C}_0 := [0,1]$, and then remove its open middle third $]1/3, 2/3[$ to obtain $\mathcal{C}_1 := [0, 1/3] \cup [2/3, 1]$. We then remove the open middle thirds of each of these two intervals to obtain

$\mathcal{C}_2 := [0, 1/9] \cup [2/9, 3/9] \cup [6/9, 7/9] \cup [8/9, 1]$

and, continuing this process ad infinitum, we obtain a nested sequence of compact sets $\mathcal{C}_0 \supset \mathcal{C}_1 \supset \mathcal{C}_2 \supset \dots$. Note that $\mathcal{C}_n$ is the union of $2^n$ intervals, each of length $3^{-n}$. We refer to the following set

$\mathcal{C} := \displaystyle\bigcap_{n=0}^{\infty} \mathcal{C}_n$

as the standard (ternary) Cantor set. This set is most interesting, indeed, since it is uncountable and has Lebesgue measure zero [1].

__________

In Haskell, a closed interval $[a, b]$ can be represented by an ordered pair $(a,b)$. Each set $\mathcal{C}_n$ can be represented by a list of ordered pairs, where each pair represents a closed interval. We create a function $f$ that takes $\mathcal{C}_n$ and returns $\mathcal{C}_{n+1} = f ( \mathcal{C}_n )$. We will work with arbitrary-precision rational numbers, not floating-point numbers.

The following Haskell script lazily generates the sequence of sets:

import Data.Ratio

type Interval = (Rational, Rational)

-- remove the middle third of an interval
removeMiddleThird :: Interval -> [Interval]
removeMiddleThird (a,b) = [(a,b'),(a',b)]
where b' = (2%3)*a + (1%3)*b
a' = (1%3)*a + (2%3)*b

-- define function f
f :: [Interval] -> [Interval]
f intervals = concat $map removeMiddleThird intervals -- create list of sets sets :: [[Interval]] sets = iterate f [(0,1)] -- define Lebesgue measure measure :: Interval -> Rational measure (a,b) = b - a Note that we used function iterate to generate the sequence of sets. Here is a GHCi session: *Main> -- take first 4 sets *Main> take 4 sets [[(0 % 1,1 % 1)],[(0 % 1,1 % 3),(2 % 3,1 % 1)], [(0 % 1,1 % 9),(2 % 9,1 % 3),(2 % 3,7 % 9),(8 % 9,1 % 1)], [(0 % 1,1 % 27),(2 % 27,1 % 9),(2 % 9,7 % 27),(8 % 27,1 % 3), (2 % 3,19 % 27),(20 % 27,7 % 9),(8 % 9,25 % 27),(26 % 27,1 % 1)]] *Main> -- compute measure of C_0 *Main> sum$ map measure (sets !! 0)
1 % 1
*Main> -- compute measure of C_1
*Main> sum $map measure (sets !! 1) 2 % 3 *Main> -- compute measure of C_2 *Main> sum$ map measure (sets !! 2)
4 % 9
*Main> -- compute measure of C_3
*Main> sum \$ map measure (sets !! 3)
8 % 27

This is arguably the most useless Haskell script ever written.

__________

References

[1] Charles Chapman Pugh, Real Mathematical Analysis, Springer-Verlag, New York, 2002.