This site contains an online textbook as well as other mathematical content. Created and run by Peter Saveliev.

Topology

From Intelligent Perception

(Redirected from Betti numbers)
Jump to: navigation, search

1 Topology vs Algebra vs Geometry

In an attempt to capture the essence of Topology in a single sentence, we usually say that Topology is the science of spatial properties that are preserved under continuous transformations. To elaborate a bit, you can bend, stretch, and shrink but not tear or glue.

In order to illustrate this idea in context of Mathematics as a whole, let's take a look at these delicious donuts:


TOPOLOGY
Topology-algebra-geometry 1.png
Count: One, two, three, four, five,... six!


ALGEBRA
Topology-algebra-geometry 2.png
Compute: Three times four... is twelve!


GEOMETRY
Topology-algebra-geometry 3.png
Measure: Seven... eighths!


In order to see how Topology is necessary for counting, consider the fact that the first step is to recognize that these are separate – disconnected from each other -- objects! Furthermore, to count the holes we need to recognize them as a different kind of topological feature. In fact, counting, computing, and measuring are all preceded by our ability to see the topology in these pictures.

As we shall see, Topology is the science of spatial properties that don't involve measuring.

Now, to answer “why do we need to study Topology?” we start with a few elementary examples. They come from four seemingly unrelated areas: vision and computer vision, cosmology, data analysis, and the theory of social choice.

2 The integrity of everyday objects

In order to be able to delegate some of the decision making to computers, one has to start by describing what he intuitively understands in absolutely unambiguous terms.

In industrial settings, one might need to consider the integrity of objects being manufactured or inspected.

The first question may be: this bolt is supposed to hold two things together, does it still or is there a crack in it?

Crack.jpg

In other words: would the bolt hold a hair or might it slip through?

The second question may be: this sheet of material is supposed to stop a flow of liquid, is it still water-tight or is there leakage?

Sponge.png

In other words: would the sheet hold water or might some permeate through?

The third question may be: to be strong this alloy is supposed to be solid, is it still or are there air bubbles?

Microstructure.jpg

In other words: would the alloy hold no air or might some get in?

It is important to understand now that these are three different kinds of integrity loss as there may be a crack but no hole or vice versa, etc:

Different kinds of integrity loss.png

We can describe these three situations informally as follows. The objects have:

  • cuts, or
  • tunnels, or
  • voids.

Of course, the presence of these features doesn't have to mean that the object is defective, such as those: a rope, a bucket, and paint. The examples of objects that are intended to have these three topological features are respectively: sliced bread, a strainer, and a balloon.

Different kinds of integrity features intended.png

Next, we will classify these three types of “defects”, according to their dimensions.

To understand why and how, let's recall from elementary geometry (or linear algebra) the list of $0$-, $1$-, and $2$-dimensional spaces:

  • 0. points,
  • 1. lines,
  • 2. planes.
Points, lines, and planes.png

If these spaces allowed to be deformed, the list becomes:

  • 0. points,
  • 1. curves,
  • 2. surfaces.
Points, curves, and surfaces.png

Some of those are special in the sense that they have no end-points or edges, i.e., there are no boundaries, such as these:

  • 0. point,
  • 1. circle,
  • 2. sphere.
Points, curves, and surfaces as cycles.png

These, and their deformed versions, are called cycles. Meanwhile, objects that have no such features are called acyclic.

Finally, our conclusions.

$\bullet$ 0. Any two points form a $0$-cycle and, since this is the simplest example of a cut, the latter is a $0$-dimensional feature:

Two points cut apart.png

$\bullet$ 1. Any circle is a $1$-cycle and, since this is the simplest example of a tunnel, the latter is a $1$-dimensional feature:

Looking through circle.png

$\bullet$ 2. Any sphere is a $2$-cycle and, since this is the simplest example of a void, the latter is a $2$-dimensional feature:

Head inside sphere.png

Exercise. Using this terminology, describe the topology of: a basketball, a football, a cannonball, a doughnut, an inner tire, a steering wheel, a bicycle wheel, a potter's wheel, a fingerprint, a tree, an envelope.

Exercise. Suggest your own examples of topological issues in everyday life and describe them using this terminology.

What about continuous transformations?

Breaking a bolt is not continuous but welding it back together is. Digging a tunnel (all the way) through a wall is not continuous but filling it shut is. Piercing a bubble is not continuous but patching it is. Bread is cut, tires are punctured, paper is folded, fabric is sowed into a suit or an airbag, etc etc.

As these examples show, even continuous transformations can create and remove topological features.

Exercise. Describe what happens to the three topological features in the above examples.

Sometimes topology is changing with time. For example, this is how the amoeba reproduces and that is how it feeds:

Amoeba.png

Exercise. Describe, in precise terms, what happens to the amoeba's topology and indicate which stages of development are continuous and which aren't.

3 The shape of the Universe

What is the shape of the Universe? What is its topology? Does the Universe have “cuts”, “tunnels”, or “voids”?

Looking around we don't observe any of these! But remember how, hundreds of years ago, sailors started to notice the curvature of the horizon? And later they proved -- by around-the-world travel and later by orbiting -- that the surface of the Earth encloses something inside?

As for the Universe, what we know is that we are not living in the flat world of Euclid and Newton - we are living in the curved world of Riemann and Einstein:

Curved universe.png

But the Universe that curves and bends here might curve and bend everywhere! Then, no matter how small the bent it, it might close on itself:

Bent universe is cyclic.png

It may be possible then to travel in a straight line and arrive to the starting point from the opposite direction. In fact, the light of the sun may come to us from an unexpected direction and, as a result, appear to come from a distant star:

Sun and you.png

Events of this kind would provide us with clues about the topology of the Universe. We have to rely on such indirect observations because we can't step outside and take a look at it:

You and god.png

Since we have to stay inside our Universe, we can't see its “cuts”, “tunnels”, or “voids”. The only way we can discover its structure is by traveling or by observing others -- such as light or radio waves -- travel.

If multiple universes exist but we have no way of traveling there, we can't confirm their existence. So much for $0$-cycles...

Traveling in various directions and coming, or not coming, back will produce information about loops in space. These loops, or $1$-cycles, are used to detect tunnels in the Universe.

There might also be voids and, since the Universe is $3$-dimensional, it might also have $3$-dimensional topological features. Studying these features would require us to add to the list: point, line, and plane, a new item, space, as in $3$-dimensional space. How such a space creates a $3$-cycle may be hard or impossible to visualize. However, these cycles are still detectable -- with the methods presented in this book.

Example. What if the Universe is like a room with two doors and, as you exit one door, you enter the other? You'll realize that, in fact, it's the same door! If you look through this door, this is what you see:

View through quotient door.png

$\square$

Exercise. What is the dimension of this feature?

Exercise. What if, as you exit one door, you enter the other -- but upside down? Sketch what you would see.

Elsewhere we have to face even higher dimensions...

4 Data patterns

Data lives outside of our tangible, physical, $3$-dimensional world.

Suppose we conduct an experiment that consists of a set of $100$ different measurements. We would like to make sense of the results. First, we put the experiment's results in the form of a string of $100$ numbers. Next, thinking mathematically, we see this string as a point in the $100$-dimensional space. Now, if we repeat the experiment $1000$ times, the result is a “point cloud” of $1000$ points in this space:

Point cloud of the plane.png

Now, as scientists we are after patterns in data. So, is there a pattern in this point cloud and maybe a law of nature that has produced it? What is the shape behind the data?

Point clouds.png

But our ability to see is limited to dimension 3!

Exercise. What is the highest dimension of data your spreadsheet software can visualize? Hint: colors.

With this limited ability to visualize, we still need to answer the same questions about the shape behind the point cloud:

  • Is it one piece or more?
  • Is there a tunnel or a void?
  • And what about possible $100$-dimensional topological features?

Once again, we can't step outside and take a look at this object.

The first question is very important as it is the question of classification: drugs, customers, movies, species, web sites, etc. The methods for solving this problem -- often called “clustering” -- are well developed in data analysis:

Three clusters.png

The rest of the questions will require topological thinking. The methods for solving this problem are presented in this book: we will record cycles of all dimensions in the data and, through purely algebraic procedures, detect its topological features:

Triple torus homology.png

They are called homology classes.

Example. Here is an example of data analysis one can do without a computer. Imagine you are walking through a field of flowers: daffodils, lilies, and forget-me-nots. You are blindfolded but you can detect the smells of the flowers as you walk, in this order:

  • daffodils only, then
  • daffodils and lilies, then
  • lilies only, then
  • lilies and forget-me-nots, then
  • forget-me-nots only, then
  • daffodils and forget-me-nots,
  • daffodils only again.

Now, thinking topologically you might arrive to an interesting conclusion: there is a spot in the field with either

  • none of these types of flowers, or
  • all three types.

The reason why is illustrated below:

Flower field.png

Of course, the conclusion fails if any of the types grows in several separate, disconnected, patches.

$\square$

Exercise. What if the patches are connected but might have holes in them?

5 Social choice

Next, we present examples of how the presence of topological features in the space of choices may cause some undesirable outcomes.

Suppose the owner of a piece of land needs to decide on the location for his new house based on a certain set of preferences. Suppose the land varies in terms of its qualities: grass/bush/forest, hills/valleys, wet/dry, distance to the road/river/lake, etc. If the landowner only had a single criterion for his choice, it would be simple; for example, he would choose the highest location, or the location closest to the river, or to the road.

House locations.png

However, what if, because of this variety of locations and the complexity of the issues, the owner can only decide on the relative desirability of locations, and only for locations in close proximity to each other? Is it possible to make a decision, a decision that satisfies his preferences?

Suppose first that the piece of land consists of two separate parcels. Then no two sites located in different parcels are nearby! Therefore, the comparison between them is impossible and the answer to our question is No. This observation suggests that the question may be topological in nature.

What if the land parcel is a single piece but there is lake in the middle? We will prove in this book that the answer is still No.

Ideally, the preferences are captured by a single number assigned to each location: the larger its value the better the choice. These numbers form what's called a “utility function”:

House locations and values.png

This function may have a monetary meaning in the sense that building the house will increase the value of the real estate by an amount that depends on the chosen location.

We will prove that there is always a utility function, but only when the piece of land is known to be acyclic.

What prevents us from constructing such a function for a non-acyclic parcel? Let's consider a piece of land that is a thin strip along a triangular lake. Suppose the locations within any of the three sides of the triangle are comparable but there is no comparison between the edges:

House location on the triangle.png

The result could be a cyclic preference!

Such preferences are seen elsewhere. A small child may express, if asked in a certain way, a circular preference for a Christmas present: $$bike \quad > \quad videogame \quad > \quad drum\ set \quad > \quad bike \quad > \quad ...$$

In another example, suppose we have three candidates, $A$,$B$, and $C$, running for office and there are three voters with these preferences: $$\begin{array}{c|c|c|c} & First \ choice & Second\ choice & Third\ choice \\ \hline Voter\ 1: & A & B & C\\ Voter\ 2: & B & C & A\\ Voter\ 3: & C & A & B\\ \end{array}$$ Who won? Is it candidate $C$? No, because one can argue that $B$ should win instead as two voters ($1$ and $2$) prefer $B$ to $C$ and only one voter ($3$) prefers $C$ to $B$. Then, the same argument proves that $A$ is preferred to $B$, and then $C$ is preferred to $A$. Our conclusion is: sometimes a seemingly reasonable interpretation of collective preferences can be cyclic, even if the preferences of individual voters are not.

And let's not forget about: $$rock\quad > \quad paper \quad > \quad scissors \quad > \quad rock \quad > \quad ...$$

Exercise. Think of your own examples of cyclic preferences, in food, entertainment, or weather.

This is not to say that these preferences are unreasonable but only that they cannot be captured by a utility function. In particular, we can't assign dollar values to the locations when the preferences are cyclic. We are also not saying that there is no way to make a choice when there is a lake in the middle of the parcel but only that we can't guarantee that it will always be possible. Suppose next that it is.

Suppose the landowner is able to make a location choice based on his preferences, or in some other way. What if, however, the landowner's wife has a different opinion? Can they find a compromise?

The goal is to have a procedure ready before their choices are revealed. The idea is that as the two of them place -- simultaneously -- two little flags on the map of the land, the decision is made automatically:

  • to every pair of locations $A$ and $B$, a third, compromise, location $C$ is assigned ahead of time.

The obvious method is: chose the midpoint. However, just as before, this method fails if the land consists of two separate parcels.

Forests.png

Exercise. Sometimes this midpoint method fails even if the parcel isn't disconnected, such a U-shape. Find an alternative solution.

We already know that the next question to ask is, is it always possible to find a fair compromise when there is a lake in the middle? The method may be: choose the midpoint as measured along the shore. However, what if they choose two diametrically opposite points? Then there are two midpoints!

An amended method may be: choose the midpoint and, in case of diametrically opposite choices, go clockwise from $A$ to $B$. This method, however, treats the two participants unequally...

Exercise. Suggest your own alternative solutions.

Again, we can guarantee that such a fair compromise-producing procedure is possible but only if the land parcel is known to be acyclic. This subtle result will be proven in this book. The result implies that there may be a problem when a jointly owned satellite is to be placed on a (stationary) orbit. We will also see how these topological issues create obstacles to designing a reasonable electoral system.

This isn't the end of the story though... Suppose the husband and wife have placed their little flags, $A$ and $B$, on the map of their land and then applied the designed in advance procedure to place a third flag, $C$, for the compromise location. Imagine now that as the wife leaves the room, the husband moves his flag in the direction away from the wife's. Then he also moves flag $C$ as well to preserve the appearance of a fair compromise. As a result of this manipulation, flag $C$ is now closer to the husband's ideal location!

Midpoint compromise 2.png

However, as the husband leaves the room, the wife enters and makes a similar move! And the game is on...

Such a backward movement resembles the tug of war.

Now, as the game goes on, one of them reaches the edge of the parcel. Then he (or she) realizes that there is no further advantage to be gained. While the other person continues to improve her (or his) position, eventually she (or he) too discovers that she (or he) is not gaining anything by moving further back. It's a stalemate!

Exercise. Try this game yourself -- on the square and other shapes -- using the midpoint method for finding the compromise location. What if the “compromise” is chosen to be twice as close to your ideal location than to the other?

This stalemate is thought of as an equilibrium of the game. Indeed, neither can improve one's position by a unilateral action.

Again, we can guarantee that such an equilibrium exists but only if the land parcel is known to be acyclic. We will demonstrate how the topology behind this situation applies to other games as well as the equilibrium of a market economy.

Exercise. Try to play this game on the shore of a lake using the amended midpoint method described above. Show that there is no equilibrium.