Now on ScienceBlogs: The Festival Recognizes Our First "Featured Fan"!

ScienceBlogs Book Club: Inside the Outbreaks

Good Math, Bad Math

Finding the fun in good math; Shredding bad math and squashing the crackpots who espouse it.

Search

Profile

markcc.jpg
Mark Chu-Carroll (aka MarkCC) is a PhD Computer Scientist, who works for Google as a Software Engineer. My professional interests center on programming languages and tools, and how to improve the languages and tools that are used for building complex software systems.

Donors Choose

Other Information

Add this blog to my Technorati Favorites!

Recent Posts

Recent Comments

Categories

Blogroll

Old Topic Indices

Great Online Books

« Introducing Topology | Main | Topological Spaces »

Metric Spaces

Category: topology
Posted on: August 23, 2006 7:46 PM, by Mark C. Chu-Carroll

Topology usually starts with the idea of a metric space. A metric space is a set of values with some concept of distance. We need to define that first, before we can get into anything really interesting.

Metric Spaces and Distance

What does distance mean?

Let's look at a set, S, consisting of elements s1, s2, s3,...,sn. What does it mean to measure a distance from si to sj?

We'll start by looking at a simple number-line, with the set of real numbers. What's the distance between two numbers x and y? It's a measure of how far over the number-line you have to go to get from x to y. But that's really circular; we've defined distance as "how far you have to go", which is defined by distance. Let's try again. Take a blank ruler, and put it next to the numberline, so that the left edge of the ruler is on X, and then draw a mark on the ruler where it touches Y. The length of the ruler up to that mark is the distance from x to y. The reason that this one isn't circular is because now, you can take that ruler, and use it to answer the question: is the number v farther from the number w than x is from y? Because the ruler gives you a metric that you can use that is separate from the number-line itself.

metric-ruler.jpg

A metric over S is a function that takes two elements si and sj, and returns a real number which measure the distance between those two elements. To be a proper metric, it needs to have a set of required properties. To be formal, a function d : S × S → ℜ is a metric function over S if/f:

  1. ∀ si, sj ∈ S: d(si,sj) = 0 if/f i=j. (the identity property)
  2. ∀ si, sj ∈ S: d(si,sj) = d(sj,si) (the symmetry property)
  3. ∀ si, sj, sk ∈ S: d(si,sk) ≤ d(si,sj) + d(sj,sj) (the triangle inequality property)

Some people also add a fourth property, called the non-negativity property; I prefer to leave it out, because it can be inferred from the others. But for completeness, here it is: ∀ si, sj ∈ S: d(si,sj) ≥ 0.

A metric space is just the pair (S,d) of a set S, and a metric function d over the set.

For example:

  1. The real numbers are a metric space with the ruler-metric function. You can easily verify that properties of a metric function all work with the ruler-metric. In fact, they are are all things that you can easily check with a ruler and a number-line, to see that they work. The function that you're creating with the ruler is: d(x,y) = |x-y| (the absolute value of x - y). So the ruler-metric distance from 1 to 3 is 2.
  2. A cartesian plane is a metric space whose distance function is the euclidean distance:
    d((ax,ay), (bx,by)) = ((ax-bx)2 + (ay-by)2 )1/2.
  3. In fact, for every n, the euclidean n-space is a metric space using the euclidean distance.
  4. A checkerboard is a metric space if you use the number of kings moves as the distance function.
  5. The Manhattan street grid is a metric space where the distance function between two intersections is the sum of the number of horizontal blocks and the number of vertical blocks between them.

Open and Closed Sets in Metric Spaces

You can start moving from metric spaces to topological spaces by looking at open sets. Take a metric space, (S,d), and a point p∈S. An open ball B(p,r) (a ball of radius r around point p) in S is the set of points x such that d(p,x) < r. (note: originally, this paragraph contained a major typographic error: I wrote ≤ rather than <, which causes a significant change in meaning. As usual, thanks to the commenter who caught it!)

Now, think of a subset T of S. A point p ∈ S is in the interior of T if/f there is some r where B(p,r) ∈ T. T is an open subset of S if every element of T is in its interior. A subset of space formed by an open ball is always an open subset. An open subset of a metric space S is also called an open space in S.

Here's where we can start to do some interesting things, that foreshadow what we'll do with topological spaces. If you have two open spaces T and U in a metric space S, then T ∪ U is an open space in S. So if you have open spaces, you can glue them together to form other open spaces.

In fact, in a metric space S, every open space is the union of a collection of open balls in S.

In addition to the simple gluing, we can also prove that every intersection of two open subsets is open. In fact, the intersection of any finite set of open subsets form an open subset. So we can assemble open spaces with all sorts of bizarre shapes by gluing together collections of open balls, and then taking intersections between the shapes we've built.

So now, think about a subspace T of a metric space S. We can say that a point p is adherent to T if for all r > 0, B(p,r)∩T≠∅. The closure of T (usually written as T with a horizontal line over it; sometimes written as T* by computer scientists, because that's the closure notation in many CS subjects). is the set of all points adherent to T. (note: a typo was corrected in this paragraph. Thanks to the commenter who caught it!)

A subset T of S is called a closed subset if/f T=T*. Intuitively, T is closed if it contains the surface that forms its boundary. So in 3-space, a solid sphere is a closed space. The contents of the sphere (think of the shape formed by the air in a spherical balloon) is not a closed space; it's bounded by a surface, but that surface is not part of the space.

Share on Facebook
Share on StumbleUpon
Share on Facebook

Comments

1

Typo watch:

- the last term in property 3 of a metric reads d(sj,sj), but should read d(sj,sk)

- the definition of the open ball didn't use the strict inequality

Posted by: Canuckistani | August 23, 2006 9:20 PM

2

Also, I assume that when you're defining the adherent property, you meant to say "We can say that a point p is adherent to T if for all r > 0, B(p,r)∩T≠∅". You didn't define any set O, and T is the only part that makes sense anyway.

You may want to expand that line a touch in any case, to really indicate what you're trying to say. I knew what a closed set was, but I didn't immediately get it from your definition. Basically, without my existing knowledge of sets that do/do not contain their own boundaries, I wouldn't have understood the significance of the adherence property.

Posted by: Xanthir | August 23, 2006 9:29 PM

3

The most intuitive definition of open and closed sets that I know is based on boundaries: an open set contains none of its boundary, while a closed set contains it all. It takes a bit of work to prove equivalence, though. If you define an open set using the usual metric definition, then I think the easiest way to define closed sets is as co-open sets.

By the way, is it common to say that a point is adherent to T? Before reading this post, I'd only encountered the terms limit/accumulation/cluster point, i.e. a point is an accumulation point of T.

Posted by: Alon Levy | August 23, 2006 9:35 PM

4

You shouldn't use subscripts with the definition of metric
$d(s_i,s_j)$ etc. The metric space is usually not countable. It's cleaner without em anyway.
For all $x,y,z \in S$
1. $d(x,x) =0$
2. $d(x,y) =d(y,x)$
3. $d(x,y)+d(y,z) \ge d(x,z)$

Posted by: elspi | August 23, 2006 11:11 PM

5

Any recommendations for a topology text?

Posted by: andy.s | August 23, 2006 11:22 PM

6

The arguments here are similar to ones in the first few pages of principles of mathematical analysis of Rudin.
It's a small book, and is popular as text book I think (at least, I used it at university not so long ago ;) ). But I now see that it is very expensive at the online shops like amazon (115$), but still a very good deal on ebay (~5$ + shipping ... ). Probably it would be at the public library as well.


Posted by: crf | August 24, 2006 12:21 AM

7

Rudin's books about real analysis are classics, but do they ever deal with topology outside the context of metric spaces?

Posted by: Alon Levy | August 24, 2006 1:29 AM

8

@ Mark: Just to reiterate Canuckistani's point, you've described the closed ball not the open one. The open ball radius r at p in S is all points x such that d(p,x)

@ elspi: I don't see any harm in using subscripts in describing a metric space. Many (most?) metric spaces are uncountable, but they certainly all contain countable sequences and subsets as well as finite sequences and subsets. In fact, Mark's example set, S, is finite (dimension n). There's no harm in showing the operations of the distance function with respect to this set since there's no implication that countability or finiteness is required.

@ Alon: I'm with you on the the word "adherent". "Accumulation point" and "limit point" are certainly more common, though you should be careful b/c "cluster point" is usually used in connection with sequences and is therefore a specific type of limit/accumulation point (i.e. x is a cluster point of sequence {xi} if ∀ ε>0 ∃ N(ε) such that n > N ⇒ d(x,xn) < ε).

Posted by: billb | August 24, 2006 10:47 AM

9

Dagnabbit! Whenever you put in a less-than sign using html entities and do a preview, it actually converts everything in the text entry box into those entities, so the AMPERSAND-L-T-SEMICOLN gets literally replaced with a regular < which if you don't convert back to AMPERSAND-L-T-SEMICOLN will screw up the markup everywhere.

The last bit of my first paragraph should be "d(p,x) < r".

Posted by: billb | August 24, 2006 10:57 AM

10

Andy: I would recommend "Topology" by James Munkres. It was used as a text in a point-set topology course I took last year and I found it to be quite good. (The second edition, published in 2000, has two parts; Part I is all you really need from that book. Part II is on algebraic topology, but it's an incomplete treatment, and once you've made it that far, you'd be better served by a more advanced text.)

Alon is right about Rudin's books. His lower-level book, Principles of Mathematical Analysis, has a chapter on metric topology and that's about it. His higher-level book, Real + Complex Analysis, defines a topological space and proves one relevant lemma (Urysohn's), and that's it.

Posted by: numerophile | August 24, 2006 11:07 AM

11

Rosenlicht's book Introduction to Analysis is a very readable text, done using metric spaces, and costs a mere $10. I highly recommend it.

Posted by: carey allen | August 24, 2006 5:29 PM

12

Billb, I think you defined a cluster point wrongly. As it stands, you've defined the limit of a sequence. A cluster point of a sequence a(n) is a point x such that for every e > 0, there exists i such that d(x, a(i))

Posted by: Alon Levy | August 24, 2006 5:49 PM

13

Mark:
"4. A checkerboard is a metric space if you use the number of kings moves as the distance function."

But a king moves one square in any direction. Since d((1,1),(2,1)) + d((2,1),(2,2)) - d((2,2),(1,1)) = 1 + 1 - 1 = 1 ≠ 0 = d((1,1),(1,1)), I can't see how an ambigious d can be a metric function.

Alon:
"By the way, is it common to say that a point is adherent to T?"

I'm with you and billb here, limit point it was. (IIRC, I haven't that book handy.)

Posted by: Torbjörn Larsson | August 24, 2006 9:33 PM

14

" Since d((1,1),(2,1)) + d((2,1),(2,2)) - d((2,2),(1,1)) = 1 + 1 - 1 = 1 ≠ 0 = d((1,1),(1,1)), I can't see how an ambigious d can be a metric function."

Ahh...I don't get that. For Euclidean distance the fact that
d(1,1),(2,1) + d(2,1)(2,2) - d(2,2)(1,1) isn't 0 and not equal d(1,1)(1,1) is of course also true.

Posted by: Markk | August 24, 2006 11:56 PM

15

Yes, of course, I initially saw that the king/checkerboard metric fulfilled the triangle inequality property. Indeed, I should have checked my calculation on the normal metric.

It is of course a discrete metric, I see that now. Cute.

Thanks!

Posted by: Torbjörn Larsson | August 25, 2006 12:24 AM

16

It doesn't have to be a discrete metric, Torbjörn. Just like the taxicab metric can be made continuous by letting d((x1, y1), (x2, y2)) = |x2 - x1| + |y2 - y1|, so you the checkerboard metric be made continuous by, intuitively, making the metric distance between two points the shortest total length of horizontal, vertical, and 45-degree-diagonal lines connecting them. More precisely, if you define m to be min{|x2 - x1|, |y2 - y1|} and M to be max{|x2 - x1|, |y2 - y1|}, then d = m*SQRT(2) + (M - m).

Posted by: Alon Levy | August 25, 2006 12:56 AM

17

Alon:

Ummm, it awakes some distant memories, and again I wish I had my topology book handy. Of course you can transform the metric, but I can't see that either of those two topologies gets continuous metrics unless the | | function makes some fancy moves when moving from one square to another.

This example of discrete to non-discrete I get (and it seems strangely familiar): "On the other hand, the underlying topology of a non-discrete uniform or metric space can be discrete; an example is the metric space X := {1/n : n = 1,2,3,...} (with metric inherited from the real line and given by d(x,y) = |x − y|)." ( http://en.wikipedia.org/wiki/Discrete_space )

We need a limit point, or more specifically a cluster point. :-)

Posted by: Torbjörn Larsson | August 25, 2006 2:22 AM

18

"We need a limit point, or more specifically a cluster point."

Duh! We need a limit point, but here it is a cluster point.

Posted by: Torbjörn Larsson | August 25, 2006 4:16 AM

19

"making the metric distance"

Duh! Okay, continuous it is.

Posted by: Torbjörn Larsson | August 26, 2006 11:18 PM

20

Sorry about being late to this thread. Just a comment about indexing: one does not have to index over a countable set. Actually, the "main" purpose of indexing is not served if one indexes over the countable Q.

best

Posted by: Romulo | February 12, 2007 6:19 PM

ScienceBlogs

Search ScienceBlogs:

Go to:

Advertisement
Follow ScienceBlogs on Twitter

© 2006-2011 ScienceBlogs LLC. ScienceBlogs is a registered trademark of ScienceBlogs LLC. All rights reserved.