\documentclass[11pt]{article}
\usepackage[sort]{natbib}
\usepackage{fancyhdr}
\usepackage{bm,amsmath,bbm,amsfonts,nicefrac,latexsym,amsmath,amsfonts,amsbsy,amscd,amsxtra,amsgen,amsopn,bbm,amsthm,amssymb, enumerate, appendix, listings,subcaption}
\usepackage{pifont}
\usepackage{graphicx}
\usepackage[nottoc,numbib]{tocbibind}
%-----------------------------------------------------------------------------------USER INTRODUCED PACKAGES BEGINS
%-----------------------------------------------------------------------------------USER INTRODUCED PACKAGES ENDS
\oddsidemargin 0.2cm
\topmargin -1.0cm
\textheight 24.0cm
\textwidth 15.25cm
\parindent=0pt
\parskip 1ex
\renewcommand{\baselinestretch}{1.1}
\pagestyle{fancy}
\pagenumbering{roman}
%-----------------------------------------------------------------------------------USER DEFINED COMMANDS/ENVIRONMENTS BEGINS
\newtheorem{propos}{Proposition}[section]
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corolloary}{Corollary}
\newtheorem{defn}{Definition}[section]
\newtheorem{ex}{Example}
\newtheorem*{nt}{Note:}
\newcommand{\vol}{\textnormal{vol}}
\newcommand{\diam}{\textnormal{diam}}
\newcommand{\tick}{\ding{51}}
\newcommand{\cross}{\ding{55}}
\newcommand{\rom}[1]{\romannumeral #1}
%-----------------------------------------------------------------------------------USER DEFINED COMMANDS/ENVIRONMENTS ENDS
%-----------------------------------------------------------------------------------HEADER AND TITLE INFORMATION BEGINS
\lhead{\normalsize \textrm{Part 3 Project (Project Report)}}
\chead{}
\rhead{\normalsize D. Edwards}
\lfoot{\normalsize \textrm{MA3PR}}
\cfoot{\thepage}
\rfoot{Prof. M. Levitin}
\setlength{\fboxrule}{4pt}\setlength{\fboxsep}{2ex}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
\setlength\headheight{14pt}
\addtolength{\textheight}{-54pt}
\title{Minkowski And Box Dimension}
\author{D. Edwards \\ \phantom{} \\ Department of Mathematics and Statistics \\ University of Reading }
%-----------------------------------------------------------------------------------HEADER AND TITLE INFORMATION ENDS
\begin{document}
\maketitle
\textbf{}
%-----------------------------------------------------------------------------------ABSTRACT BEGINS
\begin{abstract}
For many years we have talked about ``well behaved sets'', referring to those to which the methods and ideas of traditional calculus have applied easily. Other sets which have not fallen into such a category have been called ``badly behaved'' and seen as not worthy of study (\citet{KF}: \rom{13}). The field of fractal geometry has given us an insight into these sets. Their applications have been as far reaching as everything from financial markets to the description of clouds. Here we give a brief introduction to the field of fractal geometry. We move on to consider the dimension of fractals. We will see that there are some problems in calculating the dimension of fractals. Why many of them seem to have dimension in-between integers. We will then move to define the concept of the Minkowski dimension, to see try to define a concept of definition. We will examine the properties of this concept and examine what we in general seek from a concept of dimension. We will then see another definition of dimension, and see how these two relate to what we expect of a concept of definition. Lastly we will ask when, if ever, these two concepts are equal and prove Hutchinson’s' theorem. The assumed reader would have had equation in the field of analysis, calculus and algebra. All of this assumed knowledge may be found in the following books, ``Fundamentals of mathematical analysis'' \citep{RH} for analysis, ``Modern Engineering Mathematics'' \citep{GJ} for calculus and ``Schaum's Outline of Abstract Algebra'' \citep{LRJ} for algebra.
\end{abstract}
%-----------------------------------------------------------------------------------ABSTRACT ENDS
\newpage
\tableofcontents
\listoftables
\listoffigures
\newpage
\pagenumbering{arabic}
%-----------------------------------------------------------------------------------REPORT BODY BEGINS
\section{Introduction}
For many years the sets to which calculus has been easily applicable have been described as ``well behaved sets'' (\citet{KF}: \rom{13}). The study of these sets has changed that way of thinking in one swift movement. The reason we have been primarily concerned with these sets is due to their incredible ability to model the world around us. Recent developments have found that these ``badly behaved sets'' can be applied to the world yielding better results in some cases than our previous models. Some of these ``Badly behaved'' sets are known as \textbf{fractals}. ``At the present stage of development of science and mathematics, the idea of a fractal is most useful as a broad concept'' (\citet{MB}: 35). Hence we shall not define a fractal rigorously but rather by a collection of interesting sets, pictures, examples and concepts which, in broad principle, embody the general properties that we expect from a fractal.
This field was first explored in detail by Benoit B. Mandlebrot. Since then many have seen the ability of fractals to describe the world around us ``Mandelbrot’s fame rests on this founding of fractal geometry and showing how it applies to many fields.'' (\citet{RLH}: \rom{20}). Further far from just being applicable to describe the world, it can even be better than the traditional geometric models, ``His 1962 that prices [in financial markets] vary far more than the standard model allows... is now widely accepted by econometricians'' (\citet{RLH}: \rom{24}). A brief warning to the reader is included in Michael Barnsely's book entitled ``Fractals Everywhere'' ``[If you proceed with study of fractals] you risk losing your childhood vision of clouds, forests, galaxies, leaves, feathers, flowers, rocks, mountains torrents of water, carpets, bricks and much else.'' (\citet{MB}: 1). This quote truly shows how versatile the theory of fractals is in describing natural objects.
Although some of the sets we will study may only satisfy some of the general properties we will observe in our board definition of a fractal, we still refer to them as fractals. There are two properties that we mainly consider. These are \textbf{self-similarity}, meaning that if we enlarge the set it looks the same as it began, either graphically or pictorially. Also we consider the idea of \textbf{fine structure}. One may visualize this as the set being detailed regardless of how much we may ``zoom in'' on it. We will give much more rigorous definitions of these concepts as we proceed.
One of the most interesting aspects of fractals is their ability to have fractional dimension. Insofar the reader will have encountered and be comfortable with referring to dimension as an integer. Here we will endeavor to see why the non-integer dimension of fractals not only makes sense but how it arises. Beginning with the study of the Cantor set, we will consider the dimension of this set. Then move to generalize the concept of dimension and consider the various different dimensions that exist for calculating dimension. Here our primary point of study will be the Minkowski dimensions of fractals. We will see the properties of this dimension, explore the properties it possesses in terms of what we generally expect from dimension, compare its properties to another definition of dimension and finally move on to see under what conditions these two concepts are equal, finally will proving Hutchinson's theorem to answer this question.
\section{Preliminaries}
We here introduce or remind the reader of a few concepts that will be key in our discussion of fractals. All of the ideas that are discussed here that refer to metric spaces, openness or closure points may be found in any good book on basic topology. The reader is referred to ``Introduction to Metric and topological spaces'' \citep{WS} for more information on this topic.
\begin{defn}
A set $X$ is said to be \textbf{countable} if there exists an injective function $f: X \rightarrow \mathbb{N}$.
\end{defn}
\begin{defn}
A function $f: X \rightarrow y $ is called a \textbf{bi-Lipschitz} function if there exists $2$ constants $c_1, c_2$, with $0 < c_1 \leq c_2 < \infty$, such that
\begin{align*}
c_1 | x-y | \leq |f(x) - f(y)| \leq c_2 |x-y|
\end{align*}
\end{defn}
The above two definitions are mainly reminders; it is assumed the reader is familiar with Lipschitz functions. The above definition is merely an extension of that idea. This definition may be found in ``Fractal geometry'' (\citet{KF}: 8).
\begin{defn}
Let $X$ be a set. A \textbf{metric} (or \textbf{distance}) on $X$ is a function $d: X \times X \rightarrow \mathbb{R}$ with the following properties:
\begin{enumerate}[(M1)]
\item $\quad d(x,y) \geq 0 \ \ \forall x,y \in X \ \& \ d(x,y) = 0 \Leftrightarrow x = y$
\item $\quad d(x,y) = d(y,x) \ \ \forall x,y \in X $
\item $\quad d(x,z) \leq d(x,y) + d(y,z) \ \ \forall x,y,z \in X.$
\end{enumerate}
A \textbf{metric space} is a pair $(X,d)$ where $X$ is a set and $d$ is a metric on $X$.
\end{defn}
\begin{nt}
In general for the rest of this paper we will use $X$ to denote a metric space and $d$ will be mainly used as a general metric, unless otherwise stated. If we are referring to a subset of $\mathbb{R}^n$ then we will be using $F$.
\end{nt}
\begin{defn}
The \textbf{Euclidian metric} is defined to be if $(x_1, x_2, \cdots ,x_n) = x \in \mathbb{R}^n $ and $(y_1, y_2, \cdots ,y_n) = y \in \mathbb{R}^n $ we define the Euclidean metric (or Euclidean distance), denoted $|x-y|$, to be the metric $|x - y|: \mathbb{R}^n \times \mathbb{R}^n \rightarrow \mathbb{R}$ where,
\begin{align*}
|x-y| = \sqrt{\sum^n_{i=1} (x_i - y_i)^2}.
\end{align*}
\end{defn}
\begin{nt}
When using the Euclidian metric we will be referring to the metric space $(\mathbb{R^n}, |\cdot|)$. Unless otherwise stated.
\end{nt}
\begin{defn}
Let $(X,d)$ be a metric space, $(x_n)_{n\geq1}$ be a sequence in $X$ and let $x_0 \in X$. We say that $(x_n)_{n\geq1}$ \textbf{converges to} $x_0$ \textbf{in} $(X,d)$ as $n \rightarrow \infty$, and write $x_n \rightarrow x_0$ in $(X,d)$ as $n \rightarrow \infty$, if
\begin{align*}
\forall \varepsilon > 0 \exists N \in \mathbb{N} \text{ such that } n \geq N \Rightarrow d(x_n,x_0) < \varepsilon
\end{align*}
\end{defn}
The above notion is merely a generalization of continuity as the reader currently understands it. It is worth noting that if we choose $d$ to be the Euclidian metric and $X= \mathbb{R}$ then see that the above definition is precisely that of continuity of real analysis.
\begin{defn}
Let $(X,d)$ be a metric space. We say that $X$ is \textbf{complete} if every Cauchy sequence in $X$ converges in $X$.
\end{defn}
\begin{defn}
If $(X,d)$ is a metric space with $X \neq \phi$. We define the \textbf{diameter} of $A \subset X$ to be $\sup\{ d(x,y): x,y \in A \}$. We denote this quantity by $\diam(A)$.
\end{defn}
In the above we are examining the maximum distance between any two points in the set. Considering a circle, we may see how this will yield its diameter and hence the name. Moreover this generalized definition is very good for all purposes.
\begin{defn}
Let $(X,d)$ be a metric space. For and $x_0 \in X$ and $r>0$, we define the following sets:
\begin{align*}
&B_r(x_0) = \{ x \in X : d(x_0,x)<r \} \text{ the \textbf{open ball of center $x_0$ and radius $r$}}, \\
&\overline{B_r(x_0)} = \{x \in X : d(x_0,x) \leq r \} \text{ the \textbf{closed ball of center $x_0$ and radius $r$} }.
\end{align*}
\end{defn}
\begin{defn}
A set $A \subset X$ is said to be \textbf{open} if
\begin{align*}
\forall x \in A \ \exists \ B_r(x_0) \subset X.
\end{align*}
Further we call a set \textbf{closed} if the compliment of $A$ in $X$, denoted $A^c$, is open.
\end{defn}
It is worth noting that openness and closedness are not exhaustive. That is if a set is not open that does not imply it is closed and the converse is true. Moreover if a set is closed that does not mean it is not open. A very quick check will show that $\mathbb{R}$ is both open and closed.
\begin{defn}
A point $x \in X$ is said to be a \textbf{closure point} of $A$ if, for every $r>0$, one has that $B_r(x)\cap A \neq \phi$. The set of all closure points of $A$ is called the \textbf{closure of $A$}, and is denote $\overline{A}$.
\end{defn}
\begin{defn}
We define the concepts of \textbf{limit inferior} and \textbf{limit superior}. These are respectively,
\begin{align}
&\underline{\lim_{x \rightarrow 0}} f(x) = \lim_{\varepsilon \to 0} ( \sup \{ f(x) : x \in E \cap B_\varepsilon(a) - \{a\} \} ) \label{liminf} \\
&\overline{\lim_{x \to a}} f(x) = \lim_{\varepsilon \to 0} ( \inf \{ f(x) : x \in E \cap B_\varepsilon(a) - \{a\} \} ) \label{limsup}.
\end{align}
If the values in (\ref{liminf}) and (\ref{limsup}) are equal then $\lim f(x)$ exists and is the common value of the two.
\end{defn}
In this definition we are seeking to maximize or minimize the sequence and then take its limit. These concepts are, in general, not equal as we will see later on.
\section{Fractal Sets}
\subsection{The middle third Cantor set}
\begin{figure}[t]
\begin{center}
\includegraphics[height=3cm]{Cantorsetgraphic.jpg}
\end{center}\caption{The middle third cantor set}\label{cantor}
\end{figure}
Insofar we have discussed the notation of a fractal set and a few of the properties we expect them to have. Now we seek to give some substance to the previous ideas by discussing some of the most famous examples of fractal sets in general. Unquestionably one of the most famous fractal sets is the middle third Cantor set. The middle third Cantor set is generated by taking the unit interval $[0,1]$, which we denote $C_0$. We then split it into thirds and remove the middle third, giving $2$ new intervals of width $\frac{1}{3}$; these intervals are $\left[0,\frac{1}{3}\right]$ and $\left[\frac{2}{3},1\right]$. We call this new set $C_1$. We repeat this process to the two new intervals. This gives us $4$ intervals, each of width $\frac{1}{9}$, which are $\left[0, \frac{1}{9}\right]$, $\left[\frac{2}{9},\frac{1}{3} \right]$, $\left[\frac{2}{3},\frac{7}{9}\right]$ and $\left[\frac{8}{9},1\right]$. We call this set $C_2$. We repeat this process $n$ times to obtain $C_n$. The middle third Cantor set is the limit of $C_n$ and $n \rightarrow \infty$ \citep{KF}. A diagrammatical representation can be seen in (Figure \ref{cantor}).
We see here that this set is self-similar due to the way we generate the set we note that $C_1$ is merely $2$ copies of $C_0$ scaled by $\frac{1}{3}$. Similarly $C_3$ is merely $2$ copies of $C_2$ scaled by $\frac{1}{3}$. The middle third Cantor set, $C$, may be easily seen to be $C =\cap^\infty_{n=1} C_n$. Note that $C_1 = C_0 \cap C_1$ and $C_2= C_0 \cap C_1 \cap C_2$. Hence, substituting this definition into $C = \lim_{n \rightarrow \infty} C_n$ we obtain $C =\cap^\infty_{n=1} C_n$. Indeed one may see that the middle third Cantor set merely consists of a set of single points. However no matter how far one may ``zoom in'' on a point the point is always still there. As it is simply a singularity, in a number line. So in this sense it may be considered as having fine structure.
\subsection{The von Koch curve}
Another very famous fractal is the von Koch curve. This begins by taking an interval of unit length. We then split the interval into thirds. In the middle third we insert an equilateral triangle with no base \citep{KF}. We then repeat this process, infinitely. A graphic representation of this may be seen in (Figure: \ref{von}). The figure was generated using the Maple code written by \citet{AS}. We notice here that each of the lines in the first iteration looks like the starting intervals. The two end pieces are scaled by $\frac{1}{3}$ and the two middle pieces are scaled by $\frac{1}{3}$ and rotated appropriately. Again we see here the essence of self-similarity as discussed in the introduction. Here we can see that Von Koch curve must have fine detail as if a single side of the curve was straight the process would have been applied to it. Moreover we see here why this may be thought of as a ``badly behaved''. As there are no straight lines in the von Koch curve, it is nowhere differentiable, hence is very difficult to describe with traditional geometry. The reader is invited to see how this is constructed by observing Matlab code written by \citep{SD}.
In (Figure: \ref{von}) we see the first, second third iteration of the Von Koch curve, denoted $K_1, K_2, K_3$ respectively, as well as the final product.
\begin{figure}[ht]
\begin{center}
\includegraphics[height=4 cm]{VonKochGraphic.jpg}
\end{center}\caption{The Von Koch curve}\label{von}
\end{figure}
\subsection{The general properties of fractals}
We see here some of the main properties that are shared by these two fractals. Both are very difficult to describe using traditional geometry, both have fine structure, both are self-similar and both are generated using a relatively simple process (in the case of the Von Koch curve and middle third Cantor set a recursive process). These are probably the most common properties shared by most fractals. Hence, in general, when we refer to a set $A$ as a fractal it will have all or most of the following properties,
\begin{enumerate}[(i)]
\item $A$ has infinite detail, fine structure
\item $A$ is either very difficult or impossible to describe with traditional geometry
\item $A$ will be self-similar in some sense or another
\item $A$ will generally be defined in a very easy way. Either by an iterative process or normally.
\end{enumerate}
While the above list is not a rigorous definition it will help us in understanding what a fractal is and what we will have in mind when considering a fractal \citep{KF}.
\subsection{Dimensions of the von Koch curve and middle third Cantor set}
In the introduction we hinted that the dimension of fractals could be fractional. We now try to give some justification to that statement. Consider the middle third Cantor set, as it is merely the collection of points having no length, but due to its fine structure near each point there are more points near any given point. Hence, although each point has no length there is always another point next to it much like an interval. So it seems to make sense that the dimension would lie somewhere between zero and one.
Again applying the same logic to the von Koch curve, this clearly has length $\frac{4^k}{3^k}$ at the $k^th$ iteration meaning it has infinite length, but does not have any area. Hence, it again seems to make sense that the dimension would lie between one and two. Indeed for both of these fractals the bounds we have placed on them are reasonable, which we will see this when we calculate their exact dimension later on.
\section{Minkowski And Box Dimension}
\subsection{$\delta - $Parallel Bodies}
One of the most commonly used definitions of fractal dimension is the Minkowski (or box dimension). The first concept needed to introduce the concept of the Minkowski is that of a $\delta$-parallel body \citep{KF}. We define this as follows.
\begin{defn}
Let $(X,d)$ be a metric space. We define the $\delta-$parallel body of a set $A \subset X$, denoted $A_{\delta}$, to be the set,
\begin{align*}
A_{\delta} = \{ x \in X : d(x,y) \leq \delta \text{ for some } y \in A \}.
\end{align*}
\end{defn}
\begin{figure}
\centering
\begin{subfigure}{.5\textwidth}
\centering
\includegraphics[height=3cm]{PointParrellelBody}
\caption{The $\delta-$parallel body of a single point}
\label{fig:sub1}
\end{subfigure}%
\begin{subfigure}{.5\textwidth}
\centering
\includegraphics[height=3cm]{LineParrellelBody}
\caption{The $\delta-$parallel body of a line}
\label{fig:sub2}
\end{subfigure}
\caption{Two simple $\delta-$parallel bodies}
\label{fig:test}
\end{figure}
We will see that $\delta-$parallel bodies have an intrinsic relationship with the concept of dimensions as we currently know it. We will be talking about the ``lowest power of $\delta$''. We denote, $f(x) \sim \phi(x) $ if $\frac{f(x)}{\phi(x)} \rightarrow 1$. In a function of $\delta$ then $\phi(\delta)$ is clearly going to be the lowest power of $\delta$. Let $A = \{a \}$, $X = \mathbb{R}^2$, and $d$ be the Euclidean metric. Consider the $\delta-$parallel body of this set. This can be seen in (Figure : \ref{fig:sub1}). Now consider the volume of the area bounded by the red line in (Figure : \ref{fig:sub1}). This is obviously a circle by our definition of a $\delta-$parallel body. We may easily compute the volume of this, which we denote $\vol A_{\delta}$ which is known to be $\vol A_{\delta} = \pi \delta^2 \sim \pi \delta^{2-0}$.
We can also consider the $\delta-$parallel body around an interval. In this case let $B = [a,b]$ for some $a,b \in \mathbb{R}$ with $a<b$, $X = \mathbb{R}^2$, and $d$ as before. Then we may form the $\delta-$parallel body, $A_{\delta}$. This may be seen in (Figure \ref{fig:sub2}). The volume of this, denoted as above, is easily seen to be $\vol B_{\delta} = 2 \delta(b-a) + \pi \delta^2 \sim 2(b-a)\delta^{2-1}$.
One may also find the $\delta-$parallel body of a circular line known as the one dimensional torus. In this case we consider the unit circle $C= \{ x^2 + y^2 = 1 : x,y \in \mathbb{R} \}$. We now have $C_\delta$ as the area between $2$ circles enclosing our original line, this may be seen in (Figure: \ref{fig:sub3}) and is the area enclosed by the red and yellow line with the blue circle being the set we are considering. It is also apparent one would have that $\vol C_\delta = \pi (1 + \delta)^2 - \pi (1-\delta)^2 \sim 4 \pi \delta^{2-1}$. We may consider a $2$ dimensional unit circle centered at the origin, here we have $D = \{ x^2 + y^2 \leq 1: x,y \in \mathbb{R} \}$. This may be seen in in (Figure: \ref{fig:sub4}). It is worth noting an animated version of this plot is available see \citep{DE}. Here we have $\vol D_\delta = \pi (1+ \delta)^2 \sim \pi \delta^{2-2}$.
We notice that if we express the lowest power of $\delta$ in $\vol A_\delta$ where $A$ is our set as $2 - s$ for an appropriate $s$, then $s$ is the dimension of the set we are considering. We may also extend this idea to three dimensions, in this case we have that $X = \mathbb{R}^3$. So for the three of the sets we considered above, we now see that the $\delta-$parallel body for a single point is a sphere, for the line we have two hemispheres at each end of a tube around the line and for a circular line it would be the torus enclosing. These volumes may be seen in (Table: \ref{Table1}).
Again we notice here that is we express the lowest power of $\delta$ in $\vol A_\delta$, where $A$ is our set, as $3-s$ for an appropriate $s$, then $s$ is the dimension of the set we are considering. In general, for an easily described geometric shape, we may say that for $A \subset \mathbb{R}^n$ with the Euclidian metric and $X = \mathbb{R}^n$ if $A_{\delta} \sim \delta^q$ then the value $s$ is the dimension of $A$ given by, $q = n - s$.
\begin{table}[ht]
\begin{center} \caption{The volume of certain parallel bodies} \label{Table1}
\begin{tabular}{| c | c | c |}
\hline
Shape, $A$ & $\vol A_{\delta}$ in $\mathbb{R}^3$ \\ \hline\hline
Single point &$\frac{4}{3} \pi \delta^3 \sim \frac{4}{3} \pi \delta^{3-0}$ \\ \hline
Line & $\frac{4}{3} \pi \delta^3 + \pi \delta^2(b-a) \sim \pi \delta^{3-1}(b-a)$ \\ \hline
Circular line & $2 \pi^2 \cdot 1 \cdot (2 \delta)^2 \sim 8 \pi^2 \delta^{3-1} $ \\
\hline
\end{tabular}
\end{center}
\end{table}
\begin{figure}
\centering
\begin{subfigure}{.5\textwidth}
\centering
\includegraphics[height=3cm]{ThreeCirclesParrellelBody}
\caption{The $\delta-$parallel body of a circular line}
\label{fig:sub3}
\end{subfigure}%
\begin{subfigure}{.5\textwidth}
\centering
\includegraphics[height=3cm]{TwoCirclesParrellelBody}
\caption{The $\delta-$parallel body of a circle}
\label{fig:sub4}
\end{subfigure}
\caption{Two more $\delta-$parallel bodies}
\label{fig}
\end{figure}
\subsection{Definition of Minkowski/Box Dimension}
We observed above that the concept of dimension has a very intrinsic relationship with the concept of $\delta-$parallel bodies. We may now seek to define the Minkowski (or box) dimension of fractals, herein referred to as just the Minkowski dimension. We noticed that the volume of a $\delta-$parallel body is different depending on set we are considering the $\delta-$parallel body to be in, i.e. $X$. So we will make definition to be explicit in our calculations.
\begin{defn}
Let $A \subset \mathbb{R}^n$ with the Euclidean metric, then we define $\vol^n A_\delta$ to be the volume of $A_\delta$ where $X= \mathbb{R}^n$.
\end{defn}
We may now define the Minkowski dimension of a set \citep{MB}.
\begin{defn}
If $A$ is a subset of $\mathbb{R}^n$, then the \textbf{upper and lower Minkowski dimensions} are,
\begin{align}
\underline{\dim}_{B} A = n - \underline{\lim}_{\delta \rightarrow 0} \frac{\log \vol^n(A_{\delta})}{\log \delta} \label{lower} \\
\overline{\dim}_{B} A = n - \overline{\lim}_{\delta \rightarrow 0} \frac{\log \vol^n(A_{\delta})}{\log \delta} \label{upper}
\end{align}
respectively, where $F_{\delta}$ is the $\delta-$parallel body to $F$. If the quantities (\ref{lower}) and (\ref{upper}) are equal we refer to them as the \textbf{Minkowski dimension} or \textbf{box dimension} of $F$ and we write
\begin{align*}
\dim_B =n - \lim_{\delta \rightarrow 0} \frac{\log \vol^n(F_{\delta})}{\log \delta}.
\end{align*}
\end{defn}
It is all very well quoting a definition and saying that this concept of definition. We now seek to justify the above definition, through some examples.
\begin{ex}
\begin{enumerate}[(a)]
\item We seek to find the Minkowski dimension of a single point $A = \{ a \}$, with $X= \mathbb{R}^2$. In this case as we have already discussed we have $\vol^n A_\delta= \pi \delta^2$. Hence we have here that the upper and lower Minkowski dimensions, respectively, are,
\begin{align}
\underline{\dim}_{B} A = 2 - \underline{\lim}_{\delta \rightarrow 0} \frac{\log \pi \delta^2}{\log \delta} = 2-2 = 0\label{l1} \\
\overline{\dim}_{B} A = 2 - \overline{\lim}_{\delta \rightarrow 0} \frac{\log \pi \delta^2}{\log \delta} = 2-2 = 0, \label{u1}
\end{align}
using L'Hospital to compute the limit. We have that the upper and lower sums are equal hence the Minkowski dimension is $0$. We see here that this is equal to the dimension that we know of a singular point.
\item We have already discussed the dimension of a circular line in $\mathbb{R}^3$. We will now seek to compute the upper and lower Minkowski dimensions. These are respectively given by,
\begin{align}
\underline{\dim}_{B} A = 3 - \underline{\lim}_{\delta \rightarrow 0} \frac{\log 2 \pi^2 \cdot 1 \cdot (2 \delta)^2}{\log \delta} \label{l3} = 3-2 = 1 \\
\overline{\dim}_{B} A = 3 - \overline{\lim}_{\delta \rightarrow 0} \frac{\log 2 \pi^2 \cdot 1 \cdot (2 \delta)^2}{\log \delta} \label{u3} = 3-2 = 1,
\end{align}
computing the limits as in the first example.
\end{enumerate}
\end{ex}
So we see here that this definition of dimension is consistent with our current knowledge of dimensions of such sets as points and lines. It is easily enough shown to also be consistent with our knowledge of dimension of shapes such as circles, spheres, cubes and other such sets that are easily described by current geometry. We will see later in this paper that this set is concept of dimension is also useful in describing the dimensions of fractals and while returning an integer for the value of dimension as we currently know it, it does indeed give us fractional dimension for the dimension of some fractals such as the Cantor set and von Koch curve as seen later.
\subsection{Alternative Definitions of Box Dimension}
We now define a somewhat more useful version of the Minkowski dimension. This definition is one of the most widely used due, in part, to its relatively easy calculation \citep{KF}. We must first introduce another concept here to be able to make the definition.
\begin{defn}
Let $F$ be a set and $I$ a countable (or finite) indexing set. Let $\{ U_i \}_{i \in I}$ be a collection of sets. We say that $\{ U_i \}_{i \in I}$ is a \textbf{$\delta-$ cover} of the set $F$ if $F \subset \cup_{i \in I} U_i$ with $0< \diam( U ) \leq \delta$ for each $i \in I$.
\end{defn}
In the above definition we are seeking to take individual sets of diameter at most $\delta$ and trying to cover the entire set with them, \citep{KF}. Now with this new definition we may make an alternative definition of the Minkowski dimension, the following proposition gives such a definition and we prove its equivalence to the previous definition of Minkowski dimension. The proof is lifted from ``Fractal Geometry'' (\citet{KF}: 41-42).
\begin{propos}
If $F$ is a subset of $\mathbb{R}^n$ then the upper and lower Minkowski dimensions are,
\begin{align*}
\overline{\dim}_{B} F = \overline{\lim}_{\delta \rightarrow 0} \frac{\log N_{\delta}(F)}{-\log \delta} \\
\underline{\dim}_{B} F = \underline{\lim}_{\delta \rightarrow 0} \frac{\log N_{\delta}(F)}{-\log \delta}
\end{align*}
respectively, where $\log N_{\delta}(F)$ is any of the following
\begin{enumerate}[(i)]
\item the smallest number of closed balls of radius $\delta$ that cover $F$;
\item the smallest number of cubes of side $\delta$ that cover $F$;
\item the number of $\delta-$mesh cubes that intersect $F$;
\item the smallest number of sets of diameter at most $\delta$ that over $F$;
\item the largest number of disjoint balls of radius $\delta$ with centers in $F$.
\end{enumerate}
\end{propos}
\begin{proof}
Assume that $F$ may be covered by $N_{\delta}(F)$ balls of radius $\delta$. Now consider $F_\delta$. Plainly this may be covered with balls of radius $2\delta$. Hence we obtain,
\begin{align*}
\vol^n (F_\delta) \leq N_\delta (F_\delta) c_n (2\delta)^n
\end{align*}
where $c_n$ is the volume of a unit ball in the $n$th dimension, $\mathbb{R}^n$. Now we take logarithms of both sides of the above to yield,
\begin{align*}
\frac{\log \vol^n (F_\delta)}{-\log \delta} \leq \frac{\log(2^n c_n) + n \log( \delta) + \log(N_\delta (F))}{-\log(\delta)}.
\end{align*}
Proceeding to take limits we obtain,
\begin{align}
\lim_{\delta \rightarrow \delta} \frac{\log \vol^n (F_\delta)}{-\log(\delta)} \leq n + \underline{\dim_B}(F). \label{proof4.1}
\end{align}
A similar inequality holds for the upper limit. On the other hand if there are $N_\delta (F)$ balls of radius $\delta$ that are disjoint and with centres in $F$, then
\begin{align*}
N_\delta (F) c_n (2\delta) \leq \vol^n (F_\delta).
\end{align*}
Taking logarithms and limits yields the opposite inequality to (\ref{proof4.1}), thus using definition (\rom{5}) we have equality.
\end{proof}
We have now calculated the dimension of the middle third Cantor set (\citet{KF}: 43-44).
\begin{ex}
\item We now seek to compute the Minkowski dimension of the middle third Cantor set. We have already discussed that at each stage $E_k$ we have $2^k$ intervals, of total length $3^{-k}$. Hence if we covered the intervals of the Cantor set by the $E_k$, then we have that $N_\delta (F) \leq 2^k$ provided $3^{-k} < \delta \leq 3^{-k + 1}$, then from (\ref{upper})
\begin{align*}
\overline{\dim}_{B} F = \overline{\lim}_{\delta \rightarrow 0} \frac{\log N_{\delta}(F)}{-\log \delta} \leq \overline{\lim}_{k \rightarrow \infty} \frac{\log 2^k}{\log 3^{k-1}} = \frac{\log 2}{\log 3}.
\end{align*}
Additionally if an interval is of length $\delta$ with $3^{-k-1} \leq \delta < 3^{-k}$ then this must logically only intersect one of the intervals in the $E_k$ by the width and definition of the Cantor set. There are exactly $2^k$ of these intervals so at least $2^k$ intervals of $\delta$ width are necessary to cover $F$. Hence, $N_\delta(F) \geq 2^k$. This leads to $\underline{\dim}_{B} (F) \geq \frac{\log 2}{\log 3}$. We have the upper and lower Minkowski dimensions are equal. Hence we have that the Minkowski dimension of the Cantor set is $\frac{\log 2}{\log 3}$.
\end{ex}
\section{Another concept of dimension}
We will now consider an alternative definition of dimension. Alternative definitions can be useful to us because the Minkowski dimension can be somewhat limited. Before we can introduce this new concept of dimension we must first introduce the concept of a measure.
\subsection{Measures}
Before we can introduce the concept of a measure we first define a field.
\begin{defn}
Let $X$ be a space. Let $\mathcal{F}$ denote a nonempty class of subsets of $X$ such that the following properties are true,
\begin{enumerate}[(i)]
\item $A,B \in \mathcal{F} \Rightarrow A \cup B \in \mathcal{F}$
\item $A \in \mathcal{F} \Rightarrow X \text{\textbackslash} A \in \mathcal{F}$.
Then $\mathcal{F}$ is called a \textbf{field}.
\end{enumerate}
\end{defn}
For further reading on the topic of fields and extensions the reader is directed to \citep{CWN}. Now we may define a measure.
\begin{defn}
A function $\mu$ from a field, $\mathcal{F}$, to a non-negative real number(i.e. $\mu: \mathcal{F} \rightarrow [0, \infty) \subset \mathbb{R}$), is called a measure if the following three properties hold,
\begin{enumerate}[(a)]
\item $\mu(\phi) = 0$;
\item $\mu(A) \leq \mu(B)$ if $A \subset B$
\item If $A_1, A_2, \cdots$ is a countable (or finite) sequence of sets then
\begin{align}
\mu \left( \bigcup^{\infty}_{i = 1} A_i \right) \leq \sum^{\infty}_{i =1} \mu(A_i).\label{me}
\end{align}
\end{enumerate}
A measure is called a \textbf{mass distribution} if $0 < \mu(A) < \infty$.
\end{defn}
This definition may be found in ``An introduction to measure theory'' \citep{TT}.
\subsection{The Hausdorff Measure}
Before we can define the Hausdorff dimension we need to define the Hausdorff measure \citep{KF}.
\begin{defn}
Suppose that $F$ is a subset of $X$ and $s$ is a non-negative number. For any $\delta > 0$ we define,
\begin{align*}
\mathcal{H}^s_{\delta}(F) = \inf \left\{ \sum^{\infty}_{i = 1} \diam(U)^s : \{U_i \} \text{ is a } \delta- \text{cover of } F \right\}.
\end{align*}
So we aim to minimize the sum of $s^th$ powers of the diameters of any cover of $F$ of diameter at most $\delta$. As $\delta$ decreases the class of covers of $F$ which satisfy our conditions decreases. Therefore the infimum of $\mathcal{H}^s_{\delta}$ increases and so must approach a limit . Considering the limit we define $\mathcal{H}^s$ as follows
\begin{align*}
\mathcal{H}^s(F) = \lim_{\delta \rightarrow 0} \mathcal{H}^s_{\delta}(F).
\end{align*}
We call $\mathcal{H}^s$ the \textbf{$s$-dimensional Hausdorff measure} of $F$.
\end{defn}
%\begin{propos}
%The $s$-dimensional Hausdorff measure is a measure.
%\end{propos}
%\begin{proof}
%We need to show the $3$ conditions for a measure are true for the Hausdorff measure from the definition of a measure. So, firstly, we consider $\mathcal{H}^s(\phi)$. We may choose the $\delta-$parallel body here to be $B_\delta (0)$. This is a suitable choice as we have $\diam(B_\delta (0)) = \delta \leq \delta$ and further $\phi \subset B_\delta(0)$. So we have a $\delta-$cover of $\phi$ with diameter $\delta$. Hence we now have, using this $\delta-$cover in particular, that
%\begin{align*}
%\mathcal{H}^s_{\delta}(\phi) \leq \delta^s
%\end{align*}
%Now taking the limits of both sides as $\delta \rightarrow 0$ we obtain that $\mathcal{H}^s \leq 0$. However as $\diam(A) \geq 0 \forall A$, by definition. We see $\mathcal{H}^s_{\delta}(A) \geq 0 \forall A$ and hence $\mathcal{H}^s(A) \geq 0 \forall A$. So we obtain that $\mathcal{H}^s(\phi) = 0$. As required.
%Next we check our second condition for a measure, as such we need to prove $\mu(A) \leq \mu(B)$ if $A \subset B$. Note that firstly if $A \subset B$ then we immediately have that if $\{ U_i\}$ is a $\delta-$cover of $B$ then it also a $\delta-$cover of $A$. Moreover if $A \subset B \Rightarrow \diam(A) \leq \diam(B)$. Hence, it is apparent that $\mathcal{H}^s_\delta(A) \leq \mathcal{H}^s_\delta (B)$. Taking the limits of both sides we must therefore have that $\mathcal{H}^s (A) \leq \mathcal{H}^s (B)$.
%Finally we show that if $A_1, A_2, \cdots$ is a countable (or finite) sequence of sets then
%\begin{align}
%\mu \left( \bigcup^{\infty}_{i = 1} A_i \right) \leq \sum^{\infty}_{i =1} \mu(A_i).
%\end{align}
%\end{proof}
\subsection{Hausdorff Dimension}
We may now define the Hausdorff dimension \citep{KF}.
\begin{defn}
The Hausdorff dimension, denoted $\dim_H$ of a set $F \subset X$ s defined by,
\begin{align*}
\dim_H(F) = \inf \{ s: \mathcal{H}^s(F) = 0 \} = \sup \{ s: \mathcal{H}^s(F) = \infty \}
\end{align*}
\end{defn}
\subsection{Relationship between Hausdorff and Minkowski Dimension}
It is important to understand the relationship between the Minkowski and Hausdorff dimension. It is already obvious that we have that $\overline{\dim_B}(F) \geq \underline{\dim_B}(F)$. We ask how the Hausdorff dimension fits into this. Now it is apparent from the definition of the Hausdorff measure that if we have that $F$ may be covered by $N_\delta(F)$ sets then $\mathcal{H}_\delta^s \leq N_\delta (F) \delta^s$. Now if we have that $1 < \mathcal{H}^s$ then $\log N_\delta(F) + s \log(\delta) > 0$, given that $\delta$ is small enough. Thus,
\begin{align*}
s \leq \underline{\lim}_{\delta \rightarrow 0} \frac{\log N_\delta (F)}{\log \delta}.
\end{align*}
So we have that,
\begin{align}
\dim_H(F) \leq \underline{\dim_B}(F) \leq \overline{\dim_B}(F). \label{qqq}
\end{align}
This gives us a very good idea of how the two relate (\citet{KF}: 42-43) and will be used in the final step of our principle result.
\section{Properties Of Dimension}
\subsection{Properties of Dimension}
In so far we have discussed two different concepts of dimension. We have yet to give any rigorous definition of what a function that yields ``dimension'' is (\citet{KF}: 29). From our previous studies there are a few properties we expect from dimension. These are listed below and we will give justification for them.
\subsubsection{Properties of General Dimension}
\begin{enumerate}[(i)]
\item \textbf{Monotonicity:} If $E \subset F$ then $\dim(E) \leq \dim(F)$.
\item \textbf{Stability:} $\dim(E \cup F) = \max\{\dim(E), \dim(F) \}$
\item \textbf{Countable stability:} $\dim(\cup^{\infty}_{i = 1} F_i) = \sup_{1 \leq i < \infty} \{ \dim F_i\}$
\item \textbf{Geometric invariance:} $\dim (f(F)) = \dim (F)$ if $f$ is a transformation of $\mathbb{R}^n$ such as a translation, rotation, similarity or affinity.
\item \textbf{Countable sets dimension:} $\dim(F) = 0$ if $F$ is finite or countable.
\item \textbf{Open set dimension:} If $F$ is an open subset of $\mathbb{R}^n$ then $\dim(F) = n$.
%\item \textbf{Smooth Manifolds:} $\dim(F) = m$ if $F$ is a smooth $m$-dimensional manifold.
\end{enumerate}
The first is quite apparent as we expect a smaller set to have smaller dimension. Next we talk about stability. It seems logical that the union of two sets could not increase dimension, and extending this idea to a countable number of sets we obtain the countable stability condition. Following that we consider geometric invariance, one would assume that by turning a set you could not reduce its dimension; a line turned $\frac{\pi}{2}$ is still a line, similarly with a square. Indeed moving a shape in $\mathbb{R}^n$ should not change its dimension. We know that the dimension of a point is zero. This means that, from the countable stability condition, if $\{ F_i\}$ is a countable collection of singletons then again we would have dimension zero. Lastly; if $F$ is an open set, then by definition of an open set $\exists r>0 $ such that $ B_r(a) \subset F$ for some $a \in F$. Then we have that the dimension of $F$ must be at least $n$ this and obviously it cannot be greater than $n$ as $F \subset \mathbb{R}^n$ so therefor we must have that the dimension of $F$ is exactly $n$. (Assuming our definition of dimension is less than or equal to the topological dimension.)
These are the properties we primarily think of when we discuss dimension. Although these are what we generally think a concept of dimension should have, we will not require that dimension should have all of these. Here we adopt the same approach as we did when defined a fractal and as such ask that the reader forms a broad concept of dimension and not a rigorous definition. This will be more advantageous to us, as we will see in the next section that the concepts of dimension we have already discussed insofar don't satisfy all of these conditions.
\subsubsection{Properties of Minkowski \& Hausdorff dimension}
We now explore the properties of the Minkowski and Hausdorff dimensions. After defining these it is important to know their limits. We will then seek to make a new definition, a modified Minkowski dimension. This will be to address the properties that the Minkowski dimension does not satisfy and, as it is of our primary focus, see which properties the modified Minkowski dimension satisfies (\citet{KF}: 29,44).
\begin{table}[ht]
\begin{center} \caption{Properties of dimension} \label{Table}
\begin{tabular}{| l| l | l | l |}
\hline
Property & $\underline{\dim_B}$ & $\overline{\dim_B}$ & $\dim_H$ \\ \hline\hline
Monotonicity & \tick & \tick & \tick \\ \hline %
Stability & \tick & \cross& \tick \\ \hline %
Countable Stability & \cross & \cross & \tick \\ \hline %
%Geometric Invariance & \tick & \tick & \tick \\ \hline
Lipschitz Invariance & \tick & \tick & \tick \\ \hline %
Countable Sets Dimension & \cross & \cross & \tick \\ \hline %
%Open Set Dimension & \tick & \tick & \tick \\ \hline
\hline
\end{tabular}
\end{center}
\end{table}
We see here that although the Hausdorff dimension satisfies these conditions, the Minkowski dimension is much more limited. The advantages of the Minkowski dimension is that in general it is much easier to calculate. However this is at a loss as can be seen above in the table or from the definition. We see that the Minkowski dimension relies on the upper and lower Minkowski dimension to be equal, and if they are not then the dimension does not exist. While the Hausdorff dimension has many more properties that we may consider ``nice'', it is in principle much harder to calculate than the Minkowski dimension. So we see that while both have their merits, they both have drawbacks as well. We now question whether we could ``improve'' the Minkowski dimension. Could we through a different definition, which is formed along the same lines of thinking, that we recoup the properties we would like? We explore this idea below.
\subsection{Modified Minkowski Dimension}
\begin{defn}
We define here the \textbf{modified Minkowski} dimension. If $\{ U_i\}$is a cover of $F$ then we define the upper and lower modified Minkowski dimensions to be
\begin{align*}
\overline{\dim_{MB}}(F) = \inf \left\{ \sup_i \overline{\dim_B}(U_i): F \subset \bigcup^\infty_{i=0} U_i \right\} \\
\underline{\dim_{MB}}(F) = \inf \left\{ \sup_i \underline{\dim_B}(U_i): F \subset \bigcup^\infty_{i=0} U_i \right\}
\end{align*}
respectively.
\end{defn}
This gives us all of the properties that we stipulated a concept of dimension should have (\citet{KF}: 46). However we do note here that we have merely defined a different concept of dimension, although it is a function of the Minkowski dimension. The natural questions we ask is are these two concepts similar? The best result we could have would be finding they are very similar i.e. returning the same value for many sets. So we ask when these two concepts are equal. The following proposition gives us some idea of this.
\begin{propos}
Let $F \subset \mathbb{R}^n$ be compact. Suppose that
\begin{align*}
\overline{\dim_B}(F \cap V) = \overline{\dim_B}(F)
\end{align*}
for all open sets $V$ that intersect with $F$. Then $\overline{\dim}(F) = \overline{\dim_MB}$. A similar result holds for the lower Minkowski dimensions.
\end{propos}
\begin{nt}
We omit this proof due to the large amount of topology and functional analysis required to prove Baire's category theorem. The proof of Baire's category theorem can be found in \citep{WR} and the proof of this proposition can be found on (\citet{KF}: 46).
\end{nt}
\section{Hutchinson's Theorem And Self Similar Sets}
After defining these two concepts of dimension the natural question to ask if these concept are equivalent and, if they are not, when are they equal, if ever. This shall be our main result. We first propose the mass distribution principle (\citet{KF}: 55).
\subsection{Mass Distributions And The Mass distribution Principle}
\begin{propos} \label{mdp}
Let $\mu$ be a mass distribution on $F$ and suppose that for some $s$ there are numbers $c>0$ and $\delta > 0$ such that
\begin{align*}
\mu(U) \leq c \cdot \diam(U)^s
\end{align*}
for all sets $U$ with $\diam (U) \leq \delta$. Then $\mathcal{H}^s \geq \frac{\mu(F)}{c}$ and
\begin{align*}
s \leq \dim_H(F) \leq \underline{\dim_B}(F) \leq \overline{\dim_B}(F).
\end{align*}
\end{propos}
\begin{proof}
If $\{ U_i \}$ is any cover of $F$ then
\begin{align*}
0 < \mu(F) = \mu \left( \bigcup_i U_i\right) \leq \sum_i \mu(U_i) \leq c \sum_i \diam(U_i)^s.
\end{align*}
Taking the infimum of both sides, we obtain $\mathcal{H}^s_{\delta} \geq \frac{\mu(F)}{c}$ if $\delta$ is small enough, so $\mathcal{H}^s(F) \geq \frac{\mu(F)}{c}$
\end{proof}
\subsection{Contractions And Similarities}
When we defined the fractal we talked a lot about self-similarity we now seek to give some substance to this idea.
\begin{defn}
A transformation $S: X \rightarrow X$, on a metric space $(X,d)$, is called a \textbf{contraction mapping} if there is a constant $0 \leq s < 1$ such that
\begin{align*}
d(f(x),f(y)) \leq c \cdot d(x,y) \quad \forall x,y \in X
\end{align*}
where the number $c$ is the \textbf{ratio} for $f$. Moreover if we have equality in the above equation then we call $f$ a \textbf{similarity} \citep{MB}.
\end{defn}
\subsection{Invariant Sets}
\begin{defn}
If we have that $S_1, \cdots , S_n$ are contractions. We call a subset $F$ of $D$ \textbf{invariant} for the transformation $S_1, \cdots, S_n$ if
\begin{align*}
F = \bigcup^n_{i=1}S_i(F).
\end{align*}
\end{defn}
This definition, and an alternative proof of our main theorem may be found in \citep{JEH}. Before we may continue we must make one last topological definition, this may also be found in \citep{WS}
\begin{defn}
If $A$ is a subset of a metric space $(X,d)$ and $A$ is covered by a family of open sets $\{ U_i \}$ we call the family an \textbf{open cover of $A$}. We call $A$ \textbf{compact} if every open covering of $A$ contains a finite number of sets $\{ V_i \}$ which cover $A$ and we have $\cup V_i \subset \cup U_i$.
\end{defn}
We may prove a theorem here which is necessary for our main result. This theorem and proof may be found in ``Fractal geometry'' (\citet{KF}:114-115).
\begin{theorem}
Let $S_1, \cdots, S_k$ be contractions $D \subset \mathbb{R}^n$ such that,
\begin{align*}
d(S_i(x),S_i(y)) \leq c_i \cdot d(x,y) \quad \forall x,y \in X
\end{align*}
with $0 < c_i < 1$ for $1 \leq i \leq k$ and $d$ as the Euclidean metric. Then there exists a unique compact set $F$ that is invariant under the contractions $S_i$. Moreover if we define a transformation $S$ on the class of non-empty compact sets that are subsets of $D$ by, $S(E) = \cup^m_{i = 1} S_i(E)$. With the notation $S^k(E)$ for the $k$th iteration of $S$ given by,
\begin{align*}
S^k(E) = \bigcup_{J_k} = S_{i_1} \circ S_{i_2} \circ \cdots \circ S_{i_k}
\end{align*}
where $J_k$ is the set of all sequences with $k$ terms $(i_1, \cdots i_k)$ with $1 \leq i_j \leq m$. Then we have that,
\begin{align}
F = \bigcap^\infty_{k = 1} S^k(E) \label{inter}
\end{align}
for any non-empty compact set $E \subset D$ such that $S_i(E) \subset E$ for each $i$.
\end{theorem}
\begin{proof}
Note that if we apply $S$ to any non-empty compact set we obtain a non-empty compact set. Let $E$ be any set satisfying the condition $S_i(E)= E \forall i$. We may take $B_r(0) \cap D$, which will suffice for our purpose as long as $r$ is sufficiently large. Then we have that $S^k(E) \subset S^{k-1}(E)$ i.e. $S^k$ is a decreasing sequence of non-empty compact sets. These compact sets have necessarily non-empty compact intersection. We denote this by $F= \cap^\infty_{k = 1} S^k(E)$. Now since we have that $S^k(E)$ is a decreasing sequence, it follows that $S^0(F) = S(F) = F$, hence $F$ is invariant.
Now we claimed that this set $F$ is invariant. We now seek to prove this claim. We defined a metric on the space of $\mathcal{L} = \{ A: A \text{ is compact and } A \subset D \}$. We denote this as $e$ and define it as follows,
\begin{align*}
e(A,B) = \inf \{ \delta : A \subset B_{\delta} \text{ and } B \subset A_{\delta}\}.
\end{align*}
This is easily checked to be a metric We do so by satisfying the three criteria we stated in the introduction. The first two are fairly apparent, as from the definition of a $\delta-$parallel body we must have that $\delta \geq 0$, and if $\delta=0$ then $A \subset B_0 = B$, also $B \subset A_0 = A$ so $A=B$. Moreover, from the definition of our metric, changing the places of $A$ and $B$ has no effect due to the symmetry of the definition, thus the third condition is also true. Now we have that $(\mathcal{L}, e)$ is a metric space. So consider if $A$ and $B$ are invariant sets, then,
\begin{align*}
e(S(A), S(B)) = e\left( \bigcup^m_{i=1}S_i(A), \bigcup^m_{i=1}S_i(B)\right) \leq \max_{1 \leq i \leq m} e(S_i(A), S_i(B)),
\end{align*}
as if $(S_i(A))_\delta \supset S_i (B) \Rightarrow (\cup^m_{i= 1} S_i(A))_\delta \supset \cup^m_{i=1 S_i(B)}$. Hence we have that, $e(S(A),S(B)) \leq (\max_{1 \leq i \leq m} c_i) e(A,B)$. It follows that if $S(A) = A$ and $S(B)= B$ then $d(A,B) = 0 \Leftrightarrow A=B$.
Thus we have that $e(S(E),F) = e(S(E), S(F)) \leq (\max_{1 \leq i \leq m} c_i) e(E,F)$ therefore, $e(S^k(E),F) = (\max_{1 \leq i \leq m} c_i)^k e(E,F)$. Hence we have that $e(S^k(E),F) \rightarrow 0$ as $k \rightarrow \infty$. So we have that $S^k(E)$ converges to $F$ i $\mathcal{L}$ for any $E \in \mathcal{L}$.
\end{proof}
\subsection{Open Set Condition}
Lastly we define the open set condition \citep{JEH}.
\begin{defn}
Let $S_1, \cdots , S_n$ be similarities on the set $F$. We say that the $S_i$ satisfy the \textbf{open set condition} if
\begin{align*}
\exists V \neq \phi, \text{ with $V$ open and bounded such that } V \supset \bigcup^n_{i = 1}S_i(V).
\end{align*}
\end{defn}
We now state and prove our main result.
\subsection{Hutchinson's Theorem}
The following lemma, theorem and both proofs are from ``Fractal geometry'' (\citet{KF}: 118-119). The proofs are near identical following the same structure and notation but more explicitly written.
\begin{lemma}
Let $\{ V_i\}$ be an arbitrary collection of disjoint subsets of $\mathbb{R}^n$ with each $V_i$ open for each $i \in I$, where $I$ is an indexing set. If $B_{a_1 r}(x) \subset V_i \subset B_{a_2 r}(x)$ for some $x \in V_i$ and appropriate radii. Then any ball $B_r$ must intersect at most $(1+2a_2)^n a_1^{-n}$ of the closures of $V_i$.
\end{lemma}
\begin{proof}
If $B_r$ intersects with $\overline{V_i}$ then $\overline{V_i} \subset B_{(1+2a_2)r}$. Suppose that $q$ of the $\overline{V_i}$ intersect with $B_r$. Now summing the volumes of the corresponding interior balls of radii $a_1 r$, we logically have that $q(a_1 r)^n \leq (1+2a_2)^n r^n$. Dividing through to obtain $q$ we have the required bound for $q$.
\end{proof}
\begin{theorem}[Hutchinson's Theorem]
Assume that the open set condition, as above, holds for the similarities $S_1, S_2, \cdots , S_n$ on $\mathbb{R}^n$ with similarity ratios $c_i (0 \leq i \leq m)$. If $F$ is the invariant set satisfying,
\begin{align}
F = \bigcup^m_{i = 1} S_i(F) \label{invariant}
\end{align}
then $\dim_H(F) = \dim_B(F) = s$, where $s$ is given by,
\begin{align}
\sum^n_{i = 1} c_i^s = 1. \label{sss}
\end{align}
Moreover for this value of $s$, $0 < \mathcal{H}^s(F) < \infty$.
\end{theorem}
\begin{proof}
Assume that $s$ is the number as given by (\ref{sss}). We define for any set $A$ we have that $A_{i_1, i_2, \cdots, i_k} = S_{i_1} \circ S_{i_2} \circ \cdots \circ S_{i_k}(A) $, where the $S_i$ are the similarities given from the fact that $F$ is a invariant set. So we are considering the set $A$ under the composition of $k$ similarities, for arbitrary $k$. We here let $J_k$ be the set with members being the sequences $(i_1, \cdots, i_k)$ such that $1 \leq i_l \leq m$ with $k$ terms. In other words $J_k$ is the set of all of the sequences of the $i_l$ ($1 \leq i_l \leq m$) such that we may consider the set $A_{j}$ where $j= (i_1, \cdots, i_k) \in I_k$. Now it is apparent that,
\begin{align}
F = \bigcup_{I_k} F_{i_1, \cdots, i_k} \label{tpe1}
\end{align}
(\ref{tpe1}) comes from (\ref{invariant}). This can be seen easily first note that,
\begin{align*}
\bigcup_{I_k} F_{i_1, \cdots, i_k} &= \bigcup^m_{l_1 = 1}S_{l_1} \left(\bigcup^m_{l_2 = 1}S_{l_2} \left(\cdots \bigcup^m_{l_k = 1}S_{l_k}( F) \right) \right).
\end{align*}
As for any sequence $j \in J_k$ we may write this as $(i_1, \cdots, i_k)$ such that $1 \leq i_l \leq m$. Hence, by choosing $l_1 = i_1, l_2 = i_2, \cdots , l_k = i_k$ we have that $F_{i_1, \cdots, i_k}$ is in our left hand side, hence the left hand side is a subset of the right hand side. The argument works in reverse. Let $F_{l_1, \cdots, l_k}$ be in the right hand side, then choosing $(i_1, \cdots, i_k)$ such that $l_1 = i_1, l_2 = i_2, \cdots, l_k = j_k$ and we have that it must be in the left hand side. So the sets must be equal. Now from (\ref{invariant}) we have that,
\begin{align*}
\bigcup^m_{l_1 = 1}S_{l_1} \left(\bigcup^m_{l_2 = 1}S_{l_2} \left(\cdots \bigcup^m_{l_k = 1}S_{l_k}( F) \right) \right) = \bigcup^m_{l_1 = 1}S_{l_1} \left(\bigcup^m_{l_2 = 1}S_{l_2} \left(\cdots \bigcup^m_{l_{k-1} = 1}S_{l_{k-1}}( F) \right) \right).
\end{align*}
Applying this argument $k$ times we obtain (\ref{tpe1}).
We now confirm that these covers provide us with a suitable upper bound for the Hausdorff measure. We know that each of the $S_i$ is a similarity with similarity ration $c_i$, it follows that $S_{i_1} \circ S_{i_2} \circ \cdots \circ S_{i_k}$ must logically have similarity ratio $c_{i_1} \times c_{i_2} \times \cdots \times c_{i_k}$. We now have that,
\begin{align*}
\sum_{J_k} \diam(F_{i_1, \cdots, i_k})^s &= \sum_{J_k} (c_{i_1}c_{i_2} \cdots c_{i_k})^s \diam(F)^s \\
&= \left( \sum^m_{i_1 = 1}c^s_{i_1} \right)\cdots \left( \sum^m_{i_k = 1}c^s_{i_k} \right) \diam(F)^s \\
&= \diam(F)^s
\end{align*}
by (\ref{sss}). Now we have that $\forall \delta > 0$ we may choose $k$ such that $\diam(F_{i_1, \cdots, i_k}) \leq (\max_i c_i)^k \leq \delta$. So we have that $\mathcal{H}^s_\delta \leq \diam(F)$ and as $\mathcal{H}^s \leq \mathcal{H}^s_\delta$ we have that $\mathcal{H}^s \leq \diam(F)$.
We now need to find a lower bound for the Hausdorff measure. We define $I$ to be the set of infinite sequences of the $i_j$, i.e. $I= \{(i_1, i_2, \cdots ) : 1 \leq i_j \leq m \}$. Now also let $I_{i_1, \cdots, i_k} = \{ (i_1, i_2, \cdots, i_k, q_{k+1}, \cdots ) : 1 \leq i_j \leq m \& 1 \leq q_j \leq m\}$ be the set consisting of all the sequences of initial terms $(i_1, \cdots, i_k)$. We may now put a mass distribution, $\mu$ on $I$ with $\mu(I_{i_1, \cdots, i_k}) = (c_{i_1} \cdots c_{i_k})$. Now note that,
\begin{align}
(c_{i_1} \cdots c_{i_k})^s = \sum^m_{i=1} (c_{i_1} \cdots c_{i_k} c_i)^s
\end{align}
from (\ref{sss}). Equivalently we have $\mu(I_{i_1, \cdots, i_k }) = \sum^m_{i=1} I_{i_1, \cdots, i_k, i}$. Indeed we have that $\mu$ is a mass distribution, further for the subsets of $I$ we have that $\mu(I) = 1$. Now note that from (\ref{inter}) we have that for subsets $A$ of $F$ if $S_i(A) \subset A$ for each $i$ and $x \in F$ then there exists a sequence $(i_1, \cdots, i_k)$ such that $x \in A_{i_1, \cdots, i_k}$. Hence we denote this $x_{i_1, i_2, \cdots}$. Now we extend the mass distribution $\mu$ to $F$, which we will denote this $\widetilde{\mu}$. We define this on the subsets $A$ of $F$ as $\widetilde{\mu}(A)= \mu \{ (i_1, i_2, \cdots, i_k): x_{i_1, i_2, \cdots } \in A\}$. It is easily confirmed that $\widetilde{\mu}(F) = 1$.
We now demonstrate $\widetilde{\mu}$ satisfies (\ref{mdp}). Let $V$ be the open set stipulated by the open set condition. Now as we have that $ S(\overline{V}) \subset \overline{V}$ where $S(\overline{V}) = \cup^m_{i = 1} S_i(\overline{V})$. Recall from the last theorem that $S^k(\overline{V})$ is a decreasing sequence and as $\overline{V} \supset F$ we have that $S^k(\overline{V})$ converges to $F$, by (\ref{inter}). Moreover we have that $\overline{V}_{i_1, \cdots, i_k} \supset F_{i_1, \cdots, i_k}$ for all sequences $(i_1, \cdots, i_k)$. Now consider $B_r$, we estimate $\widetilde{\mu}(B_r)$ by considering the sets $V_{i_1, \cdots, i_k}$ where $\diam(V_{i_1, \cdots, i_k}) \approx \diam(B_r)$ and with closures intersecting $F \cap B_r$. We truncate every sequence $(i_1, i_2, \cdots) \in I$ after the first term $i_k$ for which the statement,
\begin{align}
\left( \min_{i} c_i\right) \leq c_{i_1} c_{i_2} \cdots c_{i_k} \leq r \label{tpe2}
\end{align}
is true. Now let $\mathcal{Q}$ denote the finite set of all of the finite sequences generated this way. Then we have,
\begin{align*}
\forall (i_1, i_2, \cdots ) \in I \quad \exists \text{ unique } k \text{ such that } (i_1, \cdots, i_k) \in \mathcal{Q}.
\end{align*}
Now since each $V_j$ for $1 \leq j \leq m$ is disjoint by assumption, so are the $V_{i_1, \cdots, i_k, j}$ for $j$ as before and each $(i_1, \cdots, i_k)$. So we have that each open set in $\{V_{i_1, \cdots, i_k} : (i_1,\cdots, i_k) \in \mathcal{Q} \}$ is disjoint. Following the same ideas we obtain, $F \subset \cup_{\mathcal{Q}} F_{i_1, \cdots, i_k} \subset \cup_{\mathcal{Q}} \overline{V}_{i_1, \cdots, i_k}$.
Now we choose $a_1$ and $a_2$ such that we have $B_{a_1} \subset V \subset B_{a_2}$. Then for $(i_1, \cdots, i_k) \in \mathcal{Q}$, the set $V_{i_1, \cdots, i_k} \supset B_{c_{i_1} \cdots c_{i_k} a_2}$ and hence we also have $B_{\min_i c_i a_1 r} \subset V_{i_1, \cdots, i_k} \subset B_{a_2}$. Now consider $\mathcal{Q}_1 = \{ (i_1, \cdots, i_k) \in \mathcal{Q} \text{ such that } B_r\cap \overline{V}_{i_1, \cdots, i_k} \neq \phi\}$. The by the lemma proved just before this theorem we have that there are at most $q = (1 + 2a_2)^n a^{-n}_1 (\min_i c_i)^{-n}$ such sequences in $\mathcal{Q}_1$. Then we have that,
\begin{align*}
\widetilde{\mu}(B_r) &\leq \mu \{(i_1, \cdots, i_k): x_{i_1, i_2, \cdots} \in F\cap B_r \} \\
&\leq \mu \{ \bigcup_{\mathcal{Q}_1} I_{i_1, \cdots, i_k} \}
\end{align*}
as if $x_{i_1, i_2, \cdots} \in F\cap B_r \subset \bigcup_{\mathcal{Q}_1} \overline{V}_{i_1, \cdots, i_k}$ then there exists an integer $k$ such that $(i_1, \cdots, i_k)$. Thus we have that,
\begin{align*}
\widetilde{\mu}(B_r) &\leq \sum_{\mathcal{Q}_1} \mu(I_{i_1, \cdots, i_k}) \\
&= \sum_{\mathcal{Q}_1} (c_{i_1} \cdots c_{i_k})^s \leq \sum_{\mathcal{Q}_1} r^s \leq r^s q
\end{align*}
using (\ref{tpe2}). Now since $U$ is any set with $U \subset B_{\diam(U)}$, we have that $\widetilde{\mu} \leq \diam(U) q$. So by (\ref{mdp}) we have that $\mathcal{H}^s \geq q^{-1} > 0$ and we have that $\dim_H (F) \geq s$, but we have already shown $\dim_H (F) \leq s$. Hence we have that $\dim_H(F) = s$.
We have shown that the Hausdorff dimension is equal to $s$. We must now show that we also have that the Minkowski dimension is also equal to $s$. Now if we have $\mathcal{Q}$ as an arbitrary set of infinite sequences such that for every $(i_1, i_2 \cdots) \in I$ there is one $k$ such that $(i_1, \cdots, i_k) \in \mathcal{Q}$. We may apply (\ref{sss}) inductively to obtain that $\sum_{\mathcal{Q}} (c_{i_1} \cdots,C_{i_k})^s = 1$. Thus if we choose $\mathcal{Q}$ as before then we have that $\mathcal{Q}$ contains at most $(\min_i c_i )^{-s} r^{-s}$ sequences. For each sequence in $\mathcal{Q}$ we have $\diam{\overline{V}_{i_1, \cdots, i_k}} = c_{i_1} \cdots c_{i_q} \diam(\overline{V}) \leq r \diam{\overline{V}}$. So logically $F$ may be covered by $(\min_{i} c_i)^{-s} r^{-s}$ sets of diameter $r \diam{\overline{V}}$ for each $0<r<1$. Now from alternative definition of the Minkowski dimension (\rom{4}), we have that that $\overline{\dim_B}(F) \leq s$ and since the Hausdorff dimension is also $s$ from (\ref{qqq}) we have that $\dim_B(F) = dim_{H}(F) = s$.
\end{proof}
%-----------------------------------------------------------------------------------REPORT BODY ENDS
\newpage
\begin{thebibliography}{999}
\bibitem[Barnsley, M.(1988)]{MB}{Barnsley, M. (1988) Fractals everywhere, Boston: Academic Press.}
\bibitem[Durrani, S. (2014)]{SD}{Durrani, S. (2014) A function which plots the 'Koch curve' fractal, Available at: http://www.mathworks.co.uk/matlabcentral/fileexchange/301-koch-m (Accessed: 3rd March 2014).}
\bibitem[Edwards, D. (2014)]{DE}{Edwards, D. (2014) Animated Matlab plot to show two circles approximating the 1-D torus, Available at: http://imgur.com/a/3a2oN\#0 (Accessed: 4rd March 2014).}
\bibitem[Falconer, K. J.(1990)]{KF}{Falconer, K. J. (1990) Fractal geometry: mathematical foundations and applications, Chichester: Wiley.
}
\bibitem[Haggarty, R. (1993)]{RH}{Haggarty, R. (1993) Fundamentals of Mathematical Analysis, 2nd edn., Harlow: Prentice-Hall.}
\bibitem[Hutchinson, J. E.(1981)]{JEH}{Hutchinson, J. E. (1981) 'Fractals And Self Similarity', Indiana University Mathematics Journal, \textbf{30}, pp. 713-747.}
\bibitem[Jaisingh, L. R. (2003)]{LRJ}{Jaisingh, L. R. (2003) Schaum's Outline of Abstract Algebra, 2nd edn., United States of America: McGraw-Hill.}
\bibitem[James, G. (2010)]{GJ}{James, G. (2010) Modern Engineering Mathematics, 4th edn., New Jersey: Prentice Hall.}
\bibitem[Le Stang, A. (2013)]{AS}{Le Stang, A.(2013) Koch Snowflake, Available at: http://alamanya.free.fr/themes/vonkoch.htm (Accessed: 3rd March 2014).}
\bibitem[Norman, C. W. (1986)]{CWN}{Norman, C. W. (1986) Undergraduate algebra: a first course, Oxford: Clarendon Press.}
\bibitem[Hudson, R. L. (2008)]{RLH}{Mandelbrot, B. B. (2008) Misbehaviour of Markets, Croydon: Profile Books.}
\bibitem[Rudin, W. (1987)]{WR}{Rudin, W. (1987) Real and complex analysis, 3rd edn., : McGraw-Hill.}
\bibitem[Sutherland, W. A. (2009)]{WS}{Sutherland, W. A. (2009) Introduction to Metric and Topological Spaces, Oxford: Oxford University Press.}
\bibitem[Tao, T. (2011)]{TT}{Tao, T. (2011) An introduction to measure theory, Providence, R.I: American Mathematical Society.}
\end{thebibliography}
\newpage
\appendix
\section{\\Title of Appendix A} \label{App:AppendixA}
This is the code for the animated graph as discussed in section 4.1. All the other graphs are merely variants on this main code.
\lstinputlisting{ThreeCirclesAnimated.m}
\end{document}
