# The Geometric Viewpoint

geometric and topological excursions by and for undergraduates

• Monthly Archives November 2014
• ## Topology & Infinite-Dimensional Linear Algebra

For the student wishing to see interplay between the three major branches of mathematics (analysis, algebra, topology), Hilbert Space is a great place to explore!  Hilbert Space is a tool that gives us the ability to do linear algebra in infinite dimensions.  The very fact that infinity is involved should tell us that we will need analysis, and where ever there’s analysis, there’s also topology.  Oftentimes, interplay between analysis, algebra, and topology is not glimpsed at the undergraduate level; such connections are designated as “grad school material”.  Hilbert Space will offer us a chance to see these connections at work. Rather than give a host of definitions that define Hilbert Space and then give an example, it will perhaps be useful to work in the reverse order.  Consider the set of all complex-valued sequences.  An element of this set might look like this: $(4+ i, 3 - i, 1 - 7i, 5, 0, 5-9i, 2i,\ldots)$.  We look at a special subset:  let $\ell_2$ be the subset consisting of sequences that are square summable; that is, the sequences $(x_n)$ satisfying

$\sum\limits_{i=1}^\infty {\vert x_{i} \vert}^2 < \infty$.

It shouldn’t be entirely clear why we are interested in sequences satisfying this seemingly arbitrary condition, but shortly we will see its importance.  Notice the similarity between the dot product and the infinite sum on the left – the sum looks a lot like the dot product of a vector in $\mathbb{C}^n$ with itself.  The set $\ell_2$ is an example of Hilbert Space; it is just the natural extension of $\mathbb{C}^n$.  We will work a lot with $\ell_2$, but first let’s make sure we really understand this space.  We set out on defining Hilbert Space – a fairly tall order as we shall see!

David Hilbert first introduced the concept of Hilbert Space

This may sound intimidating; it shouldn’t be. A Hilbert Space is just a very special type of vector space. Recall from linear algebra that a (real or complex) vector space $V$ is a set that is closed under addition and scalar multiplication (by real or complex numbers). We call a subset $B$ of $V$ a basis if $V = span(B)$ and if $B$ is linearly independent. In this case we define the dimension of $V$ by saying $dim(V) = \vert B \vert$. Notice that there is nothing about this definition which requires $B$ to be a finite set. Indeed, while finite dimensional vector spaces are the primary object of consideration in linear algebra, so-called infinite dimensional vector spaces are the central object in a subject called operator theory, and Hilbert Space is to operator theory what $\mathbb{R}^n$ and $\mathbb{C}^n$ are to linear algebra. We need a few preliminary definitions in order to define a Hilbert Space. We will work over $\mathbb{C}$ (it is no more difficult to do so than to work over $\mathbb{R}$). We first define an inner product on a vector space $V$.  An inner product is just a generalization of the dot product on $\mathbb{R}^n$ or $\mathbb{C}^n$.  Recall the importance of the dot product: it gives us a notion of length, angle, and orthogonality.  So an inner product on an arbitrary vector space is a way of giving the space some geometry. An inner product is denoted $\langle \cdot , \cdot \rangle$, and we replace the dots with vectors to indicate that we’re taking the inner product of those two vectors.  Of course, there is a more rigorous, axiomatic definition.  For thoroughness, we state this definition, but it can be safely ignored without loss of understanding later on.  An inner product on a vector space $V$ is a function from $V \times V$ to $\mathbb{C}$ that satisfies the following four rules:

1. $\langle a + b, c \rangle = \langle a , c \rangle + \langle b , c \rangle$ for every $a, b, c \in V$.
2. $\langle \lambda a , b \rangle = \lambda \langle a , b \rangle$ for every $a, b \in V$, $\lambda \in \mathbb{C}$.
3. $\langle a , b \rangle = \overline{\langle b , a \rangle}$ for every $a, b \in V$.
4. $\langle a , a \rangle$ is real and greater than $0$ if $a \neq 0$.

Note that if we were working over $\mathbb{R}$, property (3) would just say that the inner product is symmetric.  We call a vector space with an associated inner product an inner product space. Recall that the definition of the dot product on $\mathbb{C}^n$ is $x \cdot y = \sum\limits_{i=l}^n x_{i}\overline{y_{i}}$, where $x_{i}$ and $y_{i}$ are the components of $x$ and $y$, respectively. The dot product satisfies all the properties above, and so it is an inner product on $\mathbb{C}^n$.  Once one has verified that the dot product on $\mathbb{C}^n$ is an inner product, it is not too hard to convince oneself that the extension of the dot product to $\ell_2$ is an inner product as well.  We define an inner product on $\ell_2$ by

$\langle x , y \rangle = \sum\limits_{i=1}^\infty x_i \overline{y_i}$

An example of a norm, just the usual distance function on the plane

The square summable condition we imposed on $\ell_2$ suddenly makes sense.  If we tried to compute the above inner product on sequences that are not square summable, we might end up with a divergent series on the right side of the equation – and we don’t want that! We define the norm of an element $v$ in an inner product space $V$ to be $\Vert v \Vert = \langle v , v \rangle ^\frac{1}{2}$. We will denote the norm on $\ell_2$ by ${\Vert \cdot \Vert}_2$.  Notice that if one applies this definition to $\mathbb{R}^n$, the norm of a point is just its distance in the origin.  So we think of a norm as a function that assigns lengths to vectors in our vector space.  In general, a norm is any function $\Vert \cdot \Vert: V \to \mathbb{R}$ that satisfies the following three axioms:

1. $\Vert x \Vert \geq 0$ for all $x \in V$, with equality if and only if $x = 0$.
2. $\Vert \lambda x \Vert = \lambda \Vert x \Vert$ for all $x \in V$, $\lambda \in \mathbb{C}$.
3. $\Vert x + y \Vert \leq \Vert x \Vert + \Vert y \Vert$ for all $x,y \in V$.

One can verify that any inner product induces a norm. Although we defined the norm in terms of an inner product, we say that any function satisfying (1), (2), and (3) is a norm, whether or not it is given in terms of an inner product. So, any inner product defines a norm, but not every norm is given by an inner product. For example, it is impossible to define an inner product on $\mathbb{R}^2$ such that the induced norm is $\Vert (x,y) \Vert = max\{ \vert x \vert , \vert y \vert \}$.

Sequences of rational numbers can ”converge” to irrational numbers, so the rationals are not complete

We need one more definition before we can define a Hilbert Space. We need the concept of completeness. This is a fundamental property of the real numbers – completeness is what allows us to do real analysis. Essentially a space is complete if there are no “gaps” in it. For example, $\mathbb{Q}$ is not complete because the sequence $3, 3.1, 3.14, 3.141, 3.1415, \ldots$ should converge, but it doesn’t (in $\mathbb{Q}$). Such a gap does not exist in $\mathbb{R}$, so we say the reals are complete. We are now in a position to define a Hilbert Space: a Hilbert Space is a complete vector space equipped with an inner product. A similar structure is a Banach Space, which is a complete vector space equipped with a norm. So any Hilbert Space is a Banach Space, but the converse is not true. We can immediately get our hands on some Hilbert Spaces: $\mathbb{R}^n$ and $\mathbb{C}^n$ are both finite-dimensional Hilbert Spaces. These are not particularly interesting Hilbert Spaces because they are finite-dimensional. But we are also ready to consider an infinite-dimensional Hilbert Space.  As we stated before, $\ell_2$ is a Hilbert Space.  It is not difficult to show that $\ell_2$ is a vector space, and we’ve already defined an inner product on it.  Showing that $\ell_2$ is complete does take a bit of work, but it’s doable.  We can also readily see that $\ell_2$ has no finite basis.  Indeed, an example of a basis for $\ell_2$ is the collection of sequences $e_{i} = (0, 0,\ldots, 1, 0, 0,\ldots)$ where the $1$ appears in the $i^{th}$ entry.  Of course, there are many other examples of Hilbert Spaces, but a somewhat remarkable fact is that every Hilbert Space that has a countable (indexed by $\mathbb{N}$) basis is isomorphic to $\ell_2$! For this reason, mathematicians sometimes refer to “the” Hilbert Space, as if there is only one. The upshot is that we can work exclusively in $\ell_2$ without sacrificing the generality obtained by referring to a general Hilbert Space.

A rotation about the origin is a linear operator on the plane

Since $\ell_2$ is a vector space, the natural thing to do is think about linear transformations of the space.  We define a linear operator on $\ell_2$ in the same way a linear transformation is defined in linear algebra. A function $T: \ell_2 \to \ell_2$ is a linear operator if

1. $T(x+y) = T(x) + T(y)$ for every $x,y \in \ell_2$.
2. $T(\lambda x) = \lambda T(x)$ for every $x \in \ell_2$ and $\lambda \in \mathbb{C}$.

It should be noted that not everything one may have learned about linear transformations in linear algebra is true for linear operators on $\ell_2$. For example, consider the shift operators $S$ and $S^*$ on $\ell_2$ defined by $S(x_1,x_2,x_3,\ldots) = (0,x_1,x_2,\ldots)$ and $S^*(x_1,x_2,x_3,\ldots) = (x_2, x_3,x_4,\ldots)$. It is easily verified that these are both linear operators, and that $S$ is injective but not surjective, $S^*$ is surjective but not injective, and $S^*S = I$ but $SS^* \neq I$. In linear algebra, one learns that all of these conditions are equivalent, but in Hilbert Space this is not the case.  An important part of operator theory is determining what kinds of operators on $\ell_2$ behave like linear transformations on a finite-dimensional vector space.

We call a linear operator $T$ on $\ell_2$ bounded if there is a constant $M$ such that $T$ is bounded on the unit ball $\mathbb{B} = \{ x \in \ell_2 : {\Vert x \Vert}_2 \leq 1 \}$ by $M$. The norm ${\Vert T \Vert}_{op}$ of a linear operator is defined to be the smallest such $M$ that works in the preceding definition. Equivalently, ${\Vert T \Vert}_{op}$ is the largest value of ${\Vert T(x) \Vert}_2$, where $x$ ranges over the unit ball in $\ell_2$. An interesting fact about linear operators on $\ell_2$ is that they are continuous if and only if they are bounded (an exercise!). We define $B(\ell_2)$ to be the set of all bounded (continuous) linear operators on $\ell_2$.

$B(\ell_2)$ is an interesting space in and of itself: equipped with the norm defined in the preceding paragraph, $B(\ell_2)$ is a Banach Space (a complete normed vector space) with respect to pointwise addition and multiplication by complex scalars. We have seen a little bit of analysis and algebra, so it’s time to introduce some topology to the mix. Our goal is to define and understand some topologies on $B(\ell_2)$. This should be a bit surprising. After all, what does it mean for a subset of linear operators to be “open”? There are many topologies that can be put this set, but we will consider the three most common ones: the norm topology, the strong operator topology, and the weak operator topology. In describing a topology on a space, it is difficult to pin down exactly what the topology is; this is because in most interesting spaces, there are so many open sets that it’s impossible to list all of them. Instead we can define a topology by describing what properties our set has when equipped with this topology. For example, we might say that a topology on a set $A$ is “the smallest topology such that our space $A$ has property $X$“. We can also define a topology in terms of a base which, roughly speaking, is a collection of open sets that generates the rest of the open sets (by taking unions). Before we embark on defining different topologies on $B(\ell_2)$, let’s stop and think about why we may need different topologies on the same set, and whether it is of real importance. A question one may ask is, “What properties of $B(\ell_2)$ will change when the topology changes?” As we will see shortly, the definition of convergent sequence changes drastically. It may not seem obvious that changing the topology will have a big effect on convergence of sequences; after all, the definition of convergence that one meets in a real analysis course does not explicitly mention open sets! But let’s examine this a little closer. In real analysis, convergence is usually defined in regards to a metric. In more general topological spaces, there may be no metric (although in Hilbert Space the metric is induced by the norm), so the definition from real analysis may not be applicable. Nevertheless, we can define convergence in terms of open sets thusly (and this definition works in every topological space, including metric spaces):

Take an open interval about 1 on the vertical axis and eventually, all but finitely many points are in this interval

Let $(x_n)$ be a sequence in a topological space $X$.  We say $x_n \to x$ if for every open set $U \subset X$ containing $x$, we have $x_n \in U$ for sufficiently large $n$. It is clear, now, that convergence depends on the definition of open set. As we introduce new topologies on $B(\ell_2)$, we can describe what convergence “means” with respect to this new topology.

The norm topology on $B(\ell_2)$ is the topology induced by the operator norm. To explain what this means, let us consider that any normed space has a corresponding topology induced by its norm. Think about $\mathbb{R}$ for example. The norm of a point in $\mathbb{R}$ is

The open set O(1.5, 1.5)

just its absolute value. Think about the subsets of $\mathbb{R}$ defined by $O(x,\epsilon) = \{ y \in \mathbb{R}^2 : \vert x - y \vert < \epsilon \}$, where $x \in \mathbb{R}$ and $\epsilon$ is a positive real number. Each set is an open interval centered at $x$ and of radius $\epsilon$. The open sets in $\mathbb{R}$ are open intervals and unions of open intervals, so the collection $\{O(x,\epsilon) : x \in \mathbb{R}, \epsilon > 0 \}$ is a base for the usual topology on $\mathbb{R}$. Now we return to our set $B(\ell_2)$, where the norm topology will be defined analogously. The collection of all subsets of $B(\ell_2)$ of the form $O(T, \epsilon) = \{ S \in B(\ell_2) : {\Vert S - T \Vert}_{op} < \epsilon \}$ is a base for the norm topology on $B(\ell_2)$.  Remember that a norm is a way of defining length or distance in our space.  So the set $O(T, \epsilon)$ is the set of all operators that have distance from $T$ less than $\epsilon$.  It probably seems odd think about the distance between two functions – this is why we need careful and precise definitions of norms and, in particular, the operator norm.  The norm topology is a very important topology on $B(H)$ indeed – it is the topology which makes $B(\ell_2)$ a Banach Space.

Before looking at any special properties of the norm topology, we introduce the next topology on $B(\ell_2)$ because the interesting thing to do is to compare the different topologies. Next we consider the Strong Operator Topology (SOT). The SOT is defined to be the smallest topology containing all sets of the form $U(T,x,\epsilon) = \{ S \in B(\ell_2) : {\Vert S(x) - T(x) \Vert}_2 < \epsilon \}$ where $T$ is any bounded linear operator, $x$ is any element of $H$, and $\epsilon$ is any positive real number. Equivalently, SOT is the smallest topology on $B(\ell_2)$ such that the evaluation maps $T \mapsto T(x)$ are continuous for every choice of $x \in \ell_2$. A word of caution: The sets $U(T,x,\epsilon)$ may seem very similar to the sets we defined in the previous paragraph, but they’re not. Notice that we use the $\ell_2$ norm here, and the operator norm in the preceding paragraph. It is important to keep track of which norm function is being used and what quantity is inside the norm – of course, it wouldn’t make sense to take the operator norm of the quantity $S(x) - T(x)$! We can describe some of the properties of the SOT. The SOT is (somewhat paradoxically) weaker than the norm topology; that is, there are more open sets in the norm topology than there are in the SOT. The SOT is perhaps a more natural choice of topology on $B(\ell_2)$. To explain this, I first pose a question: what does it mean for a sequence of bounded linear operators $(T_n)$ to converge to an operator $T$? Well, it depends on which topology you use! In the SOT, the sequence $(T_n)$ converges to $T$ if for every $x \in \ell_2$, the sequence $(T_n(x))$ converges to $T(x)$. That is, convergence in SOT means that a sequence of operators converges pointwise to some operator. This indeed seems like a very natural definition of convergence. Contrast this with convergence in the norm topology: the sequence $(T_n)$ converges to $T$ in the norm topology if ${\Vert T - T_n \Vert}_{op} \to 0$.  In a way, this definition of convergence seems more complicated and less natural than convergence in SOT.  This already is an advantage of using SOT instead of the norm topology. We mentioned that SOT is weaker than the norm topology. It isn’t too difficult to show that convergence in the norm topology implies convergence in SOT (for the reader who wants a challenge: assume ${\Vert T_n - T \Vert}_{op} \to 0$. Pick $x \in \ell_2$ and show $T_n(x) \to T(x)$). Using the given definitions of convergence in each topology, we can show that the converse is not true. Consider the following sequence of operators $(P_n)$ on $\ell_2$:

$P_n(x) = \sum\limits_{i=1}^n \langle x , e_i \rangle x$,

where $\{e_i\}$ is the basis we defined earlier. The operators $P_n$ are called projections, because they take an input $x$ and project $x$ onto the linear span of the first $n$ basis vectors. It is not hard to see that as $n \to \infty$, we have $P_n(x) \to x$, i.e. $P_n \to I$ in SOT ($I$ is the identity operator). However, the claim is that $P_n \nrightarrow I$ in the norm topology.  We will just sketch a proof here.  Let $m,n \in \mathbb{N}$ with $m > n$.  Then find a lower bound on ${\Vert P_m - P_n \Vert}_{op}$ (a bound of 1 is easy to obtain by picking the unit vector that has a $1$ in the $m^{th}$ entry and else all zeroes).  What this tells us is that every element of the sequence is at least distance 1 from every other element of the sequence, and clearly no sequence with this property can converge.

The third and final topology we introduce on the space $B(\ell_2)$ is the Weak Operator Topology (WOT). The WOT is the smallest topology on $B(\ell_2)$ containing the following sets $U(T,x,y,\epsilon) = \{ S \in B(\ell_2) : \vert \langle T(x) - S(x) , y \rangle \vert < \epsilon \}$, where $T \in B(\ell_2)$, $x, y \in \ell_2$ and $\epsilon$ is a positive real number. Equivalently, the WOT is the smallest topology such that the map (called a linear functional) $T \mapsto \langle T(x) , y \rangle$ is continuous for any choice of $x, y \in \ell_2$.  So a sequence of operators $(T_n)$ converges to an operator $T$ if $\langle T_n(x) , y \rangle \to \langle T(x) , y \rangle$ for every choice of $x, y \in \ell_2$.   In order for the names given to these topologies to make sense, we had better hope WOT is weaker than SOT. Alas, this is indeed the case. Again, it is not hard to prove that SOT convergence implies WOT convergence (the only part that may be difficult is to show that an inner product is continuous). Again we can show the converse does not hold. Recall the definition of the shift operator $S$ on $\ell_2$. Define $S_n$ by composing $S$ $n$ times. That is, $S_n(x_1, x_2, x_3,\ldots) = (0, 0,\ldots,x_1, x_2, x_3,\ldots)$ where the sequence on the right starts with $n$ zeroes. First we can show that $S_n \nrightarrow 0$ in SOT. Consider $x = (1,0,0,\ldots)$. Then the sequence $(S_n(x))$ does not converge to the $0$ sequence. To see this, take any $m,n \in \mathbb{N}$ with $m \neq n$. Then $S_m(x) - S_n(x)$ is a sequence with $1$ in the $m^{th}$ entry and $-1$ in the $n^{th}$ entry, hence we have ${{\Vert S_n(x) - S_m(x) \Vert}^2_{2}} = 2$. Since this is true for any choice of $m$ and $n$, the distance between any two distinct points in the sequence $(S_n(x))$ is $\sqrt{2}$.  So the sequence does not converge to any limit, including $0$. It is harder (but not too difficult) to show that $S_n \to0$ in WOT. The reader who wishes to provide a proof of this statement may want to read about linear functionals and the Riesz Representation Theorem.

Of course, there is much more to say about Hilbert Space (and even about $B(\ell_2)$ than I could fit into this post.  Hilbert Space could easily be the sole focus of a semester- or even year-long course.  In his Mathematics: a Very Short Introduction, mathematician Timothy Gowers wrote, “The notion of a Hilbert Space sheds light on so much of modern mathematics, from number theory to quantum mechanics, that if you do not know at least the rudiments of Hilbert Space theory then you cannot claim to be a well-educated mathematician.”  Hopefully the reader leaves with an appreciation for the fact that Hilbert Space is a (relatively) easy space to understand and that algebra, analysis, and topology are all lurking around in Hilbert Space.

The author Dan Medici was a student in Scott Taylor’s Fall 2014 Topology class at Colby College.

This entry was posted in Uncategorized. Bookmark the permalink.

• ## Using Configuration Spaces to Find Inscribed Squares

As an undergraduate in mathematics, every once in a while, one of your math friends will send you a link to a very interesting unsolved problem in mathematics.  I made the mistake of clicking on one, because after reading it, it captivated my mind for weeks: “The Inscribed Square Problem.” Now, this conjecture says that for any simple closed curve (Jordan curve), there is a square whose corner points all lie in the curve. On first examination, I thought to myself, “wow there’s no way this is true, there are some pretty messed up curves out there, and I bet there’s at least one of them where this does not hold.” So I went to talk to my topology professor about this and we talked about a method of approaching this problem using configuration spaces, which I will talk a little bit about in this blog post.

First we will start off by explaining exactly what a configuration space is. A configuration space is a way to topologically represent how objects can be placed and moved around within certain spaces. For example, if you have a circle and you want to place two points on it, you might start by thinking that for every place you put your first point, the places that you could place the second point can be represented by a circle with a point removed (because both points cannot be in the same place), and so it turns out that the configuration space of two points in a circle (denoted $C^2(S^1)$ where $S^1$ is the circle and the superscript 2 denotes how many bodies are in the space) is $S^1 \times(S^1 - \{a\})$ where a is a point on the circle. Now this is interesting, because $S^1 \times S^1$ is an interesting construction called the torus (it’s pretty much just a doughnut):

However, removing a point from the second circle transforms it into a line segment

so you end up with something similar to $S^1 \times (S^1 - \{a\})$ which looks like the result of rolling a piece of paper up. (Something akin to the outside shell of a hollow cylinder without the circles on the ends)

Now, while you may believe me when I say that each point on this gives a place for two positions on the circle, let us examine how this actually works, here I have drawn a circle with two points A and B on it (I have also drawn an arrow at the top as a reference point).  First let us choose our A position.  The place around the cylinder determines where our first point should go.  We want to place our A point somewhere on the cylinder where the dashed-and-dotted line is because that is where A is in relation to our point of reference (note that if we were to look at the cylinder from the top, that line would correspond exactly to where A is).  Now, the height at which we place our B point on the cylinder is determined by where in relation to A it is.  Here we can see that B is a little after A if we head clockwise around the circle.  So we can place B a little bit away from the top to get the point shown on our cylinder.  Note that this also demonstrates why the bottom and top of our cylinders are open, because as we get to the edges of the cylinder, we get closer and closer to the A point, but can’t actually reach it.  If we could, we could say that the top and bottom of our cylinder were essentially the same circle and “glue” them together to get the torus.

Now, a Jordan curve in the plane can be described as the image of an injective continuous function from the unit circle to the plane. Knowing that our goal is to try and determine whether it has an inscribed square, we should start by examining how 4 points can be configured on our curve, that is $C^4(\phi(S^1))$ where $\phi$ is our injective continuous function. Now, because our curve is continuous and does not cross over itself, it is essentially just a circle which has been squished and pulled to make it our circle, so by reversing our process (finding a continuous function which when composed with $\phi$ gives us a circle), we can deform it back into the circle:

and by doing this, we can notice a few things about the structure of our configuration space. Firstly we already know how to place 2 points on the circle, but we can also realize that placing four points on the circle is exactly the same as placing 2 points on the circle twice! (This is fairly obvious in real life, but its mathematical meaning has a bit more significance) that is

$C^4(S^1) = C^{2}(C^{2}(S^{1}))$

So, we can look at the configuration space of $C^2(\phi(S^1))$ and notice that it will be equal to

$C^{2}(C^{2}(S^{1})) = (C^{2}S^{1}))\times(C^{2}(S^{1})-\{a\})$

So what on earth does this mean? It means that for every point in one of our “cylinders” we can represent two point on the circle by placing one point in our cylinder-like construction and then placing our second point on a different cylinder-like construction with a point missing (Taking the cross product of the two spaces)

Alternatively, you could just declare your configuration space to be

$C^{4}(\phi(S^{1})) = \{(a,b,c,d)\in S^{1} | a\ne b\ne c\ne d \}$

But I find the first definition to be much easier to picture in my head than the second succinct but abstract one.
So, now that we have a rough picture of a configuration space for if our curve was a circle, remember that we simplified this by stretching it into a circle, now we can translate it back to our initial curve, $\phi$, by twisting and bending every circle that we encounter back into our Jordan curve (slightly more formally, we have been composing $\phi$ with a function which continuously deforms it into a circle.  At this point, we stop composing $\phi$ with that function).

Now, let us talk briefly about how we can define some fairly useful functions on configuration spaces.  First let’s look at the distance function $d:C^2(S^1)\rightarrow \mathbb{R}$.  First let us not that this function is continuous, if we change our point in the space by a tiny bit, the distance between the two points will not change drastically.  Also we can see that the closer you get to the edges of the cylinder, the closer the two points are (at the edges, they would occupy the same space), so from this, we can see that the maximum distance is the ring in the very center of our cylinder.  This is a very neat way of seeing that the points in the ring in the center of our cylinder occur exactly when our two points on the circle are placed opposite each other.

We can now define very useful function $f$ from $C^4(\phi(S^1))$ to the set {0,1} such that a point $x \in C^4(\phi(S^1))$ is mapped to 1 if one of the components (the points coming from each mutilated circle) $x_1$ is a distance c away from $x_2$ and $x_3$ and is a distance $c\sqrt{2}$ away from the third one, and furthermore, that $x_3,x_1,x_2$ form a right angle and that $x_1,x_2,x_4$ form a right angle. This will ensure that any point in the configuration space that would make a square in the original curve (remember that the configuration space has coordinates for four points on the curve) gets mapped to 1. Now, we can proceed from here in several different ways, we could take the preimage $f^{-1}(1)$ and determine if it is not empty, or we could define the topology on our configuration space to be the indiscrete topology, (the one where the only open sets are the empty set and the entire space), this has the benefit that the only functions which are continuous are constant functions. So, since there will be at least one point in our configuration space which gets mapped to 0 (otherwise every set of four points is an inscribed square, which is obviously not the case), so if $f$ maps a point to 1, it will be discontinuous, and so all we need to do is check to see if f is continuous.

Now, this is easier said than done, the nature of this function $f$ is such that determining whether it is continuous could be just as difficult as determining the truth of the original statement using geometric means. However, topology has many different ways of determining continuity, so it could just be that someone could come along and prove that this function is always discontinuous (meaning that the conjecture holds) or they use this method to construct a curve where our function is discontinuous (the conjecture does not hold)

We could also define a continuous function $f^\prime:C^2(S^1)\rightarrow \mathbb{R}^6$ whose components are the distances between two respective points.  We’ve already seen that the distance component is continuous, and so since its components are continuous $f^\prime$ will be continuous.  Now, we just have to see where in $\mathbb{R}^6$ the function would satisfy the conditions.  This is not too difficult, it is fairly common knowledge that for the four points in a square, the distance between four pairs of them will be equal, and the distance between the other two pairs will be equal as well.  So, any point in $\mathbb{R}^6$  where 4 of the components are equal and the other two are equal as well will do.  Now, since $f^\prime$ is continuous, we have many tools at our disposal to determine whether or not there is a point in its range which satisfies the conditions for being a square.

For more information on the inscribed square problem and what has been proven about it, visit this website

<i>Professor’s note:</i> Joseph took Topology from me (Scott Taylor) in the Fall of 2014. Although there some inaccuracies in the exploration of configuration spaces above, I was quite taken with the refreshing approach and tone of the piece, so I have left it unedited.

This entry was posted in Uncategorized. Bookmark the permalink.

• ## Algorithms for Working with Triangulated Surfaces

Let’s imagine that you and your friends just took out a steaming pepperoni pizza out of the oven. How would you go about triangulating (divide using triangles) the surface (the pizza) into equal pieces? This shouldn’t be to hard, should it? But what if someone took a knife and placed a couple of points on the pizza, and said the triangulation has to contain triangles that have those points as vertices. How would unite the dots, making sure that the triangles you get yield the fairest division? Not so easy is it?

This is a problem that most graphics software engineers encounter. But their conundrum is even more complicated as they deal with millions of points located in 3D space, and the process they’re using has to be automated and work for every possible case. Because we will use this problem to guide us through the concepts presented in this post, we should first offer a clear description of the problem and of the solution we are looking for. In Computer Graphics, models (let’s say a human face) are made of thousand of patches that consist of a fixed number of points (usually numbers that are perfect squares). These points keep track of their position in 3D space (these are called world coordinates, as they lie in the coordinate system of the model). Because the computer programmer wants to create a realistic human face while making his program fast, he or she devises an algorithm that subdivides the patches into subpatches that have less than a certain distance in screen coordinates between adjacent points (i.e. the distance between two points on the screen will be smaller than an certain limit). This way, instead of having nice patches made out of 16, 25 or 36 points, we end up with all sorts of random configuration of points. And we have lots of such configurations. We are interested in finding an algorithm that, after the aforementioned subdivision, is able to create a triangulation of all the points in the model, while rendering an image as realistic as possible. By realistic, we understand that we don’t want our triangles to be too skinny, too big or too small, because that would create a deformed face (not that every face isn’t beautiful in its own way). Also, we are not allowed to have edges crossing each other (because that wouldn’t be a triangulation anymore), and we are not allowed to add new points.  To keep the problem simple, we will ignore things like aliasing and hidden surface removal, and we will also reduce our example to two dimensions. The presented method works in all dimensions, and the problem can actually be reduced to two dimensions by creating a bounding cube around the object and reflecting the points onto the closest face).

This is the kind of result we are looking for. Note that in this case, a different type of subdividing from the one we presented is used. The points are more dense in regions were the protuberances of the faces are more pronounced.

This is how we can reduce the problem from three dimensions to only two dimensions.

A mathematical structure that encompasses all of the above requirements is the Delaunay Triangulation. Before jumping into any algorithms, we shall first try to gain a mathematical understanding of Delaunay Triangulations. We can define Delaunay Trinagulations in two ways:

• Geometrically,  a Delaunay triangulation for a set P of points in a plane is a triangulation DT(P) such that no point in P is inside the circum-circle (the unique circle that passes through each of the triangle’s three vertices) of any triangle in DT(P) .
• Topologically, a Delaunay triangulation of a ﬁnite set ${{S}\subseteq \mathbb{R}^n}$ is isomorphic to the nerve of the Voronoi diagram of ${{S}}$.

As with most things in life, let us first ignore the harder definition and focus on the geometric one. The following image should make the definition clearer:

As you can see, the first picture is a Delaunay Triangulation because there are no points within any of the four circumcircles.

Because for our set ${{S} = \left\{ {A,B,C,D,E}\right\} }$ no points lie within the circumcirlces of triangles ${\Delta ABC,\Delta ACE,\Delta CED,\Delta BCD}$, then ${{DT(P)} = \left\{\Delta ABC,\Delta ACE,\Delta CED,\Delta BCD\right\}}$. Note that the triangulation of a set of points is a set of triangles. This definition is clear and easy, and it will be the one we will use when implementing our algorithm. However, why this specific triangulation works for our imposed conditions is not that apparent. If we take a look at the three triangulations above, we can observe that the Delaunay Triangulation is the most ‘aesthetically pleasing’ one, in the way that we don’t have long, slim triangles and that we only connect points that are close to each other. As it turns out, this ‘aesthetically pleasing’ property is given by the fact that Delaunay Triangulations maximize the minimal angle. In other words, the minimal angle of all the triangles in a Delaunay Triangulation of a set  ${{P}}$ , will be larger than the minimal angle of all the other triangulations of  ${{P}}$. Why does the property that no point of ${{P}}$ lies within the circumcircle of any triangle maximize the minimal angle? Pick a triangle in our triangulation and look at its least angle. Observe that as we move the vertex at that angle away from the center of the circle, two things happen: the circle increases in area along with the odds of another point of the set entering the circle, and the angle further decreases. So, because we are trying to form triangles with circumcircles that are as small as possible (ATTENTION: this is only an implication that is generally true, but it isn’t by any means a requirement, as Delunay triangulations don’t concern minimizing the edge length),we are ensuring that our triangulation connects points that are close and that we are avoiding ‘ugly’ triangles. This makes the Delaunay triangulation a perfect solution to our problem. Other properties of Delaunay Triangulations that we will take for granted are: every set of points in the Euclidean Space has a Delaunay Triangulation that is unique if no two points lie on the same sphere, the union of all the triangles form the convex hull of the set of points (i.e. the minimum convex set containing all the points in the set or a rubber band stretched using the points of the set so that it contains all of the points in the set in its interior).

Now let’s turn our attention towards the topological definition of a Delaunay Triangulation. At a first glance, the definition seems discouraging, but as we will set out to explain the terms, we will see that the sky isn’t that gray. The first word of the day is ‘isomorphic’, which for all intents and purposes means ‘the same’. The second math term is ‘nerve’. Lets look at the picture below and try to make sense of it:

The nerve(red) of a set of triangle (green)

Given a union of triangles ${{T_i}}$, we can form its nerve ${{N}}$ by following these steps. Start with  ${{N}}$ empty, and for each triangle in the union associate one point ${{t_i}}$ and add it to ${{N}}$. Then, look at non-empty intersections of the triangles(non-empty means that they share at least a point), and for every point shared by at least two triangles add a new set formed with the ${{t_i}}$‘s corresponding to the triangles that share that point. In this process you cannot repeat sets. If you correctly cover all the possible intersections, ${{N}}$ will be the nerve of the union of triangles. Observe that ${{N}}$ is a set containing sets of one or more points, sets which we can graphically represent through points, edges and polygons as seen in the picture above. The final unknown term is “Voronoi diagram”. Again, pictures comes in handy:

A nicely colored Voronoi Diagram of 20 points.

We form the Vornoi cell of a point P by taking the intersection of all the half-spaces that contain P.

The Voronoi diagram(the whole first picture) of a set of points(the black points) ${{S}\subseteq \mathbb{R}^n}$ is the collection of all the Voronoi cells(the colored polygons), denoted by ${{V_u}}$, where ${{u}}$ is a point of ${{S}}$ and ${{V_u} = \left\{x\in\mathbb{R}^n\mid \|x-u\| \le \|x-v\|,v\in\mathbb{R}^n\right\} }$. This definition tells us that every point in the cell ${{V_u}}$ is closer to ${{u}}$ than it is to any other point in ${{S}}$ and that the points on the edges of the diagram are equally distanced from the points that generate incident Voronoi cells.  So, using this definition, we can form the Voronoi cell of a point ${u\in{S}}$ by dividing the plane, for each other point ${v\in{S}}$, into two pieces(a.k.a. ‘half-spaces’) using lines that are equally far away from ${{u}}$ and ${{v}}$. Then, if we take the intersection of all the half-spaces that contain ${{u}}$, we will end up with ${{V_u}}$. Although the definition allows for building Voronoi diagrams for spaces with dimension greater than 2, it turns out that for computational purposes this is not feasible process, as it a huge amount of time and storage space.

Stereographic Projection

To plunge even deeper into topology, we present two more constructions for the Voronoi cells. To do this, we will go down one more dimension to create some visual intuition of the constructions, and then let the reader work his newly gained knowledge by extending the example to two dimensions. Use the picture bellow for reference. The Voronoi Diagram of a set ${{S}\subseteq \mathbb{R}^1}$ is nothing more than a segmented line, where the segments are the Voronoi cells(in our drawing, the Voronoi diagram of the set ${{S} = \left\{ {a,b,c,d}\right\} }$ is the segmented equator). We will lift our Vornoi cells to two dimensions by using stereographic projection. Intuitively, the stereographic projection of circle(sphere for two dimensions) is the shadow of its points cast by a single light on the surface of the circle onto a line(plane in two dimensions). By casting shadows, we mean picking a point ${{N}}$ and drawing lines from it that intersect both a point on the circle and the line . This creates a mapping( an isomorphism, if you will), between the circle minus the point ${{N}}$ and the line. So, we draw a circle that has our space as its equator, and take the north pole as our point ${{N}}$. Using the inverse of the stereographic projection of the circle(i.e. we start from points on our space and draw lines that go through ${{N}}$ and intersect the circle(the brown lines in our drawing)), we map our set ${{S} = \left\{ {a,b,c,d}\right\} }$ onto the circle. For the first construction, we will draw tangent lines to the circle at the newly obtained points. These are the Pa,Pb,Pc,Pd in our drawing. Look carefully at their intersections. It seems that if we were to draw a line connecting the intersecting points and ${{N}}$, we would intersect the line at the boundary of the Voronoi cells of the points that yielded the tangent lines. This turns out to be true. It is also true that if we draw lines from ${{N}}$ to the stereographic projection of the points in our space, the line which we will first intersect, corresponds to the Voronoi cell to which the point belongs. For our second construction, we can build circles(Ca,Cb,Cc,Cd) that contain both ${{N}}$ and the points in ${{S}}$ and that are tangent to the equator. Take a moment to convince yourself that these circles are unique. Again look at the points of the intersections of the circles and remark that a line containing ${{N}}$ and any of these points will also contain the boundary of two Voronoi cells. Thus, the first intersection of the segment connecting a point in our space and ${{N}}$ is with the circle corresponding to the Voronoi cell to which the point belongs.

How to construct Vornoi cells using lifting

Having our terms all sorted out, it becomes apparent what the second definition means. Broadly, it tells us that by drawing edges between the points that generate two neighboring Voronoi cells, we will get a Delaunay Triangulation of the set of points. Observe that the edges we are drawing to geometrically represent the nerve of the Voronoi diagram are always perpendicular to the boundaries of the cells. Just try for a moment to draw a Voronoi diagram that yields triangles with small angles, and you will begin to see why this property maximizes the minimal angle. The only problem would be having more than 4 cells meeting at a point. As it turns out, this is equivalent to four points lying on the same circle, which, as we’ve stated in the first part, makes for having more than one Delaunay Triangulation.

These constructions are less intuitive and you might ask why do we need them when we already have something as simple as the first definition of a Delaunay Triangulation. The reason is that there exist algorithms such as Fortune’s Algorithm or Bowyer-Watson Algorithm that generate Delaunay Triangulations using Voronoi cells. These algorithms prove to be more useful as they can create Vornoi diagrams which have multiple applications across a vast array of domains.

Delaunay Triangulation derived from a Voronoi Diagram

Now that we have a strong theoretical basis, let us focus on one algorithm for creating a Delaunay Triangulation. Note that there are a lot of algorithms for doing this, but the one that we will be presenting is one of the simplest and most time efficient. The algorithm that we choose to implement employs the “divide and conquer” strategy.

Let us start with a set of random points ( we will work with an example that has 12 points to gain a better intuition). We begin by ordering them with respect to their x-coordinate. Also, if two points have the same x-coordinate, their ordering is determined by their y-coordinate in increasing order.

This our example of 12 points with the labeling imposed by our ordering.

We continue by subdividing the points into halves using their labeling, until we are left with sets of two or three points. If we can’t split a set into two equal sets, we let the first subset to have one more element then the second. We then triangulate the newly formed sets by creating triangles in the case where we are left with three vertices, and edges in the case where we are left with two vertices.

The way we divide the set of points and the triangulations we can form. The thickness of the black lines indicates the order in which we divide starting from thickest

By taking a look at the picture, we can observe that we obtain a bunch of triangles with sharp angles which should give us an idea that most of the triangles formed in these first steps are not part of the Delaunay triangulation. However, as we have discussed earlier, the triangles in a Delaunay triangulation tend to be small, so it is very likely that some of the edges coincide. For a large number of vertices, this a huge time saver.

The next step is to merge neighboring sets of points by adding edges in the opposite order in which we have divided them. We will use the following notation to distinguish between edges: LL are edges that were formed using vertices from the left division, RR are edges that were formed using vertices from the right division, and LR are edges that were formed using vertices from both. We will try to now merge the first two divisions. For now we only have LL and RR edges. Throughout the process we will delete LL and RR edges but never add more, and we will try to add LR edges that are as good as possible. Remember that union of the triangles in a Delaunay triangulation of a set of points forms the convex hull of that set of points. Thus, we can safely assume that our first LR edge, which will certainly be in the final triangulation, is the edge between the two points with the smallest y-coordinate of the two divisions. Observe that this is also true for the upper part of the set of points.

Now it’s time to look for the next LR edge that can only be added above the previously created LR. To get a triangulation, we need this edge to start at one of the vertices of the previously added edge. Thus, we are looking for an vertex that forms with the previous LR edge a triangle whose circumcircle does not contain any other points. By the existence of a Delaunay triangulation and by its uniqueness(if we don’t have four co-circular points) we are guaranteed that such a point exists and that it is unique. We will look at the possible candidates and pick the best one from each side and then the best one from the two. Let us start with the right side. We will look at the vertices that share an edge with point 5 and pick the ones that form the two smallest angles with the previously added LR edge. The vertex associated with the smallest angle will be the Current Potential Candidate(CPC) and the other vertex will be the Next Potential Candidate(NPC). If our CPC fullfils the two following criteria we found our candidate for the right side :

• The clockwise angle from the base LR-edge to the potential candidate must be less than 180 degrees. (This ensures that we have traingles and that we don’t go outside the convex hull)
• The circumcircle defined by the two endpoints of the base LR-edge and the potential candidate must not contain the next potential candidate in its interior. (This is the Dealunay criterion that no circumcircle contains a point in its interior)

If our CPC doesn’t fullfill the criteria, we set CPC to NPC and then get the next NPC by looking at the next vertex in order of the angle mentioned above. We repeat this process until we either find a good candidate or we run out of candidates. If we do run out of candidates, the best candidate from the other side will win. If neither side has a candidate, then our merge is complete.

The process for the right side is similar, but instead of point 5 we use point 2 and we measure the angle at point 2 counter-clockwise. If we candidates from both sides, we repeat the circle test and pick the point for which the other point is not in the circumcircle. Be the existence of the Delaunay triangulation, we are guaranteed that such a point exists.

Once we get a “winner” vertex, we delete any vertex that intersects the newly formed LR edge.

We repeat this process until we have completed the merge, then move on through all the merges until our triangulation is complete. Note that any step of the way, we can delete previously added edges, so don’t assume that any of the created LR edges will be part of the final triangulation.

I will display the process for the first merges and then just display the result of the second and third merges:

Vertex 3 and vertex 4 are the candidates from each side, but vertex three obviously wins

We add the new edge and repeat the process

Right side:
We start with 4 but fail the test so 6 is selected.
Left side: we can’t pick 2 because the angle is more than 180, but 1 works.
Of the two candidates 6 wins.

We add the new edge. Note the deletion of the RR edge.

Observe that we have 4 co-circular points, so we can pick either 34 or 16 as our edge

We add the final two edge. The last one doesn’t require any computation.

The finite Delaunay Triangulation of our set of points. A true beauty!

Triangulations seem like an easy mathematical concept, but things get a lot more complicated when you only have simple instructions at your disposal. Next time you want a brain teaser, try to forget everything you have just read, and attempt to create an algorithm that triangulates ( not even a Delaunay Triangulation) the convex hull of a set of points. You will see how things that you can easily do with a pen and a piece of paper become a lot harder to translate into instructions that work for all cases and that a machine can understand. That’s why computer science requires a vast knowldge  of mathematical concepts that are able to describe the same object or process into different modes, allowing the programmer to pick a method that can be transformed efficiently into code.

This entry was posted in Uncategorized. Bookmark the permalink.

• ## The Long Line

Topology can be best described as the study of certain “spaces” and the properties they have. Now it is important to figure out what spaces are essentially the “same” and which are different. We define two spaces to be the “same” if we can transform one into the other continuously, and the transformation we preformed can be undone continuously as well. Now you may be asking, “what exactly do you mean by a ‘space’?” A topological space is defined as a set $X$ with an associated set $\mathscr{T}$ consisting of subsets of $X$ which satisfies certain properties. The elements of $\mathscr{T}$ are declared to be the open sets of our topological space $(X,\mathscr{T})$.

Now a major aspect of topology is to define properties that different spaces could have and what these properties should “say” about a space. For example, one may want to determine when a space is connected together or when it can be broken up into different pieces. Or one may wish to determine when any two points in a space can be connected together by a path through the space. Now at first glance these two definitions seem to be describing the same property but in fact they aren’t. The first definition describes when a space is “connected” and the other when a space is “path-connected.” It turns out that “path-connected” is a stronger claim about a space than just “connected.” In other words, there are space which are connected but not path-connected, for example The Topologist’s Sine Curve . However every path-connected space is also connected. One may begin to wonder what other properties in topology share this type of connection. In other words, which properties imply other properties and which do not. Now to show that one property implies another, one must start from the most general assumptions and come up with some mathematical proof. However to show that some property does not imply another, one must simply come up with a counter example. It is the later strategy that this blog is concerned with. I will be discussing a particular topological space, “the long line,” that can be used as a counter example to certain properties of a space, namely different levels of “compactness.”

Before we begin discussing the long line it will be useful to have an overview of an order topology. Now on the real line $\mathbb{R},$ the order topology ends up coinciding with the usual definition of open set, namely the union of open intervals. The key property of the real line that allows us to have this definition of open intervals is that it is totally ordered. This simply means that given any two points $a,b \in \mathbb{R}$, either $a\leq b$ or $b\leq a$. It turns out that we can define an order topology on any set which is totally ordered by some relation $\leq.$ Given a totally ordered set $(X,\leq)$ we can define an order topology on $X$ by first letting $\mathscr{T}''$ be the set consisting of all sets of the form $\{y : y < a\}$ and $\{y : b for any $a,b \in X$. We then create another set $\mathscr{T}'$ of all the finite intersection of elements of $\mathscr{T}''$ and then let our topology $\mathscr{T}$ be all the sets which can be expressed as the arbitrary union and finite intersection of elements of $\mathscr{T}'$. The reader should think about this construction in terms of the real line and note that we end up producing all the open intervals and unions of open intervals of the real line. Refer to the image below to see how the construction comes together.

Example of the creation of an open interval with elements of T”.

We are almost ready to construct the long line, but first we must make one more detour, into the world of set theory. The principle object we will use in our construction of the long line is the ordinal. Ordinals are just a very special type of well ordered set. Now a well ordered set is very similar to a totally ordered set with the additional property that every non-empty subset has a minimum element. An amazing fact from set theory is that every set can be well ordered. It turns out that the ordinals can be thought of as the standard well ordered sets. In fact, every well ordered set can be put into a bijective correspondence which preserves order with a unique ordinal. Now you may be wondering what’s so special about these ordinals. An ordinal  $X$ can be defined as a well ordered set with the property that each element $a \in X$ is exactly the set of all elements in $X$ which precede $a$. In other words, $X$ is an ordinal if for every element $a \in X$, $a = \{x \in X : x. The you may be wondering if such a thing even exists. Refer to the images for a glimpse of the finite and the first few infinite ordinals. You may be interested in a more thorough description of ordinals, which can be found here.

The first few finite ordinals.

The first few infinite ordinals.

Now it turns out that inclusion will always be the well order on an ordinal. It also turns out that there are a lot of ordinals. In fact the collection of all ordinals is not even a set! Naively we can think that there are just too many ordinals for them to be a set. Now as seen above there are ordinals with an infinite number of elements. In fact the first infinite ordinal can be used to make sense of the natural numbers. We often denote the first infinite ordinal as $w$. Amazingly there are different sized infinities, and $w$ can be thought of as the “smallest” infinity. Sets which can be put in a bijective correspondence with it are deemed “countable.” The next size of infinity is known as “uncountable” and we will let $\Omega$ stand for the first uncountable ordinal.

After the long build up we are finally ready to define the long line. The long line can be thought of as taking uncountably many copies of the interval $\lbrack 0,1)$ and “stacking” them end to end. For comparisons sake, we can think of the positive real line as countably many copies of the same interval “stacked” end to end. The long line must be very long indeed! While this definition may provide a good image, it leaves little to work with as far as properties go. Here is a more precise definition, the long line $L$ is the cartesian product $\Omega \times \lbrack 0,1)$ where the elements are ordered lexicographically. In other words, given two elements $(\alpha, a)$ and $(\beta,b)$ with $(\alpha, a)\leq (\beta,b)$, either $\alpha \leq \beta$ or in the case of equality, $a \leq b$. It is easy to see that this is a total order and so we can construct the order topology on $L.$ While this definition may seem strange, it is actually very easy to visualize. Take the set of all non-negative real numbers as an example. We can think of this set as the cartesian product $\mathbb{N} \times \lbrack 0,1)$ (keeping in mind that the natural number $\mathbb{N}$ can be fully described by the ordinal $w$). First note that we can think of elements $(n,d)$ of our set as telling us first the integer part of the number and then the decimal part. Now I ask the reader to consider how they would compare the size of two different positive real numbers. First you would compare the integer parts, and if they were equal you would then move on to the decimal parts. That’s comparing lexicographically! So the long line $L$ is just a much “longer” version of that example. The image below provides a description of our analogy to the long line, unfortunately it is very difficult to create a visual for an uncountable well ordered set.

The real line as a cartesian product.

Now you may wonder, “how much longer is the long line?” Perhaps the best way to compare the “length” of these lines is by looking at sequences. It is common knowledge that any strictly increasing sequence of real numbers does not converge. This is easily seen and accepted and it may be easy to conclude the same fact about the long line as well, however that would be a mistake.

Lemma 1: Every increasing sequence converges in the Long Line.

Proof: Suppose $(x_n)$ is an increasing sequence in the long line. Now consider the first element of each term of our sequence (remember elements of the long line are doubles, the first being the ordinal, and the second being the decimal part). Let $(\alpha_n)$ be the sequence of first elements. Therefore $(\alpha_n)$ is an increasing sequence of ordinal numbers. Now I will present it as fact that every increasing sequence of ordinal numbers has a limit point. Also $\Omega$ can never be the limit point of a sequence of countable ordinals. Therefore $(\alpha_n)$ must converge to a countable ordinal and therefore an ordinal that is represented in the long line. Now, if $(\alpha_n)$ never reaches a point where it remains constant, then we never have to consider the decimal part of the sequence since the limit point of the sequence of ordinals together with 0 will be the limit point of our sequence. So suppose that eventually $(\alpha_n)$ becomes a constant sequence. Let $\alpha'$ be the eventual constant term. Now we will consider the sequence of decimal parts of all terms after the sequence becomes constant in terms of the ordinals. Let $(d_m)$ be this sequence. Since $\lbrack 0,1)$ is bounded and $(d_m)$ must be increasing, it is easy to conclude that it converges, possibly to 1 in which case we take the point $(\alpha'+1,0)$ as our limit point for the original sequence. Therefore we can conclude that every increasing sequence converges in the long line. $\square$

Now amazingly with this one fact we glean even more information about the long line. For instance the long line is sequentially compact. First a quick definition, a topological space is sequentially compact if every sequence in the space has a convergent sub-sequence. Before I prove this I will prove a quick lemma about sequences in a totally ordered set.

Lemma 2: Every sequence in a totally ordered set has a monotone sub-sequence.

Proof: Suppose $(X,\leq)$ is a totally ordered set. Now let $(x_n)$ be a sequence in $X$. Let $x_p$ be a peak of the sequence if for all $n\geq p : x_n \leq x_p$. Now clearly there are two cases to consider, either $(x_n)$ has infinitely many such peaks or it has finitely many. First suppose that $(x_n)$ has infinitely many peaks, $\{x_{n_1}, x_{n_2},\ldots \}$. Therefore we can take $(x_{n_p})$ as our sub-sequence and clearly by definition this sequence must be decreasing. Now suppose our sequence has only finitely many peaks. Therefore there is a last peak $x_{n_{0-1}}$. Now consider the term $x_{n_0}$. Since this term is not a peak there must exist another term $x_{n_1}$ which is greater than $x_{n_0}$. We can then find a term $x_{n_2} \geq x_{n_1}$ since $x_{n_1}$ was not a peak. We can continue this process, creating a sub-sequence $(x_{n_m})$ which is increasing. $\square$

Now we are ready to prove that the Long Line $L$ is sequentially compact.

Proof: Suppose $(x_n)$ is a sequence in $L.$ By the second lemma we know we can find a monotone sub-sequence $(x_{n_m})$. Now first suppose that $(x_{n_m})$ is increasing. Then by the first lemma $(x_{n_m})$ converges. Now suppose that $(x_{n_m})$ is decreasing. Now since the long line is bounded below we know that $(x_{n_m})$ must converge. So $(x_n)$ has a convergent sub-sequence. $\square$

So the long line is sequentially compact. Of course the next question to ask is if the long line is compact. Interestingly it is not. Now the topological definition is a little different then the one given in most calculus classes. A topological space $X$ is compact if every open cover $\mathscr{U}$ of $X$ has a finite sub-cover. Now a cover is just a collection of open sets where the union of the collection is equal to the entire space.

Lemma 3: The Long Line $L$ is not compact.

Proof: Consider the collection of open sets $\mathscr{U'} = \{ (\alpha, \alpha+1) : \alpha \in \Omega \}$. We can then add to this collection sets of the form $((\alpha,\frac{2}{3}),(\alpha+1, \frac{1}{3}))$ giving us a cover $\mathscr{U}$. To see that this is a cover just note that the only points $\mathscr{U'}$ only misses the points with no decimal part, and note that the added collection of sets catch all the ordinals with no decimal part. Finally note that if any set of $\mathscr{U}$ is removed, we will no longer have a cover of $L$ and since $\mathscr{U}$ is clearly infinite we can conclude that $L$ is not compact. $\square$

This then leads us to one more interesting aspect of the long line; the long line is not metrizable. Now before I can explain what a metrizable space is, I will give a brief description of a metric space. A metric space is a set together with a “distance” function that determines how far away two points are. Open sets are then the union of open balls, which is just the set of all points strictly less than some radius from a given point. For instance, the usual distance function, $d$, on $\mathbb{R}$ is just $d(a,b) = |a-b|$. Open balls then correspond to sets of the form $\{x\in \mathbb{R} : |a-x| < \epsilon\}$. Now a metrizable space is a topological space where one can create a distance function on the set that then creates precisely the same open sets that were in the original topology. Now metric spaces, and therefore metrizable spaces, usually have “nicer” properties than general topological spaces, especially when it comes to equivalent features. The property that interests us here is than in a metric space, and so a metrizable space, the concept of sequentially compact and compact coincide. In other words, if a metric space is compact, then it is sequentially compact, and likewise in reverse. So immediately we can see that the long line cannot be metrizable since it is sequentially compact but not compact. So it would be impossible to create a “distance” function, which made sense, on the long line which lead to the construction of all the open sets we have.

Now you may be wondering what’s the point of creating the long line. You may ask yourself why anyone should care. Aside from just being able to work with a weird topological space, the creation and examination of the long line has multiple benefits. First off, it gives us a concrete counter example to properties that seem so similar. If all you ever work with are metrizable spaces, you won’t ever be able to really see how sequentially compact and compact are different. The long line is just one example of the importance of searching for counter examples. One may think that it is possible for spaces to have some properties and not have others, but until a concrete counter example is created, it’s all just conjecture.

For more information on the long line refer to Counter Examples in Topology, Steen and Seebach.

Editor’s note: The author of this post Josh Hews was a student in the Fall 2014 Topology course at Colby College taught by Scott Taylor. Submissions to the blog of essays by and for undergraduates on subjects pertaining to geometry and topology are welcome. For more information see the “Submit and Essay” tab above.

This entry was posted in Uncategorized. Bookmark the permalink.

• ## Constant Sequences With Infinitely Many Limits

Posted on November 18, 2014 1:23 pm by formatted with Image Comment

Back in calculus, we were taught that any convergent sequence (${x_n}$) in ${\mathbb{R}}$ has exactly one limit. This statement is true, and you might have seen the proof before. But is this necessarily a case in non-${\mathbb{R}}$ spaces?

It turns out that this is still true in some non-${\mathbb{R}}$ spaces, but, as we will see later, not all.

But what are spaces where things behave strangely? First, let’s consider the following definition:

Definition: a space H is Hausdorff if for any two distinct points you pick, there are disjoint open sets containing them.

An example of a Hausdorff space is ${\mathbb{R}}$ (the real line). By a standard fact, we know that for any two distinct real numbers x and y, we can find disjoint open intervals containing them (another way to think of this: suppose that the distance between x and y is d. Start by letting ${{I_x}}$ be an open interval centered at x with radius d/2 and let ${{I_y}}$ be an open interval centered at y with radius d/2 as well. It is easy to observe that these two intervals are disjoint.).

It turns out that in every Hausdorff space, a convergent sequence has exactly one limit (as we will prove later). On the other hand, in a non-Hausdorff space, a constant sequence (which obviously converges) can have infinitely many limits!

It might be hard to image what non-Hausdorff spaces look like, so we will begin by introducing the concept of topological spaces.

Given a set X, (X, T) is a topological space exactly when these four conditions hold:

1. X ${\in}$ T

2. ${\emptyset}$ ${\in}$ T

3. If a finite number of sets are elements of T, then their intersection ${\in}$ T

4. If we have sets that are elements of T, then their union ${\in}$ T

and T is called a topology on X (don’t confuse it with topography). Elements of T are exactly open sets in (X, T).

Observation: A set can be both closed and open. By the definition, C is a closed set exactly when the complement of C is open. For any given set X and topology T on X, since X and ${\emptyset}$ are in T, they are open sets in the space (X, T). Thus, their complements, ${\emptyset^c}$ = X and ${X^c}$ = ${\emptyset}$ are both closed.

The picture below represents a (X, T) topological space, where X = {1,2} and T = {ø, {1},{2},{1,2}}. It is easy to check that this is a Hausdorff space.

Before we move on to examples of sequences in non-Hausdorff topological spaces with multiple limits, let’s recall the definition of a limit of a sequence.

Definition: x is a limit of sequence (${x_n}$) if and only if for any open set U containing x, eventually there is a term of (${x_n}$) in U such that all the succeeding terms of (${x_n}$) are in U as well.

2 Examples are given here:

Example 1:

Let F be {1, 2, 3} and T = {${\emptyset}$, {1, 2}, F}. T satisfies all the 4 conditions, so it is a topology on set F. Obviously, (F, T) is not Hausdorff. Consider 1 and 2. Open sets containing 1 are exactly those that contain 2. Thus, regardless of your choice of the pair of open sets containing 1 and 2, the intersection is never empty.

Let (${x_n}$) be a constant sequence such that ${x_n}$ = 1 for every n. For any open set containing 1 (there are 2 of them: ({1,2} and F), every term of (${x_n}$) is in the open set, thus, (${x_n}$) converges to 1. On the other hand, since open sets containing 1 are exactly ones that contain 2, (${x_n}$) also converges to 2. It is easy to see that the open set containing 3 also contains all terms of (${x_n}$). Thus, the set of limits of (${x_n}$) is {1, 2, 3}.

Example 2:

Let’s consider a more interesting example. Let X = ${\mathbb{N}}$ (the set of all natural numbers), and let T = {${\emptyset}$, X}. Obviously, T is a topology on X (${\textbf{note:}}$ for any set X, T = {${\emptyset}$, X} is called an indiscrete topology on X). Clearly, this is not Hausdorff.

Let (${x_n}$) be a constant sequence such that ${x_n}$ = 1 for every n. Let j be an arbitrary natural number. Since every open set in the space (X, T) containing j contains all terms of (${x_n}$), j is a limit of (${x_n}$). Thus, every natural number is a limit point of (${x_n}$) in (X, T). This points out that the set of limit points does not even need to be finite!

Intuitively, the result of this example may seem contradictory, since the given sequence is constant but is also “arbitrarily” close to infinitely many points. This shows that things could behave bizarrely in non-Hausdorff spaces.

Convergent sequences and their limits in Hausdorff spaces

After seeing these two examples, one might wonder if a convergent sequence in a Hausdorff topological space always has exactly one limit. It turns out that this is true.

Let (X, T) be a Hausdorff topological space and (${x_n}$) be a convergent sequence in the space, we’ll show that it has exactly one limit.

We’ll prove our claim by contradiction. In other words, we’ll assume that our claim is false and show that such assumption can’t be true.

For contradiction, suppose that (${x_n}$) has two distinct limits x and y in X. Since the space is Hausdorff, there are open sets ${U_x}$ and ${U_y}$ containing x and y respectively, and the intersection ${U_x}$ ${\cap}$ ${U_y}$ = ${\emptyset}$ Since (${x_n}$) converges to x, there is ${x_{n_k}}$ ${\in}$ ${U_x}$ such that all the suceeding ${x_n}$ are in ${U_x}$.

Similarly, since (${x_n}$) converges to y, there is ${x_{n_m}}$ ${\in}$ ${U_y}$ such that all the suceeding ${x_n}$ are in ${U_y}$. There are 2 cases:

case1: ${n_{k}}$ ${\geq}$ ${n_{m}}$ ${\longrightarrow}$ ${x_{n_k}}$ is in both ${U_x}$ and ${U_y}$

case2: ${n_{k}}$ ${\textless}$ ${n_{m}}$ ${\longrightarrow}$ ${x_{n_m}}$ is in both ${U_x}$ and ${U_y}$

Thus, ${U_x}$ ${\cap}$ ${U_y}$ ${\neq}$ ${\emptyset}$, which is a contradiction.

This points out that our assumption is false, and (${x_n}$) must have exactly one limit in X

Since the space and the sequence are arbitrary, any convergent sequence in a Hausdorff space has exactly one limit.

Convergent sequences and their limits in “weakened” Hausdorff spaces

In mathematics, changing hypothesis can drastically change the result, and the idea that we are exploring here is not an exception. Although a convergent sequence in any Hausdorff space has the unique limit, a convergent sequence in a “weaker” Hausdorff space can have many limits!

Definition: a space H is T1 if for any two distinct points, each has a neighborhood which does not contain the other point.

We can observe that this is weaker than the definition of a Hausdorff space, since the neighborhoods are not required to be disjoint. If for each pair of points, there are neighborhoods that happen to be disjoint, then this T1 space is also a Hausdorff space. However, that does not have to be a case. Obviously, every Hausdorff space is also T1, but not the other way around.

But how does using a weaker condition affect the behavior of convergent sequences? As we have seen, a convergent sequence in any Hausdorff space has exactly one limit, and a convergent sequence in a non-Hausdorff space may have many limits, but what can we say about a convergent sequence in a T1 space?

It turns out that it is possible to find a T1 space where a convergent sequence has infinitely many limits! Let’s consider the following example: space (X, T) when X = ${\mathbb{N}}$ and T = {${O}$ $\subset$ ${\mathbb{N}}$${O^c}$ is finite} $\cup$ {$\emptyset$}

Proving that this is a topological space is not hard, and we will skip it to discuss more interesting results.

First, we will show that (X, T) is a T1 space. Let a,b be distinct points of X. Since X\{a} and X\{b} have finite complements, they are elements of T. Given that X\{a} contains b but not a and X\{b} contains a but not b, (X, T) is a T1 space.

Consider a sequence (${x_n}$) in (X, T) where ${x_n}$ = n for each n ${\in}$ ${\mathbb{N}}$. We will show that every natural number is a limit point of (${x_n}$). Let j be an arbitrary natural number and let ${U_j}$ be an open set containing j. Since (${U_j}$) is an element of T, the complement of (${U_j}$) is finite. In other words, C(${U_j}$) is either ${\emptyset}$ or {${n_1}$, ${n_2}$, …, ${n_k}$} (where these ${n_j}$ are natural numbers). Without loss of generality, we can assume that, in the second case, ${n_k}$ is the biggest element of such finite set.

If C(${U_j}$) is ${\emptyset}$, then ${U_j}$ contains all the natural numbers. Thus, it contains every term of the sequence (${x_n}$).

On the other hand, if If C(${U_j}$) is {${n_1}$, ${n_2}$, …, ${n_k}$}, then ${U_j}$ contains all n > ${n_k}$. Equivalently, for all n > ${n_k}$, ${x_n}$ is contained in ${U_j}$.

${U_j}$ is arbitrary, so (${x_n}$) converges to j.

But j is also arbitrary, so the sequence (${x_n}$) converges to all natural numbers.

Question:

We’ve seen that every convergent sequence in any Hausdorff space has exactly one limit and that there are non-Hausdorff spaces where a convergent sequence can have more than one limit. Is it possible to have a convergent sequence in a non-Hausdorff space with exactly one limit?

Saran was a student in Scott Taylor’s Fall 2014 Topology course at Colby College.

References

http://math.stackexchange.com/questions/901154/unique-limits-in-t1-spaces

http://en.wikipedia.org/wiki/Interior_(topology)#mediaviewer/File:Interior_illustration.svg

https://dragonflytraining.files.wordpress.com/2013/10/man-with-question-01.png

This entry was posted in Uncategorized and tagged , . Bookmark the permalink.